Xuedong Shang
email: xuedong.shang@inria.fr

Emilie Kaufmann
email: emilie.kaufmann@univ-lille.fr

Michal Valko
email: valkom@google.com

A simple dynamic bandit algorithm for hyper-parameter tuning

Hyper-parameter tuning is a major part of modern machine learning systems. The tuning itself can be seen as a sequential resource allocation problem. As such, methods for multi-armed bandits have been already applied. In this paper, we view hyper-parameter optimization as an instance of best-arm identification in infinitely many-armed bandits. We propose D-TTTS, a new adaptive algorithm inspired by Thompson sampling, which dynamically balances between refining the estimate of the quality of hyper-parameter configurations previously explored and adding new hyper-parameter configurations to the pool of candidates. The algorithm is easy to implement and shows competitive performance compared to state-of-the-art algorithms for hyper-parameter tuning.

1.

Introduction

Training a machine learning algorithm often requires to specify several parameters. For instance, for neural networks, it is the architecture of the network and also the parameters of the gradient algorithm used or the choice of regularization. These hyper-parameters are difficult to learn through the standard training process and are often manually specified.

When it is not feasible to design algorithms with a few hyper-parameters, we opt for hyper-parameter optimization (HPO). HPO can be viewed as a black-box optimization problem where the evaluation of the objective function is expensive as it is the accuracy of a learning algorithm for a given configuration of hyper-parameters. This vastly limits the number of evaluations that can be carried out, which calls for a design of efficient high-level algorithms that automate the tuning procedure.

Several naive but daily used HPO methods are grid search and random search. More sophisticated methods address HPO as a sequential resource allocation problem, by adaptively choosing the next hyper-parameter(s) to explore, based on the result obtained previously. For example, evolutionary optimization follows a process inspired by the biological concept of evolution, which repeatedly replaces the worst-performing hyper-parameter configurations from a randomly initialized population of solutions; see [START_REF] Loshchilov | CMA-ES for hyperparameter optimization of deep neural networks[END_REF] for an example of using CMA-ES for hyper-parameter tuning. A major drawback of evolutionary optimization is its lack of theoretical understanding.

Bayesian optimization (BO) is another approach that leverages the sequential nature of the setting. BO depends on a prior belief for the target function, typically a Gaussian c 2019 Xuedong Shang, Emilie Kaufmann, Michal Valko. process. This prior distribution can be updated to a posterior given a sequence of observations. Several algorithms exploiting this posterior distribution to decide where to sample next have been given (see [START_REF] Shahriari | Taking the human out of the loop: A review of Bayesian optimization[END_REF], for a survey). [START_REF] Snoek | Practical bayesian optimization of machine learning algorithms[END_REF] and [START_REF] Klein | RoBO: A flexible and robust Bayesian optimization framework in Python[END_REF] provide Python packages called Spearmint and RoBO to perform hyperparameter tuning with BO methods. Similar packages are available for PyTorch (BoTorch 1 ) and TensorFlow (GPflowOpt by [START_REF] Knudde | GPflowOpt: A Bayesian optimization library using TensorFlow[END_REF]). Among BO algorithms, TPE [START_REF] Bergstra | Algorithms for hyperparameter optimization[END_REF] and SMAC [START_REF] Hutter | Sequential model-based optimization for general algorithm configuration[END_REF] were specifically proposed for HPO. A shortcoming of BO is that most algorithms select where to sample next based on optimizing some acquisition function computed from the posterior, e.g., the expected improvement [START_REF] Jones | Efficient global optimization of expensive black-box functions[END_REF]. This auxiliary task cannot be solved analytically but needs to be performed itself by optimization procedures as L-BFGS that make the process slow.

Bandits (see [START_REF] Lattimore | Bandit algorithms[END_REF] for a recent book) are a simple model for sequential resource allocation, and some bandit tools have already been explored for global optimization and HPO: First, in the field of Bayesian optimization, the GP-UCB algorithm [START_REF] Srinivas | Gaussian process optimization in the bandit setting: No regret and experimental design[END_REF] is a Gaussian process extension of the classical UCB bandit algorithm [START_REF] Auer | Finite-time analysis of the multi-armed bandit problem[END_REF]. Later, [START_REF] Hoffman | On correlation and budget constraints in model-based bandit optimization with application to automatic machine learning[END_REF] proposed to use best-arm identification (BAI) tools-still with a Bayesian flavor-for automated machine learning, where the goal is to smartly try hyper-parameters from a pre-specified finite grid.

However, in most cases, the number of hyper-parameter configurations to explore is infinite. In this paper, we investigate the use of bandit tools suited for an infinite number of arms. There are two lines of work for tackling a very large or infinite number of configurations (arms). The first combines standard bandit tools with a hierarchical partitioning of the arm space and aims at exploiting the (possibly unknown) smoothness of the black-box function to optimize [START_REF] Bubeck | X -armed bandits[END_REF][START_REF] Grill | Black-box optimization of noisy functions with unknown smoothness[END_REF][START_REF] Shang | General parallel optimization without a metric[END_REF][START_REF] Peter | A simple parameter-free and adaptive approach to optimization under a minimal local smoothness assumption[END_REF]. To the best of our knowledge, these methods have never been investigated for HPO. The second line of work does not assume any smoothness: At each round, the learner may ask for a new arm from a reservoir distribution ν 0 (pick randomly a new hyper-parameter configuration) and add it to the current arm pool A, or re-sample one of the previous arms (evaluate configuration already included in A), in order to find an arm with a good mean reward (i.e., a hyper-parameter configuration with a good validation accuracy). The stochastic infinitely many-armed bandits (SIAB) is studied by [START_REF] Berry | Bandit problems with infinitely many arms[END_REF]; [START_REF] Wang | Algorithms for infinitely many-armed bandits[END_REF] for the rewards maximization problem while [START_REF] Carpentier | Simple regret for infinitely many armed bandits[END_REF]; Aziz et al. (2018a) study the simple regret problem, which is related to BAI. While most proposed algorithms consist of querying an adequate number of arms from the reservoir before running a standard BAI algorithm, [START_REF] Li | Hyperband: Bandit-based configuration evaluation for hyperparameter optimization[END_REF] propose a more robust approach called Hyperband that uses several such phases.

In this paper, we go even further and propose the first dynamic algorithm for BAI in SIAB, that at each round, may either query a new arm from the reservoir or re-sample arms previously queried. Our algorithm leverages a Bayesian model and builds on the toptwo Thompson sampling (TTTS) algorithm by [START_REF] Russo | Simple Bayesian algorithms for best arm identification[END_REF]. An extensive numerical study is presented to show the competitiveness of our algorithm with respect to state-of-the-art HPO methods.

Hyper-parameter optimization

In this paper, we view HPO as a particular global optimization setting, for which the target function f is a mapping from a hyper-parameter configuration to some measure of failure for the machine learning algorithm trained with these hyper-parameters. Formally, we aim at solving an optimization problem of the form f = min{f (λ) : λ ∈ Ω}, where λ denotes a configuration of hyper-parameters chosen from a configuration space Ω. A hyper-parameter optimizer is a sequential procedure, that at each round t, selects a configuration λ t to evaluate using some sampling rule, after which a (costly and noisy) evaluation of f (λ t ) is observed. Besides, a hyper-parameter configuration λ is recommended as a guess for a close-to-optimal configuration at the end. The hope is that f ( λ ) is not far from f . We restrict our presentation to hyper-parameter tuning for supervised learning algorithms. Given a training dataset D train containing n labeled examples in X × Y and a choice of hyper-parameter configuration λ, a supervised learning algorithm (neural network, SVM, gradient boosting, . . . ) produces a predictor g (n)

