快速A/B/n测试：通过树耦合反馈共享进行精确多策略比较

# 快速 A/B/n 测试：通过树耦合反馈共享实现精确多策略比较

来源：https://arxiv.org/html/2608.12831

Yuxiao Wen

致谢：Yuxiao Wen 就职于纽约大学库朗数学科学研究所，邮箱：[[email protected]](mailto:[email protected])。

###### 摘要

在线平台越来越多地比较多种自适应决策策略——排序系统、推荐算法、定价规则和语言模型智能体——而每一次带有奖励的交互都可能代价高昂或存在风险。直接的 A/B/n 设计为每个 \(J\) 策略提供其自身的 \(T\) 时域轨迹，因此使用 \(JT\) 个结果。我们引入了树耦合 A/B 测试（Tree-Coupled A/B Testing，TCAB），这是一种针对任意历史依赖的上下文赌博机策略的精确反馈共享设计。在每一轮中，一棵可预测的树连接当前的策略历史；每个父子上下文–动作律都被最大耦合，并且在匹配的树边组件内共享一个奖励。尽管这些策略被有意地设置为相依的，每个策略仍然严格保留其独立的有限时域轨迹律。如果 \(D_{e,t}\) 记录了第 \(t\) 轮树边 \(e\) 上的不匹配，那么奖励查询的数量满足逐路径恒等式 \(N(T)=T+\sum_{t,e}D_{e,t}\)，因此在期望上等于 \(T\) 加上累积的树边全变差。该代价在所选树上的精确边局部设计类中是条件最优的，而当前轮的最小生成树在树设计中是短视最优的。对于固定的 \(J\)，每个策略的次线性伪遗憾及几乎必然唯一的预言机动作蕴含 \(\mathbb{E}[N(T)]=T+o(T)\)，而独立运行则为 \(JT\)。我们还获得了成对策略对比的有限样本方差界。在奖励模型评估、多选语言模型评估和自适应搜索策略上的实验表明，代价–精度前沿有显著改善。

关键词：在线实验；A/B 测试；上下文赌博机；最大耦合；自适应策略比较；反馈共享。

## 1 引言

在线受控实验是大型数字平台的生产基础设施。Google、Microsoft/Bing 和 LinkedIn 已描述了支持重叠实验和持续产品迭代的系统（Tang et al. 2010；Kohavi et al. 2013；Xu et al. 2015）。一个涉及十三个组织的跨行业峰会的报告显示，参与组织在前一年总共测试了超过十万个处理变体（Gupta et al. 2019）。同样的压力现在也出现在机器学习评估中：产品团队比较许多推荐系统配置、排序策略、提示策略和模型检查点，而人工或在线反馈仍然昂贵。例如，原始的 Chatbot Arena 研究积累了超过 24 万条人类偏好投票来比较语言模型（Chiang et al. 2024）。

一个有用的区分是重用*流量*和重用*反馈*。例如，Google 的重叠实验基础设施允许不同层中的兼容实验共享相同的基础流量，同时保留每个实验所需的随机化（Tang et al. 2010）。我们的问题与其互补，并且在多策略比较的内部运作：当几个候选策略会产生相同的上下文决策时，能否让一个已实现的结果被多个策略使用，而不改变其中任何一个的有限时域律？这一区分很重要，因为仅靠流量复用并不能消除单个策略比较问题中各备选方案之间重复的带奖励交互。

经典 A/B 实验是为静态处理设计的。现代系统则往往比较*策略*：策略观察当前查询或用户上下文，选择一个动作，只接收被选动作的结果，并可能根据其自适应历史更新所有后续决策。要在相同的目标时域 \(T\) 上比较 \(J\) 个候选策略，直接的 A/B/n 设计会运行 \(J\) 条独立轨迹，并使用 \(JT\) 次带奖励的交互。当实验性动作可能降低用户体验、消耗专家标签、调用昂贵模型或延迟部署决策时，这一代价在操作上非常重要。

然而，仍然存在巨大的冗余来源。由相邻超参数、模型检查点或业务规则生成的候选策略经常在同一上下文上做出相同的决策。当两个策略实现相同的完整上下文–动作对时，它们需要相同的条件奖励律，因此可以接收相同的物理结果。有目的地耦合它们的轨迹可以去除重复的奖励噪声并节省一次交互。挑战在于，这样做不能改变任一策略的自适应轨迹分布。

