n-step Bootstrapping

7.1 n-step TD prediction

If $t+n\ge T$, the missing terms are zero and $G_{t:t+n}\doteq G_t$ (the full return). The n-step return isn't available until time $t+n$, so:

No updates in the first $n-1$ steps of an episode; the same number of extra updates are made after termination.

Input: a policy π
Algorithm parameters: step size α ∈ (0, 1], a positive integer n
Initialize V(s) arbitrarily, for all s ∈ S
All store and access operations (for S_t and R_t) can take their index mod n + 1
Loop for each episode:
    Initialize and store S₀ ≠ terminal
    T ← ∞
    Loop for t = 0, 1, 2, …:
        If t < T, then:
            Take an action according to π(·|S_t)
            Observe and store the next reward as R_{t+1} and the next state as S_{t+1}
            If S_{t+1} is terminal, then T ← t + 1
        τ ← t − n + 1          (τ is the time whose state's estimate is being updated)
        If τ ≥ 0:
            G ← Σ_{i=τ+1}^{min(τ+n,T)} γ^{i−τ−1} R_i
            If τ + n < T, then: G ← G + γⁿ V(S_{τ+n})          (G_{τ:τ+n})
            V(S_τ) ← V(S_τ) + α [G − V(S_τ)]
    Until τ = T − 1

The expected n-step return is a better estimate of $v_\pi$ than $V$ is, in the worst-state sense — so all n-step TD methods converge to the correct predictions under appropriate conditions. TD(0) and MC are the extreme members of a family of sound methods.

Exercise 7.1 — with V fixed, the n-step error is a sum of TD errors: $G_{t:t+n}-V(S_t)=\sum_{k=t}^{\min(t+n,T)-1}\gamma^{k-t}\delta_k$ (generalising 6.6).

Example 7.1 — n-step TD on the random walk

5-state walk, first episode C → D → E → right (+1), all $V=0.5$: one-step updates only $V(E)$; two-step updates $V(D)$ and $V(E)$; three-step or more updates all three visited states toward 1, by the same amount.

Figure 7.2 uses a 19-state walk with outcome −1 on the left, +1 on the right, values initialised to 0. Measure: RMS error over the 19 states at the end of each episode, averaged over the first 10 episodes and 100 runs.

7.2 n-step Sarsa

Switch states for state–action pairs and use an ε-greedy policy. One-step Sarsa is now called Sarsa(0).

Initialize Q(s,a) arbitrarily, for all s ∈ S, a ∈ A
Initialize π to be ε-greedy with respect to Q, or to a fixed given policy
Algorithm parameters: step size α ∈ (0, 1], small ε > 0, a positive integer n
All store and access operations (for S_t, A_t, and R_t) can take their index mod n + 1
Loop for each episode:
    Initialize and store S₀ ≠ terminal
    Select and store an action A₀ ∼ π(·|S₀)
    T ← ∞
    Loop for t = 0, 1, 2, …:
        If t < T, then:
            Take action A_t
            Observe and store the next reward as R_{t+1} and the next state as S_{t+1}
            If S_{t+1} is terminal, then: T ← t + 1
            else: Select and store an action A_{t+1} ∼ π(·|S_{t+1})
        τ ← t − n + 1          (τ is the time whose estimate is being updated)
        If τ ≥ 0:
            G ← Σ_{i=τ+1}^{min(τ+n,T)} γ^{i−τ−1} R_i
            If τ + n < T, then G ← G + γⁿ Q(S_{τ+n}, A_{τ+n})          (G_{τ:τ+n})
            Q(S_τ, A_τ) ← Q(S_τ, A_τ) + α [G − Q(S_τ, A_τ)]
            If π is being learned, then ensure that π(·|S_τ) is ε-greedy wrt Q
    Until τ = T − 1

Figure 7.4 — why n-step methods speed up learning

All rewards are 0 except at G, and Q starts at 0. After one episode, one-step Sarsa strengthens only the last action before G; n-step Sarsa strengthens the last n actions — much more is learned from one episode.

n-step Expected Sarsa

$\bar V$ of a terminal state is 0. Expected approximate values recur throughout the rest of the book.

Exercise 7.4 — Sarsa's n-step return as a sum of "novel" TD errors: $G_{t:t+n}=Q_{t-1}(S_t,A_t)+\sum_{k=t}^{\min(t+n,T)-1}\gamma^{k-t}\big[R_{k+1}+\gamma Q_k(S_{k+1},A_{k+1})-Q_{k-1}(S_k,A_k)\big]$ — proven by telescoping: the $Q$ terms cancel pairwise, leaving the rewards plus $\gamma^nQ_{t+n-1}(S_{t+n},A_{t+n})$ (or nothing past T).

7.3 n-step off-policy learning (importance sampling)

Weight each n-step update by the relative probability of the n actions under π and $b$:

If π would never take some action ($\pi=0$), the return gets zero weight. If an action is much likelier under π than $b$, the return is over-weighted (it's characteristic of π but rare in the data). On-policy ($\pi=b$) ⇒ ρ = 1, so (7.9) and (7.11) generalise the on-policy updates.

Input: an arbitrary behavior policy b such that b(a|s) > 0, for all s ∈ S, a ∈ A
Initialize Q(s,a) arbitrarily, for all s ∈ S, a ∈ A
Initialize π to be greedy with respect to Q, or as a fixed given policy
Algorithm parameters: step size α ∈ (0, 1], a positive integer n
All store and access operations (for S_t, A_t, and R_t) can take their index mod n + 1
Loop for each episode:
    Initialize and store S₀ ≠ terminal
    Select and store an action A₀ ∼ b(·|S₀)
    T ← ∞
    Loop for t = 0, 1, 2, …:
        If t < T, then:
            Take action A_t
            Observe and store the next reward as R_{t+1} and the next state as S_{t+1}
            If S_{t+1} is terminal, then: T ← t + 1
            else: Select and store an action A_{t+1} ∼ b(·|S_{t+1})
        τ ← t − n + 1
        If τ ≥ 0:
            ρ ← Π_{i=τ+1}^{min(τ+n,T−1)} π(A_i|S_i) / b(A_i|S_i)          (ρ_{τ+1:τ+n})
            G ← Σ_{i=τ+1}^{min(τ+n,T)} γ^{i−τ−1} R_i
            If τ + n < T, then: G ← G + γⁿ Q(S_{τ+n}, A_{τ+n})          (G_{τ:τ+n})
            Q(S_τ, A_τ) ← Q(S_τ, A_τ) + α ρ [G − Q(S_τ, A_τ)]
            If π is being learned, then ensure that π(·|S_τ) is greedy wrt Q
    Until τ = T − 1

7.4 *Per-decision methods with control variates

Write the n-step return recursively, $G_{t:h}=R_{t+1}+\gamma G_{t+1:h}$ with $G_{h:h}\doteq V_{h-1}(S_h)$. Simply multiplying by $\rho_t$ would make the target 0 whenever $\rho_t=0$ (shrinking the estimate, high variance). Instead:

• If $\rho_t=0$ the target equals the current estimate ⇒ no change (ignore the sample) — sensible.
• The control variate has expected value zero ($\E[\rho_t]=1$, uncorrelated with the estimate) ⇒ the expected update is unchanged; variance is reduced. (Exercise 7.6)
• On-policy ($\rho_t=1$) it reduces to (7.1). Use it with the plain n-step TD update (7.2) — no extra ratios.

Recursion ends with $G_{h:h}\doteq Q_{h-1}(S_h,A_h)$ if $h\lt T$, or $G_{T-1:h}\doteq R_T$ if $h\ge T$. The first action is not importance-sampled. Exercise 7.8: with V fixed, (7.13) is $G_{t:h}=V(S_t)+\sum_{k=t}^{h-1}\gamma^{k-t}\big(\prod_{i=t}^{k}\rho_i\big)\delta_k$.

Importance sampling enables sound off-policy learning but gives high-variance updates (forcing small α, slow learning). Remedies: control variates, adaptive step sizes (Autostep), invariant updates, and — next — avoiding IS altogether.

7.5 Off-policy learning without importance sampling: n-step tree backup

Down the spine: sampled states, rewards and actions. Hanging off each state: the actions not selected — we have no data for them, so we bootstrap from their estimated values. The target is formed from the leaf nodes of the whole tree; interior (taken) action nodes don't contribute directly. Leaf weights:

• first-level non-selected $a$: $\pi(a\mid S_{t+1})$;
• second-level non-selected $a'$: $\pi(A_{t+1}\mid S_{t+1})\,\pi(a'\mid S_{t+2})$;
• third-level: $\pi(A_{t+1}|S_{t+1})\pi(A_{t+2}|S_{t+2})\pi(a''|S_{t+3})$, and so on.

Used with the plain n-step Sarsa update (7.5). Exercise 7.11: with fixed Q, $G_{t:t+n}=Q(S_t,A_t)+\sum_{k=t}^{\min(t+n-1,T-1)}\delta_k\prod_{i=t+1}^{k}\gamma\pi(A_i|S_i)$ with $\delta_t\doteq R_{t+1}+\gamma\bar V_t(S_{t+1})-Q(S_t,A_t)$.

Initialize Q(s,a) arbitrarily, for all s ∈ S, a ∈ A
Initialize π to be greedy with respect to Q, or as a fixed given policy
Algorithm parameters: step size α ∈ (0, 1], a positive integer n
All store and access operations can take their index mod n + 1
Loop for each episode:
    Initialize and store S₀ ≠ terminal
    Choose an action A₀ arbitrarily as a function of S₀; Store A₀
    T ← ∞
    Loop for t = 0, 1, 2, …:
        If t < T:
            Take action A_t; observe and store the next reward and state as R_{t+1}, S_{t+1}
            If S_{t+1} is terminal: T ← t + 1
            else: Choose an action A_{t+1} arbitrarily as a function of S_{t+1}; Store A_{t+1}
        τ ← t + 1 − n
        If τ ≥ 0:
            If t + 1 ≥ T: G ← R_T
            else: G ← R_{t+1} + γ Σ_a π(a|S_{t+1}) Q(S_{t+1}, a)
            Loop for k = min(t, T − 1) down through τ + 1:
                G ← R_k + γ Σ_{a≠A_k} π(a|S_k) Q(S_k, a) + γ π(A_k|S_k) G
            Q(S_τ, A_τ) ← Q(S_τ, A_τ) + α [G − Q(S_τ, A_τ)]
            If π is being learned, then ensure that π(·|S_τ) is greedy wrt Q
    Until τ = T − 1

7.6 *A unifying algorithm: n-step Q(σ)

Decide step by step whether to sample the action (σ = 1, like Sarsa) or take the expectation over actions (σ = 0, like tree backup). σ_t ∈ [0, 1] may even vary continuously and depend on the state/action.

Recursion ends with $G_{h:h}\doteq Q_{h-1}(S_h,A_h)$ if $h\lt T$, or $G_{T-1:T}\doteq R_T$. Use with the plain update (7.5).

Input: an arbitrary behavior policy b such that b(a|s) > 0, for all s ∈ S, a ∈ A
Initialize Q(s,a) arbitrarily, for all s ∈ S, a ∈ A
Initialize π to be greedy with respect to Q, or else it is a fixed given policy
Algorithm parameters: step size α ∈ (0, 1], a positive integer n
Loop for each episode:
    Initialize and store S₀ ≠ terminal
    Choose and store an action A₀ ∼ b(·|S₀)
    T ← ∞
    Loop for t = 0, 1, 2, …:
        If t < T:
            Take action A_t; observe and store the next reward and state as R_{t+1}, S_{t+1}
            If S_{t+1} is terminal: T ← t + 1
            else:
                Choose and store an action A_{t+1} ∼ b(·|S_{t+1})
                Select and store σ_{t+1}
                Store π(A_{t+1}|S_{t+1}) / b(A_{t+1}|S_{t+1}) as ρ_{t+1}
        τ ← t − n + 1
        If τ ≥ 0:
            If t + 1 < T: G ← Q(S_{t+1}, A_{t+1})
            Loop for k = min(t + 1, T) down through τ + 1:
                if k = T: G ← R_T
                else:
                    V̄ ← Σ_a π(a|S_k) Q(S_k, a)
                    G ← R_k + γ (σ_k ρ_k + (1 − σ_k) π(A_k|S_k)) (G − Q(S_k, A_k)) + γ V̄
            Q(S_τ, A_τ) ← Q(S_τ, A_τ) + α [G − Q(S_τ, A_τ)]
            If π is being learned, then ensure that π(·|S_τ) is greedy wrt Q
    Until τ = T − 1

7.7 Summary

Hyperparameters in this chapter

Self-test

Chapter quiz — check your understanding

Scored quiz: pick an answer (or type a number) to get instant feedback and an explanation. Questions marked Exam-style give you values to interpret (sweeps, logs, returns, learning curves), the way exam problems do. Your best score is saved in this browser and shown on the home page. "Shuffle & restart" re-orders the questions.