acceptodds
Under review as a conference paper at ICLR 2027

Fast A/B-Testing: Efficient Policy Evaluation via Tree-Coupled Feedback Sharing

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. The standard recipe is a direct A/B/n test, which runs each of candidate policies over an independent -horizon and therefore uses outcomes. We introduce Tree-Coupled A/B Testing (TCAB), an exact feedback-sharing design for reducing the outcome usage while preserving the marginal trajectories. At a high level, the policies are associated to a tree structure and are executed by any topological order. The observed outcome is shared along an edge when the two policies on this edge can be coupled. Every policy retains exactly its standalone finite-horizon trajectory law, even though the policies are deliberately dependent. If records a mismatch on tree edge at round , the number of outcomes satisfies the pathwise identity . This cost is conditionally optimal for the selected tree, and we propose a heuristic for empirically finding the optimal tree. For fixed , sublinear pseudo-regret of every policy can imply . We also obtain finite-sample variance bounds for pairwise policy contrasts. Experiments on language-model evaluation and adaptive bandit policies demonstrate substantial improvements—around 20-50% outcome save and improved policy evaluation precision.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Policy evaluation, statistical testing, sample efficiency, AB testing

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_WeEtOpenReview ↗
Rating
4(+1)
Confidence
2
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies how to compare multiple adaptive policies while reducing the number of expensive reward observations. The paper proposes Tree-Coupled A/B Testing, that organizes candidate policies into a given tree and shares observations between connected policies according to the tree structure. The key insight is that candidate policies often behave similarly, that they can share an observed outcome whenever their context–action distributions can be coupled. The paper establishes theoretical guarantees for the expected reward-query cost and the expected proposal overhead.

Critical strengths

The topic studied is useful and of importance to applications.

The algorithm is elegent itself.

The authors made an effort to answer potential questions that reviewers may raise. This draft is quite complete from my viewpoint.

This draft is also clearly written.

Critical weaknesses

I found a potential flaw in the design of this current algorithm, and I wish the authors can TRY to improve the design during the discussion phase.

  1. The algorithm itself adds latency to the A/B test, compared with standard A/B tests, policies are run independently and simultaneously. This may deserves few sentences of discussion.

  2. The expectation of Proposal Overhead is discussed but it does not control the worst-case number of proposals or the tail latency. We know Proposal Overhead is related to \delta. Let \delta be very small but strictly larger than zero, once enter the residual branch (even though the chance is small but still no zero), the algorithm can get stuck at this step.

  3. The optimal fixed tree, and regret bound both suggest to use edges with small \delta, but the chances of getting stuck at residual branch may increase. There seems to be a trade-off between reward-query complexity and tail latency under the current desgin. Perhaps the authors could propose alternatives to the current residual branch, such as truncation, early stopping with estimation, or sampling contexts according to policy disagreement.

Questions for authors

See above.

3 comments

We sincerely appreciate the reviewer's positive feedback and thoughtful concerns and questions raised in this review. We have uploaded a revised PDF submission (revised parts in blue) and hope to answer the questions below:

W1. Additional delays compared to standard A/B tests.

We agree that this deserves a few sentences of discussion. In the revision, we add a discussion on the sampling overhead and its delay in Section 4 and a potential remedy, and then we refer to Appendix B for more details. In Appendix B, we include a remark on asynchronous implementation (which is important to unblock the policies on the tree) at the end of page 16. In Figure 5, we plot the distribution of the run times of our algorithms and compare against the standard A/B; our original TCAB (with the asynchronous implementation) is very close to the standard A/B test up to machine measurement errors and hardware variance.

W2. The tail of overhead count.

This is an excellent and important point! In the revision, we add a detailed discussion and analysis about the proposal overhead in Section 4, below Proposition 4.1. In particular, we give explicit dependency for the overhead variance on the policy TV δij,t\delta_{ij,t}. This rate implies that the variance scales inversely in the TV (as the policies saturate toward the same set of optimal actions); but the expected overhead remains 1. Then we add an impossibility result to illustrate that this variance is somewhat binding for maximal-coupling sampler under the single-exposure condition (that each context arrival can only be used for one reward query, which matches many real-world applications).

Finally, to remedy for this variance, we provide analysis and extensive experiments on an alternative Relaxed-coupling sampler. The relaxed sampler takes the insight from the impossibility result above and achieves zero variance by forfeiting maximality: it tries to use a new sample for the child first, whereas the maximal sampler tries to inherit from the parent first and only uses a new sample afterwards. More details and experiments are provided in Appendix B (Figure 4,5).

In a word, the alternative successfully controls the tail of the overhead count at the expenses of less reward-query-saving, but our original sampler was already good enough in terms of cumulative run time and estimation errors, because (1) for nonadaptive policies, the TV is constant; (2) for adaptive policies, they do not saturate to be identical within our horizon. If they do saturate, we believe the propose alternative in Appendix B would be a balanced solution, with guaranteed bounded variance.

W3. The trade-off between reward savings and tail latency.

To control the tail when the TV is small, we propose the relaxed sampler above and also include the truncation and a slack heuristic in Appendix D. The experiments in Figure 4, 5, and 7 indicate clear Pareto curves for the trade-off for all three datasets we use, for each of the three alternatives respectively.

We did not test the reviewer’s proposal on sampling contexts according to the policy disagreement, because it would require us to sample from X∼d(X)δijPX(X)X\sim \frac{d(X)}{\delta_{ij}}P_X(X) where d(X)=TV(πi(⋅∣X)∥πj(⋅∣X))d(X) = TV(\pi_i(\cdot|X)\|\pi_j(\cdot|X)) and δij=EX[d(X)]\delta_{ij}=\mathbb{E}_X[d(X)] (please correct us if we misunderstood the proposed idea). Using rejection sample, even when we know d(X)d(X), we would require 1/δij1/\delta_{ij} context proposals from PXP_X on average for such a sample from the new distribution, which does not fix the overhead issue.


We truly appreciate the reviewer’s feedback, observations, and thoughtful questions. We are more than happy to discuss any question or unclarity further.

I’m very happy with the relaxed coupling sampler. The complete pipeline now accommodates a broad range of situations, and I’m willing to raise my score. Just one minor comment: the text in Figure 5 is too small to read.

We sincerely appreciate the reviewer's positive feedback, and we will make Figure 5 into 2 row (MST & STAR) by 3 col for better visualization in the next revision.

Reviewer_xXCvOpenReview ↗
Rating
2(+1)
Confidence
2
Informativeness
2
Presentation
2(+1)
Soundness
2
Read review
Paper summary

This paper studies the sample-efficient online evaluation and comparison of J≥2J \ge 2 adaptive contextual bandit policies over a horizon TT in a stationary environment with i.i.d. contexts and nonparametric reward kernels. It proposes Tree-Coupled A/B Testing, a round-synchronous protocol that arranges the policies on a predictable directed tree at each round t and couples each parent-child edge (i,j)∈Et(i,j) \in E_t by running a one-sided maximal-coupling rejection sampler on the joint context-action space X×A\mathcal{X} \times \mathcal{A} (sharing the parent's context, action, and observed reward on acceptance, and drawing fresh context-action proposals from the child's law until acceptance on the residual branch, with rejected contexts routed out of the experiment). Under this model, the paper proves that each policy's marginal trajectory distribution matches its standalone execution, that the expected number of reward queries per round is 1+∑e∈Etδe,t1 + \sum_{e \in E_t} \delta_{e,t} where δij,t\delta_{ij,t} is the conditional joint total variation distance, and that when all policies have sublinear cumulative pseudo-regret and optimal actions are almost surely unique, the expected total reward queries scale as T+o(T)T + o(T) while pairwise policy-contrast variances scale as o(T)o(T) when realized regret variances are also sublinear. Experiments evaluate star (TCAB.STAR) and minimum-spanning-tree (TCAB.MST) topologies on static LLM benchmarks and a semi-synthetic contextual bandit benchmark

Critical strengths
  • Coherent tree-structured coupling framework with sound finite-sample proofs (Appendices B–F). Conditional on the pre-round history Ft−1\mathcal{F}_{t-1} and for predictable tree choices, the measure-theoretic gluing of pairwise maximal couplings along a tree (Lemma B.3), the connected-component identity for expected reward queries E[Nt∣Ft−1]=1+∑e∈Etδe,t\mathbb{E}[N_t \mid \mathcal{F}_{t-1}] = 1 + \sum_{e \in E_t} \delta_{e,t} (Theorem 5.3), the degree-weighted small-gap split bounding edge TV distances via cumulative pseudo-regret (Theorem 5.5 and Corollary 5.6), and the matched-path martingale difference decomposition for policy-contrast variance (Theorem 5.7) are mathematically clean and correct.
Critical weaknesses
  • Mismatch between the joint context-action rejection sampler, repeatable-context evaluation interfaces, and synchronous user-routing latency as δij,t↓0\delta_{ij,t} \downarrow 0 (Sections 3.2 and 4; Proposition 4.1).

    • Because every candidate policy observes contexts from the same marginal distribution PXP_X (Eq. 3.2), the joint context–action total variation distance in Equation (4.2) is equal to the expected conditional action-space total variation distance: δij,t(hi,hj)=TV(νi,thi,νj,thj)=EX∼PX[TV(πi,t(⋅∣hi,X), πj,t(⋅∣hi,X))].\delta_{ij,t}(h_i,h_j) = \mathrm{TV}\left(\nu_{i,t}^{h_i}, \nu_{j,t}^{h_j}\right) = \mathbb{E}_{X \sim P_X}\left[\mathrm{TV}\left(\pi_{i,t}(\cdot \mid h_i, X),\, \pi_{j,t}(\cdot \mid h_i, X)\right)\right]. Whenever the evaluation environment allows querying multiple actions at the same context Xt∼PXX_t \sim P_X, one can simply feed the same context XtX_t to all JJ policies and maximally couple the finite KK-action distributions πj,t(⋅∣Ht−1j,Xt)\pi_{j,t}(\cdot \mid H_{t-1}^j, X_t) along the edges of Tt\mathcal{T}_t in O(K)O(K) arithmetic. That direct conditional coupling preserves every policy's standalone marginal trajectory law, achieves the exact same conditional mismatch probability δij,t\delta_{ij,t}, expected reward-query cost, regret-to-cost bound, and contrast-variance bound, and requires zero rejected context proposals.
    • Conversely, in a physical user-routing setting where each arriving user can receive only one action (necessitating fresh user draws upon disagreement), TCAB's classical one-sided rejection sampler (Lemma B.2, Eqs. 4.4–4.5) exhibits diverging proposal-screening variance in the low-disagreement regime δij,t↓0\delta_{ij,t} \downarrow 0: although the branch-averaged mean proposal count is E[Uij,t∣Ft−1]=1{δij,t>0}\mathbb{E}[U_{ij,t} \mid \mathcal{F}_{t-1}] = \mathbf{1}\{\delta_{ij,t} > 0\} (Proposition 4.1), its conditional variance is Var(Uij,t∣Ft−1)=2δij,t−2→∞\mathrm{Var}(U_{ij,t} \mid \mathcal{F}_{t-1}) = \frac{2}{\delta_{ij,t}} - 2 \to \infty as δij,t↓0\delta_{ij,t} \downarrow 0. Conditional on entering the residual branch (probability δij,t>0\delta_{ij,t} > 0), the child policy must screen and reject an average of 1δij,t−1\frac{1}{\delta_{ij,t}} - 1 arriving user contexts before accepting one, stalling the round-synchronous barrier in Algorithm 1 (line 7). Moreover, citing Corenflos & Särkkä (2022) on page 3 (lines 133–134) as justification for this rejection step is misleading, as Corenflos & Särkkä (2022, Section 1) specifically point out this O(1/δ)O(1/\delta) runtime-variance blowup of Thorisson's classical maximal rejection sampler and construct a different, dominating-proposal sampler to avoid it.
  • Incremental analytical pipeline relative to Meng, Chen, & Gao (2026) and imprecise main-text theorem statements and cost accounting (Sections 5.1–5.4).

    • Beyond gluing one-step maximal couplings along a tree (Lemma B.3), the paper's two primary theoretical guarantees, i.e., bounding excess interaction cost via expected suboptimal arm pulls (Theorem 5.5) and bounding policy-contrast variance via coupled reward-noise cancellation plus regret variance (Theorem 5.7), closely follow the conceptual and analytical framework of Meng, Chen, & Gao (2026, Theorems 3 and 5), combined with a standard Tsybakov margin split. While Meng et al. (2026) is cited in Section 2 as the closest predecessor, the paper does not sufficiently compare its theorem-level proof mechanisms against theirs.
    • Several statements in the main text also omit assumptions required by their proofs or conflict with the experimental accounting: (i) Theorem 5.1 states marginal exactness for "every policy-tree sequence {Tt}\{\mathcal{T}_t\}," omitting the predictability requirement (Tt∈Ft−1\mathcal{T}_t \in \mathcal{F}_{t-1}) used in Appendix C (lines 737–740); (ii) the asymptotic claim Var(Sj(T)−Si(T))=o(T)\mathrm{Var}(S_j(T) - S_i(T)) = o(T) in Theorem 5.7 (p. 7, lines 371–373) omits the inherited assumptions of fixed JJ and almost-sure uniqueness of a∗(X)a^*(X) from Theorem 5.5 (without uniqueness, two zero-regret policies pulling distinct optimal arms have Bij(T)=TB_{ij}(T) = T and Θ(T)\Theta(T) contrast variance); and (iii) Section 5.2 (lines 299–301) states that reconstructing the root trajectory from offline logs shaves the linear term TT in TCAB.STAR, whereas Corollary 5.4, Footnote 3, and Figure 2 all retain the +T+T root cost.
Questions for authors
  1. In the repeatable reward interfaces used by RewardBench, MMLU-Pro, and MSLR-Search, how does TCAB compare with sharing a fresh context across all policies and coupling their action laws directly? For the adaptive benchmark, please compare both reward-query cost and contrast variance, since the induced joint history laws can differ.
  2. Beyond the expected proposal count, what are the proposal-count or waiting-time quantiles when edge disagreement rates are small? How does round-synchronous execution affect the practical tradeoff between screening traffic and reward-query savings?
  3. Does the TCAB.STAR experiment include the historical root collection cost, as Footnote 3's formula indicates? If a separate logged-root variant is intended, what assumptions on log generation, selection, and residual sampling access preserve exact marginal trajectories?
  4. Section 2 identifies Meng, Chen, & Gao (2026) as the closest methodological predecessor. Could the paper directly compare Theorems 5.5 and 5.7 with that work's cost and variance guarantees, distinguishing its shared-reward-stack construction from the present roundwise tree coupling?
5 comments

We sincerely appreciate the reviewer's feedback and thoughtful concerns and questions raised in this review. We have uploaded a revised PDF submission (revised parts in blue) and hope to answer the questions below:

W1. Repeatable-context has a better sampler.

We fully agree with the reviewer on this point. If one context can be used for repeated reward queries (which we call multi-exposure in the revision), the shared-context sampler achieves every desired property without rejection. In this work, we hoped to develop an algorithm that works and gain advantages under the single-exposure scenarios, while remaining applicable under other scenarios, which led to the current results. We clarify our emphasis in contributions and Remark 3.3 in the revision. For a complete study, we also implement and test this algorithm in Appendix E (Figure 8), which gives improved reward savings and comparable MSE to our algorithms, when multi-exposure is allowed. We do respectfully insist that single-exposure is the common case in practice, making it incomparable in general.

We add a more detailed discussion and analysis about the proposal overhead in Section 4, below Proposition 4.1. As the reviewer mentions, the variance scales inversely in the TV (as the policies saturate toward the same set of optimal actions); the expected overhead remains 1. We add an impossibility result to illustrate that this variance is somewhat binding for maximal-coupling sampler under the single-exposure condition.

To alleviate this potentially unbounded TV, we provide analysis and extensive experiments on an alternative Relaxed-coupling sampler. The relaxed sampler takes the insight from the impossibility result above and achieves zero variance by forfeiting maximality: it tries to use a new sample for the child first, whereas the maximal sampler tries to inherit from the parent first and only uses a new sample afterwards. More details and experiments are provided in Appendix B (Figure 4,5). In a word, the alternative successfully controls the tail of the overhead count at the expenses of less reward-query-saving, but our original sampler was already good enough in terms of cumulative run time and estimation errors, because (1) for nonadaptive policies, the TV is constant; (2) for adaptive policies, they do not saturate to be identical within our horizon. If they do saturate, we believe the propose alternative in Appendix B would be a balanced solution, with guaranteed bounded variance.

W2. Missed-out assumption, incremental proofs.

We deeply appreciate the reviewer for pointing out the mistake of missing out an assumption on Theorem 5.1 and 5.7 respectively. We have added “predictable” in Theorem 5.1 and the uniqueness assumption in Theorem 5.7 (which was used when we invoke Theorem 5.5 in the proof).

We would like to clarify that, in Section 5.2, “reconstructing the root trajectory from offline logs” was meant to be a remark that practitioners can possibly try for more saving in TCAB.STAR. It is independent from our theory or experiments throughout. We have made it a footnote to avoid this confusion in the revision.

On comparison to Meng et al. (2026), we thank the reviewer for this observation. We agree that our results share the high-level intuition of theirs: convergence to optimal decisions leads to less queries (under appropriately designed feedback sharing) and variance reduction. We are happy to discuss with the reviewer and add the following theorem-level comparisons in the next revision.

  • For Theorem 5.5, Meng et al. derive the cost bound from arm-wise replay counts, whereas our analysis uses an edge-wise TV cost identity, a contextual margin decomposition, and degree-weighted regret to accommodate multiple policies and time-varying trees.
  • For Theorem 5.7, Meng et al. establish asymptotic variance reduction through a covariance decomposition based on shared reward stacks and stopping times. In contrast, we obtain a finite-sample bound for arbitrary policy pairs using round-wise martingale differences that vanish whenever their connecting tree path shares feedback. We also note that Meng et al. explicitly lists the contextual settings as an open problem, because (context, action) overlap is rare, and their approach of stacking observations and replay cannot apply. By contrast, we introduce a tree-gluing coupling to make J>2J>2 possible, and instantaneous sampling and coupling to make contextual sharing feasible.

[Please kindly see next for our responses to questions]

Q1. Repeatable-context.

Please kindly see our response to W1 and Appendix E in the revision. The variance plot is mostly the same as the MSE plot in Figure 8, since all the algorithms are exact and exhibit no bias (except the truncation variants), so we did not include the variance plot purely for the sake of redundancy.

Q2. Saving-traffic trade-off.

This is an excellent question! Please see Figure 4, 5, and 7 for this trade-off and the run time distribution of our algorithms. Please also see a remark on the asynchronous implementation at the end of page 16. In short, bounding the tail overhead count does reduce tail CPU latency at the expense of less savings. But the overall run time remains the same or becomes worse, because it enters the residual branch more often (as a trade-off to controlling variance).

Q3. Does TCAB.STAR include the root’s cost in the experiments?

We thank the reviewer for pointing out this potential confusion. Yes, the root’s cost is included and the formula for the nonadaptive policies in Section 6.1 follows Footnote 3 in the original submission. As mentioned in our response to W2, we move the remark about “using offline logs to save root’s cost” to a footnote to emphasize that it is only mentioned as a possible practice, not a part of our algorithm.

Q4. Comparison with Meng et al.’s theorems.

