🤖 machine learning

Quotient DAGs for Off-Policy Evaluation:Forward-Flow Importance Sampling and Exact Slate Propensities

本文引入了一种商图（quotient-DAG）框架和前向动态规划（Forward-DP）算法，以消除冗余方差，并实现对自回归推荐系统中无序 slate 倾向的精确计算，从而提升离线策略评估的效率。

原作者： Ziwen Xie, Shaowen Xiang, Hongyu He, Dianbo Liu

发布于 2026-05-29

📖 1 分钟阅读☕ 轻松阅读

原作者： Ziwen Xie, Shaowen Xiang, Hongyu He, Dianbo Liu

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象你是一位厨师，试图评估一道新食谱（目标策略）的好坏，但你无法在自己的厨房里实际烹饪它，因为成本太高或风险太大。相反，你有一本笔记，里面记录了另一位厨师（行为策略）过去烹饪过的食谱。你的目标是仅利用这本旧笔记来估算新食谱会有多美味。这就是**离线策略评估（OPE）**的核心问题。

问题：数错了东西

通常，为了评估新食谱，你会查看旧厨师采取的每一个步骤。你会说：“好的，他们先加了盐，然后加胡椒，再加大蒜。”你基于那个确切的顺序计算出一个分数。

但这里有个陷阱：有时添加食材的顺序实际上并不会改变最终菜肴的味道。

场景：想象一个包含若干项目的“板”（例如 5 首歌曲的歌单，或 5 道开胃菜的托盘）。顾客只关心托盘上有哪些5 个项目，而不关心厨师放置它们的顺序。
错误：旧笔记记录了顺序（歌曲 A，然后是 B，然后是 C……）。如果你基于那个特定顺序计算分数，你就是在把“顺序”当作重要因素。但由于顾客并不在意，你实际上是在计算中引入了“噪声”。
结果：这种噪声会产生巨大的混淆（方差）。这就像试图通过单独称量行李箱里的每一只袜子来猜测行李箱的重量，而不是直接称量整个行李箱。根据你称量袜子的方式不同，你会得到许多不同的答案。

此外，计算获得特定 5 件物品组合（忽略顺序）的“真实”概率是一场数学噩梦。如果你有 5 件物品，它们被选中的方式有 120 种（5 的阶乘）。对于大型组合，对笔记中的每一条目都进行这种数学运算在计算上是不可行的。

解决方案：“商 DAG"（分组映射）

作者提出了一种巧妙的数据查看方式。他们建议不要查看厨师采取的每一条路径，而是将所有导致相同结果的路径分组。

类比：想象一棵巨大的树，每个分支代表一种不同的添加食材顺序。
- 旧方法：你走过每一个分支，测量重量，然后试图取平均值。
- 新方法（商 DAG）：你意识到，所有最终包含相同集合食材的分支，实际上在你的地图中是同一个“节点”。你将所有这些分支坍缩为一个点。
- 地图：这创建了一个“有向无环图”（DAG）——一张你只关心已选物品集合、而不关心顺序的地图。

魔法技巧：前向流重要性采样

一旦你有了这个简化的地图，你就需要知道新厨师到达特定“集合”的可能性与旧厨师相比如何。

旧方法：你必须将所有 120 种不同顺序的概率相加才能得到答案。
新方法（前向动态规划）：作者发明了一种称为**前向动态规划（Forward-DP）**的方法。把这想象成一个智能计算器，它一步步构建答案。
- 它从一个空托盘开始（概率为 1）。
- 它问：“如果我有 1 件物品，添加第 2 件的概率是多少？”
- 它问：“如果我有 2 件物品，添加第 3 件的概率是多少？”
- 它不断构建出整个集合的概率，而无需列出所有 120 种顺序。

这种方法是精确的（它不猜测）且快速的。它不需要花费数年时间来计算（阶乘时间），而是需要可管理的时间量（相对于托盘大小呈指数级，但相对于菜单大小呈多项式级）。

为什么这很重要

更少噪声：通过忽略无关的“顺序”细节，数学变得更加清晰。估算结果更准确、更稳定。
可行性：这使得评估复杂的推荐系统（例如“给我展示 10 部电影”）成为可能，而这些系统以前因计算过于困难而无法精确评估。
现实世界测试：作者在以下数据上测试了该方法：
- 医疗数据：模拟脓毒症（血液感染）的治疗。与旧方法相比，他们的方法对患者预后的预测准确度高得多。
- 推荐数据：使用名为 KuaiRec（视频推荐）的数据集。他们表明，他们的方法可以在几秒钟内计算出一组视频被推荐的“真实”概率，而旧方法则需要数天甚至无法完成。

总结

这篇论文提出了一种方法，停止过度分析“如何”（动作的顺序），转而关注“什么”（最终的项目集合）。通过将等效路径分组在一起，并使用一种聪明的、逐步的计算方法（前向动态规划），他们能够更准确、更高效地评估新策略，特别是在医疗保健和推荐引擎等领域，因为在现实生活中测试新想法过于危险或昂贵。

技术摘要：用于离线策略评估的商 DAG

问题陈述

离线策略评估（OPE）利用由行为策略 $\beta$ 收集的数据来估计目标策略 $\pi$ 的性能。标准重要性采样（IS）通过目标策略与行为策略的动作概率比值的乘积，对记录的轨迹进行重加权。然而，这种方法往往将生成过程的细节视为有意义，即使评估目标本身忽略这些细节。

这一问题的一个主要实例出现在列表（slate）推荐中，现代生成器通常以自回归方式构建列表（物品集合），沿特定顺序暴露每一步的概率。然而，奖励和下游估计量往往仅依赖于无序列表。标准轨迹 IS 为特定的有序路径分配似然比，从而产生“联合倾向性差距”：记录器暴露的是有序概率，而估计量需要的是无序列表的总概率。计算这种精确的无序倾向性通常需要对所有 $K!$ 种生成顺序求和，对于中等规模的列表而言，这在计算上是不可行的。此外，将顺序视为重要因素会在奖励对生成顺序不变时引入不必要的方差。

