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

arXiv: https://arxiv.org/abs/2605.31309 · HTML: https://mlsanity.com/paper/2605.31309/

## Key facts

- Cited by 1 papers 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.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 30 of 58)

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architectures](https://mlsanity.com/paper/1802.01561/) (2018)
- [End-to-End Training of Deep Visuomotor Policies](https://mlsanity.com/paper/1504.00702/) (2015)
- [Safe and Efficient Off-Policy Reinforcement Learning](https://mlsanity.com/paper/1606.02647/) (2016)
- [Reinforcement learning based recommender systems: A survey](https://mlsanity.com/paper/2101.06286/) (2021)
- [Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/1902.00923/) (2019)
- [Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2005.12900/) (2020)
- [A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Norm](https://mlsanity.com/paper/1902.03736/) (2019)
- [Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learning](https://mlsanity.com/paper/2002.00260/) (2020)
- [Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction](https://mlsanity.com/paper/2006.03041/) (2020)
- [Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis](https://mlsanity.com/paper/2102.06548/) (2021)
- [Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learning](https://mlsanity.com/paper/1905.06265/) (2019)
- [On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration](https://mlsanity.com/paper/2004.04719/) (2020)
- [Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learning](https://mlsanity.com/paper/1905.11425/) (2019)
- [Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noise](https://mlsanity.com/paper/2002.01268/) (2020)
- [Q(λ) with Off-Policy Corrections](https://mlsanity.com/paper/1602.04951/) (2016)
- [Finite-time High-probability Bounds for Polyak-Ruppert Averaged Iterates of Linear Stochastic Approximation](https://mlsanity.com/paper/2207.04475/) (2022)
- [A Finite Sample Complexity Bound for Distributionally Robust Q-learning](https://mlsanity.com/paper/2302.13203/) (2023)
- [Nonlinear Two-Time-Scale Stochastic Approximation: Convergence and Finite-Time Performance](https://mlsanity.com/paper/2011.01868/) (2020)
- [The ODE Method for Asymptotic Statistics in Stochastic Approximation and Reinforcement Learning](https://mlsanity.com/paper/2110.14427/) (2021)
- [First-order Policy Optimization for Robust Markov Decision Process](https://mlsanity.com/paper/2209.10579/) (2022)
- [Target Network and Truncation Overcome The Deadly Triad in Q-Learning](https://mlsanity.com/paper/2203.02628/) (2022)
- [Simple and optimal high-probability bounds for strongly-convex stochastic gradient descent](https://mlsanity.com/paper/1909.00843/) (2019)
- [Tight High Probability Bounds for Linear Stochastic Approximation with Fixed Stepsize](https://mlsanity.com/paper/2106.01257/) (2021)
- [Fictitious play in zero-sum stochastic games](https://mlsanity.com/paper/2010.04223/) (2020)
- [Concentration of Contractive Stochastic Approximation: Additive and Multiplicative Noise](https://mlsanity.com/paper/2303.15740/) (2023)
- [On Lower Complexity Bounds for Large-Scale Smooth Convex Optimization](https://mlsanity.com/paper/1307.5001/) (2013)
- [Stochastic fixed-point iterations for nonexpansive maps: Convergence and error bounds](https://mlsanity.com/paper/2208.04193/) (2022)
- [Concentration of Contractive Stochastic Approximation and Reinforcement Learning](https://mlsanity.com/paper/2106.14308/) (2021)

## Built on by (most cited first, 1 of 1)

- [Concentration and Mean-Square Bounds for Contractive Stochastic Approximation: A Unified Elementary Approach](https://mlsanity.com/paper/2607.17595/) (2026)

## 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.