mlsanityData to 7 Oct 2026

A General-Purpose Theorem for High-Probability Bounds of Stochastic Approximation with Polyak Averaging

arXiv 2505.21796 ↗First posted 27 May 2025stat.ML cs.LG math.PRcited by 4

Not on the map. Why?

Abstract (arXiv)

Polyak-Ruppert averaging is a widely used technique to achieve the optimal asymptotic variance of stochastic approximation (SA) algorithms, yet its high-probability performance guarantees remain underexplored in general settings. In this paper, we present a general framework for establishing non-asymptotic concentration bounds for the error of averaged SA iterates. Our approach assumes access to individual concentration bounds for the unaveraged iterates and yields a sharp bound on the averaged iterates. We also construct an example, showing the tightness of our result up to constant multiplicative factors. As direct applications, we derive tight concentration bounds for contractive SA algorithms and for algorithms such as temporal difference learning and Q-learning with averaging, obtaining new bounds in settings where traditional analysis is challenging.

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Builds on 28 of its 59 references that are in the map. First posted on arXiv 27 May 2025.

Builds on

28 of 59 references.

References · 28

  1. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 225
  2. 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 165
  3. 2013Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)cited by 110
  4. 2020Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learningcited by 93
  5. 2020Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reductioncited by 93
  6. 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 89
  7. 2020On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentrationcited by 65
  8. 2020Is Temporal Difference Learning Optimal? An Instance-Dependent Analysiscited by 41
  9. 2022Finite-time High-probability Bounds for Polyak-Ruppert Averaged Iterates of Linear Stochastic Approximationcited by 41
  10. 2022Adapting to Mixing Time in Stochastic Optimization with Markovian Datacited by 35
  11. 2021A Statistical Analysis of Polyak-Ruppert Averaged Q-learningcited by 29
  12. 2021Tight High Probability Bounds for Linear Stochastic Approximation with Fixed Stepsizecited by 26
16 more
  1. 2023Concentration of Contractive Stochastic Approximation: Additive and Multiplicative Noisecited by 26
  2. 2021Concentration of Contractive Stochastic Approximation and Reinforcement Learningcited by 23
  3. 2022Finite time analysis of temporal difference learning with linear function approximation: Tail averaging and regularisationcited by 23
  4. 2021Finite-Sample Analysis of Off-Policy Natural Actor-Critic with Linear Function Approximationcited by 22
  5. 2020Temporal Difference Learning as Gradient Splittingcited by 21
  6. 2021Instance-optimality in optimal value estimation: Adaptivity via variance-reduced Q-learningcited by 21
  7. 2021Accelerated and instance-optimal policy evaluation with linear function approximationcited by 18
  8. 2024Constant Stepsize Q-learning: Distributional Convergence, Bias and Extrapolationcited by 17
  9. 2024Rates of Convergence in the Central Limit Theorem for Markov Chains, with an Application to TD Learningcited by 17
  10. 2015A Concentration Bound for Stochastic Approximation via Alekseev's Formulacited by 16
  11. 2023High-probability sample complexities for policy evaluation with linear function approximationcited by 16
  12. 2024A Simple Finite-Time Analysis of TD Learning with Linear Function Approximationcited by 15
  13. 2023A Concentration Bound for TD(0) with Function Approximationcited by 10
  14. 2025Finite-Time Bounds for Two-Time-Scale Stochastic Approximation with Arbitrary Norm Contractions and Markovian Noisecited by 9
  15. 2025Nonasymptotic CLT and Error Bounds for Linear Two-Time-Scale Stochastic Approximationcited by 6
  16. 2025O(1/k) Finite-Time Bound for Non-Linear Two-Time-Scale Stochastic Approximationcited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 3; 2026: 1.

4 papers.

  1. 2025Can SGD Handle Heavy-Tailed Noise?cited by 15
  2. 2025Extensions of Robbins-Siegmund Theorem with Applications in Reinforcement Learningcited by 5
  3. 2025Central Limit Theorems for Asynchronous Averaged Q-Learningcited by 3
  4. 2026Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Driftcited by 0