Paper deep dive
Fast A/B/n Testing: Exact Multi-Policy Comparison via Tree-Coupled Feedback Sharing
Yuxiao Wen
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 93%
Last extracted: 8/14/2026, 5:14:39 AM
Summary
The paper introduces Tree-Coupled A/B Testing (TCAB), an exact feedback-sharing design for comparing multiple adaptive decision policies (contextual bandits) simultaneously. By constructing a predictable tree that connects policy histories, TCAB maximally couples parent-child context-action laws, allowing shared rewards when policies agree on a context-action pair. This reduces the total number of reward queries from JT (independent runs) to approximately T plus the cumulative total variation of tree edges, offering significant cost-precision improvements while preserving the standalone trajectory law of each policy.
Entities (6)
Relation Signals (5)
TCAB → appliesto → Contextual Bandits
confidence 95% · an exact feedback-sharing design for arbitrary history-dependent contextual-bandit policies.
TCAB → uses → Policy Tree
confidence 95% · We resolve this incompatibility with a policy tree... Our algorithm, Tree-Coupled A/B Testing (TCAB), is round-synchronous... select any tree measurable with respect to the histories
Policy Tree → enables → Maximal Coupling
confidence 90% · Pairwise couplings prescribed on the J-1 edges of an acyclic graph can always be glued into one joint law.
TCAB → optimizes → Reward Queries
confidence 90% · This cost is conditionally optimal among exact edge-local designs... The expected query cost is T plus cumulative total variation over the selected tree edges.
TCAB → compareswith → A/B/n Testing
confidence 85% · A direct A/B/n design gives each of J policies its own horizon-T trajectory... We introduce Tree-Coupled A/B Testing (TCAB)
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract: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.
Tags
Links
- Source: https://arxiv.org/abs/2608.12831v1
- Canonical: https://arxiv.org/abs/2608.12831v1
Trouble viewing inline? Open PDF directly →
Full Text
77,550 characters extracted from source content.
Expand or collapse full text
Fast A/B/n Testing: Exact Multi-Policy Comparison via Tree-Coupled Feedback Sharing Yuxiao Wen Thanks: Yuxiao Wen is with the Courant Institute of Mathematical Sciences, New York University, email: yuxiaowen@nyu.edu. Abstract 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 JTJT 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 De,tD_e,t records a mismatch on tree edge e at round t, the number of reward queries satisfies the pathwise identity N(T)=T+∑t,eDe,tN(T)=T+ _t,eD_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 [N(T)]=T+o(T)E[N(T)]=T+o(T), versus JTJT 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. Keywords: Online experimentation; A/B testing; contextual bandits; maximal coupling; adaptive policy comparison; feedback sharing. 1 Introduction Online controlled experiments are production infrastructure at major digital platforms. Google, Microsoft/Bing, and LinkedIn have described systems that support overlapping experiments and continuous product iteration (Tang et al. 2010; Kohavi et al. 2013; Xu et al. 2015). A cross-industry summit involving thirteen organizations reported that the participating organizations had collectively tested more than one hundred thousand treatment variants in the preceding year (Gupta et al. 2019). The same pressure now appears in machine-learning evaluation: product teams compare many recommender-system configurations, ranking policies, prompting strategies, and model checkpoints, while human or online feedback remains expensive. For example, the original Chatbot Arena study accumulated more than 240,000 human preference votes to compare language models (Chiang et al. 2024). A useful distinction is between reusing traffic and reusing feedback. Google’s overlapping-experiment infrastructure, for example, allows compatible experiments in different layers to share the same underlying traffic while preserving the randomization needed within each experiment (Tang et al. 2010). Our question is complementary and operates inside a multi-policy comparison: 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? This distinction matters because traffic multiplexing alone does not remove duplicated reward-bearing interactions among the alternatives in a single policy-comparison problem. The classical A/B experiment is designed for static treatments. Modern systems instead often compare policies: a policy observes the current query or user context, chooses an action, receives only the selected action’s outcome, and may update all later decisions from its 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 JTJT reward-bearing interactions. This cost is operationally important when an experimental action can reduce user experience, consume expert labels, invoke a costly model, or delay a deployment decision. There is nevertheless a large source of redundancy. Candidate policies generated by neighboring hyperparameters, model checkpoints, or business rules frequently make the same decision on the same context. When two policies realize the same complete context–action pair, they require the same conditional reward law and can therefore receive the same physical outcome. Purposefully coupling their trajectories can remove duplicated reward noise and save an interaction. The challenge is to do so without changing either policy’s adaptive trajectory distribution. 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. We therefore model a full-context reward kernel Qa(⋅∣x)Q_a(· x) and couple 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≥3J≥ 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 (Angel and Spinka 2019). We resolve this incompatibility with a policy tree. Pairwise couplings prescribed on the J−1J-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. Our algorithm, Tree-Coupled A/B Testing (TCAB), is round-synchronous. At the beginning of round t, the experiment may select any tree measurable with respect to the histories available through round t−1t-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. Adaptive policies remain sequential across rounds, as they must, while nonadaptive policies can additionally parallelize across rounds. (a) Standard A/B/C test (b) Tree-based with data sharing Figure 1: In standard A/B tests, policies are run independently and simultaneously. In TCAB, the policies are run in phases per round, which are determined by the tree, and reuse data from previous phases. The resulting guarantees are finite-horizon and model-free. Every policy trajectory has exactly its standalone law, so all values and policy contrasts are unbiased. The expected query cost is T plus cumulative total variation over the selected tree edges. This identity yields a precise design principle: a baseline-centered star is simple and makes every baseline comparison maximal, while an oracle minimum-spanning tree minimizes the current-round cost among edge-local tree designs. We emphasize that this is a myopic tree-optimality statement, not a claim of global optimality among arbitrary multi-marginal couplings or over the full adaptive horizon. 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. This makes the theory directly diagnostic: the same edge disagreements that determine cost also indicate when feedback sharing will or will not help. Contributions. Our main contributions are as follows. 1. We formulate 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 Qa(⋅∣x)Q_a(· x). 2. We introduce a round-synchronous, predictably time-adaptive version of TCAB. Maximal couplings on all selected tree edges coexist, all same-depth coupling operations and all component-level reward queries admit parallel execution, and every policy retains exactly its standalone trajectory law. 3. We prove the pathwise and expected cost identities N(T)=T+∑t=1T∑e∈EtDe,t,[N(T)]=T+∑t=1T[∑e∈Etδe,t].N(T)=T+ _t=1^T _e∈ E_tD_e,t, [N(T)]=T+ _t=1^TE\! [ _e∈ E_t _e,t ]. Within the natural class of conditionally exact edge-local designs, TCAB is optimal on every selected tree. A baseline star and a current-round minimum-spanning tree give two concrete specializations. 4. We establish a finite-sample regret-to-cost bound for predictable tree sequences. For fixed J, almost-sure uniqueness of the oracle action and o(T)o(T) pseudo-regret for every policy imply T+o(T)T+o(T) expected reward queries; a margin condition yields an explicit rate. 5. We prove finite-sample variance bounds for every pairwise policy contrast. The bounds extend to time-varying trees and isolate the roles of edge mismatches and realized pseudo-regret; a general fixed zero-sum extension is given in the appendix. 6. Across two language-model evaluation tasks and an adaptive search-bandit task, TCAB improves the empirical cost–precision trade-off relative to independent A/B/n baselines with matched or full budgets. 2 Related literature Large-scale online experimentation. Online controlled experimentation has become core infrastructure at large digital platforms. Google’s overlapping-experiment architecture was designed to run more experiments on limited traffic by allowing compatible experiments in different layers to overlap on the same users or queries (Tang et al. 2010); Microsoft/Bing and LinkedIn describe related large-scale experimentation systems and organizational challenges (Kohavi et al. 2013; Xu et al. 2015). A cross-industry summit emphasizes the scale of the resulting experimentation programs and the operational pressure for faster, more reliable decisions (Gupta et al. 2019). These systems motivate our resource question but solve a different problem: they multiplex traffic across experiments, whereas TCAB shares realized feedback across the candidate policies within one multi-policy comparison while preserving each policy’s standalone trajectory law. Artificial Replay and comparison of learning algorithms. The closest methodological work is Meng et al. 2026, which introduces Artificial Replay for comparing two context-free stochastic bandit algorithms and proves exact marginal, interaction-cost, and variance guarantees. Our setting introduces two obstacles absent from the two-policy context-free construction. First, a contextual policy selects actions after observing a query, so exact reuse requires coupling the complete context–action law rather than only an arm label. Second, for J≥3J≥ 3 distributions, all pairwise maximal couplings need not be compatible; our policy tree selects J−1J-1 pairs whose maximal couplings can be glued simultaneously. The phrase “artificial replay” is also used by Banerjee et al. 2022 for incorporating an exogenous historical data set to warm-start a bandit. That problem concerns how one learner uses historical observations, rather than how several prospective policy trajectories share newly generated feedback. Multiple comparisons, adaptive experiments, and policy selection. Classical many-to-one procedures compare several static treatments with a common control while accounting for multiplicity (Dunnett 1955). Adaptive-design work studies how observations should be allocated, or how valid inference can be maintained, under adaptively collected data (Kasy and Sautmann 2021; Hadad et al. 2021; Simchi-Levi and Wang 2025). Related work on policy comparison and selection includes safe exploration for evaluating several policies (Wan et al. 2022), high-confidence off-policy selection (Kuzborskij et al. 2021), and ranking policies from a fixed experience data set (Yang et al. 2022). These works optimize allocation or inference under a given data-generating scheme. Our objective is different: construct a joint prospective experiment in which every adaptive candidate has exactly the finite-horizon path law it would have had in isolation, but duplicated reward queries are shared whenever coupling permits. Contextual replay and off-policy evaluation. Li et al. 2011 give an exact replay evaluator for a contextual-bandit algorithm from a uniformly randomized log: a logged event is retained when the target algorithm chooses the logged action, so the retained adaptive history has the same law as an online target trajectory. Inverse-propensity, doubly robust, self-normalized, and related methods form a broader off-policy-evaluation literature (Dudík et al. 2011; Swaminathan and Joachims 2015; Wang et al. 2017; Su et al. 2020; Zhan et al. 2021). Those methods begin with an exogenous log and therefore require support, weighting, modeling, or a bias–variance compromise. In TCAB, the candidate policies are runnable and the experiment prospectively generates residual observations when policies fail to couple. Lack of overlap therefore raises the number of reward queries rather than invalidating the target policy trajectory. Data sharing and interference between learning algorithms. A distinct line of work asks what happens when algorithms in an A/B experiment share training data. Brennan et al. 2025 document “symbiosis bias” in recommendation experiments, and Li et al. 2025 analyze settings in which data sharing can alter or even reverse the ranking of two bandit algorithms. Such sharing changes what the learning algorithms observe and can therefore change the estimand. TCAB instead introduces dependence through an exact coupling: an observation is shared only on a branch for which the recipient policy’s conditional transition law remains correct. Hence cross-policy dependence is intentional and accounted for, while each individual policy’s path law is preserved. Maximal coupling, common random numbers, and multi-marginal transport. For two probability laws, maximal coupling attains the total-variation lower bound on disagreement (Thorisson 2000; Lindvall 2002); one-sided rejection constructions provide exact implementations under density-ratio access (Corenflos and Särkkä 2022). With three or more marginals, simultaneous pairwise maximality can fail (Angel and Spinka 2019). Our tree construction uses the complementary fact that prescribed pairwise couplings on the edges of an acyclic graph can always be glued, so exactly J−1J-1 strategically selected pairs can be maximal without approximation. Sharing contexts and outcomes is also related to common-random-number methods for simulation comparison (Kleijnen 1975; Nelson and Matejcik 1995; Glasserman 2003). The adaptive-policy setting is more delicate because shared randomness enters a learner’s history and changes later actions unless the correct conditional transition is maintained recursively. At a fixed round, globally minimizing the number of distinct realized context–action pairs over all J marginals can be viewed as a multi-marginal optimal-transport problem (Pass 2015; Villani 2009). We use the tree restriction for exactness, transparency, and an implementable local sampler; we do not claim to solve the unrestricted multi-marginal problem. Bandits and no-regret online learning. Our efficiency guarantees connect directly to the extensive literature on no-regret sequential decision-making. In stochastic multi-armed bandits, classical upper-confidence-bound algorithms achieve logarithmic instance-dependent regret (Auer et al. 2002), while Thompson sampling admits logarithmic instance-dependent and near-optimal worst-case regret guarantees (Agrawal and Goyal 2012; Agrawal and Goyal 2013a). No-regret guarantees extend broadly to contextual and structured settings, including contextual bandits with general policy classes (Beygelzimer et al. 2011; Agarwal et al. 2014), linear contextual bandits (Abbasi-Yadkori et al. 2011; Agrawal and Goyal 2013b), and stochastic contextual models under structural conditions such as smooth covariate effects, covariate diversity, and plentiful contexts (Perchet and Rigollet 2013; Bastani et al. 2021; Wu et al. 2020; Ghosh and Sankararaman 2022; Hanna et al. 2023; Wen et al. 2026a); see Lattimore and Szepesvári 2020 for a general treatment. Such online-learning models arise in a wide range of applications, including pricing (Kleinberg and Leighton 2003; Cohen et al. 2020), advertising (Weed et al. 2016; Wen et al. 2025; Hu et al. 2026), and search and recommendation systems (Li et al. 2010; Wen et al. 2026b). TCAB does not require the candidate policies to belong to any particular model class and treats them as black boxes: these structural assumptions are needed only to establish a particular policy’s regret rate, not for coupling exactness or the query-cost identity. The connection arises through our query-efficiency result: whenever the compared policies have sublinear pseudo-regret and increasingly concentrate on a common optimal action, their pairwise disagreement is sublinear, and TCAB requires only T+o(T)T+o(T) reward queries for any fixed number of policies, rather than the JTJT queries required by independent evaluation. Thus, advances in no-regret learning that make candidate policies converge more rapidly toward the oracle translate directly into greater feedback sharing under TCAB. 3 Problem formulation 3.1 Stochastic contextual environment Let T≥1T≥ 1 be the target horizon, =[K]A=[K] the action space, and (,ℬ)(X,B_X) a standard Borel full-context space. Contexts arrive as Xt∼PXi.i.d. over t.X_t P_X .i.d. over t. (1) For a slate, XtX_t may contain the user and all candidate-item features; changing feasible actions can likewise be encoded in XtX_t. For each a∈a , a reward query at (x,a)(x,a) returns a draw from the full-context kernel Qa(⋅∣x)Q_a(· x), with mean μa(x):=∫rQa(r∣x) _a(x):= r\,Q_a(\,dr x). Assumption 3.1 (I.i.d. stationary full-context outcomes). Conditional on the queried context–action pairs, reward queries are independent draws from their corresponding kernels Qa(⋅∣x)Q_a(· x); rejected unlabeled context proposals generate no reward and cause no carryover or interference. 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)(X,A) require the same conditional reward law. 3.2 Candidate policies and estimands Fix J≥2J≥ 2 policies indexed by ℐ:=0,1,…,J−1I:=\0,1,…,J-1\. Policy j is a sequence of measurable kernels πj,t(⋅∣h,x)∈Δ() _j,t(· h,x)∈ (A) with history Ht−1j=(Xsj,Asj,Rsj)s<tH_t-1^j=(X_s^j,A_s^j,R_s^j)_s<t; any persistent internal state affecting future decisions is included in this state. In a standalone run, Xtj∼PX,Atj∼πj,t(⋅∣Ht−1j,Xtj),Rtj∼QAtj(⋅∣Xtj).X_t^j P_X, A_t^j _j,t(· H_t-1^j,X_t^j), R_t^j Q_A_t^j(· X_t^j). (2) Define Sj(T):=∑t=1TRtj,Vj(T):=[Sj(T)],V(T):=(V0(T),…,VJ−1(T))⊤.S_j(T):= _t=1^TR_t^j, V_j(T):=E[S_j(T)], V(T):=(V_0(T),…,V_J-1(T)) . (3) For a baseline r, let θ(r)(T):=(Vj(T)−Vr(T))j≠r.θ^(r)(T):= (V_j(T)-V_r(T) )_j≠ r. (4) Independent runs spend JTJT reward queries. We seek exact horizon-T trajectories for all policies using a random total N(T)≤JTN(T)≤ JT, while preserving unbiased estimation of these values and baseline contrasts. 3.3 Operational access Assumption 3.2 (Pairwise context–action coupling access). Before requesting a reward, the experiment can draw an unlabeled x∼PXx P_X, side-effect-free sample/evaluate the relevant policy kernels at x, reject a proposal without updating either policy, and request a reward only after a context–action pair is accepted (or reuse an already queried reward after an exact match). Equivalently, the experiment can implement the pairwise maximal-coupling primitive used below. More explicitly, for an ordered parent–child pair (p,v)(p,v) at current histories (hp,hv)(h_p,h_v), the experiment must be able to (i) draw x∼PXx P_X before requesting a reward; (i) sample from and evaluate πp,t(⋅∣hp,x) _p,t(· h_p,x) and πv,t(⋅∣hv,x) _v,t(· h_v,x) without advancing either policy state; (i) reject a proposal and return the underlying query to the default workflow without updating either policy; and (iv) after acceptance, either query Qa(⋅∣x)Q_a(· x) or copy an already queried reward when the two complete pairs match. The ability to screen contexts without consuming the reward-bearing resource is the operational distinction between a context proposal and an experimental reward query. We count the latter resource. Depending on the application, it may correspond to exposing a user to an experimental action and observing a click or purchase, collecting a human preference label, invoking an expensive downstream model or tool, or obtaining another outcome that is materially more costly than evaluating the candidate policies on an unlabeled context. The number of screened proposals can also matter computationally; Section 4.2 gives its exact rejection-sampling behavior separately from the reward-query count N(T)N(T). Neither the density of PXP_X nor the reward kernel QaQ_a needs to be evaluated. What is needed is policy-probability access on a proposed context. For deterministic policies, these probabilities reduce to evaluating the policies’ chosen actions, and the coupling implementation simplifies accordingly. 4 Tree-Coupled A/B Testing Let ℱt−1F_t-1 contain all policy histories and experimental randomness revealed through round t−1t-1. At the start of round t, choose an ℱt−1F_t-1-measurable rooted spanning tree t=(ℐ,Et,rt)T_t=(I,E_t,r_t). Thus the tree may react to past data but cannot depend on unrevealed round-t information. Write pt(v)p_t(v) and dept(v)dep_t(v) for the parent and depth of a nonroot vertex v. 4.1 Conditional context–action laws and tree coupling Let :=×Z:=X×A, Ztj=(Xtj,Atj)Z_t^j=(X_t^j,A_t^j), and, conditional on policy history hjh_j, define the policy’s next complete-pair law νj,thj(dx,a):=PX(dx)πj,t(a∣hj,x). _j,t^h_j(\,dx,a):=P_X(\,dx)\, _j,t(a h_j,x). (5) For policies i,ji,j let δij,t(hi,hj):=(νi,thi,νj,thj)=12∫‖πi,t(⋅∣hi,x)−πj,t(⋅∣hj,x)‖1PX(dx). _ij,t(h_i,h_j):= TV\! ( _i,t^h_i, _j,t^h_j )= 12 _X\! _i,t(· h_i,x)- _j,t(· h_j,x) _1P_X(\,dx). (6) A maximal coupling of these two laws matches their complete pairs with probability 1−δij,t1- _ij,t. Conditional on ℱt−1F_t-1 and tT_t, TCAB samples the root from its law (5) and recursively maximally couples each child to its parent. Since the selected edges form a tree, the J−1J-1 prescribed edge couplings can be glued into a single joint law while preserving every node marginal; the formal gluing statement is proved in Appendix A. The use of the complete pair Z=(X,A)Z=(X,A) is essential. Sharing merely because two policies select the same arm can be invalid in a contextual problem: the distribution of the context attached to that arm is itself policy dependent. With the full-context reward model Qa(⋅∣x)Q_a(· x), equality of (X,A)(X,A) is exactly the event on which two policies require the same conditional reward law. 4.2 One-sided rejection implementation Every law in (5) is dominated by ρ:=PX⊗countingρ:=P_X , with density pj,thj(x,a)=πj,t(a∣hj,x).p_j,t^h_j(x,a)= _j,t(a h_j,x). Consider an oriented tree edge (p,v)(p,v) and fix the current histories (hp,hv)(h_p,h_v). A parent-first maximal coupling first draws Zp∼νp,thpZ_p _p,t^h_p and lets the child inherit this same pair with probability qpv,t(Zp):=min1,pv,thv(Zp)p,thp(Zp)=min1,πv,t(Ap∣hv,Xp)πp,t(Ap∣hp,Xp).q_pv,t(Z_p):= \! \1, p_v,t^h_v(Z_p)p_p,t^h_p(Z_p) \= \! \1, _v,t(A_p h_v,X_p) _p,t(A_p h_p,X_p) \. (7) The denominator is positive almost surely on a pair generated by the parent. The accepted mass is the overlap measure minp,thp,pv,thvρ \p_p,t^h_p,p_v,t^h_v\ρ. If the parent pair is rejected, the child must be drawn from the residual part of its own law. Operationally, repeatedly draw X∼PX,A∼πv,t(⋅∣hv,X),X P_X, A _v,t(· h_v,X), and accept the proposal with probability spv,t(X,A):=1−min1,πp,t(A∣hp,X)πv,t(A∣hv,X).s_pv,t(X,A):=1- \! \1, _p,t(A h_p,X) _v,t(A h_v,X) \. (8) The accepted residual has normalized density (pv,thv−p,thp)+δpv,t(hp,hv) (p_v,t^h_v-p_p,t^h_p)_+ _pv,t(h_p,h_v) with respect to ρ. Thus the procedure is an exact maximal coupling. The common context measure cancels from both ratios, which is why the experiment never needs to know a density for PXP_X; the reward kernel also does not enter the coupling decision. For deterministic policies, (7) reduces to an intuitive rule: the parent’s pair is inherited exactly when the child would choose the same action on the parent’s context. After a mismatch, contexts are proposed until the two current decision rules disagree in the direction required by the residual law. This is also useful operationally because model scoring or policy evaluation can often be done before committing a query to the experimental treatment. Proposition 4.1 (Exact rejection implementation and proposal overhead). Let Upv,tU_pv,t denote the number of sampled proposals before one is accepted by (8). Under Assumption 3.2, (7)–(8) implement the edge couplings used by TCAB. For an edge (p,v)(p,v) with δpv,t>0 _pv,t>0, conditional on entering the residual branch, the number of child proposals is geometric with mean 1/δpv,t1/ _pv,t. Since the residual branch itself is entered with probability δpv,t _pv,t, its unconditional expected proposal contribution is at most one: [Upv,t]=1,if δpv,t>0;0,if δpv,t=0.E[U_pv,t]= cases1,&if $ _pv,t>0$;\\ 0,&if $ _pv,t=0$. cases Hence the total expected residual-proposal overhead is at most (J−1)T(J-1)T. The proposition separates two notions of cost. Small total variation means that reward sharing is frequent, but a rare residual event can require many screened proposals conditional on occurring. Their product is controlled: the expected number of residual context proposals per active edge-round is at most one. Our theoretical objective N(T)N(T) nevertheless counts only reward-bearing experimental interactions, because those are the resource that feedback sharing is designed to reduce. 4.3 Reward inheritance, matched components, and parallelism After all context–action pairs at round t are generated, retain the tree edges on which the endpoints match and let tC_t be the resulting connected components. Equality propagates along a matched path, so every policy in a component C has the same pair ZtC=(XtC,AtC)Z_t^C=(X_t^C,A_t^C). TCAB draws one reward RtC∼QAtC(⋅∣XtC)R_t^C Q_A_t^C(· X_t^C) and assigns that same physical draw to every policy in C. Distinct components receive conditionally independent fresh rewards. Equivalently, a child inherits its parent’s reward on a matched edge and opens a new reward lineage on a mismatch. The round-synchronous order is important for adaptive policies: all policies first generate their round-t observations and then update to round t+1t+1. Within a round, however, every child at the same tree depth can be coupled in parallel once its parent pair is available, and the reward queries for distinct matched components can also be issued in parallel. For nonadaptive policies, different rounds may additionally be parallelized because there is no history dependence across t. Input: Horizon T, policies (πj)j∈ℐ( _j)_j , predictable tree rule (Ψt)t≤T( _t)_t≤ T, context sampler, reward interface Initialize H0j←∅H_0^j← for every j∈ℐj ; 1 for t=1,…,Tt=1,…,T do 2 Select t=(ℐ,Et,rt)←Ψt((Ht−1j)j∈ℐ)T_t=(I,E_t,r_t)← _t((H_t-1^j)_j ); 3 Draw Ztrt∼νrt,tHt−1rtZ_t^r_t _r_t,t^H_t-1^r_t; 4 for d=1,…,maxvdept(v)d=1,…, _vdep_t(v) do 5 In parallel over v at depth d, maximally couple ZtvZ_t^v to Ztpt(v)Z_t^p_t(v) using (7)–(8); 6 Form the matched-edge components tC_t; 7 In parallel over C∈tC _t, query one RtC∼QAtC(⋅∣XtC)R_t^C Q_A_t^C(· X_t^C) and assign it to every j∈Cj∈ C; 8 Simultaneously append (Xtj,Atj,Rtj)(X_t^j,A_t^j,R_t^j) to every policy history; 9 return (Sj(T))j∈ℐ(S_j(T))_j and the desired policy contrasts. Algorithm 1 Round-synchronous Tree-Coupled A/B Testing (TCAB) 4.4 Tree choices and when they help A star rooted at a designated baseline r is the simplest choice. 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−1J-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. We denote this specialization by TCAB.STAR. A general tree can connect similar policies through intermediate policies. If all current pairwise distances δij,t(Ht−1i,Ht−1j) _ij,t(H_t-1^i,H_t-1^j) were available, a minimum-spanning tree minimizes their sum and hence the current-round expected query cost within the edge-local tree class; Section 5 states this formally. Deterministic tie-breaking makes such a rule predictable. The guarantee is deliberately myopic: today’s joint coupling can affect cross-policy dependence in future histories, so a sequence of greedy MSTs need not be globally horizon-optimal. In practice, current conditional TV distances are rarely available exactly. Our TCAB.MST 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. For adaptive policies the pilot score can depend on the pilot history distribution and coupling, so pilot construction, random seeds, and separation from the main experiment should be reported. These two choices illustrate where the method gains most. A star is natural for product launches that compare many challengers to a deployed incumbent. An MST is natural when candidates form clusters—for example, nearby checkpoints, prompt variants, exploration parameters, or recommendation rules—because an intermediate policy can relay feedback between alternatives that are not both close to the baseline. The exact cost identity below makes this intuition quantitative: only disagreement on the selected tree edges creates additional reward queries. 5 Exactness and reward-query efficiency For e=i,j∈Ete=\i,j\∈ E_t, define De,t:=Zti≠Ztj,Nt:=number of reward queries at round t,N(T):=∑t=1TNt.D_e,t:= 1\Z_t^i≠ Z_t^j\, N_t:=number of reward queries at round t, N(T):= _t=1^TN_t. The component construction gives Nt=1+∑e∈EtDe,t,N(T)=T+∑t=1T∑e∈EtDe,tpathwise.N_t=1+ _e∈ E_tD_e,t, N(T)=T+ _t=1^T _e∈ E_tD_e,t . (9) Since every tree has J−1J-1 edges, T≤N(T)≤JTalmost surely.T≤ N(T)≤ JT surely. (10) 5.1 Exact trajectory marginals and unbiased contrasts Theorem 5.1 (Exact marginal trajectories for predictable tree sequences). Under Assumption 3.1, for every finite T,JT,J, every predictable rooted-tree sequence (t)t≤T(T_t)_t≤ T, and every collection of measurable history-dependent policies, the TCAB trajectory HTj=(Xtj,Atj,Rtj)t=1TH_T^j=(X_t^j,A_t^j,R_t^j)_t=1^T has exactly the same distribution as the standalone process (2), for every j∈ℐj . The theorem 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 (Unbiased values and baseline contrasts). If rewards have finite first moments, then [Sj(T)]=Vj(T),[Sj(T)−Sr(T)]=Vj(T)−Vr(T)E[S_j(T)]=V_j(T), [S_j(T)-S_r(T)]=V_j(T)-V_r(T) for every j,r∈ℐj,r . 5.2 Exact query cost and the scope of optimality The lower-bound statement requires a conditional notion of exactness. Marginal equality of a policy’s complete trajectory alone does not imply that its next-step law remains correct after conditioning on other policies’ histories. Definition 5.1 (Conditionally exact design). A multi-policy design is conditionally exact if, for every round t and policy j, ℒ(Ztj∣ℱt−1)=νj,tHt−1jalmost surely,L(Z_t^j _t-1)= _j,t^H_t-1^j surely, and the reward assigned to j, conditional on ℱt−1F_t-1 and Ztj=(x,a)Z_t^j=(x,a), has law Qa(⋅∣x)Q_a(· x). The design is edge-local on a rooted tree if a nonroot policy can inherit an existing reward lineage only from its parent and only when the two complete pairs coincide; otherwise the child opens a fresh reward query that may be inherited by its descendants. Theorem 5.2 (Conditional cost identity and edge-local optimality). Let δe,t:=(νi,tHt−1i,νj,tHt−1j),e=i,j∈Et. _e,t:= TV\! ( _i,t^H_t-1^i, _j,t^H_t-1^j ), e=\i,j\∈ E_t. For TCAB, [Nt∣ℱt−1]=1+∑e∈Etδe,t,[N(T)]=T+∑t=1T[∑e∈Etδe,t].E[N_t _t-1]=1+ _e∈ E_t _e,t, [N(T)]=T+ _t=1^TE\! [ _e∈ E_t _e,t ]. (11) Conditional on the same pre-round information and selected tree, every conditionally exact edge-local design has expected round-t cost at least 1+∑e∈Etδe,t1+ _e∈ E_t _e,t. Thus TCAB is conditionally optimal in that class. This theorem does not claim global instancewise optimality among arbitrary multi-marginal designs. A non-tree design may sometimes share a reward across nonadjacent policies and beat every tree. The tree restriction buys an explicit sampler, simultaneous edge maximality, and exact cost accounting. Corollary 5.2 (Baseline-centered star). For the fixed star rooted at r, [N(T)]=T+∑t=1T∑j≠r[(νr,tHt−1r,νj,tHt−1j)].E[N(T)]=T+ _t=1^T _j≠ rE\! [ TV\! ( _r,t^H_t-1^r, _j,t^H_t-1^j ) ]. (12) Within the class of conditionally exact baseline-local designs, TCAB.STAR minimizes each round’s conditional expected cost. Corollary 5.3 (Myopic MST optimality within tree designs). Conditional on ℱt−1F_t-1, suppose every pairwise distance δij,t _ij,t is available. The smallest round-t conditional expected cost among conditionally exact edge-local tree designs is 1+min∑i,j∈E() spanning treeδij,t.1+ _T spanning tree _\i,j\∈ E(T) _ij,t. (13) A predictably selected minimum-spanning tree followed by tree-maximal coupling attains this value. The result is current-round optimality; it does not establish full-horizon optimality of the greedy MST sequence. When a fixed star uses a baseline trajectory from historical logs, the leading T queries may be avoided only if the log itself has the exact standalone law required here and the policies can be replayed against the stored baseline history. This observation does not automatically extend to a changing-root adaptive tree. 5.3 Low regret implies near-one-trajectory cost Assume rewards lie in [0,1][0,1] for this subsection. Define μ∗(x):=maxa∈μa(x),Δa(x):=μ∗(x)−μa(x). _*(x):= _a _a(x), _a(x):= _*(x)- _a(x). When the maximizer is unique, let a∗(x):=argmaxaμa(x),Δ(x):=mina≠a∗(x)Δa(x).a^*(x):= _a _a(x), (x):= _a≠ a^*(x) _a(x). Policy j’s pseudo-regret is ℛj(T):=[∑t=1TΔAtj(Xtj)].R_j(T):=E\! [ _t=1^T _A_t^j(X_t^j) ]. (14) Let dj,td_j,t be the degree of j in tT_t and define the degree-weighted regret ℛdeg(T):=[∑t=1T∑j∈ℐdj,tΔAtj(Xtj)].R_ (T):=E\! [ _t=1^T _j d_j,t _A_t^j(X_t^j) ]. (15) Since dj,t≤J−1d_j,t≤ J-1, ℛdeg(T)≤(J−1)∑j∈ℐℛj(T).R_ (T)≤(J-1) _j R_j(T). (16) Theorem 5.3 (Finite-sample regret-to-cost bound). Suppose the oracle action is unique PXP_X-almost surely and define FΔ(ε):=ℙΔ(X)≤ε.F_ ( ):=P\ (X)≤ \. For every predictable tree sequence and every ε>0 >0, [N(T)]−T≤2(J−1)TFΔ(ε)+ℛdeg(T)ε.E[N(T)]-T≤ 2(J-1)TF_ ( )+ R_ (T) . (17) Consequently, if J is fixed and ℛj(T)=o(T)R_j(T)=o(T) for every j, then [N(T)]=T+o(T).E[N(T)]=T+o(T). (18) Almost-sure uniqueness is needed only to force FΔ(ε)→0F_ ( )→ 0 as ε↓0 0. Without a common tie-breaking rule, two zero-regret policies can disagree indefinitely on a positive-probability tie set. Corollary 5.4 (Margin and uniform-gap rates). If FΔ(ε)≤CεβF_ ( )≤ C ^β for all sufficiently small ε , with C,β>0C,β>0, then [N(T)]−T=O(((J−1)T)1/(β+1)ℛdeg(T)β/(β+1)),E[N(T)]-T=O\! ( ((J-1)T )^1/(β+1)R_ (T)^β/(β+1) ), (19) where the constant depends only on C and β. If Δ(X)≥Δmin>0 (X)≥ _ >0 almost surely, then [N(T)]−T≤ℛdeg(T)Δmin.E[N(T)]-T≤ R_ (T) _ . (20) 5.4 Variance reduction for policy contrasts Assume rewards lie in [0,1][0,1]. Define realized regret Lj(T):=∑t=1TΔAtj(Xtj).L_j(T):= _t=1^T _A_t^j(X_t^j). For policies i,ji,j, let Pij,tP_ij,t denote their unique path in the round-t tree tT_t and set Bij(T):=15∑t=1T[∑e∈Pij,tDe,t]+6Var(Li(T))+6Var(Lj(T)).B_ij(T):=15 _t=1^TE\! [ _e∈ P_ij,tD_e,t ]+6Var(L_i(T))+6Var(L_j(T)). (21) Theorem 5.4 (Finite-sample pairwise-contrast variance). For every i,j∈ℐi,j , Var(Sj(T)−Si(T))≤Bij(T).Var\! (S_j(T)-S_i(T) )≤ B_ij(T). (22) In particular, if the expected number of mismatches along the time-varying paths Pij,tP_ij,t is o(T)o(T) and both realized-regret variances are o(T)o(T), then T−1Var(Sj(T)−Si(T))⟶0.T^-1Var\! (S_j(T)-S_i(T) ) 0. Theorem 5.4 is the main inferential guarantee: a round contributes no reward noise to the i–j comparison whenever the entire tree path between the two policies matches. Any fixed zero-sum linear comparison can be written as a finite linear combination of pairwise contrasts; Appendix E.1 records the resulting general extension. 6 Numerical experiments This section evaluates the empirical cost–precision trade-off of TCAB using the two specializations TCAB.STAR and TCAB.MST in three settings. For every horizon and Monte Carlo replication, we run one faithful horizon-T tree experiment and record its realized reward-query cost N(T)N(T); we do not average multiple tree trajectories within a reported experimental unit. We compare against independent A/B/n testing with the full JTJT budget (AB.FULL) and against a matched-budget independent design. The latter allocates qT=⌊N(T)/J⌋q_T= N(T)/J observations or learning rounds to each policy. For history-free policies, scaling the resulting per-round estimate by T remains unbiased for the horizon-T cumulative target; for adaptive policies, the corresponding extrapolation is generally biased and is interpreted separately below. Across the three experiments, TCAB improves the cost–precision frontier while preserving the target contrasts. At matched query budgets, it reduces median contrast error and variance relative to independent A/B/n designs, detects smaller policy differences, and uses substantially fewer reward observations. The results show that STAR and MST coupling can make multi-policy comparisons practical under constrained experimental budgets. 6.1 LLM agents as nonadaptive policies RewardBench RewardBench is a benchmark for assessing whether language models correctly rank a human–preferred response above a rejected response (Lambert et al. 2025). We use all 2,985 examples in its filtered evaluation split, which span chat, difficult chat, safety, mathematical reasoning, and code, and sample examples according to weights that reproduce the benchmark’s official category–level aggregation. Each example constitutes a context X containing a prompt and a preferred–rejected response pair, and the action space is binary: A=0A=0 selects the preferred response and A=1A=1 selects the rejected response. The policies are J=12J=12 language models with complete scores in the pinned RewardBench results repository. For policy j, we convert its cached scores into the deterministic action Aj(X)=0A_j(X)=0 when it assigns the higher score to the preferred response and Aj(X)=1A_j(X)=1 otherwise, using a fixed tie rule. We then model a noisy preference observation by assigning reward R∼Bernoulli(0.9)R (0.9) when the selected response is preferred and R∼Bernoulli(0.1)R (0.1) otherwise. MMLU-Pro MMLU-Pro is a challenging multiple-choice benchmark for evaluating language understanding and reasoning across 14 academic domains, with questions containing up to ten candidate answers (Wang et al. 2024). We use its pinned test split as a finite empirical context distribution: a context X is a question together with its answer options, sampled uniformly with replacement, and the action space A=0,…,9A=0,…,9 indexes the candidate answers. We construct J=6J=6 deterministic policies from three open-weight instruction models—SmolLM2-360M-Instruct, Qwen2.5-0.5B-Instruct, and TinyLlama-1.1B-Chat—each evaluated under plain and chat-formatted prompt variants. For every model–prompt combination and question, we score the answer letters and cache the highest-scoring valid option as the policy action. The reward is R(X,A)=A=YXR(X,A)=1\A=Y_X\, where YXY_X is the correct answer, so each policy’s value equals its test-set accuracy. (a) query ratio. (b) MDE80 vs query cost. (c) contrast MSE. (d) contrast variance. (e) query ratio. (f) MDE80 vs query cost. (g) contrast MSE. (h) contrast variance. Figure 2: Query cost, inferential sensitivity, and estimation accuracy for RewardBench (top) and MMLU-Pro (bottom). Lines report medians and shaded regions report the interquartile range across pairwise policy contrasts over 500 independent runs. Lower MDE80 indicates sensitivity to smaller policy differences. The minimum detectable effect at 80% power (MDE80) is the smallest per-round difference between two policies that a two-sided 5% test detects with 80% probability under the testing procedure used in the experiment. Lower values indicate better sensitivity. Figure 2 shows that TCAB resolves smaller differences at a given reward-query budget. 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.11 1 For history-free, time-invariant policies, every edge distance is a constant δe _e, so Theorem 5.2 gives [N(T)]=T1+∑e∈EδeE[N(T)]=T\1+ _e∈ E _e\. Hence the normalized query ratio is constant in T, as observed. 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. On MMLU-Pro, the corresponding reductions are about 31% and 20%. 6.2 Adaptive online learning policies To further highlight the benefit of TCAB, we consider a benchmark with adaptive policies. By Theorem 5.3, when the policies asymptotically learn the optimal action, we are able to share most of the observations and attain [N(T)]=T+o(T)E[N(T)]=T+o(T). MSLR-Search We construct a semi-synthetic search environment from MSLR-WEB10K, a learning-to-rank dataset containing query–document relevance judgments and 136 ranking features (Microsoft Research 2010; Qin and Liu 2013). At each round, a query is sampled uniformly and ten candidate documents are drawn from its precomputed top-20 pool; the resulting document-feature vectors form the context, and the action selects one document for the top search position. Selecting document a produces a Bernoulli click whose mean is a ridge-regression relevance score, constrained to [0.05,0.95][0.05,0.95]. We compare six adaptive policies—LinUCB with exploration parameters 0.50.5 and 1.01.0, decaying ϵε-greedy with constants 0.50.5 and 2.02.0, and finite-particle linear Thompson sampling with scales 0.10.1 and 0.250.25. Because these policies update from their observed clicks, this experiment evaluates TCAB in a genuinely history-dependent setting; the semi-synthetic ridge-regression score permits accurate hindsight estimates of policy values and cumulative regret. (a) query ratio. (b) MDE80 vs query cost. (c) contrast MSE. (d) policy regret. Figure 3: Query cost, inferential sensitivity, and estimation accuracy for MSLR-Search. (d) plots the average pseudo-regret of each policy. 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 JTJT budget over the reported horizon. Plot (b) shows a widening MDE80 advantage at matched cost. For a realized tree cost N(T)N(T), the matched-budget independent baseline can advance each of the J adaptive policies for only qT=⌊N(T)/J⌋q_T= N(T)/J rounds. To display an estimate against the horizon-T cumulative target, the experiment rescales it as TSj(qT)/qTTS_j(q_T)/q_T. This extrapolation is generally biased during learning because the average reward over the first qTq_T 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. References Abbasi-Yadkori et al. [2011] Y. Abbasi-Yadkori, D. Pál, and C. Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, volume 24, 2011. Agarwal et al. [2014] A. Agarwal, D. Hsu, S. Kale, J. Langford, L. Li, and R. E. Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. In Proceedings of the 31st International Conference on Machine Learning, volume 32 of Proceedings of Machine Learning Research, pages 1638–1646. PMLR, 2014. Agrawal and Goyal [2012] S. Agrawal and N. Goyal. Analysis of thompson sampling for the multi-armed bandit problem. In Proceedings of the 25th Annual Conference on Learning Theory, volume 23 of Proceedings of Machine Learning Research, pages 39.1–39.26. PMLR, 2012. Agrawal and Goyal [2013a] S. Agrawal and N. Goyal. Further optimal regret bounds for thompson sampling. In Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics, volume 31 of Proceedings of Machine Learning Research, pages 99–107. PMLR, 2013a. Agrawal and Goyal [2013b] S. Agrawal and N. Goyal. Thompson sampling for contextual bandits with linear payoffs. In Proceedings of the 30th International Conference on Machine Learning, volume 28 of Proceedings of Machine Learning Research, pages 127–135. PMLR, 2013b. Angel and Spinka [2019] O. Angel and Y. Spinka. Pairwise optimal coupling of multiple random variables. arXiv preprint arXiv:1903.00632, 2019. Auer et al. [2002] P. Auer, N. Cesa-Bianchi, and P. Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47(2–3):235–256, 2002. doi: 10.1023/A:1013689704352. Banerjee et al. [2022] S. Banerjee, S. R. Sinclair, M. Tambe, L. Xu, and C. L. Yu. Artificial replay: A meta-algorithm for harnessing historical data in bandits. arXiv preprint arXiv:2210.00025, 2022. Bastani et al. [2021] H. Bastani, M. Bayati, and K. Khosravi. Mostly exploration-free algorithms for contextual bandits. Management Science, 67(3):1329–1349, 2021. doi: 10.1287/mnsc.2020.3605. Beygelzimer et al. [2011] A. Beygelzimer, J. Langford, L. Li, L. Reyzin, and R. E. Schapire. Contextual bandit algorithms with supervised learning guarantees. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, volume 15 of Proceedings of Machine Learning Research, pages 19–26. PMLR, 2011. Brennan et al. [2025] J. Brennan, Y. Cong, Y. Yu, L. Lin, Y. Peng, C. Meng, N. Han, J. Pouget-Abadie, and D. M. Holtz. Reducing symbiosis bias through better A/B tests of recommendation algorithms. In Proceedings of the ACM Web Conference 2025, pages 3702–3715. ACM, 2025. doi: 10.1145/3696410.3714738. Chiang et al. [2024] W.-L. Chiang, L. Zheng, Y. Sheng, A. N. Angelopoulos, T. Li, D. Li, B. Zhu, H. Zhang, M. Jordan, J. E. Gonzalez, and I. Stoica. Chatbot arena: An open platform for evaluating LLMs by human preference. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 8359–8388. PMLR, 2024. Cohen et al. [2020] M. C. Cohen, I. Lobel, and R. Paes Leme. Feature-based dynamic pricing. Management Science, 66(11):4921–4943, 2020. Corenflos and Särkkä [2022] A. Corenflos and S. Särkkä. The coupled rejection sampler. arXiv preprint arXiv:2201.09585, 2022. Dudík et al. [2011] M. Dudík, J. Langford, and L. Li. Doubly robust policy evaluation and learning. In Proceedings of the 28th International Conference on Machine Learning, pages 1097–1104, 2011. Dunnett [1955] C. W. Dunnett. A multiple comparison procedure for comparing several treatments with a control. Journal of the American Statistical Association, 50(272):1096–1121, 1955. doi: 10.1080/01621459.1955.10501294. Ghosh and Sankararaman [2022] A. Ghosh and A. Sankararaman. Breaking the T T barrier: Instance-independent logarithmic regret in stochastic contextual linear bandits. In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 7531–7549. PMLR, 2022. Glasserman [2003] P. Glasserman. Monte Carlo Methods in Financial Engineering. Springer, New York, 2003. Gupta et al. [2019] S. Gupta, R. Kohavi, D. Tang, Y. Xu, R. Andersen, E. Bakshy, N. Cardin, S. Chandran, N. Chen, D. Coey, et al. Top challenges from the first practical online controlled experiments summit. ACM SIGKDD Explorations Newsletter, 21(1):20–35, 2019. doi: 10.1145/3331651.3331655. Hadad et al. [2021] V. Hadad, D. A. Hirshberg, R. Zhan, S. Wager, and S. Athey. Confidence intervals for policy evaluation in adaptive experiments. Proceedings of the National Academy of Sciences, 118(15):e2014602118, 2021. doi: 10.1073/pnas.2014602118. Hanna et al. [2023] O. A. Hanna, L. Yang, and C. Fragouli. Contexts can be cheap: Solving stochastic contextual bandits with linear bandit algorithms. In Proceedings of the 36th Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 1791–1821. PMLR, 2023. Hu et al. [2026] Z. Hu, Y. Wen, Y. Yao, J. Zhang, and Z. Zhou. Learning to bid with unknown private values in budget-constrained first-price auctions. arXiv preprint arXiv:2605.09448, 2026. Kasy and Sautmann [2021] M. Kasy and A. Sautmann. Adaptive treatment assignment in experiments for policy choice. Econometrica, 89(1):113–132, 2021. doi: 10.3982/ECTA17527. Kleijnen [1975] J. P. C. Kleijnen. Antithetic variates, common random numbers and optimal computer time allocation in simulation. Management Science, 21(10):1176–1185, 1975. doi: 10.1287/mnsc.21.10.1176. Kleinberg and Leighton [2003] R. Kleinberg and T. Leighton. The value of knowing a demand curve: Bounds on regret for online posted-price auctions. In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., pages 594–605. IEEE, 2003. Kohavi et al. [2013] R. Kohavi, A. Deng, B. Frasca, T. Walker, Y. Xu, and N. Pohlmann. Online controlled experiments at large scale. In Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1168–1176. ACM, 2013. doi: 10.1145/2487575.2488217. Kuzborskij et al. [2021] I. Kuzborskij, C. Vernade, A. Gyorgy, and C. Szepesvari. Confident off-policy evaluation and selection through self-normalized importance weighting. In Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 640–648. PMLR, 2021. Lambert et al. [2025] N. Lambert, V. Pyatkin, J. Morrison, L. Miranda, B. Y. Lin, K. Chandu, N. Dziri, S. Kumar, T. Zick, Y. Choi, N. A. Smith, and H. Hajishirzi. Rewardbench: Evaluating reward models for language modeling. In Findings of the Association for Computational Linguistics: NAACL 2025, pages 1755–1797, 2025. Lattimore and Szepesvári [2020] T. Lattimore and C. Szepesvári. Bandit Algorithms. Cambridge University Press, Cambridge, 2020. Li et al. [2010] L. Li, W. Chu, J. Langford, and R. E. Schapire. A contextual-bandit approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pages 661–670, 2010. Li et al. [2011] L. Li, W. Chu, J. Langford, and X. Wang. Unbiased offline evaluation of contextual-bandit-based news article recommendation algorithms. In Proceedings of the Fourth ACM International Conference on Web Search and Data Mining, pages 297–306. ACM, 2011. doi: 10.1145/1935826.1935878. Li et al. [2025] S. Li, C. Wang, and J. Wang. Choosing the better bandit algorithm under data sharing: When do A/B experiments work? arXiv preprint arXiv:2507.11891, 2025. Lindvall [2002] T. Lindvall. Lectures on the Coupling Method. Dover Publications, Mineola, NY, 2002. Meng et al. [2026] H. Meng, N. Chen, and X. Gao. Design experiments to compare multi-armed bandit algorithms. arXiv preprint arXiv:2603.05919, 2026. Microsoft Research [2010] Microsoft Research. Microsoft learning to rank datasets. MSLR-WEB10K, 2010. Nelson and Matejcik [1995] B. L. Nelson and F. J. Matejcik. Using common random numbers for indifference-zone selection and multiple comparisons in simulation. Management Science, 41(12):1935–1945, 1995. doi: 10.1287/mnsc.41.12.1935. Pass [2015] B. Pass. Multi-marginal optimal transport: Theory and applications. ESAIM: Mathematical Modelling and Numerical Analysis, 49(6):1771–1790, 2015. doi: 10.1051/m2an/2015020. Perchet and Rigollet [2013] V. Perchet and P. Rigollet. The multi-armed bandit problem with covariates. The Annals of Statistics, 41:693–721, 2013. doi: 10.1214/13-AOS1101. Qin and Liu [2013] T. Qin and T. Liu. Introducing LETOR 4.0 datasets. CoRR, abs/1306.2597, 2013. URL http://arxiv.org/abs/1306.2597. Simchi-Levi and Wang [2025] D. Simchi-Levi and C. Wang. Multi-armed bandit experimental design: Online decision-making and adaptive inference. Management Science, 71(6):4828–4846, 2025. doi: 10.1287/mnsc.2023.00492. Su et al. [2020] Y. Su, M. Dimakopoulou, A. Krishnamurthy, and M. Dudik. Doubly robust off-policy evaluation with shrinkage. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 9167–9176. PMLR, 2020. Swaminathan and Joachims [2015] A. Swaminathan and T. Joachims. Counterfactual risk minimization: Learning from logged bandit feedback. In Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pages 814–823. PMLR, 2015. Tang et al. [2010] D. Tang, A. Agarwal, D. O’Brien, and M. Meyer. Overlapping experiment infrastructure: More, better, faster experimentation. In Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 17–26. ACM, 2010. doi: 10.1145/1835804.1835810. Thorisson [2000] H. Thorisson. Coupling, Stationarity, and Regeneration. Springer, New York, 2000. Villani [2009] C. Villani. Optimal Transport: Old and New, volume 338 of Grundlehren der mathematischen Wissenschaften. Springer, Berlin, 2009. doi: 10.1007/978-3-540-71050-9. Wan et al. [2022] R. Wan, B. Kveton, and R. Song. Safe exploration for efficient policy evaluation and comparison. In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 22491–22511. PMLR, 2022. Wang et al. [2024] Y. Wang, X. Ma, G. Zhang, Y. Ni, A. Chandra, S. Guo, W. Ren, A. Arulraj, X. He, Z. Jiang, T. Li, M. Ku, K. Wang, A. Zhuang, R. Fan, X. Yue, and W. Chen. Mmlu-pro: A more robust and challenging multi-task language understanding benchmark. In Advances in Neural Information Processing Systems, volume 37, 2024. Wang et al. [2017] Y.-X. Wang, A. Agarwal, and M. Dudík. Optimal and adaptive off-policy evaluation in contextual bandits. In Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 3589–3597. PMLR, 2017. Weed et al. [2016] J. Weed, V. Perchet, and P. Rigollet. Online learning in repeated auctions. In Conference on Learning Theory, pages 1562–1583. PMLR, 2016. Wen et al. [2025] Y. Wen, Y. Han, and Z. Zhou. Joint value estimation and bidding in repeated first-price auctions. arXiv preprint arXiv:2502.17292, 2025. Wen et al. [2026a] Y. Wen, Y. Han, and Z. Zhou. Optimal arm elimination algorithms for combinatorial bandits. Twenty-Ninth Annual Conference on Artificial Intelligence and Statistics, 2026a. Wen et al. [2026b] Y. Wen, Z. Hu, Y. Han, Y. Yao, and Z. Zhou. The (marginal) value of a search ad: An online causal framework for repeated second-price auctions. In Forty-third International Conference on Machine Learning, 2026b. Wu et al. [2020] W. Wu, J. Yang, and C. Shen. Stochastic linear contextual bandits with diverse contexts. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 2392–2401. PMLR, 2020. Xu et al. [2015] Y. Xu, N. Chen, A. Fernandez, O. Sinno, and A. Bhasin. From infrastructure to culture: A/B testing challenges in large scale social networks. In Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 2227–2236. ACM, 2015. doi: 10.1145/2783258.2788602. Yang et al. [2022] M. Yang, B. Dai, O. Nachum, G. Tucker, and D. Schuurmans. Offline policy selection under uncertainty. In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pages 4376–4396. PMLR, 2022. Zhan et al. [2021] R. Zhan, V. Hadad, D. A. Hirshberg, and S. Athey. Off-policy evaluation via adaptive weighting with data from contextual bandits. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 2125–2135. ACM, 2021. Appendix A Coupling preliminaries A.1 Two-marginal maximal coupling Let (,)( Z,Z) be standard Borel and let ν0,ν1 _0, _1 be dominated by ρ, with densities p0,p1p_0,p_1. Define λ(dz):=minp0(z),p1(z)ρ(dz),α:=λ(),δ:=1−α.λ(\,dz):= \p_0(z),p_1(z)\ρ(\,dz), α:=λ( Z), δ:=1-α. When δ>0δ>0, define ν~i(dz):=νi(dz)−λ(dz)δ,i∈0,1. ν_i(\,dz):= _i(\,dz)-λ(\,dz)δ, i∈\0,1\. Lemma A.1 (Canonical maximal coupling). With probability α, draw Z from λ/αλ/α and set Z0=Z1=Z_0=Z_1=Z; this branch is absent when α=0α=0. With probability δ, draw (Z0,Z1)(Z_0,Z_1) from any coupling of (ν~0,ν~1)( ν_0, ν_1); this branch is absent when δ=0δ=0. Then Zi∼νiZ_i _i and ℙ(Z0≠Z1)=δ=(ν0,ν1).P(Z_0≠ Z_1)=δ= TV( _0, _1). No coupling has a smaller disagreement probability. Proof. The marginal decomposition νi=λ+δν~i _i=λ+δ ν_i gives the required laws. The residual measures are mutually singular because their densities are supported on p0>p1\p_0>p_1\ and p1>p0\p_1>p_0\, respectively, so the residual branch cannot agree with positive probability. Also (ν0,ν1)=1−∫minp0,p1ρ=δ. TV( _0, _1)=1- \p_0,p_1\\,dρ=δ. For any coupling, the common-value submeasure is dominated by both marginals and therefore has mass at most ∫minp0,p1ρ=α \p_0,p_1\\,dρ=α. Hence ℙ(Z0≠Z1)≥δP(Z_0≠ Z_1)≥δ. See Thorisson 2000 and Lindvall 2002. ∎ Lemma A.2 (One-sided rejection sampler). Suppose samples from ν0,ν1 _0, _1 and the density ratios are available. Draw Z0∼ν0Z_0 _0. Set Z1=Z0Z_1=Z_0 with probability min1,p1(Z0)/p0(Z0) \1,p_1(Z_0)/p_0(Z_0)\. Otherwise repeatedly draw Y∼ν1Y _1 until it is accepted with probability 1−min1,p0(Y)/p1(Y),1- \1,p_0(Y)/p_1(Y)\, and set Z1=YZ_1=Y. This is a maximal coupling. The first-stage match probability is α. If δ>0δ>0, conditional on entering the residual branch, the number of ν1 _1 proposals is geometric with success probability δ and mean 1/δ1/δ; when δ=0δ=0, the branch is never entered. Proof. The accepted first-stage measure is p0(z)min1,p1(z)/p0(z)ρ(dz)=λ(dz).p_0(z) \1,p_1(z)/p_0(z)\ρ(\,dz)=λ(\,dz). A residual proposal is accepted with unnormalized density p1(z)[1−min1,p0(z)/p1(z)]=(p1(z)−p0(z))+,p_1(z) [1- \1,p_0(z)/p_1(z)\ ]=(p_1(z)-p_0(z))_+, whose total mass is δ. Thus the accepted residual has law ν~1 ν_1 and the proposal count has the stated geometric law. ∎ A.2 Tree gluing Lemma A.3 (Tree gluing lemma). Let =(ℐ,E)T=(I,E) be a finite rooted tree on a standard Borel space Z. For every directed edge e=(p(v),v)e=(p(v),v), let γe _e be a coupling of νp(v) _p(v) and νv _v. Then there is a joint coupling of (νj)j∈ℐ( _j)_j whose marginal on every edge is γe _e. In particular, maximal couplings can be attained simultaneously on all tree edges. Proof. Disintegrate γe(dzp,dzv)=νp(dzp)Ke(zp,dzv), _e(\,dz_p,\,dz_v)= _p(\,dz_p)K_e(z_p,\,dz_v), which is possible on standard Borel spaces. Draw Zr∼νrZ_r _r and then recursively draw Zv∼K(p(v),v)(Zp(v),⋅),Z_v K_(p(v),v)(Z_p(v),·), conditionally independently across siblings if desired. Induction over depth gives every node marginal νv _v, and the construction gives the prescribed edge law. Acyclicity removes compatibility constraints that can arise on graphs with cycles. ∎ Appendix B Proof of the implementation proposition Proof of Proposition 4.1. Fix a round, an oriented edge (p,v)(p,v), and the two current histories. Apply Lemma A.2 to νp(dx,a)=PX(dx)πp,t(a∣hp,x),νv(dx,a)=PX(dx)πv,t(a∣hv,x), _p(\,dx,a)=P_X(\,dx) _p,t(a h_p,x), _v(\,dx,a)=P_X(\,dx) _v,t(a h_v,x), with dominating measure PX⊗countingP_X . The common PXP_X factor cancels, yielding exactly (7) and (8). Lemma A.3 glues these edge laws into the round-t tree coupling used in Algorithm 1. The residual branch is entered with probability δpv,t _pv,t and, when positive, its conditional proposal mean is 1/δpv,t1/ _pv,t; its unconditional contribution is therefore one. Summing over at most J−1J-1 edges in each of T rounds proves the proposal bound. Reward sampling is performed only after the complete-pair coupling and therefore does not enter the acceptance ratios. ∎ Appendix C Proofs of exactness and query cost Proof of Theorem 5.1. Fix t and condition on ℱt−1F_t-1. The tree tT_t and every policy history are then fixed. By the canonical edge construction and Lemma A.3, ℒ(Ztj∣ℱt−1)=νj,tHt−1jL(Z_t^j _t-1)= _j,t^H_t-1^j (23) for every j. In particular, for measurable B⊆B and a∈a , ℙ(Xtj∈B,Atj=a∣ℱt−1)=∫Bπj,t(a∣Ht−1j,x)PX(x).P(X_t^j∈ B,A_t^j=a _t-1)= _B _j,t(a H_t-1^j,x)P_X(\,dx). Now condition further on all round-t complete pairs and their matched components. A component with common pair (x,a)(x,a) receives a fresh draw from Qa(⋅∣x)Q_a(· x), independent of the coupling randomness. Thus, for every node, ℒ(Rtj∣ℱt−1,Ztj=(x,a))=Qa(⋅∣x).L(R_t^j _t-1,Z_t^j=(x,a))=Q_a(· x). (24) Sharing the draw across a component changes cross-policy dependence but not any node’s conditional law. Equations (23)–(24) are exactly the standalone transition (2). Starting from empty histories and iterating proves equality of each complete marginal path law by induction, equivalently by uniqueness in the Ionescu–Tulcea theorem. ∎ Proof of Corollary 5.1. Theorem 5.1 gives the standalone distribution, hence expectation, of every Sj(T)S_j(T). Linearity gives the baseline-contrast identities. ∎ Proof of Theorem 5.2. Removing the mismatched edges from a tree creates exactly one more component per removed edge. Because TCAB queries one reward per component, (9) holds. Conditional on ℱt−1F_t-1, every selected edge is a maximal coupling, so [De,t∣ℱt−1]=δe,t.E[D_e,t _t-1]= _e,t. Taking conditional expectation in the pathwise identity, then summing and taking ordinary expectations, proves (11). For the lower bound, fix ℱt−1F_t-1 and consider any conditionally exact edge-local design on the same selected tree. On edge e=i,je=\i,j\, conditional exactness fixes the two node marginals as νi,tHt−1i _i,t^H_t-1^i and νj,tHt−1j _j,t^H_t-1^j. The coupling inequality therefore gives ℙ(Zti≠Ztj∣ℱt−1)≥δe,t.P(Z_t^i≠ Z_t^j _t-1)≥ _e,t. Edge locality forces a new reward lineage whenever a child mismatches its parent, so its conditional expected cost is at least 1+∑e∈Etℙ(Zti≠Ztj∣ℱt−1)≥1+∑e∈Etδe,t.1+ _e∈ E_tP(Z_t^i≠ Z_t^j _t-1)≥ 1+ _e∈ E_t _e,t. Tree gluing shows that all edgewise lower bounds can coexist, and TCAB attains them. ∎ Proof of Corollary 5.2. Apply Theorem 5.2 to the edges r,j\r,j\, j≠rj≠ r. The lower-bound class specializes to designs in which every alternative can inherit only from the baseline. ∎ Proof of Corollary 5.3. For any selected tree, Theorem 5.2 gives minimal conditional tree-local cost 1+∑e∈Eδe,t1+ _e∈ E _e,t. Minimizing this sum over spanning trees is exactly the minimum-spanning-tree problem. There are finitely many labeled trees; a deterministic lexicographic rule among minimizers makes the choice measurable in the edge weights and hence predictable. Applying the tree coupling preserves every node marginal. The argument is pointwise in the current histories and therefore establishes only the stated current-round result. ∎ Appendix D Proofs of regret-based efficiency Proof of Theorem 5.3. For history hjh_j, define the conditional nonoracle probability qj,t(hj):=∫[1−πj,t(a∗(x)∣hj,x)]PX(x).q_j,t(h_j):= _X [1- _j,t(a^*(x) h_j,x) ]P_X(\,dx). For an edge i,j\i,j\ and fixed context x, write pi,pjp_i,p_j for the two current action distributions. Their overlap includes at least the smaller mass assigned to the common oracle action, so (pi,pj) TV(p_i,p_j) =1−∑aminpi(a),pj(a) =1- _a \p_i(a),p_j(a)\ ≤1−minpi(a∗(x)),pj(a∗(x)) ≤ 1- \p_i(a^*(x)),p_j(a^*(x))\ ≤[1−pi(a∗(x))]+[1−pj(a∗(x))]. ≤[1-p_i(a^*(x))]+[1-p_j(a^*(x))]. Integrating over PXP_X gives δij,t≤qi,t(Ht−1i)+qj,t(Ht−1j). _ij,t≤ q_i,t(H_t-1^i)+q_j,t(H_t-1^j). Summing over the round-t tree and then over time yields [N(T)]−T≤[∑t=1T∑j∈ℐdj,tAtj≠a∗(Xtj)].E[N(T)]-T \! [ _t=1^T _j d_j,t 1\A_t^j≠ a^*(X_t^j)\ ]. (25) Here we used conditional exactness of TCAB to identify qj,tq_j,t with the conditional nonoracle probability of policy j. For every ε>0 >0, dj,tAtj≠a∗(Xtj)≤dj,tΔ(Xtj)≤ε+dj,tεΔAtj(Xtj).d_j,t 1\A_t^j≠ a^*(X_t^j)\≤ d_j,t 1\ (X_t^j)≤ \+ d_j,t _A_t^j(X_t^j). Because dj,td_j,t is ℱt−1F_t-1-measurable and XtjX_t^j has conditional marginal PXP_X, ∑j∈ℐ[dj,tΔ(Xtj)≤ε]=FΔ(ε)[∑jdj,t]=2(J−1)FΔ(ε). _j E\! [d_j,t 1\ (X_t^j)≤ \ ]=F_ ( )E\! [ _jd_j,t ]=2(J-1)F_ ( ). Summing over t and using (15) in (25) proves (17). For fixed J, (16) and ℛj(T)=o(T)R_j(T)=o(T) imply rT:=ℛdeg(T)/T→0r_T:=R_ (T)/T→ 0. If rT>0r_T>0, choose εT=rT _T= r_T; otherwise choose any deterministic εT↓0 _T 0. Almost-sure uniqueness and finite K imply Δ(X)>0 (X)>0 almost surely and hence FΔ(εT)→0F_ ( _T)→ 0. Divide (17) by T to obtain (18). ∎ Proof of Corollary 5.4. Under the margin condition, (17) is at most 2C(J−1)Tεβ+ℛdeg(T)ε.2C(J-1)T ^β+ R_ (T) . Balancing the two terms gives ε≍(ℛdeg(T)(J−1)T)1/(β+1), ( R_ (T)(J-1)T )^1/(β+1), which proves (19). Under a uniform gap, every nonoracle action incurs loss at least Δmin _ , so the right side of (25) is at most ℛdeg(T)/ΔminR_ (T)/ _ . ∎ Appendix E Proofs of the variance results Proof of Theorem 5.4. Fix i,ji,j and define Utij:=at least one edge in Pij,t mismatches.U_t^ij:= 1\at least one edge in P_ij,t mismatches\. Then Utij≤∑e∈Pij,tDe,t.U_t^ij≤ _e∈ P_ij,tD_e,t. (26) If Utij=0U_t^ij=0, equality propagates along the matched path, so Zti=ZtjZ_t^i=Z_t^j and Rti=RtjR_t^i=R_t^j. Define Ctij:=μ∗(Xtj)−μ∗(Xti).C_t^ij:= _*(X_t^j)- _*(X_t^i). Both endpoint contexts have conditional marginal PXP_X, hence [Ctij∣ℱt−1]=0E[C_t^ij _t-1]=0. Also Ctij=0C_t^ij=0 when Utij=0U_t^ij=0 and |Ctij|≤1|C_t^ij|≤ 1. Therefore Var(∑t=1TCtij)≤[∑t=1TUtij].Var\! ( _t=1^TC_t^ij ) \! [ _t=1^TU_t^ij ]. (27) Let tG_t enlarge ℱt−1F_t-1 by all round-t complete pairs, the tree, and the component partition, but not the reward draws. Define Etij:=Rtj−μAtj(Xtj)−Rti−μAti(Xti).E_t^ij:=\R_t^j- _A_t^j(X_t^j)\-\R_t^i- _A_t^i(X_t^i)\. Conditional on tG_t, each residual has mean zero. Thus [Etij∣t]=0E[E_t^ij _t]=0. Moreover, Etij=0E_t^ij=0 when Utij=0U_t^ij=0 and |Etij|≤2Utij|E_t^ij|≤ 2U_t^ij, giving Var(∑t=1TEtij)≤4[∑t=1TUtij].Var\! ( _t=1^TE_t^ij )≤ 4E\! [ _t=1^TU_t^ij ]. (28) Writing ℓtj:=ΔAtj(Xtj) _t^j:= _A_t^j(X_t^j), Rtj−Rti=Ctij+ℓti−ℓtj+Etij.R_t^j-R_t^i=C_t^ij+ _t^i- _t^j+E_t^ij. After summing over t, use Var(U+V+W)≤3Var(U)+Var(V)+Var(W),Var(Li−Lj)≤2Var(Li)+2Var(Lj),Var(U+V+W)≤ 3\Var(U)+Var(V)+Var(W)\, (L_i-L_j)≤ 2Var(L_i)+2Var(L_j), together with (26)–(28). This yields Var(Sj−Si)≤15∑t=1T[∑e∈Pij,tDe,t]+6Var(Li)+6Var(Lj),Var(S_j-S_i)≤ 15 _t=1^TE\! [ _e∈ P_ij,tD_e,t ]+6Var(L_i)+6Var(L_j), which is (22). ∎ E.1 General fixed zero-sum contrasts The pairwise result immediately extends to comparative linear functionals. Let S(T):=(S0(T),…,SJ−1(T))⊤,c∈ℝJ,⊤c=0,S(T):=(S_0(T),…,S_J-1(T)) , c ^J, 1 c=0, and define the corresponding target by θc(T):=c⊤V(T). _c(T):=c V(T). By Theorem 5.1, c⊤S(T)c S(T) is unbiased for θc(T) _c(T) whenever rewards have finite first moments. Theorem E.1 (Fixed zero-sum contrasts). Fix an anchor r∈ℐr . Then Var(c⊤S(T))≤(∑j≠r|cj|Bjr(T))2.Var\! (c S(T) )≤ ( _j≠ r|c_j| B_jr(T) )^2. (29) If J,cJ,c are fixed, [N(T)]−T=o(T)E[N(T)]-T=o(T), and Var(Lj(T))=o(T)Var(L_j(T))=o(T) for every policy, then Var(c⊤S(T))=o(T)Var(c S(T))=o(T). Corollary E.1 (Simple second-moment condition). Let Mj(T):=∑t=1TAtj≠a∗(Xtj).M_j(T):= _t=1^T 1\A_t^j≠ a^*(X_t^j)\. If [N(T)]−T=o(T)E[N(T)]-T=o(T) and [Mj(T)2]=o(T)E[M_j(T)^2]=o(T) for every j, then every fixed zero-sum contrast has variance o(T)o(T). Proof of Theorem E.1. Because ∑jcj=0 _jc_j=0, c⊤S(T)=∑j≠rcjSj(T)−Sr(T).c S(T)= _j≠ rc_j\S_j(T)-S_r(T)\. Center both sides and apply Minkowski’s inequality in L2L^2: Var(c⊤S(T))≤∑j≠r|cj|Var(Sj(T)−Sr(T)). Var(c S(T))≤ _j≠ r|c_j| Var(S_j(T)-S_r(T)). Theorem 5.4 gives (29). Moreover, ∑t=1T[∑e∈Pjr,tDe,t]≤[N(T)]−T. _t=1^TE\! [ _e∈ P_jr,tD_e,t ] [N(T)]-T. Thus every Bjr(T)=o(T)B_jr(T)=o(T) under the stated assumptions, and a fixed finite sum of o(T)o( T) terms has square o(T)o(T). ∎ Proof of Corollary E.1. Since rewards lie in [0,1][0,1], every gap lies in [0,1][0,1] and 0≤Lj(T)≤Mj(T).0≤ L_j(T)≤ M_j(T). Hence Var(Lj(T))≤[Lj(T)2]≤[Mj(T)2]=o(T).Var(L_j(T)) [L_j(T)^2] [M_j(T)^2]=o(T). Apply Theorem E.1. ∎