PaperlayerView exact revision on arXiv

Source-linked AI summary

Rethinking Successive Rejects Algorithms

Mohamed Khair, Junpei Komiyama

arXiv:2610.22051v1stat.MLcs.LG

TL;DR

Best-arm identification asks how to allocate a fixed observation budget to find the arm with the largest mean, while SR’s fixed schedule may not match the difficulty of avoiding mistaken eliminations. This paper optimizes SR’s schedule to form H1-SR. For Gaussian arms, it achieves at least 11/12 of the optimal H1-normalized rate for every K, with the certified fraction approaching one as K grows.

  • Problem

    SR fixes its phase lengths, leaving open whether that schedule is well matched to the statistical difficulty of avoiding erroneous eliminations.

    Source: §1 · pp. 1–2

  • Method

    The paper optimizes the phase schedule by bounding adaptive algorithms’ H1-normalized rate and solving a deterministic balancing problem for equal-count SR schedules.

    Source: §1 · p. 2

  • Results

    H1-SR achieves at least 11/12 of the optimal Gaussian H1-normalized rate for every K, with its certified fraction tending to one as K grows, while original SR approaches 1/4.

    Source: §5 · p. 9

  • Takeaways & Limitations

    H1-SR spends less before early eliminations and more on final comparisons, where fewer arms remain.

    Source: §3.2 · p. 8

    The adaptive-algorithm theorem is a worst-instance asymptotic restriction, not a finite-budget lower bound for every individual instance.

    Source: §2.2 · p. 5

Abstract

from arXiv · show

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\ge2$, and this approximation ratio converges to one as $1-O(1/\log K)$ as $K\to\infty$. 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.

1 INTRODUCTION

Successive Rejects uses fixed phase lengths, leaving open whether its schedule is matched to the difficulty of avoiding erroneous eliminations. This section motivates optimizing that schedule and compares the resulting H1-SR with adaptive-algorithm benchmarks and prior work.

1 INTRODUCTION

  • SR uses K −1 fixed phases, sampling surviving arms equally before eliminating the arm with the smallest cumulative empirical mean.The introduction frames the phase schedule as the remaining design choice once this rejection rule is fixed.Source: §1 · pp. 1–2

1.1 HOW SHOULD WE COMPARE IDENTIFICATION ALGORITHMS?

  • H1 measures instance difficulty through gaps to the best arm, and the comparison benchmark is the best normalized rate over all adaptive algorithms.The algorithm is evaluated using H1 but does not take the true gaps as input.Source: §1.1 · p. 2

1.2 CONTRIBUTIONS

  • Across ten synthetic and two dataset-derived Gaussian benchmarks, H1-SR often improves terminal error, but the experiments also show a finite-budget failure case.The failure case cautions against reading the asymptotic worst-instance guarantee as pointwise dominance.Source: §1.2 · p. 2

1.3 RELATED WORK

  • Earlier work studied general sequential-elimination schedules without characterizing their optimal phase lengths; Continuous Rejects instead chooses lengths dynamically.The paper positions its schedule optimization as distinct from these prior approaches.Source: §1.3 · pp. 2–3

2 FROM ARBITRARY ADAPTIVE ALGORITHMS TO AN OPTIMIZED REJECTION

The paper bounds the H1-normalized rate available to adaptive algorithms, then optimizes deterministic equal-count schedules for successive rejection. The resulting H1-SR schedule is class-optimal and approaches the unrestricted Gaussian rate as the number of arms grows.

2.1 MODEL AND PERFORMANCE CRITERION

  • The performance criterion compares worst-instance error exponents after normalizing by H1, the instance complexity based on inverse squared gaps to the best arm.H1 increases as competitors approach the best arm, reflecting the greater difficulty of distinguishing their means.Source: §2.1 · p. 4

