Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Drift
Xinyu Liu, Zixuan Xie, Shangtong Zhang · 2026
Read Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Drift by Xinyu Liu, Zixuan Xie, Shangtong Zhang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-07104.txt.
Description
Xinyu Liu, Zixuan Xie, and Shangtong Zhang derive convergence rates for stochastic approximation under noise that depends on the past. Such methods power reinforcement learning algorithms like Q-learning, but proving how fast they settle when noise is Markovian has been a stubborn problem. The authors study methods whose average update shrinks toward the answer.
They obtain rates that hold almost surely, coming close to the best possible rate in the harmonic step-size case. The key tool combines a correction based on the Poisson equation with a smoothing technique for contractive maps. Their results cover a learning-rate range used widely in practice and give firmer ground for learning theory.
Catalog record
| CREATOR | Xinyu Liu, Zixuan Xie, Shangtong Zhang |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 90 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.07104