mlsanityData to 7 Oct 2026

Concentration of Contractive Stochastic Approximation and Reinforcement Learning

arXiv 2106.14308 ↗First posted 27 Jun 2021cs.LG cs.SY eess.SYcited by 23

Not on the map. Why?

Abstract (arXiv)

Using a martingale concentration inequality, concentration bounds `from time n0 on' are derived for stochastic approximation algorithms with contractive maps and both martingale difference and Markov noises. These are applied to reinforcement learning algorithms, in particular to asynchronous Q-learning and TD(0).

Key facts. Cited by 23 papers in the map (data through 7 Oct 2026). Builds on 14 of its 45 references that are in the map. First posted on arXiv 27 Jun 2021.

Builds on

14 of 45 references.

References · 14

  1. 2018Is Q-learning Provably Efficient?cited by 485
  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. 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. 2019Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learningcited by 74
  8. 2019Variance-reduced Q-learning is minimax optimalcited by 72
  9. 2018On Markov Chain Gradient Descentcited by 63
  10. 2021A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variantscited by 57
  11. 2020Finite-Time Analysis of Stochastic Gradient Descent under Markov Randomnesscited by 18
  12. 2015A Concentration Bound for Stochastic Approximation via Alekseev's Formulacited by 16
2 more
  1. 2013Concentration bounds for temporal difference learning with linear function approximation: The case of batch data and uniform samplingcited by 13
  2. 2019A Multistep Lyapunov Approach for Finite-Time Analysis of Biased Stochastic Approximationcited by 10

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 1; 2022: 6; 2023: 4; 2024: 2; 2025: 7; 2026: 3.

23 papers.

Sort:

  1. 2022Target Network and Truncation Overcome The Deadly Triad in Q-Learningcited by 31
  2. 2022Bias and Extrapolation in Markovian Linear Stochastic Approximation with Constant Stepsizescited by 28
  3. 2023Concentration of Contractive Stochastic Approximation: Additive and Multiplicative Noisecited by 26
  4. 2024Constant Stepsize Q-learning: Distributional Convergence, Bias and Extrapolationcited by 17
  5. 2022Reinforcement Learning in Non-Markovian Environmentscited by 10
  6. 2023A Concentration Bound for TD(0) with Function Approximationcited by 10
  7. 2024Computing the Bias of Constant-step Stochastic Approximation with Markovian Noisecited by 9
  8. 2025Finite-Time Bounds for Two-Time-Scale Stochastic Approximation with Arbitrary Norm Contractions and Markovian Noisecited by 9
  9. 2023Full Gradient Deep Reinforcement Learning for Average-Reward Criterioncited by 5
  10. 2025O(1/k) Finite-Time Bound for Non-Linear Two-Time-Scale Stochastic Approximationcited by 5
  11. 2025Extensions of Robbins-Siegmund Theorem with Applications in Reinforcement Learningcited by 5
  12. 2025A General-Purpose Theorem for High-Probability Bounds of Stochastic Approximation with Polyak Averagingcited by 4
11 more
  1. 2025Non-Expansive Mappings in Two-Time-Scale Stochastic Approximation: Finite-Time Analysiscited by 3
  2. 2025A Minimal-Assumption Analysis of Q-Learning with Time-Varying Policiescited by 3
  3. 2026Solving Stochastic Fixed-Point Equations with High Probabilitycited by 3
  4. 2023Equilibrium Bandits: Learning Optimal Equilibria of Unknown Dynamicscited by 1
  5. 2026Regret and Sample Complexity of Online Q-Learning via Concentration of Stochastic Approximation with Time-Inhomogeneous Markov Chainscited by 1
  6. 2026Non-Asymptotic Convergence of Stochastic Iterative Algorithms: A Lyapunov Frameworkcited by 1
  7. 2021A Concentration Bound for LSPE(λ)cited by 0
  8. 2022Finite-Time Accuracy of Temporal-Difference Learning Under Schur-Stable Recursionscited by 0
  9. 2022Concentration bounds for SSP Q-learning for average cost MDPscited by 0
  10. 2022A Concentration Bound for Distributed Stochastic Approximationcited by 0
  11. 2025On the Optimality of Tracking Fisher Information in Adaptive Testing with Stochastic Binary Responsescited by 0