Rethinking the Successive Rejects Algorithm: Optimized Stage Scheduling Improves Best-Arm Identification Efficiency

In the Best-Arm Identification (BAI) problem, algorithms adaptively select arms to find the one with the highest mean reward. Successive Rejects (SR), a simple and classic fixed-budget best-arm identification algorithm that eliminates one candidate arm per round, has long been regarded as a representative of limited adaptivity—after all, its stage lengths are predetermined. However, a recent study rethinks and extends the SR algorithm, significantly improving its performance by optimizing its stage scheduling.

Why Is the SR Algorithm So Competitive?

The core mechanism of the Successive Rejects algorithm is quite simple: divide the total budget into several stages, and after each stage, eliminate the currently worst-performing candidate arm until only one arm remains. This "round-by-round elimination" strategy seems mechanical, yet performs surprisingly well in practice.

The study points out that for Gaussian arms with common variance, SR's worst-case error exponent (normalized by the popular complexity measure H₁(P)) is already optimal within a constant factor. This theoretical property partly explains why SR can compete with state-of-the-art adaptive sampling algorithms, and even holds its own in many scenarios.

In other words, SR's "non-adaptive" label is misleading—its predetermined schedule already implicitly contains a certain optimal structure, but this optimality had not been fully exploited and leveraged before.

Error Exponent is a core metric for measuring the performance of best-arm identification algorithms. Under the large deviation theory framework, as the total budget tends to infinity, the algorithm's error probability decays at an exponential rate, and this decay rate is the error exponent. The larger the error exponent, the lower the error probability under the same budget. For the fixed-budget BAI problem, the error exponent is typically inversely proportional to a complexity measure that depends on the reward gaps between arms: the smaller the gaps, the harder the identification, and the higher the complexity.

The H₁(P) complexity measure is one such classic normalization benchmark, taking the form of a weighted sum of the inverse squared gaps between each suboptimal arm and the optimal arm. Researchers often use the product of the error exponent and this measure (i.e., the normalized error exponent) as an evaluation criterion, because the upper bound of this product characterizes the optimal rate achievable by all algorithms. If an algorithm's normalized error exponent approaches the upper bound within a constant factor, it is said to be near-optimal in that sense. The reason SR is competitive is precisely that its predetermined schedule happens to make the normalized error exponent reach the upper bound within a constant factor.

Converting Stage Scheduling Design into an Optimization Problem

Since SR's predetermined stage lengths are not optimal, can they be improved through mathematical optimization? This is precisely the core contribution of the study.

The authors formalize the stage scheduling design as an optimization problem targeting the normalized error exponent. By solving this problem, they propose a new SR variant—H₁-Balanced Successive Rejects (H₁-SR for short). This optimized schedule is optimal among SR-type algorithms with deterministic equal-counting plans.

This means that among all algorithms following the "equal-count elimination" framework, H₁-SR's stage arrangement has reached the theoretical optimum and cannot be further improved under this constraint.

The common-variance Gaussian arm model is a standard setting in BAI theoretical analysis: each arm's reward follows a Gaussian distribution with the same variance and unknown mean, and the algorithm obtains noisy observations through sampling to infer which arm has the largest mean. The common variance assumption simplifies the analysis, making the error exponent depend only on mean gaps without interference from variance differences across arms.

A deterministic equal-counting plan means that in SR-type algorithms, the number of samples for each candidate arm in each stage is predetermined and equal. This constraint ensures that the algorithm samples each candidate arm in a balanced manner under a fixed budget, facilitating theoretical analysis while making stage length the only degree of freedom that can be optimized. Under this constraint, the choice of stage length directly determines when each arm is eliminated, thereby affecting the error exponent. The study optimizes precisely this degree of freedom, finding the optimal schedule within the equal-counting framework.

H₁-SR's Theoretical Guarantee: Approaching the Optimal Adaptive Algorithm

The most striking contribution of H₁-SR lies in its theoretical guarantee. For Gaussian arms with common variance, the algorithm achieves at least 11/12 of the optimal normalized rate among all adaptive algorithms, and this ratio holds for any K≥2.

More profoundly, as the number of candidate arms K tends to infinity, this approximation ratio converges to 1 at a rate of 1-O(1/log K). In other words, as the problem scale grows, H₁-SR can achieve nearly the optimal performance of a fully adaptive algorithm.

