Sutton & Barto Chapter 12 — Eligibility Traces Explained

// the one-minute version

The λ-return is a geometrically weighted mixture of every n-step return: λ=0 is one-step TD and λ→1 approaches Monte Carlo in episodic tasks. That forward view seems to require future data. An eligibility trace supplies an equivalent backward view: recently active features carry fading credit, so each new TD error updates many predecessors immediately. True-online TD(λ) adds a correction and Dutch traces to match an online forward view exactly. Sarsa(λ) extends traces to control; off-policy variants must correct or cut traces when behavior departs from the target.

Asha’s robot performs six careful moves before a parcel finally locks into its tray. Reward arrives only on the sixth. One-step TD first teaches the final alignment and leaves the earlier approach nearly unchanged. Monte Carlo credits the whole sequence, but only after completion and with high variance. Chapter 12 asks for a continuous dial between those extremes—and an online implementation that does not keep every possible n-step return.

01 A continuum of backup lengths

Chapter 7 chose one horizon n. Chapter 12 mixes all horizons. Let G_t:t+n be the n-step return. The λ-return is

forward viewG_t^λ=(1−λ)Σ_n=1^∞λⁿ⁻¹G_t:t+n.

The weights form a geometric distribution and sum to one. With λ=0, only the one-step return survives. As λ approaches one in a terminating episode, weight moves toward the full return. Thus λ controls how much an update trusts bootstrap estimates versus subsequent observed rewards.

02 Why the forward view is conceptually clean but operationally late

At time t, G_t:t+5 cannot be known until five transitions arrive. A literal λ-return would revise old states repeatedly as horizons become available, or wait until episode end. It is excellent for defining the desired update but awkward for continual online learning.

The truncated λ-return stops at the current horizon h and puts remaining probability on the longest available return. The online λ-return algorithm updates every earlier state toward its newly extended truncated return after each step. This is precise but computationally expensive; it serves as the target behavior that true-online methods reproduce efficiently.

03 The backward view: TD errors flow through a fading memory

An eligibility vector z has one component per parameter. At each step, old eligibility decays by γλ and the gradient of the current estimate is added:

accumulating tracez_t=γλz_t−1+∇v̂(S_t,w); w←w+αδ_tz_t.

A feature is eligible if it was recently responsible for a prediction. When a TD error arrives, every eligible parameter changes; recent features change most. Algebra shows that over an episode, the sum of TD errors weighted by traces equals the λ-return update in the offline case.

The trace stores credit eligibility, not rewards and not a replayable trajectory.

04 Accumulating, replacing, and Dutch traces

Accumulating traces add x each time a feature activates. Rapid revisits can make a binary feature’s trace exceed one. A replacing trace sets an active binary feature to one while inactive traces decay, often improving control with tile coding. For action values, replacing also commonly clears traces for the other actions in the current state.

Replacing traces are a useful modification, but they do not produce exact online forward-view equivalence. Dutch traces use a step-size-dependent correction: z←γλz+[1−αγλzᵀx]x. They arise from the algebra of true-online TD, not from an analogy about memory.

05 True-online TD(λ): exact at every step

Conventional TD(λ) matches the forward view only after an episode with fixed weights, or approximately when α is tiny. Online learning changes weights while the future unfolds, so old targets and new predictions interact. True-online TD(λ) adds a small correction using the change in prediction, often called the TD-error correction, and uses Dutch traces.

The result is exactly equivalent at every time step to the online λ-return algorithm for linear approximation, while retaining time proportional to the number of features. It often performs at least as well as conventional TD(λ), particularly for larger α. “True online” refers to this exact equivalence—not simply processing samples one by one.

06 Sarsa(λ) brings traces into control

Replace state-value gradients with action-value gradients and use Sarsa’s on-policy TD error. The trace now remembers recent state-action features. A delayed positive δ reinforces the chain of decisions that preceded it; a negative δ weakens them.

Sarsa(λ)δ=R+γq̂(S′,A′,w)−q̂(S,A,w); z←γλz+∇q̂(S,A,w); w←w+αδz.

At episode start, clear z. At termination, bootstrap with zero and still apply the final update. True-online Sarsa(λ) supplies the analogous exact-forward-view corrections for linear action values.

07 Variable λ and γ express structure, not just tuning

λ may depend on state. Set it lower where bootstrapping is reliable or where a boundary should cut credit; set it higher where delayed evidence is essential. γ can also vary by transition, naturally encoding termination or task continuation. The generalized trace decays by γ_tλ_t.

This turns traces into a language for temporal abstraction: γ says whether future reward remains part of the question; λ says how far sampled evidence should replace current predictions.

08 Off-policy traces need correction

Ordinary importance-sampled TD(λ) places ratios into traces, correcting the probability of the whole credited action sequence. Products of ratios can create severe variance. Several algorithms choose different bias–variance compromises.

Watkins’s Q(λ) follows Q-learning while exploratory nongreedy actions cut the trace, because earlier updates should not credit a sequence that the greedy target would not take. Tree-Backup(λ) replaces sampled-action ratios with target-policy probabilities for unchosen branches, avoiding importance sampling. Retrace-style ideas cap trace coefficients. The unifying object is a trace coefficient controlling how much each past feature receives from the current TD error.

09 Asha’s delayed grasp and the implementation checklist

walk it throughAt the successful lock, δ is strongly positive. With γ=.99 and λ=.8, the immediately preceding alignment feature receives about .792 of current eligibility, the prior approach about .627, and older actions progressively less. Learning spreads through the skill in one episode while preserving recency.

gotchasClear traces at real episode boundaries. Do not confuse λ with γ: λ controls backup mixing, γ defines the return. Sweep α and λ jointly. Sparse traces still need pruning when many features accumulate. In off-policy learning, never reuse on-policy traces without stating the correction rule.

10 Questions a master’s student should be able to answer

Is λ a literal memory length?

No. Eligibility decays geometrically rather than stopping after a fixed number of steps. Its effective timescale depends jointly on γλ and feature revisitation.

Why can a backward trace equal a mixture of future returns?

Expand each n-step return into TD errors. The same TD error appears in earlier returns with geometric weights. Reordering the double sum yields the backward-view eligibility coefficients.

When is λ=1 exactly Monte Carlo?

In episodic tasks with appropriate terminal handling, the forward λ-return tends to the full return. In continuing tasks there may be no complete episode, and γ still affects the infinite return.

Why prefer true-online TD(λ)?

It exactly matches the incremental forward view for linear approximation and avoids the approximation error of conventional traces at finite step sizes, with similar computational order.

Why do nongreedy actions cut Watkins’s trace?

Q-learning’s target assumes greedy continuation. Once behavior takes a nongreedy action, the sampled continuation no longer represents that target sequence, so old credit is stopped rather than misassigned.

11 Chapter summary and exam-ready map

Forward view: λ geometrically mixes all n-step returns.
Backward view: traces turn current TD errors into graded updates of recent features.
Trace variants: accumulating adds revisits, replacing caps binary features, and Dutch traces enable exact online equivalence.
True online: correction terms match the changing truncated forward view at every step.
Control: Sarsa(λ) credits recent state-action features and resets at episode boundaries.
Generalization: state-dependent γ and λ express continuation and credit decisions.
Off-policy: ratios, trace cutting, or expected branches are required; each chooses a bias–variance trade-off.

// master’s study sheetchapter 12

derive

equivalenceExpand n-step returns into TD errors and reorder the sum to obtain geometric eligibility.

limitsShow λ=0 gives TD(0), while episodic λ→1 gives the full return.

implement

comparisonRun TD(0), conventional TD(λ), and true-online TD(λ) on random walk; sweep α×λ and plot RMS error.

12 Source trail and scope

These are independent companion notes, not a replacement for the textbook. The chapter organization follows Sutton and Barto's second edition; explanations and examples here are original. Use the authors' book page, the MIT Press edition page, and the official table of contents for the primary source and exact section sequence.

Chapter 12 — Eligibility Traces, explained.