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

Abstract

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^{\pi }-{\hat{Q}}^{\pi }|<\epsilon$ 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 (H^{2}S/d_m{\epsilon }^2)$ lower bound (over model-based family) for the global uniform OPE and our main result establishes an upper bound of $\tilde{O}(H^2/d_m{\epsilon }^2)$ for the \emph{local} uniform convergence that applies to all \emph{near-empirically optimal} policies for the MDPs with \emph{stationary} transition. Here $d_m$ is the minimal marginal state-action probability. Critically, the highlight in achieving the optimal rate $\tilde{O}(H^2/d_m{\epsilon }^2)$ is our design of \emph{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 $\tilde{O}(H^2\log (K)/d_m{\epsilon }^2)$ ($K$ is the number of tasks) and $\tilde{O}(H^{2}S/d_m{\epsilon }^2)$ respectively. These results provide a unified solution for simultaneously solving different offline RL problems.

References in corpus (20)

• Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems
• MOPO: Model-based Offline Policy Optimization
• Provably Efficient Reinforcement Learning with Linear Function Approximation
• MOReL : Model-Based Offline Reinforcement Learning
• Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimation
• What are the Statistical Limits of Offline RL with Linear Function Approximation?
• Provably Good Batch Reinforcement Learning Without Great Exploration
• On Reward-Free Reinforcement Learning with Linear Function Approximation
• Fast active learning for pure exploration in reinforcement learning
• Batch Value-function Approximation with Only Realizability
• Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon
• Is Pessimism Provably Efficient for Offline RL?
• Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity
• Near-Optimal Provable Uniform Convergence in Offline Policy Evaluation for Reinforcement Learning
• Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RL
• Near-Optimal Offline Reinforcement Learning via Double Variance Reduction
• Sparse Feature Selection Makes Batch Reinforcement Learning More Sample Efficient
• Adaptive Reward-Free Exploration
• Nearly Minimax Optimal Reward-free Reinforcement Learning
• Nearly Horizon-Free Offline Reinforcement Learning