Abstract
Off-policy evaluation (OPE) is essential for predicting the performance of new policies using historical data, particularly in high-stakes fields like healthcare and autonomous driving. Traditional OPE methods primarily estimate the expected return, which often fails to capture critical risk and uncertainty profiles. We present the Universal Off-Policy Estimator (UnO), a framework that first estimates the entire cumulative distribution function (CDF) of returns. This approach provides a unified mechanism to derive high-confidence bounds for any performance metric—including CVaR, variance, and medians—while remaining robust to non-stationarity and partial observability.
Introduction
In Reinforcement Learning, OPE is the task of predicting how a new "evaluation policy" will perform using only historical data collected by a different "behavior policy." This is vital in real-world scenarios where testing a new, unproven strategy live is too risky or expensive. Traditionally, OPE has focused almost exclusively on estimating the expected return (the mean). However, the mean is a poor metric for safety-critical systems. For instance, a medical treatment might have a high average success rate but a 5% chance of being fatal; the mean alone obscures this risk.
To address this, we need to evaluate risk (e.g., Value at Risk), uncertainty (variance), or robustness (median). Until now, estimating these metrics required specialized, often complex algorithms that rarely provided "finite-sample" confidence bounds—mathematical guarantees that the true value lies within a certain range based on limited data.
The UnO Framework
The core innovation of the Universal Off-Policy Estimator (UnO) is to estimate the Cumulative Distribution Function (CDF) first, rather than targeting specific scalar metrics directly.
CDF Estimation and Confidence Bands
Instead of using Importance Sampling (IS) to correct the mean return, UnO uses it to estimate the probability that a return is less than or equal to a specific value $\nu$. By evaluating this across various points, the framework constructs an unbiased estimate of the entire return distribution.
Once the CDF is estimated, the authors construct a "confidence band"—a region in which the true CDF is guaranteed to lie with high probability. This is achieved by calculating confidence intervals at several key points and leveraging the monotonic nature of CDFs to interpolate the bounds.
Universal Metric Bounding
With a valid confidence band for the CDF, high-confidence upper and lower bounds for any metric can be found by identifying the "best-case" and "worst-case" CDFs within that band. This allows for simultaneous guarantees across multiple metrics without the need for loose "union bounds."
Experimental Evaluation
The authors evaluated UnO across three diverse domains:
- Diabetes Treatment: Using an FDA-approved simulator (Simglucose), representing a high-stakes medical application where risk (CVaR) is paramount.
- Recommender Systems: Tested in both stationary and non-stationary modes to simulate drifting user interests.
- Gridworld (POMDP): A continuous-state world with partial observability and unobserved confounders.
Key Insights and Results
- Universality and Efficiency: UnO accurately estimated the entire CDF across all domains. In the Diabetes Treatment task, it provided competitive bounds for the mean and significantly tighter bounds for variance compared to previous state-of-the-art specialized methods.
- Better Variance Bounds: UnO's general-purpose bounds for variance can be an order of magnitude tighter than specialized bounds. This is because UnO's CDF-based approach avoids the squared importance weights ($\rho^2$) that often cause traditional variance estimators to explode over long horizons.
- Robustness to Drift: In non-stationary environments, a variant of UnO using wild bootstrapping successfully bounded future performance, whereas standard OPE methods assuming stationarity failed as the speed of environmental change increased.
- Minimal Assumptions: UnO is model-free and does not require the environment to be Markovian. It remains valid even in the presence of hidden confounders, provided the behavior policy's action probabilities are known.
Limitations and Future Work
Despite its advantages, UnO faces the "Curse of Horizon." Like all importance sampling methods, the estimator's variance grows exponentially with episode length. Furthermore, UnO requires exact knowledge of the behavior policy ($\beta$). If $\beta$ must be estimated from data (e.g., from human experts), it introduces bias and may compromise the theoretical coverage of the bounds. Future work may involve combining UnO with "doubly robust" techniques to further reduce variance in long-horizon problems.
Summary updated