mlsanityData to 13 Oct 2026

On Gap-dependent Bounds for Offline Reinforcement Learning

arXiv 2206.00177 ↗First posted 1 Jun 2022cs.LG cs.AIcited by 13

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

Abstract (arXiv)

This paper presents a systematic study on gap-dependent sample complexity in offline reinforcement learning. Prior work showed when the density ratio between an optimal policy and the behavior policy is upper bounded (the optimal policy coverage assumption), then the agent can achieve an Oleft(frac1ε2right) rate, which is also minimax optimal. We show under the optimal policy coverage assumption, the rate can be improved to Oleft(frac1εright) when there is a positive sub-optimality gap in the optimal Q-function. Furthermore, we show when the visitation probabilities of the behavior policy are uniformly lower bounded for states where an optimal policy's visitation probabilities are positive (the uniform optimal policy coverage assumption), the sample complexity of identifying an optimal policy is independent of frac1ε. Lastly, we present nearly-matching lower bounds to complement our gap-dependent upper bounds.

Key facts. Cited by 13 papers in the map (data through 13 Oct 2026). Placed in Offline RL algorithms, one of 13 directions in Offline RL and imitation learning from data. Builds on 29 of its 40 references that are in the map. First posted on arXiv 1 Jun 2022.

Builds on

29 of 40 references.

Closest ancestors · 14

Same direction, newest first

  1. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learning11 Apr
  2. 2022Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexity28 Feb
  3. 2021Towards Instance-Optimal Offline Reinforcement Learning with Pessimism17 Oct
  4. 2021Representation Learning for Online and Offline RL in Low-rank MDPs9 Oct
  5. 2021Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning19 Aug
  6. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage13 Jul
  7. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning9 Jun
  8. 2021Nearly Horizon-Free Offline Reinforcement Learning25 Mar
  9. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism22 Mar
  10. 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reduction2 Feb
  11. 2021Fast Rates for the Regret of Offline Reinforcement Learning31 Jan
  12. 2020Is Pessimism Provably Efficient for Offline RL?30 Dec
2 more
  1. 2020Batch Value-function Approximation with Only Realizability11 Aug
  2. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems4 May

Other references · 15

  1. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 195
  2. 2018Top-K Off-Policy Correction for a REINFORCE Recommender Systemcited by 181
  3. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 175
  4. 2019Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Samplingcited by 118
  5. 2019Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPscited by 104
  6. 2020Logarithmic Regret for Reinforcement Learning with Linear Function Approximationcited by 79
  7. 2020Asymptotically Efficient Off-Policy Evaluation for Tabular Reinforcement Learningcited by 60
  8. 2021Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrapcited by 48
  9. 2019Approximating Interactive Human Evaluation with Self-Play for Open-Domain Dialog Systemscited by 42
  10. 2021Beyond No Regret: Instance-Dependent PAC Reinforcement Learningcited by 41
  11. 2022The Efficacy of Pessimism in Asynchronous Q-Learningcited by 41
  12. 2020Planning in Markov Decision Processes with Gap-Dependent Sample Complexitycited by 34
3 more
  1. 2021Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learningcited by 34
  2. 2021Task-Optimal Exploration in Linear Dynamical Systemscited by 15
  3. 2021A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPscited by 15

Built on by

Cited by year (2026 to 13 Oct)

Citing papers per year: 2022: 2; 2023: 4; 2024: 1; 2025: 4; 2026: 2.

13 papers.

Sort:

By area:

  1. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 45
  2. 2022Optimal Conservative Offline RL with General Function Approximation via Augmented Lagrangiancited by 29
  3. 2022On Instance-Dependent Bounds for Offline Reinforcement Learning with Linear Function Approximationcited by 22
  4. 2023Importance Weighted Actor-Critic for Optimal Conservative Offline Reinforcement Learningcited by 13
  5. 2023Offline Minimax Soft-Q-learning Under Realizability and Partial Coveragecited by 9
  6. 2025Gap-Dependent Bounds for Federated Q-learningcited by 4
  7. 2025Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPscited by 4
  8. 2024Taming "data-hungry" reinforcement learning? Stability in continuous state-action spacescited by 3
  9. 2025Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learningcited by 2
  10. 2023Offline Reinforcement Learning with Additional Covering Distributionscited by 1
  11. 2025Q-Learning with Fine-Grained Gap-Dependent Regretcited by 1
  12. 2026Fast Rates for Offline Contextual Bandits with Forward-KL Regularization under Single-Policy Concentrabilitycited by 1
1 more
  1. 2026On the Complexity of Offline Reinforcement Learning with Q^star-Approximation and Partial Coveragecited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2023On the Sample Complexity of Vanilla Model-Based Offline Reinforcement Learning with Dependent Samples
  2. 2022Offline Reinforcement Learning Under Value and Density-Ratio Realizability: The Power of Gaps
  3. 2022Offline Reinforcement Learning via Linear-Programming with Error-Bound Induced Constraints
  4. 2025Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RL
  5. 2022The Role of Coverage in Online Reinforcement Learning
  6. 2021Infinite-Horizon Offline Reinforcement Learning with Linear Function Approximation: Curse of Dimensionality and Algorithm
  7. 2021Finite Sample Analysis of Minimax Offline Reinforcement Learning: Completeness, Fast Rates and First-Order Efficiency
  8. 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrability