Inverse Propensity Scoring for Off-Policy Evaluation

You have six months of logs from the current recommender and a candidate replacement. Deploying it to find out costs an experiment and some risk. Off-policy evaluation asks whether the logs alone can answer the question, and the answer is yes, under one condition that most logging pipelines fail to meet.

The condition is that the logging policy was stochastic and its action probabilities were recorded. Given that, each logged event \((x_i, a_i, r_i)\) with logging probability \(\pi_0(a_i \mid x_i)\) can be reweighted to estimate the value of a target policy \(\pi\):

The ratio is the importance weight. Actions the new policy favours more than the old one are up-weighted; actions it would rarely take are down-weighted toward zero. The estimator is unbiased whenever the weights are valid.

What the weights are doing

Think of each log entry as a sample from the wrong distribution. IPS corrects the mismatch by asking, for each observed decision, how much more often the target policy would have made it. A logged action taken with probability 0.1 that the new policy would take with probability 0.5 counts five times.

The validity requirement is common support: \(\pi(a\mid x) > 0\) must imply \(\pi_0(a \mid x) > 0\). Any action the new policy would take that the old one never took contributes no data, and its contribution to the value is simply missing. A deterministic logging policy has \(\pi_0 \in \{0,1\}\), so every action it did not take is unobserved and IPS is undefined. This is the failure that kills most attempts: production systems are usually deterministic, or stochastic with unlogged probabilities, and the propensities cannot be reconstructed after the fact.

Variance, and the standard repairs

IPS is unbiased and often unusably noisy. If the target policy differs substantially from the logging policy, a few log entries acquire enormous weights and dominate the estimate. Variance grows with the divergence between the policies, so the estimator is trustworthy exactly when the new policy resembles the old one, which is when you least need it.

Three repairs are standard, and each trades bias for variance.

Weight clipping caps importance weights at some \(M\). It introduces bias proportional to how much mass is clipped, and it is the simplest effective intervention.

Self-normalised IPS divides by the sum of weights rather than by \(n\). The estimator becomes consistent rather than unbiased, and its variance is dramatically lower because a uniformly inflated weight vector cancels between numerator and denominator. It is a near-free improvement and should be the default.

Effective sample size, \((\sum w_i)^2 / \sum w_i^2\), is the diagnostic that decides whether the estimate is worth reporting. A million logged events with an ESS of 300 is a 300-sample estimate, and reporting a tight confidence interval from it is the standard way this analysis goes wrong.

When it breaks

Combinatorial action spaces make weights degenerate. A ranked list of ten items from a catalogue of ten thousand has an astronomically large action space, so \(\pi(a\mid x)/\pi_0(a\mid x)\) is essentially always zero or enormous. Slate-specific estimators exploit structure by assuming the reward decomposes across positions, which is an assumption about the user, not about the algorithm.

Deficient support is invisible in the output. When the new policy prefers actions the logs never contain, IPS silently evaluates only the overlapping part of the policy and returns a number. Nothing in the estimate indicates that the interesting half of the new policy was never assessed.

Non-stationarity breaks the whole premise. Logs from six months ago describe a different user population and a different catalogue. The estimator assumes the reward distribution given context and action is unchanged, and no reweighting corrects a shift in that conditional.

Delayed and partial rewards. IPS assumes \(r_i\) is observed for the logged action. When the reward arrives days later, or only for a subset, the missing-reward mechanism must itself be modelled, and it is frequently correlated with the action taken.