mlsanityData to 14 Oct 2026

Non-Asymptotic Convergence of Stochastic Iterative Algorithms: A Lyapunov Framework

arXiv 2605.31309 ↗First posted 29 May 2026cs.LG math.PR stat.MLcited by 1

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

We survey Lyapunov-based techniques for the finite-time analysis of stochastic iterative algorithms, also known as stochastic approximation (SA) algorithms, for solving fixed-point equations barF(x)=x, where the operator barF(·) can only be accessed through a noisy oracle. We first focus on the standard setting in which barF(·) is contractive with respect to some norm and the noise is i.i.d., and explain how generalized Moreau envelopes serve as universal Lyapunov functions, regardless of the underlying norm. We then show how this framework yields mean-square convergence guarantees and applies to stochastic gradient descent, linear SA, and value-based reinforcement learning algorithms such as Q-learning and temporal-difference learning. Finally, we discuss extensions to Markovian noise, seminorm-contractive operators, dissipative operators, and high-probability bounds, and conclude with open problems. The goal is to present a unified and self-contained roadmap for the finite-time analysis of SA and its applications, especially in reinforcement learning.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 58 of its 121 references that are in the map. First posted on arXiv 29 May 2026.

Builds on

58 of 121 references.

Closest ancestors · 9

Same direction, newest first

  1. 2026Regret and Sample Complexity of Online Q-Learning via Concentration of Stochastic Approximation with Time-Inhomogeneous Markov Chains18 Feb
  2. 2025A Minimal-Assumption Analysis of Q-Learning with Time-Varying Policies17 Oct
  3. 2025Finite-Time Bounds for Two-Time-Scale Stochastic Approximation with Arbitrary Norm Contractions and Markovian Noise24 Mar
  4. 2025Finite-Sample Analysis of Policy Evaluation for Robust Average Reward Reinforcement Learning24 Feb
  5. 2025Linear Q-Learning Does Not Diverge in L2: Convergence Rates to a Bounded Set31 Jan
  6. 2024Almost Sure Convergence Rates and Concentration of Stochastic Approximation and Reinforcement Learning with Markovian Noise20 Nov
  7. 2024Stochastic Approximation with Unbounded Markovian Noise: A General-Purpose Theorem29 Oct
  8. 2024Prelimit Coupling and Steady-State Convergence of Constant-stepsize Nonsmooth Contractive SA9 Apr
  9. 2024Constant Stepsize Q-learning: Distributional Convergence, Bias and Extrapolation25 Jan

Other references · 49

  1. 2022Training language models to follow instructions with human feedbackcited by 15,971
  2. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,150
  3. 2018IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architecturescited by 883
  4. 2015End-to-End Training of Deep Visuomotor Policiescited by 875
  5. 2016Safe and Efficient Off-Policy Reinforcement Learningcited by 264
  6. 2021Reinforcement learning based recommender systems: A surveycited by 188
  7. 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 166
  8. 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 109
  9. 2019A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Normcited by 106
  10. 2020Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learningcited by 96
  11. 2020Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reductioncited by 95
  12. 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 92
