n-Step Bootstrapping Methods

Consider a trajectory $S_0, A_0, R_1, S_1, A_1, R_2, S_2, \dots$ generated under a policy $\pi$. The one-step TD target is $R_{t+1} + \gamma V(S_{t+1})$: it uses exactly one real reward and then bootstraps, substituting the current value estimate for everything that would happen afterward. The Monte Carlo target is the full return $G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots$, using every real reward until termination and no bootstrapping at all. The n-step return generalizes both by truncating the sum after n real rewards and bootstrapping there:

Here $V_{t+n-1}$ denotes the value function estimate available at time $t+n-1$ (subscripting the estimate this way is the standard convention that makes the update rule well-defined even mid-episode). If $t+n \geq T$ (the episode terminates before n steps elapse), the bootstrap term is simply dropped and $G_{t:t+n} = G_t$, the ordinary return. The update rule mirrors one-step TD exactly, just applied n steps later:

This is still a form of Bootstrapping and the Bias-Variance Tradeoff: the target is not the true expected return, but an estimate contaminated by whatever error currently sits in $V(S_{t+n})$. As n grows, that contamination shrinks — after n steps the bootstrapped term is discounted by $\gamma^n$, so its influence on the target decays geometrically — while the variance contributed by the n sampled rewards grows, since each reward is itself a random variable. The n-step return is a genuine statistical interpolation: it is provably less biased than the one-step target (whenever $V$ is inaccurate) and provably lower-variance than the full Monte Carlo return, for any finite n and $0 < \gamma < 1$. A crucial structural fact: because $G_{t:t+n}$ requires rewards $R_{t+1}, \dots, R_{t+n}$ and state $S_{t+n}$, the update for $V(S_t)$ cannot be performed until time $t + n$. This delay is the price of looking further ahead, and it is the central bookkeeping challenge in implementing these algorithms correctly.

n-step TD prediction. The agent walks the trajectory, and at each time step $\tau$ once $\tau + n$ rewards have been observed (or the episode has ended), it computes $G_{\tau:\tau+n}$ and updates $V(S_\tau)$. A circular buffer of the last $n{+}1$ states and $n$ rewards is the natural implementation, since only that much history is needed at any moment. ``` Algorithm: n-step TD for estimating V ≈ v_π Input: policy π, step size α ∈ (0,1], integer n ≥ 1 Initialize V(s) arbitrarily for all states s for each episode: Initialize and store S_0 T ← ∞ # will hold the episode length once known for t = 0, 1, 2, ...: if t < T: take action A_t ~ π(·|S_t) observe and store R_{t+1}, S_{t+1} if S_{t+1} is terminal: T ← t + 1 τ ← t - n + 1 # time whose estimate is being updated if τ ≥ 0: G ← 0 for i = τ+1 to min(τ+n, T): G ← G + γ^(i-τ-1) R_i if τ + n < T: G ← G + γ^n V(S_{τ+n}) V(S_τ) ← V(S_τ) + α (G - V(S_τ)) if τ == T - 1: break # all remaining updates done, episode finished ``` Two indexing subtleties deserve emphasis. First, $\tau = t - n + 1$ is the time step being updated, which lags the current simulation time $t$ by $n-1$ steps; this is the most common source of off-by-one bugs. Second, the loop must keep running for $n-1$ extra iterations after* the episode terminates at $T$, because early time steps like $\tau = T - n$ still need their (now fully realized, no-bootstrap) n-step return computed — this is why the loop condition is on $\tau$ reaching $T-1$, not on the episode-generation step reaching $T$.

n-step SARSA for control. The same idea lifts directly to action-value control by bootstrapping on $Q(S_{t+n}, A_{t+n})$ instead of $V(S_{t+n})$, using the action actually selected by the current (on-policy) behavior:

``` Algorithm: n-step SARSA for estimating Q ≈ q_π (or q_ with GLIE policy) Input: step size α ∈ (0,1], small ε > 0, integer n ≥ 1 Initialize Q(s,a) arbitrarily for all s,a; policy π = ε-greedy w.r.t. Q for each episode: Initialize S_0; choose A_0 ~ π(·|S_0) T ← ∞ for t = 0, 1, 2, ...: if t < T: take action A_t, observe R_{t+1}, S_{t+1} if S_{t+1} is terminal: T ← t + 1 else: choose A_{t+1} ~ π(·|S_{t+1}) # on-policy next action τ ← t - n + 1 if τ ≥ 0: G ← 0 for i = τ+1 to min(τ+n, T): G ← G + γ^(i-τ-1) R_i if τ + n < T: G ← G + γ^n Q(S_{τ+n}, A_{τ+n}) Q(S_τ, A_τ) ← Q(S_τ, A_τ) + α (G - Q(S_τ, A_τ)) update π to be ε-greedy w.r.t. Q # policy improves online if τ == T - 1: break ``` Because $A_{t+1}$ is chosen before it is needed as the bootstrap action, the algorithm must select actions one step ahead of when they are consumed in the update — exactly analogous to ordinary SARSA: On-Policy TD Control, just with the bootstrap pushed n steps further down the trajectory.

Off-policy n-step control. If the behavior policy $b$ differs from the target policy $\pi$, each of the n actions along the segment must be corrected by an importance-sampling ratio $\rho_{t:t+n-1} = \prod_{k=t}^{t+n-1} \frac{\pi(A_k|S_k)}{b(A_k|S_k)}$, and the update becomes $Q(S_t, A_t) \leftarrow Q(S_t,A_t) + \alpha \, \rho_{t+1:t+n-1}\big[G_{t:t+n} - Q(S_t,A_t)\big]$. Each additional factor in the product can push the ratio toward 0 or blow it up, so variance grows multiplicatively with n — this is the direct control-side manifestation of the bias-variance cost analyzed below. (n-step tree-backup and $Q(\sigma)$ are further refinements that reduce or eliminate this variance blow-up, but they are extensions beyond the scope of the core method.)

Time complexity. Each n-step update requires summing n discounted rewards, an $O(n)$ operation if computed naively as shown in the pseudocode. In practice this sum is almost always maintained incrementally: on each new time step, the buffered partial return can be updated in $O(1)$ by adding the new discounted reward and removing the oldest bootstrap contribution, since $G_{t:t+n}$ and $G_{t+1:t+n+1}$ share $n-1$ common reward terms. With that optimization, each of the $T$ time steps in an episode costs $O(1)$ amortized work, so a full episode is processed in $O(T)$ total time, identical in order to one-step TD or Monte Carlo — the constant factor grows with n but the asymptotic behavior does not change. Space is $O(n)$: a sliding window must retain the last $n{+}1$ states, $n$ rewards, and (for SARSA) $n$ actions, versus $O(1)$ for TD(0) and $O(T)$ for a naive Monte Carlo implementation that stores an entire episode.

Bias–variance derivation. Fix a state $S_t = s$ and write $v_\pi(s)$ for the true value. Decompose the error of the n-step target:

This holds because the real-reward prefix $R_{t+1} + \cdots + \gamma^{n-1}R_{t+n} + \gamma^n v_\pi(S_{t+n})$ is, by the definition of $v_\pi$ as an expected return, an unbiased estimator of $v_\pi(s)$ — the only source of bias is substituting the (possibly wrong) current estimate $V_{t+n-1}$ for the true $v_\pi$ at the horizon, and that substitution error is attenuated by $\gamma^n$. So:

• As $n \to \infty$ (or $\gamma < 1$ fixed and $n$ reaches episode length), $\gamma^n \to 0$: bias vanishes, recovering the unbiased Monte Carlo return.
• As $n \to 1$, bias equals $\gamma \, \mathbb{E}[V_t(S_{t+1}) - v_\pi(S_{t+1})]$, the full one-step TD bias, present whenever $V$ has not yet converged.

For variance, treat the $n$ reward random variables as (approximately, for a fixed policy) having bounded variance $\sigma_R^2$ each and being suitably weakly correlated; the discounted-sum variance grows roughly as

a strictly increasing function of n for $\gamma>0$: every additional real reward folded into the target adds sampling noise that no bootstrap could have contributed, since the bootstrap only contracts the tail of the sum, not the prefix. This formalizes the intuitive tradeoff: larger n monotonically trades bias for variance.

