acceptodds
Under review as a conference paper at ICLR 2027

Rethinking successive rejects algorithms

11 views

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 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 -balanced Successive Rejects (). This schedule is optimal within the class of SR-type algorithms with deterministic equal-count schedules. For Gaussian arms with common variance, -SR achieves at least of the optimal normalized rate over all adaptive algorithms for every , and this approximation ratio converges to one as as . This is a significant improvement over original SR, whose corresponding fraction of the optimal normalized rate converges to . % The finite-budget uarantee for -SR extends to independent sub-Gaussian rewards. 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.

Primary area:
learning theory
Keywords:
multi armed bandits, best arm identification

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_grNwOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper revisits the Successive Rejects (SR) algorithm for best arm identification. The author extends the framework of SR by optimizing its predefined schedule of phase lengths. They formulate phase-schedule design as an optimization problem for the normalized error exponent. The main theoretical result is that the proposed schedule is optimal within the class of deterministic, equal-count SR-type algorithms. Numerical experiments demonstrate improvements over the original SR algorithm on several instances.

Critical strengths

The theoretical analysis and result is interesting, which provides a sharper characterization of the error exponent. The proposed algorithm is simple to implement and dose not introduce additional computational complexity compared with original SR. And it also performs better than SR on most instances. The overall writing is clear and easy to follow.

Critical weaknesses

1.The general idea of modifying the phase lengths of SR algorithm has been explored in the literature [1], which the authors also cite. The proposed schedule remains deterministic and does not adapt phase lengths based on observed sample means. A potentially more interesting direction would be to determine phase lengths adaptively using the observed information. From my point of view, the algorithmic novelty is limited. The main contribution lies in establishing stronger theoretical guarantees under a specific optimality criterion

[1] Shahrampour, Shahin, Mohammad Noshad, and Vahid Tarokh. "On sequential elimination algorithms for best-arm identification in multi-armed bandits." IEEE Transactions on Signal Processing 65.16 (2017): 4281-4292.

2.The empirical evaluation is relatively limited. Several related BAI algorithms have been proposed in the literature, including the nonlinear elimination method in [1], Continuous Rejects [2], and almost tracking in [3]. These methods are also cited by the author. However, the experiments compare H1-SR only with the original SR algorithm, which is insufficient to establish the practical competitiveness of the proposed method. Since the theoretical guarantees focus on worst-case asymptotic optimality. It is important to evaluate H1-SR against these existing methods across instances with different gap structures and T to better assess its performance.

[2] Wang, Po-An, Ruo-Chun Tzeng, and Alexandre Proutiere. "Best arm identification with fixed budget: A large deviation perspective." Advances in Neural Information Processing Systems 36 (2023): 16804-16815.

[3] Komiyama, Junpei, Kyoungseok Jang, and Junya Honda. "Rate-optimal Design for Anytime Best Arm Identification." arXiv preprint arXiv:2510.23199 (2025).

3.This paper adopts H1 as the complexity measure, which I agree is a reasonable and meaningful choice. However, I wonder to what extent the proposed algorithm and its theoretical guarantees depend on this particular measure. Specifically, would the optimal sampling schedule change if a different complexity measure were used? Would the main conclusions and optimality guarantees still hold? Clarifying these questions would help assess the generality of the proposed approach.

I would be willing to raise my score if these concerns are adequately addressed.

Questions for authors

See the weakness.

2 comments

Thank you for your insightful comments. We have revised the paper to address your concerns.

1. Algorithmic contribution and adaptivity.

Adapting the phase lengths to the observations could indeed improve performance on particular instances. However, our result shows that H1H_1-SR, while using predetermined checkpoints, achieves near-minimax performance under H1H_1. H1H_1-SR achieves at least 11/1211/12 of the optimal worst-instance H1H_1-normalized rate for every K≥2K\ge2, and a fraction 1−O(1/log⁡K)1-O(1/\log K) as K→∞K\to\infty, taking the horizon limit first. Therefore, in view of minimax optimality, the predetermined checkpoints of H1H_1-SR are very close to optimal, and adaptive length adjustments has limited margin. Achieving this guarantee despite restricted adaptivity is a central contribution of our work, rather than a limitation.

Shahrampour, Noshad and Tarokh (2017) already study nonlinear elimination schedules, and we acknowledge this prior work. Our contribution is the exact worst-instance H1H_1-normalized rate of every deterministic equal-count SR schedule with positive limiting checkpoint fractions, with matching upper and lower bounds. Optimizing that expression gives the optimal limiting allocation in this class. We also obtain original SR's exact H1H_1-normalized rate and compare the optimized schedule with the best rate among all adaptive policies.

Wang, Tzeng and Proutiere (2023) develop a large-deviation analysis and Continuous Rejects, whose rejection times depend on empirical gaps. Our result establishes the exact schedule optimization and the above minimax comparison while retaining predetermined checkpoints. We have also added Continuous Rejects to the experiments.

2. Empirical comparisons: additional experiments.

Appendix L in our revision now compares sixteen methods on all twelve original instances and their original horizons, with 10,00010{,}000 runs per entry. It includes CR-A/CR-C, Simple/Almost Tracking, top-two methods, uniform sampling, Sequential Halving/doubling variants and nonlinear elimination. We find that H1H_1-SR is competitive with the other methods despite its simple schedule. The probability-of-error percentages (smaller better) on all twelve instances are:

InstanceTTH1H_1-SRCR-AAlmost Tracking
Synthetic 16,0009.9211.7214.32
Synthetic 21,0001.375.523.38
Synthetic 34,0007.725.067.94
Synthetic 44,5009.887.0311.35
Synthetic 525,0009.479.4611.59
Synthetic 65,0005.546.528.62
Synthetic 78,00015.886.342.88
Synthetic 82,0002.011.252.56
Synthetic 91,5001.761.943.20
Synthetic 102,5007.035.589.42
MovieLens 1M10,00018.2720.1422.34
Open Bandit3,0009.3749.889.96

These results illustrate both the practical gains of our methods.

3. Dependence on the complexity measure H1H_1.

Our framework extends to other complexity measures beyond H1H_1. In particular, our revision has added a concrete extension in Appendix J.1: H2H_2-SR, obtained by optimizing the exact H2H_2-normalized rate over the same SR class. For Gaussian arms with common variance, it is asymptotically minimax among all adaptive policies as KK grows. Writing RH2(A)R_{H_2}(\mathcal A) for policy A\mathcal A's worst-instance normalized rate and RH2,K⋆R_{H_2,K}^\star for the unrestricted optimum (including any adaptive algorithm), we establish the following, taking the horizon limit first for each fixed KK and numerically evaluating the explicit lower bound for 2≤K≤402\le K\le40:

\qquad \frac{R_{H_2}(H_2\text{-SR})}{R_{H_2,K}^\star}\ge 0.824 \quad\text{for all } 2 \le K \le 40.$$ The appendix also gives the finite-$K$ rate comparisons and $H_2$-SR results on the twelve experiments. This shows that the methodology extends beyond $H_1$, while the best schedule depends on the chosen complexity. Appendix K explains the general step: once rejection-cost coefficients are established for a complexity $H$, balancing the phase budgets gives the corresponding $H$-SR schedule. Exact class optimality requires matching rate bounds, and comparison with all adaptive policies requires a separate converse. We carry out these arguments for $H_2$ in Appendix J.1; the main paper remains focused on $H_1$-SR.

Thank the authors for their response. I have raised my score accordingly. However, my concern about the novelty of the algorithm remains.

Reviewer_tj2dOpenReview ↗
Rating
2(+1)
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper presents a variant of the Successive Reject algorithm (Audibert et al., 2010) called H1H_1-SR, where the authors use a different phase length (budget) from the original version. So the main contribution of this paper is designing the optimal phase budget for each phase of the Successive Reject algorithm.

The authors claim that this methodology improves the sample complexity by at least a 11/12 factor. Also provide some, experiments to validate their claim.

Critical strengths

This paper is motivated by the practical adaptivity of the Successive Reject algorithm.

Critical weaknesses

I think the main weakness of this paper is that the phase design is not adaptive. The allocated phase budget does not depend on rewards or the data collected. It only depends on the number of arms. So basically, the phase allocation does not depend on the difficulty or ease of the arm set. So it looks like just hyperparameter tuning rather than an optimization problem. So the contribution seems insignificant.

