Chapter 121: Function Approximation

What You'll Learn

Explain why tabular methods fail in large or continuous state spaces
Describe the function approximation approach to RL
Implement linear function approximation for value estimation
Understand the deadly triad and its implications
Explain how neural networks enable deep RL

Our Q-learning agent mastered a 4x4 grid. But what about a robot navigating a room? With continuous position (x, y) and orientation, there are infinite states. We can’t have a table entry for every possible configuration.

We need a way to generalize.

Why Function Approximation?

In tabular RL, we stored a value for every state (or state-action pair). This works for small, discrete problems. But real-world problems often have:

Continuous states: Position, velocity, angles
High-dimensional observations: Images with millions of pixels
Combinatorially large spaces: Chess has more positions than atoms in the universe

Function approximation lets us represent value functions compactly and generalize across similar states.

Chapter Overview

This chapter bridges tabular RL and deep RL, introducing the core ideas that make modern RL algorithms work:

Why Tables Fail

The curse of dimensionality in RL

Linear Approximation

Features, weights, and gradient descent

Neural Networks

Deep learning meets reinforcement learning

The Core Idea

📖Function Approximation

Instead of storing $Q(s,a)$ for every state-action pair, we learn parameters $\mathbf{w}$ such that $\hat{Q}(s,a;\mathbf{w}) \approx Q^*(s,a)$ . Similar states automatically get similar values.

Any function approximator can play this role — linear models, neural networks, decision trees. The choice of approximator determines:

What patterns can be captured
How efficiently we learn
Whether training is stable

Our Running Example: CartPole

From here through the policy gradient chapters, CartPole is our recurring test environment: a cart slides along a track, a pole is hinged on top, and the agent must keep the pole balanced by nudging the cart left or right.

State variables (continuous)

Actions (push left / right)

Reward per step upright

500

Max steps per episode

State: cart position, cart velocity, pole angle, pole angular velocity — four real numbers, so there is no finite table of states
Actions: push the cart left or push it right
Reward: +1 for every timestep the pole stays up; the episode ends when the pole tips too far, the cart leaves the track, or 500 steps elapse

CartPole is ideal for this part of the book: its continuous state defeats tabular methods immediately, yet it is small enough that every algorithm we build — linear approximation, neural Q-learning, DQN, and later policy gradients — can solve it in seconds.

Prerequisites

This chapter assumes familiarity with:

Q-Learning for the core algorithm we’re extending
Basic calculus (gradients and optimization)
(Recommended) Bellman Equations for the theoretical foundation

Key Questions We’ll Answer

Why can’t we just discretize continuous states?
How do we update parameters instead of table entries?
What is the “deadly triad” and why should we care?
How do neural networks unlock deep RL?

Check Your Understanding

Check your understanding

1. With linear function approximation and on-policy sampling, what does semi-gradient TD(0) converge to?

The weights that minimize the mean squared value error (MSVE)The exact value function V-pi for every stateThe TD fixed point of the projected Bellman equation, which generally differs from the MSVE minimizerNothing—TD never converges once function approximation is involved

2. Which three ingredients form the deadly triad?

Neural networks, experience replay, and epsilon-greedy explorationFunction approximation, bootstrapping, and off-policy learningLarge state spaces, sparse rewards, and continuous actionsFunction approximation, exploration, and discounting

3. Why is semi-gradient TD called "semi"-gradient?

It uses half the learning rate of full gradient descentIt differentiates only the prediction, treating the bootstrapped target as a constantIt updates only half of the weight vector on each stepIt approximates the gradient with a random subset of features

4. A CartPole state is four real numbers. Why not just discretize each into 100 bins and use tabular Q-learning?

Discretization makes the environment non-MarkovThat yields 100 million states with no generalization between neighboring bins—most would never be visitedTabular Q-learning cannot handle more than two state variablesThe bins would make the reward function discontinuous

5. What makes linear function approximation "linear"?

The value estimate must be a linear function of the raw state variablesThe value estimate is linear in the weights; the features themselves can be arbitrarily nonlinear in the stateIt can only represent linearly increasing value functionsThe features must be normalized to the unit interval

Generalization is the point
Learn from some states, apply to similar ones. Tables cannot do this—every entry is learned independently.
Linear approximation is simple but capable
V(s) = w-transpose phi(s): the gradient is just the feature vector, and good features (like tile coding) go a long way.
TD with approximation converges to the TD fixed point
Not the MSVE minimizer—but provably within a 1/(1-gamma) factor of it, for on-policy linear TD.
The deadly triad can cause divergence
Function approximation + bootstrapping + off-policy learning together can make weights explode. Any two alone are generally safe.
Neural networks learn their own features
End-to-end learning from raw observations—at the cost of amplifying the triad's instability, which DQN's tricks address.

Primary Sources

Sutton & Barto, Reinforcement Learning: An Introduction (2nd ed.), Chapters 9–11 — the definitive treatment of on-policy prediction and control with approximation, and of off-policy divergence. Book page
Baird (1995), “Residual Algorithms: Reinforcement Learning with Function Approximation,” ICML 1995 — introduces the counterexample where off-policy semi-gradient TD provably diverges
Tsitsiklis & Van Roy (1997), “An Analysis of Temporal-Difference Learning with Function Approximation,” IEEE Transactions on Automatic Control — the convergence proof for on-policy linear TD and the TD fixed point error bound

Next ChapterDeep Q-Networks→