λ : X → Y. Note that there can be some randomness in the training process (e.g., if stochastic gradient descent is used) so that g

(n)
λ may still be random for a given training set and hyper-parameters. The goal is to build a predictor that generalizes well. If we had access to the distribution P that generated the data (i.e., assuming that data points in D train are i.i.d. from P), this generalization power would be measured by the risk f

(λ) E Y , g (n)
λ (X) , where is some loss function measuring the distance between two predictions and the expectation is taken on (X, Y ) ∼ P and the possible randomness in the training process.

In practice, however, the explicit evaluation of f is impossible, but there are several methods for noisy evaluations. We can either compute the validation error of g

(n) λ on a held-out validation set, 1/|D valid | |Dvalid| i=1 ( g (n)
λ (x i ), y i ), or a cross validation error over the training set as an approximation of the objective.

Active Thompson sampling for HPO

HPO can be cast as a BAI in bandits. However, standard algorithms are not directly applicable since the search space is often continuous. We thus turn our attention to BAI an infinitely many-armed bandits; see Appendix A for a detailed discussion.

In this section, we introduce a new algorithm for BAI in an infinite bandit model, that is an adaptation of Thompson sampling [START_REF] William | On the likelihood that one unknown probability exceeds another in view of the evidence of two samples[END_REF]. Thompson sampling can be seen as the very first bandit algorithm ever proposed, but has been used for the rewards maximization objective, which is quite different from BAI, as explained by [START_REF] Bubeck | Pure in multi-armed bandits problems[END_REF]. Instead of using vanilla Thompson sampling, we build on TTTS that is an adaptation of Thompson sampling for BAI in finite-arm bandits. Unlike the state-of-the-art algorithm SequentialHalving that requires the knowledge of the total budget to operate, TTTS is particularly appealing as it does not need to have it. Such algorithms are referred to as anytime. Besides, it is known to be optimal in a Bayesian (asymptotic) sense, as it attains the best possible rate of decay of the posterior probability of the set of wrong models.

As a Bayesian algorithm, TTTS uses a prior distribution Π 0 over the vector of means of the K arms, µ (µ 1 , . . . , µ K ), which can be updated to a posterior distribution Π t after t observations. Under the Bernoulli bandit model, arm i produces a reward Y t,i = 1 with probability µ i , and Y t,i = 0 with probability 1 -µ i when sampled at round t. Given independent uniform prior for the mean of each arm, the posterior distribution on µ is a product of K Beta distributions: Π t = K i=1 Beta(1 + S t,i , N t,i -S t,i + 1), where N t,i is the number of selections of arm i until round t and S t,i is the sum of rewards obtained from that arm. At each round t, TTTS chooses one arm from the following two candidates to evaluate: (1) it first samples a parameter θ from Π t-1 , and the first candidate is defined as

I (1) t arg max i∈A θ i , (2) it repeatedly samples new θ until I (2) t arg max i∈A θ i is different from I (1)
t . TTTS depends on a parameter β ∈ (0, 1). In particular, the algorithm selects I t = I

(1) t with probability β and I t = I

(2) t with probability 1 -β. TTTS can also be used for bandit settings in which the rewards are bounded in [0, 1] by using a binarization trick first proposed by [START_REF] Agrawal | Analysis of Thompson sampling for the multi-armed bandit problem[END_REF]: When a reward Y t,i ∈ [0, 1] is observed, the algorithm is updated with a fake reward Y t,i ∼ Ber(Y t,i ) ∈ {0, 1}. TTTS can thus be used for BAI for a finite number of arms that with rewards in [0, 1]. We now present a simple way of extending TTTS to deal with an infinite number of arms.

Dynamic TTTS In an infinite bandit algorithm, at each round, we either query a new arm from the reservoir and sample it, or re-sample a previous arm. In a Bayesian setting, we can also imagine that at each round, an arm is queried from the reservoir and added with a uniform prior to the list of queried arms, regardless of whether it is sampled or not. Then, at round t, D-TTTS consists in running TTTS on these t arms, out of which several are endowed with a uniform prior and have never been sampled.

