Balancing Performance and Costs in Best Arm Identification
Authors: Michael O Harding
Kirthevasan Kandasamy
Venue: NeurIPS 2025 poster ()
Keywords: Bandit Algorithms
Exploration
Primary area: general_machine_learning

Abstract: We consider the problem of identifying the best arm in a multi-armed bandit model. Despite a wealth of literature in the traditional fixed budget and fixed confidence regimes of the best arm identification problem, it still remains a mystery to most practitioners as to how to choose an approach and corresponding budget or confidence parameter. We propose a new formalism to avoid this dilemma altogether by minimizing a risk functional which explicitly balances the performance of the recommended arm and the cost incurred by learning this arm. In this framework, a cost is incurred for each observation during the sampling phase, and upon recommending an arm, a performance penalty is incurred for identifying a suboptimal arm. The learner's goal is to minimize the sum of the penalty and cost. This new regime mirrors the priorities of many practitioners, e.g. maximizing profit in an A/B testing framework, better than classical fixed budget or confidence settings. We derive theoretical lower bounds for the risk of each of two choices for the performance penalty, the probability of misidentification and the simple regret, and propose an algorithm called DBCARE to match these lower bounds up to polylog factors on nearly all problem instances. We then demonstrate the performance of DBCARE on a number of simulated models, comparing to fixed budget and confidence algorithms to show the shortfalls of existing BAI paradigms on this problem.

