Eligibility Traces

Chapter 1: The λ-Return

The n-step return from Chapter 7 is G_t:t+n = R_t+1 + γR_t+2 + … + γⁿ⁻¹R_t+n + γⁿV(S_t+n). It uses n real rewards and then bootstraps. The λ-return is a weighted average of all these n-step returns:

The weights are geometric: the 1-step return gets weight (1−λ), the 2-step return gets (1−λ)λ, the 3-step gets (1−λ)λ², and so on. The full MC return G_t gets whatever weight is left: λ^T−t−1. These weights always sum to 1 — it's a proper average.

At λ = 0: only the 1-step return has nonzero weight. G_t^λ=0 = G_t:t+1 = R_t+1 + γV(S_t+1). This is the TD(0) target.

At λ = 1: only the final MC return has nonzero weight. G_t^λ=1 = G_t. This is the Monte Carlo target.

At λ = 0.5: the 1-step return gets weight 0.5, the 2-step gets 0.25, the 3-step gets 0.125, etc. Short-term returns dominate, but long-term information is blended in.

Chapter 2: TD(λ)

Computing the λ-return requires the full episode (since the MC return is part of the blend). That defeats the purpose of TD's incremental, online nature. The eligibility trace solves this by turning the forward-looking λ-return into a backward-looking mechanism that updates after every step.

The eligibility trace z_t is a vector the same size as the weight vector w. It starts at zero and updates on every step:

Each time a state is visited, its features get added to z. Between visits, z decays by γλ per step. The trace records a fading memory of which features were recently active. Then the weight update is simply:

pseudocode
# Semi-gradient TD(λ) — backward view
Initialize w arbitrarily
for each episode:
  S ← start state
  z ← 0 (trace vector)
  while S is not terminal:
    A ← π(S)
    take A, observe R, S'
    δ ← R + γ v̂(S', w) − v̂(S, w)
    z ← γ λ z + ∇ v̂(S, w)
    w ← w + α δ z
    S ← S'

Chapter 3: Forward vs Backward

There are two equivalent ways to think about the same algorithm. The forward view says: at each time step t, look forward to all future rewards, compute the λ-return G_t^λ, and update w toward it. The backward view says: at each time step t, compute the TD error δ_t and send credit backward to all recently visited states through the eligibility trace.

The equivalence holds exactly in the linear case with accumulating traces. For the online case (apply updates immediately), the two views diverge slightly because each update changes w, which changes future TD errors. The true online TD(λ) algorithm (Chapter 6) closes this gap.

Why does this matter? Because the backward view is O(d) per step (d = number of features), while computing the forward view naively is O(d · T) per episode. The trace is the computational trick that makes λ-returns practical for large-scale problems.

Chapter 4: Truncated λ-Return

The λ-return involves the MC return at the end, which means you need the full episode. For continuing tasks (no episodes), this is a problem. The truncated λ-return solves it by cutting off after h steps:

Instead of averaging all the way to the end of the episode, we average up to h steps ahead, putting all remaining weight on the h-step return. This is an approximation — the truncated λ-return is not exactly the same as the full λ-return. But for large h and λγ < 1, the distant terms have decayed to near-zero weight anyway.

The truncated λ-return is the basis for the TTD(λ) algorithm. It updates each state t using the truncated return computed h steps later. This requires a buffer of h recent transitions — more memory than the trace approach, but it works for continuing tasks and doesn't accumulate trace arithmetic.

Chapter 5: Online λ-Return

Consider a subtle problem with the offline λ-return. At time t, we compute G_t^λ using the weight vector w_t (the version of w at time t). But by the time we have all the data to compute G_t^λ, w has already been updated many times. Wouldn't it be better to use the latest w at each point?

The online λ-return algorithm does exactly this. At each time step h, it goes back and redoes all updates from the start of the episode using the h-step truncated λ-return with the latest weights. It's as if, at each step, you erase all the updates you've done and redo them with better information.

This seems prohibitively expensive. At step h, we redo h updates, each costing O(d). Over a T-step episode, the total cost is O(d · T²). For short episodes this is fine. For long episodes it's impractical. But the mathematical sequence of weight vectors it produces is the best that the λ-return framework can achieve online — it's the ideal that other algorithms approximate.

The key: w_t^h means "the weight vector at time t, computed using data up to time h." The online algorithm, at each new time step h, recomputes this entire sequence from scratch. Impractical? Yes. But it defines the target that the next chapter's efficient algorithm matches exactly.

Chapter 6: True Online TD(λ)

The online λ-return is ideal but costs O(T²). True online TD(λ) (van Seijen & Sutton, 2014) achieves the exact same sequence of weight updates in O(d) per step — the same cost as regular TD(λ). It's a mathematical marvel: through careful algebraic manipulation, the O(T²) algorithm collapses to O(d).

The trick is Dutch traces. Instead of the standard accumulating trace, the Dutch trace is:

where x_t = ∇v̂(S_t, w_t) is the feature vector. The extra term (1 − αγλ z_t−1^Tx_t) corrects for the online nature of the algorithm. The weight update also includes an additional correction:

pseudocode
# True Online TD(λ) with Dutch traces
Initialize w
for each episode:
  S ← start; z ← 0; V_old ← 0
  while S is not terminal:
    A ← π(S); take A, observe R, S'
    x ← feature vector for S
    V ← wTx; V' ← wTx'
    δ ← R + γ V' − V
    z ← γλ z + (1 − αγλ zTx) x
    w ← w + α(δ + V − V_old) z − α(V − V_old) x
    V_old ← V'
    S ← S'

Chapter 7: Sarsa(λ)

Everything we've done with eligibility traces for prediction (learning V) extends naturally to control (learning Q). Sarsa(λ) uses traces to assign credit over multiple time steps in the action-value setting.

The update is exactly the TD(λ) pattern, but with Q instead of V and with features defined over (state, action) pairs:

where δ_t = R_t+1 + γ q̂(S_t+1, A_t+1, w_t) − q̂(S_t, A_t, w_t).

Chapter 8: Variable λ and γ

So far λ and γ have been constants. But there's no reason they can't vary by state. State-dependent bootstrapping lets the agent decide, at each state, how much to bootstrap.

The generalized λ-return uses λ(s) and γ(s):

State-dependent γ has a natural interpretation too. Setting γ(s) = 0 for terminal states is something we already do — it signals the end of the return. But we can also set γ(s) to values between 0 and 1 to encode how much we care about future rewards from different states. This is a form of soft termination.

The state-dependent formulation subsumes all the previous versions as special cases. Constant λ and γ are just the case where λ(s) = λ and γ(s) = γ for all s. The theory (convergence guarantees, forward-backward equivalence) carries through with appropriate modifications.

Chapter 9: Off-policy Traces

Eligibility traces and off-policy learning interact in complex ways. Chapter 11 showed that off-policy with function approximation is already dangerous. Adding traces (which propagate updates over multiple steps) compounds the importance sampling problem: the IS ratio for an n-step update is the product ρ_tρ_t+1…ρ_t+n−1, which can have enormous variance.

Several approaches handle this:

IS-weighted Traces

Multiply the trace update by ρ_t:

When ρ_t = 0 (the target policy wouldn't take this action), the trace resets to zero. This is correct but can have very high variance when ratios are large.

Tree-Backup Traces

Instead of IS ratios, use the target policy's action probabilities directly. The trace decays by π(A_t|S_t) instead of using ρ. This bounds the trace (no ratios greater than 1) but means the effective λ is reduced — you bootstrap more when the policies differ.

Retrace(λ)

Cap the IS ratio at 1: use min(ρ_t, 1) in place of ρ_t. This keeps the trace bounded (low variance) while still correcting for the off-policy distribution. Retrace is the basis of many practical deep RL algorithms.

Chapter 10: Empirical Results

Theory tells us that λ interpolates between TD(0) and MC. But which value of λ actually works best? The consistent empirical finding, replicated across many domains, is: intermediate values of λ are best. Neither λ=0 (pure TD) nor λ=1 (pure MC) wins.

The optimal λ also interacts with the step size α. With a very small α, the bias of TD(0) is corrected slowly, so higher λ is better. With a large α, the variance of MC makes λ=1 unstable, so lower λ is preferred. The best (α, λ) pair is problem-dependent, which is why tuning both is standard practice.

In the tabular case on the 19-state random walk, the best performance is typically around λ = 0.4–0.6 with moderate α. With function approximation on harder problems, λ = 0.8–0.95 is common. The empirical lesson is clear: always try intermediate λ, never assume one extreme is best.

Chapter 11: Summary

Eligibility traces provide a unified mechanism for assigning credit over time. They bridge the gap between TD(0) and Monte Carlo, and the parameter λ provides a smooth dial between them. In practice, intermediate λ almost always outperforms either extreme.

What comes next: Chapter 11 explored the instability of off-policy learning. Chapter 13 takes a completely different approach: instead of learning value functions and deriving policies from them, we learn the policy directly. This is the world of policy gradient methods — the foundation of modern deep RL.