Optimal Multi-Fidelity Best-Arm Identification

"Narrow problem focus" and comparison of MF-BAI with MFBO

First, we note that the multi-fidelity BAI is an established problem within the literature (i.e., "Multi-fidelity best-arm identification", Poiani et al., NeurIPS 2022, and "Multi-fidelity multi-armed bandits revisited", Wang et al., NeurIPS 2024).

Furthermore, we note that our work on BAI differs from MFBO studies in at least the two following dimensions (similar comments have already been made in e.g., "Multi-fidelity Best-Arm Identification", Poiani et al., 2022):

1. First, we only use a minimal assumption on the arm space, that is $|\mu_{i,m} - \mu_{i,M}| \le \xi_m$ for all arms $i \in [K]$ and fidelity $m \in [M]$. On the other hand, works on MFBO (e.g., "Gaussian Process Bandit Optimisation with Multi-fidelity Evaluations", Kandasamy et al., NeurIPS 2016, "Multi-fidelity bayesian optimisation with continuous approximations", Kandasamy et al., ICML 2017, "Multi-fidelity Gaussian Process Bandit Optimisation", Kandasamy et al., JAIR 2018) typically impose stronger structural such as Gaussian Process modeling.
2. Secondly, these lines of work usually analyze the simple/cumulative regret. Our paper, instead, aims at minimizing the cost complexity. As one can verify, this has a significant impact on the algorithm design and its theoretical analysis.

For these reasons, we retain that our work is different (rather than less general) w.r.t. MFBO approaches. We will better clarify these differences in a revised version of the manuscript.

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

The theoretical result on the lower bound leads to the first asymptotically optimal algorithm for the MF-BAI problem. As discussed both in the lower bound section and in the algorithmic one, these novel results significantly improve the state-of-the-art in the MF-BAI tasks. Indeed, previous lower bounds were, in general, not tight up to a $\lambda_M / \lambda_1$ factor, which can be arbitrarily large, and existing algorithms were based on a sub-optimal concept of "optimal fidelity". As verified in the experimental section, these lead to a superior identification performance of our method compared to existing algorithms.

Finally, our study proves that, to identify the optimal arm, there almost always exists an optimal arm-dependent fidelity that the learning system should query.

"Does Theorem 3.1 hold regardless of the specific multi-fidelity model or acquisition function used?"

Theorem 3.1 holds for any algorithm that satisfies the $\delta$-correctness requirement on all the multi-fidelity bandits within the class $\mathcal{M}^*_{\textup{MF}}$. These are all the multi-fidelity problems that can be modeled as a BAI problem formulated in Section 2.

We are unsure what the reviewer means by "hold regardless of the specific multi-fidelity model." Furthermore, we are not sure what the reviewer means by "any acquisition function used" as there is no concept of acquisition function within our work. Can the reviewer clarify these points?

"How realistic is Assumption (5) in Theorem 4.1?"

We are unsure what the reviewer means by Assumption (5) in Theorem 4.1 as there is no assumption in the statement or in the proof of Theorem 4.1. Can the reviewer clarify this point?

"The gradient computation with respect to ω and μ is not entirely clear, especially given that these are often discrete values in bandit problems"

First, we recall that the sub-gradient is computed only w.r.t. to ${\omega}$, as $\omega$ represents the cost-proportions that the algorithm should play in expectation to identify the optimal arm using the minimum cost.

Secondly, we notice that the values of both $\omega$ and $\mu$ do not assume discrete values. Indeed, $\omega$ belongs to the simplex, while $\mu$ belongs to the set of possible means (i.e., $\Theta^{KM}$), which is not a finite set. This is standard in the BAI literature (see, e.g., "Optimal Best Arm Identification with Fixed Confidence", Garivier et al., 2016), where $\omega$ and $\mu$ do not belong to discrete sets as well.

Finally, the sub-gradient is computed exactly as stated in Theorem 4.3, and, more precisely, in Equations (8) and (9), where $\eta^*_{i,a}$ and $\psi^*_j$ are the quantities introduced in Lemma 4.2 and Line 253. In other words, for fixed $\mu$ and $\omega$, one first computes the pair of arms $(i,a)$ that attain the maximum of Equation (2), and then tests whether $\psi^*_i > \psi^*_a$ to decide which expression to use among Equations (8) and (9).

The discussion presented in Lines 272-291 then provides an efficient algorithm to compute $\eta^*_{i,a}$. Lemma C.4 in the appendix provides an analogous algorithm for the computation of $\psi^*_i$.

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

As done in previous works in MF-BAI, we have considered simulated domains in our experiments. When dealing with real-world problems, challenges arise when directly applying the multi-fidelity formalism considered in MF-BAI. For instance, the arm space might be continuous, such as in the case of hyper-parameter optimization. In this scenario, practical methods (e.g., "Multi-fidelity Bayesian optimization via deep neural networks", Li et al., NeurIPS 2020), can overcome these challenges at the price of sacrificing theoretical guarantees. An interesting future research direction to bridge this gap would be to study the MF-BAI setting under the presence of linear function approximators; e.g., by drawing inspiration from linear BAI ("Optimal best-arm identification in linear bandits", Jedra et al., NeurIPS 2020).

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

I don't see any shaded area denoting confidence intervals in Figure 3.

We thank the Reviewer for raising this point. There are actually shaded areas on the plot, but the confidence intervals are really small. This is also evident from footnote 8, where we measure the distance of ${\omega}(T)$ from $\omega^*$ at iteration $T=10^5$. In this case, the 95% confidence intervals are $0.0006$.

The appendix presents experiments with more evident confidence intervals (see, e.g., Figure 4).

Line 78: notation.

We thank the Reviewer for pointing out the typo. We have fixed it in a revised version.

Writing suggestion

We thank the Reviewer for suggesting ways to improve the presentation of our algorithm. We have incorporated the symbols also within the algorithm box in a revised version of the manuscript.

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

We thank the Reviewer for rising this point. We do believe that the fixed-budget MF-BAI is actually a valid problem that should deserve the attention of the community. In this case, the budget should be expressed as a total cost available to the learning system, and the agent might exploit the different fidelity to lower (an upper bound on) the probability of error of not recommending the optimal arm.

Although this future research direction is of interest to the community, we currently conjecture that further and ad-hoc algorithms are probably needed to face the fixed-budget problem. Indeed, to the best of the author's knowledge, fixed-budget algorithms usually follow different design principles compared to asymptotically optimal fixed-confidence ones. One of the main reasons behind this conjecture is that we expect the lower bound for the fixed-budget setting to differ from the one for fixed confidence.

Finally, we agree that one could in principle apply MF-GRAD for fixed-budget problems as suggested by the reviewer (i.e., by removing the stopping rule and terminating when the budget is over). However, we are unsure on which kind of theoretical guarantees this approach would enjoy.