---
title: "Model-Free Prediction and Control"
module: Reinforcement Learning
moduleNumber: 11
lessonNumber: 2
order: 1102
summary: >
  When the dynamics are unknown, an agent cannot plan against a model; it must
  learn directly from sampled experience. We build prediction and control from
  two estimators of the same return: Monte Carlo averages whole episodes, while
  temporal-difference learning bootstraps from its own next estimate. We trace
  the bias-variance contrast between them, derive SARSA and Q-learning as the
  on-policy and off-policy forms of control, unify everything through n-step
  returns and eligibility traces, and close on the deadly triad that makes
  off-policy bootstrapping with function approximation diverge.
topics: [Reinforcement Learning]
sources:
  - book: Goodfellow
    ref: "Ch. 1 — learning from sampled experience without a model"
---

The [foundations of reinforcement learning](/deep-learning/reinforcement-learning/foundations-of-reinforcement-learning)
gave us the Bellman equations and the policy-/value-iteration machinery that
solves them. Both assume a **model**: the transition kernel $P(s' \mid s, a)$ and
the reward function $R(s, a)$ are known, so every backup is an exact expectation
over $s'$. The agent in this lesson has neither. It sees only a stream of
transitions $(S_t, A_t, R_{t+1}, S_{t+1})$ drawn by acting in the environment,
and must estimate value functions and improve its policy from that stream
alone. This is the **model-free** setting, and it splits into two
problems we treat in turn.

> **Definition (Model-free prediction and control).** _Prediction_ is estimating
> the value function $v_\pi$ (or $q_\pi$) of a fixed policy $\pi$ from sampled
> experience, with $P$ and $R$ unknown. _Control_ is improving the policy toward
> $\pi_\star$ from that same experience, without ever forming an explicit model
> of the dynamics.

The object both methods estimate is the **return**, the discounted sum of
rewards from time $t$ onward, and the value functions are its expectation:

$$
G_t = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1},
\qquad
v_\pi(s) = \mathbb{E}_\pi\brackets{G_t \mid S_t = s},
\qquad
q_\pi(s,a) = \mathbb{E}_\pi\brackets{G_t \mid S_t = s,\, A_t = a}.
$$

Without a model the expectation cannot be computed, only **sampled**. Every
algorithm below is a different answer to one question: given a stream of
experience, how do you estimate $\mathbb{E}_\pi[G_t]$?

## Monte Carlo prediction

The most direct estimator is the one from
[Monte Carlo methods](/deep-learning/probabilistic-methods/monte-carlo-and-mcmc):
$v_\pi(s)$ is an expectation, so average sampled returns. Run an episode to
termination, compute the realized return $G_t$ from each visited state, and let
$V(s)$ be the mean of the returns observed from $s$. No model, no bootstrapping;
the estimate is grounded entirely in completed experience.

> **Definition (First-visit and every-visit MC).** For state $s$, **first-visit
> MC** averages the returns following only the _first_ occurrence of $s$ in each
> episode; **every-visit MC** averages the returns following _every_ occurrence.
> Both converge to $v_\pi(s)$ as the number of visits grows; first-visit returns
> are i.i.d., every-visit returns are not.

The distinction matters for the analysis. If a state recurs inside one episode,
its two returns share a common tail of rewards, so they are correlated.
First-visit MC sidesteps this by keeping only one return per episode: the returns
it averages are independent draws of the same random variable $G_t \mid S_t = s$,
so the ordinary law of large numbers applies and its estimate is unbiased at every
sample size with error shrinking like $1/\sqrt{n}$ in the number of visits $n$.
Every-visit MC reuses the correlated within-episode returns; it is biased for
finite $n$ but the bias vanishes as $n \to \infty$, and it often wastes less data.

### The sample mean is an incremental update

Averaging returns does not require storing every return seen from $s$.
The arithmetic mean of $n$ numbers can be written as a correction to the
mean of the first $n-1$, which turns a batch average into a constant-memory online
rule. Write $V_n(s)$ for the mean of the first $n$ returns $G_1, \dots, G_n$
observed from $s$. Then

$$
V_n = \frac{1}{n}\sum_{k=1}^{n} G_k
    = \frac{1}{n}\brackets{G_n + \sum_{k=1}^{n-1} G_k}
    = \frac{1}{n}\brackets{G_n + (n-1)\,V_{n-1}}.
$$

Expand and regroup the last expression around $V_{n-1}$:

$$
V_n = \frac{1}{n}G_n + \frac{n-1}{n}V_{n-1}
    = V_{n-1} + \frac{1}{n}\brackets{G_n - V_{n-1}}.
$$

The batch average and this one-line update produce the identical number at every
$n$; nothing is approximated. Maintaining a visit count $N(s)$, each new return
$G_t$ therefore nudges the running estimate toward itself by a $1/N(s)$ fraction
of the residual:

$$
N(S_t) \gets N(S_t) + 1,
\qquad
V(S_t) \gets V(S_t) + \frac{1}{N(S_t)}\brackets{G_t - V(S_t)}.
$$

The bracketed residual $G_t - V(S_t)$ is a prediction error, and the step size
$1/N(s)$ shrinks as evidence accumulates, so early returns move the estimate a lot
and later ones barely at all. Replacing $1/N(s)$ with a constant step $\alpha$
gives a **running** average that tracks a nonstationary target, the form we keep
for the rest of the lesson:

$$
V(S_t) \;\gets\; V(S_t) + \alpha\brackets{G_t - V(S_t)}.
$$

A constant $\alpha$ never lets the step size vanish, so this update weights recent
returns more heavily than old ones, a geometric recency weighting worth having when
the policy (and thus the return distribution) is still changing. The estimator is
unbiased in the $1/N$ case because $\mathbb{E}_\pi[G_t \mid S_t = s] = v_\pi(s)$
exactly; MC regresses $V(s)$ directly onto the very quantity it targets, with no
model and no bootstrap in between.

$$
% caption: A Monte Carlo backup updates $V(S_0)$ from the full sampled return
% $G_0 = R_1 + \gamma R_2 + \gamma^2 R_3 + \gamma^3 R_4$ of one complete episode to terminal $T$.
\begin{tikzpicture}[>=stealth, font=\footnotesize, scale=1.0]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  % chain of states
  \foreach \i/\x/\lab in {0/0/{$S_0$}, 1/2.0/{$S_1$}, 2/4.0/{$S_2$}, 3/6.0/{$S_3$}} {
    \node[draw=black, thick, circle, minimum size=0.85cm] (n\i) at (\x,0) {\lab};
  }
  \node[draw=green, thick, rectangle, minimum size=0.85cm] (nT) at (8.0,0) {$T$};
  % reward-labelled transitions
  \foreach \a/\b/\r in {0/1/{$R_1$}, 1/2/{$R_2$}, 2/3/{$R_3$}} {
    \draw[->, black, thick] (n\a) -- (n\b) node[midway, above] {\r};
  }
  \draw[->, black, thick] (n3) -- (nT) node[midway, above] {$R_4$};
  % the MC backup: long arc from terminal return back to S0
  \draw[->, acc, very thick] (nT.south) .. controls (5.0,-2.0) and (1.5,-2.0) .. (n0.south)
    node[midway, below, text=acc] {discounted return $G_0$};
  \node[acc, anchor=south] at (0,0.7) {MC update};
\end{tikzpicture}
$$

## Monte Carlo control

Prediction estimates $v_\pi$; control must _improve_ $\pi$. Two obstacles appear
at once. First, greedy improvement needs action values, not state values:
$\pi'(s) = \arg\max_a q(s,a)$ requires $q$, since without a model we cannot turn
$v$ into a one-step lookahead. So MC control estimates $Q(s,a)$ directly,
averaging returns following each state-action pair. Second, a purely greedy
policy stops exploring: actions it currently rates poorly are never tried, so
their estimates never improve. The standard fix is **$\varepsilon$-greedy**
action selection.

> **Definition ($\varepsilon$-greedy policy).** With probability $1-\varepsilon$
> take the greedy action $\arg\max_a Q(s,a)$, and with probability $\varepsilon$
> take a uniformly random action. Every action then has probability at least
> $\varepsilon / \abs{\mathcal{A}}$, so exploration never fully stops.

The single parameter $\varepsilon$ sets the balance between **exploitation** (act
on what you believe is best now) and **exploration** (try alternatives to correct
a wrong belief). Large $\varepsilon$ gathers information but earns little reward;
$\varepsilon = 0$ maximizes immediate reward but can lock in a suboptimal action
whose true value was never sampled.

$$
% caption: $\varepsilon$-greedy splits the action probability: mass $1-\varepsilon$ on
% the greedy action (exploit), the remaining $\varepsilon$ spread uniformly over all
% $|\mathcal{A}|$ actions (explore), so every action keeps probability at least $\varepsilon/|\mathcal{A}|$.
\begin{tikzpicture}[>=stealth, font=\footnotesize, scale=1.0]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  % baseline
  \draw[black, thick] (0,0) -- (8.4,0);
  % four action bars; action a2 is greedy (tall), others get the uniform floor
  \foreach \i/\x/\h/\lab in {1/0.8/0.55/{$a_1$}, 2/2.8/3.0/{$a_2$}, 3/4.8/0.55/{$a_3$}, 4/6.8/0.55/{$a_4$}} {
    \draw[thick, fill=black!8] ({\x-0.4},0) rectangle ({\x+0.4},\h);
    \node[anchor=north] at (\x,-0.1) {\lab};
  }
  % recolor greedy bar
  \draw[acc, thick, fill=acc!18] (2.4,0) rectangle (3.2,3.0);
  % floor color on the explore bars
  \foreach \x in {0.8,4.8,6.8} {
    \draw[green, thick, fill=green!15] ({\x-0.4},0) rectangle ({\x+0.4},0.55);
  }
  % labels
  \node[acc, anchor=south] at (2.8,3.05) {exploit};
  \node[green, anchor=west] at (5.4,1.4) {explore};
  \draw[green, thick, ->] (5.9,1.25) -- (6.8,0.65);
  \node[anchor=east, black] at (0.35,3.0) {prob.};
\end{tikzpicture}
$$

$\varepsilon$-greedy improvement is sound: any $\varepsilon$-greedy policy with
respect to $q_\pi$ is at least as good as $\pi$ itself.

