---
title: Off-Policy Methods and the Deadly Triad
module: Approximate Solution Methods
moduleNumber: 3
lessonNumber: 5
order: 305
summary: >
  Off-policy learning with function approximation is where the convergence
  guarantees of reinforcement learning fail. We extend the tabular off-policy
  updates to semi-gradient form with per-step importance sampling, show Baird's
  counterexample driving the weights to infinity, and identify the cause: the deadly
  triad of function approximation, bootstrapping, and off-policy training — any
  two are safe, all three can diverge. The divergence is not caused by sampling
  noise: a fully synchronous dynamic-programming update blows up just the same,
  which is what makes the triad a structural hazard rather than a fluke.
topics: [Approximation]
sources:
  - book: Sutton & Barto
    ref: "Ch. 11 — Off-policy Methods with Approximation; §11.1 Semi-gradient Methods; §11.2 Examples of Off-policy Divergence"
  - book: Sutton & Barto
    ref: "§11.3 The Deadly Triad"
---

[Off-policy learning](/reinforcement-learning/tabular-methods/temporal-difference-learning)
was almost free in the tabular case. Q-learning bootstrapped toward the greedy
target while a behavior policy explored, and the value table converged. Add
[function approximation](/reinforcement-learning/approximation/on-policy-prediction)
and that convenience collapses. The combination of learning off-policy, updating
from an existing estimate, and generalizing across states with a parameter vector
$\mathbf{w}$ can make the weights diverge to infinity — not on a contrived
pathology, but on a seven-state Markov process with a linearly independent feature
set. This lesson is about why, and about the two families of methods that repair
it.[^sb-intro]

The challenge splits cleanly in two. The **first part** is correcting the _target_
of each update: the behavior policy $b$ samples actions the target policy $\pi$
would not, so the update must be reweighted by an importance-sampling ratio. That
part carries over from the tabular case unchanged. The **second part** is that the
_distribution_ of updates no longer matches the on-policy distribution, and that
mismatch is what breaks stability. The bulk of this lesson is the second part.

## Semi-gradient off-policy methods

Converting a tabular off-policy algorithm to function approximation is mechanical:
replace the update to a table entry ($V$ or $Q$) with an update to the weight vector
$\mathbf{w}$, using the approximate value $\hat{v}(s, \mathbf{w})$ and its gradient
$\nabla \hat{v}(s, \mathbf{w})$.[^sb-semi] Every per-step off-policy method uses the
importance-sampling ratio

$$
\rho_t \;\doteq\; \rho_{t:t} \;=\; \frac{\pi(A_t \mid S_t)}{b(A_t \mid S_t)},
$$

the relative probability that the target and behavior policies take the action
actually taken. The one-step state-value method, **semi-gradient off-policy TD(0)**,
takes the on-policy rule and multiplies in $\rho_t$:

$$
\mathbf{w}_{t+1} \;\doteq\; \mathbf{w}_t + \alpha\, \rho_t\, \delta_t\, \nabla \hat{v}(S_t, \mathbf{w}_t),
\qquad
\delta_t \;\doteq\; R_{t+1} + \gamma\, \hat{v}(S_{t+1}, \mathbf{w}_t) - \hat{v}(S_t, \mathbf{w}_t).
$$

The ratio $\rho_t$ scales the whole update by how much the target policy favored
this transition. When $\pi$ would never take $A_t$, $\rho_t = 0$ and the transition
contributes nothing; when $\pi$ favors it more than $b$ did, $\rho_t > 1$ and the
update is amplified.

These methods are called **semi-gradient** because $\delta_t$ contains a bootstrapped
estimate $\hat{v}(S_{t+1}, \mathbf{w}_t)$ that also depends on $\mathbf{w}$, yet the
gradient is taken only of the current-state term $\hat{v}(S_t, \mathbf{w}_t)$. The
update follows part of the gradient of the squared error, not all of it. In the
tabular case they are provably convergent; the trouble is what the missing half
does once features are shared across states.