方法论

本文引入了一种商 DAG 视角来解决这些问题。其核心思想是将历史前缀的展开树针对评估目标所需的充分等价关系进行商化。

商 DAG 与前向流：
- 通过合并对评估目标等价的历史前缀（例如，包含相同被选物品集合的前缀，无论顺序如何），将展开树折叠。
- 这形成了一个分层的有向无环图（DAG），其中节点代表等价类（商状态）。
- 该方法不再基于单一实现路径的比值进行加权，而是使用前向流比值 $F_\pi(z)/F_\beta(z)$ 分配权重，其中 $F_\mu(z)$ 是在策略 $\mu$ 下到达节点 $z$ 的概率质量。
- 这种方法推广了现有方法：每步决策 IS、边缘化 IS 和已知抽象 MIS 分别对应于不同等价关系选择的特例。
前向流重要性采样（FF-IS）：
- 对于一般的有限时域 OPE，该估计量用商似然比替换了每步决策 IS（PDIS）中的采样前缀比值。
- 理论分析表明，对于终端商可测回报，这种加权消除了“类内”目标与行为的不匹配，提供了一个精确的方差差距表达式，量化了不必要方差的减少。
用于列表 OPE 的前向动态规划（Forward-DP）：
- 本文将该框架专门应用于集合充分接口（定义 1）下的自回归列表生成。如果选择下一个物品的概率仅取决于上下文和已选物品的集合，而不取决于它们的顺序，则该策略是集合充分的。
- 在集合充分性下，排列商对应于一个子集 DAG，其中节点是目录的子集，边表示追加未选物品。
- Forward-DP 算法： 一种动态规划算法通过对子集而非排列求和，计算精确的无序列表倾向性 $F_\mu(S|x)$ $F_{μ} (S ∣ x)$ 。
  - 复杂度： $O((M + K) \cdot 2^K)$ ，其中 $M$ 是目录大小， $K$ 是列表大小。这避免了 $K!$ 的枚举。
  - 最优性： 本文证明，任何计算集合充分策略精确无序倾向性的确定性算法，在最坏情况下必须查询列表的每一个真子集，从而确立了 Forward-DP 在常数因子范围内是查询最优的。

主要贡献

理论框架： 一个统一的商 DAG 视角用于 OPE，该视角在更粗粒度的样本空间上导出精确似然比作为前向流比值。
算法创新： Forward-DP 算法，它能在关于目录大小多项式、关于列表大小指数（在 $K$ 上为固定参数可解）的时间内，计算上下文依赖、集合充分的自回归记录器的精确无序列表倾向性。
方差减少： 形式化证明商加权消除了由无关生成顺序引起的方差分量（顺序 nuisance 方差），特别是在奖励对列表生成序列不变的情况下。
列表 OPE 的原语： 引入 Forward-DP 作为一种原语，使基于精确倾向性的评估和基于 Transformer 的列表推荐器的模型选择成为可能，填补了固定分数 Plackett-Luce 公式不适用的上下文依赖记录器的空白。

实验结果

作者在有限时域 MDP 基准和列表推荐任务上评估了该方法：

有限时域 MDP（败血症与 ICU-败血症）：
- 与标准轨迹 IS 和其他基线（如 DualDICE、GenDICE）相比，前向流 IS（FF-IS）显著降低了均方根误差（RMSE）。
- 在败血症基准测试中，FF-WIS 将 RMSE 从 0.291（WIS）降低到了 0.0568。
- 这些提升仅通过使用记录的轨迹实现，无需拟合转换模型。
KuaiRec 列表实验：
- 计算效率： Forward-DP 计算精确倾向性的速度比 $K!$ 枚举快几个数量级。对于 $K=8$ ，枚举耗时约 97,108 秒，而 Forward-DP 耗时约 8.94 秒。对于 $K=12$ ，枚举不可行，而 Forward-DP 在约 13.7 秒内完成。
- 下游 OPE： 使用 Forward-DP 权重的估计量（FF-OIS、FF-DR）在所有列表大小（ $K \in \{4, 6, 8\}$ ）上，在 RMSE 方面始终优于其轨迹加权对应物（OIS、DR）。
- 模型选择： 在自回归 Transformer 推荐器之间的离线策略模型选择中，利用 Forward-DP 的估计量（如 Tree-DR、DP-OPCB-DR）在 Top-1 准确率、Spearman 相关系数方面取得了更优表现，且遗憾值更低，优于基于轨迹的方法。

意义与主张

本文声称，所提出的框架提供了每步决策 IS 的Rao–Blackwell 化。通过在充分等价关系下对展开树进行商化，该方法消除了与无关历史细节（如列表推荐中的生成顺序）相关的 nuisance 方差。

具体到列表推荐，本文断言 Forward-DP 为上下文依赖的自回归记录器提供了缺失的 OPE 原语。与依赖固定分数假设（物品分数不随部分列表变化）或蒙特卡洛近似的前序方法不同，Forward-DP 处理了下一个物品 softmax 依赖于部分列表的情况，无需阶乘枚举即可计算精确的联合倾向性。这使得针对现代基于 Transformer 的推荐器进行实用的、基于精确倾向性的评估和模型选择成为可能。

作者指出了局限性，包括需要集合充分性假设（这可能需要在实际部署中对被选集合进行规范化），以及随列表大小 $K$ 呈指数级扩展，但他们认为这对于典型的列表大小（ $K \le 10$ ）是可行的，而在这些规模下 $K!$ 是不可行的。