A tree-based coupling scheme lets platforms compare many adaptive policies while preserving each policy's exact trajectory law, cutting costly outcome queries from JT to T plus policy-disagreement mass and, under common no-regret conditions, often to nearly T; the method yields finite-sample variance bounds and myopically optimal tree choices under practical operational assumptions.

Main Finding

Tree-Coupled A/B Testing (TCAB) is a constructive experimental design that lets J arbitrary history-dependent contextual policies share reward-bearing interactions exactly (no marginal bias) by maximally coupling complete context–action pairs along the edges of a spanning tree chosen per round. TCAB preserves each policy’s standalone finite-horizon trajectory law while reducing the number of reward queries from JT (independent runs) to N(T) = T + sum of per-round tree-edge disagreements, so the expected query cost is T plus cumulative edge total-variation. Under natural no-regret conditions (policies concentrate on the same optimal action), the excess query cost is sublinear and E[N(T)] = T + o(T). The paper also gives finite-sample variance bounds for pairwise contrasts and shows empirical gains on language-model evaluation and adaptive search tasks.

Key Points

• Exactness and unbiasedness
  • Every policy’s marginal finite-horizon trajectory law is preserved exactly (same distribution as standalone run), so estimates and contrasts are unbiased.
  • Exactness holds despite deliberate dependence across policies, because coupling is on the full context–action pair (X, A) and reward kernels Qa(· | x).
• Coupling mechanism
  • At the start of each round t, choose a rooted spanning tree Tt (measurable w.r.t. past). Sample the root from its marginal; for each tree edge (parent p, child v) perform a parent-first maximal coupling of the child’s and parent’s complete-pair laws.
  • The tree ensures pairwise maximal couplings on edges can be glued into a joint coupling for all J policies (acyclic graph property).
  • Implementation uses a rejection-sampling primitive that requires the ability to propose contexts without consuming rewards (screen contexts), evaluate policy action probabilities on those contexts, and then request a reward only after accepting a proposal or when sharing a previously queried reward.
• Exact cost identities and optimality
  • Pathwise identity: N(T) = T + sum_{t,e} D_{e,t} where D_{e,t} is an indicator of a broken tree edge at round t. In expectation: E[N(T)] = T + sum_{t,e} E[δ_{e,t}], where δ_{e,t} is the total-variation distance between the two complete-pair laws on edge e at round t.
  • Among conditionally exact edge-local designs (those that couple only along chosen tree edges in an edgewise-maximal way), TCAB is optimal on the chosen tree. A baseline-centered star is a simple practical choice; a minimum-spanning tree (w.r.t. current edge δ’s) is myopically optimal per round.
• Regret, disagreement, and asymptotic cost
  • If each policy has sublinear pseudo-regret and the oracle optimal action is almost surely unique, pairwise disagreement rates are sublinear; hence for fixed J, E[N(T)] = T + o(T). A margin condition gives explicit rates.
  • Thus improvements grow as policies increasingly agree (e.g., nearby checkpoints, hyperparameter grid, convergent learners).
• Variance and parallelism
  • Finite-sample variance bounds are provided for pairwise policy contrasts; bounds separate contributions from edge mismatches and realized pseudo-regret.
  • The round-synchronous tree design permits parallel coupling across same-depth children and concurrent reward queries across distinct matched components.
• Practical scope & limitations
  • TCAB is most effective when candidate policies often produce identical complete context–action pairs (nearby models, similar hyperparameters, convergent learners).
  • If policies rarely agree, TCAB remains exact but yields little cost saving.
  • Operationally requires the ability to propose/evaluate contexts without consuming the expensive reward resource and to compute or sample per-policy action probabilities on proposed contexts.

Data & Methods

• Formal environment
  • Contexts Xt are i.i.d. from PX (standard Borel); for each action a, rewards are drawn from full-context kernels Qa(· | x). The model is nonparametric in the reward kernel.
  • Policies πj,t are arbitrary history-dependent stochastic kernels (black-box access suffices).
