Multi-Fidelity Best-Arm Identification
Authors: Riccardo Poiani
Alberto Maria Metelli
Marcello Restelli
Venue: NeurIPS 2022 Accept (2022)
Keywords: best-arm identification
fixed-confidence
multi-fidelity
multi-armed bandit

Abstract: In several real-world applications, a learner has access to multiple environment simulators, each with a different precision (e.g., simulation accuracy) and cost (e.g., computational time). In such a scenario, the learner faces the trade-off between selecting expensive accurate simulators or preferring cheap imprecise ones. We formalize this setting as a multi-fidelity variant of the stochastic best-arm identification problem, where querying the original arm is expensive, but multiple and biased approximations (i.e., fidelities) are available at lower costs. The learner's goal, in this setting, is to sequentially choose which simulator to query in order to minimize the total cost, while guaranteeing to identify the optimal arm with high probability. We first derive a lower bound on the identification cost, assuming that the maximum bias of each fidelity is known to the learner. Then, we propose a novel algorithm, Iterative Imprecise Successive Elimination (IISE), which provably reduces the total cost w.r.t. algorithms that ignore the multi-fidelity structure and whose cost complexity upper bound mimics the structure of the lower bound. Furthermore, we show that the cost complexity of IISE can be further reduced when the agent has access to a more fine-grained knowledge of the error introduced by the approximators.
Finally, we numerically validate IISE, showing the benefits of our method in simulated domains.


Multi-Fidelity Best-Arm Identification
Riccardo Poiani
Alberto Maria Metelli
DEIB, Politecnico di Milano riccardo. poi andaani@ppll @polimi..m...mmmmmm it
DEIB, Politecnico di Milano
allertomaria. impoiiiiiit
Marcello Restelli DEIB, Politecnico Milano
Abstract
several real-world applications, a learner has access to multiple environment simulators, each with different precision (e.g., simulation accuracy) and cost (e.g., computational time). In such a scenario, the learner faces the trade-off between selecting expensive accurate simulators preferring cheap imprecise ones. We formalize this setting as a multi-fidelity variant of the stochastic best- arm identification problem, where querying the original arm is expensive, but multiple and biased approximations (i.e., fidelities) are available at lower costs. The learner's goal, in this setting, is sequentially choose which simulator query in order to minimize the total cost, while guaranteeing to identify the optimal with high probability. We first derive lower bound the identification cost, assuming that the maximum bias of each fidelity is known to the learner. Then, we propose novel algorithm, Iterative Imprecise Successive Elimination (IIS),, which provably reduces the total cost w.r.t. algorithms that ignore the multi-fidelity structure and whose cost complexity upper bound mimics the structure of the lower bound. Furthermore, we show that the cost complexity of IISE can be further reduced when the agent has access to a more fine fine-grained knowledge of the error introduced by the approximators. Finally, we numerically validate IISE, showing the benefits of our method in simulated domains.
Introduction
In the multi-armed bandit setting (26], the agent selects, at each interaction round, an arm and observes sample drawn from its reward distribution. Unlike the regret minimization setting (26). where the agent tries to maximize the cumulative return, best-arm identification (BAI) problems [10 2], the evaluation index relates exclusively to the quality of the arm recommended at the end of the exploration phase. More specifically, in the fixed-confidence setting [17], the agent aims identifying, with probability 5, the arm with the largest mean reward, while minimizing the sample complexity, i.e., the number of collected samples necessary to make the final decision. Due its generality, the BAI framework encompasses a wide spectrum of applications, ranging from medical trials (38), to hyper-paramett parameter optimization (27]. crowdsourcing [7), recommender systems 25 simulation-based studies in physies 443 and A/B testing [4].
However, in practical cases, querying an arm to obtain a sample from its reward distribution might be expensive. For instance, in the context of physics simulation studies, where pulling arm corresponds to the evaluation of complex model under some given arm parameters, intensive use of computing power required to obtain the reward we are interested Nevertheless, simpler and, consequently, cheaper and biased, models might be available to the agent. Another example is stochastic planning, where the agent needs compute the best action (i.e., arm) that maximizes the future sum of rewards over maximum horizon H. However, while in principle it is possible to plan
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

