An analysis of temporal-difference learning with function approximation

By John N. Tsitsiklis, Benjamin Van Roy. 1997

We discuss the temporal-difference learning algorithm, as applied to approximating the cost-to-go function of an infinite-horizon discounted Markov chain. The algorithm we analyze updates parameters of a linear function approximator online during a single endless trajectory of an irreducible aperiodic Markov chain with a finite or infinite state space. We present a proof of convergence (with probability one), a characterization of the limit of convergence, and a bound on the resulting approximation error. Furthermore, our analysis is based on a new line of reasoning that provides new intuition about the dynamics of temporal-difference learning. In addition to proving new and stronger positive results than those previously available, we identify the significance of online updating and potential hazards associated with the use of nonlinear function approximators. First, we prove that divergence may occur when updates are not based on trajectories of the Markov chain. This fact reconciles positive and negative results that have been discussed in the literature, regarding the soundness of temporal-difference learning. Second, we present an example illustrating the possibility of divergence when temporal difference learning is used in the presence of a nonlinear function approximator.

Subfields: Reinforcement Learning

How researchers see this paper

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

In Reinforcement Learning

Citations in the corpus

Bridging the Gap Between Value and Policy Based Reinforcement Learning (2017, background): “For any policy π and state s k , ˜ V π ( s k ) satisﬁes the recurrence The fact that B π is a contraction mapping follows directly from standard arguments about the on-policy Bellman operator (Tsitsiklis & Van Roy, 1997).”
Graying the black box: Understanding DQNs (2016, background): “Unfortunately, such methods are known to be unstable or even to diverge when used to represent the action-value function (Tsitsiklis & Van Roy, 1997; Gordon, 1995; Riedmiller, 2005).”
Reinforcement learning in robotics: A survey (2013, background): “Similarly, it is well known that linear value-function approximation is unstable in the offpolicy case (Tsitsiklis and Van Roy, 1997; Sutton and Barto, 1998; Gordon, 1999).”
Infinite-Horizon Policy-Gradient Estimation (2001, background): “It has been shown that for linear functions, converges to a parameter minimizing the expected squared loss under the stationary distribution ( Tsitsikilis & Van-Roy, 1997 ):”
Least Squares Temporal Difference Methods: An Analysis under General Conditions (2012, methodology): “The line of our analysis is considerably different from those in the literature for similar on-policy TD methods (Tsitsiklis and Van Roy [34], Nedić and Bertsekas [24]) and off-policy TD methods [25, 8].”
GQ(lambda): A general gradient algorithm for temporal-difference prediction learning with eligibility traces (2010, positive): “Prior to their work, the existing classical TD algorithms (e.g.; TD( λ ) and Q-learning) with function approximation could become unstable and diverge (Baird, 1995; Tsitsiklis and Van Roy, 1997).”
A Kernel Loss for Solving the Bellman Equation (2019, methodology): “…such as neural networks is used to represent the value function in large-scale problems, the critical property of contraction is generally lost (e.g., Boyan & Moore, 1995; Baird, 1995; Tsitsiklis & Van Roy, 1997), except in rather restricted cases (e.g., Gordon, 1995; Tsitsiklis & Van Roy, 1997).”
Unifying Task Specification in Reinforcement Learning (2016, background): “Another example is the classic divide between episodic and continuing problems, which typically require different convergence proofs (Bertsekas and Tsitsiklis, 1996; Tsitsiklis and Van Roy, 1997; Sutton et al., 2009) and different algo-rithm speciﬁcations.”
Concurrent Hierarchical Reinforcement Learning (2005, background): “Unfortunately, convergence results are hard to come by once function approximation is introduced, and in fact, there are known examples of divergence [Gordon, 1995; Tsitsiklis and Van Roy, 1996; Baird, 1995; Bertsekas and Tsitsiklis, 1996].”
Bayes Meets Bellman: The Gaussian Process Approach to Temporal Difference Learning (2003, methodology): “Third, we would like to establish convergence guarantees in the spirit of Tsitsiklis and Van-Roy (1997) .”
Fast gradient-descent methods for temporal-difference learning with linear function approximation (2009, unknown): “We assume that the Markov chain is ergodic and uni-chain, so there exists a limiting distribution d such that ds = limt#" P(st = s).1 In the on-policy case, d is linked to the transition probabilities (in particular, we know that P! d = d) and this linkage is critical to the convergence of algorithm”