On-Line Policy Iteration for Infinite Horizon Dynamic Programming

Dimitri Bertsekas† Abstract 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. The common characteristic of these variants is that, in addition to being suitable for on-line implementation, they are simplified in two ways: (a) They perform policy improvement operations only for the states that are encountered during the on-line operation of the system.