Q-learning

The problem it addresses

The note starts from a question that sounds simple but is not: how can an agent learn, by trial and error, to act optimally in a controlled Markovian domain — an environment whose state changes in response to the agent's own actions? The difficulty is delayed reward. Whether an action was good often only becomes visible several steps later, so the agent has to attribute credit backwards over time.

Q-learning was not introduced for the first time in this note. The abstract labels Q-learning as Watkins's 1989 work, and the reference list points to his doctoral thesis at the University of Cambridge, "Learning from delayed rewards", as the origin of the method ^[1]. The 1992 note, written jointly with Dayan, presents the method as a journal paper and adds the piece the thesis had only sketched: a detailed convergence proof ^[1].

How the method works

According to the abstract, Q-learning is a simple way for agents to learn how to act optimally in controlled Markovian domains ^[1]. It amounts to an incremental method for dynamic programming with limited computational demands, and it works by successively improving its evaluations of the quality of particular actions at particular states ^[1].

Put concretely: the agent keeps one number for each state–action pair, which can be read as how much it is worth to take this action here once the rewards that follow are included. Each time it acts and observes a reward and a next state, it nudges that number toward a better estimate. Nothing else has to be stored — in particular, no model of how the environment moves from state to state — and that is what keeps the computation small.

The convergence theorem

The central contribution of the note is a convergence theorem, presented and proved in detail, building on one outlined in Watkins's 1989 thesis ^[1]. The theorem states that Q-learning converges to the optimum action-values with probability 1, so long as all actions are repeatedly sampled in all states and the action-values are represented discretely ^[1].

Both conditions carry weight. The sampling condition requires that every action keeps being tried in every state, otherwise the estimate for that pair never gets corrected. The representation condition constrains how the values are stored. "With probability 1" means the convergence happens almost surely, not that every single update improves the estimate.

Two extensions

The note also sketches extensions in two directions ^[1]. One covers non-discounted but absorbing Markov environments; the other covers cases where many Q values can be changed on each iteration rather than just one ^[1].

Where it appeared

The technical note "Q-learning" was published in the journal Machine Learning in May 1992, in volume 8, pages 279–292, with DOI 10.1007/BF00992698 ^[1]. At the time, Watkins was based in London and Dayan at the Centre for Cognitive Science, University of Edinburgh ^[1].

Why it matters

The note matters for what it puts together: an update rule that costs very little computation, and an explicit statement of when that rule can be trusted. The proof does not simply assert that the method works; it names the two conditions under which it does, which is what a practitioner needs in order to judge whether the method applies to a given problem. Because the algorithm requires no model of the environment and only limited computation, those conditions are the main thing standing between the method and a guarantee.