上下文性使这一挑战从根本上不同于重放一个臂标签。即使在 i.i.d. 上下文中，被选动作的观察所附带的上下文也取决于策略的选择规则和历史。此外，在排序列表、拍卖和推荐等应用中，选择一项的结果可能取决于整个展示列表或用户状态，而不仅仅是被选项的局部特征。因此，我们对完整的上下文奖励核 \(Q_a(\cdot\mid x)\) 建模，并耦合策略的完整单步*上下文–动作律*。最大耦合使两个完整对以它们的全变差距离所允许的最大概率相等；共享分支使用一个奖励，而残差分支则开启一个新的查询。

从两个策略到 \(J\ge 3\) 会产生第二个障碍。成对最大耦合不一定可以联合兼容：一般来说，不存在一个单一耦合能够同时最大化每一对的相等概率（Angel and Spinka 2019）。我们通过策略树来解决这一不相容性。在无环图的 \(J-1\) 条边上规定的成对耦合总是可以被粘合为一个联合律。一条断裂的边会开启一个新的奖励谱系；匹配的边会传递相同的上下文、动作和奖励。因此，每一轮的奖励查询数量恰好等于 1 加上断裂边的数量。

我们的算法 Tree-Coupled A/B Testing（TCAB）是逐轮同步的。在第 \(t\) 轮开始时，实验可以选择任何根据截至第 \(t-1\) 轮可用历史可测的树。然后它对根进行采样，按深度遍历树，为每个匹配边组件查询一个结果，并同时更新所有策略。这种随时间循环的外层结构直接允许可预测的、随时间自适应的树。它也暴露了实际的并行性：一旦父节点可用，同一深度的所有子节点都可以并发耦合，不同组件的奖励查询也可以并发发出。自适应策略按轮次保持顺序，这是必须的，而自适应策略还可以在轮次之间额外并行。

参见图注

(a) 标准 A/B/C 测试

(b) 基于树的数据共享

图 1：在标准 A/B 测试中，策略是独立且同时运行的。在 TCAB 中，策略按轮次分阶段运行，阶段由树决定，并重用先前阶段的数据。

由此得到的保证是有限时域且无模型依赖的。每个策略轨迹都精确地拥有其独立的律，因此所有值和策略对比都是无偏的。期望查询代价为 \(T\) 加上所选树边上的累积全变差。这一恒等式给出了一个精确的设计原则：以基线为中心的星形树简单，并使每个基线比较达到最大；而预言机最小生成树则在边局部树设计中最小化*当前轮*的代价。我们要强调，这是一个短视树最优性陈述，而非在任意多边际耦合或完整自适应时域上的全局最优性主张。

当候选策略是相关的而非任意时，该方法最为有用。例子包括相邻模型检查点、相近超参数设置、在大多数用户上一致的可选排序或推荐规则，以及越来越集中于相同良好动作的学习算法。在第一种情形下，相关的树边全变差距离从一开始就很小；在第二种情形下，我们的遗憾分析表明，超额查询代价相对于 \(T\) 可以消失。相反，如果候选策略几乎从不在其完整上下文–动作对上一致，TCAB 仍然精确，但几乎不节省查询。这使得该理论具有直接的诊断性：决定代价的同一边不匹配也指示了反馈共享是否会有帮助。

#### 贡献。

我们的主要贡献如下。

1. 我们形式化了在 i.i.d. 完整上下文和非参数完整上下文奖励核 \(Q_a(\cdot\mid x)\) 下，对 \(J\) 个任意历史依赖、可能随机的上下文策略的精确有限时域比较。
2. 我们引入了 TCAB 的逐轮同步、可预测时间自适应版本。所有选定树边上的最大耦合能够同时共存，所有同深度的耦合操作和所有组件级奖励查询都可以并行执行，并且每个策略都严格保留其独立的轨迹律。
3. 我们证明了逐路径和期望代价恒等式

\[
N(T)=T+\sum_{t=1}^{T}\sum_{e\in E_t}D_{e,t},\qquad
\mathbb{E}[N(T)]=T+\sum_{t=1}^{T}\mathbb{E}\!\left[\sum_{e\in E_t}\delta_{e,t}\right].
\]

