The History of AI

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

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.

Open in the interactive timeline