Q-Learning Convergence

Context

Watkins1992 - Q-Learning proves almost-sure convergence of tabular Q-learning for finite controlled Markov processes under repeated exploration and standard stochastic-approximation learning-rate conditions.

Formal Statement

For a sampled transition (x_n,a_n,r_n,y_n), tabular Q-learning updates

$$Q_n(x_n,a_n)=(1-{\alpha }_n)Q_{n-1}(x_n,a_n)+{\alpha }_n\left[r_n+\gamma \underset{b}{\max }{Q}_{n-1}(y_n,b)\right].$$

All other Q-table entries remain unchanged. If rewards are bounded, every state-action pair is sampled infinitely often, action values are represented discretely, and for each state-action pair

$$\sum _i{\alpha }_{n_i(x,a)}=\infty ,\sum _i{\alpha }_{n_i(x,a)}^2<\infty ,$$

then Q_n(x,a) converges to Q*(x,a) with probability 1 for all states and actions.

Derivation / Construction

• Define an action-replay process (ARP) from the actual sequence of sampled episodes and learning rates.
• Show by construction that the learner’s current Q_n(x,a) values are the optimal action values for states at level n of the ARP.
• Show that the ARP’s empirical transition probabilities and expected rewards converge almost surely to those of the real controlled Markov process.
• Compare finite action sequences in the ARP and the real process; discounting makes long-tail differences vanish as the horizon grows.
• Conclude that the ARP optimal action values converge to the true optimal action values, hence the Q-learning table converges to Q*.

Implications

The theorem is foundational but narrow. It explains why the tabular update is legitimate under ideal exploration and representation assumptions. Modern deep Q-learning, reward-machine Q-learning, shielded Q-learning, and cooperative value factorization reuse the update shape, but each must separately justify what happens when function approximation, altered exploration, non-stationarity, or action masking breaks the original assumptions.

Links

• Watkins1992 - Q-Learning
• Q-Learning
• Temporal Difference Learning