Q-learning: Learning what an action is worth

The event and the narrow claim

In May 1989 Christopher Watkins submitted a PhD thesis at the University of Cambridge, as a member of King's College, under the title "Learning from Delayed Rewards". Its seventh chapter, on what Watkins called primitive learning, defined a method he named one-step Q-learning: an agent keeps a running estimate of the value of each action in each situation and, after every step, nudges that estimate toward the reward it just received plus the best value it currently expects from wherever it landed. An appendix sketched a proof that, in a finite Markov decision process, these estimates converge to the optimal action values. Three years later Watkins and Peter Dayan published the full convergence proof in the journal Machine Learning, and that 1992 technical note is the citation most later work gives.

The narrow, documented claim is modest and mathematical. For a problem with a finite number of states and actions, stored as a lookup table, an agent that never builds a model of its environment can still learn the optimal value of every action, provided it keeps trying every action in every state and its step sizes shrink at a suitable rate. The broader claim, that this algorithm became a foundation of modern reinforcement learning, from the deep Q-network that learned Atari games to robots that learned to grasp, rests on what happened over the following three decades. That claim is well supported, but it should not be read back into a thesis whose experiments were two small demonstration programs and whose author doubted he was the first to think of the idea.

A thesis about how animals might learn

Watkins was not trying to build a game player or a robot controller. His thesis summary starts from behavioural ecology, where stochastic dynamic programming was used to calculate the policies an animal ought to follow, and asks how the animals themselves could come to learn such policies from experience. He argued that Markov decision processes are a general formal model of an animal's choices, and that the conventional dynamic programming calculation is not something an animal could plausibly carry out. The opening chapter observes that learning from rewards and punishments had been studied extensively in experimental psychology, yet Watkins knew of no paper on animal learning in the mainstream artificial intelligence literature.

The preface places the work in a small network. Watkins thanks his supervisor Richard Young, the behavioural ecologist Alex Kacelnik for examples from foraging theory, and Andy Barto for helpful conversations, and he records that Rich Sutton sent him technical reports and pointed out a difficulty with Q-learning. The demonstrations in chapter 11 were written in Pascal and run on a Sun 3 workstation. One was a synthetic route-finding task; the other, which Watkins described as a simple implementation of Q-learning for conditioning, mimicked a Skinner box in which an agent pecks under fixed-ratio and variable-interval reward schedules, and he explicitly declined to claim it was a realistic model of animal learning. His conclusion presents the algorithms as direct implementations of associative learning according to the law of effect. The method that would later sit inside deep reinforcement learning arrived as a computational account of how animals learn from consequences.

Three threads that had not yet met

By the late 1980s the ingredients existed in separate literatures. Dynamic programming could compute optimal policies for Markov decision processes, but only when the transition probabilities and expected rewards were known in advance. Watkins and Dayan note that the traditional alternative, estimating those quantities while planning as if the current estimates were correct, costs dearly in the early stages of learning. Trial-and-error learning, including Barto, Sutton and Anderson's adaptive critic of 1983 and Sutton's 1984 thesis, learned policies together with the values of states, but, as Watkins's literature review points out, none of those methods represented the values of actions explicitly.

The third thread was temporal-difference learning. Sutton's 1988 paper showed how to learn predictions from the difference between successive predictions rather than waiting for a final outcome, traced the idea to Arthur Samuel's checkers player, and proved convergence for special cases. But it addressed prediction, estimating how good a situation is, not control, choosing what to do. Sutton and Barto's textbook history describes the temporal-difference and optimal-control threads as fully brought together in 1989 by Watkins's Q-learning, and says his treatment of reinforcement learning in the Markov decision process formalism was widely adopted. The same text attributes the term action value to Watkins and suggests he may have been the first to use epsilon-greedy exploration, taking the best-looking action most of the time and a random one otherwise.

One line of arithmetic: the update rule

Q-learning keeps a number Q(x, a) for every state x and action a, meant to estimate the total discounted reward the agent will collect if it takes action a in state x and behaves optimally afterwards. In the thesis the update is a weighted average. After taking action a in state x, receiving reward r and arriving in state y, the agent replaces its old estimate with a mixture of the old value and a new target: the reward plus the discounted value of the best action available in y. The weight on the new target is the learning factor, a small positive number, and every other entry in the table is left alone. The agent's current policy is implicit in the table: in each state, pick the action with the highest Q value.

A worked example makes the mechanism concrete. Suppose an agent's table says that moving left from some square is worth 2. It moves left, receives a reward of 1, and lands in a square where its best estimated action is worth 5. With a discount factor of 0.9 the target is 1 plus 0.9 times 5, which is 5.5. With a learning factor of 0.1 the estimate moves a tenth of the way from 2 toward 5.5, ending at 2.35. Nothing about the environment's dynamics was needed: no probability that moving left leads to that square, no table of expected rewards. Watkins and Dayan describe this as model-free learning that lets an agent act optimally without building maps of its domain, and as a form of asynchronous dynamic programming. Watkins himself framed it as incremental Monte Carlo value iteration, in which sampled experience stands in for the model that classical dynamic programming requires.

Learning about one policy while following another

The property that later mattered most is easy to miss in the equation. Because the target uses the best action in the next state, not the action the agent actually takes next, the values being learned are those of the greedy, optimal policy, however the agent behaves. Watkins noted that the method does not specify which actions to take at all: the agent may act as it likes, as long as it tries each action in each state many times. In modern terms Q-learning is off-policy, and Sutton and Barto call this off-policy control algorithm one of the field's early breakthroughs. The learned function approximates the optimal action values independently of the behaviour that generated the data, which simplified the analysis and enabled early convergence proofs.

Off-policy learning has a visible cost, which the same textbook illustrates with a cliff-walking gridworld. An agent that explores by taking a random move 10 percent of the time learns, under Q-learning, the values of the optimal route along the cliff edge, and then occasionally falls off because its own exploration jostles it. Sarsa, an on-policy alternative that G. A. Rummery and M. Niranjan of Cambridge's engineering department introduced in 1994 under the name modified connectionist Q-learning, learns the value of the policy it is actually following and so prefers a longer, safer path. Q-learning finds the better policy and earns less while learning it. That trade, correct values for the target policy against safety during exploration, recurs throughout the algorithm's later history.

A proof built from a deck of cards

Watkins's appendix argued for convergence with an unusual device, an imaginary action-replay process built from the agent's own record of observations. The 1992 paper explains it as a card game. Each experience (state, action, reward, next state) is written on a card, and the cards are stacked in the order they happened. To act in the imaginary process, you search down the deck for a card matching your state and action and replay it with a probability equal to the learning rate used when that card was learned; if you reach the bottom card, you receive the initial guess. By construction, the Q values the agent holds after n experiences are exactly the optimal action values of this card process at level n, and as the deck grows the card process comes to resemble the real environment.

The theorem's conditions are precise. Rewards must be bounded, learning rates must lie between 0 and 1, their sum must be infinite while the sum of their squares stays finite, and every action must be tried in every state infinitely often. Under those conditions the estimates converge to the optimal action values with probability 1. The note closes by saying such a guarantee had eluded most earlier reinforcement learning methods. The corrigenda printed at the front of the thesis already restate the appendix's sufficient conditions, a sign that the 1989 argument was a sketch that needed tightening. Within two years the result was absorbed into general theory. John Tsitsiklis and, in a separate paper, Tommi Jaakkola, Michael Jordan and Satinder Singh proved convergence through stochastic approximation theory, placing Q-learning and TD(λ) in a broader class of convergent algorithms under more general conditions.

What Watkins could not prove, and who else was close

The thesis is candid about its limits. Watkins described a family of Q-learning methods that estimate returns over several steps, the ancestor of what textbooks now call Watkins's Q(λ), and admitted he could not show they always work, because a small error in the values can change the implied policy and destabilize learning; in his own programs the instabilities were not significant. His conclusion says the algorithms can be justified as incremental dynamic programming in only one case. Watkins and Dayan repeat the restriction: their theorem covers only the one-step version and does not extend trivially to multi-step returns. They also record that Watkins had shown Q-learning may not converge correctly with representations other than a lookup table, a warning that would matter a great deal.

