Q-Learning, explained in 5 lines

Module 16 · Advanced AI · 23 concepts

In depth / 15 lines

Q-Learning, in more detail

Q-learning estimates the value of taking a particular action in a particular state.

That estimate is the Q-value, meaning expected total future reward from there onwards.

Knowing the Q-values means the policy is simply to take the highest one.

It starts with estimates that are wrong and improves them from experience.

After each step it compares its prediction with what actually happened.

The reward received plus the best value of the next state is the better estimate.

The gap between those is the error, and the estimate moves a fraction of the way across.

That update rule comes from the Bellman equation.

It is off-policy, meaning it can learn about a good strategy while behaving randomly.

That matters, since it lets the agent explore without learning to prefer exploration.

Epsilon-greedy is the usual exploration rule: mostly best action, occasionally random.

Classic Q-learning stores a table with one entry per state and action.

That is impossible when states are images, since the table would be astronomically large.

Deep Q-Networks replace the table with a neural network that predicts Q-values.

Experience replay and a separate target network are what made that stable enough to work.

Want the full technical article? Wikipedia ↗

Deep dive

What is underneath Q-Learning

The update rule

Q(s, a) \leftarrow Q(s, a) + \alpha \Big[ r + \gamma \max_{a'} Q(s', a') - Q(s, a) \Big]

$\alpha$ : the learning rate.
$r + \gamma \max_{a'} Q(s', a')$ : the target, what the value should have been.
The bracket: the temporal difference error.

The estimate moves a fraction of the way towards a better estimate built from one real reward and the current guess about the future.

\delta = r + \gamma \max_{a'} Q(s', a') - Q(s, a)

Nothing waits for the episode to end. Each transition updates immediately, which is what bootstrapping means and why it is sample efficient.

Why it is off-policy

\max_{a'} Q(s', a')

The target uses the best action from the next state, regardless of what the agent actually did there.

So the agent can behave exploratorily, even randomly, and still learn the value of the optimal policy, which is the property that makes replay buffers and learning from logged data possible.

Q(s,a) \leftarrow Q(s,a) + \alpha\big[r + \gamma Q(s', a') - Q(s,a)\big]

SARSA uses the action actually taken instead, which makes it on-policy and gives it different, more cautious behaviour near cliffs.

One episode, in order

Observe the state.
Choose an action by epsilon-greedy on the current $Q$ .
Execute it, and receive the reward and the next state.
Compute the temporal difference error and update that one entry.
Move to the next state, and repeat until the episode ends.

$Q$ converges to $Q^{*}$ if every pair is visited infinitely often and $\alpha$ decays.

The convergence guarantee is real and its conditions are demanding, and it holds only for a lookup table.

Deep Q-learning, and the two fixes it needed

\mathcal{L} = \Big( r + \gamma \max_{a'} Q_{\theta^{-}}(s', a') - Q_{\theta}(s, a) \Big)^{2}

Replacing the table with a network makes the target depend on the same weights being updated, so the target moves as fast as the estimate and training oscillates.

\theta^{-} \leftarrow \theta \text{ every } C \text{ steps}

A target network holds a frozen copy of the weights for a few thousand steps, which stabilises the regression by holding still.

The second fix, a replay buffer, stores past transitions and samples them at random.

That breaks the correlation between consecutive samples, which would otherwise violate every assumption in stochastic gradient descent.

The bias nobody removes for free

\mathbb{E}\big[\max_a Q\big] \geq \max_a \mathbb{E}\big[Q\big]

Taking a maximum over noisy estimates is biased upward, so Q-learning systematically overestimates values, and the error compounds through bootstrapping.

Q_{\theta^{-}}\big(s', \arg\max_{a'} Q_{\theta}(s', a')\big)

Double Q-learning selects the action with one network and evaluates it with the other, which decorrelates the two roles and removes most of the bias for almost no cost.

That fix, the target network and the replay buffer are the three things that turned a tabular algorithm from 1989 into something that plays Atari.

Test yourself

One question on this card. Every option explains itself once you pick, right or wrong.

Question 1

What does a Q-value estimate?

Advanced AI

23 concepts in this module, then a graded test with every answer explained.

Study this module →