GQ(lambda): A general gradient algorithm for temporal-difference prediction learning with eligibility traces

By Hamid Reza Maei, Richard S. Sutton. 2010

153 citations recorded by the source corpus.

A new family of gradient temporal-diﬀerence learning algorithms have recently been introduced by Sutton, Maei and others in which function approximation is much more straightforward. In this paper, we introduce the GQ( λ ) algorithm which can be seen as extension of that work to a more general setting including eligibility traces and oﬀ-policy learning of temporally abstract predictions. These extensions bring us closer to the ultimate goal of this work—the development of a universal prediction learning algorithm suitable for learning experientially grounded knowledge of the world. Eligibility traces are essential to this goal because they bridge the temporal gaps in cause and eﬀect when experience is processed at a temporally ﬁne resolution. Temporally abstract predictions are also essential as the means for representing abstract, higher-level knowledge about courses of action, or options. GQ( λ ) can be thought of as an extension of Q-learning. We extend existing convergence results for policy evaluation to this setting and carry out a forward-view/backward-view analysis to derive and prove the validity of the new algorithm.

Subfields: Artificial Intelligence, Reinforcement Learning, Optimization & Training

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 Reinforcement Learning

In Optimization & Training

Citations in the corpus

High-Confidence Off-Policy Evaluation (2015, methodology): “Existing methods for estimating the performance of the evaluation policy using trajectories from behavior policies do not provide confidence bounds (Maei and Sutton 2010; Liu, Mahadevan, and Liu 2012; Mandel et al. 2014).”
Linear Off-Policy Actor-Critic (2012, background): “…d b ( s ) on its diagonal; Π is a projection operator that projects a value function to the nearest representable value function given the function approximator; and T λ,γπ is the λ -weighted Bellman operator for the target policy π with termination probability γ (e.g., see Maei & Sutton, 2010).”
Off-policy learning with eligibility traces: a survey (2013, methodology): “It was originally proposed by Maei and Sutton (2010) under the name GQ(λ). We call it off-policy TDC(λ) to highlight the fact that it is the extension of the original TDC algorithm of Sutton et al. (2009) to off-policy learning with traces.”
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].”
Emphatic Temporal-Difference Learning (2015, methodology): “Temporal-difference learning algorithms, such as TD(λ) (Sutton 1988), GQ(λ) (Maei & Sutton 2010), and LSTD(λ) (Boyan 1999, Bradtke & Barto 1996), provide effective solutions to this problem.”
Least Squares Temporal Difference Methods: An Analysis under General Conditions (2012, background): “The associated computation methods use importance sampling techniques and form an established methodology for reinforcement learning (Sutton and Barto [32]) and simulation-based large-scale dynamic programming in general (Glynn and Igle-hart [16]).”
Offline Evaluation of Online Reinforcement Learning Algorithms (2016, methodology): “…in off-policy learning, as an objective function when us-ing policy gradient methods (Levine and Koltun 2013; Peshkin and Shelton 2002) or as a way to re-weight samples in off-policy TD-learning methods (Mahmood, van Has-selt, and Sutton 2014; Sutton, Mahmood, and White 2015; Maei and Sutton 2010).”
Unifying Task Specification in Reinforcement Learning (2016, methodology): “Copyright 2017 by the author(s). jectives, including options (Sutton et al., 1999), state-based discounting (Sutton, 1995; Sutton et al., 2011) and interest functions (Reza and Sutton, 2010; Sutton et al., 2016).”
Horde: a scalable real-time architecture for learning knowledge from unsupervised sensorimotor interaction (2011, methodology): “Our architecture, called Horde, differs from temporal-difference networks in its more straightforward handling of state and function approximation (no predictive state representations) and in its use of more efficient algorithms for off-policy learning (Maei & Sutton 2010; Sutton et al. 2009).”
Toward Off-Policy Learning Control with Function Approximation (2010, methodology): “The update rules of Greedy-GQ are similar to GQ(λ) with λ = 0 (Maei & Sutton, 2010).”
Investigating Practical Linear Temporal Difference Learning (2016, methodology): “In off-policy learning, we require AπC Aπ to be positive definite to satisfy the conditions of the ordinary differential equation proof of convergence [10], which holds because C−1 is positive definite and therefore AπC Aπ is positive definite, because Aπ is full rank (true by assumption).”
Off-policy learning based on weighted importance sampling with linear computational complexity (2015, background): “Modern off-policy algorithms with O ( n ) computational complexity, such as GTD( � ) (Maei 2011), GQ( � ) (Maei & Sutton 2010), and true online GTD( � ) (van Hasselt, Mah-mood & Sutton 2014), all use the ordinary variant of importance sampling and can suffer severely due to the problem of large…”
True online TD(λ) (2014, background): “Maei, Sutton, and others (Maei, 2011; Maei & Sutton, 2010; Sutton et al, in preparation; Sutton et al., 2009) have explored generalizations of TD(λ)-like algorithms to offpolicy learning, in which the behavior policy (generating the data) and the target policy (whose value function is being…”
Incremental Basis Construction from Temporal Difference Error (2011, methodology): “The positive semi-definite matrix K differs from method to method, and examples include K rg = L ⊺ DL for residual gradient (Baird, 1995), K gtd = (ΦDL) ⊺ (ΦDL) for GTD(0) (Sutton et al., 2008), and K lstd = L ⊺ Π D DΠ D L for LSTD (Bradtke et al., 1996) and TDC (Sutton et al., 2009).”
True Online Emphatic TD(λ): Quick Reference and Implementation Guide (2015, background): “We consider the setting of general value functions, or GVFs (Maei & Sutton 2010, Sutton et al. 2011, White 2015, Sutton, Mahmood & White 2015).”