# A Statistical Analysis of Polyak-Ruppert Averaged Q-learning

arXiv: https://arxiv.org/abs/2112.14582 · HTML: https://mlsanity.com/paper/2112.14582/

## 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 (most cited first, 30 of 38)

- [Continuous control with deep reinforcement learning](https://mlsanity.com/paper/1509.02971/) (2015)
- [Doubly Robust Off-policy Value Evaluation for Reinforcement Learning](https://mlsanity.com/paper/1511.03722/) (2015)
- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [Understanding the impact of entropy on policy optimization](https://mlsanity.com/paper/1811.11214/) (2018)
- [Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization](https://mlsanity.com/paper/2007.06558/) (2020)
- [Maximum Entropy RL (Provably) Solves Some Robust RL Problems](https://mlsanity.com/paper/2103.06257/) (2021)
- [Minimax Weight and Q-Function Learning for Off-Policy Evaluation](https://mlsanity.com/paper/1910.12809/) (2019)
- [Taming the Noise in Reinforcement Learning via Soft Updates](https://mlsanity.com/paper/1512.08562/) (2015)
- [Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal](https://mlsanity.com/paper/1906.03804/) (2019)
- [Double Reinforcement Learning for Efficient Off-Policy Evaluation in Markov Decision Processes](https://mlsanity.com/paper/1908.08526/) (2019)
- [Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2005.12900/) (2020)
- [Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learning](https://mlsanity.com/paper/2002.00260/) (2020)
- [Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction](https://mlsanity.com/paper/2006.03041/) (2020)
- [Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis](https://mlsanity.com/paper/2102.06548/) (2021)
- [Variance-Reduced Methods for Machine Learning](https://mlsanity.com/paper/2010.00892/) (2020)
- [Towards Instance-Optimal Offline Reinforcement Learning with Pessimism](https://mlsanity.com/paper/2110.08695/) (2021)
- [Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learning](https://mlsanity.com/paper/1905.06265/) (2019)
- [Variance-reduced Q-learning is minimax optimal](https://mlsanity.com/paper/1906.04697/) (2019)
- [Statistical Inference for Model Parameters in Stochastic Gradient Descent](https://mlsanity.com/paper/1610.08637/) (2016)
- [On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration](https://mlsanity.com/paper/2004.04719/) (2020)
- [Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learning](https://mlsanity.com/paper/1905.11425/) (2019)
- [Estimating Dynamic Treatment Regimes in Mobile Health Using V-learning](https://mlsanity.com/paper/1611.03531/) (2016)
- [Statistical Inference of the Value Function for Reinforcement Learning in Infinite Horizon Settings](https://mlsanity.com/paper/2001.04515/) (2020)
- [Asymptotically Efficient Off-Policy Evaluation for Tabular Reinforcement Learning](https://mlsanity.com/paper/2001.10742/) (2020)
- [Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes](https://mlsanity.com/paper/1710.09988/) (2017)
- [A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variants](https://mlsanity.com/paper/2102.01567/) (2021)
- [Stochastic Heavy Ball](https://mlsanity.com/paper/1609.04228/) (2016)
- [Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis](https://mlsanity.com/paper/2003.07337/) (2020)
- [Q-learning with Nearest Neighbors](https://mlsanity.com/paper/1802.03900/) (2018)
- [Online Covariance Matrix Estimation in Stochastic Gradient Descent](https://mlsanity.com/paper/2002.03979/) (2020)

## Built on by (most cited first, 29 of 29)

- [Sample Complexity of Variance-reduced Distributionally Robust Q-learning](https://mlsanity.com/paper/2305.18420/) (2023)
- [Maximum Entropy Reinforcement Learning via Energy-Based Normalizing Flow](https://mlsanity.com/paper/2405.13629/) (2024)
- [Online Statistical Inference for Nonlinear Stochastic Approximation with Markovian Data](https://mlsanity.com/paper/2302.07690/) (2023)
- [Constant Stepsize Q-learning: Distributional Convergence, Bias and Extrapolation](https://mlsanity.com/paper/2401.13884/) (2024)
- [Rates of Convergence in the Central Limit Theorem for Markov Chains, with an Application to TD Learning](https://mlsanity.com/paper/2401.15719/) (2024)
- [Tight Finite Time Bounds of Two-Time-Scale Linear Stochastic Approximation with Markovian Noise](https://mlsanity.com/paper/2401.00364/) (2023)
- [Variance-aware robust reinforcement learning with linear function approximation under heavy-tailed rewards](https://mlsanity.com/paper/2303.05606/) (2023)
- [Estimation and Inference in Distributional Reinforcement Learning](https://mlsanity.com/paper/2309.17262/) (2023)
- [Efficient Reinforcement Learning for Global Decision Making in the Presence of Local Agents at Scale](https://mlsanity.com/paper/2403.00222/) (2024)
- [Online covariance estimation for stochastic gradient descent under Markovian sampling](https://mlsanity.com/paper/2308.01481/) (2023)
- [Optimal Sample Complexity of Stable Discounted Markov Decision Processes](https://mlsanity.com/paper/2302.07477/) (2023)
- [Extensions of Robbins-Siegmund Theorem with Applications in Reinforcement Learning](https://mlsanity.com/paper/2509.26442/) (2025)
- [A General-Purpose Theorem for High-Probability Bounds of Stochastic Approximation with Polyak Averaging](https://mlsanity.com/paper/2505.21796/) (2025)
- [Central Limit Theorems for Asynchronous Averaged Q-Learning](https://mlsanity.com/paper/2509.18964/) (2025)
- [A Minimal-Assumption Analysis of Q-Learning with Time-Varying Policies](https://mlsanity.com/paper/2510.16132/) (2025)
- [Asymptotic Time-Uniform Inference for Parameters in Averaged Stochastic Approximation](https://mlsanity.com/paper/2410.15057/) (2024)
- [A Piecewise Lyapunov Analysis of Sub-quadratic SGD: Applications to Robust and Quantile Regression](https://mlsanity.com/paper/2504.08178/) (2025)
- [Asymptotic Analysis of Sample-averaged Q-learning](https://mlsanity.com/paper/2410.10737/) (2024)
- [Parameter-free Optimal Rates for Nonlinear Semi-Norm Contractions with Applications to Q-Learning](https://mlsanity.com/paper/2508.05984/) (2025)
- [Optimism Stabilizes Thompson Sampling for Adaptive Inference](https://mlsanity.com/paper/2602.06014/) (2026)
- [Parameter-Free Federated TD Learning with Markov Noise in Heterogeneous Environments](https://mlsanity.com/paper/2510.07436/) (2025)
- [Gaussian Approximation for Asynchronous Q-learning](https://mlsanity.com/paper/2604.07323/) (2026)
- [Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Drift](https://mlsanity.com/paper/2605.07104/) (2026)
- [Online Inference for Quantile Temporal Difference Learning in Distributional Reinforcement Learning](https://mlsanity.com/paper/2608.12973/) (2026)
- [Variance-Reduced Cascade Q-learning: Algorithms and Sample Complexity](https://mlsanity.com/paper/2408.06544/) (2024)
- [Sharp asymptotic theory for Q-learning with LDTZ learning rate and its generalization](https://mlsanity.com/paper/2604.04218/) (2026)
- [On Gaussian approximation for entropy-regularized Q-learning with function approximation](https://mlsanity.com/paper/2605.17678/) (2026)
- [Mathematical methods of reinforcement learning](https://mlsanity.com/paper/2607.06935/) (2026)
- [Adaptive Finite-Budget Training for CVaR Risk-Aware Q-Learning](https://mlsanity.com/paper/2608.04305/) (2026)

## 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.