Research map / Bandits and online learning / Multi-armed bandits
On Universally Optimal Algorithms for A/B Testing
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that for two-armed fixed-budget best-arm identification (A/B testing) with Bernoulli rewards no algorithm can beat uniform sampling on all instances while strictly outperforming it on another, and gives exact asymptotic error rate of Successive Rejects showing uniform sampling can beat it for K=3.
Problem
Fixed-budget best-arm identification in Bernoulli bandits: whether any adaptive algorithm can match uniform sampling everywhere and strictly beat it somewhere (open problem), and whether a universally optimal instance-specific error lower bound exists.
Approach
Introduces consistent and stable algorithm classes; shows better-than-uniform algorithms belong to them, and that any consistent stable algorithm has error exponent at least that of uniform sampling, so uniform sampling is universally optimal among them in the two-arm case. For K≥3, derives the exact asymptotic error rate of Successive Rejects and shows uniform sampling beats it on some instances.
Key results
- For two arms, any better-than-uniform algorithm achieves exactly the uniform sampling exponent 1/g(1/2,mu) on every instance, so no algorithm strictly outperforms uniform sampling.
- Exact asymptotic error rate of Successive Rejects is derived as max_j j log-bar K / Gamma_j(mu).
- On instance (0.5,0.3,0.3), SR has exponent about 70.36 versus about 71.1 for uniform sampling, so uniform sampling strictly outperforms SR there.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace Successive Rejects with uniform sampling | 3-arm Bernoulli bandit · (0.5, 0.3, 0.3) | T/log(1/p): 71.1 -> 70.3587 | Helped |
| replace uniform sampling with an algorithm that is no worse on every instance | Two-arm Bernoulli bandits · A/B testing | asymptotic T/log(1/p) | No clear effect |
| use uniform sampling instead of Successive Rejects | K-arm Bernoulli bandits · Some instances with K≥3 | asymptotic error rate | Helped |
Surprising findings
- Adaptive algorithms cannot universally match and strictly beat uniform sampling in the two-armed case.
- Uniform sampling outperforms the Successive Rejects algorithm on some three-armed instances.
Limitations
- Two-armed result relies on the consistent and stable algorithm class; general K-armed case only partially addressed.
- Results are asymptotic in the budget T and specific to Bernoulli rewards.
Experimental setup
Metrics: asymptotic error exponent T/log(1/p)
Baselines: uniform sampling Successive Rejects best static algorithm
Builds on: Successive Rejects Kaufmann et al. 2016 fixed-budget lower bound analysis
Closest papers by meaning
- Optimal Multi-Fidelity Best-Arm Identification (NeurIPS 2024 · similarity 0.90)
- Balancing Performance and Costs in Best Arm Identification (NeurIPS 2025 · similarity 0.90)
- Sharp Non-Asymptotic Analysis of the Penalized Challenger in $\beta$-EB-TCI for Bernoulli Bandits (NeurIPS 2026 · similarity 0.89)
- Fixed-Budget Differentially Private Best Arm Identification (ICLR 2024 · similarity 0.89)
- Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits (NeurIPS 2024 · similarity 0.89)
- Best Arm Identification in Generalized Linear Bandits via Hybrid Feedback (NeurIPS 2026 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.