Q-Learning
Q-learning is an off-policy temporal-difference method that learns the optimal action-value function regardless of how the agent explores.
Learning optimal action values
Q-learning is a foundational reinforcement learning algorithm that estimates the optimal action-value function Q* directly from experience, without a model. Its defining feature is that it learns about the best policy while following a different, exploratory one — it is off-policy.
The update rule
After a transition (s, a, r, s'), Q-learning updates Q(s, a) <- Q(s, a) + alpha [ r + gamma max over a' of Q(s', a') - Q(s, a) ]. The target uses the maximum over next-state actions, which is a sampled form of the Bellman optimality equation, regardless of which action the agent actually takes next.
Off-policy learning
Because the target maximizes over next actions rather than using the action the behavior policy chose, Q-learning converges toward Q* even while exploring with, say, an epsilon-greedy policy. It learns the greedy target policy from data generated by an exploratory behavior policy. This decoupling is powerful but is also the source of some instabilities.
Convergence
In the tabular case with every state-action pair visited infinitely often and a suitably decaying learning rate, Q-learning is proven to converge to Q*. In practice, with function approximation, these guarantees weaken and care is needed.
Strengths and pitfalls
- Strength: learns the optimal policy while exploring freely.
- Strength: simple, model-free, widely applicable to discrete actions.
- Pitfall: the max operator causes overestimation bias, addressed by double Q-learning.
- Pitfall: with neural approximation it can diverge without stabilizers, motivating the deep Q-network.
Its on-policy cousin is SARSA, which uses the action actually taken instead of the maximum.