Playing Atari with deep reinforcement learning

1Values from the frames

Besides the score, the agent sees only the game's frames, and the figures' agent looks at the last two. A network turns that pair into a value for each move: the points to expect from making it and playing well after, later points counting for less.

The figure shows the network that section 3's run trains. Drag the ball: where you drop it is where it is now, on the later frame, and the way you moved it sets where it was a step before, drawn faint.

• The bars are the network's values of the three moves, and the blue arrow beside the paddle points to the move worth most.
• The short red line across each bar is that move's exact value under best play, computed from the game's rules, which the network never sees.
• The One frame button shows the values of a network whose input is only the later frame.

Where a move decides a hit, the network's best move hits; moves seldom made in a situation keep rough values. The rest of this section builds what the figure shows: the state the network sees, the values it aims at, and the network itself.

The paper's agent plays through an emulator of the console, ℰ. At each time step t it picks an action a_t from 𝒜 = {1, …, K}, here K = 3: up, stay and down; it sees an image x_t ∈ ℝ^d, the pixels of the frame (here d = 48, each 0 or 1); and it receives a reward r_t, the change in the score. The rest of this note's game:

• There are 12 serves, from the left wall on any of the 6 rows, rising or falling, with the paddle on rows 2 and 3; within a step the paddle moves before the ball.
• A rally is cut at 10 hits: the cut is not an ending, and the agent learns as if play went on.

With One frame, a ball beside the paddle gets the same values rising or falling, though the move that hits it depends on which: one frame does not show the whole situation.

So the paper takes as the state the whole sequence of frames and actions so far,

The sequence holds everything that decides what comes next, and since every episode of the paper's games ends, there are finitely many sequences: a large but finite problem, to which the earlier notes' methods apply.

A network needs an input of fixed length, so the paper feeds it φ(s_t), the last four frames, each shrunk to 84 × 84 gray pixels. In this note's game the ball moves one pixel diagonally per step, in a straight line between bounces, so two frames show where it is going, except at the serve, where the first frame counts twice:

The agent aims at the return, the rewards from t on, each discounted by γ for every step it comes later (the paper gives no value; the figures use γ = 0.9):

and the value of an action is the largest expected return after it, over all ways of playing on,

The figure's red lines are Q^*, which the page computes exactly for this game, by the value iteration of the model-based note over the game's 552 true situations, which the agent, knowing neither the rules nor the state, cannot do. Since the cut is not an ending, these are the values of a rally that never ends:

With a value for each sequence, or each pair of frames, the agent would learn nothing about a pair it had not seen, and while this game has only 1,336 pairs, an Atari game has far too many. So the paper estimates Q^* with weights θ, as the approximation notes did:

A linear estimate like those notes' fails on the pixels. Each lit pixel adds its own weight, so the estimate cannot say that moving up is good when the ball is above the paddle and bad when it is below, wherever the two are. A network learns such combinations from the pixels.

A network is built in layers, each multiplying what it receives by a table of weights and passing the result through a fixed function (the network of the word2vec note). The figures' network has two layers:

• 96 inputs, the pixels of the two frames;
• 32 hidden rectifier units, max(0, z), which keep a positive number and turn a negative one into 0;
• and 3 outputs, one value for each move:

with a 1 in front of φ and of the hidden layer, so that the first columns of W₁ and W₂ hold the biases, as in the word vectors note; θ is W₁ (32 × 97) and W₂ (3 × 33), 3,203 weights; the paper's Q(s, a; θ) is computed as Q(φ(s), a; θ).

One output per move is the paper's choice: earlier networks took the action as an input and needed a pass for each action; this one gives every move's value in one pass. In the earlier notes' notation:

2Learning from its own estimates

Q^* obeys the Bellman optimality equation of the Q-learning note, here in the paper's notation (its equation 1):

Value iteration, which the model-based note ran on the values of states, turns it into an update repeated iteration after iteration, and converges to Q^*:

It needs a value for every sequence, though, and learns nothing about one sequence from another.

The paper keeps value iteration's shape with a network. At iteration i it fits the weights θ_i to targets computed with the weights of the iteration before, θ_i−1, by making a loss small, a number that says how wrong the estimates are, as the VE of the prediction note did (the paper's equation 2):

