---
title: n-Step Bootstrapping
module: Tabular Solution Methods
moduleNumber: 2
lessonNumber: 7
order: 207
summary: >
  Monte Carlo waits for the full return; one-step TD bootstraps after a single
  reward. Between them lies a whole spectrum, indexed by one integer n: look
  ahead n real rewards, then bootstrap from the value n steps out. The n-step
  return unifies the previous two lessons, and — on the random walk — an
  intermediate n beats both extremes. We build the n-step return, the n-step TD
  update, the backup-diagram spectrum, and n-step Sarsa for control.
topics: [Tabular Methods]
sources:
  - book: Sutton & Barto
    ref: "Ch. 7 — n-step Bootstrapping; §7.1 n-step TD Prediction; §7.2 n-step Sarsa"
---

The last two lessons drew the same estimation problem from opposite ends.
[Monte Carlo](/reinforcement-learning/tabular-methods/monte-carlo-methods) waits
until an episode terminates and updates each visited state toward the full
observed return — no bootstrapping, but no learning until the very end.
[Temporal-difference learning](/reinforcement-learning/tabular-methods/temporal-difference-learning)
updates after a single step, using one real reward $R_{t+1}$ plus the current
estimate $V(S_{t+1})$ as a stand-in for everything after — all bootstrapping,
and online. The two are the endpoints of one family, indexed by a single
integer $n$.

An **$n$-step method** looks ahead exactly $n$ real rewards and
then bootstraps from the estimated value of the state reached $n$ steps later.
Set $n = 1$ and you recover one-step TD; let $n$ run to the end of the episode
and you recover Monte Carlo. Every value of $n$ in between is a genuine method,
and an intermediate $n$ often learns faster than either extreme.[^sb-nstep]

## The n-step return

Fix the state–reward sequence an agent generates while following $\pi$,

$$
S_t,\, R_{t+1},\, S_{t+1},\, R_{t+2},\, \ldots,\, R_T,\, S_T,
$$

where $T$ is the terminal step (actions omitted for now). Whatever method we use
to estimate $v_\pi(S_t)$, it updates $V(S_t)$ toward some **target**. The
different members of the family are just different choices of target.

Monte Carlo aims at the complete return, every reward until termination:

$$
G_t \;\doteq\; R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots + \gamma^{T-t-1} R_T.
$$

One-step TD truncates after a single reward and patches the missing tail with a
bootstrapped estimate — the **one-step return**:

$$
G_{t:t+1} \;\doteq\; R_{t+1} + \gamma\, V_t(S_{t+1}),
$$

where $V_t$ is the estimate of $v_\pi$ at time $t$. The subscript notation
$G_{t:t+1}$ reads "a return for time $t$ using rewards up through time $t+1$":
the discounted estimate $\gamma\, V_t(S_{t+1})$ takes the place of the discarded
tail $\gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots + \gamma^{T-t-1} R_T$. The same
idea extends past one step. A **two-step return** keeps two real rewards and
bootstraps from the value two steps out,

$$
G_{t:t+2} \;\doteq\; R_{t+1} + \gamma R_{t+2} + \gamma^2\, V_{t+1}(S_{t+2}),
$$

where $\gamma^2 V_{t+1}(S_{t+2})$ now corrects for the absence of
$\gamma^2 R_{t+3} + \cdots + \gamma^{T-t-1} R_T$. In general, the target for an
arbitrary $n$-step update is the **$n$-step return**:

$$
G_{t:t+n} \;\doteq\; R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^{n-1} R_{t+n} + \gamma^{n}\, V_{t+n-1}(S_{t+n}),
$$

for all $n \ge 1$ and $0 \le t < T - n$. Every $n$-step return is an
approximation to the full return $G_t$, truncated after $n$ rewards and then
corrected for the remaining missing terms by $\gamma^n V_{t+n-1}(S_{t+n})$. If
the horizon runs to or past termination — that is, if $t + n \ge T$ — all the
missing terms are already zero, and the $n$-step return equals the ordinary full
return: $G_{t:t+n} \doteq G_t$ whenever $t + n \ge T$.

