8.Function Approximation & the Deadly Triad

8.1 The end of tables

Pendle's state is $(\theta, \dot\theta)$ — two real numbers. There are uncountably many of them. A table has no entry for $\theta = 0.7231847\ldots$, and it never will.

Discretizing does not rescue us. Chapter 5's widget made the arithmetic concrete: even a coarse 10-bin discretization of a 7-degree-of-freedom arm produces more states than could be swept in the lifetime of the universe. And a discretization fine enough to control well is far worse than coarse.

The deeper problem is that tables cannot generalize. Rusty learning that a cell three metres from a shelf is safe tells a table nothing about the cell one centimetre away. Every state must be visited to be learned. For a robot that is not a slow path to success; it is no path at all.

So we replace the table with a parameterized function

$\hat v(s, \mathbf{w}) \approx v_\pi(s), \qquad \mathbf{w} \in \mathbb{R}^d, \quad d \ll |\mathcal{S}|,$

and accept the consequence: changing one weight changes the value of many states at once. That is the entire point — it is how generalization happens — and it is also the source of every difficulty in this chapter.

8.2 What are we even optimizing?

With a table, we could hit the Bellman equation exactly. With $d \ll |\mathcal{S}|$ parameters we generally cannot, so we must decide which errors matter.

The standard choice is the mean squared value error, weighted by how often each state is actually visited:

$\overline{\text{VE}}(\mathbf{w}) \doteq \sum_{s} \mu(s) \left[ v_\pi(s) - \hat v(s, \mathbf{w}) \right]^2,$

where $\mu$ is the on-policy state distribution.

8.3 Semi-gradient TD, and the term we drop

Gradient descent on $\overline{\text{VE}}$ would use targets $v_\pi(s)$ — which we do not have. Substituting the TD target gives the update

$\mathbf{w} \leftarrow \mathbf{w} + \alpha \left[ R_{t+1} + \gamma\, \hat v(S_{t+1}, \mathbf{w}) - \hat v(S_t, \mathbf{w}) \right] \nabla \hat v(S_t, \mathbf{w}).$

Look carefully at what happened. The target $R_{t+1} + \gamma \hat v(S_{t+1}, \mathbf{w})$ depends on $\mathbf{w}$, yet we did not differentiate through it. That is deliberate, and it is why this is called a semi-gradient method: it is the gradient of the error with respect to the prediction only, treating the target as a constant.

For the linear case $\hat v(s,\mathbf{w}) = \mathbf{w}^\top \mathbf{x}(s)$ the gradient is just the feature vector, and there is real theory. On-policy linear semi-gradient TD(0) converges to the TD fixed point $\mathbf{w}_{\text{TD}}$, which satisfies

$\overline{\text{VE}}(\mathbf{w}_{\text{TD}}) \le \frac{1}{1-\gamma} \min_{\mathbf{w}} \overline{\text{VE}}(\mathbf{w}).$

So TD's answer is within a factor $1/(1-\gamma)$ of the best the function class can do. At $\gamma = 0.99$ that factor is 100 — a weak guarantee, but a guarantee, and it is more than Part II will offer once networks arrive.

8.4 Features: tile coding and what came after

Linear methods are only as good as their features. The classic robotics choice is tile coding: overlay several offset grids ("tilings") on the state space; a state activates exactly one tile per tiling, giving a sparse binary feature vector.

Tile coding gets three things right at once. Generalization is controlled by tile width while resolution is controlled by the number of tilings — you tune them independently. Lookup is $O(\text{tilings})$ regardless of dimension. And with exactly $n$ active features, the effective learning rate is $\alpha/n$, so step sizes behave predictably.

/// Tile coding over a bounded continuous state space.
/// Each tiling is offset so that a state activates a different tile in each,
/// giving resolution finer than any single tiling's width.
pub struct TileCoder {
    n_tilings: usize,
    tiles_per_dim: usize,
    bounds: Vec<(f64, f64)>,
    offsets: Vec<Vec<f64>>,
}
 
impl TileCoder {
    /// Indices of the active features — exactly `n_tilings` of them.
    pub fn active(&self, state: &[f64]) -> Vec<usize> {
        let mut idx = Vec::with_capacity(self.n_tilings);
 
        for (t, offset) in self.offsets.iter().enumerate() {
            let mut coords = Vec::with_capacity(state.len());
 
            for (d, &x) in state.iter().enumerate() {
                let (lo, hi) = self.bounds[d];
                let scaled = (x - lo) / (hi - lo) * self.tiles_per_dim as f64;
                let c = (scaled + offset[d]).floor() as isize;
                coords.push(c.clamp(0, self.tiles_per_dim as isize - 1) as usize);
            }
 
            // Flatten (tiling, coords) into one feature index.
            let mut flat = t;
            for c in coords {
                flat = flat * self.tiles_per_dim + c;
            }
            idx.push(flat);
        }
        idx
    }
}
 
/// Semi-gradient SARSA with binary features: the update touches only the
/// active tiles, so it costs O(n_tilings) regardless of the table's size.
pub fn sarsa_update(w: &mut [f64], active: &[usize], delta: f64, alpha: f64) {
    let step = alpha / active.len() as f64;
    for &i in active {
        w[i] += step * delta;
    }
}

Neural networks replace hand-designed features with learned ones. The trade is stark: networks handle raw pixels and high dimensions where tile coding cannot, at the cost of every theoretical guarantee in this section and orders of magnitude more compute. For a 2-D state like Pendle's, tile coding is still the better engineering choice — a fact worth knowing before reaching for a GPU.

8.5 The deadly triad

Now the central result of the chapter, and the reason Part II is engineered the way it is.

Three ingredients, each individually fine:

1. Function approximation — required, since tables do not scale.
2. Bootstrapping — targets built from your own estimates, as in TD. Gives efficiency and low variance.
3. Off-policy training — learning about one policy from data generated by another. Essential for sample efficiency, which robots cannot do without.

Any two are safe. All three together can make the parameters diverge to infinity.

Baird's counterexample is the cleanest demonstration. Every reward is zero, so the true value function is $v = 0$ everywhere — and it is exactly representable by the feature set. There is nothing to approximate badly. Yet the weights grow without bound.

Three families of response exist, and Part II uses all of them:

Live with it, carefully. DQN (Chapter 9) is squarely in the triad and works anyway — because target networks slow the feedback loop and replay buffers keep the update distribution broad. It is engineering, not theory, and it is honest to say so.

Stay on-policy. PPO (Chapter 10) avoids the third ingredient entirely, which is a large part of why it is the workhorse of real-world robot RL despite being less sample-efficient. Tang's survey finds on-policy methods dominating the successful sim-to-real results, and this is the reason.

Fix the objective. Gradient-TD methods (GTD2, TDC) perform true stochastic gradient descent on a projected Bellman error, and converge under all three conditions. They are theoretically satisfying, somewhat more complex, and less used in practice than they deserve.

8.6 Control with approximation

For control, parameterize $\hat q(s,a,\mathbf{w})$ and run the same GPI loop from Chapter 5, with semi-gradient SARSA updates and $\varepsilon$-greedy action selection.

Two new difficulties appear immediately. The policy is no longer stable: a small weight change can flip the argmax at many states at once, so the policy can oscillate even when the values are nearly converged. And the state distribution shifts as the policy changes, so the $\mu$ that made $\overline{\text{VE}}$ meaningful is a moving target — a control problem is a non-stationary prediction problem wearing a disguise.

Despite this, semi-gradient SARSA with tile coding is remarkably robust in practice and remains a strong baseline. Before assuming a robot problem needs deep RL, it is worth trying: it trains in seconds, has few hyperparameters, and when it works you are done.

8.7 Chapter bridge

We gave up tables and got generalization. We also gave up exact convergence guarantees, learned that our update is not a gradient of anything, and met a mechanism that can make training diverge on a problem with zero rewards and a representable answer.

Chapter 9 takes the triad on anyway. Deep Q-networks put a neural network in the value function, train off-policy from a replay buffer, and bootstrap — all three ingredients at maximum strength. It works, and understanding why it works is understanding the two pieces of engineering that make it work: replay buffers that decorrelate the update distribution, and target networks that slow the feedback loop enough that the loop's gain drops below one. Both are direct responses to what this chapter diagnosed.

References