By comparison, the original SR algorithm's corresponding optimal normalized rate ratio converges to only 1/4. The leap from 1/4 to nearly 1 shows that the optimization of stage scheduling is not a minor tweak but a fundamental improvement.

Approximation Ratio is a commonly used metric for measuring the gap between an algorithm's performance and the theoretical optimum. In BAI, if the ratio of an algorithm's normalized error exponent to the optimal value achievable by all adaptive algorithms is defined as the approximation ratio, then the closer this ratio is to 1, the closer the algorithm is to being fully adaptive. H₁-SR's approximation ratio is 11/12 (about 0.917), meaning its error exponent reaches at least 91.7% of the optimal value.

The convergence rate 1-O(1/log K) describes the asymptotic behavior of the approximation ratio as the number of candidate arms K increases. As K tends to infinity, 1/log K tends to 0, so the approximation ratio approaches 1, meaning H₁-SR loses almost no performance on large-scale problems. In contrast, the original SR's approximation ratio converges to only 1/4, meaning its error exponent is at most one quarter of the optimal value. This significant gap indicates that optimizing stage scheduling not only improves the constant factor but fundamentally changes the algorithm's asymptotic efficiency.

Experimental Validation: Significant Gains and Revealed Costs

The study conducted experiments on ten synthetic instances and two dataset-based Gaussian benchmarks, comparing the optimized schedule with the original SR under a finite time horizon.

The experimental results show two key findings: on the one hand, on most test instances, the optimized schedule brings substantial performance improvements, validating the theoretical analysis predictions; on the other hand, the experiments also reveal a mechanism worth noting—in certain problem environments, an overly aggressive early elimination strategy can actually incur higher costs.

This finding reminds practitioners that although optimizing stage scheduling is promising, it is not a case of "the earlier the elimination, the better"—trade-offs must be made based on the specific problem structure.

Synthetic instances and dataset-based Gaussian benchmarks are two typical types of test environments for BAI experimental evaluation. Synthetic instances precisely control problem difficulty by manually setting the means and variances of each arm, facilitating validation of theoretical predictions; dataset-based Gaussian benchmarks estimate each arm's reward distribution from real data, getting closer to practical application scenarios. Combining both allows testing the algorithm's performance under idealized conditions as well as evaluating its robustness under real data distributions.

A finite time horizon refers to an experimental setting where the total budget is fixed and limited, which differs from asymptotic theoretical analysis—theory focuses on limiting performance as the budget tends to infinity, while practical applications are often constrained by a finite number of samples. Under a finite budget, the algorithm's constant factor and early decision quality become crucial, so the gains from optimizing the schedule may be more significant than asymptotic analysis suggests, or may incur extra costs due to overly aggressive early elimination.

Implications for the Best-Arm Identification Field

This work vindicates SR-type algorithms: a predetermined schedule that appears to lack adaptivity, after careful optimization, can theoretically approach the optimal performance of fully adaptive algorithms. This conclusion challenges the simple notion that "adaptive is better than non-adaptive" and provides new ideas for the design of fixed-budget best-arm identification algorithms.

For practical applications, H₁-SR's computational overhead is almost comparable to the original SR, yet it achieves significant improvements in both theoretical guarantees and experimental performance. This "low complexity, high reward" characteristic gives it practical value in scenarios requiring rapid decision-making.

One-line Summary

A study re-optimizes the stage scheduling of Successive Rejects, proposing H₁-SR, enabling a non-adaptive algorithm to approach fully adaptive performance.

Paragraph Summary

This article introduces a rethinking and extension of the classic fixed-budget best-arm identification algorithm Successive Rejects (SR). Although SR uses predetermined stage lengths, its normalized error exponent is already optimal within a constant factor, which explains its long-standing competitiveness. Researchers formalize the stage scheduling design as an optimization problem and propose the H₁-SR variant, achieving the optimal schedule among deterministic equal-counting SR-type algorithms. Theoretical analysis shows that H₁-SR achieves at least 11/12 of the optimal normalized rate among all adaptive algorithms, and converges to 1 at a rate of 1-O(1/log K) as the number of candidate arms K increases, far outperforming the original SR's 1/4. Experiments on ten synthetic instances and two Gaussian benchmarks validate significant gains while revealing that overly aggressive early elimination may incur higher costs in some scenarios. This work challenges the simple notion that "adaptive is necessarily better than non-adaptive" and provides new ideas for fixed-budget BAI algorithm design.