Deep Q-Networks

The big idea

A Q-table needs one entry for every state. An Atari screen is 210 by 160 pixels with a 128-colour palette, so the number of possible screens is beyond counting, and the agent will almost never see exactly the same one twice. A table cannot learn anything from a screen it has not seen. What you want is a function that looks at a new screen and says "this looks like the situations where firing paid off". That is a neural network, and a deep Q-networkA Q-learning agent whose action values come from a deep neural network that takes the state (for example, stacked game frames) as input and outputs one Q-value per action. (DQN) is Q-learning with the table replaced by one.

The catch is that the Q-learning update was never designed for this. Consecutive game frames are nearly identical, so the network sees long runs of correlated examples. And the target it is chasing, $r+\gamma \max Q(s^{\prime },a^{\prime })$, is computed by the same network it is updating, so every step moves the goalposts. Think of tuning a guitar string while someone keeps turning the reference string's peg. DQN's two tricks, experience replay and a target network, stop the reference from moving while you tune.

How it works

Step 1: Function approximation

Instead of a table entry $Q(s,a)$, use a network $Q(s,a;\theta )$ with weights $\theta$. For each transition $(s,a,r,s^{\prime })$ compute the same target as before and take a gradient step on the squared error:

Here ${\theta }^{-}$ are the weights used to compute the target; more on them in step 3. Because a network generalizes, one update changes the values of many similar states at once. That is the point, and also the danger.

Two design choices from the 2013 paper are worth copying. The input is the last four frames stacked, because one frame does not show which way things are moving: a single frame is not a Markov state ( RL fundamentals and MDPs ). And the network outputs one Q-value per action instead of taking the action as an input, so all actions are scored in one pass.

Step 2: Experience replay

Experience replayStoring past transitions (state, action, reward, next state) in a buffer and training on random minibatches drawn from it, instead of on each transition as it happens. stores every transition in a buffer (the 2013 paper kept the most recent one million frames) and trains on random minibatches drawn from it. The paper gives three reasons:

• Data efficiency. Each transition is used in many updates instead of one.
• Breaking correlations. Consecutive frames are nearly identical; random samples from a large buffer are not, which reduces the variance of the updates.
• Avoiding feedback loops. When learning from the latest data only, the current policy decides the next training data. If the greedy action is "move left", the data fills with left-side states, which can make learning oscillate or diverge. Replay averages over many past behaviours.

Replay requires an off-policy method, because the stored transitions came from older versions of the policy. Q-learning, with its max over next actions, is exactly that.

Step 3: A target network

The 2015 Nature paper added the second trick. Every $C$ updates, copy the network's weights into a separate target networkA frozen copy of the Q-network, refreshed every C updates, used only to compute the TD targets so they do not shift with every gradient step. ${\theta }^{-}$, and compute all targets with that frozen copy until the next refresh. The paper explains why: with one network, an update that increases $Q(s_t,a_t)$ often also increases $Q(s_{t+1},a)$ for all actions, and so increases the target too, which can lead to oscillations or divergence. Freezing the target adds a delay between an update and its effect on the targets.

Step 4: Other details that mattered

• Reward clipping. Game scores differ by orders of magnitude, so during training all positive rewards became +1 and negative ones -1. That let one learning rate work across games, at the cost of not telling small rewards from large ones.
• Error clipping. The Nature paper clipped the error term to between -1 and 1, which is the same as switching from a squared to an absolute loss for large errors.
• Frame skipping. The agent chose an action every 4th frame and repeated it in between (every 3rd in Space Invaders, where the lasers blink at a rate that made them invisible with 4).
• Annealed exploration. Epsilon fell linearly from 1 to 0.1 over the first million frames.

Going deeper

Code: a tiny DQN in numpy

import numpy as np

# A tiny deep Q-network in numpy. The agent sees its position as two numbers in [0, 1] on a
# 10 x 10 grid (no table: a network must generalize), moves up/down/left/right, and gets +1 for
# reaching the far corner. A 2-64-4 network predicts Q for all four actions in one pass.
G, GAMMA, MOVES = 10, 0.9, np.array([[-1, 0], [1, 0], [0, -1], [0, 1]])
feat = lambda s: np.asarray(s, float) / (G - 1)

def init(rng): return [rng.normal(0, 0.5, (2, 64)), np.zeros(64), rng.normal(0, 0.1, (64, 4)), np.zeros(4)]
def forward(w, x):
    h = np.tanh(x @ w[0] + w[1]); return h, h @ w[2] + w[3]
def sgd(w, x, a, y, lr=0.05):                         # one gradient step on (y - Q(x, a))^2
    h, q = forward(w, x)
    d = np.zeros_like(q); d[np.arange(len(a)), a] = np.clip(q[np.arange(len(a)), a] - y, -1, 1)
    dh = (d @ w[2].T) * (1 - h ** 2)
    for p, g in zip(w, [x.T @ dh, dh.sum(0), h.T @ d, d.sum(0)]): p -= lr * g / len(a)

def train(replay, target, steps=20000, seed=0):
    rng = np.random.default_rng(seed); w = init(rng); w_t = [p.copy() for p in w]
    buf, s = [], rng.integers(0, G, 2)
    for t in range(steps):
        eps = max(0.1, 1 - t / 10000)                 # anneal exploration from 1 to 0.1
        a = rng.integers(4) if rng.random() < eps else int(np.argmax(forward(w, feat(s))[1]))
        s2 = np.clip(s + MOVES[a], 0, G - 1); done = (s2 == G - 1).all()
        buf.append((feat(s), a, float(done), feat(s2), done)); buf = buf[-10000:]
        batch = [buf[i] for i in rng.integers(len(buf), size=32)] if replay else [buf[-1]]
        X, A, R, X2, D = map(np.array, zip(*batch))
        y = R + GAMMA * forward(w_t if target else w, X2)[1].max(1) * (1 - D)
        sgd(w, X, A, y)
        if target and t % 500 == 0: w_t = [p.copy() for p in w]   # refresh the frozen copy
        s = rng.integers(0, G, 2) if done or t % 20 == 19 else s2
    return w

def evaluate(w):                                       # greedy run from every cell: share reaching the goal
    ok, err = 0, []
    for start in np.ndindex(G, G):
        s = np.array(start)
        for k in range(30):
            if (s == G - 1).all(): ok += 1; break
            s = np.clip(s + MOVES[int(np.argmax(forward(w, feat(s))[1]))], 0, G - 1)
        dist = 2 * (G - 1) - sum(start)               # steps to the goal; true Q* = gamma^(dist - 1)
        if dist: err.append(abs(forward(w, feat(start))[1].max() - GAMMA ** (dist - 1)))
    return ok / G ** 2, np.mean(err)

for name, kw in [("online, no replay, no target", dict(replay=False, target=False)),
                 ("replay buffer only", dict(replay=True, target=False)),
                 ("replay + target network", dict(replay=True, target=True))]:
    res = [evaluate(train(seed=sd, **kw)) for sd in range(4)]
    print(f"{name:29s} cells reaching goal {np.mean([r[0] for r in res]):5.0%}   mean |Q - true| {np.mean([r[1] for r in res]):.3f}")

w, rng, moved = train(replay=True, target=True), np.random.default_rng(9), []   # the moving-target problem:
for _ in range(200):                                 # one update to Q(s, a) also shifts Q(s', .), its own target
    s = rng.integers(0, G - 1, 2); a = 3; s2 = np.clip(s + MOVES[a], 0, G - 1)
    before, q_sa = forward(w, feat(s2))[1].max(), forward(w, feat(s))[1][a]
    w2 = [p.copy() for p in w]; sgd(w2, feat(s)[None], np.array([a]), np.array([q_sa + 0.5]))
    moved.append(abs(forward(w2, feat(s2))[1].max() - before) / abs(forward(w2, feat(s))[1][a] - q_sa))
print(f"one step that raises Q(s, a) moves the next state's best Q by {np.mean(moved):.0%} as much")

online, no replay, no target  cells reaching goal   10%   mean |Q - true| 0.055
replay buffer only            cells reaching goal  100%   mean |Q - true| 0.026
replay + target network       cells reaching goal  100%   mean |Q - true| 0.029
one step that raises Q(s, a) moves the next state's best Q by 87% as much

The agent sees its position on a 10 by 10 grid as two numbers between 0 and 1, so there is no table: a small 2-64-4 network has to generalize. Reaching the far corner pays +1, the discount is 0.9, and each variant trains for 20,000 steps with epsilon annealed from 1 to 0.1, averaged over 4 seeds. Quality is the share of start cells from which the greedy policy reaches the goal, and the gap between the network's best Q and the true optimal value.

• Online updates on each transition as it happens reach the goal from only 10 percent of cells.
• Adding a replay buffer of 10,000 transitions with minibatches of 32 takes that to 100 percent, with a mean Q error of 0.026.
• Adding a target network (refreshed every 500 steps) also gives 100 percent, with error 0.029: on a problem this small it neither helps nor hurts. Its value shows up with large networks and long training, where the Nature paper found it made learning more stable.
• The moving-target effect is real even here. One gradient step that raises $Q(s,a)$ moves the best Q of the very next state by 87 percent as much, because neighbouring states share the network's weights. Without a frozen copy, the target runs away from the update.

The same agent in PyTorch is the usual starting point in practice; the course environment has no PyTorch, so the code runs the identical algorithm in numpy.

What came after

DQN's best-known weakness is that the max in the target overestimates values when estimates are noisy; Double DQN uses the online network to choose the next action and the target network to value it. Prioritized replay samples transitions with large errors more often, which the 2013 paper itself suggested as a direction. All of these keep the core recipe of this lesson.

Trade-offs

Common mistakes

• Training on transitions in the order they happen, with no replay: correlated updates and feedback loops.
• Computing targets with the network being trained and wondering why values oscillate or blow up.
• Feeding a single frame when motion matters; stack frames or add memory.
• Using DQN for continuous actions (a steering angle): the max over actions needs a finite list. Use policy-gradient or actor-critic methods instead.
• Reading the training reward curve alone. It is very noisy; the 2013 paper also tracked the average predicted Q on a fixed set of states as a steadier signal.

In the wild

Check yourself

Recap