The paper in four sentences
Earlier game-playing programs needed people to hand-pick what to look at, such as where the ball is. This paper gives the computer only the raw screen and the score.
A neural network looks at the last four frames and guesses, for each joystick move, how much score that move will lead to. The agent mostly picks the move with the best guess, and sometimes a random one to explore.
Every moment of play is saved in a large memory, and the network learns from random handfuls of old moments rather than only from what just happened, which makes learning much steadier.
With one design and one set of settings, trained separately on each of seven Atari games, it beats all earlier methods on six of them and an expert human on Breakout, Enduro and Pong.
Idea · §1
Learning from the screen and the score alone
The Atari 2600 was a home games console from 1977. Researchers had built a toolkit that lets a computer program play its games: the program sees the picture on the screen, presses joystick buttons, and is told the score. That is the whole interface.
This is a problem of reinforcement learning: learning by trial and error from rewards (here, points). It is hard for three reasons. The reward often comes long after the move that earned it. The picture is a big grid of pixels, not a neat description like "ball at position 40". And what the agent sees next depends on what it did, so its experience is a strongly connected chain of moments rather than a shuffled pile of independent examples.
Before this paper, the best Atari programs relied on features chosen by people, such as subtracting the background so only moving objects remain. The authors wanted a single program that works on every game without any of that, using the kind of deep network that had just transformed image recognition (see AlexNet).
TakeawayThe goal is generality: one learning method, no game-specific knowledge, raw pixels in, joystick moves out.
Idea · §2
Q-values: how good is each move from here?
The method is built on Q-learning, an idea from 1989. For every situation and every possible move, keep a number, the Q-value: "if I make this move now and play well afterwards, how much reward will I collect?" Rewards that come later are counted a little less than rewards now, by a discount factor such as 0.9 per step.
You learn Q-values by checking each guess against one step of experience. Make a move, see the reward and where you land, and compare your old guess with "reward just received + discount × best Q-value from the new place". Move the guess a bit toward that. Good news then spreads backwards, one step at a time, from the reward to the moves that led to it.
To keep discovering, the agent is ε-greedy: with a small probability ε it presses a random button instead of its current favourite. Try it below on a tiny maze, where the "Q-table" is small enough to draw.
An Atari screen has far too many possible pictures to keep one number per picture. So the paper replaces the table with a neural network that takes in the screen and outputs a Q-value for every button. That is the "deep" in deep Q-learning, and the source of the name Deep Q-Network, or DQN.
TakeawayA Q-value scores a move by the reward it eventually leads to. Q-learning improves every guess using the next step's guess, so reward news flows backwards in time.
Check yourself
- Why does the square next to the exit learn a high value before the start square does?
- Each update only looks one step ahead. The square beside the exit sees the reward directly; squares further away only learn once their neighbours' values have risen.
- What goes wrong with no exploration at all?
- The agent keeps repeating whatever it currently thinks is best, so it may never try the moves that lead to the reward and never learn they are good.
Idea · §4.1
A network that looks at four frames
The screen is shrunk to grey and cropped to an 84 × 84 square. A single picture cannot tell you which way the ball is moving, so the network is shown the last four frames stacked together. It also only chooses a move every fourth frame and repeats it in between, which lets it play roughly four times as many games for the same computing cost.
The network is small by today's standards: two convolutional layers (pattern detectors that slide across the image, the same idea as in LeNet), one layer of 256 units, and one output per joystick action, between 4 and 18 depending on the game. One pass through the network gives the Q-value of every action at once, so picking the best move is cheap.
One more trick keeps the settings shared across games: scores are clipped. Any gain counts as +1, any loss as −1. A game that awards 10 points per enemy and one that awards 1,000 then look the same to the learner, so a single learning rate suits them all. The price is that the agent cannot tell a big reward from a small one.
TakeawaySmall grey screens, four frames at a time, a compact network with one output per button, and clipped rewards: the same recipe for every game.
Idea · §4
Learning from a shuffled memory
Neural networks learn best from examples that are varied and shuffled. Play gives the opposite: frame after frame of nearly the same scene. A network that learns only from the latest moment keeps adjusting itself to whatever part of the game it is in, and forgets the rest.
The paper's fix is experience replay. Every step (screen, move, reward, next screen) is stored in a memory that holds the last one million frames. Each learning step picks 32 moments at random from that memory. Each experience gets reused many times, neighbouring moments no longer arrive together, and the network sees a mix of old and new situations.
The toy below shows the same effect on a simpler task: learning the shape of a curve while the "agent" drifts slowly back and forth along it, so consecutive examples are always neighbours.
TakeawayReplay turns a stream of look-alike moments into a shuffled pile of examples, which is what neural networks need to learn steadily.
Check yourself
- Name two benefits of experience replay the paper gives.
- Each experience can be used in many updates (data efficiency), and random sampling breaks the strong correlations between consecutive frames. It also averages over many past behaviours, which smooths learning.
- Why does learning only from the newest moment cause forgetting?
- Each update pushes the shared network toward the current situation, and nothing pushes back on the situations it is not seeing right now.
Idea · §5 · Table 1
Results, and what the sequel added
The agent was trained on seven games: Beam Rider, Breakout, Enduro, Pong, Q*bert, Seaquest and Space Invaders. Each game got its own fresh network, but the design and settings were identical (the only exception: in Space Invaders it acts every third frame instead of every fourth, so the flashing lasers are visible).
It beat every earlier learning method on six of the seven games, and beat an expert human on Breakout, Enduro and Pong. It was far below human on Q*bert, Seaquest and Space Invaders, games where you need a plan that stretches over a long time. The paper also shows that the network's predicted value rises when an enemy appears in Seaquest and falls once it is destroyed: it has learned something sensible about the game.
One honest caveat from the authors: there is no proof this kind of learning settles down. In practice, they saw no runs fall apart.
TakeawayOne general recipe learned several very different games from pixels. It was weakest where long-term planning matters, and its stability was improved in the 2015 version.
Abstract, restated
The first deep learning model to learn control policies directly from high-dimensional sensory input with reinforcement learning. A convolutional network, trained with a variant of Q-learning, maps raw pixels to estimates of future reward. Applied to seven Atari 2600 games from the Arcade Learning Environment with no change of architecture or learning algorithm, it outperforms all previous approaches on six games and surpasses a human expert on three. NIPS Deep Learning Workshop, 2013 (arXiv:1312.5602).
Section · §2 · Eqs. 1–3
Q-learning with a function approximator
The agent interacts with emulator ℰ, observing images xt, choosing actions at and receiving score changes rt. Since a single screen does not determine the state, the state is the sequence st = x1, a1, …, at−1, xt, giving a large but finite MDP. The return is Rt = Σt′ ≥ t γt′−t rt′, and the optimal action-value function satisfies the Bellman equation
A network Q(s, a; θ) ≈ Q*(s, a) is trained by minimising a sequence of losses, with ρ the behaviour distribution over states and actions:
The target is held at the previous iterate's parameters θi−1 while optimising Li, but in practice the paper optimises by single stochastic gradient steps, and with per-step updates "θi−1" is simply the current network. Unlike supervised learning, the targets depend on the weights. The method is model-free (it never models ℰ) and off-policy (it learns the greedy policy while following ε-greedy behaviour). The paper notes that Q-learning with nonlinear approximators was known to be able to diverge (Tsitsiklis and Van Roy, 1997), and that its method has no convergence guarantee.
Section · §4 · Algorithm 1
Experience replay
Initialise replay memory 𝒟 with capacity N
Initialise Q with random weights
for episode = 1 … M:
s₁ = {x₁}; φ₁ = φ(s₁)
for t = 1 … T:
with probability ε choose random aₜ, else aₜ = argmaxₐ Q(φ(sₜ), a; θ)
execute aₜ, observe rₜ and image xₜ₊₁
sₜ₊₁ = sₜ, aₜ, xₜ₊₁; φₜ₊₁ = φ(sₜ₊₁)
store (φₜ, aₜ, rₜ, φₜ₊₁) in 𝒟
sample random minibatch (φⱼ, aⱼ, rⱼ, φⱼ₊₁) from 𝒟
yⱼ = rⱼ if φⱼ₊₁ terminal
= rⱼ + γ maxₐ′ Q(φⱼ₊₁, a′; θ) otherwise
gradient step on (yⱼ − Q(φⱼ, aⱼ; θ))² Eq. 3
The paper gives three advantages over standard online Q-learning: each step of experience is potentially used in many updates; randomising over samples breaks the correlations between consecutive samples and so reduces update variance; and the behaviour distribution is averaged over many previous states, which smooths learning and avoids oscillation or divergence. The last point is specific to on-policy feedback loops: if the maximising action is "move left", the training data become dominated by left-side samples, which can trap learning in a bad feedback loop. Because replayed samples were generated by older parameters, learning must be off-policy, which motivates Q-learning.
The memory stores only the last N experiences and samples uniformly, so it does not distinguish important transitions. The authors suggest something like prioritised sweeping as future work.
Section · §4.1 · §5
Preprocessing, architecture and training
| Component | Setting in the paper |
|---|---|
| Raw frame | 210 × 160, 128-colour palette |
| φ | Grey-scale, downsample to 110 × 84, crop an 84 × 84 playing area (square because the GPU convolution code expected square inputs); stack the last 4 frames → 84 × 84 × 4 |
| Conv 1 | 16 filters 8 × 8, stride 4, ReLU |
| Conv 2 | 32 filters 4 × 4, stride 2, ReLU |
| Hidden | Fully connected, 256 ReLU units |
| Output | Linear, one unit per valid action (4 to 18) |
| Optimiser | RMSProp, minibatch 32 |
| Exploration | ε annealed linearly 1 → 0.1 over the first million frames, then fixed at 0.1 |
| Training | 10 million frames; replay memory of the 1 million most recent frames |
| Frame skip | k = 4 (3 for Space Invaders), the only per-game difference |
| Rewards | Clipped to {−1, 0, +1} during training |
The architecture takes only the state as input and outputs a Q-value for each action, so all actions are evaluated in one forward pass. Earlier neural Q-learners fed the action as an input and needed one forward pass per action. Frame skipping lets the agent play about k times as many games for roughly the same compute, since stepping the emulator is far cheaper than running the network.
Evaluation (§5.1, Fig. 2). Average episode reward per training epoch (50,000 minibatch updates, about 30 minutes of training) is noisy. A smoother metric is the average of maxa Q over a fixed set of states collected by a random policy before training; it rises steadily on all games. The authors report no divergence in any experiment. Fig. 3 shows the predicted value tracking events in a 30-frame Seaquest clip: it jumps when an enemy appears (A), peaks just before a torpedo hits (B) and falls back when the enemy disappears (C).
Section · §5.3 · Table 1
Results on seven games
Table 1 compares average scores (ε = 0.05) with Sarsa and Contingency, two learners on hand-engineered features from Bellemare et al. (2013) and Bellemare et al. (2012); with HyperNEAT (Hausknecht et al.) using hand-designed object detectors ("HNeat Best") or the emulator's special 8-channel object-label representation ("HNeat Pixel"); and with a human expert's median score after around two hours of play. "Best" rows report the single best episode.
DQN outperforms all other learning methods on six games; on Space Invaders, HNeat Best (1,720) beats DQN's average (581) and even its best episode (1,075), though HNeat Best relies on hand-designed object detectors, and the authors note that HNeat's deterministic policies are unlikely to cope with perturbations. DQN exceeds the human expert on Breakout, Enduro and Pong, is close on Beam Rider, and is far behind on Q*bert, Seaquest and Space Invaders, which the authors attribute to strategies that extend over long time scales.
Check yourself
- Why is the average maximum Q on held-out states a better progress measure than episode reward?
- Episode reward is very noisy because small weight changes alter which states the policy visits. The Q estimate on a fixed state set changes smoothly, so it shows learning progress more clearly.
- Why must DQN use an off-policy method?
- The minibatches come from the replay memory and were generated by older versions of the policy, so the learner must be able to learn about the current greedy policy from another policy's data.
- What does reward clipping cost?
- The agent cannot distinguish rewards of different magnitude, so it may prefer frequent small rewards over rare large ones.
Section · §6 and lineage
Limitations and lineage
- No stability guarantee. Bootstrapped targets from the same network that is being trained, plus nonlinear approximation and off-policy data, can diverge in principle. The paper observed no divergence on its seven games.
- Uniform replay. All transitions are equally likely to be replayed, and the oldest are overwritten first.
- Long horizons. Performance is poor on games needing extended strategies (Q*bert, Seaquest, Space Invaders).
- Reward clipping removes magnitude information.
- Small evaluation. Seven games, one run each, without error bars.
Reference
Glossary
- MDP
- Markov decision process: states, actions, transition probabilities and rewards, with the future depending only on the current state.
- Q(s, a)
- Action value: expected discounted return after taking a in s and acting optimally (for Q*) thereafter.
- γ
- Discount factor weighting future rewards.
- Bootstrapping
- Using the current estimate of the next state's value inside the learning target.
- ε-greedy
- Act greedily with probability 1 − ε, uniformly at random otherwise.
- Off-policy
- Learning about one policy (greedy) from data generated by another (ε-greedy, older parameters).
- Experience replay
- Storing transitions and training on random minibatches drawn from the store.
- Frame skip
- Repeating the chosen action for k frames.
- ALE
- Arcade Learning Environment, the Atari 2600 emulator interface used for evaluation.