Coordinate-wise stochastic approximation converges to a contraction fixed point

Fix $i\in I$ and put $B_{n+1}^{(i)}={\mathbf{1}}_{\{I_n=i\}}{\alpha }_{N_n(i)}(i)$. The indicator and visit count are ${\mathcal{F}}_n$-measurable, so $B_{n+1}^{(i)}$ is ${\mathcal{F}}_n$-measurable. Each visit to $i$ contributes one term ${\alpha }_k(i{)}^2$ to ${\sum }_{n\ge 0}(B_{n+1}^{(i)}{)}^2$, hence this sum is at most ${\sum }_{k\ge 0}{\alpha }_k(i{)}^2<\mathrm{\infty }$. By [F2], [F4], and the bound on $\xi$, the series ${\sum }_{n\ge 0}{B}_{n+1}^{(i)}{\xi }_{n+1}$ converges almost surely. Since $I$ is finite, these convergence events hold simultaneously for all $i$ outside one null set.

Fix an outcome in that full-measure event where all coordinates are visited infinitely often and the iterates are bounded. For a fixed $i$, let ${\tau }_i(k)$ be the time of the $(k+1)$st update of coordinate $i$, put $z_0=x_0(i)-x^{\ast }(i)$ and $z_{k+1}=x_{{\tau }_i(k)+1}(i)-x^{\ast }(i)$, and let $u_k=(T(x_{{\tau }_i(k)}))(i)-x^{\ast }(i)$ and $v_k={\alpha }_k(i){\xi }_{{\tau }_i(k)+1}$. Before the $(k+1)$st update, coordinate $i$ still has its value after the first $k$ updates, so the update and $T(x^{\ast })=x^{\ast }$ give $z_{k+1}=(1-{\alpha }_k(i))z_k+{\alpha }_k(i)u_k+v_k$. By step 1.1, ${\sum }_{k\ge 0}{v}_k$ converges; put $e_k={\sum }_{j\ge k}{v}_j$, so $e_k\to 0$. For $y_k=z_k+e_k$, the identity $e_k=v_k+e_{k+1}$ gives $y_{k+1}=(1-{\alpha }_k(i))y_k+{\alpha }_k(i)(u_k+e_k)\mathrm{.}$

Let $U_i={\mathrm{lim\hspace{0.17em}sup}}_{k\to \mathrm{\infty }}\mathrm{\mid }{u}_k\mathrm{\mid }$, which is finite because the iterates are bounded and $T$ is a contraction. For every $\epsilon >0$, eventually $\mathrm{\mid }{u}_k+e_k\mathrm{\mid }\le U_i+2\epsilon$. Iterating the convex-combination recurrence in step 2.1 from such an index $m$ bounds $\mathrm{\mid }{y}_k\mathrm{\mid }$ by a vanishing multiple of $\mathrm{\mid }{y}_m\mathrm{\mid }$ plus $U_i+2\epsilon$: the coefficient of $\mathrm{\mid }{y}_m\mathrm{\mid }$ is ${\prod }_{j=m}^{k-1}(1-{\alpha }_j(i))$, which tends to zero since ${\prod }_{j=m}^{k-1}(1-{\alpha }_j(i))\le \frac{1}{1+{\sum }_{j=m}^{k-1}{\alpha }_j(i)}⟶0.$ Thus ${\mathrm{lim\hspace{0.17em}sup}}_k\mathrm{\mid }{y}_k\mathrm{\mid }\le U_i+2\epsilon$. Letting $\epsilon \downarrow 0$ and using $e_k\to 0$ yields ${\mathrm{lim\hspace{0.17em}sup}}_k\mathrm{\mid }{z}_k\mathrm{\mid }\le U_i$.

Put $E={\mathrm{lim\hspace{0.17em}sup}}_{n\to \mathrm{\infty }}\mathrm{\parallel }{x}_n-x^{\ast }{\mathrm{\parallel }}_{\mathrm{\infty }}$, finite by boundedness. For every $\epsilon >0$, eventually $\mathrm{\parallel }{x}_n-x^{\ast }{\mathrm{\parallel }}_{\mathrm{\infty }}\le E+\epsilon$. Since ${\tau }_i(k)\to \mathrm{\infty }$, contraction gives $\mathrm{\mid }{u}_k\mathrm{\mid }=\mathrm{\mid }(T(x_{{\tau }_i(k)}))(i)-(T(x^{\ast }))(i)\mathrm{\mid }\le q\mathrm{\parallel }{x}_{{\tau }_i(k)}-x^{\ast }{\mathrm{\parallel }}_{\mathrm{\infty }}$, so $U_i\le qE$. Step 3.1 gives ${\mathrm{lim\hspace{0.17em}sup}}_k\mathrm{\mid }{z}_k\mathrm{\mid }\le qE$. Coordinate $i$ is constant between updates; since the number of its updates tends to infinity, its full-time limsup error equals the limsup of the post-update sequence $\mathrm{\mid }{z}_k\mathrm{\mid }$. Also, for finite $I$, taking a tail supremum commutes with the finite maximum, and the decreasing tail suprema commute with a finite maximum when taking their infimum; hence $E={\max }_{i\in I}{\mathrm{lim\hspace{0.17em}sup}}_n\mathrm{\mid }{x}_n(i)-x^{\ast }(i)\mathrm{\mid }$. Therefore $E\le qE$, and $0\le q<1$ forces $E=0$. Thus $\mathrm{\parallel }{x}_n-x^{\ast }{\mathrm{\parallel }}_{\mathrm{\infty }}\to 0$ on the full-measure event, proving almost-sure convergence.