mlsanityData to 14 Oct 2026

Is Pessimism Provably Efficient for Offline RL?

arXiv 2012.15085 ↗First posted 30 Dec 2020cs.LG cs.AI math.OCcited by 364

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

Abstract (arXiv)

We study offline reinforcement learning (RL), which aims to learn an optimal policy based on a dataset collected a priori. Due to the lack of further interactions with the environment, offline RL suffers from the insufficient coverage of the dataset, which eludes most existing theoretical analysis. In this paper, we propose a pessimistic variant of the value iteration algorithm (PEVI), which incorporates an uncertainty quantifier as the penalty function. Such a penalty function simply flips the sign of the bonus function for promoting exploration in online RL, which makes it easily implementable and compatible with general function approximators. Without assuming the sufficient coverage of the dataset, we establish a data-dependent upper bound on the suboptimality of PEVI for general Markov decision processes (MDPs). When specialized to linear MDPs, it matches the information-theoretic lower bound up to multiplicative factors of the dimension and horizon. In other words, pessimism is not only provably efficient but also minimax optimal. In particular, given the dataset, the learned policy serves as the "best effort" among all policies, as no other policies can do better. Our theoretical analysis identifies the critical role of pessimism in eliminating a notion of spurious correlation, which emerges from the "irrelevant" trajectories that are less covered by the dataset and not informative for the optimal policy.

Key facts. Cited by 364 papers in the map (data through 14 Oct 2026). Placed in Offline RL algorithms, one of 13 directions in Offline RL and imitation learning from data. Builds on 54 of its 98 references that are in the map. First posted on arXiv 30 Dec 2020.

Builds on

54 of 98 references.

Closest ancestors · 12

Same direction, newest first

  1. 2020What are the Statistical Limits of Offline RL with Linear Function Approximation?22 Oct
  2. 2020Batch Value-function Approximation with Only Realizability11 Aug
  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. 2020Critic Regularized Regression26 Jun
  6. 2020Conservative Q-Learning for Offline Reinforcement Learning8 Jun
  7. 2020Doubly Robust Off-Policy Value and Gradient Estimation for Deterministic Policies6 Jun
  8. 2020MOPO: Model-based Offline Policy Optimization27 May
  9. 2020MOReL : Model-Based Offline Reinforcement Learning12 May
  10. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems4 May
  11. 2020D4RL: Datasets for Deep Data-Driven Reinforcement Learning15 Apr
  12. 2020Keep Doing What Worked: Behavioral Modelling Priors for Offline Reinforcement Learning19 Feb

Other references · 42

  1. 2019Scalability in Perception for Autonomous Driving: Waymo Open Datasetcited by 2,451
  2. 2018Off-Policy Deep Reinforcement Learning without Explorationcited by 1,241
  3. 2019Stabilizing Off-Policy Q-Learning via Bootstrapping Error Reductioncited by 840
  4. 2020AWAC: Accelerating Online Reinforcement Learning with Offline Datasetscited by 671
  5. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  6. 2018Is Q-learning Provably Efficient?cited by 487
  7. 2015An Introduction to Matrix Concentration Inequalitiescited by 397
  8. 2017On Kernelized Multi-armed Banditscited by 352
  9. 2015Doubly Robust Off-policy Value Evaluation for Reinforcement Learningcited by 339
  10. 2016Safe, Multi-Agent, Reinforcement Learning for Autonomous Drivingcited by 311
  11. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 287
  12. 2016Data-Efficient Off-Policy Policy Evaluation for Reinforcement Learningcited by 286
30 more
  1. 2019Way Off-Policy Batch Deep Reinforcement Learning of Implicit Human Preferences in Dialogcited by 284
  2. 2017StarCraft II: A New Challenge for Reinforcement Learningcited by 274
  3. 2019DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Correctionscited by 254
  4. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 234
  5. 2018Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimationcited by 227
  6. 2019A Theoretical Analysis of Deep Q-Learningcited by 215
  7. 2019Provably Efficient Exploration in Policy Optimizationcited by 205
  8. 2019AlgaeDICE: Policy Gradient from Arbitrary Experiencecited by 188
  9. 2014An Information-Theoretic Analysis of Thompson Samplingcited by 178
  10. 2014Learning to Optimize via Information-Directed Samplingcited by 168
  11. 2019Neural Policy Gradient Methods: Global Optimality and Rates of Convergencecited by 159
  12. 2019Minimax Weight and Q-Function Learning for Off-Policy Evaluationcited by 150
  13. 2017Safe Policy Improvement with Baseline Bootstrappingcited by 144
  14. 2018More Robust Doubly Robust Off-policy Evaluationcited by 141
  15. 2020GenDICE: Generalized Offline Estimation of Stationary Valuescited by 122
  16. 2020Minimax-Optimal Off-Policy Evaluation with Linear Function Approximationcited by 120
  17. 2019Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Samplingcited by 119
  18. 2014Model-based Reinforcement Learning and the Eluder Dimensioncited by 116
  19. 2020Variational Policy Gradient Method for Reinforcement Learning with General Utilitiescited by 111
  20. 2020Reinforcement Learning via Fenchel-Rockafellar Dualitycited by 100
  21. 2020The Importance of Pessimism in Fixed-Dataset Policy Optimizationcited by 99
  22. 2020Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learningcited by 96
  23. 2020Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reductioncited by 95
  24. 2020Off-Policy Evaluation via the Regularized Lagrangiancited by 86
  25. 2019Efficiently Breaking the Curse of Horizon in Off-Policy Evaluation with Double Reinforcement Learningcited by 75
  26. 2020Batch Policy Learning in Average Reward Markov Decision Processescited by 69
  27. 2020Asymptotically Efficient Off-Policy Evaluation for Tabular Reinforcement Learningcited by 60
  28. 2019Doubly Robust Bias Reduction in Infinite Horizon Off-Policy Estimationcited by 48
  29. 2020Single-Timescale Actor-Critic Provably Finds Globally Optimal Policycited by 34
  30. 2020On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spacescited by 19

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 36; 2022: 76; 2023: 93; 2024: 74; 2025: 45; 2026: 40.

