Best Arm Identification (BAI) conventionally measures the cost of experimentation by the number of samples collected. In many operational settings, however, the cost of exploration relative to a trusted baseline already in place is equally important. We study BAI under both a fixed sampling horizon and a regret budget. Unlike generic resources considered in constrained pure exploration, regret has a distinctive structure: sampling better arms is less costly relative to the baseline. We theoretically show that the regret cost of exploration decreases across the phases of Sequential Halving, a widely used pure-exploration algorithm. This observation yields improved guarantees on the probability of identifying the best arm and motivates a more effective allocation of the regret budget. We propose Sequential Halving with Proportional Regret Rationing (SHPRR), which front-loads the regret budget to allow more exploration when many arms remain. Experiments on synthetic and real-world instances show that SHPRR improves best-arm identification performance over uniform regret allocation and existing baselines.
Figures & tables
Figure 1: SP and NSR across synthetic ( top ) and real-world ( bottom ) environments.
Figure 2: SP across the four synthetic environments as δ varies from 0.3 to 0.
Figure 3: Performance analysis across three baseline arm selection criteria (from left to right): best arm, top 1%, and top 5%, evaluated under varying budget levels.
Figure 4: Phase-wise arm quality under a Poly reward configuration. Boxplots show the mean reward distribution among surviving arms at each phase, for four SHPRR variants with α∈{0.0,0.2,0.8,1.0} . Significance brackets indicate t -tests paired across seeds against the α=0.0 reference ( SH-RR ); a star ( ⋆ ) marks the highest mean at each phase. Phase 9 is the final recommended arm.
Appendix figures & tables3 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 1: Reward distributions in the four baseline configurations of the synthetic environments.
Figure 2: Arm reward distributions in the four real-world environments: the three New Yorker Caption Contests (c511, c538, c780) and Criteo. Arms are sorted by mean reward in descending order.
Figure 3: Phase-wise arm quality under a polynomial reward family, for β∈{0.25,0.5,0.75,1.0} .
In many applications, evaluating the effectiveness of different alternatives comes with varying costs or resource usage. Motivated by such heterogeneity, we study the Best Arm Identification with Resource Constraints (BAIwRC) problem, where an agent seeks to identify the best alternative (aka arm) in the presence of resource constraints. Each arm pull consumes one or more types of limited resources. We make two key contributions. First, we propose the Successive Halving with Resource Rationing (SH-RR) algorithm, which integrates resource-aware allocation into the classical successive halving framework on best arm identification. The SH-RR algorithm unifies the theoretical analysis for both the stochastic and deterministic consumption settings, with a new \textit{effective consumption measure
Zitian Li, Wang Chi Cheung
Department of Industrial Systems Engineering & Management, National University of Singapore, Singapore
We introduce Box Thirding (B3), a flexible and efficient algorithm for Best Arm Identification (BAI) under fixed-budget constraints. It is designed for both anytime BAI and scenarios with large N, where the number of arms is too large for exhaustive evaluation within a limited budget T. The algorithm employs an iterative ternary comparison: in each iteration, three arms are compared--the best-performing arm is explored further, the median is deferred for future comparisons, and the weakest is discarded. Even without prior knowledge of T, B3 achieves an epsilon-best arm misidentification probability comparable to Successive Halving (SH), which requires T as a predefined parameter, applied to a randomly selected subset of c0 arms that fit within the budget. Empirical results show that B3 outperforms existing methods under limited-budget constraints in terms of simple regret, as demonstrated on the New Yorker Cartoon Caption Contest dataset.
Seohwa Hwang, Junyong Park
Department of Statistics, Seoul National University, Seoul, Republic of Korea
In fixed-budget best-arm identification, also known as ranking and selection, an algorithm has a sampling budget to distribute across K arms. Each sample provides noisy feedback about that arm's mean, and the goal is to identify the arm with the largest mean. A common performance benchmark is the static oracle: a non-adaptive strategy that knows the means in advance and chooses fixed sampling proportions to maximize the exponential decay rate of the probability of incorrect identification. Several adaptive algorithms have been constructed such that their sampling proportions converge to the static oracle proportions. However, it has remained open whether any algorithm could match the static oracle's error decay rate uniformly across all problem instances. We answer this in the negative. For any K≥3 and for rewards drawn from any one-parameter natural exponential family, we show that for any algorithm, there is at least one instance where the error decay rate is at most (1+8log(K))−1 times that of the static oracle. This also answers the open question posed by Qin (2022), showing that fixed-budget best-arm identification does not admit a complexity.