> **Definition ($n$-step return).** For $n \ge 1$, the $n$-step return from time
> $t$ is
> $$
> G_{t:t+n} \doteq \sum_{k=1}^{n} \gamma^{k-1} R_{t+k} \;+\; \gamma^{n}\, V_{t+n-1}(S_{t+n}),
> $$
> the first $n$ real rewards, discounted, followed by the estimated value of the
> state reached $n$ steps out. At the two extremes it is the one-step TD target
> ($n=1$) and the Monte Carlo return ($n \to \infty$, i.e. $t + n \ge T$).

One subtlety: the $n$-step return for step $t$ uses
future rewards $R_{t+1}, \ldots, R_{t+n}$ and the future state $S_{t+n}$ — none
of which exist at time $t+1$. No real algorithm can use $G_{t:t+n}$ until it has
seen $R_{t+n}$ and computed $V_{t+n-1}$; the first moment all of that is
available is time $t+n$. This lag is unavoidable when looking ahead, and it
shapes the pseudocode below.

## The n-step TD update

With the target in hand, the update follows directly. At time $t+n$ (the first
moment $G_{t:t+n}$ is computable) we move $V(S_t)$ a fraction $\alpha$ of the
way toward it:

$$
V_{t+n}(S_t) \;\doteq\; V_{t+n-1}(S_t) \;+\; \alpha\,\big[\, G_{t:t+n} - V_{t+n-1}(S_t) \,\big],
\qquad 0 \le t < T,
$$

while every other state's estimate is left unchanged, $V_{t+n}(s) =
V_{t+n-1}(s)$ for $s \ne S_t$. This is **$n$-step TD**. The bracketed quantity
is the familiar TD error, but with an $n$-step target in place of the one-step
one. Because the update for $S_t$ fires only at $t+n$, the first $n-1$ states of
each episode get no update as the episode begins; to compensate, an equal number
of updates are made at the end, after termination, before the next episode
starts.

```algorithm
caption: $\textsc{n-Step-TD}$ — estimate $V \approx v_\pi$
input: a policy $\pi$; step size $\alpha \in (0,1]$; a positive integer $n$
initialize $V(s)$ arbitrarily for all $s$
for each episode do
  initialize and store $S_0 \ne$ terminal
  $T \gets \infty$
  for $t = 0, 1, 2, \ldots$ do
    if $t < T$ then
      take an action according to $\pi(\cdot \mid S_t)$
      observe and store $R_{t+1}$ and $S_{t+1}$
      if $S_{t+1}$ is terminal then
        $T \gets t + 1$
    $\tau \gets t - n + 1$ // $\tau$ = time whose estimate is updated now
    if $\tau \ge 0$ then
      $G \gets \sum_{i=\tau+1}^{\min(\tau+n,\,T)} \gamma^{\,i-\tau-1} R_i$
      if $\tau + n < T$ then
        $G \gets G + \gamma^{n} V(S_{\tau+n})$ // bootstrap
      $V(S_\tau) \gets V(S_\tau) + \alpha\,[\,G - V(S_\tau)\,]$
  until $\tau = T - 1$
```

The index $\tau = t - n + 1$ is the state currently being updated: at wall-clock
time $t$ we have just enough lookahead to finish the update for the state $n-1$
steps in the past. All storage can be kept modulo $n+1$, since only the last
$n+1$ states and rewards ever matter at once — the method's memory is bounded by
$n$, not by the episode length.

### Why an intermediate n is sound

That $n$-step returns interpolate between two known-good methods does not by
itself prove they converge. The guarantee comes from a worst-case bound. The
intuition: each real reward folded into the target is observed rather than
estimated, so it reduces the target's dependence on the error in the
bootstrapped estimate; after $n$ steps only a $\gamma^n$ fraction of that error
remains. Formally, the expectation of the $n$-step return is a better
estimate of
$v_\pi$ than $V_{t+n-1}$ is, in the following sense: its worst error over states
is at most $\gamma^n$ times the worst error of the current estimate,

$$
\max_s \Big| \,\mathbb{E}_\pi\!\big[\, G_{t:t+n} \mid S_t = s \,\big] - v_\pi(s)\, \Big|
\;\le\; \gamma^n \, \max_s \big| \,V_{t+n-1}(s) - v_\pi(s)\, \big|,
$$

for all $n \ge 1$. This is the **error-reduction property**. Because $\gamma^n <
1$, each expected $n$-step backup contracts the worst-case error, and one can
show from this that $n$-step TD converges to the correct $v_\pi$ under
appropriate conditions. Every method in the family is sound; one-step TD and
Monte Carlo are simply its two extreme members.

