所属模块：
M7 · 检索、排序与推荐系统 (Retrieval, Ranking & RecSys)| 专题分类：离线评估与 OPE (Offline Evaluation & OPE)| 难度等级：Hard
一、核心一句话结论 (One-Sentence Summary)
序列决策中动作影响后续状态（长期效应）；多步 IPS 用’轨迹级’权重，方差随长度指数增长。
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 Insights)
- 📌 序列决策：动作影响后续状态（不能逐时刻独立评估）
- 📌 多步 IPS：用’轨迹级’权重（各时刻权重的乘积）
- 📌 方差随轨迹长度指数增长（乘积效应）
English Insights:
– 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 Principles & Derivation)
$$hat V_{text{seq}}=frac1nsum_ileft(prod_{t=1}^Tfrac{pi_{text{new}}(a_{i,t}|x_{i,t})}{pi_{text{old}}(a_{i,t}|x_{i,t})}right)cdotleft(sum_{t=1}^Tgamma^{t-1}r_{i,t}right)$$
数学机理：序列决策 OPE 的困难——(1) 与单步的区别——(a) 单步——动作只影响’当次奖励’（如’推荐一个物品 → 是否点击’）；(b) 序列——动作影响后续状态（如’推荐了 A → 用户看了 A → 后续推荐 B 的效果变化’）；(c) 后果——’长期效应’（一个动作的收益跨越多个时刻）；故不能逐时刻独立评估。(2) 多步 IPS（trajectory-level IPS）——用’轨迹级权重’：w_traj=∏{t=1}^T [π_new(a_t|x_t)/π_old(a_t|x_t)]；估计式：V̂=(1/n)Σ_i w_traj,i·(Σ_t γ^{t-1}r{i,t)（各时刻奖励的折扣和）。(3) 方差问题（严重）——(a) 乘积效应——w_traj 是 T 个权重的乘积；若每个权重的期望≈1 但方差>0，则乘积的方差随 T 指数增长；(b) 量化——若每个时刻的权重在 [0.5, 2] 波动，则 T=100 时乘积的范围是 [2⁻¹⁰⁰, 2¹⁰⁰]（完全不可用）；(c) 后果——多步 IPS 在实践中几乎不可用（除非轨迹很短或策略很接近）。(4) 缓解手段——(a) 权重截断（每步或轨迹级）；(b) 自归一化（SNIPS 的序列版）；(c) ‘每步独立’的近似（假设动作不影响后续状态——强假设）；(d) DR 的序列版（用模型作基线，只处理残差）；(e) ‘折扣因子’（γ<1 降低远期权重，使有效长度变短）；(f) 降低评估范围（只评估短片段）；(g) 模型基方法（MB）——学一个’环境模型’（状态转移 + 奖励），用它模拟新策略（优点——方差低；缺点——模型误差累积）；(h) 混合（MB + IS）。其他序列 OPE 方法——(a) MAGIC（模型基与 IS 的组合）；(b) Doubly Robust 的序列版（DR 用于序列）；(c) ‘伪逆/双重稳健’的变体；(d) ‘离线强化学习’（不只评估、还要优化）。与其他问题的关系——(a) 与’离线强化学习’（OPE 是 RL 的一部分）；(b) 与’长期效应评估’（同一问题）；(c) 与’延迟反馈’（序列中的延迟奖励）。实践建议——(a) 短轨迹 → 多步 IPS 可行（配截断）；(b) 长轨迹 → 用 DR/模型基方法（方差更低）；(c) ‘每步独立’的近似（若合理）；(d) 折扣因子（缩短有效长度）；(e) 模型基方法（注意误差累积）；(f) 与 A/B 对比验证；(g) 离线只做粗筛。度量——(a) OPE 估计 vs A/B；(b) 方差（重复估计的波动）；(c) 有效轨迹长度；(d) 权重的分布。
📖 查看英文严格数学推导 (English Mathematical Derivation)
Mathematical Formulation: Sequential OPE & Curse of Horizon.
(1) The Sequential Markov Decision Process (MDP) Framework:
Let user session trajectory of length $T$ be $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(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(tau) = sum_{t=1}^T gamma^{t-1} r_t$.
(2) Full Trajectory Importance Sampling:
Notice that transition dynamics $P(s_{t+1} mid s_t, a_t)$ and initial state distribution $P(s_1)$ are identical across policies and cancel out in the likelihood ratio:
$$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$$
$$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: $text{Var}(hat{V}) propto O(C^T)$ where $C = mathbb{E}[w_t^2] > 1$. For $T = 20$, variance routinely exceeds $10^{10}$, rendering the estimator useless.
(3) Per-Decision Importance Sampling (PDIS, Precup et al.):
Recognizes that future actions $a_{t+1:T}$ cannot causally influence past reward $r_t$. Dropping future weights reduces variance without introducing bias:
$$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 $hat{Q}(s, a)$ and value functions $hat{V}(s)$ backwards from $T$ down to 1:
$$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.
四、工业级落地权衡与工程考量 (Industrial Trade-offs)
深度剖析与工程权衡：① ‘方差随轨迹长度指数增长’是关键——乘积效应使多步 IPS 几乎不可用；面试中能指出这一点是深度理解的标志。② ‘DR 的序列版方差更低’——用模型作基线；是长轨迹的实用选择。③ ‘模型基方法的误差累积’——模型误差在长轨迹上累积；故需与 IS 混合。④ ‘折扣因子缩短有效长度’——γ<1 使远期权重小（降方差）；这是实用技巧。⑤ ‘离线强化学习’是更一般的问题——OPE 是其中的评估部分。⑥ 面试要点——被问’序列决策怎么评估’，应给出’多步 IPS（轨迹级权重）+ 方差指数增长 + 缓解（截断/DR/折扣/模型基/混合）‘；能指出’乘积效应’是深度理解的标志。
⚙️ 查看英文落地权衡分析 (English Systems & 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 le 5$); for long multi-session user journeys ($T ge 20$), importance sampling breaks down completely; systems transition to Marginalized Importance Sampling (MIS / DualDICE) which estimates stationary state-action distribution ratios $frac{d_{pi_1}(s, a)}{d_{pi_0}(s, a)}$, breaking the exponential dependence on $T$. ② 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 $s_t$ satisfies the Markov property ($s_{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 $s_t$ restores Markovian validity. ④ Near-deterministic candidate policies—if candidate policy $pi_1$ is an argmax greedy policy, step weights $w_t$ frequently evaluate to 0 or extreme spikes; soft temperature exploration policies ($pi_1(a mid s) propto exp(Q(s, a) / tau)$) stabilize evaluation. ⑤ Session truncation in production logs—bounding maximum session length (e.g., $T_{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 $prod w_t$, explain the exponential curse of horizon $O(C^T)$, and detail Per-Decision IPS and Sequential Doubly Robust (SDR).
五、常见面试避坑陷阱 (Common Pitfalls & Traps)
- ⚠️ 用多步 IPS 评估长轨迹（方差爆炸）
- ⚠️ 忽略’动作影响后续状态’（逐时刻独立评估）
English 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.
六、高频深度面试追问与预测 (Follow-Up Questions)
- 为什么不能逐时刻用 IPS？
- How does Per-Decision IPS (PDIS) eliminate unnecessary future importance weights to reduce variance in sequential evaluation?
- 如何降低多步 IPS 的方差？
- What is Marginalized Importance Sampling (MIS), and how does it estimate state-action distribution ratios to break the curse of horizon?
七、知识图谱对齐 (Knowledge Graph Anchor)
- 🔗 关联底层卡片：
推荐系统离线评估与离线策略评估 (OPE)：逆倾向得分 (IPS) 与重要性采样(Off-Policy Evaluation (OPE): IPS, Doubly Robust & Calibration) - 🗺️ 知识图谱模块：
机器学习工程师高频考点导图
🔬 算法科学家与机器学习深度考察全量题库 (Science Depth)
本题收录于 TalentMe 算法科学家深度考察真题库 (Science Depth)。全库共 856 道硬核考点，深度覆盖数学统计、经典ML、深度学习、Transformer、大语言模型、多模态、推荐系统与 MLOps。支持 Jev 面经智能匹配、一键离线单文件 HTML 手册导出并直连 Obsidian 本地记忆。