Leveraging the fact the the maximum of k uniform distribution has a Beta(k, 1) distribution and that TTTS only depends on the maxima of posterior samples, we give the following equivalent implementation for D-TTTS (Algorithm 1). Letting L t be the list of arms that have been queried from the reservoir and sampled at least once before round t, at round t we run TTTS on the set A t L t ∪ {µ 0 } where µ 0 is a pseudo-arm with posterior distribution Beta(t -k t , 1), where k t |L t |.

It remains to decide how to recommend the arm as our best guess. In this paper, we choose the most natural recommendation strategy for Bayesian algorithms that outputs the arm with the largest posterior probability of being optimal. Letting Θ i be the subset of the set Θ of possible mean vectors such that arm i is optimal, Θ i θ ∈ Θ | θ i > max j =i θ j , the posterior probability that arm i is optimal after round t is defined as Π t (Θ i ). At any time t, we therefore recommend arm I t arg max i∈A Π t (Θ i ).

Experiments

We benchmark our bandit-based strategy against different types of HPO algorithms, namely, TPE, random search, Hyperband and a simple Thompson sampling variant of Hyperband (called H-TTTS described in Appendix B), for the tuning of classifiers (SVM and MLP) on 4 different classification tasks: wine, breast cancer, and adult datasets from UCI machine learning repository [START_REF] Dua | UCI machine learning repository[END_REF]; and the MNIST dataset [START_REF] Lecun | Gradient-based learning applied to document recognition[END_REF].

For all the methods, a noisy evaluation of the black-box function f (see the terminology introduced in Section 2) for a hyper-parameter configuration λ consists in performing a shuffled 3-fold cross-validation on D train . More precisely, given a random partitioning ∪ 3 j=1 D j valid of D train , where the folds are of equal size, we train a classifier g (j) λ

Algorithm 1 Sampling rule of Dynamic TTTS (D-TTTS) Input: β; B (total budget); ν 0 Initialization:

µ 1 ∼ ν 0 ; t ← 0; A ← {µ 0 , µ 1 }; m ← 1; S 0 , N 0 ← 0; S 1 ∼ Ber(µ 1 ), N 1 ← 1 1: while t < B do 2: ∀i = 0, . . . , m, θ i ∼ Beta(S i + 1, N i -S i + 1); U ∼ U([0, 1]) 3:
I (1) ← arg max i=0,...,m θ i 4:

if U > β then 5:

while

I (2) = I (1) do 6: ∀i = 0, . . . , m, θ i ∼ Beta(S i + 1, N i -S i + 1)
7:

I (2) ← arg max i=0,...,m θ i 8:
end while 9:

I (1) ← I (2)
10:

end if

11: if I (1) = 0 then 12:
Y ← evaluate arm I (1) ; X ∼ Ber(Y )

13:

S I (1) ← S I (1) + X; N I (1) ← N I (1) + 1; S 0 ← S 0 + 1 14:
else 15:

µ m+1 ∼ ν 0 ; A ← A ∪ {µ m+1 }; 16: Y ← evaluate arm m + 1; X ∼ Ber(Y ) 17: S m+1 ← X; N m+1 ← 1; m ← m + 1 18:
end if 19:

t ← t + 1 20: end while on D train \D j valid for each fold j and compute the average validation error defined as e 1/|D train | 3

j=1 i∈D j valid 1{ g (j)
λ (x i ) = y i }, which we report as a noisy estimate of the risk f (λ) P( g

(n) λ (X) = Y ).
Observe that both the noisy evaluation and the value of f belong to [0, 1]. Therefore we can introduce an arm with rewards in [0, 1] for each hyper-parameter λ. Sampling arm λ produces reward r