> **Definition (Error-reduction property).** The worst-state error of the
> expected $n$-step return is bounded by $\gamma^n$ times the worst-state error
> of the value function it bootstraps from. The larger $n$, the more real reward
> enters the target and the smaller the residual dependence on the (possibly
> wrong) estimate — at the cost of higher variance.

### A worked n-step target

For example, take $\gamma = 0.9$, and
suppose an agent following $\pi$ produces the reward stream

$$
R_{t+1} = 2,\quad R_{t+2} = 0,\quad R_{t+3} = 1,\quad R_{t+4} = 3,\quad R_{t+5} = 0,\; \ldots
$$

with current value estimates $V(S_{t+1}) = 5$, $V(S_{t+2}) = 4$, $V(S_{t+3}) = 6$,
and $V(S_{t+4}) = 2$. The **one-step return** keeps one real reward and bootstraps
from the very next state:

$$
G_{t:t+1} = R_{t+1} + \gamma V(S_{t+1}) = 2 + 0.9\cdot 5 = 6.5.
$$

The **two-step return** keeps two rewards and bootstraps two states out:

$$
G_{t:t+2} = R_{t+1} + \gamma R_{t+2} + \gamma^2 V(S_{t+2})
          = 2 + 0.9\cdot 0 + 0.81\cdot 4 = 5.24.
$$

The **three-step return** keeps three:

$$
G_{t:t+3} = 2 + 0.9\cdot 0 + 0.81\cdot 1 + 0.729\cdot 6
          = 2 + 0 + 0.81 + 4.374 = 7.184.
$$

Each target is the same shape — accumulated discounted reward, then one bootstrap
term $\gamma^n V(S_{t+n})$ standing in for everything past the horizon. The three
targets differ in the depth at which they rely on the estimate: $G_{t:t+1}$
depends almost entirely on $V(S_{t+1}) = 5$, while $G_{t:t+3}$ has replaced two
layers of that estimate with real rewards and now depends on $V(S_{t+3}) = 6$. If
the early estimates were biased, the deeper target has removed more of that bias
— the error-reduction property in a single trajectory. The bootstrap weight
itself shrinks with depth: $\gamma^1 = 0.9$, $\gamma^2 = 0.81$, $\gamma^3 = 0.729$,
so the further out the bootstrap, the less it can distort the target.

## The backup-diagram spectrum

The family is easiest to see through its
[backup diagrams](/reinforcement-learning/foundations/value-functions-and-optimality).
Each diagram traces the states and rewards whose values are backed up into the
root. One-step TD backs up from a single reward and one bootstrapped state;
$n$-step TD strings $n$ rewards down a spine before bootstrapping; Monte Carlo
extends the spine all the way to the terminal square. The whole family is one
picture at increasing depth.

