Deadly Triad: Why RL Diverges

Three good ideas, function approximation, bootstrapping, and off-policy data, turn toxic together. The updates stop shrinking errors and start growing them.

Function approximation, bootstrapping, and off-policy sampling combine into a feedback loop with gain 1.08, pushing one shared weight from 10.00 to 14.69 in five steps

Why Does This Exist?

You want three things at once. You want a compact value function that covers huge state spaces, so you use function approximation. You want updates after every step instead of waiting for episodes to end, so you bootstrap from your own estimates. And you want to learn from old or exploratory data, so you go off-policy. Each one is a win on its own, and any pair of them behaves.

Put all three together and learning can blow up. The weights do not settle near the truth. They grow every step, smoothly and confidently, until the values are garbage and the floats give up. The canonical demonstration is Baird's counterexample, and the fixes with real guarantees live under gradient TD methods. This page explains the mechanism: why the contraction that makes TD safe disappears the moment the sampling distribution stops matching the policy being evaluated.

The one idea you need first.

Temporal-difference learning updates a guess from another guess. After moving from state $S$ to state $S'$ with reward $R$ , it forms the TD error $\delta = R + \gamma \hat{v}(S') - \hat{v}(S)$ , where $\hat{v}$ is your current value estimate and $\gamma$ is the discount factor, then nudges the weights with $\mathbf{w} \leftarrow \mathbf{w} + \alpha \delta \nabla \hat{v}(S)$ with step size $\alpha$ . The target $R + \gamma \hat{v}(S')$ is built from your own estimate. That self reference is the bootstrapping leg of the triad.

Think of It Like This

A PA system about to howl

You are running sound for a small gig. A microphone picks up the whole room, one speaker replays what the mic hears, and someone carries the mic into the corner by the speaker while the room EQ was tuned for the center.

Point for point: the mic hearing everything at once is function approximation, because one shared weight feels every state. The speaker replaying the mic is bootstrapping, because each target is built from your own current estimates. Carrying the mic somewhere the EQ never accounted for is off-policy sampling, because the update distribution no longer matches the policy being evaluated. Each loop through the system multiplies the hum by a fixed gain, here $1.08$ , so $10.00$ becomes $10.80$ , then $11.66$ , then worse. Any two pieces alone stay quiet. The mic plus the speaker, aimed right, is fine. All three together howl.

Where it stops: a real PA saturates at the speaker's maximum volume, so the screech plateaus. TD weights have no ceiling. They grow geometrically until the values overflow to infinity or NaN.

How It Actually Works

The three ingredients in symbols

Write the approximate value as $\hat{v}(s, \mathbf{w})$ , a parameterized function of state $s$ with weights $\mathbf{w}$ . Each step computes the TD error $\delta = R + \gamma \hat{v}(S', \mathbf{w}) - \hat{v}(S, \mathbf{w})$ and moves the weights along the gradient of the current state's value: $\mathbf{w} \leftarrow \mathbf{w} + \alpha \delta \nabla_{\mathbf{w}} \hat{v}(S, \mathbf{w})$ . Three choices hide inside that one line:

Function approximation means $\hat{v}$ shares weights across states, so fixing one state's value shifts its neighbors.
Bootstrapping means the target contains $\hat{v}(S', \mathbf{w})$ , your own estimate, so errors feed back into the next target.
Off-policy learning means the sampled states $S$ come from a behavior policy $b$ that differs from the target policy $\pi$ being evaluated, as covered in off-policy learning with approximation.

Drop any one and a classical result keeps you safe. Tabular off-policy TD contracts in the maximum norm. On-policy linear TD converges because the projection and the Bellman operator agree on the weighting. Monte Carlo with approximation is true gradient descent on prediction error, since its targets never bootstrap. Only the triple has no such guarantee.

Why the contraction breaks

Think of the update as applying a projected Bellman operator: first the Bellman backup improves the values, then a projection squeezes the result back into what your function class can represent. On-policy, both stages shrink errors when measured under the policy's own visit distribution, and Tsitsiklis and Van Roy showed linear TD converges there. Off-policy, the projection is weighted by the behavior distribution while the backup still belongs to the target policy. That mismatch lets the combined operator stretch some error directions instead of shrinking them. Stretched errors get re-sampled, re-bootstrapped, and stretched again, which is the geometric growth you will compute below.

Deep Q-networks live inside the triad by construction: neural network approximation, one-step TD targets, and a replay buffer full of old policies. They survive it with engineering, chiefly target networks that freeze the bootstrap target while the online weights move.

Worked example

Two states, one shared weight $w$ , discount $\gamma = 0.9$ , step size $\alpha = 0.1$ , starting at $w_0 = 10.0$ . State 1 has feature $1.0$ so $\hat{v}(1) = w$ , state 2 has feature $2.0$ so $\hat{v}(2) = 2w$ . All rewards are $0$ . The behavior policy samples only transitions from state 1 to state 2.

Each step: the target is $0 + 0.9 \times 2w = 1.8w$ , the current estimate is $w$ , so the TD error is $\delta = 0.8w$ . The gradient of $\hat{v}(1)$ with respect to $w$ is $1.0$ , giving $w \leftarrow w + 0.1 \times 0.8w = 1.08w$ . Every step multiplies by $1.08$ :

$w_0 = 10.00$
$w_1 = 10.80$
$w_2 = 11.66$
$w_5 = 14.69$
$w_{10} = 21.59$ , still climbing with no ceiling

The true values are all $0$ , so every step walks away from the answer. Now sample on-policy instead, visiting both states evenly: the expected multiplier flips to $0.93$ , and the same rule contracts toward $0$ . Same update, same step size. Only the sampling distribution changed, which is the whole lesson.

Code

A minimal replay of the worked example: one shared weight, off-policy sampling of state 1 only, five updates.

1def td_step(w: float, gamma: float = 0.9, alpha: float = 0.1) -> float:2    """One semi-gradient TD(0) update on the 1 -> 2 transition."""3    target = gamma * (2.0 * w)  # R=0 plus bootstrapped value of state 24    error = target - (1.0 * w)  # TD error against state 1 estimate5    return w + alpha * error * 1.0  # gradient of v(1) wrt w is 1.06
7
8w = 10.09for _ in range(5):10    w = td_step(w)11print(f"{w:.4f}")  # -> 14.6933

The printout matches the hand arithmetic: $10.00 \times 1.08^5 = 14.6933$ . Change the sampled transition to alternate between the two states and the trajectory shrinks instead.

Watch Out For

A replay buffer without a frozen target still howls

The symptom is unmistakable once you have seen it: Q-values creep upward across training, then spike, then NaN, while the TD loss looks unrelated to policy quality. The cause is the triad running at full strength: the network generalizes each update, targets bootstrap from the same moving weights, and the buffer serves stale off-policy transitions.

Freeze the bootstrap target. Keep a separate target network whose weights trail the online net with infrequent copies or slow Polyak averaging, and build TD targets from it. If values still climb, shorten the target sync gap last and check reward scale first, since huge rewards produce the same symptom through a different door.

Zero TD error on sampled states is not convergence

Under off-policy sampling the TD error can sit at zero on every transition you actually sample while unvisited states hold large errors your function class smears back in later. Symptom: training curves look flat and healthy, then evaluation on the target policy collapses.

Test on the distribution you care about, not the one you trained on. Evaluate the greedy policy's visited states separately, and if you need guarantees rather than engineering, reach for provably convergent off-policy methods such as gradient TD instead of more samples from the same behavior policy.

The Quick Version

The deadly triad is function approximation plus bootstrapping plus off-policy data, and divergence needs all three at once.
Shared weights let one state's error leak into its neighbors, bootstrapping feeds that error into the next target, and off-policy sampling replays the mismatch forever.
On-policy, the projected Bellman operator shrinks errors; off-policy, the projection and the backup disagree on weighting and the operator can stretch them.
In the two-state example each update multiplies the weight by 1.08, so 10.00 reaches 14.69 in five steps while the true answer is 0.
Deep Q-networks live inside the triad and stay alive with frozen target networks that decouple the bootstrap target from the moving weights.
Zero TD error on your sampled states proves nothing about the target policy's states, so evaluate on-policy before trusting the curves.