- 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 the authors for their response. I have raised my score accordingly. However, my concern about the novelty of the algorithm remains.
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 H1-SR, while using predetermined checkpoints, achieves near-minimax performance under H1. H1-SR achieves at least 11/12 of the optimal worst-instance H1-normalized rate for every K≥2, and a fraction 1−O(1/logK) as K→∞, taking the horizon limit first. Therefore, in view of minimax optimality, the predetermined checkpoints of H1-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 H1-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 H1-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,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 H1-SR is competitive with the other methods despite its simple schedule. The probability-of-error percentages (smaller better) on all twelve instances are:
These results illustrate both the practical gains of our methods.
3. Dependence on the complexity measure H1.
Our framework extends to other complexity measures beyond H1. In particular, our revision has added a concrete extension in Appendix J.1: H2-SR, obtained by optimizing the exact H2-normalized rate over the same SR class. For Gaussian arms with common variance, it is asymptotically minimax among all adaptive policies as K grows. Writing RH2(A) for policy A's worst-instance normalized rate and RH2,K⋆ for the unrestricted optimum (including any adaptive algorithm), we establish the following, taking the horizon limit first for each fixed K and numerically evaluating the explicit lower bound for 2≤K≤40:
\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.