convergence of Q-learning

Q-learning updates a table of action-values by nudging each entry toward the reward plus the discounted best next value. The natural question is whether this endless nudging actually settles on the true optimal Q-function, or whether it can oscillate forever. The classic theorem says yes — in the tabular case it converges to Q* with probability one — but only under specific conditions.

Three ingredients are required. First, every state-action pair must be visited infinitely often, so no part of the table is starved. Second, the step sizes must satisfy the Robbins-Monro conditions: they must sum to infinity (enough total movement) yet have summable squares (enough damping of noise). Third, rewards must be bounded. Given these, the stochastic-approximation argument leans on the Bellman optimality operator being a γ-contraction, which pins down a unique fixed point the iterates are dragged toward.

This guarantee is fragile. Add function approximation and off-policy bootstrapping — the "deadly triad" — and the same updates can diverge. Tabular convergence is the clean baseline against which deep-RL instability is measured.