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

Ming Yin, Yu-Xiang Wang

Executive Summary

This paper establishes the statistical limits of model-based offline reinforcement learning for uniform offline policy evaluation (OPE) in time-homogeneous (stationary) environments. By introducing a novel "singleton-absorbing MDP" analysis technique, the authors achieve optimal sample complexities for offline learning and extend their framework to optimally solve offline task-agnostic and reward-free learning problems.

Introduction

In offline Reinforcement Learning (RL), an agent must learn a reward-maximizing policy using only a static, pre-collected dataset, without any active exploration. A powerful way to guarantee the success of offline RL is through Uniform Offline Policy Evaluation (Uniform OPE), which ensures that the estimated values of an entire class of policies are simultaneously accurate. If an algorithm can accurately evaluate all policies (or all good policies), it can confidently select the optimal one.

Previously, researchers established sample complexity bounds for Uniform OPE in non-stationary environments (where transition dynamics change at every time step). However, for stationary (time-homogeneous) environments, existing bounds were suboptimal. The shared data dependencies across time steps in stationary Markov Decision Processes (MDPs) make the mathematical analysis incredibly tricky. Furthermore, it was unknown whether "global" uniform OPE (evaluating every possible policy) was fundamentally harder than just finding the optimal policy. Finally, the offline versions of more complex settings—like task-agnostic learning (learning multiple tasks at once) and reward-free learning (exploring without a reward signal to prepare for any future reward)—lacked optimal statistical guarantees.

Methodology: The Singleton-Absorbing MDP

The authors focus on model-based plug-in estimators. The algorithm is straightforward: use the offline dataset to build an empirical estimate of the MDP's transition dynamics, and then run a planning algorithm (like Value Iteration) on this empirical MDP.

The true novelty lies in the mathematical analysis used to prove the efficiency of this method. To handle the complex data dependencies in stationary MDPs, the authors invent the Singleton-Absorbing MDP.

  • The standard approach to decouple these dependencies uses "absorbing MDPs" combined with an $\epsilon$-net (a grid of possible value functions). In finite-horizon settings, this grid scales exponentially with the horizon $H$, leading to loose, suboptimal bounds.
  • The novel approach constructs a single, carefully designed absorbing MDP using an $H$-dimensional reference point based on the optimal value function differences. This entirely bypasses the need for an $\epsilon$-net, avoiding the exponential blowup in $H$ and yielding tight, optimal bounds.

Key Insights

  • Global OPE is fundamentally harder than offline learning: The authors prove that evaluating all policies (Global Uniform OPE) requires a sample complexity that scales linearly with the size of the state space $S$. In contrast, finding the optimal policy only requires evaluating "good" policies (Local Uniform OPE), which avoids this $S$ dependence.
  • One absorbing MDP is enough: The "Singleton-Absorbing MDP" technique proves that you do not need a massive, exponentially large grid of absorbing MDPs to decouple data dependencies in stationary finite-horizon MDPs. A single, smartly chosen reference MDP is sufficient.
  • Model-based methods are a universal hammer for offline RL: The exact same simple model-based framework (build an empirical MDP, then plan) is fundamentally powerful enough to optimally solve standard offline RL, task-agnostic offline RL, and reward-free offline RL. The unified perspective shows that these seemingly distinct problems share the same optimal learning pattern in the offline regime.

Main Results

The paper provides several tight sample complexity bounds, where $H$ is the horizon, $S$ is the state space size, $d_m$ is the minimal data coverage probability, and $\epsilon$ is the target accuracy.

Comparison of sample complexities and uniform guarantees across different offline RL methods.
  • Global OPE Lower Bound: Proved a minimax lower bound of $\Omega(H^2S/d_m\epsilon^2)$ for model-based methods, establishing the strict statistical separation between global evaluation and optimal control.
  • Optimal Local OPE & Offline Learning: Achieved an upper bound of $\tilde{O}(H^2/d_m\epsilon^2)$. This is near-minimax optimal, improving upon prior work by a factor of $H$.
  • Offline Task-Agnostic Learning: Proved that learning $K$ different tasks simultaneously from a single offline dataset requires $\tilde{O}(H^2\log(K)/d_m\epsilon^2)$ episodes, which is optimal.
  • Offline Reward-Free Learning: Proved that guaranteeing an optimal policy for any arbitrarily chosen future reward function requires $\tilde{O}(H^2S/d_m\epsilon^2)$ episodes.
  • Extension to Linear MDPs: Successfully extended the singleton-absorbing MDP trick to linear MDPs with anchor representations, achieving an optimal total sample complexity of $\tilde{O}(KH^3/\epsilon^2)$.

Limitations and Future Directions

While the main terms in the provided bounds are optimal, the higher-order error terms still contain an additional $\sqrt{HS}$ dependence. The authors note that removing this remains an elusive challenge for the community.

Additionally, the extension to linear MDPs relies on "anchor representations" (assuming the state-action space can be represented as a convex combination of finite anchor points), which the authors acknowledge is a somewhat strong assumption. Future work could extend uniform OPE to more practical settings, such as general linear MDPs (without anchor assumptions), game environments, and multi-agent settings. The authors also propose developing general complexity measures (analogous to VC-dimension in supervised learning) that precisely capture uniform convergence in RL.

Summary updated

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^2S/d_m\epsilon^2)$ respectively. These results provide a unified solution for simultaneously solving different offline RL problems.
BibTeX
@inproceedings{yin2021optimal,
  author = {Ming Yin and Yu-Xiang Wang},
  title = {{Optimal Uniform OPE and Model-based Offline Reinforcement Learning in Time-Homogeneous, Reward-Free and Task-Agnostic Settings}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=yMf3SLah5-y},
}
Figure