# On the Complexity of A/B Testing

arXiv: https://arxiv.org/abs/1405.3224 · HTML: https://mlsanity.com/paper/1405.3224/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 May 2014.

## Built on by (most cited first, 14 of 14)

- [Top Two Algorithms Revisited](https://mlsanity.com/paper/2206.05979/) (2022)
- [Non-Asymptotic Analysis of a UCB-based Top Two Algorithm](https://mlsanity.com/paper/2210.05431/) (2022)
- [On Universally Optimal Algorithms for A/B Testing](https://mlsanity.com/paper/2308.12000/) (2023)
- [Maximizing and Satisficing in Multi-armed Bandits with Graph Information](https://mlsanity.com/paper/2108.01152/) (2021)
- [Optimal Best Arm Identification in Two-Armed Bandits with a Fixed Budget under a Small Gap](https://mlsanity.com/paper/2201.04469/) (2022)
- [Best Arm Identification with Contextual Information under a Small Gap](https://mlsanity.com/paper/2209.07330/) (2022)
- [Representative Arm Identification: A fixed confidence approach to identify cluster representatives](https://mlsanity.com/paper/2408.14195/) (2024)
- [Multi-Metric Adaptive Experimental Design Under a Fixed Budget with Validation](https://mlsanity.com/paper/2506.03062/) (2025)
- [Active Bipartite Ranking with Smooth Posterior Distributions](https://mlsanity.com/paper/2602.24263/) (2026)
- [Fixed Confidence Best Arm Identification in the Bayesian Setting](https://mlsanity.com/paper/2402.10429/) (2024)
- [Minimax Optimal Simple Regret in Two-Armed Best-Arm Identification](https://mlsanity.com/paper/2412.17753/) (2024)
- [Near Optimal Best Arm Identification for Clustered Bandits](https://mlsanity.com/paper/2505.10147/) (2025)
- [Minimax and Bayes Optimal Adaptive Experimental Design for Treatment Choice](https://mlsanity.com/paper/2512.08513/) (2025)
- [Gap Entropy and Almost Instance-Wise Optimal Best-Arm Identification](https://mlsanity.com/paper/2609.13703/) (2026)

## Abstract (arXiv)

A/B testing refers to the task of determining the best option among two alternatives that yield random outcomes. We provide distribution-dependent lower bounds for the performance of A/B testing that improve over the results currently available both in the fixed-confidence (or delta-PAC) and fixed-budget settings. When the distribution of the outcomes are Gaussian, we prove that the complexity of the fixed-confidence and fixed-budget settings are equivalent, and that uniform sampling of both alternatives is optimal only in the case of equal variances. In the common variance case, we also provide a stopping rule that terminates faster than existing fixed-confidence algorithms. In the case of Bernoulli distributions, we show that the complexity of fixed-budget setting is smaller than that of fixed-confidence setting and that uniform sampling of both alternatives -though not optimal- is advisable in practice when combined with an appropriate stopping criterion.