RobotGuide
Foundations/Function approximation: the three ingredients that take you from 'guaranteed convergence' to 'blowing up'

Foundations 05 / 11 · value functions

Function approximation: the three ingredients that take you from 'guaranteed convergence' to 'blowing up'

Semi-gradient, the deadly triad, the distribution decides the answer, target networks. This piece explains why deep RL training curves often don't 'converge slowly' but 'explode'

55 minAdvanced6 derivation steps4 self-test questions

One-line conclusion

The convergence guarantees of tabular methods die the moment you switch to function approximation. The failure is not random: it requires three things to hold simultaneously - function approximation, bootstrapping, off-policy. Remove any one and you are still safe; all three together diverge.

This piece is the only entry point for understanding the 'designs that look odd' in DQN/TD3/SAC: why target networks exist, why experience replay exists, why a bigger replay buffer is both better and more biased.

Symbol table

SymbolMeaning
v̂(s;w)the approximate value function with parameters w: state in, value out
∇_w v̂gradient of the approximator with respect to the parameters, i.e. 'which weights to move to change this state's value'
d(s)the sampling distribution: which states your data actually comes from
A, bthe two quantities of the fixed-point equation in the linear case; A depends on the sampling distribution d

Derivation

  1. Semi-gradient: why it is called 'semi'
  2. The deadly triad: only lethal when all three show up
  3. The sampling distribution decides the answer (this bites more often than 'divergence')
  4. Overestimation from max: why you must take the min of two Qs
  5. The target network: pinning the moving target temporarily
  6. Experience replay: both the cure and the cause

1. Semi-gradient: why it is called 'semi'

The TD target contains w; a strict full gradient would differentiate through it too. Implementations treat the target as a constant - this is the semi-gradient. It is not laziness; it is deliberate.

