The History of AI

Q-learning

Era 3 · From the expert boom to the statistical turn (1980–2011) › Reinforcement learning

Lineage
Data and learning
Kind
Theory

Who

University of Cambridge

What happened

Chris Watkins submits a doctoral thesis at Cambridge, Learning from Delayed Rewards, which frames reinforcement learning as the control of a Markov decision process by incremental dynamic programming and introduces Q-learning.

Why it mattered

An agent learns the value of each action in each situation from experience, without knowing in advance how the environment works. It joins Bellman's dynamic programming with temporal differences.

The full story

Bellman's dynamic programming solves multistage decision problems, but it needs a complete model of the environment: what happens after each action, and with what probability. An animal or a robot has no such model; all it can do is act and see what happens. Watkins asked how to learn to decide well under those conditions.

The answer was to learn a table of Q-values directly: for each situation and each possible action, how much future reward can be expected by taking that action and then continuing to act as well as possible. Each time the agent acts, it observes the immediate reward and the new situation, and corrects the value of the action it took, moving it toward that reward plus the best value available in the next situation. It is the Bellman equation turned into a temporal-difference learning rule.

Q-learning has a very useful property: it learns the best policy even while the agent explores and sometimes takes actions that are not the best. That makes it possible to separate learning from acting.

The thesis sketched a proof that the method converges. The full version, with Peter Dayan, came in 1992. Q-learning became the best-known algorithm in the field, and in 2013 DeepMind combined it with a convolutional network in DQN to play Atari games from pixels.

Under the hood

The Q-learning rule fits on one line: Q(s, a) ← Q(s, a) + α·[r + γ·max Q(s′, a′) − Q(s, a)], where the maximum is taken over the possible actions a′ in s′. After taking action a in state s, the agent receives reward r and reaches s′; the expression in brackets is the temporal-difference error.

The maximum is what separates learning from acting: the target uses the best action in the next state, not the one the agent actually takes. The agent can explore, for example by choosing at random with a small probability, and still learn the values of the best policy.

With a table, Watkins and Dayan proved in 1992 that the method converges to the optimal values if every state-action pair is tried infinitely often and the rate α decreases appropriately. With a neural network in place of the table that guarantee is lost, and DQN needed tricks such as replaying past experiences to keep learning stable.

Builds on

  • Temporal differences (August 1988)

    Documented direct influence

    According to Sutton and Barto, Q-learning brings together the temporal-difference thread and the optimal-control thread in 1989

  • Dynamic Programming (1957)

    Documented direct influence

    Watkins frames reinforcement learning as incremental dynamic programming, and Q-learning is the Bellman equation turned into a learning rule

Leads to

  • DQN (December 19, 2013)

    Documented direct influence

    DQN is Q-learning with a deep network

Threads that pass through here

Sources

How to cite

“Q-learning.” The History of AI, revised November 13, 2026. https://thehistoryofai.com/en/milestone/watkins-q-learning

This entry was last reviewed on November 13, 2026.

Open in the interactive timeline