  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.
