mlsanityData to 14 Oct 2026

Almost Sure Convergence Rates and Concentration of Stochastic Approximation and Reinforcement Learning with Markovian Noise

arXiv 2411.13711 ↗First posted 20 Nov 2024cs.LG math.OC stat.MLcited by 12

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

This paper establishes the first almost sure convergence rate and the first maximal concentration bound with exponential tails for general contractive stochastic approximation algorithms with Markovian noise. As a corollary, we also obtain convergence rates in Lp. Key to our successes is a novel discretization of the mean ODE of stochastic approximation algorithms using intervals with diminishing (instead of constant) length. As applications, we provide the first almost sure convergence rate for Q-learning with Markovian samples without count-based learning rates. We also provide the first concentration bound for off-policy temporal difference learning with Markovian samples.

Key facts. Cited by 12 papers in the map (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 11 of its 84 references that are in the map. First posted on arXiv 20 Nov 2024.

Builds on

11 of 84 references.

References · 11

  1. 2019Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learningcited by 77
  2. 2021A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variantscited by 57
  3. 2021The ODE Method for Asymptotic Statistics in Stochastic Approximation and Reinforcement Learningcited by 32
  4. 2019Simple and optimal high-probability bounds for strongly-convex stochastic gradient descentcited by 27
  5. 2023Concentration of Contractive Stochastic Approximation: Additive and Multiplicative Noisecited by 26
  6. 2020Finite-Sample Analysis of Stochastic Approximation Using Smooth Convex Envelopescited by 19
  7. 2022Optimal variance-reduced stochastic approximation in Banach spacescited by 17
  8. 2015A Concentration Bound for Stochastic Approximation via Alekseev's Formulacited by 16
  9. 2019A Unified Switching System Perspective and O.D.E. Analysis of Q-Learning Algorithmscited by 15
  10. 2023A Concentration Bound for TD(0) with Function Approximationcited by 10
  11. 2024Revisiting Step-Size Assumptions in Stochastic Approximationcited by 10

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 4; 2026: 8.

12 papers.

  1. 2025Linear Q-Learning Does Not Diverge in L2: Convergence Rates to a Bounded Setcited by 12
  2. 2025Towards Formalizing Reinforcement Learning Theory: A Robbins-Siegmund Approachcited by 7
  3. 2025Finite Sample Analysis of Linear Temporal Difference Learning with Arbitrary Featurescited by 5
  4. 2025Extensions of Robbins-Siegmund Theorem with Applications in Reinforcement Learningcited by 5
  5. 2026Concentration of General Stochastic Approximation Under Heavy-Tailed Markovian Noisecited by 5
  6. 2026Almost Sure Convergence of Differential Temporal Difference Learning for Average Reward Markov Decision Processescited by 2
  7. 2026Regret and Sample Complexity of Online Q-Learning via Concentration of Stochastic Approximation with Time-Inhomogeneous Markov Chainscited by 1
  8. 2026Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Driftcited by 1
  9. 2026Non-Asymptotic Convergence of Stochastic Iterative Algorithms: A Lyapunov Frameworkcited by 1
  10. 2026Large-scale Uncertainty Quantification for Latent Variable Models Using Subsampling Markov Chain Monte Carlocited by 0
  11. 2026Concentration and Mean-Square Bounds for Contractive Stochastic Approximation: A Unified Elementary Approachcited by 0
  12. 2026Shrinking-Tube Concentration for Adaptive Markovian Stochastic Approximationcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Stochastic Approximation with Unbounded Markovian Noise: A General-Purpose Theorem
  2. 2024Asymptotic and Finite Sample Analysis of Nonexpansive Stochastic Approximations with Markovian Noise
  3. 2024The ODE Method for Stochastic Approximation and Reinforcement Learning with Markovian Noise
  4. 2024Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling
  5. 2025Finite-Time Bounds for Two-Time-Scale Stochastic Approximation with Arbitrary Norm Contractions and Markovian Noise
  6. 2026Reinforcement Learning with Function Approximation for Non-Markov Processes
  7. 2026Convergence of Two-Timescale Markovian Stochastic Approximations with Applications in Reinforcement Learning
  8. 2023Q-Learning for Stochastic Control under General Information Structures and Non-Markovian Environments