mlsanityData to 7 Oct 2026

On Sample-Efficient Offline Reinforcement Learning: Data Diversity, Posterior Sampling, and Beyond

arXiv 2401.03301 ↗First posted 6 Jan 2024cs.LG cs.AI stat.MLcited by 6

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

Abstract (arXiv)

We seek to understand what facilitates sample-efficient learning from historical datasets for sequential decision-making, a problem that is popularly known as offline reinforcement learning (RL). Further, we are interested in algorithms that enjoy sample efficiency while leveraging (value) function approximation. In this paper, we address these fundamental questions by (i) proposing a notion of data diversity that subsumes the previous notions of coverage measures in offline RL and (ii) using this notion to unify three distinct classes of offline RL algorithms based on version spaces (VS), regularized optimization (RO), and posterior sampling (PS). We establish that VS-based, RO-based, and PS-based algorithms, under standard assumptions, achieve comparable sample efficiency, which recovers the state-of-the-art sub-optimality bounds for finite and linear model classes with the standard assumptions. This result is surprising, given that the prior work suggested an unfavorable sample complexity of the RO-based algorithm compared to the VS-based algorithm, whereas posterior sampling is rarely considered in offline RL due to its explorative nature. Notably, our proposed model-free PS-based algorithm for offline RL is novel, with sub-optimality bounds that are frequentist (i.e., worst-case) in nature.

Key facts. Cited by 6 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 42 of its 55 references that are in the map. First posted on arXiv 6 Jan 2024.

Builds on

42 of 55 references.

Closest ancestors · 22

Same direction, newest first

  1. 2023Pessimistic Nonlinear Least-Squares Value Iteration for Offline Reinforcement Learning2 Oct
  2. 2023Offline Primal-Dual Reinforcement Learning for Linear MDPs22 May
  3. 2023VIPeR: Provably Efficient Algorithm for Offline RL with Neural Function Approximation24 Feb
  4. 2023Importance Weighted Actor-Critic for Optimal Conservative Offline Reinforcement Learning30 Jan
  5. 2022Offline Reinforcement Learning via Linear-Programming with Error-Bound Induced Constraints28 Dec
  6. 2022On Instance-Dependent Bounds for Offline Reinforcement Learning with Linear Function Approximation23 Nov
  7. 2022Optimal Conservative Offline RL with General Function Approximation via Augmented Lagrangian1 Nov
  8. 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Game31 May
  9. 2022Offline Reinforcement Learning Under Value and Density-Ratio Realizability: The Power of Gaps25 Mar
  10. 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrability9 Feb
  11. 2022Adversarially Trained Actor Critic for Offline Reinforcement Learning5 Feb
  12. 2021Offline Neural Contextual Bandits: Pessimism, Optimization and Generalization27 Nov
10 more
  1. 2021Towards Instance-Optimal Offline Reinforcement Learning with Pessimism17 Oct
  2. 2021Representation Learning for Online and Offline RL in Low-rank MDPs9 Oct
  3. 2021Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning19 Aug
  4. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage13 Jul
  5. 2021Bellman-consistent Pessimism for Offline Reinforcement Learning13 Jun
  6. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism22 Mar
  7. 2021Sample Complexity of Offline Reinforcement Learning with Deep ReLU Networks11 Mar
  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. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems4 May

Other references · 20

  1. 2016Deep Exploration via Bootstrapped DQNcited by 518
  2. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  3. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  4. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 285
  5. 2013Learning to Optimize Via Posterior Samplingcited by 253
  6. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  7. 2021The Statistical Complexity of Interactive Decision Makingcited by 208
  8. 2020On the Theory of Transfer Learning: The Importance of Task Diversitycited by 186
  9. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
  10. 2020Minimax-Optimal Off-Policy Evaluation with Linear Function Approximationcited by 120
  11. 2022A Review of Off-Policy Evaluation in Reinforcement Learningcited by 92
  12. 2021Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learningcited by 65
8 more
  1. 2019Off-Policy Policy Gradient with State Distribution Correctioncited by 43
  2. 2022Policy learning "without" overlap: Pessimism and generalized empirical Bernstein's inequalitycited by 32
  3. 2022A Provably Efficient Model-Free Posterior Sampling Method for Episodic Reinforcement Learningcited by 30
  4. 2021Policy Learning with Adaptively Collected Datacited by 21
  5. 2022A Self-Play Posterior Sampling Algorithm for Zero-Sum Markov Gamescited by 14
  6. 2022Sample Complexity of Nonparametric Off-Policy Evaluation on Low-Dimensional Manifolds using Deep Networkscited by 12
  7. 2022Non-Linear Reinforcement Learning in Large Action Spaces: Structural Conditions and Sample-efficiency of Posterior Samplingcited by 10
  8. 2023Local Optimization Achieves Global Optimality in Multi-Agent Reinforcement Learningcited by 4

Built on by

Cited by year

Citing papers per year: 2024: 2; 2025: 4.

6 papers.

  1. 2024Offline Multitask Representation Learning for Reinforcement Learningcited by 14
  2. 2025Provable Zero-Shot Generalization in Offline Reinforcement Learningcited by 3
  3. 2024Continual Diffuser (CoD): Mastering Continual Offline Reinforcement Learning with Experience Rehearsalcited by 2
  4. 2025On The Statistical Complexity of Offline Decision-Makingcited by 2
  5. 2025Online Optimization for Offline Safe Reinforcement Learningcited by 1
  6. 2025Data Uniformity Improves Training Efficiency and More, with a Convergence Framework Beyond the NTK Regimecited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learning
  2. 2023On the Sample Complexity of Vanilla Model-Based Offline Reinforcement Learning with Dependent Samples
  3. 2023Beyond Uniform Sampling: Offline Reinforcement Learning with Imbalanced Datasets
  4. 2023Offline Reinforcement Learning with Additional Covering Distributions
  5. 2021Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation
  6. 2021Importance of Empirical Sample Complexity Analysis for Offline Reinforcement Learning
  7. 2025On the Statistical Complexity for Offline and Low-Adaptive Reinforcement Learning with Structures
  8. 2025Unsupervised Data Generation for Offline Reinforcement Learning: A Perspective from Model