considering the entire horizon, cheaper and biased estimates can be obtained by cutting the depth of the search < H. For these scenarios, the fideli-i (MF) framework (9 21 [2] that exploits this additional opportunity has recently gained attention in the literature. The main rationale behind these methodologies is to exploit less expensive approximations specific regions of the arm space to limit the resources allocated to distinguish options that are far from optimal, and do not require high accuracy. So far, most of the multi-fidelity literature has focussed on black-box function optimization, with the goal of optimizing target function f when multiple approximations of f are available I.. Among these works, the ones more related to the bandit literature under different smoothness assumptions, these authors aimed at designing strategies that explore the arm space to minimize the simple regret, i.c., the difference between the true optimal value of and the best unbiased query made to f during the optimization process. Other works studied cumulative regret analysis [21 20 active learning [46 32.. reinforcement learning
15
33
22
39
19
28
22
19
39
40
9 30
and applied approaches 36 44 31.
In this paper, on the other hand, we focus on the understudied multi-fidelity fixed-confidence BAI setting. More specifically, we study the minimization of the cost complexity, novel metric that we introduce by extending the notion of sample complexity to the multi-fidelity setting, by weighting each sample with the related cost. The goal of the agent is to output the optimal arm with probability 1 8, while minimizing the total cost. To this purpose, as commonly done in the literature (9] 21 (20, 39 M. we assume that the agent has some knowledge of the quality of the approximator, which is usually expressed in terms of upper bounds on the maximum bias that the fidelities introduce on the arm set. This term corresponds to the maximum distance between the mean of the desired (but expensive) arm distributions and their approximations.
Contributions. In this paper, we introduce the notion of cost complexity for the multi-fidelity BAI setting (Section[]. 2 We derive a lower bound for this novel index, under the standard assumption that the agent is equipped with knowledge of the maximum bias that each fidelity has w.r.t. the original, expensive and unbiased bandit model (Section 3} As we shall show, our result highlights several properties of the problem along with its challenges. Furthermore, we propose the Iterative Imprecise Successive Elimination (IISE) algorithm (Section D. for which, we derive cost complexity upper bounds that, under certain assumptions, mimic the structure of the lower bound, and that is provably robust w.r.t. BAI algorithms that ignore the multi-fidelity structure. We also show that the performance of IISE can be further improved when a more fine-grained knowledge of the behavior of the approximations is available to the agent (Section 5). After revising the literature (Section 6 propose numerical experiments on simulated domains that empirically verify our claims (Section 77.
2 Setting
In the classical (ui...., where K E N is the number of arms and v; denotes the reward distribution associated with arm E [K] = (1...., K}. Denote with (4; the expectation of v4 and, assume, that the K arms are ordered such that 141 #2 2... j.K- We assume that the reward distributions 14: subgaussian with known scale parameter o². At each interaction round t E N. the agent selects an arm 4 E [K] and receives a reward R2 sampled from Vi,- Let (:) be the total number of pulls of arm E [K] up to time E N. Given a confidence level 5 E 1), the goal of the agent is to recommend an arm I(() E [K] that corresponds to the optimal arm 1 with probability at least 1 8, while minimizing the sample complexity P(T) = Σie(K] IE (T)]. where T is the stopping time of the agent. Any algorithm that recommends the best arm with probability 1 1- 5 is said 8-correct. For every sub-optimal arm i >>> 1, we define its gap w.r.t. the optimal arm A, μ4 M4.
BAI setting [7]. the agent interacts with a bandit model v =
In this paper, we differ from this classical setting as, for each arm E [K] we assume the agent has access to M - 1 E N fidelity distributions V4, ......... Mr,M- each - -ubbaausss,nn, with means Ms,1, M4,.. - We unify the notation introducing a maximum fidelity M to encode the true arm distributions the agent is interested in, i.e., V4,M 1/4 with mean H., == f4z. As in previous works [1 20 M.. we assume that there is a relation encoding how much information distributions of fidelity < M contain w.r.t. to the true arm distribution. More specifically, for each fidelity m E [M], it is always possible to write fs.m := A4, + Es.m for some appropriate Ei.m E R. Then, we assume that the agent has access to &m 2 maX [L,, from which follows that |Ms. - Pa.M| 5m- We notice that &m represents an upper-bound on the maximum bias of fidelity m E [M]. At each
2

---

interaction round E N, the agent selects an arm I, E [K], fidelity m, E [M]. and observes a reward R2, drawn from mm The cost of gathering samples at fidelity m known and specified by Am We make the standard assumption that λ < A2 <.... < XM and & f >.... Ear :00 At this point, let Tim (t) be the number of pulls to arm E [K] at fidelity m E [M] up to time Ze N; we define the cost complexity as:
((T)=
Σ Σ
Am (Temm
(1)
KE|K] me[w]
where is the stopping time at which the agent will output the optimal arm with probability 1- 8.
3 Cost Complexity Lower Bound
In this section, we discuss the intrinsic complexity of the multi-fidelity BAI problem, by providing and analyzing a lower bound on the cost complexity (proof Appendix B
Theorem Consider a multi-fidelity bandit model with Gaussian distributions Vi,m =N m o²)
such that ju Pi.M| S 5m for every i E [K] and m E [M]. Then, for any 8-correct algorithm and ò S 0.15, it holds that:
Am
K
Am
E [
min
min mEM;
log 2.48
meM: (L 12,m)
(L(Vism 1m
where KL(p, 9) is the Kullback- Leibllr divergence between distributions and q, 12,m = NN222M Em, 0²), 7i.m = =N -N Em. )²), M1 = {m [M] fl.m > ExwVe, [x]] and M, = {m E [M]
Egww,, m [x) > |imm) for i>
This bound reveals several properties of the multi-fidelity fxed-confidence BAI problem. A single term KL_
1m.m) with i i 1 can be interpreted as lower bound on the minimum cost that any 8-correct algorithm needs to pay to conclude that arm is sub-optimal. Suppose, for the moment, that M; contains any fidelity Am (T 11.,) is the cost-based multi multi-fideitty counterpart of the usual KT.-1(Mi: v1) which appears in the standard BAI lower bound [24. This can seen as a lower bound on the cost to discard arm i using samples gathered at fidelity
[M]. Then, once we fix E M,, its related component
Notice that, in this sense, the term 71.m replaces the usual vi to take the bias of fidelity m into account. The minimum, consequently, encodes a lower bound on the cost of the most convenient fidelity with which we can discard i. The reason why we have a minimum over M; instead of [M] is that, given a fidelity m E [M], m might not be useful to discard i, since A; might be too small for the bias that introduces. This concept is further clarified in the following remark:
Remark 1. Consider the following problem instance: for each m E [M], let 11,m = M1,M - Sm and Ms.m Mi.M + for i + 1. Then, Theroem I reduces to:
Amo²
Ω
Σ
min MEMM : A.>2E (A,
m
As we can see, if A; < 2 for some m, its related component is not present in the lower bound. note that the setting of Remark represents a worst-case fidelity-
Furthermore, it is interesting dependent scenario. Indeed, each fidelity m E [M - underestimates the reward of the optimal arm and overestimates the ones of sub-optimal arms.
Thighlights the main challenge of our setting. For each value of Em- there exists a multi-fidelity bandit model / for which the lower bound is given by R Aug" A
Finally, we show how Theorem [
(given Remark 1 it is sufficient consider A; such that the only fidelity in the minimization set is M). It is clear that this cost complexity can be matched (up to log factors) by many BAI algorithms available in the literature (e.g., (10) that ignore the multi-fidelipg structure of the problem. The main
CCases in which X; = As41 or & = E.+1 hold can easily be ruled out. Indeed, with the same cost one could gather a more precise sample using another fidelity, or equivalently, one could gather a sample of the same precision, using cheaper fidelity; ie., remove these dominated fidelity prior running any method.
3

---

High bins
Low cost
Arm
Arm 2
Arm
Arm K
88
perform
m=2
Aru
Arm 2
Arm K-
Arm K
fidelity
on tidelity m+-1
$888
Low bios High
M
Arm
Arm
Arms
Arm K
2
Figure 1: A visualization of how IISE works: at the beginning IISE pulls arms the cheapest fidelity Successive Elimination fashion. Using samples from these biased distributions, it tries to discard sub-optimal arms whose A; is sufficiently large. Once given number of samples determined by Om has been reached, ISEE moves to the sub-sequent fidelity. This process goes on until the optimal arm is identified in high-probabilityy
issue, in this sense, is the fact that the agent does not know, priori, the values of A, To build an algorithm that achieves robustness (i.e.. not being worse than these uninformed strategies). then, need to control how much spend to explore the arm distributions at fidelity < M. More generally, this reasoning also extends to building algorithms that match the lower bound. In this sense, observe, for the fixed-confidence BAI setting, the adversarial behavior that fidelity might have, as previously reported in 21 for the finite-armed bandit regret minimization setting.
4 Imprecise and Iterative Successive Elimination
In this section, we present our algorithm, Imprecise and Iterative Successive Elimination (IISE, Algorithm ??), to solve multi-fidelity fixed-confidence BAI problems. In particular, while developing our method, we pursue the following two objectives. First, we want to guarantee robustness w.r.t. uninformed strategies that blindly use only the highest fidelity M to identify the best arm. Indeed, we expect a good agent be able to reduce the total cost by exploiting the peculiar multi-fidelity structure of the problem. Second, we aim at providing strategy whose upper- -ouer-bound structure resembles, as close as possible, the one of the lower bound presented in Section
Our solution (pseudo-code in Algorithm [ and visual representation in Figure I builds on the Successive Elimination algorithm [10]. More specifically, we proceed by epochs, one for each fidelity m E [MM], considered in increasing order. In each phase m E [M]) we query all the active arms, i.e., those that have not been discarded yet, through their approximated distributions Vs,m at fidelity m. We denote the set of active arms with S C [K]. IISE keeps usual empirical mean estimates pi,m.t of the mean Pi. of reward distributions Vi,m for each E S, and discards all the arms for which the following applies:
Pjmme U (1, K.K.555 Sm 12 Pi. (1, KM -m
8
BjES S:
(3)
where U (1, is symmetric bound the empirical means (defined below). Condition (3) aims at eliminating all the active arms whose estimated empirical mean upper bound falls below the empirical mean lower bound of another active arm j. More specifically, set U (t, 5, g) =
B (1, () + / 2 log 1s2
+ E. As we can see, U (1, 6,E) is composed of the usual concentration term B (t, 8) plus the fidelity bias &. As proof highlights, this additional term is required to

---

Algorithm Iterative Imprecise Successive Elimination (IISE).
Require: Mulli-fidelity bandit model v, confidence thresholds {am JM
bounds (Em JM
1: S - []
2: m <- 1 and L <- 0
3: while |S]
do
4: if a. 2 4B (L, KM then
5: m m- + and 0
6: end if
7:
Pull all arms in fidelity m and f +
8: Update P...m. for all E
9: St S-S\ (iE (0..m.................... U (t, RMr (m) Mimm. +U (t, KM
RMM (mm)
10: end while
11:
return
ensure that the optimal arm remains, with high probability, in the active set S until termination The duration of each epoch (i.e., how much IISE tries to exploit fidelity m) is determined by a threshold parameter am (to be defined later). At each round, the value of B (t, KM) decreases and as soon á as 4B (t, KM drops below Omm, ISE switches to the next fidelity m + 1. Notice that, to achieve 5-correctness, is required to ou to O, so that the last phase is guaranteed identify the optimal arm, and am > 0 for m < M, so that each phase is assured to terminate in finite number of rounds. Then, keeping generic thresholds a'm that satisfy the previous conditions, we can show that ISSE is d-correct and its cost complexity is upper bounded by the following theorem (proof in Appendix
Theorem 2. af > for every m E [M - 1] and αM = O, then, with probability at least - 8, ISE returns the optimal arm with cost complexity c(T) upper bounded by:
Xm, 45m,)² -
OKM
Amo²
o2MK
o
c(7)
Σ
log
Σ
log
(A
(A. 46
a
where m; is the smallest m [or which A; 48 a'm holds.
We notice that the cost required by IISE to discard i is composed of two terms. The first one is the cost discarding arm using samples at fidelity m, while the second one is the cost trying to discard arm at lower fidelity < m,, As our proof reveals, my is the smallest fidelity for which IISE ensures that arm will be discarded.
4.1 On the Choice of the Thresholds Ot
In this section, we highlight one of the main challenges of the MF setting, mentioned in Section Since we are unaware of the suboptimality gaps A,, we may attempt to choose am so as to minimize w.r.t. the worst-case choice of suboptimality gaps A,, that is:
the cost complexity of Theorem
2
Am, o²
Am
o MK
min (A, mm,.)²
log
Σ mcmm
log
(4)
(A,
45m,
a
where (a1 (M) and A (A2. (A2....,, Ax) are the threshold and gap vectors. However, it easy to verify that Equation 4 minimized for am +o0 for all m < M and aar = 0, i.e., an algorithm that exploits the highest fidelity M only. As we can see, IISE reflects the peculiar issue of the MF-BAI lower bound. In the worst case, any fidelity m < M is not useful to reduce the identification cost since it introduces too much bias w.r.t. A,, regardless its cost. For this reason, as done in previous works 21], we restrict the class problems with some assumptions whose goal is making the fidelity structure provably convenient. More specifically:
Assumption 1 (Costs and Biases Relationship). For every fidelity T7 [M 11-1) 1]. it holds that:
(VAe Vdm
(V>: / Am)
Σ min k
< min
(5)
(Em: )2
(Em E2
*Omitting in the elimination rule might wrongly eliminate the optimal arm just because, at low fidelity, its approximated distribution has negative bias.
5

---

Assumption 1 deserves some comments. First of all, it directly encodes a relationship between costs and biases. To provide an interpretation, we notice that the assumption always satisfied for: (i) costs that grow at least linearly and (ii) 5's that satisfy the following decay rate: Σmem (E.. (m---m-1>> cm
The intuition behind the cost increase rate (i) is that, with sub-linese growth, attempting to discard arms with a cheaper fidelity is too inconvenient w.r.t. gathering more accurate samples for slightly higher cost. For what concerns the {'s decay rate, instead, condition (ii) limits the adversarial behavior that fidelity might have. If two subsequent ç's are very close together, little can be inferred from switching from the first fidelity to the second one. This sort of problem was already highlighted in 2111 We remark that Assumption [] compared to Assumption 1 of 22 Emcm [5m) a involves both costs and biases, which is something we expect since the main challenge of the setting is to trade-off between them. Indeed, depending on the values of X's it is possible to tolerate g's that decay linearly; vere-versa, if ('s decay fast enough, is possible to tolerate costs that increase sub-linearly.
Although Equation (5) might appear abstract, we show that it holds for a large class problems. Consider Markov Decision Process (MDP) [35 (),, p, r. where is the state space, A is the action space, p= {phhppp,.a h221 set of transitions kernels, r r= {rr h221 a set of reward functions, and n E [0. is a discount factor. When an agent takes action a in state y at step h transitions to y' with probability Ps (v' y, a). and receives a deterministic reward rΛ (v, a) E [0, 1]. Given a state E ), our goal is to find the action that maximizes the cumulative discounted reward over the next H stepy Given an initial action, way to compute sample from its future cumulative discounted reward is to apply a Monte Carlo search algorithm (e.g., depth first search) truncating the planning depth at hh < to obtain a cheaper but biased estimate of the cumulative discounted reward. In this sense, this scenario fits the fixed-confidence MF-BAI setting. Let M be the maximum depth, then, for each depth m E [M], we set as Am the number of generated nodes, that, assuming a constant branch factor A, is exponential in vn (i.e., Am = ). Instead, for &. is easy to obtain the following upper bounds on the maximum bias S..
(1)=+1 7 (MM++)/( //11 - 11). Now, it possible to show that Assumption
holds (proof in Appendix C.
Proposition 1. Consider A 2. If Am = A and f. = (n - 1/1+1)/(1 - 11) for all m E [M), then Assumption hoolds.
4.2
Most Convenient Fidelity Thresholds
Given the structure of Theorem I and its interpretation, during a phase m E [M]] we expect a good choice of thresholds a to let IISE discard all the arms i * 1 that should (and can) be discarded at m. Therefore, during m, we aim at concluding that a given arm suboptimal only if there is no other fidelity m > m in which gathering samples at m is more convenient, in term of identification cost, w.r.t. m. We formalize the previous concept in the following definition.
Definition (Fidelity Convenience). Consider a sub-optimal arm i and a fidelity m M such that A > 46m- We say that fidelity m is convenient for arm i if:
Am
Am
min 177
(6)
(A, 46m)
In Equation 6
we are comparing the cost of discarding gathering samples at phase m only with the cost of discarding i using more precise fidelity ग > m. Therefore, solving it for A;, we identify the gaps of the arms that can be conveniently discarded at fidelity m rather than at 77:
4(5m V Am
5.
4(Em, Em Am
A
max M2Rc>
max 4 M2m>> m
V
/mmm
VA
V
To discard all i that satisfy Equation
it sufficient to set thresholds am for m < M as follows:
4(5m - Am
O'm
max M2m>m
(8)
Vxm
VAm
At this point, under Assumption I it possible to prove that, with this peculiar threshold choice, the cost complexity of IISE can be rewritten in the following way (proof in Appendix C
p Mooe formally, (vAr-i - vA, s (VAAAii for i,j E [M-1] and j > i.
In the discounted setting, this is equivalent to search for c-optimal action.

---

Theorem 3. Under Assumption I selecting the thresholds as in Equation 1 with probability least 8, IISE returns the optimal arm with cost complexity d(T) upper bounder by:
K min [EIMMAA,>455 (A,
Am
AMO A
SŌ
46m)
As we can appreciate, this result comes with two desired properties. First of all, IISE is provably robust w.r.t algorithms that ignore the multi-fidelity structure of the problem. We remark that to have this nice property, Assumption does not need to hold for each m E [M]. It is always possible to pre-select subset of fidelity for which the assumption holds. Secondly, the bound in Theorem 3 clossey mimics the behavior of the lower bound (Equation 2). The only difference stands in the filled in for future work. Notice, again, that the similarity also holds for the case in which we select subset of fidelity for which the assumption holds. In this case, however, our minimization will be on a restricted fidelity set w.r.t the original one.
fact that 2 now replaced with 45m- We leave this gap
4.3 Nearly-Optimal Identification
As for the Successive Elimination algorithm, one can easily modify IISE so that it returns an c-optimal arm. In this case, show that the identification cost is upper bounded by (proof in Appendix C)
Amo?
Amo?
c(T)
Σ KE
min m.d. 245m (A,
min mm (E- 45
45m)²
where K., (i E [K] 114 cc. As usual, for arms that are not c-optimal we pay the original cost of Theorem For the ones in Kc,, instead, their cost is actually clipped by c. In multi-fidelit this has the further implication that, depending on the values of biases, costs and required accuracy, we might never query the most expensive unbiased fidelity M. In particular, let us focus on two-armed bandit problem with two fidelity values, and consider A <2<E. E. Then, we will never query M if:
45 Am
( 46 + VAM
Amm
The first term guarantees that ISE can discard using m. the second one, instead encodes the convenience of w.r.t. M in terms of costs. As AM increases, this term shrinks to zero. When λM - +00, the condition reduces to e 45m- This means that if fidelity m is precise enough for the desired accuracy e, we completely neglect fidelity M.
5 Breaking the Cost Barrier
We now show that (a slightly modified version of) IISE can further reduce the cost complexity when more fine-grat fine-grained knowledge on the type of error that approximators introduce available. The main intuition behind the following reasoning is that what matters when exploiting fidelity m < M is not the bias they introduce, but whether the arms do not preserve the order w.r.t. the mean of the true reward distributions Vi,M. Indeed suppose to have access to a fidelity with very large bias but which fully preserves the order on the means of the arms. In this scenario, it is possible to run a standard BAT technique on this fidelity only and still obtain the optimal arm. We now formalize how much certain fidelity m preserves the order with the novel concept of maximum bias variation Tmm
Ymm max {l [i.. {..ml)
1.j K]
Under the assumption that 71 22 2 ... TM == are available the learner, IISE can be conve- niently modified to obtain the following bound the cost complexity (proofs, pscudocode, and
7

---

formal statement in Appendix D
K Σ
Am
(
min mE 2 (A; 2mm))
To obtain such result, the only required modifications stand in the elimination condition, which now becomes F...m.t - B (t, KM fi.m,. + B (t, KA +'mm and in the definition of the thresholds Om: in which 4f's s are swapped with 2y's. s. We will refer this modified algorithm with IISE-y. As our proofs show, IISE-7 can also exploit upper bounds om on the true maximum bias variation (i.e., on 2 "m) the complexity as in Equation ( but 7m replaced with dnn-
8
We remark that, by definition, 7' S 2m which provably demonstrates the benefits of exploiting order-aware knowledge in the MF-BAI setting. Interestingly, we also notice that in the worst-case scenario (i.e., 7mm 2m,, Equation (9) implicitly recovers the cost complexity of Theorem 3
Practical Relevance of Maximum Bias Variation. Finally, we highlight that the knowledge about upper bounds 6m is available in large class of problems. In particular, consider settings in which means of fidelity m < M are underestimations of the ones of fidelity M, i.e., 14,M - /1.m 2 0 for all EE [K] and m E [M]- This is the case, for instance, of the stochastic planning application of Section but it also common in other settings such as training models with less iterations. In these problems, it always holds that 7/m. S (proof in Appendix D Therefore, we can set @m = Em in IISE-y to obtain the improved cost complexity of Equation where 2/m is replaced with 25m.
Related Works
In this section, we revise the literature with particular attention to best-arm identification and the multi-fidelity setting.
Best-Arm Identification. The BAT setting has aroused the interest of the research community for a long time 10 6 2) In particular, [10) proposed the Successive Elimination algorithm, together K A (log (ō-1)
with the first gap- depeedenndent upper bound on the sample complexity: O
log (K) log (A, ))) This algorithm is known to match the lower bound up to logarithmic factors. Indeed, (29 24 showed that, for all possible instances, every d-correct algorithm requires at least 22 AF loog 1)) samples to output the optimal arm with probability 1 8. To overcome the
logarithmic mismatch, several works have proposed both tighter upper 12
23 16 7
[3 & and
lower bounds [66 13 g. Concerning the BAI literature, we leverage on the change of distributions
arguments presented in [4 to build lower bounds for our novel cost complexity metric. As for the upper bound, instead, to favor the simplicity of exposition and intuition, we build on the Successive Elimination algorithm. Clearly, our proofs can straightforwardly incorporate the techniques from the
more refined analysis [e.g.. 23 to tighten the logarithmic dependencies.
Multiple Fidelity. The use of multiple fidelity has gathered particular attention from the Bayesian Optimization (BO) (5) field, with large variety of algorithms that operate under different assumptions and with different goals 15
33 34 28.. In particular, a recent line of works [22 19 has focused
on minimizing the simple regret suffered when certain budget has been spent optimize target function under smoothness conditions guaranteed by Gaussian processes 37 The study of the simple
regret has also been extended to black-box function optimization (3 40 under hierarchical
partition assumptions on the target function. However, all previous work differs significantly from the study we present in this paper. Indeed, they optimize different goals w.r.t. our novel cost complexity notion and make structured assumptions about the target function (i.e., the arm space). With most of them 2T 20 39
we share the assumption on the knowledge of the upper bound on the maximum bias& &m for each fidelity. Of particular interest w.r.t. our work, is the one of [11]. In particular, the authors highlighted the concept that what matters when exploiting fidelity m < M is how much they preserve the order rather than the bias they have. However, their assumption about order preservation is expressed in a general form; with the maximum bias variation Tm. instead, we
'The cost complexity bound is obtained under an assumption equivalent to Assumption in which all E's are replaced with y's.
8

---

Table 1: Cost complexity results (mean and 95% confidence interval of 100 runs).
Algorithm
Synthetic A
Synthetic B
Yahtzee
MFE
212.43 +: 3.89
3330.27 + 62.59
342.75 + 0.69
ISE
11.47 + 0.31
27.06 + 0.77
0.53 + 0.01
IISE-
2.53 = 0.06
6.39 0.17
0.001 + 0.01
propose a closed-form expression for this concept, and we quantitatively show its impact in terms of benefits with respect to the upper bound on the maximum bias. We also showed that upper bounds 4m on this metric are known and available in a large class of problems, and that our algorithm can successfully exploit this knowledge to reduce identification cost.
The work most closely related to ours is [1]. The authors consider the finite arm setting with known upper bounds on the maximum bias for each fidelity. However, while we take into account the identification cost, in [1], the authors analyze a pseudo-regrer notion that sets as optimal strategy the one that invests the whole budget in querying the optimal arm. Interestingly, we got similar results, in terms of structure, for what concerns the lower bound, although remark that the proof techniques are different since we deal with a different performance metric. As for the proposed algorithm and the upper bounds, our proofs rely on novel concepts such the fidelity convenience (i.e., Definition[] I which are tailored to the identification cost we have analyzed. In addition, as we have seen in Section we make a different assumption w.r.t. [2]]: our assumption directly states a relationship between costs and biases, which is more reasonable since the goal of the multi-fidelity setting is to trade-off between the two. Finally, w.r.t. 21 we analyze the effect of more fine-graines knowledge on different fidelity, which provably leads to performance improvements.
To conclude, some works 9 30 have also investigated the of multi- fidelity simulators in Reinforcement Learning (RL) algorithms (up a desired precision e both for the RL setting and for the bandit one. However, their setting is significantly different from ours as they do not consider each fidelity to be related to a given cost. Instead, they simply aim at minimizing the number of sub-optimal steps at fidelity M, while controlling the number of samples taken in fidelity m < M to ensure they are polynomial.
42 domains. Among these works, [9] develops fixed confidence
7 Numerical Validation
In this section, we provide a numerical validation of our theoretical claims in both synthetic and simulated domains. To prove that IISE is successful at exploiting fidelity, we compare it with: (i) Successive Elimination (SE) [00), which exploits only maximum fidelity, and with a version of IISE that chooses the thresholds an.. We call this modified version Maximum Fidelity Exploit (MFE) algorithm. Table I repprts all the results in terms of the percentage of cost complexity of given algorithm w.r.t. the one of Successive Elimination. The value 100 corresponds to the relative cost complexity of SE.
to exploit every fidelity as much as possible (i.c., O'm close 0).
Synthetic bandits. We start presenting some experiments and Synthetic B) with randomly generated arms. These experiments aim at validating our robustness results along with the benefit of the order-aware knowledge. Synthetic A setting parameters are K 2000, .M- 4, X = [1, 10, 100, 1000). ę = [1.15, 0.225, 0.015, 0J. 7 [0.3, 0.05, 0.001, 0]: for Syn- thetic B, instead, K = 1000, M 5, À = [16, 64, 256, 1024, 4096], E [1.15, 0.45, 0. 0.105, 0.0105, 0). = [0.3, 0.1, 0.01, 0.001, 0J. To make the and & settings directly comparable, we generated the arms such that the fidelity index m is left unchanged (i.e., it simultaneously holds that A > A > ... AM. E > E2 > ... > Ear, and ?1 > 722 > ... > 7As). Further details on this generation process can be found in Appendix(E) As we can appreciate from Table ! IISE substantially reduces the cost complexity w.r.t. SE, and, its order-aware version IISE-y, obtains further improvements. Table also highlights the importance of choosing a good threshold Omm- Indeed, MFE insists in exploiting given fidelity, even when there is no convenience in doing so, thus obtaining significantly worse results than SE.
synthetic bandits (Synthetic A
Yahtzee. We now apply our algorithm to the problem of choosing the first action in the stochastic planning domain introduced in Section T More specifically, we consider the Yahtzee game [. Yahtzee is sequential dice game in which a player rolls 5 dice up to 3 times and then chooses a particular move that assigns score to the final dice combination. For instance, typical moves are:

---

"Sixes" with score given by the sum of dice with the number 6, and "Yahtzee", that assigns 50 points if all the dice show the same number, and otherwise. The total number of these possible moves is 14 (i.e., our branching factor A). The game proceeds in 13 rounds. During each round I, the player selects a move and obtains the corresponding points. We consider the variant of Yathzee in which, if the player has already selected certain move at i < f. then, at f, that move will lead to reward O. Furthermore, during each round, the player will roll the dice only once, after which a move has to be selected. Further details are provided in Appendix E Table [sows that our method significantly reduces the total number of generated nodes, thus lowering successfully the total cost of identifying the best action, and, that exploiting the upper bounds on the maximum bias variation instead of 5 is beneficial in terms of total cost. Finally, MFE overexploits fidelity and underperforms SE.
8 Conclusions and Discussion
In this work, we have studied, for the first time, the variant of the fixed-confidence BAI scenario in which the agent has access to multiple approximations with different costs and biases of the original bandit model. We proposed the novel notion of cost complexity to evaluate the performance that a given algorithm obtains in these situations. We derived a lower bound on this index, which shows several interesting properties of the problem, along with its main challenges. We also presented novel algorithm, IISE, which provably reduces the cost complexity compared to algorithms that ignore the availability of multiple fidelity. More specifically, IIE discards sub-optimal arm i with the most convenient, in terms of cost and fidelity, thus closely mimicking the shape of the lower bound. Furthermore, we also showed that the maximum bias is not what actually matters in identifying the best arm. Indeed, better guarantees can be obtained with the knowledge of the maximum bias variation, an original concept that we introduce to encode how much a given fidelity preserves order.
To close the problem from theoretical perspective, it is reasonable to assume that both upper and lower bounds could be improved in settings that do not fall under Assumption [ More specifically, the lower bound of Theorem T that considers the minimum over the entire fidelity set, seems currently optimistic since it does not encode the cost that is needed to explore at other fidelities. To tackle this issue, proof techniques that rely on the characteristic time function [I3 might lead to tighter lower bounds. Consequently, adapting to the MF setting their well-known "Track and Stop" strategy [I3 might provide upper bounds that asymptotically match the lower bound in its characteristic time form. However, results obtainable from these approaches usually come at the cost of lower interpretability (and, depending on the nature of the resulting characteristic function, computational complexity). On the other hand, Theorem provides several intuitions behind the challenges of the Multi-Fidehhe BAI setting, and ISS is computationally efficient.
Furthermore, whenever Assumption [ does not hold, the cost of "exploring" lower fidelities becomes more and more relevant. Indeed, Assumption ! (i.e., fidelity differs in terms of the joint costs-biases relationship specified by the assumption). The main issue in settings, where this gap is small, roots down to the chicken-egg problem of MF-BAI. On one side, we would like to exploit these approximators to discard sub-optimal arms; on the other side, we do not know if these approximators will be useful (i.e., in the worst case, we pay an exploration cost). In the case, where the "fidelity-gap" is small, this problem is repeated over and over for all these fidelities close to one another (i.c., the cumulative sum of the exploration costs becomes negliigii,,.... In this sense, tighter lower bounds (such as the ones previously suggested) might shed light on whether such assumptions are necessary or not, or if tighter assumptions are possible/necessaryy This represents an exciting line for future research.
guarantees that there is large enough "fidelity gap"
To conclude, we note that previous studies [45] II highlighted the strong connections between fixed-confidence BAI and learning near-optimal RL policies while minimizing the number of samples gathered in the environment. In this sense, our ideas pave the way for future work that aims at learning these policies when multiple simulators are available. Indeed, previous efforts in MF-RL g 3,30 41 do not directly take the challenging cost cost-precision trade-off into account.
References
[1] Aymen Al Marjani and Alexandre Proutiere. Adaptive sampling for best policy identification in markov decision processes. In International Conference on Machine Learning, pages 7459-
10

---

7468. PMLR, 2021.
[2] Yves Audibert, Sébastien Bubeck, and Rémi Munos. Best arm identification in multi-armed bandits. In COLT, pages 41-53, Citeseer, 2010.
[3] Andrea Bonarini, Alessandro Lazaric, and Marcello Restelli. Yahtzee: a large stochastic environment for rl benchmarks. In NIPS 2005 Workshop on Reinforcement Learinn Benchmarks and Bake-off's II, pages 43 48, 2005.
[4] Stéphane Boucheron, Gábor Lugosi, and Olivier Bousquet. Concentration inequalities. In Summer school on machine learning, pages 108-240. Springer, 2003.
[5] Eric Brochu, Vlad M Cora, and Nando De Freitas. tutorial on bayesian optimization of expensive cost functions, with application to active user modeling and hierarchical reinforcement learning. arXiv preprint arXiv: 1012.250 2010.
[6] Sébastien Bubeck, Rémi Munos, and Gilles Stoltz. Pure exploration multi-armed bandits problems. In International conference on Algorithmic learning theory, pages 23-37. Springer, 2009.
[7] Lijie Chen and Jian Li. On the optimal sample complexity for best arm identification. arXiv preprint
2015.
[8] Lijie Chen, Jian Li, and Mingda Qiao. Towards instance optimal bounds for best arm identifica- tion. In Conference on Learning Theory, pages 535-592. PMLR, 2017.
(9] Mark Cutler, Thomas J Walsh, and Jonathan P How. Reinforcement learning with multi-fidelity simulators. In 2014 IEEE International Conference on Robotics and Automation (ICRA), pages 3888-3895. IEEE, 2014.
[10] Eyal Even-Dar, Shie Mannor, and Yishay Mansour. Pac bounds for multi-armed bandit and markov decision processes. International Conference on Computational Learning Theory, pages 255-270 Springer, 2002.
[11] Côme Fiegel, Victor Gabillon, and Michal Valko. Adaptive multi-fidelity optimization with fast learning rates. In International Conference on Artificial Intelligence and Statistics, pages 3492-3502. PMLR, 2020.
[12] Victor Gabillon, Mohammad Ghavamzadeh, and Alessandro Lazaric. Best arm identification: unified approach fixed budget and fixed confidence. Advances in Neural Information Processing Systems, 25, 2012.
[13] Aurélien Garivier and Emilie Kaufmann. Optimal best arm identification with fixed confidence. In Conference on Learning Theory, pages 998-1027. PMLR, 2016.
[14] Steven R Howard and Aaditya Ramdas. Sequential estimation of quantiles with applications to a/b testing and best-arm identification. Bernoulli, 2803):1704-1728 2022.
[15] Deng Huang, Theodore T Allen, William I Notz, and R Allen Miller. Sequential kriging optimization using multiple-fideliyy evaluations. Structural and Multidisciplinary Optimization, (15))369-382, 2006.
[16] Kevin Jamieson, Matthew Malloy, Robert Nowak, and Sébastien Bubeck. lil' fil'ueb: An optimal exploration algorithm for multi-armed bandits. In Conference on Learning Theory, pages 423-439. PMLR, 2014.
[17] Kevin Jamieson and Robert Nowak. Best-arm identification algorithms for aumti-armed bandits in the fixed confidence setting. In 2014 48th Annual Conference on Information Sciences and Systems (CISS), pages 1-6. IEEE, 2014.
[18] Anders Jonsson, Emilie Kaufmann, Pierre Ménard, Omar Darwiche Domingues, Edouard Leurent, and Michal Valko. Planning in markov decision processes with gap-dependent sample complexity. Advances in Neural Information Processing Systems, 33:1253-1263 2020.
11

---

[19] Kirthevasan Kandasamy, Gautam Dasarathy, Junier Oliva, Jeff Schneider, and Barnabas Poczos. Multi-fidellff gaussian process bandit optimisation. Journal of Artificial Intelligence Research, 66:151-196, 2019.
[20] Kirthevasan Kandasamy, Gautam Dasarathy, Junier B Oliva, Jeff Schneider, and Barnabás Póczos. Gaussian process bandit optimisation with multi-fidelii evaluations. Advances in neural information processing systems, 29, 2016.
[21] Kirthevasan Kandasamy, Gautam Dasarathy, Barnabas Poczos, and Jeff Schneider. The multi- fidelity multi-armed bandit. Advances in neural information processing systems, 29, 2016.
[22] Kirthevasan Kandasamy, Gautam Dasarathy, Jeff Schneider, and Barnabás Póczos. Multi-fideii bayesian optimisation with continuous approximations. In International Conference on Machine Learning, pages 1808. PMLR, 2017.
[23] Zohar Karnin, Tomer Koren, and Oren Somekh. Almost optimal exploration in multi-armed bandits. In International Conference on Machine Learning, pages 1238-1246. PMLR, 2013.
[24] Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier. On the complexity of best-arm identification in multi-armed bandit models. The Journal of Machine Learning Research, 17(1):1-42, 2016.
[25] Pushmeet Kohli, Mahyar Salek, and Greg Stoddard. A fast bandit algorithm for recommenda- tion to users with heterogenous tastes. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 27, pages 1135-1141, 2013.
[26] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[27] Lisha Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadeh, and Ameet Talwalkar. Hyper- band: A novel sandit-based approach to hyperparameter optimization. The Journal of Machine Learning Research, 18(1):6765-688 2017.
(28) Shibo Li, Wei Xing, Robert Kirby, and Shandian Zhe. Multi-fidelity bayesian optimization via deep neural networks. Advances in Neural Information Processing Systems, 33:8521-8531, 2020.
[29] Shie Mannor and John Tsitsiklis. The sample complexity of exploration the multi-armed bandit problem. Journal of Machine Learning Research, 5(Jun):623664,, 2004.
[30] Alonso Marco, Felix Berkenkamp, Philipp Hennig, Angela P Schoellig, Andreas Krause, Stefan Schaal, and Sebastian Trimpe. Virtual vs. real: Trading off simulations and physical experiments in reinforcement learning with bayesian optimization. In 2017 IEEE International Conference on Robotics and Automation (ICRA), pages 1557-1563. IEEE, 2017.
[31] Arturo Molina-Cristóbal, Patrick R Palmer, Benjamin A Skinner, and Geoffrey T Parks. Multi- fidelity simulation modelling in optimization of a submarine propulsion system. In 2010 IEEE Vehicle Power and Propulsion Conference, pages 1-6. IEEE, 2010.
[32] Quan Nguyen, Arghavan Modiri, and Roman Garnet.. Nonmyopic multifidelity acitve search. In International Conference on Machine Learning, pages 8109-81 8118. PMLR, 2021.
[33] Victor Picheny, David Ginsbourger, Yann Richet, and Gregory Caplin. Quantile-based opti- mization of noisy computer experiments with tunable precision. Technometrics, 55(1):2-13, 2013.
[34] Matthias Poloczek, Jialei Wang, and Peter Frazier. Multi-information source optimization. Advances in neural information processing systems, 30, 2017.
[35] Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
[36] Dev Rajnarayan, Alex Haas, and Ilan Kroo. A multifidelity gradient-free optimization method and application to aerodynamic design. 12th AIAA/ISŠMO multidisciplinary analysis and optimization conference, page 6020, 2008
12

---

[37] Carl Edward Rasmussen. Gaussian processes in machine learning. In Summer school on machine learning. pages 63-71. Springer, 2003.
[38] Herbert Robbins. Some aspects of the sequential design of experiments. Bulletin the American Mathematical Society, 58(5):527-553 1952.
[39] Rajat Sen, Kirthevasan Kandasamy, and Sanjay Shakkottai. Multi-fidelity black-box opti- mization with hierarchical partitions. In International conference on machine learning, pages 4538 4547. PMLR, 2018.
[40] Rajat Sen, Kirthevasan Kandasamy, and Sanjay Shakkottai. Noisy blackbox optimization using multi-fidelity queries: A tree search approach. The 22nd international conference on artificial intelligence and statistics, pages 2096-2105. PMLR, 2019.
[41] Varun Suryan, Nahush Gondhalekar, and Pratap Tokekar. Multifidelity reinforcement learning with gaussian processes: model-based and model-free algorithms. IEEE Robolics & Automation Magazine, 27(2):117-128, 2020.
[42] Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
[43] Brijen Thananjeyan, Kirthevasan Kandasamy, Ion Stoica, Michael Jordan, Ken Goldberg, and Joseph Gonzalez. Resource allocation in multi-armed bandit exploration: Overcoming sublinear scaling with adaptive parallelism. In International Conference on Machine Learning, pages 00236-10244 PMLR, 2021.
[44] Felipe AC Viana, Valder Steffen, Sergio Butkewitsch, and Marcus de Freitas Leal. Optimiza- tion of aircraft structural components by using nature-inspinee algorithms and multi-fidelity approximations. Journal of Global Optimization, 45(3):427-44 2009.
[45] Andrea Zanette, Mykel J Kochenderfer, and Emma Brunskill. Almost dorizon-free structure- aware best policy identification with a generative model. Advances in Neural Information Processing Systems, 32, 2019.
[46] Chicheng Zhang and Kamalika Chaudhuri. Active learning from weak and strong labelers. Advances in Neural Information Processing Systems, 28, 2015.
[47] Yuan Zhou, Xi Chen, and Jian Li. Optimal pac multiple arm identification with applications to crowdsourcing. In International Conference Machine Learning, pages 217-225. PMLR, 2014.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] See for instance the contributions subsection. It list, one by one, the content of each of the section of the paper.
(b) Did you describe the limitations of your work? [Yes] See Section 4
(c) Did you discuss any potential negative societal impacts of your work? [No] Did not
find any.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] We stated formally all the theoretical results throughout the main text (i.c., Theorem I Theorem Theorem Proposition T. We highlighted the set of assumptions in each claim. For extensions (e.g. Equation 99 we provide formal statements in the Appendix, but set of assumptions has been specified also in the main text.
(b) Did you include complete proofs of all theoretical results? [Yes] We provide a detailed appendix with complete proofs of all theoretical results.
13

---

3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material
URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] Experiments are detailed in Section and further documented in Appendix
[ Further details can be found within the codebase.
(c) Did you report error bars (c.g., with respect to the random seed after running exper- iments multiple times)? [Yes] As specified in Section 7 we report mean and 95% confidence intervals using 100 runs.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] Yes, see Appendix E
4. If you using existing assets (e.g., code, data, models) curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "YKQ7-4U0BcR", "reviewer": "Reviewer_LAgF", "summary": "The authors tackle establishing the best arm in a multi-arm bandit problem, where each arm can be pulled with a different “fidelity”.  Lower fidelity evaluations are cheaper to evaluate, but provide a more biased estimate of the objective function.  They present and analyse a new algorithm, IISE, that theoretically outperforms basic bandit algorithms that do no exploit the multi fidelity structure of the problem.  They then numerically confirm this on two experiments.  \n", "questions": "I raised several questions in my main review.\n", "limitations": "There are no ethical considerations.\n\nI raised several comments on the limitations of the work above, including the limitations of the setting, the approach taken, the presentation and the empirical validation.  \n", "rating": 3, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "====== I posted this in a comment after my review, but it isn't visible to the authors for some reason.  Sorry for the confusion.\n\n## Slight revision.\n\nI have thought about this paper and my review a little more since initially writing it.  I figure I'd say this in the discussion phase anyway so I might as well put it here so the authors can respond in their rebuttal.  \n\nMy stance on the paper has relaxed a little bit.  While I still broadly stand by my concerns, I think if the authors can allay them, then I would endorse this paper.  \n\nSpecifically:\n- I believe the paper could benefit from simplification of the exposition, maybe even cutting some material to the supplement.  I would consider adding an executive summary of the method, banner figure, algorithm/pseudo-code block*, flow chart etc.  Right now it is an impenetrable wall of math.\n- The fixed subgaussian noise ($\\sigma^2$) still troubles me.  I think this is my main technical reservation.  \n- The empirical validation is very weak.  Right now the paper is hinging on the significance of the theoretical and methodological contribution, as it hasn't, in my opinion, been shown empirically _beyond doubt_ to be better than the alternatives.  \n\nThanks, LAgF\n\n*I know you have an algorithm block in there, but it is still quite low-level.  I'd like to see a higher-level / word-based / pseudocode version of this.\n\n\n\n========= Original Review:\n\n\nI will preface my review with the statement that I am not an expert on bandits, or on multi fidelity methods.  That said, the paper is well written enough on a high level that I get the general point.\n\nThere is a huge amount of theoretical work that has gone into this paper, and for that, the authors are to be commended.  I think there is definitely an audience at NeurIPS that will get a lot from reading this paper and the accompanying materials (I only skimmed the results presented in the supplement).  \n\nThat said, I am not currently endorsing the publication of this paper, as I have some fairly substantial questions.  If the authors can allay my concerns and make some (again, fairly substantial) updates to the paper, then I would be willing to endorse it. \n\nI query some of the modelling choices made (1).  I also struggle with some elements of the presentation (2), and the empirical validation (3) .  I will try and break my criticism down a bit.\n\n# Major Comments:\n\n### 1.  Fixed subgaussian noise.\nYou assume a fixed variance for the subgaussian noise across all arms.  This seems like a pretty fundamental limitation to me.  I often think about mutlifidelity in terms of how many iterations / MC samples I allow my simulator/solver to take.  Therefore, lower fidelity simulators have a much higher variance on their evaluation than higher fidelity simulators.  Alternatively, lower-fidelity simulators may have lower variance because they are too simple to capture the full variability.  Finally, in the MDP example you give, longer windows have a higher variance, and therefore this doesn’t apply.  As the variable evaluation noise operating regime is not catered for in your work, it therefore excludes a large set of practical application domains where your theoretical guarantees don’t hold.  I invite the authors to comment on this.\n\n\n### 2.  I really struggle with the presentation of the material.  \nI understand that bandits and MF methods are individually quite notationally dense and difficult to get down on paper; and that a bandit + MF method is probably that difficulty squared.  However, the authors must do better (in my opinion) to strip out all the complexity and present the ideas as simply and as notationally clear as possible.  \n\n- This paper may benefit greatly from a banner diagram to try and visually present the ideas, and at least unload some of the burden of explaining everything from the text.  \n\n- For instance, the aside on MDPs and Prop 1 doesn’t seem to be used.  This should be cut from the main text and placed entirely in the supplement to clear space and reduce the amount of technical content.\n  \n- A table of notation in the supplement would be very helpful as well.\n \n- Really try to keep subscripts, superscripts, diacritics to a minimum. \n\n\n### 3.  Weak empirical validation\nThere is obviously a sizeable theoretical contribution in this paper, however, the empirical validation is lacking in my opinion.  A toy synthetic problem and a single other problem tested against a single baseline doesn’t really convince me that your method works and is superior.  Obviously this isn’t required for publication, but, I do not consider this method to have been empirically validated.  To convince me of this, I would want to see a few more baselines evaluated on a range of more standard problems on which existing methods have been tested.  I have little-to-no idea if “X” is a good score on “synthetic toy problem 2”, whether synthetic toy problem 2 is a fair baseline on which to apply MFE etc.  I imagine there is a wealth of domains you can leverage to get a good example – image classification with different length glimpse sequences [Harvey, Teng, Wood, 2019], maybe train different stochastic classifiers with different sizes, number of latent samples, numbers of particles etc.  Maybe we just actually use the MDP / RL examples?  I really think this paper would be strengthened by using a domain that many readers will “understand.”  There is also a chronic shortage of implementation and experimental details in the main text and the supplement.  I do note however that code was released. \n\n\n# Minor Comments.\nNone, actually.\n\n\n# Very Minor / Typographical Comments.\ni. Theorem 3:  “upper bounder” -> “upper bounded.\n\nii.  Throughout:  (I.e. in Theorem 3)  Inconsistent use of “Equation \\\\eqref\\{\\}”, “\\\\eqref\\{\\}”, “Equation \\\\ref\\{\\}” and just “\\\\ref\\{\\}”.\n\niii.   Line 232:  “w.r.t” -> “w.r.t.”.\n\niv.  Line 243: “0” -> “zero”  (numbers less than 13 are typically written out).\n\nv.  Try to avoid footnotes.  They are bad for readability.  If they are important then they should be integrated into the main text, otherwise, they should be removed. \n\nvi.  Line 454:  Matyas shouldn’t be “et al.”.  Also inconsistent use of just first initial.  \n\n\n# Summary.\nAs outlined above, I think this paper has some serious limitations and weaknesses as it is currently presented.  I think there is a good conference paper in there somewhere, but I do not believe it is currently at that point.  There could even be a better, more impactful, and more widely distributed conference paper if published at a more specialised venue, if you are unfortunately rejected in this review cycle.  Good luck.  \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "GNi5MeMYaVf", "reviewer": "Reviewer_jriY", "summary": "The paper studies multi-fidelity best arm identification (BAI). Here, we have a bandit model\nwith M different fidelities. On each round, a decision-maker should choose which arm to\npull and which fidelity to pull the arm at. It's goal is to identify the best arm (the arm\nwith the largest mean at the highest fidelity), but can pull the arms at lower fidelities\nto obtain cheaper approximations at lower cost. The authors assume that the lower\nfidelities may be biased from the highest fidelity, but these biases are bounded by some known\nquantity.\nThey first prove a lower bound for this problem and describe a racing-style algorithm\nwhich achieves this lower bound under certain assumptions on the biases and costs.\n\n\nMulti-fidelity bandits are well-studied in the regret minimization setting under the same\nmodel considered by the authors\nHowever, I am not\naware of papers which have studied multi-fidelity BAI. It is a very natural formalism with\nuseful applications.\nWhile the paper falls short of solving this problem completely, I think the authors have\nmade meaningful advances.\nHence, I believe it would be a nice addition to the proceedings.", "questions": "See above", "limitations": "See above", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The lower bound given in the paper is quantifiably better than the lower bound for regular\nBAI. However, I am not sure if it is tight enough. In particular, taking the minimum on\neach term in the summation seems a bit too optimistic as it doesn't account for the\nexploration cost at other fidelities. \n\nRelated to the above: Assumption 1 seems to only consider problems where there is large\nseparation between fidelities (i.e. the costs increase sharply between a lower fidelity to\na higher while the gaps decrease sharply). This rules out many challenging problems where\nthe fidelities might be similar (i.e. similar costs/gaps); here, you might still expect a\nsmart enough policy to use that information or quickly ignore that information and move to\nhigher fidelities.\n\nIt might be useful to discuss the above issues to elucidate on the gap between the lower\nand upper bounds. My hunch is that they will both need to be tightened outside of\nAssumption 1.\n\nOther comments:\nFootnote 1 is very unclear, what does it mean for costs and fidelity to hold with\nequality and what does it mean for it to be discarded. You need to be more clear and\nprecise about what is meant here.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "4VocqR7loM4", "reviewer": "Reviewer_K1jV", "summary": "This work studies the multi-fidelity variant of the best-arm-identification problem. It first proposes a new performance measure called cost complexity, then gives a lower bound for the cost complexity of this problem. To solve this problem, this work offers an algorithm called Iterative Imprecise Successive Elimination (IISE), along with the cost complexity upper bound analysis. Then this work gives a better result when the algorithm has access to some more fine-grained knowledge of the multi-fidelity setting. Finally, empirical studies validate the effectiveness of the proposed method.", "questions": "Typos:\n1. Line 179: convenient provably convenient -> provably convenient", "limitations": "Not much.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. This work gives a solution to this novel problem along with the corresponding upper bound, which also closely mimics the behavior of the lower bound.\n2. The overall paper is well-written and quite readable, especially some discussions about the intuition behind certain conclusions.\n\nWeakness:\nNot much.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "3dBmKID8jX", "reviewer": "Reviewer_9j2c", "summary": "This paper presents a new algorithm and analysis for multi-fidelity\nbest-arm identification.  It builds on the ideas of previous\nalgorithms that do successive elimination of arms until only one is\nleft.  A unique aspect is their joint consideration of the costs and\naccuracies of each fidelity level.  They demonstrate their method\nempirically on a couple toy/synthetic problems.\n", "questions": "none", "limitations": "none", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well written and covers the prior work well.  My only\nconcern is that the contributions are relatively incremental given the\nlarge amount of prior work on best arm identification, and\nmulti-fidelity methods.\n\nThe idea of using multi-fidelity best arm identification as a planning algorithm is interesting.  Perhaps that needs to be left for another paper but it would be interesting to explore it more and see how it compares to SOTA planning algorithms.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept