Deep Q-Learning

The previous note ended with a table of twelve numbers: two actions in each of six states, solved exactly with algebra because the rewards and the transitions were known in advance. Neither luxury survives contact with a real problem. A lander falling toward a pad has a state made of real numbers, so there is no table to fill in, and it does not know what a thruster does until it fires one.

This note is the bridge. The Bellman equation stops being an identity to solve and becomes a training target for a neural network, which turns the whole of reinforcement learning into a supervised learning problem that keeps rewriting its own labels.

In one line. Approximate $Q(s,a)$ with a network. For a stored transition $(s,a,r,s')$, the Bellman equation says the answer should be $y = r + \gamma \max_{a'} Q(s',a')$ — so use that as the label and fit by least squares. Act $\varepsilon$-greedily so the data keeps improving, replay old transitions so the batches are not correlated, and compute the target with a delayed copy of the network so the labels hold still long enough to be learned.

Discrete states, and why they run out

A discrete state space is a finite set — the six cells of the rover's strip. The state is an index, $V(s)$ and $Q(s,a)$ live in arrays, and exact dynamic programming applies. It is simple and it does not scale: describing the world by which of six boxes you are in is a very coarse description of anything.

Continuous state

A ground vehicle is better described by a vector of real numbers — where it is, which way it is pointing, and how fast each of those is changing:

$$ s = \begin{bmatrix} x \ y \ \theta \ \dot{x} \ \dot{y} \ \dot{\theta} \end{bmatrix} \qquad\qquad \text{a helicopter needs twelve: } \; \begin{bmatrix} x & y & z & \phi & \theta & \psi & \dot{x} & \dot{y} & \dot{z} & \dot{\phi} & \dot{\theta} & \dot{\psi} \end{bmatrix}^{\mathsf{T}} $$

There are now infinitely many states, so no table can be stored. The obvious escape — chop each axis into bins and go back to a table — fails for a reason worth seeing rather than asserting:

The only way forward is function approximation: represent $Q(s,a)$ as a parametrised function — linear features, a kernel, or a neural network — and fit its parameters. A network with a few thousand weights covers the whole space, and, unlike a table, what it learns at one state transfers to the states nearby.

Choosing a Markov state

The state must satisfy the Markov property to be usable:

$$ P\left(S_{t+1} \mid S_t = s,\, A_t = a,\, \text{history}\right) = P\left(S_{t+1} \mid s, a\right). $$

This is a design constraint, not a fact of nature. Position alone is not Markov for a moving vehicle — where it will be next depends on how fast it is going — so the velocities have to be in the state. Where sensors are noisy the raw reading is not Markov either, and a state estimator (a Kalman filter, say) is used to produce something that is.

The lunar lander

State and actions

A 2-D lander must touch down between two flags. The state is eight numbers:

The action space is discrete — four choices: do nothing, fire the left thruster, fire the main engine, fire the right thruster. Continuous state with discrete actions is exactly the combination value-based methods handle well, which is why this task is the standard example.

The shaped reward

The objective is the usual one — find $\pi$ maximising $\mathbb{E}\pi\left[\sum_t \gamma^t R\right]$ — with $\gamma \approx 0.985$, high enough that a landing several hundred steps away still carries real weight. That claim is checkable: the share of the total discounted weight that falls within the first $N$ steps is $1 - \gamma^N$, so

Approximating $Q$ with a network

Two arrangements are used, and it is worth knowing both because the slides show one and every implementation uses the other:

• State and action in, one value out. Concatenate the state with a one-hot code for the action — $8 + 4 = 12$ inputs — pass it through two hidden layers of 64 units, and read one number, $Q(s,a)$. Choosing an action means four forward passes, one per action, then taking the largest.
• State in, one value per action out. The network is $8 \to 64 \to 64 \to 4$ and returns the whole vector $\left[Q(s,\text{nothing}), Q(s,\text{left}), Q(s,\text{main}), Q(s,\text{right})\right]$ in a single pass. Same function, one quarter of the compute; this is what DQN actually does.

