M7-084M7: Retrieval, Ranking & RecSysOffline Evaluation & OPEEasy
⚡Flashcard Drill➔Mastery:
Write the Inverse Propensity Scoring (IPS) Estimator and Explain Its High Variance and Mitigation Strategies
🎯 Active Recall Self-Check (Draft First, Verify After)
Login-free practice tracker: recall core answer, audit pitfalls, and log review status.
Step 1 · Draft your concise answer & assumptions
Step 2 · Check Pitfalls & Follow-up Inquiries
📐 Mathematical Definition
⚡ One-Sentence Core Answer
The Inverse Propensity Scoring (IPS) estimator uses importance weights (pi_new / pi_old) to achieve unbiased offline policy evaluation, but suffers from extreme variance when logging probabilities are tiny; clipping and self-normalization stabilize estimation.
📌 Key Takeaways
- •Importance sampling foundation: Reweights logged rewards by the likelihood ratio between candidate policy pi_new and historical logging policy pi_old.
- •Proof of unbiasedness: Re-weighting cancels out the sampling distribution of the logging policy in expectation.
- •Variance explosion pathology: When the old policy assigns tiny probability to an action that the new policy favors, weights explode, destabilizing the estimator.
- •Mitigation techniques: Weight clipping (Clipped-IPS) and Self-Normalized IPS (SNIPS).
📐 Mathematical Derivations
Mathematical Formulation & Proof: IPS Mechanics & Variance Analysis.
(1) The IPS Estimator Formulation:
Let be logged under policy , where . The IPS estimator for new policy is:
where is the importance weight.
(2) Proof of Unbiasedness:
Assuming Common Support ():
The estimator is mathematically unbiased: .
(3) The Variance Explosion Problem:
The variance of the IPS estimator depends quadratically on importance weights:
If for some sample , the old policy rarely took action (e.g., ) while the new policy takes it frequently (), the weight explodes: . A single observation dominates the entire summation, driving variance to infinity.
(4) Mitigation Variants:
- Clipped IPS: Truncates weights at ceiling (). Bounded variance at the expense of introducing slight asymptotic bias.
- Self-Normalized IPS (SNIPS / Hájek Estimator):
Normalizing by empirical weight sum guarantees the estimate remains strictly bounded within the valid reward range .
(1) The IPS Estimator Formulation:
Let be logged under policy , where . The IPS estimator for new policy is:
where is the importance weight.
(2) Proof of Unbiasedness:
Assuming Common Support ():
The estimator is mathematically unbiased: .
(3) The Variance Explosion Problem:
The variance of the IPS estimator depends quadratically on importance weights:
If for some sample , the old policy rarely took action (e.g., ) while the new policy takes it frequently (), the weight explodes: . A single observation dominates the entire summation, driving variance to infinity.
(4) Mitigation Variants:
- Clipped IPS: Truncates weights at ceiling (). Bounded variance at the expense of introducing slight asymptotic bias.
- Self-Normalized IPS (SNIPS / Hájek Estimator):
Normalizing by empirical weight sum guarantees the estimate remains strictly bounded within the valid reward range .
🏭 Production Trade-offs
In-Depth Analysis & Engineering Trade-offs: ① The Bias-Variance Trade-Off in Clipped IPS—as clipping threshold decreases, variance drops dramatically, but bias increases; setting is standard in industrial counterfactual evaluation. ② SNIPS vs. Standard IPS—standard IPS is unbiased for finite samples, but can output absurd values (e.g., predicting an average CTR of if an explosive weight hits a clicked sample); SNIPS is slightly biased for finite but asymptotically consistent (), strictly bounded in , and empirically exhibits substantially lower Mean Squared Error (MSE). ③ Logging policy design—if the production logging policy is purely uniform random, is constant, eliminating weight variance at the cost of severely degrading user experience during data collection; systems use -greedy logging or softmax logging around the production model to balance user experience with offline evaluation fidelity. ④ Slate recommendation variance explosion—for a slate of 10 items, the importance weight is the product of marginal weights: ; joint weights easily reach , making naive slate-level IPS completely useless; systems apply independent slate IPS or top-k prefix importance sampling. ⑤ Effective Sample Size (ESS)—monitoring alerts engineers when an evaluation is dominated by a few outlier weights. ⑥ Interview takeaway—write out the IPS formula, prove its unbiasedness via the cancellation of , explain the quadratic variance term , and present Clipped IPS and SNIPS as the standard solutions.
⚠️ Common Interview Pitfalls
- ✕Deploying unclipped IPS on datasets where logging probabilities pi_0 are small, allowing a single weight spike to produce nonsensical evaluation estimates.
- ✕Applying single-action IPS directly to multi-item recommendation slates without factoring slate independence, triggering exponential product variance explosion.
- ✕Evaluating IPS on historical logs where the logging policy pi_0 assigned exact zero probability to certain candidate actions, violating the common support condition.
🎯 Interviewer Follow-up Inquiries
- ?Why is the Self-Normalized IPS (SNIPS) estimator guaranteed to output values bounded within the true reward interval [0, 1]?
- ?How does Effective Sample Size (ESS) quantify the statistical reliability of an off-policy importance sampling evaluation?
- ?What independent marginalization techniques permit off-policy evaluation over 10-item recommendation slates without combinatorial variance explosion?
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
📚