Tabular Q-learning converges under per-pair Robbins–Monro steps and full visitation

Let $V^{\ast }$ be the unique fixed point of $T^{\ast }$ supplied by [F3], and define $Q^{†}(s,a)={\sum }_{s^{\mathrm{\prime }},\rho }p(s^{\mathrm{\prime }},\rho \mid s,a)[\rho +\gamma V^{\ast }(s^{\mathrm{\prime }})]\mathrm{.}$ For each $(s,a)$, the finite sum in [F1] gives $Q^{†}(s,a)=r(s,a)+\gamma {\sum }_{s^{\mathrm{\prime }}}P(s^{\mathrm{\prime }}\mid s,a)V^{\ast }(s^{\mathrm{\prime }})$. Thus [F2] and $T^{\ast }{V}^{\ast }=V^{\ast }$ give ${\max }_{a\in A(s)}{Q}^{†}(s,a)=V^{\ast }(s)$. Substituting this identity into [F4] yields $H{Q}^{†}=Q^{†}$. For finite lists $(x_b)$ and $(y_b)$, let $m={\max }_b\mathrm{\mid }{x}_b-y_b\mathrm{\mid }$; then $x_b\le y_b+m$ for every $b$, so ${\max }_b{x}_b\le {\max }_b{y}_b+m$, and exchanging the lists gives $\mathrm{\mid }{\max }_b{x}_b-{\max }_b{y}_b\mathrm{\mid }\le m$. Therefore, for each $(s,a)$, $\mathrm{\mid }(HQ)(s,a)-(H\tilde{Q})(s,a)\mathrm{\mid }\le \gamma {\sum }_{s^{\mathrm{\prime }},\rho }p(s^{\mathrm{\prime }},\rho \mid s,a)\mid {\max }_{b}Q(s^{\mathrm{\prime }},b)-{\max }_b\tilde{Q}(s^{\mathrm{\prime }},b)\mid \le \gamma \mathrm{\parallel }Q-\tilde{Q}{\mathrm{\parallel }}_{\mathrm{\infty }}\mathrm{.}$ Taking the maximum over $(s,a)\in D$ proves $\mathrm{\parallel }HQ-H\tilde{Q}{\mathrm{\parallel }}_{\mathrm{\infty }}\le \gamma \mathrm{\parallel }Q-\tilde{Q}{\mathrm{\parallel }}_{\mathrm{\infty }}$. Any other fixed point $Q$ would then satisfy $\mathrm{\parallel }Q-Q^{†}{\mathrm{\parallel }}_{\mathrm{\infty }}\le \gamma \mathrm{\parallel }Q-Q^{†}{\mathrm{\parallel }}_{\mathrm{\infty }}$; since $\gamma <1$, this forces $Q=Q^{†}$. By [F10], this fixed point is the pointwise maximal expected discounted return from each initial state-action pair and is attained by a greedy stationary continuation, so it is the optimal action-value function $Q^{\ast }$ in the Statement.

Put $C=\max \{\mathrm{\parallel }{Q}_0{\mathrm{\parallel }}_{\mathrm{\infty }},M\mathrm{/}(1-\gamma )\}$. Then $M+\gamma C\le C$. If $\mathrm{\parallel }{Q}_n{\mathrm{\parallel }}_{\mathrm{\infty }}\le C$, the sampled target $Y_{n+1}=R_{n+1}+\gamma {\max }_b{Q}_n(S_{n+1},b)$ lies in $[-M-\gamma C,M+\gamma C]\subseteq [-C,C]$. The update is a convex combination of $Q_n(I_n)$ and $Y_{n+1}$ because $0\le {\alpha }_{N_n(I_n)}(I_n)\le 1$; hence induction gives $\mathrm{\parallel }{Q}_n{\mathrm{\parallel }}_{\mathrm{\infty }}\le C$ for every $n$.

By induction from deterministic $Q_0$, the update and the observation measurability in the Statement make $Q_n$ ${\mathcal{F}}_n$-measurable. Define ${\xi }_{n+1}=Y_{n+1}-(H{Q}_n)(I_n)$. Expand $Y_{n+1}$ as a finite sum over $s^{\mathrm{\prime }}\in S$ and $\rho \in \mathcal{R}$ using the indicators of $(S_{n+1},R_{n+1})=(s^{\mathrm{\prime }},\rho )$. Since $Q_n$ and $I_n$ are ${\mathcal{F}}_n$-measurable, the conditional transition-reward identity in the Statement, linearity, and taking out known factors [F7]–[F8] give $E[Y_{n+1}\mid {\mathcal{F}}_n]=(H{Q}_n)(I_n)$. Thus ${\xi }_{n+1}$ is an ${\mathcal{F}}_{n+1}$-measurable martingale difference by [F6]. Step 1.2 bounds both $Y_{n+1}$ and its conditional expectation by $C$, so $\mathrm{\mid }{\xi }_{n+1}\mathrm{\mid }\le 2C$ almost surely. Rewriting the update as $Q_{n+1}(i)=Q_n(i)+{\mathbf{1}}_{\{I_n=i\}}{\alpha }_{N_n(i)}(i)[(H{Q}_n)(i)-Q_n(i)+{\xi }_{n+1}]$ shows that all hypotheses of [F9] hold for index set $D$, map $H$, fixed point $Q^{\ast }$ from step 1.1, and contraction constant $\gamma$.

Applying [F9] gives $Q_n\to Q^{\ast }$ almost surely in $\mathrm{\parallel }\cdot {\mathrm{\parallel }}_{\mathrm{\infty }}$. This is the asserted convergence.