> **Definition (Semi-gradient method).** An update of the form $\mathbf{w}_{t+1} =
> \mathbf{w}_t + \alpha\,\delta_t\,\nabla \hat{v}(S_t, \mathbf{w}_t)$, where the TD
> error $\delta_t$ bootstraps from $\hat{v}(S_{t+1}, \mathbf{w}_t)$ but the gradient
> ignores that dependence. It moves $\mathbf{w}$ toward a moving target rather than
> down the true gradient of an error, which is why its convergence guarantees
> hold tabularly but not under off-policy function approximation.

The action-value case is analogous: semi-gradient Expected Sarsa uses no importance
sampling in its one-step form, because the only action sampled is $A_t$ and its
target already averages over $\pi$; the multi-step generalizations of both state-
and action-value methods reintroduce products of ratios $\rho_{t:t+n-1}$.

## Examples of off-policy divergence

To see the instability in miniature, take the smallest possible example.[^sb-diverge]
Two states have estimated values $w$ and $2w$ under a single scalar weight $w$ — the
feature vectors are the numbers $1$ and $2$. One action is available in the first
state, deterministically transitioning to the second with reward $0$.

$$
% caption: The w-to-2w fragment. The single transition has reward zero, so its TD
% error is $\delta_t = \gamma\,2w_t - w_t = (2\gamma - 1)w_t$, and one
% semi-gradient off-policy TD(0) step multiplies $w$ by $1 + \alpha(2\gamma - 1)$.
\begin{tikzpicture}[>=stealth, font=\small,
  st/.style={draw, circle, minimum size=11mm, inner sep=0pt}]
  \definecolor{acc}{HTML}{2348F2}
  \node[st] (a) at (0,0) {w};
  \node[st] (b) at (3,0) {2w};
  \draw[->, acc, thick] (a) -- node[above, font=\footnotesize, text=black] {reward 0} (b);
\end{tikzpicture}
$$

The reward is zero, $\rho_t = 1$ (only one action, so both policies must take it),
and the TD error on the transition is

$$
\delta_t \;=\; R_{t+1} + \gamma\, \hat{v}(S_{t+1}, w_t) - \hat{v}(S_t, w_t)
\;=\; 0 + \gamma\, 2w_t - w_t \;=\; (2\gamma - 1)\, w_t.
$$

The semi-gradient TD(0) update is therefore

$$
w_{t+1} \;=\; w_t + \alpha\, \rho_t\, \delta_t\, \nabla \hat{v}(S_t, w_t)
\;=\; w_t + \alpha (2\gamma - 1) w_t \cdot 1
\;=\; \bigl(1 + \alpha(2\gamma - 1)\bigr)\, w_t.
$$

Each step multiplies $w$ by the constant $1 + \alpha(2\gamma - 1)$. Whenever
$\gamma > 0.5$ that constant exceeds $1$, and $w$ grows without bound regardless of
how small $\alpha$ is — the step size sets the _rate_ of divergence, not whether it
happens. The mechanism is off-policy: this transition can occur over and over
without $w$ being pulled back by the transitions _out_ of the $2w$ state, because
the behavior policy takes actions there that the target policy never would. The
promised future value is never checked against real outcomes.

Put numbers on it. Take $\gamma = 0.9$, $\alpha = 0.1$, and start from $w_0 = 1$.
The multiplier is $1 + 0.1\,(2 \cdot 0.9 - 1) = 1 + 0.1 \cdot 0.8 = 1.08$, so the
weight is a geometric sequence $w_k = (1.08)^k$: it reaches $w_5 = 1.469$,
$w_{20} = 4.661$, $w_{50} = 46.90$, $w_{100} = 2199.8$. The estimated values $w$ and
$2w$ climb together, and because the reward is zero and the true value is zero, the
value error grows in lockstep. Halving the step size to $\alpha = 0.05$ only changes
the multiplier to $1.04$ and slows the climb — $w_{100} = (1.04)^{100} = 50.5$
instead of $2200$ — without ever turning the growth around. Drop $\gamma$ to $0.5$
and the multiplier is exactly $1$: the weight sits still, neither converging nor
diverging, the boundary below which the fragment is safe.

