n-Step Bootstrapping

The last two lessons drew the same estimation problem from opposite ends. Monte Carlo waits until an episode terminates and updates each visited state toward the full observed return — no bootstrapping, but no learning until the very end. Temporal-difference learning updates after a single step, using one real reward $R_{t+1}$ plus the current estimate $V(S_{t+1})$ as a stand-in for everything after — all bootstrapping, and online. The two are the endpoints of one family, indexed by a single integer $n$.

An $n$-step method looks ahead exactly $n$ real rewards and then bootstraps from the estimated value of the state reached $n$ steps later. Set $n=1$ and you recover one-step TD; let $n$ run to the end of the episode and you recover Monte Carlo. Every value of $n$ in between is a genuine method, and an intermediate $n$ often learns faster than either extreme.¹

The n-step return

Fix the state–reward sequence an agent generates while following $\pi$,

where $T$ is the terminal step (actions omitted for now). Whatever method we use to estimate $v_{\pi }(S_t)$, it updates $V(S_t)$ toward some target. The different members of the family are just different choices of target.

Monte Carlo aims at the complete return, every reward until termination:

One-step TD truncates after a single reward and patches the missing tail with a bootstrapped estimate — the one-step return:

where $V_t$ is the estimate of $v_{\pi }$ at time $t$. The subscript notation $G_{t:t+1}$ reads a return for time $t$ using rewards up through time $t+1$: the discounted estimate $\gamma V_t(S_{t+1})$ takes the place of the discarded tail $\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+\cdots +{\gamma }^{T-t-1}{R}_T$. The same idea extends past one step. A two-step return keeps two real rewards and bootstraps from the value two steps out,

where ${\gamma }^2{V}_{t+1}(S_{t+2})$ now corrects for the absence of ${\gamma }^2{R}_{t+3}+\cdots +{\gamma }^{T-t-1}{R}_T$. In general, the target for an arbitrary $n$-step update is the $n$-step return:

for all $n\ge 1$ and $0\le t<T-n$. Every $n$-step return is an approximation to the full return $G_t$, truncated after $n$ rewards and then corrected for the remaining missing terms by ${\gamma }^n{V}_{t+n-1}(S_{t+n})$. If the horizon runs to or past termination — that is, if $t+n\ge T$ — all the missing terms are already zero, and the $n$-step return equals the ordinary full return: $G_{t:t+n}\doteq G_t$ whenever $t+n\ge T$.

One subtlety: the $n$-step return for step $t$ uses future rewards $R_{t+1},\dots ,R_{t+n}$ and the future state $S_{t+n}$ — none of which exist at time $t+1$. No real algorithm can use $G_{t:t+n}$ until it has seen $R_{t+n}$ and computed $V_{t+n-1}$; the first moment all of that is available is time $t+n$. This lag is unavoidable when looking ahead, and it shapes the pseudocode below.

The n-step TD update

With the target in hand, the update follows directly. At time $t+n$ (the first moment $G_{t:t+n}$ is computable) we move $V(S_t)$ a fraction $\alpha$ of the way toward it:

while every other state's estimate is left unchanged, $V_{t+n}(s)=V_{t+n-1}(s)$ for $s\ne S_t$. This is $n$-step TD. The bracketed quantity is the familiar TD error, but with an $n$-step target in place of the one-step one. Because the update for $S_t$ fires only at $t+n$, the first $n-1$ states of each episode get no update as the episode begins; to compensate, an equal number of updates are made at the end, after termination, before the next episode starts.

The index $\tau =t-n+1$ is the state currently being updated: at wall-clock time $t$ we have just enough lookahead to finish the update for the state $n-1$ steps in the past. All storage can be kept modulo $n+1$, since only the last $n+1$ states and rewards ever matter at once — the method's memory is bounded by $n$, not by the episode length.

Why an intermediate n is sound

That $n$-step returns interpolate between two known-good methods does not by itself prove they converge. The guarantee comes from a worst-case bound. The intuition: each real reward folded into the target is observed rather than estimated, so it reduces the target's dependence on the error in the bootstrapped estimate; after $n$ steps only a ${\gamma }^n$ fraction of that error remains. Formally, the expectation of the $n$-step return is a better estimate of $v_{\pi }$ than $V_{t+n-1}$ is, in the following sense: its worst error over states is at most ${\gamma }^n$ times the worst error of the current estimate,

for all $n\ge 1$. This is the error-reduction property. Because ${\gamma }^n<1$, each expected $n$-step backup contracts the worst-case error, and one can show from this that $n$-step TD converges to the correct $v_{\pi }$ under appropriate conditions. Every method in the family is sound; one-step TD and Monte Carlo are simply its two extreme members.

A worked n-step target

For example, take $\gamma =0.9$, and suppose an agent following $\pi$ produces the reward stream

