Prelimit Coupling and Steady-State Convergence of Constant-Step-Size Nonsmooth Contractive Stochastic Approximation

Motivated by Q-learning, we study nonsmooth contractive stochastic approximation (SA) with constant step size. We establish the weak convergence of the iterates to a stationary limit distribution in Wasserstein distance. Furthermore, we develop a prelimit coupling technique to establish steady-state convergence and characterize the limit of the stationary distribution as the step size goes to zero. As an intermediate step, we prove a universal result that the general nonsmooth contractive SA is asymptotically equivalent to the nonsmooth contractive SA with only additive Gaussian noise. This result, of independent interest, serves as a powerful tool to analyze SA. By the steady-state convergence result, we show that the asymptotic bias of nonsmooth SA is proportional to the square root of the step size, which stands in sharp contrast to smooth SA. Importantly, this bias characterization enables the use of Richardson–Romberg extrapolation for bias reduction in nonsmooth SA.

Funding: Q. Xie and Y. Zhang are supported in part by the National Science Foundation (NSF) [Grants CNS-1955997, EPCN-2339794, and EPCN-2432546]. Y. Chen is supported in part by the NSF [Grants CCF-1704828 and CCF-2233152] and by the Vilas Associate Award from the University of Wisconsin–Madison.

Supplemental Material: All supplemental materials, including the code, data, and files required to reproduce the results, are available at https://doi.org/10.1287/opre.2024.1538.