Deep Q-networks (DQN): Q-learning with a neural network

A deep Q-network replaces the Q-table of Q-learning with a neural network that takes a state and outputs a value for every action. It is trained on remembered experience, towards targets computed by a slowly updated copy of itself.

Why it matters

A Q-table needs one row for every state. A grid of 16 squares fits; a game screen, a robot's sensors or a conversation never will, because there are more possible states than could ever be stored. A network shares what it learns between similar states, so it can value states it has never seen.

DQN was the first method to learn dozens of Atari games from the raw pixels. Its two tricks, a replay buffer and a target network, are still in almost every value-based method.

The idea

Keep Q-learning, but swap the table for a network that outputs a value for every action. Two additions keep the training stable: a replay buffer of past moves, learned from in random order, and a frozen copy of the network that computes the targets.

A chess player who keeps a diary of her games. Each evening she studies random old positions, not just today's game, and grades every move against last week's notes, which stay the same while she studies.

Her notes could come from a stronger player. The target network is only an older copy of the same learner, so early targets are as wrong as the learner is. The two improve together, and that is why the estimates can drift too high.

How it works

  1. The network takes a state (here 16 numbers, with a 1 for the agent's square) and outputs four numbers: the estimated Q-value of moving up, down, left and right.
  2. Act with ε-greedy: with probability ε take a random action, otherwise the action with the highest Q-value. Start with ε = 1, all random, and lower it to 0.05.
  3. Store every move (s, a, r, s′, done) in a replay buffer: a list of the last 5,000 moves.
  4. At every step, draw 32 random moves from the buffer. For each, build the target y = r + γ·max Q_target(s′, ·), or just y = r if that move ended the episode.
  5. Train the network to bring Q(s, a) closer to y, with the squared error. Only the output for the action that was taken is trained.
  6. Q_target is a frozen copy of the network, refreshed every 100 steps. Without it the target would move every time the network changed, like chasing your own shadow.
  7. After 300 episodes, following the highest Q-value from the start reaches the goal in 6 moves, the fewest possible. The network values the start at 0.59 = 0.9⁵: one reward, discounted five times.

Key points

Common mistakes

Not true: Continuous actions (a steering angle): DQN handles them as well as a short list of actions.
In fact: DQN's target takes a max over the actions, which needs a short list of them. For continuous actions, use policy-gradient methods instead.

Not true: Last move of an episode: the target is still y = r + γ·max Q_target(s′, ·).
In fact: After the last move there is no next state, so the target is just the reward r. Adding a value there teaches the network something false.

Part of Unit 7: Generative models and reinforcement learning in the free ML Foundations course.