Improvement also just some constant times, which is not very significant in a theoretical perspective.

Minor mistakes:

Line 74: Appendix reference is absent. Some symbols are referred to before being defined. Problem set up is not explained in the beginning, hence it might be difficult for non-expert reviewers.

Questions for authors

Can't we design phase budget allocation in a data-centric way, rather than this deterministic scheduling ?

6 comments

Thank you for insightful comments. We have revised the papers to address your concerns.

1. Not adaptive

You are right that we consider the class of elimination algorithms in which the phase size is predetermined. We would like to clarify that we derived that H1H_1-SR achieves at least 11/1211/12 of the minimax rate as well as 1−O(1/log⁡K)1 - O(1/\log K) minimax rate, even when compared with fully adaptive policies. In view of minimax rate, which is the standard criterion for evaluating such algorithms, we show that our algorithm is nearly minimax optimal and there is only limited value of adaptivity. Achieving this guarantee despite restricted adaptivity is a central contribution of our work, rather than a limitation.

2. Improvement is just some constant times

We derived an explicit upper bound on the best achievable rate (Theorem 1) as well as a tight rate of our algorithm (Theorem 4). The corresponding information-theoretic upper bound was previously expressed implicitly, as the constant that corresponds to Theorem 1 (Komiyama et al. 2022, Theorem 2 therein) was represented as an optimization that is hard to evaluate. Therefore, even though the original SR is 1/41/4-minimax optimal, this fact was not known before as we did not have an explicit upper bound on the best achievable rate sharp enough to establish this comparison. This fact, combined with our max⁡(11/12,1−O(1/log⁡K))\max(11/12,1-O(1/\log K)) minimax rate, is novel.

3. Presentation.

We have revised the paper and the introduction now explains the arms, noisy observations, fixed budget and error objective before the formal setup in Section 2. We have also corrected the missing appendix reference and clarified the two rate comparisons above. Thank you for your valuable feedback.

Dear Reviewer tj2d,

As the discussion period is coming to an end, we kindly ask you to check our response. Our main points are that (1) the algorithm is compared against the minimax over all adaptive algorithms, and (2) the rate is asymptotically optimal as K→∞K \rightarrow \infty.

Thank you for the revisions.

However, I am still concerned with the significance of this work. It is more of a numerical scheduling tuning than any novel algorithmic contribution.

Say for example, a SH algorithm (sequential halving) in fixed budget best arm identification, uses halving method just to get a theoretical guarantee of particular order, however any exponential fold might work (say keeping only 1/3 of the arms, etc). The order of the bound will be the same except for the base of the logarithmic term.

However, I would not consider finding such a best scheduling for SH (basically affecting the base of logarithmic terms) as a standalone theoretical contribution. It would be for a practitioner or Engineer to figure it out.

I shall raise my score by 1. However, I am still leaning towards rejection.

Karnin, Z., Koren, T., and Somekh, O. Almost Optimal Exploration in Multi-Armed Bandits. In Proceedings of the International Conference on Machine Learning (ICML), pp. 1238–1246, 2013.

Reviewer_3GvsOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper presents H1-SR, a Successive Rejects (SR) algorithm for Gaussian arms. SR takes only sample lengths as parameters, which is attractive to practitioners. Under H1's normalizing factor, the paper shows that H1-SR is optimal for the class of equal-count sampling SR schemes. Moreover, for equal-variance Gaussians, H1-SR achieves at least 11/12 of the optimal normalized rate, which approaches 1 as the number of arms approaches infinity. Ten synthetic and two benchmark experiments show improvements over classical SR in many cases, while reporting one synthetic case where it does not, highlighting the limitations of asymptotic optimality analysis.

Critical strengths
  • The algorithm seems simple and practical. It preserves the familiar SR framework while augmenting it with sharper analysis and optimization on the sampling and phase decisions. The algorithm and its finite-budget guarantee also seamlessly extend to sub-Gaussian and bounded rewards.

  • The optimality analysis is convincing and adds value to H1-SR. The information requirement coefficient of a_s = 2s/(s-1)^2 derived from the simultaneous-rejection bound sounds like a crisp results, and the balancing argument of Proposition 2 seems useful.

  • The experiments report a substantial deterioration on instance 7, showing that improved worst-instance normalized asymptotic rates do not imply pointwise finite-budget dominance.

