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

Understand

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 $\widetilde{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$).