Chapter 7: n-step Bootstrapping

This chapter unifies MC methods and one-step TD methods. n-step TD methods generalize both so one can smoothly shift between them. n-step methods span a spectrum with MC at one end and one-step TD at the other. The best methods are often intermediate between the two extremes.

n-step methods free you from the tyranny of the time step. With one-step TD, the same time step determines how often actions change and the bootstrapping interval. n-step methods enable bootstrapping over multiple steps.

MC uses the complete return G_t. One-step TD uses G_t:t+1 = R_t+1 + γV(S_t+1). The n-step return interpolates between them:

The n-step TD update is:

Example 7.1: On a 19-state random walk, n-step TD with intermediate n values (e.g., n=4 or 8) outperforms both one-step TD (n=1) and MC (n→∞), illustrating the benefit of intermediate bootstrapping.

n-step Sarsa extends Sarsa by switching states for state–action pairs. The n-step return for action values:

Figure 7.4 shows that one-step Sarsa only strengthens the last action before a high reward, while n-step Sarsa strengthens the last n actions — dramatically speeding up learning from a single episode.

n-step Expected Sarsa replaces the last state–action pair with a branch over all actions weighted by π, using V̄_t(s) = Σ_a π(a|s)Q_t(s,a).

For off-policy n-step methods, we weight returns by the importance sampling ratio ρ_t:h for the n actions from A_t to A_h:

For n-step TD prediction: V(S_t) ← V(S_t) + αρ_t:t+n-1[G_t:t+n − V(S_t)]. For n-step Sarsa control: Q(S_t,A_t) ← Q(S_t,A_t) + αρ_t+1:t+n[G_t:t+n − Q(S_t,A_t)]. Note the ratio starts one step later for action values.

A more sophisticated off-policy approach uses per-decision importance sampling with control variates. The n-step return is defined recursively:

If ρ_t=0 (action never selected by π), the target equals the current estimate (no update), rather than zero (which would shrink the estimate). The control variate (1−ρ_t)V_h-1(S_t) doesn't change the expected update but reduces variance.

The tree-backup algorithm enables off-policy learning without importance sampling. The target includes the estimated values of all "dangling" action nodes not selected, weighted by their probability under π.

The tree backup can be viewed as alternating sample half-steps and expected half-steps. It generalizes Q-learning to multi-step with stochastic target policies. However, if π is substantially different from b, bootstrapping may span only a few steps even if n is large (because π(A_k|S_k) can be small).

n-step Q(σ) unifies Sarsa, tree-backup, and Expected Sarsa by introducing a parameter σ_t ∈ [0,1] that controls the degree of sampling vs. expectation on each step:

σ=1 → Sarsa (full sampling), σ=0 → tree backup (pure expectation), Expected Sarsa → σ=1 for all steps except the last (σ=0).

n-step methods with intermediate bootstrapping typically outperform both extremes (1-step TD and MC). They involve a delay of n steps before updating and require more memory/computation. Two off-policy approaches: (1) importance sampling (high variance), (2) tree backup (no IS but limited effective horizon). In Chapter 12, eligibility traces will implement multi-step TD with minimal overhead.