Technical Note: Q-Learning

CHRISTOPHER J.C.H. WATKINSPETER DAYAN

article2004Machine-mediated learning2,391 citations

Proves that Q-learning converges with probability one to optimal action-values in discrete Markov decision processes, establishing the mathematical foundation for model-free reinforcement learning.

Listen

In complex, dynamic environments, automated systems must frequently learn to make optimal decisions without an upfront manual or exact mathematical model of their surroundings. Traditional dynamic programming methods require knowing all system transition probabilities and expected payoffs in advance, whereas learning such models on the fly often leads to high computational costs and early operational errors. The article addresses this challenge by establishing the mathematical foundations for Q-learning, an incremental, model-free reinforcement learning technique that allows an agent to optimize long-term performance solely through direct experience.

The primary objective of the article is to present and formally prove a rigorous convergence theorem for Q-learning. Specifically, it demonstrates that successive, experience-based updates to discrete action values will converge to the true optimal action-values with probability one in controlled, finite Markov decision environments.

To establish this result, the authors construct a theoretical surrogate environment called the action-replay process. This framework models past experiences as a decreasing stack of historical episodes through which the learning updates operate via backwards induction. By connecting the surrogate process to standard stochastic approximation principles, the analysis formally proves that the behavior and rewards within the replay structure asymptotically match those of the true operational environment.

The findings confirm three core principles. First, discrete Q-learning guarantees convergence to the unique optimal strategy with probability one, provided that every state-action pair is visited infinitely often and learning rate parameters diminish under standard conditions. Second, the convergence guarantee successfully extends to non-discounted tasks that possess absorbing termination states, as well as to operational variants where multiple values are updated simultaneously within each iteration. Third, the analysis illustrates that remembering and repeatedly sampling historical episodes bridges the gap between pure incremental learning and full certainty-equivalence modeling, offering a spectrum of practical implementations.

These results provide vital theoretical backing for deploying reinforcement learning in automated control, industrial robotics, and adaptive software without the risk of divergent decision rules. Organizations can confidently use model-free algorithms to discover optimal operational policies without incurring the heavy upfront costs and computational burdens of complete environment mapping. However, decision-makers must recognize that the convergence guarantee strictly assumes finite, discrete lookup tables and exhaustive exploration; it does not directly cover multi-step eligibility traces or complex function approximations. Future initiatives should focus on developing alternative proofs for multi-step reward updates and exploring practical memory-reuse strategies during real-time implementation.

University of Edinburgh q-learning continuous time markov chain ARP State Real Process

WATKINS et al (2004).pdf

Paper: Q-learning, CHRISTOPHER J.C.H. WATKINS et al. (1992). Reading Watkins and Dayan's foundational convergence proof for Q-learning provides the exact mathematical framework that this technical note summarizes and extends.
Paper: Learning to Predict by the Methods of Temporal Differences, Richard S. Sutton (1988). Understanding Sutton's introduction of temporal-difference prediction is essential for grasping the foundational learning mechanisms underpinning Q-learning.
Paper: Reinforcement Learning: A Survey, Leslie Pack Kaelbling et al. (1996). This comprehensive survey of reinforcement learning establishes the broader algorithmic context of Markov decision processes and model-free updating that Q-learning builds upon.

Paper: Deep Reinforcement Learning with Double Q-learning, Hado van Hasselt et al. (2016). Extends standard Q-learning by identifying and correcting its systematic value overestimation in complex deep reinforcement learning environments.
Paper: Playing Atari with Deep Reinforcement Learning, Volodymyr Mnih et al. (2013). Builds directly upon Q-learning by scaling the tabular algorithm to handle high-dimensional raw pixel inputs via deep convolutional neural networks.
Paper: Prioritized Experience Replay, Tom Schaul et al. (2016). Continues the algorithmic development of Q-learning by prioritizing experience replay transitions based on temporal-difference error to accelerate learning.
Paper: Dueling Network Architectures for Deep Reinforcement Learning, Ziyu Wang et al. (2016). Extends standard Q-learning architectures by decoupling state-value estimation from action-advantage estimation to improve policy evaluation in redundant spaces.
Paper: Distributional Reinforcement Learning with Quantile Regression, Will Dabney et al. (2018). Generalizes Q-learning into a distributional framework that models the full spread of returns rather than just the expected average value.

Abstract

Q-learning (Watkins, 1989) is a simple way for agents to learn how to act optimally in controlled Markovian domains. It amounts to an incremental method for dynamic programming which imposes limited computational demands. It works by successively improving its evaluations of the quality of particular actions at particular states.

This paper presents and proves in detail a convergence theorem for Q-learning based on that outlined in Watkins (1989). We show 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. We also sketch extensions to the cases of non-discounted, but absorbing, Markov environments, and where many Q values can be changed each iteration, rather than just one.

Topics

q-learning continuous time markov chain

Keywords

ARP State Real Process Learning Actions Q-Learning Action Level Probability Note

1. Introduction
2. The task for Q-learning
3. The convergence proof
3.1. Lemmas
3.2. The theorem
4. Discussions and conclusions
Acknowledgments
Notes
Appendix
The action-replay process
References

Knowls

Knowl 1 — Convergence Theorem of Tabular Q-Learning
theoretical result
Let a controlled Markov process have a finite state space $X$ , a finite action space $A$ , bounded immediate rewards $|r_n| \le \mathcal{R}$ , and a discount factor $\gamma \in [0, 1)$ . Let $Q_n(x, a)$ denote the tabular action-value estimates at step $n$ , and let $n^i(x, a)$ denote the episode index at which action $a$ is executed in state $x$ for the $i$ -th time.

If every state-action pair $(x, a) \in X \times A$ is visited infinitely often and the sequence of learning rates $\alpha_n \in [0, 1)$ satisfies the standard stochastic approximation conditions:
$\sum_{i=1}^\infty \alpha_{n^i(x, a)} = \infty \quad \text{and} \quad \sum_{i=1}^\infty \left[\alpha_{n^i(x, a)}\right]^2 < \infty \quad \forall x \in X, a \in A,$
then as $n \to \infty$ , $Q_n(x, a)$ converges to the unique optimal action-values $Q^*(x, a)$ with probability 1 for all $x \in X$ and $a \in A$ , regardless of the initial values $Q_0(x, a)$ and regardless of whether the sampled transitions form a continuous trajectory.
Knowl 2 — Tabular Q-Learning Algorithm
algorithm
Tabular Q-learning is an asynchronous, model-free reinforcement learning algorithm that iteratively estimates optimal action-values $Q^*(x, a)$ directly from observed experience without estimating the underlying transition or reward models.
Input: Discount factor $\gamma \in [0, 1)$ , arbitrary initial values $Q_0(x, a)$ for all $x \in X, a \in A$ , learning rate sequence $\alpha_n \in [0, 1)$
Initialize episode step $n = 1$
for each episode step $n = 1, 2, \dots$
    Observe current state $x_n \in X$
    Select and execute action $a_n \in A$
    Observe subsequent state $y_n \in X$ and immediate reward $r_n$
     $V_{n-1}(y_n) = \max_{b \in A} Q_{n-1}(y_n, b)$
    for each $x \in X$ and $a \in A$
        if $x = x_n$ and $a = a_n$ then
             $Q_n(x, a) = (1 - \alpha_n) Q_{n-1}(x, a) + \alpha_n (r_n + \gamma V_{n-1}(y_n))$
        else
             $Q_n(x, a) = Q_{n-1}(x, a)$
