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

Date: August 14, 2026 (arXiv:2608.12831v1)

---

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. The paper introduces Tree-Coupled A/B Testing (TCAB), an exact feedback-sharing design for arbitrary history-dependent contextual-bandit policies.

The key distinction is between reusing traffic and reusing feedback. While Google's overlapping-experiment infrastructure allows compatible experiments in different layers to share the same underlying traffic, TCAB addresses a complementary question: when several candidate policies would produce the same contextual decision, can one realized outcome be used by several policies without changing the finite-horizon law of any of them?

The classical A/B experiment is designed for static treatments. Modern systems instead often compare policies that observe the current query or user context, choose an action, receive only the selected action's outcome, and update all later decisions from their adaptive history. To compare J candidate policies over the same target horizon T, the direct A/B/n design runs J independent trajectories and uses JT reward-bearing interactions.

The setting assumes i.i.d. contexts Xt ∼ PX over time, an action space A = [K], and a full-context reward kernel Qa(· x) with mean µa(x). The full-context specification allows the selected action's outcome to depend on the entire user/slate state and guarantees that two policies matching on (X, A) require the same conditional reward law.

Policy j is a sequence of measurable kernels πj,t(· h, x) ∈ Δ(A) with history Ht−1 j = (Xs j, As j, Rs j)s<t. In a standalone run:

• Xt j ∼ PX

• At j ∼ πj,t(· Ht−1 j, Xt j)

• Rt j ∼ QAt j(· Xt j)

The estimands are Sj(T) = Σ Rt j, Vj(T) = E[Sj(T)], and baseline contrasts θ(r)(T) = (Vj(T) − Vr(T))j≠r.

"Contextuality makes this challenge fundamentally different from replaying an arm label. Even under i.i.d. contexts, the contexts attached to the observations of a selected action depend on the policy's selection rule and history. Moreover, in applications such as ranked slates, auctions, and recommendation, the outcome of choosing one item may depend on the entire displayed slate or user state, not only on the chosen item's local feature."

The paper therefore models a full-context reward kernel and couples the policies' complete one-step context–action laws. A maximal coupling makes two complete pairs equal with the largest probability permitted by their total-variation distance; the shared branch uses one reward and the residual branch opens a fresh query.

Moving from two policies to J ≥ 3 creates a second obstruction: Pairwise maximal couplings need not be jointly compatible: in general there is no single coupling that maximizes the equality probability of every pair simultaneously. The paper resolves this with a policy tree: "Pairwise couplings prescribed on the J − 1 edges of an acyclic graph can always be glued into one joint law. A broken edge starts a new reward lineage; matched edges transmit the same context, action, and reward. Consequently, the number of reward queries is exactly one plus the number of broken edges in each round."

TCAB is round-synchronous. At the beginning of round t, the experiment selects any tree measurable with respect to histories available through round t−1. It then samples the root, traverses the tree by depth, queries one outcome per matched-edge component, and updates all policies simultaneously. "This outer-loop-over-time formulation directly permits predictable, time-adaptive trees. It also exposes practical parallelism: all children at the same depth can be coupled concurrently once their parents are available, and the reward queries for distinct components can be issued concurrently."

For an oriented tree edge (p, v), a parent-first maximal coupling first draws Zp from the parent's law and lets the child inherit this same pair with probability:

qpv,t(Zp) = min 1, πv,t(Ap hv, Xp) / πp,t(Ap hp, Xp)

If the parent pair is rejected, the child is drawn from the residual part of its own law via rejection sampling with acceptance probability:

spv,t(X, A) = 1 − min 1, πp,t(A hp, X) / πv,t(A hv, X)

The common context measure cancels from both ratios, so the experiment never needs to know a density for PX; the reward kernel also does not enter the coupling decision.

Proposition 4.1 establishes that the expected residual-proposal overhead is at most (J−1)T: Since the residual branch itself is entered with probability δpv,t, its unconditional expected proposal contribution is at most one.

