Successive Rejects
A classical fixed-budget best-arm identification algorithm that divides the total budget into several phases, eliminating the worst-performing candidate arm in each phase. It belongs to the class of limited adaptive sampling strategies.
Timeline (last 90 days)
Successive Rejects (SR) is a classic fixed-budget best-arm identification algorithm that eliminates one candidate arm per round, with the length of each stage set in advance.
For Gaussian arms with a common variance, SR's worst-case error exponent (after normalization by H₁(P)) is already optimal up to a constant factor.
A recent study formalized the design of SR's stage schedule as an optimization problem over the normalized error exponent, and proposed a new variant, H₁-Balanced Successive Rejects (H₁-SR).
The corresponding ratio to the optimal normalized rate for the original SR algorithm converges to only 1/4.
The study conducted experiments on ten synthetic instances and two dataset-based Gaussian benchmarks, comparing the optimized schedule with the original SR over a finite time horizon.
The computational overhead of H₁-SR is almost comparable to that of the original SR.
All Facts (6)
Successive Rejects (SR) is a classic fixed-budget best-arm identification algorithm that eliminates one candidate arm per round, with the length of each stage set in advance.
50%UnverifiedFor Gaussian arms with a common variance, SR's worst-case error exponent (after normalization by H₁(P)) is already optimal up to a constant factor.
50%UnverifiedThe corresponding ratio to the optimal normalized rate for the original SR algorithm converges to only 1/4.
50%UnverifiedThe computational overhead of H₁-SR is almost comparable to that of the original SR.
50%UnverifiedA recent study formalized the design of SR's stage schedule as an optimization problem over the normalized error exponent, and proposed a new variant, H₁-Balanced Successive Rejects (H₁-SR).
50%UnverifiedThe study conducted experiments on ten synthetic instances and two dataset-based Gaussian benchmarks, comparing the optimized schedule with the original SR over a finite time horizon.
50%