Critical weaknesses
  • Comparing H1-SR and SR in H1 may be unfair. SR is designed with H2 as its main scoring criterion. Comparing how the guarantees change under H2 would strengthen the conclusion, which currently depends on the choice of H1.

  • Theorem 3’s 2^(K-1) factor is technically a constant when analyzing the behavior of T. However, a moderately large K can make the finite-budget guarantee vacuous. Could the paper elaborate more on this aspect?

  • There are no experiments against other baselines such as Sequential Halving or Continuous Rejects.

Questions for authors
  1. Can the paper comment on whether Theorem 3’s 2^(K-1) term is the best we can expect?
  2. Is it possible to include H2-normalized scores for experiments? This can give a fairer comparison between methods that are designed with different metrics in mind.
  3. Section 1.1 has an unresolved reference “Appendix ??”.
1 comment

Thank you for these suggestions. We revised the paper accordingly. Our algorithm is flexible, and we have updated the paper to extend the rate comparison to H2H_2, added a finite-budget bound with a smaller polynomial prefactor, and expanded the experiments in the appendix.

1. Comparison under H2H_2 scoring criterion.

Appendix J.1 now gives the exact worst-instance rates of SR and H1H_1-SR under H2H_2 normalization. We have also added an algorithm H2H_2-SR, the schedule that optimizes the minimax rate under H2H_2 within the SR class.

For Gaussian arms of common variance σ2\sigma^2, write RH2(A)R_{H_2}(\mathcal A) for policy A\mathcal A's worst-instance normalized rate. The results are (larger better):

Methodσ2RH2\sigma^2R_{H_2} at K=40K=40σ2RH2\sigma^2R_{H_2} as K→∞K\to\infty
SR0.0661630.066163∼1/(4log⁡K)\sim 1/(4\log K)
H1H_1-SR0.0535230.053523∼c⋆/(2log⁡K)\sim c_\star/(2\log K)
H2H_2-SR0.0822740.082274∼1/(2log⁡K)\sim 1/(2\log K)

Here c⋆≃0.84278723c_\star\simeq0.84278723 is derived in Appendix J.1, and the horizon limit is taken first for each fixed KK. The ordering does depend on the complexity: at K=40K=40, SR has a better H2H_2-normalized rate than H1H_1-SR, while H2H_2-SR improves on SR by about 24.3524.35\\%.

We further prove that H2H_2-SR is optimal up to 1−O(1/log⁡K)1-O(1/\log K), which implies this algorithm is asymptotically minimax, among any algorithms, including general and more adaptive best arm identification algorithms. At K=40K=40, the all-policy upper bound certifies at least 82.482.4\\% of the optimum.

Empirical results: The same appendix adds H2H_2-SR to the twelve original experiments, with 10,00010{,}000 runs per instance. We report terminal PoE: at fixed instance PP and horizon TT, the score −H2(P)log⁡p^T/T-H_2(P)\log\widehat p_T/T is a monotone transformation of the same empirical error p^T\widehat p_T: lower error means a higher normalized score.

2. The exponential prefactor at large KK and modest TT.

The factor 2K−1−12^{K-1}-1 comes from a union over possible surviving subsets; we do not consider it is necessary. To address this, Appendix J proves another bound with smaller prefactor: Namely, Let ms(T)m_s(T) be the (predetermined) total number of samples collected from each remaining arm by the end of the phase with ss arms, including samples from earlier phases, and let pTp_T be the error probability. Then

\exp\\!\left[-\frac{\min_{2\le s\le K}s\\,m_s(T)} {4\sigma^2H_2(P)}\right]\right\\}.$$ At $K=40$, the prefactor is $780$, compared with $2^{39}-1\simeq 5.50\times10^{11}$. Instead, the exponent in this bound is loose up to a constant factor $4$. ### 3. **Additional baselines and the missing reference.** Appendix L now compares sixteen methods on the original twelve instances and horizons, with $10{,}000$ runs per entry. These include CR-A/CR-C, Simple/Almost Tracking, top-two methods, Sequential Halving variants and nonlinear elimination. The expanded comparison shows that $H_1$-SR is competitive with these alternatives. The unresolved reference in Section 1.1 has also been corrected.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.