arXiv:2605.29500cs.LGcs.AI2026-05

提出新方法精准评估推荐系统,避免传统方法的计算浪费与误差

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

论文配图:Quotient DAGs for Off-Policy Evaluation:Forward-Flow Importance Sampling and Exact Slate Propensities
图 1 · 摘自论文原文
  • 用商图结构合并等效决策路径,简化评估复杂度
  • 首次实现无序推荐项组合的精确权重计算,无需遍历所有顺序
  • 适合需要高精度评估的推荐、医疗等高风险场景

离线策略评估旨在利用行为策略采集的数据估计目标策略的表现,这在推荐系统或医疗等在线测试成本高或有风险的场景中至关重要。标准重要性采样会重新加权每条日志轨迹,但可能将生成过程中的细节视为有效信息,而这些细节在评估目标中其实无关——例如自回归式推荐器按顺序生成项目,但奖励和下游估计器仅依赖无序的项目集合。这导致冗余方差和计算瓶颈,因为精确计算无序集合的倾向值需对所有生成顺序求和。本文提出商图(Quotient DAG)视角,将评估中等效的历史路径合并,并在合并图上使用目标到行为策略的前向流动比率分配权重。针对满足集合充分性下一项目接口的推荐任务,该方法导出Forward-DP,一种基于子集DAG的动态规划算法,可不进行阶乘级枚举即计算精确的无序倾向值。由此得到的倾向值基元使基于倾向值的评估与模型选择在上下文相关自回归日志器中成为可行方案。

原文摘要 · Abstract (English)

Off-policy evaluation estimates how a target policy would perform using data collected by a different behavior policy, which is crucial when online testing is costly or risky, such as in recommendation or healthcare. Standard importance sampling reweights each logged trajectory, but it can treat details of the generation process as meaningful even when the evaluation target ignores them: for example, an autoregressive slate recommender may generate an ordered sequence of items while the reward and downstream estimator depend only on the unordered slate. This creates nuisance variance and a computational gap, since exact unordered slate propensities require summing over all generation orders. We introduce a quotient-DAG view that merges histories equivalent for evaluation and assigns weights using target-to-behavior forward-flow ratios on the merged graph. For slate recommendation under a set-sufficient next-item interface, this yields Forward-DP, a subset-DAG dynamic program that computes exact unordered propensities without factorial enumeration. The resulting propensity primitive enables practical propensity-based evaluation and model selection for context-dependent autoregressive slate loggers.

离线评估推荐系统重要性采样动态规划

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。