An Analysis of Temporal-Di erence Learning with Function Approximation

By John N. Tsitsiklis, Benjamin Van Roy. 1996

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

DisCor: Corrective Feedback in Reinforcement Learning via Distribution Correction (2020, background): “On the other hand, prior work on fully online Q-learning from a stochastic approximation viewpoint analyzes time-varying µ , but in the absence of function approximation [9, 25, 26], or at the granularity of a single time-step in the environment [27], unlike our setting.”
GQ(lambda): A general gradient algorithm for temporal-difference prediction learning with eligibility traces (2010, neutral): “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 Greedy Approach to Adapting the Trace Parameter for Temporal Difference Learning (2016, background): “For the ﬁrst moment, the Bellman operator is known to be a contraction [30].”
Finite-sample analysis of least-squares policy iteration (2012, methodology): “It is important to note that the asymptotic bound obtained by taking the number of samples, n , to inﬁnity is equal (up to constants) to the bound in Tsitsiklis and Van Roy (1997) for model-based LSTD.”
Off-Policy Temporal Difference Learning with Function Approximation (2001, methodology): “…function Qπ for a given policy π. Operating in an onpolicy mode, updating state–action pairs according to the same distribution with which they would be experienced under π, this method is stable and convergent near the best possible solution (Tsitsiklis and Van Roy, 1997; Tadic, 2001).”
Model-Based Reinforcement Learning with an Approximate, Learned Model (1996, background): “While a wide class of methods have been proven convergent for the table-lookup case, many of these, including Q-learning and dynamic programming methods, appear to be unstable when simple function approximators are used (Baird 1995; Gordon 1995).”
Scalable Bilinear π Learning Using State and Action Features (2018, methodology): “Linear basis functions have been used for both policy evaluation and optimization (Tsitsiklis and Van Roy, 1997; Nedi´c and Bertsekas, 2003; Lagoudakis and Parr, 2003; Melo et al., 2008; Sutton et al., 2009).”
SBEED: Convergent Reinforcement Learning with Nonlinear Function Approximation (2017, methodology): “Unfortunately, when function approximatiors are used, such ﬁxed-point methods easily become unstable or even divergent (Boyan & Moore, 1995; Baird, 1995; Tsitsiklis & Van Roy, 1997), except in a few special cases.”
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).”
Distributional reinforcement learning with linear function approximation (2019, methodology): “When the states to be updated are sampled according to a distribution ξ , the expected behaviour of this update rule corresponds to an operator akin to a projection (Tsitsiklis & Van Roy, 1997).”
Reinforcement Learning by Value Gradients (2008, background): “Previous examples of divergence for a function approximator with bootstrapping have usually been for “oﬀ-policy” learning (see for example, Baird, 1995; Tsitsiklis and Roy, 1996b).”
Traffic Light Control Using Deep Policy-Gradient and Value-Function Based Reinforcement Learning (2017, background): “Applying non-linear function approximators such as neural networks with model-free reinforcement learning algorithms in high-dimensional continuous state and action spaces, has some convergence problems [37].”
Multi-step Off-policy Learning Without Importance Sampling Ratios (2017, methodology): “In this case, solutions produced by multi-step learning can be much superior to those produced by one-step learning (Tsitsiklis & Van Roy 1997).”
Dual Representations for Dynamic Programming (2008, background): “This combined operator is guaranteed to converge, since composing a non-expansion with a contraction is still a contraction, that is, k q + − q Π k z ≤ 1 1 − γ q Π − P q Π k z (Tsitsiklis and Van Roy, 1997).”