Tree-Coupled A/B Testing Speeds Up Multi-Policy Comparisons.

Online platforms frequently need to compare numerous adaptive decision policies, such as ranking algorithms, recommendation systems, or pricing rules. Traditional A/B/n testing, which assigns each policy its own independent experiment, can be resource-intensive and slow, especially when interactions are costly or risky. Researchers have introduced Tree-Coupled A/B Testing (TCAB), an innovative feedback-sharing design. This method allows for the exact comparison of multiple history-dependent contextual-bandit policies by strategically coupling policy histories in a tree structure. At each step, a single reward is shared among matched tree edges, significantly reducing the total number of reward queries needed. TCAB ensures that each policy's finite-horizon trajectory law remains exactly as it would be in an independent run, despite the deliberate dependencies introduced for feedback sharing. This leads to substantial improvements in cost-precision efficiency, with the number of reward queries approaching T (the horizon) plus a sublinear term, compared to JT (J policies * T horizon) for independent runs. Experiments confirm its effectiveness in various applications, including reward model and language model evaluation.