Rethinking Successive Rejects Algorithms
Abstract
In the best-arm identification problem, an algorithm adaptively selects arms to find the arm of the largest mean reward. Successive Rejects (SR) is a simple fixed-budget best-arm identification algorithm that eliminates one candidate arm at each phase. At first glance, SR seems to have limited adaptivity, since it follows predetermined phase lengths. However, for Gaussian arms with common variance, SR's worst-instance error exponent normalized by the popular complexity measure H1(P) is optimal up to a constant factor, which partly explains why SR's performance is competitive compared with state-of-the-art adaptive sampling algorithms. In this paper, we extend the framework of SR by optimizing its predefined schedule of phase lengths. We formulate phase-schedule design as an optimization problem for the normalized error exponent. Then, we introduce a version of SR with the optimized schedule, which we call H1-balanced Successive Rejects (H1-SR). This schedule is optimal within the class of SR-type algorithms with deterministic equal-count schedules. For Gaussian arms with common variance, H1-SR achieves at least 11/12 of the optimal normalized rate over all adaptive algorithms for every K≥2, and this approximation ratio converges to one as 1−O(1/log K) as K→∞. This is a significant improvement over original SR, whose corresponding fraction of the optimal normalized rate converges to 1/4. Finally, experiments on ten synthetic instances and two dataset-derived Gaussian benchmarks compare the optimized schedule with original SR at finite horizons. They show substantial gains on many instances while also exposing a regime in which more aggressive early elimination is costly.
Related
- Mean Values and Normal Order of a Successive-Iterate Ratio of Dedekind's Arithmetic Function
- Relative cone of curves and contractions of a successive blowup
- Distributed Algorithm for Linear Least Squares Problems via Iteratively Preconditioning by Successive Over-Relaxation
- Successive design of backstepping observers for parabolic PDE-ODE systems and its duality to state feedback stabilization
- Successive Refinement Under Strong-Sense Perfect Perception
BibTeX
@misc{khair2026rethinking,
title = {{Rethinking Successive Rejects Algorithms}},
author = {Mohamed Khair and Junpei Komiyama},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.22051},
eprint = {2610.22051},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.22051},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Rethinking Successive Rejects Algorithms
AU - Mohamed Khair
AU - Junpei Komiyama
PY - 2026
DA - 2026/10/15
PB - arXiv
DO - 10.48550/arxiv.2610.22051
UR - https://arxiv.org/abs/2610.22051
AB - In the best-arm identification problem, an algorithm adaptively selects arms to find the arm of the largest mean reward. Successive Rejects (SR) is a simple fixed-budget best-arm identification algorithm that eliminates one candidate arm at each phase. At first glance, SR seems to have limited adaptivity, since it follows predetermined phase lengths. However, for Gaussian arms with common variance, SR's worst-instance error exponent normalized by the popular complexity measure H_1(P) is optimal up to a constant factor, which partly explains why SR's performance is competitive compared with state-of-the-art adaptive sampling algorithms. In this paper, we extend the framework of SR by optimizing its predefined schedule of phase lengths. We formulate phase-schedule design as an optimization problem for the normalized error exponent. Then, we introduce a version of SR with the optimized schedule, which we call H_1-balanced Successive Rejects (H_1-SR). This schedule is optimal within the class of SR-type algorithms with deterministic equal-count schedules. For Gaussian arms with common variance, H_1-SR achieves at least 11/12 of the optimal normalized rate over all adaptive algorithms for every K≥2, and this approximation ratio converges to one as 1−O(1/log K) as K→∞. This is a significant improvement over original SR, whose corresponding fraction of the optimal normalized rate converges to 1/4. Finally, experiments on ten synthetic instances and two dataset-derived Gaussian benchmarks compare the optimized schedule with original SR at finite horizons. They show substantial gains on many instances while also exposing a regime in which more aggressive early elimination is costly.
ER -