Reinforcement Learning with Replacing Eligibility Traces

By Satinder Singh, Richard S. Sutton. 2005

465 citations recorded by the source corpus.

The eligibility trace is one of the basic mechanisms used in reinforcement learning to handle delayed reward. In this paper we introduce a new kind of eligibility trace, the replacing trace, analyze it theoretically, and show that it results in faster, more reliable learning than the conventional trace. Both kinds of trace assign credit to prior events according to how recently they occurred, but only the conventional trace gives greater credit to repeated events. Our analysis is for conventional and replace-trace versions of the offline TD(1) algorithm applied to undiscounted absorbing Markov chains. First, we show that these methods converge under repeated presentations of the training set to the same predictions as two well known Monte Carlo methods. We then analyze the relative efficiency of the two Monte Carlo methods. We show that the method corresponding to conventional TD is biased, whereas the method corresponding to replace-trace TD is unbiased. In addition, we show that the method corresponding to replacing traces is closely related to the maximum likelihood solution for these tasks, and that its mean squared error is always lower in the long run. Computational results confirm these analyses and show that they are applicable more generally. In particular, we show that replacing traces significantly improve performance and reduce parameter sensitivity on the "Mountain-Car" task, a full reinforcement-learning problem with a continuous state space, when using a feature-based function approximator.

Subfields: Artificial Intelligence, 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 Reinforcement Learning

Citations in the corpus

Bridging the Gap Between Value and Policy Based Reinforcement Learning (2017, methodology): “The constraint (2) applies to any policy π and serves as the basis of the on-policy one-step expected SARSA (Rummery & Ni-ranjan, 1994; Singh & Sutton, 1996) and actor-critic (Mnih et al., 2016) algorithms; while the constraint (3) only applies to a maximum reward policy and is the basis of the…”
Doubly Robust Off-policy Value Evaluation for Reinforcement Learning (2015, background): “Domain description Mountain car is a popular RL benchmark problem with a 2-dimensional continuous state space, 3 discrete actions, and deterministic dynamics (Singh & Sutton, 1996).”
Trajectory-wise Control Variates for Variance Reduction in Policy Gradient Methods (2019, background): “, variants of TD(λ) [37], during policy optimization.”
Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Sampling (2019, methodology): “Finally, we benchmark our estimator on the Mountain Car domain [Singh and Sutton, 1996], where an under-powered car drives up a steep valley by “swinging” on both sides to gradually build up potential energy.”
Eligibility Traces and Plasticity on Behavioral Time Scales: Experimental Support of NeoHebbian Three-Factor Learning Rules (2018, unknown): “Nevertheless, extended eligibility traces across multiple time steps are considered convenient heuristic tools to speed up learning in temporal difference algorithms such as TD(λ) or SARSA(λ) (Singh and Sutton, 1996; Sutton and Barto, 1998).”
Reinforcement Learning in Continuous State and Action Spaces (2012, methodology): “Replacing traces (Singh and Sutton, 1996) are less straightforward, although the suggestion by Främling (2007) seem sensible:”
Medial prefrontal cortex as an action-outcome predictor (2011, unknown): “Examples of other related reinforcement learning models include Q learning and SARS”
Combating the Compounding-Error Problem with a Multi-step Model (2019, methodology): “Though multi-step algorithms are popular in the model-free setting [Sutton and Barto, 2018; Asis et al. , 2017; Singh and Sutton, 1996; Precup, 2000], extension to the model-based setting remains less explored.”
Policy Transfer using Reward Shaping (2015, unknown): “In the standard Mountain Car task [16], the agent is in control of a car and needs to drive this car up a hill.”
Multiagent Fully Decentralized Value Function Learning With Linear Convergence Rates (2018, methodology): “We remark that the idea of an eligibility trace parameter λ as a bias-variance tradeoff is not novel to this article and has been previously used in algorithms such as TD(λ) [36], TD(λ) with replacing traces [37], GTD(λ) [8], and True Online GTD(λ) [9].”
StarCraft Micromanagement With Reinforcement Learning and Curriculum Transfer Learning (2018, background): “As a basic mechanism in RL, eligibility traces are used to assign temporal credit, which consider a set of previously experienced transitions [61].”
TD γ : Re-evaluating Complex Backups in Temporal Difference Learning (2011, methodology): “While several different algorithms exist within the TD(λ) family—the original incremental and online algorithm [2], replacing traces [3], least-squares algorithms [4], algorithms for learning state-action value functions [1, 5], and algorithms for adapting λ [6], among others—the λ-return formulatio”
True online TD(λ) (2014, unknown): “…e = 0 initialize S repeat {for each step in the episode} generate reward R and next state S for S δ ← R + γ θ φ(S ) − θ φ(S) e ← γλe + αφ(S) θ ← θ + δe S ← S until S is terminal end loop Singh and Sutton (1996) introduced an interesting variation on the traces of TD(λ) called replacing traces.”
Reinforcement learning with misspecified model classes (2013, background): “Mountain car [18] is a standard RL benchmark simulation where the agent starts in a valley between two hills and takes actions to reach the top of the right hill and receives -1 reward for every time step the agent is not at the goal.”