Least Squares Temporal Difference Methods: An Analysis under General Conditions

By Huizhen Yu. 2012

51 citations recorded by the source corpus.

We consider approximate policy evaluation for finite state and action Markov de- cision processes (MDP) with the least squares temporal difference (LSTD) algorithm, LSTD(λ), in an exploration-enhanced learning context, where policy costs are computed from observations of a Markov chain different from the one corresponding to the policy under evaluation. We establish for the discounted cost criterion that LSTD(λ) converges almost surely under mild, minimal conditions. We also analyze other properties of the iterates involved in the algorithm, including convergence in mean and boundedness. Our analysis draws on theories of both finite space Markov chains and weak Feller Markov chains on a topological space. Our results can be applied to other temporal difference algorithms and MDP models. As examples, we give a convergence analysis of a TD(λ) algorithm and extensions to MDP with compact state and action spaces, as well as a convergence proof of a new LSTD algorithm with state-dependent λ-parameters.

Subfields: Artificial Intelligence, Management Science and Operations Research, Reinforcement Learning, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

In Reinforcement Learning

In Statistical Learning Theory

Citations in the corpus

Generalized Emphatic Temporal Difference Learning: Bias-Variance Analysis (2015, methodology): “In recent years, several different off-policy policy-evaluation algorithms have been studied, such as importance-sampling based least-squares TD (Yu, 2012), and gradient-based TD (Sutton et al., 2009; Liu et al., 2015).”
Emphatic TD Bellman Operator is a Contraction (2015, background): “In recent years, several different off-policy policy-evalu tion algorithms have been proposed and analyzed, such as importance-sampling based least-squareTD (Yu, 2012), gradient-based TD (Sutton et al., 2009), and ETD (Sutton et al., 2015).”
On Convergence of Emphatic Temporal-Difference Learning (2015, methodology): “For regular off-policy LSTD(λ) and TD(λ) (Bertsekas and Yu, 2009), it has been shown by Yu (2012) that the associated joint process of states and trace iterates exhibit useful properties, by which convergence results for LSTD(λ) can be derived.”
An Emphatic Approach to the Problem of Off-policy Temporal-Difference Learning (2015, neutral): “Nevertheless, in the function approximation case little attention has been paid in the literature to specifing the relative importance of different states (an exception is Thomas 2014), though there are intimations of this in the initiation set of options (Sutton et al. 1999).”
Off-policy learning with eligibility traces: a survey (2013, methodology): “Thus, the analyses of Yu (2010a) and Nedić and Bertsekas (2003) (for the convergence of Ni) imply the following convergence result: under the assumptions required for the convergence of off-policy LSTD(λ), and the additional assumption that the operator Π0T λ has a spectral radius smaller than 1…”
Emphatic Temporal-Difference Learning (2015, neutral): “The proof is similar to but more complex than the convergence proof for off-policy LSTD/TD (Yu 2012).”
Finite-Sample Analysis of Proximal Gradient TD Algorithms (2015, methodology): “This is standard in stochastic approximation algorithms and has been used in off-policy TD(λ) [Yu, 2012] and actor-critic algorithms (e.”
Unifying Task Specification in Reinforcement Learning (2016, neutral): “2010; Sutton et al., 2014; Yu, 2012).”
Approximate policy iteration: a survey and some new methods (2011, methodology): “c) In Yu [41, 42], for all λ ∈ [0, 1] and λ n ∑”
Q-learning and enhanced policy iteration in discounted dynamic programming (2010, background): “For example, some LSTD()type policy evaluation algorithms use the richer set of data thus obtained together with importance sampling to guarantee convergence (Bertsekas and Yu [13], Yu [50, 51]).”
Multi-step Off-policy Learning Without Importance Sampling Ratios (2017, background): “…to access or estimate the model of the environment and in that sense are model-free (Precup et al. 2000, 2001, Maei & Sutton 2010, Maei 2011, Yu 2012, Geist & Scherrer 2014, Dann et al. 2014, van Hasselt et al. 2014, Mahmood et al. 2014, Yu 2015, 2016, Hallak et al. 2015a, Mahmood et al.…”
Weak Convergence Properties of Constrained Emphatic Temporal-difference Learning with Constant and Slowly Diminishing Stepsize (2015, methodology): “, (16)It is not necessary to multiply the term φ(St)θt by ρt, and that version of the algorithm was the one given in [5, 51].”