$$
% caption: The w-to-2w weight $w_k = (1 + \alpha(2\gamma-1))^k$ against sweeps, from
% $w_0 = 1$. At $\gamma = 0.9, \alpha = 0.1$ the multiplier is 1.08 and the weight
% diverges geometrically; halving the step size to $\alpha = 0.05$ (multiplier 1.04)
% only slows it; at $\gamma = 0.5$ the multiplier is exactly 1 and the weight is flat.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \draw[->, black] (0,0) -- (6.4,0) node[anchor=north east, font=\scriptsize] {sweeps k};
  \draw[->, black] (0,0) -- (0,4.2) node[anchor=south east, font=\scriptsize] {weight w};
  \node[anchor=north east, font=\scriptsize] at (-0.05,0) {1};
  % fast divergence, alpha=0.1
  \draw[red, very thick] (0,0.5)
    .. controls (2.6,0.75) and (4.0,1.7) .. (5.8,3.9);
  \node[red, anchor=west, font=\scriptsize] at (5.85,3.9) {a = 0.1};
  % slow divergence, alpha=0.05
  \draw[acc, very thick] (0,0.5)
    .. controls (3.0,0.62) and (4.6,1.0) .. (5.8,2.05);
  \node[acc, anchor=west, font=\scriptsize] at (5.85,2.05) {a = 0.05};
  % flat, gamma=0.5
  \draw[black, thick] (0,0.5) -- (5.8,0.5);
  \node[black, anchor=west, font=\scriptsize] at (5.85,0.5) {gamma = 0.5};
\end{tikzpicture}
$$

### Baird's counterexample

The fragment is suggestive but incomplete. Can a full MDP actually diverge? Yes —
**Baird's counterexample** is the standard demonstration.[^sb-baird] It is an episodic
seven-state, two-action MDP. The **dashed** action sends the system to one of the six
upper states with equal probability; the **solid** action sends it to the seventh
(lower) state. The behavior policy picks dashed with probability $6/7$ and solid with
$1/7$, making the next-state distribution uniform. The target policy $\pi$ always
takes solid, so its on-policy distribution is concentrated on the seventh state.
Every reward is zero and $\gamma = 0.99$.

The state values use an over-parameterized linear form: the six upper states are
$2w_1 + w_8, \dots, 2w_6 + w_8$ and the seventh is $w_7 + 2w_8$, with weight vector
$\mathbf{w} \in \mathbb{R}^8$. Because all rewards are zero, the true value is
$v_\pi(s) = 0$ everywhere, exactly representable by $\mathbf{w} = \mathbf{0}$. The
feature vectors are linearly independent. By every conventional measure this is a
_favorable_ case for linear approximation — and it diverges anyway.

