If TD learning (sutton-1988-learning-to-predict-by-the) is the algorithm for prediction, Q-learning is the algorithm for control. Together, they form the theoretical backbone of classical reinforcement learning.
The action-value function
Q(s, a) answers a specific question: “If I’m in state s and take action a right now, then follow the optimal policy afterward, what total discounted reward can I expect?” The optimal Q-function Q* satisfies the Bellman optimality equation:
Q*(s,a) = E[r + γ max_{a'} Q*(s',a')]
Once you have Q*, acting optimally is trivial: at every state, take the action with the highest Q-value.
The off-policy insight
The key contribution over on-policy TD methods: Q-learning is off-policy. The update target always uses the greedy action (max over a’), regardless of what action the agent actually took. This separation means:
- The agent can explore freely (random actions, ε-greedy, etc.)
- The Q-values still converge to the optimal policy, not the exploratory one
- You can learn from demonstrations, stored data, or any behavior policy
On-policy methods (Sarsa) update toward the action actually taken — if you explore a lot, the learned policy reflects that exploration. Q-learning always optimizes as if it were greedy, even while exploring.
Why convergence matters
Before Watkins, model-free RL algorithms were heuristics with no theoretical guarantee. Q-learning’s convergence proof (strengthened by Watkins and Dayan 1992, further by Tsitsiklis 1994) established RL on solid mathematical ground: given sufficient exploration and appropriate learning rates, Q-learning will find the optimal policy. This gave the field theoretical legitimacy.
The scalability wall — and DQN
The Q-table has one entry per (state, action) pair. For anything beyond small gridworlds, this is impossible:
- Backgammon: ~10²⁰ states
- Go: ~10^170 states
- Atari games: 210×160 pixels × 4 frames = continuous high-dimensional space
The solution, introduced 23 years later, was to replace the table with a neural network — DQN (mnih-2015-human-level-control-through-deep-reinforcement). The Q-learning update rule is identical; only the function approximator changes. The convergence proof no longer applies (neural networks + bootstrapping + off-policy is the “deadly triad”), but in practice DQN worked well enough to beat human performance on Atari.
Relationship to TD learning
Q-learning is Q-values learned by one-step TD(0). Sarsa is Q-values learned on-policy. TD(λ) applied to Q-values yields Q(λ). The unifying view: all model-free RL algorithms are bootstrapped value estimation + some form of policy improvement. Q-learning chose the simplest, most theoretically tractable combination.