跳转至

文章背景与核心概要

在现代在线平台中，经常需要同时评估多种自适应决策策略，例如排序系统、推荐算法、定价规则以及大语言模型智能体。然而，与用户交互以收集反馈通常成本高昂或存在风险。传统的 A/B/n 测试为每种策略分配独立的视界-\(T\) 轨迹，导致总成本高达 \(JT\) 次结果观测。

为了克服这种低效性，本文引入了树耦合 A/B 测试（Tree-Coupled A/B Testing, TCAB），这是一种专为任意历史依赖的上下文强盗机（contextual-bandit）策略定制的精确反馈共享设计。通过最大化耦合（Maximal Coupling）与精确轨迹保持（Exact Trajectory Preservation），TCAB 在保证每种策略维持其精确独立有限视界轨迹分布的同时，大幅降低了奖励查询成本。对于固定的 \(J\)，随着策略渐进次线性伪遗憾及预言机动作的几乎必然唯一性，其期望成本达到了 \(\mathbb{E}[N(T)] = T + o(T)\)，极大地优于独立运行所需的 \(JT\) 成本，并在奖励模型评估、多选大模型评估以及自适应搜索策略的实验中展现出卓越的成本-精度前沿提升。

Fast A/B/n Testing: Exact Multi-Policy Comparison via Tree-Coupled Feedback Sharing

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

Authors: Yuxiao Wen
Primary Subject: Machine Learning (cs.LG)
Secondary Subject: Artificial Intelligence (cs.AI)
arXiv ID: arXiv:2608.12831 [cs.LG]
Dates: Submitted on 13 August 2026; Last revised 14 August 2026 (v2)
DOI: 10.48550/arXiv.2608.12831

Authors: Yuxiao Wen
Primary Subject: Machine Learning (cs.LG)
Secondary Subject: Artificial Intelligence (cs.AI)
arXiv ID: arXiv:2608.12831 [cs.LG]
Dates: Submitted on 13 August 2026; Last revised 14 August 2026 (v2)
DOI: 10.48550/arXiv.2608.12831

Summary

总结

Modern online platforms frequently need to evaluate multiple adaptive decision policies—such as ranking systems, recommendation algorithms, pricing rules, and language-model agents—simultaneously. However, interacting with users to gather feedback can be costly or risky.

现代在线平台经常需要同时评估多个自适应决策策略——例如排序系统、推荐算法、定价规则和大语言模型智能体。然而，与用户交互以收集反馈可能是昂贵或充满风险的。

Traditional A/B/n testing assigns each of the \(J \ge 2\) policies its own horizon-\(T\) trajectory, resulting in a total cost of \(JT\) outcomes. To overcome this inefficiency, this paper introduces Tree-Coupled A/B Testing (TCAB), an exact feedback-sharing design tailored for arbitrary history-dependent contextual-bandit policies:

传统的 A/B/n 测试为 \(J \ge 2\) 个策略中的每一个分配其自己的视界-\(T\) 轨迹，导致总成本为 \(JT\) 个结果。为了克服这种低效性，本文引入了树耦合 A/B 测试（Tree-Coupled A/B Testing, TCAB），这是一种专为任意历史依赖的上下文强盗机策略量身定制的精确反馈共享设计：

  • Maximal Coupling: At each round, a predictable tree connects the current policy histories, maximally coupling every parent-child context-action law. A single reward is shared within each component of matched tree edges.
  • Exact Trajectory Preservation: Despite the policies being deliberately dependent, every policy maintains its exact standalone finite-horizon trajectory law.
  • Cost Efficiency: Using a mismatch indicator \(D_{e,t}\) on tree edge \(e\) at round \(t\), the number of required reward queries satisfies the pathwise identity: $\(N(T) = T + \sum_{t,e} D_{e,t}\)$ In expectation, this cost equals \(T\) plus the cumulative tree-edge total variation.
  • Optimality: This cost is conditionally optimal among exact edge-local designs on the chosen tree, while a current-round minimum-spanning tree is myopically optimal among tree designs.
  • Asymptotic Performance: For a fixed \(J\), the sublinear pseudo-regret of every policy and the almost-sure uniqueness of the oracle action lead to \(\mathbb{E}[N(T)] = T + o(T)\), drastically outperforming the \(JT\) cost of independent runs. The paper also derives finite-sample variance bounds for pairwise policy contrasts.
  • 最大化耦合（Maximal Coupling）： 在每一轮中，一棵可预测的树将当前的策略历史连接起来，最大化地耦合每一个父子上下文-动作规律。在每个匹配树边分量内共享一个单一奖励。
  • 精确轨迹保持（Exact Trajectory Preservation）： 尽管这些策略被刻意设计为相互依赖，但每个策略都保持其精确的独立有限视界轨迹分布。
  • 成本效率（Cost Efficiency）： 通过在轮次 \(t\) 的树边 \(e\) 上使用不匹配指示器 \(D_{e,t}\)，所需的奖励查询次数满足路径恒等式： $\(N(T) = T + \sum_{t,e} D_{e,t}\)$ 在期望上，该成本等于 \(T\) 加上累积的树边全变差（total variation）。
  • 最优性（Optimality）： 该成本在所选树上的精确局部边设计中是有条件最优的，而当前轮次的最小生成树在树设计中是短视（myopic）最优的。
  • 渐进性能（Asymptotic Performance）： 对于固定的 \(J\)，每个策略的次线性伪遗憾以及预言机动作的几乎必然唯一性导致 \(\mathbb{E}[N(T)] = T + o(T)\)，大大优于独立运行的 \(JT\) 成本。本文还推导了成对策略对比的有限样本方差界。

Empirical evaluations across reward-model evaluation, multiple-choice language-model evaluation, and adaptive search policies demonstrate substantial improvements in the cost–precision frontier.

在奖励模型评估、多选语言模型评估和自适应搜索策略等方面的实证评估表明，成本-精度前沿得到了显著改善。