Either way, acting greedily means $a^\ast = \arg\max_a Q_\theta(s,a)$.

Turning Bellman into supervised learning

The target

The Bellman equation from the previous note says what $Q(s,a)$ ought to equal. Take that right-hand side and call it a label:

and now it is ordinary regression: fit $f_{W,B}(x) \approx y$ by least squares. The strange part is that the labels are produced by the network being trained — §8 is about the trouble that causes.

Why one step reaches the whole future

The target only looks one step ahead, yet a lander is rewarded hundreds of steps later. $Q(s', a')$ is defined by the same equation, so its own value already contains the step after that, and so on:

$$ Q(s_t, a_t) \approx r_t + \gamma r_{t+1} + \gamma^2 r_{t+2} + \cdots $$

Information about a distant reward travels backwards one link per update. It is slow, and it is why deep RL needs so many episodes — but it does arrive.

Building the targets, worked

Three transitions from the replay buffer, $\gamma = 0.99$:

The three training pairs are $x^{(i)} = \left(s^{(i)}, a^{(i)}\right)$ against $y = [\,1.88,\; 1.191,\; 100\,]$, and the network is updated by gradient descent on

$$ L(\theta) = \frac{1}{3}\sum_{i=1}^{3}\left(Q_\theta\left(x^{(i)}\right) - y^{(i)}\right)^2 . $$

Nothing here is specific to reinforcement learning any more — it is the mean squared error of note 1, fitted to labels that happen to have been manufactured by the Bellman equation.

The learning loop

The algorithm

In the sizes Ng uses for the lander: keep the most recent 10,000 transitions, and train on random minibatches of 1,000 of them.

initialize Q-network parameters θ randomly
D = empty replay buffer (capacity 10,000)

