Abstract
Off-policy evaluation (OPE) is the problem of estimating the value of a target policy using historical data collected under a different logging policy. OPE methods typically assume overlap between the target and logging policy, enabling solutions based on importance weighting and/or imputation. In this work, we approach OPE without assuming either overlap or a well-specified model by considering a strategy based on partial identification under non-parametric assumptions on the conditional mean function, focusing especially on Lipschitz smoothness. Under such smoothness assumptions, we formulate a pair of linear programs whose optimal values upper and lower bound the contributions of the no-overlap region to the off-policy value. We show that these linear programs have a concise closed form solution that can be computed efficiently and that their solutions converge, under the Lipschitz assumption, to the sharp partial identification bounds on the off-policy value. Furthermore, we show that the rate of convergence is minimax optimal, up to log factors. We deploy our methods on two semi-synthetic examples, and obtain informative and valid bounds that are tighter than those possible without smoothness assumptions.
Introduction
Off-policy evaluation (OPE) is a cornerstone of data-driven decision-making, allowing researchers to estimate the performance of a new "target" policy using data generated by a different "logging" policy. This is critical in domains like medicine or autonomous driving, where deploying an untested policy is risky or unethical.
Traditional OPE methods rely heavily on the overlap assumption: the requirement that every action the target policy might take has been tried at least occasionally by the logging policy. When this assumption is violated—for instance, if a clinical trial never tested a specific drug on a certain age group—standard estimators like Inverse Probability Weighting (IPW) suffer from infinite variance, while imputation methods rely on potentially biased extrapolations. This paper addresses the challenge of OPE in the no-overlap region by shifting the goal from point estimation to partial identification.
Methodology: Bounding the Unknown
Instead of attempting to guess a single value for the reward in regions where data is missing, the authors propose finding a valid range (interval) that the true value must fall into. This is achieved by imposing a non-parametric assumption: Lipschitz smoothness.
If we assume the underlying reward function is $L$-Lipschitz, then for any two points $x$ and $x'$, the difference in their rewards is bounded by $L$ times the distance between them. This allows us to use known data points in the overlap region to constrain the possible values in the no-overlap region.
As shown in the figure above, the evaluation is decomposed into two parts. In the overlap region ($\pi_b > 0$), standard estimators provide a point estimate. In the no-overlap region (the shaded area where $\pi_b = 0$), the Lipschitz assumption generates diverging upper and lower bounds that define the uncertainty of the policy's performance.
The No-Interaction Property and Efficient Computation
Initially, finding the tightest possible bounds requires solving complex linear programs (LPs) over the entire covariate space. However, the authors identify a critical mathematical breakthrough termed the no-interaction property.
This property states that for Lipschitz smoothness, the constraints on a point in the "blind spot" are determined solely by its relationship to the observed data, rather than by other unknown points in the no-overlap region. This insight simplifies a potentially $O(n^5)$ optimization problem into a closed-form solution that can be computed in $O(n^2)$ time, making it scalable to large datasets.
Theoretical and Empirical Results
The proposed framework is not only computationally efficient but also theoretically robust. The authors prove that their estimator achieves minimax optimality, converging to the sharpest possible bounds at a rate of $n^{-2/(d+2)}$, where $d$ is the number of covariates.
Empirical evaluations were conducted on two datasets:
- Yeast Dataset (UCI): In simulations where the logging policy intentionally avoided certain actions, the Lipschitz-based bounds were 40-50% narrower than standard "Manski bounds" (which only assume rewards are within a fixed range like [0, 1]).
- Yahoo! Front Page Today Dataset: On real-world news recommendation data, the method successfully identified the uncertainty inherent in regions where the logging policy was highly selective, providing valid intervals that contained the true policy value while highlighting the risks of pure imputation.
Conclusion
By framing OPE as a partial identification problem, this work provides a rigorous way to handle "blind spots" in historical data. The Lipschitz constant $L$ serves as a transparent "knob" for sensitivity analysis, allowing practitioners to understand how much their conclusions depend on smoothness assumptions. While the "curse of dimensionality" remains a challenge for distance-based methods, this approach offers a significant step toward more reliable and honest off-policy evaluation in the absence of perfect overlap.
Summary updated