n-step TD

In TD(0), the target for updating $V(S_t)$ was one real reward plus a bootstrap: $R_{t+1} + \gamma V(S_{t+1})$. In Monte Carlo, the target was the complete return—every reward until the episode ends. Nobody said you have to choose one of those two. You can collect two real rewards before bootstrapping. Or three. Or ten.

That single observation gives us n-step TD, and with it, a tunable dial between TD and MC:

Each card uses more real reward and less estimated value. By the end of this page you’ll know how to implement any point on this dial—and you’ll see measured evidence that the middle of the dial learns fastest.

The n-step Return

The Algorithm: Learning n Steps Behind

There’s one wrinkle in turning this into an algorithm: at time $t$, the n-step return for $S_t$ isn’t computable yet—you have to wait until time $t + n$ to have seen the $n$ rewards. So n-step TD always updates the state visited $n$ steps ago. When the episode ends, the last few states get their (shortened) updates in a final flush.

Algorithm: n-step TD for Estimating V^π
────────────────────────────────────────
Input: policy π, step size α, discount γ, steps n
Initialize V(s) arbitrarily

Loop for each episode:
    Store S_0; T ← ∞
    For t = 0, 1, 2, ...:
        If t < T:
            Take action from π, observe and store R_{t+1}, S_{t+1}
            If S_{t+1} is terminal: T ← t + 1
        τ ← t − n + 1        (τ is the time whose state gets updated)
        If τ ≥ 0:
            G ← sum of γ^(i−τ−1) R_i  for i = τ+1 ... min(τ+n, T)
            If τ + n < T:  G ← G + γ^n V(S_{τ+n})
            V(S_τ) ← V(S_τ) + α [G − V(S_τ)]
    Until τ = T − 1

import numpy as np

# 19-state random walk (Sutton & Barto, Fig 7.2 setup):
# non-terminal states 1..19, terminals at 0 and 20, start at 10.
# Stepping into 0 gives reward -1; into 20 gives +1; else 0. gamma = 1.
N, START, GAMMA = 19, 10, 1.0
TRUE_V = np.arange(-20, 22, 2) / 20.0   # true values: v(s) = s/10 - 1
TRUE_V[0] = TRUE_V[20] = 0.0            # terminals

def gen_episode(rng):
    """Return (states, rewards); rewards[t] is for states[t] -> states[t+1]."""
    states, rewards, s = [START], [], START
    while 0 < s < 20:
        s2 = s + (1 if rng.random() < 0.5 else -1)
        rewards.append(1.0 if s2 == 20 else (-1.0 if s2 == 0 else 0.0))
        states.append(s2)
        s = s2
    return states, rewards

def nstep_td_run(n, alpha, episodes, rng):
    """Online n-step TD prediction. Returns RMS error after each episode."""
    V = np.zeros(21)
    errs = []
    for _ in range(episodes):
        states, rewards = gen_episode(rng)
        T = len(rewards)
        for tau in range(T):                    # update time for S_tau
            end = min(tau + n, T)
            G = sum(GAMMA ** (k - tau) * rewards[k] for k in range(tau, end))
            if tau + n < T:                     # bootstrap unless past the end
                G += GAMMA ** n * V[states[tau + n]]
            V[states[tau]] += alpha * (G - V[states[tau]])
        errs.append(np.sqrt(np.mean((V[1:20] - TRUE_V[1:20]) ** 2)))
    return errs

The Experiment: Which n Wins?

Time to settle it with data. The task: estimate the value function of the 19-state random walk under the random policy, starting from $V = 0$ everywhere.

Why 19 states instead of 5? Room to maneuver. With longer episodes (about 101 steps on average, measured over 20,000 episodes), there’s space for multi-step returns to show their strength—and for very deep returns to show their weakness.

Protocol (following Sutton & Barto’s Figure 7.2): for each $n \in \{1, 2, 4, 8, 16, 32\}$ and each $\alpha \in \{0.02, 0.04, \ldots, 1.0\}$, run 10 episodes, compute the RMS error between $V$ and the true values (averaged over the 19 states and the 10 episodes), and average that over 100 independent runs. Identical episode sequences are used for every $(n, \alpha)$ pair, so differences are purely algorithmic. The measured results:

The shape is a clean U: error falls from $n = 1$ to $n = 4$, then climbs again. The intermediate methods—neither TD(0) nor Monte Carlo—learn fastest. Exactly the result Sutton & Barto report, reproduced here from scratch.

Two further patterns in the measured data are worth noticing:

n-step SARSA: The Same Dial for Control

Everything above was prediction. To get a control method, do exactly what SARSA did to TD(0): switch from state values to action values and follow an ε-greedy policy. The n-step return simply ends in $Q(S_{t+n}, A_{t+n})$ instead of $V(S_{t+n})$, and the update targets $Q(S_\tau, A_\tau)$—everything else, including the n-step lag and the end-of-episode flush, carries over unchanged. Deeper backups pay off in control for the same reason they did in prediction, and often more visibly: when rewards are sparse, a single successful episode updates the last $n$ state-action pairs along the path instead of only the final one, so good news spreads $n$ times faster through the Q-table.

def nstep_sarsa_episode(env, Q, n, alpha=0.1, gamma=1.0, eps=0.1, rng=None):
    """One episode of on-policy n-step SARSA (tabular)."""
    rng = rng or np.random.default_rng()

    def eps_greedy(s):
        if rng.random() < eps:
            return rng.integers(len(Q[s]))
        return int(np.argmax(Q[s]))

    s = env.reset()
    a = eps_greedy(s)
    S, A, R = [s], [a], [0.0]        # R[0] unused; R[t+1] rewards transition t
    T, t = float('inf'), 0
    while True:
        if t < T:
            s2, r, done = env.step(A[t])
            S.append(s2); R.append(r)
            if done:
                T = t + 1
            else:
                A.append(eps_greedy(s2))
        tau = t - n + 1
        if tau >= 0:
            end = int(min(tau + n, T))
            G = sum(gamma ** (i - tau - 1) * R[i] for i in range(tau + 1, end + 1))
            if tau + n < T:
                G += gamma ** n * Q[S[tau + n]][A[tau + n]]
            Q[S[tau]][A[tau]] += alpha * (G - Q[S[tau]][A[tau]])
        if tau == T - 1:
            break
        t += 1

Summary

The n-step return $G_{t:t+n}$ generalizes both of our target constructions: $n$ real rewards, then a bootstrap. Measured on the 19-state random walk, intermediate depths win—$n = 4$ achieved RMS error 0.267 versus 0.348 for TD(0) and 0.361 for the deepest setting tested—because moderate n dilutes bootstrap bias without absorbing the full variance of a long return. The same dial converts to control as n-step SARSA.

But n-step methods force a discrete choice: one n for every state, every update, plus an n-step buffer and update lag. The next section asks a better question: why pick one n at all? Averaging all n-step returns—with a clever incremental implementation—gives us TD(λ) and eligibility traces.