Value-Function Geometry and Gradient-TD Methods

This builds on off-policy methods and the deadly triad, which showed that function approximation, bootstrapping, and off-policy training together can send the weights to infinity — on a seven-state problem with linearly independent features, no less. That lesson named the failure but did not explain it. This lesson does, by picturing value functions as points in a vector space, and from that picture builds the two families of methods that make off-policy learning stable.

Linear value-function geometry

To understand why the triad diverges and how to fix it, it helps to picture value functions as vectors.¹ Enumerate the states $\mathcal{S}=\{s_1,\dots ,s_{|\mathcal{S}|}\}$; then any value function $v$ is the vector $[v(s_1),\dots ,v(s_{|\mathcal{S}|}){]}^{\top }$ in an $|\mathcal{S}|$-dimensional space. The whole space holds every conceivable value function; most correspond to no policy at all.

A linear approximator with $d<|\mathcal{S}|$ parameters can only reach a $d$-dimensional subspace of that space — the plane of all $v_{\mathbf{w}}=\mathbf{Xw}$ representable by some weight vector. The true value $v_{\pi }$ of a policy generally lies outside this subspace, too complex to represent exactly.

To measure how far apart two value functions are, Euclidean distance is wrong: some states matter more because they are visited more often. Weight each state by the distribution $\mu$ (typically the on-policy distribution) and use the $\mu$-norm

The projection operator $\Pi$ takes any value function to the representable one closest in this norm:

where $\mathbf{X}$ stacks the feature vectors as rows and $\mathbf{D}$ is the diagonal matrix of the weights $\mu (s)$. The projection of the true value, $\Pi v_{\pi }$, is the best representable approximation in the value-error sense, and the point Monte Carlo methods converge to.

Bellman error versus projected Bellman error

TD methods aim somewhere else. The Bellman operator $B_{\pi }$ applies one sweep of the Bellman equation:

Its unique fixed point is the true value: $v_{\pi }=B_{\pi }{v}_{\pi }$, which is just the Bellman equation rewritten. For any representable $v_{\mathbf{w}}$, the difference ${\bar{\delta }}_{\mathbf{w}}=B_{\pi }{v}_{\mathbf{w}}-v_{\mathbf{w}}$ is the Bellman error vector — the expectation of the TD error at each state — and its squared $\mu$-norm is the mean square Bellman error:

Here is the geometric crux. Applying $B_{\pi }$ to a representable value function generally produces one outside the subspace (the gray arrow leaving the plane in the figure). In pure dynamic programming, without approximation, you follow $B_{\pi }$ repeatedly and converge to $v_{\pi }$. With approximation you cannot: after one Bellman step you must project back into the subspace to have a representable function, then step out again, then project back. The quantity TD methods drive to zero is the residual inside the subspace — the projected Bellman error:

The three objectives generally have different minimizers: $\overline{VE}$ is minimized at $\Pi v_{\pi }$, $\overline{BE}$ at some other point, and $\overline{PBE}$ at the TD fixed point ${\mathbf{w}}_{\text{TD}}$. Semi-gradient TD, when it converges, converges to ${\mathbf{w}}_{\text{TD}}$ — but under off-policy training it need not converge at all.

A tempting fix is to do true gradient descent on the Bellman error itself (the residual-gradient algorithm), which is a genuine SGD method and converges. But two results rule it out as a general approach. First, on the A-split example it converges to the wrong values, minimizing a temporal-smoothing surrogate rather than accuracy. Second, and more fundamentally, the $\overline{BE}$ is not learnable: two Markov reward processes can produce identical data yet have different $\overline{BE}$-minimizing weight vectors, so no algorithm working from feature vectors, actions, and rewards alone can minimize it.² That leaves the $\overline{PBE}$, which is learnable, as the objective worth pursuing.

Gradient-TD methods

Gradient-TD methods perform true stochastic gradient descent on the $\overline{PBE}$.³ Because they follow an actual gradient, they inherit SGD's robust convergence — stable even under off-policy training and nonlinear approximation — at $O(d)$ cost per step, only about double that of semi-gradient TD.

The derivation expands the $\overline{PBE}$ in matrix form and differentiates. The key point in the algebra: the gradient factors into three pieces, and two of them share a random quantity (${\mathbf{x}}_{t+1}$), so sampling each independently and multiplying would double-count the noise. Gradient-TD works around that one obstacle.

The gradient turns out to be a product of three expectations,

and the trouble is that the first and last factors both depend on the next feature ${\mathbf{x}}_{t+1}$, so sampling them independently and multiplying gives a biased estimate — the same double-sampling problem that afflicts the residual-gradient method. The Gradient-TD solution is to estimate and store the product of the last two factors as a second parameter vector $\mathbf{v}$,

which is the solution to a least-squares problem and is learned by an importance-weighted LMS rule on a second, faster step size $\beta$:

Given ${\mathbf{v}}_t$, the main weight vector is updated by a rule that is $O(d)$ if the inner product ${\mathbf{x}}_t^{\top }{\mathbf{v}}_t$ is formed first. Two members of the family:

TDC (TD with gradient correction) is the semi-gradient TD update $\alpha {\rho }_t{\delta }_t{\mathbf{x}}_t$ plus a correction term $-\alpha {\rho }_t\gamma {\mathbf{x}}_{t+1}({\mathbf{x}}_t^{\top }{\mathbf{v}}_t)$ that supplies the missing half of the gradient. That single correction is the difference between divergence and convergence.

On Baird's counterexample TDC does exactly what the theory promises: the $\overline{PBE}$ decays to zero and the weights stop growing. Notice the components do not all reach zero, so the value error stays near $2$ — the $\overline{PBE}$ fixed point is not the best approximation in the $\overline{VE}$ sense — but the divergence is gone. GTD2 and TDC are two-time-scale methods: the correction estimate $\mathbf{v}$ (fast, step size $\beta$) must track ahead of the primary weights $\mathbf{w}$ (slow, step size $\alpha$), which the convergence proofs formalize as a cascade requiring $\beta \to 0$ and $\alpha /\beta \to 0$. Gradient-TD is currently the best-understood and most widely used family of stable off-policy methods, with extensions to action values, control, and eligibility traces.

A note on emphatic-TD

Gradient-TD attacks the second part of the problem — the wrong update distribution — by building a true gradient method. Emphatic-TD attacks it differently: keep the simple, computationally cheap semi-gradient update, but reweight the states so the update distribution recovers the on-policy properties that make linear semi-gradient TD stable.⁴ Linear semi-gradient TD is stable on-policy precisely because the state distribution matches the transitions under $\pi$; emphatic-TD manufactures that match by scaling each update with an emphasis $M_t$ that accumulates responsibility for the current state through a recursive trace,

with the interest $I_t$ specifying how much we care about accurately valuing each state. In expectation, emphatic-TD converges to zero value error on Baird's counterexample; in practice its variance is so high that consistent results are hard to obtain, which is why the next section turns to variance-reduction techniques for all of these methods.

Reducing variance

Stability is only half the problem. Gradient-TD and emphatic-TD keep the weights from diverging, but off-policy learning is inherently higher-variance than on-policy learning, and that variance is what makes these methods slow and their results erratic in practice.⁵ The intuition is plain: if the data you receive is only loosely related to the policy you are trying to evaluate, you should expect to learn less about it. In the extreme you learn nothing — you cannot learn to drive by cooking dinner. Only when the target and behavior policies visit similar states and take similar actions is real progress possible.

Yet that overlap is what off-policy learning is for: any policy has many neighbors, similar-but-not-identical policies with considerable overlap, and the whole reason to learn off-policy is to generalize across that vast family of related policies from one stream of experience. So the variance cannot simply be avoided; it has to be managed.

Where the variance comes from

The specific source is the importance-sampling ratio. As we saw, off-policy targets are corrected by products of per-step ratios ${\rho }_t=\pi (A_t\mid S_t)/b(A_t\mid S_t)$. Each ratio is $1$ in expectation, and successive ratios are uncorrelated, so their products are $1$ in expectation too — but their values swing from zero up to very large numbers, and a product of such terms has very high variance.⁵

A worked case shows how fast the product blows up. Let the behavior policy be uniform over two actions, $b(a\mid s)=0.5$, while the target policy is nearly deterministic, $\pi (a_1\mid s)=0.9$ and $\pi (a_2\mid s)=0.1$. The per-step ratio is then $\rho =0.9/0.5=1.8$ when the behavior policy happens to sample $a_1$ and $\rho =0.1/0.5=0.2$ when it samples $a_2$; each occurs with probability $0.5$, and the mean is $0.5\cdot 1.8+0.5\cdot 0.2=1$, as it must be. Over a horizon of $n=10$ steps the cumulative ratio ${\rho }_{t:t+9}$ is a product of ten such draws. Its mean stays exactly $1$, but its spread is enormous: an all-$a_1$ trajectory (probability $0.5^{10}\approx 0.001$) carries $1.8^{10}\approx 357$, while a trajectory with even one $a_2$ is scaled down by the $0.2$ factor, and a mostly-$a_2$ trajectory carries a ratio near $0.2^{10}\approx 10^{-7}$. The variance of the product grows geometrically in $n$: a rare trajectory contributes a step roughly $357$ times the nominal size, and that single step dominates the average of thousands of ordinary ones.

The damage is done because these ratios multiply the step size in the SGD update: a large $\rho$ means a large step, which stochastic gradient descent cannot tolerate. SGD relies on averaging many small, noisy steps to estimate the true gradient; an occasional enormous step can move the parameter vector into a region of the space with a completely different gradient, and the averaging argument breaks. The obvious defense — shrinking the step size until no single step is dangerous — makes the expected step tiny and learning slow.

Five ideas for taming it

No single technique suffices, but several complementary strategies each reduce the variance.⁵

