📊 statistics

Where Does the Union Bound Go? Best-Arm Identification and Strong FWER Control

This paper clarifies why the union bound is necessary in fixed-confidence best-arm identification by demonstrating that the apparent multiplicity issue persists regardless of hypothesis orientation, manifesting either as multiple true nulls or as multiple pathways to falsely rejecting the single true null.

Original authors: Rianne de Heide

Published 2026-08-21

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Rianne de Heide

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a world where you must choose the single best option from a crowded field of candidates, but you cannot see their true quality directly. You can only learn about them by taking repeated, imperfect measurements. This is the core challenge of a field known as best-arm identification, a branch of statistics that helps algorithms make the right choice in uncertain environments. Whether a doctor is selecting the most effective treatment from several trials, or a computer is tuning the settings of a complex system, the goal is the same: find the winner with high confidence while using as few measurements as possible. To do this safely, researchers must ensure that the chance of picking the wrong winner stays below a tiny, pre-set limit. For decades, the standard way to prove that an algorithm meets this safety limit has involved a specific mathematical trick called a union bound. This trick essentially adds up the risks of making a mistake against every single rival candidate. If there are a hundred candidates, the math suggests you must account for the risk of failing against ninety-nine of them.

This approach has long seemed puzzling to experts in a related field called multiple testing. In that world, if you are looking for a single true fact among many possibilities, logic dictates that only one hypothesis can be correct at a time. If you know only one thing is true, it feels strange to pay a heavy penalty for checking all the others. It is as if a security guard, knowing only one thief is in a building, insists on searching every single empty room with the same intensity as the one occupied room. For years, this created a quiet disconnect between the two communities. One side saw a necessary cost for safety, while the other saw an unnecessary burden of logic. A new note by Rianne de Heide resolves this tension by showing that the cost is not an error, but a matter of perspective. The paper demonstrates that the "extra" cost does not disappear; it simply moves to a different place depending on how you frame the question.

De Heide's work clarifies that there are two natural ways to look at the problem, and both lead to the same result, just through different routes. In the first way of looking at it, the researcher asks, "Is this specific candidate not the best?" In this framing, almost every candidate is indeed not the best. If there are a hundred options, ninety-nine of them are truly not the winner. Therefore, when the algorithm makes a mistake, it is failing to reject one of those ninety-nine true statements. Because so many of these "not the best" statements are simultaneously true, the math correctly requires the algorithm to be extra careful about all of them. The cost of checking many rivals is real and necessary here because the reality of the situation involves many true negatives.

The second way of looking at the problem flips the question entirely. Here, the researcher asks, "Is this specific candidate the best?" In this version, only one statement can ever be true. The logic of multiple testing suggests that if only one thing is true, you should not need to pay a penalty for checking the others. And indeed, if you could test this single "best" claim directly, you would not need the extra cost. However, the paper reveals that in practice, we cannot test this single claim in isolation. To prove that a candidate is the best, the algorithm must effectively prove that this candidate is better than every single rival. This turns the single "best" claim into a bundle of many smaller comparisons. The algorithm must show that the winner beats rival A, and beats rival B, and beats rival C, and so on.

This is where the cost reappears. Even though there is only one true "best" candidate, the test for that candidate is built from many smaller tests against each rival. If the algorithm makes a mistake, it might fail because it was fooled by rival A, or by rival B, or by any of the others. The risk of failure is the sum of the risks of being fooled by each individual rival. The paper shows that the mathematical factor representing the number of rivals, which appears as a penalty in the first way of looking at the problem, is simply hiding inside the construction of the test in the second way. It has not vanished; it has just been moved from the final safety check to the internal logic of how the test is built.

The significance of this finding is not that it changes the final numbers or the cost of running these algorithms. The paper does not suggest that we can suddenly find the best option with fewer measurements than before. Instead, it provides a unified understanding of why the math works the way it does. It explains that the "penalty" for having many options is an unavoidable feature of the problem, whether you view it as a collection of many false claims or as a single true claim that must be defended against many attackers. By making this equivalence explicit, the note bridges the gap between two different schools of statistical thought. It confirms that the standard methods used by researchers are logically sound, not because they are blindly following a rule, but because they are correctly accounting for the many ways a single true winner can be mistaken for a loser. The puzzle is solved not by removing the cost, but by understanding exactly where it lives.

Technical Summary: "Where Does the Union Bound Go? Best-Arm Identification and Strong FWER Control"

Problem Statement
In fixed-confidence Best-Arm Identification (BAI), algorithms aim to identify the unique arm $i^\star$ with the highest mean $\mu_{i^\star}$ among $K$ arms, ensuring the probability of error is at most $\delta$ . A recurring puzzle in the literature is the presence of a factor related to $K-1$ (often appearing as $\log(K-1)$ in stopping thresholds) in error bounds derived via the union bound.

From a multiple-testing perspective, this appears contradictory. If the parameter space is constrained such that exactly one arm is the best, then among the hypotheses "arm $i$ is best," only one is true. Standard multiple-testing theory (e.g., Bonferroni corrections) suggests that if only one null hypothesis is true, the error rate should not require a correction factor summing over $K-1$ alternatives. However, standard BAI proofs consistently allocate error budgets across $K-1$ competing events. This paper investigates the source of this apparent contradiction.