• Core algorithm (TCAB)
  • Per round: choose an Ft−1-measurable rooted spanning tree Tt; sample root’s (X,A) from its marginal; recursively maximal-couple each child to its parent by comparing the two complete-pair laws ν_{·,t}(dx,a) = PX(dx) π_{·,t}(a | history, x).
  • Parent-first maximal coupling implemented by a rejection-sampling ratio test using action probabilities; when (X,A) are equal across matched nodes, a single reward query is used and copied.
• Theoretical results
  • Proofs use maximal-coupling properties and the fact that maximal pairwise couplings on the edges of an acyclic graph can be glued to a joint law preserving all node marginals.
  • Pathwise identity for N(T) derived from the tree matching structure; expectation uses total-variation distances δ_{e,t}.
  • Optimality: conditional optimality among edge-local exact designs and myopic MST result follow from the cost identity.
  • Regret-to-cost bound: connects sublinear pseudo-regret to sublinear cumulative edge δ and thus to T + o(T) expected queries for fixed J.
  • Finite-sample variance bounds for contrasts are given (also time-varying trees and an appendix with zero-sum extension).
• Experiments
  • Tasks: reward-model evaluation, multiple-choice language-model evaluation, and an adaptive search-bandit task.
  • Benchmarks: independent A/B/n baselines with matched/full budgets.
  • Findings: substantial improvements on the empirical cost–precision frontier (i.e., for the same precision, TCAB uses fewer reward queries).

Implications for AI Economics

• Lower marginal evaluation cost
  • TCAB can substantially reduce the number of costly reward-bearing interactions (human labels, user exposures, expensive model calls) when many candidate policies agree frequently. This directly lowers the per-comparison cost of model selection and hyperparameter search.
• Faster and cheaper experimentation cycles
  • By reducing query cost and enabling safe parallelization, platforms can evaluate more checkpoints or strategies per unit budget, speeding iteration and deployment decisions.
• Incentives and market effects
  • Reduced evaluation cost lowers barriers to entry for experimentation-driven improvements (e.g., smaller teams can run more comparisons), potentially increasing innovation rate and competition in ML-enabled services.
  • Demand for human labels or expert evaluations may shift: fewer labels per round but potentially more rounds/variants tested — pricing and labor allocation for labeled feedback could change.
• Better power / variance-efficiency
  • Variance bounds and sharing of outcomes can increase statistical power for pairwise contrasts per reward query, improving decision accuracy for a given budget — useful for A/B testing infrastructure design and regulatory reporting.
• Interaction with learning dynamics
  • TCAB’s benefits grow as candidate policies concentrate (no-regret / convergent learners). Thus progress in algorithmic learning (faster convergence) feeds directly into lower evaluation costs; conversely, when policies are deliberately diverse (e.g., exploring different product designs), savings are limited.
• Implementation & operational requirements
  • Platforms need technical capability to propose contexts and evaluate policy action distributions without triggering the reward-producing interaction (screening), and to instrument per-policy action probability evaluations. These infrastructure investments are nontrivial but reusable across experiments.
• Cautions and considerations
  • If candidate policies rarely agree on full (X,A) pairs, TCAB yields little saving; the same edge total-variation diagnostics that determine cost also diagnose when TCAB is worthwhile.
  • Sharing outcomes across policy branches is done only when it does not alter any policy’s marginal law; nevertheless, platform designers should audit for unintended cross-policy interference in downstream systems (e.g., training logs, shared state) outside the modeled reward process.
  • Ethical/user-experience risks are not increased by TCAB relative to standalone runs (marginals preserved), but operational safeguards remain essential when reward queries correspond to potentially risky user exposures.

Summary takeaway: TCAB gives a practical, provably exact way to reduce costly reward queries in multi-policy comparisons by maximally coupling complete context–action pairs along a history-adaptive tree. For many-realistic regimes in ML evaluation (nearby checkpoints, convergent learners), it converts JT queries into ≈T queries asymptotically, improving the economics of model evaluation and experimentation.