"Under Assumption 3.1, for every finite T, J, every predictable rooted-tree sequence (Tt)t≤T, and every collection of measurable history-dependent policies, the TCAB trajectory HT j = (Xt j, At j, Rt j)t=1 T has exactly the same distribution as the standalone process (2), for every j ∈ I."

This is a complete path-law statement: Policies are dependent across j, but no individual policy can statistically distinguish its TCAB trajectory from a standalone run.

Corollary 5.1: If rewards have finite first moments, then E[Sj(T)] = Vj(T) and E[Sj(T) − Sr(T)] = Vj(T) − Vr(T) for every j, r ∈ I.

The pathwise identity is:

N(T) = T + Σt Σe∈Et De,t

where De,t = 1 Zt i ≠ Zt j for edge e = i, j. The expected cost is:

E[N(T)] = T + Σt E[Σe∈Et δe,t]

where δe,t is the total-variation distance between the two policies' conditional context–action laws.

Within the natural class of conditionally exact edge-local designs, TCAB is optimal on every selected tree. The lower bound states that every conditionally exact edge-local design has expected round-t cost at least 1 + Σe∈Et δe,t.

Corollary 5.2 (Baseline-centered star): For the fixed star rooted at r, E[N(T)] = T + Σt Σj≠r E[TV(νr,t, νj,t)]. Within the class of conditionally exact baseline-local designs, TCAB.STAR minimizes each round's conditional expected cost.

Corollary 5.3 (Myopic MST optimality): The smallest round-t conditional expected cost among conditionally exact edge-local tree designs is 1 + min over spanning trees of Σ δij,t. A predictably selected minimum-spanning tree followed by tree-maximal coupling attains this value. The result is current-round optimality, not full-horizon optimality.

Assuming rewards lie in [0,1], define the oracle action a*(x) = arg max µa(x), the gap ∆(x) = min a≠a* ∆a(x), and F∆(ε) = P ∆(X) ≤ ε. Let Rdeg(T) be the degree-weighted regret. Then:

"For every predictable tree sequence and every ε > 0, E[N(T)] − T ≤ 2(J−1)T F∆(ε) + Rdeg(T)/ε."

Consequently, if J is fixed and Rj(T) = o(T) for every j, then E[N(T)] = T + o(T). This means TCAB requires only T + o(T) reward queries for any fixed number of policies, rather than the JT queries required by independent evaluation.

Corollary 5.4: If F∆(ε) ≤ Cε β, then E[N(T)] − T = O(((J−1)T) 1/(β+1) Rdeg(T) β/(β+1)). If ∆(X) ≥ ∆min > 0 almost surely, then E[N(T)] − T ≤ Rdeg(T)/∆min.

For policies i, j, let Pij,t denote their unique path in the round-t tree and define:

Bij(T) = 15 E[Σt Σe∈Pij,t De,t] + 6 Var(Li(T)) + 6 Var(Lj(T))

where Lj(T) is realized regret. Then:

Var(Sj(T) − Si(T)) ≤ Bij(T)

In particular, if the expected number of mismatches along the time-varying paths Pij,t is o(T) and both realized-regret variances are o(T), then T-1 Var(Sj(T) − Si(T)) → 0.

A general fixed zero-sum contrast extension is given in Theorem E.1: Var(c T S(T)) ≤ (Σ j≠r cj √Bjr(T))2.

• TCAB.STAR: A star rooted at a designated baseline r. "It makes every baseline–alternative pair maximal and has depth one, so all alternatives can be processed in parallel after the baseline pair is available. Its cost, however, charges disagreement with the baseline J − 1 times; it is therefore most attractive when the incumbent policy is representative of the alternatives or when baseline-versus-alternative contrasts are the main inferential targets."

• TCAB.MST: If all current pairwise distances were available, a minimum-spanning tree minimizes their sum and hence the current-round expected query cost within the edge-local tree class. In practice, the implementation "uses pilot data or a simulator to estimate a fixed pairwise similarity score—for example, average complete-pair mismatch over pilot trajectories—constructs the corresponding MST, and freezes it before the main experiment."