2.2 AN INFORMATION BOUND FOR EVERY ADAPTIVE ALGORITHM

  • R*_K is bounded by an explicit information constraint for Gaussian arms, and this is a worst-instance asymptotic restriction, not a finite-budget bound for every instance.The bound concerns the H1-normalized rate attainable by arbitrary adaptive algorithms.Source: §2.2 · p. 5

2.4 HOW THE DETERMINISTIC SCHEDULE CONTROLS PERFORMANCE

  • A phase’s error bound depends on its surviving-arm count, so the schedule balances checkpoint counts to prevent any active-set size from becoming the bottleneck.The analysis bounds the cost of empirical means that make the true best arm appear worst.Source: §2.4 · p. 6

2.5 A SMALL BALANCING PROBLEM WITH AN EXPLICIT SOLUTION

  • H1-SR uniquely maximizes the guaranteed normalized exponent within deterministic equal-count SR schedules, attaining value 1/D_K with checkpoint fractions q_s = a_s/D_K.The schedule class preserves equal sampling of surviving arms and rejects an arm with a smallest empirical mean.Source: §2.3 · p. 5, §2.5 · p. 6

2.6 THE RESULTING ALGORITHM AND ITS GUARANTEE

  • At finite horizon, H1-SR implements the optimized checkpoint fractions by integer rounding and removes the active arm with the smallest empirical mean at each checkpoint.Each phase adds samples to every remaining arm until all have the same cumulative count.Source: §2.6 · p. 7
  • For independent σ^2-sub-Gaussian rewards, the fixed-instance error exponent is at least 1/(σ^2D_KH1(P)); for Gaussian arms, the asymptotic rate is exactly 1/(σ^2D_K).The Gaussian equality follows from a matching upper bound.Source: §2.6 · p. 7

2.7 CLASS OPTIMALITY AND COMPARISON WITH ANY ALGORITHM

  • As K grows, H1-SR’s normalized rate approaches the unrestricted optimum, with B_K/D_K = 1−O(1/log K) and R*_K ∼ 1/(2σ^2 log K).The comparison takes the fixed-K horizon limit before K tends to infinity.Source: §2.7 · p. 8

3 H1-SR VERSUS ORIGINAL SUCCESSIVE REJECTS

H1-SR improves the worst-instance normalized rate over original SR and shifts sampling effort toward later comparisons. Its rate advantage is asymptotic and does not imply pointwise finite-budget dominance.

3.1 SHARP NORMALIZED-RATE COMPARISON

  • For K ≥3, H1-SR has a strictly better worst-instance normalized exponent than original SR, with a fourfold advantage for large K.For Gaussian arms, original SR's normalized rate is 1/(8σ^2 log(K)).Source: §3.1 · p. 8
  • For general σ^2-sub-Gaussian arms, the finite-budget bound has prefactor K(K −1)/2 rather than the Gaussian K(K −1)/4.The exact-rate and minimax comparisons are Gaussian.Source: §3.1 · p. 8

3.2 INTUITION ON THE RATIO

  • The H1-SR-to-original-SR allocation ratio rises as fewer arms remain, spending less before early eliminations and more on final comparisons.The final-two ratio tends to 4 as K grows.Source: §3.2 · p. 8

4 NUMERICAL EXPERIMENTS

Across twelve fixed-horizon Gaussian benchmarks, H1-SR often has lower empirical terminal error than original SR, though one instance favors SR and two comparisons are inconclusive.

4 NUMERICAL EXPERIMENTS

  • The twelve fixed-horizon Gaussian problems comprise ten synthetic instances with K = 40, MovieLens 1M with K = 31, and Open Bandit with K = 80.Each cell uses 10,000 repetitions at its configured horizon.Source: §4 · p. 9
  • Table 1 shows lower empirical terminal error for H1-SR on 10 of 12 instances; Holm-corrected tests support H1-SR on nine, SR on one, and neither on two.The table reports terminal error over 10,000 repetitions.Source: Table 1 · p. 9, §4 · p. 9
  • On MovieLens, the H1-SR-to-SR error ratio is 0.735, while synthetic instance 7 has ratio 3.189.In instance 7, H1-SR uses 27 versus 53 observations per arm before the first elimination, but 2023 versus 1054 at the final-two checkpoint.Source: §4 · p. 9

5 CONCLUSION AND LIMITATIONS

The paper optimizes deterministic SR checkpoints to obtain H1-SR, which is optimal within that schedule class and approaches the optimal Gaussian H1-normalized rate. Finite-budget experiments show gains on many instances but also a non-dominance case.

5 CONCLUSION AND LIMITATIONS

  • H1-SR is optimal among deterministic equal-count SR-type schedules and achieves at least 11/12 of the optimal Gaussian H1-normalized rate for every fixed K.Its certified fraction tends to one as K grows, while original SR approaches 1/4.Source: §5 · p. 9
  • Experiments show finite-budget gains on many instances but also a clear case where H1-SR does not dominate original SR.The finite-budget bound extends to independent sub-Gaussian rewards; matching optimality beyond Gaussian rewards remains open.Source: §5 · p. 9

A EXPERIMENTAL INSTANCES AND TRAJECTORY PLOTS

The appendix describes ten synthetic and two dataset-derived Gaussian instances and presents error trajectories for subsets of those benchmarks.

A EXPERIMENTAL INSTANCES AND TRAJECTORY PLOTS

  • The ten synthetic benchmarks use K = 40 independent unit-variance Gaussian arms; the other two derive their means from MovieLens 1M and Open Bandit.The synthetic configurations follow the benchmark family used by Komiyama et al. (2026).Source: A EXPERIMENTAL INSTANCES AND… · p. 12

A.1 TRAJECTORY PLOTS

  • Figures 2 and 3 show empirical error trajectories for synthetic instances 1–10 and the MovieLens 1M and Open Bandit-derived instances.Figure 2's terminal points correspond to the fixed-horizon results in Table 1.Source: §A.1 · p. 12, Figure 2 · p. 13, Figure 3 · p. 14
  • At t < T, each plotted point is an intermediate recommendation from the same T-configured run, so the trajectories are not anytime guarantees.The curves use pointwise exact 95% binomial intervals and a logarithmic vertical axis.Source: §A.1 · p. 12

B JOINT REJECTION BOUNDS AND GAUSSIAN SHARPNESS

The section bounds the probability that the best arm is jointly rejected using a fixed-subset geometric argument, then establishes Gaussian sharpness. The equal-gap case has an explicit minimizing geometry, while an upper bound alone does not establish an exact exponent.

B JOINT REJECTION BOUNDS AND GAUSSIAN SHARPNESS

  • At a common deterministic count, the best arm’s probability of having the smallest sample mean is bounded using the joint rejection event and sub-Gaussian concentration.The proof uses independent potential-reward streams and does not condition sample-mean laws on survival.Source: B JOINT REJECTION BOUNDS AND GAUSSIAN… · p. 15
  • The closest point in the rejection region is optimized over a shared shift u, yielding a squared-distance lower bound of (s−1)^2/(sH_A).For each competitor, the closest feasible coordinate is max{−δ_j, −u}; values u < 0 cannot improve the minimum.Source: B JOINT REJECTION BOUNDS AND GAUSSIAN… · p. 15
  • An error upper bound alone does not establish an exact exponent; the Gaussian lower bound is used for the hard instances.Source: B JOINT REJECTION BOUNDS AND GAUSSIAN… · p. 16
  • For equal gaps, the minimizing vector has every coordinate −(s−1)∆/s and squared distance (s−1)∆^2/s.The Gaussian lower-bound argument establishes the exact rate in this equal-gap case.Source: B JOINT REJECTION BOUNDS AND GAUSSIAN… · p. 16

C THE BALANCED CLOCK AND ITS GAUSSIAN WORST-INSTANCE RATE

The balanced clock assigns sampling fractions in proportion to phase coefficients, attaining the schedule’s max–min balance and a Gaussian worst-instance rate bound. Within SR-type algorithms with deterministic common checkpoints, no schedule has a better normalized rate.