> **Theorem ($\varepsilon$-greedy improvement).** Let $\pi$ be
> $\varepsilon$-greedy and let $\pi'$ be $\varepsilon$-greedy with respect to
> $q_\pi$. Then $v_{\pi'}(s) \ge v_\pi(s)$ for all $s$, with equality only when
> both equal $v_\star$.

> **Proof.** Write the action probabilities of $\pi'$ as $\varepsilon /
> \abs{\mathcal{A}}$ uniform plus mass $1-\varepsilon$ on the greedy action.
> Then
> $$
> \sum_a \pi'(a \mid s)\, q_\pi(s,a)
> = \frac{\varepsilon}{\abs{\mathcal{A}}}\sum_a q_\pi(s,a)
>   + (1-\varepsilon)\max_a q_\pi(s,a).
> $$
> The greedy max is at least the $\pi$-weighted average of the same values once
> the uniform floor is subtracted out, so this quantity is
> $\ge \sum_a \pi(a\mid s)\, q_\pi(s,a) = v_\pi(s)$. The policy-improvement
> theorem then gives $v_{\pi'} \ge v_\pi$. $\qed$

Interleaving $\varepsilon$-greedy evaluation with $\varepsilon$-greedy
improvement converges, provided exploration decays so that the limiting policy
is greedy. That condition has a name.

> **Definition (GLIE).** A schedule is **greedy in the limit with infinite
> exploration** if every state-action pair is visited infinitely often
> ($N(s,a) \to \infty$) yet the policy becomes greedy in the limit
> ($\pi(a\mid s) \to \mathbf{1}[a = \arg\max_{a'} Q(s,a')]$). Taking
> $\varepsilon_k = 1/k$ satisfies both. Under GLIE, MC control converges to
> $q_\star$.

```algorithm
caption: $\textsc{MonteCarloControl}(\varepsilon\text{-greedy, GLIE})$ — on-policy first-visit MC control
initialize $Q(s,a)$ arbitrarily, $N(s,a) \gets 0$
for each episode $k = 1, 2, \dots$ do
  set $\varepsilon \gets 1/k$ and generate an episode with the $\varepsilon$-greedy policy in $Q$
  for each $(s,a)$ first-visited in the episode do
    $G \gets$ return following that first visit
    $N(s,a) \gets N(s,a) + 1$
    $Q(s,a) \gets Q(s,a) + \frac{1}{N(s,a)}\brackets{G - Q(s,a)} $ // incremental mean
return the greedy policy in $Q$
```

The structural weakness of MC is that it needs **complete episodes**. The return
$G_t$ is unknown until termination, so MC cannot update mid-episode, cannot learn
in continuing (non-terminating) tasks, and waits a long time on long episodes
before any signal propagates.

## Temporal-difference learning

Temporal-difference learning removes the wait. Instead of substituting the full
sampled return $G_t$, it substitutes the **one-step bootstrap target**
$R_{t+1} + \gamma V(S_{t+1})$: one real reward plus the current estimate of the
rest. This is the sampled form of the Bellman expectation equation
$v_\pi(s) = \mathbb{E}_\pi[R_{t+1} + \gamma v_\pi(S_{t+1}) \mid S_t = s]$.

> **Definition (TD(0) update).** After observing the transition
> $(S_t, R_{t+1}, S_{t+1})$, update
> $$
> V(S_t) \;\gets\; V(S_t) + \alpha\brackets{\,\underbrace{R_{t+1} + \gamma V(S_{t+1}) - V(S_t)}_{\delta_t}\,},
> $$
> where $\delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t)$ is the **TD error**: the
> difference between the bootstrapped target and the current estimate.

The TD error appears in every method that follows: it is the gap between what the
agent expected and what one step of
experience plus its own forecast now suggest. MC and TD differ only in their
**target**: MC regresses $V(S_t)$ toward the realized $G_t$, TD toward
$R_{t+1} + \gamma V(S_{t+1})$. Dynamic programming uses the same target as TD but
takes a full expectation over $S_{t+1}$ instead of sampling one.

$$
% caption: Three backups for $V(S_t)$. MC samples a full path to terminal; TD samples
% one step then bootstraps; DP takes a full expectation over successors.
\begin{tikzpicture}[>=stealth, font=\footnotesize, scale=1.0]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  \definecolor{red}{HTML}{C0392B}
  % ===== MC panel =====
  \begin{scope}
    \node[anchor=south, font=\small] at (0,2.6) {MC};
    \node[draw=acc, thick, circle, minimum size=0.5cm] (m0) at (0,2.0) {};
    \node[draw=black, thick, circle, minimum size=0.42cm] (m1) at (0,1.1) {};
    \node[draw=black, thick, circle, minimum size=0.42cm] (m2) at (0,0.2) {};
    \node[draw=green, thick, rectangle, minimum size=0.42cm] (mT) at (0,-0.8) {};
    \draw[->, black, thick] (m0) -- (m1);
    \draw[->, black, thick] (m1) -- (m2);
    \draw[->, black, thick] (m2) -- (mT);
    \node[green, anchor=west] at (0.35,-0.8) {terminal};
  \end{scope}
  % ===== TD panel =====
  \begin{scope}[xshift=4.2cm]
    \node[anchor=south, font=\small] at (0,2.6) {TD(0)};
    \node[draw=acc, thick, circle, minimum size=0.5cm] (t0) at (0,2.0) {};
    \node[draw=black, thick, circle, minimum size=0.42cm] (t1) at (0,1.1) {};
    \draw[->, acc, very thick] (t0) -- (t1);
    \draw[->, black, dashed, thick] (t1) -- (0,0.4);
    \node[acc, anchor=west] at (0.35,1.55) {bootstrap};
  \end{scope}
  % ===== DP panel =====
  \begin{scope}[xshift=8.4cm]
    \node[anchor=south, font=\small] at (0,2.6) {DP};
    \node[draw=acc, thick, circle, minimum size=0.5cm] (d0) at (0,2.0) {};
    \node[draw=black, thick, circle, minimum size=0.42cm] (da) at (-1.0,1.0) {};
    \node[draw=black, thick, circle, minimum size=0.42cm] (db) at (0,1.0) {};
    \node[draw=black, thick, circle, minimum size=0.42cm] (dc) at (1.0,1.0) {};
    \draw[->, acc, very thick] (d0) -- (da);
    \draw[->, acc, very thick] (d0) -- (db);
    \draw[->, acc, very thick] (d0) -- (dc);
    \node[acc, anchor=north, font=\footnotesize] at (0,0.85) {\texttt{full expectation}};
  \end{scope}
\end{tikzpicture}
$$

The implications are immediate: TD learns **online**, after every step, from
**incomplete** episodes, and works in **continuing** tasks where no terminal
state exists. It bootstraps, so it can begin propagating value before any episode
finishes.

### A worked TD(0) update

For example, take $\gamma = 0.9$ and step size
$\alpha = 0.1$. The current table holds $V(S_t) = 5$ and $V(S_{t+1}) = 8$. The
agent takes its action and observes reward $R_{t+1} = 2$, landing in $S_{t+1}$.
Form the bootstrap target, then the TD error, then the update:

$$
\text{target} = R_{t+1} + \gamma\,V(S_{t+1}) = 2 + 0.9 \times 8 = 9.2,
$$

$$
\delta_t = \text{target} - V(S_t) = 9.2 - 5 = 4.2,
$$

$$
V(S_t) \gets 5 + 0.1 \times 4.2 = 5.42.
$$

The estimate moves a tenth of the way from $5$ toward the target $9.2$. It did not
jump to $9.2$: a single transition is one noisy sample, and $\alpha = 0.1$ limits
how much weight it receives. Had the reward been unluckily large, the target
would overshoot and the next transition from $S_t$ would pull the estimate part of
the way back; the step size averages these samples over time. Every method in this
lesson is a variation on this three-line loop, changing only what fills the target
slot.

$$
% caption: The TD update on a value line. The TD error $\delta_t = 4.2$ is the gap from the
% old estimate $V(S_t) = 5$ to the target $9.2$; the estimate steps $\alpha\,\delta_t = 0.42$
% along that gap, landing at the new value $5.42$.
\begin{tikzpicture}[>=stealth, font=\footnotesize, scale=1.0]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  \definecolor{red}{HTML}{C0392B}
  % value axis
  \draw[->, thick] (0,0) -- (9.8,0) node[right] {$V$};
  % ticks at old (2.5), new (3.35), target (9.0)
  \draw[thick] (2.5,0.12) -- (2.5,-0.12);
  \draw[thick] (3.35,0.12) -- (3.35,-0.12);
  \draw[thick] (9.0,0.12) -- (9.0,-0.12);
  \node[anchor=north] at (2.5,-0.15) {\texttt{5.0}};
  \node[anchor=north] at (9.0,-0.15) {\texttt{9.2}};
  % old estimate marker
  \filldraw[acc] (2.5,0) circle (2.2pt);
  \node[acc, anchor=east] at (2.35,0.9) {old $V(S_t)$};
  % target marker
  \filldraw[red] (9.0,0) circle (2.2pt);
  \node[red, anchor=west] at (9.15,0.9) {target};
  % new estimate marker
  \filldraw[green] (3.35,0) circle (2.2pt);
  \node[green, anchor=north west] at (3.6,-0.35) {new \texttt{= 5.42}};
  \draw[green, thick, ->] (3.7,-0.35) -- (3.42,-0.06);
  % the TD error span (old to target)
  \draw[red, thick, |-|] (2.5,1.35) -- (9.0,1.35);
  \node[red, anchor=south] at (5.75,1.4) {TD error \texttt{= 4.2}};
  % the taken step (old to new)
  \draw[acc, very thick, ->] (2.5,0.4) -- (3.35,0.4);
  \node[acc, anchor=south west, font=\footnotesize] at (2.55,0.45) {step \texttt{0.42}};
\end{tikzpicture}
$$

## Bias and variance

TD and MC are both correct in the limit, but they trade bias against variance.
The MC target $G_t$ is an unbiased sample of $v_\pi(S_t)$ but accumulates the
randomness of _every_ reward and transition along the whole trajectory, so its
variance is large. The TD target $R_{t+1} + \gamma V(S_{t+1})$ depends on a
**single** random transition, so its variance is small, but it bootstraps off the
current estimate $V$, which is wrong early in training, so it is **biased** until
$V$ converges.

| Property | Monte Carlo | TD(0) |
| --- | --- | --- |
| Target | full return $G_t$ | $R_{t+1} + \gamma V(S_{t+1})$ |
| Bias | unbiased ($\mathbb{E}[G_t]=v_\pi$) | biased (bootstraps off $V$) |
| Variance | high (whole trajectory) | low (one transition) |
| Needs complete episodes | yes | no |
| Continuing tasks | no | yes |
| Markov property | not required | exploited |
| Initial-value sensitivity | low | high |

The Markov-property row is the deepest distinction. On finite data, MC converges
to the values that minimize mean-squared error on the observed returns, whereas
TD(0) converges to the values of the **maximum-likelihood Markov model** fit to
the data, the so-called certainty-equivalence estimate. When the environment
really is Markov, TD's structural assumption is a feature and it is typically far
more data-efficient; when it is not, MC's model-freedom is safer.

## On-policy control: SARSA

Control needs action values, and the same TD idea applied to $Q$ gives
**SARSA**, named for the quintuple $(S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1})$ that
the update consumes. The bootstrap target uses the action $A_{t+1}$ that the
agent **actually takes** next under its current policy.

> **Definition (SARSA update).** For the observed transition
> $(S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1})$ with $A_{t+1} \sim \pi$,
> $$
> Q(S_t, A_t) \;\gets\; Q(S_t, A_t)
>   + \alpha\brackets{R_{t+1} + \gamma\, Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t)}.
> $$

SARSA is **on-policy**: the target evaluates the very policy generating the data,
so as the policy improves, the values it learns are the values of the improving
policy. With a GLIE schedule the policy becomes greedy and SARSA converges to
$q_\star$.

```algorithm
caption: $\textsc{Sarsa}(\alpha, \gamma, \varepsilon)$ — on-policy TD control
initialize $Q(s,a)$ arbitrarily, $Q(\text{terminal}, \cdot) \gets 0$
for each episode do
  $S \gets$ initial state; choose $A$ from $S$ by $\varepsilon$-greedy in $Q$
  repeat for each step of the episode
    take $A$, observe $R$ and $S'$
    choose $A'$ from $S'$ by $\varepsilon$-greedy in $Q$ // next action under the policy
    $Q(S,A) \gets Q(S,A) + \alpha\brackets{R + \gamma\, Q(S',A') - Q(S,A)}$
    $S \gets S'$; $A \gets A'$
  until $S$ is terminal
return $Q$
```

## Off-policy control: Q-learning

**Q-learning** changes one symbol and the character of the algorithm with it. Its
target bootstraps off the **greedy** action $\max_{a'} Q(S_{t+1}, a')$, not the
action actually taken. It learns about the optimal policy while behaving by an
exploratory one.

> **Definition (Q-learning update).** For the transition
> $(S_t, A_t, R_{t+1}, S_{t+1})$,
> $$
> Q(S_t, A_t) \;\gets\; Q(S_t, A_t)
>   + \alpha\brackets{R_{t+1} + \gamma\, \max_{a'} Q(S_{t+1}, a') - Q(S_t, A_t)}.
> $$

This is **off-policy**: the **behavior policy** that selects $A_t$ (e.g.
$\varepsilon$-greedy, for exploration) differs from the **target policy** the
update evaluates (greedy). Because the $\max$ target is a sampled form of the
Bellman **optimality** equation, Q-learning converges to $q_\star$ directly under
the standard step-size conditions, regardless of the behavior policy, as long as
it keeps visiting every pair.

### One term separates the two

Line up the two targets and only one factor differs:

$$
\underbrace{R_{t+1} + \gamma\, Q(S_{t+1}, A_{t+1})}_{\text{SARSA}},
\qquad
\underbrace{R_{t+1} + \gamma\, \max_{a'} Q(S_{t+1}, a')}_{\text{Q-learning}}.
$$

SARSA plugs in $Q$ at the action $A_{t+1}$ the behavior policy _actually samples_
next. That action is $\varepsilon$-greedy, so with probability $\varepsilon$ it is
a random, possibly bad action, and its low value is folded into the target. The
target therefore describes the value of _following the exploratory policy_,
including its mistakes; SARSA evaluates the policy that generated the data, which
is the definition of on-policy. Q-learning replaces $Q(S_{t+1}, A_{t+1})$ with
$\max_{a'} Q(S_{t+1}, a')$, the value of the _best_ action regardless of what the
agent will do next. The $\max$ erases the behavior policy from the target: whatever
exploratory action gets taken, the bootstrap always assumes greedy continuation.
That is why the target policy (greedy) is decoupled from the behavior policy
($\varepsilon$-greedy) — the decoupling that defines off-policy learning. When
$\varepsilon \to 0$ the sampled action and the greedy action coincide and the two
updates become identical; the gap between them is the cost of exploration, which
SARSA counts and Q-learning ignores.

$$
% caption: Backup targets for one transition. SARSA (left) bootstraps off the sampled
% next action A'; Q-learning (right) bootstraps off the best next action via max over a'.
\begin{tikzpicture}[>=stealth, font=\footnotesize, scale=1.0]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  \definecolor{red}{HTML}{C0392B}
  % ===== SARSA panel =====
  \begin{scope}
    \node[anchor=south, font=\small] at (1.0,3.0) {SARSA (on-policy)};
    \node[draw=acc, thick, circle, minimum size=0.5cm] (s0) at (1.0,2.3) {};
    \node[acc, anchor=east] at (0.5,2.3) {state, action};
    \node[draw=black, thick, circle, minimum size=0.42cm] (s1) at (1.0,1.2) {};
    \draw[->, black, thick] (s0) -- (s1) node[midway, right] {$R$};
    % three candidate next actions, one sampled
    \node[draw=green, thick, circle, minimum size=0.36cm] (sa) at (0.0,0.2) {};
    \node[draw=black, circle, minimum size=0.36cm] (sb) at (1.0,0.2) {};
    \node[draw=black, circle, minimum size=0.36cm] (sc) at (2.0,0.2) {};
    \draw[->, green, very thick] (s1) -- (sa);
    \draw[->, black] (s1) -- (sb);
    \draw[->, black] (s1) -- (sc);
    \node[green, anchor=north, font=\scriptsize] at (0.0,-0.1) {sampled next};
  \end{scope}
  % ===== Q-learning panel =====
  \begin{scope}[xshift=5.2cm]
    \node[anchor=south, font=\small] at (1.0,3.0) {Q-learning (of\/f-policy)};
    \node[draw=acc, thick, circle, minimum size=0.5cm] (q0) at (1.0,2.3) {};
    \node[acc, anchor=east] at (0.5,2.3) {state, action};
    \node[draw=black, thick, circle, minimum size=0.42cm] (q1) at (1.0,1.2) {};
    \draw[->, black, thick] (q0) -- (q1) node[midway, right] {$R$};
    \node[draw=black, circle, minimum size=0.36cm] (qa) at (0.0,0.2) {};
    \node[draw=red, thick, circle, minimum size=0.36cm] (qb) at (1.0,0.2) {};
    \node[draw=black, circle, minimum size=0.36cm] (qc) at (2.0,0.2) {};
    \draw[->, black] (q1) -- (qa);
    \draw[->, red, very thick] (q1) -- (qb);
    \draw[->, black] (q1) -- (qc);
    \node[red, anchor=north, font=\scriptsize] at (1.0,-0.1) {best (max)};
  \end{scope}
\end{tikzpicture}
$$

