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
Next: M7-085 →
📐 Mathematical Definition
V^IPS=1n∑i=1nπnew(ai∣xi)πold(ai∣xi)ri\hat V_{\text{IPS}}=\frac1n\sum_{i=1}^n\frac{\pi_{\text{new}}(a_i|x_i)}{\pi_{\text{old}}(a_i|x_i)}r_i
⚡ 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 D={(xi,ai,ri,pi)}i=1N\mathcal{D} = \{(x_i, a_i, r_i, p_i)\}_{i=1}^N be logged under policy π0\pi_0, where pi=π0(ai∣xi)p_i = \pi_0(a_i \mid x_i). The IPS estimator for new policy π1\pi_1 is:
V^IPS(π1)=1N∑i=1Nπ1(ai∣xi)π0(ai∣xi)⋅ri=1N∑i=1Nwi⋅ri\hat{V}_{\text{IPS}}(\pi_1) = \frac{1}{N} \sum_{i=1}^N \frac{\pi_1(a_i \mid x_i)}{\pi_0(a_i \mid x_i)} \cdot r_i = \frac{1}{N} \sum_{i=1}^N w_i \cdot r_i
where wi=π1(ai∣xi)π0(ai∣xi)w_i = \frac{\pi_1(a_i \mid x_i)}{\pi_0(a_i \mid x_i)} is the importance weight.

(2) Proof of Unbiasedness:
Assuming Common Support (π1(a∣x)>0  ⟹  π0(a∣x)>0\pi_1(a \mid x) > 0 \implies \pi_0(a \mid x) > 0):
ED[V^IPS(π1)]=Ex∼P(x)Ea∼π0(a∣x)[π1(a∣x)π0(a∣x)r(x,a)]\mathbb{E}_{\mathcal{D}}[\hat{V}_{\text{IPS}}(\pi_1)] = \mathbb{E}_{x \sim P(x)} \mathbb{E}_{a \sim \pi_0(a \mid x)} \left[ \frac{\pi_1(a \mid x)}{\pi_0(a \mid x)} r(x, a) \right]=∫P(x)(∑a∈Aπ0(a∣x)π1(a∣x)π0(a∣x)r(x,a))dx=∫P(x)(∑a∈Aπ1(a∣x)r(x,a))dx=V(π1)= \int P(x) \left( \sum_{a \in \mathcal{A}} \pi_0(a \mid x) \frac{\pi_1(a \mid x)}{\pi_0(a \mid x)} r(x, a) \right) dx = \int P(x) \left( \sum_{a \in \mathcal{A}} \pi_1(a \mid x) r(x, a) \right) dx = V(\pi_1)
The estimator is mathematically unbiased: E[V^IPS(π1)]=V(π1)\mathbb{E}[\hat{V}_{\text{IPS}}(\pi_1)] = V(\pi_1).

(3) The Variance Explosion Problem:
The variance of the IPS estimator depends quadratically on importance weights:
Var(V^IPS)=1NEπ0[(π1(a∣x)π0(a∣x))2r2(x,a)]−V(π1)2N\text{Var}(\hat{V}_{\text{IPS}}) = \frac{1}{N} \mathbb{E}_{\pi_0}\left[ \left( \frac{\pi_1(a \mid x)}{\pi_0(a \mid x)} \right)^2 r^2(x, a) \right] - \frac{V(\pi_1)^2}{N}
If for some sample ii, the old policy rarely took action aia_i (e.g., π0=0.001\pi_0 = 0.001) while the new policy takes it frequently (π1=0.50\pi_1 = 0.50), the weight explodes: wi=0.500.001=500w_i = \frac{0.50}{0.001} = 500. A single observation dominates the entire summation, driving variance to infinity.

(4) Mitigation Variants:
- Clipped IPS: Truncates weights at ceiling MM (wiclip=min⁡(wi,M)w_i^{\text{clip}} = \min(w_i, M)). Bounded variance at the expense of introducing slight asymptotic bias.
- Self-Normalized IPS (SNIPS / Hájek Estimator):
V^SNIPS(π1)=∑i=1Nwi⋅ri∑i=1Nwi\hat{V}_{\text{SNIPS}}(\pi_1) = \frac{\sum_{i=1}^N w_i \cdot r_i}{\sum_{i=1}^N w_i}
Normalizing by empirical weight sum guarantees the estimate remains strictly bounded within the valid reward range [0,1][0, 1].

🏭 Production Trade-offs

In-Depth Analysis & Engineering Trade-offs: ① The Bias-Variance Trade-Off in Clipped IPS—as clipping threshold MM decreases, variance drops dramatically, but bias increases; setting M∈[10,50]M \in [10, 50] 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 140%140\% if an explosive weight hits a clicked sample); SNIPS is slightly biased for finite NN but asymptotically consistent (N→∞N \to \infty), strictly bounded in [0,1][0, 1], and empirically exhibits substantially lower Mean Squared Error (MSE). ③ Logging policy design—if the production logging policy π0\pi_0 is purely uniform random, pi=1/Kp_i = 1/K is constant, eliminating weight variance at the cost of severely degrading user experience during data collection; systems use ϵ\epsilon-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: W=∏k=110wkW = \prod_{k=1}^{10} w_k; joint weights easily reach 101510^{15}, making naive slate-level IPS completely useless; systems apply independent slate IPS or top-k prefix importance sampling. ⑤ Effective Sample Size (ESS)—monitoring ESS=(∑wi)2∑wi2\text{ESS} = \frac{(\sum w_i)^2}{\sum w_i^2} 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 π0(a∣x)\pi_0(a \mid x), explain the quadratic variance term wi2w_i^2, 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.
🎯 Drill This Card Now➔
📚

Associated Knowledge Base Guides & Mindmaps

← PreviousM7-083: Explain Why Offline Evaluation Cannot Naively Use Historical Logged Data to Evaluate New Policies📋 Back to BankNext →M7-085: Explain the Doubly Robust (DR) Estimator and Its Dual Robustness Property in Off-Policy Evaluation