mlsanityData to 14 Oct 2026

Constant Stepsize Q-learning: Distributional Convergence, Bias and Extrapolation

arXiv 2401.13884 ↗First posted 25 Jan 2024stat.ML cs.LG math.OCcited by 17

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

Abstract (arXiv)

Stochastic Approximation (SA) is a widely used algorithmic approach in various fields, including optimization and reinforcement learning (RL). Among RL algorithms, Q-learning is particularly popular due to its empirical success. In this paper, we study asynchronous Q-learning with constant stepsize, which is commonly used in practice for its fast convergence. By connecting the constant stepsize Q-learning to a time-homogeneous Markov chain, we show the distributional convergence of the iterates in Wasserstein distance and establish its exponential convergence rate. We also establish a Central Limit Theory for Q-learning iterates, demonstrating the asymptotic normality of the averaged iterates. Moreover, we provide an explicit expansion of the asymptotic bias of the averaged iterate in stepsize. Specifically, the bias is proportional to the stepsize up to higher-order terms and we provide an explicit expression for the linear coefficient. This precise characterization of the bias allows the application of Richardson-Romberg (RR) extrapolation technique to construct a new estimate that is provably closer to the optimal Q function. Numerical results corroborate our theoretical finding on the improvement of the RR extrapolation method.

Key facts. Cited by 17 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 39 of its 106 references that are in the map. First posted on arXiv 25 Jan 2024.

Builds on

39 of 106 references.

References · 39

  1. 2018Is Q-learning Provably Efficient?cited by 487
  2. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 229
  3. 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 166
  4. 2013Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)cited by 111
  5. 2020Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learningcited by 96
  6. 2020Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reductioncited by 95
  7. 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 92
  8. 2017Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chainscited by 88
  9. 2019Provably Efficient Q-Learning with Low Switching Costcited by 78
  10. 2019Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learningcited by 77
  11. 2019Variance-reduced Q-learning is minimax optimalcited by 73
  12. 2020On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentrationcited by 68
27 more
  1. 2019Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learningcited by 67
  2. 2017Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processescited by 57
  3. 2021A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variantscited by 57
  4. 2020Least Squares Regression with Markovian Data: Fundamental Limits and Algorithmscited by 56
  5. 2020An Analysis of Constant Step Size SGD in the Non-convex Regime: Asymptotic Normality and Biascited by 48
  6. 2019A Finite-Time Analysis of Q-Learning with Neural Network Function Approximationcited by 47
  7. 2020Is Temporal Difference Learning Optimal? An Instance-Dependent Analysiscited by 41
  8. 2020Queueing Network Controls via Deep Reinforcement Learningcited by 41
  9. 2022Finite-time High-probability Bounds for Polyak-Ruppert Averaged Iterates of Linear Stochastic Approximationcited by 41
  10. 2021Optimal and instance-dependent guarantees for Markovian linear stochastic approximationcited by 33
  11. 2021The ODE Method for Asymptotic Statistics in Stochastic Approximation and Reinforcement Learningcited by 32
  12. 2022Bias and Extrapolation in Markovian Linear Stochastic Approximation with Constant Stepsizescited by 30
  13. 2021A Statistical Analysis of Polyak-Ruppert Averaged Q-learningcited by 29
  14. 2020Convergence of constant step stochastic gradient descent for non-smooth non-convex functionscited by 27
  15. 2021Tight High Probability Bounds for Linear Stochastic Approximation with Fixed Stepsizecited by 27
  16. 2021On the Stability of Random Matrix Product with Markovian Noise: Application to Linear Stochastic Approximation and TD Learningcited by 23
  17. 2021Concentration of Contractive Stochastic Approximation and Reinforcement Learningcited by 23
  18. 2014On TD(0) with function approximation: Concentration bounds and a centered variant with exponential convergencecited by 22
  19. 2023Online Statistical Inference for Nonlinear Stochastic Approximation with Markovian Datacited by 20
  20. 2021Finite-Sample Analysis of Off-Policy TD-Learning via Generalized Bellman Operatorscited by 17
  21. 2021Stationary Behavior of Constant Stepsize SGD Type Algorithms: An Asymptotic Characterizationcited by 13
  22. 2021On Riemannian Stochastic Approximation Schemes with Fixed Step-Sizecited by 12
  23. 2020The Mean-Squared Error of Double Q-Learningcited by 11
  24. 2013Policy Iteration for Factored MDPscited by 6
  25. 2017Fastest Convergence for Q-learningcited by 6
  26. 2022Does DQN Learn?cited by 4
  27. 2022Stochastic Gradient Descent with Dependent Data for Offline Reinforcement Learningcited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 3; 2025: 8; 2026: 6.

17 papers.

Sort:

By area:

  1. 2025Linear Q-Learning Does Not Diverge in L2: Convergence Rates to a Bounded Setcited by 12
  2. 2024Computing the Bias of Constant-step Stochastic Approximation with Markovian Noisecited by 9
  3. 2025Finite-Time Bounds for Two-Time-Scale Stochastic Approximation with Arbitrary Norm Contractions and Markovian Noisecited by 9
  4. 2024Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson-Romberg Extrapolationcited by 6
  5. 2024Two-Timescale Linear Stochastic Approximation: Constant Stepsizes Go a Long Waycited by 5
  6. 2025Extensions of Robbins-Siegmund Theorem with Applications in Reinforcement Learningcited by 5
  7. 2025A General-Purpose Theorem for High-Probability Bounds of Stochastic Approximation with Polyak Averagingcited by 4
  8. 2025Central Limit Theorems for Asynchronous Averaged Q-Learningcited by 4
  9. 2025A Minimal-Assumption Analysis of Q-Learning with Time-Varying Policiescited by 4
  10. 2025A Piecewise Lyapunov Analysis of Sub-quadratic SGD: Applications to Robust and Quantile Regressioncited by 3
  11. 2025High-Order Error Bounds for Markovian LSA with Richardson-Romberg Extrapolationcited by 1
  12. 2026Shuffling the Data, Stretching the Step-size: Sharper Bias in constant step-size SGDcited by 1
5 more
  1. 2026Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Driftcited by 1
  2. 2026Non-Asymptotic Convergence of Stochastic Iterative Algorithms: A Lyapunov Frameworkcited by 1
  3. 2026Gaussian Approximation in Wasserstein-p: Markovian Martingale Differences and Stochastic Approximationcited by 1
  4. 2026Implicit Q-Learning and SARSA: Liberating Policy Control from Step-Size Calibrationcited by 0
  5. 2026Sharp asymptotic theory for Q-learning with LDTZ learning rate and its generalizationcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025From Set Convergence to Pointwise Convergence: Finite-Time Guarantees for Average-Reward Q-Learning with Adaptive Stepsizes
  2. 2026Periodic Regularized Q-Learning
  3. 2024Prelimit Coupling and Steady-State Convergence of Constant-stepsize Nonsmooth Contractive SA
  4. 2024Two-Step Q-Learning
  5. 2024Asymptotic Analysis of Sample-averaged Q-learning
  6. 2026Gaussian Approximation for Asynchronous Q-learning
  7. 2026Non-asymptotic Convergence of Average-reward Q-learning with Options
  8. 2026Switching Theory for Q-Learning