C THE BALANCED CLOCK AND ITS GAUSSIAN WORST-INSTANCE RATE

D OPTIMALITY WITHIN THE CLASS OF SR-TYPE ALGORITHMS

  • For every SR-type algorithm with deterministic common checkpoints, the normalized rate is at most 1/(σ^2D_K), attained by H1-SR.The converse constructs an instance difficult at each possible checkpoint; a positive rate requires q_K>0.Source: D OPTIMALITY WITHIN THE CLASS OF… · pp. 17–18

E A CONVERSE FOR ALL ADAPTIVE ALGORITHMS

The converse bounds the best normalized rate achievable by any adaptive algorithm for common-variance Gaussian arms. It uses a single allocation vector to impose information constraints across alternatives and prefixes.

E A CONVERSE FOR ALL ADAPTIVE ALGORITHMS

F THE EXACT EXPONENT OF ORIGINAL SUCCESSIVE REJECTS

For Gaussian rewards, original Successive Rejects has an exact worst-instance normalized exponent. The section also gives finite-budget bounds and distinguishes the Gaussian-specific prefactor from the sub-Gaussian guarantee.

F THE EXACT EXPONENT OF ORIGINAL SUCCESSIVE REJECTS

G UNIFORM FACTORS AND THE LARGE-ARM LIMIT

H1-SR’s normalized rate is at least 11/12 of the optimal rate for every K, and the section characterizes how its improvement over SR behaves as K grows.

G UNIFORM FACTORS AND THE LARGE-ARM LIMIT

  • For K = 2, H1-SR is optimal; for K ≥ 3, its rate ratio B_K/D_K is greater than 11/12.The section uses 11/12 as a convenient uniform lower bound, not the exact minimum.Source: G UNIFORM FACTORS AND THE LARGE-ARM… · p. 21
  • As K grows, both B_K and D_K equal 2 log K + O(1), while 8log(K) equals 8 log K + O(1).The section also notes that the achieved rate cannot exceed the all-algorithm optimum.Source: G UNIFORM FACTORS AND THE LARGE-ARM… · pp. 21–22
  • 8log(K)/D_K → 4 is the exact improvement of the balanced rate over SR in the fixed-K asymptotic error-exponent limit.The horizon limit is taken first; the result does not require discarding a K-dependent finite-budget prefactor when K grows with T.Source: G UNIFORM FACTORS AND THE LARGE-ARM… · p. 22

H NON-DOMINANCE OF H1-SR OVER ORIGINAL SR

H1-SR’s worst-instance normalized asymptotic optimality does not imply fixed-budget dominance over original SR. The section also relates the largest inverse-gap term to H1 and reports how the two complexity measures compare.

H NON-DOMINANCE OF H1-SR OVER ORIGINAL SR

  • H1-SR’s worst-instance normalized asymptotic rate does not guarantee fixed-budget dominance; performance can trade off across distributions.The paper contrasts this with fixed-confidence algorithms that attain instance-dependent lower bounds asymptotically as δ → 0.Source: H NON-DOMINANCE OF H1-SR OVER ORIGINAL… · p. 22
  • On synthetic instance 7 at T = 8000, original SR outperforms H1-SR, which takes 27 observations per arm before the first elimination versus 53 for SR.The instance has one best arm with mean 1 and 39 competitors with mean 0.8, with unit-variance Gaussian rewards; the first elimination matters most to correct identification.Source: H NON-DOMINANCE OF H1-SR OVER ORIGINAL… · p. 22

I THE INVERSE-GAP COMPLEXITY MEASURES

  • The largest of the K − 1 terms in H1 lies between H1/(K − 1) and H1.The original SR complexity assigns the best arm the artificial gap Δ(2) and includes its inverse square.Source: I THE INVERSE-GAP COMPLEXITY MEASURES · p. 22

Related papers

Loading 2610.22051v1…