Optimal Multi-Fidelity Best-Arm Identification

Authors: riccardo  poiani
rémy  degenne
emilie  kaufmann
alberto maria metelli
marcello  restelli
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 10:30:09

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.

Main paper: 
 introduction: 
 In multi-armed bandits [20] , an algorithm chooses at each step one arm among K > 1 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 is a well-studied problem [6, 1, 12, 10, 8] with potential applications to, e.g. A/B/n testing [27] or hyper-parameter optimization [11] .In some applications, like physics, parameter studies, or hyper-parameter optimization, getting a sample from the arm distribution might be expensive since it requires evaluating or training a complex model and is computationally demanding. However, it is often the case that cheaper, less accurate sampling methods are available, for instance, by using a coarser model in the physics study example.The multi-fidelity bandit framework takes such scenarios into account. When choosing an arm, the algorithm also chooses a fidelity, with a trade-off: a higher fidelity gives a more precise observation but has a higher cost. We assume that the algorithm knows both the cost and the maximal bias of the observations from each fidelity. This is also how the knowledge about the fidelity was modeled in prior work [see, e.g., 16, 15, 25, 31] . 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 a correct answer with probably at least 1 -δ for a given parameter δ ∈ (0, 1). A good algorithm should do that at a minimum cost, and thus, the appropriate quality metric for evaluating an algorithm's performance is the sum of costs paid until it stops, i.e., the cost complexity. Previous work on the multi-fidelity BAI problem [25, 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 [31] , 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 Section 2, we define fixed-confidence best arm identification in multi-fidelity bandits in more mathematical detail and introduce the notations used throughout the paper. Then, Section 3 contains our first contribution: a tight instance-dependent lower bound on the cost complexity of any algorithm expressed with the maximum of a 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 a computationally efficient procedure for computing gradients of the function featured in the lower bound and describe a gradient-based algorithm whose cost complexity is asymptotically matching the lower bound. Finally, in Section 5, we present the results of numerical experiments which demonstrate the good empirical performance of our new algorithm compared to prior work.The multi-fidelity setting has mostly been studied in the context of Bayesian optimization [9, 24, 17, 26, 14, 21] and black-box function optimization with different structural assumptions [28, 29, 7, 23] . The goal there is to find the minimum of a 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 a variant of the Track-and-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 a complex optimization problem for which we have no 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., 8, 4, 22] ; nevertheless, as we discuss throughout the text, these studies cannot be directly applied to the multi-fidelity BAI problem. 
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-fidelity bandit model with K arms and M fidelities is a set of K ×M probability distributions ν = (ν a,m ) a∈[K],m∈ [M ] where ν a,m has mean of µ a,m . For each arm a ∈ [K], µ a,m represents the mean value of an observation of arm a using fidelity m, and let µ = (µ a,m ) a∈[K],m∈ [M ] . An observation at fidelity m is assigned a (known) cost λ m ≥ 0 with λ 1 < λ 2 < • • • < λ M . The goal is to identify the arm that has the largest mean at the highest fidelity M , a (µ) := argmax a∈[K] µ a,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 assume that there are some (known) values ξ 1 > ξ 2 > • • • > ξ M = 0 such that, for all arm a ∈ [K], the vector µ a := (µ a,m ) m∈[M ] satisfies ∀m ∈ [M ], |µ a,m -µ a,M | ≤ ξ m .We write µ a ∈ MF to indicate that arm a satisfies these multi-fidelity constraints, with these particular parameters ξ m (although they are not shown in the notation). In this paper, we consider arms that belong to a 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 ν using the means of its arms µ, which belongs to the set M MF := {µ ∈ Θ K×M : ∀a ∈ [K], µ a ∈ MF}, where Θ ⊆ R is the interval of possible means.At each interaction round t = 1, 2, . . . , the agent selects an arm A t and a fidelity M t , observes a sample X t ∼ ν At,Mt and pays a cost λ Mt . Letting F t = σ(A 1 , M 1 , X 1 , . . . , A t , M t , X t ) be the sigma field generated by the observations up to time t, a fixed-confidence identification algorithm takes as input a risk parameter δ ∈ (0, 1) and is defined by the following ingredients: (i) a sampling rule (A t , M t ) t , where (A t , M t ) is F t-1 -measurable, (ii) a stopping rule τ δ , which is a stopping time w.r.t. F t , and (iii) a decision rule âτ δ ∈ [K], which is F τ δ -measurable. We want to build strategies that ensure P µ (â τ δ = a (µ)) ≤ δ for all µ ∈ M MF with a unique optimal arm. Such a strategy is called δ-correct. Among δ-correct strategies, we are looking for strategies that minimize the expected identification cost (i.e., cost complexity) defined asE µ [c τ δ ] := a∈[K] m∈[M ] λ m E µ [N a,m (τ δ )] = a∈[K] m∈[M ] E µ [C a,m (τ δ )],where N a,m (t) denotes the number of pulls of arm a at fidelity m up to time t and C a,m (t) = λ m N a,m (t) denotes the cost associated to these pulls. In the sequel, we will provide cost complexity guarantees for multi-fidelity instances µ that belong to the set M * MF of multi-fidelity instances with a unique optimal arm, i.e., for which |a (µ)| = 1. We remark that for M = 1 and λ m = 1 we recover the best arm identification problem in a classical bandit model, for which the cost complexity coincides with the sample complexity, E µ [τ δ ].Additional notation Given an integer n ∈ N, we denote by ∆ n the n-dimensional simplex. Furthermore, given x, y ∈ (0, 1), we define kl(x, y) = x log(x/y) + (1 -x) log((1 -x)/(1y)). Given (p, q) ∈ Θ 2 , we denote by d(p, q) the Kullback-Leibler (KL) divergence between the distribution in the exponential family with mean p and that with mean q. We also write d -(x, y) = d(x, y)1 {x ≥ y} and d + (x, y) = d(x, y)1 {x ≤ y}. Finally, we denote by v(p) the variance of the distribution with mean p. 
on the cost complexity of multi-fidelity best-arm identification: 
 In this section, we discuss the statistical complexity of identifying the best-arm in MF-BAI problems. Formal proofs of the claims of this section are presented in Appendix B.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 ω ∈ ∆ K×M and µ ∈ Θ K×M , we defineEQUATIONEQUATIONThe quantity f i,j (ω, µ) is the dissimilarity according to a KL weighted by the costs between µ and the closest θ ∈ Θ K×M such that arms i and j satisfy the multi-fidelity constraints and θ k = µ k for k / ∈ {i, j}, with arm j better than arm i. If µ ∈ M MF then that closest θ is also in M MF but otherwise it might not be the case: if an arm k / ∈ {i, j} is not in MF for µ, then it is equally not in MF for θ. For µ ∈ M MF the maximum in the definition of F is realized at the best arm , as min a =i f i,a (ω, µ) is zero for i = . That is, F (ω, µ) = min j = f ,j (ω, µ). We define F with a maximum over i and not with that last expression because we want to define it for all points in Θ K×M , even the points which are not in M MF . For those points, we could imagine different notions of best arm, for example, arg max k µ k,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 δ ∈ (0, 1). For any δ-correct strategy, and any multi-fidelity bandit model µ ∈ M * MF , it holds that:EQUATIONwhereC * (µ) -1 := sup ω∈∆ K×M F (ω, µ) = sup ω∈∆ K×M min a = f ,a (ω, µ) .The quantity C * (µ) describes the statistical complexity of an MF problem µ as the typical max-min game that appears in lower bounds for BAI problems [see, e.g., 8, 3] . Specifically, first, the max-player chooses a vector ω ∈ ∆ K×M , and then the min-player chooses a bandit model θ ∈ M MF in which the optimal arm is different, with the goal of minimizing the function F (ω, µ). Following the methods from previous work, the objective value for ω and θ should be a∈[K] m∈[M ] ω a,m d(µa,m,θa,m) λm, featuring a sum over all arms and fidelities. However in the definition of f i,a (ω, µ) we restrict θ to be different from µ on only two arms. We can prove that if µ ∈ M MF , this gives the same objective value at the minimizing θ as the full sum. The difference will be important in our algorithm, which will compute that minimizer for points μ that do not belong to M MF .A difference with standard BAI settings is that in Equation ( 1) each ω ∈ ∆ K×M should be interpreted as a vector of cost proportions that the max-player is investing (in expectation) in each arm-fidelity pair to identify the optimal arm µ ,M . 2 We can interpret the oracle weights ω * ∈ argmax ∆ K×M F (ω, µ) as the optimal cost proportions that the agent should follow in order to identify µ ,M while minimizing the identification cost. To clarify the difference and the relationship between cost and pull proportions we notice that, given a cost proportion ω, it is always possible to compute the pull proportions π(ω) ∈ ∆ K×M that the agent should play in order to incur the costs proportions specified by ω, and vice versa. More specifically, these relationships are described for each arm-fidelity pair by the following equations for every a ∈ [K] and m ∈ [M ]:EQUATIONAs a direct consequence, it is possible to rewrite C * (µ) -1 as a function of π, the pull proportions. Doing so reveals that the minimizer θ in f ,j does not depend on the costs: it is also the minimizer of a∈{i,j},m∈[M ] π a,m d(µ a,m , θ a,m ). While the agent optimizes the cost proportions ω to get the best possible information/cost ratio, the min-player minimizes only the information available to the algorithm to tell µ and θ apart. Finally, we notice that F (ω, µ) is concave in ω 3 but F (ω(π), µ) is not concave in π. As we shall see in Section 4, this difference will play a crucial role in constructing an asymptotically optimal algorithm.The formulation of the lower bound as a 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.The only known lower bound for the multi-fidelity BAI problem is the one presented in [25] . That same bound was then shown in [31] . The bound from those previous works is looser than Theorem 3.1. 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λ M (µ 1,M -µ 2,M ) -2 log(1/2.4δ), while our lower bound is 8λ M (µ 1,M -µ 2,M ) -2 log(1/2.4δ).Furthermore, on particular instances with 2 arms and 2 fidelity, we can prove that our lower bound improves by a factor λ M /λ 1 , which can be arbitrarily large (See Appendix B.2). More generally, the proof of the previous lower bounds exhibits a particular point in the alternative, which makes it always looser than our bound which features an infimum over all points. Theorem 3.1 is also optimal in the regime δ → 0 since it is matched by the algorithm we introduce in the next section.We conclude our study of the lower bound by further analyzing the optimal allocation ω * . 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-Stop-like approach [8] . Nevertheless, we will explain in the next section how to efficiently compute the f i,j 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 ω * . For each arm a ∈ [K], it is not difficult to show that there must exist some fidelity m ∈ [M ] for which ω * a,m > 0 (Lemma B.2). However, as the following result highlights, in most cases, only one fidelity per arm has non-zero weight. Theorem 3.2. Let ∆ * K×M (µ) := argmax ω∈∆ K×M F (ω, µ) andM MF := µ ∈ M * MF : ∃i ∈ [K], ∃m 1 , m 2 ∈ [M ] 2 , ∃ω * ∈ ∆ * K×M (µ) : ω * i,m1 > 0, ω * i,m2 > 0 .The set M MF is a subset of R K×M whose Lebesgue measure is zero.Theorem 3.2 implies that in almost all multi-fidelity bandits, for any ω * ∈ ∆ * K×M (µ) and each arm a ∈ [K], there exists a single fidelity m * a ∈ [M ] for which ω * a,m * a > 0 holds. However, we note that this result does not offer an easy way to compute these optimal arm-dependent fidelities. 4Nevertheless, 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 [25, 31] already proposed notions of optimal, armdependent fidelity that the agent should employ to identify the optimal arm . Nevertheless, as we verify in Appendix B.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 µ in which following these alternative concepts of optimal fidelity leads to sub-optimal performance. 
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 can be found in Algorithm 1. All proofs for this section are presented in Appendix C.A reader familiar with the literature on BAI algorithms inspired from lower bounds like Theorem 3.1 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, Track-and-Stop (even in the cost-aware variant of [13] ) would require the computation of the optimal cost proportions at μ(t), which is a max-min problem for which we don'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-fidelity case could likely allow us to adapt the algorithm of [4] , or the exploration part of the regret-minimizing algorithm of [5] .Let us introduce some auxiliary notation. Let ω ∈ ∆ K×M be the uniform vector 1 KM , . . . , 1 KM . For all t ∈ N, we define Clipt (x) = min{x a,m , G √ t} a∈[K],m∈[M ]for an arbitrary constant G > 0.We also defineα t = 1 √ t and γ t = 1 4 √ t .Finally, for all t ∈ N, we denote by C(t) ∈ R KM the vector whose (a, m)-th dimension is given by C a,m (t). We now present Algorithm 1.Sampling rule After a first initialization phase in which the algorithm pulls each arm at each fidelity once (Line 1), the agent starts its sub-gradient ascent routine. More specifically at each iteration t ∈ N, the agent first computes the vector ω(t + 1) using the Exponential Weights algorithm on the sequence of gain functions {g s } t s=1 := {Clip s a,m λ m πa,m (s) ∇F (ω(s), μ(s)) } t s=1 , where π(t) := π(ω(t)) represents the pull-proportions induced by ω(t) and ∇F (ω(s), μ(s)) denotes a sub-gradient of F (ω, µ) w.r.t ω (Line 3). Neglecting for a moment the clipping function and the term Algorithm 1 Multi-Fidelity Sub-Gradient Ascent 1: Initialization. Pull each arm at each fidelity once, and set ω(t) = ω for all t ∈ {1, . . . , KM } 2: Sampling Rule for t ≥ KM 3: Sub-gradient Ascentω(t + 1) ∈ argmax ω∈∆ K×M α t+1 t s=KM ω • Clip s a,m λ m πa,m (s) ∇F (ω(s), μ(s)) -kl(ω, ω) 4: From Costs to Pulls πa,m (t + 1) = ωa,m (t + 1) λ m 1 i∈[K] j∈[M ] ωi,j (t+1) λj ∀a ∈ [K], m ∈ [M ] 5: Forced Exploration π (t + 1) = (1 -γ t )π(t + 1) + γ t ω 6: Cumulative Tracking (A t+1 , M t+1 ) ∈ argmax (a,m)∈[K]×[M ] t s=1 π a,m (s) -N a,m (t) 7: Stopping Rule τ δ = inf t ≥ KM : max i∈[K] min j =i f i,j (C(t), μ(t)) ≥ β t,δ 8: Decision Rule âτ δ ∈ argmax i∈[K] min j =i f i,j (C(t), μ(t))c(s) := a,m λ m πa,m (s) (these terms are present mainly for technical reasons), this step can be interpreted, from an intuitive perspective, as finding a sequence of weights {ω(t)} t that minimizes the regret on the sequence of empirical losses F (ω * , μ(s)) -F (ω(s), μ(s)). 5 At this point, once ω(t + 1) is computed, Algorithm 1 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 [8] in the pull-proportion space so to ensure that N a,m (t) ≈ t s=1 π a,m (s) (Line 6).Stopping and decision rule Finally, the algorithm applies a generalized likelihood ratio (GLR) test to decide when to stop (Line 7). For i, j ∈ [K], f i,j (C(t), μ(t)) can be interpreted a GLR statistics for comparing two classes: Θ KM versus {θ | θ i ∈ MF, θ j ∈ MF, θ j,M ≥ θ i,M }. If that GLR is large enough (if it exceeds a threshold β t,δ ), we can reject the hypothesis that µ belongs to the second class. If there is an arm i for which we can reject the alternative class for all j = i, we have rejected all θ ∈ M MF where i is not the best arm and we can safely stop and return the answer âτ δ = i. Since each f i,j is expressed as a sum of only two arms and M fidelities, it is possible to show that choosing β t,δ ≈ log(K/δ) + 2M log (log(t) + 1) (see its exact expression in (31) ) guarantees the correctness of the test, namely that P µ (â τ δ = ) ≤ δ holds (Proposition C.13).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 µ ∈ M MF , Algorithm 1 using the threshold β t,δ given in (31) is δ-correct and satisfiesEQUATIONAs we can see from Theorem 4.1, Algorithm 1 is asymptotically optimal, meaning that it matches the lower bound we presented in Theorem 3.1 for the asymptotic regime of δ → 0.Comparison with existing MF-BAI algorithms We conclude this section by comparing our results with the literature [25, 31] . First, [25] and [31] rely on additional assumptions that play a crucial role both for the algorithm design and the resulting theoretical guarantees. In [25] , the authors enforce an additional and intricate structural assumption on the relationships between λ's and ξ's (see Assumption 1 in [25] ). In [31] , instead, the authors assume additional knowledge expressed as an upper bound on µ ,M and a lower bound on argmax i = µ i,M . For both works, whenever these assumptions are not satisfied (i.e., λ's and ξ's do not respect Assumption 1 in [25] , and the knowledge on µ ,M , argmax i = µ i,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 of [31] matches the lower bound of Theorem 3.1, even when their additional hypotheses are satisfied.4.2 Computing the gradient of F (ω, µ)Algorithm 1 requires computing a sub-gradient of F (ω, µ). Notably, we remark that this is needed for a generic µ ∈ Θ KM , as μ(t) might violate the fidelity constraints due to inaccurate estimations or degenerate cases in which the multi-fidelity constraints are attained with equality. In this section, we provide an efficient algorithm for the computation of the sub-gradient that arises from a more in-depth study of the function F (ω, µ). To this end, we begin by presenting some intermediate characterization of the functions f i,j (ω, µ) that define F (ω, µ). ψ * k := argmin ψ∈R M m=1 ω k,m d -(µ k,m , ψ + ξ m ) + d + (µ k,m , ψ -ξ m ) λ mThen, the following holds:EQUATIONEQUATIONWe further introduce η * i,j as the minimizer in the expression in (7) 6 . When µ ∈ M MF , we can show that ψ * k = µ k,M for all k and due to the multi-fidelity constraints the expression in ( 6) is always equal to zero. Hence in both cases f i,j (ω, µ) is equal to the expression in (7) , which can be rewrittenf i,j (ω, µ) = 1 (µ i,M ≥ µ j,m ) k∈{i,j} M m=1 ω k,m d -(µ k,m , η * i,j + ξ m ) + d + (µ k,m , η * i,j -ξ m ) λ m .This quantity can be interpreted as the transportation cost for making µ j,M larger than µ i,M . Whenµ i / ∈ MF or µ j / ∈ MF, if ψ * j > ψ * i , f i,j (ω, µ) is equal to the expression (6) that can be interpreted as a transportation cost with an alternative in which i and j satisfy the multi-fidelity constraints.Using this preliminary result, we provide a precise expression for the sub-gradient of F (ω, µ). Theorem 4.3. Consider µ ∈ Θ KM and ω ∈ ∆ K×M such that F (ω, µ) > 0 holds. Let (i, a) ∈ [K] 2 be a pair of arms that attains the max-min value in Equation (2). Then a sub-gradient ∇F (ω, µ) of F (ω, µ) w.r.t. to ω is given by one of the two following expressions: for j ∈ {a, i} and m ∈ [M ] ,EQUATIONEQUATION)That sub-gradient ∇F (ω, µ) is 0 in all the remaining KM -2M dimensions.Theorem 4.3 shows how to compute a sub-gradient of F (ω, µ) under the mild assumption that F (ω, µ) > 0. 7 More specifically, it is sufficient to consider the pair (i, a) that attains the max-min value in Equation ( 2), and then test whether ψ * i ≥ ψ * a holds to choose which expression to use among Equations ( 8) and ( 9). An interesting interpretation of the sub-gradient expression is that, whenever ψ * i ≥ ψ * a , the sub-gradient is pointing toward the direction of the space that aims at increasing the information to discriminate the eventual optimality of arm a against i. On the other hand, whenever ψ * a > ψ * i 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 is required to compute ψ * k for all arm k and η * i,j for all pairs of arms such that ψ * i ≥ ψ * j . Using their definitions, this will require solving O(K 2 ) one-dimensional optimization problems of functions that involve O(M ) variables, which leads to a computational complexity which is roughlyO(K 2 M n),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 f i,j 's to obtain an algorithm whose total complexity is O(K 2 M 2 ) and that does not suffer from any approximation error due to the optimization procedure. Specifically, we now present a result that shows how to compute η * i,j . A similar result holds also forψ * k and is deferred to Appendix C. Lemma 4.4. Consider µ ∈ Θ KM and ω ∈ ∆ K×M such that f i,j (ω, µ) > 0 . Suppose that ψ * i, ≥ ψ * j holds.Then, there exists a unique minimizer η * i,j (ω) of Equation ( 7) which is the unique solution of the following equation of η:EQUATIONwherek a,m (x) = 1{x ≥ µ a,m + ξ m } and k a,m (x) = 1{x ≤ µ i,m -ξ m }.From Lemma 4.4, to compute η * i,j 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 ( 10) depends on η only for the presence of the indicator functions k a,m (η) and k a,m (η), which can only take a finite number of values. Hence, it is sufficient to evaluate the right-hand side at an arbitrary point within a 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 O(M ) candidate fixed points, this procedure takes at most O(M 2 ) steps.Computational complexity remark It follows that the per-iteration computational complexity of Algorithm 1 is O K 2 M 2 . The computationally efficient technique explained above indeed applies not only to the sampling rule but also to the stopping and the decision rules. 8 
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 at fidelity M . We will refer to this additional baseline as GRAD. In the following, we avoided the comparison with the multi-fidelity algorithms in [31] as we ran 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 an argument that shows a mistake in the proofs of [31] .Given this setup, first, we test all methods on a 4 × 5 multi-fidelity bandit with Gaussian arms that have been randomly generated, using a risk parameter δ = 0.01. Due to space constraints and for the sake of exposition, we refer the reader to Appendix D.1 for the value of µ, ξ's and λ's and details on the stopping rules calibration. We report the empirical distribution of the resulting cost complexities in Figure 1 . As one can verify, MF-GRAD obtains the most competitive performance. Experiments on additional 4 × 5 bandits that are reported in Appendix D.3 provide a similar conclusion. Furthermore, to illustrate the sub-optimality of IISE and GRAD from an intuitive perspective, we test our algorithm on a simple 5 × 2 instance that allows to easily understand why existing methods underperform MF-GRAD. Specifically, we consider µ i = [0.4, 0.5] for all i ∈ [4], µ 5 = [0.5, 0.6], In this case, we can prove that the optimal fidelity is sparse on fidelity m = 1 for i ∈ [4] , and on fidelity m = 2 for arm 5. Furthermore, thanks to the symmetry of the problem, it is possible to show that ω * i = [0.09621, 0] for all i ∈ [4], and ω * 5 = [0, 0.61516] (see Appendix D.1). As one can see, IISE obtains the worst performance in this domain. The reason is that the concept of optimal fidelity on which IISE relies is sub-optimal (i.e., according to the design principle of IISE, the optimal fidelity is m = 2 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 a first period in which IISE tries to exploit (unsuccessfully) data at fidelity m = 1. GRAD, on the other hand, obtains sub-optimal performances since although most of the budget should be spent on fidelity 2 (as ω * 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 ω * . To verify this behavior, we removed the stopping rule from MF-GRAD, and let the algorithm run for 10 5 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 ω * . 9 . Finally, we also refer the reader to Appendix D for additional results (e.g., additional domains, smaller regimes of δ) and further insights. 
conclusions: 
 For fixed-confidence best arm identification in multi-fidelity bandits, we presented a lower bound on the cost complexity and an algorithm with a matching upper bound in the regime of high confidence. The algorithm uses features of the lower bound optimization problem in order to compute its 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 of 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 w * a,m = 0 (such as the ones given in Proposition B.6) to eliminate some fidelities and reduce the support of the forced exploration component of the algorithm seems a 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 δ. In future work, we will seek a 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 * (µ) essentially scales with K due to the sparsity pattern, an interesting open question is whether there is a worse case O(KM ) scaling in the moderate confidence regime, indicating that all fidelities do need to be explored at least a constant amount of times. 
safeguards: 
 Question: Does the paper describe 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)? Answer: [NA] Justification: This paper does not involve such assets. Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [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 or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. 
 
 Appendix: Table 1 reports a summary on the main symbols and the notation used throughout the paper. KL divergence between two distributions with means p,q in the exponential familyd + (p, q), d -(p, q) d + (p, q) = d(p, q)1 {p ≤ q}, d -(x, y) = d(p, q)1 {p ≥ q} v(y)Variance of the distribution in the exponential family with mean parameter y C * (µ) -1 Expression that characterizes the lower-bound on the cost-complexity ω, πVector of cost and pull proportions respectivelyω * ω * ∈ argmax ω∈∆ K×M F (ω, µ) f i,j (ω, µ)Dissimilarity between arms i and j defined in Equation ( 1)F (ω, µ) max i∈[K] min j =i f i,j (ω, µ) ∆ * K×M (µ)Set of optimal oracle weights ω * for the multi-fidelity bandit model µ M MF Subset of multi-fidelity bandit models for which there exists a non-sparse optimal allocation ω * ω Uniform KM -dimensional vector ((KM ) -1 , . . . , (KM ) -1 ) G > 0Clipping constant in Algorithm 1 α t , γ tLearning rate and forced exploration rate respectivelyC(t) Vector whose (a, m)-th dimension is C a,m (t) ω(t) Vector of empirical cost proportions, namely ω a,m (t) = C a,m (t)( i∈[K] j∈[M ] C i,j (t)) -1 ψ * i Minimizer of Equation (6) η * i,jMinimizer of Equation ( 7) k i,m (η) 1 {η ≥ µ i,m + ξ m } k i,m (η) 1 {η ≤ µ i,m -ξ m } B CostEQUATIONwhereC * (µ) -1 := sup ω∈∆ K×M F (ω, µ) = sup ω∈∆ K×M min a = f ,a (ω, µ) .Proof. Consider δ ∈ (0, 1), a multi-fidelity bandit model µ and an alternative instance θ ∈ Alt(µ) where Alt(µ) = i = {θ ∈ M MF : θ a,M > θ ,M }. Then, by applying Lemma 1 in [18] , we can directly connect the expected number of draws of each arm to the KL divergence of the two multifidelity bandit models. More specifically, we have that:EQUATIONThen, similarly to Theorem 1 in [8] , we now proceed by applying Equation ( 11) with all the alternative models θ ∈ Alt(µ). Specifically, we have that:kl(δ, 1 -δ) ≤ inf θ∈Alt(µ) a∈[K] m∈[M ] E µ [N a,m (τ δ )]d(µ a,m , θ a,m ) = E µ [c τ δ ] inf θ∈Alt(µ) a∈[K] m∈[M ] E µ [λ m N a,m (τ δ )] E µ [c τ δ ] d(µ a,m , θ a,m ) λ m ≤ E µ [c τ δ ] sup ω∈∆ K×M inf θ∈Alt(µ) a∈[K] m∈[M ] ω a,m d(µ a,m , θ a,m ) λ m = E µ [c τ δ ] sup ω∈∆ K×M min a = inf θ∈MMF: θ a,M >θ ,M i,m ω i,m d(µ i,m , θ i,m ) λ m (a) = E µ [c τ δ ] sup ω∈∆ K×M min a = inf θa∈MF,θ ∈MF: θ a,M >θ ,M i∈{ ,a},m∈[M ] ω i,m d(µ i,m , θ i,m ) λ m = E µ [c τ δ ] sup ω∈∆ K×M min a = f ,a (ω, µ) = E µ [c τ δ ]C * (µ) -1 ,where in (a) we use that as µ ∈ M MF , the minimum in θ does not change any arm i / ∈ { , a}. Finally, we lower bound kl(δ, 1 -δ) with log 1 2.4 δ , thus concluding the proof.In this section, we provide a comparison with the existing lower bound for the MF-BAI setting. In the following, we restrict our attention to bandits with Gaussian arms with variance 1/2. We assume for simplicity of the exposition that = 1 and thatµ 1,M > µ 2,M ≥ • • • ≥ µ K,M .Given this setup, we begin by recalling Theorem 1 in [25] . Theorem B.1 (Theorem 1 in [25] ). Consider any multi-fidelity bandit model µ with Gaussian arms with variance 1/2. Then, for any δ-correct algorithm and δ ≤ 0.15 it holds that E µ [c τ δ ]/ log (2.4δ) -1 is lower bounded by:min m∈[M ]: µ1,m>µ 2,M +ξm λ m (µ 1,m -(µ 2,M + ξ m )) 2 + K i=1 min m∈[M ]: µ 1,M -ξm>µi,m λ m (µ i,m -(µ 1,M -ξ m )) 2 .At this point, focus, for simplicity on the following 2 × 2 bandit model (but a trivial generalization holds for K × M bandits). We considerµ 1,m = µ 1,M + ξm 2 and µ 2,m = µ 2,M -ξm 2 . Furthermore, suppose that µ 1,M = -µ 2,M . Then, let ∆ := µ 1,M -µ 2,M . Suppose that ∆ = ξ m , which yields µ 1,M = ξm 2 and µ 2,M = -ξm 2 , and that ∆ ∆ -ξm 2 ≤ λ M λ m .Since ∆ = ξ m , this condition actually simplifies to λ M ≥ 4λ m .Under these conditions it is possible to verify that the lower bound of [25] is given byE µ [c τ δ ] ≥ 2λ m ∆ -ξm 2 2 log 1 2.4δ = 8λ m ∆ 2 log 1 2.4δ.At this point, consider, instead, the result that we presented in Theorem 3.1 and consider a generic weight proportion ω. From Corollary C.2, we know that:EQUATIONThen, let ω * ,M be the optimal weights restricted on the portion of the simplex in which ω 1,m = ω 2,m = 0. Then, let η * ,M be the optimal solution of Equation ( 12) when considering ω * ,M . Using the symmetry of the KL divergence for Gaussian distributions, it holds that η * ,M = 0 and ω * ,M 1,2 = ω * ,M 2,2 = 0.5. Then, for any ω it holds that:F (ω, µ) ≤ m∈[M ] ω 1,m d -(µ 1,m , η * ,M + ξ m ) λ m + ω 2,m d + (µ 2,m , η * ,M -ξ m ) λ m = ω 1,M d(µ 1,M , η * ,M ) λ M + ω 2,M d(µ 2,M , η * ,M ) λ M ≤ F (ω * ,M , µ),where in the second step, we have used the fact thatd(µ 2,m , η * ,M -ξ m ) = d(µ 2,M -ξm 2 , -ξ m ) = 0 and d(µ 1,m , η * ,M + ξ m ) = d(µ 1,M + ξm 2 , ξ m ) = 0.In other words, we have shown that in this example the optimal allocation is sparse and on fidelity M . To conclude, we have that:F (ω * ,M , µ) = 0.5 * d( ξm 2 , 0) λ M + 0.5 * d(-ξm 2 , 0) λ M = d( ξm 2 , 0) λ M = (∆/2) 2 λ M = ∆ 2 4λ M ,which leads to:E µ [c τ δ ] ≥ 4λ M ∆ 2 log (2.4δ) -1 .Under the assumptions on the problem, 4λ M ∆ 2 is always larger than 8λm ∆ 2 . This result says that the ratio among the lower bounds can be of order λ M /λ m , which is arbitrarily large.In this section, we provide a formal proof on the sparsity of the optimal oracle allocation ω * . The proofs given in this section rely on results that are explained in Appendix C.1.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 a, there always exists a fidelity m such that ω * a,m > 0 holds.Lemma B.2. Consider µ ∈ M MF and ω * ∈ ∆ * K×M (µ). Then, for all a ∈ [K], there exists m ∈ [M ] such that ω * a,m > 0.Proof. We split the proof into two cases. First we consider a = , and proceed by contradiction.Consider ω * ∈ ∆ * K×M (µ), and suppose there exists a = such that ω * ,m = 0 for all m ∈ [M ]. In this case, however, we have that:EQUATIONwhere, in the first step we have used the definition of F (ω * , µ), in the second one the fact that ω * a,m = 0 for all m ∈ [M ], and in the last one we selected θ ,m = µ ,m for all m ∈ [M ]. Nevertheless, from Lemma C.6, we know that, whenever ω i,M > 0 holds for all i ∈ [K], then F (ω, µ) > 0 holds as well. Therefore, ω * / ∈ ∆ * K×M . The proof for the case in which i = follows identical reasoning.We then continue by proving that, at any optimal allocation ω * , all the transportation costs f a (ω * , µ) are equal. Lemma B.3. Consider µ ∈ M MF and ω * ∈ ∆ * K×M (µ). Then, for all a, b such that a = and b = the following holds:f ,a (ω * , µ) = f ,b (ω * , µ).Proof. We introduce the following notation:A = a ∈ [K] \ { } : a ∈ argmin b = f b (ω * , µ) B = ([K] \ { }) \ A.At this point, we proceed by contradiction. Suppose that B = ∅. Then, for some sufficiently small > 0, we define ω ∈ ∆ K×M in the following way. For all a ∈ A:ωa,M = ω * a,M + /|A| ωa,m = ω * a,m ∀m < M.For all b ∈ B, instead:ωb,m b = ω * b,m b -/|B| ωb,m = ω * b,m ∀m = m b ,where m b ∈ [M ] is any fidelity such that ω * b,m b > 0 (which exists by Lemma B.2). Given this definition of ω, it is easy to see that f ,a ( ω, µ) > f ,a (ω * , µ) for all a ∈ A. This is a direct consequence of the fact that f ,a (•, µ) is a strictly increasing function of ω a,M , which is apparent from its expression from its expression for µ ∈ M MF given in Corollary C.2 and the computation of its gradient (Lemma C.3). Moreover, due to similar arguments, it also holds thatf ,b ( ω, µ) ≤ f ,b (ω * , µ) for all b ∈ B.Using the continuity of the functions f , for ε small enough we further have f ,a ( ω, µ) < f ,b ( ω, µ) for all a ∈ A and b ∈ B. This leads to min a = f ,a (ω * , µ) < min a = f ,a ( ω, µ) which contradicts the optimality of ω * .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 f ,a (ω, µ) with respect to ω for µ ∈ M MF (Lemma C.3). Lemma B.4. Consider µ ∈ M and ω * ∈ ∆ K×M (µ). Then, for all a = the following conditions holds:d + (µ a,m1 , η * ,a (ω * ) -ξ m1 ) λ m1 = d + (µ a,m2 , η * ,a (ω * ) -ξ m2 ) λ m2 ∀m 1 , m 2 : ω * a,m1 , ω * a,m2 > 0 d -(µ ,m1 , η * ,a (ω * ) + ξ m1 ) λ m1 = d -(µ ,m2 , η * ,a (ω * ) + ξ m2 ) λ m2 ∀m 1 , m 2 : ω * ,m1 , ω * ,m2 > 0 d + (µ a,m1 , η * ,a (ω * ) -ξ m1 ) λ m1 = d -(µ ,m2 , η * ,a (ω * ) + ξ m2 ) λ m2 ∀m 1 , m 2 : ω * a,m1 , ω * ,m2 > 0Proof. We begin by recalling the definition of C * (µ) -1 :C * (µ) -1 = sup ω∈∆ K×M min a = f ,a (ω, µ),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 ω * for which the sub-derivatives exist, i.e., from Theorem 4.3 and Corollary C.2, the ones for which the following condition hold:10 EQUATIONAt this point, fix any arm a that attains the minimum in Equation ( 14). Then, from the KKT conditions, we obtain the following system of inequalities:                 -∂ ωa,m f ,a (ω, µ) + c -b a,m = 0 ∀m ∈ [M ] -∂ ω ,m f ,a (ω, µ) = 0 ∀m ∈ [M ] b i,m ω * i,m = 0 ∀i ∈ { , a}, ∀m ∈ [M ] b i,m ≥ 0 ∀i ∈ [K], ∀m ∈ [M ] ω * i,m ≥ 0 ∀i ∈ [K], ∀m ∈ [M ] i,m ω * i,m = 1 .At this point, suppose that ω i1,m1 > 0, ω i2,m2 > 0 for some i 1 , i 2 ∈ { , a} and some m 1 , m 2 ∈ [M ], then b i1,m1 = 0, b i2,m2 = 0. As a consequence, by applying Lemma C.3 and the fact that µ ∈ M MF (i.e., see Corollary C.2), the following equations holds:d + (µ a,m1 , η * ,a (ω * ) -ξ m1 ) λ m1 = d + (µ a,m2 , η * ,a (ω * ) -ξ m2 ) λ m2 ∀m 1 , m 2 : ω * a,m1 , ω * a,m2 > 0 d -(µ ,m1 , η * ,a (ω * ) + ξ m1 ) λ m1 = d -(µ ,m2 , η * ,a (ω * ) + ξ m2 ) λ m2 ∀m 1 , m 2 : ω * ,m1 , ω * ,m2 > 0 d + (µ a,m1 , η * ,a (ω * ) -ξ m1 ) λ m1 = d -(µ ,m2 , η * ,a (ω * ) + ξ m2 ) λ m2 ∀m 1 , m 2 : ω * a,m1 , ω * ,m2 > 0Finally, to conclude the proof, it is sufficient to iterate these arguments for all a = . Indeed, from Lemma B.3, we know that all sub-optimal arms will attain the minimum in Equation ( 14) at a global optimum ω * .At this point we are ready to prove our main result. Theorem 3.2. Let ∆ * K×M (µ) := argmax ω∈∆ K×M F (ω, µ) andM MF := µ ∈ M * MF : ∃i ∈ [K], ∃m 1 , m 2 ∈ [M ] 2 , ∃ω * ∈ ∆ * K×M (µ) : ω * i,m1 > 0, ω * i,m2 > 0 .The set M MF is a subset of R K×M whose Lebesgue measure is zero.Proof. Let us introduce some additional notation. Consider a subset of arm-fidelity pairs X ⊆ [K] × [M ], and define G(X ) ⊆ M as the subset of multi-fidelity bandit models µ for which there exists ω * ∈ ∆ * K×M (µ) such that, for all (i, m) ∈ X , ω * i,m > 0 holds. Then, fix an arm i = , and any three fidelity m 1 , m 2 , m 3 ∈ [M ], and consider µ ∈ G({(i, m 1 ), (i, m 2 ), ( , m 3 )}). 11 Then, from Lemma B.4, we know that the following condition holds:EQUATIONThis, in turn, implies that η * ,i (ω * ) is uniquely identified as a function of µ i,m1 , µ ,m3 , ξ m1 , ξ m3 , λ m1 and λ m3 . Indeed,d + (µ i,m1 , η * ,i (ω * ) -ξ m1 ) is a strictly increasing function of η * ,i (ω * ), while d -(µ ,m3 , η * ,i (ω * ) + ξ m3 ) is a strictly decreasing function of η * ,i (ω * ). Let c 1 = η * ,i (ω * ), and let c 2 = d + (µi,m 1 ,η * ,i (ω * )-ξm 1 ) λm 1. At this point, since ω * i,m2 > 0 holds by definition, we also know, from Lemma B.4, that the following condition has to be satisfied:d + (µ i,m2 , c 1 -ξ m2 ) λ m2 = c 2 .Therefore, the value of µ i,m2 is uniquely identified as a function of µ i,m1 , µ ,m3 ,ξ m1 , ξ m3 , λ m1 and λ m3 . That function is measurable (it's a combination of d + , d -and their inverses), hence µ lies on the graph of a measurable function, and such a graph has Lebesgue measure 0. Therefore, G({(i, m 1 ), (i, m 2 ), ( , m 3 )}) has measure 0. At this point, thanks to Lemma B.2, we know that, for arm , there always exists at least a fidelity m 3 such that ω * ,m3 > 0. We thus have thatG((i, m 1 ), (i, m 2 )) ⊆ m3∈[M ]G((i, m 1 ), (i, m 2 ), ( , m 3 )) .Since G((i, m 1 ), (i, m 2 )) is contained in a set which is a countable union of null measure sets, it has null measure.To conclude the proof, we notice that:M MF ⊆ K i=1 m1,m2∈[M ] 2 G({(i, m 1 ), (i, m 2 )}) := Y.The proof follows from the fact that (i) Y is a countable union of set of null measure (and, consequently, has null measure), and (ii) M MF ⊆ Y.In this section, we present additional results on the sparsity of the oracle weights. Specifically:(i) We identify a specific class of multi-fidelity bandit models in which the optimal allocation is sparse. In particular, within this class of MF-bandit models, the optimal allocation have non-zero values only at the cheapest fidelity.(ii) We then provide sufficient conditions to determine whether some fidelity have zero weights at any optimal weight vector ω *We now proceed by constructing the class of multi-fidelity bandits that we mentioned in point (i) above. In this construction, we will consider Gaussian multi-fidelity bandits with variance 1 2 . Then, for any number of arms K and fidelity M , we will denote with A KM , the set of Gaussian multifidelity 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 µ ,m > 0, and let µ a,M = -µ ,m for all a = . Then, for each fidelity m < M , and any values of λ m and ξ m , we let µ i,m = µ i,M -ξ m for all i = , and µ ,m = µ ,M + ξ m . Finally, to simplify some computations, we set σ 2 of each Gaussian distribution to 1 2 . Proposition B.5. For all µ ∈ A KM , and any ω * ∈ ∆ * K×M , it holds that, for all a ∈ [K] and all m > 1, ω * a,m = 0.Proof. To prove the result, starting from Corollary C.2, it is sufficient to notice that, for all µ ∈ A KM and all a = , f ,a (ω, µ) can be rewritten as:EQUATIONSpecifically, Equation ( 16) follows directly from the symmetric property of KL divergence for Gaussian distributions, and by the construction of µ. The proof then continue by contradiction. Suppose there exists ω * such that there exists (i, m) (with m > 1) such that ω * i,m > 0. By defining ω as the vector which is equal to ω * except in the components (i, m) and (a, 1) for all a ∈ [K]. More specifically, for a sufficiently small > 0, we define ωi,m = ω * i,mand ωa,1 = ω * a,1 + /(K) for all a ∈ [K]. Then, it is easy to see that f ,a (ω, µ) > f ,a (ω * , µ) holds for all a = , thus contradicting the optimality of ω * . Finally, we now provide sufficient conditions to determine whether some fidelity have zero weights at any optimal weight vector ω * Proposition B.6. Fix a = . Then, if µ a,m + ξ m ≥ µ ,m , then it holds that ω * a,m = 0. Furthermore, if µ ,m -ξ m ≤ µ j,M for all j = * , then it holds that ω * ,m = 0.Proof. Consider a = , and let us analyze f ,a (ω, µ) for any ω ∈ ∆ K×M . More specifically, we recall from Corollary C.2, that the only term in which ω a,m plays a role is the following one:EQUATIONNevertheless, since η * ,a (ω) ≤ µ ,m ≤ µ a,m + ξ m , we have that Equation ( 17) is always equal to 0 for all ω ∈ ∆ K×M . To prove the result we now proceed by contradiction. Suppose that ω * is such that ω * a,m > 0. Then, consider ω as a vector which is equal to ω * except in the components (a, m) and (i, M ) for all i = . More specifically, for a sufficiently small > 0, we define ωa,m = ω * a,mand ωi,M = ω * i,M + /(K -1) for all i = . At this point, by noticing that f ,i (ω, µ) is strictly increasing in ω i,M (i.e., due to Theorem 4.3 and the fact that µ ∈ M MF ), and since f ,a (ω, µ) is not affected by the value of ω a,m (i.e., Equation ( 17)), we have that f ,i (ω, µ) > f ,i (ω * , µ) for all i = * , thus contradicting the optimality of ω * .To show that if µ ,m -ξ m ≤ µ j,M for all j = * , then it holds that ω * ,m = 0, it is possible to follow identifical reasonings. The only difference is that the term ω ,m plays a role in each of the (K -1)-equations defining F (ω, µ), namely:EQUATIONNevertheless, Equation ( 18) is equal to 0 for all a = since η * ,a (ω) ≥ µ i,m -ξ m ≥ µ a,M holds for all ω and all a = . The proof then follows by an identical construction of an alternative weight vector ω which increases the objective function.In this section, we discuss how the concept of "optimal" fidelity of previous works (i.e., [25] and [31] ) fails to satisfy the notion of optimal fidelity that arises from the tighter lower bound that we presented in Section 3. In this section, we consider as example 2 × 2 multi-fidelity bandit models with Gaussian distributions. To ease the notation, we will consider µ 1,M > µ 2,M .We notice that [25] provided the two concepts of optimal fidelity. The first one is from their Theorem 1. This same concept was then considered later in [31] . A fidelity m is optimal for a certain arm a ∈ [K] if it satisfies the following condition:EQUATIONThen, consider the following 2 × 2 example of multi-fidelity BAI problem. Let ξ 1 = 0.1, µ 1,M = 0.6, µ 1,m = 0.65, µ 2,M = 0.5, µ 2,m = 0.45 (where we use the notation M = 2 for the maximal fidelity and m = 1). Suppose, furthermore, that all distributions are Gaussian. In this case, from Equation ( 19)-( 20), we have that m * 1 = 1 and m * 2 = 1 whenever the following conditions are satisfied:µ 1,M -(µ 2,m + ξ m ) √ λ m > µ 1,M -µ 2,M √ λ M µ 1,m -ξ m -µ 2,M √ λ m > µ 1,M -µ 2,M √ λ M .Plugging in the numerical values, we obtain in both cases0.05 √ λ m > 0.1 √ λ M ,thus showing that, according to [31] , the optimal fidelity for both arms is m = 1 whenever λ M λm > 0.1 0.05 .At this point, consider the expression of F (ω, µ) = f 1,2 (ω, µ) in this particular example. Then, it is possible to show that, for any ω ∈ ∆ 2×2 such that ω 1,M = ω 2,M = 0, then, f 1,2 (ω, µ) = 0. Specifically, we have that F (ω, µ) is given by:inf η∈[µ 2,M ,µ 1,M ] ω 1,m d(µ 1,m , η + ξ m )1{η ≤ µ 1,m -ξ m } λ m + ω a,m d(µ 2,m , η -ξ m )1{η ≥ µ a,m + ξ m } λ mIn turn, this is equal to:inf η∈[0.5,0.6] ω 1,m d(0.55, η)1{η ≤ 0.55} λ m + ω a,m d(0.55, η)1{η ≥ 0.55} λ m ,which is always 0 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 (ω, µ) > 0.Furthermore, [25] provided also the following concept of optimal fidelity which only holds for sub-optimal arms (see Definition 1 in [25] ). A fidelity m such that µ 1,M -µ 2,M > 4ξ m holds is said to be optimal for arm a = 1 if the following holds:EQUATION)At this point, consider the following classes of multi-fidelity bandit models:µ 2,m = µ 2,M -ξ m , µ 1,m = µ 1,M + ξ m , µ 1,M -µ 2,M ≤ 4ξ m .In this case, from Equation ( 20) it follows that the optimal fidelity for arm 2 is always M . Nevertheless, sinceµ 2,m = µ 2,M -ξ m , µ 1,m = µ 1,M + ξ m , we know from Proposition B.5 ω 1,M = ω 2,M = 0.We start by analyzing a salient feature of f i,j (ω, µ) that holds for any µ ∈ Θ KM .Lemma C.1. Consider µ ∈ Θ KM . Fix any ω ∈ ∆ K×M and i, j ∈ [K]. Let θ * be the solution of the following optimization problem:θ * ∈ argmin θi∈MF,θj ∈MF: θ j,M ≥θ i,M m∈[M ] ω j,m d(µ j,m , θ j,m ) λ m + m∈[M ] ω i,m d(µ i,m , θ i,m ) λ m .Furthermore, define for k ∈ {i, j}:EQUATIONIn particular,f i,j (w, µ) = k∈{i,j} m∈[M ] ω k,m d -(µ k,m , θ * k,M + ξ m ) + d + (µ k,m , θ * k,M -ξ m ) λ m = min θ j,M ≥θ i,M k∈{i,j} m∈[M ] ω k,m d -(µ k,m , θ k,M + ξ m ) + d + (µ k,m , θ k,M -ξ m ) λ mProof. We begin by proving Equation (22) . To this end, it is sufficient to notice that, given a fixed θ * k,M , it is possible to set θ * k,m := µ k,m , whenever the following condition is satisfied:EQUATION)The condition is Equation ( 25) is equivalent to requiring m ∈ [M ] \ M k (ω, µ, θ * ) ∪ M k (ω, µ, θ * ) , which concludes the first part of the proof.We continue by proving Equation (23) . Consider m ∈ M k (ω, µ, θ * ), that is θ * k,m > µ k,m + ξ m . From this condition, it directly follows that θ * k,m > µ k,m ; therefore, since d(µ k,m , x) is increasing in x, it follows that, in order to attain the argmin, we need to pick the smallest value of θ k,m that satisfies the multi-fidelity constraint |θ * k,M -θ k,m |, that is θ * k,M -ξ m . The proof of Equation ( 23) follows is almost identical to the one of Equation ( 24); it is sufficient to replace the definition of M k (ω, µ, θ * ) with M k (ω, µ, θ * ).At this point, we continue by analyzing in more detail the function f i,j (ω, µ). ψ * k := argmin ψ∈R M m=1 ω k,m d -(µ k,m , ψ + ξ m ) + d + (µ k,m , ψ -ξ m ) λ mThen, the following holds:EQUATIONEQUATIONProof. The proof follows by analyzing the definition of f i,j (ω, µ). Consider θ * i , θ * j that attaines the minimum in Equation (1). Then, there are two possibilities: either θ * i,M = θ * j,M or θ * j,M > θ * i,M . Suppose that θ * j,M > θ * i,M , then we notice that the optimization problem in f i,j (ω, µ) is a 2D-convex optimization problem in the variables θ j,M , θ i,M (thanks to Lemma C.1). Therefore, since the minimum of the constrained problem is such that θ j,M > θ i,M , than, by the convexity of the problem, this is also a minimum for the unconstrained problem, thus leading to:f i,j (ω, µ) = inf θi∈MF,θj ∈MF k∈{i,j} m∈[M ] ω k,m d(µ k,m , θ k,m ) λ m .At this point, we notice that the constraints in the previous optimization problem are only intra-arm. Therefore, we can rewrite f i,j (ω, µ) as:f i,j (ω, µ) = k∈{i,j} inf θ k ∈MF m∈[M ] ω k,m d(µ k,m , θ k,m ) λ m .Furthermore, applying the same reasoning as in the proof of Lemma C.1, we can further rewrite f i,j (ω, µ) as follows:f i,j (ω, µ) = k∈{i,j} inf ψ∈R m∈[M ] ω k,m d + (µ k,m , ψ -ξ m ) + d -(µ k,m , ψ + ξ m ) λ m = k∈{i,j} m∈[M ] ω k,m d -(µ k,m , ψ * k + ξ m ) + d + (µ k,m , ψ * k -ξ m ) λ m .At this point, we notice that due to Lemma C.1 we know that θ * j,M = ψ * j and θ * i,M = ψ * i , thus concluding the first part of the proof. Consider now the case in which θ * j,M = θ * i,M holds. Then, applying Lemma C.1, and using θ * i,M = θ * j,M , we can rewrite f i,j (ω, µ) as follows:f i,j (ω, µ) = inf η∈R k∈{i,j} M m=1 ω k,m λ m d + (µ k,m , η -ξ m ) + d -(µ k,m , η + ξ m ) ,thus concluding the proof.Given this result, we recall that the definitions ofEQUATION)EQUATION)Corollary C.2. Consider µ ∈ M MF , and a ∈ [K] such that a = . Then it holds that:f ,a (ω, µ) = inf η∈[µ a,M ,µ ,M ] i∈{ ,a} M m=1 ω i,m d -(µ i,m , η + ξ m ) + d + (µ i,m , η -ξ m ) λ m = inf η∈[µ a,M ,µ ,M ] M m=1 ω ,m d -(µ ,m , η + ξ m ) λ m + ω a,m d + (µ a,m , η -ξ m ) λ mProof. At this point, we notice that whenever µ ∈ M MF it holds that f ,a can always be expressed as Equation (7) . This is direct by the condition on ψ's in Lemma 4.2. Furthermore, it also holds at η * ,a that d -(µ a,m , η * ,a + ξ m ) = 0, and d + (µ ,m , η * ,a -ξ m ) = 0. This is a consequence of the fact that η * ,a ∈ [µ a,M , µ ,M ] for all weights ω. Indeed, η * ,a ∈ [µ a,M , µ ,M ] holds due to monotonicity property of the KL divergence.We now analyze in more detail Equations ( 26) and (27) . In particular, we begin by focusing on Equation (26) . Taking the gradient in Equation ( 27) w.r.t. the optimization variable η, and setting it equal to 0, we obtain that any optimal point η * i,j (ω) needs to satisfy the following equation:η   a∈{i,j} M m=1 ω a,m λ m k a,m 1 v(η -ξ m ) + k a,m 1 v(η + ξ m )   = (28) a∈{i,j} M m=1 ω a,m λ m k a,m µ a,m + ξ m v(η -ξ m ) + k a,m µ a,m -ξ m v(η + ξ m ) .where we recall that k a,m (η) and k a,m (η) are given by:k a,m (η) = 1 {η ≥ µ a,m + ξ m } k a,m (η) = 1 {η ≤ µ a,m -ξ m } .Given this intermediate result, we now investigate in more depth the solution of Equation ( 28). Lemma 4.4. Consider µ ∈ Θ KM and ω ∈ ∆ K×M such that f i,j (ω, µ) > 0 . Suppose that ψ * i, ≥ ψ * j holds. Then, there exists a unique minimizer η * i,j (ω) of Equation (7) which is the unique solution of the following equation of η:EQUATION)wherek a,m (x) = 1{x ≥ µ a,m + ξ m } and k a,m (x) = 1{x ≤ µ i,m -ξ m }.Proof. Let us analyze:f i,j (ω, µ) = inf η∈R a∈{i,j} m∈M ω a,m d -(µ a,m , η + ξ m ) λ m + ω a,m d + (µ a,m , η -ξ m ) λ m := inf η∈R g i,j (ω, µ, η).At this point, we proceed by contradiction. Suppose that there exists x 1 , x 2 ∈ argmin η∈R g i,j (ω, µ, η) such that x 1 = x 2 . From the convexity of g i,j (ω, µ, η) w.r.t. η, we know that any x ∈ [x 1 , x 2 ] belongs to the argmin set as well. Furthermore, for all x ∈ [x 1 , x 2 ], since f i,j (ω, µ) > 0, at least one of the following condition is satisfied:EQUATIONx) > 0 holds for some a ∈ {i, j} and some fidelity m < M • ωa,m λm d(µ a,M , x -ξ m )k a,m (x) > 0 holds for some a ∈ {i, j} and some fidelity m < M Therefore, from Equation ( 28), we obtain that all x ∈ [x 1 , x 2 ] are fixed points of the following Equation:EQUATIONAt this point, we notice that for any couple of different x1 , x2 that satisfies Equation ( 29), there exists at least one arm a ∈ {i, j} and one fidelity m < M such that at least one of the following two conditions hold:• k a,m (x 1 ) = k a,m (x 2 ) • k a,m (x 2 ) = k a,m (x 2 )This however, is possible only for a finite number of points, while the interval [x 1 , x 2 ] contains infinitely many optimal points. Therefore, there exists a unique solution η * i,j (ω) ∈ argmin η∈R g i,j (ω, µ, η), and, furthermore, it is a solution of Equation ( 29), thus concluding the proof.Given this result, we continue by providing a result on how to compute the derivative of f i,j (ω, µ) whenever f i,j (ω, µ) is given by Equation ( 7).Lemma C.3. Consider µ ∈ Θ KM and ω ∈ ∆ K×M such that f i,j (ω, µ) > 0. Furthermore, suppose that f i,j (ω, µ) is given by Equation (7) . Then, for all a ∈ {i, j} and all m ∈ [M ]:∂f i,j (ω, µ) ∂ω a,m = d + (µ a,m , η * i,j + ξ m ) + d -(µ i,m , η * i,j -ξ m ) λ m .Proof. First of all, we notice that, since f i,j (ω, µ) > 0 holds, and since f i,j (ω, µ) is expressed as in Equation ( 7), then, thanks to Lemma 4.4, we know that η * i,j (ω) is the unique optimum of the Equation (7) . In the rest of this proof, we will explicit the relationship between f i,j and η * i,j (ω) by writing f i,j (ω, µ, η * i,j (ω)). At this point, fix a ∈ {i, j} and m ∈ [M ]. Then, it is easy to verify from Equation ( 10) that both the right and left derivative of η * i,j (ω) w.r.t. ω a,m exists. Suppose for a moment that they are equal, then we have that∂η * i,j (ω)∂ωa,m exists and it continuous. Therefore, we obtain∂ ∂ω a,m f i,j (ω, µ, η * i,j (ω)) = ∂f i,j ∂ω a,m (ω, µ, η * i,j (ω)) + ∂f i,j ∂η * i,j (ω) (ω, µ, η * i,j (ω)) ∂η * i,j (ω) ∂ω a,m = ∂f i,j ∂ω a,m (ω, µ, η * i,j (ω)) = d + (µ a,m , η * i,j + ξ m ) + d -(µ a,m , η * i,j -ξ m ) λ m ,where in the second step we have used that ∂fi,j ∂η * i,j (ω) (ω, µ, η * i,j (ω)) = 0 since η * i,j (ω) is a minimizer of Equation (7) .Similarly, whenever, the right and the left derivatives of η * i,j (ω) are different 12 , we can 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 f i,j thanks to the fact that η * i,j (ω) is a minimizer of Equation (7) .At this point, it remains to analyze in more detail the case in which we have that f i,j (ω) is expressed as in Equation ( 6). Lemma C.4. Consider µ ∈ Θ KM and ω ∈ ∆ K×M such that f i,j (ω, µ) > 0 holds. Furthermore, suppose that ψ * j > ψ * i . Then, for each a ∈ {i, j}, there exists a unique minimizer ψ * a of Equation ( 6) which is the unique solution of the following equation of ψ:EQUATION)Proof. The proof follows by noticing that, for each a ∈ {i, j}, the optimization problem in Equation ( 6) is an unconstrained convex optimization problem in ψ. Taking the derivative and setting it equal to 0 yields the desired result.At this point, we proceed by showing how to compute the partial derivatives of f i,j (ω) whenever it is expressed as in Equation ( 6). Lemma C.5. Consider µ ∈ Θ KM and ω ∈ ∆ K×M such that f i,j (ω, µ) > 0. Furthermore, suppose that ψ * j > ψ * i . Then, for all m ∈ [M ] it holds that:∂f i,j (ω, µ) ∂ω a,m = d + (µ a,m , ψ * a + ξ m ) + d -(µ a,m , ψ * a -ξ m ) λ m .Proof. The proof is a straightforward adaptation of the proof of Lemma C.3.Finally, we are now ready to prove our result on the sub-gradient of F (ω, µ).Theorem 4.3. Consider µ ∈ Θ KM and ω ∈ ∆ K×M such that F (ω, µ) > 0 holds. Let (i, a) ∈ [K] 2be a pair of arms that attains the max-min value in Equation (2). Then a sub-gradient ∇F (ω, µ) of F (ω, µ) w.r.t. to ω is given by one of the two following expressions: for j ∈ {a, i} and mEQUATIONEQUATIONThat sub-gradient ∇F (ω, µ) is 0 in all the remaining KM -2M dimensions.Proof. The proof follows by the definition of F (ω, µ) together with Lemma 4.2, Lemma C.3, and Lemma C.5.We now show a sufficient condition for F (ω, µ) > 0 to hold when µ ∈ Θ KM . Lemma C.6. Consider µ ∈ Θ KM such that there exists for which µ ,M > max a = µ a,M . Furthermore, consider ω ∈ ∆ K×M such that ω i,M > 0 holds for all i ∈ [K]. Then, we have that F (ω, µ) > 0.Proof. From the definition of F , and the definition of , we have that:F (ω, µ) ≥ min a = inf θa∈MF, θ ∈MF θ a,M ≥θ ,M j∈{ ,a} m∈[M ] ω j,m d(µ j,m , θ j,m ) λ m ≥ min a = inf y≥x ω ,M d(µ ,M , x) λ M + ω a,M d(µ a,M , y) λ M = min a = inf η∈[µ a,M ,µ ,M ] ω ,M d(µ ,M , η) λ M + ω a,M d(µ a,M , η) λ M > 0,where in the last step we have used the fact that µ ,M > µ i,M for all i = , together with ω i,M > 0for all i ∈ [K].Furthermore, we show that the sequence of weights generated by Algorithm 1 satisfy ω i,M > 0 for all i ∈ [K] Lemma C.7. The sequence of weights {ω(t)} t satisfy ω i,M (t) > 0 for all i ∈ [K] and for all t.Proof. We begin by recalling the definition of ω(t):ω(t + 1) ∈ argmax ω∈∆ K×M α t+1 t s=KM ω • Clip s (∇F (ω(s), μ(s)) -kl(ω, ω)From this definition, thanks to the property of kl, we have that ωa,m (t) > 0 for all a ∈ [K], and all m ∈ [M ].Remark C.8. It follows by combining Lemma C.6 and Lemma C.7, that F (ω(t), μ(t)) = 0 might happen only when there are multiple best arms at fidelity M . Whenever this condition is encountered, it is possible to project the bandit model μ(t) to have a unique optimal arm (e.g., by adding a small > 0 to one of the optimal arms). When looking at the proof of Theorem 4.1, we can see that this does not impact its theoretical guarantees as (i) on the good event E T this does not happen, and, Lemma C.17 holds unchanged.Lemma C.9. For any set S ⊆ Θ KM and any subset of armsA ⊆ [K], the function (ω, µ) → inf θ∈S a∈A,m∈[M ] ω a,m d(µa,m,θa,m) λm is jointly continuous on ∆ K×M × Θ KM .Proof. We apply (a trivial generalization of) Lemma 27 of [3] . The lemma in that paper is stated for a set of alternative models, but the proof actually works for any set S. Likewise, it is stated for the case of λ m = 1, but since it works for an arbitrary Bregman divergence d it applies to a 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 a function of (ω A×[M ] , µ 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(ω, µ) → F (ω, µ) is jointly continuous on ∆ K×M × Θ KM . Proof. By definition, F (ω, µ) = max i min a =i f i,a (ω, µ) with f i,a (ω, µ) = inf θ∈Si,a a∈Ai,a,m∈[M ] ω a,m d(µa,m,θa,m) λm for S i,a = {θ ∈ M M F | θ a,M ≥ θ i,M} and A i,a = {i, a}. Since a minimum of finitely many continuous functions is continuous and likewise for the maximum, it suffices to show that each f i,a is jointly continuous. This is true by Lemma C.9.Corollary C.11. Let C ⊆ Θ KM be a compact set. Then F is uniformly continuous on ∆ K×M × C.Proof. The set ∆ K×M × C is compact and F is continuous, hence it is uniformly continuous on that set.Lemma C.12. Let µ ∈ Θ KM . For all ε > 0, there exists κ > 0 such that for all ω ∈ K×M and all µ ∈ Θ KM ,µ -µ ∞ ≤ κ =⇒ F (ω, µ ) -F (ω, µ) ≤ .Proof. Take any compact ball B(µ, κ) for the norm • ∞ with κ > 0 centered at µ. Then F is uniformly continuous on ∆ K×M × B(µ, κ) by Corollary C.11. This means that for any ε > 0, there exists κ ε > 0 such that for all (ω , µ) ∈ ∆ K×M × B(µ, κ), ω -ω ∞ ≤ κ ε ∧ µ -µ ∞ ≤ κ ε =⇒ |F (ω , µ ) -F (ω, µ)| ≤ ε .We can take κ ε = min{κ, κ ε } to remove the condition µ ∈ B(µ, κ). The result of the Lemma is this for the special case ω = ω.In the following, we propose an analysis on the correctness which is based on the concentration results provided in [22] . We notice that these results are based on Gaussian distributions. Nevertheless, at the cost of a more involved notation, it is possible to extend all the results of this work for canonical exponential families using, e.g., Theorem 7 in [19] .At this point, let us consider the following value of β t,δ :EQUATIONwhere C is a universal constant (see Proposition 1 in [22] ). Then, we can show the following result. Proposition C.13. Let δ > 0, then it holds that P µ (â τ δ = * ) ≤ δ.Proof. With probabilistic arguments we have that:P µ (â τ δ = ) ≤ P µ ∃t ≥ KM, ∃i = , min j =i f i,j (C(t), μ(t)) ≥ β t,δ ≤ i = P µ ∃t ≥ KM, min j =i f i,j (C(t), μ(t)) ≥ β t,δ ≤ i = P µ (∃t ≥ KM, f i, (C(t), μ(t)) ≥ β t,δ ) ≤ i = P µ   ∃t ≥ KM, k∈{i, } m∈[M ] N k,m d(μ a,m (t), µ a,m ) ≥ β t,δ   ≤ δ,where in fourth step we have used the definition of f i, , and in the last one Proposition 1 in [22] together with a union bound on K.This section contains auxiliary lemmas that will be used in the analysis of Algorithm 1.Lemma C.14. For all a ∈ [K], m ∈ [M ], and for all t ≥ 1, it holds that N a,m (t) ≥ √ t 4KM -ln(KM ). Furthermore, it holds that:EQUATIONProof. This lemma is a simple combination of Lemma 3 in [22] with the tracking result of [5] . Using algebraic manipulations, we have that:N a,m (t) ≥ t s=1 π a,m (s) -N a,m (t) - t s=1 π a,m (s) ≥ t s=1 π a,m (s) -ln(KM ) ≥ t s=1 γ s KM -ln(KM ) = 1 KM t s=1 1 4 √ s -ln(KM ) ≥ √ t 4KM -ln(KM ),where, in the second step we have used Theorem 6 in [5] , together with the fact that ln(KM ) ≥ ln(4) ≥ 1.For the second part of the proof, we have that:t s=1 πa,m (s) -N a,m (t) ≤ t s=1 π a,m (s) -N a,m (t) + 2 t s=1 γ s ≤ ln(KM ) + √ t ≤ 2 ln(KM ) √ t.Lemma C.15. Consider > 0 and B ∈ R such that C * (µ) -1 -B -> 0. Then, there exists a constant C such that, forEQUATIONit holds that:EQUATION.Proof. Let C be a constant that depends on such that, for T ≥ C it holds that:12M log(log(T ) + 3) + 2M C λ min ≤ T.Then, for a,m C a,m (T ) ≥ C 0 ( , δ), we have that:β T,δ a,m C a,m (T ) = log K δ + 2M log 4 log K δ + 1 + 12M log(log(T ) + 3) + 2M C a,m C a,m (T ) ≤ log K δ + 2M log 4 log K δ + 1 a,m C a,m (T ) + ≤ C * (µ) -1 -B,which concludes the proof.Before diving into the proof of Theorem 4.1, we introduce some additional notation. We denote with B ∞ (x, κ) the ball of radius κ centered at x. Then, for all T , and > 0, we introduce the following event:E (T ) = T t≥h(T ) { μ(t) ∈ B ∞ (µ, κ )} ,where h(T ) ≈ T 1/4 . At this point, we present our result. Furthermore, we denote with ω(t) the vector of empirical cost proportions, namely, for all (a, m), ω a,m (t) = Ca,m(t) Ci,j (t) . First of all, we introduce an initial result that controls the expectation of the stopping cost. Lemma C. 16 . Consider B such that C * (µ) -1 -B -> 0, and suppose that there exists a constant T such that, for all T ≥ T , it holds that F (ω(T ), μ(T )) ≥ F (ω * (µ)) -B on the good event E (T ). Then, it holds that:i∈[K] j∈[M ]EQUATIONProof. Using probabilistic arguments, we have that:E µ [c τ δ ] = +∞ 0 P µ (c τ δ > x)dx ≤ λ M T + C 0 ( , δ) + λ M T +C0( ,δ) P µ (c τ δ > x, c τ δ ≥ C 0 ( , δ))dx ≤ λ M T + C 0 ( , δ) + λ M T +C0( ,δ) P µ τ δ > x λ M , c τ δ ≥ C 0 ( , δ) dx ≤ λ M T + C 0 ( , δ) + 1 + +∞ T = T + C 0 ( ,δ) λ M P µ (τ δ > T, c τ δ ≥ C 0 ( , δ)) ≤ λ M T + C 0 ( , δ) + 1 + +∞ T =0 P µ (E(T ) c ),where (i) in the second inequality, we have upper bounded c τ δ ≤ λ M τ δ , (ii) in the third inequality, we have used the fact that τ δ is an integer variable, and (iii) in the last inequality we have used that for all T ≥ T such that a,m C a,m (T ) ≥ C 0 ( , δ), then we have that E(T ) ⊆ {τ δ < T }. Indeed, combining Lemma C.15 with the definition T , we obtain that for all T ≥ T such that a,m C a,m (T ) ≥ C 0 ( , δ), then we have that E(T ) ⊆ {τ δ < T }. This last step is direct by noticing that F (ω(T ), μ(T )) ≥ β T ,δ a,m Ca,m(T ) implies stopping.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., [8] ).Then, we 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 E T , it holds that there exists a constant L, that depends on µ, such that the empirical sub-gradients are uniformly-bounded by L. Lemma C.17. Let c(t) = a,m λ m πa,m (s). Define C r := log(KM ) + KM G + 4(Lλ M ) 2 + 2G 2 , and consider the sequence of weights {ω(t)} t generated by Algorithm 1. Then, on the good event E (T ) it holds that:T t=h(t) c(t)∇F (ω * , μ(t)) • (ω * -ω(t)) ≤ C r √ T .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 L by λ M , to the additional presence of c(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 C µ that will be useful in performing some upper-bound reasoning in the proof of the final result.Lemma C.18. Consider the following quantity:EQUATION.There exists a problem dependent constant C µ such that the previous equation can be upper bounded by:F (ω(T ), µ) + 4 ln(KM )M λ M C µ λ min √ T .Proof. Let us begin by analyzing F (ω(T ), µ). Fix ā such that F (ω(T ), µ) = f ,ā (ω(T ), µ). Moreover, consider θ , θ ā ∈ argmin i∈{ ,ā} m ω a,m (T ) d(µa,m,θa,m) λm. Then, consider the following difference:H := min a = inf θa,θ ∈MF T s=1 i∈{ ,a} m πi,m (s)d(µ i,m , θ i,m ) a,m C a,m (T ) -F (ω(T ), µ).Then, the previous Equation can be upper bounded by:H ≤ i∈{ ,ā} m T s=1 πi,m (s) -N i,m (T ) d(µ i,m , θ * i,m ) a,m C a,m (T ) ≤ 2 ln(KM ) √ T i∈{ ,ā} m d(µ i,m , θ * i,m ) a,m C a,m (T ) ≤ 4 ln(KM )M √ T C µ a,m C a,m (T ), where in the first step, we have used the definition of θ * ā, θ * and the definition of ω(T ), in the second one, we have used Lemma C.14, and in the last one the facts that, thanks to definition θ * ā, θ * , there exists some problem dependent constant C µ such that d(µ i,m , θ * i,m ) is bounded.Theorem 4.1. For any multi-fidelity bandit model µ ∈ M MF , Algorithm 1 using the threshold β t,δ given in (31) is δ-correct and satisfiesEQUATIONProof. 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 ):EQUATIONDefine, for brevity, T := T -h(T ) + 1 and c(s) := a,m λ m πa,m (s). Then, we start by analyzing F (ω * , µ). On E (T ) we have that:F (ω * , µ) = a,m C a,m (T ) a,m C a,m (T ) F (ω * , µ) - T s=1 c(s) a,m C a,m (T ) F (ω * , µ) + T s=1 c(s) a,m C a,m (T ) F (ω * , µ) ≤ T s=1 c(s) a,m C a,m (T ) F (ω * , µ) + F (ω * , µ) a,m C a,m (T ) 2 ln(KM ) √ T ≤ T s=1 c(s) a,m C a,m (T ) F (ω * , µ) + 2 ln(KM )F (ω * , µ) λ min √ T ≤ T s=h(T ) c(s) a,m C a,m (T ) F (ω * , µ) + h(T ) λ min T F (ω * , µ) + 2 ln(KM )F (ω * , µ) λ min √ T ≤ T s=h(T ) c(s)F (ω * , μ(t))) a,m C a,m (T ) + λ M T λ min T + h(T ) λ min T F (ω * , µ) + 2 ln(KM )F (ω * , µ) λ min √ T ,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 E (T ). At this point, we focus our analysis onT s=h(T ) c(s)F (ω * , μ(t)) a,m Ca,m(T ).Define, for brevity, g s = c(s)∇F (ω(s), μ(s)); then, we have that:T s=h(T ) c(s)F (ω * , μ(s))) a,m C a,m (T ) = T s=h(T ) c(s) (F (ω * , μ)) ± F (ω(s), μ(s)))) a,m C a,m (T ) ≤ T s=h(T ) c(s)F (ω(s), μ(s))) a,m C a,m (T ) + T s=h(T ) g s • (ω * -ω(s)) a,m C a,m (T ) ≤ T s=h(T ) c(s)F (ω(s), μ(s))) a,m C a,m (T ) + C r λ min √ T ≤ T s=h(T ) c(s)F (ω(s), µ) a,m C a,m (T ) + C r λ min √ T + λ M T λ min T ,where in the first inequality we have used the concavity of F , in the second one we have used Lemma C.17, and in the last one Lemma C.12 and the definition of E (T ).Finally, we have that:T s=1 c(s)F (ω(s), µ) a,m C a,m (T ) = T s=1 min a = inf θa,θ ∈MF i∈{ ,a} m πi,m (s)d(µ i,m , θ i,m ) a,m C a,m (T ) ≤ min a = inf θa,θ ∈MF T s=1 i∈{ ,a} m πi,m (s)d(µ i,m , θ i,m ) a,m C a,m (T ) ≤ F (ω(T ), µ) + 4 ln(KM )M C µ λ min √ T ≤ F (ω(T ), μ(T )) + 4 ln(KM )M C µ λ min √ T + ,where (i) in the first equality we used the definition of c(s), ω(s) and F , in the second one we used Lemma C.18, and in the last one Lemma C.12.Given this analysis, let us define:B T := 2λ M T λ min T + h(T ) λ min T F (ω * , µ) + 2 ln(KM )F (ω * , µ) λ min √ T + + C r λ min √ T + 4 ln(KM )M C µ λ min √ T + .used to generate MF instances in [25] (see their Appendix D.1). Specifically, first, two M -dimensional vectors are specified, which we refer to as a and b. Specifically, a and b are such that a m ≥ a m+1 and b m ≥ b m+1 for all m ∈ [M -1]. Then, we first sample the means of the arm at fidelity M13 , and once this is done we sampleµ i,m ∈ µ i,M -a m -b 2 , µ i,M + a m + b 2 .Then, ξ is computed as ξ m = a m + bm 2 . In this sampling procedure, we have used a = [0.075, 0.06, 0.04, 0.02, 0] and b = [0.05, 0.04, 0.02, 0.01, 0].We now recall the 5 × 2 example of Section 5: We prove that, in this instance, the oracle weights are given by ω * i = [0.09621, 0] for all i ∈ [4] , and ω * 5 = [0, 0.61516] (this number have been rounded to the fourth decimal precision). In order to prove this, we first notice that in the considered domain the optimal fidelity for i ∈ [4] is m = 1. This is direct from the fact that µ i,m = µ i,M -ξ m (see, e.g., Proposition B.5). Furthermore, we recall the expression f 5,i , for any i ∈ [4] :f 5,i (ω, µ) = inf η∈[µ i,M ,µ 5,M ] m∈[M ] ω 5,m d -(µ 5,m , η + ξ m ) λ m + ω i,m d + (µ i,m , η -ξ m ) λ m .Then, since η * 5,i ∈ [µ i,M , µ 5,M ], µ i,M = µ 5,m = µ 5,M -ξ m , we have that the optimal fidelity for arm 5 is m = 2. At this point, consider the oracle weights ω * . We notice that, due to the symmetry of the problem, ω * i,1 is equal for all i ∈ [4] . Then, we can rewrite f 5,i (ω * , µ) as a function of a single variable, that is:f 5,i (ω, µ) = inf η∈[µ i,M ,µ 5,M ] (1 -4ω i,1 ) d -(µ 5,2 , η) λ M + ω i,1 d + (µ i,1 , η -ξ m ) λ m ,and, consequently, we obtain that C * (µ) -1 can be expressed as a convex optimization of a single variable, that is ω i,1 . Taking the derivative of F (ω, µ) w.r.t. ω i,1 we obtain that the following equality should be satisfied at the optimum:4 d(µ 1,M , η * 5,i ) λ M = d(µ i,1 , η * 5,i -1) λ m .Solving for η * 5,i gives a unique solution in the range [0.5, 0.6], which is 0.539. Then, using Lemma C.3 and solving for ω i,1 , we obtain ω i,1 = 0.09621, and consequently, ω 5,2 = 0.61516.Thresholds To conclude, we comment on the thresholds β t,δ used by the algorithms. For the stopping rule in MF-GRAD we used β t,δ = log(K/δ) + M log(log(t) + 1), which is a simplification of its theoretical value (31) that retains the same scaling in K and M (up to constants). In GRAD, we used β t,δ = log(K/δ) + log(log(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 C.13) only requires to concentrate a sum over 2 KL terms. Finally, in the confidence intervals that are used in IISE we have used the confidence bonuses 2σ 2 (log(KM/δ)+log(log(t))) Na,m(t) 14 , which compared to their original form is replacing some crude union bound over t 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 δ-correctness requirement in all cases.In this section, we analyze the behavior of MF-GRAD by analyzing the evolution of the empirical cost proportions. Specifically, we repeat on the 4 × 5 bandit model of Table 2 , the same experiment that we presented in Section 5 for the 5 × 2 bandit model. Figure 4 reports the result. Interestingly, we highlight how the sparsity pattern emerges also in this domain.In this section, we present results on additional 4 × 5 multi-fidelity bandit models. Specifically, we generate another random instance according to the procedure of [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 5 . In both cases, we considered Gaussian distribution with σ 2 = 0.1. Empirical results of MF-GRAD, IISE and GRAD for δ = 0.01 can be found in Figure 5 and 6 respectively. As we can appreciate, MF-GRAD maintains the most competitive performance across both domains. As reported in [22] , using constant learning rate can improve the identification performance in standard BAI settings. In the following, we analyze the performance difference of MF-GRAD that uses the theoretical learning rate, and MF-GRAD that uses a constant learning rate of α = 0.25. We will refer this second version as MF-GRAD-CONST. Figure 7 and 8 reports the performance of the algorithms in the two bandit models of Section 5. As we can see, in both cases, MF-GRAD-CONST 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 4 and 9 we can appreciate as MF-GRAD-CONST move away from the initial cost proportions way sooner than MF-GRAD, which explains its superior performance in the moderate regime of δ.Finally, we repeat the experiments that we presented in the previous section using smaller values of δ. Specifically, we consider δ = 10 -10 . Figure 11 4 .Figure 14 : Empirical cost complexity for 1000 runs times with δ = 10 -10 on the multi-fidelity bandit of Table 5 .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 in a specific instance (Section D.6.1). Then, in Section D.6.2, we point out an error in the analysis of [31] that highlights how both algorithms fails at stopping when considering instances such as the one that has been considered in Section D.6.2.When experimenting with the algorithms proposed in [31] , namely LUCBExploreA and LUCB-ExploreB, we 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: µ 1 = [0.64, 0.6], µ 2 = [0.46, 0.5], λ = [0.1, 5], ξ = [0.1, 0] and σ 2 = 1. In this scenario, the well-known LUCB algorithm [12] which only uses samples at fidelity M , stops soon (iteration ≈ 100k) paying a total cost of roughly 500k. When running LUCBExploreA and LUCBExploreB, instead, we faced termination issues. We let both algorithms run for a maximum number of 10 8 samples (reaching a total cost which is approximately 10 7 ), and the stopping criterion was never met for LUCBExploreA, while 70% of LUCBExploreB runs did not stop. LUCBExploreB explores more fidelities at the beginning, and that initial exploration can be enough to trigger the stopping test on 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 an upper bound on µ 1,M and a lower bound on µ 2,M (assuming arms to being ordered according to µ1,M > µ 2,M ≥ • • • ≥ µ 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 .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. In Appendix B.5, we described how that "optimal fidelity" can differ from the fidelity selected by our lower bound. Since our lower bound can be matched by an algorithm and thus describes the actual cost complexity of the problem, it betters represent the 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 in the mechanism used to look for the target fidelity. 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 to stop on some examples. We then highlight an issue with the proof of [31] . where β(n, t, δ) = log(Lt 4 /δ)/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 a confidence interval is not valid, which happens with small probability. If μ1,1 (t) ≤ µ 1,1 + β(t/2, t, δ), LCB 1 (t) = max{0, μ1,1 (t) -ξ 1 -β(t/2, t, δ)} ≤ µ 1,1 -ξ 2 = 0.55 .On the other hand, if min{1, μ2,1 (t) ≥ µ 2,1 -β(t/2, t, δ), U CB 2 (t) = min{1, μ2,1 (t) + ξ 1 + β(t/2, t, δ)} ≥ µ 2,1 + ξ 1 = 0.55 .We get that we always have LCB 1 (t) ≤ U CB 2 (t), unless one of the two concentration inequalities on the empirical means are not true. The confidence width β is designed to make those inequalities true for all t ∈ N with probability close to 1. We can similarly get that LCB 2 (t) ≤ U CB 1 (t) (which is expected since 2 is a 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 a threshold c (with value 0.55 in 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 (t) ≤ c and U CB t (t) ≥ c or both LCB ut (t) ≤ c and U CB ut (t) ≥ c.• Step 2: confidence intervals are likely to hold.• Step 3: if a sub-optimal arm k satisfies LCB k (t) ≤ c and U CB k (t) ≥ 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 as in the last paragraph.In the example above with the oracle choice for the target fidelity, we saw that if confidence intervals hold and t = 1 (which is the most likely), then LCB t (t) ≤ c and U CB t (t) ≥ c. That is, step 1 gives a condition on arm 1 only (and nothing on arm 2). But then we get nothing from step 3, since arm 1 is not a sub-optimal arm.We only get an upper bound on the number of pulls for sub-optimal arms if we can say that they satisfy LCB k (t) ≤ c and U CB k (t) ≥ c at some point, but it might not be the case. Indeed, when the algorithm does not terminate, steps 1 and 2 together give that with large probability either both LCB t (t) ≤ c and U CB t (t) ≥ c or both LCB ut (t) ≤ c and U CB ut (t) ≥ c. It is possible that we always have this property for t = 1 (the optimal arm), and that we can never apply step 3.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).This claim is evident when looking at the proof of Theorem3.1. 3 This is a consequence of the fact F (ω, µ) is an infimum over linear functions of ω.We provide insights on cases in which it is possible to compute the optimal fidelity in Appendix B.4.Whenever μ(s) is sufficiently close to µ, this implicitly generates a sequence of weights that provide values of F (•, µ) "close" to the one of the oracle weights ω * .To ease the notation, we omit (most of the time) the dependence of ψ * k and η * i,j in ω and µ.As we discuss in Remark C.8, F ( ω(t), μ(t)) = 0 is a rare condition, and, whenever it happens, it is possible to alter Algorithm 1 slightly without affecting its theoretical guarantees.Given the definition of fi,j, it is sufficient to replace ωi,m/λm in Equation(10) with Na,m(t).Furthermore, at the end of this period, we measured the distance between ω * and the empirical cost proportions ω(10 5 ); it holds that ||ω * -ω(10 5 )||2 ≈ 0.031 ± 0.0006. The error has been estimated withindependent runs, and 0.0006 reports the 95% confidence intervals.We notice that a global optimum point clearly satisfies this condition.Similar arguments hold also for i = .This can happen, for instance, whenever η * i,j (ω) = µa,m ± ξm.For this step, we constrained the minimum gap between arms at fidelity M is at least 0.1.Notice, indeed, that ISEE requires a union bound both on K and M . 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: 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: limitations: No major limitation to me.
paper_summary: paper_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. 

The 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.
strength_weakness: strength_weakness: I do not see any issue that can be flagged as a significant weakness.
questions: questions: I don't see any shaded area denoting confidence intervals in Figure 3.

Line 78: notation.
limitations: limitations: No concerns on social impacts
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

Connection 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.

Assumption 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.

Narrow 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.

Gradient 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.
questions: 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?

Can the authors provide more intuition or examples of how the theoretical results help in understanding real-world multi-fidelity optimization problems?

Theorem 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?

How 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?

The 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?

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?
limitations: 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.

The authors should provide more context on the limitations of the best-arm identification framework compared to more general multi-fidelity Bayesian optimization problems.

A discussion on the potential challenges in applying the method to more complex, real-world problems would be valuable.
The paper would benefit from a more comprehensive discussion of the potential negative societal impacts of the work, even if they are indirect.

Comments: title: Thank you for your response
comment: I appreciate your response. I keep my score.
Dear reviewer, 

first thanks again for the time taken to review our paper. We are writing a general comment here to outline some doubts that we have on this review, as there are some comments that we believe are not aligned with the content of our paper, and consequently, we are unsure on how to answer some questions. Specifically: 

- Within the summary, the reviewer mentions that "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" and "The method combines ideas from Thompson sampling, Gaussian process surrogates, and evolutionary algorithms to address challenges in multiobjective optimization with expensive oracles." Nevertheless, this is not aligned with the content of our paper.
- Similarly, within the strenghts there is another reference to the qPOTS algorithm, which is not something that we consider in our paper.
- Then, in the weaknesses, the reviewer mentions Assumption (5) in Theorem 4.1. However, there is no assumption neither in the statement nor the proof of the theorem
- Finally, in the questions, the reviewer also asks if our results holds for any acquisition function used. However, there is no concept of acquisition function within our work.

In the rebuttal, we answer the reviewer's comment to the best of our understanding. Naturally, we remain available for further clarifications, but we kindly ask the reviewer to clarify the points above.

Best regards,

The authors