On-Line Policy Iteration for Infinite Horizon Dynamic Programming
This incremental improvement addresses computational efficiency in dynamic programming for researchers and practitioners in optimization and control.
The paper tackles the problem of infinite horizon dynamic programming by proposing an on-line policy iteration algorithm that updates policies only for encountered states, enabling continuous improvement. It converges in finite stages to a locally optimal policy and suggests simplified variants for policy iteration and multiagent settings.
In this paper we propose an on-line policy iteration (PI) algorithm for finite-state infinite horizon discounted dynamic programming, whereby the policy improvement operation is done on-line, only for the states that are encountered during operation of the system. This allows the continuous updating/improvement of the current policy, thus resulting in a form of on-line PI that incorporates the improved controls into the current policy as new states and controls are generated. The algorithm converges in a finite number of stages to a type of locally optimal policy, and suggests the possibility of variants of PI and multiagent PI where the policy improvement is simplified. Moreover, the algorithm can be used with on-line replanning, and is also well-suited for on-line PI algorithms with value and policy approximations.