Off-Policy Evaluation: Why Importance Sampling Gives Unbiased Estimates You Cannot Trust

You have logs from a recommendation system that served one ranking policy, and you want to know how a different policy would have performed. You cannot run the new policy yet. You have no A/B test. All you have is data collected under a policy you are trying to replace.

This is the off-policy evaluation problem, and it sits underneath almost every offline decision in reinforcement learning: recommender systems, ad placement, clinical treatment policies, robotics. The theory says the problem is solved. Importance sampling gives an unbiased estimator of the new policy's value. The practice says the estimator is often useless. The gap between those two statements is one of the most instructive in all of machine learning, because it is a gap between unbiasedness and usefulness.

The setup

A behaviour policy $μ$ collected the data. A target policy $π$ is the one we want to evaluate. Each logged trajectory is a sequence of states, actions and rewards $(s_{0}, a_{0}, r_{0}, s_{1}, a_{1}, r_{1}, \dots)$ , with actions drawn from $μ$ and rewards drawn from the environment.

The value of a policy is its expected return:

V (π) = E_{π} [t = 0 \sum H - 1 γ^{t} r_{t}]

where $H$ is the horizon and $γ$ is the discount factor. The data give us samples from $μ$ , not from $π$ . The naive move, averaging the returns in the log, estimates $V (μ)$ , which is the value of the old policy. That is the wrong number, and in a system that was already optimised, it is usually an optimistic one.

Importance sampling: the correction

Importance sampling reweights each trajectory by the ratio of the probability of that trajectory under the target policy to its probability under the behaviour policy. For a trajectory $τ$ of length $H$ :

ρ (τ) = t = 0 \prod H - 1 \frac{π ( a _{t} ∣ s _{t} )}{μ ( a _{t} ∣ s _{t} )}

The ordinary importance sampling estimator is then:

V^I S (π) = \frac{1}{n} \sum i = 1^{n} ρ (τ_{i}) G (τ_{i})

where $G (τ_{i})$ is the return of trajectory $i$ . Under one condition, this estimator is unbiased: the behaviour policy must have support everywhere the target policy does. Wherever $π (a ∣ s) > 0$ , we need $μ (a ∣ s) > 0$ . If the new policy sometimes takes an action the old policy never took, the data contain no information about that action, and no reweighting can conjure it.

That unbiasedness is real, and it is also nearly irrelevant in practice. The problem is variance.

Why the variance explodes

The importance weight is a product of $H$ ratios. Suppose at each step the target policy is only slightly different from the behaviour policy, say each ratio is 1.2 on average. Over a horizon of 50 steps, the weight is roughly $1. 2^{50} \approx 9100$ . If some ratios are below 1 and others above, the product is a random variable whose distribution is heavy-tailed: most trajectories get tiny weights and a handful get enormous ones.

The variance of the estimator grows roughly exponentially in the horizon. A formal way to see it: the second moment of the weight involves the product of squared ratios, so the variance contains a term that scales like the exponential of the horizon times the per-step divergence between the two policies. For long horizons, or for policies that differ much at all, the estimator is dominated by one or two trajectories. Your estimate of the new policy's value is effectively the return of the single luckiest logged trajectory, multiplied by a huge weight.

This is the curse of horizon. It is why off-policy evaluation with plain importance sampling works for contextual bandits, where $H = 1$ and the weight is a single ratio, and falls apart for the sequential problems where you most want it.

A concrete illustration: a bandit with one step, behaviour policy uniform over 10 actions, target policy putting 90 percent of its mass on one action. The importance weight is 9 when the logged action matches the target's favourite and about 0.11 otherwise. That is manageable. Now make it a 20-step problem with the same per-step mismatch. The weights now span many orders of magnitude, and a few thousand logged trajectories are nowhere near enough.

Weighted importance sampling: trading a little bias for a lot of variance

The first standard fix is to self-normalise. Weighted importance sampling divides by the sum of the weights instead of by $n$ :

V^W I S (π) = \frac{\sum i = 1 ^{n} ρ ( τ _{i} ) G ( τ _{i} )}{\sum _{i = 1 n} ρ ( τ _{i} )}

This estimator is biased, but the bias shrinks as $n$ grows, and the variance is usually far smaller. Intuitively, the normalisation cancels the common scale of the weights: if all weights are inflated by the same factor, the estimate does not move. In practice, weighted importance sampling is almost always the better choice, and the small asymptotic bias is a price worth paying.

But self-normalisation does not cure the curse of horizon. It dampens it. The estimator is still dominated by the largest weights when the horizon is long.

Per-decision importance sampling: use the structure of the return

