mlsanityData to 7 Oct 2026

Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexity

arXiv 2202.13890 ↗First posted 28 Feb 2022cs.LG stat.MLcited by 84

On the map: Offline RL and imitation learning from data → Offline RL algorithms

Abstract (arXiv)

Offline or batch reinforcement learning seeks to learn a near-optimal policy using history data without active exploration of the environment. To counter the insufficient coverage and sample scarcity of many offline datasets, the principle of pessimism has been recently introduced to mitigate high bias of the estimated values. While pessimistic variants of model-based algorithms (e.g., value iteration with lower confidence bounds) have been theoretically investigated, their model-free counterparts -- which do not require explicit model estimation -- have not been adequately studied, especially in terms of sample efficiency. To address this inadequacy, we study a pessimistic variant of Q-learning in the context of finite-horizon Markov decision processes, and characterize its sample complexity under the single-policy concentrability assumption which does not require the full coverage of the state-action space. In addition, a variance-reduced pessimistic Q-learning algorithm is proposed to achieve near-optimal sample complexity. Altogether, this work highlights the efficiency of model-free algorithms in offline RL when used in conjunction with pessimism and variance reduction.

Key facts. Cited by 84 papers in the map (data through 7 Oct 2026). Placed in Offline RL algorithms, one of 13 directions in Offline RL and imitation learning from data. Builds on 46 of its 66 references that are in the map. First posted on arXiv 28 Feb 2022.

Builds on

46 of 66 references.

Closest ancestors · 20

Same direction, newest first

  1. 2021Towards Instance-Optimal Offline Reinforcement Learning with Pessimism17 Oct
  2. 2021Representation Learning for Online and Offline RL in Low-rank MDPs9 Oct
  3. 2021Conservative Data Sharing for Multi-Task Offline Reinforcement Learning16 Sep
  4. 2021Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning19 Aug
  5. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage13 Jul
  6. 2021Bellman-consistent Pessimism for Offline Reinforcement Learning13 Jun
  7. 2021Offline Reinforcement Learning as Anti-Exploration11 Jun
  8. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning9 Jun
  9. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism22 Mar
  10. 2021Sample Complexity of Offline Reinforcement Learning with Deep ReLU Networks11 Mar
  11. 2021Offline Reinforcement Learning with Pseudometric Learning2 Mar
  12. 2021COMBO: Conservative Offline Model-Based Policy Optimization16 Feb
8 more
  1. 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reduction2 Feb
  2. 2020Is Pessimism Provably Efficient for Offline RL?30 Dec
  3. 2020Provably Good Batch Reinforcement Learning Without Great Exploration16 Jul
  4. 2020Near-Optimal Provable Uniform Convergence in Offline Policy Evaluation for Reinforcement Learning7 Jul
  5. 2020Conservative Q-Learning for Offline Reinforcement Learning8 Jun
  6. 2020MOPO: Model-based Offline Policy Optimization27 May
  7. 2020MOReL : Model-Based Offline Reinforcement Learning12 May
  8. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems4 May

Other references · 26

  1. 2018Off-Policy Deep Reinforcement Learning without Explorationcited by 1,227
  2. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  3. 2018Is Q-learning Provably Efficient?cited by 485
  4. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 285
  5. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  6. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 124
  7. 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 108
  8. 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 104
  9. 2020The Importance of Pessimism in Fixed-Dataset Policy Optimizationcited by 99
  10. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
  11. 2020Toward the Fundamental Limits of Imitation Learningcited by 96
  12. 2020Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learningcited by 93
14 more
  1. 2020Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reductioncited by 93
  2. 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 89
  3. 2019Provably Efficient Q-Learning with Low Switching Costcited by 77
  4. 2019Variance-reduced Q-learning is minimax optimalcited by 72
  5. 2020Q-learning with Logarithmic Regretcited by 59
  6. 2017Stochastic Variance Reduction Methods for Policy Evaluationcited by 56
  7. 2017Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processescited by 56
  8. 2019Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDPcited by 53
  9. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 51
  10. 2020Is Temporal Difference Learning Optimal? An Instance-Dependent Analysiscited by 41
  11. 2020Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexitycited by 28
  12. 2020Reanalysis of Variance Reduced Temporal Difference Learningcited by 23
  13. 2020Finite-Sample Analysis of Stochastic Approximation Using Smooth Convex Envelopescited by 19
  14. 2020A Model-free Learning Algorithm for Infinite-horizon Average-reward MDPs with Near-optimal Regretcited by 7

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 16; 2023: 28; 2024: 21; 2025: 10; 2026: 9.

84 papers.

Sort:

By area:

  1. 2024Provably Mitigating Overoptimization in RLHF: Your SFT Loss is Implicitly an Adversarial Regularizercited by 109
  2. 2022Distributionally Robust Model-Based Offline Reinforcement Learning with Near-Optimal Sample Complexitycited by 85
  3. 2024Value-Incentivized Preference Optimization: A Unified Approach to Online and Offline RLHFcited by 73
  4. 2023Reinforcement Learning with Human Feedback: Learning Dynamic Choices via Pessimismcited by 69
  5. 2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimismcited by 63
  6. 2023Provable Offline Preference-Based Reinforcement Learningcited by 55
  7. 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Gamecited by 53
  8. 2023Double Pessimism is Provably Efficient for Distributionally Robust Offline Reinforcement Learning: Generic Algorithm and Robust Partial Coveragecited by 51
  9. 2023The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Modelcited by 50
  10. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 44
  11. 2022The Efficacy of Pessimism in Asynchronous Q-Learningcited by 41
  12. 2023The Blessing of Heterogeneity in Federated Q-Learning: Linear Speedup and Beyondcited by 34