$$
% caption: The backup-diagram spectrum of $n$-step TD. Left to right, the spine
% deepens: one-step TD ($n{=}1$) backs up from a single reward and one
% bootstrapped state, $n$-step TD from $n$ rewards, and $\infty$-step TD from the
% whole episode down to the terminal square — Monte Carlo. The final open circle
% of each column (or the terminal square) is where the estimate is bootstrapped.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  st/.style={circle, draw, fill=white, minimum size=3.6mm, inner sep=0pt},
  ac/.style={circle, draw, fill=black, minimum size=1.7mm, inner sep=0pt},
  term/.style={rectangle, draw, fill=black!30, minimum size=3.6mm, inner sep=0pt}]
  \definecolor{acc}{HTML}{2348F2}
  % ---- column 1: 1-step ----
  \node[st] (a0) at (0,4) {};
  \node[ac] (a1) at (0,3.3) {};
  \node[st] (a2) at (0,2.6) {};
  \draw[black] (a0) -- (a1) -- (a2);
  \node[align=center, font=\scriptsize] at (0,4.9) {1-step TD\\and TD(0)};
  % ---- column 2: 2-step ----
  \node[st] (b0) at (1.6,4) {};
  \node[ac] (b1) at (1.6,3.3) {};
  \node[st] (b2) at (1.6,2.6) {};
  \node[ac] (b3) at (1.6,1.9) {};
  \node[st] (b4) at (1.6,1.2) {};
  \draw[black] (b0) -- (b1) -- (b2) -- (b3) -- (b4);
  \node[font=\scriptsize] at (1.6,4.9) {2-step TD};
  % ---- column 3: 3-step ----
  \node[st] (c0) at (3.2,4) {};
  \node[ac] (c1) at (3.2,3.3) {};
  \node[st] (c2) at (3.2,2.6) {};
  \node[ac] (c3) at (3.2,1.9) {};
  \node[st] (c4) at (3.2,1.2) {};
  \node[ac] (c5) at (3.2,0.5) {};
  \node[st] (c6) at (3.2,-0.2) {};
  \draw[black] (c0) -- (c1) -- (c2) -- (c3) -- (c4) -- (c5) -- (c6);
  \node[font=\scriptsize] at (3.2,4.9) {3-step TD};
  % ---- ellipsis ----
  \foreach \dx in {-0.2,0,0.2} \fill[black] (4.5+\dx,1.9) circle (0.9pt);
  % ---- column 4: n-step ----
  \node[st] (d0) at (5.8,4) {};
  \node[ac] (d1) at (5.8,3.3) {};
  \node[st] (d2) at (5.8,2.6) {};
  \node[ac] (d3) at (5.8,1.9) {};
  \node[st] (d4) at (5.8,1.2) {};
  \draw[black] (d0) -- (d1) -- (d2) -- (d3) -- (d4);
  \node[font=\scriptsize] at (5.8,0.65) {$\vdots$};
  \node[ac] (d5) at (5.8,0.0) {};
  \node[st] (d6) at (5.8,-0.7) {};
  \draw[black] (d5) -- (d6);
  \node[font=\scriptsize] at (5.8,4.9) {n-step TD};
  % ---- ellipsis ----
  \foreach \dx in {-0.2,0,0.2} \fill[black] (7.1+\dx,1.9) circle (0.9pt);
  % ---- column 5: infinity / MC ----
  \node[st] (e0) at (8.4,4) {};
  \node[ac] (e1) at (8.4,3.3) {};
  \node[st] (e2) at (8.4,2.6) {};
  \node[ac] (e3) at (8.4,1.9) {};
  \node[st] (e4) at (8.4,1.2) {};
  \draw[black] (e0) -- (e1) -- (e2) -- (e3) -- (e4);
  \node[font=\scriptsize] at (8.4,0.65) {$\vdots$};
  \node[ac] (e5) at (8.4,0.0) {};
  \node[term] (e6) at (8.4,-0.7) {};
  \draw[black] (e5) -- (e6);
  \node[align=center, font=\scriptsize] at (8.4,4.95) {inf-step TD\\and Monte Carlo};
\end{tikzpicture}
$$

Depth controls a bias–variance tradeoff: shallow backups (small $n$) depend
heavily on the bootstrapped estimate, so they are low-variance but inherit
whatever bias sits in $V$; deep backups (large $n$) use more real reward,
shedding bias but taking on the variance of long reward sequences. The best
depth is intermediate and task-dependent.

## An intermediate n beats both extremes

The random walk quantifies the tradeoff. Take a chain of $19$ states with a
terminal on each end, an outcome of $-1$ on the left and $+1$ on the right, all
values initialized to $0$, and equiprobable left/right moves. Run $n$-step TD
for a sweep of $n$ and $\alpha$, and measure the RMS error of the predictions
against the true values, averaged over the first $10$ episodes and $100$ runs.

Two things stand out. Each curve is a U in $\alpha$ — too small a step learns
too slowly, too large a step overshoots — and the bottom of the U, the best
achievable error, is lowest for an _intermediate_ $n$, neither $n=1$ nor the very
largest. A one-step method after this walk would change only the value of the
last state visited; a two-step method would nudge the last two; an $n$-step
method credits the last $n$ states of the run, all by the same reward. Spreading
credit further than one step, but not all the way to the episode's start, gives
the lowest error.

$$
% caption: Performance of $n$-step TD on the 19-state random walk: average RMS
% error (first 10 episodes, 100 runs) versus step size $\alpha$, one curve per
% $n$. Each curve is U-shaped in $\alpha$; the lowest minimum belongs to an
% intermediate $n$ (here around $n=4$), beating both one-step TD ($n{=}1$) and
% the deep, Monte-Carlo-like backups ($n{=}32,64$). Curves are labelled at their
% right ends.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \definecolor{grn}{HTML}{1F9D4D}
  % axes
  \draw[->, black] (0,0) -- (6.6,0);
  \node[anchor=north, font=\scriptsize] at (3.0,-0.5) {step size};
  \draw[->, black] (0,0) -- (0,4.3);
  \foreach \x/\lab in {0/0, 1.2/0.2, 2.4/0.4, 3.6/0.6, 4.8/0.8, 6.0/1.0}
    \node[anchor=north, font=\scriptsize] at (\x,-0.05) {\lab};
  \foreach \y/\lab in {0/0.25, 1.0/0.35, 2.0/0.45, 3.0/0.55}
    \node[anchor=east, font=\scriptsize] at (-0.08,\y) {\lab};
  \node[align=center, font=\scriptsize, anchor=east] at (-0.55,3.7)
    {Average\\RMS error};
  % n=1 : shallow U, minimum near right, higher floor
  \draw[red, thick] (0.5,3.3) .. controls (2.6,1.6) and (4.4,1.35) .. (6.0,1.55);
  \node[red, anchor=west, font=\scriptsize] at (6.05,1.55) {n=1};
  % n=2 : min shifts left, a bit lower
  \draw[acc, thick] (0.4,3.2) .. controls (1.9,1.2) and (3.3,1.0) .. (6.0,2.5);
  \node[acc, anchor=west, font=\scriptsize] at (6.05,2.5) {n=2};
  % n=4 : lowest floor, min at small alpha
  \draw[grn, thick] (0.35,3.15) .. controls (1.2,0.75) and (2.0,0.6) .. (4.6,3.6);
  \node[grn, anchor=west, font=\scriptsize] at (4.62,3.6) {n=4};
  % n=32 : min far left, climbs fast, higher floor (deep backups)
  \draw[black!70, thick] (0.3,3.3) .. controls (0.7,1.35) and (1.1,1.25) .. (2.6,3.9);
  \node[black!70, anchor=south, font=\scriptsize] at (2.62,3.9) {n=32};
\end{tikzpicture}
$$

Sutton and Barto's full figure sweeps more values of $n$ and finds the whole family of
U-curves nested this way, with the minimum-of-minima at a small-but-not-one $n$.
As the backup-diagram spectrum suggests, bootstrapping too aggressively (small
$n$) ties the estimate to a possibly poor initial value function, while not
bootstrapping at all (Monte Carlo) takes on the full variance of the sampled
return. An intermediate $n$ holds both errors down at once.

## n-step Sarsa: control

Prediction estimates $v_\pi$ for a fixed policy; **control** improves the policy.
The move from prediction to control is the one from the previous lesson: switch
from states to state–action pairs and act $\varepsilon$-greedily with respect to
the action values. The $n$-step version of Sarsa — the original one-step Sarsa is
now **Sarsa(0)** — redefines the return over action values instead of state
values:

$$
G_{t:t+n} \;\doteq\; R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^{n-1} R_{t+n} + \gamma^{n}\, Q_{t+n-1}(S_{t+n}, A_{t+n}),
\qquad n \ge 1,\; 0 \le t < T - n,
$$

with $G_{t:t+n} \doteq G_t$ when $t + n \ge T$. The bootstrap now uses the
estimated value of a state–_action_ pair, $Q_{t+n-1}(S_{t+n}, A_{t+n})$, rather
than a state. The update mirrors $n$-step TD:

$$
Q_{t+n}(S_t, A_t) \;\doteq\; Q_{t+n-1}(S_t, A_t) + \alpha\,\big[\, G_{t:t+n} - Q_{t+n-1}(S_t, A_t) \,\big],
\qquad 0 \le t < T,
$$

leaving all other action values unchanged. Its backup diagrams are the same
spectrum as before, but every column now begins and ends on an _action_ (a solid
dot) rather than a state, with the sample actions and states alternating down the
spine.

