mlsanityData to 7 Oct 2026

The Efficacy of Pessimism in Asynchronous Q-Learning

arXiv 2203.07368 ↗First posted 14 Mar 2022cs.LG cs.IT math.ITcited by 41

Not on the map. Why?

Abstract (arXiv)

This paper is concerned with the asynchronous form of Q-learning, which applies a stochastic approximation scheme to Markovian data samples. Motivated by the recent advances in offline reinforcement learning, we develop an algorithmic framework that incorporates the principle of pessimism into asynchronous Q-learning, which penalizes infrequently-visited state-action pairs based on suitable lower confidence bounds (LCBs). This framework leads to, among other things, improved sample efficiency and enhanced adaptivity in the presence of near-expert data. Our approach permits the observed data in some important scenarios to cover only partial state-action space, which is in stark contrast to prior theory that requires uniform coverage of all state-action pairs. When coupled with the idea of variance reduction, asynchronous Q-learning with LCB penalization achieves near-optimal sample complexity, provided that the target accuracy level is small enough. In comparison, prior works were suboptimal in terms of the dependency on the effective horizon even when i.i.d. sampling is permitted. Our results deliver the first theoretical support for the use of pessimism principle in the presence of Markovian non-i.i.d. data.

Key facts. Cited by 41 papers in the map (data through 7 Oct 2026). Builds on 42 of its 69 references that are in the map. First posted on arXiv 14 Mar 2022.

Builds on

42 of 69 references.

References · 42

  1. 2020Conservative Q-Learning for Offline Reinforcement Learningcited by 1,777
  2. 2020MOPO: Model-based Offline Policy Optimizationcited by 630
  3. 2020MOReL : Model-Based Offline Reinforcement Learningcited by 582
  4. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  5. 2018Is Q-learning Provably Efficient?cited by 485
  6. 2021COMBO: Conservative Offline Model-Based Policy Optimizationcited by 365
  7. 2020Is Pessimism Provably Efficient for Offline RL?cited by 362
  8. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimismcited by 275
  9. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coveragecited by 160
  10. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learningcited by 157
  11. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  12. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 124
30 more
  1. 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 108
  2. 2020Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learningcited by 93
  3. 2020Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reductioncited by 93
  4. 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 89
  5. 2022Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexitycited by 84
  6. 2021Towards Instance-Optimal Offline Reinforcement Learning with Pessimismcited by 78
  7. 2019Provably Efficient Q-Learning with Low Switching Costcited by 77
  8. 2020Provably Good Batch Reinforcement Learning Without Great Explorationcited by 77
  9. 2019Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learningcited by 74
  10. 2019Variance-reduced Q-learning is minimax optimalcited by 72
  11. 2021Conservative Data Sharing for Multi-Task Offline Reinforcement Learningcited by 64
  12. 2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimismcited by 63
  13. 2020Q-learning with Logarithmic Regretcited by 59
  14. 2021A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variantscited by 57
  15. 2017Stochastic Variance Reduction Methods for Policy Evaluationcited by 56
  16. 2017Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processescited by 56
  17. 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reductioncited by 56
  18. 2019Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDPcited by 53
  19. 2021Corruption-Robust Offline Reinforcement Learningcited by 51
  20. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 51
  21. 2021UCB Momentum Q-learning: Correcting the bias without forgettingcited by 45
  22. 2020Is Temporal Difference Learning Optimal? An Instance-Dependent Analysiscited by 41
  23. 2018Q-learning with Nearest Neighborscited by 37
  24. 2022Target Network and Truncation Overcome The Deadly Triad in Q-Learningcited by 31
  25. 2020Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexitycited by 28
  26. 2021Mitigating Covariate Shift in Imitation Learning via Offline Data Without Great Coveragecited by 26
  27. 2020Reanalysis of Variance Reduced Temporal Difference Learningcited by 23
  28. 2021Instance-optimality in optimal value estimation: Adaptivity via variance-reduced Q-learningcited by 21
  29. 2021Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Modelcited by 18
  30. 2020Finite-Time Analysis for Double Q-learningcited by 12

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 13; 2023: 14; 2024: 7; 2025: 4; 2026: 3.

41 papers.

Sort:

By area:

  1. 2022Distributionally Robust Model-Based Offline Reinforcement Learning with Near-Optimal Sample Complexitycited by 85
  2. 2023The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Modelcited by 50
  3. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 44
  4. 2023The Blessing of Heterogeneity in Federated Q-Learning: Linear Speedup and Beyondcited by 34
  5. 2022Policy learning "without" overlap: Pessimism and generalized empirical Bernstein's inequalitycited by 32
  6. 2022Optimal Conservative Offline RL with General Function Approximation via Augmented Lagrangiancited by 29
  7. 2022Pessimism in the Face of Confounders: Provably Efficient Offline Reinforcement Learning in Partially Observable Markov Decision Processescited by 26
  8. 2024Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertaintycited by 24
  9. 2022Offline Reinforcement Learning with Instrumental Variables in Confounded Markov Decision Processescited by 19
  10. 2022Pessimism for Offline Linear Contextual Bandits using ℓp Confidence Setscited by 18
  11. 2024Self-Play with Adversarial Critic: Provable and Scalable Offline Alignment for Language Modelscited by 16
  12. 2023A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Gamescited by 15
29 more
  1. 2023Reward-agnostic Fine-tuning: Provable Statistical Benefits of Hybrid Reinforcement Learningcited by 15
  2. 2023Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learningcited by 14
  3. 2022On Gap-dependent Bounds for Offline Reinforcement Learningcited by 13
  4. 2022Provably Efficient Offline Reinforcement Learning with Trajectory-Wise Rewardcited by 13
  5. 2023Importance Weighted Actor-Critic for Optimal Conservative Offline Reinforcement Learningcited by 13
  6. 2023Provable Benefits of Policy Learning from Human Preferences in Contextual Bandit Problemscited by 12
  7. 2024Sample Complexity of Offline Distributionally Robust Linear Markov Decision Processescited by 12
  8. 2024Federated Offline Reinforcement Learning: Collaborative Single-Policy Coverage Sufficescited by 11
  9. 2022Strategic Decision-Making in the Presence of Information Asymmetry: Provably Efficient RL with Algorithmic Instrumentscited by 9
  10. 2023Regret-Optimal Model-Free Reinforcement Learning for Discounted MDPs with Short Burn-In Timecited by 8
  11. 2024The Sample-Communication Complexity Trade-off in Federated Q-Learningcited by 8
  12. 2024Gap-Dependent Bounds for Q-Learning using Reference-Advantage Decompositioncited by 8
  13. 2022Stabilizing Q-learning with Linear Architectures for Provably Efficient Learningcited by 5
  14. 2022A Near-Optimal Primal-Dual Method for Off-Policy Learning in CMDPcited by 5
  15. 2023On the Sample Complexity of Vanilla Model-Based Offline Reinforcement Learning with Dependent Samplescited by 4
  16. 2023Bayesian Safe Policy Learning with Chance Constrained Optimization: Application to Military Security Assessment during the Vietnam Warcited by 4
  17. 2023Achieving the Asymptotically Optimal Sample Complexity of Offline Reinforcement Learning: A DRO-Based Approachcited by 3
  18. 2025Provable Zero-Shot Generalization in Offline Reinforcement Learningcited by 3
  19. 2022Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPscited by 2
  20. 2022Semi-supervised Batch Learning From Logged Datacited by 2
  21. 2023A Unified Framework of Policy Learning for Contextual Bandit with Confounding Bias and Missing Observationscited by 2
  22. 2023Two-Timescale Q-Learning with Function Approximation in Zero-Sum Stochastic Gamescited by 2
  23. 2025Towards Optimal Offline Reinforcement Learningcited by 2
  24. 2025Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learningcited by 2
  25. 2025Statistical and Algorithmic Foundations of Reinforcement Learningcited by 2
  26. 2026On the Optimal Sample Complexity of Offline Multi-Armed Bandits with KL Regularizationcited by 2
  27. 2024Pessimistic Causal Reinforcement Learning with Mediators for Confounded Offline Datacited by 0
  28. 2026Sample Complexity of Average-Reward Q-Learning: From Single-agent to Federated Reinforcement Learningcited by 0
  29. 2026Improved Model-based Reinforcement Learning with Smooth Kernelscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Semi-pessimistic Reinforcement Learning
  2. 2022State-Aware Proximal Pessimistic Algorithms for Offline Reinforcement Learning
  3. 2022Why So Pessimistic? Estimating Uncertainties for Offline RL through Ensembles, and Why Their Independence Matters
  4. 2024ACL-QL: Adaptive Conservative Level in Q-Learning for Offline Reinforcement Learning
  5. 2026Pessimistic Auxiliary Policy for Offline Reinforcement Learning
  6. 2021Bellman-consistent Pessimism for Offline Reinforcement Learning
  7. 2022Model-Based Offline Reinforcement Learning with Pessimism-Modulated Dynamics Belief
  8. 2024Strategically Conservative Q-Learning