So far we wrote value into a table with one cell per state. But backgammon has $10^{20}$ states, Go has $10^{170}$, and a helicopter is continuous, so its states cannot even be counted. The table breaks down here. Instead we approximate the value with a function of a few parameters, and generalize even to states never seen.
Lecture slides: PDF
Why abandon the table
Table lookup has two problems. There are too many states or actions to hold in memory, and even if they fit, learning the value of each state separately is too slow. A state never visited stays unknown forever.
The remedy is function approximation. We replace the true value $v_\pi(s)$ with an approximate function that has parameters $\mathbf{w}$.
$$\hat v(s, \mathbf{w}) \approx v_\pi(s) \quad\text{or}\quad \hat q(s, a, \mathbf{w}) \approx q_\pi(s, a)$$The parameters are far fewer than the number of states. So what is learned on seen states leaks into unseen states (generalization). And we update this $\mathbf{w}$ with the MC or TD methods from earlier lectures.
There are three architectures, depending on how the approximator is wired up.
- Feed in one state and emit that state’s single value $\hat v(s, \mathbf{w})$.
- Feed in a state and an action together and emit that pair’s single action-value $\hat q(s, a, \mathbf{w})$.
- Feed in one state only, and emit the action-values of all possible actions $\hat q(s, a_1, \mathbf{w}), \dots, \hat q(s, a_m, \mathbf{w})$ at once.
The third is the one DQN uses. In control we often need $\max_a \hat q(s, a)$, and with the third structure a single forward pass yields all action-values, so picking the maximum is nearly free.
There are many candidate approximators: a linear combination of features, neural networks, decision trees, nearest neighbor, Fourier or wavelet bases, and so on. This lecture deals only with the differentiable ones (since we have to follow the gradient). The linear combination and the neural network are the protagonists.
And there is one important caveat. The data of reinforcement learning is unlike ordinary supervised learning. When the policy changes the data distribution changes, so it is non-stationary; and consecutive states are strongly entangled with one another, so they are not independent and identically distributed (iid). We therefore cannot take supervised learning off the shelf, and we need a learning method suited to data like this. Half of this lecture is that story.
Incremental methods: riding the gradient down
The goal is clear: reduce the mean squared error between the approximate value and the true value.
$$J(\mathbf{w}) = \mathbb{E}_\pi\big[(v_\pi(S) - \hat v(S, \mathbf{w}))^2\big]$$Nudging $\mathbf{w}$ a little in the direction opposite the gradient of this $J$ descends toward a local minimum. With a step size $\alpha$ we have $\Delta\mathbf{w} = -\tfrac{1}{2}\alpha\nabla_\mathbf{w}J(\mathbf{w})$. Working out the expectation,
$$\Delta\mathbf{w} = \alpha\,\mathbb{E}_\pi\big[(v_\pi(S) - \hat v(S, \mathbf{w}))\nabla_\mathbf{w}\hat v(S, \mathbf{w})\big]$$Computing the full expectation every time is expensive. So we draw a single sample at a time and mimic the gradient. This is stochastic gradient descent (SGD).
$$\Delta\mathbf{w} = \alpha\,(v_\pi(S) - \hat v(S, \mathbf{w}))\nabla_\mathbf{w}\hat v(S, \mathbf{w})$$Since the expectation of the single-sample update equals the full gradient update, repeating it many times eventually leads to the same place.
Feature vectors and linear approximation
A summary of a state into a few numbers is the feature vector.
$$\mathbf{x}(S) = \big(x_1(S), \dots, x_n(S)\big)^\top$$A robot’s distances from landmarks, the trends of a stock market, the arrangement of pieces on a chessboard: these become features. The simplest approximation combines these features linearly.
$$\hat v(S, \mathbf{w}) = \mathbf{x}(S)^\top \mathbf{w} = \sum_{j=1}^{n} x_j(S)\,w_j$$Here the objective is quadratic in $\mathbf{w}$, so the local minimum is the global minimum. SGD converges to the global optimum. On top of that the gradient is very clean. Since $\nabla_\mathbf{w}\hat v(S, \mathbf{w}) = \mathbf{x}(S)$, the update becomes
$$\Delta\mathbf{w} = \alpha\,(v_\pi(S) - \hat v(S, \mathbf{w}))\,\mathbf{x}(S)$$Put into words: update = step size × prediction error × feature value. We push the parameters in the direction where the error is large and that feature was strongly switched on.
Here is one amusing fact. Table lookup is a special case of linear approximation. If we take the features as indicators for “is this the state or not,”
$$\mathbf{x}^{\text{table}}(S) = \big(\mathbf{1}(S = s_1), \dots, \mathbf{1}(S = s_n)\big)^\top$$then multiplying this feature vector by $\mathbf{w}$ leaves only the $w_i$ of the cell corresponding to the current state. That is, the parameter vector becomes a table holding the value of each state directly. The table is not the opposite of approximation but merely one extreme end, where the features are chopped up as finely as possible.
No true value: swapping in the target
The equations so far contained the true value $v_\pi(S)$. But reinforcement learning has no supervisor to tell you the answer. There is only reward. So we plug the target built in earlier lectures into the place of $v_\pi(S)$.
- MC uses the actual return $G_t$ as the target: $$\Delta\mathbf{w} = \alpha\,(G_t - \hat v(S_t, \mathbf{w}))\nabla_\mathbf{w}\hat v(S_t, \mathbf{w})$$
- TD(0) uses the bootstrapped TD target $R_{t+1} + \gamma\hat v(S_{t+1}, \mathbf{w})$: $$\Delta\mathbf{w} = \alpha\,(R_{t+1} + \gamma\hat v(S_{t+1}, \mathbf{w}) - \hat v(S_t, \mathbf{w}))\nabla_\mathbf{w}\hat v(S_t, \mathbf{w})$$
- TD(λ) uses the λ-return $G_t^\lambda$: $$\Delta\mathbf{w} = \alpha\,(G_t^\lambda - \hat v(S_t, \mathbf{w}))\nabla_\mathbf{w}\hat v(S_t, \mathbf{w})$$
The MC return is an unbiased (though noisy) sample of the true value. So we can take $\langle S_1, G_1\rangle, \langle S_2, G_2\rangle, \dots$ as training data and run it like supervised learning, and even with a nonlinear approximator it converges to a local optimum.
The TD target still carries the estimate $\hat v(S_{t+1}, \mathbf{w})$, which is not yet correct, so it is a biased sample. Even so we can set it up as training data and learn, and linear TD(0) converges near the global optimum. The update of linear TD(0) is written cleanly with the TD error $\delta$ as $\Delta\mathbf{w} = \alpha\delta\,\mathbf{x}(S)$.
TD(λ) likewise has a forward view (with the λ-return as target) and a backward view (online processing with eligibility traces), and in the linear case the two give exactly the same update. The backward view is
$$\delta_t = R_{t+1} + \gamma\hat v(S_{t+1}, \mathbf{w}) - \hat v(S_t, \mathbf{w})$$$$E_t = \gamma\lambda E_{t-1} + \mathbf{x}(S_t), \qquad \Delta\mathbf{w} = \alpha\delta_t E_t$$The only difference from Lecture 4 now is that the trace accumulates the feature vector $\mathbf{x}(S_t)$ rather than a state indicator.
Control: approximating action-values
To move beyond prediction into control, we approximate the action-value rather than the state-value. We reduce the mean squared error of $\hat q(S, A, \mathbf{w}) \approx q_\pi(S, A)$, and run generalized policy iteration that improves the policy $\varepsilon$-greedily from the approximated $\hat q$. In the linear case we featurize state and action together as $\mathbf{x}(S, A)$ and set
$$\hat q(S, A, \mathbf{w}) = \mathbf{x}(S, A)^\top\mathbf{w}, \qquad \Delta\mathbf{w} = \alpha\,(q_\pi(S, A) - \hat q(S, A, \mathbf{w}))\mathbf{x}(S, A)$$as the update. As in prediction, into the place of $q_\pi$ we plug $G_t$ for MC, $R_{t+1} + \gamma\hat q(S_{t+1}, A_{t+1}, \mathbf{w})$ for TD(0), and the λ-return for TD(λ). The TD(0) version is exactly Sarsa with an approximator on top.
Mountain car: continuous states as features
Mountain car is a problem where an underpowered car is stuck in a valley. Pushing straight to the right won’t climb out; you have to deliberately back up the opposite hill and cross over with the momentum. The state is position and velocity, both continuous. With infinite cells, a table is out.
Silver puts linear Sarsa on this. The crux is how to turn continuous states into features, and he uses coarse coding. The position-velocity plane is covered with several overlapping grids (tiles), and features are made as indicators that switch on and off according to which tiles the current state falls in. Since one point straddles several tiles at once, neighboring states share features, and so generalization is smooth. Instead of tiles, radial basis functions (RBFs, bell-shaped features that fall off smoothly as you move away from the center) can cover the continuous surface similarly.
Once the features are made this way, the rest is exactly the linear Sarsa update seen earlier. As learning proceeds, the valley-shaped value surface grows sharper, and the policy of crossing the hill with momentum naturally emerges.
Should you bootstrap
A question that follows naturally from the incremental methods: what to set λ to. $\lambda = 0$ is full bootstrapping (TD), $\lambda = 1$ is no bootstrapping (MC), and in between is a compromise.
Silver shows graphs measuring performance across several domains (including mountain car) while varying λ. The conclusion is consistent. $\lambda = 1$ (pure MC) is almost always the worst, and the best-performing point is usually somewhere in the middle. The spectrum that Lecture 4 drew with bootstrapping and sampling as its two axes is thus borne out in practice with function approximation on top. Bootstrapping accepts bias to greatly reduce variance, and when it meets the noise of the approximator, the benefit of that variance reduction is especially large.
Baird’s counterexample: the moment of divergence
The good news ends here. When three things overlap (off-policy + linear approximation + TD), learning does not merely fail to converge; the parameters actually diverge to infinity. Baird’s counterexample is the concrete evidence. It is a small MDP made of only a few states, but running linear TD off-policy makes the weights grow larger with every iteration until the graph explodes. This is not a bug but a property of the algorithm.
Organized as a convergence table, it looks like this.
| Table lookup | Linear | Nonlinear | |
|---|---|---|---|
| On-policy MC | O | O | O |
| On-policy TD(0) | O | O | X |
| On-policy TD(λ) | O | O | X |
| Off-policy MC | O | O | O |
| Off-policy TD(0) | O | X | X |
| Off-policy TD(λ) | O | X | X |
The off-policy + linear + TD cell is exactly the X, the spot where Baird blows up.
To point at the root cause: the TD update is not the true gradient of any objective. On the surface $\Delta\mathbf{w} = \alpha\delta\,\mathbf{x}(S)$ looks like gradient descent, but $\hat v(S_{t+1}, \mathbf{w})$ inside the TD target also depends on $\mathbf{w}$, and we do not differentiate that part but freeze it like a constant (semi-gradient). Since it is not the true gradient, there is no guarantee of “going down the hill,” and when off-policy skews the data distribution, it can instead climb the hill.
The prescription is to make it follow the true gradient. Gradient TD descends the actual gradient of a well-defined objective, the projected Bellman error. Then convergence is recovered even with linear or nonlinear approximation on top of off-policy.
| Table lookup | Linear | Nonlinear | |
|---|---|---|---|
| Off-policy TD | O | X | X |
| Off-policy Gradient TD | O | O | O |
When we move to control the situation is one layer more subtle. Monte Carlo control or Sarsa with linear approximation usually does head near the optimum, but instead of stopping at exactly one point it keeps oscillating around the approximate optimum (chattering). This is because of the feedback where a slight change in the policy changes the value, and that value changes the policy again slightly. Linear Q-learning can outright diverge, and gradient Q-learning reins this in.
Batch methods: pool experience and solve at once
The incremental method (SGD) is simple and appealing but wastes samples, because it throws away the experience used in one update. The batch method asks the opposite: what value function best fits all the experience gathered so far?
If we take the experience as a collection of state-value pairs $\mathcal{D} = \{\langle s_1, v_1^\pi\rangle, \dots, \langle s_T, v_T^\pi\rangle\}$, least squares finds the $\mathbf{w}$ that minimizes the sum of errors over the whole set.
$$LS(\mathbf{w}) = \sum_{t=1}^{T}(v_t^\pi - \hat v(s_t, \mathbf{w}))^2$$Experience replay
This least-squares solution can also be obtained with SGD. Instead of using only new experience at each step, we repeatedly draw a pair at random again from the stored experience pool $\mathcal{D}$ and update.
- Sample from experience: $\langle s, v^\pi\rangle \sim \mathcal{D}$
- Apply the SGD update: $\Delta\mathbf{w} = \alpha\,(v^\pi - \hat v(s, \mathbf{w}))\nabla_\mathbf{w}\hat v(s, \mathbf{w})$
Repeating this enough converges to the least-squares solution $\mathbf{w}^\pi = \arg\min_\mathbf{w} LS(\mathbf{w})$. This is experience replay. Since the same experience is squeezed for use many times, sample efficiency rises, and since we draw it shuffled at random, the correlation between consecutive states (the non-iid problem) is also broken.
Linear gives a closed form
If the approximation is linear, $\hat v(s, \mathbf{w}) = \mathbf{x}(s)^\top\mathbf{w}$, there is no need even to iterate. The least-squares solution can be computed directly. At the minimum the expected update must be zero, so solving
$$\sum_{t=1}^{T}\mathbf{x}(s_t)(v_t^\pi - \mathbf{x}(s_t)^\top\mathbf{w}) = 0$$gives
$$\mathbf{w} = \left(\sum_{t=1}^{T}\mathbf{x}(s_t)\mathbf{x}(s_t)^\top\right)^{-1}\sum_{t=1}^{T}\mathbf{x}(s_t)v_t^\pi$$With $N$ features, this direct solution costs $O(N^3)$ because of the matrix inversion (with a Sherman-Morrison incremental update it is $O(N^2)$).
Not knowing the true value $v_t^\pi$ is the case here too, so into that place we plug a noisy sample. Using the return gives LSMC, using the TD target gives LSTD, and using the λ-return gives LSTD(λ). In each case it solves the fixed point of MC, TD, or TD(λ) directly as a closed form. Interestingly, even when incremental TD diverges off-policy, LSTD, which solves that fixed point directly, converges in the linear case.
Extended to control, this becomes least-squares policy iteration (LSPI). It repeatedly re-evaluates the stored experience $\mathcal{D}$ while changing the policy. Inside, it evaluates action-values off-policy by least squares with LSTDQ (on transitions produced by the old policy, it pulls toward the value of the successor action $A' = \pi_{\text{new}}(S_{t+1})$ that the new policy would choose), and outside, it improves greedily with $\pi'(s) = \arg\max_a Q(s, a)$, cycling until the policy stabilizes. Silver shows LSPI converging to the optimal policy in just a few iterations on a 50-state chain walk problem.
DQN: replay and fixed targets
DQN is what happened when the idea of experience replay met nonlinear approximation (deep neural networks) and exploded. DQN stabilizes learning with two devices.
- Experience replay: acting with an $\varepsilon$-greedy policy, it stacks transitions $(s_t, a_t, r_{t+1}, s_{t+1})$ into the replay memory $\mathcal{D}$. When learning, it draws minibatches from there at random. It breaks correlation and recycles samples.
- Fixed target network: when computing the Q-learning target, it uses not the currently learning parameters $\mathbf{w}$ but old parameters $\mathbf{w}^-$ that have been frozen for a while. This keeps the target from wobbling every step along with learning.
The loss is
$$L_i(\mathbf{w}_i) = \mathbb{E}_{s,a,r,s' \sim \mathcal{D}_i}\left[\left(r + \gamma\max_{a'}Q(s', a'; \mathbf{w}_i^-) - Q(s, a; \mathbf{w}_i)\right)^2\right]$$and it is minimized with a variant of SGD. The key point is that inside the target is $\mathbf{w}_i^-$ (frozen) and the prediction is $\mathbf{w}_i$ (learning).
How much each of these two devices contributes is shown clearly by an ablation experiment. These are the scores across five games with replay and the fixed target switched on and off.
| Game | Replay + fixed target | Replay only | Fixed target only | Neither |
|---|---|---|---|---|
| Breakout | 316.8 | 240.7 | 10.2 | 3.2 |
| Enduro | 1006.3 | 831.3 | 141.9 | 29.1 |
| River Raid | 7446.6 | 4102.8 | 2867.7 | 1453.0 |
| Seaquest | 2894.4 | 822.6 | 1003.0 | 275.8 |
| Space Invaders | 1088.9 | 826.3 | 373.2 | 302.0 |
Look at Breakout: 3.2 points with neither, 316.8 with both on. A hundredfold difference. Without the two stabilizing devices, the dangerous combination of nonlinear approximation + off-policy + bootstrapping collapses outright, and the moment the two devices are added, it comes to life.
From pixels to human level
Bolting this stabilized DQN wholesale onto Atari games is that result we saw in Lecture 1. The input is not the game rules or hand-crafted features but a stack of the raw pixels of the last four frames. The output is $Q(s, a)$ for each of the 18 joystick-and-button positions (the third architecture mentioned earlier: from one state, all action-values at once), and the reward is only the change in score at that step. The network structure and hyperparameters were fixed identically for all games. Without touching anything per game, it reached human-level skill on several games looking only at pixels.
Getting past a big problem that couldn’t fill even one table by parameter approximation, and holding that approximation in place with replay and fixed targets so it wouldn’t diverge: that is the bridge this lecture built. In the next lecture we move on to policy gradients, which parameterize the policy itself directly instead of approximating the value.