Research map / Optimization / Nonconvex and smooth optimization

Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Drift

NeurIPS 2026 · Optimization › Nonconvex and smooth optimization · approach: Langevin sampling for nonconvex problems · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proves almost sure convergence rates for contractive stochastic approximation with Markovian noise by adding a Poisson-equation correction to a Moreau-envelope Lyapunov drift, yielding almost-supermartingales, and applies it to single-trajectory generalized TD.

Problem

Almost sure convergence rates for stochastic approximation and RL (e.g., Q-learning, linear TD) when the noise is Markovian and the expected update is contractive only in a possibly non-Euclidean norm.

Approach

A Poisson-Moreau drift V_n = M_xi(e_n) + alpha_n <grad M_xi(e_n), H_{theta_n}(Y_n)> + K alpha_n^2 that applies a Poisson-equation correction directly to the Moreau envelope Lyapunov function, making it an almost-nonnegative supermartingale conditionally, so almost-supermartingale rate results apply pathwise.

Key results

• For power-law learning rate with eta in (1/2,1), the iterates satisfy (n+1)^zeta ||theta_n - theta*||^2 -> 0 a.s. for any zeta in (0, 2eta-1), improving on prior skeleton-iterate rates that do not cover eta in (1/2, 2/3].
• For harmonic learning rate eta=1, almost sure rate o(n^{-1}) arbitrarily close, versus prior subpolynomial rate.
• Corollary gives L2 rates O(n^{-eta}) for all eta in (0,1] without square-summability.

Surprising findings

• The L2 convergence rate holds for all learning rate exponents in (0,1], including those not square-summable, via the same drift argument.

Limitations

• Almost sure rates are established only for eta in (1/2,1], not the full range (0,1].
• Rates are not tight relative to the law of the iterated logarithm rate O(n^-1 log log n).
• Does not provide exponential-tail high-probability concentration bounds.

Experimental setup

Metrics: almost sure convergence rate exponent L2 convergence rate

Baselines: skeleton-iterates almost sure rate (prior Markovian contractive SA work) algorithm-specific almost sure rates for Q-learning linear TD concentration analyses

Builds on: Moreau envelope smoothing for contractive SA Robbins-Siegmund almost-supermartingale theorem skeleton iterates approach Poisson equation noise decomposition generalized TD family (Q-trace, Retrace, Tree-Backup)

Closest papers by meaning

• Asymptotic and Finite Sample Analysis of Nonexpansive Stochastic Approximations with Markovian Noise (AAAI 2026 · similarity 0.91)
• Linear $Q$-Learning Does Not Diverge in $L^2$: Convergence Rates to a Bounded Set (ICML 2025 · similarity 0.89)
• Improved Lower Bounds for First-order Stochastic Non-convex Optimization under Markov Sampling (ICML 2025 · similarity 0.89)
• The Collusion of Memory and Nonlinearity in Stochastic Approximation With Constant Stepsize (NeurIPS 2024 · similarity 0.87)
• Convergence Rate in a Nonlinear Two-Time-Scale Stochastic Approximation with State (Time)-Dependence (AAAI 2025 · similarity 0.87)
• Deep Learning for Computing Convergence Rates of Markov Chains (NeurIPS 2024 · similarity 0.86)