The update requires only local look-up table storage $Q(x, a)$ and can be applied to non-continuous experience tuples $(x_n, a_n, y_n, r_n)$ where $y_{n-1}$ is not necessarily $x_n$ .
Knowl 3 — Action-Value Function and Model-Free Optimal Policy Extraction
definition
In a controlled Markov process with finite state space $X$ , action space $A$ , transition probabilities $P_{xy}[a] = \Pr(y \mid x, a)$ , mean immediate rewards $R_x(a)$ , and discount factor $\gamma \in [0, 1)$ , the value function $V^\pi(x)$ under a stationary policy $\pi: X \to A$ is:
$V^\pi(x) = R_x(\pi(x)) + \gamma \sum_{y \in X} P_{xy}[\pi(x)] V^\pi(y).$
The action-value function $Q^\pi(x, a)$ is defined as the expected total discounted reward of taking action $a$ in state $x$ and subsequently following policy $\pi$ :
$Q^\pi(x, a) = R_x(a) + \gamma \sum_{y \in X} P_{xy}[a] V^\pi(y).$
The optimal action-value function $Q^*(x, a) \equiv Q^{\pi^*}(x, a)$ and optimal state value $V^*(x) \equiv \max_{a \in A} Q^*(x, a)$ satisfy the Bellman optimality equation:
$Q^*(x, a) = R_x(a) + \gamma \sum_{y \in X} P_{xy}[a] \max_{b \in A} Q^*(y, b).$
Once $Q^*(x, a)$ is known, an optimal stationary policy $\pi^*$ can be extracted directly without knowledge of the model parameters $P_{xy}[a]$ or $R_x(a)$ via the greedy rule:
$\pi^*(x) = \arg\max_{a \in A} Q^*(x, a).$
Knowl 4 — Action-Replay Process Equivalence to Q-Learning Estimates
model/method
The Action-Replay Process (ARP) is an artificial controlled Markov decision process constructed from an observed history of transition tuples $(x_t, a_t, y_t, r_t, \alpha_t)$ and initial values $Q_0(x, a)$ . States in the ARP are pairs $(x, n)$ (denoting process state $x \in X$ at history level/step $n$ ) plus a terminal absorbing state.

When executing action $a$ at state $(x, n)$ in the ARP, the process searches backward through past episodes $t \le n$ matching $(x, a)$ . At the most recent matching episode $t$ , a coin with head probability $\alpha_t$ is flipped:
- On heads, the episode is replayed: reward $r_t$ is emitted, and the process transitions to state $(y_t, t - 1)$ .
- On tails, episode $t$ is discarded and the search continues for the next prior match.
- If no prior match exists (reaching level $0$ ), the ARP transitions to the absorbing state and emits terminal reward $Q_0(x, a)$ .
By backwards induction on the levels $n$ , the optimal action-value function of the ARP, denoted $Q^*_{\text{ARP}}((x, n), a)$ , is identically equal to the $Q$ -learning iterate:
$Q^*_{\text{ARP}}((x, n), a) = Q_n(x, a) \quad \forall x \in X, a \in A, n \ge 0.$
Knowl 5 — Q-Learning Convergence in Undiscounted Absorbing MDPs
theoretical result
Tabular Q-learning converges almost surely to $Q^*(x, a)$ in undiscounted Markov decision processes ( $\gamma = 1$ ) provided the environment contains one or more absorbing goal states that trap the agent with probability 1 under any policy.

Formally, if for every state $x \in X$ there exists a step count $u(x)$ and probability $p(x) > 0$ such that the agent reaches a goal state within $u(x)$ actions regardless of the action sequence, let $u^* = \max_{x} u(x)$ and $p^* = \min_{x} p(x) > 0$ . Then the value under any policy is uniformly bounded:
$|V^\pi(x)| \le \frac{u^* \mathcal{R}}{p^*},$
where $\mathcal{R}$ is the reward bound ( $|r_n| \le \mathcal{R}$ ). The guaranteed absorption bounds the effective horizon, replacing the role of $\gamma < 1$ in ensuring that the finite-horizon truncation error vanishes as horizon $s \to \infty$ .
Knowl 6 — Convergence Under Simultaneous Multi-State Q-Updates
theoretical result
The convergence of tabular Q-learning to $Q^*(x, a)$ with probability 1 extends directly to asynchronous settings where multiple state-action pairs $(x, a)$ are updated simultaneously in each iteration $n$ , rather than updating only the single pair $(x_n, a_n)$ visited by the trajectory.

