Research map / Learning theory and algorithms / Sample complexity
Off-policy Evaluation Beyond Overlap: Sharp Partial Identification Under Smoothness
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Partial identification bounds for off-policy evaluation in the no-overlap region under Lipschitz smoothness of the outcome, with a closed-form solution to the bounding linear program and minimax-rate estimators.
Problem
Off-policy evaluation and policy learning when the logging policy has zero probability on some actions (no overlap), so the off-policy value is not point identified and existing methods rely on well-specified models or overly conservative bounds.
Approach
Assume the conditional outcome mean is L-Lipschitz in the covariates, and bound the no-overlap contribution via a pair of linear programs over sample points; the programs have a closed-form solution because of a no-interaction property (no-overlap points do not sharply bound each other), yielding sharp bounds and minimax-optimal rates.
Key results
- On Yeast, the proposed Lipschitz intervals are 40-50% narrower than Ben-Michael et al. (2021) intervals across sample sizes 500-3000 at L=1.
- With L=1 on the Yahoo! experiment, the intervals are 73.5%, 79.1%, 83.7%, and 91.5% narrower than Manski bounds for T=0.25, 0.3, 0.35, 0.4.
- The closed-form solution computes the bound in O(n^2) instead of the O(n^5) worst-case cost of solving the linear program, and the estimator's MSE rate n^{-2/(d+2)} matches the minimax lower bound up to log factors.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed interval method instead of the Ben-Michael et al. (2021) baseline | Off-policy evaluation · Yeast | average interval width: 1.50, 1.58, 1.50, 1.48, 1.47, 1.43 | Helped |
| Use Lipschitz smoothness L=1 | Proposed partial-identification intervals · Yeast, n=2000 | coverage percentage: 0.03 | Hurt |
| Use Lipschitz smoothness L=3 | Proposed partial-identification intervals · Yeast | coverage percentage: 64.6 -> 96.9 | Helped |
| Use Lipschitz smoothness L=4 | Proposed partial-identification intervals · Yeast | coverage percentage: 68.2 -> 98.0 | Helped |
| Use Lipschitz smoothness L=5 | Proposed partial-identification intervals · Yeast | coverage percentage: 70.6 -> 98.4 | Helped |
| Add the Lipschitz assumption with L=1 to Manski boundedness bounds | Partial identification of policy value · Yahoo! Front Page Today, T=0.25 | interval width reduction: 73.5% | Helped |
| Add the Lipschitz assumption with L=1 to Manski boundedness bounds | Partial identification of policy value · Yahoo! Front Page Today, T=0.3 | interval width reduction: 79.1% | Helped |
| Add the Lipschitz assumption with L=1 to Manski boundedness bounds | Partial identification of policy value · Yahoo! Front Page Today, T=0.35 | interval width reduction: 83.7% | Helped |
| Add the Lipschitz assumption with L=1 to Manski boundedness bounds | Partial identification of policy value · Yahoo! Front Page Today, T=0.4 | interval width reduction: 91.5% | Helped |
Surprising findings
- Adding monotonicity to Lipschitz smoothness breaks the no-interaction property, so the closed form no longer holds.
- For small L (1 or 2) on Yeast, the Lipschitz constraint becomes infeasible at larger sample sizes, so the intervals are undefined and rarely cover the true value.
Limitations
- Bounds are only as useful as the plausibility of the smoothness assumption and chosen covariate metric.
- Rates degrade in high-dimensional covariate settings, and inferential (confidence interval) methods under smoothness are not yet developed.
- Assumption 4.2 (Lipschitz feasibility of the overlap-region fit) can fail for small L, making bounds undefined.
Experimental setup
Datasets: Yeast (UCI) Yahoo! Front Page Today (Webscope)
Benchmarks: Yeast (semi-synthetic OPE) Yahoo! Front Page Today (semi-synthetic OPE)
Metrics: coverage percentage interval width feasibility rate of Assumption 4.2
Baselines: Ben-Michael et al. 2021 Manski bounds pure imputation
Builds on: Manski bounds doubly-robust estimation Xie et al. 2021 pessimistic off-policy learning Ben-Michael et al. 2021 Lipschitz bounds
Closest papers by meaning
- Optimal Off-Policy Evaluation from Multiple Logging Policies (ICML 2021 · similarity 0.89)
- Cross-Validated Off-Policy Evaluation (AAAI 2025 · similarity 0.89)
- Minimax Value Interval for Off-Policy Evaluation and Policy Optimization (NeurIPS 2020 · similarity 0.88)
- Logarithmic Smoothing for Pessimistic Off-Policy Evaluation, Selection and Learning (NeurIPS 2024 · similarity 0.88)
- Beyond the Return: Off-policy Function Estimation under User-specified Error-measuring Distributions (NeurIPS 2022 · similarity 0.88)
- Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Sampling (NeurIPS 2019 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.