Eligibility Traces and TD(λ)

n-step TD left us with a nagging inefficiency: we measured that $n = 4$ beats $n = 1$ and $n = 8$ on the random walk—but we only learned that by running all of them. Every n-step return is a legitimate estimate of the same quantity. Why should one update use exactly one of them and throw the rest away?

It doesn’t have to. This section develops the two central ideas:

1. The forward view: define a target that averages all n-step returns at once, weighted geometrically by a parameter $\lambda$. This is the λ-return.
2. The backward view: compute that averaging online, one cheap update per step, using a fading memory called an eligibility trace. This is the TD(λ) algorithm.

The punchline—kept precise throughout, and consistent with how we introduced it back in TD(0) Prediction: $\lambda$ is a trace-decay parameter, not a step count. Setting $\lambda = 0$ recovers one-step TD; setting $\lambda = 1$ recovers (every-visit) Monte Carlo.

The Forward View: The λ-Return

Here are those weights, computed for $\lambda = 0.9$:

There’s an obvious practical problem, though. The λ-return for time $t$ depends on n-step returns of every depth—which means it isn’t fully known until the episode ends. Written this way, the λ-return algorithm is Monte Carlo-like in the worst way: theoretically clean, but offline and acausal. We seem to have lost TD’s best feature.

The Backward View: Eligibility Traces

The fix is one of the most elegant ideas in RL: flip the direction of time.

Algorithm: Tabular TD(λ), accumulating traces
─────────────────────────────────────────────
Input: policy π, step size α, discount γ, trace decay λ
Initialize V(s) arbitrarily

Loop for each episode:
    e(s) ← 0 for all s
    Initialize S
    Loop for each step:
        Take action from π, observe R, S'
        δ ← R + γV(S') − V(S)          (V(S') = 0 if S' terminal)
        e(s) ← γλ e(s) for all s       (all traces fade)
        e(S) ← e(S) + 1                (current state flares up)
        V(s) ← V(s) + α δ e(s) for all s
        S ← S'
    until S is terminal

import numpy as np

# Same 19-state random walk as the n-step experiment:
# states 1..19, terminals 0 and 20, start at 10, rewards -1/+1 at the ends.
N, START, GAMMA = 19, 10, 1.0
TRUE_V = np.arange(-20, 22, 2) / 20.0
TRUE_V[0] = TRUE_V[20] = 0.0

def gen_episode(rng):
    states, rewards, s = [START], [], START
    while 0 < s < 20:
        s2 = s + (1 if rng.random() < 0.5 else -1)
        rewards.append(1.0 if s2 == 20 else (-1.0 if s2 == 0 else 0.0))
        states.append(s2)
        s = s2
    return states, rewards

def td_lambda_run(lam, alpha, episodes, rng):
    """Online TD(lambda), accumulating traces. RMS error after each episode."""
    V = np.zeros(21)
    errs = []
    for _ in range(episodes):
        states, rewards = gen_episode(rng)
        e = np.zeros(21)                      # traces reset each episode
        for t in range(len(rewards)):
            s, s2, r = states[t], states[t + 1], rewards[t]
            delta = r + GAMMA * V[s2] - V[s]  # one ordinary TD error
            e *= GAMMA * lam                  # all traces fade
            e[s] += 1.0                       # current state becomes eligible
            V += alpha * delta * e            # one error updates many states
        errs.append(np.sqrt(np.mean((V[1:20] - TRUE_V[1:20]) ** 2)))
    return errs

Measured: TD(λ) on the Random Walk

Same protocol as the n-step experiment—average RMS error over the 19 states and the first 10 episodes, averaged over 100 runs, sweeping $\alpha$ from 0.02 to 1.0 for each λ. The measured results:

The same U-shape as the n sweep, for the same bias-variance reason—and the numbers line up beautifully with the n-step results:

• λ = 0 exactly reproduces 1-step TD: best α of 0.82 and RMS 0.348, identical to the $n = 1$ row of the n-step sweep. That’s not a coincidence; it’s the boundary case, confirmed numerically.
• The winner, λ = 0.8 (RMS 0.266), matches the best n-step result ($n = 4$, RMS 0.267). With $\lambda = 0.8$, over half the λ-return’s weight falls on depths 4 and shallower, with the rest spreading deeper—an averaged version of the same intermediate depth.
• λ = 1 is the worst setting tested (RMS 0.508 at a tiny best α of 0.02), and it’s fragile: with accumulating traces it diverged outright for every α of 0.32 and above in this sweep—value estimates ran away to floating-point overflow—and even at α = 0.1 the average error exploded to about 167. Monte Carlo-like variance plus traces that can grow past 1 on revisits is an explosive combination. λ = 1 is a conceptual endpoint, not a practical setting.

Why the Two Views Agree

We introduced traces with a metaphor. Here’s the actual claim, and a numerical verification of it.

def offline_forward_increments(states, rewards, V, lam, alpha):
    """Summed lambda-return updates for one episode (V frozen)."""
    T, inc = len(rewards), np.zeros(21)
    for t in range(T):
        G_lam = 0.0
        for n in range(1, T - t):                       # truncated n-step returns
            G = sum(GAMMA ** k * rewards[t + k] for k in range(n))
            G += GAMMA ** n * V[states[t + n]]
            G_lam += (1 - lam) * lam ** (n - 1) * G
        G_full = sum(GAMMA ** k * rewards[t + k] for k in range(T - t))
        G_lam += lam ** (T - t - 1) * G_full            # tail weight on full return
        inc[states[t]] += alpha * (G_lam - V[states[t]])
    return inc

def offline_backward_increments(states, rewards, V, lam, alpha):
    """Summed eligibility-trace updates for one episode (V frozen)."""
    inc, e = np.zeros(21), np.zeros(21)
    for t in range(len(rewards)):
        s, s2, r = states[t], states[t + 1], rewards[t]
        delta = r + GAMMA * V[s2] - V[s]
        e *= GAMMA * lam
        e[s] += 1.0
        inc += alpha * delta * e
    return inc

The Endpoints, Precisely

We can now state the family relationships exactly—these are the claims previewed in TD(0) Prediction and TD vs Monte Carlo, now proven and measured:

Note the fine print on the MC side: it’s every-visit MC (each visit to a state gets an update), not first-visit—and the equivalence is for offline updating. Online TD(1) is a slightly different, and as we measured, fragile algorithm.

Summary

The λ-return averages all n-step returns with geometric weights $(1-\lambda)\lambda^{n-1}$—the forward view. Eligibility traces compute the same learning backward in time: traces fade by $\gamma\lambda$, flare on visits, and each one-step TD error updates all traced states at once—online, O(states) per step, no waiting. The two views produce identical total updates offline (verified to 10⁻¹⁵ here), and the endpoints are exact: λ = 0 is one-step TD, offline λ = 1 is every-visit Monte Carlo. Measured on the random walk, intermediate λ wins—λ = 0.8 hit RMS 0.266, matching the best n-step method, while λ = 1 was both worst and prone to divergence.

You’ve now seen the complete bridge between TD and Monte Carlo, built twice—once with n, once with λ. The final section zooms out: one map for every method so far, and the direct line from this chapter to Rainbow and GAE.