1 -e ∈ [0, 1] with a different random partitioning and random seed for training for each selection. Arm λ is assumed to have mean of 1 -f (λ). In an infinite arm setting, querying a new arm from the reservoir corresponds to selecting a new hyperparameter at random from the search space. With these two notions (arm sampling and reservoir querying), our algorithm for infinite BAI applies to HPO.

For the experiments, we adapt the recommendation rule of D-TTTS to the HPO applications considered and always recommend the hyper-parameter configuration that has produced the smallest cross-validation error so far (which is also the recommendation rule used by other approaches, e.g., Hyperband). For all methods, we report the cross-validation error for the recommended hyper-parameter configuration, as a function of time. We stress again that, unlike in standard bandits, where we could use the simple regret as a performance metric, we do not have access to the ground truth generalization error in real classification tasks. Therefore, we only report a proxy of the true error rate that we are interested in.

Results

We first benchmark2 our methods on a few simple UCI datasets using SVM from scikit-learn as the classifier. We optimize over two hyper-parameters: the penalty parameter C and the kernel coefficient γ3 for an RBF kernel, for which the pre-defined search bounds are both 10 -5 , 10 5 .

Fig. 1a shows the mean cross-validation error of SVM run on the UCI wine dataset over 24 pulls4 averaged on 100 runs. The task is to predict the quality score of wine (between 0 and 10) given 11 attributes. Recall that one iteration corresponds to one arm pull. In this experiment, D-TTTS improves over other benchmark algorithms. Fig. 1b is the same experiment run on the UCI breast cancer dataset over 81 pulls. The task is to predict whether a patient has breast cancer based on 32 attributes. We repeat the experiment 100 times. This time, D-TTTS is slightly worse than Hyperband at the beginning, but improves later. Finally, we optimize SVM on a relatively more complicated UCI adult dataset over 162 pulls, for which the result is shown in Fig. 1c. The task is to tell whether the income of an individual is higher than 50k or not given 14 attributes. This experiment is also averaged over 100 runs. D-TTTS is better than other algorithms at the beginning, but is outperformed by TPE towards the end. We see that, although not always the best, D-TTTS shows a consistent, robust, and quite competitive performance in the 3 tasks.

We now carry out the classic MNIST digits classification task using multi-layer perceptron (MLP). We choose to optimize over three hyper-parameters: the size of hidden layer (an integer between 5 and 50), the 2 penalty parameter α (between 0 and 0.9) and the initial learning rate (bounded in 10 -5 , 10 -1 ). Fig. 1d shows the result of MLP run on MNIST over 108 pulls, this time averaged over 20 runs. D-TTTS is slightly worse than Hyperband and H-TTTS in the very beginning, but is performing well afterward.

Discussion

We presented a way to use Thompson sampling for BAI for infinitely many-armed bandits and explained how to use it for HPO. We introduced the first fully dynamic algorithm for this setting and showed through an empirical study that it is a promising approach for HPO. In the future, we plan to provide experiments on more datasets and establish theoretical guarantees to support the good performance of D-TTTS, with the hope to provide a finitetime upper bound on its probability of error. We also plan to investigate variants of this algorithm for the non-stochastic bandits for which Hyperband can be used, which would allow spending more time on the more promising algorithms.

Remark 1 Hyperband was given specifically for hyper-parameter tuning. Its original philosophy is to adaptively allocate resources to more promising configurations. Resources can be time, the size of a random subset of the dataset, the number of randomly sampled features, etc. In this setting, the classifier is not always trained into completion given a parameter configuration, but is rather stopped early if it is empirically not performing well so that we can allocate more resources to other configurations. In such case, different evaluations of a single configuration are not i.i.d. anymore. Thus, HPO is stated as a nonstochastic infinitely-armed bandit problem. The idea of early stopping we further combined with Bayesian optimization [START_REF] Falkner | BOHB: Robust and efficient hyperparameter optimization at scale[END_REF].

