Calibrated Intervals for Off-Policy Evaluation When the Log Never Tried the Action

Companies and hospitals often want to know how a new decision rule would perform before deploying it. The standard way to find out is off-policy evaluation: reweight historical logs, collected under an old rule, so that they approximate the new rule. This breaks when the new rule picks actions the old one never tried, a situation called support deficiency. Recent estimators get around it by borrowing information from similar actions. They guess the reward of an untried item from the rewards of items with similar features. These methods return a single number, or a bootstrap interval that reflects only sampling noise. That makes them overconfident in the plainest sense. The reported uncertainty ignores the largest source of error, which is whether the extrapolation to untried actions is right. Nothing in the reported interval grows as more of the new rule's probability falls on untried actions.

We propose to measure that extrapolation error from the log itself. The log contains many actions that were tried. We repeatedly pretend that a subset of them was never tried, refit the extrapolator without them, and record how wrong its policy-level guess is on the hidden actions. The spread of these errors, reweighted so the hidden actions resemble the truly untried ones, gives a distribution-free correction to add to the interval. The deliverable is an interval for the new policy's value that keeps its stated coverage as support deficiency rises from zero to 90%. We will check this on the Open Bandit Dataset, where the true value of the target policy is known.

Core Claim

Write the target policy's value as $V(\pi_e) = V_S + V_U$. Here $V_S$ is the contribution of actions the logging policy $\pi_b$ supports, and $V_U = \mathbb{E}_x \sum_{a \in U(x)} \pi_e(a \mid x)\, q(x,a)$ is the contribution of the unsupported set $U(x)$, where $q(x,a)$ is the expected reward. The data identify $V_S$, and standard importance weighting gives it an honest interval. The data do not identify $V_U$. Any estimate of it rests on an extrapolation assumption, such as linearity in action features, smoothness under cosine similarity, or the "no direct effect" condition behind embedding estimators.

Our claim has two parts. First, the intervals that current deficient-support estimators report are miscalibrated, and their shortfall in coverage grows with the unsupported mass $m_U = \mathbb{E}_x \sum_{a\in U(x)} \pi_e(a\mid x)$. Second, the extrapolation error of $\hat V_U$ can be calibrated with pseudo-deficiency replicates: supported actions that are hidden, predicted, and scored. Weighting those replicates by a model of which actions tend to go unsupported gives intervals of the form

$$ \hat V_S + \hat V_U \;\pm\; \big(z\,\hat\sigma_S + \hat Q_{1-\alpha}\big), $$

where $\hat\sigma_S$ is the usual standard error of the supported part, $z$ the corresponding normal quantile, and $\hat Q_{1-\alpha}$ the weighted $(1-\alpha)$ quantile of absolute policy-level extrapolation errors across replicates, each scaled to the actual unsupported mass. Coverage is guaranteed when the hidden actions are exchangeable with the truly unsupported ones after reweighting. This mirrors how weighted conformal prediction handles covariate shift. The assumption is testable, and we test where it breaks.

Relation to Prior Work

Three papers motivate the proposal by showing that calibration governs whether importance weighting survives limited overlap. Behaviour Policy Estimation in Off-Policy Policy Evaluation: Calibration Matters shows that neural behavior models are overconfident in sparse sepsis states. It also shows that k-nearest-neighbor estimates, being better calibrated, cut evaluation error. Calibrated and Conformal Propensity Scores for Causal Effect Estimation and Stabilized Inverse Probability Weighting via Isotonic Calibration recalibrate propensities, or inverse propensities, for binary treatments. All three calibrate the propensity, which only helps where the propensity is positive. We calibrate the extrapolated reward on the region where the propensity is exactly zero, which none of them can reach.

Two papers supply the methods we reuse. Off-Policy Evaluation with Deficient Support Using Side Information introduces the PseudoInverse estimator (reward linear in action features) and the Similarity estimator (cosine-kernel imputation). It shows their error stays flat on the Open Bandit Dataset as up to 90% of actions are removed, while plain importance weighting explodes. Off-Policy Evaluation for Large Action Spaces via Embeddings introduces marginalized importance weighting over action embeddings. These estimators serve as our extrapolators $\hat V_U$. What they lack is any interval that accounts for their own modeling assumptions. Clustering Context in Off-Policy Evaluation makes the same point from the context side: its V-shaped error curve over cluster counts shows that extrapolation assumptions fail silently.

Two papers constrain the design. Conformal Prediction Beyond the Horizon achieves 90% coverage for policy evaluation under policy shift, but it assumes overlap. We borrow its weighted-conformal logic and move exchangeability from trajectories to actions. Minimax Value Interval for Off-Policy Evaluation and Policy Optimization treats non-exploratory data as misspecification and returns bounds that can reverse when both of its function classes are misspecified. Our intervals are data-calibrated rather than worst-case over a function class, so they cannot reverse. The trade-off is that their validity depends on the exchangeability assumption instead.

Research Program

The first step is diagnostic. On the Open Bandit Dataset, logs from the uniform Random policy are used to evaluate the Bernoulli Thompson Sampling policy, whose true value comes from its own on-policy logs. We impose deficiency by removing actions from the logging support, following the side-information paper's protocol. We then plot empirical coverage of each estimator's nominal 90% and 95% intervals against $m_U$. We expect undercoverage to grow roughly linearly in $m_U$, because the unmodeled bias is $m_U$ times the average per-action extrapolation error. Such a plot would make overconfidence concrete for this problem.

The second step builds the replicates. For each replicate $r$, we hide a set $H_r$ of supported actions. The draw uses a missingness model: a classifier on action features and context that predicts whether an action is unsupported. This way, hidden sets look like real gaps. For example, if the logger never showed men's items, replicates preferentially hide items with men's-like features. We then refit the extrapolator without $H_r$. Next we compute its $\pi_e$-weighted value on $H_r$ and compare against a doubly robust estimate of the same quantity from the log. Because that reference is itself noisy, we subtract its estimated variance from the empirical error spread, clipping the result at zero. Finally, each replicate's error is rescaled by the ratio of true unsupported mass to hidden mass, and its conformal weight is the missingness model's likelihood ratio.

The third step stresses exchangeability. In one condition actions are removed at random. In another, removal is driven by features, such as dropping whole categories or gender groups. In a third, the removed items are the ones a greedy logger would avoid, meaning items with low click rates. This last condition is the adversarial case, because the untried actions differ in reward from anything the replicates can show. There we expect, and will report, residual undercoverage, together with how much of it the missingness weighting recovers.

Baselines

The naive reference is the Similarity or PseudoInverse estimator with a nonparametric bootstrap interval, as practitioners would use it today. It is the natural "do nothing" choice because it is exactly what the side-information paper's estimators produce with standard resampling. It runs on the same logs, features and deficiency masks as our method, so the only difference is how the interval is built. Beating it means reaching nominal coverage at deficiency rates where it undercovers.

The strongest identified-part competitor is doubly robust estimation with optimistic shrinkage. A Large-scale Open Dataset for Bandit Algorithms reports it reaching RMSE 0.316 on the "All" campaign at $n=300{,}000$, a 34% improvement over plain doubly robust estimation. That number is under full support. For coverage under imposed deficiency on this dataset we found no reported result on Lacuna, so we will run this estimator with its bootstrap interval and gradient-boosted reward model at matched sample sizes. For the extrapolators themselves, the side-information paper reports that the cosine Similarity estimator is most robust at 60–90% deficiency and PseudoInverse is best at lower rates, but it gives no printed numbers. We will reproduce both and use whichever is stronger at each deficiency level.

The worst-case reference is partial identification: bound $V_U$ by $m_U$ times the reward range. This interval is always valid. The minimax interval of Jiang and Huang is the structured alternative. We run it with the same reward and weight function classes as our extrapolator. We count it as beaten if our intervals are narrower at equal or better coverage, or if they cover where it reverses.

Two ablations isolate the key ingredient. One draws replicates uniformly at random, removing the missingness weighting. The other replaces replicate calibration with the reward model's own predictive spread from a five-member ensemble, which shows whether calibrating on hidden actions is doing the work. All methods share one tuning budget, and the conformal level $\alpha$ is never tuned on target-policy ground truth.

Why not just…?

Why not just bootstrap the Similarity estimator? The bootstrap resamples logged rounds. It therefore measures sampling variance of the fit, not the error of the smoothness assumption itself. With 26 million impressions that variance shrinks toward zero while the extrapolation bias stays fixed, so the interval becomes more confidently wrong as data grows. The diagnostic in step one tests this directly. If bootstrap coverage turns out adequate across deficiency levels, our main claim is false and we will say so.

Why not just use worst-case bounds? They are valid, and they are the honest fallback. But on click data with small reward rates, bounding the unsupported mass by the full reward range produces intervals far wider than the effect sizes practitioners compare. The ShareChat test in Δ-OPE involved relative gains of 0.14–0.32%. Our method only earns its place if it is much narrower while still covering. If it is not narrower than worst-case bounds in the structured-removal condition, we will conclude that data-driven calibration gains nothing where it matters most.

Why not just take uncertainty from a Bayesian or ensemble reward model? This is the most serious threat. Ensembles can disagree off-support, and CHIPS already offers a Bayesian cluster variant. The literature in the file, however, shows that learned models tend to be overconfident exactly where data are sparse. The neural sepsis model's calibration error in severe states was 0.426, against 0.199 for nearest neighbors, and Calibrated Language Model Fine-Tuning for In- and Out-of-Distribution Data needed explicit off-manifold regularization to fix similar behavior. The ensemble ablation settles this. If ensemble spread matches our coverage and width, the replicate machinery is unnecessary.

Why not just clip the weights? Clipping caps large finite weights. At zero support the weight is undefined, so the unsupported actions contribute nothing to the estimate. The side-information paper shows clipped importance weighting's error exploding toward 90% deficiency. We include it only in the diagnostic plot.

Proposed Experiments

The main experiment evaluates Thompson Sampling from Random-policy logs on all three Open Bandit campaigns. We sweep deficiency from 0% to 90% under random, feature-structured and reward-correlated removal, with sample sizes from 10,000 to 300,000 and 100 seeds per cell. The metrics are empirical coverage at 90% and 95%, mean interval width relative to the worst-case bound, and RMSE of the point estimate.

A synthetic Open Bandit Pipeline study scales the action space to 5,000 items. This matches the regime where embedding-based weighting reported a 12x MSE gain over importance weighting. Here we can control how strongly the no-direct-effect assumption is violated, which lets us trace coverage as a function of violation strength.

The decisive checks are three. Our intervals should hold nominal coverage, within Monte Carlo error, under random and feature-structured removal at every deficiency level. Every bootstrap baseline should fall below nominal as $m_U$ grows. And our intervals should be at least a factor of two narrower than worst-case bounds at 60% deficiency or more. Failing the first check under feature-structured removal would falsify the claim that missingness weighting restores exchangeability. Failing the third would mean the method is a costly route back to worst-case bounds.