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.
Figures & tables
Figure 1: Toy example of remedian estimation: partition the data into three blocks and take their within-block medians (2.8,5.3,4.8) ; taking the median of these medians yields 4.8 . Repeating this hierarchical “median-of-medians” construction produces an estimator that converges in probability to the population median.
Figure 2: Illustration of ARRANGE_BOX ( l,j;D ) when μ^i1>μ^i2>μ^i3 . The DISCARD operation is omitted for clarity.
Figure 3: Fraction of arms that are lifted, shifted, and discarded at a fixed level l .
Figure 4: Simulation results on the NYCCC 893 dataset under three reward noise regimes. Curves indicate mean performance and shaded regions denote the 25%–75% quantile range.
Appendix figures & tables3 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 5: Simulation results on the NYCCC 893 dataset under different reward distributions. Curves indicate the mean performance, and shaded regions correspond to the 25%–75% quantile range.
Algorithm
Knowledge of T
Average Simple Regret
25% Quantile
75% Quantile
B3 (Ours)
No (Anytime)
0.0490
0.0290
0.0682
SH ( r0=1.7 )
Yes (Fixed)
0.0446
0.0281
0.0652
SH ( r0=2.0 )
Yes (Fixed)
0.0516
0.0290
0.0682
UCB-E
Yes (Fixed)
0.0664
0.0502
0.0749
BSH
No (Anytime)
0.0992
0.0587
0.1569
BUCB
No (Anytime)
0.1252
0.0682
0.1769
Appendix
Table 1: Simple regret for N=128 and T=896 ( T=Nlog2N ).
Algorithm
Knowledge of T
Average Simple Regret
25% Quantile
75% Quantile
B3 (Ours)
No (Anytime)
0.0268
0.0000
0.0502
SH ( r0=1.7 )
Yes (Fixed)
0.0195
0.0000
0.0290
SH ( r0=2.0 )
Yes (Fixed)
0.0288
0.0000
0.0507
UCB-E
Yes (Fixed)
0.0403
0.0222
0.0588
BSH
No (Anytime)
0.1531
0.0661
0.2475
BUCB
No (Anytime)
0.2558
0.2374
0.3039
Appendix
Table 2: Simple regret for N=1,024 and T=10,240 ( T=Nlog2N ).
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
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.
We study fixed budget constrained best-arm identification in grouped bandits, where each arm consists of multiple independent attributes with stochastic rewards. An arm is considered feasible only if all its attributes' means are above a given threshold. The aim is to find the feasible arm with the largest overall mean. We first derive a lower bound on the error probability for any algorithm on this setting. We then propose Feasibility Constrained Successive Rejects (FCSR), a novel algorithm that identifies the best arm while ensuring feasibility. We show it attains optimal dependence on problem parameters up to constant factors in the exponent. Empirically, FCSR outperforms natural baselines while preserving feasibility guarantees.
Raunak Mukherjee, Sharayu Moharir
Indian Institute of Technology, Bombay · Dept. of Electrical Engineering, IIT Bombay