Convergence of Q-learning
Era 3 · From the expert boom to the statistical turn (1980–2011) › Reinforcement learning
- Lineage
- Data and learning
- Kind
- Theory
Who
What happened
Chris Watkins and Peter Dayan publish "Q-learning" in Machine Learning, with the proof that the algorithm converges to the optimal values.
Why it mattered
It guarantees that, if every action is tried often enough and learning is gradually tempered, Q-learning finds the optimal action values with probability one.
The full story
An algorithm that works in experiments is not the same as one that is known to work. Watkins's thesis had only sketched why Q-learning should converge, and the field needed a guarantee to build on.
Peter Dayan and Watkins gave the full proof in a special issue of Machine Learning devoted to reinforcement learning. The result says that if the environment is a Markov decision process with finite states and actions, if every situation-action pair is visited infinitely often, and if the size of the learning steps shrinks in the right way, the Q-values converge to the optimal ones with probability one.
The proof rests on an ingenious construction, an artificial process that replays the experience the agent lives through, in which the learned values are exactly the optimal values of that process. As the number of experiences grows, that process looks more and more like the real one.
The conditions are demanding: they do not hold when a neural network is used to approximate the values, and in that case the algorithm can in fact diverge. That is why DQN, in 2013, had to add tricks to stabilize it. But the 1992 result gave tabular reinforcement learning a firm theoretical footing.
Sources
Original source
- Q-learning. Machine Learning, 8(3-4), pp. 279-292 (opens in a new tab). Christopher J. C. H. Watkins and Peter Dayan, 1992
Further reading
How to cite
“Convergence of Q-learning.” The History of AI, revised November 13, 2026. https://thehistoryofai.com/en/milestone/q-learning-convergence
This entry was last reviewed on November 13, 2026.