Methodology and Theoretical Framework
The paper resolves the puzzle by demonstrating that the $K-1$ factor arises from the implicit choice of hypothesis orientation. The author analyzes two distinct ways to formulate the null hypotheses within the unique-best-arm parameter space $\Theta_{\text{uniq}}$ :

Orientation 1: "Arm $i$ is not best"
- Hypotheses: Define $H_i^- := \{ \mu \in \Theta_{\text{uniq}} : i \neq i^\star(\mu) \}$ . The null hypothesis $H_i^-$ asserts that arm $i$ is not the best.
- Logic: If the true best arm is $i^\star$ , then $H_{i^\star}^-$ is false, but $H_i^-$ is true for all $i \neq i^\star$ .
- Multiplicity: In this formulation, there are exactly $K-1$ true null hypotheses simultaneously. Therefore, a standard union bound over the $K-1$ true nulls is logically necessary to control the Familywise Error Rate (FWER). The BAI error event $\{ \hat{b}_\tau \neq i^\star \}$ corresponds exactly to the event of rejecting at least one true null in this family.
Orientation 2: "Arm $i$ is best"
- Hypotheses: Define $G_i := \{ \mu \in \Theta_{\text{uniq}} : i = i^\star(\mu) \}$ . These form a partition of the parameter space where exactly one $G_i$ is true.
- Logic: Here, there is only one true null hypothesis. An elimination algorithm rejects $G_i$ if sufficient evidence suggests arm $i$ is not the best.
- Multiplicity: While there is only one true null, the construction of the test for $G_i$ introduces the multiplicity. The statement "arm $i$ is best" is an intersection of $K-1$ pairwise statements: $G_i = \bigcap_{j \neq i} \{ \mu_i > \mu_j \}$ .
- Mechanism: A pairwise elimination rule rejects $G_i$ if any competitor $j$ provides sufficient evidence against it. Thus, the rejection event for the single true composite null $G_{i^\star}$ is the union of $K-1$ pairwise rejection events: $\{ G_{i^\star} \text{ is rejected} \} = \bigcup_{j \neq i^\star} R_{j, i^\star}$ .
- Result: The union bound (and the resulting $K-1$ factor) does not disappear; it moves "inside" the test of the single true composite hypothesis. The error probability is bounded by the sum of probabilities of the $K-1$ pairwise comparisons.

Key Contributions

Explicit Equivalence: The paper makes the equivalence between the standard BAI error analysis and strong FWER control explicit in the terminology of both the BAI and multiple-testing communities. It clarifies that the "puzzle" of the $K-1$ factor is a result of switching between these two hypothesis orientations.
Clarification of Multiplicity: It demonstrates that multiplicity in BAI is not an artifact of poor proof techniques but a fundamental property of the problem structure. Whether viewed as $K-1$ true nulls (Orientation 1) or $K-1$ ways to contradict a single true null via pairwise comparisons (Orientation 2), the combinatorial factor remains.
Distinction between Rank and Witnesses: The paper clarifies the distinction between the "rank" of a problem (which is 2 for BAI, as only two arms are needed to disprove a candidate) and the number of possible "witnesses" (which is $K-1$ ). The rank explains why pairwise statistics suffice, while the union over witnesses explains the $K-1$ term in non-asymptotic error calibration.

Results and Analysis of Existing Literature
The paper analyzes how this duality manifests in specific algorithms and bounds:

Garivier and Kaufmann (2016): The threshold $\beta(t, \delta) = \log(2t(K-1)/\delta)$ explicitly sums over $K-1$ wrong winners after fixing the true best arm.
Kaufmann and Koolen (2021): Their improved, time-uniform mixture-martingale bounds sharpen the concentration within a pair but still apply a weighted union bound over the $K-1$ subsets $\{1, j\}$ . The multiplicity enters via the term $\log((K-1)/\delta)$ in the calibration function, even though the time dependence is sharper than previous bounds.
Sample Complexity: The paper notes that while the $K-1$ factor appears in non-asymptotic bounds, it does not necessarily imply a multiplicative $K-1$ loss in sample complexity for fixed $K$ as $\delta \to 0$ . The leading order term remains governed by $\log(1/\delta)$ .

Significance and Claims
The paper modestly claims to be a "note" that clarifies logical equivalences rather than proposing new algorithms or experimental results. Its primary significance lies in:

Unifying Perspectives: It bridges the gap between the BAI literature (which often treats the problem as identifying a unique winner) and the multiple-testing literature (which focuses on FWER control and logical constraints).
Demystifying the Union Bound: It argues that the union bound is not "wasted" in BAI proofs; rather, it is the correct tool for the specific logical structure of the problem, regardless of whether one views the problem as having many true nulls or one true null with many potential refuters.
Future Directions: The paper suggests that while joint tests exploiting the geometry of the full composite null (as seen in related pure-exploration problems like those by Katz-Samuels et al., 2020) might avoid explicit arm-by-arm union bounds, the fundamental combinatorial nature of the witnesses remains a key feature of the problem geometry.

The paper concludes that both communities are organizing error across logically related candidate answers, but they often place the multiplicity at different levels of the construction.

Technical Summary: "Where Does the Union Bound Go? Best-Arm Identification and Strong FWER Control"

More like this