n-Step TD Prediction

Why Does This Exist?

In reinforcement learning, estimating a state value function $V(s)$ requires an update target. Classical methods stand at two opposing extremes of a fundamental trade-off:

1. One-step Temporal Difference learning, or TD(0): Bootstraps immediately after experiencing a single transition ($n=1$). The target is $R_{t+1} + \gamma V(S_{t+1})$. Because it only depends on a single sample step, its variance is low. However, its target heavily relies on the current value estimate $V(S_{t+1})$. If the initial value estimates are poorly calibrated, TD(0) injects substantial estimation bias into every update. Furthermore, a terminal reward must trickle backwards one transition per episode, requiring many episodes for distant states to learn.
2. Monte Carlo (MC) prediction: Waits until the entire trajectory terminates ($n=\infty$) before computing the actual sample return $G_t = \sum_{k=0}^{T-t-1} \gamma^k R_{t+k+1}$. Because it uses actual realized rewards with zero bootstrapping, its target is completely unbiased. But accumulating dozens or hundreds of stochastic transitions introduces high sample variance. MC also cannot learn in non-terminating continuing tasks or mid-episode.

n-step TD prediction exists to bridge this gap. Instead of forcing an all-or-nothing choice between one step and complete termination, it parameterizes the lookahead horizon to an arbitrary integer $n \ge 1$. By accumulating $n$ steps of real environment transitions before substituting the remaining future with a bootstrapped value estimate, $n$-step TD lets practitioners dial the exact sweet spot between bias and variance. Empirically, intermediate horizons (such as $n \in [3, 10]$) learn significantly faster and achieve lower asymptotic error than either extreme.

Think of It Like This

How It Actually Works

Multi-Step Bootstrapping and the Error Reduction Property

Consider an agent interacting with an environment in discrete time steps $t = 0, 1, 2, \dots$. At time step $t$, the agent occupies state $S_t$, takes action $A_t$, transitions to state $S_{t+1}$, and receives a scalar reward $R_{t+1}$. The discount factor is $\gamma \in [0, 1]$, and the episode terminates at time step $T$.

1. The n-Step Return

The core object of $n$-step TD prediction is the $n$-step return, denoted $G_{t:t+n}$. It sums the first $n$ discounted rewards and bootstraps from the estimated value of the state visited $n$ steps into the future:

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

Where:

• $R_{t+k}$ is the reward observed at transition $k$.
• $\gamma^{k-1}$ discounts the reward received $k$ steps ahead.
• $V_{t+n-1}(S_{t+n})$ is the estimate of the value of state $S_{t+n}$ available at time $t+n-1$.
• $\gamma^n$ scales the bootstrapped value estimate.

If the trajectory reaches or surpasses terminal time step $T$ (that is, $t + n \ge T$), the return is simply truncated at $T$, and no bootstrapping occurs because the value of a terminal state is identically zero:

$G_{t:t+n} = G_t = \sum_{k=t+1}^T \gamma^{k-t-1} R_k \quad \text{when } t + n \ge T$

Notice the two boundary conditions:

• When $n = 1$: $G_{t:t+1} = R_{t+1} + \gamma V_t(S_{t+1})$, which is the standard one-step TD target.
• When $n = \infty$ (or $n \ge T - t$): $G_{t:\infty} = G_t$, which is the complete Monte Carlo return.

2. The Value Update Rule

Because computing $G_{t:t+n}$ requires knowledge of transitions up to time step $t+n$, the update for state $S_t$ cannot be executed at time $t$. It is delayed until time $t+n$.

Let $\tau = t - n + 1$ denote the index of the state being updated. When the agent reaches time step $t$ (for $t \ge n - 1$), it updates the value of the state visited at time $\tau \ge 0$:

$V_{t}(S_\tau) = V_{t-1}(S_\tau) + \alpha \left[ G_{\tau:\tau+n} - V_{t-1}(S_\tau) \right]$

Where:

• $\alpha \in (0, 1]$ is the step-size learning rate.
• $G_{\tau:\tau+n} - V_{t-1}(S_\tau)$ is the $n$-step TD error.
• All other state estimates remain unchanged: $V_t(s) = V_{t-1}(s)$ for all $s \ne S_\tau$.

When the episode terminates at step $T$, the agent must drain its buffer by continuing to apply updates for all remaining historical states $\tau = T - n + 1, \dots, T - 1$ until every visited state has been updated.

3. Theoretical Guarantee: The Error Reduction Property

Why is multi-step bootstrapping guaranteed to behave well? Sutton and Barto established the error reduction property of $n$-step returns:

$\max_s \left| \mathbb{E}_\pi \left[ G_{t:t+n} \mid S_t = s \right] - v_\pi(s) \right| \le \gamma^n \max_s \left| V(s) - v_\pi(s) \right|$

Where $v_\pi(s)$ is the true underlying value under policy $\pi$.

This theorem proves that the expected $n$-step return is guaranteed to be a strictly better estimate of $v_\pi$ than the current estimate $V$, shrinking the worst-case error by a geometric factor of at least $\gamma^n$. As $n$ increases, the worst-case bias decays exponentially at rate $\gamma^n$.

Worked numerical example

To see how $n$-step returns accelerate reward propagation, let us trace a single episode through a 5-step deterministic trajectory:

$\text{States: } S_0 \xrightarrow{R_1 = 1.0} S_1 \xrightarrow{R_2 = 2.0} S_2 \xrightarrow{R_3 = 0.0} S_3 \xrightarrow{R_4 = 10.0} S_4 \text{ (Terminal)}$

Let:

• Discount factor $\gamma = 0.9$
• Step size $\alpha = 0.5$
• Initial value estimates for all states: $V(s) = 0.0$ for all $s \in \{S_0, S_1, S_2, S_3, S_4\}$

We will compare the update applied to the starting state $S_0$ across $n=1$, $n=2$, $n=3$, and Monte Carlo ($n=4$):

Case 1: One-Step TD ($n = 1$)

At time step $t=1$, the agent observes transition $S_0 \to S_1$ with reward $R_1 = 1.0$. $\tau = 1 - 1 = 0 \implies \text{Updating } S_0$ $G_{0:1} = R_1 + \gamma V(S_1) = 1.0 + 0.9 \times (0.0) = 1.0000$ $V(S_0) \leftarrow 0.0 + 0.5 \times (1.0000 - 0.0) = \mathbf{0.5000}$

The large downstream reward $R_4 = 10.0$ has zero impact on $S_0$ in this episode.

Case 2: Two-Step TD ($n = 2$)

At time step $t=2$, the agent has observed $S_0 \to S_1 \to S_2$ with rewards $R_1 = 1.0, R_2 = 2.0$. $\tau = 2 - 2 = 0 \implies \text{Updating } S_0$ $G_{0:2} = R_1 + \gamma R_2 + \gamma^2 V(S_2) = 1.0 + 0.9 \times (2.0) + (0.9)^2 \times (0.0) = 1.0 + 1.8000 = 2.8000$ $V(S_0) \leftarrow 0.0 + 0.5 \times (2.8000 - 0.0) = \mathbf{1.4000}$

Now $S_0$ directly benefits from both $R_1$ and $R_2$, nearly tripling its value adjustment.

Case 3: Three-Step TD ($n = 3$)

At time step $t=3$, the agent has observed transitions up to $S_3$ with rewards $R_1 = 1.0, R_2 = 2.0, R_3 = 0.0$. $\tau = 3 - 3 = 0 \implies \text{Updating } S_0$ $G_{0:3} = R_1 + \gamma R_2 + \gamma^2 R_3 + \gamma^3 V(S_3) = 1.0 + 0.9 \times (2.0) + 0.81 \times (0.0) + 0.729 \times (0.0) = 2.8000$ $V(S_0) \leftarrow 0.0 + 0.5 \times (2.8000 - 0.0) = \mathbf{1.4000}$

Case 4: Full Monte Carlo ($n = 4$, Horizon Reaches Terminal $T=4$)

At time step $t=4$, the terminal state $S_4$ is reached. $\tau = 4 - 4 = 0 \implies \text{Updating } S_0$ $G_{0:4} = R_1 + \gamma R_2 + \gamma^2 R_3 + \gamma^3 R_4 = 1.0 + 0.9(2.0) + 0.81(0.0) + 0.729(10.0) = 1.0 + 1.8000 + 0.0 + 7.2900 = 10.0900$ $V(S_0) \leftarrow 0.0 + 0.5 \times (10.0900 - 0.0) = \mathbf{5.0450}$

Comparison Across the Full Episode

When the episode finishes and all buffered updates are drained, the learned values across all states are:

Notice how the terminal reward $R_4 = 10.0$ propagates backwards:

• In $n=1$, it only reaches $S_3$.
• In $n=2$, it reaches $S_3$ and $S_2$.
• In $n=3$, it reaches $S_3, S_2$, and $S_1$.
• In Monte Carlo, it travels all the way back to $S_0$ in a single episode.

Code

