Gradient-TD Methods (TDC & GTD2)

Gradient TD methods pair the usual value weights with a fast helper vector, so off policy updates with function approximation descend a real error instead of spiraling out of control.

Gradient TD splits learning into fast helper weights that track the projection and slow value weights that descend the projected Bellman error

Why Does This Exist?

Three ingredients together break ordinary temporal difference learning: function approximation, bootstrapping, and off policy data. This trio is called the deadly triad, and under it plain TD can diverge with weights running to infinity. Baird's counterexample shows it on seven states with zero reward everywhere: there is nothing to learn, yet the weights explode.

The natural fix looks easy but hides a trap. Minimizing the Bellman error directly needs two independent next states from the same spot to get an unbiased sample gradient, which online learning cannot provide. That is the double sampling problem. Gradient TD methods, GTD2 and TDC from Sutton and coauthors in 2009, dodge it with a second weight vector that learns fast and carries the missing piece, so the main weights descend the mean squared projected Bellman error in linear time. For the trio itself, read the deadly triad first.

The one idea you need first

The TD error delta measures surprise on one step: reward plus discounted next estimate minus current estimate. With reward 1.0, discount 0.9, next value 1.0 and current value 2.0, the error is 1.0 + 0.9 - 2.0 = -0.1. Off policy steps scale this by the importance ratio rho, the target policy chance over the behavior policy chance.

Think of It Like This

A crane operator with a fast spotter

A crane swings a heavy load while the wind gusts from the side. If the operator steers only from the load's current position, each correction arrives late and the swing grows until something snaps. That is plain TD under the triad.

So the crew adds a spotter with a light flag who reacts in a blink. The spotter does not move the load; they track the wind's push moment by moment. The operator watches the flag and moves the crane slowly against the reported push. Fast sensing plus slow muscle turns an unstable loop into a stable one.

Where it stops: the spotter feels real wind, while the helper vector solves a least squares projection between two expectations. And if the spotter reacts slower than the crane, the whole scheme fails, which is exactly the timescale rule below.

How It Actually Works

Values are linear in features: estimate equals weights dot features, vhat = w . x. The projected Bellman error, MSPBE, measures the gap between the current estimate and the Bellman target after projecting that target back into what the features can express. In matrix shorthand with A for the transition structure, b for rewards, and C for feature covariance:

MSPBE(w) = (b - A w)^T C^{-1} (b - A w)

Its gradient needs a product of two expectations, which one sample cannot supply without bias. The trick is a helper vector u that tracks C^{-1}(b - A w) through plain least squares on a fast step size beta:

u_{new} = u + \beta \, (\rho \, \delta - x^T u) \, x

With u in hand, the slow weights w step on size alpha. GTD2 follows the product form directly. TDC, the version most people use, keeps the familiar TD piece and subtracts a correction:

w_{new} = w + \alpha \, \rho \, \delta \, x - \alpha \, \gamma \, \rho \, x_{next} \, (x^T u)

The first term is ordinary off policy TD. The second term is the guardrail that pulls the update back onto the true descent direction. Convergence needs beta well above alpha, classically five to ten times larger, so u always looks settled from the slow weights' viewpoint.

Worked example

One TDC step with discount gamma = 0.9, slow rate alpha = 0.1, fast rate beta = 0.5, and ratio rho = 1.5. Current weights w = [1.0, 0.5], helper u = [0.4, 0.1], features x = [1.0, 2.0], next features [0.5, 1.0], reward 1.0.

Step one, values and error: current value 1.0 * 1.0 + 0.5 * 2.0 = 2.0, next value 1.0 * 0.5 + 0.5 * 1.0 = 1.0, so delta = 1.0 + 0.9 * 1.0 - 2.0 = -0.1 and rho * delta = -0.15.

Step two, the helper projection: x . u = 1.0 * 0.4 + 2.0 * 0.1 = 0.60. The residual is -0.15 - 0.60 = -0.75, giving u = [0.4, 0.1] + 0.5 * (-0.75) * [1.0, 2.0] = [0.025, -0.650].

Step three, the slow weights: the TD piece is 0.1 * (-0.15) * [1.0, 2.0] = [-0.015, -0.030], and the correction is -0.1 * 0.9 * 1.5 * [0.5, 1.0] * 0.60 = [-0.0405, -0.0810]. Added together, w = [1.0, 0.5] + [-0.015, -0.030] + [-0.0405, -0.0810] = [0.9445, 0.3890]. Both vectors stay bounded, with the correction doing visible work.

Code

This snippet replays the worked step with plain Python, printing the same error, helper, and weights derived by hand.

1w = [1.0, 0.5]2u = [0.4, 0.1]3x = [1.0, 2.0]4x_next = [0.5, 1.0]5reward, gamma, rho, alpha, beta = 1.0, 0.9, 1.5, 0.1, 0.56
7cur = w[0] * x[0] + w[1] * x[1]8nxt = w[0] * x_next[0] + w[1] * x_next[1]9delta = reward + gamma * nxt - cur10rhod = rho * delta11proj = x[0] * u[0] + x[1] * u[1]12u = [ui + beta * (rhod - proj) * xi for ui, xi in zip(u, x)]13w = [wi + alpha * rhod * xi - alpha * gamma * rho * xni * proj for wi, xi, xni in zip(w, x, x_next)]14print(f"{delta:.4f} {rhod:.4f} {proj:.4f}")  # -> -0.1000 -0.1500 0.600015print([f"{v:.4f}" for v in u])  # -> ['0.0250', '-0.6500']16print([f"{v:.4f}" for v in w])  # -> ['0.9445', '0.3890']

Every print matches the hand pass: error -0.1000, helper [0.0250, -0.6500], weights [0.9445, 0.3890].

Watch Out For

Running the helper at the same speed as the weights

The helper must adapt much faster than the main weights, or its estimate of the projection goes stale and the correction points the wrong way. TDC then diverges much like the plain TD it was meant to replace.

Symptom: bounded learning for a while, then growing oscillations in w that shrinking alpha alone does not cure. Fix: keep beta at least five to ten times alpha, for example alpha = 0.005 with beta = 0.05, and never invert the covariance matrix directly since the helper recursion already does that job in linear time.

Expecting gradient TD to fix bad features

Convergence is not accuracy. MSPBE conserves whatever the features can express, so with weak features TDC converges confidently to a poor value, and the helper happily tracks that poor projection.

Symptom: stable weights plus stubbornly wrong predictions on held out states. Fix: improve features first, using linear methods as the checklist, and compare against emphatic TD when the state weighting itself looks wrong.

The Quick Version

The deadly triad of approximation plus bootstrapping plus off policy data makes plain TD diverge, as Baird's zero reward demo proves.
GTD2 and TDC descend the projected Bellman error instead, which stays inside what the features can express.
A fast helper vector tracks the projection piece, dodging the double sampling trap in linear time per step.
TDC pairs a familiar TD step with a correction term; the worked step landed at helper [0.025, -0.650] and weights [0.9445, 0.3890].
Keep the helper five to ten times faster than the weights, or the guardrail fails.
Start with the deadly triad, see the divergence in Baird's counterexample, and compare emphatic TD methods as the one vector alternative.