[41] A. G. PEREVOZCHIKOV, *The complexity of the computation of the global extremum in a class of multi-extremum problems*, USSR Computational Mathematics and Mathematical Physics, 30 (1990), pp. 28-33.

[42] V. PICHENY, D. GINSBOURGER, AND Y. RICHET, *Noisy expected improvement and on-line computation time allocation for the optimization of simulators with tunable fidelity*, in 2nd International Conference on Engineering Optimization, 2010, p. 10 p.

[43] V. PICHENY, T. WAGNER, AND D. GINSBOURGER, *A benchmark of kriging-based infill criteria for noisy optimization*, Structural and multidisciplinary optimization, 48 (2013), pp. 607-626.

[44] S. PIYAVSKII, *An algorithm for finding the absolute extremum of a function*, USSR Computational Mathematics and Mathematical Physics, 12 (1972), pp. 57-67.

[45] P. Z. G. QIAN AND C. F. J. WU, *Bayesian hierarchical modeling for integrating low-accuracy and high-accuracy experiments*, Technometrics, 50 (2008), pp. 192-204.

[46] R. SEN, K. KANDASAMY, AND S. SHAKKOTTAI, *Multi-fidelity black-box optimization with hierarchical partitions*, in International conference on machine learning, PMLR, 2018, pp. 4538-4547.

[47] R. SEN, K. KANDASAMY, AND S. SHAKKOTTAI, *Noisy blackbox optimization using multi-fidelity queries: A tree search approach*, in The 22nd international conference on artificial intelligence and statistics, PMLR, 2019, pp. 2096-2105.

[48] X. SHANG, E. KAUFMANN, AND M. VALKO, *General parallel optimization without a metric*, in Proceedings of the 30th International Conference on Algorithmic Learning Theory, A. Garivier and S. Kale, eds., vol. 98 of Proceedings of Machine Learning Research, PMLR, 22-24 Mar 2019, pp. 762-788.

[49] B. O. SHUBERT, *A sequential method seeking the global maximum of a function*, SIAM Journal on Numerical Analysis, 9 (1972), pp. 379-388.

[50] A. SLIVKINS ET AL., *Introduction to multi-armed bandits*, Foundations and Trends® in Machine Learning, 12 (2019), pp. 1-286.

[51] J. SONG, Y. CHEN, AND Y. YUE, *A general framework for multi-fidelity Bayesian optimization with Gaussian processes*, in The 22nd International Conference on Artificial Intelligence and Statistics, PMLR, 2019, pp. 3158-3167.

[52] J. C. SPALL, *Introduction to stochastic search and optimization: estimation, simulation, and control*, Wiley-Interscience, 2003.

[53] N. SRINIVAS, A. KRAUSE, S. M. KAKADE, AND M. W. SEEGER, *Gaussian process optimization in the bandit setting: No regret and experimental design*, in Proceedings of the 27th International Conference on Machine Learning, J. Fürnkranz and T. Joachims, eds., Omnipress, 2010, pp. 1015-1022.

[54] N. SRINIVAS, A. KRAUSE, S. M. KAKADE, AND M. W. SEEGER, *Information-theoretic regret bounds for Gaussian process optimization in the bandit setting*, IEEE Transactions on information theory, 58 (2012), pp. 3088-3095.

[55] G. SUN, G. LI, S. ZHOU, W. XU, X. YANG, AND Q. LI, *Multi-fidelity optimization for sheet metal forming process*, Structural and Multidisciplinary Optimization, 44 (2011), pp. 111-124.

[56] M. VALKO, A. CARPENTIER, AND R. MUNOS, *Stochastic simultaneous optimistic optimization*, in International Conference on Machine Learning, PMLR, 2013, pp. 19-27.