The following self-contained Python implementation processes an episodic trajectory using an explicit sliding window update buffer, properly handling the delayed updates and the end-of-episode draining phase.

1from typing import Dict, List, Optional, Tuple2
3
4def n_step_td_prediction(5    trajectory: List[Tuple[str, float]],6    n: int,7    gamma: float = 0.9,8    alpha: float = 0.5,9    initial_values: Optional[Dict[str, float]] = None,10) -> Dict[str, float]:11    """Computes state value estimates using episodic n-step TD prediction.12
13    Args:14        trajectory: List of (state, reward) tuples where reward is received15          upon entering state. First element is (S0, 0.0); last is (Terminal,16          final_reward).17        n: Number of lookahead steps before bootstrapping (n >= 1).18        gamma: Discount factor in [0, 1].19        alpha: Step size learning rate in (0, 1].20        initial_values: Optional initial state values dictionary.21
22    Returns:23        Dictionary mapping non-terminal state identifiers to updated values.24    """25    states = [step[0] for step in trajectory]26    rewards = [step[1] for step in trajectory]27    total_steps = len(trajectory) - 1  # Terminal step T28
29    # Initialize value dictionary30    v_table = (31        {s: 0.0 for s in set(states)}32        if initial_values is None33        else initial_values.copy()34    )35    terminal_state = states[total_steps]36    v_table[terminal_state] = 0.0  # Terminal state value is always 0.037
38    t = 039    while True:40        # tau is the index of the state whose estimate is currently being updated41        tau = t - n + 142
43        if tau >= 0:44            # 1. Sum observed rewards from step tau + 1 up to min(tau + n, T)45            g_return = 0.046            horizon = min(tau + n, total_steps)47            for i in range(tau + 1, horizon + 1):48                discount_power = i - tau - 149                g_return += (gamma**discount_power) * rewards[i]50
51            # 2. Add bootstrapped value estimate only if horizon does not reach terminal step52            if tau + n < total_steps:53                bootstrapped_state = states[tau + n]54                g_return += (gamma**n) * v_table[bootstrapped_state]55
56            # 3. Apply gradient-descent update rule to state S_tau57            state_to_update = states[tau]58            v_table[state_to_update] += alpha * (59                g_return - v_table[state_to_update]60            )61
62        # Termination condition: last updated state is T - 163        if tau == total_steps - 1:64            break65
66        t += 167
68    return {69        s: round(v_table[s], 4)70        for s in sorted(v_table.keys())71        if s != terminal_state72    }73
74
75# Trajectory: S0 -> (R=1.0) -> S1 -> (R=2.0) -> S2 -> (R=0.0) -> S3 -> (R=10.0) -> S4 (Terminal)76example_trajectory = [77    ("S0", 0.0),78    ("S1", 1.0),79    ("S2", 2.0),80    ("S3", 0.0),81    ("S4", 10.0),82]83
84print("n=1 (TD(0)):", n_step_td_prediction(example_trajectory, n=1))85print("n=2:        ", n_step_td_prediction(example_trajectory, n=2))86print("n=3:        ", n_step_td_prediction(example_trajectory, n=3))87print("n=4 (MC):   ", n_step_td_prediction(example_trajectory, n=4))88
89# -> Expected output:90# -> n=1 (TD(0)): {'S0': 0.5, 'S1': 1.0, 'S2': 0.0, 'S3': 5.0}91# -> n=2:         {'S0': 1.4, 'S1': 1.0, 'S2': 4.5, 'S3': 5.0}92# -> n=3:         {'S0': 1.4, 'S1': 5.05, 'S2': 4.5, 'S3': 5.0}93# -> n=4 (MC):    {'S0': 5.045, 'S1': 5.05, 'S2': 4.5, 'S3': 5.0}

Watch Out For

The Quick Version

• Tunable spectrum: $n$-step TD prediction bridges 1-step TD(0) and full Monte Carlo, letting you select an intermediate horizon $n$ that balances bootstrapping bias against trajectory variance.
• Delayed updates: Updates to state $S_\tau$ are computed at time $\tau + n$, requiring a memory buffer of size $n+1$ to store recent states and rewards.
• Faster reward propagation: Increasing $n$ propagates terminal rewards multiple steps backwards within a single episode, eliminating the single-transition bottleneck of TD(0).
• Error reduction guarantee: The expected $n$-step return is guaranteed to contract the maximum value error by at least $\gamma^n$, ensuring stable convergence toward the true value function $v_\pi$.

What to Read Next

• Temporal Difference Learning
• Monte Carlo Methods
• Forward View of TD(lambda)