Concept · Chapter 5: Vision, Speech & Reinforcement Learning
Q-Learning
Q-learning learns how good each action is in each state by repeatedly nudging its estimate toward the reward received plus the discounted value of the best next action.
The problem
The agent does not know the environment's rules or rewards in advance, so it cannot compute optimal values by planning.
The solution
After every step, move Q(s, a) a fraction α toward the target r + γ · max Q(s′, ·), learning from its own experience one transition at a time.
The consequence
Value information flows backward from rewards through the states that lead to them; with a neural network in place of the table, the same rule learned Atari games from pixels (DQN).
You should understand first
- The Turing Test
- Symbolic AI
- Logic and Rules
- Expert Systems
- Knowledge Representation
- The Knowledge-Acquisition Bottleneck
- From Rules to Learning
- Supervised, Unsupervised and Self-Supervised Learning
- Probability and Distributions
- Expected Value and Variance
- Reinforcement Learning
- MDPs, Policies and Value
- Q-Learning
Intuition: updating a guess with a better guess
You estimate your commute takes 30 minutes. Halfway there you hit traffic, and your best guess for the remaining half becomes 25 minutes. You do not need to wait until you arrive to revise the total: you already know your 30 was too low. Learning from a later estimate instead of the final outcome is temporal-difference (TD) learning, and Q-learning applies it to action values.
Tiny numeric example (the lab's numbers)
Take α = 0.5 and γ = 0.9, and start every Q at 0.
First success
The agent steps into the +10 goal. Target = 10 (the episode ends, so there is no next value). Q ← 0 + 0.5 × (10 − 0) = 5.One step earlier
Later it reaches the square before that move. Target = 0 + 0.9 × 5 = 4.5. Q ← 0 + 0.5 × (4.5 − 0) = 2.25.Repeat
Each visit pulls the estimate closer to its target, and each target improves as the values downstream improve. With enough visits, the move into the goal approaches 10, the move that leads next to the goal approaches 9, and so on backward.
The equation
Watkins introduced Q-learning in his 1989 thesis, and Watkins and Dayan proved in 1992 that tabular Q-learning converges to the optimal values if every state–action pair keeps being tried and the learning rates shrink appropriately Established. That "keeps being tried" condition is why exploration matters.
Try it
Try it · toy model
Watch Q-learning fill in a value table move by move, and see an agent settle for a small reward until optimism or a gentler discount changes its mind.
From a table to a network
A table needs one entry per state–action pair: fine for 26 squares, impossible for Atari screens. DQN (2015) replaced the table with a CNN that reads game frames and outputs a Q value per joystick action, and it learned to play 49 Atari games from pixels and score Established. Two stabilisers made it work: experience replay (train on random past transitions, not just the latest, so updates are less correlated) and a target network (compute targets with a slowly updated copy, so the goal does not move at every step).
Why should I care?
As a researcher
Temporal-difference learning, updating a guess from a later guess, is one of RL's central ideas, with links to how animals may learn from prediction errors.
As an engineer
The update is a few lines of code, and its failure modes (unstable targets, overestimation, correlated data) explain the tricks every deep RL library ships with.
Modern systems that depend on it
- DQN
- actor–critic methods
- value-based deep RL
Historical context
Before
Dynamic programming could compute optimal values, but only with a complete model of the environment's transitions and rewards.
After
An agent can learn optimal action values purely from trial and error, without a model.
Used today
Tabular Q-learning is a teaching and small-problem tool; its deep descendants (DQN and variants) remain standard baselines, and the value-learning idea lives on in actor–critic methods.
What to remember
- Q(s, a) ← Q(s, a) + α · [ r + γ · max Q(s′, ·) − Q(s, a) ].
- The bracket is the temporal-difference error: how surprised the agent was.
- Values spread backward one step per update, from rewards to the states that lead to them.
- Off-policy: it learns the value of the best actions even while exploring with random ones.
- DQN (2015): a CNN estimates Q from game pixels, stabilised by experience replay and a target network.
Key papers
Human-level control through deep reinforcement learning
Volodymyr Mnih, Koray Kavukcuoglu et al. · 2015 · Nature
A single deep network learned to play dozens of Atari games from raw pixels and score alone — deep learning meets reinforcement learning.
Reinforcement Learning: An Introduction (2nd edition)
Richard S. Sutton, Andrew G. Barto · 2018 · MIT Press
The standard textbook, free online from the authors. Everything in this chapter's RL half (MDPs, value functions, Q-learning, exploration, policy gradients, actor–critic) is developed carefully there.
How to read it: Chapters 1, 3 and 6 cover the core: the problem, MDPs, and temporal-difference learning including Q-learning. Chapter 13 is policy gradients.
Q-learning
Christopher J. C. H. Watkins, Peter Dayan · 1992 · Machine Learning
Proved that Q-learning, which Watkins introduced in his 1989 thesis, converges to the optimal action values under stated conditions: learn the best behaviour while behaving otherwise.