# On the Sample Complexity of Vanilla Model-Based Offline Reinforcement Learning with Dependent Samples

arXiv: https://arxiv.org/abs/2303.04268 · HTML: https://mlsanity.com/paper/2303.04268/

## Key facts

- Cited by 4 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 17 of its 32 references that are in the map.
- First posted on arXiv 7 Mar 2023.

## Placed in

- Offline RL and imitation learning from data / [Offline RL algorithms](https://mlsanity.com/offlinerl/offline-rl-algorithms/)

## Builds on (most cited first, 17 of 17)

- [MOPO: Model-based Offline Policy Optimization](https://mlsanity.com/paper/2005.13239/) (2020)
- [COMBO: Conservative Offline Model-Based Policy Optimization](https://mlsanity.com/paper/2102.08363/) (2021)
- [Learning Hand-Eye Coordination for Robotic Grasping with Deep Learning and Large-Scale Data Collection](https://mlsanity.com/paper/1603.02199/) (2016)
- [Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism](https://mlsanity.com/paper/2103.12021/) (2021)
- [Visual Foresight: Model-Based Deep Reinforcement Learning for Vision-Based Robotic Control](https://mlsanity.com/paper/1812.00568/) (2018)
- [Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimation](https://mlsanity.com/paper/1810.12429/) (2018)
- [Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage](https://mlsanity.com/paper/2107.06226/) (2021)
- [Minimax Weight and Q-Function Learning for Off-Policy Evaluation](https://mlsanity.com/paper/1910.12809/) (2019)
- [Learning Synergies between Pushing and Grasping with Self-supervised Deep Reinforcement Learning](https://mlsanity.com/paper/1803.09956/) (2018)
- [Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Sampling](https://mlsanity.com/paper/1906.03393/) (2019)
- [Off-policy evaluation for slate recommendation](https://mlsanity.com/paper/1605.04812/) (2016)
- [Offline A/B testing for Recommender Systems](https://mlsanity.com/paper/1801.07030/) (2018)
- [Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis](https://mlsanity.com/paper/2102.06548/) (2021)
- [Settling the Sample Complexity of Model-Based Offline Reinforcement Learning](https://mlsanity.com/paper/2204.05275/) (2022)
- [The Efficacy of Pessimism in Asynchronous Q-Learning](https://mlsanity.com/paper/2203.07368/) (2022)
- [Bootstrapping Fitted Q-Evaluation for Off-Policy Inference](https://mlsanity.com/paper/2102.03607/) (2021)
- [End-to-End Offline Goal-Oriented Dialog Policy Learning via Policy Gradient](https://mlsanity.com/paper/1712.02838/) (2017)

## Built on by (most cited first, 4 of 4)

- [A2PO: Towards Effective Offline Reinforcement Learning from an Advantage-aware Perspective](https://mlsanity.com/paper/2403.07262/) (2024)
- [Expressive Value Learning for Scalable Offline Reinforcement Learning](https://mlsanity.com/paper/2510.08218/) (2025)
- [When Should a Leader Act Suboptimally? The Role of Inferability in Repeated Stackelberg Games](https://mlsanity.com/paper/2310.00468/) (2023)
- [When Does Action Credit Need Updating?](https://mlsanity.com/paper/2609.29007/) (2026)

## Abstract (arXiv)

Offline reinforcement learning (offline RL) considers problems where learning is performed using only previously collected samples and is helpful for the settings in which collecting new data is costly or risky. In model-based offline RL, the learner performs estimation (or optimization) using a model constructed according to the empirical transition frequencies. We analyze the sample complexity of vanilla model-based offline RL with dependent samples in the infinite-horizon discounted-reward setting. In our setting, the samples obey the dynamics of the Markov decision process and, consequently, may have interdependencies. Under no assumption of independent samples, we provide a high-probability, polynomial sample complexity bound for vanilla model-based off-policy evaluation that requires partial or uniform coverage. We extend this result to the off-policy optimization under uniform coverage. As a comparison to the model-based approach, we analyze the sample complexity of off-policy evaluation with vanilla importance sampling in the infinite-horizon setting. Finally, we provide an estimator that outperforms the sample-mean estimator for almost deterministic dynamics that are prevalent in reinforcement learning.