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
Figures & tables
Figure 1: Convergence rates of log(Pr(ψ=1)) , with 107 repeated trials
Figure 2: Comparison of SH-RR and anytime baselines in different setups
Algorithm
MNIST 3&8
Handwritten
SHRR
0
0.12
ATLUCB
0.21
0.23
UCB
0.21
0.34
Uniform
0.21
0.25
DSH
0.14
0.20
Table 1: Failure Probability of different BAI strategies on Real-life datasets
Algorithm
Arcene
Obesity
MADELON
SHRR
0.38
0.31
0
ATLUCB
0.6
0.43
0.42
UCB
0.71
0.43
0.30
Uniform
0.81
0.56
0.29
DSH
0.67
0.54
0.12
Table 2: Failure Probability of different BAI strategies on Real-life datasets, cont.
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
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.