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

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 (s0​,a0​,r0​,s1​,a1​,r1​,…) , with actions drawn from μ and rewards drawn from the environment. The value of a policy is its expected return: V(π)=Eπ​[t=0∑H−1​γtrt​] 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∏H−1​μ(at​∣st​)π(at​∣st​)​ The ordinary importance sampling estimator is then: V^IS(π)=n1​∑i=1nρ(τ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.250≈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^WIS(π)=∑i=1n​ρ(τi​)∑i=1nρ(τi​)G(τ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^PDIS(π)=n1​∑i=1nt=0∑H−1​γtρ0:t(i)​rt(i)​ where ρ0:t(i)​=∏s=0t​μ(as​∣ss​)π(as​∣ss​)​ 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: ρclipped​=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=∑i​ρi2​(∑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}") print(f"Weighted IS: {v_wis:.3f}") print(f"Effective sample size: {ess:.0f} of 2000") Run this and you will see ordinary importance sampling swing widely across seeds while weighted importance sampling stays close to the truth, with an effective sample size far below 2000. Stretch the same idea to a 20-step trajectory and both estimators degrade; that is the curse of horizon in miniature. When importance sampling is not enough There are two directions out of the variance trap. The first is to bring in a model. Doubly robust estimators combine an importance-weighted correction with a learned model of the reward or value function, so the estimator is accurate if either the model or the behaviour policy is right, and the variance drops because the model absorbs most of the signal. The second is to change the estimand: instead of evaluating the exact target policy, evaluate a policy constrained to stay close to the behaviour policy, which is what conservative offline reinforcement learning does. Both are admissions that pure importance sampling does not scale to long horizons and distant policies. Fitted Q evaluation is the other main family: learn a Q-function from the logged data by regression, then read off the value of the target policy from the learned Q. It has no importance weights at all, so no variance explosion, but it inherits the bias of the function approximator and the distribution shift between the logged data and the target policy's state distribution. In practice, the choice between importance sampling methods and fitted Q evaluation is a choice between variance and bias, and the honest answer is usually to compute both and worry when they disagree. Limitations and common pitfalls Support failure is silent. If the target policy takes an action the behaviour policy never took, importance sampling cannot detect it from the weights, because those trajectories never appear in the log. Check support explicitly before trusting any estimate. Unbiased does not mean accurate. An unbiased estimator with variance larger than the signal is worse than a biased estimator with small variance. Judge estimators by mean squared error, not by unbiasedness alone. The horizon is the enemy. Every additional step multiplies the variance. For long-horizon problems, per-decision weights and doubly robust corrections are not optional refinements; they are the difference between an estimate and noise. Clipping hides the problem it solves. A clipped estimator with a small cap is mostly estimating the behaviour policy's value with a tilt. If the cap binds on a large fraction of trajectories, say so. Offline evaluation is not a substitute for an online test. It is a filter for bad policies, not a proof that a good-looking policy is good. The policies that look best offline are exactly the ones most likely to be overestimated, because the estimator's errors correlate with the policy's apparent advantage. This is the offline version of the winner's curse, and it bites hardest precisely when the evaluation is used to select between many candidate policies. The takeaway Importance sampling is the cleanest idea in off-policy evaluation: reweight what you saw by how much more likely the new policy would have been to do it, and you get an unbiased estimate of a policy you never ran. The maths is correct and the estimator is, in finite samples, often unusable. The variance grows exponentially with the horizon, the effective sample size collapses, and a handful of trajectories end up deciding the answer. Per-decision weights, self-normalisation, and clipping each buy back some ground, and doubly robust methods buy back more, but none of them repeal the underlying tradeoff. Off-policy evaluation is a tool for ruling policies out, not for crowning them, and the most important number in any offline evaluation report is not the estimated value. It is the effective sample size. Connect with me on LinkedIn: linkedin.com/in/umeshtharukaofficial