# The ODE Method for Asymptotic Statistics in Stochastic Approximation and Reinforcement Learning

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

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 70 references that are in the map.
- First posted on arXiv 27 Oct 2021.

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

- [Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/1902.00923/) (2019)
- [Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)](https://mlsanity.com/paper/1306.2119/) (2013)
- [Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noise](https://mlsanity.com/paper/2002.01268/) (2020)
- [Non-asymptotic Analysis of Biased Stochastic Approximation Scheme](https://mlsanity.com/paper/1902.00629/) (2019)
- [Tight High Probability Bounds for Linear Stochastic Approximation with Fixed Stepsize](https://mlsanity.com/paper/2106.01257/) (2021)
- [On the Stability of Random Matrix Product with Markovian Noise: Application to Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/2102.00185/) (2021)
- [Explicit Mean-Square Error Bounds for Monte-Carlo and Linear Stochastic Approximation](https://mlsanity.com/paper/2002.02584/) (2020)
- [Stability of Stochastic Approximations with `Controlled Markov' Noise and Temporal Difference Learning](https://mlsanity.com/paper/1504.06043/) (2015)
- [Two Timescale Stochastic Approximation with Controlled Markov noise and Off-policy temporal difference learning](https://mlsanity.com/paper/1503.09105/) (2015)
- [A Generalization of the Borkar-Meyn Theorem for Stochastic Recursive Inclusions](https://mlsanity.com/paper/1502.01953/) (2015)

## Built on by (most cited first, 30 of 32)

- [Bias and Extrapolation in Markovian Linear Stochastic Approximation with Constant Stepsizes](https://mlsanity.com/paper/2210.00953/) (2022)
- [A Statistical Analysis of Polyak-Ruppert Averaged Q-learning](https://mlsanity.com/paper/2112.14582/) (2021)
- [Online Statistical Inference for Nonlinear Stochastic Approximation with Markovian Data](https://mlsanity.com/paper/2302.07690/) (2023)
- [Constant Stepsize Q-learning: Distributional Convergence, Bias and Extrapolation](https://mlsanity.com/paper/2401.13884/) (2024)
- [Rates of Convergence in the Central Limit Theorem for Markov Chains, with an Application to TD Learning](https://mlsanity.com/paper/2401.15719/) (2024)
- [A Simple Finite-Time Analysis of TD Learning with Linear Function Approximation](https://mlsanity.com/paper/2403.02476/) (2024)
- [Almost Sure Convergence Rates and Concentration of Stochastic Approximation and Reinforcement Learning with Markovian Noise](https://mlsanity.com/paper/2411.13711/) (2024)
- [Linear Q-Learning Does Not Diverge in L2: Convergence Rates to a Bounded Set](https://mlsanity.com/paper/2501.19254/) (2025)
- [Revisiting Step-Size Assumptions in Stochastic Approximation](https://mlsanity.com/paper/2405.17834/) (2024)
- [Asymptotic and Finite Sample Analysis of Nonexpansive Stochastic Approximations with Markovian Noise](https://mlsanity.com/paper/2409.19546/) (2024)
- [Stability of Q-Learning Through Design and Optimism](https://mlsanity.com/paper/2307.02632/) (2023)
- [The case for and against fixed step-size: Stochastic approximation algorithms in optimization and machine learning](https://mlsanity.com/paper/2309.02944/) (2023)
- [Towards Formalizing Reinforcement Learning Theory: A Robbins-Siegmund Approach](https://mlsanity.com/paper/2511.03618/) (2025)
- [Effectiveness of Constant Stepsize in Markovian LSA and Statistical Inference](https://mlsanity.com/paper/2312.10894/) (2023)
- [Almost Sure Convergence of Linear Temporal Difference Learning with Arbitrary Features](https://mlsanity.com/paper/2409.12135/) (2024)
- [Finite Sample Analysis of Linear Temporal Difference Learning with Arbitrary Features](https://mlsanity.com/paper/2505.21391/) (2025)
- [Extensions of Robbins-Siegmund Theorem with Applications in Reinforcement Learning](https://mlsanity.com/paper/2509.26442/) (2025)
- [Central Limit Theorems for Asynchronous Averaged Q-Learning](https://mlsanity.com/paper/2509.18964/) (2025)
- [Finite-Sample Wasserstein Error Bounds and Concentration Inequalities for Nonlinear Stochastic Approximation](https://mlsanity.com/paper/2602.02445/) (2026)
- [Does Worst-Performing Agent Lead the Pack? Analyzing Agent Dynamics in Unified Distributed SGD](https://mlsanity.com/paper/2409.17499/) (2024)
- [Asymptotic Analysis of Sample-averaged Q-learning](https://mlsanity.com/paper/2410.10737/) (2024)
- [Reinforcement Learning Design for Quickest Change Detection](https://mlsanity.com/paper/2403.14109/) (2024)
- [Optimistic Training and Convergence of Q-Learning -- Extended Version](https://mlsanity.com/paper/2602.06146/) (2026)
- [Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Drift](https://mlsanity.com/paper/2605.07104/) (2026)
- [Non-Asymptotic Convergence of Stochastic Iterative Algorithms: A Lyapunov Framework](https://mlsanity.com/paper/2605.31309/) (2026)
- [Off-OAB: Off-Policy Policy Gradient Method with Optimal Action-Dependent Baseline](https://mlsanity.com/paper/2405.02572/) (2024)
- [Markovian Foundations for Quasi-Stochastic Approximation in Two Timescales: Extended Version](https://mlsanity.com/paper/2409.07842/) (2024)
- [Reinforcement Learning for Optimal Stopping in POMDPs with Application to Quickest Change Detection](https://mlsanity.com/paper/2512.22347/) (2025)
- [Stability and Sensitivity Analysis of Relative Temporal-Difference Learning: Extended Version](https://mlsanity.com/paper/2603.27874/) (2026)
- [Vanishing L2 regularization for the softmax Multi Armed Bandit](https://mlsanity.com/paper/2605.03752/) (2026)

## Abstract (arXiv)

The paper concerns the d-dimensional stochastic approximation recursion,  θn+1= θn + αn + 1 f(θn, Phin+1)  where   Phin  is a stochastic process on a general state space, satisfying a conditional Markov property that allows for parameter-dependent noise. The main results are established under additional conditions on the mean flow and a version of the Donsker-Varadhan Lyapunov drift condition known as (DV3): (i) An appropriate Lyapunov function is constructed that implies convergence of the estimates in L4. (ii) A functional central limit theorem (CLT) is established, as well as the usual one-dimensional CLT for the normalized error. Moment bounds combined with the CLT imply convergence of the normalized covariance textsfE[ zn znT ] to the asymptotic covariance in the CLT, where zn =: (θn-θ^*)/√αn. (iii) The CLT holds for the normalized version zPRn =: √n [θPRn -θ^*], of the averaged parameters θPRn =:n-1 sumk=1nθk, subject to standard assumptions on the step-size. Moreover, the covariance in the CLT coincides with the minimal covariance of Polyak and Ruppert. (iv) An example is given where f and barf are linear in θ, and Phi is a geometrically ergodic Markov chain but does not satisfy (DV3). While the algorithm is convergent, the second moment of θn is unbounded and in fact diverges. This arXiv version represents a major extension of the results in prior versions.The main results now allow for parameter-dependent noise, as is often the case in applications to reinforcement learning.