mlsanityData to 14 Oct 2026

A Statistical Analysis of Polyak-Ruppert Averaged Q-learning

arXiv 2112.14582 ↗First posted 29 Dec 2021stat.ML cs.LGcited by 29

Not on the map. Why?

Abstract (arXiv)

We study Q-learning with Polyak-Ruppert averaging in a discounted Markov decision process in synchronous and tabular settings. Under a Lipschitz condition, we establish a functional central limit theorem for the averaged iteration barboldsymbolQT and show that its standardized partial-sum process converges weakly to a rescaled Brownian motion. The functional central limit theorem implies a fully online inference method for reinforcement learning. Furthermore, we show that barboldsymbolQT is the regular asymptotically linear (RAL) estimator for the optimal Q-value function boldsymbolQ^* that has the most efficient influence function. We present a nonasymptotic analysis for the ℓ∞ error, mathbbE|barboldsymbolQT-boldsymbolQ^*|∞, showing that it matches the instance-dependent lower bound for polynomial step sizes. Similar results are provided for entropy-regularized Q-learning without the Lipschitz condition.

Key facts. Cited by 29 papers in the map (data through 14 Oct 2026). Builds on 38 of its 84 references that are in the map. First posted on arXiv 29 Dec 2021.

Builds on

38 of 84 references.

References · 38

  1. 2015Continuous control with deep reinforcement learningcited by 3,407
  2. 2015Doubly Robust Off-policy Value Evaluation for Reinforcement Learningcited by 339
  3. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 229
  4. 2018Understanding the impact of entropy on policy optimizationcited by 176
  5. 2020Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularizationcited by 176
  6. 2021Maximum Entropy RL (Provably) Solves Some Robust RL Problemscited by 176
  7. 2019Minimax Weight and Q-Function Learning for Off-Policy Evaluationcited by 150
  8. 2015Taming the Noise in Reinforcement Learning via Soft Updatescited by 127
  9. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 127
  10. 2019Double Reinforcement Learning for Efficient Off-Policy Evaluation in Markov Decision Processescited by 119
  11. 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 109
  12. 2020Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learningcited by 96
26 more
  1. 2020Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reductioncited by 95
  2. 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 92
  3. 2020Variance-Reduced Methods for Machine Learningcited by 79
  4. 2021Towards Instance-Optimal Offline Reinforcement Learning with Pessimismcited by 78
  5. 2019Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learningcited by 77
  6. 2019Variance-reduced Q-learning is minimax optimalcited by 73
  7. 2016Statistical Inference for Model Parameters in Stochastic Gradient Descentcited by 71
  8. 2020On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentrationcited by 68
  9. 2019Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learningcited by 67
  10. 2016Estimating Dynamic Treatment Regimes in Mobile Health Using V-learningcited by 65
  11. 2020Statistical Inference of the Value Function for Reinforcement Learning in Infinite Horizon Settingscited by 65
  12. 2020Asymptotically Efficient Off-Policy Evaluation for Tabular Reinforcement Learningcited by 60
  13. 2017Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processescited by 57
  14. 2021A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variantscited by 57
  15. 2016Stochastic Heavy Ballcited by 42
  16. 2020Is Temporal Difference Learning Optimal? An Instance-Dependent Analysiscited by 41
  17. 2018Q-learning with Nearest Neighborscited by 37
  18. 2020Online Covariance Matrix Estimation in Stochastic Gradient Descentcited by 37
  19. 2021The ODE Method for Asymptotic Statistics in Stochastic Approximation and Reinforcement Learningcited by 32
  20. 2021Fast and Robust Online Inference with Stochastic Gradient Descent via Random Scalingcited by 28
  21. 2021Towards Theoretical Understandings of Robust Markov Decision Processes: Sample Complexity and Asymptoticscited by 27
  22. 2021Instance-optimality in optimal value estimation: Adaptivity via variance-reduced Q-learningcited by 22
  23. 2020Finite-Sample Analysis of Stochastic Approximation Using Smooth Convex Envelopescited by 19
  24. 2021Accelerated and instance-optimal policy evaluation with linear function approximationcited by 18
  25. 2019A Unified Switching System Perspective and O.D.E. Analysis of Q-Learning Algorithmscited by 15
  26. 2020Optimal oracle inequalities for solving projected fixed-point equationscited by 10

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 7; 2024: 7; 2025: 7; 2026: 8.

29 papers.

Sort:

By area:

  1. 2023Sample Complexity of Variance-reduced Distributionally Robust Q-learningcited by 29
  2. 2024Maximum Entropy Reinforcement Learning via Energy-Based Normalizing Flowcited by 26
  3. 2023Online Statistical Inference for Nonlinear Stochastic Approximation with Markovian Datacited by 20
  4. 2024Constant Stepsize Q-learning: Distributional Convergence, Bias and Extrapolationcited by 17
  5. 2024Rates of Convergence in the Central Limit Theorem for Markov Chains, with an Application to TD Learningcited by 17
  6. 2023Tight Finite Time Bounds of Two-Time-Scale Linear Stochastic Approximation with Markovian Noisecited by 15
  7. 2023Variance-aware robust reinforcement learning with linear function approximation under heavy-tailed rewardscited by 8
  8. 2023Estimation and Inference in Distributional Reinforcement Learningcited by 8
  9. 2024Efficient Reinforcement Learning for Global Decision Making in the Presence of Local Agents at Scalecited by 8
  10. 2023Online covariance estimation for stochastic gradient descent under Markovian samplingcited by 7
  11. 2023Optimal Sample Complexity of Stable Discounted Markov Decision Processescited by 6
  12. 2025Extensions of Robbins-Siegmund Theorem with Applications in Reinforcement Learningcited by 5
17 more
  1. 2025A General-Purpose Theorem for High-Probability Bounds of Stochastic Approximation with Polyak Averagingcited by 4
  2. 2025Central Limit Theorems for Asynchronous Averaged Q-Learningcited by 4
  3. 2025A Minimal-Assumption Analysis of Q-Learning with Time-Varying Policiescited by 4
  4. 2024Asymptotic Time-Uniform Inference for Parameters in Averaged Stochastic Approximationcited by 3
  5. 2025A Piecewise Lyapunov Analysis of Sub-quadratic SGD: Applications to Robust and Quantile Regressioncited by 3
  6. 2024Asymptotic Analysis of Sample-averaged Q-learningcited by 2
  7. 2025Parameter-free Optimal Rates for Nonlinear Semi-Norm Contractions with Applications to Q-Learningcited by 2
  8. 2026Optimism Stabilizes Thompson Sampling for Adaptive Inferencecited by 2
  9. 2025Parameter-Free Federated TD Learning with Markov Noise in Heterogeneous Environmentscited by 1
  10. 2026Gaussian Approximation for Asynchronous Q-learningcited by 1
  11. 2026Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Driftcited by 1
  12. 2026Online Inference for Quantile Temporal Difference Learning in Distributional Reinforcement Learningcited by 1
  13. 2024Variance-Reduced Cascade Q-learning: Algorithms and Sample Complexitycited by 0
  14. 2026Sharp asymptotic theory for Q-learning with LDTZ learning rate and its generalizationcited by 0
  15. 2026On Gaussian approximation for entropy-regularized Q-learning with function approximationcited by 0
  16. 2026Mathematical methods of reinforcement learningcited by 0
  17. 2026Adaptive Finite-Budget Training for CVaR Risk-Aware Q-Learningcited by 0