mlsanityData to 14 Oct 2026

Explicit Mean-Square Error Bounds for Monte-Carlo and Linear Stochastic Approximation

arXiv 2002.02584 ↗First posted 7 Feb 2020math.PR cs.LG cs.SYcited by 19

Not on the map. Why?

Abstract (arXiv)

This paper concerns error bounds for recursive equations subject to Markovian disturbances. Motivating examples abound within the fields of Markov chain Monte Carlo (MCMC) and Reinforcement Learning (RL), and many of these algorithms can be interpreted as special cases of stochastic approximation (SA). It is argued that it is not possible in general to obtain a Hoeffding bound on the error sequence, even when the underlying Markov chain is reversible and geometrically ergodic, such as the M/M/1 queue. This is motivation for the focus on mean square error bounds for parameter estimates. It is shown that mean square error achieves the optimal rate of O(1/n), subject to conditions on the step-size sequence. Moreover, the exact constants in the rate are obtained, which is of great value in algorithm design.

Key facts. Cited by 19 papers in the map (data through 14 Oct 2026). First posted on arXiv 7 Feb 2020.

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2021: 5; 2022: 3; 2023: 3; 2024: 7; 2025: 1.

19 papers.

Sort:

By area:

  1. 2022Finite-time High-probability Bounds for Polyak-Ruppert Averaged Iterates of Linear Stochastic Approximationcited by 41
  2. 2021The ODE Method for Asymptotic Statistics in Stochastic Approximation and Reinforcement Learningcited by 32
  3. 2021Tight High Probability Bounds for Linear Stochastic Approximation with Fixed Stepsizecited by 27
  4. 2021On the Stability of Random Matrix Product with Markovian Noise: Application to Linear Stochastic Approximation and TD Learningcited by 23
  5. 2022Finite time analysis of temporal difference learning with linear function approximation: Tail averaging and regularisationcited by 23
  6. 2023Improved High-Probability Bounds for the Temporal Difference Learning Algorithm via Exponential Stabilitycited by 20
  7. 2021Finite-Time Convergence Rates of Nonlinear Two-Time-Scale Stochastic Approximation under Markovian Noisecited by 10
  8. 2023Streaming PCA for Markovian Datacited by 9
  9. 2023On the Statistical Benefits of Temporal Difference Learningcited by 8
  10. 2024Central Limit Theorem for Two-Timescale Stochastic Approximation with Markovian Noise: Theory and Applicationscited by 7
  11. 2024Fast Nonlinear Two-Time-Scale Stochastic Approximation: Achieving O(1/k) Finite-Sample Complexitycited by 7
  12. 2022Efficiency Ordering of Stochastic Gradient Descentcited by 6
7 more
  1. 2024Deflated Dynamics Value Iterationcited by 5
  2. 2025Central Limit Theorems for Asynchronous Averaged Q-Learningcited by 4
  3. 2024Accelerating Distributed Stochastic Optimization via Self-Repellent Random Walkscited by 2
  4. 2024Markov Chain Variance Estimation: A Stochastic Approximation Approachcited by 2
  5. 2024Does Worst-Performing Agent Lead the Pack? Analyzing Agent Dynamics in Unified Distributed SGDcited by 2
  6. 2021Finite-Time Error Bounds for Distributed Linear Stochastic Approximationcited by 1
  7. 2024Regularized Q-learning through Robust Averagingcited by 0