37 more
  1. 2019Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learningcited by 77
  2. 2020On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentrationcited by 68
  3. 2019Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learningcited by 67
  4. 2020Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noisecited by 53
  5. 2016Q(λ) with Off-Policy Correctionscited by 48
  6. 2022Finite-time High-probability Bounds for Polyak-Ruppert Averaged Iterates of Linear Stochastic Approximationcited by 41
  7. 2023A Finite Sample Complexity Bound for Distributionally Robust Q-learningcited by 36
  8. 2020Nonlinear Two-Time-Scale Stochastic Approximation: Convergence and Finite-Time Performancecited by 35
  9. 2021The ODE Method for Asymptotic Statistics in Stochastic Approximation and Reinforcement Learningcited by 32
  10. 2022First-order Policy Optimization for Robust Markov Decision Processcited by 32
  11. 2022Target Network and Truncation Overcome The Deadly Triad in Q-Learningcited by 31
  12. 2019Simple and optimal high-probability bounds for strongly-convex stochastic gradient descentcited by 27
  13. 2021Tight High Probability Bounds for Linear Stochastic Approximation with Fixed Stepsizecited by 27
  14. 2020Fictitious play in zero-sum stochastic gamescited by 26
  15. 2023Concentration of Contractive Stochastic Approximation: Additive and Multiplicative Noisecited by 26
  16. 2013On Lower Complexity Bounds for Large-Scale Smooth Convex Optimizationcited by 24
  17. 2022Stochastic fixed-point iterations for nonexpansive maps: Convergence and error boundscited by 24
  18. 2021Concentration of Contractive Stochastic Approximation and Reinforcement Learningcited by 23
  19. 2022A unified stochastic approximation framework for learning in gamescited by 23
  20. 2022Finite time analysis of temporal difference learning with linear function approximation: Tail averaging and regularisationcited by 23
  21. 2023Improved High-Probability Bounds for the Temporal Difference Learning Algorithm via Exponential Stabilitycited by 20
  22. 2019Finite-Time Analysis and Restarting Scheme for Linear Two-Time-Scale Stochastic Approximationcited by 18
  23. 2021Finite-Sample Analysis of Off-Policy TD-Learning via Generalized Bellman Operatorscited by 17
  24. 2022Stochastic linear optimization never overfits with quadratically-bounded losses on general datacited by 17
  25. 2015A Concentration Bound for Stochastic Approximation via Alekseev's Formulacited by 16
  26. 2023High-probability sample complexities for policy evaluation with linear function approximationcited by 16
  27. 2023Asymptotic normality and optimality in nonsmooth stochastic approximationcited by 14
  28. 2013Concentration bounds for temporal difference learning with linear function approximation: The case of batch data and uniform samplingcited by 13
  29. 2022Stochastic Approximation with Decision-Dependent Distributions: Asymptotic Normality and Optimalitycited by 12
  30. 2021Best-Response Dynamics and Fictitious Play in Identical-Interest and Zero-Sum Stochastic Gamescited by 10
  31. 2024Revisiting Step-Size Assumptions in Stochastic Approximationcited by 10
  32. 2024Asymptotic and Finite Sample Analysis of Nonexpansive Stochastic Approximations with Markovian Noisecited by 10
  33. 2025A Non-Asymptotic Theory of Seminorm Lyapunov Stability: From Deterministic to Stochastic Iterative Algorithmscited by 10
  34. 2021Multi Timescale Stochastic Approximation: Stability and Convergencecited by 5
  35. 2024Accelerated Multi-Time-Scale Stochastic Approximation: Optimal Complexity and Applications in Reinforcement Learning and Multi-Agent Gamescited by 5
  36. 2026Concentration of General Stochastic Approximation Under Heavy-Tailed Markovian Noisecited by 5
  37. 2019Stochastic Approximation in a Markovian Framework Revisited: Lipschitz Continuity of the Poisson Equationcited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Concentration and Mean-Square Bounds for Contractive Stochastic Approximation: A Unified Elementary Approachcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024The ODE Method for Stochastic Approximation and Reinforcement Learning with Markovian Noise
  2. 2026Heavy-Tailed and Long-Range Dependent Noise in Stochastic Approximation: A Finite-Time Analysis
  3. 2024Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling
  4. 2024Markovian Foundations for Quasi-Stochastic Approximation in Two Timescales: Extended Version
  5. 2025Non-Expansive Mappings in Two-Time-Scale Stochastic Approximation: Finite-Time Analysis
  6. 2026The Bias of Nonlinear Two-Time-scale Stochastic Approximation under Constant Step-Sizes
  7. 2026Finite-Time Concentration and Convergence Rates for Projected Two-Time-Scale Stochastic Approximation with Markov Noise
  8. 2024Asynchronous Stochastic Approximation with Applications to Average-Reward Reinforcement Learning