aiqbench analysis
This research establishes the steady-state convergence of nonsmooth contractive stochastic approximation, specifically addressing Q-learning dynamics with constant stepsizes. It reveals that asymptotic bias in nonsmooth settings scales with the square root of the stepsize rather than linearly, enabling new Richardson-Romberg extrapolation techniques for bias reduction. These theoretical advances directly impact the stability and accuracy of reinforcement learning algorithms operating under noisy, non-differentiable conditions.
Prelimit Coupling and Steady-State Convergence of Constant-stepsize Nonsmooth Contractive SA
arXiv:2404.06023v3 Announce Type: replace-cross Abstract: Motivated by Q-learning, we study nonsmooth contractive stochastic approximation (SA) with constant stepsize. We focus on two important classes of dynamics: 1) nonsmooth contractive SA with additive noise, and 2) synchronous and asynchronous Q-learning, which features both additive and multiplicative noise. For both dynamics, we establish weak convergence of the iterates to a stationary limit distribution in Wasserstein distance. Furthermore, we propose a prelimit coupling technique for establishing steady-state convergence and characterize the limit of the stationary distribution as the stepsize goes to zero. Using this result, we derive that the asymptotic bias of nonsmooth SA is proportional to the square root of the stepsize, which stands in sharp contrast to smooth SA. This bias characterization allows for the use of Richardson-Romberg extrapolation for bias reduction in nonsmooth SA.
Abstract:Motivated by Q-learning, we study nonsmooth contractive stochastic approximation (SA) with constant stepsize. We focus on two important classes of dynamics: 1) nonsmooth contractive SA with additive noise, and 2) synchronous and asynchronous Q-learning, which features both additive and multiplicative noise. For both dynamics, we establish weak convergence of the iterates to a stationary limit distribution in Wasserstein distance. Furthermore, we propose a prelimit coupling technique for establishing steady-state convergence and characterize the limit of the stationary distribution as the stepsize goes to zero. Using this result, we derive that the asymptotic bias of nonsmooth SA is proportional to the square root of the stepsize, which stands in sharp contrast to smooth SA. This bias characterization allows for the use of Richardson-Romberg extrapolation for bias reduction in nonsmooth SA.
Accepted at Operations Research. 77 pages, 4 figures
Machine Learning (stat.ML); Machine Learning (cs.LG); Optimization and Control (math.OC); Probability (math.PR)
arXiv:2404.06023 [stat.ML]
(or arXiv:2404.06023v3 [stat.ML] for this version)
https://doi.org/10.48550/arXiv.2404.06023 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 238 words
Related coverage
Steady-State Convergence of Stochastic Approximation
arXiv · Sep 15, 2026
Constant-Stepsize Stochastic Approximation: Finite-Time Convergence, Gaussian Approximation, and Tail Bounds
arXiv · Sep 9, 2026
Impedance MPC with Patient-Torque Estimation for Knee Rehabilitation Exoskeletons
arXiv · Jun 16, 2026
DIGing--SGLD: Decentralized and Scalable Langevin Sampling over Time--Varying Networks
arXiv · Aug 25, 2026