Optimal Multi-Fidelity Best-Arm Identification
Authors: Riccardo Poiani
Rémy Degenne
Emilie Kaufmann
Alberto Maria Metelli
Marcello Restelli
Venue: NeurIPS 2024 poster (2024)
Keywords: Multi-Fidelity
Best-Arm Identification
Fixed Confidence
Primary area: bandits

Abstract: In bandit best-arm identification, an algorithm is tasked with finding the arm with highest mean reward with a specified accuracy as fast as possible. We study multi-fidelity best-arm identification, in which the algorithm can choose to sample an arm at a lower fidelity (less accurate mean estimate) for a lower cost. Several methods have been proposed for tackling this problem, but their optimality remain elusive, notably due to loose lower bounds on the total cost needed to identify the best arm. Our first contribution is a tight, instance-dependent lower bound on the cost complexity. The study of the optimization problem featured in the lower bound provides new insights to devise computationally efficient algorithms, and leads us to propose a gradient-based approach with asymptotically optimal cost complexity. We demonstrate the benefits of the new algorithm compared to existing methods in experiments. Our theoretical and empirical findings also shed light on an intriguing concept of optimal fidelity for each arm.

Optimal Multi-Fidelity Best-Arm Identification
Riccardo Poiani"
DEIB, Politecnico di Milano, Milan, Italy ric riccardo, poiani@@oling @ppllmi......... i
Rémy Degenne
Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189-CRISAAL, F-59000 Lille, France remy degenne@inria.ff
Emilie Kaufmann
Univ. Lille, CNRS, Inria, Centrale Lille, UMR 9189-CRISIAL, F-59000 Lille, France mmilie.ne kaufmanm@mii--ille..... fr
Alberto Maria Metelli
Marcello Restelli
DEIB, Politecnico di Milano, Milan, Italy al bbberttmrria.mmtellllggee.
DEIB, Politecnico di Milano, Milan, Italy marcello. restorll@eeellleeeeee
Abstract
In bandit best-arm identification, algorithm is tasked with finding the arm with highest mean reward with specified accuracy as fast as possible. We study multi- fidelity best-arm identification, in which the algorithm can choose sample at a lower fidelity (less accurate mean estimate) for a lower cost. Several methods have been proposed for tackling this problem, but their optimality remain elusive, notably due to loose lower bounds on the total cost needed to identify the best arm. Our first contribution is a tight, instance-deps ddeenndee lower bound on the cost complexity. The study of the optimization problem featured in the lower bound provides new insights to devise computationally efficient algorithms, and leads to propose mradient-based approach with asymptotically optimal cost complexity. We demonstrate the benefits of the new algorithm compared to existing methods experiments. Our theoretical and empirical findings also shed light on an intriguing concept of optimal fidelity for each arm.
Introduction
In multi-armi bandits 20). an algorithm chooses each step one arm among possibilities. It then observes a reward, sampled from a probability distribution on R corresponding to the arm. Several goals are possible for the algorithm, and we focus on the best arm identification task (BAI) in which we aim to identify the arm with the largest mean, using as few samples as possible, This
a well-studied problem [6] I 12
10 g with potential applications to, e.g. A/B/n testing [27 or
optimization 11.
In some applications, like physics, parameter studies, hyper-parameter optimization, getting sample from the arm distribution might be expensive since it requires evaluating or training complex model and is computationally demanding. However, often the case that cheaper, less accurate sampling methods are available, for instance, by using a coarser model in the physics study example.
Work done while at Inria, Lille, France.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

The multi-fidelit bandit framework takes such scenarios into account. When choosing an arm, the algorithm also chooses fidelity, with a trade-off: a higher fidelity gives a more precise observation but has higher cost. We assume that the algorithm knows both the cost and the maximal bias of the observations from each fidelity. This also how the knowledge about the fidelity was modeled in prior work [see, e.g., 16 15 25 BT. The goal is then to find the best arm (i.e., the arm with the highest mean at the highest fidelity) with high probability and minimal cost.
Specifically, the bandit algorithm interacts with the multi-fidelity environment and gathers information to find which arm has the highest mean when pulled at the highest fidelity. In the fixed confidence setting, we want to ensure that the algorithm returns correct answer with probably at least 1 - 8 for a given parameter å (0. 1). good algorithm should do that a minimum cost, and thus, the appropriate quality metric for evaluating an algorithm's 's performance is the sum of costs paid until it stops, i.e., the cost complexity. Previous work on the multi-fidelity BAI problem 225 31 provided lower bounds on the cost complexity as well as algorithms with cost upper bounds. Those lower and upper bounds do not match, and the proposed methods require additional prior information [1], or their guarantees are restricted to problems satisfying additional hypotheses [25]. We lift all those requirements and provide an improved lower bound and an algorithm with a matching upper bound.
Contributions and organization of the paper After presenting additional related works, in Sec- [ion[] we define fixe-coofidencc best arm identification in fideiifi bandits in more mathe- matical detail and introduce the notations used throughout the paper. Then, Section contains our first contribution: a tight instance-dependee expressed with the maximum of complex function over all possible cost allocations. We also highlight features of that lower bound, like the existence of an optimal fidelity for each arm, which should be chosen exclusively. In Section 4 we propose computationally efficient procedure for computing gradients of the function featured in the lower bound and describe a gradient-basee algorithm whose cost complexity is asymptotically matching the lower bound. Finally, in Section S we present the results of numerical experiments which demonstrate the good empirical performance of our new algorithm compared to prior work.
lower bound on the cost complexity of any algorithm
Additional related works The multi- multi-fidelity setting has mostly been studied in the context of
14, 21] and black-box function optimization with different 23 The goal there is to find the minimum of function by successive queries of that function or of cheaper approximations. The metric for success in these works is most often the simple regret, that is, the difference between the best value found and the true minimum, although other goals were considered like the cumulative regret [16 15] Furthermore, we notice that best arm identification with costs has recently been studied in 13 for BAI with only one fidelity. The authors introduce variant of the Track-and-Ste Stop algorithm 8 and prove its asymptotic optimality. However, we will not be able to adapt this study to the multi-fidelity case because, as we shall see, it requires solving complex optimization problem for which we have efficient solution. Finally, our work is related to the vast strand of BAI studies that proposes tight lower bound with asymptotically optimal algorithms [e.g.. N. 4 22 nevertheless, we discuss throughout the text, these studies cannot be directly applied to the multi- molti-fidelity BAI problem.
Bayesian optimization [9] 24
17
26
structural assumptions 28
29
Background
In this section, we provide essential background and notation that is used throughout the rest of the paper. A table that summarizes the notation is available in Appendix A
A multi-fidelit fidelity bandit model with K arms and M fidelities is a set of K x M probability distributions
(Va. ) [m([)) where Pa,m has mean of pa.m- For each arm a [K], Ha,m represents the mean value of observation of arm a using fidelity m, and let μa ((o.m ( [M]]] An observation at fidelity m is assigned a (known) cost Am 2 0 with A < A2 < ... < AM. The goal is to identify the arm that has the largest mean at the highest fidelity M, a. (14 == argmax Mo, M (sometimes denoted by in the sequel to ease notation) with a small total sampling cost, by exploring the arms at different fidelities and using some prior knowledge about their precision. Specifically, we [K].
assume that there are some (known) values E > E2 > EM O such that, for all arm the vector Pa == (H ) satisfies
Vm [M],
|Mam - Ma.Ml S Em
2

---

We write Ha E MF to indicate that arm a satisfies these fadtii-fidelity constraints, with these particular parameters Em (although they are not shown in the notation). In this paper, we consider arns that belong to canonical exponential family 2 This includes, e.g. arms that have Bernoulli distributions or Gaussian distributions with known variances. Such models are known to be characterized by their means and we refer to such an exponential multi-fidelity bandit model D using the means of its arms n,, which belongs to the set MMF == {u E @KxM Va [K], Pa MF). where θ C IR is the interval of possible means.
..... the agent selects an arm A, and a fidelity M, observes a sample X₁ ~ M, and pays a cost AM,- Letting Fi o(A1. M1.X1, Xi...., Ar, Mr, X,) be the sigma field generated by the observations up to time fixed-confidence identification algorithm takes as input risk parameter å E (0, 1) and is defined by the following ingredients: (i) a sampling rule ( (Ae, M,), where (A,, M.) is Ft-1 -measurbaee,,le, (ii) a stopping rule Ts. which is a stopping time w.r.t. Fr, and (iii) decision rule âr, E [K) which is Fr, -measurrabl... We want to build strategies that ensure Pp (āz, # aax(1)) I 8 for all μ E .Mar with a unique optimal arm, Such strategy called d-correct. Among d-correct strategies, we are looking for strategies that minimize the expected identification cost (i.e., cost complexity) defined as
At each interaction round
EplcT1 = Σ
E aE[K] ME[M]
Am Eyla,
Σ EalCa,m(Ts)) aE|K] me[ad]
E
where (t) denotes the number of pulls of arm at fidelity up to time and Ca.m (t)= Am (t) denotes the cost associated to these pulls. In the sequel, we will provide cost complexity guarantees for multi-fidelity instances fe that belong to the set MMP of multi-fidelity instances with a unique optimal arm, i.e., for which (a, (14) = 1. We remark that for M = 1 and Am = 1 we recover the best arm identification problem in classical bandit model, for which the cost complexity coincides with the sample complexity, [T(]
Additional notation Given integer n N, we denote by A. the n-dimensional simplex. Furthermore, given v. y E (0, 1), we define kl(x, y) = x log(x/v) + (1 - x) log((1 x)/(1 v)). Given (p.q) E O², we denote by d(p, q) the Kullback-Leibler (KL) divergence between the distribution in the exponential family with mean and that with mean q. We also write d (x, = distribution with mean
d(ær, y)1 {ar 2 y) and dt (zr, d(x,y) {s S y). Finally, we denote by vp) the variance of the
3 On the cost complexity of multi-fidelity best-arm identification
In this section, we discuss the statistical complexity of identifying the best-arm MF-BAI problems. Formal proofs of the claims of this section are presented in Appendix B
3.1 Lower bound on the cost complexity
We present an instance-dependent lower bound on the expected cost-complexity. The lower bound uses the solution to an optimization problem, where the functions optimized quantify the trade-off between the information gained by pulling an arm at some fidelity and the cost of that fidelity. Since those functions also appear in our algorithm, we will now introduce notation for them. For all w E Λ and μ E OKxM. M. we define
d(pa.ms 0a,m)
Res(w, p1) = inf
Σ
Σ
Wa.m
e O.EMF, EM aE(i.j mE(M) 20,
Am
F(w, 14) = max min (w. 14) SE]K]
(2)
The quantity [w, (1) is the dissimilarity according to a KL. weighted by the costs between μa and the closest 0 E OKx such that arms and j /satisyy the multi-fidelity constraints and 6g μu for & (i.j), with arm j better than arm If fa E MMF then that closest 0 is also AMF but otherwise it might not be the case: if an arm A $ [i.j] is not in MF for μ., then it is equally not in MF for O. For μa E MMF the maximum in the definition of realized at the best arm *, as minaze Ji,o (u, μ1)
is zero for i o *. That is, F(w, 14) minjæ4 fagg (w, 1)). We define F' with maximum over and
3

---

not with that last expression because we want to define it for all points in OKMM, even the points which are not MMF. For those points, we could imagine different notions of best arm, for example, arg max; M,.M, but the right one for our algorithm is the arm for which we have the most evidence (weighted by cost) to say that all other arms are not better. That arm is the argmax in our definition of F. Given these definitions, we now introduce our new lower bound.
Theorem 3.1. Let 8 E (0, 1). For any ô-correct strategy, and any multi-fidelityy bandit model c E M holds that:
En[crs] 2 (* log (218),
(3)
where C* (p)- -SUPPAAKKS P(w, (1) = SUPWEARхM millagss (aw pt).
The quantity (1) describes the statistical complexity of an MF problem μ the typical max-min game that appears in lower bounds for BAI problems (see, e.g., 8 3. Specifically, first, the max-player chooses vector E AKXM M,, and then the min-player chooses bandit model I E MMM in which the optimal arm is different, with the goal of minimizing the function F(w, 14). Following the methods
from previous work, the objective value for and 0 should be EmE[k] Emerar] Wa.m dipu 8s... Am
featuring a sum over all arms and fidelities. However in the definition of fi, (w, we restrict e to be different from 14 on only two arms. We can prove that if f E MMMP, this gives the same objective value at the minimizing 0 as the full sum. The difference will be important in our algorithm, which will compute that minimizer for points ji that do not belong to MMM..
difference with standard BAI settings is that in Equation 4 each w AK M should be interpreted as vector of cost proportions that the max- max-player is investing (in expectation) in each arm- arm-fidelity pair to identify the optimal arm He, We can interpret the oracle weights w argmax x Ar F(W,, n)) as the optimal cost proportions that the agent should follow in order to identify pr,M while minimizing the identification cost. To clarify the difference and the relationship between cost and pull proportions notice that, given a cost proportion w, it is always possible to compute the pull proportions T (w) E AKx that the agent should play in order to incur the costs proportions specified by w. and vice versa. More specifically, these relationships are described for each urm-fidelity pair by the following equations for every a E [K] and m E [M]]
Ta.m (m)((w) Wa.m
1
Am Fa.m
Wamm (T) = ΣiE[K] EjE(an AymTe
(4)
Am LiE(K] ΣJE(M)
Wid X
As direct consequence, it is possible to rewrite C* (M)- as function of æ, the pull proportions. Doing so reveals that the minimizer in fagj does not depend on the costs: is also the minimizer of >n (i.jj).m[[M Tamd 0a,m). While the agent optimizes the cost proportions to get the best possible information/cost ratio, the min min-player minimizes only the information available to the algorithm to tell μ and apart. Finally, we notice that F(w,, 11) is concave in w 3 but ((W((T), ), 14) is not concave in π. As we shall see in Section 4 this difference will play crucial role in constructing an asymptotically optimal algorithm.
The formulation of the lower bound as game where one player maximizes an information/cost ratio while the other player minimizes information makes our result close to lower bounds for regret minimization like the one of [5), where the (unknown) gap of an arm plays the role of the cost.
Comparison to previous work The only known lower bound for the multi-fidelity BAI problem is the one presented in (25]. That same bound was then shown in (3I. The bound from those previous works is looser than Theorem 3.T For example, in a two-arms bandit with a single fidelity (denoted by M) and Gaussian rewards with variance 1, the bound from previous work is AM (2.2x) ) log((1 (122466) while our lower bound is 8A (MI.M (2.M) log (1..466). Furthermore, on particular instances with 2 arms and 2 fidelity, we can prove that our lower bound improves by a factor AM/ AA, which can be arbitrarily large (See Appendix B.2)). More generally, the proof of the previous lower bounds exhibits particular point in the alternative, which makes it always looser than our bound which features an infimum over all points. Theorem [s also optimal in the regime& 5 0 since it is matched by the algorithm we introduce in the next section.
This claim is evident when looking at the proof Theorem 3.1
This is consequence of the fact F(w,, 11) is infimum over linear functions of w.

---

3.2 Sparsity of the oracle weights: a tight concept of optimal fidelity
We conclude our study of the lower bound by further analyzing the optimal allocation w". Unlike in the standard best arm identification problem, we did not find an efficient algorithm to compute it, which prevents us from using a Track-and- -nn-s-----tt approach [8] Nevertheless, we will explain in the next section how to efficiently compute the ft, functions and their gradient. These computations are crucial for our algorithm but also allow us to prove our next result about the possible sparsity of [K] it is not difficult to show that there must exist some fidelity [M] for which w > 0 (Lemmal B.2h. However, as the following result highlights, in most cases, only one fidelity per arm has non-zero weight.
w", For each arm
Theorem 3.2. Let A (11) == argmaxwEAKwи F(w,, (1) and
MMF = E MMP: Di [K], [K), m2 E "M] E AkxM(() : wh,m 0, 0, 0}.
The set MMF a subset of RK whose Lebesgue measure is zero.
Theorem 3.2 implies that in almost all multi-fidelity bandits, for any w E RxAM (14) and each arm E KT. there exists a single fidelity m E [M] for which wa, > 0 holds. However, we
note that this result does not offer an easy way compute these optimal arm-dependent fidelities Nevertheless, as we shall see in the next section, our algorithm does not actually require identifying these optimal fidelity levels to enjoy optimality guarantees.
Finally, we remark that existing MF-BAI works [15] already proposed notions of optimal, arm- dependent fidelity that the agent should employ identify the optimal arm Nevertheless, as we verify in Appendix [.5] these concepts do not comply with the concept of optimal fidelity that arises from the tight lower bound of Theorem 3.1 In other words, there exist bandit models f in which following these alternative concepts of optimal fidelity leads to sub- aub-optimal performance.
4 The multi-fidelity sub-gradient ascent algorithm
We present our solution for solving MF-BAI problems, an algorithm called Multi-Fidelity Sub-
Gradient Ascent (MF-GRAD). Its pseudocode be found in Algorithm T All proofs for this
section are presented in Appendix [
A reader familiar with the literature on BAI algorithms inspired from lower bounds like Theorem 3.] may have the natural idea of simply using the Track-and-Stop algorithm [8] or the related game-based algorithm of 4. Those algorithms can't be directly applied here, first because of the costs: we want to bound the cost complexity, not the stopping time, and adapting those methods to costs is not trivial. Furthermore, computation of the optimal cost proportions at (t).). which is a max- min problem for which we don't 't have an efficient algorithm. Our solution is inspired by the gradient ascent algorithm of 22 which requires computing gradients of F (hence only a minimization problem and not a max-min). The same innovations required to extend this method to the multi-iidelity case could likely allow to adapt the algorithm of [4) or the exploration part of the regret-minimizing algorithm of [5]
and-Stop (even in the cost-aware variant of [33 would require the
Let us introduce some auxiliary notation. Let w E AKxM M be the uniform vector (KM...... KM For all t N. we define Clip, (x) (min(Za.m- GVT)) ae[K]]]]]]]) [e[K],me[M]] for an arbitrary constant G O. We also define a; 7 and Y 4 Finally, for all I N, we denote by C(I) E KRM the vector whose (a, m)ht dimension is given by Ca,m We now present Algorithm [
Sampling rule After a first initialization phase in which the algorithm pulls each arm at each fidelity once (Line []. the agent starts its sub-gradient ascent routine. More specifically at each iteration t E N, the agent first computes the vector W(t + 1) using the Exponential Weights algorithm on the sequence of gain functions (g.)s= = (Clip, ((Eam Am
VF(W(s), (())) Y5 where (t) = π (t)) represents the pull-proportions induced by (t)) and (s) ()))) denotes uab-gradient of F(w,, μ1) w.r.t w (Line 3). Neglecting for a moment the clipping function and the term
WWe provide insights on cases in which it is possible to compute the optimal fidelity in Appendix B.4
5

---

Algorithm Multi-Fidelity Sub-Gradient Ascent
1: Initialization. Pull each arm at each fidelity once, and set (()) + for all t E fi..... KM}
2: Sampling Rule for 2 K.M
3: Sub-grade Sub-gradient Ascent
(EEnntam VF(O()),
@ 1) E argmax O11 WEAKxM
E
w.
Clipp,,
kl(w, (
==KM
a,m
4: From Costs to Pulls
Wam (t (t+1)
aa (t +1]
Va E [K], E [M]
Am
Σie[k] EjE[M
(1+1) A
5: Forced Exploration
T' (A--1, M411) E argmax (a, [{]]]] (M) E.=1 (8) Na,
+ 7
6: Cumulative Tracking
7: Stopping Rule
To inf (t KM max minzei (Cs) 2 Be.5)
8: Decision Rule
âr, argmax;e(k] mingæs fi. (C(t),
d(s) = (0000(mam Eaam Am Tam (s) (these terms are present mainly for technical reasons), this step can be
interpreted, from an intuitive perspective, as finding a sequence of weights (ao(t)} that minimizes the regret the sequence of empirical losses F(w", s)))) (()(s), (s))). At this point, once @t + 1) is computed, Algorithm will convert these cost proportions into pull proportions while
adding some forced exploration (Line 4 5), and then, it applies a standard cumulative tracking
procedure
g
in the pull-proportion space ensure that No (() E Taam (s) (Line 6).
Stopping and decision rule Finally, the algorithm applies a generalized likelihood ratio (GLR) test decide when to stop (Line 7b. For č, E [K], fi. (t)) can be interpreted GLR statisties for comparing
classes: KMM versus (0 0g E MF, 0j MF, 0g.M 0i.m) ). If that GLR is large enough (if it exceeds a threshold 8,,8), we can reject the hypothesis that fa belongs to the second class. If there is an arm for which we can reject the alternative class for all j o i, we have rejected all O E +MME where is not the best arm and we can safely stop and return the answer â, = i. Since each fi, expressed as sum only two arms and M fidelities, it is possible show that choosing 3r.5 & log(K/o) + 2M log (log(t) + 1) (see its exact expression in (31) guarantees the correctness of the test, namely that P (ā., F +) holds (Proposition C.13
4.1 Theoretical guarantees
At this point, we are ready to state the main theoretical result on the performance of our algorithm. Theorem 4.1. For any multi-fidelity bandit model E ~MMF Algorithm I usiin the threshold 3r,5 given in 31 is 8-correct and satisfies
E [crel
lim sup 8-+0
< (H))
(5)
log (1/8)
As we can see from Theorem 4.1 Algorithm is asymptotically optimal, meaning that it matches the lower bound we presented in Theorem 3.1 for the asymptotic regime of 8 - 0.
Comparison with existing MF-BAI algorithms We conclude this section by comparing our results with the literature [25] B1). First, [25] and [3 rely additional assumptions that play crucial role both for the algorithm design and the resulting theoretical guarantees. (25), the authors enforce additional and intricate structural assumption on the relationships between X A's and E's (see Assumption
[5 In [31] instead, the authors assume additional knowledge expressed as
Whenever (a(s) ) is sufficiently close to p. this implicitly generates a sequence of weights that provide values of F(,, 11) "close" the of the oracle weights w'.

---

an upper bound on P..M and a lower bound on argmax ML.M- For both works, whenever these assumptions are not satisfied (i.e., X's and {'s do not respect Assumption in [25], and the knowledge on Mr,M, argmax,4, .f. H4.M is imprecise/not available), the theoretical guarantees offered by existing algorithms are arbitrarily sub-optimal. On the other hand, our algorithm requires no additional assumptions and is the only one that matches exactly the cost complexity lower bound. Indeed. neither the cost upper bound of (25) nor the one [31 matches the lower bound of Theorem 3.1 even when their additional hypotheses are satisfied.
4.2 Computing the gradient of F(w, (b)
Algorithm D requires computing a sub- sub-gradient of F(w. (o). Notably, we remark that this is needed for a generic μe E @KM, as fu(t) might violate the fidelity constraints due to inaccurate estimations or degenerate cases which the multi-fidelity constraints are attained with equality. In this section, we provide an efficient algorithm for the computation of the sub-gr uub-gradient that arises from a more in-depth study of the function F(w, pt). To this end, we begin by presenting some intermediate characterization of the functions fi,j (e) that define F(w, ut).
Lemma 4.2. Consider μ E KKM and AAKM. Define for k [K].
d du vp + {m) + d+ (prr.ms vb Em)
argmin PER
Wk.m
Am
Then, the following holds:
M
d (4kims Up + Em) + at (pummms 22 Em) if if > +
fislw, 14) =
Wk.m
(6)
Am
(E-j) m=m
M
d (H4,mm 17 + Emd + d+ (145. 1 Em)
fes(w,, = inf Σ
Wk.m
otherwise.
(7)
WER
Am
kE(t,))
m=1
We further introduce ; as the minimizer in the expression in When ja E .MMF, we can show that eig Mk.M for all k and due to the multi-fidelity constraints the expression in (6) is always equal to zero. Hence in both cases fr. (w, p1) is equal to the expression in (7). which can be rewritten
M
d (1kmm Miy Em) d+ (Mus,m Whis 5m
fis(w, v)) = (Mi, 2 ().m)
Σ
Wk.m
Am
(E(())
m=
This quantity be interpreted the transportation cost for making Mj.M larger than (4, When 14 & MF or H4 & MF, if bb; > VJ Ji, (w, (1) is equal to the expression (6) that can be interpreted as transportation cost with an alternative in which i and satisfy the multi-fideityy constraints.
Using this preliminary result, we provide a precise expression for the sub-gradient of F(w, 11).
Theorem 4.3. Consider μ E KKM and w E Ax such that F(w, μ1) > 0 holds. Let (i, a) E [K]]
be a pair of arms that attains the max-min value in Equation (2). Then sub-gradient F (w, u)) of F(w, (1) w.r.t to w is given by one of the two following expressions: for j {a, i] and m E [M].
dt (Hg.m: n.a Em) + dt (H. M.a Em)
VF(w, p)
if 2h
(8)
Am -Em) + d (Pijams 43 + Em)
VF(W, a+ (H4,m, 17
otherwise.
(9)
Am
That sub- aab-gradient F( (1) is in all the remaining KM- 2M dimensions.
Theorem 4.3 shows how to compute a sub-gradient of F(w, μJ) under the mild assumption that F(w. 11) 0. More specifically, it is sufficient consider the pair (i, a) that attains the max-min
"To ease the notation, we omit (most of the time) the dependence of voΣ and ni in w and p. 7 As we discuss in Remark C.8 (() p(t)) = 0 is rare condition, and, whenever it happens, it is possible to alter Algorithm slightly without affecting its theoretical guarantees.
7

---

value in Equation (2. and then test whether of 2 via holds to choose which expression to use among Equations @8) and D. An interesting interpretation of the sub- gradient expression is that, whenever "i 2 Vaa the sub- aub-gradient is pointing toward the direction of the space that aims at increasing the information to discriminate the eventual optimality of arm a against On the other hand, whenever vi > 2 holds, the sub-gradient points towards the direction of minimizing errors in the multi-fidelity constraints for arm i and arm a (if any).
Computing the sub-gradient efficiently To conclude, we notice that to compute a sub-gradient, it required to compute V for all arm i and ni, for all pairs of arms such that 5, 2 2Φ.. Using their definitions, this will require solving O one-dimensional optimization problems of functions that involve (M)) variables, which leads to a computational complexity which is roughly O(K² nn), where n is the number of iterations of the convex solver. In the following, we show that it is possible to exploit the structure of the fi.j" 's to obtain algorithm whose total complexity is O M2) and that does not suffer from any approximation error due to the optimization procedure. Specifically, now present result that shows how to compute M. A similar result holds also for 2% and is deferred to Appendix C
Lemma 4.4. Consider μ E @KM and w E AςхM such that fig(ws μ)) > 0 3/ 2 3 holds. Then, there exists unique minimizer (w)( of Equation 7 solution of the following equation of m:
Suppose that
which is the unique
Enefish Em 1
Wa.m
(ka.m(1) (1) Ham + me (1) Pa.m Smm v(n-
Am
(10)
Eae(io)) Em
wam. Amm
Ta (11) u(n Em) + kamm (1) o(p+
where ka,m (2) = 1 Namm + 5m and Ka,m (2) 1fx S Mi,m Em]
From Lemma 4.4. to compute vi,,, it is sufficient to find the unique solution to the fixed point equation given in (10) To do this efficiently, we observe that the right hand side of Equation (TO) depends
on 17 only for the presence of the indicator functions Fa.m(() (1) and E.. (n), which can only take finite number of values. Hence, it is sufficient to evaluate the right-hand side at an arbitrary point within given interval where the values of the indicator functions do not change. If the resulting value is within the considered interval, then this value is our fixed point. Since there are at most (M) candidate fixed points, this procedure takes most ( steps.
Computational complexity remark It follows that the per-iteration computational complexity of Algorithm
1 is O (K² The computationally efficient technique explained above indeed applies not only to the sampling rule but also the stopping and the decision rules
5 Numerical experiments
We conclude this work by presenting numerical simulations whose goal is to show the empirical benefits of our approach. We compare MF-GRAD against IISE [25), and the gradient approach of
[22] that simply does BAI using samples collected fidelity M. We will refer to this additional
baseline as GRAD. In the following, we avoided the comparison with the multi- multi-fidelity algorithms in
31 as we into issues when doing experiments. We elaborate more on this point in Appendix [D.6] where we provide numerical evidence of the fact those algorithms might fail at stopping, together with argument that shows a mistake in the proofs of 31
Given this setup, first, we test all methods on a 4 X multi-fidelity bandit with Gaussian arms that have been randomly generated, using a risk parameter 8 = 0.01. Due to space constraints and for the sake of exposition, we refer the reader to Appendix [D. for the value of μ., E's and A and details on the stopping rules calibration. We report the empirical distribution of the resulting cost complexities in Figure As one can verify, MF-GRAD obtains the most competitive performance. Experiments on additional 4 x bandits that are reported in Appendix provide similar conclusion.
Furthermore, to illustrate the sub-optimality of IISE and GRAD from an intuitive perspective, we test our algorithm on a simple 5 x 2 instance that allows to easily understand why existing methods underperform MF-GRAD. Specifically, we consider 144 = [0.4, 0.5) for all i [4), 145 [0.5, 0.6),
*Given the definition of ft.j, it is sufficient to replace wi. / Am in Equation 10 with No.. (t).
8

---

3533
700
3003
Complexty
Cost Compleesit
200
1993
200
1933
160
530
Figure 1: Empirical complexity for 1000
Figure 2: Empirical cost complexity for 1000
times with 0.01 on the 4 multi-fidelity bandit.
times with ó 0.01 on the multi-fidelity bandit.
0.6
Emgirical Cast Propuntons
0.5
0.4
0.3
0.2
0.0
20000
10000
60000
80000
100000
lteration Number
W1.
W2,0
W3.0
6/5,0
WC,1
011
63,1
W4,1
Figure Empirical cost proportions of MF-MRAI for 100000 iterations on the 5 x 2 bandit model. Results are average over 100 runs and shaded area report 95% confidence intervals. Empirical cost proportions of certain arm plotted with the same color. Cost proportions fidelity and 2 are visualized with circle and squared respectively.
= 00.5, 5). c 10.1.0 0] and report the cost complexity of the three algorithms in Figure 2 In this case, we can prove that the optimal fidelity sparse on fidelity m = 1 for E [4], and on fidelity = for arm 5. Furthermore, thanks to the symmetry of the problem. it is possible to show that - = [0.09622 (0.09621,0) 0] for all i [4], and w = j0, 0.61516] (see Appendix D.I). As one can see, IISE obtains the worst performance in this domain. The reason is that the concept of optimal fidelity on which IIS relies sub-optimal (i.e., according to the design principle of IIS,, the optimal fidelity is m for all arms), and the algorithm, in practice, will discard sub-optimal arms using samples that have been collected only at fidelity m 2. Nevertheless, this will only happen after first period in which IISE tries exploit (unsuccessfully) data fidelity m 1. GRAD, on the other hand, obtains sub-optimal performances since although most of the budget should be spent on fidelity (as w* s=s,2 5,2 0.61516), it never pulls the cheapest (and optimal) fidelity for arms i [4]. Finally, MF-GRAD, on the other hand, obtains the most competitive performance since, as learning progresses, its empirical cost proportions eventually approach the one prescribed by w*. To verify this behavior, we removed the stopping rule from MF-GRAD, and let the algorithm run for 10 iterations. In Figure 3 we report the entire evolution of the cost proportions during learning. As one can appreciate, at the end of this process, the empirical cost proportions of MF-GRAD are approaching the one described by w² [ (e.g., additional domains, smaller regimes of d) and further insights.
Finally, we also refer the reader to Appendix D for additional results
FFrtteermore, at the end of this period, we measured the distance between w' and the empirical cost proportions w110):: ): it holds that -| w(10")llz ||2 z 0.031 0.0006. The error has been estimated with 100 independent runs. and 0.0006 reports the 95% confidence intervals.

---

Conclusions
For fixed-confidence best arm identification in multi-fidelity bandits, we presented a lower bound on the cost complexity and an algorithm with matching upper bound in the regime of high confidence. The algorithm uses features of the lower bound optimization problem in order to compute updates efficiently. Unlike prior work, it does not require any assumption or prior knowledge on the bandit instance. Our work also confirmed the existence in most cases of an "optimal fidelity" to explore each arm in the asymptotic regime, and revealed that the intuitive such notions proposed in prior work were inaccurate. Yet, our algorithm does not need to identify these optimal fidelities in order to be asymptotically optimal.
This raises the following question: could the performance the algorithm be enhanced by exploiting the sparsity pattern? We conjecture that estimating the optimal fidelities accurately may actually be harder than identifying the best arm. However, leveraging some sufficient conditions for wa,m (such as the ones given in Proposition to eliminate some fidelities and reduce the support of the forced exploration component of the algorithm seems promising idea. A limitation of our current analysis is that it only provides asymptotic guarantees in the high confidence regime, although our experiments reveal good performance for moderate values of 6. future work, we will seek better understanding of the moderate confidence regime (30]. To this end, we may leverage some proof techniques from other works using online optimization that obtain finite-time bounds 4 5 On the lower bound side, while C* (H) essentially scales with K due to the sparsity pattern, interesting open question is whether there is worse case O (.MM M) scaling in the moderate confidence regime, indicating that all fidelities do need to be explored at least constant amount of times.
Acknowledgments and Disclosure of Funding
This work was done while Riccardo Poiani was visiting the Scool team of Inria Lille. He acknowledges the funding of MOB-LIL-EX grant from the University of Lille. Rémy Degenne and Emilie Kaufmann acknowledge the funding of the French National Research Agency under the project FATE (ANR22-CE23-001 6-00) and the PEPR IA FOUNDRY project Metelli and Marcello Restelli acknowledge the funding of the European Union Next Generation EU within the project NRPP M4C2, Investment 1..3 DD. 341 15 march 2022 FAIR Future Artificial Intelligence Research Spoke 4 PE00000013 D53C22002380066.
Alberto Maria
10

---

References
[1] J-Y. Audibert, S. Bubeck, and R. Munos. Best Arm Identification in Multi-armed Bandits. In Proceedings of the 23rd Conference on Learning Theory, 2010.
[2] Olivier Cappé, Aurélien Garivier, Odalric-Ambrym Maillard, Rémi Munos, and Gilles Stoltz. Kullback-leibler upper confidence bounds for optimal Statistics, pages 1516-1541, 2013.
sequential sequential allocation. The Annals of
[3] Rémy Degenne and Wouter M Koolen. Pure exploration with multiple correct answers. Advances in Neural Information Processing Systems, 32, 2019.
[4] Rémy Degenne, Wouter M Koolen, and Pierre Ménard. Non-asymptoti pure exploration by solving games. Advances in Neural Information Processing Systems, 32, 2019.
[5] Rémy Degenne, Han Shao, and Wouter Koolen. Structure adaptive algorithms for stochastic bandits. In International Conference on Machine Learning, pages 2443-2452. PMLR, 2020.
[6] 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:1079-1 -0009 2006.
[7] Côme Fiegel, Victor Gabillon, and Michal Valko. Adaptive multi-fidelit optimization with fast learning rates. In International Conference on Artificial Intelligence and Statistics, pages 3493-3502, PMLR, 2020.
[8] Aurélien Garivier and Emilie Kaufmann. Optimal best arm identification with fixed confidence. In Conference on Learning Theory, pages 998-1027. PMLR, 2016.
[9] Deng Huang, Theodore T Allen, William I Notz, and R Allen Miller. Sequential kriging optimization using multiple-fidelity evaluations. Structural and Multidisciplinary Optimization, 32:369-382. 2006.
[10] Jamieson, M. Malloy, R. Nowak, and S. Bubeck. UiI an Optimal Exploration Algorithm for Multi-Armed Bandits. In Proceedings of the 27th Conference on Learning Theory, 2014.
[11] Kevin G. Jamieson and Ameet Talwalkar. Non-stochastic best arm identification and hyperpa- rameter optimization. In AISTATS, 2016.
[12] Shivaram Kalyanakrishnan, Ambuj Tewari, Peter Auer, and Peter Stone. Pac subset selection in stochastic multi-armed bandits. In ICML, volume 12, pages 655-662, 2012.
[13] Kellen Kanarios, Qining Zhang, and Lei Ying. Cost aware best arm identification. arXiv preprint arXiv:2402.16710. 2024.
[14] Kirthevasan Kandasamy, Gautam Dasarathy, Junier Oliva, Jeff Schneider, and Barnabas Poczos. Multi-fidelity gaussian process bandit optimisation. Journal of Artificial Intelligence Research, 66:151-196, 2019.
[15] Kirthevasan Kandasamy, Gautam Dasarathy, Junier B Oliva, Jeff Schneider, and Barnabás Póczos. Gaussian process bandit optimisation with multi-fidelity evaluations. Advances in neural information processing systems, 29, 2016.
[16] Kirthevasan Kandasamy. Gautam Dasarathy, Barnabas Poczos, and Jeff Schneider. The multi- fidelity multi-armed bandit. Advances in neural information processing systems, 29, 2016.
[17] Kirthevasan Kandasamy, Gautam Dasarathy, Jeff Schneider, and Barnabás Póczos. Multi hulti-fidelity bayesian optimisation with continuous approximations. In International conference on machine learning, pages 1799-1800 1808. PMLR, 2017.
[18] Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier. On the complexity of best arm identification in multi-armed bandit models. Journal of Machine Learning Research, 17:1-42, 2016.
[19] Emilie Kaufmann and Wouter M Koolen. Mixture martingales revisited with applications to sequential tests and confidence intervals. Journal of Machine Learning Research, 22(246):1-44, 2021.
[20] Tor Lattimore and Csaba Szepesvari. Bandit Algorithms. Cambridge University Press, 2019.
[21] Shibo Li, Wei Xing, Robert Kirby, and Shandian Zhe. Multi-fidelity bayesian optimization via deep neural networks. Advances in Neural Information Processing Systems, $3:8521-8531 2020.

---

[22] Pierre Ménard. Gradient ascent for active exploration in bandit problems. arXiv preprint P.Xiv:990.00816. 2019.
[23] Quan Nguyen, Arghavan Modiri, and Roman Garnett. Nonmyopic multifidelity acitve search.
In International Conference on Machine Learning, pages 8109-81 18. PMLR, 2021.
[24] 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.
[25] Riccardo Poiani, Alberto Maria Metelli, and Marcello Restelli. Multi-fidelity best-arm identifi- cation. Advances in Neural Information Processing Systems, 35:17857-17870, 2022.
[26] Matthias Poloczek, Jialei Wang, and Peter Frazier. Multi-information source optimization.
Advances in neural information processing systems, 30, 2017.
[27] Yoan Russac, Christina Katsimerou, Dennis Bohle. Olivier Cappé, Aurélien Garivier, and Wouter M Koolen. A/b/n testing with control in the presence of subpopulations. Advances in Neural Information Processing Systems, 34, 2021.
(28) Rajat Sen, Kirthevasan Kandasamy, and Sanjay Shakkottai. Multi-fidelity black-box opti- mization with hierarchical partitions. International conference on machine learning, pages 4538 4547. PMLR, 2018.
[29] 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.
[30] Max Simchowitz, Kevin G. Jamieson, and Benjamin Recht. The simulator: Understanding adaptive sampling in the moderate-confidence regime. In International Conference On Learning T'heory (COLT), 2017.
[31] Xuchuang Wang. Qingyun Wu, Wei Chen, and John Lui. Multi-fidelity multi-armed bandits revisited. Advances in Neural Information Processing Systems, 36, 2024.
12

---

A Table of Symbols
Table 1 reports a summary on the main symbols and the notation used throughout the paper.
Table Notation
Symbol
Meaning
K, M
Number of arms and number of fidelity
8 E (0
Maximum risk parameter
Ts
Stopping time of algorithm
Cre
Cost incurred at the stopping time
a. (pL)
argmax,e[K] Pa.M- Often denoted simply by *
Arm recommended by the algorithm when it stops
Bandit model
Di.m
Mean of the i-th arm fidelity within bandit model JA
Em
Precision of fidelity m, i.e., max Hi.m Ha,arl S Em
Am
Cost incurred for gathering samples fidelity m
θ
Set of possible means in the exponential family
Pa E MF
Arm a satisfies the multi-fidelity constraints Empirical bandit model at time & Set of multi multi-fidelity bandit models Set of multi-fidelity bandit models with a unique optimal arm
at)
MMF
MMF
d(p. g)
KI. divergence between two distributions with means p.g in the exponential family d' (p, d(p, 4)1 {p S 4). d (xx v) d(p, q)1 {p q} Variance of the distribution in the exponential family with mean parameter y Expression that characterizes the lower-bound the cost-complexity
d (p,.)), dt
oly)
C (a)-
w, π
Vector of cost and pull proportions respectively
w"
w² argmax xM F(w, μt)
Re)(w,
Dissimilarity between arms and j defined in Equation ma minjzi [ μt)
F(w.
(H)M((H
Set of optimal oracle weights w for the multi-fidelity bandit model μ
MMF
Subset of multi-fidelity bandit models for which there exists non-sparse optimal allocation w Uniform K -dddimensional vector ((KM) ...... (KM)
G>0 0
Clipping constant in Algorithm
Learning rate and forced exploration rate respectively
C(t)
Vector whose (a, m))thh dimension is Ca,m (t)
(t)
Vector of empirical cost proportions, namely Wa,m (t) = (t) EjE[M] Ct,(())-)
of
Minimizer of Equation Minimizer of Equation
kirm (1)
(1) 2 14.m {m)
kmmm (1)
1 {n7 S Pi. Em
Cost complexity lower bound: proofs and derivations
B.1 Proof of Theorem 3.1
Theorem 3.1. Let 8 10, For any 8-correct strategy, and any multi fulti-fideiity bandit model
E M it holds that:
En(cr,] C" (H) log (218),
(3)
where (p))- = supwEARKM F(w, pd) suw minaz+ S pi).
Proof. Consider E (0, 1), filtiifidelity bandit model y and an alternative instance 0 E Alt(p)
where Alt(H) Ult (0 E MMF 0a > O. Then, by applying Lemma in [18), we can
13

---

directly connect the expected number of draws of each amm to the KL divergence of the two multi- fidelity bandit models. More specifically, we have that:
Σ
Σ [N(Na. (Tslmmm)))(((a Oa,) 2 kl(d, -6)-
(11)
[ mE[M]
Then, similarly Theorem in 8 we now proceed by applying Equation with all the alternative models 0 E Alt(u). Specifically, we have that:
kl 8) - inf (EAl((
Σ
Σ
Ep (Na (Ta) Ma 0a,m)
aε[K] me(dd]
Ex Nam (T8)
d(Ha,m 0a,m)
Eulcrsl
inf BEAl(())
Σ
Ex [Cral
Am
aE[K] mE(M)
da Oam
Bplcr [CT]]
sup inf W δEAl((H)
Σ
Wa.m
Am
aE[K] mE|M]
d(fiim iz.m)
Bplers]
sup
min
inf OEMMR:
Σ
Wim
WEAKxM of* 0 20.M 1,m
Am
(a) wEAKXM
Epleral
sup
min
inf M.MF 0, EMF: 0. 20,M
Σ (E(+a)).E[(M)
Wi,m
d(p Os,m) Am
a+*
sup wEARxM
min (w, os
Eple,, (C" (H)
where (a) we use that as μ E MMP, the minimum in 0 does not change any arm i & (*,a). Finally, we lower bound kl(6, 1 8) with log (..))) thus concluding the proof.
B.2 Comparison with existing lower bound
In this section, we provide comparison with the existing lower bound for the MF-BAI setting. In the following, we restrict attention bandits with Gaussian arms with variance 1/2. We assume for simplicity of the exposition that * = and that JA,M > P2,M 2 ... MKKM- Given this setup,
we begin by recalling Theorem in (25]
Theorem B.1 (Theorem 1 in (2)). Consider any multi-fidelity bandit model μ with Gaus-
sian arms with variance 1/2. Then, for any 8-correct algorithm and I 0.15 it holds that E [crul/ log ((2.45) lower bounded by:
K
Am
Am
min MEIM fL.m 22. +-mm
min ME]
(M1.m (H2 {m
(Nim
(MI.M 5m
At this point, focus, for simplicity on the following 2 x 2 bandit model (but a trivial generalization holds for K x M bandits). We consider f1,m M1,M + &m and P2,m H2, &mm. Furthermore, suppose that J1.M = 122MM Then, let PA,M - M2, Suppose that A Em. which yields
2
H1.M S.. and N2.M = Em and that
A
Am
A
fm
Am
Since A = Em. this condition actually simplifies to AM 2 4Am-
Under these conditions it is possible to verify that the lower bound of [25] is given by
2)m
1
8Am
E2 [Cr)]
2
log
log
2.48
A
2.45
A
Em
14

---

At this point, consider, instead, the result that we presented in Theorem 3.1 and consider a generic weight proportion w. From Corollary C.2
know that:
d (p1mm 1) + Em) d+ (42,. Em
F(w; p1) f1,2(w, 1))
inf
W1,m
+ w2.m
TEl ML.
Am
Am
MEIM]
(12)
Then, let w.. be the optimal weights restricted on the portion of the simplex in which w1,m W2. = 0. Then, let 17" be the optimal solution of Equation (12) when considering wt..
Using the symmetry of the KL divergence for Gaussian distributions, it holds that 17 = and ..M
with = -22 = 0.5. Then, for any w holds that:
d' mm n + 5m)
dt (12 n Em)
(W 5 E W1,m
w2.m
Am
Am
MEIM!
d(HI.M. ...MM
-W,M
W2,M
AM
Am
I F(w*.M 1t),
where in the second step, have used the fact that d( 17" T - -mm) d(p2 -mm) 0 and d(p1.m 17 ",, + 5m) = d( + Sus Em) = O. In other words, we have shown that in this 2
example the optimal allocation is sparse and on fidelity M. To conclude, we have that:
d 5m 0)
d( a d( d(fr.o) (A/2)2 A
fm
F(w M 11) 0.5
+ 0.5
Am
AM
Am
Am
4
which leads to:
4AM A
En(ers] 2
log (22.46)-1).
Under the assumptions the problem, Lay is always larger than Sdy. This result says that the ratio among the lower bounds can be order Am/ / Am which is arbitrarily large.
B.3 Proof of Theorem
In this section, provide formal proof the sparsity of the optimal oracle allocation wt. The proofs given in this section rely on results that are explained in Appendix C.I
At this point, in order to prove Theorem 3.2 we first introduce some intermediate results that will be used in the proving the theorem. Specifically, we begin by showing that, for each arm o, there always exists fidelity m such that wa.m holds.
Lemma B.2. Consider μ &Mur and w AkxM(()). Then, for all E [K], there exists m [M] such that wa.m 0.
Proof. We split the proof into cases. First consider + and proceed by contradiction. Consider w" E x (H), and suppose there exists a + * such that w for all m E [M]. In this case, however, have that:
d(u 0m.)) 0,
F(w", .p) (w.a
inf 6.EMF EMF: 6., 60,M20,,
Σ wi.m
(13)
Am
where, the first step we have used the definition of F(w", 11), in the second one the fact that wi.m 0 for all m E [M]] and in the last one we selected 0 0.,m px.m for all m E [M]. Nevertheless, from Lemma C.6 C.6
know that, whenever wa,M 0 holds for all [K], then F(w: (1) > 0 holds as well. Therefore, w" & A
The proof for the case in which i follows identical reasoning.
15

---

We then continue by proving that, at any optimal allocation w", all the transportation costs fa(w", pt) are equal.
Lemma B.3. Consider μs Maa and w" E Axxxr(H)). Then, for all a, b such that # and
b + * the following holds:
fralw" (4) fa,olw,
Proof. We introduce the following notation:
A [K] [+t) argmin folw", 14) bet
B = (<K] (+)) AA
At this point, we proceed by contradiction. Suppose that B 0. Then, for some sufficiently small e > 0, we define ت E Aαхм in the following way. For all a E AA:
Wa.M Wa,M + e/|A
Wa,m wa.m Vm < M.
For all E B, instead:
Wb,ms Whbmm c/ |B|
Wb.m Wb.m Vm F mb:
where my E [M] is any fidelity such that wa, wT,m, O (which exists by Lemma B.2
Given this definition of w. it is easy to see that f+ (wr (e) > f= " μ)) for all E A. This direct consequence of the fact that f+, is strictly increasing function of Wa.Ms which is apparent from its expression from its expression for μ .MM given in Corollary C.2 the computation of its gradient (Lemma C.3) Moreover, due to similar arguments, it also holds that [r,a(W, μe) S [ww("" (u) for all E B. Using the continuity of the functions, f. for & small enough we further have (", (1) < f.,6(W,, ju) for all a A and b E B. This leads to minay* S (w" p.) min S (wo, (1) which contradicts the optimality of w".
We now continue by providing necessary conditions that characterize some key properties of the oracle weights which follows from the expression of the gradient of fw, (1) with respect to w for μ E MMF (Lemma C.3).
Lemma B.4. Consider μ M and wt (KxM( Then, for all + the following conditions holds:
dt (Ha.ms "haa Emi)
at d+ (Ma (ww( - Emz) Vm m2 Wa,my W Wa,mg 0
Ama d= (p (wo( + Emg)
Amz
d (Mu, (ha(w")) (ww)+++ + Ema)
Vm1, m2 w my Wh,mg >
Ama
Amz
at (Hangg na (w"" Emg) d' (pr,ma Wh. (w)) Emz)
Vmn, m2 Wa wh >> 0
Amy
Amz
Proof. We begin by recalling the definition of C* (14)
(²(N)) sup min f.aa(,, (W.H). 14)
wEAxxM agf
which, is a concave optimization problem with a non-empty feasible region. Therefore, we can apply the KKT conditions to study the properties of each local optimal point w' for which the sub-derivatives exist, i.c., from Theorem 4.3 and Corollary C22 the ones for which the following condition hold
min (w) > 0. of*
(14)
We notice that global optimum point clearly satisties this condition.
16

---

At this point, fix any arm a that attains the minimum in Equation 14 we obtain the following system of inequalities:
Then, from the KKT conditions,
8_ (w, (1) + ba.m =0 0
Vm E [M]]
wamm
w.mm (na(W,
mm [M]]
bi,m
Vi E {+, a) Vm [M]
bi,
vi E [K], Vm [M]
W 2 0
Vi E [K], Vm E [M]
E i.
ff =
At this point, suppose that .i O, W2y.m for some $1, i2
{*.0] and some m1, m2 E [M].
then bi..m, = 0, by ma O. As a consequence, by applying Lemma C.3 and the fact that μ E MMF (i.e., see Corollary C.2 the following equations holds:
at (Hammi Na,a (w)) Em1)
dt (Pa,m2: Vi, (r.a(w") Emz)
4m1, m2 wa,mu Wa > 0
Am1
Amz
d= (14 (w=) + Em²)
d (1un (ia( + Ema)
Vmn, my w wmn Wh
Ama
Amz
d+ (Ha,m, We, (walww)) - Em1) dt (Merma Th (w) + Ema) Vmn, m2 W we >
Am1
Amz
Finally, to conclude the proof, sufficient iterate these arguments for a a *. Indeed, from
Lemma B.3 optimum
we know that all sub-optimal arms will attain the minimum in Equation (14) at a global
At this point we are ready to prove our main result.
Theorem 3.2. Let AxxM (14) argmax F(w, n1) and
MMF= =
Ei E [K], 30,,,,,,, m2 E [M] Fwu E AxxM(()) wf.. > 0, 0immm > 0}.
The set MAR a subset of R xx xM whose Lebesgue measure is zero.
Proof. Let us introduce some additional notation. Consider subset of arm-fidelity pairs X' S [K] x [M). and define (XX) C M as the subset of multi-fidelity bandit models for which there exists w' A (H) such that, for all (i, m) X, wi,. > 0 holds.
Then, fix an arm i # *. and any three fidelity M.. m2, m3
[M], and consider μ
G(i(i, m1), (i, (*, m2)) Then, from Lemma B.4 we know that the following condition holds:
d (Himm Th (w0)) - Emy) d= (p (w=) + Emg)
(15)
Ama
Ams
This, in turn, implies that ni, (w=)) is uniquely identified as function of pi,mi Man Emy Emg- Amy and Amy- Indeed, d+ (Jt,,, ",, (w=") Em,) ) a strictly increasing function of 1),, (w=),, while d' (pa (w") + Ems) is a strictly decreasing function of ni,, (w"). Let c1 = nT (w=",, and let at (Mr.mn mi,,(w" (w") Smmm) At this point, since w > 0 holds by definition, also know, from Amy
(w=))+
02
Lemma B.4 that the following condition has to be satisfied:
d' (Hr.ma Ema) C2-
Amz
Therefore, the value of Mi,ma is uniquely identified as a function of Pi,mis 5m Ems. Am. and Amg. That function is measurable (it's combination of d+, d= and their inverses), hence f lies on the graph of a measurable function, and such a graph has Lebesgue measure Therefore,
Similar arguments hold also for
17

---

((((i, m1), (f. m2), (+, m2)}) has measure O. At this point, thanks to Lemma B.2 we know that, for arm *, there always exists least a fidelity my such that wi,mg O. We thus have that
G((i, m1). (1, m2)) S
U m [M]
G((i, (1, m2), (+, ms))
Since G((i, m1), (t, m2)) is contained in set which is countable union of null measure sets, it has null measure.
To conclude the proof, we notice that:
K MMF S U
U mm.
((((i, (i,
i=1
The proof follows from the fact that (i) y is countable union of of null measure (and, consequently, has null measure), and (ii) MMF _
B.4 Additional results on the sparsity of the oracle weights
In this section, we present additional results on the sparsity of the oracle weights. Specifically:
We identify specific class of multi-fidelity bandit models in which the optimal allocation is sparse. In particular, within this class MF-handit models, the optimal allocation have non-zero values only at the cheapest fidelity.
(ii) We then provide sufficient conditions determine whether some fidelity have zero weights at any optimal weight vector w
We now proceed by constructing the class of multi-fidelity bandits that we mentioned in point (i) above. In this construction, will consider Gaussian multi-fidelity bandits with variance 2- Then, for any number of arms K and fidelity M, we will denote with AKas . the set of Gaussian multi- fidelity bandits that satisfy the following construction. We start by building the means of the arms at the highest fidelity M. Specifically, we consider a generic J4,m > 0, and let Ma, = P..m for all f Then, for each fidelity m M, and any values of Am and Em, we let Jtim = -i.M &m for all i + *, and M.m H.,M + Em. Finally, to simplify some computations, Gaussian distribution to 2.
set o² of each
Proposition B.5. For all μ AKM, and any w E A ii it holds that, for all [K] and all m 1, W a.m
Proof. To prove the result, starting from Corollary is sufficient notice that, for all μ AKM and all a + *, fr.a (w, (t) can be rewritten as:
M
d(pa,M,))
nElMo M. (E(+.a) (w) inf
Σ
Wimm
(16)
Ay
Specifically, Equation (T6) follows directly from the symmetrie property of KL divergence for Gaussian distributions, and by the construction of μ.. The proof then continue by contradiction. Suppose there exists w' such that there exists (i, m) (with m > 1) such that wi,. > 0. By defining w as the vector which is equal to w" except in the components (i, m) and (a, 1) for all a E [K]. More specifically, for sufficiently small > O, we define üi.m w/ c and Wa,1 w + c/(K) for all E [K]. Then, it is easy to see that ( > f.a holds for all * thus contradicting the optimality wf"
Finally, we now provide sufficient conditions to determine whether some fidelity have zero weights at any optimal weight vector wt
Proposition B.6. Fix a + x. Then, if pa.m + Ex 2 pm then holds that wi.. p.m Em P3. for all & then it holds that w m O.
Furthermore,
18

---

Proof. Consider * *, and let us analyze f. (e) for any w E AKXM- More specifically, we recall from Corollary that the only term which Wa.m plays a role the following one:
d(uamm: Ti (w)) Em), (Niia(w) 2 Ma.m + Sm
Wa,m
(17)
Am
Nevertheless, since Ve (w) S pa.m SS Pa.m + Em. we have that Equation (17) is always equal to 0 for all w Ax M. To prove the result we now proceed by contradiction. Suppose that w such that wa,, > 0. Then, consider W as a vector which is equal to w" except in the components (a, m) and (i, .)) for all i o *. More specifically, for sufficiently small e >> 0, we define Wa,m = w -6 and W = wi. + t 1) for all i o x. At this point, by noticing that f,,(w, μ1) is strictly increasing in Wi.M (i.e., due to Theorem 4.3 and the fact that μ E .MMF), and since faalw, μe) is not affected by the value of wa.m (i.e., Equation (T7)), we have that f0, u1) > fw,("", 14) for all i * *, thus contradicting the optimality of w".
To show that if j4.m mm S Pj.M for all j * then it holds that wI follow identifical reasonings. The only difference is that the term wa,m plays a role in each of the (K ))eeuaaiions defining F F(w, (t), namely:
it is possible to
d(pl,, ne,a (w) + Sm) (w) S f1,m Em
Wa,m
Va +
(18)
Am
Nevertheless, Equation 18 is equal to 0 for all a * * since ni (w) 2 fi.m - Em 2 Mo,M holds for all w and all * *. The proof then follows by an identical construction of an alternative weight vector e which increases the objective function.
B.5 Sub-optimality of "optimal" fidelity of previous works
In this section, we discuss how the concept of "oopiimll" fidelity of previous works (i.e., 225 and fails to satisfy the notion of optimal fidelity that arises from the tighter lower bound that we presented in Section In this section, we consider as example 2 x 2 multi-fidelity bandit models with Gaussian distributions. To ease the notation, we will consider J1,M > P2.M-
(T)
B.5.1
Case 1
We notice that 22 provided the two concepts of optimal fidelity. The first one is from their Theorem 1. This same concept was then considered later in B1I. fidelity m optimal for certain arm a E [K] if it satisfies the following condition:
M1,M (Hamm + Sm)
m E argmax mE[M]
if +
(19)
V\m
(Ha.m
Em) H2.M
m E argmax mE[M]
if
(20)
V Amm
Then, consider the following 2 2 example of multi-iidelity BAI problem. Let &1 = 0.1, M1,M 0.6. fi,m = 0.65, H2,M 0.5, f2.m = 0,45 (where we use the notation M for the maximal fidelity and m = 1). Suppose, furthermore, that all distributions are Gaussian. In this case, from Equation I9 20 we have that m = 1 and m = whenever the following conditions are satisfied:
PI.M (M2.m + Em) Vdm
P1.M P2.M
VAM
P1.m Em
U2,M
PL.M
M2.M
VAm
Vdas
Plugging in the numerical values, we obtain in both cases
0.05
0.1
VdM
AM thus showing that, according to 31, the optimal fidelity for both arms is m whenever
0.1
0.05
19

---

At this point, consider the expression of p4) = f1,2(w, in this particular example. Then, then, fi,2(w, p1)
is possible show that, for any w E A2x2 such that WI,M W2,M Specifically, we have that F(w, 14) is given by:
d(11m + Em (n S Pl.m Em} + wa.m
d(p 11 Em) n 2 Namm Em
inf M
wi.m
Am
Am
In turn, this is equal
d(0.55, 1) 1) S 0.55]
d(0.55, 1) 2 0.55)
inf w1, De 0.55.06
+ wa.m
Am
Am
which is always for 0.55.
On the other hand, Lemma C.6 shows that any strategy that gives positive value to weights at fidelity M 2 obtains F(w. (1)
B.5.2 Case 2
Furthermore, 25 provided also the following concept of optimal fidelity which only holds for
sub-optimal arms (see Definition in (25)) fidelity such that P1.M 12,M 4fm holds said to be optimal for arm # if the following holds:
Am
Am
(21)
(11,
Pa.M 4m
mmm (1
Ma.M
45m)²
At this point, consider the following classes of multi multi-fidelity bandit models: f22m = A2.M Em- M1,m. = M1.M + Em. M1,M μ2,M S 46m. this case, from Equation (20) it follows that the optimal fidelity for arm 2 is always M. Nevertheless, since 12.m = H2.M Em. M1.m M1.M + Sm. we W2.M O.
know from Proposition B.5
W1,M
C Algorithm analysis
C.1 Gradient computation
We start by analyzing a salient feature of ft,[W, (a) that holds for any μa K.M.
Lemma C.1. Consider μ E KKM, Fix any w E A and i,j E [K]. Let 0" be the solution of the following optimization problem:
a(p.mm (gm)
d(pim 02,m)
argmin
Σ
Wpm
+
Σ M
Wi.m
0.EMM MAMB,,,MME EM::: mE(M)
Am
Am
0g 20.M
Furthermore, define for E {i,j}:
(w, μ. 0²) = (m [M - 1]: 67. > pk.m + 5m
M (w, μe 0*) = {m [M - 1]: 0h. < Pk.m Em
Then, k E ii }} we have that
0g = Hk.m
Vm E [M] \ (M U (,W,
(22)
fi.m OK.M M
Em
Vm E M (w, μt, 0")
(23)
hr 0% Em
Vm E M,(w, μc, 0")
(24)
In particular,
d (p 0R Em) d+ (Juk.ms Ok.M Em
(1 14)
Σ
Σ Wk.m
Am
kE(A,)) me[ad]
d (Hk.m OR.Ms + Em) + dt (pu.. Ok.M - Em)
Σ
Σ
min 0j.M 28.,
Wkm
Am
&e kE(1)) ME[M]
20

---

Proof. We begin by proving Equation 22).
To this end, it is sufficient to notice that, given fixed R. is possible set k. = Pk,m. whenever the following condition satisfied:
10 - Pk.ml S Em-
(25)
The condition is Equation (Ma(w, ne, 0*) M, 0*)). which concludes the first part of the proof.
is equivalent to requiring
E
[M]
We continue by proving Equation From this condition, it directly follows that 0 Pk,mi therefore, since dm 3:) is increasing in æ, it follows that, in order to attain the argmin, need to pick the smallest value of 8k.m that satisfies the fidei-fi constraint 18t,r - 0k,ml that is fk.M 5m.
Consider Mu(w, μs. 0*). that is Fr.m Mk.m + Em-
The proof of Equation (33 follows is almost identical to the of Equation 24 is sufficient replace the definition of Mx(w, pe, 0*) with M3 (w, μr, 0*).
At this point, we continue by analyzing in more detail the function Si.j (w, ut) Lemma 4.2. Consider μa E @KM and w AxxM. Define for k E [K].
d (Huemm v + Em) + dt (Hek.ms Em)
argmin RE
Wkmm
Am
Then, the following holds:
d' (1kkms 1/ + {m) + dt (Mk.m 10 Sml
feg(w, 11)
Σ
Wk.m
is > 1/
(6)
Am
KE kE(..)) m=1
d (Hu.m 77 Em) + dt (pkk.m 17 Em)
fig(w, inf Σ
Wk.m
otherwise.
NER
Am
kE(i.)
Proof. The proof follows by analyzing the definition of fwg μt). Consider 0% 07 that attaines the minimum in Equation (T). Then, there are two possibilities: either 07 =03.a 0j.M or 0J.M > 07
Suppose that fj.M f then notice that the optimization problem in fe,( μ1) is 2D-convex optimization problem in the variables f fg.M (thanks to Lemma C. Therefore, since the minimum of the constrained problem is such that f > 0 than, by the convexity of the problem, this is also minimum for the unconstrained problem, thus leading to:
d(uk.m OR,m)
Ses(w, 14)
inf BEEM,,,EEM
Σ
Wk.m
Am
(i mE[M]]
At this point, we notice that the constraints in the previous optimization problem are only intra-arm. Therefore, we can rewrite fr. (w, (1) as:
d(pi.. Ok.m)
[e)(w,
inf BLEMF kE(L.)
Σ
Σ
Wh.m
Am
mE(M)
Furthermore, applying the reasoning in the proof of Lemma C.1 we can further rewrite fu,(w, 4) as follows:
d+ (t 1b Ema + d (pk tb + Em
fiy(w (4) = Σ
inf VER
Σ
Wk.m
Am
mE[M]]
(pkmms 24 + Em) + d' (Hu,ms 2i Em)
Σ
Σ
Wk.m
Am
(E( ME(M]
At this point, we notice that due to Lemma concluding the first part of the proof.
we know that 07,0s = 1/ and 07 1/. thus
21

---

Consider now the case in which J.Ms = d. holds. Then, applying Lemma C.1 and using f.M j.ss. we can rewrite Jig (w, (e) follows:
M
feylw: 14)
inf Σ
Σ
Wk.m
(d+ (Momm))) - Em) + d (H 11 + Em))
nER (E((J)
Am
m=1
thus concluding the proof.
Given this result, we recall that the definitions of
d' (ui,m
vb + Em) + d+ (nimm v/ Em)
1 argmin
Σ
Wi.m
(26)
PER
mE[M]
Am
d' (1skm 17 + Em) + (146. 17 Em)
Wi
argmin
Σ
Σ
Wk.m
(27)
Am
NER
be (E(i mE[N]]
Corollary C.2. Consider E MMF, and a E [K] such that o * Then it holds that:
M Wi,m
d (pim.: 17 + Em) + d (p4,m. Em)
fa (,, ())
inf nElmo, (M,
Σ
Am.
(E(x.a) m=1
d (Hrem 77 5m)
dt (pa,m: Em)
inf ne(Me, ad)
Wmam
Wa.m
Am
Am
Proof. At this point, we notice that whenever MMF it holds that f..a can always be expressed as Equation (7). This is direct by the condition on et's Lemma 4.2 Furthermore, also holds at Th, that d (Ma,m: Dr,a + {m) = O. and dt (Hrm 17,a [m) = 0. This is a consequence of the fact that nh E [Ha,Mr, p4.arl for all weights w. Indeed, 7h E [M Me.M] holds due to monotonicity property of the KL divergence.
We analyze in more detail Equations 26 and (27 In particular, begin by focusing
Equation (26). Taking the gradient in Equation 27 w.r.t the optimization variable and setting
equal O, we obtain that any optimal point Wi. ()) needs to satisfy the following equation:
M
7
Σ
Wa.m
hiam r(1 Em²
+ ka.m v(1 + Em²
(28)
Am
m=1
M
Wa.m
Ka,m Mamm + Em
Ha.m Em + kam u(n + Em)
Am
v(n Em)
(E().) ml
where recall that Ra,m (n) and k ka.m (1) are given by:
Kamm (n) = =1 {n 2 Ha,m + Em
ke m 1 {n < Ha.m Em
Given this intermediate result, we now investigate in more depth the solution of Equation (88
Lemma 4.4. Consider μ E @KM and w E AкхM such that feg(w, pa) > 0 Suppose that vig 33 holds. Then, there exists unique minimizer (.,((w) of Equation which is the unique solution of the following equation of m
Ene(ie) Em
Wa.m
(Kam(1) thm + ka (1)) v1n)-5m)
Pn.m Em v(i+tm)
Am
11 Ene(in)) Em
(10)
Ta v(n- + kam (1) v(rtsm)) where (x) = 1fx Mam + Emi and kam (x) 1fx pim Emd.
Xm
22

---

Proof. First of all, we notice that, since (w, (4) > holds, and since (w,, 14) is expressed as in Equation (7). then, thanks to Lemma 4.4 we know that (w)(w) is the unique optimum of the Equation 7 In the rest of this proof, we will explicit the relationship between fúj and mi,, (w) Proof. Let us analyze:
d (Hamm 17 Em)
d' (aa.m. 17 Em)
fej(w, = inf Σ HER (E(1 MEM
Σ
Wa,m
+ wamm
Am
Am
inf gi, (wi pr, 17)
NER
At this point, we proceed by contradiction. Suppose that there exists $1.32 E argmingeR (w, 14, such that ø + z2. From the convexity of gis(w, (1) w.r.t 7,, know that any x E [22] belongs the argmin well. Furthermore, for all (22, since [i,(W, 14) > 0, at least one of the following condition is satisfied:
Wa.ar d(Ha,, 2) > O holds for some {i,}}
Aar
Wa.m
d(Ha, Em)Ra, (x) holds for some {i,j} and some fidelity M Am
Wa.m d(Ha,M km) Am
holds for some a E { and some fidelity m < M
[2], x22 are fixed points of the following Therefore, from Equation 288 we obtain that all Equation:
Eme
Em
was.o Am
(Ka,m (2r)
Merm (((
+ li m (2))
Muu -mm -Sm (((+tEm)
(29)
(Eue(,J) EM
Ha
Kaam (I) (1(x0tm) Emn) ka ma (x) v(atem)))
Am
At this point, notice that for any couple of different 31, By that satisfies Equation 29 there exists at least one arm a E {i,}} and one fidelity m < M such that at least one the following two conditions hold:
Fām o Ta,m((2
kam (Tz)) o ka (i2)
This however, is possible only for a finite number of points, while the interval [21 con- tains infinitely many optimal points. Therefore, there exists unique solution (w) argmin (w, μr, 1),, and, furthermore, it is a solution of Equation (29), thus concluding the proof.
Given this result, we continue by providing result how compute the derivative of fr, pu) whenever (is(w, (u) is given by Equation
Lemma C.3, Consider μ E 9KM and w E Aαхм such that fi.j p1) > 0. Furthermore, suppose that fig (w (1) is given by Equation 7 Then, for all {i,5} and all m E [M]:
0fs((.H1) dt dHaa,m Me + Em) + d (pi. nh Em)
Owa,m
Am
by writing (w,, pa vi. (w)). At this point, fix E {i.j} and m [M]. Then, it is easy verify from Equation (10) that both the right and left derivative of nh (w) w.r.t. wa, exists. Suppose for
23

---

moment that they are equal, then we have that (n),y(w) exists and continuous.
Therefore, we obtain
① fan (w, N4, (..((w)
ifi (w, ne Mi.s (w))
afu, (w, pe, (hs(ww) ) Oni (w)
Owo,m
Owa.m
Swa.m
Ofis (w, ,e No. (w))
Owam
dt (Hamm Thi + Em) + dt (Hamm Vai 5m)
Am
where in the second step have used that of Equation
(w, pe, Thig (w)) = 0 since ni, (w) is minimizer anj
0s
Similarly. whenever, the right and the left derivatives of ni (w) are differen we follow similar arguments, but analyzing left and right derivatives, and we will obtain an Identical result. Indeed, this does not introduce discontinuity issue in the derivatives of fij thanks to the fact that n. (W)) is minimizer of Equation (
At this point, it remains analyze in more detail the case in which we have that (w] is expressed as in Equation (6).
Lemma C.4. Consider μ E QKM and E ARXM such that fuj(w, p.) > holds. Furthermore, suppose that V > V.. Then, for each {i,5}, there exists unique minimizer va of Equation (6) which is the unique solution of the following equation of th:
Σ
Em=1=
M
Wa.m
(Kamm(t) (16)
Pu.m them o(w- Emm)
Ka Kamm m (b)) Mi -m.
Am
+
(30)
>
Waim
(kam((1) v(W-Em) + Ka ka, (v) (((+(m)))
mmml
Am
Proof. The proof follows by noticing that, for each a E j.. the optimization problem in Equation (6) is unconstrained convex optimization problem in vb. Taking the derivative and setting it equal to yields the desired result.
At this point, proceed by showing how compute the partial derivatives of fu, whenever it is expressed as in Equation (6).
Lemma C.5. Consider μ E @KM and w E AxxM M such that feg( pa) > Furthermore, suppose that 33 > v Then, for all m. E [M] it holds that:
0fi,(w,11 dt (Ma,m, v/ + Em) + dt (Na,m 1/ -mm
Owamm
2m
Proof. The proof is straightforward adaptation of the proof of Lemma C.3
Finally, we now ready prove our result on the sub-gradient of F(w,
Theorem 4.3. Consider μ E O and w E A such that F(w, u)) > 0 holds. Let (i, a) E [K]]
be a pair of arms that attains the max-min value in Equation ②
Then sub-gradient F u) of
Flw, (1) w.r.t to w is given by one of the two following expressions: for j {a, i} and m E [M].
a+ (Js..mm Vi. - Em) + (1ij.m Vi. + Em)
F((w,
if oh
(8)
VF(W, at (us,m, Uy - Emm + d' (pym V3 + Em)
otherwise.
(9)
Am
That sub-gradient FF μ)) is in all the remaining KM- 2M dimensions.
The proof follows by the definition of F(w, (1) together with Lemma 4.2 Lemma Lemma
Proof.
C,3 and
This happen, for instance, whenever (w)( Ba,m + Emn

---

We now show a sufficient condition for F(w, p)) > 0 to hold when μ E OKM. Lemma C.6. Consider le E @KM such that there exists * for which Mr.M >> maxa Pa.M M- Furthermore, consider AxM such that WiMM 0 holds for all i [K]. Then, have that F(w.pt p)) O.
Proof. From the definition of F, and the definition of *, we have that:
d(pmmm fp.,)
F(w. 10) 2 min ax* 0. MFE O.EMF
inf
Σ
Wim
Am
0 20,
(E(N,)) mc(M]
d(p,,M,))) x)
d(Ha...B)
min inf W., aff 92
Wa,M AM
AM
d(HA.M + Wa.M
d(po,M
min af*
inf
W..M
AM
Am
> 0,
where in the last step we have used the fact that J.,M > Ml.M for all i + *, together with Wi,M > for all i E [K].
Furthermore, show that the sequence of weights generated by Algorithm satiify wi,M >> 0 for all i [K]
Lemma C.7. The sequence of weights (a(()), satisfy wi, (1) 0 for all E [K] and for all t.
Proof. We begin by recalling the definition of (():
(t + +1) E argmax O++1
Σ w. ww.Cllp.(VF(@(ss,.) (VF(O()).
kl(w,, w)
WEANxM
==KM
From this definition, thanks to the property of kl, we have that aa.m (1) 0 for all E [K]. and all m E [M].
Remark C.8. It follows by combining Lemma C.6 and Lemma C.7 that F(w((), (a()) = 0 might happen only when there multiple best arms fidelity M. Whenever this condition is encountered, is possible to project the bandit model (i(t) to have unique optimal arm (e.g.. by adding a small 0 to of the optimal arms). When looking the proof of Theorem 4.1 we see that this does not impact its theoretical guarantees as (i) on the good event Er this does not happen, and, Lemma C.17 holds unchanged.
C.2 Smoothness of F(w, p1)
Lemma C.9. For any set S C GKM and any subset of arms A C [K], the function (w, 11) + infees EueA,mE(M]] Wa.m
me,, is jointly continuous on A AxxM x OKM
Am
Proof. We apply (a trivial generalization of) Lemma 27 of [3] The lemma in that paper is stated for set of alternative models, but the proof actually works for any set S. Likewise, it is stated for the case of Am = 1, but since it works for an arbitrary Bregman divergence d it applies to rescaled version as well. To deal with the restriction to a subset of arms A instead of all arms, we can view the function as function of (w Ax MM); (A),, where we restrict the vectors to the arms in A, and continuity of the original function is equivalent to continuity of the restricted version.
Lemma C.10. The function (w. (1) + F(w.pt 1)) is jointly continuous on AKXM X OKM
Proof. By definition, F(w. (1) infoes... EMEA Wa.m d(.m...Pa.m) for S.a {0 MMF | 0a.M 0.Ms and
max; minaşi fi,a fi,(w,, 44) with fu)(w.
Ai. = ai, Since a minimum of finitely many continuous functions is continuous and likewise for
the maximum, it suffices to show that each fia is jointly continuous. This is true by Lemma C.9 D
25

---

Corollary C.11. Let C' S @KM KM be a compact set. Then F is uniformly continuous on A X C.
Proof. The set AxxM x C is compact and F is continuous, hence it is uniformly continuous on that set.
Lemma C.12. Let E OKM, For all > O, there exists > O such that for all w E AK and all p' OKM,
[(W, u') - F(w, u)) Se.
S Kie
Proof. Take any compact ball B k) for the norm ||.
loc with x > centered at μ.. Then F is
uniformly continuous ΛкхM M B(J,, x) by Corollary C.11 This means that for any 0, there exists Kz > 0 such that for all (w', uu)) E Ax x (),,
|| 1/ N/2 A l|
1 l/ Skk
[F(w', F(w, n1) S
We can take ri= min n/)) to remove the condition μ' B(), The result of the Lemma is this for the special case w = w.
C.3 Correctness
In the following, we propose analysis the correctness which is based the concentration results provided in [22). We notice that these results are based on Gaussian distributions. Nevertheless, at the cost of more involved notation, it is possible to extend all the results of this work for canonical exponential families using, c.g., Theorem 7 in [19]
At this point, let consider the following value of 32,8
Bi, = log
K T
+ 2M log 4 1og
K
11 + 12M log (log(t) + + 2MC,
(31)
where Ö' is a universal constant (see Proposition I in (2 Then, we can show the following result. Proposition C.13. Let 0, then it holds that (a +*) S 6.
Proof. With probabilistic arguments we have that:
(a # x)
PM
3t 2 KM, # min (CC(), 2 BC,5) 571
Σ
KM,
min jFi
(C(t), ((t) 2 31.
17
PA (3t >
KM, (C(t,, 2 Bc,6)
x
Σ *
32 KM,
Σ Nk. (ea (B), Haym) 2 Be,8
KE (E( mE[M]
8,
where fourth step we have used the definition of Si,, and the last one Proposition in together with a union bound on K.
C.4
Auxiliary lemmas
This section contains auxiliary lemmas that will be used in the analysis of Algorithm
Lemma C.14. For all a & [K], m E [M], and all 2 1, it holds that No (t) 2 T Furthermore, it holds that:
Vi
In K KM).
Σ #(s) NOO
32ln(KM)VL
(32)
26

---

Proof. This lemma is simple combination of Lemma 3 in [2 with the tracking result of [5]. Using
algebraic manipulations, we have that:
Na (1)
am (8) Na.m (1)
Fa (8)
aa (8) - ll((KM
KM (I(KKM)
1 ln(KM)
KM
4
Vt
In(KM),
4K M
where, the second step we have used Theorem in (5) together with the fact that In (n(MM) 2 In(4)= 2 1.
For the second part of the proof, have that:
am (s) NN.m(t) $ Σ T'm (8) Nam (t) +2 Σ
s=1
ln(KM) + Vt
s 2lnKM)
Lemma C.15. Consider O and B such that C* (*²) B E > Then, there exists
constant C. such that, for
log (*) + 2M log (4 K
8 +1]
Ca.m(1 (T) max AnSCe,
Cole, (33)
C*(
it holds that:
BT,b
(²) -BZ
(34)
Ea,m Ca,m (T)
Proof. Let C. be a constant that depends on e such that, for T 2 C. it holds that:
12M log(log(11) +3) 2MC
S eT.
Amin
Then, for En,n Cam 2 Co(e, 8), we have that:
Br,s
log (45 + 2M log log (4) + 1) + 12M log(log(T)) + +3) + 2MC
Eam (T)
Eam Ca. (T)
log K + 2M log (4 (4) 11 +
Ea.m Ca.m (T)
< 0 (M)
B,
which concludes the proof.
27

---

C.5 Proof of Theorem 4.1
Before diving into the proof of Theorem 4.1 we introduce some additional notation. We denote with Bo (x, K) the ball of radius centered at Then, for all T. and e >> 0, we introduce the following event:
T n (a(t) E Boo (p, 12)(T)
(T)
where h(T) T1/4. At this point, present result. Furthermore, we denote with w() the vector of empirical cost proportions, namely, for all (a, m)) Wa,m (1) Eve(k) Zzeja Cl)
Ca.(())
First of all, we introduce initial result that controls the expectation of the stopping cost.
Lemma C.16. Consider B such that (H)))= - B e O, and suppose that there exists a constant T. such that, for all T N To it holds that F(w(T), ((T) 2 F(w" (μi) on the good event E (T). Then, it holds that:
Em(cT) S AMTe + Cole.)) +1
Σ P (E(T))))
(35)
Proof. Using probabilistic arguments, we have that:
E =
Pulcs > x)dx
AMT. Co(l,))+ + SAN JAMTT--GolE.))
Pulers Ir, 2 Co(e, 8))dr
SMM + Co(c,5) + -ANTTACOted)
Pu
PH
Pu(T
To>
I
Cr 2 Cole,)) de
Am
SMMT. c) +1+
Σ
Pu(TO > Cr, 2 Cole,
T=IT.+
Colua AM
+00
S AMTT. + Co(, + +1+
P (E(T))))
T=0
where (i) in the second inequality, we have upper bounded Cra I AM (ii) in the third inequality, have used the fact that ть is an integer variable, and (iii) in the last inequality that for all T 2 T. such that Ea.,. Ca. 2 Cole, 8), then we have that ((T) S {Ta < T). Indeed, combining Lemma C.15 with the definition T., we obtain that for all T 2 T. such that Eam Ca, (T' 2 Cu(e, d), then we have that E(T) S {TB < T}. This last step is direct by noticing
have used
that (T) (TT) 2 Za.m Ca.m (T) implies stopping.
AT
Lemma C.16 shows how to upper-bound the expected cost complexity. Notice that this result requires different arguments w.r.t. the usual ones that appears while controlling the expected sample complexity (see, e.g., ()).
Then, report a basic property of the sub- gradient ascent routing that is employed in our algorithm. Before doing that, we recall that, on the good-event Er, it holds that there exists a constant L, that depends μl, such that the empirical sub sub-gradients are miifoomll--boundee
by L.
Lemma C.17. Let ē(t) Eam Ta (s). Define C, = log( (M) + KMG + 4(LAm)) + 2G2. and consider the sequence of weights (t)) generated by Algorithm | E, (T) it holds that:
Then, on the good event
T Σ (=)(t)
(()VF((> (w- -0(1))))))) C.VT.
28

---

Proof. The proof is identical to the one of Proposition 3 in [22]. The only difference is that, in our case, we need to multiply the scale of the sub-gradient by AM. the additional presence of ē(t) in the sequence of gains that we use in our sub-gradient ascent algorithm.
Finally, we show that there exists an additional problem dependent constant Cp that will be useful in performing some upper-bound reasoning in the proof of the final result.
Lemma C.18. Consider the following quantity:
minafs info., EMF E Eiettaat Em (s) de,m)
Eam Cam
There exists problem dependent constant Cp such that the previous equation be upper bounded by:
F(w(T), H)+ + 4n(KM))MMMCH
Amin VT
Proof. Let begin by analyzing (T), M)). Fix such that F(w((T), fa,a(w(T)) μ). More- over, consider 0,, Oa E argmin Eie(,,a) Em Wamm (T) dijta 8a.m) difference:
Am Then, consider the following
minagt infe
Ex Eie(na) Em Tsm (s)d(ss)) 0im) ([w(T), p.).
Ea,m Ca.m (T)
Then, the previous Equation can be upper bounded by:
Eie(na)) Em (ETH Ts.m (8) (T) d(pi.m m)
H 5
Eam (T)
Eiethay Em dipumm 07
$ 22h(KM) VT
Eam (T)
41(KM))MTCC Ea,m Ca,m (T)
where in the first step, have used the definition of 0% 0 and the definition of wT),, in the second one, we have used Lemma CC14| and in the last one the facts that, thanks to definition 0 0 there exists some problem dependent constant Cμ such that d(pa, ()))) is bounded.
Theorem 4.1. For any multi-fidelity bandit model μ MME. Algorithm 7 Juiin the threshold Br,5 given in 31 is 8-correct and satisfies
Ey(crel log(1/0)
lim sup 8-30
< (²)))..
(5)
Proof. The proof of the ~-correctness is from Proposition C.13
To prove the optimality, we first proceed by upper bounding the following quantity on the good event E, (T):
F(w", 11) - F(W((T)) ((T)).
(36)
29

---

Define, for brevity, T = T h(T) + and ē(s) = Eam Ammam (s). Then, we start by analyzing
F(w", ()). On (T) we have that:
Lam Cam (T)
Ex=rd(s) 2(s)
Ei) ((s) F(w". 11)
F(w", .1)
F(w=", .11)
(+) Eam Com
a,m (T)
Ea, Cam
$ s=1 ((s)
F(w"; :K) 2In(KM)VT
F(w"", + Σe, Lam Ca, (T)
Cam (T)
En s=ml ((s)
F(w",,M) + 2ln(KM)F(W.... 1
a.m Cam (T)
Amin VT
B(T) d(S)
F(W"" (p) + h(T)
F(w" (4) + F m
am Ca.m(T)
Amint
Amin VT
E hTT)
Aa
h(T)
2l((KM)F(w'.. 11)
+
Flw" 1) +
Eam a.m (T)
Amin T
Amin
Amin VT
where in the first inequality we have used Lemma C.14 while in the last step we have used Lemma
C.12 together with the event & (T). At this point, we focus our analysis on E ((s)F((" f(t))
Ea,m (T.
Define, for brevity, Io = ((s)V (())); then, we have that: E. h d(s) (F(w", =
Exenery ((s)F(wW, (s))))
Ea,m Ca.m (T)
Eam (T)
Σ M(T) 0(s) (())) ((s)))
Σx Lim Io (w--6(s))
Ea, Cam (T)
Ea,m Cam (T)
MT) ((s)) ((()))
C2
Eam (T)
Amin VT
Ex=h(r) (L)
T
C₁
AMTT
Ea,m Ca, (T)
Amin
VT
Amii T
where in the first inequality have used the concavity of F, in the second one we have used Lemma C.17 and in the last one Lemma C.12 the definition of (T).
Finally, we have that:
Et ((s))((()) Σ. minaz. infe. 0. EMP Eie(n,)) Em it.m (s) a) Eam Ca,m(T)
Eam (T)
minaz, info,.0. EMF Σ Eistho Em tim (s)(())( a..))
Eam (T)
$ F(w((T), + 4ln(KM)MC Amin VT < (T)) + 4ln(KM)MC, 6,
Amin
where (i) in the first equality we used the definition of č(s), (s) and F, in the second one we used Lemma C.18 and the last one Lemma C.12
Given this analysis, let us define:
By = 2AM7e
((T) F(w". .u)+ + 2ln(KM)F(W>,. ,1)
Aminn
Aminn T
Amin I
C₁
4ln(KM)MC, +
+
Amin VT
Amin VT
30

---

Consider 7' such that:
{ (2)
( )²
Cr
(4 (A
}}
T's max
Te.
A
Amnin
Aminn
Then, it holds that:
2dMse
Br
+ be Be:
Ami
and, consequently, we have that Combining this result with Lemma C.15 and C.16 we obtain:
(T) ((T)) 2 F(w", (i) - Be.
+00
Crg] S AMT. + Co(d, + + Σ (1)).
By Lemma and
and Lemma 19 in 8 we obtain that:
E(Cr.] log(1/6) (²(p)-1-
lim sup 6-20
Letting + 0 concludes the proof.
D Experiment details and additional results
In this section, we provide experimental details and additional results. For the experiments relied on a server with 100 Intel(R) (R) Gold 6238R CPU @ 2.20GHz cpus and 256GB of RAM. The time obtain all the empirical results is less than day.
This section is structured as follows.
First, provide an additional details and results the experiment presented in Section (Section D.I and Section D.2).
Secondly, we provide results on additional 4 x 5 multi-fidelity bandits (Section D.3
Then, we analyze typical trick that is used improve the performance of gradient-based methods, that is using a constant rate against using the learning rate that the theory prescribes. (SectionD..4)
We then present results using very small value of w.r.t. to the one that has been considered in the main text (Section D.5). In particular, we verify that the performance difference amplifies.
Finally, we discuss the approaches of 31
D.1 Further details on the experiments presented in Section
First instance We begin by providing further details on the 4 x multi-fidelity bandit model that we used in Figure and Figure 2
First, Table reports the bandit model of Figure [
Table 2: Multi filti-fiielity bandit model presented in Figure
Ai
142
μ43
A
1
0.9465
0.8526
0.8162
0.9099
0.1
0.05
m 2
0.7727
0.8708
0.9050
1.0594
0.08
0.1
3
0.8812
0.8515
0.8209
1.0083
0.05
0.2
m 4
0.8284
0.8374
0.8353
0.9745
0.025
0.4
5 0.8494
0.8401
0.8495
0.9856
0.0
5
arms, both for the bandit model of Figure D and 2 are Gaussian distributions with variance
2² = 0.1. The bandit model in Figure has been generated according to procedure that has been
31

---

used to generate MF instances in 25 (see their Appendix D.I). Specifically, first, two M --dimensional vectors are specified, which we refer to as a and Specifically, and b are such that am 2 am and bn. 2 1m for all E [M 1]. Then, we first sample the means of the arm at fidelity M
and once this is done we sample Hi,m E [Pa.M am 2 Mi.M + am + 2 Then, & is computed
as S.. Om bm. In this sampling procedure, we have used [0.075, 0.06, 0.04, 0.02, 0] and
0 b = [0.05, 0.04, 6.02, 0.01,
Second instance
We now recall the x 2 example of Section 5
Table 3: Multi fudti-fidelity bandit model presented in Figure 2
f41
μ42
J43
[41
[A5
5
m = 1
0.4
0.4
0.4
0.4
0.5
0.1
0.5
2
0.5
0.5
0.5
0.5
0.6
We prove that, in this instance, the oracle weights are given by w = [0.09621. .0 for all E [4], and w = [0, 0.61516) (this number have been rounded to the fourth decimal precision). In order prove this, we first notice that in the considered domain the optimal fidelity for i E [4] is m = 1. This is direct from the fact that pim H4.M Em (see, c.g., Proposition B.5). Furthermore, we recall the expression fi,5, for any i E [4]:
d' (15, + Em) + Ws.m
dt (Hi, 1) Em)
fs,((w, 14)
inf VElMs, Ms. Arl
Σ ME[M]
Wa.m
Am
Am
Then, since n E [un Ms. Pr.M = Ms.. = Ms.M - Em. we have that the optimal fidelity for arm 5 is 2. At this point, consider the oracle weights w* We notice that, due to the symmetry of the problem, w;, equal for all i E [4]. Then, we can rewrite fa.i(w,, (1) as a function of single variable, that is:
d (M5,2, 17) + W1,1
d' (ti,1, 17 - Em)
fs.(w. inf nelu Ha,
(1 - (1-4w;,1)
Am
Am
and, consequently, obtain that C* (M) can be expressed convex optimization of a single variable, that W;,1- Taking the derivative F(w,, v1) w.r.t. Wi,1 we obtain that the following equality should be satisfied at the optimum:
d(pi,M Th.s) d(p;,1 n5, - 1)
AM
Am
Solving for vi.s gives unique solution in the range [0.5, 0.6). which is 0.539. Then, using Lemma C.3 and solving for wi,1, obtain 41,1 0.09621, and consequently, W5,2 0.61516.
Thresholds To conclude, we comment on the thresholds Br.5 used by the algorithms. For the stopping rule in MF-GRAD of its theoretical value 31 that retains the same scaling in K and M (up to constants). In GRAD, we used Br,8 = log( (K/8) /8) + log(log(t) (t) + 1), which is a similar simplification of the usual threshold for BAI, which instead of concentrating a sum of 2M KL terms (see the proof of Proposition CC13) only requires to concentrate sum over 2 KL terms. Finally, in the confidence intervals that are used in
used $t,5 log (K/) M log(log(t) +)) which is simplification
which compared their original form is replacing some crude union bound over with a stylized version of the threshold that would follows from using tight time-uniform concentration. These choices were adopted consistently in all the experiments presented in this appendix, and they ensured the 8-correctness requirement in all cases.
IISE we have used the confidence bonuses
20o2( K KM/5) (lg//o)
Na.
For step, we constrained the minimum gap hetween arms fidelity M is at least 0.1. "Notice, indeed, that ISEE requires union bound both K and M.
32

---

D.2 Empirical cost proportions of MF-GRAD
In this section, we analyze the behavior of ME-GRAD by analyzing the evolution of the empirical cost proportions. Specifically, repeat the x 5 bandit model of Table the same experiment that we presented in Section the x 2 bandit model. Figure Seuurerrepue reports the result. Interestingly, we highlight how the sparsity pattern emerges also in this domain.
D.3 Results on additional domains
In this section, present results additional 4 5 multi-fidelity bandit models. Specifically, generate another random instance according to the procedure [25], and we report the model in Table 4 Furthermore, we created an additional bandit model where means of some arms are slightly increasing on displaying a stationary trend over fidelity and we report the model in Table both cases, considered Gaussian distribution with o² 0.1. Empirical results of ME-GRAD, ISE and GRAD for = 0.01 can be found in Figure and 6 respectively. As we can appreciate, ME-GRAD maintains the most competitive performance across both domains.
Table 4: Additional random multi-fidelity bandit model.
P1
μ4
À
1
0.6944
0.5080
0.4153
0.3564
0.1
0.05
m = 2
0.5634
0.3723
0.4132
0.4570
0.08
0.1
m 3
0.6178
0.4322
0.3817
0.4065
0.05
0.2
m = 4
0.6323
0.4225
0.3838
0.3582
0.025
0.4
m 5
0.6171
0.4216
0.3831
0.3783
0.0
1
Table 5: Additional multi culti-fidelity bandit model.
μ4
P22
μ33
μ4
{
0.41
0.35
0.51
0.41
0.1
0.1
m =
0.45
0.37
0.56
0.39
0.08
0.125
0.47
0.38
0.64
0.40
0.04
0.25
m 0.48
0.36
0.62
0.42
0.02
0.5
m 0.5
0.35
0.61
0.42
0.0
1
D.4 Improving performance with constant learning rate
As reported in [22], using constant learning rate can improve the identification performance in standard BAI settings. the following, we analyze the performance difference ME-GRAD that uses the theoretical learning rate, and MF-GRAD that uses a constant learning rate of a 0.25. We will refer this second version as MF-GRAD-CONST. Figure see, in both cases, MF-GGRAD-CONT
and and reports the performance of the
algorithms in the two bandit models of Section As outperforms MF-GRAD.
We further investigate this behavior by showing the evolution of the empirical cost proportions of MF-GRAD-CONST during the learning process. Figure 9 and 10 reports the evolution of the empirical costs, over 100000 iterations. Comparing the results with Figure 2 and as
Jnd [ewe can appreciate move away from the initial cost proportions way sooner than MF-GRAD, which explains its superior performance in the moderate regime of 6.
D.5 Smaller value of
Finally, we repeat the experiments that we presented in the previous section using smaller values of 8.
Specifically, we consider 10-10 Figure 11 reports the performance of the x bandit model of
Section 5 Figure 12 reports the performance of the 5 x 2 bandit model of Section 5] Figure 13 and reports the performance the additional bandit models presented in Appendix D.3 As one can notice the performance gap between MF-GRAD and the considered baseline increases.
33

---

0.4
Empirical Cost Proportions
0.3
0.2
0.1
0.0
20000
40000
60000
80000
100000
Iteration Number
Wo.0
W1,0
W2,
W3.0
W0.1
W1, 1
W2.1
W3.1
W0,2 2
W1,2
W2,2 2
W3,2
W0.3
W1,3
W2.3
W3,3
Wo,4 4
W1.4
W2.4
W3.4
Figure 4: Empirical cost proportions of MF-GRAD for 100000 iterations on the 5 2 bandit model of Section Results are average over 100 runs and shaded area report 95% confidence intervals. Empirical cost proportions of each plotted with the color. Cost proportions fidelity 1, 2, 3, 4 and visualized with circle, squared, cross, triangle, diamond respectively.
125
K20
190
Complextty
Complexity
600
450
200
GRAD
MF-GRAD
USE
GRAD
MF-GRAD
UISE
Figure 5: Empirical cost complexity for 1000 runs times with 5 = 0.01 on the multi-fidelity bandit of Table
Figure 6: Empirical cost complexity for 1000 runs times with 5 = 0.01 on the multi-fidelity bandit of
Table 5
34

---

100
140
1200
Compleutt
120
Cost Curplesity
1033
000
MF-GRAD
NF-GRAD
MF-GRAD
MF MF-GRAD-CONE
Figure 7: Empirical cost complexity for 1000 times with 5 0.01 the x multi-fidelity bandit Section
Figure 8: Empirical cost complexity for 1000 runs
times with 0.01 the x multi-fidelity bandit
of Section 5
0.35
0.30
Empirical Cost Proportions
0.25
0.20
0.15
0.10
0.05
0.00
20000
40000
60000
80000
100000
Iteration Number
Wo, 0
W1,0 0
W2,0
W3, 0
Wo,
W1,1
W2,1
W3,
Wo.2
W1,2
W2,2
W3,2
W0.3
W1,3
W2,3
W3,
Wo.4
W1,4 4
W2,4 4
W3,4
for 100000 iterations on the x bandit model of Section 5 Results are average over 100 runs and shaded area report 95% confidence intervals. Empirical cost proportions of each arm are plotted with the same color. Cost proportions at fidelity 1, 2, 3, 4 and 5 are visualized with cirele, squared, cross, triangle, and diamond respectively.
Figure 9: Empirical cost proportions of MF-GGAD-COOME
35

---

0.6
Empirical Cost Proportions
0.5
0.4
0.3
0.2
0.1
0.0
0
20000
40000
60000
80000
100000
Iteration Number
Wo.0 0
W1,0 0
W2, 0
W3,0
W4,0 0
Wo,1
W1,1
W2, 1
W3,
W4, 1
Figure 10: Empirical cost proportions of DE-GRRA-COONS for 100000 iterations the 5 x 2 bandit model of Section Results average 100 and shaded report 95% confidence intervals. Empirical cost proportions each arm are plotted with same Cost proportions fidelity are visualized with cirele and squared respectively.
0000
Complexty
Cost Complesxiy
6000
6000
250
1900
GRAD
MF-GRAD
USF
GRAD
MF-GRAD
USE
Figure 11: Empirical cost complexity for 1000 runs times with 10 10 the x 5 multi-fidelity handit of Table
Figure 12: Empirical cost complexity for 1000 runs times with 8 10 the 5 x 2 multi-fidelity bandit of T'able
36

---

400
Complexby
1500
Complextt
330
230
2000
130
140
Figure 13: Empirical complexity for 1000
Figure 14: Empirical cost complexity for 1000
times with 10 on multi-fidelity bandit of Table
times with 10 multi-fidelity bandit Table S
D.6 LUCB-ExploreA and LUCB-ExploreB
In this section, we present in detail the main issue behind the algorithms presented in 31 i.e., LUCBExploreA and LUCBExploreB, that is the fact that these algorithm might fail at stopping in some specific multi-fidelity bandit models. First, we provide numerical evidence of this phenomena by running both methods a specific instance (Section D.6.1). Then, in Section D.6.2, we point out error in the analysis of [31] that highlights how both algorithms fails stopping when considering instances such as the one that has been considered in Section D.6.2
D.6.1 Experimental issues
When experimenting with the algorithms proposed [31. namely LUCBExplore and LUCB- ExploreB, have faced stopping issues. Specifically, both algorithms were not terminating in any reasonable number of steps on some specific instances. We now report an illustrative example of such scenarios. Consider the following Gaussian multi-fidelity bandit model: μn [0.64, 0.6), ju2 = 0.46, 0.5), À = 10.1, 5). = 00.1, and x² = 1. In this scenario, the well-known LUCB algo- rithm [2] which only uses samples fidelity M, stops soon (iteration 100k) paying a total of roughly 500k. When running LUCBExploreA and LUCBExploreB, instead, we faced termination issues. We let both algorithms run for maximum number of 10 samples (reaching total cost which is approximately 10?), and the stopping criterion was never met for LUCBExploreA, while 70% LUCBExploreB runs did not stop. LUCBExploreB explores more fidelities the beginning. and that initial exploration can be enough to trigger the stopping test some runs, but many continue until we artificially stop the experiment. Figure 15 reports the results of this experiment.
As a final remark, we notice that both LUCBExploreA and LUCBExploreB require additional knowledge in order to run, that is upper bound on ji.M and lower bound μ22 (assuming arms to being ordered according to 11,M >> P2.M 2 ... 2 (K,M). The result presented in this section have been presented running their algorithms in the most favorable scenario, that is the situation in which the agent has perfect knowledge on the values μ1,M and μ2.M.
D.6.2 Theoretical issues
The general idea of the LUCBExplore algorithms of 31
is to identify for each arm the "optimal fidelity" and pull the arm at that fidelity. Appendix B.5 we described how that "optimal fidelity" can differ from the fidelity selected by our lower bound. S Since our lower bound can be matched by an algorithm and thus describes the actual cost complexity notion of optimal fidelity. We will thus call the fidelity used by the LUCBExplore algorithms target fidelity instead. The two variants ExploreA and ExploreB differ the mechanism used to look for the target fidelity.
the problem, it betters represent
37

---

1.0
Cost Complexity
0.6
0.4
LUCB
LUCBExploreA
LUCBExploreB
Figure 15: Visualization non-stopping behavior of LUCBExploreA LUCBExploreB.
We first show that even if their algorithm used an oracle for the fidelity exploration mechanism that returns the target fidelity for all arms, it would still not be able stop some examples. We then highlight an issue with the proof of [1
Failure to stop with an oracle Consider the bandit instance from Appendix B.5 Recall that this is
2 2 example of multi-fidelity BAI problem with & = 0.1, & = 0.0, M1.M 0.6, 11,m = 0.65, M2,M = 0.5, 12.m 0.45 (we write M = 2 and
1). All distributions are Gaussian with variance 1. We choose Aas > 4Am, which means that the target fidelity for that problem are m
and m² 1 (see details in Appendix B.5). LUCBExplore with oracle that always selects that fidelity is the following algorithm:
Initialization: f (t) 0, NN.m = 0. UCB (t), 0 for all arms & and fidelity m. & = u4 2.
While LCB,, (1) S (UB.,(())
4 = arg max (C)B((), = arg max UCB;(()
Pull arms l, and u, at their target fidelity.
Output l
The indices are
LCBa(t) max (p (t) Em (t),
m
UCB min (px. (t) Em + B(Nk. (t), 5))
where 8(n,t,5) = /loo(Ltt/// /8)/n for some constant L > 0.
In the two-arms example here, the algorithm simplifies greatly: it always pulls both arms alternatively, always at fidelity m 1. It stops when the LCB of one arm surpasses the LCB of the other.
We show that it can't stop and return the best arm 1, unless confidence interval is not valid, which happens with small probability. If (t) & f1,1 + (t),
IC (1) max (1) E1 - -(t/2,,,,
$ -
0.55.
38

---

On the other hand, if min(1,/2,.1()) 2 P2,1 -
8(t/2,t,,),
UCB2(11) = min((1,/2,10)) + + + -(tt222),,
2 12,1 +
= 0.55
We get that we always have I,C (t) S UCB)((), unless one of the two concentration inequalities on the empirical means are not true. The confidence width /8 is designed to make those inequalities true for all E N with probability close to We can similarly get that LC B2(t)) Σ B (which expected since 2 is worse arm) unless some concentration inequality is false.
We obtain that this algorithm with an oracle selection for the target fidelity cannot stop fast: the only way it can stop is if unlikely deviations occur.
Issue with the proof There is an issue with the proof of the cost complexity upper bound of [31]. The issue is in the first 3 steps of their appendix E.2, pages 17 and 18. They identify threshold c (with value 0.55 our example of the last paragraph) and prove the following.
Step 1: if the algorithm does not terminate and confidence intervals hold, then either both LCB,, (t) S and UC (t) 2 or both LC L,, (t) I and UCBu, (t) 2 c.
Step 2: confidence intervals are likely hold.
Step 3: if sub-optimal arm k satisfies LCBB(tt and UCB:(t) 2 c, then its target fidelity cannot be pulled much.
They conclude that for all arms, the number of pulls at the target fidelity is upper bounded, with large probability.
Let's see the issue with that proof, on the same example in the last paragraph.
In the example above with the oracle choice for the target fidelity, hold and & 1 (which is the most likely), then LCB,, (1) S e and UC (l) 2 c. That is, step gives condition on arm 1 only (and nothing on arm 2). But then we get nothing from step 3, since arm 1 is not sub-optimal arm.
saw that if confidence intervals
We only get upper bound the number of pulls for sub-optimal arms if satisfy BC (t) S and (t) 2 c at some point, but it might not be the case. Indeed, when the algorithm does not terminate, steps and together give that with large probability either both LCB,,() (t) < and (C, 2 c or both LCB., (t) S and U.B,,. (f) 2 c. It is possible that we always have this property for l (the optimal arm), and that we can never apply step 3.
say that they
39

---

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:
Claims and introduction reflects the contribution and content of the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to 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:
We discuss limitations and future direction of improvements in Section
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 are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on 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 images are taken in low lighting. Or speech-to-text system might 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 faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in 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.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
40

---

Justification:
Each statement presented in the main text is supported with formal proofs presented in the appendix.
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 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 be 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 of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Our algorithm described in mathematical rigor so that it can reproduced. Furthermore, codebase and detailed instructions on how to reproduce the result is provided.
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 make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all 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 new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is 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).
(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 possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
41

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
We provide the codebase with instructions on how to reproduce the results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
//nips.c... cttpsscccpppccc///ceeceeeccccccc htapa///guddeee/eeeeebiiissssss /ac////oddbiisssseeeeeee swisssoiicyyyyyyccooooooclcpiipp for more details.
The authors should provide instructions on 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. If 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 the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
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 understand the results?
Question:
Answer: [Yes]
Justification: Experiments have been detailed in Appendix D Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: All results average of 1000/100 runs. Error bars reported in all cases (e.g., depending on the experiment, via boxplots and 95% confidence intervals).
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, 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 with given experimental conditions).
42

---

The method for calculating the error bars should be explained (closed form formula, call 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.
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 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 out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in 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 on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Computational resources employed in this study are reported in Appendix D Time taken to re-run all the experiments is also reported.
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 compute required for each of the individual experimental runs well 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 into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the htt.aiiieeehiesuueeeeeeeee..e.ee
NeurIPS Code of Ethics htttps:/nneurps
Answer:
[Yes]
Justification: The paper aligns with the guidelines (e.g., does not involve human participants nor datasets) and anonymity the submission is preserved.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper is foundational research work whose goal is advance theoretical aspects of sequential-decision making. We do not any direct path to negative applications.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
43

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess 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 out 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 generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used 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 unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper does not involve such assets.
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 to usage guidelines or 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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
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?
Question:
Answer: [NA]
Justification:
The paper does not rely on existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, 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 use in package should be provided. For popular datasets, paperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
44

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
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:
[Yes]
We provide the codebase together with instruction on how to reproduce the experiments.
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the datasct/code/model as 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 used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
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 details about compensation (if any)?
Question:
Answer: [NA]
Justification: No crowdsourcing experiments and research with human subjects were in- volved this work.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information 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 the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: 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?
Answer: [NA]
Justification:
No study participants were involved in this work.
Guidelines:
The answer NA means that the paper does 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 we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
45

---

For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
46


Reviews:
[{"review_id": "mMOSOwEv0K", "reviewer": "Reviewer_bSBL", "summary": "The paper studies the problem of multi-fidelity best arm identification in the fixed confidence setting. The main contribution is an instance-dependent lower bound on the cost complexity. The authors demonstrate the bound's tightness by providing an algorithm with a matching upper bound in asymptotics, as well as an instance where the lower bound improves on the previous lower bound by a tighter constant.", "questions": "Do the authors have any conjectures on the fixed-budget setting for multi-fidelity best arm identification? I'm not entirely sure this is a valid problem, but I wonder if it could be approached similarly to the normal track-and-stop method. By solving the optimization problem and sampling according to it without a stopping rule, it naturally turns into a fixed-budget algorithm. Can MF-GRAD be used in a similar manner?", "limitations": "No major limitation to me.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well-presented in terms of its theorem statements and comparison with prior works. The theoretical result, specifically the lower bound, shows a clear improvement over previous work.", "weaknesses": "I think there is room to improve the presentation of the algorithm. Just by staring at the algorithm box, it took some time to understand the relationships between $\\tilde{\\omega}$, $\\bar{\\omega} $, $\\tilde{\\pi}$, $\\pi'$, and have to look for their definitions here and there. It would be great if these could be made clear within the algorithm box itself.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> ### Writing suggestion\n\nWe thank the Reviewer for suggesting ways to improve the presentation of our algorithm. We have incorporated the symbols also within the algorithm box in a revised version of the manuscript.\n\n\n> ### \"Do the authors have any conjectures on the fixed-budget setting for multi-fidelity best arm identification? I'm not entirely sure this is a valid problem, but I wonder if it could be approached similarly to the normal track-and-stop method. By solving the optimization problem and sampling according to it without a stopping rule, it naturally turns into a fixed-budget algorithm. Can MF-GRAD be used in a similar manner?\"\n\n\nWe thank the Reviewer for rising this point. We do believe that the fixed-budget MF-BAI is actually a valid problem that should deserve the attention of the community. In this case, the **budget should be expressed as a total cost available** to the learning system, and the agent might exploit the different fidelity to lower (an upper bound on) the probability of error of not recommending the optimal arm.\n\nAlthough this future research direction is of interest to the community, we currently conjecture that **further and ad-hoc algorithms are probably needed** to face the fixed-budget problem. Indeed, to the best of the author's knowledge, fixed-budget algorithms usually follow different design principles compared to asymptotically optimal fixed-confidence ones. One of the main reasons behind this conjecture is that we expect the lower bound for the fixed-budget setting to differ from the one for fixed confidence. \n\nFinally, we agree that one could in principle apply MF-GRAD for fixed-budget problems as suggested by the reviewer (i.e., by removing the stopping rule and terminating when the budget is over). However, we are unsure on which kind of theoretical guarantees this approach would enjoy.", "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": "", "extra_scores": {}}, {"review_id": "39Rkyu6GGb", "reviewer": "Reviewer_97EK", "summary": "This paper considers the fixed confidence BAI problem in a multi-fidelity setting, where each arm can be sampled at lower or higher fidelity levels, with a corresponding lower or higher cost. The objective is to declare the best arm, which is the arm with the highest mean at the highest fidelity level. \n\nThe authors derive an instance dependent cost lower bound, in terms of optimal sampling frequencies at each fidelity level for each arm. They then propose a sub gradient based algorithm with forced exploration that is asymptotically optimal in terms of cost.", "questions": "I don't see any shaded area denoting confidence intervals in Figure 3.\n\nLine 78: notation.", "limitations": "No concerns on social impacts", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper makes non-trivial technical contributions to the state of the art in multi fidelity BAI. The measure-zero result in Theorem 3.2 seems novel and interesting. The \"achievability\" part is also novel, in the sense that it is not an extension of traditional track and stop. It uses a sub gradient ascent algorithm (which has been used in bandits before), but the gradient computation section in 4.2 also appears potentially useful in related problem settings.\n\nAppendix B.2 shows that the lower bound in [26] can be significantly worse (by an arbitrarily large multiplicative factor) than the proposed lower bound.\n\nIn appendix D.6, the authors also identify a problem of \"non-stopping\" from [33], both numerically and analytically.", "weaknesses": "I do not see any issue that can be flagged as a significant weakness.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> ### I don't see any shaded area denoting confidence intervals in Figure 3.\n\nWe thank the Reviewer for raising this point. There are actually shaded areas on the plot, but the confidence intervals are really small. This is also evident from footnote 8, where we measure the distance of ${\\omega}(T)$ from $\\omega^*$ at iteration $T=10^5$. In this case, the 95% confidence intervals are $0.0006$. \n\nThe appendix presents experiments with more evident confidence intervals  (see, e.g., Figure 4).\n\n> ### Line 78: notation.\n\nWe thank the Reviewer for pointing out the typo. We have fixed it in a revised version.", "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": "", "extra_scores": {}}, {"review_id": "YTSuksGaPi", "reviewer": "Reviewer_7qou", "summary": "This paper introduces qPOTS (Pareto Optimal Thompson Sampling), a novel approach for efficient batch multiobjective Bayesian optimization in the context of best-arm identification (BAI) with multi-fidelity bandits. The authors present a tight lower bound on the cost complexity of multi-fidelity BAI and propose an algorithm that asymptotically matches this bound. The method combines ideas from Thompson sampling, Gaussian process surrogates, and evolutionary algorithms to address challenges in multiobjective optimization with expensive oracles. The paper provides theoretical analysis, including convergence guarantees, and demonstrates empirical performance on synthetic and real-world problems.", "questions": "How does this work relate to broader multi-fidelity Bayesian optimization problems? Can the authors elaborate on potential extensions or applications beyond best-arm identification?\n\nCan the authors provide more intuition or examples of how the theoretical results help in understanding real-world multi-fidelity optimization problems?\n\nTheorem 3.1 states that the lower bound holds for any multi-fidelity bandit. Does this truly hold regardless of the specific multi-fidelity model or acquisition function used? If so, could the authors elaborate on why this is the case?\n\nHow realistic is Assumption (5) in Theorem 4.1? Can the authors provide examples of scenarios where this assumption would or would not hold, and discuss the implications?\n\nThe gradient computation with respect to ω and μ is not entirely clear, especially given that these are often discrete values in bandit problems. Could the authors provide a more detailed explanation of how these gradients are defined and computed, ensuring clarity and precision in the notation?\n\nHave the authors considered applying their method to more complex real-world applications, such as neural architecture search or other MFBO problems that can be framed as BAI? If not, what challenges might arise in such applications?", "limitations": "The paper could benefit from a more thorough discussion of the scenarios where the assumptions might not hold and the potential implications for the algorithm's performance.\n\nThe authors should provide more context on the limitations of the best-arm identification framework compared to more general multi-fidelity Bayesian optimization problems.\n\nA discussion on the potential challenges in applying the method to more complex, real-world problems would be valuable.\nThe paper would benefit from a more comprehensive discussion of the potential negative societal impacts of the work, even if they are indirect.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "Theoretical contributions: The paper presents a tight lower bound on the cost complexity of multi-fidelity BAI, which improves upon previous bounds in the literature. This provides valuable insights into the fundamental limits of such problems.\n\nAlgorithm development: The proposed qPOTS algorithm is designed to asymptotically match the lower bound, potentially offering optimal performance in the high-confidence regime.", "weaknesses": "Limited experimental evaluation: The experiments seem relatively limited in scope, focusing primarily on synthetic problems and a few real-world examples. More extensive testing on diverse real-world applications, such as neural architecture search or classic multi-fidelity Bayesian optimization problems, would strengthen the paper's practical relevance.\n\nConnection to real-world problems: While the theoretical results are impressive, it's not immediately clear how they translate to understanding or solving real-world problems. More discussion on practical implications would be beneficial.\n\nAssumption realism: The paper relies on some assumptions that may not always hold in practice. For example, Assumption 5 in Theorem 4.1 (asymptotic convergence) may not be realistic in all scenarios. More discussion on the implications of these assumptions would be helpful.\n\nNarrow problem focus: The best-arm identification problem, while important, may be seen as somewhat limited compared to more general multi-fidelity Bayesian optimization problems. The authors could elaborate more on how their work relates to or extends to broader MFBO settings.\n\nGradient computation clarity: The explanation of gradient computation with respect to ω and μ could be clearer, especially given that these values are often discrete in bandit problems. More detailed explanations and precise notation would improve understanding.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> ###  \"Narrow problem focus\" and comparison of MF-BAI with MFBO \n\nFirst, we note that the **multi-fidelity BAI is an established problem within the literature** (i.e., \"Multi-fidelity best-arm identification\", Poiani et al., NeurIPS 2022, and \"Multi-fidelity multi-armed bandits revisited\", Wang et al., NeurIPS 2024).\n\nFurthermore, we note that our work on BAI **differs** from MFBO studies in at least the two following dimensions (similar comments have already been made in e.g., \"Multi-fidelity Best-Arm Identification\", Poiani et al., 2022):\n1. First, we only use a minimal assumption on the arm space, that is $|\\mu_{i,m} - \\mu_{i,M}| \\le \\xi_m$ for all arms $i \\in [K]$ and fidelity $m \\in [M]$. On the other hand, works on MFBO (e.g., \"Gaussian Process Bandit Optimisation with Multi-fidelity Evaluations\", Kandasamy et al., NeurIPS 2016, \"Multi-fidelity bayesian optimisation with continuous approximations\", Kandasamy et al., ICML 2017, \"Multi-fidelity Gaussian Process Bandit Optimisation\", Kandasamy et al., JAIR 2018) typically impose stronger structural such as Gaussian Process modeling. \n2. Secondly, these lines of work usually analyze the simple/cumulative regret. Our paper, instead, aims at minimizing the cost complexity. As one can verify, this has a significant impact on the algorithm design and its theoretical analysis. \n\nFor these reasons, we retain that our work is **different** (rather than less general) w.r.t. MFBO approaches. We will better clarify these differences in a revised version of the manuscript.\n\n> ### \"Can the authors provide more intuition or examples of how the theoretical results help in understanding real-world multi-fidelity optimization problems?\"\n\nThe theoretical result on the lower bound leads to the first asymptotically optimal algorithm for the MF-BAI problem. As discussed both in the lower bound section and in the algorithmic one, these novel results significantly improve the state-of-the-art in the MF-BAI tasks. Indeed, previous lower bounds were, in general, not tight up to a $\\lambda_M / \\lambda_1$ factor, which can be arbitrarily large, and existing algorithms were based on a sub-optimal concept of \"optimal fidelity\". As verified in the experimental section, these lead to a superior identification performance of our method compared to existing algorithms.\n\nFinally, our study proves that, to identify the optimal arm, there almost always exists an optimal arm-dependent fidelity that the learning system should query.\n\n> ### \"Does Theorem 3.1 hold regardless of the specific multi-fidelity model or acquisition function used?\"\n\nTheorem 3.1 holds for any algorithm that satisfies the $\\delta$-correctness requirement on all the multi-fidelity bandits within the class $\\mathcal{M}^*_{\\textup{MF}}$. These are all the multi-fidelity problems that can be modeled as a BAI problem formulated in Section 2. \n\nWe are unsure what the reviewer means by \"hold regardless of the specific multi-fidelity model.\" Furthermore, we are not sure what the reviewer means by \"any acquisition function used\" as there is no concept of acquisition function within our work.  Can the reviewer clarify these points?\n\n> ### \"How realistic is Assumption (5) in Theorem 4.1?\"\n\nWe are unsure what the reviewer means by Assumption (5) in Theorem 4.1 as **there is no assumption** in the statement or in the proof of Theorem 4.1. Can the reviewer clarify this point?\n\n> ### \"The gradient computation with respect to ω and μ is not entirely clear, especially given that these are often discrete values in bandit problems\"\n\nFirst, we recall that the sub-gradient is computed only w.r.t. to ${\\omega}$, as $\\omega$ represents the cost-proportions that the algorithm should play in expectation to identify the optimal arm using the minimum cost.\n\nSecondly, we notice that the values of both $\\omega$ and $\\mu$ **do not assume discrete values**. Indeed, $\\omega$ belongs to the simplex, while $\\mu$ belongs to the set of possible means (i.e., $\\Theta^{KM}$), which is not a finite set. This is standard in the BAI literature (see, e.g., \"Optimal Best Arm Identification with Fixed Confidence\", Garivier et al., 2016), where $\\omega$ and $\\mu$ do not belong to discrete sets as well.\n\nFinally, the sub-gradient is computed exactly as stated in Theorem 4.3, and, more precisely, in Equations (8) and (9), where $\\eta^*_{i,a}$ and $\\psi^*_j$ are the quantities introduced in Lemma 4.2 and Line 253. In other words, for fixed $\\mu$ and $\\omega$, one first computes the pair of arms $(i,a)$ that attain the maximum of Equation (2), and then tests whether $\\psi^*_i > \\psi^*_a$ to decide which expression to use among Equations (8) and (9). \n\nThe discussion presented in Lines 272-291 then provides an efficient algorithm to compute $\\eta^*_{i,a}$. Lemma C.4 in the appendix provides an analogous algorithm for the computation of $\\psi^*_i$. \n\n> ### \"Have the authors considered applying their method to more complex real-world applications, such as neural architecture search or other MFBO problems that can be framed as BAI? If not, what challenges might arise in such applications?\"\n\nAs done in previous works in MF-BAI, we have considered simulated domains in our experiments. When dealing with real-world problems, challenges arise when directly applying the multi-fidelity formalism considered in MF-BAI. For instance, the arm space might be continuous, such as in the case of hyper-parameter optimization.\nIn this scenario, practical methods (e.g., \"Multi-fidelity Bayesian optimization via deep neural networks\", Li et al., NeurIPS 2020), can overcome these challenges at the price of sacrificing theoretical guarantees. An interesting future research direction to bridge this gap would be to study the MF-BAI setting under the presence of linear function approximators; e.g., by drawing inspiration from linear BAI (\"Optimal best-arm identification in linear bandits\", Jedra et al., NeurIPS 2020).", "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": "", "extra_scores": {}}]

Author rebuttal:
We thank the Reviewers for their efforts in reviewing our paper. We are happy that the reviewers have recognized our paper as a "clear improvement over previous work" (Reviewer bSBL) and that they appreciated the "non-trivial technical contributions to the state of the art in multi fidelity BAI" (Reviewer 97EK). In the following, we aim to address the remaining questions.

Meta-review: This paper is broadly acknowledged to make significant contributions to algorithm design for the practical problem of multi-fidelity best arm identification problems in bandits. It not only improves upon previous fundamental limits on costs, but also develops a gradient-based algorithm which, given current computational paradigms in ML, is appealing from the implementation point of view, while also being situated on firm foundations. 

In view of the strengths of the paper, it is recommended for acceptance.
Decision: Accept (poster)