n-Step TD Prediction in RL

n-step TD waits a few real rewards before guessing the rest, so you tune how far to look ahead between fast one step updates and full episode returns.

n-step returns sum n real rewards then bootstrap, so a 2-step return of 2.80 moves the start value to 1.40 while 1-step sees only 1.00

Why Does This Exist?

Value estimates need a target. One step TD bootstraps after a single reward as $R_{t+1} + \gamma V(S_{t+1})$ . Variance stays low because only one random step enters, but bias stays high when $V$ starts poorly, and a far reward crawls back one state per episode. Monte Carlo waits for the full return $G_t$ with no bootstrap. Bias falls because real rewards replace guesses, but variance rises with each added random step, and learning must wait for termination.

n-step TD sets the lookahead to an integer $n$ of at least 1. It sums $n$ real rewards, then bootstraps the rest. That dials the bias variance trade directly. Small $n$ behaves like one step TD. Large $n$ behaves like Monte Carlo. The averaging view that extends this idea is forward view TD lambda.

This page covers the return, the delayed update, and one traced episode that shows reward travel.

Think of It Like This

Daily notes versus quarterly reviews versus a career memoir

A manager judges a new hire three ways.

Daily notes use today output plus a hunch about tomorrow. Fast feedback, heavy hunch. A memoir waits for retirement, sums a whole career with no hunch, but arrives too late and mixes in years of luck. A quarterly review logs three months of real output, then adds a forecast for the rest. Enough fact to anchor judgment, early enough to steer work.

The map holds. Daily notes are TD with $n = 1$ . Memoirs are Monte Carlo. Quarterly reviews are n-step with $n$ around 3 to 10. Real logged output is summed rewards. The forecast is bootstrapped $V(S_{t+n})$ scaled by $\gamma^n$ .

Where it stops: reviews use judgment for the forecast, while n-step multiplies by an exact discount power and applies a fixed step size $\alpha$ through a sliding buffer.

How It Actually Works

At step $t$ the agent sits in $S_t$ , takes $A_t$ , lands in $S_{t+1}$ , and banks $R_{t+1}$ . Discount is $\gamma$ in $[0, 1]$ . Episode ends at $T$ . Value $V(s)$ estimates expected discounted return from $s$ .

The n-step return

Sum the first $n$ discounted rewards, then bootstrap from the state $n$ steps ahead:

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

$R_{t+k}$ is the reward $k$ steps ahead. $\gamma^{k-1}$ discounts it. $V(S_{t+n})$ is the stored estimate for the landing state. When $t + n$ reaches $T$ , cut the sum at $T$ and drop the bootstrap because terminal value is zero. Then $n = 1$ gives the TD target and $n$ past the end gives the Monte Carlo return.

Expected n-step returns shrink worst case error by at least $\gamma^n$ relative to current $V$ . Larger $n$ cuts bias faster in expectation while adding sample variance. That is why mid values often win in practice.

Updates wait n steps

$G_{t:t+n}$ needs future data, so the update for $S_t$ runs at time $t + n$ . Write $\tau = t - n + 1$ for the state due now:

V(S_{\tau}) \leftarrow V(S_{\tau}) + \alpha [G_{\tau:\tau+n} - V(S_{\tau})]

Here $\alpha$ in $(0, 1]$ is step size and the bracket is n-step TD error. Other states sit still. After $T$ , drain the buffer so states $\tau = T - n + 1$ through $T - 1$ all get their updates.

Worked example on one episode

Track $S_0$ to $S_4$ terminal with $R_1 = 1.0$ , $R_2 = 2.0$ , $R_3 = 0.0$ , $R_4 = 10.0$ . Set $\gamma = 0.9$ , $\alpha = 0.5$ , all $V = 0.0$ .

1-step: $G_{0:1} = 1.0 + 0.9 \times 0.0 = 1.00$ . Update gives $0.0 + 0.5 \times 1.00 = 0.50$ . The 10.0 reward has no effect on $S_0$ this episode.
2-step: $G_{0:2} = 1.0 + 0.9 \times 2.0 = 2.80$ . Update gives $0.0 + 0.5 \times 2.80 = 1.40$ .
3-step: $G_{0:3} = 1.0 + 1.80 + 0.81 \times 0.0 = 2.80$ . Update gives 1.40.
Monte Carlo with $n = 4$ : $G_{0:4} = 1.0 + 1.80 + 0.0 + 0.729 \times 10.0 = 10.09$ . Update gives $0.0 + 0.5 \times 10.09 = 5.045$ .

Longer $n$ pulls the far 10.0 back to the start in one episode. Shorter $n$ needs more episodes for the same travel.

Code

This snippet recomputes the four start returns and their updates from the worked example.

1def n_step_return(rewards: list[float], gamma: float, n: int) -> float:2    total: float = 0.03    for i in range(min(n, len(rewards))):4        total += (gamma ** i) * rewards[i]5    return total6
7
8rewards: list[float] = [1.0, 2.0, 0.0, 10.0]9for n in [1, 2, 3, 4]:10    g: float = n_step_return(rewards, 0.9, n)11    print(f"{n} {g:.2f} {0.5 * g:.3f}")  # -> 1 1.00 0.500 etc

The printed triples are $n$ , $G_{0:n}$ , and updated $V(S_0)$ . They read 1 1.00 0.500, 2 2.80 1.400, 3 2.80 1.400, and 4 10.09 5.045.

Watch Out For

Bootstrapping past termination adds phantom value

Adding $\gamma^n V(S_{\tau+n})$ when $\tau + n$ is at or past $T$ is a common bug. Symptom: index errors near episode end, or terminal states that slowly gain value that should stay zero.

Sum rewards only to $\min(\tau + n, T)$ . Add the bootstrap term only when $\tau + n$ is still before $T$ . Keep terminal value fixed at zero.

Stopping at T drops the last buffer

Quitting the loop when time hits $T$ skips updates for the final $n - 1$ states. Symptom: late states learn slowly or never, while early states look fine.

Loop until $\tau = T - 1$ so each visited state gets its delayed update. Size the buffer for $n + 1$ entries of states and rewards from the start.

The Quick Version

n-step TD sums $n$ real discounted rewards then bootstraps, sitting between TD with $n = 1$ and Monte Carlo at the episode end.
Updates for $S_t$ run at $t + n$ , so recent states and rewards live in a short buffer.
Expected error shrinks by at least $\gamma^n$ , which cuts bias as $n$ grows while variance rises.
With gamma 0.9, the start return is 1.00 for $n = 1$ , 2.80 for $n = 2$ , and 10.09 for full Monte Carlo.
Corresponding start values after step 0.5 are 0.50, 1.40, and 5.045.
Clamp sums at termination, drop the bootstrap there, and drain the buffer to the last state.