Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Drift
Abstract
Establishing almost sure convergence rates for stochastic approximation and reinforcement learning under Markovian noise is a fundamental theoretical challenge. We make progress towards this challenge for a class of stochastic approximation algorithms whose expected updates are contractive, a setting that arises in many reinforcement learning algorithms such as Q-learning and linear temporal difference learning. Specifically, for a power-law learning rate O(n−η) with η∈ (1/2, 1), we obtain an almost sure convergence rate arbitrarily close to o(n1 − 2η). For the harmonic learning rate αn=α/(n+1), the almost sure squared-error rate is o(n−ζ) for every ζ<min{1,2(1−κ)α}, where κ is the contraction factor. Thus exponents arbitrarily close to one are available when 2(1−κ)α≥1. This approaches the n−1 polynomial exponent of classical law-of-the-iterated-logarithm benchmarks. Key to our analysis is a novel Lyapunov drift construction that applies a Poisson-equation based correction for Markovian noise to the well-established Moreau-envelope smoothing for the contractive mapping.
Related
- Flux-Matched Poisson Iteration for Generated Jacobian Equations: Local Convergence and Spectral Galerkin Approximation
- Convergence of a fully discrete approximation for the stochastic 2D Euler equations with Kraichnan transport noise
- Weak Convergence Rates for Partial-Sum Processes of Nonlinear Stochastic Approximation
- Steady-State Convergence of Stochastic Approximation
- Uniform-in-time approximation and convergence of invariant measuresfor the damped stochastic Korteweg-de Vries equation
BibTeX
@misc{liu2026almost,
title = {{Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Drift}},
author = {Xinyu Liu and Zixuan Xie and Shangtong Zhang},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2605.07104},
eprint = {2605.07104},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.07104},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Drift
AU - Xinyu Liu
AU - Zixuan Xie
AU - Shangtong Zhang
PY - 2026
DA - 2026/11/03
PB - arXiv
DO - 10.48550/arxiv.2605.07104
UR - https://arxiv.org/abs/2605.07104
AB - Establishing almost sure convergence rates for stochastic approximation and reinforcement learning under Markovian noise is a fundamental theoretical challenge. We make progress towards this challenge for a class of stochastic approximation algorithms whose expected updates are contractive, a setting that arises in many reinforcement learning algorithms such as Q-learning and linear temporal difference learning. Specifically, for a power-law learning rate O(n^−η) with η∈ (1/2, 1), we obtain an almost sure convergence rate arbitrarily close to o(n^1 − 2η). For the harmonic learning rate α_n=α/(n+1), the almost sure squared-error rate is o(n^−ζ) for every ζ<min{1,2(1−κ)α}, where κ is the contraction factor. Thus exponents arbitrarily close to one are available when 2(1−κ)α≥1. This approaches the n^−1 polynomial exponent of classical law-of-the-iterated-logarithm benchmarks. Key to our analysis is a novel Lyapunov drift construction that applies a Poisson-equation based correction for Markovian noise to the well-established Moreau-envelope smoothing for the contractive mapping.
ER -