RewardBench is a benchmark for assessing whether language models correctly rank a human-preferred response above a rejected response. The paper uses all 2,985 examples in its filtered evaluation split. The policies are J = 12 language models with complete scores in the pinned RewardBench results repository. Each policy deterministically selects the response it scores higher, and reward is Bernoulli(0.9) for preferred and Bernoulli(0.1) otherwise.

Results: "Both TCAB.STAR and TCAB.MST achieve cumulative mean-squared error (MSE) and variance comparable to AB.FULL, and substantially smaller than independent A/B/n runs with matched budgets, while using about 80% and 40% of the full query budget on RewardBench and MMLU-Pro, respectively. On RewardBench, the reported median contrast MSE and variance reductions relative to matched-budget A/B/n are about 67% for TCAB.MST and 59% for TCAB.STAR."

MMLU-Pro is a multiple-choice benchmark with questions containing up to ten candidate answers. The paper constructs J = 6 deterministic policies from three open-weight instruction models (SmolLM2-360M-Instruct, Qwen2.5-0.5B-Instruct, TinyLlama-1.1B-Chat), each under plain and chat-formatted prompt variants. The reward is R(X, A) = 1 A = YX, so each policy's value equals its test-set accuracy.

Results: On MMLU-Pro, the corresponding reductions are about 31% and 20% for TCAB.MST and TCAB.STAR, respectively, relative to matched-budget A/B/n.

A semi-synthetic search environment from MSLR-WEB10K. At each round, a query is sampled uniformly and ten candidate documents are drawn from its precomputed top-20 pool. The action selects one document for the top search position, and selecting document a produces a Bernoulli click whose mean is a ridge-regression relevance score constrained to [0.05, 0.95]. Six adaptive policies are compared: LinUCB with exploration parameters 0.5 and 1.0, decaying ε-greedy with constants 0.5 and 2.0, and finite-particle linear Thompson sampling with scales 0.1 and 0.25.

Results: Consistent with Theorem 5.3, the normalized query cost decreases as the adaptive policies' per-round regrets fall, from roughly 80% toward 50% of the full JT budget over the reported horizon. The matched-budget independent baseline is generally biased during learning because the average reward over the first qT rounds need not equal the average reward over the first T rounds; the same issue does not arise for the exact horizon-T TCAB trajectory.

1. Formulation of exact finite-horizon comparison of J arbitrary history-dependent, possibly randomized contextual policies under i.i.d. full contexts and nonparametric full-context reward kernels.

2. Introduction of a round-synchronous, predictably time-adaptive TCAB version with maximal couplings on all selected tree edges, parallel execution, and exact standalone trajectory laws.

3. Proof of pathwise and expected cost identities N(T) = T + Σ De,t, with conditional optimality among exact edge-local designs on every selected tree.

4. Finite-sample regret-to-cost bound showing T + o(T) expected reward queries for fixed J with sublinear pseudo-regret.

5. Finite-sample variance bounds for pairwise policy contrasts, extending to time-varying trees and fixed zero-sum contrasts.

6. Empirical improvements in cost–precision trade-off across two language-model evaluation tasks and an adaptive search-bandit task.

"The method is most useful when candidate policies are related rather than arbitrary. Examples include neighboring model checkpoints, nearby hyperparameter settings, alternative ranking or recommendation rules that agree on most users, and learning algorithms that increasingly concentrate on the same good actions. In the first regime, the relevant tree-edge total-variation distances are small from the outset; in the second, our regret analysis shows that the excess query cost can vanish relative to T. Conversely, if candidate policies almost never agree on their complete context–action pairs, TCAB remains exact but offers little query saving."

Based on the TCAB paper, here are specific improvements for AI systems and what the improved systems can do:

Improvement: Implement TCAB's tree-coupled feedback-sharing mechanism in AI evaluation pipelines that compare multiple model variants (e.g., different checkpoints, hyperparameter settings, or prompt strategies).

What the improved system can do: Evaluate J candidate policies over horizon T using T + o(T) reward queries instead of JT queries—a near-linear reduction. For example, comparing 12 language models on RewardBench used 40-80% fewer queries while maintaining comparable MSE and variance to full independent evaluation.