loop over episodes:
    reset the environment, observe s
    repeat for each step:
        a = epsilon_greedy(Q_θ, s)              # explore or exploit
        execute a, observe r and s'
        store (s, a, r, s', done) in D          # oldest tuple falls out

        sample a minibatch of N = 1000 from D
        for each sample:  y_i = r_i                         if done
                          y_i = r_i + γ max_a' Q(s'_i, a')  otherwise
        take a gradient step on  (1/N) Σ (Q_θ(s_i, a_i) − y_i)²
        every K steps:  θ̄ ← θ                  # refresh the target network

Why a replay buffer

Two reasons, both about the data rather than the algorithm:

• Consecutive transitions are almost the same. A lander's state changes slightly per frame, so a batch of consecutive steps is one situation repeated — nothing like the independent samples that gradient descent assumes. Sampling randomly from a large buffer breaks that correlation.
• Experience is expensive. Every transition costs a step of simulation. Storing them lets each one be learned from many times instead of once.

Exploration and $\varepsilon$-greedy

Why act randomly on purpose

Early in training $Q_\theta$ is nonsense — it was initialised at random. An agent that always takes $\arg\max_a Q_\theta(s,a)$ will act on that nonsense, and here is the trap: if the network happens to underrate firing the main engine, the agent never fires it, never sees the reward it would have produced, and never gets the data that would correct the estimate. The mistake is self-sealing.

The fix is to sometimes act at random. With probability $1-\varepsilon$ take the greedy action; with probability $\varepsilon$ pick uniformly among all actions.

The probabilities

With $K$ actions, the greedy one is also in the random draw, so:

$$ \Pr(a^\ast \mid s) = 1 - \varepsilon + \frac{\varepsilon}{K}, \qquad \Pr(a \ne a^\ast \mid s) = \frac{\varepsilon}{K}. $$

Worked, with the network outputting $[\,Q(s,\text{nothing}), Q(s,\text{left}), Q(s,\text{main}), Q(s,\text{right})\,] = [\,1.2,\, 0.7,\, 0.5,\, 1.1\,]$, so the greedy action is nothing, and $\varepsilon = 0.05$ with $K = 4$:

$$ \Pr(\text{nothing}) = 1 - 0.05 + \tfrac{0.05}{4} = 0.9625, \qquad \Pr(\text{left}) = \Pr(\text{main}) = \Pr(\text{right}) = \tfrac{0.05}{4} = 0.0125 . $$

So $96.25\%$ exploit and $3.75\%$ explore, split evenly over the three non-greedy actions.

Annealing $\varepsilon$

The right amount of exploration changes over training: high at the start, when the estimates are worthless, and low later, when they are not. So $\varepsilon$ is decayed —

$$ \varepsilon_t = \max\left(\varepsilon_{\min},\; \varepsilon_{\max} - (\varepsilon_{\max} - \varepsilon_{\min})\tfrac{t}{T}\right) \quad\text{(linear)}, \qquad \varepsilon_t = \varepsilon_{\min} + (\varepsilon_{\max} - \varepsilon_{\min})e^{-t/\tau} \quad\text{(exponential)}, $$

typically from $\varepsilon_{\max} \approx 1.0$ down to $\varepsilon_{\min}$ between $0.01$ and $0.05$.

Off-policy, and why that is fine. The agent behaves $\varepsilon$-greedily but the target uses $\max_{a'}$ — it learns the value of acting optimally while actually acting randomly some of the time. That mismatch is what "off-policy" means, and it is the property that lets a replay buffer full of old, worse-policy transitions still be useful.

The moving target, and how to slow it down

Target networks

There is something circular in §4: the labels $y = r + \gamma \max_{a'} Q_\theta(s',a')$ are computed from the network being updated. Every gradient step changes the labels, so the network is chasing a target that runs away from it — which oscillates and sometimes diverges.

The standard fix is a target network $Q_{\bar\theta}$, a delayed copy used only for computing labels:

Soft updates (Polyak averaging)

Copying $\bar\theta \leftarrow \theta$ outright moves the targets abruptly every $K$ steps. A gentler version blends instead of replaces:

• Typical values are $\tau \in [0.005,\, 0.02]$.
• $\tau = 1$ is the hard update — an instant copy.
• Smaller $\tau$ tracks more smoothly but more slowly; too small and the target is stale.

The trade is easiest to see by asking what each rule does when the online network moves. Let $\theta$ jump once, from $0$ to $1$, and watch $\bar\theta$ follow:

Neither column of that picture is obviously right, which is why both are in use. What they share is the property that matters: the labels move slower than the network being fitted, so each gradient step is aimed at something that has not already moved.

Pitfalls

• $\varepsilon$ too small too early starves exploration; too large too late leaves the policy noisy and the score jumping around long after it should have settled.
• Break ties in $\arg\max$ at random. With ties broken by index, an untrained network — whose outputs are often equal — silently prefers action 0.
• Keep the buffer big enough and the target updates slow enough; add gradient clipping if the loss spikes.
• Do not forget the done case. Bootstrapping past the end of an episode adds the value of a state that never happened, and it inflates every value that leads to a terminal state.

Where this goes next

This completes the third course, and the arc of these notes: from fitting a line through classification, networks, evaluation and trees, to unsupervised structure, recommenders, and finally agents that generate their own data.

Deep Q-learning is the beginning of deep RL rather than the end of it. The natural next steps, in roughly the order they are usually met:

• Better value estimates — double DQN removes the systematic overestimation caused by taking a $\max$ over noisy values; duelling architectures split $Q$ into a state value and an action advantage; prioritised replay samples surprising transitions more often.
• Continuous actions. $\arg\max_a$ is unusable when $a$ is a real vector — a helicopter's control stick, not four buttons. Policy-gradient and actor-critic methods (PPO, DDPG, SAC) learn the policy directly instead of deriving it from $Q$.
• Model-based control. When the dynamics are known or can be learned, planning against the model (LQR, MPC) is far more sample-efficient than learning from scratch.

Backwards from here: foundations has the returns, policies and Bellman equation this note fits a network to; the network reference has the network itself; and model development is still the right place to look when training goes wrong.