38 more
  1. 2022Policy learning "without" overlap: Pessimism and generalized empirical Bernstein's inequalitycited by 32
  2. 2023Adversarial Model for Offline Reinforcement Learningcited by 31
  3. 2022Optimal Conservative Offline RL with General Function Approximation via Augmented Lagrangiancited by 29
  4. 2023Towards Robust Offline Reinforcement Learning under Diverse Data Corruptioncited by 24
  5. 2022Offline Reinforcement Learning with Instrumental Variables in Confounded Markov Decision Processescited by 19
  6. 2022Pessimism for Offline Linear Contextual Bandits using ℓp Confidence Setscited by 18
  7. 2023Offline Learning in Markov Games with General Function Approximationcited by 16
  8. 2023High-probability sample complexities for policy evaluation with linear function approximationcited by 16
  9. 2023Model-based Offline Reinforcement Learning with Count-based Conservatismcited by 16
  10. 2024Self-Play with Adversarial Critic: Provable and Scalable Offline Alignment for Language Modelscited by 16
  11. 2023Reward-agnostic Fine-tuning: Provable Statistical Benefits of Hybrid Reinforcement Learningcited by 15
  12. 2023Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learningcited by 14
  13. 2022On Gap-dependent Bounds for Offline Reinforcement Learningcited by 13
  14. 2022Provably Efficient Offline Reinforcement Learning with Trajectory-Wise Rewardcited by 13
  15. 2023Provable Benefits of Policy Learning from Human Preferences in Contextual Bandit Problemscited by 12
  16. 2023Bridging Distributionally Robust Learning and Offline RL: An Approach to Mitigate Distribution Shift and Partial Data Coveragecited by 12
  17. 2024Sample Complexity of Offline Distributionally Robust Linear Markov Decision Processescited by 12
  18. 2024Federated Offline Reinforcement Learning: Collaborative Single-Policy Coverage Sufficescited by 11
  19. 2023Offline Meta Reinforcement Learning with In-Distribution Online Adaptationcited by 10
  20. 2023Fast and Regret Optimal Best Arm Identification: Fundamental Limits and Low-Complexity Algorithmscited by 10
  21. 2024Offline-Boosted Actor-Critic: Adaptively Blending Optimal Historical Behaviors in Deep Off-Policy RLcited by 10
  22. 2024OASIS: Conditional Distribution Shaping for Offline Safe Reinforcement Learningcited by 10
  23. 2022Strategic Decision-Making in the Presence of Information Asymmetry: Provably Efficient RL with Algorithmic Instrumentscited by 9
  24. 2023Offline Minimax Soft-Q-learning Under Realizability and Partial Coveragecited by 9
  25. 2023Conservative State Value Estimation for Offline Reinforcement Learningcited by 9
  26. 2023Pessimistic Nonlinear Least-Squares Value Iteration for Offline Reinforcement Learningcited by 9
  27. 2024Learning from Sparse Offline Datasets via Conservative Density Estimationcited by 9
  28. 2025Towards a Sharp Analysis of Offline Policy Learning for f-Divergence-Regularized Contextual Banditscited by 9
  29. 2023Regret-Optimal Model-Free Reinforcement Learning for Discounted MDPs with Short Burn-In Timecited by 8
  30. 2024The Sample-Communication Complexity Trade-off in Federated Q-Learningcited by 8
  31. 2024Gap-Dependent Bounds for Q-Learning using Reference-Advantage Decompositioncited by 8
  32. 2024Combining Experimental and Historical Data for Policy Evaluationcited by 6
  33. 2026Safe Exploration via Policy Priorscited by 6
  34. 2022Stabilizing Q-learning with Linear Architectures for Provably Efficient Learningcited by 5
  35. 2022A Near-Optimal Primal-Dual Method for Off-Policy Learning in CMDPcited by 5
  36. 2022Offline Estimation of Controlled Markov Chains: Minimaxity and Sample Complexitycited by 5
  37. 2023Provably Efficient Offline Goal-Conditioned Reinforcement Learning with General Function Approximation and Single-Policy Concentrabilitycited by 5
  38. 2024A Natural Extension To Online Algorithms For Hybrid RL With Limited Coveragecited by 5

50 most cited of 84 All 84 (JSON)

Similar, not cited

Close in wording, no citation either way

  1. 2022Pessimism in the Face of Confounders: Provably Efficient Offline Reinforcement Learning in Partially Observable Markov Decision Processes
  2. 2025Semi-pessimistic Reinforcement Learning
  3. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learning
  4. 2026Pessimistic Auxiliary Policy for Offline Reinforcement Learning
  5. 2022Model-Based Offline Reinforcement Learning with Pessimism-Modulated Dynamics Belief
  6. 2022Pessimistic Bootstrapping for Uncertainty-Driven Offline Reinforcement Learning
  7. 2022State-Aware Proximal Pessimistic Algorithms for Offline Reinforcement Learning
  8. 2023On the Sample Complexity of Vanilla Model-Based Offline Reinforcement Learning with Dependent Samples