This work studies the statistical limits of uniform convergence for offline policy evaluation (OPE) problems with model-based methods (for finite horizon MDP) and provides a unified view towards optimal learning for several well-motivated offline tasks. Uniform OPE \sup_\Pi|Q^\pi-Q^\pi|<\epsilon (initiated by \mbox{%DIFAUXCMD yin2021near is a stronger measure than the point-wise (fixed policy) OPE and ensures offline policy learning when \Pi contains all policies ( global policy 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 , where d_m is the minimal state-action probability induced by the behavior policy. Next, our main result establishes an episode complexity of O(H^2/d_m\epsilon^2) for  \emph{local} uniform convergence that applies to all \emph{near-empirically optimal} policies for the MDPs with \emph{stationary} transition. This result implies the optimal sample complexity for offline learning and separates the local uniform OPE from the global case due to the extra S factor. Paramountly, the\tilde{O}\emph{  model-based method combining with our new analysis technique (singleton absorbing MDP) can be adapted 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^2S/d_m\epsilon^2) respectively , which provides a unified framework for simultaneously solving different offline RL problems.
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-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 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^2S/d_m\epsilon^2) respectively . These results provide a unified solution for simultaneously solving different offline RL problems.
R
finite horizon
episodic
R
view
framework
D
(initiated by \mbox{%DIFAUXCMD yin2021near
D
(fixed policy)
D
policy
R
global policy
the global
R
, where d_m is the minimal state-action probability induced by the behavior policy. Next,
and
R
episode complexity
upper bound
A
the
R
This result implies the optimal sample complexity for offline learning and separates the local uniform OPE from the global case due to the extra S factor. Paramountly, the
Here d_m is the minimal marginal state-action probability. Critically, the highlight in achieving the optimal rate
A
(H^2/d_m\epsilon^2) is our design of
A
singleton absorbing MDP
A
, which is a new sharp analysis tool that works with the
R
method combining with our new analysis technique (singleton absorbing MDP) can be adapted
approach. We generalize such a model-based framework
R
, which provides a unified framework
. These results provide a unified solution