Priority is murkier than a single name suggests. Watkins wrote that the idea was simple and, as far as he knew, new, but that after thirty years of work on Markov decision processes it was unlikely nobody had considered it. The 1992 note points readers to Paul Werbos's work of 1977, and Sutton and Barto credit Werbos with arguing from 1977 onward for joining trial-and-error learning to dynamic programming. The note also lists Long-Ji Lin among early users and says he developed the method independently, although Lin's own 1992 paper attributes Q-learning to Watkins. The defensible statement is that Watkins gave the first clear formulation, named it, and outlined why it converges, while closely related ideas were in circulation.

Replay, neural networks and the trouble with approximation

The May 1992 issue of Machine Learning that carried the convergence proof also carried Gerald Tesauro's paper on training backgammon networks by temporal differences, the work behind TD-Gammon, and Lin's study, which pushed Q-learning toward harder problems. Lin compared eight frameworks built on Sutton's adaptive heuristic critic and on Watkins's Q-learning, with neural networks providing generalization, and tested three ways of speeding them up: experience replay, learned action models for planning, and teaching. Experience replay, storing past transitions and reusing them for further updates, would become central two decades later, and it depends on an off-policy learner, because the replayed data were generated by an older version of the agent.

Generalization came at a price. A lookup table cannot hold a problem with millions of states, so practitioners replaced the table with a function approximator, and the convergence guarantee disappeared. Leemon Baird published a small counterexample in 1995 on which an off-policy learner of this kind diverges, and Sutton and Barto later generalized the lesson as the deadly triad: function approximation, bootstrapping from existing estimates, and off-policy training together create a danger of instability and divergence. Q-learning with a neural network combines all three. The 2013 DeepMind paper records the consequence: after results showing that Q-learning with nonlinear approximators or off-policy learning could diverge, most work in the field turned to linear function approximators with better guarantees.

From lookup tables to Atari pixels

That retreat ended with the deep Q-network. Mnih and colleagues' 2013 workshop paper trained a convolutional network with a variant of Q-learning to choose joystick actions from raw Atari screen pixels, used the same architecture and learning algorithm across seven games, and reported better results than earlier learning methods on six of them. Their reason for choosing Q-learning is telling. Sampling stored experience at random breaks the strong correlations between successive frames and smooths training, but learning from replayed data requires an off-policy method, which they say motivated the choice of Q-learning. They cite Lin for replay and Watkins and Dayan for the algorithm. The expanded 2015 Nature paper scaled the test to 49 games, reported play comparable to a professional human games tester, and analysed the separate effects of replay and of a separate target Q-network, the stabilizers that kept the deadly triad in check well enough in practice.

The algorithm's known weaknesses resurfaced at scale and produced their own line of work. Hado van Hasselt showed in 2010 that Q-learning can perform very poorly in some stochastic environments, because taking the maximum over noisy estimates introduces a positive bias, and he proposed Double Q-learning, which uses two estimators so that choosing an action and evaluating it are decoupled, and which still converges to the optimal policy. Sutton and Barto note that DQN, like TD-Gammon, trained a multilayer network with gradients computed by backpropagation, and found Q-learning a natural choice because it was both model-free and off-policy.

Routers, robots and pricing algorithms

Q-learning's reach extended well beyond games. In 1993 Justin Boyan and Michael Littman proposed Q-routing, which embedded a learning module in each node of a packet-switching network to track which routing decisions lead to the shortest delivery times. The Q in their function was named for Watkins's algorithm, and on a simulated 36-node irregular network the method beat routing along precomputed shortest paths and kept working when the load varied. In robotics, the Google Brain team behind QT-Opt used a continuous-action generalization of Q-learning, trained on more than 580,000 real grasp attempts collected by seven robots over several weeks, to reach 96 percent grasp success on objects it had not seen.

The most consequential application outside computer science may be in economics. Calvano, Calzolari, Denicolò and Pastorello, writing in the American Economic Review in 2020, set Q-learning pricing algorithms against each other in a standard model of repeated oligopoly competition. They found that the algorithms consistently learned to charge prices above the competitive level without communicating, sustained by strategies that punished deviations for a finite period and then returned gradually to cooperation. A method devised to model animal learning became a test case for whether autonomous pricing software can collude tacitly. These applications share almost nothing except the core update, which is a measure of how general the 1989 formulation was.