364 papers.

Sort:

By area:

  1. 2023RAFT: Reward rAnked FineTuning for Generative Foundation Model Alignmentcited by 686
  2. 2021Offline Reinforcement Learning as One Big Sequence Modeling Problemcited by 644
  3. 2021COMBO: Conservative Offline Model-Based Policy Optimizationcited by 370
  4. 2023Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraintcited by 350
  5. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimismcited by 279
  6. 2021Bellman-consistent Pessimism for Offline Reinforcement Learningcited by 269
  7. 2023Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisonscited by 247
  8. 2023Cal-QL: Calibrated Offline RL Pre-Training for Efficient Online Fine-Tuningcited by 237
  9. 2025Steering Your Diffusion Policy with Latent Space Reinforcement Learningcited by 169
  10. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coveragecited by 164
  11. 2022Hybrid RL: Using Both Offline and Online Data Can Make RL Efficientcited by 161
  12. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learningcited by 158
38 more
  1. 2024Regularizing Hidden States Enables Learning Generalizable Reward Model for LLMscited by 142
  2. 2023Supervised Pretraining Can Learn In-Context Reinforcement Learningcited by 139
  3. 2021Representation Learning for Online and Offline RL in Low-rank MDPscited by 129
  4. 2024DPO Meets PPO: Reinforced Token Optimization for RLHFcited by 127
  5. 2022Pessimistic Bootstrapping for Uncertainty-Driven Offline Reinforcement Learningcited by 125
  6. 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrabilitycited by 123
  7. 2022Mildly Conservative Q-Learning for Offline Reinforcement Learningcited by 112
  8. 2022Adversarially Trained Actor Critic for Offline Reinforcement Learningcited by 111
  9. 2021Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learningcited by 110
  10. 2024Provably Mitigating Overoptimization in RLHF: Your SFT Loss is Implicitly an Adversarial Regularizercited by 109
  11. 2022A Review of Off-Policy Evaluation in Reinforcement Learningcited by 95
  12. 2022When Should We Prefer Offline Reinforcement Learning Over Behavioral Cloning?cited by 89
  13. 2022Distributionally Robust Model-Based Offline Reinforcement Learning with Near-Optimal Sample Complexitycited by 87
  14. 2022Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexitycited by 85
  15. 2022RORL: Robust Offline Reinforcement Learning via Conservative Smoothingcited by 84
  16. 2022The Role of Coverage in Online Reinforcement Learningcited by 83
  17. 2023Contrastive Preference Learning: Learning from Human Feedback without RLcited by 79
  18. 2021Towards Instance-Optimal Offline Reinforcement Learning with Pessimismcited by 78
  19. 2022Why So Pessimistic? Estimating Uncertainties for Offline RL through Ensembles, and Why Their Independence Matterscited by 76
  20. 2024An Overview of Diffusion Models: Applications, Guided Generation, Statistical Rates and Optimizationcited by 73
  21. 2023Reinforcement Learning with Human Feedback: Learning Dynamic Choices via Pessimismcited by 69
  22. 2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimismcited by 65
  23. 2024Iterative Data Smoothing: Mitigating Reward Overfitting and Overoptimization in RLHFcited by 57
  24. 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reductioncited by 56
  25. 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Gamecited by 55
  26. 2023Provable Offline Preference-Based Reinforcement Learningcited by 55
  27. 2026Expanding the Capabilities of Reinforcement Learning via Text Feedbackcited by 53
  28. 2022Offline RL Policies Should be Trained to be Adaptivecited by 52
  29. 2023The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Modelcited by 52
  30. 2024Online Iterative Reinforcement Learning from Human Feedback with General Preference Modelcited by 52
  31. 2021Corruption-Robust Offline Reinforcement Learningcited by 51
  32. 2023Double Pessimism is Provably Efficient for Distributionally Robust Offline Reinforcement Learning: Generic Algorithm and Robust Partial Coveragecited by 51
  33. 2023Reward-Directed Conditional Diffusion: Provable Distribution Estimation and Reward Improvementcited by 49
  34. 2023Reason for Future, Act for Now: A Principled Framework for Autonomous LLM Agents with Provable Sample Efficiencycited by 46
  35. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 45
  36. 2021Offline Reinforcement Learning as Anti-Explorationcited by 44
  37. 2022Pessimistic Minimax Value Iteration: Provably Efficient Equilibrium Learning from Offline Datasetscited by 44
  38. 2021Heuristic-Guided Reinforcement Learningcited by 42

50 most cited of 364 All 364 (JSON)

Similar, not cited

Close in wording, no citation either way

  1. 2022Model-Based Offline Reinforcement Learning with Pessimism-Modulated Dynamics Belief
  2. 2026Generalization in offline RL: The structure is more important than the amount of pessimism
  3. 2021Dealing with the Unknown: Pessimistic Offline Reinforcement Learning
  4. 2025Semi-pessimistic Reinforcement Learning
  5. 2026Pessimistic Auxiliary Policy for Offline Reinforcement Learning
  6. 2020POPO: Pessimistic Offline Policy Optimization
  7. 2024The Virtues of Pessimism in Inverse Reinforcement Learning
  8. 2025On the Statistical Complexity for Offline and Low-Adaptive Reinforcement Learning with Structures