w ← w + α[ r + γ v̂(s';w) - v̂(s;w) ] ∇_w v̂(s;w)

Why this holdsIf you also differentiate the target (residual gradient), you get the true gradient, but it converges extremely slowly and gets stuck on trivial solutions like 'collapse the values of neighboring states together'. The semi-gradient has no theoretical convergence guarantee but is far faster in practice - a classic divergence point between engineering and theory.

2. The deadly triad: only lethal when all three show up

Function approximation + bootstrapping + off-policy. What does each one do, and why do they compound into divergence?

function approximation (shared parameters) + bootstrap (the target is an estimate) + off-policy (data distribution ≠ policy distribution) ⟹ possible divergence

Why this holdsIntuition: function approximation lets one update affect a whole swath of states (parameter sharing); bootstrapping propagates error along the state chain; off-policy makes 'the distribution being updated' differ from 'the distribution the data came from', so some states get pushed repeatedly in one direction and never receive samples that correct them. Remove any one and it is safe: tabular (no sharing), MC (no bootstrapping), on-policy (distributions match).

3. The sampling distribution decides the answer (this bites more often than 'divergence')

With linear approximation, the fixed point is determined by A w = b, and both A and b carry expectations over the sampling distribution. So 'change the data, change the solution' - even when the algorithm is entirely correct.

A = E_d[ x(s)(x(s) - γx(s'))^T ], b = E_d[ r·x(s) ]

Why this holdsA more extreme example: if sampling covers only one state, A becomes a rank-1 matrix, directly singular, and the equation has no solution. numpy's solver will actually raise LinAlgError. So 'the replay buffer is full of early failure data' is not an efficiency issue - it is mathematically unsolvable.

4. Overestimation from max: why you must take the min of two Qs

Piece 3 already derived the direction; here is the magnitude. It explains the 'double Q' design of every algorithm after DQN.

with true values all 0, 10 actions, noise σ=1: E[max Q̂] = 1.54

Why this holdsMeasured: σ=0.5→0.769, σ=1→1.539, σ=2→3.087. The bias is proportional to σ and roughly proportional to the square root of the number of actions. Taking the min of two independent estimates turns a positive bias into a slight negative one - small cost, big payoff, hence standard equipment.

5. The target network: pinning the moving target temporarily

Since the target is 'computed from yourself', use a stale copy of the parameters to compute the target and sync every so often. That is the target network.

θ⁻ ← τθ + (1-τ)θ⁻, commonly τ=0.005 (equivalent to updating about every 200 steps)

Why this holdsThe cost is lag: smaller τ is more stable but slower, and when the target lags the policy too much you get 'nothing learns'. A hard update (full copy every N steps, N=1000) and a soft update (0.5% per step) are equivalent; the latter is smoother. To diagnose 'is the target too slow': check whether the mean of Q sits near 0 without moving for a long time.

6. Experience replay: both the cure and the cause

Replay breaks sample correlation (making gradients less jittery) and lets you learn repeatedly from a little data. But it turns on-policy into off-policy - exactly the third item of the deadly triad.

on-policy: data distribution = current policy; replay: data distribution = a mixture of all past policies

Why this holdsThis is why PPO only dares to update a few epochs (usually 4) on the same batch of data before resampling, while DQN dares to use a 1M-step buffer: DQN has target networks + double Q as a backstop, PPO does not. So PPO's clipping is its weapon against off-policy bias.

Work it by hand

Three-state chain 0→1→2 (2 is terminal, entering 2 gives reward 1), linear features x(s)=(1, s) and γ=0.9. Find the linear TD fixed point under a uniform distribution and under the skewed distribution [0.7,0.2,0.1], and compare.

  1. the true values are [0.81, 0.90, 1.00], while the linear form w0+w1·s can only express arithmetic sequences and carries approximation error by itself
  2. under the uniform distribution, solve A w = b: w=(0.810, 0.0935), giving V=[0.810, 0.903, 0.997]
  3. under the skewed distribution [0.7,0.2,0.1]: w=(0.8096, 0.0912), V=[0.810, 0.901, 0.992]
  4. if only s=2 is sampled: A = x(2)x(2)^T is rank 1, singular, numpy raises LinAlgError
Answer

The two distributions give different solutions (0.903 vs 0.901); the difference is small because this example's features are good enough, but 'sampling only one state yields no solution' is hard - insufficient off-policy coverage makes the equation lose its solution, not merely 'solve it a bit worse'. Practical implication: you must keep feeding fresh policy data into the replay buffer; don't expect old data to last forever.

Run it

25 lines, computes the numbers above and verifies the matrix is singular when 'only one state is sampled'. You can comment out the try in the second block to watch it actually raise.

python · numpy only
import numpy as np
G, n = 0.9, 3
def fixed_point(dist):
    A, b = np.zeros((2,2)), np.zeros(2)
    for s, d in enumerate(dist):
        x = np.array([1.0, float(s)])
        if s == n - 1:
            A += d * np.outer(x, x); b += d * x
        else:
            xn = np.array([1.0, float(s+1)])
            A += d * np.outer(x, x - G * xn)
    return np.linalg.solve(A, b)
for d in ([1/3,1/3,1/3], [0.7,0.2,0.1]):
    w = fixed_point(d)
    print(d, 'w =', np.round(w,4), 'V =', np.round([w[0]+w[1]*s for s in range(3)],3))
try:
    fixed_point([0.0, 0.0, 1.0])
except np.linalg.LinAlgError:
    print('only the terminal state sampled -> A singular, no solution')

You pass when you see this

The two runs differ slightly in w (second component 0.0935 vs 0.0912), and the last line prints 'A singular'. If the second solution is identical to the first, check whether you actually multiplied d into A (forgetting d is the most common implementation mistake).

Self-test · 4 questions

Answer first, then expand. Each question traces back to a specific derivation section.

01Which ingredient of the deadly triad is easiest to remove, and which one do practitioners usually remove?

Removing bootstrapping is easiest: use MC or n-step returns, at the cost of higher variance and lower sample efficiency. In practice most choose 'remove off-policy' or 'tough it out with a target network + double Q' - PPO picks the former, DQN/SAC the latter.

02Why does PPO only dare to update about 4 epochs on the same batch of data?

Because it is an on-policy algorithm; more epochs push the policy further and further from the sampling distribution (the importance sampling ratio runs away). Clipping only bounds that drift at ±20%; it does not fix the root cause.

03Q values suddenly jump from 100 to 1e4 - the two most likely bugs?

(1) Reward given every step instead of only at termination (scale wrong); (2) target network not synced or τ too large (bootstrapping amplifying itself). Check these two before touching the learning rate.

04The linear TD fixed point depends on the sampling distribution - does that mean 'the algorithm is wrong'?

No. It is an inherent property of least-squares projection: you are minimizing the Bellman error weighted by the distribution d, so changing the weights changes the answer. The only ways to change the answer are changing the features or changing the distribution.

Keep reading

Previous: MC and TDNext: the policy gradient derivationreinforcement learning knowledge page
PreviousModel-Free: The Bias-Variance Ledger of MC vs TD NextPolicy gradient: deriving REINFORCE line by line

The whole series · 11 articles

01The Only Four Math Tools You Need40 min02MDP and Return: Writing 'What To Do' as Something Computable45 min03The Bellman Equation: Why V Is a Fixed Point and Why Iteration Must Converge60 min04Model-Free: The Bias-Variance Ledger of MC vs TD60 min05Function approximation: the three ingredients that take you from 'guaranteed convergence' to 'blowing up'55 min06Policy gradient: deriving REINFORCE line by line70 min07Actor–critic and GAE: turning the variance knob to λ60 min08PPO: what does clip actually clip70 min09SAC: entropy, reparameterization, double Q - three parts, each solving one problem75 min10HER: why goal relabeling is mathematically legitimate50 min11How to debug non-convergence: map symptoms back to formulas45 min