The return is a sum over time steps, and the reward at time $t$ only depends on the actions taken up to time $t$ . There is no reason to reweight the reward at step 3 by the action ratio at step 40. Per-decision importance sampling exploits this:

V^P D I S (π) = \frac{1}{n} \sum i = 1^{n} t = 0 \sum H - 1 γ^{t} ρ_{0 : t (i)} r_{t (i)}

where $ρ_{0 : t (i)} = \prod_{s = 0 t} \frac{π ( a _{s} ∣ s _{s} )}{μ ( a _{s} ∣ s _{s} )}$ is the partial product up to time $t$ . Early rewards are reweighted by short products, which have far smaller variance. This is still unbiased under the same support condition, and it is a strict improvement over ordinary importance sampling in variance terms.

Per-decision importance sampling is the right default for trajectory data. It is also the point where the purely model-free story starts to run out of road. Even partial products grow exponentially with $t$ , so late-horizon rewards are still estimated with enormous variance.

Clipping: the bias-variance knob you actually control

When weights explode, practitioners clip them:

ρ_{c l i pp e d} = min (ρ, c)

for some cap $c$ , often chosen as a quantile of the observed weights. Clipping introduces bias, because it downweights exactly the trajectories the target policy would have produced most often. But it bounds the variance, and in finite samples the mean squared error usually improves dramatically.

The cap is a bias-variance tradeoff dial, and there is no universally right setting. A useful diagnostic is the effective sample size:

ESS = \frac{( \sum _{i} ρ _{i} ) ^{2}}{\sum _{i} ρ _{i 2}}

If your effective sample size is 12 out of 10,000 logged trajectories, your estimate is resting on 12 trajectories, whatever the nominal sample size says. Reporting the effective sample size alongside any importance sampling estimate is a basic honesty check, and it is the first number to look at when an offline evaluation looks too good.

A minimal example

The mechanics are simple enough to see in a few lines of Python. Here is a one-step bandit version, where the variance problem is already visible:

import numpy as np rng = np.random.default_rng(0) n_actions = 10 true_reward = np.linspace(0.1, 1.0, n_actions) # Behaviour policy: uniform. Target policy: mostly action 9. mu = np.full(n_actions, 1.0 / n_actions) pi = np.full(n_actions, 0.01) pi[9] = 0.91 actions = rng.choice(n_actions, size=2000, p=mu) rewards = true_reward[actions] + rng.normal(0, 0.1, size=2000) weights = pi[actions] / mu[actions] v_is = np.mean(weights * rewards) v_wis = np.sum(weights * rewards) / np.sum(weights) v_true = np.dot(pi, true_reward) ess = weights.sum() ** 2 / np.sum(weights ** 2) print(f"True value: {v_true:.3f}") print(f"Ordinary IS: {v_is:.3f}") printSource：https://dev.to/umeshtharukaofficial/off-policy-evaluation-why-importance-sampling-gives-unbiased-estimates-you-cannot-trust-2na9My favorites

PreviousNHSの630億円AIと、僕らがQuestで作った「遊べる弱視訓練」の距離感 #医療DX #弱視治療 #VR療法 #AmblyoPunch #デジタルヘルスNext5 more public-data tools for AI agents: building permits, new FL/TX businesses, domain WHOIS and Wayback snapshots

`Related posts`


Securing an EOL Host Against PHP2Shell
This guide details how to decouple the PHP runtime from your host operating system. By shifting execution into an isolat
0dev.to
A memory that curates itself: from grep to BM25, and the warm layer we built a week later
How an agent's operational memory fits in ~110 KB of prompt plus a wiki of 36 file-cards — on a 2 GB, IPv6-only cloud VM
0dev.to
Syncing Shopify Orders Back to Inventory to Prevent Oversell
--> Syncing Shopify Orders Back to Inventory to Prevent Oversell When you run a reverse-Taobao style storefront that pus
0dev.to
5 more public-data tools for AI agents: building permits, new FL/TX businesses, domain WHOIS and Wayback snapshots
Disclosure: I build these tools, and I used AI to help write them and this post. Five more Panda Federation tools went p
0dev.to
When Open Firmware Meets Open Vision: A Builder's Note on Polyend and Amblyotube Polyend open-sourcing the Tracker firmware…
When Open Firmware Meets Open Vision: A Builder's Note on Polyend and Amblyotube Polyend open-sourcing the Tracker firmw
0dev.to
The Bird Flu Death That Made Me Rethink How We Visualize Viral Proteins in VR
The Bird Flu Death That Made Me Rethink How We Visualize Viral Proteins in VR I read the headline on a quiet Tuesday, co
0dev.to