```algorithm
caption: $\textsc{QLearning}(\alpha, \gamma, \varepsilon)$ — off-policy TD control
initialize $Q(s,a)$ arbitrarily, $Q(\text{terminal}, \cdot) \gets 0$
for each episode do
  $S \gets$ initial state
  repeat for each step of the episode
    choose $A$ from $S$ by $\varepsilon$-greedy in $Q$ // behavior policy
    take $A$, observe $R$ and $S'$
    $Q(S,A) \gets Q(S,A) + \alpha\brackets{R + \gamma\, \max_{a'} Q(S',a') - Q(S,A)}$ // greedy target
    $S \gets S'$
  until $S$ is terminal
return $Q$
```

The on-policy/off-policy gap changes the actual path the agent
learns. The canonical demonstration is **cliff walking**: a gridworld
where the bottom edge between start and goal is a cliff that costs $-100$ and
resets the agent, while every other step costs $-1$. The optimal path hugs the
cliff edge. Q-learning learns exactly that optimal greedy path. SARSA, because it
evaluates the $\varepsilon$-greedy policy it actually follows, accounts for the
random exploratory steps that occasionally push it off the cliff, so it learns a
**safer** path one row away from the edge, earning more reward _online_ during
$\varepsilon$-greedy training.

$$
% caption: Cliff walking. Q-learning learns the optimal greedy path along the cliff edge;
% SARSA, valuing its own exploration, learns a safer path one row higher.
\begin{tikzpicture}[>=stealth, font=\footnotesize, scale=0.62]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  \definecolor{red}{HTML}{C0392B}
  % outer border only (no interior grid so labels stay clear)
  \draw[black, thick] (0,0) rectangle (12,4);
  % the cliff cells (bottom row, columns 1..10) light red fill + outline
  \foreach \c in {1,2,3,4,5,6,7,8,9,10} {
    \draw[red, thick, fill=red!15] (\c,0) rectangle (\c+1,1);
  }
  \node[red, anchor=north] at (6,-0.35) {a fall here: reward minus 100, reset to start};
  % start and goal
  \node[green, anchor=center] at (0.5,0.5) {S};
  \node[green, anchor=center] at (11.5,0.5) {G};
  % Q-learning optimal path: hug the edge along row y=1 then up to goal
  \draw[acc, very thick, ->]
    (0.5,0.5) -- (0.5,1.5) -- (11.5,1.5) -- (11.5,0.5);
  \node[acc, anchor=south] at (6,1.6) {Q-learning (optimal)};
  % SARSA safe path: go up two rows, across, down
  \draw[green, very thick, ->]
    (0.5,0.5) -- (0.5,3.1) -- (11.5,3.1) -- (11.5,0.5);
  \node[green, anchor=south] at (6,3.2) {SARSA (safe)};
\end{tikzpicture}
$$

## n-step returns and the unified spectrum

MC and TD(0) are the endpoints of a dial. TD(0) bootstraps after one reward; MC
after all of them. In between, the **$n$-step return** takes $n$ real rewards and
then bootstraps:

$$
G_t^{(n)} = R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^{n-1} R_{t+n}
          + \gamma^{n} V(S_{t+n}).
$$

At $n = 1$ this is the TD(0) target; as $n \to \infty$ (to termination) it is the
MC return $G_t$. The corresponding **$n$-step TD** update is
$V(S_t) \gets V(S_t) + \alpha\,[\,G_t^{(n)} - V(S_t)\,]$. Intermediate $n$
typically beats both endpoints: enough real reward to cut the bootstrap bias,
few enough steps to hold the variance down.

## TD($\lambda$) and eligibility traces

Rather than commit to one $n$, **TD($\lambda$)** averages all of them. The
**$\lambda$-return** is a geometric average of every $n$-step return, weighted by
$(1-\lambda)\lambda^{n-1}$:

$$
G_t^\lambda = (1-\lambda)\sum_{n=1}^{\infty} \lambda^{n-1}\, G_t^{(n)},
\qquad \lambda \in [0,1].
$$

The weights sum to one. At $\lambda = 0$ all weight collapses onto $G_t^{(1)}$,
recovering TD(0); at $\lambda = 1$ the average reduces to the MC return $G_t$. The
single knob $\lambda$ sweeps continuously between bootstrapping and full sampling.

$$
% caption: The $\lambda$-return weights each $n$-step return by $(1-\lambda)\lambda^{n-1}$,
% interpolating between TD(0) at $n=1$ and Monte Carlo at the terminal step.
\begin{tikzpicture}[>=stealth, font=\footnotesize, scale=1.0]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  % axes
  \draw[->, thick] (0,0) -- (7.4,0) node[right] {$n$ (steps before bootstrap)};
  \draw[->, thick] (0,0) -- (0,3.4) node[above] {weight};
  % decaying weight bars (1-lam) lam^(n-1), lam=0.6 scaled
  \foreach \n/\h in {1/3.0, 2/1.8, 3/1.08, 4/0.65, 5/0.39, 6/0.23} {
    \draw[acc, very thick, fill=acc!15] ({\n-0.78},0) rectangle ({\n-0.42},\h);
  }
  % endpoint labels
  \node[acc, anchor=south] at (0.6,3.05) {TD(0)};
  \node[green, anchor=west] at (5.7,0.55) {toward MC};
  \draw[green, very thick, ->] (5.6,0.35) -- (6.9,0.35);
  \node[black, anchor=north] at (0.6,0) {$1$};
  \node[black, anchor=north] at (5.6,0) {terminal};
\end{tikzpicture}
$$

The $\lambda$-return as written is a **forward view**: it looks ahead to future
rewards, so like MC it needs the whole episode. The equivalent **backward view**
makes it online and incremental through **eligibility traces**. Each state keeps a
trace $e(s)$ that spikes on visit and decays by $\gamma\lambda$, marking how
recently and how often it was seen. A single TD error $\delta_t$ is then broadcast
to all states in proportion to their trace.

