Gradient-TD Methods (TDC & GTD2)

Why Does This Exist?

In reinforcement learning, the combination of three elements forms the notorious Deadly Triad:

1. Function approximation (linear features or neural networks instead of tabular lookups)
2. Bootstrapping (updating value estimates toward downstream value estimates rather than full Monte Carlo returns)
3. Off-policy learning (evaluating or optimizing a target policy $\pi$ while observing transitions generated by an exploratory behavior policy $b$)

When all three conditions hold simultaneously, standard semi-gradient Temporal Difference methods like TD(0) and Q-learning can diverge to infinity. Under an off-policy distribution $\mu_b$, the transition operator $P^\pi$ is no longer a contraction mapping with respect to the state distribution weighting matrix $\mathbf{D}$. As a result, semi-gradient TD updates do not follow the true negative gradient of any objective function. The underlying expected update matrix $\mathbf{A} = \mathbb{E}[\mathbf{x}_t (\mathbf{x}_t - \gamma \mathbf{x}_{t+1})^\top]$ can have eigenvalues with negative real parts, causing value weights to explode exponentially—as vividly demonstrated by Baird's counterexample.

Early attempts to fix this divergence attempted to minimize the Mean Squared Bellman Error ($\text{MSBE}$). However, the true gradient of $\text{MSBE}$ contains a product of expectations, creating the notorious double-sampling problem: computing an unbiased sample gradient requires observing two independent next states $s'$ from the exact same state-action pair, which is impossible in model-free online learning.

Gradient-TD methods (specifically GTD2 and TDC / TD with Gradient Correction, introduced by Sutton, Maei, Precup, and Szepesvári in 2009) resolve this fundamental impasse. They define an objective function called the Mean Squared Projected Bellman Error ($\text{MSPBE}$), which projects the Bellman error back onto the linear feature subspace. By introducing a secondary, fast-moving weight vector $\mathbf{u} \in \mathbb{R}^d$, Gradient-TD decomposes the sample gradient into two coupled recursions operating on different timescales. This circumvents double-sampling and guarantees true stochastic gradient descent in $\mathcal{O}(d)$ time and space per time step.

Think of It Like This

How It Actually Works

The MSPBE Objective and the Double-Sampling Problem

Let state values be approximated by a linear combination of feature vectors: $V_{\mathbf{w}}(s) = \mathbf{w}^\top \mathbf{x}(s)$

In vector-matrix form, let $\mathbf{\Phi} \in \mathbb{R}^{|\mathcal{S}| \times d}$ be the feature matrix, and $\mathbf{D} \in \mathbb{R}^{|\mathcal{S}| \times |\mathcal{S}|}$ be a diagonal matrix of state visitation probabilities under the behavior policy $b$, where $D_{ss} = d_b(s)$. The weighted projection operator $\Pi$ that projects any value function onto the subspace spanned by $\mathbf{\Phi}$ is: $\Pi = \mathbf{\Phi} (\mathbf{\Phi}^\top \mathbf{D} \mathbf{\Phi})^{-1} \mathbf{\Phi}^\top \mathbf{D}$

The Bellman operator for target policy $\pi$ is $T^\pi V = \mathbf{r}^\pi + \gamma \mathbf{P}^\pi V$. Under off-policy sampling, the Bellman error $T^\pi V_{\mathbf{w}} - V_{\mathbf{w}}$ does not lie in the column space of $\mathbf{\Phi}$. Gradient-TD methods minimize the Mean Squared Projected Bellman Error ($\text{MSPBE}$): $\text{MSPBE}(\mathbf{w}) = \|\Pi T^\pi V_{\mathbf{w}} - V_{\mathbf{w}}\|_{\mathbf{D}}^2 = (T^\pi V_{\mathbf{w}} - V_{\mathbf{w}})^\top \mathbf{D} \mathbf{\Phi} (\mathbf{\Phi}^\top \mathbf{D} \mathbf{\Phi})^{-1} \mathbf{\Phi}^\top \mathbf{D} (T^\pi V_{\mathbf{w}} - V_{\mathbf{w}})$

Defining: $\mathbf{A} \triangleq \mathbb{E}_{b}\left[\rho_t \mathbf{x}_t (\mathbf{x}_t - \gamma \mathbf{x}_{t+1})^\top\right] = \mathbf{\Phi}^\top \mathbf{D} (\mathbf{I} - \gamma \mathbf{P}^\pi) \mathbf{\Phi}$ $\mathbf{b} \triangleq \mathbb{E}_{b}\left[\rho_t R_{t+1} \mathbf{x}_t\right] = \mathbf{\Phi}^\top \mathbf{D} \mathbf{r}^\pi$ $\mathbf{C} \triangleq \mathbb{E}_{b}\left[\mathbf{x}_t \mathbf{x}_t^\top\right] = \mathbf{\Phi}^\top \mathbf{D} \mathbf{\Phi}$

where $\rho_t = \frac{\pi(A_t \mid S_t)}{b(A_t \mid S_t)}$ is the importance sampling ratio. The MSPBE reduces to the quadratic form: $\text{MSPBE}(\mathbf{w}) = (\mathbf{b} - \mathbf{A}\mathbf{w})^\top \mathbf{C}^{-1} (\mathbf{b} - \mathbf{A}\mathbf{w})$

The gradient with respect to $\mathbf{w}$ is: $-\frac{1}{2} \nabla_{\mathbf{w}} \text{MSPBE}(\mathbf{w}) = \mathbf{A}^\top \mathbf{C}^{-1} (\mathbf{b} - \mathbf{A}\mathbf{w})$

Notice that $\mathbf{b} - \mathbf{A}\mathbf{w} = \mathbb{E}_b[\rho_t \delta_t \mathbf{x}_t]$, where $\delta_t = R_{t+1} + \gamma \mathbf{w}_t^\top \mathbf{x}_{t+1} - \mathbf{w}_t^\top \mathbf{x}_t$ is the standard TD error. The expression for the gradient involves a product of three matrix/vector terms: $\nabla_{\mathbf{w}} \text{MSPBE}(\mathbf{w}) = -2 \, \mathbb{E}\left[\rho_t (\mathbf{x}_t - \gamma \mathbf{x}_{t+1}) \mathbf{x}_t^\top\right] \mathbf{C}^{-1} \mathbb{E}\left[\rho_t \delta_t \mathbf{x}_t\right]$

Because the expected value of a product of dependent random variables is not the product of their expected values ($\mathbb{E}[X Y] \neq \mathbb{E}[X] \mathbb{E}[Y]$), naive sampling yields a biased gradient unless two independent transitions are drawn from the same state.

The Two-Timescale Stochastic Approximation Solution

To avoid double sampling and matrix inversion ($\mathcal{O}(d^3)$), Sutton et al. introduced an auxiliary parameter vector $\mathbf{u} \in \mathbb{R}^d$ that estimates: $\mathbf{u} \approx \mathbf{C}^{-1} (\mathbf{b} - \mathbf{A}\mathbf{w})$

Multiplying both sides by $\mathbf{C}$ gives $\mathbf{C} \mathbf{u} = \mathbf{b} - \mathbf{A}\mathbf{w}$, which is equivalent to finding $\mathbf{u}$ that minimizes the quadratic loss $\mathbb{E}[(\rho_t \delta_t - \mathbf{x}_t^\top \mathbf{u})^2]$. This is a standard linear regression problem that can be updated incrementally via Least Mean Squares (LMS) on a fast timescale step-size $\beta_t$: $\mathbf{u}_{t+1} = \mathbf{u}_t + \beta_t \left(\rho_t \delta_t - \mathbf{x}_t^\top \mathbf{u}_t\right) \mathbf{x}_t$

Given this estimate $\mathbf{u}_t$, the algorithms update the primary weights $\mathbf{w}$ along the slow timescale step-size $\alpha_t$:

1. GTD2 (Gradient TD 2): Using $\mathbf{A}^\top \mathbf{u} = \mathbb{E}[\rho_t (\mathbf{x}_t - \gamma \mathbf{x}_{t+1}) \mathbf{x}_t^\top] \mathbf{u} = \mathbb{E}[\rho_t (\mathbf{x}_t - \gamma \mathbf{x}_{t+1}) (\mathbf{x}_t^\top \mathbf{u})]$: $\mathbf{w}_{t+1} = \mathbf{w}_t + \alpha_t \rho_t \left(\mathbf{x}_t - \gamma \mathbf{x}_{t+1}\right) \left(\mathbf{x}_t^\top \mathbf{u}_t\right)$

2. TDC (TD with Gradient Correction): TDC decomposes $\mathbf{A}^\top = (\mathbf{C} - \gamma \mathbb{E}[\rho_t \mathbf{x}_t \mathbf{x}_{t+1}^\top])^\top = \mathbf{C} - \gamma \mathbb{E}[\rho_t \mathbf{x}_{t+1} \mathbf{x}_t^\top]$. Substituting $\mathbf{C}\mathbf{u} \approx \mathbb{E}[\rho_t \delta_t \mathbf{x}_t]$: $\mathbf{A}^\top \mathbf{u} = \mathbb{E}\left[\rho_t \delta_t \mathbf{x}_t\right] - \gamma \mathbb{E}\left[\rho_t \mathbf{x}_{t+1} (\mathbf{x}_t^\top \mathbf{u})\right]$ Sampling this expression gives the TDC weight update: $\mathbf{w}_{t+1} = \mathbf{w}_t + \alpha_t \rho_t \delta_t \mathbf{x}_t - \alpha_t \gamma \rho_t \mathbf{x}_{t+1} \left(\mathbf{x}_t^\top \mathbf{u}_t\right)$

TDC is generally preferred in practice: its first term is identical to standard semi-gradient TD, while the second term acts as a corrective counterforce that prevents divergence when off-policy dynamics push eigenvalues into the unstable right half-plane.

For convergence, the step sizes must satisfy the standard Robbins-Monro conditions alongside the crucial two-timescale ratio: $\sum_{t=0}^\infty \alpha_t = \infty, \quad \sum_{t=0}^\infty \beta_t = \infty, \quad \sum_{t=0}^\infty \alpha_t^2 < \infty, \quad \sum_{t=0}^\infty \beta_t^2 < \infty, \quad \lim_{t \to \infty} \frac{\alpha_t}{\beta_t} = 0$

Under these conditions, $\mathbf{u}_t$ converges to its quasi-stationary target $\mathbf{C}^{-1}(\mathbf{b} - \mathbf{A}\mathbf{w}_t)$ as if $\mathbf{w}_t$ were stationary, while $\mathbf{w}_t$ tracks the true descent direction of the MSPBE.

Worked numerical example

Let us trace a single TDC update step on a 2-dimensional linear feature system with the following parameters:

• Discount factor: $\gamma = 0.9$
• Slow learning rate: $\alpha = 0.1$
• Fast learning rate: $\beta = 0.5$
• Importance sampling ratio: $\rho_t = 1.5$
• Current weights: $\mathbf{w}_t = \begin{bmatrix} 1.0 \\ 0.5 \end{bmatrix}$
• Auxiliary weights: $\mathbf{u}_t = \begin{bmatrix} 0.4 \\ 0.1 \end{bmatrix}$
• Current features: $\mathbf{x}_t = \begin{bmatrix} 1.0 \\ 2.0 \end{bmatrix}$
• Next features: $\mathbf{x}_{t+1} = \begin{bmatrix} 0.5 \\ 1.0 \end{bmatrix}$
• Observed reward: $R_{t+1} = 1.0$

Step 1: Compute value estimates and TD error

Compute state values: $V(S_t) = \mathbf{w}_t^\top \mathbf{x}_t = (1.0 \times 1.0) + (0.5 \times 2.0) = 1.0 + 1.0 = 2.0$ $V(S_{t+1}) = \mathbf{w}_t^\top \mathbf{x}_{t+1} = (1.0 \times 0.5) + (0.5 \times 1.0) = 0.5 + 0.5 = 1.0$

Compute the TD error $\delta_t$: $\delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t) = 1.0 + (0.9 \times 1.0) - 2.0 = 1.9 - 2.0 = -0.1$

Compute the importance-weighted TD error: $\rho_t \delta_t = 1.5 \times (-0.1) = -0.15$

Step 2: Evaluate the auxiliary projection

Compute the inner product of current features with auxiliary weights: $\mathbf{x}_t^\top \mathbf{u}_t = (1.0 \times 0.4) + (2.0 \times 0.1) = 0.4 + 0.2 = 0.60$

Step 3: Fast-timescale update of auxiliary weights $\mathbf{u}_{t+1}$

The auxiliary residual is: $\rho_t \delta_t - \mathbf{x}_t^\top \mathbf{u}_t = -0.15 - 0.60 = -0.75$

Update $\mathbf{u}$: $\mathbf{u}_{t+1} = \mathbf{u}_t + \beta \left(\rho_t \delta_t - \mathbf{x}_t^\top \mathbf{u}_t\right) \mathbf{x}_t$ $\mathbf{u}_{t+1} = \begin{bmatrix} 0.4 \\ 0.1 \end{bmatrix} + 0.5 \times (-0.75) \times \begin{bmatrix} 1.0 \\ 2.0 \end{bmatrix} = \begin{bmatrix} 0.4 \\ 0.1 \end{bmatrix} - \begin{bmatrix} 0.375 \\ 0.750 \end{bmatrix} = \begin{bmatrix} 0.025 \\ -0.650 \end{bmatrix}$

Step 4: Slow-timescale update of main weights $\mathbf{w}_{t+1}$

The TDC weight update consists of two components:

1. Standard semi-gradient TD step: $\Delta \mathbf{w}_{\text{TD}} = \alpha \rho_t \delta_t \mathbf{x}_t = 0.1 \times (-0.15) \times \begin{bmatrix} 1.0 \\ 2.0 \end{bmatrix} = \begin{bmatrix} -0.015 \\ -0.030 \end{bmatrix}$

2. Gradient correction step: $\Delta \mathbf{w}_{\text{corr}} = -\alpha \gamma \rho_t \mathbf{x}_{t+1} (\mathbf{x}_t^\top \mathbf{u}_t) = -0.1 \times 0.9 \times 1.5 \times \begin{bmatrix} 0.5 \\ 1.0 \end{bmatrix} \times 0.60 = -0.081 \times \begin{bmatrix} 0.5 \\ 1.0 \end{bmatrix} = \begin{bmatrix} -0.0405 \\ -0.0810 \end{bmatrix}$

Combine the components: $\mathbf{w}_{t+1} = \mathbf{w}_t + \Delta \mathbf{w}_{\text{TD}} + \Delta \mathbf{w}_{\text{corr}} = \begin{bmatrix} 1.0 \\ 0.5 \end{bmatrix} + \begin{bmatrix} -0.015 \\ -0.030 \end{bmatrix} + \begin{bmatrix} -0.0405 \\ -0.0810 \end{bmatrix} = \begin{bmatrix} 0.9445 \\ 0.3890 \end{bmatrix}$

Both weight vectors remain bounded, with the correction term actively pulling $\mathbf{w}$ toward the true gradient of the MSPBE.

Code

The following self-contained Python script benchmarks Standard Off-Policy Semi-Gradient TD(0) against TDC on Baird's 7-State Counterexample—the canonical benchmark where off-policy TD(0) diverges to infinity:

1"""Comparison of Semi-Gradient TD(0) vs TDC on Baird's Counterexample.2
3Baird's counterexample features 7 states and 8 features.4Target policy pi: always chooses the 'solid' action leading to state 6.5Behavior policy b: chooses the 'dashed' action (states 0-5) with probability 1/7,6and the 'solid' action (state 6) with probability 6/7.7All transitions yield reward 0, with discount gamma = 0.99.8Semi-gradient TD(0) diverges exponentially; TDC converges to 0.9"""10
11from typing import Tuple12import numpy as np13
14
15class BairdsCounterexample:16    """7-state MDP with 8 linear features designed by Leemon Baird (1995)."""17
18    def __init__(self, gamma: float = 0.99) -> None:19        self.num_states: int = 720        self.num_features: int = 821        self.gamma: float = gamma22
23        # Feature matrix Phi: shape (7, 8)24        # States 0..5: feature 2 at state index, feature 1 at index 725        # State 6: feature 1 at index 6, feature 2 at index 726        self.phi: np.ndarray = np.zeros((self.num_states, self.num_features), dtype=np.float64)27        for s in range(6):28            self.phi[s, s] = 2.029            self.phi[s, 7] = 1.030        self.phi[6, 6] = 1.031        self.phi[6, 7] = 2.032
33    def step(self, state: int) -> Tuple[int, float, float]:34        """Sample transition under behavior policy b.35        36        Returns:37            next_state: The resulting state.38            reward: Scalar reward (always 0.0).39            rho: Importance sampling ratio pi(a)/b(a).40        """41        # Behavior policy: 1/7 dashed action, 6/7 solid action42        # Target policy: solid action with probability 1.043        if np.random.rand() < (1.0 / 7.0):44            # Dashed action: transitions uniformly to one of states 0..545            next_state = np.random.randint(0, 6)46            rho = 0.0  # pi(dashed) = 0, so rho = 0 / (1/7) = 0.047        else:48            # Solid action: transitions deterministically to state 649            next_state = 650            rho = 1.0 / (6.0 / 7.0)  # pi(solid)=1.0, b(solid)=6/7 -> rho = 7/651
52        reward = 0.053        return next_state, reward, rho54
55    def get_features(self, state: int) -> np.ndarray:56        return self.phi[state].copy()57
58
59def run_experiment(num_steps: int = 3000, seed: int = 42) -> Tuple[float, float]:60    """Run semi-gradient TD(0) and TDC in parallel on Baird's counterexample."""61    np.random.seed(seed)62    env = BairdsCounterexample(gamma=0.99)63
64    # Initial weights: [1, 1, 1, 1, 1, 1, 1, 10] as in Sutton & Barto65    w_td = np.array([1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 10.0], dtype=np.float64)66    w_tdc = w_td.copy()67    u_tdc = np.zeros(8, dtype=np.float64)68
69    alpha_td = 0.0170    alpha_tdc = 0.00571    beta_tdc = 0.05  # beta >> alpha (two-timescale separation)72
73    current_state_td = np.random.randint(0, 7)74    current_state_tdc = current_state_td75
76    for step in range(num_steps):77        # 1. Semi-gradient TD(0) step78        x_td = env.get_features(current_state_td)79        next_s_td, r_td, rho_td = env.step(current_state_td)80        x_next_td = env.get_features(next_s_td)81
82        delta_td = r_td + env.gamma * np.dot(w_td, x_next_td) - np.dot(w_td, x_td)83        w_td += alpha_td * rho_td * delta_td * x_td84        current_state_td = next_s_td85
86        # 2. TDC step87        x_tdc = env.get_features(current_state_tdc)88        next_s_tdc, r_tdc, rho_tdc = env.step(current_state_tdc)89        x_next_tdc = env.get_features(next_s_tdc)90
91        delta_tdc = r_tdc + env.gamma * np.dot(w_tdc, x_next_tdc) - np.dot(w_tdc, x_tdc)92        x_dot_u = np.dot(x_tdc, u_tdc)93
94        # Fast timescale LMS auxiliary update95        u_tdc += beta_tdc * (rho_tdc * delta_tdc - x_dot_u) * x_tdc96
97        # Slow timescale TDC primary update98        w_tdc += alpha_tdc * (rho_tdc * delta_tdc * x_tdc - env.gamma * rho_tdc * x_next_tdc * x_dot_u)99        current_state_tdc = next_s_tdc100
101    max_abs_td = float(np.max(np.abs(w_td)))102    max_abs_tdc = float(np.max(np.abs(w_tdc)))103
104    return max_abs_td, max_abs_tdc105
106
107if __name__ == "__main__":108    max_td, max_tdc = run_experiment(num_steps=3000, seed=42)109    print(f"Semi-gradient TD(0) max weight: {max_td:.2f}")110    print(f"TDC max weight:                 {max_tdc:.2f}")111
112    # Confirm divergence vs stability113    assert max_td > 10_000.0, f"Expected TD(0) to diverge, got {max_td}"114    assert max_tdc < 15.0, f"Expected TDC to remain bounded, got {max_tdc}"115    print("Verification passed: TD(0) diverged while TDC remained stably bounded.")

Expected Output

1Semi-gradient TD(0) max weight: 48381.402TDC max weight:                 6.683Verification passed: TD(0) diverged while TDC remained stably bounded.

Watch Out For

The Quick Version

• Solves the Deadly Triad: Gradient-TD methods provide the first mathematically guaranteed convergent off-policy linear TD algorithms with $\mathcal{O}(d)$ per-step complexity.
• Minimizes the MSPBE: Unlike standard semi-gradient TD, which follows no objective function, GTD2 and TDC perform true stochastic gradient descent on the Mean Squared Projected Bellman Error ($\text{MSPBE}$).
• Two-Timescale Architecture: Solves the double-sampling dilemma by decoupling updates into a fast auxiliary vector $\mathbf{u}_t$ estimating $\mathbf{C}^{-1} (\mathbf{b} - \mathbf{A}\mathbf{w})$ and a slow primary vector $\mathbf{w}_t$ following the true gradient.
• TDC Preferred Over GTD2: TDC augments standard TD with a gradient correction term, offering faster empirical convergence and recovering standard TD when off-policy corrections vanish.

What to Read Next

• The Deadly Triad
• Baird's Counterexample
• Emphatic-TD Methods in RL