Baird's Counterexample

Why Does This Exist?

In the early history of reinforcement learning, researchers believed that linear function approximation was inherently safe. Because the Mean Squared Value Error objective $\overline{\text{VE}}(\mathbf{w})$ is a strictly convex quadratic bowl with a unique global optimum, intuition suggested that linear TD methods could never diverge.

In 1995, Leemon Baird shattered this assumption by constructing an ingeniously simple 7-state Markov Decision Process. Baird proved that even with:

1. A simple linear value function $\hat{v}(s, \mathbf{w}) = \mathbf{w}^\top \mathbf{x}(s)$,
2. A deterministic transition model where every single reward is zero ($R = 0$), and
3. An infinitesimal step size $\alpha > 0$,

standard semi-gradient Temporal Difference learning diverges exponentially to infinity ($\|\mathbf{w}_t\| \to \infty$).

Baird's counterexample is historically famous because it provides the concrete mathematical proof of the Deadly Triad: the dangerous confluence of Function Approximation, Bootstrapping, and Off-Policy Learning. Whenever all three conditions coincide, semi-gradient updates cease to be a contraction mapping, causing value estimates to destabilize and self-amplify without bound.

Think of It Like This

How It Actually Works

The 7-State Star MDP Specification

Baird's counterexample consists of seven states $\mathcal{S} = \{s_1, s_2, s_3, s_4, s_5, s_6, s_7\}$ and two actions:

• Upper states: Six satellite states $s_1, s_2, \dots, s_6$.
• Lower state: One central hub state $s_7$.

The MDP has two actions available in every state:

1. Solid Action: Deterministically transitions the agent to the lower state $s_7$.
2. Dashed Action: Transitions the agent uniformly to one of the six upper states $\{s_1, \dots, s_6\}$, each with probability $\frac{1}{6}$.

Every transition in the environment yields a reward of zero: $R_{t+1} = 0 \quad \forall s, a$ The discount factor is set near unity: $\gamma = 0.99$.

Target Policy vs. Behavior Policy (Off-Policy Setting)

• Target Policy $\pi$: Deterministically chooses the solid action ($\pi(\text{solid} \mid s) = 1.0$). Under $\pi$, the agent always transitions to $s_7$.
• Behavior Policy $b$: Chooses the dashed action with probability $\frac{5}{6}$ and the solid action with probability $\frac{1}{6}$: $b(\text{dashed} \mid s) = \frac{5}{6}, \quad b(\text{solid} \mid s) = \frac{1}{6}$

Because the behavior policy's transitions are independent of the current state, the stationary state distribution under $b$ is: $\mu(s_i) = \frac{5}{6} \times \frac{1}{6} = \frac{5}{36} \quad (i = 1 \dots 6), \quad \mu(s_7) = \frac{1}{6} = \frac{6}{36}$

Linear Feature Parameterization

The value function is represented linearly with seven parameters $\mathbf{w} = [w_1, w_2, \dots, w_7]^\top \in \mathbb{R}^7$:

• For upper states $s_1 \dots s_6$: $\mathbf{x}(s_i) = 2 \mathbf{e}_i + \mathbf{e}_7 \implies \hat{v}(s_i, \mathbf{w}) = 2 w_i + w_7 \quad (i = 1 \dots 6)$
• For the lower state $s_7$: $\mathbf{x}(s_7) = \mathbf{e}_1 + 2 \mathbf{e}_7 \implies \hat{v}(s_7, \mathbf{w}) = w_1 + 2 w_7$

Notice that the true value of every state under target policy $\pi$ is exactly zero ($v_\pi(s) = 0$), which is perfectly representable by setting $\mathbf{w}^* = \mathbf{0}$.

The Deadly Triad and Analytical Divergence

When training semi-gradient TD(0) off-policy with importance sampling ratio $\rho_t = \frac{\pi(A_t \mid S_t)}{b(A_t \mid S_t)}$:

• When the behavior policy selects the dashed action: $\rho_t = \frac{\pi(\text{dashed})}{b(\text{dashed})} = \frac{0}{5/6} = 0 \implies \Delta \mathbf{w} = \mathbf{0}$
• When the behavior policy selects the solid action (probability $\frac{1}{6}$): $\rho_t = \frac{\pi(\text{solid})}{b(\text{solid})} = \frac{1}{1/6} = 6$ The next state is guaranteed to be $s_7$, with reward $R = 0$. The semi-gradient update for state $S_t = s$ is: $\Delta \mathbf{w} = \alpha \rho_t \left[ 0 + \gamma \hat{v}(s_7, \mathbf{w}) - \hat{v}(s, \mathbf{w}) \right] \mathbf{x}(s)$

Taking the expectation over the behavior distribution $\mu(s)$, the factor of $6$ in $\rho_t$ exactly cancels the probability $\frac{1}{6}$:

$\mathbb{E}[\Delta \mathbf{w}] = \alpha \sum_{s=1}^7 \mu(s) \left[ \gamma \mathbf{w}^\top \mathbf{x}(s_7) - \mathbf{w}^\top \mathbf{x}(s) \right] \mathbf{x}(s) = -\alpha \mathbf{A} \mathbf{w}$

where the expected key transition matrix $\mathbf{A} \in \mathbb{R}^{7 \times 7}$ is:

$\mathbf{A} = \sum_{s=1}^7 \mu(s) \mathbf{x}(s) \left( \mathbf{x}(s) - \gamma \mathbf{x}(s_7) \right)^\top$

The Eigenvalue Instability of the TD Operator

In stable on-policy linear TD, the matrix $\mathbf{A}$ is guaranteed to be positive definite (all eigenvalues have positive real parts), meaning $-\alpha \mathbf{A}$ pulls weights inward toward the origin like a damped spring.

In Baird's counterexample, computing the eigenvalues of $\mathbf{A}$ reveals that two eigenvalues have negative real parts: $\text{Re}(\lambda_1) \approx -0.5227, \quad \text{Re}(\lambda_2) \approx -0.0040$

In the discrete update equation: $\mathbf{w}_{k+1} = (\mathbf{I} - \alpha \mathbf{A}) \mathbf{w}_k$ any eigenvector associated with a negative eigenvalue of $\mathbf{A}$ corresponds to an eigenvalue of $(\mathbf{I} - \alpha \mathbf{A})$ strictly greater than 1: $1 - \alpha (-0.5227) = 1 + 0.5227 \alpha > 1$

At every iteration, the projection along this unstable eigenvector is multiplied by a factor strictly greater than one, generating an exponential explosion: $\|\mathbf{w}_k\| \propto (1 + 0.5227 \alpha)^k \xrightarrow{k \to \infty} \infty$

Worked numerical example

Let initial weights be: $\mathbf{w}_0 = \begin{bmatrix} 1.0, & 1.0, & 1.0, & 1.0, & 1.0, & 1.0, & 10.0 \end{bmatrix}^\top, \quad \alpha = 0.01, \quad \gamma = 0.99$ Initial weight vector norm: $\|\mathbf{w}_0\| = \sqrt{6(1.0^2) + 10.0^2} = \sqrt{106} \approx \mathbf{10.2956}$

Step 1: First Expected Update

Multiplying by the expected transition matrix $\mathbf{A}$: $\Delta \mathbf{w}_0 = -\alpha \mathbf{A} \mathbf{w}_0 = \begin{bmatrix} +0.0241, & +0.0244, & +0.0244, & +0.0244, & +0.0244, & +0.0244, & +0.0726 \end{bmatrix}^\top$

New weight vector: $\mathbf{w}_1 = \mathbf{w}_0 + \Delta \mathbf{w}_0 = \begin{bmatrix} 1.0241, & 1.0244, & 1.0244, & 1.0244, & 1.0244, & 1.0244, & 10.0726 \end{bmatrix}^\top$ $\|\mathbf{w}_1\| \approx \mathbf{10.3804} \quad (> 10.2956)$

Step 2: Second Expected Update

$\mathbf{w}_2 = \begin{bmatrix} 1.0483, & 1.0490, & 1.0490, & 1.0490, & 1.0490, & 1.0490, & 10.1455 \end{bmatrix}^\top$ $\|\mathbf{w}_2\| \approx \mathbf{10.4657} \quad (> 10.3804)$

Step 3: Third Expected Update

$\mathbf{w}_3 = \begin{bmatrix} 1.0726, & 1.0736, & 1.0736, & 1.0736, & 1.0736, & 1.0736, & 10.2188 \end{bmatrix}^\top$ $\|\mathbf{w}_3\| \approx \mathbf{10.5517} \quad (> 10.4657)$

Long-Term Trajectory

By step 1,000, the weight norm reaches $\|\mathbf{w}_{1000}\| \approx \mathbf{3,302.63}$. By step 2,000, it surpasses $1.2 \times 10^6$. The weights diverge exponentially toward infinity without ever stabilizing.

Code