As long as the stochastic approximation conditions:
$\sum_{i=1}^\infty \alpha_{n^i(x, a)} = \infty \quad \text{and} \quad \sum_{i=1}^\infty \left[\alpha_{n^i(x, a)}\right]^2 < \infty$
hold for each state-action pair $(x, a)$ , the Action-Replay Process accommodates multiple actions per level without altering the optimal action-value equivalence $Q_n(x, a) = Q^*_{\text{ARP}}((x, n), a)$ or the asymptotic convergence.
Knowl 7 — Value Discrepancy Bound for Perturbed Finite-Horizon Markov Chains
theoretical result
Let an $s$ -step non-stationary Markov chain have transition matrices $P^i_{xy}[a]$ and expected reward functions $R^i_x(a)$ for steps $i = 1, \dots, s$ , and let a target Markov chain have transition matrix $P_{xy}[a]$ and expected rewards $R_x(a)$ bounded by $|R_x(a)| \le \mathcal{R}$ .

If for a given $\eta > 0$ the step-wise parameters satisfy:
$|R^i_x(a) - R_x(a)| < \eta \quad \text{and} \quad |P^i_{xy}[a] - P_{xy}[a]| < \frac{\eta}{\mathcal{R}} \quad \forall i \in \{1, \dots, s\}, x, y \in X, a \in A,$
then the expected undiscounted return of executing any sequence of $s$ actions $(a_1, \dots, a_s)$ from state $x$ in the concatenated chain, $\bar{Q}'(x, a_1, \dots, a_s)$ , and in the target process, $\bar{Q}(x, a_1, \dots, a_s)$ , satisfies:
$|\bar{Q}'(x, a_1, \dots, a_s) - \bar{Q}(x, a_1, \dots, a_s)| < \frac{s(s+1)}{2} \eta.$
The value discrepancy between two approximately equal Markov processes grows at most quadratically with the horizon length $s$ .
Knowl 8 — Representation and Multi-Step Update Limitations
limitation
The convergence theorem of Watkins and Dayan (1992) has two stated theoretical limitations:
1. Look-Up Table Requirement: The proof relies fundamentally on discrete look-up table representations where each state-action pair $Q(x, a)$ is stored independently. The convergence guarantee does not hold for general parameterized function approximators, where Q-learning can fail to converge.
2. Single-Step Temporal Differences: The proof is restricted to 1-step updates where targets use $r_n + \gamma \max_b Q_{n-1}(y_n, b)$ . It does not extend directly to multi-step return or eligibility trace extensions such as $\text{TD}(\lambda)$ or $Q(\lambda)$ (for $\lambda > 0$ ), which require alternative stochastic approximation techniques.

Coverage note — None was omitted; all key theoretical definitions, convergence results, algorithmic rules, proof mechanisms (Action-Replay Process), extensions, and stated limitations are fully covered.

References

1.Barto, A.G., Bradtke, S.J. & Singh, S.P. (1991). Real-time learning and control using asynchronous dynamic programming. (COINS technical report 91-57). Amherst: University of Massachusetts.
2.Barto, A.G. & Singh, S.P. (1990). On the computational economics of reinforcement learning. In D.S. Touretzky, J. Elman, T.J. Sejnowski & G.E. Hinton, (Eds.), Proceedings of the 1990 Connectionist Models Summer School. San Mateo, CA: Morgan Kaufmann.
3.Bellman, R.E. & Dreyfus, S.E. (1962). Applied dynamic programming. RAND Corporation.
4.Chapman, D. & Kaelbling, L.P. (1991). Input generalization in delayed reinforcement learning: An algorithm and performance comparisons. Proceedings of the 1991 International Joint Conference on Artificial Intelligence (pp. 726-731).
5.Kushner, H. & Clark, D. (1978). Stochastic approximation methods for constrained and unconstrained systems. Berlin, Germany: Springer-Verlag.
6.Lin, L. (1992). Self-improving reactive agents based on reinforcement learning, planning and teaching. Machine Learning, 8.
7.Mahadevan & Connell (1991). Automatic programming of behavior-based robots using reinforcement learning. Proceedings of the 1991 National Conference on AI (pp. 768-773).
8.Ross, S. (1983). Introduction to stochastic dynamic programming. New York, Academic Press.
9.Sato, M., Abe, K. & Takeda, H. (1988). Learning control of finite Markov chains with explicit trade-off between estimation and control. IEEE Transactions on Systems, Man and Cybernetics, 18, pp. 677-684.
10.Sutton, R.S. (1984). Temporal credit assignment in reinforcement learning. PhD Thesis, University of Massachusetts, Amherst, MA.
11.Sutton, R.S. (1988). Learning to predict by the methods of temporal difference. Machine Learning, 3, pp. 9-44.
12.Sutton. R.S. (1990). Integrated architectures for learning, planning, and reacting based on approximating dynamic programming. Proceedings of the Seventh International Conference on Machine Learning. San Mateo, CA: Morgan Kaufmann.
13.Watkins, C.J.C.H. (1989). Learning from delayed rewards. PhD Thesis, University of Cambridge, England.
14.Werbos, P.J. (1977). Advanced forecasting methods for global crisis warning and models of intelligence. General Systems Yearbook, 22, pp. 25-38.

Citation

MLA

Watkins, C. J. C. H., and P. Dayan. “Technical Note: Q-Learning”. Machine Learning, vol. 8, nos. 3-4, 1992, pp. 279–92, https://doi.org/10.1023/A:1022676722315.

APA

Watkins, C. J. C. H., & Dayan, P. (1992). Technical Note: Q-Learning. Machine Learning, 8(3-4), 279–292. https://doi.org/10.1023/A:1022676722315

Chicago

Watkins, C. J. C. H., and P. Dayan. 1992. “Technical Note: Q-Learning”. Machine Learning 8 (3-4): 279–92. https://doi.org/10.1023/A:1022676722315.

Harvard

Watkins, C.J.C.H. and Dayan, P. (1992) “Technical Note: Q-Learning”, Machine Learning, 8(3-4), pp. 279–292. Available at: https://doi.org/10.1023/A:1022676722315.

Vancouver

1. Watkins CJCH, Dayan P (1992) Technical Note: Q-Learning. Machine Learning 8:279–292

BibTeX

@article{Watkins_1992, title={Technical Note: Q-Learning}, volume={8}, ISSN={1573-0565}, url={http://dx.doi.org/10.1023/A:1022676722315}, DOI={10.1023/a:1022676722315}, number={3-4}, journal={Machine Learning}, publisher={Springer Science and Business Media LLC}, author={Watkins, Christopher J.C.H. and Dayan, Peter}, year={1992}, month=May, pages={279–292} }

Metadata:Crossref

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

Technical Note: Q-Learning

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Convergence Theorem of Tabular Q-Learning

Knowl 2 — Tabular Q-Learning Algorithm

Knowl 3 — Action-Value Function and Model-Free Optimal Policy Extraction

Knowl 4 — Action-Replay Process Equivalence to Q-Learning Estimates

Knowl 5 — Q-Learning Convergence in Undiscounted Absorbing MDPs

Knowl 6 — Convergence Under Simultaneous Multi-State Q-Updates

Knowl 7 — Value Discrepancy Bound for Perturbed Finite-Horizon Markov Chains

Knowl 8 — Representation and Multi-Step Update Limitations

References

Citation

BibTeX

Access the Paper