Q-Learning
- Introduced by
- Christopher Watkins & Peter Dayan
- Year
- 1992
- Type
- Model-free reinforcement-learning control algorithm
- Family
- Reinforcement learning
What does it do?
Q-learning, introduced by Christopher Watkins and Peter Dayan in 1992, is a model-free reinforcement-learning algorithm that learns the value of taking each action in each state — the Q-function — purely from experience, without a model of the environment.
It is off-policy: it learns the optimal action-values while following an exploratory behaviour policy, and under standard conditions it provably converges to the optimal policy.
The intuition behind the method
An agent learning by trial and error needs to know, for each situation, how good each possible action is in the long run. Q-learning maintains exactly that: a table (or function) of Q-values estimating the total future reward of taking an action in a state and behaving optimally thereafter. Each time the agent acts, observes a reward, and lands in a new state, it nudges the Q-value toward what it just experienced plus the best it believes it can do next. Crucially, it updates toward the BEST next action regardless of what it actually did next — so it can explore freely while still learning the optimal strategy.
History
Christopher Watkins introduced Q-learning in his 1989 thesis, and Watkins and Dayan (1992) gave the convergence proof, establishing it as a cornerstone of reinforcement learning. It generalizes temporal-difference learning to control and underpins later landmarks — notably Deep Q-Networks (Mnih et al., 2015), which combined Q-learning with deep networks to play Atari games from pixels. It is treated canonically in Sutton and Barto's textbook and remains a default starting point for value-based RL.
When to use it
Use Q-learning for sequential decision problems framed as a Markov decision process where you can sample transitions and rewards but have no (or an unreliable) model of the dynamics — control, games, routing, scheduling, and adaptive systems. Tabular Q-learning suits small, discrete state-action spaces and converges to the optimum given sufficient exploration and a decaying step size. For large or continuous spaces the table is replaced by a function approximator (Deep Q-Networks). It assumes the Markov property and a stationary environment, can be sample-inefficient, and the max operator induces an optimistic (maximization) bias addressed by variants like Double Q-learning. When a stochastic or continuous-action policy is needed, policy-gradient methods are the alternative.
Limitations and considerations
- Tabular form does not scale to large or continuous state/action spaces.
- Sample-inefficient; can need many episodes to converge.
- Maximization bias (overestimation) from the max operator; mitigated by Double Q-learning.
- Assumes a (stationary) Markov decision process; struggles under partial observability or drift.
Source conditions do not replace independent scientific review or validation by an analysis engine.
Strengths
- Model-free: needs no transition/reward model, only sampled experience.
- Off-policy: learns the optimal policy while exploring with another policy.
- Provably converges to the optimal action-values under standard conditions.
- Simple, foundational, and the basis for Deep Q-Networks and many extensions.
Applications
- Game playing and simulated control tasks.
- Robot navigation and adaptive control.
- Dynamic routing, scheduling, and resource allocation.
- Recommendation and adaptive interaction policies.
- A baseline value-based method before Deep Q-Networks.
How it works
How it works
Q(s, a) estimates the expected discounted sum of future rewards from taking action a in state s and then acting optimally. The discount factor γ weights near rewards more than distant ones. Learning Q for all state-action pairs is equivalent to solving the control problem.
Formula
Q(s,a) \approx \mathbb{E}\!\left[\textstyle\sum_{k\ge0}\gamma^{k} r_{t+k+1}\mid s_t=s,a_t=a\right]After each transition (state s, action a, reward r, next state s'), Q-learning updates Q(s, a) by a step α toward the temporal-difference target r + γ·max over next actions of Q(s', a'). The 'max' is what makes it off-policy and points learning at the optimal value, independent of the action actually taken next.
Formula
Q(s,a) \leftarrow Q(s,a) + \alpha\big[r + \gamma \max_{a'} Q(s',a') - Q(s,a)\big]To gather experience the agent acts with an exploration policy, commonly ε-greedy: usually pick the current best action, but with probability ε pick a random one. Exploration ensures all state-action pairs are tried, which the convergence guarantee requires; ε typically decays over time.
Formula
a = \begin{cases}\arg\max_a Q(s,a) & \text{prob } 1-\epsilon\\ \text{random} & \text{prob } \epsilon\end{cases}Once Q has converged to the optimal action-values Q*, the optimal policy is simply to take, in each state, the action with the highest Q-value. In practice the greedy policy w.r.t. the current Q is extracted at the end (or used at deployment).
Formula
\pi^*(s) = \arg\max_a Q^*(s,a)
Common pitfalls
- Insufficient exploration (ε too small/decayed too fast), leaving the optimum unlearned.
- Poor learning-rate schedule, causing divergence or painfully slow learning.
- Applying tabular Q-learning to large spaces instead of a function approximator.
- Ignoring overestimation bias on stochastic problems where Double Q-learning helps.
Frequently asked questions
What does 'off-policy' mean in Q-learning?
It means Q-learning learns the value of the optimal policy while the agent follows a different (exploratory) behaviour policy. The update targets r + γ·max Q(s', a') — the best next action — not the action actually taken, so exploration does not bias the learned optimum.
How does Q-learning relate to Deep Q-Networks (DQN)?
DQN replaces the Q-table with a deep neural network that approximates Q(s, a), enabling Q-learning in large or continuous (e.g., pixel) state spaces. It adds stabilizing tricks — experience replay and a target network — but the core learning rule is Q-learning's temporal-difference update.
Why does Q-learning overestimate values?
The max operator in the update tends to select over-optimistic estimates, biasing Q upward, especially with noisy rewards. Double Q-learning reduces this by decoupling action selection from value evaluation using two estimators, yielding less biased and often better policies.
Related methods
Sources
Watkins, C. J. C. H., & Dayan, P. (1992). Q-learning. Machine Learning, 8(3–4), 279–292.
Open DOI referenceCopied.Sutton, R. S., & Barto, A. G. (2018). Reinforcement Learning: An Introduction (2nd ed.). MIT Press.
ISBN: 978-0-262-03924-6Copied.