Finding the arm with the largest mean reward under a fixed sampling budget is a core problem in machine learning. The Successive Rejects (SR) algorithm addresses it by eliminating one arm in each phase, using a predetermined schedule of pull counts. Despite its simplicity, SR is known to be competitive with more adaptive methods, but its fixed schedule leaves room for improvement.
Khair and Komiyama cast the design of that phase schedule as an optimization problem over the normalized error exponent. Their proposed H1-balanced Successive Rejects (H1-SR) schedule is optimal among 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 any K≥2, and the ratio approaches 1 as K grows. The original SR, by contrast, converges to only 1/4 of that rate.
The authors test the optimized schedule against original SR on ten synthetic and two dataset-derived Gaussian benchmarks at finite horizons. The gains are substantial on many instances, but the experiments also reveal a regime where more aggressive early elimination is costly, suggesting that the optimal schedule is not universally beneficial.