Convergence Results for Some Temporal Difference Methods Based on Least Squares

By Huizhen Yu, Dimitri P. Bertsekas. 2009

127 citations recorded by the source corpus.

We consider finite-state Markov decision processes, and prove convergence and rate of convergence results for certain least squares policy evaluation algorithms of the type known as LSPE(lambda ). These are temporal difference methods for constructing a linear function approximation of the cost function of a stationary policy, within the context of infinite-horizon discounted and average cost dynamic programming. We introduce an average cost method, patterned after the known discounted cost method, and we prove its convergence for a range of constant stepsize choices. We also show that the convergence rate of both the discounted and the average cost methods is optimal within the class of temporal difference methods. Analysis and experiment indicate that our methods are substantially and often dramatically faster than TD(lambda), as well as more reliable.

Subfields: Computer Networks and Communications, Control and Systems Engineering, Management Science and Operations Research

How researchers see this paper

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

In Computer Networks and Communications

In Control and Systems Engineering

In Management Science and Operations Research

Citations in the corpus

Fitted Q-Learning for Relational Domains (2020, background): “…approximation in propositional domains like Least Squares Temporal Difference (LSTD) Learning (Boyan 1999), Least Squares Policy Evaluation (LSPE) (Yu and Bertsekas 2009) and Least Sqaure Policy iteration (LSPI) (Lagoudakis and Parr 2003) approximate the Q-function as linear function of the…”
A Tour of Reinforcement Learning: The View from Continuous Control (2018, methodology): “In particular, Temporal Difference algorithms are derived from the value-function-centric perspective [75, 26, 21, 13, 89].”
Analyzing feature generation for value-function approximation (2007, background): “For a set of weights w expressed as a column vector, V = Fw. Methods for .nding reasonable w given F and a set of samples include linear TD (Sutton, 1988), LSTD (Bradtke & Barto, 1996) and LSPE (Yu & Bertsekas, 2006).”
Distributed Policy Evaluation Under Multiple Behavior Strategies (2013, background): “, [29], [34], [35]); it is promising mainly because it leads to solutions with low computational demands.”
Reinforcement learning for control: Performance, stability, and deep approximators (2018, background): “Tsitsiklis and Van Roy (1997) have analyzed approximate TD, while a comparison between gradient-based TD and LSTD from Section 3.2 is provided by Yu and Bertsekas (2009).”
An analysis of linear models, linear value-function approximation, and feature selection for reinforcement learning (2008, methodology): “Expressing the weights w as a column vector, we have V =Fw. Methods for .nding a reasonable w given Fand a set of samples include linear TD (Sutton, 1988), LSTD (Bradtke & Barto, 1996) and LSPE (Yu & Bertsekas, 2006).”
Generalized TD Learning (2011, background): “Yu and Bertsekas (2006) derived the convergence rate of LSPE (λ) and found that it had the same convergence rate as LSTD (λ).”
A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation (2018, background): “Yu and Bertsekas [2009] study the related least-squares policy iteration algorithm.”
Representation Discovery for MDPs Using Bisimulation Metrics (2015, methodology): “Approximate representations: Given a Φ, linear fixed point methods such as TD, LSTD, LSPE (Sutton 1988; Bradtke and Barto 1996; Yu and Bertsekas 2006) can be used to find the least squares fixed point approximation V π Φ of V π , which is the fixed point of the alternate operator T π Φ : T π Φ f :=…”
A Batch, Off-Policy, Actor-Critic Algorithm for Optimizing the Average Reward (2016, background): “The average reward is given by, Under the irreducible assumption the above is independent of s 0 (Yu and Bertsekas, 2009).”