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
Next: M7-091 →
📐 Mathematical Definition
V^seq=1n∑i(∏t=1Tπnew(ai,t∣xi,t)πold(ai,t∣xi,t))⋅(∑t=1Tγt−1ri,t)\hat V_{\text{seq}}=\frac1n\sum_i\left(\prod_{t=1}^T\frac{\pi_{\text{new}}(a_{i,t}|x_{i,t})}{\pi_{\text{old}}(a_{i,t}|x_{i,t})}\right)\cdot\left(\sum_{t=1}^T\gamma^{t-1}r_{i,t}\right)
⚡ 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 TT be τ=(s1,a1,r1,s2,a2,r2,…,sT,aT,rT)\tau = (s_1, a_1, r_1, s_2, a_2, r_2, \dots, s_T, a_T, r_T).
The probability of trajectory τ\tau under policy π\pi is:
P(τ∣π)=P(s1)∏t=1Tπ(at∣st)P(st+1∣st,at)P(\tau \mid \pi) = P(s_1) \prod_{t=1}^T \pi(a_t \mid s_t) P(s_{t+1} \mid s_t, a_t)
The cumulative trajectory return is R(τ)=∑t=1Tγt−1rtR(\tau) = \sum_{t=1}^T \gamma^{t-1} r_t.

(2) Full Trajectory Importance Sampling:
Notice that transition dynamics P(st+1∣st,at)P(s_{t+1} \mid s_t, a_t) and initial state distribution P(s1)P(s_1) are identical across policies and cancel out in the likelihood ratio:
ρ1:T=P(τ∣π1)P(τ∣π0)=∏t=1Tπ1(at∣st)π0(at∣st)=∏t=1Twt\rho_{1:T} = \frac{P(\tau \mid \pi_1)}{P(\tau \mid \pi_0)} = \prod_{t=1}^T \frac{\pi_1(a_t \mid s_t)}{\pi_0(a_t \mid s_t)} = \prod_{t=1}^T w_t
V^Trajectory(π1)=1N∑i=1Nρ1:T(i)⋅(∑t=1Tγt−1rt(i))\hat{V}_{\text{Trajectory}}(\pi_1) = \frac{1}{N} \sum_{i=1}^N \rho_{1:T}^{(i)} \cdot \left( \sum_{t=1}^T \gamma^{t-1} r_t^{(i)} \right)
- The Curse of Horizon: Variance scales exponentially: Var(V^)∝O(CT)\text{Var}(\hat{V}) \propto O(C^T) where C=E[wt2]>1C = \mathbb{E}[w_t^2] > 1. For T=20T = 20, variance routinely exceeds 101010^{10}, rendering the estimator useless.

(3) Per-Decision Importance Sampling (PDIS, Precup et al.):
Recognizes that future actions at+1:Ta_{t+1:T} cannot causally influence past reward rtr_t. Dropping future weights reduces variance without introducing bias:
V^PDIS(π1)=1N∑i=1N∑t=1Tγt−1(∏τ=1twτ(i))rt(i)\hat{V}_{\text{PDIS}}(\pi_1) = \frac{1}{N} \sum_{i=1}^N \sum_{t=1}^T \gamma^{t-1} \left( \prod_{\tau=1}^t w_\tau^{(i)} \right) r_t^{(i)}

(4) Sequential Doubly Robust (SDR, Jiang & Li, 2016):
Recursively estimates Q-functions Q^(s,a)\hat{Q}(s, a) and value functions V^(s)\hat{V}(s) backwards from TT down to 1:
V^DRt=V^(st)+wt(rt+γV^DRt+1−Q^(st,at))\hat{V}_{\text{DR}}^t = \hat{V}(s_t) + w_t \left( r_t + \gamma \hat{V}_{\text{DR}}^{t+1} - \hat{Q}(s_t, a_t) \right)
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 (T≤5T \le 5); for long multi-session user journeys (T≥20T \ge 20), importance sampling breaks down completely; systems transition to Marginalized Importance Sampling (MIS / DualDICE) which estimates stationary state-action distribution ratios dπ1(s,a)dπ0(s,a)\frac{d_{\pi_1}(s, a)}{d_{\pi_0}(s, a)}, breaking the exponential dependence on TT. ② 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 sts_t satisfies the Markov property (st+1⊥s<t∣st,ats_{t+1} \perp s_{<t} \mid s_t, a_t); in reality, user fatigue and mood depend on full historical trajectories; using recurrent or Transformer representations of session history as state sts_t restores Markovian validity. ④ Near-deterministic candidate policies—if candidate policy π1\pi_1 is an argmax greedy policy, step weights wtw_t frequently evaluate to 0 or extreme spikes; soft temperature exploration policies (π1(a∣s)∝exp⁡(Q(s,a)/τ)\pi_1(a \mid s) \propto \exp(Q(s, a) / \tau)) stabilize evaluation. ⑤ Session truncation in production logs—bounding maximum session length (e.g., Tmax=10T_{\text{max}} = 10) 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 ∏wt\prod w_t, explain the exponential curse of horizon O(CT)O(C^T), 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.
🎯 Drill This Card Now➔
📚

Associated Knowledge Base Guides & Mindmaps

← PreviousM7-089: Explain Causal Directed Acyclic Graphs (DAGs), Do-Calculus, and Backdoor Paths in Counterfactual Evaluation📋 Back to BankNext →M7-091: Explain Confidence Interval Estimation and Effective Sample Size (ESS) in Off-Policy Evaluation