The Choice Function Framework for Online Policy Improvement
This work addresses a foundational issue in reinforcement learning and AI planning by ensuring reliable policy improvement, which is incremental as it builds on existing online search methods.
The paper tackles the problem of ensuring that online search procedures for sequential decision making do not degrade policy performance, even with perfect models, by introducing the choice function framework. It provides sufficient conditions for choice functions to guarantee non-worse performance and demonstrates empirical utility.
There are notable examples of online search improving over hand-coded or learned policies (e.g. AlphaZero) for sequential decision making. It is not clear, however, whether or not policy improvement is guaranteed for many of these approaches, even when given a perfect evaluation function and transition model. Indeed, simple counter examples show that seemingly reasonable online search procedures can hurt performance compared to the original policy. To address this issue, we introduce the choice function framework for analyzing online search procedures for policy improvement. A choice function specifies the actions to be considered at every node of a search tree, with all other actions being pruned. Our main contribution is to give sufficient conditions for stationary and non-stationary choice functions to guarantee that the value achieved by online search is no worse than the original policy. In addition, we describe a general parametric class of choice functions that satisfy those conditions and present an illustrative use case of the framework's empirical utility.