# Convergence of Stochastic Approximation via Martingale and Converse Lyapunov Methods

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 1 of its 26 references that are in the map.
- First posted on arXiv 3 May 2022.

## Builds on (most cited first, 1 of 1)

- [Convergence of sequences: a survey](https://mlsanity.com/paper/2111.11374/) (2021)

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

- [Convergence Rates for Stochastic Approximation: Biased Noise with Unbounded Variance, and Applications](https://mlsanity.com/paper/2312.02828/) (2023)
- [Why Target Networks Stabilise Temporal Difference Methods](https://mlsanity.com/paper/2302.12537/) (2023)
- [Extensions of Robbins-Siegmund Theorem with Applications in Reinforcement Learning](https://mlsanity.com/paper/2509.26442/) (2025)
- [A Tutorial Introduction to Reinforcement Learning](https://mlsanity.com/paper/2304.00803/) (2023)
- [Does Worst-Performing Agent Lead the Pack? Analyzing Agent Dynamics in Unified Distributed SGD](https://mlsanity.com/paper/2409.17499/) (2024)
- [Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Drift](https://mlsanity.com/paper/2605.07104/) (2026)
- [Convergence of Batch Updating Methods with Approximate Gradients and/or Noisy Measurements: Theory and Computational Results](https://mlsanity.com/paper/2209.05372/) (2022)
- [Convergence of Two Time-Scale Stochastic Approximation: A Martingale Approach](https://mlsanity.com/paper/2603.14481/) (2026)

## Abstract (arXiv)

In this paper, we study the almost sure boundedness and the convergence of the stochastic approximation (SA) algorithm. At present, most available convergence proofs are based on the ODE method, and the almost sure boundedness of the iterations is an assumption and not a conclusion. In Borkar-Meyn (2000), it is shown that if the ODE has only one globally attractive equilibrium, then under additional assumptions, the iterations are bounded almost surely, and the SA algorithm converges to the desired solution. Our objective in the present paper is to provide an alternate proof of the above, based on martingale methods, which are simpler and less technical than those based on the ODE method. As a prelude, we prove a new sufficient condition for the global asymptotic stability of an ODE. Next we prove a "converse" Lyapunov theorem on the existence of a suitable Lyapunov function with a globally bounded Hessian, for a globally exponentially stable system. Both theorems are of independent interest to researchers in stability theory. Then, using these results, we provide sufficient conditions for the almost sure boundedness and the convergence of the SA algorithm. We show through examples that our theory covers some situations that are not covered by currently known results, specifically Borkar-Meyn (2000).