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

Abstract

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 $\pi$, which does not provide useful bounds for offline policy learning as $\pi$ 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 $\tilde{O}(H^3/d_m{\epsilon }^2)$ in identifying an $\epsilon$-optimal policy under the time-inhomogeneous episodic MDP model ($H$ is the planning horizon, $d_m$ is a quantity that reflects the exploration of the logging policy $\mu$). 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.

arXiv commentShort version presented at Offline RL workshop at Neurips, 2020

Cited by in corpus (15)

• Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RL
• Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning
• Finite Sample Analysis of Minimax Offline Reinforcement Learning: Completeness, Fast Rates and First-Order Efficiency
• Corruption-Robust Offline Reinforcement Learning
• Nearly Horizon-Free Offline Reinforcement Learning
• Infinite-Horizon Offline Reinforcement Learning with Linear Function Approximation: Curse of Dimensionality and Algorithm
• Towards Instance-Optimal Offline Reinforcement Learning with Pessimism
• Fast Rates for the Regret of Offline Reinforcement Learning
• Towards Theoretical Understandings of Robust Markov Decision Processes: Sample Complexity and Asymptotics
• Explaining Off-Policy Actor-Critic From A Bias-Variance Perspective
• Offline Neural Contextual Bandits: Pessimism, Optimization and Generalization
• Sample Complexity of Offline Reinforcement Learning with Deep ReLU Networks
• Optimal Uniform OPE and Model-based Offline Reinforcement Learning in Time-Homogeneous, Reward-Free and Task-Agnostic Settings
• Variance-Aware Off-Policy Evaluation with Linear Function Approximation
• Stateful Offline Contextual Policy Evaluation and Learning