with current value estimates $V(S_{t+1})=5$, $V(S_{t+2})=4$, $V(S_{t+3})=6$, and $V(S_{t+4})=2$. The one-step return keeps one real reward and bootstraps from the very next state:

The two-step return keeps two rewards and bootstraps two states out:

The three-step return keeps three:

Each target is the same shape — accumulated discounted reward, then one bootstrap term ${\gamma }^{n}V(S_{t+n})$ standing in for everything past the horizon. The three targets differ in the depth at which they rely on the estimate: $G_{t:t+1}$ depends almost entirely on $V(S_{t+1})=5$, while $G_{t:t+3}$ has replaced two layers of that estimate with real rewards and now depends on $V(S_{t+3})=6$. If the early estimates were biased, the deeper target has removed more of that bias — the error-reduction property in a single trajectory. The bootstrap weight itself shrinks with depth: ${\gamma }^1=0.9$, ${\gamma }^2=0.81$, ${\gamma }^3=0.729$, so the further out the bootstrap, the less it can distort the target.

The backup-diagram spectrum

The family is easiest to see through its backup diagrams. Each diagram traces the states and rewards whose values are backed up into the root. One-step TD backs up from a single reward and one bootstrapped state; $n$-step TD strings $n$ rewards down a spine before bootstrapping; Monte Carlo extends the spine all the way to the terminal square. The whole family is one picture at increasing depth.

Depth controls a bias–variance tradeoff: shallow backups (small $n$) depend heavily on the bootstrapped estimate, so they are low-variance but inherit whatever bias sits in $V$; deep backups (large $n$) use more real reward, shedding bias but taking on the variance of long reward sequences. The best depth is intermediate and task-dependent.

An intermediate n beats both extremes

The random walk quantifies the tradeoff. Take a chain of $19$ states with a terminal on each end, an outcome of $-1$ on the left and $+1$ on the right, all values initialized to $0$, and equiprobable left/right moves. Run $n$-step TD for a sweep of $n$ and $\alpha$, and measure the RMS error of the predictions against the true values, averaged over the first $10$ episodes and $100$ runs.

Two things stand out. Each curve is a U in $\alpha$ — too small a step learns too slowly, too large a step overshoots — and the bottom of the U, the best achievable error, is lowest for an intermediate $n$, neither $n=1$ nor the very largest. A one-step method after this walk would change only the value of the last state visited; a two-step method would nudge the last two; an $n$-step method credits the last $n$ states of the run, all by the same reward. Spreading credit further than one step, but not all the way to the episode's start, gives the lowest error.

Sutton and Barto's full figure sweeps more values of $n$ and finds the whole family of U-curves nested this way, with the minimum-of-minima at a small-but-not-one $n$. As the backup-diagram spectrum suggests, bootstrapping too aggressively (small $n$) ties the estimate to a possibly poor initial value function, while not bootstrapping at all (Monte Carlo) takes on the full variance of the sampled return. An intermediate $n$ holds both errors down at once.

n-step Sarsa: control

Prediction estimates $v_{\pi }$ for a fixed policy; control improves the policy. The move from prediction to control is the one from the previous lesson: switch from states to state–action pairs and act $\epsilon$-greedily with respect to the action values. The $n$-step version of Sarsa — the original one-step Sarsa is now Sarsa(0) — redefines the return over action values instead of state values:

with $G_{t:t+n}\doteq G_t$ when $t+n\ge T$. The bootstrap now uses the estimated value of a state–action pair, $Q_{t+n-1}(S_{t+n},A_{t+n})$, rather than a state. The update mirrors $n$-step TD:

leaving all other action values unchanged. Its backup diagrams are the same spectrum as before, but every column now begins and ends on an action (a solid dot) rather than a state, with the sample actions and states alternating down the spine.

The far-right diagram is $n$-step Expected Sarsa: identical to $n$-step Sarsa except the last element is a full branch over all actions, weighted by their probability under $\pi$. Its return replaces the final action-value with an expected value,

where the expected approximate value of a state is the policy-weighted average of its action values,

Bootstrapping from $\bar{V}$ instead of a single sampled action removes the variance of that last action choice, exactly as one-step Expected Sarsa removed it in the previous lesson.

Why n-step control speeds learning

The reason to reach past one step in control is that a single delayed reward should teach more than one action. Consider an agent wandering a gridworld, receiving zero reward until it stumbles onto a goal cell. When the episode ends, one-step Sarsa strengthens exactly one state–action value: the last action, the one that stepped onto the goal. Every earlier action on that successful path learns nothing from this episode. An $n$-step method strengthens the last $n$ actions of the path in one sweep, so a single lucky trajectory propagates credit back along its own tail.

This continues in n-Step Bootstrapping: Off-Policy Methods, which reweights n-step returns by the importance-sampling ratio, builds the tree-backup algorithm that goes off-policy with no ratios at all, and unifies the whole family under n-step Q(sigma).