> **Definition (Eligibility trace).** A memory $e_t(s)$ updated each step by
> $e_t(s) = \gamma\lambda\, e_{t-1}(s) + \mathbf{1}[S_t = s]$ (accumulating) or
> reset to $1$ on visit (replacing). The backward-view TD($\lambda$) update
> applies the current TD error to _every_ state at once,
> $V(s) \gets V(s) + \alpha\,\delta_t\, e_t(s)$, assigning credit backward in time
> along the trace.

For an offline (whole-episode) update, the backward and forward views compute
exactly the same total change, so eligibility traces are a memory-efficient,
causal implementation of the $\lambda$-return rather than a different algorithm.

> **Theorem (Forward-backward equivalence).** Summed over an episode, the offline
> backward-view TD($\lambda$) updates equal the offline forward-view
> $\lambda$-return updates: $\sum_t \alpha\,\delta_t\, e_t(s) = \sum_t \alpha\,
> [\,G_t^\lambda - V(S_t)\,]\,\mathbf{1}[S_t = s]$ for every $s$.

## Function approximation and semi-gradient TD

A table $V(s)$ is impossible when the state space is huge or continuous, the
regime every deep RL agent lives in. We replace the table with a parametric
$\hat v(s; w) \approx v_\pi(s)$, a linear map or a neural network with weights
$w$, and learn $w$ by [stochastic gradient descent](/deep-learning/optimization/gradient-descent-and-sgd).
The natural objective is the **mean-squared value error**, the value gap weighted
by how often the policy visits each state:

$$
\overline{\text{VE}}(w) = \sum_{s} d_\pi(s)\, \brackets{v_\pi(s) - \hat v(s; w)}^2,
$$

where $d_\pi$ is the on-policy state distribution. The true target
$v_\pi(s)$ is unknown, so we substitute a sampled target. With the MC target
$G_t$ this is honest SGD on a sampled return. With the **TD target**
$R_{t+1} + \gamma\hat v(S_{t+1}; w)$ it is **not**: the target itself depends on
$w$, and we deliberately ignore that dependence when taking the gradient.

> **Definition (Semi-gradient TD(0)).** The update
> $$
> w \;\gets\; w + \alpha\brackets{R_{t+1} + \gamma\hat v(S_{t+1}; w) - \hat v(S_t; w)}\,
> \nabla_w \hat v(S_t; w)
> $$
> differentiates only the prediction $\hat v(S_t; w)$, treating the bootstrap
> target as a constant. It is "semi" because it drops the $\nabla_w$ of the target,
> so it is not the true gradient of any objective.

Dropping that term is what makes it efficient and what makes it dangerous.

## The deadly triad

For on-policy linear function approximation, semi-gradient TD converges. But
three ingredients, when combined, can make the weights **diverge to infinity**
even on a finite Markov chain.

> **Definition (The deadly triad).** Instability that can cause value-function
> estimates to diverge arises when all three of the following are present at once:
> **(1) bootstrapping** (updating toward an estimate, as in TD or DP rather than
> MC); **(2) off-policy training** (learning about a target policy from data
> generated by a different behavior policy); and **(3) function approximation**
> (a parametric $\hat v$, especially nonlinear). Remove any one and stability is
> restored.

Each leg alone is safe. On-policy TD with linear approximation converges; tabular
off-policy Q-learning converges; MC with any approximator converges (it does not
bootstrap). The interaction is the hazard. The simplest divergent example is named
after its author.

