Semi-Gradient Methods with Function Approximation

In tabular TD(0), the update $V(S_t) \leftarrow V(S_t) + \alpha[R_{t+1} + \gamma V(S_{t+1}) - V(S_t)]$ nudges one table entry using an error computed from another table entry. With function approximation, $V$ is replaced by $\hat v(s,\mathbf{w})$, a parameterized function — linear in features, or a deep network — and a single weight update changes the value estimate at every state simultaneously. This is what makes function approximation powerful (generalization across states) and dangerous (interference between states) at the same time. If we wanted to write TD as true gradient descent on some objective, we would need a loss function whose gradient produces the TD update. The natural candidate is the mean squared TD error,

Differentiating this fully with respect to $\mathbf{w}$ requires differentiating both occurrences of $\mathbf{w}$ — the one inside $\hat v(S_t,\mathbf{w})$ and the one inside the target $\hat v(S_{t+1},\mathbf{w})$. The resulting "true gradient" or "residual gradient" update is mathematically valid, always converges (it is literally gradient descent), but empirically learns much more slowly and, worse, does not converge to a useful fixed point — it targets minimizing the noise in one-step predictions rather than tracking the actual value function. Semi-gradient methods make a different choice: treat $\hat v(S_{t+1},\mathbf{w})$ as a fixed target, exactly as it appears in the current update, and differentiate only the leading $\hat v(S_t,\mathbf{w})$ term. The word "semi" signals that we take a gradient with respect to only part of the expression that actually depends on $\mathbf{w}$. This is the same design principle underlying TD(lambda) and Eligibility Traces and it is what makes bootstrapped learning with function approximation fast, online, and incremental — at the cost of losing the guarantee that we are descending any single fixed objective function.

Semi-gradient TD(0) prediction. Given a fixed policy $\pi$ to evaluate, at each step we observe $(S_t, R_{t+1}, S_{t+1})$, compute the TD error using the current weights for both the value at $S_t$ and the bootstrapped value at $S_{t+1}$, and then take a gradient step using only $\nabla \hat v(S_t,\mathbf{w})$:

For terminal transitions, the bootstrap term is dropped: $\delta_t = R_{t+1} - \hat v(S_t,\mathbf{w}_t)$, matching the convention that $\hat v(\text{terminal}) = 0$.

Semi-gradient Sarsa (control). Replace the state-value function with an action-value function $\hat q(s,a,\mathbf{w})$ and bootstrap from the action actually taken next (on-policy):

Semi-gradient Q-learning (off-policy control). Bootstrap from the greedy action instead:

This is the same core equation used inside DQN, with $\hat q$ a deep network and $\mathbf{w}$ its parameters (DQN adds a separate slowly-updated target network to stabilize $\mathbf{w}_t$ used inside the max — a practical patch to the instability discussed below).

