The Unifying View | n-step Methods and Eligibility Traces

Over the last several chapters you’ve met what looks like a zoo of algorithms: dynamic programming from Policy Evaluation, Monte Carlo methods, TD(0) from Introduction to TD Learning, and now n-step methods and TD(λ). Time to put away the zoo and pull out the map.

Sutton and Barto organize all of these methods along just two dimensions. Once you see the map, every method you’ve learned—and most of the ones still ahead—snaps into place as a point in the same space.

The Two Dimensions of Backups

Every method we’ve seen improves a value estimate by performing a backup: it looks at what happens after a state, computes a target, and moves the estimate toward that target. Backups differ in exactly two ways:

Depth: How far into the future do you look before substituting a value estimate? One step (TD), n steps, or all the way to termination (MC)?
Width: Do you follow one sampled path of experience, or average over all possible next states weighted by their probabilities?

Shallow + Sample

TD(0)

One sampled transition, then bootstrap. Model-free, cheapest possible backup.

Shallow + Full

Dynamic Programming

Expected update over all next states, then bootstrap. Needs the model.

Deep + Sample

Monte Carlo

One sampled trajectory, all the way to the end. Model-free, no bootstrapping.

Deep + Full

Exhaustive Search

Every branch of every future, expanded completely. Exact—and hopeless beyond tiny problems.

The interior of this square is not empty. Along the left edge, between TD(0) and Monte Carlo, live the n-step methods and TD(λ) from this chapter—sample backups of intermediate depth. Along the top edge, between TD(0) and DP, live methods like Expected SARSA that average over actions but sample transitions. Heuristic search occupies the interior on the model-based side.

A useful way to internalize the two axes:

Depth asks: how much do I trust my current value estimates? Shallow backups trust them a lot (bootstrap early). Deep backups trust only real experience.
Width asks: how much do I know about the environment? Full-width backups require a model of the transition probabilities. Sample backups only require the ability to act and observe.

TD(0) sits at the “trust your estimates, know nothing” corner. Exhaustive search sits at the “trust nothing, know everything” corner. Most of practical RL happens near the left edge—model-free sample backups—with depth chosen by n or λ.

∑Mathematical Details

The width dimension in symbols. A sample one-step backup uses a single observed transition $(S_t, R_{t+1}, S_{t+1})$ :

$V(S_t) \leftarrow V(S_t) + \alpha \left[ R_{t+1} + \gamma V(S_{t+1}) - V(S_t) \right]$

A full (expected) one-step backup—the DP policy-evaluation update—averages over everything that could happen:

$V(s) \leftarrow \sum_a \pi(a \mid s) \sum_{s', r} p(s', r \mid s, a)\left[ r + \gamma V(s') \right]$

The full backup has no sampling error at all: it computes the exact expectation, so no step-size $\alpha$ is needed. Its cost is that it requires the model $p(s', r \mid s, a)$ and touches every possible successor. The sample backup costs one transition of experience, needs no model, and pays for it with sampling noise—which is exactly why it needs a step size to average that noise away.

The depth dimension is the one you now know well: replace the one-step target with $G_{t:t+n}$ for depth $n$ , or with $G_t$ for full depth, or with $G_t^{\lambda}$ to mix all depths.

Choosing a Point in the Space

The map is descriptive; here’s the prescriptive part. Three forces determine where you want to be.

Bias vs variance → choose depth

Shallow targets are biased by your current estimates; deep targets are noisy sums of many random rewards. Long, noisy episodes push you shallower; short episodes and bad value estimates push you deeper.

Computation and memory → sample vs full, traces vs n-step

Full backups need a model and cost a sum over successors. Among sample methods, n-step needs an n-step buffer; TD(λ) needs one trace value per state but updates every traced state each step.

Update delay → how deep you can afford to look

An n-step method can’t update a state until n more steps have passed; MC can’t update until the episode ends. Continuing tasks and real-time learning cap your usable depth—or push you to the backward view, which updates every step regardless of λ.

💡Tip

Rules of thumb that hold up well in practice:

Intermediate beats extreme. On the random walk in n-step TD, the measured error was lowest at moderate n and moderate λ—not at either endpoint. This pattern repeats across many domains.
Small n for deep RL. Modern value-based agents typically use n between 3 and 10; Rainbow uses n = 3.
High λ for advantage estimation. GAE implementations commonly default to λ around 0.95 with γ around 0.99.
When in doubt, start at n = 1 or λ = 0 (the stable, low-variance end) and increase until learning speed stops improving.

Where the Estimates Go Next: Function Approximation

Everything in this chapter used a table: one $V(s)$ entry per state. The next section of the book replaces the table with a parameterized function $\hat{V}(s; \mathbf{w})$ —a linear model or a neural network. Here’s the crucial point: the targets survive the transition unchanged.

Function approximation changes what you update (parameters instead of table cells), not what you update toward. A one-step target, an n-step target, and a λ-return are all just numbers you regress your function toward. The bias-variance dial you learned to turn in this chapter is exactly the dial you’ll keep turning in deep RL:

DQN regresses $\hat{Q}$ toward a one-step target—that’s n = 1 on the dial.
Rainbow regresses toward an n-step target—the dial moved to 3.
GAE builds policy-gradient advantages with a λ-weighted target—the dial expressed as a decay rate.

Even eligibility traces generalize: with function approximation, the trace becomes a vector with one component per parameter (tracking each parameter’s recent contribution to value predictions) rather than one per state. Same fading-memory idea, new address space.

n-step Returns in the Wild: Rainbow

The clearest modern descendant of this chapter’s first half is the n-step return inside Rainbow. DQN’s original target bootstraps after a single reward. Rainbow replaces it with a truncated n-step return—n real rewards from the replay buffer, then a bootstrap from the target network—using n = 3.

∑Mathematical Details

The Rainbow-style n-step target is the same object as this chapter’s $G_{t:t+n}$ , with the bootstrap supplied by the target network $\theta^-$ :

$G_{t:t+n} = \sum_{k=0}^{n-1} \gamma^{k} R_{t+k+1} + \gamma^{n} \max_{a'} \hat{Q}(S_{t+n}, a'; \theta^-)$

Nothing conceptually new—only the value estimate at the end of the n rewards is now a neural network’s output instead of a table entry.

Why does this help so much? Early in training, $\hat{Q}$ is mostly wrong, so a one-step target is mostly bias. Three real rewards dilute that bias and let reward information jump three steps backward per update instead of one—the same faster-credit-propagation effect you saw on the random walk. In the Rainbow paper’s ablations, removing the n-step component was among the most damaging changes—evidence that the humble depth dial matters even when everything else is deep and modern.

ℹ️Note

Notice which form of multi-step learning survived: the forward view. Deep agents compute n-step targets directly from stored trajectory fragments in a replay buffer, rather than maintaining backward-view traces. Traces assume you update on the stream of experience in order; replay buffers deliberately break that ordering. The estimator generalized; the online mechanism was traded for one that suits minibatch training. Eligibility traces still shine where learning really is online and incremental—streaming settings, some robotics and neuromorphic systems, and classic successes like TD-Gammon, which was trained with TD(λ).

The λ Idea in the Wild: GAE

The second half of this chapter—averaging all depths with geometric weights—reappears almost verbatim in policy gradient methods as Generalized Advantage Estimation, covered in detail in the GAE section and used by default in most PPO implementations.

Policy gradient methods need an estimate of the advantage $A(s, a)$ : how much better was this action than average? You can estimate it with a one-step TD error (low variance, biased) or with a full Monte Carlo return minus a baseline (unbiased, high variance). Sound familiar? It’s the same spectrum, and GAE resolves it the same way TD(λ) does.

∑Mathematical Details

Recall from the eligibility traces section that the λ-return error decomposes into a geometrically discounted sum of TD errors (exactly, when $V$ is held fixed over the episode):

$G_t^{\lambda} - V(S_t) = \sum_{k=t}^{T-1} (\gamma\lambda)^{k-t} \, \delta_k$

GAE defines the advantage estimate as precisely that sum:

$\hat{A}_t^{\text{GAE}(\gamma, \lambda)} = \sum_{k=t}^{T-1} (\gamma\lambda)^{k-t} \, \delta_k, \qquad \delta_k = R_{k+1} + \gamma V(S_{k+1}) - V(S_k)$

Set $\lambda = 0$ and you get the one-step TD error as the advantage. Set $\lambda = 1$ and you get the Monte Carlo return minus the value baseline. Intermediate $\lambda$ interpolates—with the identical geometric weighting, the identical bias-variance reading, and even the identical boundary cases as TD(λ). GAE is not “inspired by” the λ-return; it is the λ-return construction, applied to advantages instead of state values.

</>Implementation

The standard GAE computation is a single backward pass over a trajectory—compare it to the backward view of TD(λ) and you’ll recognize the recursion $\hat{A}_t = \delta_t + \gamma\lambda \hat{A}_{t+1}$ :

def gae_advantages(rewards, values, gamma=0.99, lam=0.95):
    """Generalized Advantage Estimation over one episode.

    values has len(rewards) + 1 entries (bootstrap value at the end;
    0.0 if the episode terminated).
    """
    T = len(rewards)
    adv = [0.0] * T
    running = 0.0
    for t in reversed(range(T)):
        delta = rewards[t] + gamma * values[t + 1] - values[t]
        running = delta + gamma * lam * running   # geometric accumulation
        adv[t] = running
    return adv

Every PPO codebase you read from here on will contain some version of this loop. You now know exactly where it comes from.

One Map, Backward and Forward

Here’s the whole book so far, and a good chunk of the book ahead, on the two-dimensional map:

Method	Depth	Width	Model needed?	Where covered
Policy evaluation (DP)	1 step	Full	Yes	Policy Evaluation
TD(0), SARSA, Q-learning	1 step	Sample	No	Intro to TD, SARSA, Q-Learning
n-step TD / n-step SARSA	n steps	Sample	No	n-step TD
TD(λ)	All depths, λ-weighted	Sample	No	Eligibility Traces
Monte Carlo	Full episode	Sample	No	Monte Carlo Methods
DQN / Rainbow	1 / n steps	Sample	No	DQN, Rainbow
GAE (in PPO, A2C)	All depths, λ-weighted	Sample	No	GAE

🔍Deep Dive▶

Two loose ends the map points at.

Off-policy multi-step learning. Everything in this chapter assumed the data comes from the policy being evaluated. Multi-step targets complicate off-policy learning: with n rewards in the target, all n actions must be “explained” under the target policy, which classically requires importance sampling ratios or alternatives like tree-backup updates and Retrace. This is why naively combining n-step returns with a replay buffer (as Rainbow does) is technically off-policy-inconsistent—yet works well for small n, since the behavior that generated recent replay data is close to the current policy.

Model-based methods. The right half of the map—full-width backups—reappears when agents learn a model and plan with it. Dyna-style methods and MuZero blend sampled real experience with model-generated backups, effectively moving around the map during training. See Model-Based RL.

Summary

The unifying view in four sentences:

Every value-learning method is a choice of backup depth (how many real rewards before bootstrapping) and backup width (one sampled future vs an expectation over all futures).
Depth trades bias for variance; width trades model knowledge and computation for sampling noise.
n-step methods and TD(λ) fill the model-free edge between TD(0) and Monte Carlo, and the measured sweet spot is in the middle.
The same dial—expressed as n in Rainbow and as λ in GAE—keeps setting the bias-variance balance in modern deep RL.

You’ve now completed the tabular story: prediction and control, on-policy and off-policy, one-step and multi-step. The remaining wall is that a table needs one cell per state. The next section of the book—Function Approximation—knocks that wall down, and every estimator from this chapter comes along for the ride.