Search papers, labs, and topics across Lattice.
This paper introduces Tree-Coupled A/B Testing (TCAB), a novel design that enables efficient multi-policy comparison in adaptive decision-making contexts by sharing feedback among policies. By coupling policy histories through a predictable tree structure, TCAB reduces the number of required reward queries from JT to T plus a cumulative measure of tree-edge variation, achieving a conditionally optimal cost. Experimental results show that TCAB significantly enhances the cost-precision trade-off across various applications, including reward-model evaluation and adaptive search policies.
Sharing feedback among multiple policies can reduce the cost of A/B/n testing from linear to sublinear, revolutionizing how we evaluate adaptive decision-making systems.
Online platforms increasingly compare many adaptive decision policies---ranking systems, recommendation algorithms, pricing rules, and language-model agents---while each reward-bearing interaction can be costly or risky. A direct A/B/n design gives each of $J$ policies its own horizon-$T$ trajectory and therefore uses $JT$ outcomes. We introduce Tree-Coupled A/B Testing (\TCAB), an exact feedback-sharing design for arbitrary history-dependent contextual-bandit policies. At each round, a predictable tree connects the current policy histories; every parent--child context--action law is maximally coupled, and one reward is shared within each component of matched tree edges. Every policy retains exactly its standalone finite-horizon trajectory law, even though the policies are deliberately dependent. If $D_{e,t}$ records a mismatch on tree edge $e$ at round $t$, the number of reward queries satisfies the pathwise identity $N(T)=T+\sum_{t,e}D_{e,t}$ and hence equals $T$ plus cumulative tree-edge total variation in expectation. This cost is conditionally optimal among exact edge-local designs on the selected tree, and a current-round minimum-spanning tree is myopically optimal among tree designs. For fixed $J$, sublinear pseudo-regret of every policy and almost-sure uniqueness of the oracle action imply $\mathbb{E}[N(T)]=T+o(T)$, versus $JT$ for independent runs. We also obtain finite-sample variance bounds for pairwise policy contrasts. Experiments on reward-model evaluation, multiple-choice language-model evaluation, and adaptive search policies demonstrate substantial improvements in the cost--precision frontier.
