mlsanityData to 7 Oct 2026

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

arXiv 2007.03760 ↗First posted 7 Jul 2020cs.LG cs.AI stat.MLcited by 26

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

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.

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

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2020: 1; 2021: 15; 2022: 5; 2023: 3; 2024: 2.

26 papers.

Sort:

By area:

  1. 2020Is Pessimism Provably Efficient for Offline RL?cited by 362
  2. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimismcited by 275
  3. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learningcited by 157
  4. 2021Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learningcited by 109
  5. 2022Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexitycited by 84
  6. 2021Towards Instance-Optimal Offline Reinforcement Learning with Pessimismcited by 78
  7. 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reductioncited by 56
  8. 2021Finite Sample Analysis of Minimax Offline Reinforcement Learning: Completeness, Fast Rates and First-Order Efficiencycited by 54
  9. 2021Corruption-Robust Offline Reinforcement Learningcited by 51
  10. 2021Risk Bounds and Rademacher Complexity in Batch Reinforcement Learningcited by 42
  11. 2021Nearly Horizon-Free Offline Reinforcement Learningcited by 36
  12. 2021Variance-Aware Off-Policy Evaluation with Linear Function Approximationcited by 34
14 more
  1. 2021Fast Rates for the Regret of Offline Reinforcement Learningcited by 26
  2. 2023Offline Learning in Markov Games with General Function Approximationcited by 16
  3. 2024Offline Multitask Representation Learning for Reinforcement Learningcited by 14
  4. 2022Offline Reinforcement Learning with Differentiable Function Approximation is Provably Efficientcited by 12
  5. 2021Non-asymptotic Confidence Intervals of Off-policy Evaluation: Primal and Dual Boundscited by 11
  6. 2023Policy Finetuning in Reinforcement Learning via Design of Experiments using Offline Datacited by 11
  7. 2021Infinite-Horizon Offline Reinforcement Learning with Linear Function Approximation: Curse of Dimensionality and Algorithmcited by 10
  8. 2022Bellman Residual Orthogonalization for Offline Reinforcement Learningcited by 10
  9. 2024Hybrid Transfer Reinforcement Learning: Provable Sample Efficiency from Shifted-Dynamics Datacited by 8
  10. 2023Model-based Offline Reinforcement Learning with Local Misspecificationcited by 5
  11. 2022Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Pathcited by 4
  12. 2021The Curse of Passive Data Collection in Batch Reinforcement Learningcited by 2
  13. 2021Explaining Off-Policy Actor-Critic From A Bias-Variance Perspectivecited by 2
  14. 2022Stochastic Gradient Descent with Dependent Data for Offline Reinforcement Learningcited by 2

Similar, not cited

Close in wording, no citation either way

  1. 2021Optimal Uniform OPE and Model-based Offline Reinforcement Learning in Time-Homogeneous, Reward-Free and Task-Agnostic Settings
  2. 2023Offline Policy Evaluation for Reinforcement Learning with Adaptively Collected Data
  3. 2022Offline Reinforcement Learning via Linear-Programming with Error-Bound Induced Constraints
  4. 2020MOPO: Model-based Offline Policy Optimization
  5. 2021You Only Evaluate Once: a Simple Baseline Algorithm for Offline RL
  6. 2025On the Statistical Complexity for Offline and Low-Adaptive Reinforcement Learning with Structures
  7. 2025Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RL
  8. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learning