# Near-Optimal Provable Uniform Convergence in Offline Policy Evaluation for Reinforcement Learning

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

## Key facts

- Cited by 26 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.
- First posted on arXiv 7 Jul 2020.

## Placed in

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

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

- [Is Pessimism Provably Efficient for Offline RL?](https://mlsanity.com/paper/2012.15085/) (2020)
- [Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism](https://mlsanity.com/paper/2103.12021/) (2021)
- [Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning](https://mlsanity.com/paper/2106.04895/) (2021)
- [Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning](https://mlsanity.com/paper/2108.08812/) (2021)
- [Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexity](https://mlsanity.com/paper/2202.13890/) (2022)
- [Towards Instance-Optimal Offline Reinforcement Learning with Pessimism](https://mlsanity.com/paper/2110.08695/) (2021)
- [Near-Optimal Offline Reinforcement Learning via Double Variance Reduction](https://mlsanity.com/paper/2102.01748/) (2021)
- [Finite Sample Analysis of Minimax Offline Reinforcement Learning: Completeness, Fast Rates and First-Order Efficiency](https://mlsanity.com/paper/2102.02981/) (2021)
- [Corruption-Robust Offline Reinforcement Learning](https://mlsanity.com/paper/2106.06630/) (2021)
- [Risk Bounds and Rademacher Complexity in Batch Reinforcement Learning](https://mlsanity.com/paper/2103.13883/) (2021)
- [Nearly Horizon-Free Offline Reinforcement Learning](https://mlsanity.com/paper/2103.14077/) (2021)
- [Variance-Aware Off-Policy Evaluation with Linear Function Approximation](https://mlsanity.com/paper/2106.11960/) (2021)
- [Fast Rates for the Regret of Offline Reinforcement Learning](https://mlsanity.com/paper/2102.00479/) (2021)
- [Offline Learning in Markov Games with General Function Approximation](https://mlsanity.com/paper/2302.02571/) (2023)
- [Offline Multitask Representation Learning for Reinforcement Learning](https://mlsanity.com/paper/2403.11574/) (2024)
- [Offline Reinforcement Learning with Differentiable Function Approximation is Provably Efficient](https://mlsanity.com/paper/2210.00750/) (2022)
- [Non-asymptotic Confidence Intervals of Off-policy Evaluation: Primal and Dual Bounds](https://mlsanity.com/paper/2103.05741/) (2021)
- [Policy Finetuning in Reinforcement Learning via Design of Experiments using Offline Data](https://mlsanity.com/paper/2307.04354/) (2023)
- [Infinite-Horizon Offline Reinforcement Learning with Linear Function Approximation: Curse of Dimensionality and Algorithm](https://mlsanity.com/paper/2103.09847/) (2021)
- [Bellman Residual Orthogonalization for Offline Reinforcement Learning](https://mlsanity.com/paper/2203.12786/) (2022)
- [Hybrid Transfer Reinforcement Learning: Provable Sample Efficiency from Shifted-Dynamics Data](https://mlsanity.com/paper/2411.03810/) (2024)
- [Model-based Offline Reinforcement Learning with Local Misspecification](https://mlsanity.com/paper/2301.11426/) (2023)
- [Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Path](https://mlsanity.com/paper/2210.04946/) (2022)
- [The Curse of Passive Data Collection in Batch Reinforcement Learning](https://mlsanity.com/paper/2106.09973/) (2021)
- [Explaining Off-Policy Actor-Critic From A Bias-Variance Perspective](https://mlsanity.com/paper/2110.02421/) (2021)
- [Stochastic Gradient Descent with Dependent Data for Offline Reinforcement Learning](https://mlsanity.com/paper/2202.02850/) (2022)

## Abstract (arXiv)

The problem of Offline Policy Evaluation (OPE) in Reinforcement Learning (RL) is a critical step towards applying RL in real-life applications. Existing work on OPE mostly focus on evaluating a fixed target policy π, which does not provide useful bounds for offline policy learning as π will then be data-dependent. We address this problem by simultaneously evaluating all policies in a policy class Pi -- uniform convergence in OPE -- and obtain nearly optimal error bounds for a number of global / local policy classes. Our results imply that the model-based planning achieves an optimal episode complexity of widetildeO(H3/dmε2) in identifying an ε-optimal policy under the time-inhomogeneous episodic MDP model (H is the planning horizon, dm is a quantity that reflects the exploration of the logging policy μ). To the best of our knowledge, this is the first time the optimal rate is shown to be possible for the offline RL setting and the paper is the first that systematically investigates the uniform convergence in OPE.