Where Does the Union Bound Go? Best-Arm Identification and Strong FWER Control
Analyzes the equivalence of union bound in fixed-confidence best-arm identification under two hypothesis orientations, revealing structural insights for error control.
Key Findings
Methodology
The authors analyze the union bound in best-arm identification from a multiple-testing perspective, defining two hypothesis orientations: one as 'no arm is best' with K-1 true nulls, and the other as 'arm i is best' as a composite null. They show these perspectives are logically equivalent, with the former requiring Bonferroni correction due to multiple true nulls, and the latter involving pairwise comparisons. The work integrates Chernoff bounds and pairwise elimination strategies, demonstrating how the structure of hypotheses influences error bounds and sample complexity. The analysis is grounded in recent advances by Garivier and Kaufmann (2016) and Kaufmann and Koolen (2021).
Key Results
- In the 'no arm is best' perspective, the error event aligns with strong FWER, requiring correction for K-1 hypotheses. Experiments with Bernoulli distributions confirm that Chernoff-based stopping rules incorporate a log(K-1) term in the error bound, matching theoretical predictions.
- In the 'arm i is best' perspective, the hypothesis is a conjunction of pairwise inequalities. Testing each pairwise comparison individually and combining results via union bounds reproduces the K-1 multiplicity, but structured joint tests can reduce this burden. Experimental results show significant sample savings compared to naive Bonferroni correction.
- The paper demonstrates that the apparent K-1 penalty arises from the logical structure of hypotheses, not from the inherent difficulty of the problem. Exploiting hypothesis relations allows for more efficient error control without sacrificing correctness.
Significance
This work clarifies the conceptual foundations of error control in best-arm identification, bridging the gap between statistical hypothesis testing and bandit algorithms. By elucidating the dual perspectives on the union bound, it offers new avenues for designing more sample-efficient algorithms that leverage logical structure. The insights impact both theoretical understanding and practical algorithm development, especially in high-dimensional or complex models where traditional union bounds are overly conservative. The results also deepen the connection between multiple testing theory and sequential decision-making, fostering cross-disciplinary innovation.
Technical Contribution
The paper provides a rigorous formalization of the equivalence between two hypothesis orientations in fixed-confidence best-arm identification, highlighting how the union bound's K-1 factor emerges naturally from the logic of the hypotheses. It introduces a framework to incorporate logical constraints into multiple testing procedures, enabling more efficient error control. The integration of Chernoff bounds and pairwise elimination strategies exemplifies how to reduce sample complexity while maintaining rigorous error guarantees. These contributions advance the theoretical understanding of structured multiple testing in sequential settings.
Novelty
This is the first comprehensive analysis explicitly connecting the union bound's K-1 penalty with the logical structure of hypotheses in best-arm identification. It reveals that the multiplicity arises from different but equivalent hypothesis formulations, providing a unified perspective that was previously overlooked. The work bridges classical multiple testing theory with modern bandit algorithms, offering a novel conceptual framework for error control based on hypothesis structure rather than naive union bounds.
Limitations
- The analysis primarily focuses on Bernoulli bandits; extending to other distributions or non-parametric settings remains an open challenge.
- While the theoretical framework is general, practical implementation of structured joint tests may be computationally demanding in high-dimensional or large-scale problems.
- The approach relies on explicit logical structures among hypotheses, which may not be available or easy to specify in complex real-world applications, limiting its immediate applicability.
Future Work
Future research could explore extending the framework to non-parametric models, multi-faceted hypothesis structures, and adaptive procedures that learn the logical relations dynamically. Integrating Bayesian methods and deep learning techniques to approximate joint tests could further improve scalability. Additionally, applying these insights to real-world problems such as clinical trials, recommendation systems, and adaptive experimental design remains a promising direction.
AI Executive Summary
This paper tackles a fundamental issue in fixed-confidence best-arm identification within multi-armed bandit problems: the role of the union bound in controlling error probabilities. Traditionally, error bounds rely on Bonferroni corrections, which assume multiple hypotheses can be simultaneously true, leading to a correction factor proportional to the number of hypotheses. However, in the context of best-arm identification, the hypotheses can be viewed from two different logical perspectives: one as 'no arm is best,' involving multiple true nulls, and the other as 'arm i is best,' which is a conjunction of pairwise inequalities. The authors demonstrate that these two viewpoints are logically equivalent, and the apparent K-1 penalty in error bounds arises naturally from the structure of the hypotheses rather than intrinsic difficulty.
Building on recent advances by Garivier and Kaufmann (2016) and Kaufmann and Koolen (2021), the paper employs Chernoff bounds and pairwise elimination strategies to derive error bounds that incorporate the log(K-1) term. Experiments on Bernoulli bandits confirm that these bounds accurately reflect the sample complexity and error control trade-offs. The key insight is that structured hypothesis testing, which exploits logical relations among hypotheses, can significantly reduce the sample burden compared to naive union bounds.
Overall, the work provides a unified theoretical framework that clarifies the origin of the multiplicity penalty and suggests pathways for designing more efficient algorithms. It bridges the gap between classical multiple testing theory and sequential decision-making, with broad implications for high-dimensional and complex models. Future directions include extending the framework to non-parametric settings, developing scalable joint tests, and applying these ideas to real-world adaptive experiments, promising to advance both theory and practice in statistical learning and online decision systems.
Deep Dive
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.