Convergence. Under the standard stochastic-approximation conditions — a tabular representation, every state visited infinitely often, and step sizes satisfying $\sum_t \alpha_t = \infty$, $\sum_t \alpha_t^2 < \infty$ — n-step TD converges to $v_\pi$ with probability 1 for any fixed finite n, by the same Robbins–Monro argument used for one-step TD: the n-step operator is still a contraction in expectation toward $v_\pi$ under the sup-norm (composing n applications of the Bellman evaluation operator with one bootstrap step preserves the contraction property, since the Bellman operator itself is a $\gamma$-contraction and $\gamma^n < 1$). n-step SARSA converges to $q_\pi$ analogously under a fixed policy, and to $q_*$ under GLIE (greedy in the limit with infinite exploration) policy schedules, mirroring one-step SARSA's control convergence guarantee.

Empirical tradeoff. Neither $n=1$ nor $n=\infty$ is typically optimal in practice with function approximation and a finite number of episodes: an intermediate n minimizes root-mean-square error in classic benchmarks (e.g., the random walk task from Sutton & Barto), because the reduction in bias from moderate n outweighs the added variance until n grows too large, at which point variance dominates and error rises again — an empirical U-shaped curve in n that directly reflects the bias/variance decomposition above.

Consider a 5-state random walk: states $A, B, C, D, E$ arranged left to right, with two terminal absorbing states at the far left (reward 0) and far right (reward +1); all other rewards are 0, $\gamma = 1$, and the agent starts every episode at $C$. Initialize $V(A)=V(B)=V(C)=V(D)=V(E)=0.5$. Suppose one episode runs: $C \to D \to E \to \text{Terminal(right)}$, giving rewards $R_1=0, R_2=0, R_3=1$, so $T=3$. Take $n=2$, $\alpha = 0.1$.

Trace notes: at $t=1$ ($\tau=0$), $S_{\tau+n}=S_2=E$ is not yet terminal at the moment the update is computed (termination is discovered at $t=2$), so the bootstrap term $\gamma^n V(E)=0.5$ correctly enters; because $V(E)$ was still 0.5 at that point, the update happens to leave $V(C)$ unchanged this episode. At $\tau=1$, however, $\tau+n = 3 = T$, so the algorithm correctly drops the bootstrap term entirely and uses the full realized 2-step sum of rewards, propagating the terminal $+1$ reward two states backward in a single update — something one-step TD ($n=1$) could not do until at least two separate episodes of updates. This is precisely the mechanism by which larger n propagates delayed reward information faster: $D$'s value moves from $0.5$ toward $1.0$ after just one episode, whereas one-step TD would need the +1 reward to first update $E$, and only in a later episode update $D$ from the improved $V(E)$. The final loop iterations ($t=3,4$ conceptually) handle $\tau=2$ (updating $E$ from $R_3$ alone, no bootstrap) and then terminate since $\tau = T-1 = 2$.

n-step methods emerged from the same lineage that produced Temporal-Difference Learning itself, as researchers explored the design space between the two limiting cases of bootstrapped and unbootstrapped prediction.

n-step returns are a default ingredient in modern deep reinforcement learning rather than a theoretical curiosity. Rainbow DQN combines n-step returns (typically n=3) with double Q-learning, prioritized replay, and distributional value functions, and ablations show n-step returns among the most impactful individual components for Atari performance. Actor-critic architectures such as A3C and IMPALA compute n-step (or truncated λ-return) advantage estimates to reduce the variance of policy-gradient updates while still enabling efficient rollout-based parallel training. Robotics and continuous-control agents commonly use short n-step horizons (n = 3 to 10) to balance sample efficiency against the instability that very long, high-variance rollouts introduce into function-approximated value learning. The concept also underlies generalized advantage estimation (GAE), which can be understood as a soft, exponentially-weighted average over n-step advantage estimates — directly foreshadowing how TD(lambda) and Eligibility Traces averages over all n simultaneously rather than committing to one fixed horizon.

Ask the tutor: How does the choice of n interact with function approximation error when the value network itself is inaccurate at long horizons?