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

CREATORXinyu Liu, Zixuan Xie, Shangtong Zhang
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE90 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.07104

Browse the full library · About the Tower of Babel