The Whole Spectrum: n-step Returns, TD(λ), and Eligibility Traces

A dial between MC and TD

TD(0) looks one step ahead, then bootstraps. Monte Carlo looks all the way to the end of the episode. Why not look some number of steps ahead — say 3, or 10 — and only then fall back on your value estimate? That is exactly the idea of n-step returns, and it turns the choice between MC and TD into a single tunable knob.

The n-step return uses the next n real rewards and then bootstraps off the value of the state reached after n steps: G(n) = r₁ + γr₂ + … + γⁿ⁻¹rₙ + γⁿ·V(sₙ). With n = 1 this is the TD(0) target; with n reaching the end of the episode it becomes the full Monte Carlo return. Everything in between trades off bias and variance smoothly.

G_t^{(n)} = r_{t+1} + \gamma\, r_{t+2} + \cdots + \gamma^{\,n-1} r_{t+n} + \gamma^{\,n}\, V(s_{t+n})

The n-step return blends n real rewards with one bootstrapped value: n = 1 recovers TD(0), n → ∞ recovers Monte Carlo.

n-step TD in practice

n-step temporal-difference updates V(sₜ) toward G(n) once you've seen n more rewards. Concretely you keep a small buffer of the last n transitions; when the buffer is full you can compute the n-step return for its oldest state and update it. This is still fully online — you just lag by n steps.

# n-step return for the state at time t (assumes rewards r[t+1..t+n] available)
G = 0.0
for k in range(n):
    G += (gamma ** k) * r[t + 1 + k]      # n real rewards
if t + n < T:                              # not yet terminal
    G += (gamma ** n) * V[s[t + n]]        # bootstrap off the n-th state
V[s[t]] += alpha * (G - V[s[t]])           # n-step TD update

Mixing n real rewards with one bootstrapped value gives the n-step TD update.

Empirically, intermediate n (often somewhere between 4 and 16) tends to beat both extremes: more rewards than TD(0) means less bias, but stopping short of the full return means less variance than Monte Carlo. The catch is that n is now a hyperparameter you must choose, and a single fixed n is a blunt instrument.

Averaging all the n's: the λ-return

Instead of betting on one n, why not average over all of them? The λ-return forms a geometrically weighted average of every n-step return, with weight (1−λ)·λⁿ⁻¹ on the n-step return. A single parameter λ ∈ [0, 1] now controls how far you effectively look ahead: λ = 0 collapses to one-step TD(0), and λ = 1 recovers the full Monte Carlo return. This averaged target is the heart of TD(λ).

G_t^{\lambda} = (1-\lambda)\sum_{n=1}^{\infty} \lambda^{\,n-1}\, G_t^{(n)}

The λ-return averages every n-step return with geometric weights (1−λ)λⁿ⁻¹, tuning the whole MC–TD dial with one parameter.

Defining the target this way — looking forward across many horizons — is called the forward view. It is beautifully clear conceptually, but as stated it still needs future rewards, so you couldn't compute it online. The fix is one of the most elegant tricks in RL.

Eligibility traces: the backward view

Eligibility traces let you achieve the λ-return's effect online and incrementally, with no waiting. The idea: keep a short-term memory, the trace e(s), marking how recently and how often each state was visited. Every step the trace decays by γλ and the current state's trace is bumped up. Then a single TD error δ is broadcast to all states in proportion to their trace.

# TD(lambda), backward view — applied every step
delta = r + gamma * V[s_next] - V[s]
e[s] += 1.0                          # mark current state as eligible
for x in all_states:
    V[x] += alpha * delta * e[x]     # one error updates many states
    e[x] *= gamma * lam              # traces decay each step

One TD error, distributed to recently visited states by their eligibility traces.

Remarkably, this backward view — credit flowing back to recently visited states — is mathematically equivalent (offline) to the forward-view λ-return. It also solves the credit assignment problem gracefully: when a reward finally arrives, it immediately reinforces the trail of states and actions that led there, scaled by how recently each contributed.

Choosing λ (and n) in practice

Everything so far has been prediction — estimating values for a fixed policy. The real goal of an agent is control: finding a good policy. The next guide turns these prediction methods into control algorithms — Sarsa, Q-learning, and Expected Sarsa.