Where Does the Union Bound Go? Best-Arm Identification and Strong FWER Control
Rianne de Heide
What is this note about?
In fixed-confidence best-arm identification, proofs often use a union bound over the competing arms. From a multiple-testing viewpoint this can look puzzling: if the best arm is unique, only one hypothesis of the form “arm i is best” can be true. This note explains precisely where the multiplicity correction lives, and how the answer depends on which way the hypotheses are oriented.
Abstract
In fixed-confidence best-arm identification, proofs often use a union bound across the competing arms. From a multiple-testing point of view this can look puzzling: if the best arm is unique, only one hypothesis of the form “arm i is best” can be true. Why then should there be a Bonferroni-type factor of K−1? The answer is that there are two natural ways to orient the hypotheses. In one orientation, best-arm identification is literally a strong familywise-error-rate (FWER) problem with K−1 true nulls. In the opposite orientation, exactly one null is true, but a pairwise implementation can falsely reject that one null through any of K−1 comparisons. Thus the multiplicity has not disappeared; it just pops up in different places. This note makes the equivalence explicit in the terminology of both communities.
Keywords and connections
Best-arm identification; pure exploration; ranking and selection; multiple comparisons with the best; strong FWER; familywise error rate; Bonferroni; union bound; sequential testing.