# Optimal Uniform OPE and Model-based Offline Reinforcement Learning in Time-Homogeneous, Reward-Free and Task-Agnostic Settings

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

## Key facts

- Cited by 14 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 56 of its 88 references that are in the map.
- First posted on arXiv 13 May 2021.

## Placed in

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

## Builds on (most cited first, 30 of 56)

- [Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems](https://mlsanity.com/paper/2005.01643/) (2020)
- [MOPO: Model-based Offline Policy Optimization](https://mlsanity.com/paper/2005.13239/) (2020)
- [MOReL : Model-Based Offline Reinforcement Learning](https://mlsanity.com/paper/2005.05951/) (2020)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Is Pessimism Provably Efficient for Offline RL?](https://mlsanity.com/paper/2012.15085/) (2020)
- [Doubly Robust Off-policy Value Evaluation for Reinforcement Learning](https://mlsanity.com/paper/1511.03722/) (2015)
- [Information-Theoretic Considerations in Batch Reinforcement Learning](https://mlsanity.com/paper/1905.00360/) (2019)
- [Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism](https://mlsanity.com/paper/2103.12021/) (2021)
- [DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Corrections](https://mlsanity.com/paper/1906.04733/) (2019)
- [Batch Policy Learning under Constraints](https://mlsanity.com/paper/1903.08738/) (2019)
- [Model-Based Reinforcement Learning with Value-Targeted Regression](https://mlsanity.com/paper/2006.01107/) (2020)
- [Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimation](https://mlsanity.com/paper/1810.12429/) (2018)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes](https://mlsanity.com/paper/2012.08507/) (2020)
- [Reward-Free Exploration for Reinforcement Learning](https://mlsanity.com/paper/2002.02794/) (2020)
- [Minimax Weight and Q-Function Learning for Off-Policy Evaluation](https://mlsanity.com/paper/1910.12809/) (2019)
- [What are the Statistical Limits of Offline RL with Linear Function Approximation?](https://mlsanity.com/paper/2010.11895/) (2020)
- [Provably Efficient Safe Exploration via Primal-Dual Policy Optimization](https://mlsanity.com/paper/2003.00534/) (2020)
- [Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal](https://mlsanity.com/paper/1906.03804/) (2019)
- [GenDICE: Generalized Offline Estimation of Stationary Values](https://mlsanity.com/paper/2002.09072/) (2020)
- [Minimax-Optimal Off-Policy Evaluation with Linear Function Approximation](https://mlsanity.com/paper/2002.09516/) (2020)
- [Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Sampling](https://mlsanity.com/paper/1906.03393/) (2019)
- [Double Reinforcement Learning for Efficient Off-Policy Evaluation in Markov Decision Processes](https://mlsanity.com/paper/1908.08526/) (2019)
- [Optimal and Adaptive Off-policy Evaluation in Contextual Bandits](https://mlsanity.com/paper/1612.01205/) (2016)
- [Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2005.12900/) (2020)
- [A Sharp Analysis of Model-based Reinforcement Learning with Self-Play](https://mlsanity.com/paper/2010.01604/) (2020)
- [Batch Value-function Approximation with Only Realizability](https://mlsanity.com/paper/2008.04990/) (2020)
- [Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon](https://mlsanity.com/paper/2009.13503/) (2020)
- [Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity](https://mlsanity.com/paper/2007.07461/) (2020)

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

- [Distributionally Robust Model-Based Offline Reinforcement Learning with Near-Optimal Sample Complexity](https://mlsanity.com/paper/2208.05767/) (2022)
- [Towards Instance-Optimal Offline Reinforcement Learning with Pessimism](https://mlsanity.com/paper/2110.08695/) (2021)
- [Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimism](https://mlsanity.com/paper/2203.05804/) (2022)
- [Provable Benefit of Multitask Representation Learning in Reinforcement Learning](https://mlsanity.com/paper/2206.05900/) (2022)
- [On the Statistical Efficiency of Reward-Free Exploration in Non-Linear RL](https://mlsanity.com/paper/2206.10770/) (2022)
- [Offline Reinforcement Learning with Differential Privacy](https://mlsanity.com/paper/2206.00810/) (2022)
- [Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learning](https://mlsanity.com/paper/2304.07278/) (2023)
- [Provably Feedback-Efficient Reinforcement Learning via Active Reward Learning](https://mlsanity.com/paper/2304.08944/) (2023)
- [Provably Efficient Offline Reinforcement Learning with Trajectory-Wise Reward](https://mlsanity.com/paper/2206.06426/) (2022)
- [Provable Benefits of Policy Learning from Human Preferences in Contextual Bandit Problems](https://mlsanity.com/paper/2307.12975/) (2023)
- [Diffused Task-Agnostic Milestone Planner](https://mlsanity.com/paper/2312.03395/) (2023)
- [Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learning](https://mlsanity.com/paper/2310.06793/) (2023)
- [When is Offline Policy Selection Sample Efficient for Reinforcement Learning?](https://mlsanity.com/paper/2312.02355/) (2023)
- [The Curse of Passive Data Collection in Batch Reinforcement Learning](https://mlsanity.com/paper/2106.09973/) (2021)

## Abstract (arXiv)

This work studies the statistical limits of uniform convergence for offline policy evaluation (OPE) problems with model-based methods (for episodic MDP) and provides a unified framework towards optimal learning for several well-motivated offline tasks. Uniform OPE sup_Pi|Qπ-hatQπ|<ε is a stronger measure than the point-wise OPE and ensures offline learning when Pi contains all policies (the global class). In this paper, we establish an Omega(H2 S/dmε2) lower bound (over model-based family) for the global uniform OPE and our main result establishes an upper bound of tildeO(H2/dmε2) for the local uniform convergence that applies to all near-empirically optimal policies for the MDPs with stationary transition. Here dm is the minimal marginal state-action probability. Critically, the highlight in achieving the optimal rate tildeO(H2/dmε2) is our design of singleton absorbing MDP, which is a new sharp analysis tool that works with the model-based approach. We generalize such a model-based framework to the new settings: offline task-agnostic and the offline reward-free with optimal complexity tildeO(H2log(K)/dmε2) (K is the number of tasks) and tildeO(H2S/dmε2) respectively. These results provide a unified solution for simultaneously solving different offline RL problems.