where the target is

• ρ(s, a) is the paper's behavior distribution, how often each sequence and action come up in play (the prediction note's μ, not the ratio ρ of the n-step note).
• θ_i−1 is not a second network: it is the weights before a step, and θ_i the weights the step changes.

So the targets depend on the weights. In supervised learning each example's target, its label, is fixed before learning begins. Here every step that changes the weights can change the targets too.

The figure takes the game's first step from a serve: the paddle stays, the reward is 0, and the next pair of frames is φ₂. The network learns Q(φ₁, stay; θ) from that transition alone, one gradient step on L_i per iteration, in two runs, the value in blue and its target in red:

• the left one keeps the first target, as a label would be kept;
• the right one computes it again before every step, from the weights as they stand.

The target moved because one network computes both values:

1. The step that raised staying in φ₁ changed staying's output weights, which every pair of frames uses, and hidden units fed by pixels the two frames share; so it raised staying in φ₂ too, by about four fifths as much.
2. Moving down had been φ₂'s largest value, just above staying; after the step, staying is, so the target borrows the very value the steps raise.
3. Times γ = 0.9, the target gains about 0.73 of the value's gain, so the gap shrinks by about a fifth per step until the two meet at 0.329, a fixed point, as the TD fixed point of the prediction note was for a linear estimate.

Had a step raised the value of the next pair of frames by more than 1/0.9 times as much as the value it updates, the target would have run ahead, and both would have grown without bound: learning from its own estimates can diverge, as section 4 takes up again. Only a final transition's target, the reward −1, cannot move.

