Chapter 114: n-step Methods and Eligibility Traces

TD(0) uses one real reward and then trusts its own estimate. Monte Carlo waits for every reward and trusts nothing but experience. When we compared them in TD vs Monte Carlo, each had real advantages—and we hinted that they’re actually two ends of a single dial.

This chapter turns that dial. What lives between one step and all the steps? A whole family of methods—and, as we’ll measure on a concrete problem, the middle of the dial usually beats both ends.

What You'll Learn

Define the n-step return and implement n-step TD prediction
Show experimentally why intermediate n beats both TD(0) and Monte Carlo
Extend n-step targets to control with n-step SARSA
Derive the λ-return (forward view) and implement TD(λ) with eligibility traces (backward view)
State precisely how λ = 0 recovers TD(0) and λ = 1 recovers Monte Carlo
Place TD, MC, n-step, and DP methods in one unified space of backups—and choose among them

One Dial, Not Two Algorithms

Every method in this chapter answers the same question: how many real rewards do you collect before you substitute your own value estimate for the rest?

TD(0)

1 reward,
then bootstrap

→

2-step TD

2 rewards,
then bootstrap

→

n-step TD

n rewards,
then bootstrap

→

Monte Carlo

all rewards,
no bootstrap

Slide left: less variance, more bias, faster updates. Slide right: less bias, more variance, longer waits. The highlighted middle is where the practical wins live—and this chapter measures exactly that on the classic random walk problem.

Then we go one step further. Instead of picking a single n, TD(λ) averages all the n-step targets at once, with geometrically decaying weights controlled by the trace-decay parameter $\lambda$ . Eligibility traces make that averaging cheap enough to run online, one update per step.

What’s in This Chapter

n-step TD

The n-step return, n-step prediction and SARSA, and the random walk experiment where intermediate n wins

Eligibility Traces and TD(λ)

The λ-return, the backward view with traces, and why the two views agree

The Unifying View

One map for MC, TD, n-step, and DP—and how these ideas power Rainbow and GAE

The Chapter in Three Equations

If you remember three things from this chapter:

The n-step return collects $n$ real rewards, then bootstraps from the value estimate $n$ steps ahead.
The λ-return is a weighted average of all n-step returns, with weight $(1-\lambda)\lambda^{n-1}$ on the n-step one.
Eligibility traces compute λ-return learning online: every state keeps a fading memory of having been visited, and each TD error updates all recently visited states at once, in proportion to that memory.

∑Mathematical Details

The three central equations, previewed:

$G_{t:t+n} = R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^{n-1} R_{t+n} + \gamma^n V(S_{t+n})$

$G_t^{\lambda} = (1-\lambda) \sum_{n=1}^{\infty} \lambda^{n-1} G_{t:t+n}$

$e_t(s) = \gamma \lambda \, e_{t-1}(s) + \mathbf{1}[S_t = s], \qquad V(s) \leftarrow V(s) + \alpha \, \delta_t \, e_t(s) \ \text{ for all } s$

Each is unpacked, derived, and implemented in the subsections.

</>Implementation

And the whole backward view fits in a few lines—this is the complete per-step logic of TD(λ):

delta = r + gamma * V[s_next] - V[s]   # 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

The subsections build up to this, run it on the random walk, and report the measured results.

Why This Chapter Matters

ℹ️Note

This is the last stop before function approximation—and the ideas here are not historical curiosities. The multi-step targets you’ll build in this chapter reappear almost unchanged in modern deep RL: Rainbow uses n-step returns as one of its core components, and Generalized Advantage Estimation—the default in most PPO implementations—is exactly the λ-return idea applied to advantages. Understanding the dial now means those chapters will feel familiar later.

Summary & Check Your Understanding

Key Takeaways

TD and MC are ends of one spectrum

The n-step return uses n real rewards before bootstrapping. n = 1 is TD(0); n reaching the end of the episode is Monte Carlo. It’s a dial, not a dichotomy.

The middle of the dial usually wins

On the 19-state random walk, intermediate n gives lower error than either extreme—the measured sweet spot balances TD’s bias against MC’s variance.

TD(λ) averages all n-step returns at once

The λ-return weights the n-step return by (1−λ)λ^(n−1). λ is a trace-decay parameter, not a step count: λ = 0 gives TD(0), λ = 1 gives every-visit Monte Carlo (for offline updates).

Eligibility traces make it run online

Each state’s trace e(s) fades by γλ per step and bumps by 1 on a visit. One TD error then updates every recently visited state—credit assignment without waiting.

The ideas live on in deep RL

n-step targets are a core Rainbow component, and GAE applies the λ-weighting to advantage estimates. The bias-variance dial follows you all the way to PPO.

Quick Quiz

1. What does the “0” in TD(0) refer to—and what does it not refer to?

Show answer

The 0 is the value of λ, the trace-decay parameter of the TD(λ) family. It does not count reward steps—TD(0) uses one real reward before bootstrapping. With λ = 0, all of the λ-return’s weight lands on the one-step return, so TD(λ) collapses to one-step TD. The step-count knob is a different parameter: the integer n of n-step methods.

2. Why does an intermediate n typically beat both n = 1 and Monte Carlo?

Show answer

It’s the bias-variance tradeoff. With n = 1, the target leans heavily on V(S_t+1), which is wrong early in learning—high bias. With Monte Carlo, the target sums many random rewards—high variance, so learning is noisy and slow. An intermediate n uses enough real reward to dilute the bias, but bootstraps soon enough to cap the variance. On the 19-state random walk, the measured minimum error lands at n = 4 (with n = 2 and n = 8 close behind), not at either extreme.

3. What exactly does an accumulating eligibility trace e(s) store, and what does TD(λ) cost per step?

Show answer

e(s) is a fading record of how recently (and how often) state s was visited: it decays by a factor γλ every step and increments by 1 whenever s is the current state. Each step, TD(λ) computes one ordinary TD error and adds α · δ · e(s) to every state. That’s O(number of states) work per step—constant with respect to episode length, which is what makes averaging all n-step returns tractable online.

4. Name two modern algorithms that use multi-step targets, and say which knob (n or λ) each one turns.

Show answer

Rainbow (deep value-based RL) turns the n knob: it replaces DQN’s one-step target with an n-step return (n = 3 in the paper), and ablations show it’s one of the components Rainbow can least afford to lose. GAE, used by most PPO implementations, turns the λ knob: it forms an exponentially weighted average of multi-step advantage estimates—exactly the λ-return construction, applied to advantages instead of values.

Next ChapterFunction Approximation→