$$
% caption: Baird's counterexample. Solid usually leads to the seventh state,
% dashed to one of the upper six; the behavior policy makes the next-state
% distribution uniform while the target policy always takes solid. All rewards
% are zero, so the true value is zero everywhere, yet the weights diverge.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  st/.style={draw, circle, minimum size=8.5mm, inner sep=0pt, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \foreach \i/\x in {1/-4.5, 2/-2.7, 3/-0.9, 4/0.9, 5/2.7, 6/4.5}
    \node[st] (u\i) at (\x,2.4) {2w\i+w8};
  \node[st] (low) at (-1.2,-1.6) {w7+2w8};
  % solid action: upper states to the lower state (target policy)
  \foreach \i in {1,...,6}
    \draw[->, acc, thick] (u\i) -- (low);
  % self-loop solid on the lower state
  \draw[->, acc, thick] (low) to[out=-120, in=-170, looseness=6] (low);
  % dashed action: lower state up to each upper state, bent aside to avoid the solid arrows
  \foreach \i in {1,...,6}
    \draw[->, dashed, red] (low) to[bend right=18] (u\i);
  \node[anchor=west, font=\scriptsize] at (2.9,-0.9) {pi(solid) = 1};
  \node[anchor=west, font=\scriptsize] at (2.9,-1.6) {b(dashed) = 6/7};
  \node[anchor=west, font=\scriptsize] at (2.9,-2.3) {b(solid) = 1/7};
  \node[anchor=west, font=\scriptsize] at (2.9,-3.0) {gamma = 0.99};
\end{tikzpicture}
$$

Apply semi-gradient off-policy TD(0) and the weights diverge to infinity for any
positive step size. The divergence is not caused by sampling noise or
asynchrony. If the expected update is done synchronously across all states — a
dynamic-programming update, no randomness at all —

$$
\mathbf{w}_{k+1} \;\doteq\; \mathbf{w}_k + \frac{\alpha}{|\mathcal{S}|}
\sum_s \Bigl( \mathbb{E}_\pi\bigl[ R_{t+1} + \gamma\, \hat{v}(S_{t+1}, \mathbf{w}_k) \mid S_t = s \bigr] - \hat{v}(s, \mathbf{w}_k) \Bigr) \nabla \hat{v}(s, \mathbf{w}_k),
$$

it still diverges. The only unconventional ingredient is that the update distribution
is uniform (the behavior distribution) rather than on-policy. Restore the on-policy
distribution and convergence returns.

$$
% caption: On Baird's counterexample the components of $\mathbf{w}$ under
% semi-gradient off-policy TD grow without bound; $w_7$ stays small while $w_8$
% and the block $w_1$ through $w_6$ climb. The step size is $\alpha = 0.01$ and
% the initial weights are $(1, 1, 1, 1, 1, 1, 10, 1)$.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % axes
  \draw[->, black] (0,0) -- (6.4,0) node[anchor=north east, font=\scriptsize] {sweeps};
  \draw[->, black] (0,0) -- (0,4.3) node[anchor=south east, font=\scriptsize] {weight value};
  \node[anchor=east, font=\scriptsize] at (-0.08,0) {0};
  % diverging curve w8
  \draw[acc, very thick] (0,0.35)
    .. controls (2.2,0.55) and (3.6,1.4) .. (5.9,4.0);
  \node[acc, anchor=west, font=\scriptsize] at (5.95,4.0) {w8};
  % diverging block w1..w6
  \draw[red, very thick] (0,0.35)
    .. controls (2.4,0.5) and (3.9,0.95) .. (5.9,2.35);
  \node[red, anchor=west, font=\scriptsize] at (5.95,2.35) {w1-w6};
  % flat w7
  \draw[black, thick] (0,0.7) -- (5.9,0.62);
  \node[black, anchor=west, font=\scriptsize] at (5.95,0.62) {w7};
\end{tikzpicture}
$$

The point of Baird's counterexample: semi-gradient TD and
a DP-style expected update are among the simplest, best-understood bootstrapping
methods, and linear approximation is the simplest, best-understood function
approximator, yet their combination under an off-policy update distribution is
unstable. Similar counterexamples exist for Q-learning, whose tabular convergence
guarantees are otherwise the strongest of any control method.

## The deadly triad

The danger can be named precisely. Instability and divergence arise whenever three
elements are combined; Sutton calls them **the deadly triad**.[^sb-triad]

> **Definition (The deadly triad).** The three ingredients whose combination risks
> divergence: **function approximation** (generalizing from a state space larger than
> the available memory, e.g. a linear map or a neural network), **bootstrapping**
> (update targets built from existing estimates, as in TD and DP, rather than actual
> returns as in Monte Carlo), and **off-policy training** (updating from a
> distribution of transitions other than the one the target policy would produce).
> Any two of the three are safe; all three together can diverge.

$$
% caption: The deadly triad. Each pair of ingredients is stable; only the central
% region, where function approximation, bootstrapping, and off-policy training
% overlap, risks divergence.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % three overlapping circles
  \draw[acc, thick, fill=acc!8] (0,0.75) circle (2.05);
  \draw[red, thick, fill=red!8] (-1.75,-1.25) circle (2.05);
  \draw[black, thick, fill=black!5] (1.75,-1.25) circle (2.05);
  % outer labels
  \node[acc, font=\footnotesize\bfseries, align=center] at (0,2.55) {function\\approximation};
  \node[red, font=\footnotesize\bfseries, align=center] at (-3.1,-2.15) {bootstrapping};
  \node[black, font=\footnotesize\bfseries, align=center] at (3.1,-2.15) {\texttt{off}-policy\\training};
  % center overlap
  \node[align=center, font=\scriptsize] at (0,-0.55) {all three:\\can diverge};
  % note
  \node[align=center, font=\scriptsize, black!70] at (0,-3.7) {any two of the three are stable};
\end{tikzpicture}
$$

The framing is useful because it identifies what could be given up. Consider each:

- **Function approximation** cannot be surrendered. Problems too large to tabulate are
  the entire point of approximation; state aggregation and nonparametric methods are
  either too weak or too expensive, and least-squares methods like LSTD are
  $O(d^2)$ — prohibitive at scale.
- **Bootstrapping** can be given up (that is Monte Carlo), at real cost in data and
  computational efficiency. Bootstrapping learns faster because it exploits the state
  property — recognizing a state on return — and it lets data be processed once and
  discarded rather than stored to the end of an episode. It is worth keeping.
- **Off-policy training** can sometimes be given up: Sarsa instead of Q-learning,
  on-policy control instead of off-policy. But off-policy learning is what enables
  learning many things in parallel from one stream of experience — many target policies
  and predictive questions sharing a single behavior policy — a capability we would very
  much like to keep for building predictive world models.

Two clarifications matter. The danger is _not_ specific to control or generalized
policy iteration; it appears in the simpler prediction case whenever the triad is
complete. And it is _not_ caused by learning or by uncertainty about the environment:
it occurs just as strongly in planning with a fully known model, as Baird's synchronous
DP update shows.

The triad reappears in
[deep Q-networks](/reinforcement-learning/deep-rl/deep-q-networks): DQN keeps all three
ingredients — a neural-network approximator, TD bootstrapping, and off-policy replay —
but stabilizes them with a slowly-updated **target network** and an **experience-replay
buffer** that between them break the correlations driving the instability.

## Where this leaves us

Off-policy learning with approximation is the point where the clean guarantees of
tabular RL give out. The first part of the challenge — correcting update targets
with importance sampling — is routine, if variance-prone. The second part — the
instability of bootstrapping under an off-policy update distribution — is the deadly
triad, and it is real enough to send a linearly-independent seven-state problem to
infinity, with no sampling noise required.

Naming the failure does not fix it. Why the triad diverges — and the two families
of methods that stop it without giving up any leg of the triad — needs a geometric
picture of what TD methods are minimizing. That continues in
[value-function geometry and Gradient-TD methods](/reinforcement-learning/approximation/bellman-error-and-gradient-td).

[^sb-intro]: **Sutton & Barto**, _Reinforcement Learning: An Introduction_ (2nd ed.), Ch. 11 — introduction: the two-part challenge of off-policy learning with function approximation (correcting the target with importance sampling, and correcting the update distribution), and the observation that semi-gradient methods address the first part but may diverge on the second.
[^sb-semi]: **Sutton & Barto**, §11.1 — Semi-gradient Methods: converting tabular off-policy algorithms to weight-vector updates, the per-step importance-sampling ratio $\rho_t$ (11.1), semi-gradient off-policy TD(0) (11.2)–(11.4), semi-gradient Expected Sarsa (11.5) without importance sampling, and the $n$-step and tree-backup generalizations (11.6)–(11.8).
[^sb-diverge]: **Sutton & Barto**, §11.2 — Examples of Off-policy Divergence: the $w$-to-$2w$ fragment, the TD error $(2\gamma - 1)w_t$, the update multiplier $1 + \alpha(2\gamma - 1)$, and the argument that repeated off-policy updates without compensating transitions send $w$ to infinity whenever $\gamma > 0.5$.
[^sb-baird]: **Sutton & Barto**, §11.2, Figure 11.1 and Figure 11.2: Baird's counterexample — the episodic seven-state, two-action MDP with the $2w_i + w_8$ / $w_7 + 2w_8$ linear parameterization, behavior probabilities $6/7$ dashed and $1/7$ solid, $\gamma = 0.99$, and the demonstration that both semi-gradient off-policy TD and the synchronous DP update (11.9) diverge though the true value is zero and exactly representable.
[^sb-triad]: **Sutton & Barto**, §11.3 — The Deadly Triad: function approximation, bootstrapping, and off-policy training as the three ingredients whose combination risks divergence; the argument that any two are safe; that the danger is not specific to control and not caused by learning or environmental uncertainty; and the case-by-case discussion of which leg could be given up.