The Deadly Triad: When Approximation Diverges

Three innocent ingredients

The deadly triad is the most important warning in this whole track. It names three features that are individually fine but jointly dangerous: (1) function approximation, so values generalize and can interfere; (2) bootstrapping, so targets depend on current estimates; and (3) off-policy training, where the data is collected by a different policy than the one being evaluated. Hold all three at once and your value estimates can diverge to infinity even on a tiny, fully specified problem.

Drop any one and you are safe. Tabular learning (no approximation) is safe. Monte Carlo (no bootstrapping) is safe. On-policy semi-gradient TD (no off-policy) is safe — that is why guide 3's methods converged. The danger lives only at the intersection.

How the blow-up happens

Recall that semi-gradient TD is not a true gradient — it has no objective pulling it down. On-policy, the distribution of updates still forms a contraction that drags estimates toward the fixed point. Off-policy, the mismatch between the behaviour distribution and the target distribution can turn that operator into an expansion: each sweep multiplies the error by more than one. The feedback loop is vicious — raise v̂ at one state, its bootstrapped target rises too (it generalizes), which raises v̂ further. This is function-approximation divergence.

\mathbf{w}_{k+1} = \mathbf{w}_k + \alpha\,(\mathbf{b} - \mathbf{A}\,\mathbf{w}_k)

The expected linear TD update: on-policy the matrix A keeps it a contraction toward the fixed point; off-policy A can flip sign and the same update drives the weights to infinity.

Why the obvious fixes fall short

Could importance sampling save us? It corrects the off-policy distribution in expectation, but its ratios can be huge, injecting crushing variance — it patches the bias, not the instability. Could we just use residual gradients? Yes, they converge off-policy, but, as guide 3 noted, they are slow and learn over-smoothed values, and need double samples to be unbiased. And tightening the step size only slows the explosion; it does not turn an expansion into a contraction.

\rho_t = \frac{\pi(A_t\mid S_t)}{b(A_t\mid S_t)},\qquad \rho_{t:T-1} = \prod_{k=t}^{T-1}\frac{\pi(A_k\mid S_k)}{b(A_k\mid S_k)}

The importance-sampling ratio reweights off-policy data; multiplied over many steps these ratios can explode — the crushing variance this section warns about.

What we actually want is the best of both: the speed and accuracy of semi-gradient TD, but with a real objective so convergence is guaranteed off-policy. That is exactly what gradient-TD methods deliver.

Gradient-TD: a true objective at last

Gradient temporal-difference methods (GTD2, TDC) descend a genuine objective — the mean squared projected Bellman error — which measures the Bellman residual after projecting it back onto the representable plane. Because it is a real gradient of a real loss, gradient-TD provably converges even with all three triad ingredients present, while staying linear-time per step. The cost is a second small set of weights and a second step size to tune.

The intellectual payoff: by measuring the projected Bellman error, gradient-TD respects exactly what guide 3 taught — that the best a linear method can do is the projected fixed point — and then descends honestly toward it. It is the principled resolution of the triad for the linear case.

A second hazard: overestimation

Even a method that converges can converge to something biased upward. Overestimation in approximation is the control-side cousin of divergence. Q-learning takes a max over noisy action-values; the max of noisy estimates is biased high, and approximation adds correlated noise that generalizes across actions, so the inflation compounds rather than averaging out. The agent ends up believing several actions are better than they are.