A mathematical note argues that the familiar K − 1 factor in fixed-confidence best-arm identification is relocated, not eliminated, when the problem is framed with a different kind of hypothesis. Best-arm identification means sampling K options adaptively and, after a data-dependent stopping time, returning the one with the best mean. In this setting, δ-correctness requires the chance of returning a non-best option to be no more than δ for every instance with a unique best option.
A standard proof spreads the allowed error across K − 1 competing ways to be wrong, often assigning each one δ/(K − 1). That bookkeeping typically adds log(K − 1) to the stopping threshold, the evidence level required before the algorithm stops.
The choice of null changes the picture
The first formulation treats each statement that “arm i is not best” as a null hypothesis, or a claim the data may reject. If one arm is uniquely best, exactly K − 1 of those nulls are true. The event that the algorithm returns a wrong arm is then exactly the event of rejecting at least one true null, known as the family-wise error rate, or FWER. Controlling best-arm error at δ is therefore the same logical task as strong FWER control at δ.
The second formulation reverses the question: each hypothesis says that a particular arm is best. These hypotheses form a partition, meaning that exactly one of them is true. The note says anytime-valid tests at level δ can be used to eliminate rejected cells and return the last one left, preserving δ-correctness without a multiplicity correction across the cells.
The factor reappears inside the test
That apparent escape has a catch. The statement that arm i is best is composite: it is the intersection of K − 1 pairwise claims that arm i beats each competitor. A pairwise procedure can reject the overall statement as soon as one competitor supplies enough evidence against it. The K − 1 count has therefore moved from the list of hypotheses being tested to the construction of a single composite test.
The note uses a Bernoulli example to make the calibration visible. It reports a Chernoff stopping threshold of β(t, δ) = log(2t(K − 1)/δ) and says the proof takes a union over the K − 1 possible wrong winners.
A cited mixture-martingale analysis, using time-uniform bounds, is likewise described as a weighted union over K − 1 pair subsets. In the note’s account, the multiplicity enters the calibration through log((K − 1)/δ), the argument of the calibration function.
What the result does not claim
The result is not a claim that every best-arm algorithm pays a multiplicative K − 1 penalty in sample complexity. The authors say that when K is fixed and δ becomes small, leading-order results are governed by log(1/δ); keeping K − 1 inside the logarithm changes only a lower-order term.
The note points to joint tests that use dependence among comparisons and the geometry of the full composite null; related pure-exploration examples avoid an explicit union over the number of arms. But that is not the same as showing that K − 1 disappears from ordinary unstructured best-arm identification. The analysis also stays within the unique-best-arm setting, so tied-best cases are outside what it establishes.
Paper data and sources
Original title: Where Does the Union Bound Go? Best-Arm Identification and Strong FWER Control
Authors: Rianne de Heide
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-20
DOI: Not available
Original paper · Full text