Off-Policy Evaluation for Bandits
Importance sampling, doubly robust estimator, SNIPS, variance control, distribution shift
Online A/B testing every candidate policy is expensive and risky — you need weeks of traffic and accept all the costs of deploying a suboptimal policy. Off-Policy Evaluation (OPE) addresses this: given logged data from a behaviour policy, estimate how well a new policy would perform without deploying it. The fundamental problem is that logged data reflects the behaviour policy's choices — the new policy may want to take very different actions in contexts the behaviour policy rarely encountered. Importance weighting corrects for this mismatch but variance explodes when the policies diverge significantly: a small propensity denominator drives importance weights arbitrarily large, and a few high-weight observations dominate the estimate. The doubly robust estimator is the production standard because it is consistent if either the reward model or the propensity model is correctly specified — two independent chances to be right.
Key points
- Direct method (DM): train a reward model r̂(x, a) on logged data, evaluate as V̂_DM(π_e) = (1/T) Σ_t Σ_a π_e(a|x_t) · r̂(x_t, a). Low variance — the reward model is smooth and the estimate is deterministic. Biased whenever r̂ is wrong in contexts where π_e takes actions the behaviour policy rarely took — and those are exactly the interesting contexts where a better policy diverges from the baseline.
- Importance Sampling (IS): V̂_IS(π_e) = (1/T) Σ_t w_t · r_t where w_t = π_e(a_t | x_t) / π_b(a_t | x_t). Unbiased — in expectation it equals V(π_e). Variance can be enormous when π_e concentrates on actions π_b rarely took: if π_b assigned probability 0.01 to action a but π_e assigns 0.9, the weight is 90. That single observation contributes reward × 90 to the estimate.
- **SNIPS (Self-Normalized IS): $V̂_SNIPS = Σ_t w_t r_t / Σ_t w_t.** Normalising by the sum of weig$ hts substantially reduces variance at the cost of a small bias. Consistent but biased in finite samples. Practically the default when propensities vary significantly across rounds — the effective sample size N_eff = (Σ w_t)² / Σ w_t² is much higher than for raw IS.
- Doubly Robust (DR): V̂_DR = (1/T) Σ_t [Σ_a π_e(a|x_t)·r̂(x_t,a) + w_t (r_t − r̂(x_t, a_t))]. Consistent if either r̂ is correct (then the IS correction w_t(r_t − r̂) averages to zero and DR reduces to DM) or propensities w_t are correct (then DR reduces to IS). Two chances to be right — that is what "doubly robust" means. The production standard.
- **Variance explosion from small propensities: monitor the effective sample size $N_eff = (Σ w_t)² / Σ w_t².** N_eff tells you how many i.i.d. samp$ les the weighted dataset is worth. If N_eff falls below 5-10% of T, a handful of high-weight observations are dominating the estimate and the OPE is unreliable regardless of sample volume. Propensity clipping (cap weights at W_max = 20) reduces variance at the cost of bias — the right tradeoff when N_eff is dangerously low.
- Partial feedback is the fundamental constraint: you only observe r(a_t) — the reward for the action actually taken. You do not observe what would have happened under any other action. Supervised learning has full feedback — labels exist for all classes. OPE must estimate counterfactual rewards from this inherently incomplete information — this is why it is harder than standard evaluation.
- Propensity logging must happen at serve time. If you reconstruct propensities later from a logged policy approximation, reconstruction errors propagate through every IS-based estimator. A neural policy that changed between the serve time and the reconstruction will produce wrong propensity estimates. Log the exact probability π_b(a_t | x_t) at the moment of serving — this is an engineering requirement, not an afterthought.
- Sequential dependencies: if π_b was itself a bandit that adapted over time, the log data is not i.i.d. The context distribution at time t depends on actions taken at times 1,...,t-1. Standard OPE estimators assume i.i.d. rounds and will produce biased estimates. Marginalised importance sampling (MIS) or temporal holdout strategies are required.
- Production pipeline: (1) collect logs from π_b with propensity logging at serve time, (2) train reward model r̂ on logs, (3) compute V̂_DR for each candidate π_e with N_eff monitoring, (4) promote top candidates to online A/B test. OPE enables evaluating 100 policies in the time it takes to run one A/B test — the value is in the rapid filtering.
The doubly robust estimator is the production standard because it is consistent if either the reward model or the propensities are correct — two independent chances to be right. Log propensities at serve time, not reconstructed later: reconstruction errors from a changed policy break all IS-based estimators. Monitor $N_eff = (Σw)²/(Σw²) continuously — if it falls below 5-10%$ of sample size, a handful of high-weight observations dominate the estimate and the OPE is unreliable regardless of how much data you have.
Recap
- OPE goal: estimate a new policy's value from logged behaviour-policy data, without deploying it.
- Direct method (DM): train r̂(x,a); low variance, biased where π_e diverges from π_b — exactly the interesting contexts.
- Importance sampling (IS): reweight by w_t = π_e/π_b; unbiased but variance explodes when policies diverge.
- Doubly robust (DR): $V̂_DR = (1/T) Σ_t [Σ_a π_e(a|x_t)·r̂(x_t,a) + w_t(r_t − r̂)]$; consistent if either r̂ or propensities are right — the production standard.
- Monitor N_eff = (Σw)²/Σw²: below 5-10% of T → a few high-weight rows dominate, OPE unreliable; clip weights to trade bias for variance.
- Log propensities at serve time: reconstructing later breaks every IS estimator.
- Partial feedback: you only see the reward of the action taken — counterfactual estimation is what makes OPE hard.
Check your understanding
Q1. You have 1M logged impressions from a random policy (uniform over K=10 arms) and want to evaluate a new deterministic policy that always chooses arm 3. Compute the importance weights and analyze the variance.
- A) IS weights are w_t = 10 exactly when a_t = arm3, and 0 otherwise, since the deterministic and uniform propensities differ by that factor
- B) IS weights are w_t = 1 for all rounds, because the deterministic policy and the uniform logging policy share equal propensity on arm 3
- C) IS weights are fundamentally undefined here, since you cannot ever evaluate a deterministic policy using a purely uniform logging policy
- D) IS weights are w_t = K = 10 applied uniformly to every round regardless of arm, giving variance that grows proportionally with K squared
Q2. Why is the doubly robust estimator called "doubly robust"? Construct a simple example where one model is wrong but DR is still consistent.
- A) DR earns the name because it draws on two entirely separate datasets — one purely for the reward model, one purely for propensity estimation
- B) DR is doubly robust simply because it reduces estimator variance by roughly a factor of two when compared against plain importance sampling
- C) DR is consistent if either r̂ or the propensity model is correct — two independent chances to be right, canceling either error term
- D) DR earns the name because it applies importance sampling twice over — once to correct for context shift and once again for action shift
Q3. Spotify wants to evaluate 50 new playlist ranking policies before A/B testing. Select the two true failure modes you must monitor in the OPE pipeline.
- A) Propensity degeneracy — effective sample size N_eff dropping below roughly 5% of T means a handful of rows dominate every V̂_DR estimate
- B) Support violations — π_e assigning real probability mass to (context, arm) pairs that the logging policy π_b never actually covered in logs
- C) OPE is only ever valid for policies extremely similar to the logging policy — all 50 candidates must sit within a fixed KL threshold of π_b
- D) Running a single shared reward model with plain DM is entirely sufficient here, since Spotify's playlist reward model is inherently well calibrated
Try it interactively
ML Systems Lab is a free interview-prep platform for ML engineers — work through the full interactive module, quizzes, and drills.
Open ML Systems Lab →