Why is the deadly triad of approximation, bootstrapping and off-policy updates unstable?

### The three ingredients The deadly triad is the standard name for three properties of a value-learning setup: 1. **Function approximation** - values are produced by a parametric function with shared weights rather than stored per state. 2. **Bootstrapping** - the learning target for a state is built from the algorithm's own current estimate of a successor state, rather than from an observed full return. 3. **Off-policy updates** - the data comes from a behaviour policy that differs from the target policy whose values are being learned. In value-based deep RL this is the normal case: the agent explores, but the values being learned are those of a greedy target policy, and stored past experience was generated by older versions of the policy. The striking fact is that **any two of the three are safe**, and it is only the full combination that can diverge. ### Why each pair is fine - **Drop approximation.** Tabular value learning with bootstrapping and off-policy data converges under standard step-size conditions. Cells are independent, so an update to one state cannot corrupt another. - **Drop off-policy.** With a linear approximator and data drawn from the policy being evaluated, bootstrapped updates converge to a fixed point whose error is bounded relative to the best representable approximation. The proof leans on the fact that the update is a contraction in a norm weighted by the *on-policy* state distribution. - **Drop bootstrapping.** Fitting an approximator to full Monte-Carlo returns is ordinary supervised regression on unbiased targets - a genuine gradient method on a well-defined objective - and it converges to a local optimum whether the data is on-policy or corrected for off-policyness. That pattern tells you what the real culprit is: it is not any one ingredient but the interaction between *whose values move* and *whose data decides the move*. ### The mechanism of divergence Bootstrapping means the target is not a fixed label. It is `r + gamma * (an estimate produced by the same parameters being updated)`. Fitting toward it is therefore a feedback loop: you push the estimate for state `s` toward a number that depends on the estimate for its successor. With a table, that loop is a contraction - a discount factor below one shrinks any error each time it is propagated, so the loop settles. With an approximator, the update for `s` also drags the estimate for the successor, because they share weights. The composite operation is now two steps: back up the values (a contraction), then project the result back into the function class (which the on-policy weighting makes a non-expansion, but which off-policy weighting does not). Composing a contraction with a projection under the *wrong* weighting need not be a contraction at all. When the states being inflated are visited rarely under the behaviour policy, nothing in the data ever pulls them back down, while their inflated values keep feeding the targets of states that are visited often. The estimates escalate. It is also worth knowing that the standard bootstrapped update is a *semi-gradient*: it differentiates the prediction but not the target, even though the target depends on the same parameters. So it is not gradient descent on any fixed objective, and the usual reassurance that gradient descent at least decreases something does not apply. ### Baird's counterexample The canonical demonstration is Baird's star-shaped MDP. A small set of states is arranged so that a behaviour policy mostly visits the outer states while the target policy always transitions into a single central state. Features are linear and deliberately overlapping, all rewards are zero, and the true value function - all zeros - is exactly representable by the zero weight vector. Run off-policy bootstrapped updates and the weights nonetheless grow without bound. Three lessons come out of that example. **First**, divergence does not require a deep or nonlinear network; a linear approximator suffices. **Second**, it is not caused by approximation error, since the true answer sits inside the function class. **Third**, it is not a coding bug, which is why practitioners must recognise the pattern rather than hunt for one. ### What the triad does and does not predict The triad is a statement about risk, not a guarantee of failure. Plenty of value-based agents combine all three ingredients and train fine, which is why the standard stabilising machinery exists and why it is judged empirically. The triad tells you where to look when values climb without bound, and it tells you which knob genuinely removes the danger rather than merely postponing it. There are also algorithms that keep all three ingredients and restore convergence guarantees under linear approximation - the gradient-TD family such as TDC and GTD2, and emphatic TD, which reweights updates to restore the on-policy-like weighting. They pay for it with a second parameter vector or with high-variance weights, which is why they are less common in practice than engineering fixes. ### Answering well Name the three ingredients precisely, say that each pair is safe, and explain the feedback loop through shared parameters and mismatched data weighting. Citing Baird's counterexample to kill the idea that divergence is a nonlinearity problem is the detail that separates a memorised list from real understanding.