• Weighted importance sampling. Chapter 5 already showed that weighted importance sampling is far better behaved than the ordinary kind — its updates have much lower variance because the largest weight any sample can carry is bounded. The catch is that adapting weighted importance sampling to function approximation is genuinely hard, and can probably only be done approximately, at $O(d)$ cost.
• Avoiding ratios entirely. The tree-backup algorithm performs off-policy learning without any importance-sampling ratios at all, by backing up the expected value under the target policy rather than correcting sampled actions. Extending that idea to the function-approximation case yields stable and more efficient methods, since where there are no ratios there is no ratio-variance.
• Momentum and averaging. Because the trouble is occasional large, uncorrelated steps, optimizer machinery that smooths the update sequence helps directly: momentum, Polyak–Ruppert averaging (averaging the iterates rather than trusting the latest one), and their extensions all damp the effect of a single outlier step.
• Adaptive, per-component step sizes. Rather than one global step size limited by the worst-case ratio, methods that set a separate, adaptively-tuned step size for each component of the parameter vector — and importance-weight-aware updates designed with these products in mind — let the learning rate respond to the local variance instead of being throttled globally.
• Constraining the target toward the behavior. A complementary strategy defines the target policy partly by reference to the behavior policy, so that it can never differ enough to create huge ratios in the first place. Recognizer-style constructions cap how far $\pi$ may stray from $b$, trading a little generality for a lot of stability.

None of these is decisive on its own, and the chapter is candid that off-policy variance will probably always remain a challenge. Which of these methods combine effectively with the stable Gradient-TD and emphatic-TD updates is still an open question — the whole area is young. But the framing is what matters: stability and variance are separate problems. Gradient-TD and emphatic-TD solve the first; these techniques address the second; and a usable off-policy method under function approximation generally needs both.

The triad in deep reinforcement learning

Sutton and Barto present the triad as a theoretical hazard demonstrated on small linear problems. The obvious question — does it actually break the deep networks that now dominate practice? — was answered empirically after the second edition, and the answer is more nuanced than the theory alone suggests.

Van Hasselt, Doron, Strub, Hessel, Sonnerat, and Modayil (2018, Deep Reinforcement Learning and the Deadly Triad) ran a controlled study on the 57-game Atari suite, varying the ingredients of the triad in a deep Q-network and measuring how often the action-value estimates blew up.⁶ With rewards clipped to $[-1,1]$ and $\gamma =0.99$, the largest possible true action value is about $1/(1-\gamma )=100$; they flagged any estimate that exceeded roughly that bound as soft divergence. Their findings sharpen Sutton and Barto's picture on four points.

• Unbounded divergence is rare in practice. Soft divergence — estimates growing well past the reachable range — did occur, but the values essentially never ran off to infinity (floating-point NaN). The deep networks in current use apparently sit in a regime where the triad distorts the estimates without making them diverge, which is why DQN works at all despite carrying all three ingredients.
• Longer multi-step returns diverge less. Increasing the bootstrapping horizon (using $n$-step returns instead of one-step targets) reduced both the frequency of soft divergence and the number of unstable runs, and improved control performance. More of the target comes from real returns and less from the bootstrapped estimate, weakening the leg of the triad that drives instability.
• Correcting overestimation helps. Target networks and double Q-learning — which was designed to cut the maximization bias in the Q-learning target — were the most stable variants. Reducing overestimation and decoupling the bootstrap target from the weights being updated both damp the runaway feedback.
• Bigger networks are not automatically safer. The intuition that a higher-capacity approximator, closer to tabular, should be more stable did not hold: larger networks showed more soft divergence, even though they also reached the best final performance. Capacity and stability trade off rather than align.

These results reconcile the theory with practice. The triad's danger is real — van Hasselt's own linear controls still diverge to infinity — but the specific architecture of deep Q-learning (target networks, experience replay, clipped rewards, multi-step returns) keeps the deep case in the soft-divergence regime where learning, though sometimes unstable, does not explode.

On the theory side, two lines extend Sutton and Barto's stable methods. Sutton, Mahmood, and White (2016, An Emphatic Approach to the Problem of Off-policy Temporal-Difference Learning, JMLR) gave the emphatic-TD method of §11.8 its formal footing: they proved that emphasizing linear TD($\lambda$)'s updates by the emphasis weighting makes the expected update stable under off-policy training, with a single learned weight vector and a single step size — simpler than the two-time-scale Gradient-TD family, at the cost of the higher variance the lesson already flagged.⁷ More recently, Zhang, Yao, and Whiteson (2021, Breaking the Deadly Triad with a Target Network, ICML) proved that a target network — the same trick DQN uses heuristically — combined with a projection or ratio clipping yields a genuinely convergent off-policy prediction and control algorithm under linear approximation, turning DQN's empirical stabilizer into a method with a convergence guarantee.⁸ Together these results close much of the gap between Sutton and Barto's cautionary counterexamples and the systems that run in production: the triad is still dangerous, but there are now several principled ways to avoid its divergence.

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. Two responses restore stability without abandoning any leg of the triad: Gradient-TD methods, which do true SGD on the projected Bellman error at $O(d)$ cost, and emphatic-TD methods, which reweight updates back toward the on-policy distribution. Both remain relatively young and unsettled. The most consequential practical answer arrives later: deep Q-networks keep function approximation, bootstrapping, and off-policy replay all at once, and stabilize the triad empirically with a target network and a replay buffer rather than by giving anything up.