Study guide · Robotics & reinforcement learning · 2013

Playing Atari with Deep Reinforcement Learning

Volodymyr Mnih et al. · NeurIPS 2013 workshop

Can one learning program, given nothing but the screen pixels and the score, learn to play several different video games? This short workshop paper says yes: a convolutional network trained by Q-learning, with a memory of past experience to learn from, plays seven Atari games with the same settings and beats an expert human on three of them.

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).

Everyday pictureImagine being handed a game you have never seen, with the instructions in a language you cannot read. All you can do is watch the screen, wiggle the joystick and notice when the number in the corner goes up. That is exactly the situation this program is in, for every game.

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.

Tabular Q-learning (learning rate 0.5, discount 0.9) on a toy maze, not from the paper. The agent starts at S; the exit (+1) ends the game, the pit (−1) ends it badly, and each step costs nothing. Each square shows the best Q-value there, and the arrow is the move the agent currently prefers. Right: steps taken per game. Set ε to 0 from the start and the agent may never find the exit; with some exploration the value of the exit spreads back to S.

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.

Everyday pictureA single photo of a tennis match cannot tell you where the ball is heading; a flick-book of four photos can. The network is given a tiny flick-book each time it decides.

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.

An illustrative toy, not the paper's experiment. The dashed curve is the true value along a line; the agent's position (dot) sweeps slowly left and right, giving one noisy sample per step. Both learners fit the same 7-term smooth curve with the same learning rate. Left: learns only from the newest sample, so it bends to fit wherever the agent is now. Right: stores the last 1,000 samples and learns from 4 random ones per step. At high learning rates the gap is large.

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.

Later refinementJust over a year later, the same team published the Nature version. It added a target network (a frozen copy of the network that supplies the "best Q-value from the next screen" and is refreshed only every few thousand updates), a bigger network, and much longer training, and tested on 49 games. Later work fixed DQN's habit of overestimating values (Double DQN, 2015), replayed surprising memories more often (prioritised replay, 2015, an idea this paper already suggests), and combined many such fixes (Rainbow, 2017).

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.

Follow the idea

Led to: Nature DQN (2015)