Appendix B. Hyper-TTTS

Algorithm 2 Sampling rule of Hyper TTTS (H-TTTS) Input: β; γ; B; s max ; ν 0 Initialization: T ← B/s max 1: for s ← s max to 0 do 2:

K ← smax+1 s+1 γ s 3: A ← {i = 1, . . . , K : µ i ∼ ν 0 }; t ← 0 4: while t < T do 5: sample θ ∼ Π t 6:
I while

I (2) = I (1) do 12: ∀i ∈ A, θ i ∼ Beta(S i + 1, N i -S i + 1)
13:

I (2) ← arg max i∈A θ i 14:
end while 15:

I (1) ← I (2)
16:

Y ← evaluate arm I (1) 17:

end if 18:

X ∼ Ber(Y )

19:

S I (1) ← S I (1) + X; N I (1) ← N I (1) + 1 20: t ← t + 1 21:
end while 22: end for

We also show another way of extending TTTS to deal with an infinite number of arms and call it Hyper-TTTS or H-TTTS, a variant of Hyperband in which SHA is replaced by TTTS. H-TTTS, formally stated as Algorithm 2, runs s max batches of TTTS with different number of arms and each batch with a same budget T B/s max with B the total budget. The number of arms within each bracket is decreasing by a factor of γ. One inconvenience of H-TTTS is that s max and γ still need to be tuned. In our experiments, we use the same tuning as used by Hyperband [START_REF] Li | Hyperband: Bandit-based configuration evaluation for hyperparameter optimization[END_REF].

Appendix C. More numerical simulations

In this part, we give results comparing D-TTTS to Hyperband and to ISHA (infinite sequential halving, Aziz et al. 2018b), an adaption of sequential halving to the infinite bandit setting. In these experiments, the arms are Bernoulli distributed and the reservoir distribution ν 0 is fixed to some Beta(a, b) distribution.

ISHA consists in running SHA on a fixed number of arms drawn from the reservoir. Observe that for a total budget B, there exists a maximum number of arms K that can be processed by SHA, which satisfies B K log 2 (K ) . Following Aziz et al. (2018b), we run ISHA with K arms drawn from the reservoir.

In Fig. 2, we report the simple regret as a function of time for different algorithms for four Beta reservoir distributions. H-TTTS and D-TTTS are run with β = 1/2 which is known to be a robust choice [START_REF] Russo | Simple Bayesian algorithms for best arm identification[END_REF]. Each point represents the expected simple regret E[1 -µ I * n ] estimated with 1000 runs for an algorithm run with budget n. D-TTTS is very competitive on 3 reservoirs and H-TTTS is sometimes better, sometimes worse than Hyperband. We also tried the SiRI algorithm [START_REF] Carpentier | Simple regret for infinitely many armed bandits[END_REF] with b as the tail parameter where ν 0 = Beta(a, b), but obtained worse performance and therefore we do not report its results.

Note that in the implementation of Hyperband for this stochastic infinite bandit setting we modified the algorithm so that the elimination phase of the underlying SHA algorithm is carried out according to the average loss of previous samples, as samples from an arm are i.i.d. in this setting and not a converging sequence.

  1) ← arg max i∈A θ i

Figure 2 :

 2 Figure 2: Simple regret as a function of the number of arms evaluations

code at http://researchers.lille.inria.fr/ ˜valko/hp/publications/shang2019simple.code.zip

γ is the parameter of the RBF kernel defined as exp(-γ||x -x || 2 )

the number of pulls here and later is chosen exactly as in the work of[START_REF] Li | Hyperband: Bandit-based configuration evaluation for hyperparameter optimization[END_REF]

Acknowledgments

The research presented was supported by European CHIST-ERA project DELTA, French Ministry of Higher Education and Research, Nord-Pas-de-Calais Regional Council, Inria and Otto-von-Guericke-Universitt Magdeburg associated-team north-European project Allocate, and French National Research Agency projects BADASS (n.ANR-16-CE40-0002), and BoB (n.ANR-16-CE23-0003).