[57] J. WANG, D. BASU, AND I. TRUMMER, *Procrastinated tree search: Black-box optimization with delayed, noisy, and multi-fidelity feedback*, in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 36, 2022, pp. 10381-10390.
err$_{τ}$(A', E) ≤ ε. In particular, for the “noiseless” environment E* = ((x, α) ↦→ f(x))$_{t}$≥1, there exists τ such that $\sum_{t=1}^{\tau} c(\alpha_t(E^*)) \le C$ and err$_{τ}$(A, E*) ≤ ε. Using Lemma B.1, we get that $\min\{\min_{t \le \tau} \alpha_t(E^*), \varepsilon_0/2\} \le \text{err}_τ(A, E^*) \le \varepsilon$, which implies $\min_{t \le \tau} \alpha_t(E^*) \le \varepsilon$ (since $\varepsilon_0/2 > \varepsilon$ by assumption). Because c is non-negative and non-increasing, we have:

$$C \geq \sum_{t=1}^{\tau} c(\alpha_t(E^*)) \geq c \left( \min_{t \leq \tau} \alpha_t(E^*) \right) \geq c(\varepsilon).$$

By definition of $C_{\text{inf}}(f, \varepsilon)$, this entails that $C_{\text{inf}}(f, \varepsilon) \geq c(\varepsilon)$.

<figure><img src="image_2.png" /></figure>

## Appendix C. Useful lemmas.

We recall two rather classical lemmas, and provide proofs for the convenience of the reader.

**Lemma C.1.** Let $\mathcal{X} \subset \mathbb{R}^d$ be a compact connected set with diameter $\rho$. Then for any $x \in \mathcal{X}$ and $\varepsilon \le \frac{\rho}{2}$, there exists $v \in \mathbb{R}^d$ with $\|v\| = 1$ such that $x + \varepsilon v \in \mathcal{X}$.

*Proof.* Let $x \in \mathcal{X}$ and $0 < \varepsilon \le \frac{\rho}{2}$ (the result is straightforward if $\varepsilon = 0$). Since $\rho$ is the diameter of $\mathcal{X}$ and the latter is compact, there exist $y, z \in \mathcal{X}$ such that $\|y - z\| = \rho$. Let us show by contradiction that there exists a point $x' \in \mathcal{X}$ for which $\|x - x'\| \ge \varepsilon$. Assume for a moment that for all $x' \in \mathcal{X}$, $\|x - x'\| < \varepsilon$. In that case, we would have $\|y - z\| \le \|y - x\| + \|x - z\| < 2\varepsilon \le \rho$, which is in contradiction with $\|y - z\| = \rho$.

Now that we know that it exists, let $x' \in \mathcal{X}$ be such that $\|x - x'\| \ge \varepsilon$. Because $\mathcal{X}$ is connected, there exists a continuous path $\gamma : t \in [0, 1] \mapsto \gamma(t) \in \mathcal{X}$ such that $\gamma(0) = x$ and $\gamma(1) = x'$. Let $g$ be the function $g : t \in [0, 1] \mapsto \|\gamma(t) - x\| \in \mathbb{R}$. $g$ is a continuous function from $[0, 1]$ to $\mathbb{R}$, with $g(0) = 0$ and $g(1) \ge \varepsilon > 0$, so according to the intermediate value theorem, there exists $t^* \in [0, 1]$ such that $g(t^*) = \varepsilon$. Taking $x'' = \gamma(t^*)$ and $v = \frac{x'' - x}{\|x - x''\|}$ solves the problem, because $x + \varepsilon v = x'' \in \mathcal{X}$.

<figure><img src="image_3.png" /></figure>

**Lemma C.2.** For any bounded set $E \subset \mathbb{R}^d$, and all $0 < r_1 < r_2$, we have

$$\mathcal{N}(E, r_1) \le \left( 1 + 2 \frac{r_2}{r_1} \right)^d \mathcal{N}(E, r_2).$$

The above lemma is well known and can be found, e.g., in [2, Appendix A] with a slightly weaker statement. We recall the proof for the convenience of the reader. For any $x \in \mathbb{R}^d$ and $r > 0$, we set $B(x, r) = \{u \in \mathbb{R}^d : \|u - x\| \le r\}$.

*Proof.* Fix any bounded set $E \subset \mathbb{R}^d$ and $0 < r_1 < r_2$. Consider an $r_1$-packing $F = \{x_1, \dots, x_{N_1}\}$ of $E$, with cardinality $N_1 := \mathcal{N}(E, r_1)$.

Let $F_0 = F$. We define a sequence $F_0, F_1, \dots, F_{k_{\text{end}}-1}$ of subsets of $F$ by induction, as follows. For $k \ge 1$ let $\hat{x}_k$ be any element of $F_{k-1}$, and define $B_k = F_{k-1} \cap B(\hat{x}_k, r_2)$ and $F_k = F_{k-1} \setminus B_k$. Repeating this procedure, we get an index $k_{\text{end}} \le N_1$ such that $F_{k_{\text{end}}-1}$ is non-empty while $F_{k_{\text{end}}}$ is empty.

Then, the set $\{\hat{x}_1, \dots, \hat{x}_{k_{\text{end}}}\}$ is an $r_2$-packing of $E$, so that $k_{\text{end}} \le \mathcal{N}(E, r_2)$. Let us now upper bound $N_1$ using $k_{\text{end}}$. By construction, the union of the $B_k$'s contains $F$, so for all $i \le N_1$, there exists $k \le k_{\text{end}}$ such that $x_i \in B_k$, and thus $B(x_i, r_1/2) \subset B(\hat{x}_k, r_2 + r_1/2)$. Therefore,

$$\bigcup_{1 \le i \le N_1} B(x_i, r_1/2) \subset \bigcup_{1 \le k \le k_{\text{end}}} B(\hat{x}_k, r_2 + r_1/2).$$
Moreover, the $N_1$ balls $B(x_i, r_1/2)$ are pairwise disjoint, because $F$ is an $r_1$-packing of $E$. By a volumetric argument, we thus get that $(r_1/2)^d N_1 \le (r_2 + r_1/2)^d k_{\text{end}} \le (r_2 + r_1/2)^d \mathcal{N}(E, r_2)$. Rearranging terms concludes the proof. ■

## Appendix D. The special case of constant costs.

In this short section we focus on the case of a constant cost $c(\alpha) = 1$. We formalize and prove the following very intuitive fact: when more accurate evaluations come at no additional cost, choosing the best accuracy available is always optimal. To avoid boundary effects, we slightly extend the setting by allowing the learner to choose $\alpha_t$ identically equal to zero.

**Lemma D.1.** Let $f: \mathcal{X} \to \mathbb{R}$ be an L-Lipschitz function, and assume $c: \mathbb{R}_+ \to \mathbb{R}_+$ is the constant function given by $c(\alpha) = 1$ for all $\alpha \ge 0$. Then,

* $\sigma(A, E, \varepsilon) = \inf\{t \in \mathbb{N}^*: \xi_t(E) \le \varepsilon\}$;

* the smallest cost complexity (against the worst environment) is achieved by certified algorithms that choose $\alpha_t = 0$ for all $t \in \mathbb{N}^*$.

*Proof of Lemma D.1.* Let $f$ be an L-Lipschitz function, and $\varepsilon > 0$. Since $c(\alpha) = 1$ for all $\alpha \ge 0$, the definition of $\sigma(A, E, \varepsilon)$ directly yields $\sigma(A, E, \varepsilon) = \inf\{t \in \mathbb{N}^*: \xi_t(E) \le \varepsilon\}$.

Recall that $\mathcal{A}$ denotes the set of all certified algorithms, and that $\mathcal{E}(f)$ is the set of all environments associated with the function $f$. As discussed in the introduction, $\alpha_t$ depends on $E$ only via the inaccurate approximations $y_1, \dots, y_{t-1}$ of $f$. We write $\alpha_t(y_1, \dots, y_{t-1})$ instead of $\alpha_t$ to clarify this dependency when needed. We denote by $\mathcal{A}_0$ the set of all certified algorithms such that $\alpha_t(y_1, \dots, y_{t-1}) = 0$ for all $t \in \mathbb{N}^*$ against all possible realizations of $y_1, \dots, y_{t-1}$.

Formally, what we want to prove is

$$ \inf_{A' \in \mathcal{A}_0} \sup_{E \in \mathcal{E}(f)} \sigma(A', E, \varepsilon) \le \inf_{A \in \mathcal{A}} \sup_{E \in \mathcal{E}(f)} \sigma(A, E, \varepsilon). $$

Let $\mathcal{A}$ be an algorithm in $\mathcal{A}$, and let $E^* \in \mathcal{E}(f)$ be the environment for which $E_t^*(x, \alpha) = f(x)$ for all $t \in \mathbb{N}^*$, all $x \in \mathcal{X}$ and all $\alpha \ge 0$. Note that

$$ (D.1) \qquad \sup_{E \in \mathcal{E}(f)} \sigma(A, E, \varepsilon) \ge \sigma(A, E^*, \varepsilon) $$

Now, let $\tilde{A}$ be the same algorithm as $\mathcal{A}$, with one difference: whatever the situation and the environment $E$, for all $t \in \mathbb{N}$, $\tilde{\alpha}_t(y_1, \dots, y_{t-1}) = 0$. Then $\tilde{A} \in \mathcal{A}_0$. Moreover, because of the particularity of $E^*$, $\mathcal{A}$ and $\tilde{A}$ will behave the same way against $E^*$: the sequences of query points $(x_t)_{t \in \mathbb{N}^*}$, recommendations $(x_t^*)_{t \in \mathbb{N}^*}$ and certificates $(\xi_t)_{t \in \mathbb{N}^*}$ are the same for $\mathcal{A}$ and for $\tilde{A}$. From this, we get that $\sigma(A, E^*, \varepsilon) = \sigma(\tilde{A}, E^*, \varepsilon)$. Combining with (D.1) yields

$$ (D.2) \qquad \inf_{A \in \mathcal{A}} \sup_{E \in \mathcal{E}(f)} \sigma(A, E, \varepsilon) \ge \inf_{A \in \mathcal{A}} \sigma(A, E^*, \varepsilon) \ge \inf_{\tilde{A} \in \mathcal{A}_0} \sigma(\tilde{A}, E^*, \varepsilon) $$

Let us now show that

$$ (D.3) \qquad \inf_{A' \in \mathcal{A}_0} \sigma(A', E^*, \varepsilon) = \inf_{A' \in \mathcal{A}_0} \sup_{E \in \mathcal{E}(f)} \sigma(A', E, \varepsilon), $$
which, combined with (D.2), will conclude the proof.

To see why (D.3) holds, let $A'$ be any certified algorithm with $\alpha_t = 0$ for all $t \in \mathbb{N}^*$, whatever the past observations $y_1, \dots, y_{t-1}$, and let $E$, and $E'$ be two environments in $\mathcal{E}(f)$. Then, for all $x \in \mathcal{X}$, $E_t(x, 0) = E'_t(x, 0) = f(x)$, because environments should satisfy $|E_t(x, \alpha) - f(x)| \le \alpha$ for all $x \in \mathcal{X}$ and $\alpha \ge 0$. Therefore, the behavior of $A'$ against any $E \in \mathcal{E}(f)$ is the same as against $E^*$ which proves (D.3). ■

REFERENCES

[1] P. AUER, N. CESA-BIANCHI, AND P. FISCHER, *Finite-time analysis of the multiarmed bandit problem*, Mach. Learn., 47 (2002), pp. 235–256.

[2] F. BACHOC, T. CESARI, AND S. GERCHINOVITZ, *Instance-dependent bounds for zeroth-order Lipschitz optimization with error certificates*, Advances in Neural Information Processing Systems, 34 (2021), pp. 24180–24192.

[3] P. L. BARTLETT, V. GABILLON, AND M. VALKO, *A simple parameter-free and adaptive approach to optimization under a minimal local smoothness assumption*, in Algorithmic Learning Theory, PMLR, 2019, pp. 184–206.

[4] S. P. BHAT AND C. AMBALLA, *Identifying near-optimal decisions in linear-in-parameter bandit models with continuous decision sets*, in Proceedings of the Thirty-Eighth Conference on Uncertainty in Artificial Intelligence, J. Cussens and K. Zhang, eds., vol. 180 of Proceedings of Machine Learning Research, PMLR, 01–05 Aug 2022, pp. 181–190.

[5] J. F. BONNANS, *Convex and Stochastic Optimization*, Universitext, Springer Cham, 2019.

[6] C. BOUTTIER, T. CESARI, M. DUCOFFE, AND S. GERCHINOVITZ, *Regret analysis of the Piyavskii-Shubert algorithm for global Lipschitz optimization*, 2020, https://arxiv.org/abs/2002.02390v4.

[7] S. BOYD AND L. VANDENBERGHE, *Convex optimization*, Cambridge University Press, 2004.

[8] S. BUBECK, *Convex optimization: Algorithms and complexity*, Foundations and Trends in Machine Learning, 8 (2015), pp. 231–357.

[9] S. BUBECK, R. MUNOS, G. STOLTZ, AND C. SZEPESVÁRI, *X-armed bandits*, Journal of Machine Learning Research, 12 (2011).

[10] S. BUBECK, G. STOLTZ, AND J. Y. YU, *Lipschitz bandits without the Lipschitz constant*, in Algorithmic Learning Theory, J. Kivinen, C. Szepesvári, E. Ukkonen, and T. Zeugmann, eds., Berlin, Heidelberg, 2011, Springer Berlin Heidelberg, pp. 144–158.

[11] A. D. BULL, *Convergence rates of efficient global optimization algorithms*, Journal of Machine Learning Research, 12 (2011), pp. 2879–2904.

[12] E. CARLSSON, D. BASU, F. JOHANSSON, AND D. DUBHASHI, *Pure exploration in bandits with linear constraints*, in Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, S. Dasgupta, S. Mandt, and Y. Li, eds., vol. 238 of Proceedings of Machine Learning Research, PMLR, 02–04 May 2024, pp. 334–342.

[13] E. CONTAL, D. BUFFONI, A. ROBICQUET, AND N. VAYATIS, *Parallel Gaussian process optimization with upper confidence bound and pure exploration*, in Joint European Conference on Machine Learning and Knowledge Discovery in Databases, Springer, 2013, pp. 225–240.

[14] Y. DANILIN, *Estimation of the efficiency of an absolute-minimum-finding algorithm*, USSR Computational Mathematics and Mathematical Physics, 11 (1971), pp. 261–267.

[15] R. DEGENNE, W. M. KOOLEN, AND P. MÉNARD, *Non-asymptotic pure exploration by solving games*, in Advances in Neural Information Processing Systems, H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, eds., vol. 32, Curran Associates, Inc., 2019.

[16] R. DEGENNE, P. MENARD, X. SHANG, AND M. VALKO, *Gamification of pure exploration for linear bandits*, in Proceedings of the 37th International Conference on Machine Learning, H. D. III and A. Singh, eds., vol. 119 of Proceedings of Machine Learning Research, PMLR, 13–18 Jul 2020, pp. 2432–2442.

[17] K. DEWETTINCK, A. DE VISSCHER, L. DEROO, AND A. HUYGHEBAERT, *Modeling the steady-state thermodynamic operation point of top-spray fluidized bed processing*, Journal of Food Engineering, 39 (1999), pp. 131–143.
[18] E. EVEN-DAR, S. MANNOR, AND Y. MANSOUR, PAC bounds for multi-armed bandit and Markov Decision Processes, in Computational Learning Theory, J. Kivinen and R. H. Sloan, eds., Springer Berlin Heidelberg, 2002, pp. 255-270.

[19] E. EVEN-DAR, S. MANNOR, AND Y. MANSOUR, Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems, Journal of Machine Learning Research, 7 (2006), pp. 1079-1105.

[20] C. FIEGEL, V. GABILLON, AND M. VALKO, Adaptive multi-fidelity optimization with fast learning rates, in International Conference on Artificial Intelligence and Statistics, PMLR, 2020, pp. 3493-3502.

[21] A. I. FORRESTER, A. J. KEANE, AND N. W. BRESSLOFF, Design and analysis of "noisy" computer experiments, AIAA journal, 44 (2006), pp. 2331-2339.

[22] A. I. FORRESTER, A. SÓBESTER, AND A. J. KEANE, Multi-fidelity optimization via surrogate modelling, Proceedings of the Royal Society A: mathematical, physical and engineering sciences, 463 (2007), pp. 3251-3269.

[23] A. GARIVIER AND E. KAUFMANN, Optimal best arm identification with fixed confidence in 29th Annual Conference on Learning Theory, vol. 49 of Proceedings of Machine Learning Research, 2016, pp. 998-1027.

[24] A. GARIVIER AND E. KAUFMANN, Nonasymptotic sequential tests for overlapping hypotheses applied to near-optimal arm identification in bandit models, Sequential Analysis, 40 (2021), pp. 61-96.

[25] R. GARNETT, Bayesian optimization, Cambridge University Press, 2023.

[26] K. GEISELHART, L. OZOROSKI, J. FENBERT, E. SHIELDS, AND W. LI, Integration of multifidelity multi-disciplinary computer codes for design and analysis of supersonic aircraft, in 49th AIAA Aerospace Sciences Meeting Including the New Horizons Forum and Aerospace Exposition, 2011, p. 465.

[27] J.-B. GRILL, M. VALKO, AND R. MUNOS, Black-box optimization of noisy functions with unknown smoothness, Advances in Neural Information Processing Systems, 28 (2015).

[28] P. HANSEN, B. JAUMARD, AND S.-H. LU, On the number of iterations of Piyavskii's global optimization algorithm, Mathematics of Operations Research, 16 (1991), pp. 334-350.

[29] P. HANSEN, B. JAUMARD, AND S.-H. LU, Global optimization of univariate Lipschitz functions: I. survey and properties, Mathematical Programming, 55 (1992), pp. 251-272.

[30] P. HANSEN, B. JAUMARD, AND S.-H. LU, Global optimization of univariate Lipschitz functions: II. new algorithms and computational comparison, Mathematical Programming, 55 (1992), pp. 273-292.

[31] M. HORN, Optimal algorithms for global optimization in case of unknown Lipschitz constant, Journal of Complexity, 22 (2006), pp. 50-70.

[32] D. HUANG, T. T. ALLEN, W. I. NOTZ, AND R. A. MILLER, Sequential kriging optimization using multiple-fidelity evaluations, Structural and Multidisciplinary Optimization, 32 (2006), pp. 369-382.

[33] P. JAIN AND P. KAR, Non-convex optimization for machine learning, Foundations and Trends® in Machine Learning, 10 (2017), pp. 142-336.

[34] Y. JEDRA AND A. PROUTIERE, Optimal best-arm identification in linear bandits, in Advances in Neural Information Processing Systems, H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, eds., vol. 33, Curran Associates, Inc., 2020, pp. 10007-10017.

[35] D. R. JONES, C. D. PERTTUNEN, AND B. E. STUCKMAN, Lipschitzian optimization without the Lipschitz constant, Journal of Optimization Theory and Applications, 79 (1993), pp. 157-181.

[36] D. R. JONES, M. SCHONLAU, AND W. J. WELCH, Efficient global optimization of expensive black-box functions, Journal of Global optimization, 13 (1998), pp. 455-492.

[37] M. JOURDAN AND R. DEGENNE, Choosing answers in epsilon-best-answer identification for linear bandits, in Proceedings of the 39th International Conference on Machine Learning, K. Chaudhuri, S. Jegelka, L. Song, C. Szepesvari, G. Niu, and S. Sabato, eds., vol. 162 of Proceedings of Machine Learning Research, PMLR, 17-23 Jul 2022, pp. 10384-10430.

[38] K. KANDASAMY, G. DASARATHY, J. OLIVA, J. SCHNEIDER, AND B. PÓCZOS, Multi-fidelity Gaussian process bandit optimisation, Journal of Artificial Intelligence Research, 66 (2019), pp. 151-196.

[39] K. KANDASAMY, G. DASARATHY, J. B. OLIVA, J. SCHNEIDER, AND B. PÓCZOS, Gaussian process bandit optimisation with multi-fidelity evaluations, Advances in Neural Information Processing Systems, 29 (2016), pp. 1000-1008.

[40] K. KANDASAMY, G. DASARATHY, B. PÓCZOS, AND J. SCHNEIDER, The multi-fidelity multi-armed bandit, Advances in Neural Information Processing Systems, 29 (2016), pp. 1777-1785.
[41] A. KAZEROUNI AND L. M. WEIN, *Best arm identification in generalized linear bandits*, Operations Research Letters, 49 (2021), pp. 365-371.

[42] R. KLEINBERG, A. SLIVKINS, AND E. UPFAL, *Multi-armed bandits in metric spaces*, in Proceedings of the fortieth annual ACM symposium on Theory of computing, 2008, pp. 681-690.

[43] R. KLEINBERG, A. SLIVKINS, AND E. UPFAL, *Bandits and experts in metric spaces*, Journal of the ACM (JACM), 66 (2019), pp. 1-77.

[44] H. J. KÜSHNER, *A new method of locating the maximum point of an arbitrary multipeak curve in the presence of noise*, Journal of Basic Engineering, 86 (1964), pp. 97-106.

[45] J. LARSON, M. MENICKELLY, AND S. M. WILD, *Derivative-free optimization methods*, Acta Numerica, 28 (2019), p. 287-404.

[46] T. LATTIMORE AND C. SZEPESVÁRI, *Bandit algorithms*, Cambridge University Press, 2020.

[47] L. LE GRATIET, *Multi-fidelity Gaussian process regression for computer experiments*, PhD thesis, Université Paris-Diderot-Paris VII, 2013.

[48] A. LOCATELLI AND A. CARPENTIER, *Adaptivity to smoothness in X-armed bandits*, in Conference on Learning Theory, PMLR, 2018, pp. 1463-1492.

[49] C. MALHERBE AND N. VAYATIS, *Global optimization of Lipschitz functions*, in International Conference on Machine Learning, PMLR, 2017, pp. 2314-2323.

[50] S. MANNOR AND J. N. TSITSIKLIS, *The sample complexity of exploration in the multi-armed bandit problem*, Journal of Machine Learning Research, 5 (2004), pp. 623-648.

[51] J. MOČKUS, *On bayesian methods for seeking the extremum*, in Optimization Techniques IFIP Technical Conference Novosibirsk, G. I. Marchuk, ed., Springer Berlin Heidelberg, 1975, pp. 400-404.

[52] R. MUNOS, *Optimistic optimization of a deterministic function without the knowledge of its smoothness*, Advances in neural information processing systems, 24 (2011).

[53] R. MUNOS, *From bandits to Monte-Carlo Tree Search: The optimistic principle applied to optimization and planning*, Foundations and Trends® in Machine Learning, 7 (2014), pp. 1-129.

[54] Y. NESTEROV, *Introductory lectures on convex optimization: a basic course*, vol. 87 of Applied Optimization, Springer US, 2004.

[55] B. PEHERSTORFER, K. WILLCOX, AND M. GUNZBURGER, *Survey of multifidelity methods in uncertainty propagation, inference, and optimization*, Siam Review, 60 (2018), pp. 550-591.

[56] A. G. PEREVOZCHIKOV, *The complexity of the computation of the global extremum in a class of multi-extremum problems*, USSR Computational Mathematics and Mathematical Physics, 30 (1990), pp. 28-33.

[57] V. PICHENY, D. GINSBOURGER, AND Y. RICHET, *Noisy expected improvement and on-line computation time allocation for the optimization of simulators with tunable fidelity*, in 2nd International Conference on Engineering Optimization, 2010, p. 10 p.

[58] V. PICHENY, T. WAGNER, AND D. GINSBOURGER, *A benchmark of kriging-based infill criteria for noisy optimization*, Structural and multidisciplinary optimization, 48 (2013), pp. 607-626.

[59] S. PIYAVSKII, *An algorithm for finding the absolute extremum of a function*, USSR Computational Mathematics and Mathematical Physics, 12 (1972), pp. 57-67.

[60] P. Z. G. QIAN AND C. F. J. WU, *Bayesian hierarchical modeling for integrating low-accuracy and high-accuracy experiments*, Technometrics, 50 (2008), pp. 192-204.

[61] R. SEN, K. KANDASAMY, AND S. SHAKKOTTAI, *Multi-fidelity black-box optimization with hierarchical partitions*, in International conference on machine learning, PMLR, 2018, pp. 4538-4547.

[62] R. SEN, K. KANDASAMY, AND S. SHAKKOTTAI, *Noisy blackbox optimization using multi-fidelity queries: A tree search approach*, in The 22nd international conference on artificial intelligence and statistics, PMLR, 2019, pp. 2096-2105.

[63] X. SHANG, E. KAUFMANN, AND M. VALKO, *General parallel optimization without a metric*, in Proceedings of the 30th International Conference on Algorithmic Learning Theory, A. Garivier and S. Kale, eds., vol. 98 of Proceedings of Machine Learning Research, PMLR, 22-24 Mar 2019, pp. 762-788.

[64] B. O. SHUBERT, *A sequential method seeking the global maximum of a function*, SIAM Journal on Numerical Analysis, 9 (1972), pp. 379-388.

[65] A. SLIVKINS, *Introduction to multi-armed bandits*, Foundations and Trends® in Machine Learning, 12 (2019), pp. 1-286.

[66] M. SOARE, A. LAZARIC, AND R. MUNOS, *Best-arm identification in linear bandits*, in Advances in
Neural Information Processing Systems, Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Weinberger, eds., vol. 27, Curran Associates, Inc., 2014, pp. 828–836.

[67] J. SONG, Y. CHEN, AND Y. YUE, *A general framework for multi-fidelity Bayesian optimization with Gaussian processes*, in The 22nd International Conference on Artificial Intelligence and Statistics, PMLR, 2019, pp. 3158–3167.

[68] J. C. SPALL, *Introduction to stochastic search and optimization: estimation, simulation, and control*, Wiley-Interscience, 2003.

[69] N. SRINIVAS, A. KRAUSE, S. M. KAKADE, AND M. W. SEEGER, *Gaussian process optimization in the bandit setting: No regret and experimental design*, in Proceedings of the 27th International Conference on Machine Learning, J. Fürnkranz and T. Joachims, eds., Omnipress, 2010, pp. 1015–1022.

[70] N. SRINIVAS, A. KRAUSE, S. M. KAKADE, AND M. W. SEEGER, *Information-theoretic regret bounds for Gaussian process optimization in the bandit setting*, IEEE Transactions on information theory, 58 (2012), pp. 3088–3095.

[71] G. SUN, G. LI, S. ZHOU, W. XU, X. YANG, AND Q. LI, *Multi-fidelity optimization for sheet metal forming process*, Structural and Multidisciplinary Optimization, 44 (2011), pp. 111–124.

[72] M. VALKO, A. CARPENTIER, AND R. MUNOS, *Stochastic simultaneous optimistic optimization*, in International Conference on Machine Learning, PMLR, 2013, pp. 19–27.

[73] M. J. WAINWRIGHT, *High-Dimensional Statistics: A Non-Asymptotic Viewpoint*, Cambridge Series in Statistical and Probabilistic Mathematics, Cambridge University Press, 2019.

[74] J. WANG, D. BASU, AND I. TRUMMER, *Procrastinated tree search: Black-box optimization with delayed, noisy, and multi-fidelity feedback*, in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 36, 2022, pp. 10381–10390.

[75] P.-A. WANG, R.-C. TZENG, AND A. PROUTIERE, *Fast pure exploration via Frank-Wolfe*, in Advances in Neural Information Processing Systems, M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, eds., vol. 34, Curran Associates, Inc., 2021, pp. 5810–5821.