在自然的条件精确边局部设计类中，TCAB 在每一个选定树上都是最优的。基线星形树和当前轮最小生成树给出了两个具体特例。

4. 我们建立了可预测树序列的有限样本遗憾–代价界。对于固定的 \(J\)，预言机动作的几乎必然唯一性和每个策略的 \(o(T)\) 伪遗憾意味着期望奖励查询次数为 \(T+o(T)\)；一个边际条件给出显式速率。
5. 我们证明了每个成对策略对比的有限样本方差界。这些界扩展到时变树，并分离了边不匹配和已实现伪遗憾的作用；附录中给出了一个一般的固定零和扩展。
6. 在两个语言模型评估任务和一个自适应搜索赌博机任务中，与预算匹配或全额预算的独立 A/B/n 基线相比，TCAB 改善了经验代价–精度权衡。

## 2 相关文献

#### 大规模在线实验。

在线受控实验已成为大型数字平台的核心基础设施。Google 的重叠实验架构旨在通过允许不同层中的兼容实验在同一用户或查询上重叠，从而在有限流量上运行更多实验（Tang et al. 2010）；Microsoft/Bing 和 LinkedIn 描述了相关的大规模实验系统和组织挑战（Kohavi et al. 2013；Xu et al. 2015）。一个跨行业峰会强调了由此产生的实验项目的规模，以及更快、更可靠决策的运营压力（Gupta et al. 2019）。这些系统激发了我们的资源问题，但解决的是一个不同的问题：它们在实验之间复用流量，而 TCAB 在一个多策略比较内部共享候选策略之间已实现的反馈，同时保留每个策略独立的轨迹律。

#### Artificial Replay 与学习算法比较。

最接近的方法论工作是 Meng et al. 2026，该工作引入了 Artificial Replay 来比较两个无上下文随机赌博机算法，并证明了精确边际、交互代价和方差保证。我们的设置引入了两个在双策略无上下文构造中不存在的障碍。第一，上下文策略在观察查询后选择动作，因此精确重用需要耦合完整的上下文–动作律，而不仅仅是臂标签。第二，对于 \(J\ge 3\) 个分布，所有成对最大耦合不一定兼容；我们的策略树选择 \(J-1\) 对，其最大耦合可以同时被粘合。Banerjee et al. 2022 也使用了“artificial replay”这一短语，指将外生历史数据集纳入以热启动赌博机。该问题关注的是单个学习器如何使用历史观测，而不是几个前瞻性策略轨迹如何共享新生成的反馈。

#### 多重比较、自适应实验与策略选择。

经典的“多对一”过程在考虑多重性的同时，将几个静态处理与一个公共对照进行比较（Dunnett 1955）。自适应设计工作研究在自适应收集的数据下应如何分配观测，或如何维持有效推断（Kasy and Sautmann 2021；Hadad et al. 2021；Simchi-Levi and Wang 2025）。与策略比较和选择相关的现有工作包括用于评估多个策略的安全探索（Wan et al. 2022）、高置信离线策略选择（Kuzborskij et al. 2021）以及从固定经验数据集中对策略排序（Yang et al. 2022）。这些工作优化的是在给定数据生成方案下的分配或推断。我们的目标不同：构造一个联合前瞻性实验，使得每个自适应候选都具有其在孤立情况下本应具有的有限时域路径律，但只要耦合允许，就会共享重复的奖励查询。

#### 上下文重放与离线策略评估。

Li et al. 2011 给出了从均匀随机日志中对上下文赌博机算法的精确重放评估器：当目标算法选择日志中的动作时，保留该日志事件，因此保留的自适应历史具有与在线目标轨迹相同的律。逆倾向得分、双重稳健、自归一化及相关方法构成了更广泛的离线策略评估文献（Dudík et al. 2011；Swaminathan and Joachims 2015；Wang et al. 2017；Su et al. 2020；Zhan et al. 2021）。这些方法从外生日志出发，因此需要支持、加权、建模或偏差–方差折衷。而在 TCAB 中，候选策略是可运行的，当策略无法耦合时，实验会前瞻性地生成残差观测。因此，重叠不足会提高查询次数