To make L_i small, the paper follows its gradient. With θ_i−1 held fixed it is (the paper's equation 3, with a factor added):

The prediction note's ½ gave the same step, w ← w − ½α∇[…]² = w + α[…]∇v (prediction note), and holding θ_i−1 fixed makes it what that note called a semi-gradient: the step follows how the weights move the estimate, and ignores how they move the target. For a network, ∇_θQ is computed layer by layer, from the output back, by the chain rule of the linear classifiers note, a computation called backpropagation.

Rather than computing the expectations, the paper takes stochastic gradient steps; with a single sample of ρ and of ℰ after every time step, the update is

This is Q-learning: with a table, a weight for each sequence and move, ∇_θQ is 1 for the pair updated and 0 for every other, and the step is the update of the Q-learning note; with the next move's value in place of the maximum, it would be semi-gradient Sarsa.

Like the methods of the TD note, it is model-free: it learns from samples of ℰ and builds no model of it. And it is off-policy, as in the Q-learning note: it learns about the greedy policy, a = argmax_a Q(s, a; θ), while it plays ε-greedy. The paper writes max there, and in its algorithm, where it means argmax.

3Deep Q-learning

Deep Q-learning adds one thing to that update: a memory. After every step the agent stores the transition, e_t = (s_t, a_t, r_t, s_t+1), in a data set (the algorithm stores each s as its φ, all the network reads),

the replay memory, which keeps the last N transitions, pooled over many episodes.

That lies between the prediction note's one state per step and the TD note's batch updating. Dyna-Q, in the model-based note, also drew remembered steps at random, but kept only the last outcome of each pair. Section 4 says why the draws are random.

The algorithm

Deep Q-learning with experience replay, for a network Q with weights θ, a memory of N transitions, minibatches of 32, a step size α and an ε that falls over time, as the Monte Carlo note let it shrink, for M episodes:

1. Start with 𝒟 empty, with room for N transitions, and θ at random.
2. At the start of each episode, observe the first frame x₁, and set s₁ = x₁ and φ₁ = φ(s₁).
3. With probability ε choose a random action a_t; otherwise a_t = argmax_a Q(φ_t, a; θ).
4. Take a_t, observe r_t and x_t+1, and set s_t+1 = s_t, a_t, x_t+1 and φ_t+1 = φ(s_t+1).
5. Store (φ_t, a_t, r_t, φ_t+1) in 𝒟, dropping the oldest transition once it holds N.
6. Draw a minibatch of transitions (φ_j, a_j, r_j, φ_j+1) at random from 𝒟, and set each one's target y_j (below).
7. Take one gradient step on their squared errors, with the targets held,
   θ ← θ + α · 132 Σ_j[y_j − Q(φ_j, a_j; θ)] ∇_θQ(φ_j, a_j; θ)
   If φ_t+1 is terminal, or the rally has reached the game's cut, start the next episode at step 2; otherwise go back to step 3.

The targets of step 6 are

Here j counts the transitions drawn, where section 2's i counted iterations; the targets use θ before the step, section 2's θ_i−1, and α absorbs the 2 of the squared error. A rally cut at 10 hits is not terminal, so its last target still adds γ times the value of the next pair of frames. The paper calls these networks deep Q-networks, DQN.

The figure runs these steps on the game from random weights, with the settings of the table, in three regions:

• At the top, the game, with section 1's bars and arrow; the move just chosen fills its row yellow, and the bars a target borrows are outlined red.
• In the middle, the memory, as cells, then as a strip; green numbers or ticks mark each step's draws.
• At the bottom, one drawn transition: its two pairs of frames and a gauge from its value (blue) to its target (red), with a green marker where the step takes it; one step moves a value too little to see on the bars.

Each press is one line of the steps above, as in the Sarsa figure of the control note; episode 1 is played in full, episode 2 up to its first hit, and then the figure skips to moments where something new is learned.

Each step lowered the squared error of its 32 draws taken together, but not of each draw: about a third of the drawn transitions moved away from their targets in a step, pulled by the others.

4Why experience replay

Sarsa, Q-learning and TD-Gammon, an earlier program that learned backgammon with a network, used each step once, in the order it came. A memory changes three things, the paper's advantages:

1. Each step is used in many updates: transition 12 of section 3's figure was drawn 243 times while it stayed in the memory.
2. Consecutive steps are strongly correlated, the opening's second obstacle, so learning from them in order chases the current rally; draws from the last 10,000 steps break the correlation and lower the variance of the updates.
3. When an agent learns from the data its current weights produce, the weights choose the next data, the opening's third obstacle: a network that prefers moving up trains mostly on frames with the paddle at the top. Such loops can trap the weights or make them diverge; replay averages ρ, the behavior distribution, over many past behaviors.

Replay makes learning off-policy, in section 2's sense, whether one wants it or not: a drawn transition holds a move that older weights chose, often at random. That decides the method:

Q-learning's one-step target needs no correction for the other policy, as the Q-learning note showed: given the pair it updates, the reward and the next frame do not depend on who chose the move. The paper also names the limits of its memory: it keeps only the last N transitions, dropping the oldest whatever they hold, and draws every transition alike, though in this run only 3 or 4 of each 32 draws carry a nonzero reward; it suggests favoring the transitions there is most to learn from.

The figure runs section 3's agent from 16 seeds for 30,000 steps, with three ways of choosing each step's minibatch:

Every 250 steps a check plays the 12 serves with no random moves, and each curve counts the agents that hit ten times from every serve. Replay is blue, the others faint, Latest only dashed.

Replay's gain is that it stays stable at a step size large enough to learn fast: at three times the run's α, every replay agent still learns, while no agent without replay does, and on more than half of them the values blow up. The loop of advantage 3 is not the cause: with every move random, half the Last 32 agents blow up just the same. Without replay, each step learns from the last few transitions, nearly the same frames, and pushes the same weights again and again, toward targets those weights set. Drawn at random from 10,000 steps, the pushes average out.

The paper cites results showing that Q-learning can diverge:

• when its estimate is not linear, such as a network (Tsitsiklis and Van Roy, 1997);
• or when it learns off-policy (Baird, 1995).

It offers no guarantee that its own method converges, and it reports that none of its runs diverged.

5Summary

The key ideas next to their NumPy equivalents, for the figures' network and settings. In the code:

• x_prev and x are the last two frames, w1 and w2 the weights (biases in the first column), theta both as one vector, and q the three values.
• rs holds the rewards of an episode from t on, and g is the return R_t.
• In the minibatch rows, r, done and q_a hold the 32 rewards, whether each next pair is terminal (1 or 0) and the values of the moves taken; q_next holds each next pair's values and grad_q the gradient of each Q(φ_j, a_j; θ), as rows, which backpropagation computes.

The step is the figures' plain gradient step, α absorbing the 2 of the squared error.