Balancing Performance and Costs in Best Arm Identification
Michael O. Harding
Kirthevasan Kandasamy Department Computer Science University of Wisconsin-Madison kandasamy@ca cs wisc. edu
Department of Statistics University of Wisconsin-Madisee mohardingowisc.
Abstract
We consider the problem identifying the best arm a multi-armed bandit model. Despite wealth of literature in the traditional fixed budget and fixed confidence regimes the best arm identification problem, it still remains a mystery to most practitioners to how to choose approach and corresponding budget confi- dence parameter. We propose a new formalism to avoid this dilemma altogether by minimizing risk functional which explicitly balances the performance of the rec- ommended arm and the cost incurred by learning this arm. In this framework, a cost is incurred for each observation during the sampling phase, and upon recommend- ing an arm, a performance penalty is incurred for identifying a suboptimal arm. The learner's ss goal is minimize the sum of the penalty and cost. This new regime mirrors the priorities of many practitioners, e.g. maximizing profit in an A/B testing framework, better than classical fixed budget or confidence settings. We derive theoretical lower bounds for the risk of each of two choices for the performance penalty, the probability of misidentiiication and the simple regret, and propose an algorithm called DBCARE to match these lower bounds up to polylog factors on nearly all problem instances. We then demonstrate the performance of DBCARE on a number of simulated models, comparing to fixed budget and confidence algorithms show the shortfalls of existing BAI paradigms on this problem.
1
Introduction
Best Arm Identification (BAI) in multi-armed bandits is a fundamental problem in decision-making under uncertainty. The objective is to identify the arm with the highest expected reward by adaptively drawing samples from distributions associated with each arm. BAI arises in many real-world appli- cations. In advertising, arms represent different ads, and the aim is to find the ad which maximizes revenue generated [18]. statistical model selection, arms represent different hyperparameter config- urations, and the aim is to find the best-performing one with minimal computational resources [20].
Traditionally, BAI has been studied under two paradigms: the fixed budget setting [2, 8], which seeks to maximize performance-ia. the ability of policy to recover the optimal arm-within given sampling budget, and the fixed performance (e.g., fixed confidence [33, 15]) setting, which aims to minimize the number of samples needed to meet target performance level. While algorithms for these settings have been successfully deployed in many real-world settings [32, 35, 51, 18), these settings
natural fit for all use cases. For instance, while determining the best arm is desirable, a slightly suboptimal choice may be acceptable if the cost of distinguishing between top candidates is prohibitively high. On the other hand, it is often unnecessary to continue sampling until reaching some pre-specified horizon when there is already enough evidence to determine the optimal arm.
To this end, we propose novel paradigm for BAI, in which a policy should explicitly balance performance and sampling cost on the fly, without being constrained by fixed performance level or pre-specified sampling budget. This framework allows policies to adaptively terminate according to the difficulty of the problem. The following is an example where such a framework would be natural.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Example (Advertising). Consider a firm choosing among K versions of an ad. To inform its choice, the firm may show versions to participants in a focus group (arm pull), incurring a cost c per showing. The firm wishes to choose an algorithm to maximize the expected profit, i.e. the expected revenue of the selected ad (1) minus the expected cost of the sampling procedure: Elrevenueyl cBI# arm pulls]. Letting 1* be the ad with the highest expected revenue, then maximizing expected profit can be equivalently stated as minimizing E E-veeemee-- budget or confidence algorithms would be a poor for this problem, as it is unclear how one should choose the budget or confidence level to optimize the objective.
revemuejl + cE arm pulls). Traditional fixed
1.1 Model
We will now formally introduce our setting. learner has access to a MAB model { Ja[[ which consists of K arms, each associated with a probability distribution Pa- Let pa. Ev, [X] denote the expected reward of arm a. Following common conventions in the BAT literature, we assume without loss of generality that the arms are ordered so that μ11 142 2 2 j'K (the learner is unaware of this ordering). We will assume that for each arm a E [K], the distribution Vo is and that μaa E [0, B). The learner is aware of a and B.
A learner interacts with the bandit model over a sequence of rounds t = 1, On round f. the learner selects
A E [K] according to a policy and observes an independent sample X; drawn from VA,, The choice of A, may depend the history {(Ag. X,) )==)== of previous actions and observations. Upon termination, the policy recommends an arm 7 E [K] as the estimated best arm.
Prior work. Traditionally, BAI has been studied under two main regimes: (1) Fixed budget: The learner is allowed at most T E N samples and aims minimize either the probability of misidentification [2] [P( * (67) or the simple regret [8] Eljn -My]. i.c. the expected gap between the optimal and selected arms. (2) Fixed performance: The learner must satisfy specified performance goal while minimizing the number of samples. The most common instantiation is sxeedcoofidence BAI [6, 16]. where the probability of misidentification P(P1 + m7) most given goal 6.
This work. Both the fixed-budget and pereopperfomancc formulations neglect practical situations where one may not have a pre-specified budget performance goal, but would like to trade-off between performance and sampling cost based on problem difficulty. Motivated by such consid- erations, we propose new setting, where the goal is minimize risk functional that captures both a performance penalty and the cumulative sampling cost. Choosing either the probability of misidentification or the simple regret as the penalty, we study the following two risk measures:
RMI(T, 2/ == Ex,x [1 (#1 * (p) + CT] = Pu, (#1 # p7) + [T. RSR(T, v) == F [M1 - 11) + = Eu,= [M1 11 + (EE.=(T))
(1)
Here, e >> 0 the (known) cost required to collect a sample, relative to the performance penalty, and is the stopping time (total number of samples) of the policy л. Moreover, IP,,, and E, denote the probability and expectation with respect to all randomness arising from the interaction between the policy π and the bandit model v.
1.2 Summary of our contributions and results
Novel problem formalism. To the best of our knowledge, we are the first study this risk-based formalism for BAI which trades off between performance and sampling costs. We design policies for both risk measures in (1), upper bound the risk, and provide nearly matching lower bounds.
Lower bounds. To summarize our lower bounds, let A = #1 - denote the sub-optimality gap of arm k, and let H == Σk 2 AF² be a problem complexity parameter [33, 15, 26, 21, 28, 30]. We show that the problem difficulty exhibits a phase transition depending on the magnitude of H and the smallest gap A2. Specifically, in the case of RMI, when H E (((oac)-1) we show that RAT E Ω (co2H log
and otherwise, RAI E 2(1). In the case of RSR. when HA, E ((( we show that RSR E Ω (co²H log (o(cc"H)-1)) and otherwise, RSR E 2(42). This phase transition-absent the trade-off between performance and costs inherent to our setting: probabilistically distinguishing sub-Gaussian arms scales inversely with the size of the gaps between them, so with small enough gaps it becomes optimal to simply guess the best arm without incurring the cost of sampling.
classical fixed-confidence or fixed- Exddebbudget settings-
2

---

Proof ideas. Our proof employs change-of measure arguments to lower bound the risk associated with any particular algorithm via an auxiliary function of problem parameters and the expected stopping time of the algorithm, (x,((7] [7]. Crucially, this function is convex in By.=[T], and minimizing it with respect to [T)) yields lower bounds on the performance of any algorithm while additionally revealing the phase transition behavior, via the regions where E2,x [r] = 0 is optimal.
Algorithm. We propose DBCARE (Dynamically Budgeted Cost-Adapted Risk disk-minimizing
Elimination) for this setting. DBCARE maintains a subset S c [K] of surviving arms and confi- dence intervals for the mean values of these arms. It takes as input a function N : N - N of the size of S, which determines the maximum number of times each arm in S may be pulled. It proceeds in epochs, where in each epoch, every surviving arm is pulled once. At the end of each epoch, DBCARE eliminates arms that can be confidently identified as suboptimal based on the confidence intervals. If any arms are eliminated, the budget for each surviving arm is updated based on N If the budget of arm pulls is exhausted before there is a clear winner, i.e. only one surviving arm, it recommends the surviving arm with the highest empirical mean. However, a clear winner emerges before the current budget, it terminates early and recommends this arm.
DBCARE combines ideas from both fixed-budget and fixed-confidence algorithms for BAI. However, unlike fixed budget algorithms, the budget is not given in advance; rather, the total number of times an arm can be pulled is determined by the function N which depends on the risk (1), the cost c, and the size of the current surviving set S. Similarly, unlike algorithms for fixed confidence BAI [24, 21], the confidence intervals are carefully chosen based on problem parameters, and not via a prespecified failure probability target 5. This design allows DBCARE to adapt to the problem difficulty with respect to the gaps and cost, while simultaneously ensuring control over the worst-case risk.
Upper bound. We show that the above algorithm, with carefully chosen parameters, matches the lower bounds in almost all regimes. Specifically, for RMI, our algorithm matches the lower bound up to polylog factors for all values of the complexity parameter H. For RSR, we similarly match the lower bound up to polylog factors when H is not too large. However, when H + 00, our upper bound scales as Ologg( (K) (KK22c)) while the lower bound is (2))), leaving an additive gap.
Despite this discrepancy in the Rsn case, we make two important observations. First, we show that our algorithm is minimax optimal; that is, the worst-case risk over all problem instances matches the worst-case lower bound up to logarithmic factors. Second, the lower bound in the large H regime is tight and cannot be improved: a naive guessing algorithm-ove one that selects an arm without pulling any-achieves the lower bound on certain problem instances in this region. However, such a policy performs poorly when H is small, underscoring the value of our adaptive strategy.
Proof ideas. Our use of an elimination-style procedure allows us to guarantee that we never eliminate the optimal arm with high probability, and also identify precisely when highly suboptimal arms are guaranteed to be eliminated. Then, by choosing N ([S)) = O(((S) +) for RMI and N (IS)) x ((S c) -2/3)) for RSR, we ensure that DBCARE can both match the worst-case behavior of the lower bound and adapt to easier problem settings where there are relatively few good candidate arms.
Empirical evaluation. We corroborate these theoretical findings in simulations and in real-world experiment on a drug discovery dataset. We compare to fixed budget and confidence algorithms to show the deficiencies of naive adaptations of existing BAA paradigms on this problem.
1.3
Related work
BAL The multi-armed bandit (MAB) problem, first introduced by Thompson [45], has become a foun- dational framework for studying the exploration-explottttii trade-off in sequential decision-makie under uncertainty. Within this framework, Best Arm Identification (BAI) focuses on identifying the arm with the highest expected reward [7, 25, 16, 10, 28, 21, 41].
BAI has primarily been studied under two paradigms: the fxee-buugee and fixed- performance settings. In the fixed-budger setting, the objective is to minimize the probability of misidentification [2, 29, 30, 1 1, 4], or alternatively, to minimize the simple regret [7, 8, 52]. the fixed performance setting, the majority of the literature has focused on achieving a target probability of misidentification (a. fixed confidence BAT) [14, 33, 15, 21, 17, 24, 23). To the best of our knowledge, there is no prior work on minimizing the number of pulls subject performance goal on the simple regret.
3

---

Our work builds on the extensive literature in this area. In particular, our algorithm draws inspiration from racing-styla style methods developed for creedcoofieeece BAI [34, 21, 24], while our lower bounds rely on technical lemmas from Kaufmann et al. [30]. Nevertheless, the problem we study departs meaningfully from existing formulations, requiring new conceptual insights and analytical tools.
Cost of arm pulls in MAB. Several works have explored sampling costs in BAL Xia et al. [49] and Qin al. [39] study identifying the arm with highest reward-to-cost ratio, assuming both reward and cost are observed per sample, both in fixed-budget and fixed-confidence settings. In contrast, in our setting, once final arm is selected, only its expected reward not its sampling cost-rematte relevant. Degenne et al. [13] and Yang et al. [50] consider minimizing the cumulative regret [40] while performing BAL, but this approach is not applicable when sampling costs are exogenous to rewards, as we consider in our setting. Kanarios et al. [27] study minimizing cumulative cost (instead of the number of pulls) in a fixed confidence setting, when the learner observes a stochastic cost on each arm pull in addition to the reward. Recent work in multi-Fidelity BAI [37, 48, 38) allows learner to choose to incur different costs for varying magnitudes of accuracy. The last two problem settings are distinctly different from ours. Finally, some works [3, 43] address costs in the cumulative regret setting, which is also distinct from our focus on BAI.
Bayesian sequential testing in classical statistics. Arrow et al. [1] and Wald and Wolfowitz [47] study Bayesian formulations of sequential binary hypothesis testing problems (e.g.. H1 11111 = A vs. H2 P1 A2 = -A), where the learner must balance the cost of incorrect decisions against the cost of continued testing. They show that the Bayes-optimal procedure for such problems the sequential probability ratio test (SPRT) of Wald [46], with optimal thresholds determined by solving complex implicit equations that depend on the specific problem parameters. number of works [44, 12, 31] have extended this study to the more general composite hypothesis testing framework (H1 : #1 U2 > 0 vs. H12 Mi μ2 I 0). While there are similarities to our proposed setting, their analyses have been restricted to developing procedures that are only asymptotically Bayes-optimal and only hold in the case of exponential families.
Paper organization. The remainder of this paper is organized as follows. In $2, we study the problem the 2-arm setting. This new formalism for BAI introduces novel intuitions which are best illustrated in the two arm setting. In $3, we present our algorithm and main results in the K-arm setting. Finally, in $4, we evaluate our methods on simulations and show that it outperforms traditional BAT methods on this problem.
2 Two-Arm Setting
To build intuition for this problem, we first study the K = 2 setting. Let ((K) denote all probability measures on I. and let G2 {> E P(R) Vt > 0, Px (X- [x] > t) I cxp (- -=2/2²²) denote all r-sub-Gaussiag probability distributions. Let M, defined below in (2), denote the class of two-armed bandit models with r-sub-Gaussian rewards; recall that μ. E,, [X]. For a given gap
A 2 0, let Ma. defined below, denote the subclass of models with sub-optimality gap A. We have:
M = (v = v2): V/, 1/2 E Go p1, U2 E [0, B}} Ma = {v e -1 =2= (2)
In $2.1, we begin by studying RMI in (I), which uses the probability of misidentification as the performance criterion. In $2.2, we then consider RSR, which instead uses the simple regret. Unless otherwise stated, all results in this section will be corollaries of more general results in $3.
2.1 Probability of misidentification in the two-arm setting
Lower bound. We begin with gap-dependent lower bound applicable to any policy on this problem. Corollary 1.1 (Corollary of Theorem 1, Lower bound on RMI). Fix a gap A > 0 and the cost e per arm pull. Then, for any policy π we have
6'c log (=>²))
if A Vo2c.
sup (MI(TTV) 2 (A) = 4 1/41
(3)
VEMA
if A < VoLc
instructive to compare the above result with lower bounds for fixed confidence BAI. As in the fixed confidence setting [30], we observe that for large A, the lower bound exhibits familiar

---

LBan(A)
I.Ba(())
RMI (,r, 1)
Oracle
Ran (ar, .)
Oracle
DBCARE
DBCARE
Guess
Guess
Vo
A
(o²c)
A
Figure 1: Illustrations of the lower and upper bounds on the risk for RMI (on the left) and RSR (on the right) the 2-arm case presented throughout $ 2, with the performance of the policy which guesses arm at random without pulling at all (Guess) included as a point of reference.
dependence on o² -2, indicating that the problem becomes easier as the gap increases, Our bound also depends on the cost e and includes a logarithmic term in A (a?c Notably, when the gap is small, our setting departs from fixed confidence behavior: the lower bound undergoes a phase transition and saturates at a constant value of 1/4, rather than continuing increase with A -
To build intuition towards designing a policy, it is worth considering the behavior of "oracular" policy which knows the gap A but does not know which of the two arms is optimal. Recall that it requires approximately ((A, 6) E O(a2 -2 log(1/)) samples to separate two sub-Gaussian distributions whose means are A apart [46, 22. 30] with proba- bility at least - 8. Hence, if we pull both arms (AA, 8) times, we will incur a penalty of 6 Ooocc 1))g(15)). By optimally choosing E O(oacA -)-)), we find that need to pull each arm ((A) E O(o²A
An oracular policy.
times. However, the above expression is non non-negative only when A > I(VV Intuitively, if A is very small, the policy will need to incur large cost to separate the two arms. If the policy knows A it is better off randomly guessing an arm instead of incurring this large cost. This intuition leads to the following policy and theoretical result. Its proof, which is straightforward, given Appendix C.
(
Proposition 1. Let n be the policy which pulls each arm max {0, 4n² x
times. If it pulls 0 times, it will choose arm uniformly random, and otherwise, outputs the empirically largest arm (breaking ties arbitrarily). Then, letting LBwu(A) be as (3), we have,
log C0+e
sup RMu(TA.V) 32LBxa(A) A)+ + 2c E O(LBMi(A))
MEMA
As we see, and illustrated in Fig 1, this bound matches the lower bound up to constant factors. To design a policy when A is unknown, inspiration from prior work on racing-style algorithms [36, 34], which have shown that sequentially pulling arms and eliminating them based on confidence intervals match oracular policies up to logarithmic factors in the fixed confidence setting.
will leverage the above intuition. We will also draw
A policy for RMI. We will let be confidence hyperparameter, aiming to output the optimal arm with probability at least - ó. However, to avoid over-pulling when the gap A is too small, we also incorporate hyperparameter N which is limit the total amount of times each arm. Intuitively, we know the cost grows linearly in the number of pulls, but the probability of misidentification decays exponentially, so there is point where the trade-off between the cost of pulling and the increased precision these pulls provide no longer favors continuing to pull.
willing pull
Our approach proceeds in epochs of sampling both arms once and comparing the difference between the empirical averages of the two arms against a Hoeffding confidence bound at the end of each epoch to test for separation. If the observed difference any epoch is larger than the confidence bound, it will exit and recommend the larger arm. Otherwise, it will continue to sample each arm until reaching the ~ epoch, where it will return the arm with the larger empirical average even though they have not statistically separated. In the case of the 2-arm probability of misidentification setting, we use N (2ec)-1 and 8 c(1 + 2cN*) - Here, set N be the maximum number of times the oracular policy would ever pull each arm for any A. The confidence parameter is used to control
'Proposition includes an additive penalty corresponding to the cost of two extra pulls, and similar additive term appears in all upper bounds. This is unavoidable in general, as even A - each arm must be pulled least once identify it. While this be formally incorporated in the lower bound, omit it for simplicity.
5

---

the penalty of the policy on the event that the policy's confidence interval for the gap does not contain the true gap. We have described this algorithm formally in the K-arm setting Algorithm 1.
As the corollary below demonstrates, by careful choice of N and 8, we show that we can match the lower bound in Corollary 2.1 up to log(3/c) factors, for all values of A. Based the relationship between algorithmic performance and lower bounds in the BAI literature, we conjecture that this logarithmic gap largely unavoidable, and could at best be reduced to a log-log factor [28, 21, 30]. Corollary 2.1 (Corollary of Theorem 2, DBCARE under RMI). Let π be the policy described above using N = (2ec) and 8 c(1 + 2c.Na)-1 Then, letting (A) be as in (3),
(e+1 (Ec)2
sup (MI(T, v) < 128 VEMa
LBmu(A)+ + 3c E O (log(c- (oog(c-))LBun A))BMI())
This bound and its comparison the lower bound are illustrated in Fig 1. As we can see in Fig by our choice of N our policy actually performs within a constant factor of the lower bound for small A, and the log(+/c) factor is incurred mostly in the "moderate" A regime. After the sharp transition at the midpoint of the plot in Fig I, representing the point at which our algorithm is guaranteed to output the optimal arm before reaching N epochs with high probability, we can also see that the comparison to the lower bound quickly improves until we again reach a constant factor mismatch.
2.2 Simple regret in the two-arm setting
Lower bound. We again begin by presenting a lower bound on this problem. Corollary 3.1 (Corollary of Theorem 3, Lower bound on Rsn).. Fix a gap A > O and the cost e per arm pull. Then, for any policy n
a'c 4A A/4,
log
if 2 (02c)4s
sup RSR(T v) 2 (A) = VEMa
o
(4)
if < (0²c)
Additionally, taking the worst-case over all A, we have, for any policy n
c 1/3
3
sup RSR (T, v) LB
(5)
PEM
8
As in Corollary 1.1, we observe a phase transition in the lower bound: it is 4/4 when the gap is small, and scales as ?(Λ -2) when the gap is large. For what follows, we also state the minimax (worst-case) value of this lower bound decreases as the arm-pull cost c decreases. In contrast, for RMI. the minimax lower bound is 1/1, and even a naive policy that guesses arm without any pulls incurs a penalty of only 1/2. However, for RSR, even achieving the minimax lower bound requires a well-designed policy.
function of A. As we see, this minimax lower bound
An oracular policy. To design such policy, let us again consider the behavior of an oracular policy which knows A. The motivation behind the chosen number of samples the same as before, but when pulling the arms N(A A 5) times, we now incur penalty of 8A + O(a2cA -2 log(1/s)) Because of this change, we now wish to use O(o2cA -3) leading to the following result, mirroring that of Proposition 1. Its proof, which is straightforward, is given in Appendix C.
Proposition 2. Let n* be the policy which pulls each arm max fo, A log
log
Aa [o==
times. if
pulls them 0 times, it will choose an arm uniformly random, and otherwise, outputs the empirically largest arm (breaking ties arbitrarily). Then, letting LBsR(A) be as in (4) and LB3R as in (5),
sup Rsu(m*,00 < 32LBsR (A) + 2c O(LBsR(A)) (A)). sup LBsu( .v) 8LB + 2c DEMA
VEM
policy for RSR- Our policy will proceed exactly as before, performing rounds of equal sampling until either we reach prespecified number of epochs or are able to identify the optimal arm with high probability. Like the oracular policy, though, the change in risk requires updating our hyperparameters N and 5 to ensure that algorithm still performs well in this setting. We again motivate our choice of N via the behavior of the oracular policy, choosing N (3/2))(%%))2* We also still use 8 as a tool to control the worst-case penalty when our confidence interval does not contain the true gap. and thus we set 8 e( B + 2cN

---

Corollary 4.1 (Corollary of Theorem 4, DBCARE under RSR). Let π be the policy described above using N (8/2)((%)))* and = c(B + 2 Then, letting LBsR(A) be as in (4), when N (o²c) 1/s we have,
3Bo' 1/ c
sup RSn(T, v) S 128log
LBsn - 3c E O (logí Bac (log
vEMa
When < (o) V/s we instead have,
sup RT v)= & + + vEMa
+3 E (LBsn(A)) + poly(a,c)) c))
Finally, letting Ln be as in (5), taking the worst case over all A, we have,
sup RSR(F, S 9LBiR +3c E OLLB)R) .EM
Here we see, when A 2 (o²c) these results closely mirror that of Corollary 2.1, though the log-factor now additionally scales with Bo As illustrated in Fig 1, this log-factor primarily plays role in the moderate A regime like in the case of RAI. Our bound and Fig also further highlight the inherent difficulty of designing simultaneously minimax- and instance-optimal policy for RSR, as it is impossible to match the lower bound as + O without performing fewer pulls even as the problem becomes more difficult. Illustrating why the instance-based lower bound cannot be improved in this regime, however, is the policy which guesses an arm without any pulls in purple in Fig 1.
3 K-arm Setting
We now generalize our results the K-arm setting. We begin by adapting the notation formalities for K arms. We now let M, defined in (6), denote the class of K-armed bandit models with o-sub-Gaussian rewards. Further, for a bandit model E .M, assuming WLOG that we have
Hi 2 U2 2 ... 2 P.. we define the complexity measure H(v) := Σk= AE where As = μ4 pk the k-th largest suboptimality gap. For a given complexity H 0, let MH, defined below, denote the subclass of models having complexity at most H. Thus, we define:
M = {v = (va) : v/a G.. Ma E (0, Va
Mμ = {u E M: H(v) S H3 (6)
As we will see, while our hardness results extend naturally from two to K arms, extending the intuitions for the algorithm design requires a more careful design of the budget parameter N
3.1 Probability of misidentification in the K-arm setting
Lower bound. We now present the general K -arm lower bound result for RMI-
Theorem 1. Fix a complexity H > and a cost per arm pull e > O. Then, for any policy n,
d'eH log ( if H < (0²c)-1 1/4,
sup (M v) (H) rEMH
(7)
if H (020)-1
Comparing this result to its Corollary 1.1 in the 2-arm setting, we observe the same phase transition, now in terms of the complexity, H. Using the definition of H, we note that it still occurs when A x ())=c))), and provides the same intuition: when at least some of the gaps are sufficiently close to zero (or if there are very many arms), the cost of separating them outweighs the decrease in the probability of misidentification, and it becomes optimal to guess the best arm without pulling.
A policy for RMI- We present our proposed algorithm, DBCARE, in its full K-arm generality in Algorithm To account for there now being K arms, DBCARE maintains "surviving set" S of arms that have not yet been determined to be sub-optimal, and performs rounds of equal sampling of all arms S. At the end of each round, compares the difference between the current largest empirical average in S and each other arm in S, and eliminates them based on Hoeffding confidence intervals. This continues until either there only one arm remaining, or the remaining arms have reached their maximum per-arm budget, at which point the arm with the largest empirical average is returned.
7

---

In moving from the two arm to Kaam regimes, we once again encounter the issue of balancing performance and costs when selecting our per-arm budget. On one hand, we naively replace the division by 2 in N in Corollary 2.1 with division by K, then we will fall short on performance when there are many highly sub-optimal arms. However, we keep the same budget for each arm from the 2-arm setting, we will perform too many total pulls when there are many near-optimal arms.
To this end, we allow the per-arm budgets adapt to the problem complexity by letting N increase as |S| decreases. This allows DBCARE to dedicate additional resources to separating the remaining arms as some are determined be sub-optimal, but prevents the total possible number of pulls from scaling too quickly in K. Inspired by the 2-arm setting. we let N** (k) (kec) Further, we still use the confidence ö to control the worst-case penalty when the confidence intervals do not contain the true gap, so we set ò = c(1 + 2c log( K) K (2)) The following theorem summarizes the key properties of DBCARE when applied to RMI-
Theorem 2. Let aascaa be the policy defined in Algorithm using N (k) (kec) -1 and ö c(1 + 2c (K) (K) Then, letting LBxr( (H) be as in (7), we have,
K Klog(()
sup (MI(CTOCA 5 7601og(K) log MEMx
LBMI(H) + (K + 1)c,
ec²
which is E O(polylog(K,e ())
As in the 2-arm case, we see in Theorem 2 that our policy is still able to achieve performance within polylogarithmic factor of the lower bound, with the additional log(K) factor being due to the worst-case impact of our adaptive budget updating.
Algorithm 1 Dynamically Budgeted Cost-Adapted Risk-minimizing Elimination
Require: Dynamic budget function N Confidence
1: Initialization: ix.()) 0 v & [K] eo = 0, = 0 0,5 =. = [K]
2: while n S (1S]) AND |S] > do
3: 7 +1
4: for E do
5: t +
6:
A, + k Observe X, ~ VA.
7:
end for
8:
(n) + n - 1xy (A,)X, for S
9:
On /402n log AAo'n-log((na Knō-1). log(Köö))
10:
S+S E S: max (ee (m) > en
EES
11: end while
return argmax (n) (breaking ties randomly) aES
3.2 Simple regret in the K-arm setting
Lower bound. now present our second lower bound, for RRR in the general K-arm setting.
Theorem 3. Fix a complexity H 0, a smallest gap A2 2 0, and a cost per arm pull e 0. Then, for any policy æ, we have,
co'' log
cAa Gzell
if HAJ S (o'c)
sup RSR v) LBSR VEMR
(8)
Ao/1,
if HA (0²c)-1
Additionally, taking the worst case over all problem instances, we have, for any policy n
3 (K - 1)02c 1/a
Rsn v) LB .
sup
99)
Looking at the bound presented in (8), we see that the phase transition this lower bound now jointly involves the total problem complexity and the smallest gap.

---

A policy for RSR. Following the same intuition as in the probability of misidentification case, we again wish to allow N* adapt the problem complexity and increase as the surviving set of arms shrinks. Observing the minimax lower bound presented in 9, though, we see that the maximum problem difficulty scales with K l/s unlike the constant scaling in the case of RMI. Thus, we wish for N* to scale with - instead of K- and so we choose (k) = (3/2c) (00 - 1)/) Then, controlling for the worst-case performance again, we choose 5 = cBB + e K log(
4/-
Theorem 4. Let DaaCAE be the policy defined in Algorithm I using (k) (3/2c)0 9/3 ( ( 1)c) 4/3 and 6 = cBB + eK's log( K (2)) Then, letting LBsh be as in (8), when H 2 1 (o2c)-1,
K log(o))))) Bo)
sup RER(TOICARE: v) - 550 K) log "EM#
LBsn (H) + (K + 1)c,
e//
which is E O(polylog(B, K, (L,B) When HAP > (o²c)- we instead have,
+ (K + 1)cc O(L (If) + log(K (og(())ooly((e) (pl)((,,,)))))) Finally, letting LBER be as in (9), we have,
(BsR(H) + 4 (log(K))
sup RER (ToSCaRE: v) S 20 20log(K) LK) + +K + 1)c e (K (L) PEM
In Theorem 4, we see similar performance of DBCARE compared to the lower bound as in the two-arm case: we are able to achieve performance within polylogarithnic factors when the complexity is relatively low, and we incur an additive logarithmic and polynomial factor in K, a, and e when the complexity is prohibitively high. Observing our comparison to the minimax bound, we see that our policy is still minimax-optimal being only a logarithmic factor in K beyond the lower bound.
4 Numerical Experiments
Simulation Studies. We now empirically compare our method against traditional fixed budget and fixed confidence methods to demonstrate the ability of DBCARE to perform well across all problem instances. We study the performance across a range of suboptimality gaps A for Gaussian and Bernoulli rewards in the two-arm setting using the cost
10-4 In the Gaussian setting, the arms have variance x² = 1 with means 4 for A E [0.05, 2]: for Bernoulli arms, the means are 0.5 for A [0.01, 0.95]. Results averaged across 10s runs each with different random seeds. We compare to Sequential Halving for fixed budget and elimination procedures using the optimized stopping rules of [30] for fixed confidence. We use budgets 7 = 10 and T = 500 and confidences of 6 0.1 and 8 = 0.01 for comparison against relatively low and high confidence/budget choices. We also include the oracular policies of 2 provide a baseline of good performance. As we can see in Fig 2. the fixed budget and confidence algorithms necessarily have some region of gaps where they perform sub-optimally: for the small budget, is moderate A values, for the large budget, is large A values, and for both confidences, it is small A values. On the contrary, our proposed algorithm exhibits uniformly good performance across all A values, which is preferable when A is unknown. In Appendix E, we provide further simulations in the K K-arm setting.
Gaussian MI
Gauss an 5R
Berooul MI
Bernoull 5R
TREME bw
Rufuol
3
8-53
3.34
1:30
1.30
275
4
Figure 2: Comparisons between the oracular policy, DBCARE, and fixed budget and confidence algorithms for RMI and RSR. -axes are adjusted per setting to highlight problem-specific behavior. Confidence regions represent empirical average risk + 2 SE.
Drug Discovery Experiment. To demonstrate the efficacy of our approach on a problem in practice, we present the results of a real data experiment on a drug discovery dataset. For this experiment, we take the results from Table 2 of Genovese et al. [19] on the efficacy of the drug secukinumab in patients

---

with rheumatoid arthritis. They report outcomes for 237 patients assigned to one of treatment groups (arms) and report the drug efficacy according to the American College Rheumatology criteria ACR20, ACR50, and ACR70. We consider this data under 2 settings: 1.) binary efficacy outcome, being whether patient achieved least ACR20 (1) or not (0), as this was the primary goal of [19]; and 2.) a "leveled" efficacy outcome, where no improvement results in an outcome of 0, and ACR20, ACR50, and ACR70 are outcomes 0.2, 0.5, and 0.7, respectively, approximating a continuous efficacy metric. We treat the proportions of patients reported in each category in Table 2 of [19] as population proportions, and evaluate DBCARE, Sequential Halving, and an elimination procedure with confidence bounds v4o2n log( (ng(K) on 10* runs each setting, each with different random seeds. For the binary outcome setting, the means and for the leveled outcome setting, the means were = (0.230, 0.227, 0.200, 0. 0.196, 0.102), each presented in decreasing order (order randomized during data generation). Because K and the means are fixed in this setting, we choose to evaluate our performance across range of values for [10-3 3, 10- In Fig 3, we see that other method uniformly outperforms DBCARE across all choices of c, again highlighting the ability of our method to adapt to the problem setting at hand.
μ (0.537, 0.469, 0.465, 0.360, 0.340),
Binary Etticacy
Binary Efticacy
1.25
133
DSCARE
DBCARE
FBT -
FS T 250K
1.0-
FC 5-0.0.
2:75
FC 5-0.1
2.50
5:25
0.001
Se-04
1e-04
Se-05
10-25
0.001
52-04
16:04
Se-05
1e-05
Leveled Efficacy MI
Leveled Efficacy SR
2.5
2.0
FB 250K
FB 250K
0.10
1.5
FC 6-001
v)
FC 6-0.1
1.0
0.05
0.5
0.8
0.001
Se-04
1o-44
5e-05
L6
0.001
Se-04
1o-04
5e-05
1e-05
Figure 3: Comparisons between DBCARE and fixed budget and confidence algorithms for Rι and Rsn drug discovery dataset. -axxes adjusted per setting to highlight problem-specift behavior. Error bars represent empirical average risk + 2 SE.
Conclusion
We propose a novel framework for studying best arm identification. In many practical settings, traditional fixed budget and confidence regimes do not nicely align with the objectives of practitioners. To fill this gap, our setting explicitly balances sampling costs and performance on the fly by minimizing a risk functional. We prove hardness results for this problem and provide an algorithm, DBCARE, which achieves near-optimal performance nearly all problem instances.
Future directions. We believe our lower bound analysis for simple regret in the K-arm setting can be improved. Though our bounds are tight when suboptimality gaps are similar, we believe the bounds can be tighter when they are different. We also conjecture that the additive gap we observe in the simple regret setting is unavoidable for algorithms which achieve the minimax risk.
Acknowledgmente and Disclosure of Funding
This work was supported in part by NSF Awards IIS-244 2441149 and DMMS2023222
10

---

References
[1] K. J. Arrow, D. Blackwell, and M. A. Girshick. Bayes and Minimax Solutions of Sequential Decision Problems. Econometrica, 17(3/4):2132444 1949.
[2] J.-Y. Audibert, S. Bubeck, and Munos. Best arm identification in multi-armed bandits, In 23rd Anmual Conference on Learning Theory, pages 41-53. OmniPress, 2010.
[3] A. Badanidiyuru, R. Kleinberg, and A. Slivkins. Bandits with Knapsacks. J. ACM, 65(3), 2018.
[4] A. Barrier, A. Garivier, and G. Stoltz. On Best-Arm Identification with a Fixed Budget in Non-Parametric Multi-Armed Bandits. In Proceedings of The 34th International Conference on Algorithmic Learning Theory, pages 136-181. PMLR, 2023.
[5] A. Bather and A. M. Walker. Bayes procedures for deciding the sign of a normal mean. Mathematical Proceedings of the Cambridge Philosophical Society, 58(4):599-62) -20,, 1962.
[6] R. E. Bechhofer. A Sequential Multiple-Decision Procedure for Selecting the Best One of Several Normal Populations with a Common Unknown Variance, and Its Use with Various Experimental Designs. Biometrics, 14(3):408-429, 1958.
[7] Bubeck, R. Munos, and G. Stoltz. Pure exploration in multi-armed bandits problems. In International Conference on Algorithmic Learning Theory, pages 23-37. Springer, 2009.
[8] S. Bubeck, R. Munos, and G. Stoltz. Pure exploration in finitely-armed armed and continuous-arme handits. Theoretical Computer Science, (itenne,411(19):::)). 412(19):1832-1852 2011.
[9] S. Bubeck, V. Perchet, and P. Rigollet. Bounded regret in stochastic multi-armed bandits. In Proceedings of the 26th Annual Conference on Learning Theory, pages 122-134. PMLR, 2013.
[10] S. Bubeck, T. Wang, and N. Viswanathan. Multiple Identifications Multi-Armed Bandits. In Proceedings of the 30th International Conference Machine Learning, pages 258-265. PMLR, 2013.
[11] A. Carpentier and A. Locatelli. Tight (Lower) Bounds for the Fixed Budget Best Arm Iden- tification Bandit Problem. 29th Annual Conference on Learning Theory, pages 990-604. PMLR, 2016.
[12] H. Chernoff. Sequential tests for the mean of normal distribution iv (discrete case). The Annals of Mathematical Statistics, 36(1):55-68, 1965.
[13] R. Degenne, T. Nedelec, C. Calauzenes, and V. Perchet. Bridging the gap between regret minimization and best arm identification, with application A/B tests. In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, pages 1988-1996. PMLR, 2019.
[14] E. Even-Dar, S. Mannor, and Y. Mansour. PAC bounds for multi-armed bandit and markov decision processes. In Computational Learning Theory, pages 255-270. Springer Berlin Heidelberg, 2002.
[15] E. Even-Dar, S. Mannor, and Y. Mansour. Action Elimination and Stopping Conditions for the Multi-Armed Bandit and Reinforcement Learning Problems. Journal of Machine Learning Research, 7(39): 1079-1105. 2006.
[16] V. Gabillon, M. Ghavamzadeh, and A. Lazaric. Best amm identification: A unified approach to fixed budget and fixed confidence. In Advances in Neural Information Processing Systems, volume 25, pages 3212-3220. Curran Associates, Inc., 2012.
[17] A. Garivier and F. Kaufmann. Optimal Best Arm Identification with Fixed Confidence. In 29th Anmual Conference on Learning Theory, pages 998-1027. PMLR, 2016.
[18] T. Geng, X. Lin, H. S. Nair, J. Hao, B. Xiang, and S. Fan. Comparison lift: Bandit-based experimentation system for online advertising. Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 15117-15126, 2021.

---

[19] M. C. Genovese, P. Durez, H. B. Richards, J. Supronik, E. Dokoupilova, V. Mazurov, J. A. Aclion, S.-H. Lee. C. E. Codding. H. Kellner, T. Ikawa, S. Hugot, and S. Mpofu. Efficacy and safety of secukinumab in patients with rheumatoid arthritis: A phase II, dose-finding, double-blind, randomised, placeho controlled study. Annals of the Rheumatic Diseases, 72(6):
863-869, 2013.
[20] K. Jamieson and A. Talwalkar. Non- -on-stochastic Best Arm Identification and Hyperparameter Optimization. In Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, pages 240-248, 2016.
[21] K. Jamieson, M. Malloy, R. Nowak, and S. Bubeck. ill'ucb: An optimal exploration algorithm for multi-armed bandits. In 27th Annual Conference on Learning Theory, volume 35, pages 423-439. PMLR, PMLR, 2014.
[22] C. Jennison, I. M. Johnstone, and B. W. Turnbull. Asymptotically optimal procedures for sequential adaptive selection of the best of several normal means. In Statistical Decision Theory and Related Topics III, pages 55 55-86. Academic Press, 1982.
[23] M. Jourdan, R. Degenne, D. Baudry, R. de Heide, and E. Kaufmann. Top Two Algorithms Revisited. In Advances in Neural Information Processing Systems, volume 35, pages 26791- 26803. Curran Associates, Inc., 2022.
[24] K.-S. Jun, K. Jamieson, R. Nowak, and X. Zhu. Top arm identification in multi-armed ban- dits with batch arm pulls. In Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, volume 51, pages 148. PMLR, PMLR, 2016.
[25] S. Kalyanakrishnan and P. Stone. Efficient selection of multiple bandit arms: Theory and practice. In Proceedings of the 27th International Conference on Machine Learning, pages 511-518, PMLR, 2010.
[26] S. Kalyanakrishnan, A. Tewari, P. Auer, and P. Stone. Pac subset selection in stochastic multi- armed bandits. In Proceedings of the 29th International Coference on Machine Learning, volume 12, page 227-234. Omnipress, 2012.
[27] K. Kanarios, Q Zhang, and L. Ying. Cost Aware Best Arm Identification. Reinforcement Learning Journal, 4:1533-1545, 2024.
[28] Z. Karnin, T, Koren, and O. Somekh. Almost Optimal Exploration in Multi-Armed Bandits. In Proceedings of the 30th International Conference on Machine Learning, pages 223-1246. PMLR, 2013.
[29] E. Kaufmann, R. Korda, and R. Munos. Thompson sampling: An asymptotically optimal finite-time analysis. In Algorithmic Learning Theory (ALT), pages 199-213. Springer Berlin Heidelberg, 2012.
[30] E. Kaufmann, O. Cappé, and A. Garivier. On the Complexity of Best-Arm Identification in Multi-Armed Bandit Models. Journal of Machine Learning Research, 17(1):1-42 2016.
[31] T. L. Lai, On optimal stopping problems in sequential hypothesis testing. Statistica Sinica, (1):33-51, 1997.
[32] L. Li, K. Jamieson, G. DeSalvo, A. Rostamizadeh, and A. Talwalkar. Hyperband: A novel basdit approach to hyperparameter optimization. Journal of Machine Learning Research, 18(185):1-52, 2018.
[33] S. Mannor and J. N. Tsitsiklis. The sample complexity of exploration in the multi-armed bandit problem. Journal of Machine Learning Research, 5(Jun):623-648, 2004.
[34] O. Maron and A. W. Moore. The Racing Algorithm: Model Selection for Lazy Learners. Artificial Intelligence Review, 11(1:193-2255 1997.
[35] U. Misra, R. Liaw, L. Dunlap, R. Bhardwaj, K. Kandasamy, J. E. Gonzalez, Stoica, and A. Tumanov. Rubberband: cloud-based hyperparameter tuning. In Proceedings of the Six- teenth European Conference on Computer Systems, pages 327-342, Association for Computing Machinery, 2021.
12

---

[36] E. Paulson. A sequential procedure for selecting the population with the largest mean from k: normal populations. The Annals of Mathematical Statistics, 35(1):174-180, Mar. 1964.
[37] R. Poiani, A. M. Metelli, and M. Restelli. Multi-Fidelity Best-Arm Identification. In Advances in Neural Information Processing Systems, volume 35, pages 17857-17870. Curran Associates, Inc., 2022.
[38] R. Poiani, R. Degenne, Kaufmann, A. M. Metelli, and M. Restelli. Optimal Multi-Fidelity Best-Arm Identification. In Advances in Neural Information Processing Systems, volume 37, pages 121882-121927. Curran Associates, Inc., 2024.
[39] Z. Qin, X. Gan, J. Liu, H. Wu, H. Jin, and L. Fu, Exploring Best Arm with Top Reward- Cost Ratio in Stochastic Bandits. In IEEE INFOCOM 2020 IEEE Conference on Computer Communications,, pages 159-168, 2020.
[40] H. Robbins. Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Society, 58(5):527-55) 1952.
[41] D. Russo. Simple bayesian algorithms for best arm identification. In 29th Annual Conference on Learning Theory, volume 49, pages 1417-1418. PMLR, 2016.
[42] D. Siegmund. Sequential Analysis. Springer New York, 1985.
[43] D. Sinha, K. A. Sankararaman, A. Kazerouni, and V. Avadhanula. Multi-Armed Bandits with Cost Subsidy. In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, pages 3016-3022 PMLR, 2021.
[44] M. Sobel. essentially complete class of decision functions for certain standard sequential problems. The Annals of Mathematical Statistics, pages 319-337, 1953.
[45] W. R. Thompson. On the likelihood that unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):285-299) 1933.
[46] A. Wald. Sequential Tests of Statistical Hypotheses. The Annals of Mathematical Statistics, 16 12):117-186, 1945.
[47] A. Wald and Wolfowitz. Bayes Solutions of Sequential Decision Problems. The Annals of Mathematical Statistics, 21(1):82 99, 1950.
[48] X. Wang, Q. Wu, W. Chen, and J. C. S. Lui. Multi-Fidelity Multi-Armed Bandits Revisited. In Advances Neural Information Processing Systems, volume 36, pages 31570-31600. Curran Associates, Inc., 2023.
[49] Y. Xia, Т. Qin, N. Yu, and T.-Y. Liu. Best action selection in a stochastic environment. In Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems, page 758-766. International Foundation for Autonomous Agents and Multiagent Systems, 2016.
[50] Yang, V. Y. F. Tan, and T. Jin. Best Arm Identification with Minimal Regret. arXiv preprint arXiv:2409. /8909, 2024.
[51] J. Zhang, L. Jain, Y. Guo, J. Chen, K. Zhou, S. Suresh, A. Wagenmaker. S. Sievert, T. T. Rogers, K. G. Jamieson, et al. Humor in ai: Massive scale crowd-sourced preferences and benchmarks for cartoon captioning. In Advances in Neural Information Processing Systems, volume 37, pages 125264-1 125286. Curran Associates, Inc., 2024.
[52] Y. Zhao, C. Stephens, C. Szepesvari, and K.-S. Jun. Revisiting Simple Regret: Fast Rates for Returning Good Arm. In Proceedings of the 40th International Conference Machine Learning, pages 421 22110-42155 42158. PMLR, 2023.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The claims made regarding the K-arm lower bounds are formally stated in $ 3 and proved in Appendix B. Our algorithm and theorems regarding its comparison to the lower bounds are presented in $ 3 and proven Appendix D. Our simulation studies and real data experiments are presented in Š 4 and Appendix E.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: As we compare the performance of our proposed algorithm to our stated lower bounds in $ 2 and 3, we note where our algorithm falls short and point out what improvements we believe are possible. In 5, we also discuss where believe our lower bound analysis is loose and can be improved. When presenting empirical results in Š 4 and Appendix E, we explicitly state all of our problem setting choices.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
14

---

3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: Each theoretical result in $ 2 and 3 state all relevant assumptions, and proofs are provided in Appendices B, C, and D. Necessary lemmas from external works are included in Appendix A and are properly eited.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: Our proposed algorithm is clearly written in pseudocode in Algorithm 1, which should be sufficient for implementation. All of our numerical experiments in $ 4 and Appendix E. have their settings clearly stated, which should be sufficient for replication.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access hosted model (e.g., in the of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
15

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [No]
Justification:
We do not provide access to the data and code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (uttps://nips.co
public/guides
htte//ooeeSeiiiiie htaei//gguide///eeuubbiiiiss ssionolicy) for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / /nips. cc/public/ guides/ CCodeSubmise wwsiissssoooiiiiiio onPolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All of our numerical experiments 4 and Appendix E have their settings clearly stated and parameters justified for their relevance to the problem.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
All experimental plots in 4 and Appendix E include +2 SE error bars/regions.
Guidelines:
The answer NA means that the paper does not include experiments.
16

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (c.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Compute resources declarations accompany the additional experiments in Appendix E.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: http://uuurpssccppplliiieecco /Ethiiie///eieeeeeeeeeeeeeeeeee ctwuddelllellleeenecn ines?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
17

---

Justification: Like any machine learning algorithm, our method could be used by bad actors for explicitly nefarious purposes, but we do not consider potential negative downstream effects of our work. It is our belief that our work does not enable greedy / negligent / nefarious behavior any more than already existing methods in the field.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: The real-data experiments in Appendix E are based on published scientific results and are properly cited.
Guidelines:
The answer NA means that the paper does not existing assets.
18

---

The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi code com/dataseta has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification:
19

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our L.LM policy (https: http:/pps...ccooeeeeeeeee//////e for what should or should not be described.
20

---

A Results from Prior Works
Lemma 1 (Lemma 18 of [30]). Let and v be two bandit models, and let be any stopping time with respect to Ft, where Ft = a a(A1, A Xi,..., Ar, Xt) is the sigma-algebra generated by all bandit interactions. For every event & E Fr fi.e. & such that & E (T t) Fe).
(P) = Ey [e exp( -.)),
where,
K (T)
fa(
1
log
(Y,Y,,s)
where Ya,s is the s-th i...d. observation of the a-th arm and fa and fa are the distribution functions of the a-th arm under v and v' respectively.
Lemma 2 (Lemma 4 of [9]) Let po: P1 be two probability distributions supported on some set X with P1 < Po Then, for any measurable function Φ + {00 1}. one has
Px-po (x<p)(((X) (x(X) 1) PX~pi (6(X) 0) (LL(K ll p1)).
B Proof of Lower Bounds
We begin with Lemma that will be central to all of our lower bounds, which builds upon the work of [30] to achieve a bound with the form of their Lemma 15 which admits a random stopping time. Lemma 3. Let and v' be two K-arm bandit models. Let π be any policy with associated stopping time such that (P(T < oo)= 1 which outputs arm I [K] time Then for any a [K],
Pu,* (I + Pe (f (I =) o))
exp Σ Ex KL v/aa)
where P. u.n is the probability with respect to all randomness incurred by a interacting with the bandit model v and (t) E._ [aa
the number of times arm a has been pulled up to round t.
Proof. Fix a policy ग For ease of notation, we suppress the π in the probabilities and expectations throughout the proof. Now, we begin by using Lemma I to prove that the distributions of under each bandit model are absolutely continuous with one another. Consider an event & E F, such that (E) 0. Then, because e- > 0 for all Lemma 1. Further, by our supposition that (2 < 00) = 1, we must have P, (cxp( (L, >
R, we must have (1, cxp( (op((_,))__
by
and have P (E) = 0 = (E) 0, and we achieve the reverse implication by symmetry. Now, consider the fact that we necessarily have (7 = a} F, for all a [K] by construction, and so if we denote by L() and L' (7) the distributions of / under v and v' respectively, then clearly L'(I) < L(T). Thus, we can apply Lemma 2 to show,
(T + a) + P. (f a) 2
1
exp (- (-KL(C() (I
To conclude the proof, we need only upper bound KL (') by [,[,,], which we know is equal to Σx [N (L(P, || (3) by an application of Wald's Lemma [42]. By applying the conditional Jensen inequality the statement of Lemma and rearranging the terms, we know for
any & E Fr, we have [,( E] 2 log (e Thus, letting I = {k [K] (I = k) + 0} we can write,
(E)
[x
Σ [T, 7 Pf k))
KEI
(T(T=k)
2 Σ log
P. -H =k)
(P==x(==)) k)
KEI
KL(C(T) || (I)(())),
which concludes the proof.
21

---

We now employ Lemma 3 to prove Theorems 1 and 3 and their associated corollaries.
Proof of Theorem 1. Fix H > 0, > 0,c > 0, and a policy л. Let v be a Gaussian K-arm bandit model with means μr > 12 2... 2 Px and common variance r² satisfying Hiv) = H. Then, it is easy to show by contradiction that there must exist some arm E f2...., K} such Brulr] Let v' be an alternative model with Gaussian arms having the same that _ [VV. S Ag
common variance o², where (x(1)) = (x(v/) for all k o a and Ha(v") = =Ma(v) + 24a so that arm is now the optimal arm. Clearly H(v') S H(v), and so we have v. v E =MH Then, we apply Lemma 3 to show,
sup RMI(T, 2 max (RMI(T, RMI (T, n'} vEMu
2 2
(RAi(TT,)) v) +
(I + (Pua(I
+ Pv (I + a)) + (Bu,s [T] + EE [T])
= 2
1
(Pus (T + +1)+ + Per, t (T = 1)) + (Eu, [T] Ex (7])
2 2
K
2 4
exp
Σ
Eg, [Nx(T)] KL(Uk 11 v/4))
+ c 2 (Eu, + (x))(
k=1
[T]
c (Eu=l7) + [r])
exp
(10)
O2H
2
Here, we recognize the fact that (10) is convex in [y and thus we provide a π-frre
lower bound by minimizing over Ex, [r], Ex [T] > 0, which is achieved by Eu, [T]
max(0, e² log(2/o' and [r O. Plugging in these values completes the proof.
Proof of Theorem 3. This proof proceeds nearly identically to the proof above. Again fix H > 0, O, > 0 and any policy т. Then, let v and v' be the same Gaussian K-arm bandit models as in the previous proof, with optimal arms 1 and a E f2...., K), respectively. For notational clarity, let the suboptimality gaps ......, A, be with respect to v and let A = 0, so that Ma (v') - -M(()/ = A. + A. for k # a. Then, again using Lemma 3, we have.
sup RT 2 max (Rsn(T,)) v), Rsn(TT,
vEMS
(RsR (T, v), (T))
(Bu, lun - -1yl + 1B 1nl)) + (Z),=l) + (x)))
K
Σ
A Pr ( i))+ E(4. + 4,) =)
2
3za
+
C
(Ev,,(7 [T] + Ev (T))
2
A2
(Pes ( + 1) + Par, (ì # a)) + 2 (Ev + Ex [r])
2
2
Ag
(Pest ( * 1) Par ( =1)) + (Fwn + (r
N
K
A2
exp
Ev. [N KL 1//b)
+ c
2 [Ev + [x)))
4
k=1
A
[[EyyllT] O²H
+ C [Z) + (7))
>
exp
(11)
2
= Once again, (11) is convex in ET so we can further lower bound (11) by setting Ex, [7] e²H max(O, 2 log( (o and Ey, [r] O, completing the proof of (8).
22

---

To prove (9), we can consider a specific set of means satisfying this problem instance. Consider the instance where μn A and H22 = μx 0. that 2 = A A for some A > 0 that we will specify later. With these means, we have H = (K 1) -2, Then, using (8), we can write,
sup (EM
(T
LB 1)4
(K-1)0"c 422
log
cAs (K-1)ote)
if 2 ((K 1)02c)// if < ((K - 1))00)11
A/11,
We can then find the A which maximizes this function, which occurs at A (Ve(K 1)02c) which gives,
RAR (T, LBsR ()(A)) 3 3(KK -K- 1--
sup RSR(T, (T) ME
sup NEM 1)(4*)-2
Proof of Corollaries 1.1 and 3.1. Recall that, when 2, -- and D A. The conclu- sions then follow directly from Theorems and 3.
C Oracular Policy Proofs
Proof of Proposition 1. Fix gap A > O. Because samples from each arm are i.i.d. r-sub-Gaussin by equally sampling the arms, we have i.i.d. v Saaussan observations of the gap A. By Hoeffding confidence bound, if कт pulls each arm fixed number of times [T'] and outputs the empirically largest arm, then we have
(- (_TA²
TA2 4g
RMI v) P(A mm < <0) + 2c 12 S exp
+ 2c(TT 1)
Plugging in the proposed number of pulls, we get RMI(TA. S
s0*c A
log
+ 2c when
Sarte
A Vooee, and exactly (M)(TA.)) 1/2 otherwise, then the policy guesses the optimal arm uniformly at random. Multiplying (3) by 32 and adding 2c then clearly upper bounds this quantity.
Proof of Proposition 2. This proof proceeds nearly identically to the previous. Again fix gap A and consider that we can write,
TA
v) = AP(Á < <0) + 2c [T] S Aexp
+ 2c(TT +
40
Then, plugging in the proposed number of pulls, we get (TR( 1) S 802 log
ce3
2c when
(80c))
2 (802c)1/ and exactly RSR( (TT", 1/) = 4/2 otherwise, as then the policy guesses the optimal arm uniformly random. Multiplying (4) by 32 and adding 2c then clearly upper bounds this quantity. Further, maximizing this upper bound in terms of A (occurring at A (8yeo²c)) yields,
00c
1/3
sup RTR(T*, v) sup sup Rsn(m" 53 v
2c 8LB3R + 2c
A vEMa
c
D Upper Bounds for DBCARE
We begin by presenting number of technical lemmas allowing us control the behavior of DBCARE and prove our desired upper bounds on its performance.
23

---

Lemma 4 (Bound on total number of pulls). For any bandit instance v, using N (*) = (kec) 1)c) 4/3 DBCARE satisfies,
and (k) = (3/2))0 ((k
B [.r[T] S 2oog( K)
3log (oen(K)(Ke (Ka)ya
E E. [T] -
ec
2c
respectively.
Proof. Let & denote the index of the k-th arm eliminated by the algorithm. Then by construction, Eyg [T)(T)] I (* + 1). Further, En, (NVg()) & (2). Thus,
K
BR [r] = Σ E 5 (2
(k)
k=
Then, apply the fact that 1/2 + Σk=z k- < ()) and + Ek 1)-2/3 S ck log K to prove the statements.
Lemma 5 (Elimination behavior). Consider bandit instance satisfying, WLOG, li 2 12 2 uug. Let r(() be the epoch associated with time t. Define the good event,
n N {Ax E (Ai(n(1)) - (xx(((()))))))))))))))(( em(O) Pn (m(()) fix(((()) + en(t))
(
Then,
1. Pu (G9) 5
2. On G. LE LESV n(t) n(T) (i. the optimal arm never eliminated)
3. On G. if >
16 log( (+2/a)
for all l. 2 E (2,... K} and N decreasing in k.
(*)
(x(T) 160 log (NN((1)8))
< (k)
Proof.
Part 1. Letting Ya,, denote the s-th i.i.d. observation from arm by assumption, YI,+ Yk.s are
V2o-sub-Gaussian random variables with mean AE. Thus, V 4o2 log(s/4)
d-correct confidence
interval width for Aş after observations using Åk. = P (n) -ix (n) as the point estimate [21, 30]. Replacing 5 by 6/K and taking union bound across all & E S \ {1} then proves 1. Part 2. Consider Part We begin with arm K. By the supposition, on G, there exists < N (k) such that j (n) p
that on G f (11) - fin (n) S en Ag I en for all +f 1, which proves
en 2 AK- 2en > 0, and thus K & S for m n. Further, we can upper bound the n at which this is true by 2 (1/()) by construction of e,, and this quantity less than N*(K) by the A
supposition. Then, because K & S at time (*K),, , if N is decreasing in k, the algorithm will be forced to terminate time (K) by number of epochs, only if all arms other than have already been eliminated, under which the statement would hold anyway. We can then use the same construction for each k K I....,f, proving 3.
Lemma 6 (Bound probability of misidentification the good event). For any bandit instance satisfying μn 2 l12 2 ... 2 PK. and N decreasing in k. if M E (2...., ......,, K) is the smallest value such that for each ls = MM + l....,,.. K, AR then IP,,
(if no Au satisfy this, M = K)), = 0 if M and Pu. ((T (==))n))) S exp( 46
16a2 log( INN (KY6))
N (1)
(M)
otherwise.
Proof. We begin with the case j M. By Lemma 5, arm is never eliminated by the algorithm and arms j.j + 1,... K are eliminated before round N* (j). Then, on G. DBCARE only terminates
24

---

because either S = {1} or m²T) - (*((S) 2 N*()), making Pu, j} G = 0. Now
consider j 1 M. Then,
Pu, = [u
S Pu, (1 ((N))))))))))M))))GGnnnnnnaaaaa
(M))
Σ
(Ynn-Ma Vi,) non(issar)
(M
(M)
$ PM,
Σ
(Y Y2,n) 20)
(MM
n=1
(MMA))
S exp
4g²
Lemma 7 (Bound on simple regret on the good event). For any bandit instance satisfying in 2 N2 2 ... 2 PK. and N decreasing in k, if M E (2..... K} is the smallest value such that for each k = M K, K
/ 16o log (K(66) (if no Ae satisfy this, M K), then,
(N)
402
Bv (11 1a]
V
(eN
Proof. We begin by relating the simple regret with the probability of misidentification by applying Lemma 6,
Ep M7) lal
Σ D Pe (1T=
M
Do Puçe ((mm(((T)) > (r((r)))
Now, consider that for k: > f 2, P,, (n(T)) > (e(n(T))) n G) is maximized when fh = feg and is equal to 1/2 when this the case. Thus, again applying Lemma 6, we can write.
M P. (12(()(T)) > f (m(T))
Eu,z ((1) -1)) lal < 42
2
k=2
< 2A Pu.n (1A2(n(T)) > (1(((T)))
N*(M)
$ 2A exp
2
Maximizing in terms of A₂ then proves the statement.
With this collection of technical lemmas providing control the behavior of DBCARE, ready to prove Theorems and
Proof of Theorem 2. We break this proof into two cases. First, consider problems of complexity
H & ( with 2 P2 2 ... 2 μa- Further, let M E (1,..., K) be the smallest value such that for each k = M + 1, ...., K. A > / I/oeko"clog(KK KN" (N1/8) (if no As satisfy this, M = K). Then, by the definition of H, we can write
o2cH log
M- 64eM log( (M)75)
K
1
(HM 4
+
(12)
RcH
4
A
k=
25

---

Now, if M 2 2, we apply Lemmas 4 and 5 to show the following:
Pu. ((f=(11 Bu 1c] 1o]= Pu,, (17
Eun (Nx(T) lc]
MM)
log Dgg(KN(M)//)
S1+
+ 160
(13)
4
Rrm M+1
If, in fact, M 1, then combining the results of Lemmas 4, 5, and 6, we can write
log(KN*(K)/8
Pu. ((T G) + c Lol - 16 Σ
(14)
A
k=M-1
Then, multiplying (12) by 760 log( K) log( (oonKKlooKk lee()) and adding Ke (to account for non-integer pulls) then upper bounds both (13) and (14). Now, consider the case where > (o²c) Then LBMi (H) 1/4. Directly applying Lemma 4 gives for all H.
log((K) S (o00log(K) log (
(K (Klog(K)
(K)) (2)
Pr, ([T 1 t 1++
Finally, consider that by our choice of 6, using Lemmas and 5, regardless of the value of H, we have
| s 31(1+ 2log(K)
Pu (Po.(
S
e
This then proves the statement.
Proof of Theorem 4. This proof largely mirrors that of 2. Again, first consider problems satisfying
H < (o²c)-1 with 2 P2 2 ... 2 μ4 and let M E {l,... ...,.
K} be the smallest value such
that for each h = M + 1, K. D V (322//3) 2) log(KN KN (8)/8) (if no As satisfy this, K). Then,
LBsn 2 3(M - 1042
dee K
(15)
128e log( (M))-
4
A
k=M+1
If M 2 2, we apply Lemmas 4, 5, and show
85e ((M 1)02c)
3log(M) (Mo²c)
E, [p - M7) Lal + C lel S
3
(16)
K
log (K))0)))
160
A
Amm
Additionally, if M 1, then,
log K N (k)8-1)
Ep 1 - m4) Lal + CEE lol 320
(17)
A
Then, multiplying (15) by 575 log (K) log( K log( K)BK) 2/c0/////// upper bounds both (16) and (17). Now, for the case where HA,1 (o2c)-1 -1 and for the worst-case comparison, apply Lemmas and 7 to show for all H,
88ee (KK- - 1))22)))) 3log(K) (K) (Ko²c)%
Pe - 117) lol + CT 1al S
(18)
3
We then have (18) upper bounded by 4 log( (oooK))oo2)) and LBsn (H) 2 We can also upper bound (18) by 20 log K K)LBBRR- Finally, we never incur more than an additional Ke risk due to integer pulls, and by choice of 6,
3c 3clog(K), (K))%/ Sc
P (G') (E uT GO) + C G*)) < B +
e/
which proves all statements.
26

---

Now, despite our 2-arm results being corollaries of their more general K arm counterparts, we are able to provide tighter constants in Corollaries 2.1 and 4.1 by utilizing some more precise techniques that are not generally applicable in the K-arm case. For both cases, we apply Lemma 5 in the 2-arm case to identify a A' such that, for all A > A the algorithm guaranteed to identify the optimal arm before reaching N* samples per arm on the good event G. We then show that we simply need to find a multiplier which makes the lower bound larger than the upper bound at A and this multiplier will work for all other A.
Proof of Corollary 2. We begin by using Lemma 5 identify A
/32e02
which, (ec)
c+
combined with Lemma 6, allows us to write,
exp
8
+ 1 + 3c,
A
sup RMI(T, & UB) = MEMa
(19)
32a Plogg
(We)
+ 3c,
if A > A
A
where the additive 3c term is to account for integer pulls for each of the 2 arms and an additional c
bound for the expected risk on G Clearly, for any a 2 128 log
c+1 ). (19) is upper bounded by [ee]²
aLBBM (A) + for all A > Ar. We then divide our analysis for the remaining A into two cases:
when I V and otherwise. First, when A & vea2e.
1 +
UBMi(A) (A)
LBMI(A) 2e
and UBMI ()) I 8LBMI A) for A S Veo²c. Finally, must consider A (Veo*c, A+). We begin by comparing (19) and (3) at A", then we prove that this is sufficient. This gives us,
(ec)2 c e
log
3262 log
(00)
c+1
UBMI(A*)
+ 3c,
LBMI
128e log
e+1 (ec)²
Supposing < 1/4, can that UBMI S 128 log
e+1 (ec)
LB
Finally, conclude
that this is sufficient prove the statement by showing that 128 log is decreasing for A E (Veoze, A+ We show this here:
e+11 [ec}²
LBMI (A)
UB (A)
a
A2
A
3 SEaZC
01 cLB (BMI(A)
2A3
log
0²c
4e0"c
exp
a
A
8e02c
2
3
4ea2c
A
a
16eg²e
243
A3
which is < 0 when a > 32e, which is true for a = 128 log
c+1 (ec)=
Thus, we have proven A,
E [
128 log
LB ()) 2 UB (A) 2
sup RMI(TT))
(ec)2
rEMa
Proof of Corollary 4.1. We follow the same general proof strategy as in the previous proof. We again
apply Lemma to identify A = (o2c) (86)/3 log(2N*/
(2N* (2N*/8) /s) and combine it with Lemma 6 to write,
A exp
3A2
3 (o2c) + 3c, if < A
sup RsR(T,V) UBSRBBRR))))) = VEMA
(
(20)
320 log(2N
(2N (8) 3c
if > A
PPreviously, we have not put any restriction on the value c. but we have implicitly assumed c < by the construction of our problem setting. Consider that, under RMI. if c 2 1/4, one will perform uniformly best on all instances by simply guessing the optimal arm uniformly at random. We do not explicitly account for this behavior in our algorithm construction for simplicity, but it is unrealistic to let 2 1/4 in practical settings.
27

---

First, when A < (o²c)'/, clearly UBSR(A) - (A) 2(0c)))) + 3c by (20). Then, noting that 3Ba
4/3
2 2N 8. we can clearly see that (BsR(A) v 128 log
[ang" 67/3
(A) + 3c for
A > Ar. To prove this same bound for A [(o2c)
A+ we follow the same technique as in the previous proof. First, when A E [(o&c) (VEo Vo,
3
3
(02c) 4
UBSR (A) S (/
exp
+ 3c,
LBsR (A)
8c²/
and thus UBSR(A (A) < 9LBSR + 3c for A E [(o2c)/a, (VeoPe) To prove the bound for E ((Vea"c) Ys Ar), we again compare the two at A' and then show that the difference between the functions is decreasing in this range of A, and thus this is sufficient. At A have.
UBSR(A") (o2c)
32
log( (2N
3e
(
+ +cs (02c)) 3c
(2)
3(0²c) 1/s
//2
9
LBsR (A*) 128e log(2N*)
log
log" 2/2 (2222/8)
(2 /5)
3
128 log(2N"/o)
Thus, we have UBSR (A+) I 128 log
3B3 ea/3
LBSR + We then conclude this portion of the
proof by showing 128 128log
3Bo 1/3 c²/8
LBsR (A)
-UBSR (A) decreasing for A E ((Veo>c) A+).
We show this here:
i
2 log
A
34
)
342
0 aLBaR(A) (A)
4A3
c((o2c22
exp
8e(07c)7/
4e(o²c)*/
This is < 0 for any a 2 0 when A E ((ve0
(te/s(02o)4())
When A E I (effs(o2c))/3 AT)
i
202c
34
88((o2))
4/2
aL aLBsR (A) UBSR(A)
a
2A3
4e(o²c)%
3A
a02c
a²c
8//
(E)
8/2)
2A3
4A3
3B 4/8
which is < for any a > 78, and in particular, a = 128 log
Now, all that is left to prove is the worst-case comparison with LB We can show this simply by considering that (20) is maximized at A ( where it takes value (v//3+ + (a2 2 + 3c, which is clearly upper bounded by 9LB3R + 3c.
6/3
E
Additional Experiments
Here we provide additional K-arm experiments. All experiments were performed using a 3.7GHz AMD Ryzen 9 5900X 12-Core processor with 24 GB of memory. Total runtime across all experi- ments took approximately 7.5 hours, and safeguards were employed to prevent the fixed confidence algorithms from continuing to sample after already severely underperforming the other methods when the sub-optimality gaps were particularly small (10/c total samples allowed).
K-arm simulations. We now include a number of additional K-arm experiments demonstrate that our algorithm continues to perform well compared to traditional fixed budget and confidence methods when we move beyond the simple 2-arm case. For all of our K-arm experiments, we choose to use Gaussian arms with x² = for simplicity. We begin with the "I-sparse" setting. where μn = A and μ4 = 0 for all # I, resulting in misidentification performance penalty and A E [0.05, 3] for the simple regret performance penalty. We additionally vary K among 16, and 32. For these experiments, we average across 10 runs each with different random seeds. As in $ 4, we compare to Sequential Halving [28] for fixed budget and we use an elimination, or "racing." procedure for fixed confidence, with confidence bounds / 2n logg Kno-1). To extend to the K-arm case, our "low" budget is now 5K, and our "high" budget is 250K, which align with our choices of 10 and 500 in the 2-arm case. We still use ò 0.1
(K 1)A -2, for A E [0.05, 2] for the probability of
28

---

3-sporse MIlK
123
125
138-
128-
2.7
mulme
FC 0000001
130-
025
6:54
3-sp0
1-sparse K.0
+37
024
101-11
F25-11
Figure 4: Comparisons between DBCARE and fixed budget and confidence algorithms for RMI and Rsn in the K K-arm 1-sparse setting. Y-axes are adjusted per setting to highlight problem-specific behavior. Confidence regions represent empirical average risk + SE.
and d 0.01 for our confidences. As we can see in Fig 4, in the I-sparse setting, DBCARE still enjoys uniformly good performance across the full range of A, while the fixed budget and confidence approaches have some region where they perform sub-optimally.
To explore the performance of DBCARE and fixed confidence and budget approaches across a variety of problem structures, we additionally considered the "linear decay" setting, where we set μ1 Ag and μ4 - R k-2 for l # that the suboptimality gaps linearly increase from Ag to 242- This results in R 0.5K27². We again let A E [0.05, 2] for RMT and A E [0.05, 3] for RSR. average across 10 runs each with a different random seed, and vary K among 16, and 32. As we can see in Fig 5, this setting provides similar results to the 1-sparse and 2-arm settings, with DBCARE performing well across the range of A₂ values, while the other methods generally perform sub-optimally for some A₂ values.
Unear XIl R
Unear NI 36
nete K
BOCARE
DOCARE
2BC4TE
FST 1300
757-25M
6.5
636
038
0:00
80
Liten SR K =:
Linea:SR =116
Uneer 5R =232
DECAEE 154
D0C3EE
D0C58E
737-150X
624
08
Figure 5: Comparisons between DBCARE and fixed budget and confidence algorithms for RMI and Rsn the K-arm linear decay setting. Y-axes are adjusted per setting to highlight problem-specific behavior. Confidence regions represent empirical average risk + 2 SE.
29


Reviews:
[{"review_id": "7vHpSP7B9z", "reviewer": "Reviewer_VxJA", "summary": "The paper propses a novel formulation of the objective in a multi-arm bandit setting: rather than the common fixed budget or fixed confience settings, a natural objective is proposed that offers a natural tradeoff between the performance and the cost of the arm pulls. For this objective, the paper proves lower bounds and upper bounds that match upto logarithmic factors. The techniques used are the standard machinery of change of measure arguments with a clever adaptive scheme for the algorithm.", "questions": "- The baselines are unclear -- Which specific fixed-budget and fixed-confidence algorithms served as baselines in your experiments?\n- The end of the experiments section mentions experiments on a drug-discovery dataset. Could you highlight the main takeaways from these results and explain how they demonstrate DBCARE’s superiority over traditional BAI approaches in such a real-world context?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- nice formulation which avoids the dilemma of what confidence or budget to set, and instead offers an automatic tradeoff between performance and number of arm pulls.\n- nice explanation of the intuition by considering 2 arm case and policyy with known $\\Delta$ before doing the general case.\n- elegant analysis showing an interesting phase transition between regimes of low and high complexity\n\nWeaknesses:\n- very limited experimental evaluation.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your response and questions.\n\n**Weaknesses**:\n\n- *Limited experimental evaluation*: Because we introduced a novel paradigm for multi-armed bandit problems, we found it prudent to focus more on providing intuition for the problem and clearly demonstrating new theoretical results, which limited the available space for experimental evaluation. We have included some additional synthetic and real K-arm experiments in Appendix E to further demonstrate DBCARE’s utility over classical BAI approaches to this setting. Given the additional page allowance for the final copy, we can move some of these results to the main body to provide more immediate experimental demonstrations.\n\n**Questions**:\n- *BAI Baselines*: In lines 342-343, we note that we compared to Sequential Halving for the fixed budget algorithm and to an elimination algorithm using the optimized stopping rules of Kauffman et al. (2016) for the fixed confidence algorithm. In lines 1038-1040 in Appendix E, we note that for our K-arm experiments we again use Sequential Halving for the fixed budget setting and an elimination algorithm for the fixed confidence setting, in this case using confidence bounds of \\\\(\\sqrt{4\\sigma^2n^{-1}\\log(Kn\\delta^{-1})}\\\\) for the elimination algorithm, as the optimized bounds of Kauffman et al. only hold in the 2-arm case.\n- *Drug Discovery takeaways*: We provide details of the experimental results for the drug discovery dataset in lines 1053-1074 in Appendix E, but we will provide the takeaways here as well. In this experiment, we used the results reported in Table 2 of Genovese et al. (2013) and evaluated the patient response to different doses of the drug secukinumab via the American College of Rheumatology criteria ACR20, ACR50, and ACR70. The goal of the original study was evaluate the probability of a patient achieving at least ACR20 with each dose, so we used two response models in our experiment: the first using a binary response with probability determined by the proportion of patients achieving at least ACR20 in the original study, and a discrete response corresponding to 0.2 for achieving ACR20, 0.5 for achieving ACR50, 0.7 for achieving ACR70, and 0 for not achieving any criteria, with probabilities determined by the patient proportions in the original study. Again comparing to Sequential Halving and an elimination algorithm, we varied the cost \\\\(c\\\\) in our experiments, and we demonstrated that across a range of values for \\\\(c\\\\), in both response models, and across both the misidentification and simple regret penalties, none of the traditional BAI methods uniformly outperformed DBCARE. We feel that this is a clear demonstration of the utility of using DBCARE under this problem setting, rather than choosing a traditional BAI method, when the true gaps between the means are unknown. Though DBCARE is not guaranteed to give optimal performance on every single problem instance, we have demonstrated both theoretically and empirically that DBCARE will never perform too much worse than the optimal method, and does not require access to any knowledge that would be unreasonable for a practitioner to know a priori."}, {"review_id": "rg99wJp5FW", "reviewer": "Reviewer_8fq7", "summary": "This paper proposes a new performance metric on the topic Best Arm Identification, which combines the total expected pulling times and the failure probability(or simple regret) into the loss function. Targeted on minimizing this new metric, this paper discusses an oracular policy and its further extension DBCARE. This paper also provides theoretical analysis for the algorithm DBCARE. The comparison between the upper and lower bounds suggests that the excellency of the algorithm.", "questions": "I wonder whether there exist some conclusions for the hardness of achieving best of both. For example, if an algorithm can achieve relatively good performance in the case of large H, does it mean the algorithm will perform worse in the case of smaller H? This is only an optional question, as I think the minimax bound is well acknowledged in the current community.\n\nBased on my understanding, I believe $c$ can be considered the weights of stopping times, while setting the weight of failing to identify an arm is 1. Please elaborate more on the case when $c$ is very small or $c$ is very large. \n\nMeanwhile, given the known parameter $c$, can we derive performance guarantees on $\\Pr(\\mu_1\\neq \\mu_{\\hat{I}})$ or $\\mathbb{E}[\\tau]$? I know the current Theorem 2 already provides a common upper bound for these two terms. Can we do better?\n\nRegarding the numerical experiments, I wonder whether you can compare your results with an anytime algorithm. For example, “Anytime Exploration for Multi-armed Bandits using Confidence Information”, by Jun & Nowak, proposes algorithm ATLUCB. We can take the termination time of DBSARE as the termination time of ATLUCB and compare their failure probability. Do you think this comparison is reasonable? If so, can we expect DBCARE achieve similar or even better numeric performance compared to the ATLUCB?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: \n1. This paper proposes a new metric formulation on Best Arm Identification, different with the classical fixed-confidence setting and the fixed-budget setting. This new problem formulation is a great supplement for the academic community.\n2. This paper provides theoretical analysis for both upper and lower bounds. The comparison suggests the efficiency of the algorithm design, as it can handle both performance metric MI and SR, with modification on some hyperparameters.\n\nWeakness:\n1. As discussed by the authors, the upper and lower performance bounds differ in the case of $H\\rightarrow \\infty$, under the metric $\\mathcal{R}_{SR}$.\n2. In the numeric experiment, the proposed algorithm DBCARE cannot outperform others significantly. But it is still reasonable, as it remains reasonably good across all the instances.\n3. The authors should also compare their results with this preprint: https://arxiv.org/abs/2409.18909, which is closely related to the authors' models.", "was_revised": true, "final_justification": "After interacting with the authors and reading other reviews, I think the paper is interesting and will benefit the community. Hence I increase my score. Nevertheless, the authors shall discuss the limitations of the paper as discussed.", "rebuttal": "Thank you for your response and questions.\n\n**Weaknesses**:\n- *Differences when \\\\(H\\to\\infty\\\\)*: Here we address the noted weakness and the question regarding the hardness result. In lines 113-118, we note the reason for the inability to improve the lower bound in a straightforward way, which causes this gap between the lower and upper bound to arise. However, we do conjecture that there is a hardness result of the following form: any algorithm which does not have a priori knowledge of the gap and achieves the minimax optimality under the metric \\\\(\\mathcal{R}_{\\rm{SR}}\\\\) **must** have performance of the same order as our algorithm when \\\\(H\\to\\infty\\\\). The key insight here is that any algorithm that wishes to perform on the order of the current lower bound when \\\\(H\\to\\infty\\\\), must necessarily be willing to guess the optimal arm after receiving very little information. This algorithm can perform well on very complex problems (\\\\(H\\to\\infty\\\\)) and very easy problems (\\\\(H\\to0\\\\)), but will necessarily perform poorly on problems of moderate complexity, which is the region where the maximum of the lower bound occurs, and so algorithms with this behavior should not be able to achieve the minimax rate. We hoped to include a result of this form in this submission, but were unable to rigorously prove the result. We mention this conjecture in lines 359-360, and we do hope that this problem setting is of interest to the community and that a result of this form can be included in a future work.\n- *DBCARE empirical performance*: We believe that DBCARE’s reasonable performance across all problem instances is exactly its appeal, even if it is unable to outperform every other approach on each problem instance. As seen in Figure 2, specific choices for the budget \\\\(T\\\\) or the confidence \\\\(\\delta\\\\) can perform well on certain problem instances, but no choice of budget or confidence exhibits uniformly good performance across all problems. On the other hand, we can see that DBCARE does in fact exhibit uniformly good performance across all problem instances, which is especially desirable when the problem instance at hand is almost never known to a practitioner. Further, DBCARE even often shows performance close to the best hand-tuned choice for the budget or confidence for a particular instance.\n- *Comparison to Yang et al. (2024)*: To our understanding, we believe that the setting considered by Yang et al. differs from our setting in two meaningful ways. First, the setting in Yang et al. still requires a confidence parameter \\\\(\\delta\\\\) to be specified a priori and algorithms to be \\\\(\\delta\\\\)-PAC, whereas our setting considers a risk functional which explicitly trades off between performance and sampling costs without the need for a pre-specified confidence parameter. Second, the equivalent of “sampling costs” considered by Yang et al. is defined using the cumulative regret, whereas our setting considers a separate cost parameter \\\\(c\\\\) which is not dependent upon the gaps between the arms, but instead represents an external cost associated with accessing samples from the arms, such as paying focus group participants, promoting advertisements on social media during A/B testing phases, or running costly experiments. In lines 146-148 we do discuss the work of Kanarios et al. (2024), who consider a similar setting to Yang et al., though the sampling costs of Kanarios et al. are separately stochastically observed from the rewards, rather than being induced by the cumulative regret, which is more similar to our setting, but is still distinct due to the use of a pre-specified confidence parameter \\\\(\\delta\\\\). We thank the reviewers for bringing our attention to this work, and we will cite it and discuss it in our related works section in our final version.\n\n**Questions**:\n- *Regarding the cost \\\\(c\\\\)*: Because our risk functional linearly trades off between the performance penalty and the sampling cost, you can view \\\\(c\\\\) as the relative weight given to a single sample relative to a unit difference in performance. In all of our lower and upper bounds, we considered the cost \\\\(c\\\\) to be fixed and wrote our bounds in terms of either the suboptimality gap \\\\(\\Delta\\\\), in the 2-arm case, or the complexity \\\\(H\\\\), in the K-arm case. However, we could instead consider the gap or complexity to be fixed, and glean some insight on the effect of the cost \\\\(c\\\\) by considering the bounds to be functions of \\\\(c\\\\) instead. In this light, the phase transitions we identified for the gap and complexity now become phase transitions based on the cost \\\\(c\\\\), and we can interpret them intuitively. When the cost \\\\(c\\\\) is “large” relative to the gap or the complexity, then we observe the limiting behavior that we pointed out under the small gap or large complexity setting, where the optimal behavior is to guess the optimal arm, as the cost of sampling is too large relative to the increase in performance under further sampling. On the other hand, when the cost is relatively small, then the lower bound and the performance of DBCARE are more dependent on the complexity of the particular problem at hand.\n- *Additional performance guarantees*: In order to derive the results of Theorems 2 and 4 showing DBCARE’s performance under our proposed risk functionals compared to the lower bound, we do have to separately bound the probability of misidentification (for Theorem 2) or the simple regret (for Theorem 4) and the expected number of samples (for both). Thus, we could provide guarantees for the individual terms, but the focus of our results is on the performance under the proposed risk functionals, which linearly trade off the performance penalty with the sampling costs.\n- *Comparison with anytime algorithms*: To the best of our understanding, anytime algorithms like ATLUCB, Doubling SAR, and Doubling SH exhibit successively better performance when allowed to continue running over long time horizons, but guarantees on their performance do not apply until surpassing a number of total samples depending on the problem complexity and possibly a pre-specified confidence parameter. Thus, by naively applying the stopping rule used by DBCARE to one of these algorithms, it is unclear to us how those algorithms would perform, and would likely be highly dependent on the particular problem scenario. This is especially due to the fact that the choice of stopping time for DBCARE and its theoretical guarantees are tied into the specific sampling scheme that is used by DBCARE."}, {"review_id": "QxgWnvgQnC", "reviewer": "Reviewer_1bsu", "summary": "This paper introduces a novel framework for Best Arm Identification (BAI) in multi-armed bandits that directly balances the trade-off between sampling cost and arm performance. Unlike classical fixed-budget or fixed-confidence setups, the proposed setting minimizes a risk functional that penalizes both incorrect arm identification and the cost of pulling arms. It considers two measures: the sum of misidentification probability and sampling cost, and the sum of simple regret and sampling cost. The authors establish instance-dependent lower bounds for both settings, showing a phase transition depending on problem complexity and cost parameters, which does not appear in fixed-confidence/budget setups. A new algorithm, DBCARE, is proposed and shown to nearly match the lower bounds up to polylogarithmic factors and constants across different regimes. Theoretical analysis is complemented with empirical evaluations on synthetic and real-world datasets.", "questions": "- Could the authors elaborate on the role of $\\delta$ beyond worst-case guarantees? Is there potential to select $\\delta$ in a more data-dependent or adaptive way that improves empirical performance?\n- Can the authors provide a practical scenario where this problem formulation can be used? It has mentioned clinical trials. But I suppose in these safety-critical fields, identifying a good arm is quite essential and the cost is not the primary concern.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n- The introduced cost-aware BAI formulation seems to be new from the canonical formulations.\n- The paper presents theoretical results, including lower bounds with clear phase transition behavior and matching upper bounds (up to polylogarithmic factors and constants) for the proposed algorithm across regimes.\n\n**Weaknesses**\n- The choice of the confidence parameter $\\delta$ plays a crucial role in DBCARE’s performance but lacks thorough discussion. A more detailed analysis of its sensitivity or adaptability to instance-specific features would be valuable.\n- DBCARE operates in a round-robin fashion and eliminates arms based on confidence intervals, which may limit its adaptivity. It would be beneficial to explore more adaptive sampling strategies that better focus on promising arms.", "was_revised": true, "final_justification": "This paper introduces a novel framework for Best Arm Identification (BAI) in multi-armed bandits that directly balances the trade-off between sampling cost and arm performance. The problem and the proposed algorithm is of interest to the community.", "rebuttal": "Thank you for your response and questions.\n\n**Weaknesses/Questions**:\n- *Role of \\\\(\\delta\\\\)*: The confidence parameter \\\\(\\delta\\\\) used by DBCARE diverges from that used in traditional BAI approaches, and is **not** a hyperparameter to be chosen by users per instance. We explicitly state the values used for \\\\(\\delta\\\\) in the statements of Corollary 2.1 and 4.1 and Theorems 2 and 4, and we discuss in lines 218-220, 257-258, 304-305, and 325 that \\\\(\\delta\\\\) is used to control control the worst-case performance of DBCARE, ensuring that, on the event that the true gaps are not contained within the confidence intervals, we incur no more additional risk than the cost of a single arm pull, \\\\(c\\\\). We introduce \\\\(\\delta\\\\) in this manner to guide intuition for this problem as it relates to traditional BAI approaches, and so that we can generalize a single algorithm for use with both risk functionals, \\\\(\\mathcal{R}\\_{\\text{MI}}\\\\) and \\\\(\\mathcal{R}\\_{\\text{SR}}\\\\).\n- *Sampling scheme*: With its current sampling scheme, combined with \\\\(N^\\star\\\\) being a decreasing function of the size of the surviving set, DBCARE is in fact adaptive to the problem setting at hand, quickly eliminating highly suboptimal arms and allocating additional resources to promising candidates. Further, this approach appears to be sufficient, as evidenced by the fact that DBCARE is near optimal on nearly every problem instance, and this sampling scheme aligns with many existing algorithms in the BAI literature, such as Sequential Halving, Successive Rejects, and racing / elimination-style algorithms.\n- *Practical applications*: In lines 23-24 and 39-46, we discuss the example of A/B testing in advertising, where net profit is the primary metric that most business end users would be interested in. In lines 24-25, we also mention the ability to apply this framework to hyperparameter tuning and model selection in instances where model performance and computing resources required to evaluate samples can be explicitly traded off. In Appendix E, where we report the results of some additional experiments, we further discuss the utility of our setting when applied to early-stage animal testing and high-throughput experiments for drug discovery and dose finding where revenue for a pharmacology company is relative to drug efficacy and profit is a metric of interest. In general, BAI is an abstraction to help build intuition for general problem structures and more practical applications can be built on top of the ideas introduced in works such as ours."}, {"review_id": "kStKbBIS1V", "reviewer": "Reviewer_yixL", "summary": "The authors study how to balance performance and costs in bandit problems.\nSpecifically, they propose two new settings that interpolate the fixed confidence and fixed budget settings. Specifically, they study:\n- A \"missidentification setting\", where the goal of the agent is minimizing the probability of missidentification + the expected stopping time of sampling multiplied by some costs $c$ which has to be interpreted as the cost of sampling\n- A \"simple regret\" setting, where the goal of the agent is minimizing the distance in mean of the recommended arm wrt to the optimal one + the expected stopping time of sampling multiplied by some costs $c$ which, again, has to be interpreted as the cost of sampling\n\nThe authors provide first a detailed description of both problems for the case of $K=2$ arms. Their findings highlight that there exists two regimes: when the cost is large wrt the gap, then, the agent should not sample the arms, but just recommends an arm at random, while, when gap are larges wrt the costs, the agent should explore the arms in order to minimize the two risk functionals that I mentioned above. \nThen, the authors extend the results to the K-arm setting and perform some numerical experiments.\n\nOverall, the authors provided lower bounds, and almost matching upper bounds (both in a worst-case sense on the possible problem instances).", "questions": "For the K-arm setting I was expecting a smoother transitions in the two regimes according to the gaps of the bandits. For instance, suppose that the top-K/2 arms are very close while the remaining ones are highly sub-optimal. In this case, I was expecting the LB to show that (e.g., for the MI setting) we are paying a fixed error term of proportional to K + a gap dependent quantity that encodes the cost of pulling arms to discriminate the K/2 arms with large gaps.  This is also how the algorithm is somehow working, but e.g., Theorem 2 does not show this sort of problem-dependent behavior.I suspect that this might be related to the weaknesses that I was mentioning above, i.e., the fact that all results are not problem dependent but only problem dependent on the worst-case on the possible instance. Can the authors comment on this point? It seems that this point is also related to the future directions that the authors are mentioning at the end of the work", "limitations": "This work is of theoretical work. I do not foresee a direct path to negative societal impact.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "# Strenghts\n- Interesting setting that nicely interpolates between fixed budget and fixed confidence setting. It removes the need of specifying an horizon and a confidence level, by just introducing a cost parameter $c$. To the best of my knowledge, this is novel and deserves attention from the community\n- The clarity of the exposition is good and the paper is easy to follow.\n- The paper highlights nicely the presence of two regimes that depend on costs and gaps. This provides intuition on the challenges of this problem compared to more canonical BAI settings.  \n\n# Weaknesses\n- All results are not fully problem dependent, but only problem dependent on the worst-case on the possible instance. This raises questions on the tightness of the results (see also my question below). However, I do not believe that this is a sufficient reason to stand for rejection. \n\n# Minor comments\n- Proof ideas on the algorithm is rather clear. However, proof ideas for the LB (lines 88-90) is not that informative. I invite the authors to either expand it or remove it in the future\n- Additional work on multi-fidelity BAI \"Optimal multi-fidelity best-arm identification\", Poiani et al., NeurIPS 2024\n- As a future direction, I think it would also be interesting to model the cost of pulling an arm in an arm-dependent fashion. Do the authors have any intuition on how (and if) their results extend in this direction?", "was_revised": true, "final_justification": "I am confirming my positive score as I am satisfied with the discussion", "rebuttal": "Thank you for your response and questions.\n\n**Weaknesses/Questions**:\n- *Worst-case dependence/Specific settings*: The worst-case performance that we study is the worst-case on a **fixed** gap or complexity, so while these results are not based on specific bandit instances, they are still gap/complexity-dependent results. This is in line with gap- and complexity-dependent bounds elsewhere in the BAI literature, and serves to eliminate pathological cases such as good performance of an algorithm which always returns a particular index, or problems where the noise is so small that just a single sample from each arm is sufficient to identify the optimum.\n  - Regarding the specific \\\\(K/2\\\\) close gaps structure you mention, this type of behavior is encoded via the complexity measure \\\\(H\\\\) in the lower bound. If \\\\(K/2\\\\) of the arms have some small gap \\\\(\\Delta\\\\) and the remaining have a much larger gap, then the lower bound will be proportional to \\\\(K\\Delta^{-2}\\\\) plus some much smaller quantity from the large gaps. \n- *Proof ideas*: Given more space in the final version of our work, we are happy to expand upon the lower bound proof idea to increase clarity.\n- *Additional multi-fidelity BAI work*: Thank you for pointing out this publication, we will include this in our remarks on multi-Fidelity BAI in the final version.\n- *Arm-dependent costs*: We are also interested in this as a future direction! We made some preliminary explorations into the effect of heterogeneous costs in the 2-arm setting, and it appears that the role of \\\\(c\\\\) in the lower bound would be replaced by \\\\(c\\_1+c\\_2\\\\), while the oracle upper bound depends on \\\\((\\sqrt{c\\_1}+\\sqrt{c\\_2})^2\\\\). We believe that we could allow \\\\(N^\\star\\\\) to provide a different maximal number of samples for each arm depending on the cost for that arm, but we thought it prudent to consider a more streamlined approach with a single cost parameter shared by all arms when introducing this new paradigm, especially since heterogeneous costs greatly complicated the analysis. We also believe that this was appropriate for this work because a single cost parameter is relevant in many settings such as some advertisement A/B testing or focus group testing."}]

Author rebuttal:

Meta-review: his paper studies the best arm identification problem for multi-armed bandits. However, in contrast to the fixed budget or fixed confidence setting, the authors propose a novel criteria that balances correctness with sample complexity, motivated by the difficulty of choosing the budget or confidence level. While the new criteria has its own special constant c to choose, reviewers were content with the setting and felt that the paper would make a strong contribution to the (mature) area.
Decision: Accept (poster)