Proving that tabular Q-learning converges

From a previous note:

The convergence guarantee: Tabular Q-learning converges to $Q^*$ with probability 1, provided the following conditions hold:

• Every $(s,a)$ pair is visited infinitely often.
• The learning rate decays correctly: $\sum_t \alpha_t = \infty$ but $\sum_t \alpha_t^2 < \infty$ → the steps must be large enough in total to travel any distance, but shrink fast enough to stop the noise from perpetually jostling the estimate.
• Bounded rewards, and $\gamma < 1$ (or a proper finite horizon).
• 🔑 ^ under these conditions, the nudging provably drives $Q \rightarrow Q^*$. The mechanism for this proof is a fixed-point argument: the Bellman optimality operator $\mathcal{T}$ is a contraction in the max-norm with factor $\gamma$, so repeatedly applying it pulls any starting estimate toward its unique fixed point $Q^*$. Q-learning is a stochastic, sampled version of iterating that contraction: each update applies $\mathcal{T}$ approximately, using one sampled $s'$ in place of the true expectation, and the decaying step size averages out the sampling noise so the approximate iteration still lands on the same fixed point.

In this note, we prove this.