Deep Q-Network

From a fixed table to a network that learns on its own

DQN combines two components: reinforcement learning, and specifically a long-standing method within it called Q-learning, with a convolutional neural network, the kind of network usually used for image recognition. In classic Q-learning, the system keeps a table: for every state and every possible action, it estimates how much reward it can expect in the future. That table explodes very quickly once there are too many possible states, which is exactly the situation in a computer game, where every frame on screen is a different state. DQN replaces the table with a neural network: instead of pulling a value from a row in a table, the network takes the raw image of the screen and computes an estimate for every possible action.

2013: the first experiment, seven Atari games

On 19 December 2013, researchers at DeepMind Technologies — Volodymyr Mnih and six other researchers — published a paper titled Playing Atari with Deep Reinforcement Learning. They tested the method on only seven Atari 2600 games: Beam Rider, Breakout, Enduro, Pong, Q*bert, Seaquest, and Space Invaders. The raw image went through preprocessing: converted to grayscale, downsampled, and cropped to an 84-by-84-pixel playing area; the last four frames were stacked together as a single input, so the network could also infer direction of motion. The network itself had two convolutional layers and one fully connected layer, and output an estimate for every valid action in the game (between four and 18 actions, depending on the game). According to the paper, the method outperformed all previous approaches on six of the seven games, and surpassed a human expert on three of them: Breakout, Enduro, and Pong.

The memory that prevents forgetting: experience replay

A key innovation of DQN is "experience replay": instead of learning from every step and then forgetting it, the network stores a pool of up to a million recent steps (state, action, reward, and next state), and samples a random batch from it on every training round. The original paper gives three advantages of this: it lets every step be used multiple times in different weight updates, it breaks the strong correlation between consecutive steps in sequence (which, if kept, would increase training variance), and it smooths the distribution of the data, which helps prevent oscillation or divergence during training. This 2013 version did not yet have a separate "target network" — an addition that arrived only in the later version.

2015: Nature, 49 games, and the target network

On 25 February 2015 (in the issue dated 26 February), a follow-up paper, Human-level control through deep reinforcement learning, was published in the journal Nature by a larger group of researchers at Google DeepMind in London, again led by Volodymyr Mnih. This version added a new stability component: a "target network," a separate copy of the network that is updated only once in a while, so that the evaluation the network converges toward doesn't chase itself on every single step. This time the system was tested on 49 Atari games, not seven, with the exact same algorithm, architecture, and hyperparameters across all the games, with no manual tuning per game. The network itself grew, too: instead of two convolutional layers and one fully connected layer as in 2013, the Nature version had three convolutional layers (32, 64, and 64 filters) and one fully connected layer with 512 units. According to the paper, DQN outperformed previous machine learning methods on 43 of the 49 games, and reached over 75% of the score of a professional human games tester on more than half of them — 29 of 49. The normalized score is computed as 100 times ((DQN's score minus a random-play score) divided by (the human player's score minus a random-play score)), so that 0% represents random play and 100% represents the human tester's level. This version also had a known flaw: Q-learning tends to overestimate action values, because the same network both picks the best action and estimates its value. In 2015, van Hasselt, Guez, and Silver published an improvement called Double DQN, which separates those two jobs and reduces the bias.

Where DQN failed: games that require long-term planning

Not every game succeeded equally well. According to coverage published the week the Nature paper came out, DQN "fared poorly on games such as Montezuma's Revenge, which requires a long-term planning strategy" — a game where the reward arrives only after a long sequence of correct actions, not after every step individually. The method that succeeded well on games with frequent, clear reward, like Breakout and Video Pinball, ran into trouble when the reward was sparse and distant. This limitation — low efficiency when planning ahead is needed without frequent feedback — remained a major challenge in reinforcement learning long after DQN.

The impact: from Atari to AlphaGo and beyond

DQN was the first demonstration that a single neural network, with no prior knowledge of a game's rules, could learn to play entirely different games directly from the pixels on screen. This work was done at DeepMind even before AlphaGo made the company a household name around the world, in 2016. The methods DQN used — a convolutional neural network replacing a table, and experience replay stabilizing training — became standard building blocks in the later development of deep reinforcement learning, and variants on them, like Double DQN, were published as early as 2015 to correct biases in the estimates. The practical result: one algorithm, with the same architecture and settings, trained separately on each game, that reached more than 75% of the human games tester's level on 29 of 49 games, without a programmer ever explaining the goal or what each button does.