M7-090M7: Retrieval, Ranking & RecSysOffline Evaluation & OPEHard
⚡Flashcard Drill➔Mastery:
Explain Off-Policy Evaluation for Sequential Decision-Making: Multi-Step Trajectory IPS and Doubly Robust
🎯 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
In multi-step sequential recommendation, actions influence future states; Off-Policy Evaluation requires trajectory-level importance weighting where weights multiply across time steps, causing variance to grow exponentially with horizon length (the curse of horizon).
📌 Key Takeaways
- •Sequential state transition dependency: Unlike single-step bandits, an action at time t alters user state s_{t+1}, affecting all downstream rewards across the session.
- •Trajectory-level importance sampling: Multiplies step-wise importance weights: W_{1:T} = prod_{t=1}^T (pi_new(a_t | s_t) / pi_0(a_t | s_t)).
- •The curse of horizon: Trajectory weights exhibit exponential variance explosion as sequence length T increases (e.g., T > 10).
- •Mitigation architectures: Per-Decision IPS, Marginalized Importance Sampling (MIS), and Sequential Doubly Robust (SDR) with recursive value function estimators.
📐 Mathematical Derivations
Mathematical Formulation: Sequential OPE & Curse of Horizon.
(1) The Sequential Markov Decision Process (MDP) Framework:
Let user session trajectory of length be .
The probability of trajectory under policy is:
The cumulative trajectory return is .
(2) Full Trajectory Importance Sampling:
Notice that transition dynamics and initial state distribution are identical across policies and cancel out in the likelihood ratio:
- The Curse of Horizon: Variance scales exponentially: where . For , variance routinely exceeds , rendering the estimator useless.
(3) Per-Decision Importance Sampling (PDIS, Precup et al.):
Recognizes that future actions cannot causally influence past reward . Dropping future weights reduces variance without introducing bias:
(4) Sequential Doubly Robust (SDR, Jiang & Li, 2016):
Recursively estimates Q-functions and value functions backwards from down to 1:
Achieves double robustness across sequential MDPs and dramatically suppresses the exponential variance explosion.
(1) The Sequential Markov Decision Process (MDP) Framework:
Let user session trajectory of length be .
The probability of trajectory under policy is:
The cumulative trajectory return is .
(2) Full Trajectory Importance Sampling:
Notice that transition dynamics and initial state distribution are identical across policies and cancel out in the likelihood ratio:
- The Curse of Horizon: Variance scales exponentially: where . For , variance routinely exceeds , rendering the estimator useless.
(3) Per-Decision Importance Sampling (PDIS, Precup et al.):
Recognizes that future actions cannot causally influence past reward . Dropping future weights reduces variance without introducing bias:
(4) Sequential Doubly Robust (SDR, Jiang & Li, 2016):
Recursively estimates Q-functions and value functions backwards from down to 1:
Achieves double robustness across sequential MDPs and dramatically suppresses the exponential variance explosion.
🏭 Production Trade-offs
In-Depth Analysis & Engineering Trade-offs: ① The horizon threshold for importance sampling ($T \le 5$)—standard trajectory IPS works reliably for short dialogue turns or 3-step checkout funnels (); for long multi-session user journeys (), importance sampling breaks down completely; systems transition to Marginalized Importance Sampling (MIS / DualDICE) which estimates stationary state-action distribution ratios , breaking the exponential dependence on . ② Model-based RL simulators (Virtual World Simulation)—training a deep generative world model (user behavior simulator using Transformers or GANs) to roll out synthetic candidate trajectories offline provides low variance but introduces simulation modeling bias. ③ Markovian state assumption violations—standard sequential OPE assumes user state satisfies the Markov property (); in reality, user fatigue and mood depend on full historical trajectories; using recurrent or Transformer representations of session history as state restores Markovian validity. ④ Near-deterministic candidate policies—if candidate policy is an argmax greedy policy, step weights frequently evaluate to 0 or extreme spikes; soft temperature exploration policies () stabilize evaluation. ⑤ Session truncation in production logs—bounding maximum session length (e.g., ) in offline logs prevents single infinite user sessions from corrupting batch estimator variance. ⑥ Interview takeaway—explain why sequential OPE differs from bandit OPE (actions alter future states), derive trajectory importance weighting , explain the exponential curse of horizon , and detail Per-Decision IPS and Sequential Doubly Robust (SDR).
⚠️ Common Interview Pitfalls
- ✕Multiplying importance weights across long user sessions (T > 20) without per-decision truncation, triggering infinite variance collapse.
- ✕Applying single-step bandit OPE to multi-step recommendation sessions, completely ignoring that early recommendations alter downstream user retention.
- ✕Violating the Markov state assumption by using raw item IDs as state s_t without incorporating past session interaction history.
🎯 Interviewer Follow-up Inquiries
- ?How does Per-Decision IPS (PDIS) eliminate unnecessary future importance weights to reduce variance in sequential evaluation?
- ?What is Marginalized Importance Sampling (MIS), and how does it estimate state-action distribution ratios to break the curse of horizon?
- ?How does the recursive formulation of Sequential Doubly Robust (SDR) maintain unbiasedness while stabilizing multi-step evaluation?
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
📚