Convergence of Least Squares Temporal Difference Methods Under General Conditions
Huizhen Yu · Työväentutkimus Vuosikirja · 2010
We consider approximate policy evaluation for finite state and action Markov decision processes (MDP) in the off-policy learning context and with the simulation-based least squares temporal difference algorithm, LSTD(λ). We establish for the discounted cost criterion that the off-policy LSTD(λ) converges almost surely under mild, minimal conditions. We also analyze other convergence and boundedness properties of the iterates involved in the algorithm, and based on them, we suggest a modification in its practical implementation. Our analysis uses theories of both finite space Markov chains and Markov chains on topological spaces. 1. Overview We consider approximate policy evaluation for finite state and action Markov decision processes (MDP) in an exploration-enhanced learning context, called “offpolicy” learning. In this context, we employ a certain policy called the “behavior policy ” to adequately explore the state and action space, and using the observations of costs and transitions generated under the behavior policy, we may approximately evaluate any suitable “target policy ” of interest. This differs from the standard policy evaluation case – “on-policy ” learning – where the behavior policy always coincides with the policy to be evaluated. The dichotomy between the off-policy and on-policy learning stems from the exploration-exploitation tradeoff in practical modelfree/simulation-based methods for policy search. With their flexibility, off-policy methods form an important part of the model-free learning methodology (Sutton & Barto, 1998) and have been suggested as important