Skip to content

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

Aug 2026 · arXiv.org · Vol abs/2608.12831 · 0 citations · 57 references
Computer Science

TL;DR

This work introduces Tree-Coupled A/B Testing (\TCAB), an exact feedback-sharing design for arbitrary history-dependent contextual-bandit policies and obtains finite-sample variance bounds for pairwise policy contrasts.

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\ge 2$ 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.

View source

Similar papers

#machine learning Preprint Oct 2026

Metropolis-Hastings Dominates Importance Resampling for Policy Composition

Post-training a large language model (LLM) often requires exploring trade-offs between multiple rewards, but retraining for each trade-off is expensive. Decoding-time policy composition allows these trade-offs to be adjusted by combining reward-specific policies at inference time. This composition targets a weighted pr...

Alexey Kurennoy, R. Yarullin, Fergal Reid · 0 citations
#artificial intelligence Preprint Oct 2026

TSBPO: Tree-Structured Branching for Policy Optimization in Interactive Language Agents

Terminal feedback in multi-turn agent training leaves both rollout allocation and local credit underdetermined. Dynamics-Predictive Sampling (DPS) [9] provides a task-level predictive sampling reference, but interactive agents also need to choose which visited states merit further continuations. We introduce TSBPO with...

Rui Yu, Chong Mu, Jin-Chuan Zhang · 0 citations

EPIG-Tree: Compute-Optimal Branching for Gradient-Efficient Reinforcement Learning

Empirically, EPIG reduces gradient MSE in cloned-state control, winning in all nine dense continuous-control environments of a 13-environment sweep and recovering the reference gradient direction near-perfectly, and it improves frozen-LLM gradient calibration relative to entropy branching.

Nikita Khomich, L. Hermansson, Ido Hakimi · 1 citation
Preprint Nov 2026

BLPO: Beyond-Local Policy Optimization for Long-Horizon LLM Agents

Beyond-Local Policy Optimization (BLPO), which estimates task-progress advantages from experience shared across tasks and training updates, and accumulates context-relative returns in a global memory with balanced aggregation and reliability weighting to control bias and noise from heterogeneous tasks.

Xuan-Ren Chen, Chong-Yang Tao, Wen-Peng Hu et al. · 0 citations
#artificial intelligence Preprint Oct 2026

Matched-Context Group Policy Optimization for LLM Agent Training

Training long-horizon language model agents requires assigning credit to intermediate decisions from sparse terminal feedback. Within a finite group of sibling rollouts, useful action comparisons depend on their context, evidence for both alternatives, and how that evidence enters learning. We propose Matched-Context G...

Chen-Xu Zhang, Yao-Rui Shi, Wen-Long Zhang et al. · 0 citations
Preprint Oct 2026

Cross-Behavior Policy Optimization: Unified Learning from Offline Demonstrations and On- and Off-Policy Rollouts via a Shared Regression Target

Reasoning post-training draws on offline demonstrations and policy-generated rollouts, yet conventional supervised fine-tuning (SFT) followed by reinforcement learning (RL) separates their objectives and limits continued reuse of collected responses. We propose \textbf{Cross-Behavior Policy Optimization} (CBPO), which...

Du Cheng, Jun-Yu Lu, Jing-Fan Zhang et al. · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.