Baird's Counterexample

Seven states, zero rewards, linear values, yet off policy TD blows up. Three ingredients together break the contraction that keeps learning stable.

Seven weights start at norm 10.30 and grow past 22.04 at 100 steps and 3302.63 at 1000 steps though every reward is zero

Why Does This Exist?

Linear values feel safe. Squared error is a bowl, so gradient steps should roll downhill. Baird showed in 1995 that this intuition fails once three things combine: function approximation, bootstrapping, and off policy data. That trio is the deadly triad.

His 7-state star MDP has zero reward everywhere, discount $\gamma = 0.99$ , and a linear value $\hat{v}(s) = w^T x(s)$ that can fit the truth $w = 0$ exactly. Target policy always picks the solid move to the hub. Behavior mostly picks the dashed move that spreads across the rim. Semi-gradient TD with importance weights still explodes. This page covers the construction and the blow up. Neighbors cover the trio in the deadly triad, the sampling shift in off policy with approximation, and true gradient fixes in gradient TD.

You need TD learning first: update toward $R + \gamma \hat{v}(s')$ while ignoring how the target itself moves with $w$ .

Think of It Like This

A mic facing its own speaker

A whisper enters the mic, the amp adds a little gain, the speaker throws it back into the mic, and the loop repeats. Gain above one turns quiet into squeal even with no singer in the room.

Bootstrapped targets are the mic, semi-gradient pushes are the amp, and off policy sampling aims the speaker at the mic. Zero reward is the quiet room. It still squeals because the loop gain sits above one.

Where it stops: a real amp clips at voltage rails while these weights grow with no ceiling until floats overflow. The math also names the gain exactly through eigenvalues, which air acoustics never does.

How It Actually Works

Six rim states $s_1$ to $s_6$ plus hub $s_7$ . Solid action goes to $s_7$ . Dashed action lands uniform on the rim. All $R = 0$ . Features with $e_i$ as unit vectors:

x(s_i) = 2e_i + e_7, \quad \hat{v}(s_i) = 2w_i + w_7

x(s_7) = e_1 + 2e_7, \quad \hat{v}(s_7) = w_1 + 2w_7

Behavior picks dashed with $5/6$ and solid with $1/6$ . Dashed steps get importance ratio $\rho = 0$ and contribute nothing. Solid steps get $\rho = 6$ and update toward $\gamma \hat{v}(s_7)$ . In expectation the $6$ cancels the $1/6$ visit rate, leaving:

E[\Delta w] = -\alpha A w

for a fixed $7 \times 7$ matrix $A$ . On policy $A$ stays positive definite and pulls inward. Here $A$ has eigenvalues with negative real parts near $-0.5227$ and $-0.0040$ . Then $I - \alpha A$ has gain above one along that mode:

1 + 0.5227\alpha > 1

Each pass multiplies that component, so norms grow like $(1 + 0.5227\alpha)^k$ .

Worked example

Start $w_0 = [1, 1, 1, 1, 1, 1, 10]^T$ with $\alpha = 0.01$ . Norm:

\|w_0\| = \sqrt{6 \times 1^2 + 10^2} = \sqrt{106} \approx 10.2956

Expected semi-gradient steps push outward from the start:

\|w_1\| \approx 10.3804, \quad \|w_2\| \approx 10.4657, \quad \|w_3\| \approx 10.5517

The drift compounds. By $100$ steps norm is about $22.04$ , by $500$ about $269.47$ , by $1000$ about $3302.63$ . Zero rewards, small step, exact representation, yet infinity bound.

Code

Norm growth only, hand checkable without a full simulator.

1import numpy as np2
3
4def weight_norm(w: np.ndarray) -> float:5    """Euclidean norm of the 7-dim Baird weight vector."""6    return float(np.linalg.norm(w))7
8
9w0 = np.array([1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 10.0])10print(f"{weight_norm(w0):.4f}")  # -> 10.295611
12w1 = np.array([1.0241, 1.0244, 1.0244, 1.0244, 1.0244, 1.0244, 10.0726])13print(f"{weight_norm(w1):.4f}")  # -> 10.3804

First print is $\sqrt{106}$ . Second matches the one step expected update quoted above.

Watch Out For

Blaming nonlinearity or reward scale

It is tempting to blame ReLUs or big rewards when values explode. Baird rules both out: linear model, zero rewards, tiny step.

Symptom: clipping gradients or rescaling rewards changes nothing. Fix: break the triad. Go on policy, switch to true gradient TD such as GTD2 or TDC, or reweight with emphatic traces. Check sampling and bootstrapping before touching the network.

The Quick Version

Baird's 7-state star uses zero rewards and linear features that can fit truth exactly.
Off policy ratios plus bootstrapping make matrix $A$ indefinite, with modes near $-0.5227$ .
Update gain $1 + 0.5227\alpha$ exceeds one, so weights multiply outward each pass.
Norms run $10.30$ to $22.04$ at 100 steps to $3302.63$ at 1000 steps.
Fix by removing one leg: on policy data, true gradients, or emphatic weighting.