Linear Least-Squares algorithms for temporal difference learning

By Steven J. Bradtke, Andrew Barto. 2004

798 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Mechanics, Control and Systems Engineering, 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 Artificial Intelligence

In Computational Mechanics

In Control and Systems Engineering

In Reinforcement Learning

Citations in the corpus

When to use parametric models in reinforcement learning? (2019, methodology): “When making linear predictions with least-squares temporal-difference learning [LSTD, Bradtke and Barto, 1996, Boyan, 1999], the model-free algorithm on the original data does not require (or indeed benefit from) planning: the solution will already be a best fit (in a least squares sense) even with…”
Deep learning in neural networks: An overview (2014, background): “Many variants of traditional RL exist (e.g., Barto et al., 1983; Watkins, 1989; Watkins and Dayan, 1992; Moore and Atkeson, 1993; Schwartz, 1993; Baird, 1994; Rummery and Niranjan, 1994; Singh, 1994; Baird, 1995; Kaelbling et al., 1995; Peng and Williams, 1996; Mahadevan, 1996; Tsitsiklis and van Ro”
Causally Correct Partial Models for Reinforcement Learning (2020, background): “…interest in combining causal inference with RL research in the directions of non-model-based bandit algorithms (Bareinboim et al., 2015; Forney et al., 2017; Zhang & Bareinboim, 2017; Lee & Bareinboim, 2018; Bradtke & Barto, 1996; Lu et al., 2018) and causal discovery with RL (Zhu & Chen, 2019).”
Data-Efficient Off-Policy Policy Evaluation for Reinforcement Learning (2016, methodology): “…foundation of the entire TD ( λ ) family of algorithms, which includes the original linear-time algorithm (Sutton, 1988), least-squares formulations (Bradtke & Barto, 1996; Mahmood et al., 2014), methods for adapting λ (Downey & Sanner, 2010), true-online methods (van Hasselt et al., 2014), and…”
Linear Off-Policy Actor-Critic (2012, methodology): “Least-squares methods such as LSTD (Bradtke & Barto, 1996) and LSPI (Lagoudakis & Parr, 2003) can be used oﬀ-policy and are sound with linear function approximation, but are computationally expensive; their complexity scales quadratically with the number of features and weights.”
Regularized Behavior Value Estimation (2021, methodology): “Early examples of ofﬂine/batch RL include least-squares temporal difference methods (Bradtke and Barto, 1996; Lagoudakis and Parr, 2003) and ﬁtted Q iteration (Ernst et al., 2005; Riedmiller, 2005).”
Hyperparameter Selection for Offline Reinforcement Learning (2020, methodology): “Early examples of oﬄine/batch RL include least-squares temporal diﬀerence methods (Bradtke and Barto, 1996; Lagoudakis and Parr, 2003) and ﬁtted Q iteration (Ernst et al., 2005; Riedmiller, 2005).”
Off-policy learning with eligibility traces: a survey (2013, methodology): “Solving the following fixed-point problem: θi = argmin ω∈Rp i∑ j=1 ( T̂j V̂θi − V̂ω(sj) )2 with a least-squares approach, corresponds to the Least-Squares Temporal Differences (LSTD) algorithm of Bradtke and Barto (1996).”
On Learning to Think: Algorithmic Information Theory for Novel Combinations of Reinforcement Learning Controllers and Recurrent Neural World Models (2015, methodology): “The parameters or weights of C are trained to maximize reward by a standard RL method such as Q-learning or similar methods [17, 292, 293, 172, 254, 212, 262, 10, 122, 188, 157, 281, 26, 216, 197, 272, 311, 9, 163, 174, 22, 27, 2, 137, 276, 156, 284].”
Dyna-Style Planning with Linear Function Approximation and Prioritized Sweeping (2008, methodology): “In practice, this measure can be computed very efficiently as ||A∗θ−b∗|| (in the notation of LSTD(0), see Bradtke & Barto 1996).”
Emphatic Temporal-Difference Learning (2015, methodology): “Keywords: temporal-difference learning, function approximation, off-policy learning, stability, convergence”
Batch Mode Reinforcement Learning based on the Synthesis of Artificial Trajectories (2012, methodology): “Batch mode RL techniques are probably rooted in the works of Bradtke and Barto (1996) and Boyan (2005) related to the use of least-squares techniques in the context of Temporal Difference learning methods (LSTD) for estimating the return of control policies.”
Least Squares Temporal Difference Methods: An Analysis under General Conditions (2012, methodology): “If P = Q, then all the ratios qit−1it pit−1it appearing in the above iterates become 1, and the algorithm reduces to the on-policy LSTD algorithm [12, 11].”
Model-Based Reinforcement Learning with Value-Targeted Regression (2020, methodology): “Upper Confidence RL with Value-Targeted Model Parameter Regression We develop a regret minimization algorithm that takes advantage of the linearly parametrized model by following the ideas of linear bandit Dani et al. (2008); Rusmevichientong and Tsitsiklis (2010); Li et al.”
Recent advances in reinforcement learning in finance (2021, background): “Examples include Brafman and Tennenholtz (2002), Kearns and Singh (2002), Lattimore andHutter (2012) and Szita and Szepesvári (2010).”
Why Should I Trust You, Bellman? The Bellman Error is a Poor Replacement for Value Error (2022, background): “The Bellman equation has played a prominent role in many historically significant approaches (Schweitzer & Seidmann, 1985; Baird, 1995; Bradtke & Barto, 1996; Antos et al., 2008; Sutton et al., 2009), as well as the more modern family of deep RL algorithms (Mnih et al., 2015; Lillicrap et al.,…”