mlsanityData to 7 Oct 2026

Concentration of Contractive Stochastic Approximation: Additive and Multiplicative Noise

arXiv 2303.15740 ↗First posted 28 Mar 2023cs.LG math.OCcited by 26

Not on the map. Why?

Abstract (arXiv)

In this paper, we establish maximal concentration bounds for the iterates generated by a stochastic approximation (SA) algorithm under a contractive operator with respect to some arbitrary norm (for example, the ℓ_∞-norm). We consider two settings where the iterates are potentially unbounded: SA with bounded multiplicative noise and SA with sub-Gaussian additive noise. Our maximal concentration inequalities state that the convergence error has a sub-Gaussian tail in the additive noise setting and a Weibull tail (which is faster than polynomial decay but could be slower than exponential decay) in the multiplicative noise setting. In addition, we provide an impossibility result showing that it is generally impossible to have sub-exponential tails under multiplicative noise. To establish the maximal concentration bounds, we develop a novel bootstrapping argument that involves bounding the moment-generating function of a modified version of the generalized Moreau envelope of the convergence error and constructing an exponential supermartingale to enable using Ville's maximal inequality. We demonstrate the applicability of our theoretical results in the context of linear SA and reinforcement learning.

Key facts. Cited by 26 papers in the map (data through 7 Oct 2026). Builds on 19 of its 53 references that are in the map. First posted on arXiv 28 Mar 2023.

Builds on

19 of 53 references.

References · 19

  1. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problemscited by 1,873
  2. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 225
  3. 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 165
  4. 2019A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Normcited by 105
  5. 2020Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learningcited by 93
  6. 2020Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reductioncited by 93
  7. 2019Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learningcited by 67
  8. 2020On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentrationcited by 65
  9. 2021A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variantscited by 57
  10. 2016Q(λ) with Off-Policy Correctionscited by 48
  11. 2022Finite-time High-probability Bounds for Polyak-Ruppert Averaged Iterates of Linear Stochastic Approximationcited by 41
  12. 2021Tight High Probability Bounds for Linear Stochastic Approximation with Fixed Stepsizecited by 26
7 more
  1. 2019Simple and optimal high-probability bounds for strongly-convex stochastic gradient descentcited by 25
  2. 2021Concentration of Contractive Stochastic Approximation and Reinforcement Learningcited by 23
  3. 2021Finite-Sample Analysis of Off-Policy TD-Learning via Generalized Bellman Operatorscited by 17
  4. 2015A Concentration Bound for Stochastic Approximation via Alekseev's Formulacited by 16
  5. 2022Stochastic linear optimization never overfits with quadratically-bounded losses on general datacited by 16
  6. 2022Optimal variance-reduced stochastic approximation in Banach spacescited by 14
  7. 2013Concentration bounds for temporal difference learning with linear function approximation: The case of batch data and uniform samplingcited by 13

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 1; 2024: 6; 2025: 11; 2026: 8.

26 papers.

Sort:

  1. 2024Rates of Convergence in the Central Limit Theorem for Markov Chains, with an Application to TD Learningcited by 17
  2. 2023Tight Finite Time Bounds of Two-Time-Scale Linear Stochastic Approximation with Markovian Noisecited by 14
  3. 2025QeRL: Beyond Efficiency -- Quantization-enhanced Reinforcement Learning for LLMscited by 13
  4. 2025Linear Q-Learning Does Not Diverge in L2: Convergence Rates to a Bounded Setcited by 11
  5. 2024Almost Sure Convergence Rates and Concentration of Stochastic Approximation and Reinforcement Learning with Markovian Noisecited by 10
  6. 2024Computing the Bias of Constant-step Stochastic Approximation with Markovian Noisecited by 9
  7. 2024Mean-Field Sampling for Cooperative Multi-Agent Reinforcement Learningcited by 9
  8. 2025Finite-Time Bounds for Two-Time-Scale Stochastic Approximation with Arbitrary Norm Contractions and Markovian Noisecited by 9
  9. 2024Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Samplingcited by 6
  10. 2024Almost Sure Convergence of Linear Temporal Difference Learning with Arbitrary Featurescited by 5
  11. 2025O(1/k) Finite-Time Bound for Non-Linear Two-Time-Scale Stochastic Approximationcited by 5
  12. 2025Finite Sample Analysis of Linear Temporal Difference Learning with Arbitrary Featurescited by 5
14 more
  1. 2025Extensions of Robbins-Siegmund Theorem with Applications in Reinforcement Learningcited by 5
  2. 2025Towards Formalizing Reinforcement Learning Theory: A Robbins-Siegmund Approachcited by 5
  3. 2025A General-Purpose Theorem for High-Probability Bounds of Stochastic Approximation with Polyak Averagingcited by 4
  4. 2025Non-Expansive Mappings in Two-Time-Scale Stochastic Approximation: Finite-Time Analysiscited by 3
  5. 2026Solving Stochastic Fixed-Point Equations with High Probabilitycited by 3
  6. 2025Statistical Guarantees for High-Dimensional Stochastic Gradient Descentcited by 2
  7. 2026Finite-Sample Wasserstein Error Bounds and Concentration Inequalities for Nonlinear Stochastic Approximationcited by 2
  8. 2026Learning Approximate Nash Equilibria in Cooperative Multi-Agent Reinforcement Learning via Mean-Field Subsamplingcited by 2
  9. 2025Parameter-Free Federated TD Learning with Markov Noise in Heterogeneous Environmentscited by 1
  10. 2026Graphon Mean-Field Subsampling for Cooperative Heterogeneous Multi-Agent Reinforcement Learningcited by 1
  11. 2026Regret and Sample Complexity of Online Q-Learning via Concentration of Stochastic Approximation with Time-Inhomogeneous Markov Chainscited by 1
  12. 2026Non-Asymptotic Convergence of Stochastic Iterative Algorithms: A Lyapunov Frameworkcited by 1
  13. 2026Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Driftcited by 0
  14. 2026Factor Augmented High-Dimensional SGDcited by 0