mlsanityData to 14 Oct 2026

Towards Instance-Optimal Offline Reinforcement Learning with Pessimism

arXiv 2110.08695 ↗First posted 17 Oct 2021cs.LG cs.AI stat.MLcited by 78

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

Abstract (arXiv)

We study the offline reinforcement learning (offline RL) problem, where the goal is to learn a reward-maximizing policy in an unknown Markov Decision Process (MDP) using the data coming from a policy μ. In particular, we consider the sample complexity problems of offline RL for finite-horizon MDPs. Prior works study this problem based on different data-coverage assumptions, and their learning guarantees are expressed by the covering coefficients which lack the explicit characterization of system quantities. In this work, we analyze the Adaptive Pessimistic Value Iteration (APVI) algorithm and derive the suboptimality upper bound that nearly matches [ Oleft(sumh=1Hsumsh,ahdπ^starh(sh,ah)√fracVar_Psh,ah(V^starh+1+rh)dμh(sh,ah)√frac1nright). ] In complementary, we also prove a per-instance information-theoretical lower bound under the weak assumption that dμh(sh,ah)>0 if dπ^starh(sh,ah)>0. Different from the previous minimax lower bounds, the per-instance lower bound (via local minimaxity) is a much stronger criterion as it applies to individual instances separately. Here π^star is a optimal policy, μ is the behavior policy and dhμ is the marginal state-action probability. We call the above equation the intrinsic offline reinforcement learning bound since it directly implies all the existing optimal results: minimax rate under uniform data-coverage assumption, horizon-free setting, single policy concentrability, and the tight problem-dependent results. Later, we extend the result to the assumption-free regime (where we make no assumption on μ) and obtain the assumption-free intrinsic bound. Due to its generic form, we believe the intrinsic bound could help illuminate what makes a specific problem hard and reveal the fundamental challenges in offline RL.

Key facts. Cited by 78 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 39 of its 57 references that are in the map. First posted on arXiv 17 Oct 2021.

Builds on

39 of 57 references.

Closest ancestors · 17

Same direction, newest first

  1. 2021Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning19 Aug
  2. 2021Bellman-consistent Pessimism for Offline Reinforcement Learning13 Jun
  3. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning9 Jun
  4. 2021Optimal Uniform OPE and Model-based Offline Reinforcement Learning in Time-Homogeneous, Reward-Free and Task-Agnostic Settings13 May
  5. 2021Nearly Horizon-Free Offline Reinforcement Learning25 Mar
  6. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism22 Mar
  7. 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reduction2 Feb
  8. 2020Is Pessimism Provably Efficient for Offline RL?30 Dec
  9. 2020What are the Statistical Limits of Offline RL with Linear Function Approximation?22 Oct
  10. 2020Batch Value-function Approximation with Only Realizability11 Aug
  11. 2020Provably Good Batch Reinforcement Learning Without Great Exploration16 Jul
  12. 2020Near-Optimal Provable Uniform Convergence in Offline Policy Evaluation for Reinforcement Learning7 Jul
5 more
  1. 2020RL Unplugged: A Suite of Benchmarks for Offline Reinforcement Learning24 Jun
  2. 2020MOReL : Model-Based Offline Reinforcement Learning12 May
  3. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems4 May
  4. 2020D4RL: Datasets for Deep Data-Driven Reinforcement Learning15 Apr
  5. 2020Q* Approximation Schemes for Batch Reinforcement Learning: A Theoretical Comparison9 Mar

Other references · 22

  1. 2021Offline Reinforcement Learning as One Big Sequence Modeling Problemcited by 644
  2. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  3. 2015Doubly Robust Off-policy Value Evaluation for Reinforcement Learningcited by 339
  4. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 292
  5. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 287
  6. 2019Batch Policy Learning under Constraintscited by 244
  7. 2019Provably Efficient Exploration in Policy Optimizationcited by 205
  8. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 195
  9. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 127
  10. 2020Minimax-Optimal Off-Policy Evaluation with Linear Function Approximationcited by 120
  11. 2020The Importance of Pessimism in Fixed-Dataset Policy Optimizationcited by 99
  12. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
10 more
  1. 2021Benchmarks for Deep Off-Policy Evaluationcited by 89
  2. 2019Provably Efficient Q-Learning with Low Switching Costcited by 78
  3. 2020Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimismcited by 76
  4. 2020Asymptotically Efficient Off-Policy Evaluation for Tabular Reinforcement Learningcited by 60
  5. 2020Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RLcited by 55
  6. 2019Off-Policy Policy Gradient with State Distribution Correctioncited by 43
  7. 2020Is Temporal Difference Learning Optimal? An Instance-Dependent Analysiscited by 41
  8. 2021On the Optimality of Batch Policy Optimization Algorithmscited by 28
  9. 2021Mitigating Covariate Shift in Imitation Learning via Offline Data Without Great Coveragecited by 26
  10. 2019Problem Dependent Reinforcement Learning Bounds Which Can Identify Bandit Structure in MDPscited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 1; 2022: 29; 2023: 19; 2024: 15; 2025: 7; 2026: 7.

78 papers.

Sort:

By area:

  1. 2024Provably Mitigating Overoptimization in RLHF: Your SFT Loss is Implicitly an Adversarial Regularizercited by 109
  2. 2022Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexitycited by 85
  3. 2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimismcited by 65
  4. 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Gamecited by 55
  5. 2023Provable Offline Preference-Based Reinforcement Learningcited by 55
  6. 2023Double Pessimism is Provably Efficient for Distributionally Robust Offline Reinforcement Learning: Generic Algorithm and Robust Partial Coveragecited by 51
  7. 2024Transfer Q Star: Principled Decoding for LLM Alignmentcited by 48
  8. 2022Pessimistic Minimax Value Iteration: Provably Efficient Equilibrium Learning from Offline Datasetscited by 44
  9. 2022The Efficacy of Pessimism in Asynchronous Q-Learningcited by 42
  10. 2022Policy learning "without" overlap: Pessimism and generalized empirical Bernstein's inequalitycited by 32
  11. 2023Corruption-Robust Offline Reinforcement Learning with General Function Approximationcited by 31
  12. 2022Provably Efficient Offline Multi-agent Reinforcement Learning via Strategy-wise Bonuscited by 30
38 more
  1. 2021A Statistical Analysis of Polyak-Ruppert Averaged Q-learningcited by 29
  2. 2022Provable Benefit of Multitask Representation Learning in Reinforcement Learningcited by 29
  3. 2022Optimal Conservative Offline RL with General Function Approximation via Augmented Lagrangiancited by 29
  4. 2022When is Offline Two-Player Zero-Sum Markov Game Solvable?cited by 28
  5. 2022Pessimism in the Face of Confounders: Provably Efficient Offline Reinforcement Learning in Partially Observable Markov Decision Processescited by 26
  6. 2022On Instance-Dependent Bounds for Offline Reinforcement Learning with Linear Function Approximationcited by 22
  7. 2022Offline Reinforcement Learning with Differential Privacycited by 20
  8. 2022Pessimism for Offline Linear Contextual Bandits using ℓp Confidence Setscited by 18
  9. 2023Reinforcement Learning in Low-Rank MDPs with Density Featurescited by 18
  10. 2023Offline Learning in Markov Games with General Function Approximationcited by 18
  11. 2022Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPscited by 17
  12. 2023Privately Aligning Language Models with Reinforcement Learningcited by 17
  13. 2022Near-Optimal Differentially Private Reinforcement Learningcited by 16
  14. 2023Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learningcited by 15
  15. 2024Offline Multitask Representation Learning for Reinforcement Learningcited by 14
  16. 2022On Gap-dependent Bounds for Offline Reinforcement Learningcited by 13
  17. 2022Provably Efficient Offline Reinforcement Learning with Trajectory-Wise Rewardcited by 13
  18. 2023Importance Weighted Actor-Critic for Optimal Conservative Offline Reinforcement Learningcited by 13
  19. 2023Provable Benefits of Policy Learning from Human Preferences in Contextual Bandit Problemscited by 13
  20. 2022Offline Reinforcement Learning with Differentiable Function Approximation is Provably Efficientcited by 12
  21. 2023Offline Meta Reinforcement Learning with In-Distribution Online Adaptationcited by 12
  22. 2023Robust Markov Decision Processes without Model Estimationcited by 11
  23. 2024Federated Offline Reinforcement Learning: Collaborative Single-Policy Coverage Sufficescited by 11
  24. 2025Greedy Sampling Is Provably Efficient for RLHFcited by 11
  25. 2022Bellman Residual Orthogonalization for Offline Reinforcement Learningcited by 10
  26. 2023Offline Minimax Soft-Q-learning Under Realizability and Partial Coveragecited by 10
  27. 2024On the Curses of Future and History in Future-dependent Value Functions for Off-policy Evaluationcited by 10
  28. 2023Pessimistic Nonlinear Least-Squares Value Iteration for Offline Reinforcement Learningcited by 9
  29. 2023Variance-aware robust reinforcement learning with linear function approximation under heavy-tailed rewardscited by 8
  30. 2024On Sample-Efficient Offline Reinforcement Learning: Data Diversity, Posterior Sampling, and Beyondcited by 6
  31. 2024Pessimism Meets Risk: Risk-Sensitive Offline Reinforcement Learningcited by 6
  32. 2025Balancing optimism and pessimism in offline-to-online learningcited by 6
  33. 2022Stabilizing Q-learning with Linear Architectures for Provably Efficient Learningcited by 5
  34. 2022A Near-Optimal Primal-Dual Method for Off-Policy Learning in CMDPcited by 5
  35. 2022Offline Estimation of Controlled Markov Chains: Minimaxity and Sample Complexitycited by 5
  36. 2024Offline Reinforcement Learning from Datasets with Structured Non-Stationaritycited by 5
  37. 2022Pessimism meets VCG: Learning Dynamic Mechanism Design via Offline Reinforcement Learningcited by 4
  38. 2022Incorporating Explicit Uncertainty Estimates into Deep Offline Reinforcement Learningcited by 4

50 most cited of 78 All 78 (JSON)

Similar, not cited

Close in wording, no citation either way

  1. 2022Offline Reinforcement Learning via Linear-Programming with Error-Bound Induced Constraints
  2. 2024A Primal-Dual Algorithm for Offline Constrained Reinforcement Learning with Linear MDPs
  3. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learning
  4. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage
  5. 2025Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RL
  6. 2026Offline-Online Reinforcement Learning for Linear Mixture MDPs
  7. 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrability
  8. 2023On the Sample Complexity of Vanilla Model-Based Offline Reinforcement Learning with Dependent Samples