$$
% caption: Backup diagrams for the $n$-step Sarsa spectrum on state-action
% values. Each column begins and ends on an action (solid dot); the spine
% alternates sample actions and states. Left to right: one-step Sarsa
% (Sarsa(0)), $n$-step Sarsa, and $\infty$-step Sarsa (Monte Carlo, down to the
% terminal square). Far right is $n$-step Expected Sarsa, whose last step
% branches over all actions and takes an expectation under $\pi$.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  st/.style={circle, draw, fill=white, minimum size=3.6mm, inner sep=0pt},
  ac/.style={circle, draw, fill=black, minimum size=1.7mm, inner sep=0pt},
  term/.style={rectangle, draw, fill=black!30, minimum size=3.6mm, inner sep=0pt}]
  \definecolor{acc}{HTML}{2348F2}
  % ---- column 1: 1-step Sarsa ----
  \node[ac] (a0) at (0,4) {};
  \node[st] (a1) at (0,3.3) {};
  \node[ac] (a2) at (0,2.6) {};
  \draw[black] (a0) -- (a1) -- (a2);
  \node[align=center, font=\scriptsize] at (0,4.9) {1-step\\Sarsa(0)};
  % ---- column 2: n-step Sarsa ----
  \node[ac] (b0) at (2.0,4) {};
  \node[st] (b1) at (2.0,3.3) {};
  \node[ac] (b2) at (2.0,2.6) {};
  \node[st] (b3) at (2.0,1.9) {};
  \draw[black] (b0) -- (b1) -- (b2) -- (b3);
  \node[font=\scriptsize] at (2.0,1.35) {$\vdots$};
  \node[st] (b4) at (2.0,0.7) {};
  \node[ac] (b5) at (2.0,0.0) {};
  \draw[black] (b4) -- (b5);
  \node[font=\scriptsize] at (2.0,4.9) {n-step Sarsa};
  % ---- column 3: infinity / MC ----
  \node[ac] (c0) at (4.4,4) {};
  \node[st] (c1) at (4.4,3.3) {};
  \node[ac] (c2) at (4.4,2.6) {};
  \node[st] (c3) at (4.4,1.9) {};
  \draw[black] (c0) -- (c1) -- (c2) -- (c3);
  \node[font=\scriptsize] at (4.4,1.35) {$\vdots$};
  \node[st] (c4) at (4.4,0.7) {};
  \node[term] (c5) at (4.4,0.0) {};
  \draw[black] (c4) -- (c5);
  \node[align=center, font=\scriptsize] at (4.4,4.95) {inf-step\\Monte Carlo};
  % ---- column 4: expected sarsa ----
  \node[ac] (e0) at (7.0,4) {};
  \node[st] (e1) at (7.0,3.3) {};
  \node[ac] (e2) at (7.0,2.6) {};
  \node[st] (e3) at (7.0,1.9) {};
  \draw[black] (e0) -- (e1) -- (e2) -- (e3);
  \node[font=\scriptsize] at (7.0,1.35) {$\vdots$};
  \node[st] (e4) at (7.0,0.7) {};
  \draw[black] (e4) -- (e3|-e4);
  % branch of actions at the bottom (expectation)
  \node[ac] (f1) at (6.4,0.0) {};
  \node[ac] (f2) at (6.8,0.0) {};
  \node[ac] (f3) at (7.2,0.0) {};
  \node[ac] (f4) at (7.6,0.0) {};
  \draw[black] (e4) -- (f1);
  \draw[black] (e4) -- (f2);
  \draw[black] (e4) -- (f3);
  \draw[black] (e4) -- (f4);
  \node[align=center, font=\scriptsize] at (7.0,4.95) {n-step\\Expected Sarsa};
\end{tikzpicture}
$$

The far-right diagram is **$n$-step Expected Sarsa**: identical to $n$-step
Sarsa except the last element is a full branch over all actions, weighted by
their probability under $\pi$. Its return replaces the final action-value with an
expected value,

$$
G_{t:t+n} \;\doteq\; R_{t+1} + \cdots + \gamma^{n-1} R_{t+n} + \gamma^{n}\, \bar{V}_{t+n-1}(S_{t+n}),
\qquad t + n < T,
$$

where the **expected approximate value** of a state is the policy-weighted
average of its action values,

$$
\bar{V}_t(s) \;\doteq\; \sum_a \pi(a \mid s)\, Q_t(s, a),
\qquad \text{for all } s \in \mathcal{S}.
$$

Bootstrapping from $\bar{V}$ instead of a single sampled action removes the
variance of that last action choice, exactly as one-step Expected Sarsa removed
it in the previous lesson.

### Why n-step control speeds learning

The reason to reach past one step in control is that a single delayed reward
should teach more than one action. Consider an agent wandering a gridworld,
receiving zero reward until it stumbles onto a goal cell. When the episode ends,
one-step Sarsa strengthens exactly one state–action value: the last action, the
one that stepped onto the goal. Every earlier action on that successful path
learns nothing from this episode. An $n$-step method strengthens the last $n$
actions of the path in one sweep, so a single lucky trajectory propagates credit
back along its own tail.

$$
% caption: The $n$-step speedup in a gridworld. All rewards are zero except at
% the goal G. After one successful episode, one-step Sarsa (middle) strengthens
% only the single action that entered G; $n$-step Sarsa (right) strengthens the
% last $n$ actions of the path, so far more is learned from the one episode.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  % ---------- panel 1: path taken ----------
  \begin{scope}
    \foreach \x in {0,...,6} \draw[black] (\x*0.42,0) -- (\x*0.42,2.52);
    \foreach \y in {0,...,6} \draw[black] (0,\y*0.42) -- (2.52,\y*0.42);
    \node[anchor=south, font=\scriptsize] at (1.26,2.6) {path taken};
    \node[font=\scriptsize] at (1.68,1.05) {G};
    % a winding path in accent, arrows toward G
    \draw[acc, thick, ->] (0.42,1.9) -- (0.84,1.9);
    \draw[acc, thick, ->] (0.84,1.9) -- (0.84,1.47);
    \draw[acc, thick, ->] (0.84,1.47) -- (1.26,1.47);
    \draw[acc, thick, ->] (1.26,1.47) -- (1.26,1.05);
    \draw[acc, thick, ->] (1.26,1.05) -- (1.55,1.05);
  \end{scope}
  % ---------- panel 2: one-step ----------
  \begin{scope}[xshift=3.6cm]
    \foreach \x in {0,...,6} \draw[black] (\x*0.42,0) -- (\x*0.42,2.52);
    \foreach \y in {0,...,6} \draw[black] (0,\y*0.42) -- (2.52,\y*0.42);
    \node[align=center, anchor=south, font=\scriptsize] at (1.26,2.6)
      {increased by\\one-step Sarsa};
    \node[font=\scriptsize] at (1.68,1.05) {G};
    \draw[acc, thick, ->] (1.26,1.05) -- (1.55,1.05);
  \end{scope}
  % ---------- panel 3: n-step ----------
  \begin{scope}[xshift=7.2cm]
    \foreach \x in {0,...,6} \draw[black] (\x*0.42,0) -- (\x*0.42,2.52);
    \foreach \y in {0,...,6} \draw[black] (0,\y*0.42) -- (2.52,\y*0.42);
    \node[align=center, anchor=south, font=\scriptsize] at (1.26,2.6)
      {increased by\\n-step Sarsa};
    \node[font=\scriptsize] at (1.68,1.05) {G};
    \draw[acc, thick, ->] (0.42,1.9) -- (0.84,1.9);
    \draw[acc, thick, ->] (0.84,1.9) -- (0.84,1.47);
    \draw[acc, thick, ->] (0.84,1.47) -- (1.26,1.47);
    \draw[acc, thick, ->] (1.26,1.47) -- (1.26,1.05);
    \draw[acc, thick, ->] (1.26,1.05) -- (1.55,1.05);
  \end{scope}
\end{tikzpicture}
$$

> **Algorithm ($n$-step Sarsa).** Follow an $\varepsilon$-greedy policy derived
> from $Q$. At each time $t+n$, form the $n$-step action-value return
> $G_{t:t+n}$ and update $Q(S_t, A_t) \gets Q(S_t, A_t) + \alpha\,[G_{t:t+n} -
> Q(S_t, A_t)]$, then re-derive the $\varepsilon$-greedy policy at $S_t$. With
> $n=1$ this is ordinary Sarsa; larger $n$ propagates a delayed reward back
> along the last $n$ actions of the trajectory.

This continues in [n-Step Bootstrapping: Off-Policy Methods](/reinforcement-learning/tabular-methods/n-step-off-policy-methods), which reweights n-step returns by the importance-sampling ratio, builds the tree-backup algorithm that goes off-policy with no ratios at all, and unifies the whole family under n-step Q(sigma).

[^sb-nstep]: **Sutton & Barto**, _Reinforcement Learning: An Introduction_ (2nd ed.), §7.1 — n-step TD Prediction: the $n$-step return (7.1) as a truncated, bootstrap-corrected return, the $n$-step TD update (7.2), and the error-reduction property (7.3) that makes every member of the family sound. §7.2 — n-step Sarsa: the action-value return (7.4), the control update (7.5), and $n$-step Expected Sarsa (7.7)–(7.8).