Variance-reduced $Q$-learning is minimax optimal

Abstract

We introduce and analyze a form of variance-reduced $Q$-learning. For $\gamma$-discounted MDPs with finite state space $\mathcal{X}$ and action space $\mathcal{U}$, we prove that it yields an $\epsilon$-accurate estimate of the optimal $Q$-function in the ${\ell }_{\infty }$-norm using $\mathcal{O}\left(\left(\frac{D}{{\epsilon }^2(1-\gamma {)}^3}\right)\log \left(\frac{D}{(1-\gamma )}\right)\right)$ samples, where $D=|\mathcal{X}|\times |\mathcal{U}|$. This guarantee matches known minimax lower bounds up to a logarithmic factor in the discount complexity. In contrast, our past work shows that ordinary $Q$-learning has worst-case quartic scaling in the discount complexity.

Update from v1: new Proposition 1 on minimax optimality; updated referencing and discussion of related work

References in corpus (2)

• Stochastic approximation with cone-contractive operators: Sharp ${\ell }_{\infty }$-bounds for $Q$-learning
• Learning Linear-Quadratic Regulators Efficiently with only $\sqrt{T}$ Regret

Cited by in corpus (22)

• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model
• Finite-Time Analysis of Asynchronous Stochastic Approximation and $Q$-Learning
• On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration
• Near-Optimal Offline Reinforcement Learning via Double Variance Reduction
• Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis
• Provably Efficient Exploration in Policy Optimization
• Minimum Cost Flows, MDPs, and ${\ell }_1$-Regression in Nearly Linear Time for Dense Instances
• Finite-Sample Analysis of Stochastic Approximation Using Smooth Convex Envelopes
• Quantum Algorithms for Reinforcement Learning with a Generative Model
• Q-learning with Uniformly Bounded Variance: Large Discounting is Not a Barrier to Fast Learning
• Nearly Minimax Optimal Reinforcement Learning for Discounted MDPs
• Online Robust Reinforcement Learning with Model Uncertainty
• Instance-dependent ${\ell }_{\infty }$-bounds for policy evaluation in tabular reinforcement learning
• Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Model
• Momentum in Reinforcement Learning
• Optimal oracle inequalities for solving projected fixed-point equations
• Towards Tight Bounds on the Sample Complexity of Average-reward MDPs
• Instance-optimality in optimal value estimation: Adaptivity via variance-reduced Q-learning
• Robust Risk-Sensitive Reinforcement Learning Agents for Trading Markets
• Some Limit Properties of Markov Chains Induced by Stochastic Recursive Algorithms
• Gap-Dependent Bounds for Two-Player Markov Games
• Online Target Q-learning with Reverse Experience Replay: Efficiently finding the Optimal Policy for Linear MDPs