Contributions
- Introduced Q-learning: the first provably convergent, model-free, off-policy RL algorithm for solving the full control problem
- Extended TD learning from prediction to control — choosing optimal actions, not just estimating values
- Defined the action-value function Q(s,a): expected cumulative reward from state s taking action a, then following the optimal policy
- Proved convergence of Q-learning to optimal Q* under standard stochastic approximation conditions
Methodology
Q-learning maintains a table Q(s,a) updated after each transition (s, a, r, s’):
Q(s,a) ← Q(s,a) + α[r + γ max_{a'} Q(s',a') − Q(s,a)]
The crucial innovation over Sarsa (on-policy) is that Q-learning is off-policy: it updates toward the greedy action (max over a’) regardless of the action actually taken. This decouples the behavior policy (which can explore) from the target policy (always greedy), enabling learning the optimal policy from any exploratory data.
The convergence proof requires: all state-action pairs visited infinitely often, learning rates satisfying Robbins-Monro conditions (Σα = ∞, Σα² < ∞), and bounded rewards.
Results
- Proved Q-learning converges with probability 1 to Q* given sufficient exploration and appropriate learning rates
- Demonstrated the algorithm on gridworld and similar small MDPs
- The Q-table representation made the result directly verifiable and theoretically clean
Limitations
- Tabular: Q-table scales exponentially with state and action space — impractical beyond toy problems (extended by DQN using neural networks)
- No generalization: separate Q-value for each (s,a) pair; nearby states share no information
- Convergence with function approximation (neural networks) is not guaranteed; the “deadly triad” (off-policy + function approximation + bootstrapping) can diverge
- Exploration is not specified — ε-greedy works in practice but has no optimality guarantee