mlsanityData to 14 Oct 2026

Asymptotic Analysis of Sample-averaged Q-learning

arXiv 2410.10737 ↗First posted 14 Oct 2024cs.LG cs.IT math.ITcited by 2

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

Abstract (arXiv)

Reinforcement learning (RL) has emerged as a key approach for training agents in complex and uncertain environments. Incorporating statistical inference in RL algorithms is essential for understanding and managing uncertainty in model performance. This paper introduces a generalized framework for time-varying batch-averaged Q-learning, termed sample-averaged Q-learning (SA-QL), which extends traditional single-sample Q-learning by aggregating samples of rewards and next states to better account for data variability and uncertainty. We leverage the functional central limit theorem (FCLT) to establish a novel framework that provides insights into the asymptotic normality of the sample-averaged algorithm under mild conditions. Additionally, we develop a random scaling method for interval estimation, enabling the construction of confidence intervals without requiring extra hyperparameters. Extensive numerical experiments across classic stochastic OpenAI Gym environments, including windy gridworld and slippery frozenlake, demonstrate how different batch scheduling strategies affect learning efficiency, coverage rates, and confidence interval widths. This work establishes a unified theoretical foundation for sample-averaged Q-learning, providing insights into effective batch scheduling and statistical inference for RL algorithms.

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

Builds on

17 of 39 references.

References · 17

  1. 2017A Brief Survey of Deep Reinforcement Learningcited by 483
  2. 2020Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reductioncited by 95
  3. 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 92
  4. 2019Variance-reduced Q-learning is minimax optimalcited by 73
  5. 2016Statistical Inference for Model Parameters in Stochastic Gradient Descentcited by 71
  6. 2021The ODE Method for Asymptotic Statistics in Stochastic Approximation and Reinforcement Learningcited by 32
  7. 2021A Statistical Analysis of Polyak-Ruppert Averaged Q-learningcited by 29
  8. 2021Fast and Robust Online Inference with Stochastic Gradient Descent via Random Scalingcited by 28
  9. 2021Online Bootstrap Inference For Policy Evaluation in Reinforcement Learningcited by 26
  10. 2021Instance-optimality in optimal value estimation: Adaptivity via variance-reduced Q-learningcited by 22
  11. 2017Statistical inference using SGDcited by 21
  12. 2020Statistical Inference for Online Decision Making via Stochastic Gradient Descentcited by 17
5 more
  1. 2018HiGrad: Uncertainty Quantification for Online Learning and Stochastic Approximationcited by 13
  2. 2019On Constructing Confidence Region for Model Parameters in Stochastic Gradient Descent via Batch Meanscited by 13
  3. 2022Online Statistical Inference for Contextual Bandits via Stochastic Gradient Descentcited by 8
  4. 2023Statistical Inference with Stochastic Gradient Methods under φ-mixing Datacited by 7
  5. 2017Fastest Convergence for Q-learningcited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 1; 2026: 1.

2 papers.

  1. 2025Central Limit Theorems for Asynchronous Averaged Q-Learningcited by 4
  2. 2026Nonparametric Variance-Penalized Actor-Critic: Statistical Inference for Risk-Sensitive Reinforcement Learningcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026Online Statistical Inference of Constant Sample-averaged Q-Learning
  2. 2026Sample Complexity of Average-Reward Q-Learning: From Single-agent to Federated Reinforcement Learning
  3. 2026Non-asymptotic Convergence of Average-reward Q-learning with Options
  4. 2024Constant Stepsize Q-learning: Distributional Convergence, Bias and Extrapolation
  5. 2024On Sample-Efficient Offline Reinforcement Learning: Data Diversity, Posterior Sampling, and Beyond
  6. 2025Model-Free Robust Average-Reward Reinforcement Learning with Sample Complexity Analysis
  7. 2024ACL-QL: Adaptive Conservative Level in Q-Learning for Offline Reinforcement Learning
  8. 2022Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexity