Overcoming Support Deficiency in Off-Policy Evaluation

43 concepts39 papers1 proposal

In reinforcement learning and contextual bandits, Off-Policy Evaluation (OPE) allows us to answer a crucial counterfactual question: How well would a new target policy ($\pi_e$) perform if we deployed it, using only historical data collected by a logging policy ($\pi_b$)?

This capability is vital in high-stakes domains like healthcare, robotics, and large-scale recommendation systems, where deploying an untested policy online is dangerous or prohibitively expensive. However, standard OPE methods rely on a foundational assumption known as common support or positivity: the logging policy must have a non-zero probability of selecting any action that the target policy might choose.

When the logging policy fails to explore certain actions or states, we encounter the support deficiency problem. Without historical data for these regions, traditional estimators suffer from extreme variance or severe bias.

The Core Failure Mode of Standard Estimators

To understand why support deficiency breaks OPE, consider the classic Inverse Propensity Scoring (IPS) estimator. IPS reweights observed rewards by the ratio of the target policy's probability to the logging policy's probability:

$$w(a|x) = \frac{\pi_e(a|x)}{\pi_b(a|x)}$$

If the target policy wants to take an action $a$ in context $x$ that the logging policy never tried ($\pi_b(a|x) = 0$), the importance weight becomes undefined, and the estimator completely ignores the potential reward of that action. As Alex Irpan et al. point out, OPE metrics fail to accurately predict performance the moment a target policy explores novel or out-of-distribution states. If the evaluation policy assigns a non-zero probability to actions never explored during data collection, Yash Chandak et al. demonstrate that the resulting performance estimates and confidence bounds become invalid.

This limitation is particularly acute when dealing with historical data generated by human experts or deterministic systems. As Ge Gao et al. observe, human experts follow narrow, highly consistent behavioral patterns, leaving vast regions of the state-action space completely unobserved.

The Behavior Policy Paradox

When the logging policy does have full support but is highly concentrated or adaptive, a counterintuitive statistical phenomenon occurs. One might assume that knowing the exact mathematical probabilities of the logging policy ($\pi_b$) is always optimal. However, Yusuke Narita et al. and Josiah Hanna et al. demonstrate that using an estimated behavior policy—computed directly from the observed dataset—yields more accurate counterfactual estimates.

Why does this work? Estimating the behavior policy from the sample data acts as an empirical correction mechanism. It accounts for random sampling error and fluctuations within the historical log, effectively smoothing out variance.

Yet, this optimization has a hard limit. As data collection algorithms become increasingly adaptive or greedy, they stop exploring certain actions entirely. Masahiro Kato et al. and Jeonghwan Lee et al. show that when adaptive algorithms converge toward deterministic behavior, the overlap condition vanishes. This creates severe estimation failures that standard variance-reduction techniques cannot resolve.

Strategy 1: Sharing Support via Action Embeddings

In modern web applications, the action space often consists of millions of items (e.g., products or videos). In this regime, exact support overlap is statistically impossible; the logging policy cannot try every item in every context.

To bypass this exact-match requirement, Yuta Saito et al. introduced Marginalized Inverse Propensity Scoring (MIPS). Instead of calculating propensity scores for discrete actions, MIPS maps actions into a lower-dimensional embedding space (such as product categories or genres).

[Discrete Actions]        [Embedding Space]
Action 1 (Sci-Fi Movie)  -->  [ Vector A ] \
                                            --> Shared Support Region
Action 2 (Space Drama)   -->  [ Vector B ] /

By computing importance weights over these continuous embeddings rather than individual actions, the estimator can generalize from an observed action to an unobserved but structurally similar action. This structural relaxation allows Yuta Saito et al. to drastically reduce both variance and support-deficiency bias in massive action spaces.

Strategy 2: Context Huddling and Aggregation

When data is sparse, another way to manufacture support is to group similar contexts together. If the logging policy never took action $a$ in context $x_1$, but did take action $a$ in a highly similar context $x_2$, we can pool this information.

Daniel Guzman Olivares et al. developed this intuition into an estimator called CHIPS (Context-Huddling Inverse Propensity Score). By clustering contexts into "huddles," the estimator shares data across sparse regions. Instead of requiring strict positivity at every single point in a continuous space, it requires support only over the clustered context regions, preventing the denominator of the importance weight from collapsing to zero.

Strategy 3: Exploiting Natural Randomness and Side Information

When the logging system is completely rigid and deterministic, standard OPE is fundamentally blocked because the logging probabilities are strictly zero for all but one action. Researchers have found two distinct ways to inject or find support in these scenarios:

  1. User-Side Stochasticity: Koichi Tanaka et al. demonstrate that even if a ranking algorithm is completely deterministic, the way users interact with and click on items contains natural randomness. By leveraging this user-side behavioral stochasticity, they construct valid estimators (CIPS and CDR) without requiring the logging algorithm itself to be randomized.
  2. Counterfactual Annotations: In high-stakes environments like medicine, Shengpu Tang et al. propose a semi-offline framework that incorporates human expert annotations. When the logging policy leaves a critical action unobserved, clinicians provide expert assessments of "what would have happened." This side information artificially expands the data support without introducing statistical bias.

Strategy 4: Shifting the Evaluation Objective

If the support gap is too wide to bridge, estimating the absolute value of a target policy becomes impossible. A final class of solutions changes the mathematical objective itself to be more robust.

Instead of trying to calculate an exact point estimate, Nan Jiang et al. frame OPE as a minimax optimization problem. This formulation outputs a robust value interval that bounds the policy's performance, explicitly accounting for the distribution shift caused by missing data coverage.

Alternatively, one can focus entirely on relative performance. Olivier Jeunen introduces $\Delta$-OPE, which shifts the goal from estimating the absolute return of $\pi_e$ to estimating its relative improvement over the current production policy. By evaluating pairs of policies simultaneously, the estimator exploits the positive covariance between them. This cancels out a significant portion of the variance and bias introduced by support deficiencies, providing a safer signal for offline model selection.

Key Foundational Work

Efficient Counterfactual Learning from Bandit Feedback (2019) — contributed 3 concept elements to this direction.
CAB: Continuous Adaptive Blending for Policy Evaluation and Learning (2019) — contributed 1 concept elements to this direction.
Off-Policy Evaluation via Off-Policy Classification (2019) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_support_deficiency_e2fde991,
  title = {support deficiency},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/support-deficiency/rdr_e2fde991e1a1429ba30b8bf6433b7afe},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_support_deficiency_e2fde991_v1,
  title = {support deficiency},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/support-deficiency/rdr_e2fde991e1a1429ba30b8bf6433b7afe/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake