🤖 machine learning

Kernel weighted importance sampling for off-policy evaluation in contextual bandits

This paper introduces Kernel-WIS, a novel off-policy evaluation estimator for contextual bandits that leverages offline data to achieve asymptotic consistency and superior empirical performance over existing baselines, particularly in scenarios involving behavior policy misspecification, by effectively combining the boundedness of weighted importance sampling with the linearity of vanilla importance sampling.

Original authors: Joshua Spear, Matthieu Komorowski, Rebecca Pope, Neil J Sebire, Erica E. M. Moodie

Published 2026-07-17

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Joshua Spear, Matthieu Komorowski, Rebecca Pope, Neil J Sebire, Erica E. M. Moodie

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to figure out how a new, untested strategy would perform in a complex game, but you are only allowed to look at a dusty archive of old games played by a different, perhaps clumsy, player. This is the heart of Off-Policy Evaluation (OPE), a crucial challenge in the world of artificial intelligence and machine learning. In these systems, an "agent" (like a robot or a recommendation algorithm) makes decisions based on its current situation (the "context") to get a reward. The problem is that we often want to test a brilliant new strategy (the "target policy") without actually risking real-world consequences by letting it play. Instead, we must predict its success using data collected from an old, existing strategy (the "logging policy").

To make this prediction, scientists use a mathematical trick called Importance Sampling. Think of it like adjusting a recipe: if the old player used a lot of salt (a specific action) and the new player wants to use very little, you have to mathematically "weigh" the old data to see what would have happened if the new player had been in charge. The most common tool for this is called Weighted Importance Sampling (WIS). It's a reliable workhorse that keeps the estimates from going haywire (bounded), but it has a flaw: because it relies on a single, heavy calculation involving all the data points, it can sometimes be jittery and unstable, especially when the old data doesn't match the new strategy very well. The paper you are about to explore dives into this specific problem, asking: Can we build a smarter estimator that keeps the stability of the old method but smooths out the jitter?

The authors of this paper, Joshua Spear and his team, introduce a new method called Kernel-WIS (Kernel-Weighted Importance Sampling). They propose that instead of treating every single piece of old data as a rigid, isolated fact, we can use a "kernel" function to look at the data more softly. Imagine the old data points as stars in the night sky. The traditional method tries to connect every star to every other star to draw a perfect map, which can get messy and wobbly. Kernel-WIS, however, acts like a gentle fog that blurs the stars slightly, grouping nearby ones together to create a smoother, more stable picture of what the new strategy would have achieved.

The researchers tested this idea using a "semi-simulated" setup. They took real-world datasets (like images of handwritten digits or medical records) and artificially created a game where they knew the true answer. They then pitted their new Kernel-WIS against the standard WIS and other older methods under various conditions. The results were fascinating. When the old data was generated by a "perfect" or "oracle" version of the logging policy (a scenario where the data is clean and matches the new strategy well), Kernel-WIS performed just as well as the standard method. However, when the situation got messy—specifically when the logging policy was "miss-specified" (meaning the old data was noisy or the strategy was slightly off)—Kernel-WIS shined. In these tricky, non-perfect scenarios, the new method significantly outperformed the standard WIS, providing more accurate predictions with less error.

But the story isn't a simple "new is always better." The paper reveals a crucial nuance: Kernel-WIS works best when the rewards are clear-cut, like a game where you either win a point or you don't (a "single action" reward). When the researchers tried to apply it to a more complex, "continuous" reward system (where the score is a smooth gradient, like the distance between two numbers), the new method struggled and performed worse than the old one. The authors suggest this is because the "smoothing" effect of the kernel might have been too aggressive for this type of data.

Furthermore, the team discovered that the "bandwidth" of their kernel—a parameter that controls how much the data is blurred or smoothed—was the key to success. They found that using a single, shared bandwidth for all data dimensions worked best, while trying to tune a unique bandwidth for every single feature led to "overfitting," where the model became too sensitive to noise. They also noted that while their method is mathematically proven to be consistent (meaning it gets more accurate as you add more data), the practical challenge of choosing the perfect bandwidth remains a hurdle.

In the end, the paper suggests that Kernel-WIS is a powerful new tool in the AI detective's kit. It doesn't replace the old methods entirely, but it offers a statistically superior alternative when the real world is messy and imperfect. It trades a tiny bit of theoretical perfection for a much more robust performance in the chaotic, non-oracle conditions that real-world applications usually face. The authors conclude that while there is still work to be done to refine how we choose the smoothing parameters, this new approach offers a promising path toward more reliable and safer evaluations of AI strategies.

Technical Summary: Kernel Weighted Importance Sampling for Off-Policy Evaluation in Contextual Bandits

1. Problem Statement

The paper addresses the challenge of Off-Policy Evaluation (OPE) in contextual bandits. The goal is to estimate the expected performance (value) of a target policy, $\pi_e$ , using data collected from a different logging (behavior) policy, $\pi_l$ .

Standard approaches rely on Importance Sampling (IS). The vanilla IS (VIS) estimator is unbiased but suffers from high variance and unboundedness, particularly when the target and logging policies diverge. The Weighted IS (WIS) estimator mitigates variance by normalizing weights, inducing boundedness, but introduces bias and complex dependence structures between samples that are difficult to control theoretically.

The authors identify a gap: existing methods struggle to simultaneously achieve the linearity/independence of VIS and the boundedness/variance reduction of WIS, especially under conditions of behavior policy miss-specification.

2. Methodology

2.1 The Kernel-WIS Estimator

The authors propose Kernel-WIS, a novel estimator designed to unify the benefits of VIS and WIS. It is motivated by the observation that WIS can be viewed as using a conditional control variate, $E[W|S]$ , where $W$ is the importance weight.

The estimator is defined as:
$\hat{J}_{\text{Kernel-WIS}} = \frac{1}{n} \sum_{i=1}^n r_i w_i \left( \frac{\sum_{j=1}^n k_h(s_i, s_j) w_j}{\sum_{j=1}^n k_h(s_i, s_j)} \right)^{-1}$

Where:

$r_i$ is the observed reward.
$w_i = \frac{\pi_e(a_i|s_i)}{\pi_l(a_i|s_i)}$ is the importance weight.
$k_h(s_i, s_j)$ is a kernel function with bandwidth $h$ .
The denominator term acts as a Nadaraya–Watson kernel regressor estimating the conditional expectation $E[W|S=s_i]$ .

2.2 Theoretical Properties

Asymptotic Consistency: The paper proves (Theorem 1) that under mild assumptions (including correct propensity model identification, positivity, and specific bandwidth schedules where $h \to 0$ as $n \to \infty$ ), the Kernel-WIS estimator is asymptotically consistent.
State-WIS Connection: The authors introduce a "State-WIS" estimator (a limit case where $h=0$ ) which uses exact state matching. While State-WIS is shown to be overly biased in continuous spaces, it serves as a theoretical bridge to understand Kernel-WIS.

2.3 Bandwidth Selection

A critical component of the method is selecting the bandwidth $h$ . The authors treat the denominator as a supervised learning problem (predicting $W$ given $S$ ) and employ K-fold cross-validation to minimize the Mean Squared Error (MSE) of the weight prediction.

They derive an analytic gradient for the MSE with respect to the bandwidth (assuming a Radial Basis Function kernel) to facilitate optimization using algorithms like L-BFGS-B.
Experiments utilized multiple initializations for the bandwidth to avoid local minima.

3. Key Contributions

Novel Estimator: Introduction of Kernel-WIS, which combines the boundedness of WIS with the independence properties of VIS through kernel smoothing.
Theoretical Guarantee: Proof of asymptotic consistency for the Kernel-WIS estimator under standard causal inference assumptions.
Empirical Validation: Comprehensive evaluation across 10 datasets (including real-world medical and classification data) demonstrating performance under both oracle (correctly specified) and non-oracle (miss-specified) behavior policies.

4. Experimental Results

The evaluation utilized 10 datasets from OpenML, reformulated as contextual bandit problems. The authors compared Kernel-WIS against VIS, WIS, State-WIS, and CLPD VIS.

4.1 Oracle Behavior Policies

When the logging policy was correctly specified (oracle setting), Kernel-WIS performed (statistically) identically to WIS in most scenarios.
In a minority of cases, Kernel-WIS showed a statistically significant improvement over WIS, particularly as sample sizes varied.

4.2 Non-Oracle (Miss-Specified) Behavior Policies

This is the primary domain of improvement. Under behavior policy miss-specification, Kernel-WIS (statistically) significantly outperformed WIS in the majority of scenarios.
The estimator demonstrated smaller or equivalent approximate variance compared to WIS, effectively controlling the tail behavior that plagues standard WIS.

4.3 Continuous Reward Sensitivity

The authors tested a continuous reward setting (using a VAE to define rewards based on latent space distance).
Result: In this specific setting, Kernel-WIS significantly underperformed compared to WIS. The paper notes this degradation but does not provide a definitive theoretical explanation, leaving it for future work.

4.4 Bandwidth Sensitivity

Experiments compared a Shared Bandwidth (scalar $h$ ) vs. Unique Bandwidths (vector $h$ per dimension).
The Shared Bandwidth approach generally yielded better or equivalent results. Unique bandwidths led to "overfitting" behavior, where some dimensions had extremely large bandwidths and others small, causing the estimator to degenerate toward the biased State-WIS behavior.

5. Significance and Claims

The paper claims that Kernel-WIS offers a practical utility for OPE, particularly in non-oracle settings where behavior policies are miss-specified—a common real-world scenario.

Trade-off: The method allows practitioners to trade a potential (statistically insignificant) drop in performance under perfect oracle conditions for a statistically significant boost in performance under miss-specification.
Boundedness: By combining the bounded nature of WIS with kernel smoothing, the estimator controls the variance and tail behavior better than standard WIS without introducing the extreme bias of State-WIS.
Limitations: The authors acknowledge that Kernel-WIS does not uniformly outperform WIS (especially in continuous reward settings) and that the optimization of the bandwidth remains a practical challenge. The current cross-validation approach is described as "tangential" to the ultimate goal of minimizing the error of the policy value itself, rather than the error of the weight prediction.

The paper concludes that while further research into bandwidth selection (e.g., PAC-Bayes bounds) and extensions to time-dependent settings are needed, Kernel-WIS represents a significant step forward in robust off-policy evaluation.