11 · Q-learning
The most famous RL algorithm: learn the optimal action-values directly from experience, off-policy, with a one-line update. No model of the environment needed.
Q-learning updates Q(s,a) ← Q(s,a) + α·[r + γ·max_a' Q(s',a') − Q(s,a)]. Because the target uses the MAX over next actions — not the action actually taken — it learns the OPTIMAL action-values regardless of how the agent explores. That is off-policy control, and it is enough to recover an optimal policy by trial and error alone.
Without this:
Without control algorithms like Q-learning, prediction (Chapter 4) only evaluates a fixed policy — it never improves it. Q-learning is the bridge from 'measure how good a policy is' to 'find the best policy'.
Chapter 4 taught prediction: estimate the value of a given policy. Now we want control: find the best policy. Q-learning (Watkins, 1989) does exactly that, and it is the single most influential RL algorithm — DQN, which beat humans at Atari, is Q-learning with a neural network.
The agent maintains a table Q(s, a) — its current estimate of the value of taking action a in state s and then acting optimally. Every transition (s, a, r, s') it observes drives one update:
Q(s, a) ← Q(s, a) + α·[ r + γ·max_a' Q(s', a') − Q(s, a) ]
The bracketed term is the TD error: the difference between a better estimate (the target r + γ·max_a' Q(s', a')) and the current value. The learning rate α controls how big a step we take toward the target.
The crucial detail is the max in the target. It says: "assume that from s' onward I will act greedily." This makes Q-learning off-policy — it learns the value of the optimal policy even while the agent itself is exploring with a different, exploratory policy. That exploratory policy is usually ε-greedy: with probability ε pick a random action (explore), otherwise pick argmax_a Q(s, a) (exploit). Exploration is what lets the agent discover the reward in the first place; the max is what lets it learn the optimum anyway.
Below we train a Q-table on a 4×4 gridworld purely from experience — no transition model — and watch the average reward climb while the greedy policy turns into a clean set of arrows pointing at the goal.
Python (in browser)
Q-learning on a 4×4 grid: reward rises as the table fills in, and the greedy policy becomes arrows funnelling every cell toward the goal — learned with no model, just experience.
Python runs entirely in your browser via Pyodide (~6 MB on first Run, cached after).
DQN is the same Q-learning rule (note r + γ·max Q(s′,a′)) but with a neural network, an experience-replay buffer, and a frozen target network for stability — the recipe that cracked Atari.
Why is Q-learning called 'off-policy'?
- Q-learning is model-free TD control: Q(s,a) ← Q(s,a) + α·[r + γ·max_a' Q(s',a') − Q(s,a)], learned from (s,a,r,s') tuples alone.
- The max over next actions makes it off-policy: it learns the optimal policy's values while exploring with an ε-greedy behaviour policy.
- ε-greedy balances exploration vs exploitation; the greedy policy argmax_a Q(s,a) is the agent's learned strategy.
DQN (Atari), tabular Q-learning in robotics and operations research, and Q-learning targets inside many actor-critic and offline-RL methods all use this exact update.
If you remove it: Without off-policy value-based control you cannot reuse arbitrary experience (e.g. a replay buffer) to learn an optimal policy — a foundation of deep RL.