Off-Policy Methods and the Deadly Triad

Off-policy 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 and that convenience collapses. The combination of learning off-policy, updating from an existing estimate, and generalizing across states with a parameter vector $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.¹

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 $π$ 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 $w$ , using the approximate value $\overset{v}{^} (s, w)$ and its gradient $\nabla \overset{v}{^} (s, w)$ .² Every per-step off-policy method uses the importance-sampling ratio

ρ_{t} ≐ ρ_{t : t} = \frac{π ( A _{t} ∣ S _{t} )}{b ( A _{t} ∣ 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 $ρ_{t}$ :

w_{t + 1} ≐ w_{t} + α ρ_{t} δ_{t} \nabla \overset{v}{^} (S_{t}, w_{t}), δ_{t} ≐ R_{t + 1} + γ \overset{v}{^} (S_{t + 1}, w_{t}) - \overset{v}{^} (S_{t}, w_{t}) .

The ratio $ρ_{t}$ scales the whole update by how much the target policy favored this transition. When $π$ would never take $A_{t}$ , $ρ_{t} = 0$ and the transition contributes nothing; when $π$ favors it more than $b$ did, $ρ_{t} > 1$ and the update is amplified.

These methods are called semi-gradient because $δ_{t}$ contains a bootstrapped estimate $\overset{v}{^} (S_{t + 1}, w_{t})$ that also depends on $w$ , yet the gradient is taken only of the current-state term $\overset{v}{^} (S_{t}, 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.

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 $π$ ; the multi-step generalizations of both state- and action-value methods reintroduce products of ratios $ρ_{t : t + n - 1}$ .

Examples of off-policy divergence

To see the instability in miniature, take the smallest possible example.³ Two states have estimated values $w$ and $2 w$ 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$ .

The w-to-2w fragment. The single transition has reward zero, so its TD error is

δ_{t} = γ 2 w_{t} - w_{t} = (2 γ - 1) w_{t}

, and one semi-gradient off-policy TD(0) step multiplies

w

1 + α (2 γ - 1)

The reward is zero, $ρ_{t} = 1$ (only one action, so both policies must take it), and the TD error on the transition is

δ_{t} = R_{t + 1} + γ \overset{v}{^} (S_{t + 1}, w_{t}) - \overset{v}{^} (S_{t}, w_{t}) = 0 + γ 2 w_{t} - w_{t} = (2 γ - 1) w_{t} .

The semi-gradient TD(0) update is therefore

w_{t + 1} = w_{t} + α ρ_{t} δ_{t} \nabla \overset{v}{^} (S_{t}, w_{t}) = w_{t} + α (2 γ - 1) w_{t} \cdot 1 = (1 + α (2 γ - 1)) w_{t} .

Each step multiplies $w$ by the constant $1 + α (2 γ - 1)$ . Whenever $γ > 0.5$ that constant exceeds $1$ , and $w$ grows without bound regardless of how small $α$ 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 $2 w$ 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 $γ = 0.9$ , $α = 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 $2 w$ 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 $α = 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 $γ$ 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.

The w-to-2w weight

w_{k} = (1 + α (2 γ - 1))^{k}

against sweeps, from

w_{0} = 1

. At

γ = 0.9, α = 0.1

the multiplier is 1.08 and the weight diverges geometrically; halving the step size to

α = 0.05

(multiplier 1.04) only slows it; at

γ = 0.5

the multiplier is exactly 1 and the weight is flat.

Baird's counterexample

The fragment is suggestive but incomplete. Can a full MDP actually diverge? Yes — Baird's counterexample is the standard demonstration.⁴ 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 $π$ always takes solid, so its on-policy distribution is concentrated on the seventh state. Every reward is zero and $γ = 0.99$ .

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

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.

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 —

w_{k + 1} ≐ w_{k} + \frac{α}{∣ S ∣} s \sum (E_{π} [R_{t + 1} + γ \overset{v}{^} (S_{t + 1}, w_{k}) ∣ S_{t} = s] - \overset{v}{^} (s, w_{k})) \nabla \overset{v}{^} (s, 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.

On Baird's counterexample the components of

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

α = 0.01

and the initial weights are

(1, 1, 1, 1, 1, 1, 10, 1)

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.⁵

The deadly triad. Each pair of ingredients is stable; only the central region, where function approximation, bootstrapping, and off-policy training overlap, risks divergence.

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: 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.

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. ↩
Sutton & Barto, §11.1 — Semi-gradient Methods: converting tabular off-policy algorithms to weight-vector updates, the per-step importance-sampling ratio $ρ_{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). ↩
Sutton & Barto, §11.2 — Examples of Off-policy Divergence: the $w$ -to- $2 w$ fragment, the TD error $(2 γ - 1) w_{t}$ , the update multiplier $1 + α (2 γ - 1)$ , and the argument that repeated off-policy updates without compensating transitions send $w$ to infinity whenever $γ > 0.5$ . ↩
Sutton & Barto, §11.2, Figure 11.1 and Figure 11.2: Baird's counterexample — the episodic seven-state, two-action MDP with the $2 w_{i} + w_{8}$ / $w_{7} + 2 w_{8}$ linear parameterization, behavior probabilities $6/7$ dashed and $1/7$ solid, $γ = 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. ↩
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. ↩