mlsanityData to 7 Oct 2026

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

arXiv 2105.06029 ↗First posted 13 May 2021cs.LG cs.AI stat.MLcited by 14

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

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.

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

Builds on

56 of 88 references.

Closest ancestors · 15

Same direction, newest first

  1. 2021Nearly Horizon-Free Offline Reinforcement Learning25 Mar
  2. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism22 Mar
  3. 2021Finite Sample Analysis of Minimax Offline Reinforcement Learning: Completeness, Fast Rates and First-Order Efficiency5 Feb
  4. 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reduction2 Feb
  5. 2021Fast Rates for the Regret of Offline Reinforcement Learning31 Jan
  6. 2020Is Pessimism Provably Efficient for Offline RL?30 Dec
  7. 2020Sparse Feature Selection Makes Batch Reinforcement Learning More Sample Efficient8 Nov
  8. 2020What are the Statistical Limits of Offline RL with Linear Function Approximation?22 Oct
  9. 2020Nearly Minimax Optimal Reward-free Reinforcement Learning12 Oct
  10. 2020Batch Value-function Approximation with Only Realizability11 Aug
  11. 2020Provably Good Batch Reinforcement Learning Without Great Exploration16 Jul
  12. 2020On Reward-Free Reinforcement Learning with Linear Function Approximation19 Jun
3 more
  1. 2020MOPO: Model-based Offline Policy Optimization27 May
  2. 2020MOReL : Model-Based Offline Reinforcement Learning12 May
  3. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems4 May

Other references · 41

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  2. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  3. 2018Is Q-learning Provably Efficient?cited by 485
  4. 2015Doubly Robust Off-policy Value Evaluation for Reinforcement Learningcited by 337
  5. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 285
  6. 2019DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Correctionscited by 254
  7. 2019Batch Policy Learning under Constraintscited by 242
  8. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  9. 2018Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimationcited by 226
  10. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
  11. 2020Reward-Free Exploration for Reinforcement Learningcited by 177
  12. 2019Minimax Weight and Q-Function Learning for Off-Policy Evaluationcited by 150
29 more
  1. 2020Provably Efficient Safe Exploration via Primal-Dual Policy Optimizationcited by 131
  2. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 124
  3. 2020GenDICE: Generalized Offline Estimation of Stationary Valuescited by 122
  4. 2020Minimax-Optimal Off-Policy Evaluation with Linear Function Approximationcited by 120
  5. 2019Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Samplingcited by 118
  6. 2019Double Reinforcement Learning for Efficient Off-Policy Evaluation in Markov Decision Processescited by 118
  7. 2016Optimal and Adaptive Off-policy Evaluation in Contextual Banditscited by 111
  8. 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 108
  9. 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 104
  10. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
  11. 2020Fast active learning for pure exploration in reinforcement learningcited by 92
  12. 2020Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexitycited by 91
  13. 2018Policy Certificates: Towards Accountable Reinforcement Learningcited by 81
  14. 2020Adaptive Reward-Free Explorationcited by 77
  15. 2018On Offline Evaluation of Vision-based Driving Modelscited by 62
  16. 2020Asymptotically Efficient Off-Policy Evaluation for Tabular Reinforcement Learningcited by 60
  17. 2020Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RLcited by 55
  18. 2019Simulation-based reinforcement learning for real-world autonomous drivingcited by 51
  19. 2019Tight Regret Bounds for Model-Based Reinforcement Learning with Greedy Policiescited by 38
  20. 2020Confident Off-Policy Evaluation and Selection through Self-Normalized Importance Weightingcited by 38
  21. 2019A Kernel Loss for Solving the Bellman Equationcited by 37
  22. 2020Task-agnostic Exploration in Reinforcement Learningcited by 37
  23. 2020Accountable Off-Policy Evaluation With Kernel Bellman Statisticscited by 36
  24. 2021Average-Reward Off-Policy Policy Evaluation with Function Approximationcited by 30
  25. 2019Intrinsically Efficient, Stable, and Bounded Off-Policy Evaluation for Reinforcement Learningcited by 28
  26. 2021On the Optimality of Batch Policy Optimization Algorithmscited by 28
  27. 2020Off-Policy Evaluation and Learning for External Validity under a Covariate Shiftcited by 26
  28. 2018Deep Reinforcement Learning for Dynamic Treatment Regimes on Medical Registry Datacited by 23
  29. 2020Is Plug-in Solver Sample-Efficient for Feature-based Reinforcement Learning?cited by 9

Built on by

Cited by year

Citing papers per year: 2021: 2; 2022: 6; 2023: 6.

14 papers.

Sort:

By area:

  1. 2022Distributionally Robust Model-Based Offline Reinforcement Learning with Near-Optimal Sample Complexitycited by 85
  2. 2021Towards Instance-Optimal Offline Reinforcement Learning with Pessimismcited by 78
  3. 2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimismcited by 63
  4. 2022Provable Benefit of Multitask Representation Learning in Reinforcement Learningcited by 29
  5. 2022On the Statistical Efficiency of Reward-Free Exploration in Non-Linear RLcited by 27
  6. 2022Offline Reinforcement Learning with Differential Privacycited by 19
  7. 2023Provably Feedback-Efficient Reinforcement Learning via Active Reward Learningcited by 15
  8. 2023Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learningcited by 14
  9. 2022Provably Efficient Offline Reinforcement Learning with Trajectory-Wise Rewardcited by 13
  10. 2023Provable Benefits of Policy Learning from Human Preferences in Contextual Bandit Problemscited by 12
  11. 2023Diffused Task-Agnostic Milestone Plannercited by 12
  12. 2023Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learningcited by 9
2 more
  1. 2023When is Offline Policy Selection Sample Efficient for Reinforcement Learning?cited by 3
  2. 2021The Curse of Passive Data Collection in Batch Reinforcement Learningcited by 2

Similar, not cited

Close in wording, no citation either way

  1. 2020Near-Optimal Provable Uniform Convergence in Offline Policy Evaluation for Reinforcement Learning
  2. 2023On the Sample Complexity of Vanilla Model-Based Offline Reinforcement Learning with Dependent Samples
  3. 2025On the Statistical Complexity for Offline and Low-Adaptive Reinforcement Learning with Structures
  4. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learning
  5. 2023Model-based Offline Reinforcement Learning with Local Misspecification
  6. 2022Offline Reinforcement Learning via Linear-Programming with Error-Bound Induced Constraints
  7. 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrability
  8. 2025Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RL