Convergence of Least Squares Temporal Difference Methods Under General Conditions

By Huizhen Yu. 2010

48 citations recorded by the source corpus.

How researchers see this paper

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

Citations in the corpus

An Emphatic Approach to the Problem of Off-policy Temporal-Difference Learning (2015, methodology): “Gordon (1995, 1996) proposed restricting attention to function approximators that are averagers, but this does not seem to be possible without storing many of the training examples, which would defeat the primary strength that we seek to obtain from parametric function approximation.”
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…”
Least Squares Temporal Difference Methods: An Analysis under General Conditions (2012, methodology): “Another entirely different proof based on the theory of e-chains [MT09] can be found in [Yu10]; however, it is much longer than the one given here.”
Scaling Up Robust MDPs by Reinforcement Learning (2013, background): “We note that a similar difﬁculty arises in off-policy RL [5, 18] (in fact, our Assumption 2 is similar to an assumption in [5]) , where some algorithms are shown to converge to a solution of (3) even when Π T π is not a contraction [20, 18].”
Incremental Off-policy Reinforcement Learning Algorithms (2017, methodology): “We compared the performance of WIS-LSTD(λ) with the conventional off-policy LSTD(λ) by Yu (2010) on two random-walk tasks for off-policy policy evaluation.”
Weighted importance sampling for off-policy learning with linear function approximation (2014, methodology): “The existing methods for off-policy value-function approximation either use OIS (Maei & Sutton 2010, Yu 2010, Sutton et al. 2014, Geist & Scherrer 2014, Dann et al. 2014) or use WIS but are limited to the tabular or non-parametric case (Precup et al. 2000, Shelton 2001).”
Finite-sample analysis of least-squares policy iteration (2012, background): “Off-policy LSTD. Yu and Bertsekas (2010) derived new bounds for projected linear equations substituting the 1√ 1−γ2 term in front of the approximation error with a much sharper term depending on the spectral radius of some matrices defined by the problem.”
A Multi-Agent Off-Policy Actor-Critic Algorithm for Distributed Reinforcement Learning (2019, methodology): “In that work, a distributed off-policy actor-critic algorithm is proposed that uses consensus for the actor updates – unlike [28,29] and our current work, which both use consensus for the critic step – and gradient temporal differencing (GTD) [14,19,26] for the critic updates, whereas the algorithm ”
Planning with Expectation Models (2019, methodology): “The solution of the real sys-tem is then calculated by off-policy LSTD [Yu, 2010] using the same data that is used to learn the linear model.”
Policy evaluation with temporal differences: a survey and comparison (2015, background): “This computational cost can be reduced from O(n3) to O(n2) by updating A−1t directly and maintaining an estimate θt = A −1 t bt (Nedic and Bertsekas, 2003; Yu, 2010).”
Approximate policy iteration: a survey and some new methods (2011, methodology): “c) In Yu [41, 42], for all λ ∈ [0, 1] and λ n ∑”
Weighted Bellman Equations and their Applications in Approximate Dynamic Programming ∗ (2012, methodology): “Figure 4 (right) demonstrates this difference using a two-state example from [Yu10b, Appendix], for which analysis and empirical evidence suggest that the estimates of the (least squares) TD(0.99) converge at a rate slower than 1/ √ t.”
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]).”