Appendix A. Best-arm identification for HPO Hyper-parameter optimization can be modeled as a BAI task in a bandit model. Given a finite set of arms A {1, . . . , K}, once we select arm i, we get an independent observation from some unknown distribution ν i with mean µ i . A BAI algorithm sequentially selects arms in order to identify the arm with the largest mean, I arg max i∈A µ i . 5 In the context of HPO, each arm models the quality of a given hyper-parameter configuration λ. When the arm is sampled, a noisy evaluation of f (λ) is received, where f (λ) is the mean reward of that arm. A BAI algorithm consists of a sequential arm selection strategy, indicating which arm I t is selected at round t, coupled with recommendation rule that selects a candidate best arm I t at round t. The goal is either to minimize the error probability P(µ I t = µ I ) [START_REF] Audibert | Best-arm identification in multi-armed bandits[END_REF][START_REF] Karnin | Almost optimal exploration in multiarmed bandits[END_REF] or the simple regret [START_REF] Bubeck | Pure in multi-armed bandits problems[END_REF][START_REF] Gabillon | Best-arm identification: A unified approach to fixed budget and fixed confidence[END_REF], defined as r t = µ I -µ I t , possibly after a total budget B, whose knowledge may be used by the algorithm. Note that the BAI problem can also be studied from a fixed-confidence point of view [START_REF] Even-Dar | Action elimination and stopping conditions for reinforcement learning[END_REF].

Standard BAI algorithms are however not straightforwardly applicable to HPO when the search space is infinite or continuous. To handle these important cases, we rather turn our attention to BAI in infinitely many-armed bandits [START_REF] Carpentier | Simple regret for infinitely many armed bandits[END_REF]. In this context, there is an infinite pool of arms, whose means are assumed to be drawn from some reservoir distribution ν 0 . In this setting, a BAI algorithm can maintain a list of arms (hyper-parameter configurations) that have been tried before. At each round, it can either query a new arm from the reservoir (add a new hyper-parameter, selected at random, to the current pool), add it to the list and sample it (evaluate it), or, sample an arm already in the list (re-evaluate a configuration tried before).

A natural way to perform BAI in an infinitely many-armed bandit model consists in first querying a well-chosen number of arms from the reservoir and then running a standard BAI algorithm on those arms [START_REF] Carpentier | Simple regret for infinitely many armed bandits[END_REF]. However, this ideal number may rely on the difficulty of the learning task, which is hardly known in practice. The Hyperband algorithm [START_REF] Li | Hyperband: Bandit-based configuration evaluation for hyperparameter optimization[END_REF] takes a step further and successively queries several batches of arms from the reservoir, including a decreasing number of arms in each batch, while increasing the budget dedicated to each of them. SequentialHalving (SHA, [START_REF] Karnin | Almost optimal exploration in multiarmed bandits[END_REF], a state-of-the-art BAI algorithm, is then run on each of these batches of arms. This approach seems more robust in that it trades off between the number of arms that is needed to capture a good arm and how much measurement effort we should allocate to each of them. However, a numerical study performed by Aziz et al. (2018b) seems to reveal that an infinite bandit algorithm based on SHA should always query the maximal number of arms from the reservoir. 6 All the existing algorithms are still subject to a pre-defined scheduling of how many arms should be queried from the reservoir. Contrary to them, our algorithm (D-TTTS) does not need to decide in advance how many arms will be queried, and is therefore fully dynamic.

5. In this paper, we present BAI problems in a standard way for which we search for an arm with the largest mean. However, for HPO, it is important to mention that we look for a hyper-parameter configuration that minimizes the validation error. One can easily see that it does not change the essence of the problem. 6. The reference we give is a preliminary draft that has been withdrawn due to technical issues in the proof.

Yet, we believe the experimental section to be sound.