We appreciate the reviewer for highlighting this comparison to the closest work. Please kindly see our elaboration on the theorem-level differences in the response to W2 above. We also respectfully underscore that Theorem 5.5 and 5.7 are not all of our theoretical results; we have also Theorem 5.1 and 5.3 that give the exact cost characterization and covers nonadaptive policies.


We truly appreciate the reviewer’s thoughtful observations, remarks, and questions. We are more than happy to discuss any question or unclarity further.

As the end of the reviewer-author discussion period approaches, we would like to follow up on our response and see if there is any questions or unclear points we could help answer. We appreciate the reviewer's time and efforts.

Reviewer_dpWtOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The authors introduce Tree-Coupled A/B Testing (TCAB), an experimental design aimed at reducing the JT sample complexity of evaluating J candidate policies. By structuring candidate policies along an acyclic graph, TCAB shares overlapping context-action laws to preserve exact finite-horizon trajectory distributions while minimizing redundant reward queries. For adaptive policies with sublinear pseudo-regret, the expected query cost is shown to reduce to T+o(T). The authors evaluate this approach on LLM benchmarks and a semi-synthetic search environment, demonstrating reduced reward-query budgets and improved inferential sensitivity.

Critical strengths
  • The application of the tree gluing lemma to resolve the incompatibility of simultaneous pairwise maximal couplings for J3 is mathematically elegant and rigorously justified.

  • By perfectly preserving the standalone marginal trajectories of every policy, the method guarantees that cumulative values and baseline contrasts remain unbiased without requiring complex offline estimators.

  • The empirical results on MMLU-Pro and RewardBench effectively demonstrate a reduction in query costs while maintaining, or improving, the minimum detectable effect (MDE80).

Critical weaknesses
  • While the application is practically useful, the core theoretical engine relies heavily on standard probability theory and established two-marginal maximal coupling techniques. The tree-gluing formulation functions more as a clever systems engineering optimization for data reuse than a foundational machine learning breakthrough typical of ICLR.

  • The methodology treats candidate policies entirely as black boxes to calculate total-variation distance. When deploying agentic AI or complex ranking models, ensuring a human in the oversight is critical for algorithmic governance. The paper currently lacks any framework to explain the underlying reasons why two models diverge on a given context, which is essential for safe policy deployment.

  • The experimental validation relies strictly on aggregate quantitative metrics, such as cumulative regret and variance reduction. The paper requires a granular, qualitative breakdown of residual errors. Particularly for applications like reinforcement learning in recommendation systems, it is necessary to understand exactly which user states or contextual complexities cause the coupled feedback to bottleneck the rejection sampler.

Questions for authors

1- Can you provide a qualitative analysis of the specific contexts or prompt structures where the rejection sampler experiences the highest failure rates, thereby driving up the proposal overhead?

2- How would you incorporate an explainability layer into the TCAB framework to provide human reviewers with actionable insights into why certain policy branches consistently mismatch?

3- How robust is the pre-computed TV-minimizing tree (TCAB.MST) if the contextual distribution PX experiences significant drift after the pilot calibration phase?

2 comments

We sincerely appreciate the reviewer's positive feedback and thoughtful concerns and questions raised in this review. We have uploaded a revised PDF submission (revised parts in blue) and hope to answer the questions below:

Q1. Qualitative analysis for when the proposal overhead is high.

This an excellent piece to complement our current version! We add a more detailed discussion and analysis about the proposal overhead in Section 4, below Proposition 4.1. In particular, we give explicit dependency for the overhead variance on the policy TV δij,t\delta_{ij,t}. This rate implies that the variance scales inversely in the TV (as the policies saturate toward the same set of optimal actions); but the expected overhead remains 1. Then we add an impossibility result to illustrate that this variance is somewhat binding for maximal-coupling sampler under the single-exposure condition (that each context arrival can only be used for one reward query, which matches many real-world applications).

To alleviate this potentially unbounded TV, we provide analysis and extensive comparison experiments on (1) an alternative Relaxed-coupling sampler, and (2) simple truncation/slack heuristics. The relaxed sampler takes the insight from the impossibility result above and achieves zero variance by forfeiting maximality: it tries to use a new sample for the child first, whereas the maximal sampler tries to inherit from the parent first and only uses a new sample afterwards. Truncation/slack adds simple modification to the original maximal sampler to balance the variance. More details and experiments are provided in Appendix B, D and E (Figure 4,5,7,8) respectively. In a word, those attempts successfully control the tail of the overhead count at the expenses of less reward-query-saving, but our original sampler was already good enough in terms of cumulative run time and estimation errors.

Q2. Insights on why policy branches mismatch.

The reviewer brought up an important point for our methods to be actually applied, which we are grateful to.

Such insights are partially provided by the added analysis on the overhead in Section 4. By Proposition 4.1, the mismatch probability is δij,t\delta_{ij,t}, so two policies mismatch when they are not concentrating to the same set of actions (conditioned on context). On the other hand, this is not a purely bad signal, because the overhead variance 1/δij,t1/\delta_{ij,t} is small now, and the child can find a new lineage without sampling much. As an example, for nonadaptive policies like the LLMs in Section 6.1, such TV terms are constant over time. When two LLMs show divergence on the actions/answers, this mismatch probability does not shrink; the reward saving comes from the parts where they happen to agree.

In practice, mismatches vanish over time as adaptive policies learn toward the same set of desirable behaviors. When they do saturate, it is tempting to switch to the relaxed sampler mentioned above to control the worst-case overheads (please see O-TCAB algorithm in Appendix B, which makes this sampler switch).

Q3. Is the MST robust under context shift?

This is a great question that complements the applicability of TCAB.MST. For now, we refrain ourselves from making more assumptions about the shift for theoretical analysis, since the shift is vastly different in different applications. We study the robustness of our algorithm empirically in Appendix C.

We shift the distribution PXP_X by identifying a new distribution where a new hindsight MST would be better and different from the current MST, at the middle of the horizon TT. We test the performance of TCAB.MST under the three datasets with such a shift. In Figure 6, we observe that TCAB.MST still outperforms the standard A/B test, which is reasonable because any exact feedback sharing will benefit. Also, the experiments indicate that we would gain huge benefits by adapting our tree structure to the shift, if we refit the MST periodically on the fly. Important for practitioners, such refitting can be run in parallel to the experiment, so it causes little additional delays.

Weaknesses 1 to 3

We agree on the points the reviewer has correctly brought up. In particular, the proofs in this work are not deeply novel mathematics; but we would like to reiterate that our contributions lie in proposing a universally applicable algorithm with grounded framework and analyses, and the theory is made clever to cover important aspects we may care in practice.

We also agree with the reviewer on the fact that the current results do not break down along the contexts, which would be insightful. We hope future studies can cover this aspect by possibly cohort analysis or context-conditioned overhead bounds, which may require more structured assumptions and algorithm designs.


We truly appreciate the reviewer’s excellent remarks and questions. We are more than happy to discuss any question or unclarity further.

As the end of the reviewer-author discussion period approaches, we would like to follow up on our response and see if there is any questions or unclear points we could help answer. We appreciate the reviewer's time and efforts.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of our revision and responses

We deeply appreciate the reviewers' and the AC's efforts, and the important questions the reviewers have raised. We have revised our PDF to reflect the reviews and additional experiments referenced in our responses to the reviews; the revision is in blue.

To summarize the revision:

  • We add a detailed discussion on sampling overhead variance in Section 4, together with a remedy (an alternative sampler that is not maximal but establishes zero variance). This remedy is elaborated and tested in Appendix B.
  • We add extensive comparison experiments for algorithm variants proposed in the reviews, including sampling with slack, sampling with truncation, and a shared-context algorithm under the multi-exposure condition (a context can be reward-queried multiple times). An overall algorithm comparison is included in Appendix E, Figure 8. The experiments study the trade-off between reward saving and overhead tail.

For each review, we included the specific and elaborated response below.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.