1from typing import List, Tuple2import numpy as np3
4
5def build_bairds_counterexample() -> (6    Tuple[np.ndarray, np.ndarray, np.ndarray]7):8    """Construct the feature matrix X, stationary distribution mu, and matrix A for Baird's 7-state MDP."""9    # 7 states x 7 features10    num_states = 711    num_features = 712    gamma = 0.9913
14    X = np.zeros((num_states, num_features))15    # Upper states s_1 .. s_6: 2 * e_i + e_716    for i in range(6):17        X[i, i] = 2.018        X[i, 6] = 1.019    # Lower state s_7: e_1 + 2 * e_720    X[6, 0] = 1.021    X[6, 6] = 2.022
23    # Stationary distribution under behavior policy b:24    # 5/6 chance of dashed action (uniformly transitions to s_1..s_6 with 1/6 each)25    # 1/6 chance of solid action (transitions to s_7)26    mu = np.array([5.0 / 36.0] * 6 + [6.0 / 36.0])27
28    # Transition matrix A: E_b [ rho_t * x_t * (x_t - gamma * x_{t+1})^T ]29    # Solid action is taken under b with prob 1/6, with importance ratio rho = 6.30    # Solid action always leads to s_7.31    x_7 = X[6]32    A = np.zeros((num_features, num_features))33    for s in range(num_states):34        A += mu[s] * np.outer(X[s], X[s] - gamma * x_7)35
36    return X, mu, A37
38
39def simulate_bairds_divergence(40    alpha: float = 0.01, num_steps: int = 100041) -> Tuple[List[float], np.ndarray]:42    """Run expected semi-gradient TD updates on Baird's counterexample."""43    _, _, A = build_bairds_counterexample()44
45    # Initial weights: w_0 = [1, 1, 1, 1, 1, 1, 10]^T46    w = np.array([1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 10.0])47    norms: List[float] = [float(np.linalg.norm(w))]48
49    for _ in range(num_steps):50        # Semi-gradient expected update: w_{k+1} = w_k - alpha * A @ w_k51        w = w - alpha * (A @ w)52        norms.append(float(np.linalg.norm(w)))53
54    return norms, w55
56
57if __name__ == "__main__":58    X, mu, A = build_bairds_counterexample()59    eigenvalues = np.linalg.eigvals(A)60
61    print("=== Baird's Counterexample Matrix Analysis ===")62    print("Real parts of eigenvalues of transition matrix A:")63    for ev in np.real(eigenvalues):64        print(f"  lambda_Re = {ev:+.6f}")65
66    # Check for negative eigenvalues (proof of instability)67    has_negative_ev = any(np.real(ev) < -1e-4 for ev in eigenvalues)68    assert (69        has_negative_ev70    ), "Matrix A must possess negative eigenvalues for divergence!"71    print(72        f"\nInstability verified: Matrix A has negative eigenvalues (e.g. {min(np.real(eigenvalues)):.4f})."73    )74
75    # Simulate 1000 steps of expected semi-gradient updates76    norms, final_w = simulate_bairds_divergence(alpha=0.01, num_steps=1000)77
78    print("\n=== Exponential Weight Divergence ===")79    print(f"Initial Weight Norm ||w_0||:     {norms[0]:.4f}")80    print(f"Norm after 100 steps ||w_100||:   {norms[100]:.4f}")81    print(f"Norm after 500 steps ||w_500||:   {norms[500]:.4f}")82    print(f"Norm after 1000 steps ||w_1000||: {norms[1000]:.4f}")83
84    # Assert that weights diverge by orders of magnitude85    assert (86        norms[1000] > norms[0] * 100.087    ), "Weights must explode by over 100x!"88    print(89        f"\nVerification passed: Weight norm grew by {norms[1000] / norms[0]:.1f}x across 1,000 steps."90    )91
92# Expected Output:93# === Baird's Counterexample Matrix Analysis ===94# Real parts of eigenvalues of transition matrix A:95#   lambda_Re = +0.55449096#   lambda_Re = -0.00399397#   lambda_Re = -0.52271998#   lambda_Re = +0.55555699#   lambda_Re = +0.555556100#   lambda_Re = +0.555556101#   lambda_Re = +0.555556102#103# Instability verified: Matrix A has negative eigenvalues (e.g. -0.5227).104#105# === Exponential Weight Divergence ===106# Initial Weight Norm ||w_0||:     10.2956107# Norm after 100 steps ||w_100||:   22.0383108# Norm after 500 steps ||w_500||:   269.4678109# Norm after 1000 steps ||w_1000||: 3302.6332110#111# Verification passed: Weight norm grew by 320.8x across 1,000 steps.

Watch Out For

The Quick Version

• The classic proof of divergence: Leemon Baird's 1995 7-state star MDP proves that linear semi-gradient TD can diverge to infinity when updating off-policy.
• Zero rewards cannot save you: Even when every reward is $0$ and the true value of every state is $0$, weights explode exponentially ($\|\mathbf{w}\| \to \infty$) due to unstable operator eigenvalues.
• The Deadly Triad: Instability arises whenever Function Approximation, Bootstrapping, and Off-Policy Training intersect simultaneously.
• The algorithmic remedies: Stability is restored by either eliminating off-policy training, applying true-gradient methods (GTD2/TDC), or reweighting transitions via Emphatic TD.

What to Read Next

• The Deadly Triad
• Off-Policy Learning with Approximation
• Gradient-TD Methods (TDC & GTD2)