> **Theorem (Baird's counterexample).** There is a finite seven-state Markov
> process, a linear value approximation, and an off-policy semi-gradient TD update
> for which the weight vector $w$ diverges: $\norm{w_t} \to \infty$ as
> $t \to \infty$, even though a representable solution with zero value error
> exists.

Geometrically the failure is an expansion. On-policy, the TD update is a
contraction in the $d_\pi$-weighted norm, so iterates are pulled inward toward a
fixed point. Off-policy, the data distribution no longer matches the policy being
evaluated; the semi-gradient update can become an **expansion**, and each step
pushes the weights farther out.

$$
% caption: On-policy, semi-gradient TD contracts toward a fixed point; off-policy, the
% same update can expand, driving the weight norm $\norm{w_t}$ to diverge.
\begin{tikzpicture}[>=stealth, font=\footnotesize, scale=1.0]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  \definecolor{red}{HTML}{C0392B}
  % axes
  \draw[->, thick] (0,0) -- (7.2,0) node[right] {update step $t$};
  \draw[->, thick] (0,0) -- (0,4.0) node[above] {weight size};
  % on-policy: converges to a floor
  \draw[green, very thick] plot[domain=0:6.8, samples=70]
    (\x, {0.7 + 2.0*exp(-0.7*\x)});
  \node[green, anchor=west] at (3.3,0.95) {on-policy: converges};
  % off-policy: diverges (grows)
  \draw[red, very thick] plot[domain=0:6.0, samples=70]
    (\x, {0.6*exp(0.31*\x)});
  \node[red, anchor=south] at (3.3,3.35) {of\/f-policy: diverges};
\end{tikzpicture}
$$

The triad is the reason deep RL is hard.
Deep Q-networks combine all three legs (a bootstrapped target, off-policy replay,
and a neural approximator), and the stabilizing tricks of modern value-based deep
RL, target networks and large replay buffers among them, exist precisely to tame
this interaction. True-gradient methods that descend the projected Bellman error
restore convergence at the cost of a second set of weights.

## Putting it together

The whole family is two binary choices: how the target is formed (sample versus
bootstrap), and whose policy the target evaluates (behavior versus a different
target policy).

| Method | Target | Bootstraps | On/off-policy | Needs model |
| --- | --- | --- | --- | --- |
| Dynamic programming | full expectation over $s'$ | yes | n/a | yes |
| Monte Carlo | full return $G_t$ | no | on-policy | no |
| TD(0) prediction | $R + \gamma V(S')$ | yes | on-policy | no |
| SARSA | $R + \gamma Q(S', A')$ | yes | on-policy | no |
| Q-learning | $R + \gamma \max_{a'} Q(S', a')$ | yes | off-policy | no |
| TD($\lambda$) | $\lambda$-return $G_t^\lambda$ | partial | on-policy | no |

## The maximization bias

Q-learning's $\max_{a'} Q(S_{t+1}, a')$ target has a subtle flaw the full [reinforcement-learning subject](/reinforcement-learning/tabular-methods/td-control-sarsa-and-q-learning) treats in depth and this lesson glossed: taking a $\max$ over _noisy_ estimates systematically overestimates. Because $\mathbb{E}[\max_a X_a] \ge \max_a \mathbb{E}[X_a]$ whenever the $X_a$ are noisy, the greedy target is biased _upward_ even when every action's true value is identical. If two actions both have true value $0$ but this sample reads $Q(s,a_1)=+0.3$ and $Q(s,a_2)=-0.3$, the correct target is $0$ yet $\max_a Q(s,a)=+0.3$; averaged over many visits the noise never cancels, because the $\max$ always picks whichever estimate it happened to inflate.

**Double Q-learning fixes it by decoupling selection from evaluation.** Keep two independent tables $Q_1$ and $Q_2$; use one to _select_ the greedy action and the other to _evaluate_ it, with target $R_{t+1} + \gamma\, Q_2\!\big(S_{t+1},\, \arg\max_{a'} Q_1(S_{t+1}, a')\big)$, alternating which is updated. The noise that inflated the selected action in $Q_1$ is not the noise in $Q_2$'s estimate of it, so the upward bias cancels in expectation.

$$
% caption: Maximization bias. Two actions with true value 0 have noisy estimates; the
% max always picks the noise-inflated one (blue), so the greedy target sits above 0.
% Double Q-learning evaluates the selected action with an independent estimate, cancelling it.
\begin{tikzpicture}[>=stealth, font=\footnotesize, scale=1.0]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  \definecolor{red}{HTML}{C0392B}
  \draw[->, thick] (0,0) -- (7.6,0) node[right, font=\scriptsize] {action};
  \draw[thick, dashed, black] (0,1.4) -- (7.2,1.4) node[right, font=\scriptsize, black] {true value 0};
  % noisy estimate bars above/below the true-value line
  \draw[acc, thick, fill=acc!18] (0.6,1.4) rectangle (1.6,2.3);
  \draw[black, thick, fill=black!8] (2.6,0.6) rectangle (3.6,1.4);
  \draw[black, thick, fill=black!8] (4.6,1.0) rectangle (5.6,1.4);
  \node[anchor=north, font=\scriptsize] at (1.1,-0.05) {$a_1$};
  \node[anchor=north, font=\scriptsize] at (3.1,-0.05) {$a_2$};
  \node[anchor=north, font=\scriptsize] at (5.1,-0.05) {$a_3$};
  \node[acc, anchor=south, font=\scriptsize] at (1.1,2.35) {max picks this};
  \node[red, anchor=west, font=\scriptsize] at (2.0,2.6) {target biased above 0};
\end{tikzpicture}
$$

**Double DQN** applies exactly this decoupling to the deep-Q-network of the [next lesson](/deep-learning/reinforcement-learning/deep-q-networks), using the online network to select and the target network to evaluate, measurably reducing the overestimation that plagues vanilla DQN.

## Takeaways

- **Model-free** methods estimate $v_\pi$ or $q_\pi$ from sampled transitions,
  never forming the unknown $P$ and $R$. Both prediction and control reduce to
  estimating the return $\mathbb{E}_\pi[G_t]$ from experience.
- **Monte Carlo** averages complete-episode returns: unbiased, high variance, and
  blocked in continuing tasks. **First-visit** and **every-visit** variants both
  converge to $v_\pi$.
- **TD(0)** bootstraps, $V(S_t) \gets V(S_t) + \alpha\,[R_{t+1} + \gamma
  V(S_{t+1}) - V(S_t)]$: online, low variance, biased early, and it exploits the
  Markov property by fitting the maximum-likelihood model.
- **MC control** with $\varepsilon$-greedy exploration converges to $q_\star$
  under **GLIE** (infinite exploration, greedy in the limit).
- **SARSA** ($R + \gamma Q(S', A')$) is on-policy and learns a safe path that
  accounts for its own exploration; **Q-learning** ($R + \gamma\max_{a'}Q(S',a')$)
  is off-policy and learns the optimal greedy path. Cliff walking separates them.
- **n-step returns** and **TD($\lambda$)** interpolate the MC-TD spectrum; the
  **$\lambda$-return** averages all $n$-step returns, and **eligibility traces**
  give an equivalent online backward-view implementation.
- **Semi-gradient TD** scales value estimation to parametric $\hat v(s; w)$ by SGD
  on the value error, dropping the target's gradient. Combining **bootstrapping**,
  **off-policy** training, and **function approximation**, the **deadly triad**,
  can diverge, as **Baird's counterexample** shows. This is the central difficulty
  of value-based deep RL.
- **Maximization bias:** the $\max$ target overestimates because
  $\mathbb{E}[\max_a X_a] \ge \max_a \mathbb{E}[X_a]$ under noise; **double
  Q-learning** cancels this by selecting the action with one estimate and evaluating
  it with an independent one, the idea Double DQN carries into deep RL.