The honest limits

Q-learning's guarantee is narrow. It holds for finite problems stored in tables, with unlimited experience of every state and action, and says nothing about how fast convergence happens. Even-Dar and Mansour showed that the step-size schedule matters enormously: with a learning rate that shrinks as 1/t, the convergence time can grow exponentially in 1/(1 minus the discount factor), whereas a polynomial schedule gives polynomial dependence. The maximum in the update biases estimates upward, as van Hasselt documented, and the algorithm leaves exploration unspecified: epsilon-greedy exploration is a heuristic, and the cliff-walking example shows exploration and off-policy learning pulling in different directions.

The off-policy promise has fine print too. In principle Q-learning can learn from any data. In practice, Fujimoto, Meger and Precup showed that standard off-policy deep methods such as DQN fail when trained only on a fixed batch of previously collected data, because of errors from extrapolating to actions the data do not cover. Q-learning is also hungry for experience: DQN consumed 50 million frames per game, which Sutton and Barto put at about 38 days of play. Finally, it is not the method behind every celebrated reinforcement learning result. OpenAI's InstructGPT, which tuned GPT-3 models to follow instructions using human feedback, optimized its policy with the policy-gradient method PPO rather than with learned action values.

How to place Q-learning in AI history

Q-learning is best read as the point where reinforcement learning acquired a simple, provably correct algorithm for control. Temporal-difference learning showed how to learn predictions from experience; dynamic programming showed what optimal decisions are when the world is known; Watkins showed that an agent could learn optimal action values directly from experience, without a model and while behaving however it liked, and he outlined why that works. The 1992 proof turned the sketch into a theorem, and the 1994 papers made it part of stochastic approximation theory. The vocabulary Watkins introduced, action values and the Markov decision process as the frame for learning, became the field's common language.

Its later influence is documented in the work that built on it, from Q-routing and Lin's replay experiments to DQN, Double Q-learning and QT-Opt, and in the textbook account that treats it as an early breakthrough. That influence also has boundaries. The guarantee never covered the neural networks that made Q-learning famous, its built-in maximization and off-policy learning created problems later work had to repair, and the best-known recipe for tuning language models with human feedback used a policy-gradient method instead. Placed honestly, Q-learning is neither the origin of reinforcement learning nor its universal engine. It is the compact, testable formulation of learning to act from delayed rewards that a thesis about animals handed to computer science, and the one later researchers kept returning to whenever an agent had to learn what an action is worth.

References

• Watkins (1989). Learning from Delayed Rewards, PhD thesis, King's College, Cambridge.
• Watkins and Dayan (1992). Q-learning.
• Sutton (1988). Learning to Predict by the Methods of Temporal Differences.
• Sutton and Barto (2018). Reinforcement Learning: An Introduction, second edition.
• Lin (1992). Self-improving reactive agents based on reinforcement learning, planning and teaching.
• Tesauro (1992). Practical Issues in Temporal Difference Learning.
• Tsitsiklis (1994). Asynchronous Stochastic Approximation and Q-Learning.
• Jaakkola, Jordan and Singh (1994). On the Convergence of Stochastic Iterative Dynamic Programming Algorithms.
• Mnih et al. (2013). Playing Atari with Deep Reinforcement Learning.
• Mnih et al. (2015). Human-level control through deep reinforcement learning.
• van Hasselt (2010). Double Q-learning.
• Boyan and Littman (1993). Packet Routing in Dynamically Changing Networks: A Reinforcement Learning Approach.
• Kalashnikov et al. (2018). QT-Opt: Scalable Deep Reinforcement Learning for Vision-Based Robotic Manipulation.
• Calvano, Calzolari, Denicolò and Pastorello (2020). Artificial Intelligence, Algorithmic Pricing, and Collusion.
• Even-Dar and Mansour (2003). Learning Rates for Q-learning.
• Fujimoto, Meger and Precup (2018). Off-Policy Deep Reinforcement Learning without Exploration.
• Ouyang et al. (2022). Training language models to follow instructions with human feedback.