Semi-gradient TD(λ) extends this with eligibility traces $\mathbf{z}$, which accumulate gradient directions weighted by recency, allowing credit to propagate to features seen several steps in the past without waiting for multiple sweeps: ``` Algorithm: Semi-Gradient TD(λ) for estimating v_pi (linear or nonlinear) Input: policy pi, differentiable value function v_hat(s, w), step size alpha in (0,1], trace decay lambda in [0,1], discount gamma Initialize: weight vector w arbitrarily (e.g., zero) for each episode: initialize S z <- 0 # eligibility trace, same shape as w loop for each step of episode: A <- action given by pi for S take action A, observe R, S' grad <- gradient of v_hat(S, w) with respect to w z <- gamma lambda z + grad # accumulate trace if S' is terminal: delta <- R - v_hat(S, w) else: delta <- R + gamma v_hat(S', w) - v_hat(S, w) w <- w + alpha delta * z # semi-gradient update using trace S <- S' if S is terminal: break ``` When $\lambda = 0$, the trace $\mathbf{z}$ collapses to the single current gradient $\nabla \hat v(S_t,\mathbf{w})$ and the algorithm reduces exactly to semi-gradient TD(0). When $\lambda = 1$ (with $\gamma=1$), it becomes equivalent, in expectation, to gradient Monte Carlo — no bootstrapping at all, only real returns. The crucial "semi" step is identical in every case: $\nabla \hat v(S',\mathbf{w})$ never appears anywhere in the update, only $\nabla \hat v(S,\mathbf{w})$ feeding the trace.

Time and space complexity. With linear function approximation $\hat v(s,\mathbf{w}) = \mathbf{w}^\top \mathbf{x}(s)$ over $d$ features, each step requires computing $\mathbf{x}(s)$, a dot product, and a vector update — $O(d)$ time and $O(d)$ space, independent of the number of states. This is the entire point of function approximation: tabular TD needs $O(|\mathcal S|)$ space, while semi-gradient TD needs only $O(d)$, and $d$ can be orders of magnitude smaller than $|\mathcal S|$. With a neural network of $P$ parameters, one update costs $O(P)$ for the forward pass plus $O(P)$ for backpropagation (in general, backprop cost is proportional to the number of edges in the computational graph, which is $\Theta(P)$ for standard feedforward architectures). Eligibility traces add another $O(d)$ (or $O(P)$) vector to maintain and update per step, so semi-gradient TD(λ) has the same asymptotic per-step cost as TD(0); the trace does not change the complexity class, only the constant.

Why "semi" is not a true gradient — and why that is acceptable. Consider the mean squared TD error objective introduced above. Its true gradient with respect to $\mathbf{w}$ is

The semi-gradient update uses only the first term, $\mathbb{E}[\delta_t \nabla \hat v(S_t,\mathbf{w})]$, dropping the $-\gamma\nabla\hat v(S_{t+1},\mathbf{w})$ contribution entirely. This is not an approximation to the same quantity — it is the gradient of a genuinely different, better-behaved target: the mean squared projected Bellman error $\overline{\text{PBE}}$. Define the Bellman operator $T^\pi$ and the projection $\Pi$ onto the space of representable value functions (for linear $\hat v$, projection in the weighted $L^2$ norm under the on-policy state distribution). The semi-gradient TD(0) fixed point $\mathbf{w}_{TD}$ satisfies

i.e., applying the Bellman operator and then projecting back onto the representable function class returns you to where you started. This is a well-defined, meaningful fixed point — it is the best representable approximation consistent with the Bellman equation — even though it is not the minimizer of mean squared value error $\|\hat v_\mathbf{w} - v_\pi\|^2$ in general.

Convergence guarantee (linear, on-policy). For linear $\hat v(s,\mathbf{w})=\mathbf{w}^\top\mathbf x(s)$, states sampled from the on-policy stationary distribution $d_\pi$, and a Robbins–Monro step-size schedule, semi-gradient TD(0) converges with probability 1 to the unique $\mathbf{w}_{TD}$ solving $\mathbf{A}\mathbf{w}_{TD}=\mathbf{b}$, where

The proof sketch (Tsitsiklis & Van Roy, 1997) shows that the key matrix $\mathbf{A}$ is positive definite precisely because states are weighted by the on-policy distribution — the same distribution the Markov chain naturally settles into under $\pi$. Positive definiteness of $\mathbf{A}$ guarantees the mean ODE associated with the stochastic update is globally stable, which by stochastic approximation theory implies convergence of the actual iterates. The bound on the resulting error is also known explicitly:

so the TD fixed point can be worse than the best possible linear approximation by a factor of up to $\frac{1}{1-\gamma}$ — a real cost of bootstrapping, but a bounded one.

Where the guarantee breaks. The positive-definiteness argument depends critically on sampling states according to $d_\pi$ — the on-policy distribution. If the weighting distribution changes (off-policy sampling, as in Q-learning with a replay buffer, or importance-sampling-corrected updates), $\mathbf{A}$ can become indefinite, and the ODE can become unstable. Combined with a nonlinear function approximator (where the linear-algebra argument for $\mathbf{A}$ does not even apply) and bootstrapping, semi-gradient methods can diverge — weights growing without bound even though every individual update looked reasonable. This is exactly the setup foreshadowed by The Deadly Triad: function approximation, bootstrapping, and off-policy training together remove the safety net that on-policy linear semi-gradient TD enjoys.

Consider a tiny 5-state random walk (a linearized version of Sutton & Barto's classic example): states $A,B,C,D,E$ in a line, terminal on both ends, reward $+1$ on the right exit and $0$ elsewhere, $\gamma=1$. Use linear function approximation with a single scalar feature per state — state-aggregation-style one-hot features, so $\hat v(s,\mathbf{w}) = w_s$ (this reduces to the tabular case, useful for tracing the arithmetic transparently before moving to compressed features). Initialize all $w_s = 0.5$. Suppose one episode visits $C \to D \to E \to \text{terminal (reward 1)}$, with $\alpha = 0.1$.

Notice: only $w_E$ moved. This is exactly the semi-gradient mechanic in action — the update to $\hat v(E)$ used the observed reward at the terminal transition, not a bootstrapped value, so it is trustworthy immediately. States $C$ and $D$ saw zero TD error this episode because their bootstrapped targets ($\hat v(D)=\hat v(E)=0.5$) still matched their own current estimate; the useful signal (that the right side is good) has not yet propagated backward from $E$. Now trace a second episode, $B \to C \to D \to E \to \text{terminal}$, using the updated weights ($w_E = 0.55$, others still $0.5$):

This shows the signature behavior of one-step bootstrapping under function approximation: information about the terminal reward diffuses backward one state per episode, at a rate controlled by $\alpha$ and the trace decay $\lambda$. If we instead ran semi-gradient TD(λ) with $\lambda = 0.9$, the eligibility trace from step 1 would already be nonzero (decayed by $\gamma\lambda$ each step) by the time the terminal reward arrives at step 4, so $w_B$ and $w_C$ would also receive a fraction of that terminal error within the same episode — this is precisely why traces accelerate credit assignment relative to $\lambda=0$.

Semi-gradient TD and its control variants underlie essentially all value-based deep reinforcement learning. DQN and its descendants (Double DQN, Dueling DQN, Rainbow) all compute a bootstrapped target from a neural network and update weights with exactly the semi-gradient rule, with a frozen target network standing in as a practical stabilization of the "treat the target as constant" idea. Actor-critic methods (A3C, PPO, SAC) use a semi-gradient critic to estimate a baseline or advantage function, feeding it into the policy gradient. TD(λ) with linear function approximation, and its semi-gradient update rule, was the mechanism behind TD-Gammon, one of the earliest large-scale successes of reinforcement learning, and remains a standard tool wherever features are engineered by hand rather than learned end-to-end, such as some robotics and industrial control applications where interpretability and sample efficiency of linear models are valued over the flexibility of deep networks. Understanding exactly which gradient terms are dropped, and under what conditions the remaining update is still safe, is a prerequisite for diagnosing training instability in any of these systems — instability that shows up as value estimates silently diverging while the loss curve looks deceptively smooth.

Ask the tutor: How exactly does an off-policy replay buffer break the positive-definiteness argument that makes on-policy semi-gradient TD(0) provably stable?