Optimal Uniform OPE and Model-based Offline Reinforcement Learning in Time-Homogeneous, Reward-Free and Task-Agnostic Settings
This work addresses foundational statistical challenges in offline reinforcement learning, providing optimal rates for uniform convergence that unify solutions across multiple offline tasks, though it is incremental in refining existing model-based frameworks.
This paper tackles the statistical limits of uniform convergence for offline policy evaluation in episodic MDPs, establishing a lower bound of Ω(H²S/d_mε²) and an upper bound of Õ(H²/d_mε²) for local uniform convergence, with extensions to task-agnostic and reward-free settings achieving optimal complexities of Õ(H²log(K)/d_mε²) and Õ(H²S/d_mε²), respectively.
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_Π|Q^π-\hat{Q}^π|<ε$ is a stronger measure than the point-wise OPE and ensures offline learning when $Π$ contains all policies (the global class). In this paper, we establish an $Ω(H^2 S/d_mε^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ε^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ε^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ε^2)$ ($K$ is the number of tasks) and $\tilde{O}(H^2S/d_mε^2)$ respectively. These results provide a unified solution for simultaneously solving different offline RL problems.