Put CASH on Bandits: A Max K-Armed Problem for Automated Machine Learning
Authors: Amir Rezaei Balef
Claire Vernade
Katharina Eggensperger
Venue: NeurIPS 2025 poster ()
Keywords: Multi Armed Bandit
Automated Machine Learning
Hyperparameter Optimization
Primary area: general_machine_learning
TL;DR: A Max K-armed Bandit using assumptions derived from empirical data that handles short-tailed and skewed distributions to dynamically allocate resources to hyperparameter optimization runs.

Abstract: The Combined Algorithm Selection and Hyperparameter optimization (CASH) is a challenging resource allocation problem in the field of AutoML. We propose MaxUCB, a max  $k$-armed bandit method to trade off exploring different model classes and conducting hyperparameter optimization. MaxUCB is specifically designed for the light-tailed and bounded reward distributions arising in this setting and, thus, provides an efficient alternative compared to classic max $k$-armed bandit methods assuming heavy-tailed reward distributions. We theoretically and empirically evaluate our method on four standard AutoML benchmarks, demonstrating superior performance over prior approaches. We make our code and data available at https://github.com/amirbalef/CASH_with_Bandits

Put CASH on Bandits: A Max K-Armed Problem for Automated Machine Learning
Amir Rezaei Balef, Claire Vernade and Katharina Eggensperger
Department of Computer Science, University of Tübbnnee
(amir. rezaei-babef claire. vernade, katharina. oeggerinnnagggeegsggrrrr////u Quni tuneereingettttttenn.en.eee tuebingen.ccc. de
Abstract
The Combined Algorithm Selection and Hyperparameter optimization (CASH) is challenging resource allocation problem in the field of AutoMI.. We propose MaxUCB, a max k-armed bandit method to trade off exploring different model classes and conducting hyperparameter optimization. MaxUCB is specifically designed for the light-tailed and bounded reward distributions arising in this setting and, thus, provides an efficient alternative compared to classic max k-armed bandit methods assuming heavy-tailes reward distributions. We theoretically and empiri- cally evaluate method four standard AutoML benchmarks demonstrating superior performance over prior approaches. We make our code and data available at https: httppp:///gtttiit github. com/ aamammiibaa awwraallff////aaamaaaaaaaaaae CASS wi Bandits.
Introduction
The performance of machine learning (ML) solutions is highly sensitive the choice of algorithms and their hyperparameter configurations which can make finding an effective solution a challenging task. AutoML aims reduce this complexity and make ML more accessible by automating these critical choices [Hutter et al., 2019, Baratchi et al., 2024].
For example, Hyperparameter optimization (HPO) methods focus finding well- performing hyper- parameter settings given a resource constraint, such as an iteration count or a time limit. However, in practice, it is often unclear which ML model class would perform best given dataset [Bischl et al., 2025]. The problem of jointly searching the model class and the appropriate hyperparameters has been coined CASH, Combined Algorithm Selection and Hyperparameter optimization [TThrrton et al., 2013]. As a prime example, on tabular data, a ubiquitous data modality [van Breugel and van der Schaar, 2024], the state-of-the-an ML landscape covers classic ML methods, ensembles of gradient-boosted decision trees and modern deep learning approaches [Kadra et al., 2021, Gorishniy al., 2021, 2024, McElfresh al., 2023, Kohli et al., 2024, Hollmann et al., 2023, Holzmüller et al., 2024].
A popular approach address the CASH problem is to categorical and conditional hyperparame- ters to run HPO directly on the combined hierarchical search space of models and hyperparameters. AutoML systems
this approach, which we call combined search, search well-performing MIL pipelines [Thornton et al., 2013, Feurer et al., 2015, Komer et al., 2014, Kotthoff et al., 2017, Feurer al., 2022], but HPO remains inefficient in high-dimensional and hierarchical search spaces. A naive solution to address the scalability limitation is to run HPO independently for the smaller search spaces of each ML model class and then compare the found solutions. However, this solution often exceeds available computational resources and does not scale well with an increasing number of ML models. Figure (left) illustrates the difference between searching each space individually (colored dashed lines) and combined search (black line) on an exemplary dataset.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

3.79
Multi Armed Bandit (MaxUCB)
mossiaai Dsnci Frectoo
Corfooe
nul
Boart
2.00
Extral Fees
amm 2: model class
2mm model cass
Randon Farcst
CLAS D
0.30
231
0,500 0.A0 0.750
Acawnry
Figure 1: (Left) MaxUCB (blue line) outperforms combined search (black line) to identify the best- performing model class (brown line). (Middle) The irregular distribution of the empirical performance of model classes is left- skewed, and a higher mean may not correspond to a higher maximum. (Right) MaxUCB selects for which model to run one iteration of HPO during two-level optimization.
To leverage the efficiency of HPO in low dimensions, we use a Multi-Armed Bandit (MAB) method [Lattimore and Szepesvári, 2020] to dynamically allocate our budget. As shown in Figure (right), each time the bandit strategy pulls an arm, it runs one iteration of HPO to evaluate a new configuration, resulting loss. The negative of the loss is used as reward feedback for the bandit algorithm. This approach is known two-level CASH (decomposed CASH) [Hoffman et al., 2014, Liu et al., 2019].
While most classical MAB problems aim to maximize the average rewards over time, the goal of the bandit algorithm for two-level CASH should be to maximize the maximum reward observed over time: as illustrated in Figure I (middle), tuning the LightGBM (red) will eventually outperform CatBoost. This goal aligns with Max K -AAmeed Bandit (MKB) problems [Carpentier and Valko, 2014, Achab al., 2017, Baudry et al., 2022], often referred as Extreme Bandits.
In the context of AutoML, the time horizon is limited, making efficiency crucial. Prior work on nwo-level CASH found that state-of-the-art MKB algorithms not sufficiently sample-efficient in practice [Hu et al., 2021, Balef et al., 2024]. Additionally, Nishihara et al. [2016] argued that the parametric assumptions derived from extreme value theory are not applicable in the context of HPO and stated that determining "what realistic assumptions are likely to hold in practice for hyperparameter optimization an important question".
We precisely address this open question through a thorough statistical analysis of the empirical reward distributions of HPO tasks. Our main contribution is sfate-of-thean algorithm for decomposed CASH based on a novel extreme bandit algorithm we call MaxUCB (Algorithm 1). We demonstrate the performance of our method on four benchmarks, which highlights the relevance of our assumptions for a wide variety of CASH problems. We analyze the theoretical performance of Max UCB (Theorem 4.2) through regret bounds that also justify our novel choice of exploration bonus for the type of distributions relevant to the CASH problem. Importantly, our objective is rather to propose a practical algorithm with good empirical performance CASH rather than a general multi-purpose bandit algorithm, so our guarantees hold under carefully crafted assumptions that resolve previously open questions [Nishihara al., 2016].
2 Solving CASH using Bandits
The CASH problem for supervised learning tasks is defined as follows [Thornton et al., 2013]. Given dataset TD (Dtrain; Dealid) of a supervised learning task, let A (A(1),.., (x) be the set of K candidate ML algorithms, where each algorithm A has its own hyperparameter search space A The goal is search the joint algorithm and hyperparameter configuration space to find the optimal algorithm (t") and its optimal hyperparameter configuration X that minimizes a loss metric C, e.g., the validation error!. Formally,
;....
A E arg min
C(A DD).
'We note that L can also be the result of k-fold cross volidaaliootion or other evaluation protocols measuring the expected performance of model unseen data [Raschka, 2018].

---

For our approach, we study the decomposed variant [Hoffman et al., 2014, Liu et al., 2019] and address the following two-level optimization problem depicted in Figure (right); at the upper level, we aim to find the overall best-performing ML model A by selecting model A E A iteratively, and at the lower level, we aim to find the best-perforning configuration X A (1) for the selected model A Formally,
A E arg min [(A A': D), s.t. X arg min ((4 .D).
(2)
AWEA
XEA()
The right-hand side of Equation 2 in the lower level can be efficiently addressed by existing iterative HPO methods such as Bayesian optimization (BO) [Jones et al., 1998, Garnett, 2022], which has been demonstrated to perform well in practical settings [Snoek et al., 2012, Chen et al., 2018, Cowen- Rivers et al., 2022]. BO fits a surrogate model and uses an acquisition function to find promising configuration to evaluate next. On the upper level, or left-hand side of Equation 2, the challenge is to carefully allocate the budget T of HPO runs to the K models in manner that trades off exploration of the hyperparameter space of all models and exploitation (optimization) of the most promising model. As already noted previous work, this a typical MAB problem [Cicirello and Smith, 2005, Streeter and Smith, 2006a, Nishihara et al., 2016, Metelli et al., 2022].
At time f, the bandit algorithm chooses model E A, and we denote X the configuration proposed by the HPO method in the lower level. As a reward Ti,,, we feed back to the bandit algorithm an evaluation of the negative loss:
Ti. -(A D).
In general, and as opposed to standard MAB, this reward process is not i..d. conditionally on the arm choices because the loss of the models depend on the progress of HPO on each model class (arm) as well as additional loss evaluation noise. To be able to design tractable bandit algorithm, it is crucial to find an appropriate way to model this process build controllable estimators. We focus on this aspect in the next section.
To complete the bandit model of this problem, we need to choose a regret metric that defines the oracle objective we compare to, and indeed aligns with Equation 2. For HPO, the regret should target max- value objectives [Jamieson and Talwalkar, 2016, Nishihara et al., 2016]. Therefore, in this work, we propose to minimize the (extreme) regret R(T):
R(T) = max Efmmaxraa rw.e] E[max r1,, K
1ST
where the expectation is over the stochasticity of both the HPO procedure (e.g., random search or Bayesian optimization), the ML models themselves (e.g., random initialization and training variability), and the loss evaluation procedure at each round. The regret measures the gap between the expected performance of the bandit algorithm (right part) and that of the oracle model that would achieve the lowest loss, should we assign the full budget of HPO runs to it (left part). So this objective is indeed aligned with Equation 2 and fully integrates the budget constraints.
Instead of using MKB algorithms to directly address Equation 4, related prior works focus on alternative methods. For example, Hu et al. [2021] proposed and analyzed the Extreme-Regee Region Upper Confidence Bounds (ER-UCB) algorithm maximizing the extreme region of the feedback distribution, assuming Gaussian rewards. More recently, Balef et al. [2024] have shown that existing MKB algorithms underperform when applied to swo-level CASH, and they proposed methods for maximizing the quantile values instead of the maximum value.
As another alternative method, Li et al. [2020] framed the CASH problem as Best Arm Identification (BAD) task and introduced the Rising Bandits algorithm [Li et al., 2020]. This MAB method assumes that the reward function for each arm increases with each pull, following a rested bandit model with non-decreasing payoffs [Heidari et al., 2016] (which has been shown to have linear regret when the reward increment per pull exceeds a threshold [Metelli al., 2022]). Rising Bandits can be used for our setting using the maximum observed performance of the HPO history as the reward. However, this algorithm assumes deterministic rewards and increasing concave reward functions. To weaken this assumption, Li et al. [2020] introduced a hyperparameter to increase initial exploration. Mussi et al. [2024] further weakened this assumption by assuming that the moving average of the rewards an increasing concave function.
3

---

Generally, in BAI approaches, the goal is to identify the arm with the highest mean reward. Here, rewards are the result of HPO runs, so this objective does not align well with Equation 2: there is no reason to measure the quality of model on average over random subset of hyperparameters chosen by HPO. This approximation made by prior work is justified by the complexity of this modeling problem and the existence of solid foundations on BAI to build upon. But in this work, we propose fully data-driven model that fits better the true CASH objective and results in better empirical results.
3 Data Analysis of HPO Tasks
The reward process in Equation 3 is complex it depends the model and the chosen HPO algorithm. So, as discussed, it is necessary to model it. Rather than choosing a convenient parametric family, we conduct thorough analysis of typical sequences of losses obtained real benchmarks. For each ML model class (corresponding to arms in our setup), we run T = 200 iterations of HPO, with 32 repetitions (each using different seed) varying number of datasets on four AutoML benchmarks (see Appendix D.2 and C.I).
We first analyze the survival function of the reward distributions. Recall that for random variable X d, the survival function is defined by: x + G(z) = PX~a(X 2 z). Figure 2 shows the average empirical survival function of all observed performances (normalized between 0 and for each task) for each arm. We rank model classes (i.e., arms) based on their best performance per dataset and report results two benchmarks (see Appendix C for more details and results all benchmarks). We observe that the reward distributions are
1. bounded. The reward, which measures the performance of model, is determined by score metric, e.g., accuracy. The extreme values vary for each arm and depend on the capability of the model class and the complexity of the task. Therefore, even if we run HPO indefinitely, achieving an infinite reward is impossible. Consequently, each arm has a bounded support with different maximum values, and least a single optimal arm exists. + We can define a sub-optimality gap (Definition 3.1).
2. short-tailed, left-skewed, and the right tail is not heavy. The rewards are concentrated near the maximal value per model class, and extreme events are not outliers. As the HPO method's performance reaches a certain level, further optimization often yields only small gains optima tend have flat regions [Pushak and Hoos, 2022]. Therefore, many configurations perform similarly well, resulting in skewed distribution." 2 + We expect to observe many extreme rewards.
3. nearly stationary. This means that the optimal arm does not change over time. This is clear for TabRep We observe significant changes in the distributions for YaHPOGym, but most of the sub-optimal arms remain sub-optimal over time. Ranking of well- performing arms does not change over time.
YaHPOGym
Rab
YaHPOGym
TabRepoRaw
0.5
0.25
0.30
0.75
1.00
0.4
0.6
0.5
0101
01.5
033
0.50
1.00
0700
11:55
11.00
0.75
120
Optinal ar
2nd amm
3rd 4th
5ch am
6th (orly TabRepoRax)
Wons ann
Figure 2: (Left) The average empirical survival function of the reward distribution per arm ranked per dataset. Thin lines correspond to segments of the reward sequence and show the distribution change over time. (Right) The average empirical survival function per dataset for the best and worst arm. Thin lines correspond to individual datasets.
Prior research has shown that existing MKB algorithms can underperform if their assumptions about the distributions are too weak or misaligned INishihara et al., 2016, Balef et al., 2024]. This
TThis has also been observed for related tasks, e.g., neural architecture search CIFAR-10 [Su et al., 2021].

---

underperformance is largely due to our second observation, which significantly differs from the common assumptions of the existing algorithms.
Preliminaries. Based on these observations, we can formulate the following definition and assump- tion which we develop and analyze our algorithm.
Definition 3.1. The suboptimality gap A
2
0 for arm is defined as:
A
E
max IST
IE
max *T
Ti,
where "r and ra are the rewards observed from optimal arm i' and arm at time t, respectively. Assumption 3.2. We assume that the i.i.d. random variable X, representing the rewards, follows bounded distribution with support in (a, bj and continuous survival function G.
Lemma 3.3. Suppose Assumption 3.2 holds. Then, there exists L,U 2 0 such that the survival function G can be bounded near b by linear functions:
VE E (0,b-a), S G ((b--) E) S U..
(5)
Lemma 3.3 (proof in Appendix B.1) provides a way to characterize the shape of any bounded distri- bution near its maximum value through distribution-dependenn constants, and U (see Appendix C.2 for more details and a visualization). Intuitively, it quantifies the behavior of the distribution of the ML model performance in given hyperparameter space near the optimum. A large value of L indicates a steep drop in the survival function near the maximum, while a small value of U leads to more gradual decay of the survival function and conversely (see Figure 3).
YaHPOGym
TabRepoRaw
YaHPOGym
TabRepoRaw
1.0
50-
Wont am
Went am
Plowurd 2
0.5
30
20-
Maee
Opteal
Opeind
Wert
10
0.01
Values for
Values for
Valuss for
Values for
Figure 3: (Left, Middle) L and U for the average survival functions Figure 2. (Right) We high- light the difference to right-skewed Log-normal and Pareto distributions.
Figure 4: Histogram of L and U values across individual datasets.
We study the values of and U Lemma 3.3 on our empirical data and show the distribution of and U in Figure 4 (see Appendix C.3 for more analyses). Next, focus on the uniqueness of our assumptions before discussing how this impacts our MKB algorithm's 's performance in Section 4.
Common Max K Karred Bandit assumptions are misaligned with CASH. Existing MKB algo- rithms can be classified into two main categories. First, distribution-fre approaches do not leverage any assumption on the type of reward distributions [Streeter and Smith, 2006b, Bhatt et al., 2022, Baudry et al., 2022]. Secondly, parametric and cemi-paramttric approaches typically assume that the reward distributions follow teive- distributions, typically following a second-order Pareto assumption whose parameters can be estimated using extreme value theory [Carpentier and Valko, 2014, Achab et al., 2017].
Our empirical analysis shows that existing MKB algorithms' assumptions about reward distributions are either overly broad or misaligned with the CASH problem. We identify two key differences between our assumptions and those made by current MKB algorithms. First, the sub-optimality gap makes the regret definition (Equation 4) for bounded distributions meaningful. Without the existence of a nonzero gap. the regret definition fails since any policy consistently selecting a single arm can achieve zero regret, as Nishihara et al. [2016] pointed out with Bernoulli distributions. Second, our reward distributions differ from those used in existing MKB algorithms. Lemma 3.3 characterizes shape of the distribution, with higher I. ensuring more mass near extreme values, making extreme values easier to estimate, our case, values for I, are mostly higher than while for heavy-tailed distributions, commonly used as the basis for MKB algorithms, are close to 0 (see the rightmost plot
5

---

in Figure 3). In general. our analysis shows that considering the right range of L values unlocks the problem raised by Nishihara al. [2016], who focused on constructing counterexamples through the distributions that have unrealistic values for L. Thus, under our assumptions, their negative result does not apply here.
4 MaxUCB
Based on Lemma 3.3 and the regret definition (Equation 4), we introduce MaxUCB in Algorithm 1 for arms with a limited time horizon of T iterations.*
Description of MaxUCB. Our algorithm balances exploration and exploitation according to the standard optimism principle at the heart of Upper Confidence Bound (UCB) bandit methods [Auer, 2002, Lattimore and Szepesvári, 2020]. The main novelty we introduce is in the computation of distribution-adaptee exploration bonus for MaxUCB.
Our exploration bonus ( log((t) )a deviates from typical UCB literature due to faster concentration of maximum values in bounded distributions. This is because the probability of bad events (violating confidence intervals for the expectation the max, see Equation 30 in Appendix B.3) can be written as:
P(Bad events) S O (e-nvii nn(n)).
where distribution-dependee constants are hidden for clarity. Then, setting C(n) = 1/n² minimizes the probability of bad events: the first term becomes independent of n. while the second term decreases with n. Notably, this faster concentration can only be obtained for the reasonably well- behaved distributions we consider following the study of the previous section and is not general property of the maxima; more details can be found in Appendix B.4. Furthermore, MaxUCB uses control the
trade-off; higher a leads more exploration.
Algorithm MaxUCB
Require:
cn(esploration parameter) Tiime horizon), K (arms)
1: for euch arm S K do
2: Pull
nq observe reward #1.1
Exaluating default configuration
3: end for
4: for + Ta do
5:
for each
do U, = max (fi,1 (inn;) + bogg()) )
6: Update policy
differs from classical UCB, where U; P: +
lox!t]
7: end for
8:
Select arm d arg max Us.
121, +- n.f, + 1, then observe reward (
ESK
9: end for
Analysis of MaxUCB. We first show regret decomposition result specific to max K K-armed bandits that directly relates the regret definition in equation 4 with the number of suboptimal trials.
Proposition 4.1. (Regret Upper Bound) the regret upper bound up to time T is related to the number of times sub-optimal arms are pulled:
by
R(T)
ISK
N:(T)
i
where N,(T) = = 1[1=
is the number of sub-optimal pulls of arm i, and by is the upper bound on the support of the rewards of arm i.
'Theorem 11 in [Nishihara et al., 2016]: "no policy can be guaranteed to perform asymptotically as well as oracle that plays the single best arm for given time horizon.", which means any policy needs explore all arms budget
'MaxUCB needs to store the number of pulls and the maximum reward for each arm, resulting in memory requirement of O(K). The time complexity is O(KT).

---

The proof is provided in Appendix B.2 and relies on standard tools in the extreme bandit literature [Baudry et al., 2022]. From this result, it clear that we can now obtain an upper bound on the regret by controlling the number of suboptimal arm pulls (N; (T))) individually. Our main theoretical result below proves such an upper bound for Algorithm 1.
Theorem 4.2, For any suboptimal arm + it, the number of suboptimal draws N:(T) performed by MaxUCB (Algorithm 1) up to time T is bounded by
T1-2L av
(T(T)= < 1 1 + 2a / loT))
(8)
The result of Theorem 4.2 (proof in Appendix B.3) highlights that MaxUCB primarily leverages two key properties: the sub-optimality gap A; and the shape of the distribution, as defined Lemma 3.3. Specifically, the performance improves with larger sub-optimality gap A; and higher values of Lę- (L for the optimal arm), which means that samples drawn from the distribution of the optimal arm are likely to be close to the extreme values. Additionally, smaller values of U, (U for sub-optimal arm i), which means it is less likely to draw samples close to the extreme values, reduce the number selecting sub-optimal arm i, thus enhancing overall performance. For our task, is shown in Figure 3, the values for Li- are higher than 1 and U; less than 10 in most cases, yielding high empirical performance. We compare the number of pulls observed in our experiments with the expected values based on our theoretical analysis in Appendix E.2, showing that our analysis is not loose. However, it essential to note that, in general, finding the optimal arm challenging A is close to zero or Ly- is very small. We assess the performance of MaxUCB on synthetic tasks in Appendix E.4, showing that the performance of MaxUCH deteriorates on tasks that do not satisfy our assumptions.
Finally, we provide a regret upper bound that combines the decomposition in Proposition 4.1 with the individual upper bounds above. This requires finding a parameter a that resolves trade-off between the arms and minimizes the total upper bound, as shown in Corollary 4.3, whose proof is immediate.
Corollary 4.3. If Li+, min(A) A4), and T known in advance, then the total regret RT) ifi
can be
bounded as follows by choosing the exploration parameter a appropriately:
K Klog T VT
2 log(log(T))
R(T) S
max b1), ISK
when =
1
(9)
4Le
min A. 6f11"
log(T))
This final result helps to understand the role of a and serves as guidelines to choose it in practice. Specifically, Equation 9 shows that either small value of L.- or small sub-optimality gap requires higher value for a. Intuitively, small L; means that the max value of the best arm needs more samples be nearly reached, and small suboptimality gap means that the two best arms are close and so hard to distinguish. Indeed, these problem-dependen quantities are unknown to the practitioner, so direct approach to calculate a is not feasible. Therefore, evaluating performance robustness under "loose tuning" of a is essential
5 Performance on AutoML tasks
Finally, we examine the empirical performance of MaxUCB in an AutoML setting via reporting average ranking and the number of wins, ties, and losses across tasks for each benchmark (details in Appendix D. We first focus on the impact of the hyperparameter a and then compare our approach to others. Specifically, we show that our two-level approach performs better than single-level HPO on the joint space, and MaxUCB outperforms other oftt-oofthhe-at bandit methods. To begin, we will provide brief overview of the experimental setup used across all experiments.
Experimental setup. We use four AutoML benchmarks all implementing CASH for tabular supervised learning differing in the considered ML models, HPO method, and datasets, which we
'ee used the AutoML Toolkit (AMLTK) [Bergman et al., 2024]. We ran HPO on a compute cluster equipped with Intel Xeon Gold 6 240 CPUs. requiring 20 000 CPU hours. We conducted the remaining experiments on a local machine with Intel Core 17-1370P, requiring an additional 32 CPU hours.
7

---

detail in Table D.I. For TabRepo and Reshuffling, we use available pre-computed HPO trajectories, whereas for Tab and YaHPOGym. we use SMAC [Hutter et al., 201 I, Lindauer al., 2022] as Bayesian optimization method to run HPO ourselves.
How sensitive is MaxUCB to the choice of o?? Figure 5, shows that the choice of impacts performance. Lower values of a (light red lines) lead good performance with small budgets, whereas higher values (dark red lines) achieve stronger final performance when sufficient time is available. An a around 0.5 yields balanced trade- off, offering robust anytime performance across tasks (see Appendix D.4 , for detailed results). Another insight from this study is that the right choice of a may depend on characteristics of the datasets, such as the support of the losses, and could be meta-learned.
YaHPOGym
TabRepoRaw
Ranking
200
200
Iteration
Iteration
Competitive Baselines. We compare against Quan- tile Bayes UCB [Balef al., 2024], ER-UCB-S [Hu et al., 2021] and Rising Bandits [Li et al., 2020] which have been developed for the decomposed CASH task. We consider extreme bandits (QoMax-SDo, SDA [Baudry et al., 2022], Max- Median [Bhatt et al., 2022]) and classic UCB as general bandit methods. We use default hyperparameter settings for all methods. As combined search baselines, we consider Bayesian optimization (SMAC) and random search." 6 Additionally, we report the performance of the best (oracle) arm.
0.0
0.0
3.1
0.2
0.
06
07
Figure 5: The sensitivity of MaxUCB hyperparameter a, lower is better.
How does the two-level approach compare against combined search? We first compare the average rank over time in Figure 6 using combined search (black lines; random search and SMAC if available) to the two-level approach. We observe that all methods outperform random search (dotted line) and that while SMAC quickly catches up, some bandit methods continuously achieve a better (lower) rank. Additionally, we observe that most MAB algorithms (except Rising Bandits and QoMax-SDA) lead to superior performance in the early stages (T = 50). This demonstrates that the decomposition particularly useful when the number of iterations is limited. Additionally, Table shows that the difference in final performance between combined search and the two-level approach is significant.
How does MaxUCB compare against other bandit methods? Figure 6 shows substantial difference in the ranking. In the beginning, many methods perform competitively, but MaxUCB yields the best anytime and final performance. Classical UCB (red) and extreme bandits (QoMax-SDA; brown) perform worst. The Max-Median algorithm (purple) shows strong initial performance, but its effectiveness declines with more iterations. While Max-Median identifies and avoids the worst arm; it sometimes struggles to select the optimal arm, resulting in non-robust performance.
Next, we look at methods that were originally designed for AutoML. Both ER- RR-UCB-S (pink) and Quantile Bayes UCB (orange) focus on estimating the higher region of the reward distribution rather than the extreme values. ER-UCB-S assumes a Gaussian reward distribution and is consistently outperformed by Quantile Bayes UCB, a distribution-fii algorithm. Rising Bandits (green) un- derperforms initially due to its costly initialization but reaches competitive final performance. This is especially pronounced for the YaHPOGym benchmark, where Rising Bandits outperforms MaxUCB with respect to normalized average performance (see Figure D.5 in Appendix D.5). This benchmark contains datasets where the optimal arm changes over time. Since Rising Bandits models non-stationary rewards, performs better for these instances."
Finally, MaxUCB and Quantile Bayes UCB are the only ones that significantly outperform combined search in Table 1. And looking at TabRepo and Reshuffling, as depicted in Figure 6, demonstrates that MaxUCB a robust method for CASH problems.
'Only available for Tab and YaHPOGym, where we computed HPO trajectories ourselves. A burn-in phase, i.e., pulling each arm for a few rounds at the beginning without observing the rewards, yields competitive solution assess in Appendix E.3.
8

---

[a
TahRepoRRw|SMMAC
\SHIPOGym|SMAC]
Reshufing((IEBO)
10
MaxUCU
6
Quanls Bees UCB
Ranking
Riing Ravch
GoMas SDA
Median
UCE
SMAC
2-
2-
Rastom Search
Chadi Ari
0
200
0
200
0
200
0
200
Iteration
Iteration
Iteration
Iteration
Figure 6: Average rank of algorithms on different benchmarks, lower is better. SMAC and ran- dom search perform combined search across the joint space.
Quantile Bayes UCB
Benchmark
MaxUCB
ER-UCB
Rising
QoMax
Median
TabRepo
p-value will
0.00000
0.00000
0.00000
0.00000
0.00000
0.00006
0.00000
[RS]
186/1/10
179/6/15
135/5/60
185/1/11
172/5/23
126/3/71
135/5/60
TabRepoRaw [SMAC]
p-value
0. 000072
0.00261
0.95063
0.42777
0.99194
0.99984
0.99194
21/66
23/077
11/V19
16/V14
9/0/11
YaHPOGym
p-value
O. 0,00880
D. 0.00503
0.31038
0.00074
0.08372
0.50000
O. 0.02412
[SMAC]
wivl
64/0/99
65/0/38
54/1/48
68/0335
59/044
52/0/51
62/041
Table I: P-values from a sign test assessing whether bandit methods outperform combined search.
P-values below = 0.05 are underlined, while those below a 0.05 after multiple comparison correction (adjusting by #comparisons) are boldfaced, indicating that the two-level approach is superior to combined search. Additionally, we report the number of wins, ties, and losses (w/t/l.
Conclusions, Discussions and Future Work
This paper addresses the CASH problem, proposing MaxUCB, an MKB method. Our data-driven analysis answers open question the applicability of extreme bandits CASH. We provide novel theoretical analysis and show state-of-the-an performance on several important benchmarks.
Limitations. Though our method can be applied beyond AutoML in principle, it is finely tuned for this setting with bounded and skewed distributions and for maximal value optimization. Our analysis relies on stationary distributions, which might not always be accurate, especially at the beginning of the HPO run, so a short burn-in phase may be needed to reach this regime. Our approach may not be distributionally optimal, optimality in bounded extreme bandits remains open question, and establishing lower bounds is left for future work. Lastly, we provide default value for our hyperparameter that might need adjusting for other applications.
Impact on AutoML systems. Our approach complements prior work on AutoML systems and increases their flexibility. First, our approach allows to choose any HPO method for each model at the lower level and thus it may integrate recent progress in HPO methods for some ML model classes, e.g., multi-fidelity
meta-learned methods [György and Kocsis, 2, Li et al., 2018, Falkner et al., 2018, Müller et al., 2023, Chen al., 2022]. Second, some AutoMI. systems [Swearingen et al., 2017, Li et al., 2023] decompose the search space into smaller subspaces to scale and use Bandit methods to select promising subspaces [Levine et al., 2017, Li et al., 2020]. While focus applying bandits to select promising ML models, our methods could also be applied in this setting. Finally, beyond CASH, MaxUCB well-suited for sub-supernet selection in Neural Architecture Search (NAS) [Hu al., 2022], showing similar reward distributions [Ly-Manson et al., 2024] (see Appendix E.5).
distributed setting
Choosing a adaptively. Figure suggests that one could try to tune online. However, it is known that, in theory, without additional information, data-adaptive parameters cannot be found at reasonable exploration cost in bandit optimization settings [Locatelli and Carpentier, 201 8). In AutoMI. systems, though, supplementary data, like estimates of the sub-optimality gap, reward distribution shape, and HPO convergence rate, can help adjust adaptively.

---

Future Directions. To extend our extreme bandit setting, one could further refine the reward modeling by incorporating the non-stationarity. especially in AutoML for data streams, where optimal models shift with data distributions [Verma et al., 2024]. Incorporating cost-aware optimization is another promising direction, as computational resources and time, rather than iteration counts, often define budgets in AutoML:; this would require estimating model training times and factoring them into the decision process. Addressing the growing complexity of heterogeneous ML tasks, such as those involving pre-training, fine-tuning, prompt engineering, may benefit from hierarchical approach that allocates resources effectively across diverse [Balef and Eggensperger, b0.5a,b]. Additionally, exploiting structural similarities among algorithms and their hyperparameters could reduce exploration costs by sharing information across arms in the CASH problem, further enhancing efficiency.
Acknowledgments and Disclosure of Funding
The authors are funded by the Deutsche Forschungsgemminnschatt (DFG, German Research Foun- dation) under Germany's Excellence Strategy EXC number 2064/1 Project number 390727645. Additionally, C. Vernade acknowledges funding from the DFG under the project 46880671 14 of the Emmy Noether Programme. The authors also thank the International Max Planck Research School for Intelligent Systems (IMPRS-IS).
References
Hutter, Kotthoff, and Vansehoren, editors. Automated Machine Learning: Methods, Systems, Challenges. Springer, 2019, Available for free http:/// /nt::///uuutoo //ttmmmomm.....//mm www/booggoo.ooooooooooooooooooo
M. Baratchi, C. Wang. S. Limmer, J. van Rijn, H. Hoos, B. Thomas, and M. Olhofer. Automated machine learning: past, present and future. Artificial Intelligence Review, 57, 2024.
Bernd Bischl, Giuseppe Casalicchio, Taniya Das, Matthias Feurer, Sebastian Fischer, Pieter Gijsbers, Subhaditya Mukherjee, Andreas C. Müller, László Németh, Luis Oala, Lennart Purucker, Sahithya Ravi, Jan N. van Rijn, Prabhant Singh, Joaquin Vanschoren, Jos van der Velde, and Marcel Wever. Openml: Insights from 10 years and more than thousand papers. Patterns, 6(7):101317, 2025. ISSN 1666.3899. doi: https://doi.orr www.ooooorr/////// 10../.0..001 1016/j 1016///.atterr222555 202.eer.225.10111...
C. Thornton, F. Hutter, H. Hoos, and K. Leyton- Brown, Auto Auto-WEKA: combined selection and Hyperparameter Optimization of classification algorithms. I. Dhillon, Koren, R. Ghani, T. Senator, P. Bradley, R. Parekh, J. He, R. Grossman, and R. Uthurusamy, editors, The 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'13) pages 847-855. ACM Press, 2013.
Boris van Breugel and Mihacla van der Schaar. Why tabular foundation models should be research priority. In R. Salakhutdinov, Z. Kolter, K. Heller, A. Weller, N. Oliver, J. Scarlett, and F. Berkenkamp, editors, Proceedings of the 41st International Conference on Machine Learning (ICML 24), volume 235 of Proceedings of Machine Learning Research. PMLR, 2024.
A. Kadra, M. Lindauer, F. Hutter, and Grabocka. Well-tuned simple nets excel on tabular datasets. In M. Ranzato, A. Beygelzimer, K. Nguyen, Liing. J. Vaughan, and Y. Dauphin, editors, Proceedings of the 35th International Conference on Advances in Neural Information Processing Systems (NeurIPS-2I), Curran Associates, 2021.
Y. Gorishniy, I. Rubachev, V. Khrulkov, and A. Babenko. Revisiting deep learning models for tabular data. In M. Ranzato, A. Beygelzimer, K. Nguyen, P. Liang, J. Vaughan, and Y. Dauphin, editors, Proceedings of the 35th International Conference on Advances Neural Information Processing Systems 211), Curran Associates, 2021.
Y. Gorishniy, I. Rubachev, N. Kartashev, D. Shlenskii, A. Kotelnikov, and A. Babenko. TabR: Tabular deep learning meets nearest neighbors. In International Conference on Learning Representations (ICLR'24) 2024. Published online: iclr.cc.
10

---

D. McElfresh, S. Khandagale, J. Valverde, V. Prasad, B. Feuer, C. Hegde, G. Ramakrishnan, M. Gold- blum, and White. When do neural nets outperform boosted trees on tabular data? In E. Denton, J. Ha, and J. Vanschoren, editors, Proceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks, 2023.
Ravin Kohli, Matthias Feurer, Katharina Eggensperger, Bernd Bischl, and Frank Hutter. Towards quantifying the effect of datasets for benchmarking: look at tabular machine learning. Data- centric Machine Learning Research (DMLR) Workshop at ICLR, 2024.
N. Hollmann, Müller, K. Eggensperger, and F. Hutter. TabPFN: A transformer that solves small tabular classification problems in second. In International Conference on Learning Representations (ICLR'23), 2023. Published online: iclr
D. Holzmüller, L. Grinsztajn, and I. Steinwart. Better by default: Strong pre-tuned mips and boosted trees on tabular data. A. Globerson, L. Mackey, D. Belgrave, Fan, U. Paquet, J. Tomezak, and C. Zhang, editors, Proceedings of the 37th International Conference on Advances in Neural Information Processing Systems (NeurIPS (24),, 2024.
M. Feurer, A. Klein, K. Eggensperger, J. Springenberg, M. Blum, and F. Hutter. Efficient and robust automated machine learning. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, Proceedings of the 29th International Conference on Advances in Neural Information Processing Systems (NeurIPS 15), pages 2962-2970. Curran Associates, 2015.
B. Komer, J. Bergstra, and C. Eliasmith. Hyperopt-skleam: Automatic hyperparameter configuration for scikit-learn. In Hutter, R. Caruana, R. Bardenet, M. Bilenko, I. Guyon, B. Kégl, and H. Larochelle, editors, ICML workshop on Automated Machine Learning (AutoML workshop 2014.
Lars Kotthoff, Chris Thornton, Holger H Hoos, Frank Hutter, and Kevin Leyton-Brown. Auto-WEK, 2.0: Automatic model selection and hyperparameter optimization WEKA. Journal of Machine Learning Research, 18(25):1-5, 2017.
M. Feurer, K. Eggensperger, Falkner, M. Lindauer, and Hutter. Auto-Skleam 2.0: Hands-free automl via meta-leaming. Journal of Machine Learning Research, 23(261):1-61, 2022.
Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.
Matthew Hoffman, Bobak Shahriari, and Nando Freitas. On correlation and budget constraints in basel-based bandit optimization with application to automatic machine learning. In Artificial Intelligence and Statistics, pages 365-374. PMLR, 2014.
Sijia Liu, Parikshit Ram, Deepak Vijaykeerthy, Djallel Bouneffouf, Gregory Bramble, Horst Samu- lowitz, Dakuo Wang, Andrew R. Conn, and Alexander G. Gray. An ADMM based framework for AutoML. pipeline configuration. In AAAI Conference on Artificial Intelligence, 2019.
Alexandra Carpentier and Michal Valko. Extreme bandits. In Z. Ghahramani, M. Welling, Cortes, N. Lawrence, and K. Weinberger, editors, Proceedings of the 28th International Conference on Advances in Neural Information Processing Systems 14),,, Curran Associates, 2014.
M. Achab, Clémençon, A. Garivier, A. Aurélien, A. Sabourin, and C. Vernade. Max K-Armed Bundit: On the ExtremeHuunter Algorithm and Beyond, page 384-404. Springer International Publishing. 2017.
D. Baudry, Y. Russac, and F. Kaufmann. Efficient algorithms for extreme bandits. In International Conference on Artificial Intelligence and Statistics, 2022.
Y. Hu, X. Liu, and S. Liand Y. Yu. Cascaded algorithm selection with extreme-region UCB bandit. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(10):6782-679, 2021.
Amir Rezaei Balef, Claire Vernade, and Katharina Eggensperger. Towards bandit-based optimization for automated machine learning- 5th Workshop on practical Ml. limited/low resource settings, 2024. URL //tpp//eeeie/eeee///ee net//orrmm
11

---

Robert Nishihara, David Lopez-Paz, and Léon Bottou. No regret bound for extreme bandits. In Artifiical Intelligence and Statistics, pages 259-267, PMLR, 2016.
Raschka. Model evaluation, model selection, and algorithm selection in machine learning. ArXiv, abs/1811. 12800, 2018.
D. Jones, M. Schonlau, and W. Welch. Efficient global optimization of expensive black box functions. Journal of Global Optimization, 13:455-492, 1998.
R. Garnett, Bayesian Optimization. Cambridge University Press, 2022. Available for free at https:/ http///bbbbsppbboo..oooooo com/.
Snoek, H. Larochelle, and R. Adams. Practical Bayesian optimization of machine learning algorithms. In P. Bartlett, F. Pereira, C. Burges, L. Bottou, and K. Weinberger, editors, Proceedings of the 26th International Conference on Advances in Neural Information Processing Systems (NeurIPS'12) pages 2960-2968. Curran Associates, 2012.
Y. Chen, A. Huang, Z. Wang, I. Antonoglou, J. Schrittwieser, D. Silver, and N. de Freitas. Bayesian optimization in alphago. arXiv:1812.06835 [cs.LG], 2018.
A. Cowen-Rivers, W. Lyu, R. Tutunov, Z. Wang. A. Grosnit, Griffiths, A. Maraval, H. Jianye,
J. Wang, J. Peters, and H. Ammar. HEBO: Pushing the limits of sample-efficient optimisation. Journal of Artificial Intelligence Reseurch, 74: 169-11999, 2022.
V. Cicirello and S. Smith. The max K-armed bandit: new model of exploration applied to search heuristic selection. In M. Veloso and S. Kambhampati, editors, Proceedings of the 20th National Conference on Artificial Intelligence (AAAI'05), page 1355-1361, AAAI Press, 2005.
M. Streeter and S. Smith. An asymptotically optimal algorithm for the Max k-Armed Bandit problem. In AAAI Conference on Artificial Intelligence, 2006a.
Alberto Maria Metelli, Francesco Trovo, Matteo Pirola, and Marcello Restelli. Stochastic rising bandits. In K. Chaudhuri, S. Jegelka, L. Song, C. Szepesvári, G. Niu, and S. Sabato, editors, Proceedings of the 39th International Conference Machine Learning (ICMI. volume 162 of Proceedings of Machine Learning Research. PMLR, 2022.
Kevin Jamieson and Ameet Talwalkar. Non-stochastic best arm identification and hyperparameter optimization. In Artificial intelligence and statistics, pages 440-248. PMLR, 2016.
Y. Li, Jiang. J. Gao, Y. Shao, C. Zhang, and B. Cui. Efficient automatic CASH via rising bandits. In F. Rossi, V. Conitzer, and F. Sha, editors, Proceedings of the Thirty-Fourth Conference on Artificial Intelligence (A)A pages 4763-4771. Association for the Advancement of Artificial Intelligence, AAAI Press, 2020.
H. Heidari, M. Kearns, and A. Roth. Tight policy regret bounds for improving and decaying bandits. In Kambhampati, editor, Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI' (6), pages 1572-1570, 2016.
Marco Mussi, Alessandro Montenegro, Francesco Trovó, Marcello Restelli, and Alberto Maria Metelli. Best arm identification for stochastic rising bandits. In R. Salakhutdinov, Z. Kolter, K. Heller, A. Weller, N. Oliver, J. Scarlett, and F. Berkenkamp, editors, Proceedings of the st International Conference on Machine Learning (ICML 244), volume 235 of Proceedings of Machine Learning Research. PMLR, 2024.
Y. Pushak and H. Hoos. Automl loss landscapes. ACM Transactions on Evolutionary Learning and Optimization, 2(3):1-30, 2022.
Xiu Su, Tao Huang, Yanxi Li, Shan You, Fei Wang, Chen Qian, Changshui Zhang, and Chang Xu. Prioritized architecture sampling with monto-carlo tree search. 2021 IEEE/CVE Conference on Computer Vision and Pattern Recognition (CVPR), pages 10963-10972, 2021.
Matthew J. Streeter and Stephen F. Smith. A simple distribution-free approach to the Max k- Armed Bandit problem. In International Conference on Principles and Practice of Constraint Programming, 2006b.
12

---

S. Bhatt, P. Li, and G. Samorodnitsky. Extreme bandits using robust statistics. IEEE Transactions on Information Theory, 69()):161-1776, 2022.
Peter Auer. Using confidence bounds for exploitaiion-exploraiio trade-offs. Journal of Machine Learning Research, 3(Nov):397-422, 2002.
Edward Bergman, Matthias Feurer, Aron Bahram, Amir Rezaci Balef, Lennart Purucker, Sarah Segel, Marius Lindauer, Frank Hutter, and Katharina Eggensperger. AMLTK: A Modular Automl Toolkit in Python. Journal of Open Source Software, 9(100):337,, 2024, doi: 10.21 105/0osss.00036 URL https://don org/ 10. 21105/joss joss.06367.
Hutter, H. Hoos, and K. Leyton-Brown. Sequential model-based optimization for general algorithm configuration. In C. Coello, editor, Proceedings of the Fifth International Conference on Learning and Intelligent Optimization (LION' (1), volume 6683 Lecture Notes in Computer Science, pages 507-523. Springer. 2011.
M. Lindauer, K. Eggensperger, M. Feurer, A. Biedenkapp. D. Deng, C. Benjamins, T. Ruhkopf, R. Sass, and Hutter. SMAC3: A versatile bayesian optimization package for Hyperparameter Optimization. Journal of Machine Learning Research, 23(54):1-9, 2022.
András György and Levente Koesis. Efficient multi-start strategies for local search algorithms. Journal of Artificial Intelligence Research, 41:407-444, 2011.
Lisha Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadeh, and Ameet Talwalkar. Hyperband: A novel bandit- approach to hyperparameter optimization. Journal of Machine Learning Research, 18(185):1-52, 2018.
S. Falkner, A. Klein, and F. Hutter. BOHB: Robust and efficient Hyperparameter Optimization at scale. In J. Dy and A. Krause, editors, Proceedings of the 35th International Conference on Machine Learning (ICML'I8) 18), volume 80, pages 1437-1446. Proceedings of Machine Learning Research, 2018
Samuel G. Müller, Matthias Feurer, Noah Hollmann, and Frank Hutter. PFNs4BO: In-context learning for bayesian optimization. In A. Krause, E. Brunskill, K. Cho, B. Engelhardt, S. Sabato, and J. Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning (ICML'23) volume 202 of Proceedings of Machine Learning Research. PMLR, 2023.
Yutian Chen, Xingyou Song. Chansoo Lee, Zi Wang, Richard Zhang, David Dohan, Kazuya Kawakami, Greg Kochanski, Arnaud Doucet, Marc' aurclio Ranzato, et al. Towards learning universal hyperparameter optimizers with transformers. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Proceedings of the 36th International Conference on Advances in Neural Information Processing Systems (NeurIPS pages -30668.. Curran Associates, 2022.
Thomas Swearingen, Will Drevo, Bennett Cyphers, Alfredo Cuesta-Infante, Arun Ross, and Kalyan Veeramachaneni. ATM: A distributed, collaborative, scalable system for automated machine learning. In 2017 IEEE international conference on big data (big data), pages 151-162. IEEE, 2017.
Yang Li, Yu Shen, Wentao Zhang, Ce Zhang, and Bin Cui. VolcanoML: speeding up end-to-end AutoML via scalable search space decomposition. The VLDB Journal, 32(2):389-413, 2023.
Nir Levine, Koby Crammer, and Shie Mannor. Rotting bandits. In Guyon, U. von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Proceedings of the 31st International Conference on Advances in Neural Information Processing Systems (NeurIPS Curran Associates, 2017.
Shoukang Hu, Ruochen Wang, HONG Lanqing, Zhenguo Li, Cho-Jui Hsieh, and Jiashi Feng. Generalizing few-shot NAS with gradient matching. International Conference on Learning Representations (ICLR'22), 2022.
13

---

Timotée Ly-Manson, Mathieu Leonardon, Abdeldjalil Aissa El Bey, Ghouti Boukli Hacene, and Lukas Mauch. Analyzing few-shot neural architecture search in a metric-driven framework. In M. Lindauer, K. Eggensperger, R. Garnett, J. Vanschoren, and J. Gardner, editors, Proceedings of the Third International Conference on Automated Machine Learning (AutoMI. 24). Proceedings of Machine Learning Research, 2024.
Andrea Locatelli and Alexandra Carpentier. Adaptivity to smoothness in X-armed bandits. In Anmual Conference Computational Learning Theory, 2018.
Nilesh Verma, Albert Bifet, Bernhard Pfahringer, and Maroua Bahri. ASML: A scalable and efficient AutoML solution for data streams. In M. Lindauer, K. Eggensperger, R. Garnett, J. Vanschoren, and J. Gardner, editors, Proceedings of the Third International Conference on Automated Machine Learning (AutoMI. 24). Proceedings of Machine Learning Research, 2024.
Amir Rezaei Balef and Katharina Eggensperger. Posterior sampling using prior-data fitted networks for optimizing complex automl pipelines. In Eighteenth European Workshop on Reinforcement Learning, 2025a.
Amir Rezaei Balef and Katharina Eggensperger. In-context decision making for optimizing complex automl pipelines. arXiv preprint arXiv:2508. 2025b.
F. Pfisterer, L. Schneider, J. Moosbauer, M. Binder, and B. Bischl. YAHPO Gym efficient multi- objective multi-fidelity benchmark for hyperparameter optimization. In I. Guyon, M. Lindauer, M. van der Schaar, F. Hutter, and R. Garnett, editors, Proceedings of the First International Conference on Automated Machine Learning. Proceedings of Machine Learning Research, 2022.
David Salinas and Nick Erickson. TabRepo: A large scale repository of tabular model evaluations and its AutoML applications. In M. Lindauer, K. Eggensperger, R. Garnett, J. Vanschoren, and J. Gardner, editors, Proceedings of the Third International Conference on Automated Machine Learning (AutoMLL') 24). Proceedings Machine Learning Research, 2024.
Thomas Nagler, Lennart Schneider, Bischl, and Matthias Feurer. Reshuffling resampling splits can improve generalization of hyperparameter optimization. ArXiv, abs/2405. 153393,, 2024.
Zohar Karnin, Tomer Koren, and Oren Somekh. Almost optimal exploration in multi-armed bandits.
In International Conference on Machine Learning, pages 1238-1246. PMLR, 2013.
Nobuaki Kikkawa and Hiroshi Ohno. Materials discovery using Max K-Armed Bandit. Journal of Machine Learning Research, 25(100):1-40) 2024.
Demšar. Statistical comparisons of classifiers over multiple data sets. Journal of Machine Learning Research, 7:1-30, 2006.
Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed bandit problem. SIAM Journal on Computing, 32(1):48-77, 2002.
14

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the
paper's contributions and scope?
Answer: [Yes]
Justification: We wrote the abstract and introduction reflect the paper's contribution (a practical Bandit strategy for decomposed CASH) as detailed as possible and discuss it ability generalize other settings in the Conclusion (Section 6) and in Appendix B.4.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We provide separate paragraph for the limitations of our methods in Section 6.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, c.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-tex system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
15

---

Answer: [Yes]
Justification: Yes, we provide all necessary assumptions for the theoretical results in Sec- tion 3 and detail proofs for theories in Appendix B. We also discuss the validity of assumptions using on empirical data analysís in Section 3.
Guidelines:
The answer NA means that the paper does not include theoretical results, All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: Yes, we provide detailed information about all the methods we used. This includes description of the computing infrastructure in Footnote an ablation study for hyperparameter selection in Section 5 and Appendix D.4, as well as metrics and experimental details in Appendix D.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurlPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the partieular way they provide for reproducibilitty In the case of closed-source models, it may be that access to the model is limited in
16

---

some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results, checklst
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We make our code and data available at hetps://anonymouu 4oppnn.
acience/r/CASH_He with Baandit//EAAl
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips) cc/
Beaii///guides/CoeSSuteee cosooeeessbbisiiioooooooo for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: /nips. cctppblic/guuiiccccccccceccc.oca heabli/cgiiddsssdeSSttiiiiee
het//eeoeuueieeee wwwiibmmssiinni ssionsolicy for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Yes, in addition to making code available, we provide detailed information about all the methods we used, including the choice hyperparameters. This includes a description of the computing infrastructure in Footnote 5, an ablation study for hyperparam- eter selection in Section 5 and Appendix D.4, as well as metrics and experimental details in Section D.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We report confidence intervals concerning the random seed after running the experiments multiple times (see Figure 6 and Table in the main paper), and we discuss this further in the Appendix D.
17

---

Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provide description of the computing infrastructure in Footnote 5,
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: /n/uriuuu...p/// cc httpai/eeeehhishieeeleeeeleeeeee
Answer: [Yes]
Justification: Our work complies with the NeurlPS Code of Ethics. It involves no human subjects, sensitive data, or misuse risks, and uses only public datasets.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
18

---

Answer: [NA]
Justification: This paper focuses on advancing the field of Machine Learning without direct societal impacts or specific applications that would need be discussed.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is 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 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 attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
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)?
Question:
Answer: [NA]
Justification: Our work poses no known risks of misuse and does not involve high-risk models datasets.
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 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: [Yes]
Justification: All external assets (datasets and code) used in work are publicly available, properly cited, and used in accordance with their respective licenses.
Guidelines:
The answer NA means that the paper does not existing assets.
19

---

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 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, paperswi thcode com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented, and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not introduce any new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This work does not involve crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: This research does not involve human subjects require IRB approval.
20

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question:
Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: We only used LLMs for text polishing and coding assistance.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our L.LM policy (https: httpes///neursppeeeeee /ttperrpps.cccoooffeeeeeeee///// cc//oomferencce/225//A.. for what should or should not be described.
21

---

Table of Contents for the Appendices
Appendix A: Preliminaries
23
Appendix B: Proofs
23
B.1 Proof of Lemma 3.3
23
B.2 Proof of Proposition 4.1
B.3 Proof of Theorem 4.2
B.4 Extension of Proof of Theorem 4.2
27
Appendix C: More Details on Reward Distribution
30
-C.1 Reward Distribution Analysis
30
C.2 More Details on Lemma 3.3
31
C.3 Empirical Validation of Lemma 3.3
32
Appendix D: More Details on the Experiments
35
D.I Metric Calculation
35
D.2 Experimental Setup
35
D.3 Baselines and Their Hyperparameters
D.4 More Results the Sensitivity Analysis of Hyperparameter
40
D.5 More Results for the Empirical Evaluation
43
D.6 More Baselines for the Empirical Evaluation
45
Appendix E: More Details the Empirical Behaviour of MaxUCB
47
E. The Number of Times Each Arm is Pulled
47
E.2 From Theory Practice
49
E.3 Addressing Non-Stationary Rewards
49
E,4 Toy Examples from the Extreme Bandit's Literature
E.5 Supernet Selection in Few-Shot Neural Architecture Search
53
Appendix NeurIPS Paper Checklist
15
22

---

A Preliminiaries
Lemma A.1. Let X1,..., Xn be n samples independently drawn from distribution d, and let G(x) P(X > x) be the survival function. We have:
P
max X₂ S
Se (en())
IStSn
P
max X, > x S <nG(2).
(10)
Proof. Let F(x) P(X < x) be the cumulative distribution function, so G(z) 1 - F())
P(X x). First, consider the probability that the maximum of the samples is less than or equal to
E.
P
max X 5 II (vt) Ig1sn
Se -n((z)
(II)
using the inequality (1 x² S e næ Next, consider the probability that the maximum of the samples is greater than x:
P
max X, Istsn
S
P(X > x) nG(xx.
(12)
i=1
B Proofs
B.1 Proof of Lemma 3.3
Lemma 3.3. Suppose Assumption 3.2 holds. Then, there exists L, U 2 such that the survival function G can be bounded near by two linear functions.
VE (0, a)), Le G(b c) S Ue
(13)
Proof. By applying the Mean Value Theorem (MVT) to the survival function G over an interval [b - e, b), there exists a point e (b e, b) such that:
G(b) G(b c) (c) (b e) (c)
(14)
Since G'(z) =f(x)) where fz) the probability density function (PDF) and G(b) 0 we have:
G(b-c) -) ffe)
(15)
Let I. and U be the minimum and maximum values of the PDF f(c) = G(b-c) over E (0, a).
Le < G(b - c) < Ue
(16)
Notably, cases where we are interested in the survival function near some and 01 a.e. over (b, c, by) applying the MVT again, there exists e (b1 by) such that:
G(b:) G(b, - G' =f(cc)
(17)
which rearranges to:
G(b, f())e GG(b))
(18)
For any (8,6, a1) with 8 we can bound G(b:
G(bz).
Le Le + G(b,) s G(bi c) (f(c)
8 e < Ue
(19)
23

---

B.2 Proof of Proposition 4.1
Proposition 4.1. (Upper Regret Bound) the upper regret bound up to time 7 is related to the number of times sub-optimal arms are pulled,
MAX b3
K
KSK R(T) - T
Σ N:)
(20)
i
T Where - 144= = i}} is the number of sub-optimal pulls arm i, arm d" is the optimal
1=1
arm and b; is the upper bound on the reward of arm given by Assumption 3.2, i.e., the reward of arm i lies within the interval (as, bi].
Proof. This proof is inspired by Assumption 1 of Baudry et al. [2022]. First, we need to determine an upper bound for the difference in the highest observed reward for arm when has been pulled for (T') times compared to when it has been pulled for T times.
E
max Tie
EE
max
Thet
IE
max (N(T)++SSSST
Tie maxTia IST
max N(TT++SSSST
Ti,
FST
Is (T):
E
max N((T)+ISIST
Tha
max Ti, SST
max
The S B
max NI(T)+SIST
Tha
(((T)HSSSST SB
E
mAx
TEe
MaXTIA tST
max MATTHSSSSST
B
(((T)-1S1S7
NITTHSSSST
<
P
Tie
maxTia B
1ST
E
The
max TiA
MATTHISISTT Fit B
(21)
Ni(T)-1S1S7
tST
NATT+SSIST
Since
always
max (T)+
The
b. by choosing
= b. we ensure that
max
The > B = 0, leading to:
NITTSISSIST
E
max Ts. EST
-E E
max The (T),(TT
P
max ((TT++SSSTT
= max
B
RS
N₂(T)
N₂(T)
B
bi-
(22)
T
T
24

---

Using this and according to the regret definition, we obtain the following:
R(T)=
IE. Fammax ri ,
IE. [mxx rT..))
1ST
EST
IE
max E isk
max TEE (2))
NST
min [EE
max Tan.d IST
EE
max Til (SNI(T)
RSK
min
A + E
max Ti, IST
E
max TiA (SN:())
KSK
Equation
N.(T)
min [ + (1
)b.
T
(.)
min A +
max 6:)
(23)
T
R
Based Definition 1, the suboptimality gap for the optimal arm 1" is zero (A,- = 0). Additionally, the total number of pulls for the optimal arm (T-(T) can be calculated as the difference between the total number of pulls across all arms T and the pulls for all suboptimal arms i²), i.e.
N₂- (T) T Σ ((T).. We upper bound the min in equation 23 by the specific value for the optimal arm i*:
max bj
K
R(T) v T
isk
Σ N:(T)
(24)
B.3 Proof of Theorem 4.2
Theorem 4.2. For any suboptimal arm i * i", the number of suboptimal draws NT(T) performed by Algorithm up to time T is bounded by
N.(T) S T1
1 aL + 20 / U,TToogTTT
(25)
Proof. In order find the upper bound for the number of sub-optimal pulls of arm for the algorithm 1, without loss of generality, we assume that arm is the optimal arm, i.e. i = 1. Let
A, [mmaxri.l E[maxri.1 be the suboptimality gap. Our goal is to determine an upper bound 1ST
1ST on (T")), the number of times the sub-optimal arm has been pulled up to time T. First, we identify
the event that the algorithm pulls the sub-optimal arm i time t:
S {max (r1,1, ....,.... (t)) + Ce (f)) S max (o) + (c(n(tt)) max 7i,n + (t)) < max Tin + C,(,((t)) ign$mi(()
(26)
1gn5m(()
where is the event of selecting a sub-optimal arm with a padding function C((n). The exploration bonus (z)n) is function that is designed to account for the exploration-exploiaaioo trade-off and typically depends on and the number of times each arm has been pulled n. Let n (t) and mt(() represent the number of times the optimal arm and an sub-optimal arm have been pulled, respectively, where (!) S & and (t( S l. We want to express S in a union of events that covers all possible scenarios leading to S. Thus, we split S into two complementary conditions as follows:
S S max Fin + C((n((t) S Sx) Uf max Tin + C.(n((t)) > x} (gngn(()
(27)
(5)
25

---

Where is a threshold value, we take r E[max 7t,e.
157
S
max (t)
fi, + Cc(n1(8)) - Blmaxran m IST
Ti, + C((n;(t)) Elmmx rad 15n5m((1
max
EST
max Fin S Emmax r1 (c(m(())) (s)
-
IST
max Tia > Wlmaxrraa (n.(())))) (sn5n,(t)
(28)
KST
Thus, the event S can be contained within the union two bad events:
Underestimating the upper confidence bound of extreme values for the optimal arm 1 Overestimating the upper confidence bound of extreme values for the sub-optimal arm
Now we use Lemma A.1 to calculate the probability of 28:
max 71,m S 15 3Bmaxx Ci(n((t)) 4.1) (SNSSM(()
P(S) S P
1ST
+ P (
Fi,n > E/maxr CC((m(()))
(ISH5n(())
1ST
Elmax CC)) 1S7 -mi(()
Se
+ nt)G)
E[maxrr, (c, (,,,
(29)
1TT
Now, by applying Lemma 3.3, we can simplify the analysis by eliminating the complexities associated with survival functions G1 and G,,
P(S) e (=(())(((C((( + (ntt)
(30)
For the first term of the right-hand side, by the Arithmetic Mean-Geometric Mean (AM-GM) inequality (a + b 2 2Vbb) of equation 30, we have:
(31)
In this stage, we want to find a proper padding function (n),, which controls the right-hand side of equation 30 and equation 31. By choosing (n(n) = = lolgg(() )a, we have:
(m(())((C((((())))) < 24
log())(()) =t -22,,a
(32)
((())..C((M())) U² (1)
(33)
nt(t)
This selection of the function of the exploration bonus results in two significant advantages. First, it provides an upper bound for the right-hant hand side equation 30 that remains independent ni- Furthermore, Equation 31 shows decreasing trend the number of pulls for the sub-optimal arm increases.
We note that this choice is not based on the inherent property of maximum values. In general one (z()) = lo nm for m >> 1 with the optimal m depending on the setting. In Appendix B.4 we show how affects the regret.
26

---

Now, we assume that the sub-optimal arm has been played for 4 times, so nt, 2 4. We want to calculate the number sub-optimal pulls of arm up to time T:
a U2 (0g
(T) 24 +
Σ 1=4
P(S)
244
1=4
t=
T1-2i
a²
< 4 +
T Tlgg
(34)
2L
4
By choosing 1, = av/U;Tlog(T) we have:
(T) v T1-2haav3;
+ 2ay U,T lTg(T)
(35)
1 1 2L2
B.4 Extension of Proof of Theorem 4.2
As we discuss in Section 3, the reward distribution in our setting is left-skewed. We now show that under the assumption that the survival function decays rapidly near the maximum i.e., (B[maxx Tiaa) (zz)). tighter bound can be derived. This assumption means that the reward distribution has a very light-tail near its upper extreme, which may often hold our left- skewed distributions. Furthermore, we generalize our algorithm by assuming C2 (olg(()) ym as exploration bonus function, where m 2 is hyperparameter.
Proof. We begin with Equation 27 and take IE 1B[maxria ri.a + cAi, where is arbitrary variable e E [0, 1]. We have:
KT
SC max Fi, + (t)) & E[max r ccd
(5ngm(()
tT
max (t)
Tin + C.(n((()) E[max ri cAi
'57
max Fin S Emmaxr -1- -G(m())) c((((())) (snSmI(1)
max Pin E|max rm. -C. + (5n
max Fl, F/max r1,1] -1a)-(111))))))) C(m(())
(36)
(5n
1ST
max Tin > Blmaxrad - C((n((t)) + cA., C.(n((t) scai (Sn tST
(37)
max Pín > E f/maxr (t), cA., C((((t)) cd, >d 15n5m;()
(38)
1ST
First, we calculate the probability of event Sg:
P(Sz) S P(
max Pin Ign5m,(t)
E.
mm Tú.)
} < (I.[xxammaxxx tsT
S (Emmxx KT
(39)
KT
27

---

By calculating the number of sub-optimal pulls of arm i up to time T, we know the third part of the event (Sa) can happen at most CT - (cAi) = (og(T) times:
cd;
(T) S log
1
P(S)) + P(S2)
(40)
c
(o)
T
+ G
max 1ST
maxxxcl rce)
+
P(Si)
(41)
cAi
t=1
T M +
a (T) cA,
P(S1)
(42)
Where M is a constant as we assume G, (B[maxisT ria]) O ( Finally, we need to find an upper bound for P(Si). We need to differentiate between two situations, when m 1 and when m >
For 1. We set and then we have:
P(S)) e aa -1--0 e -=1_(((((0000=----1))))) -oL log(T) <r
(43)
(44)
Finally, we have:
a log (T) -
(TT s M +
(45)
1 aLi
With +.
N,(T) 0 log(?) (T),
(46)
L A
For m > 1. We know n(( + b) 2 ab [m(m 1) -J..
We have:
P(S)) S (0 I [ m [m(m (m(m--1) #h
(og " (m(m-1) -1)
(47)
(48)
For simplicity, we set c 1.2 Then:
N.(T) S (log(())
T mm + M + Σ P(S2)
1
(49)
cA,
t=1
T1-al1 (4) m-1 1m( -1
2a log(T) (T)
+ M +
(50)
A
aL1 ( (2)) m1 [m(m 1) -/ -1]
Finally, we have:
2a log T
2 + -0) T_ ,²
N.(T)
(51)
A
And by choosing a as below
0
(52)
Li (A)),)
28

---

We have:
(T"
N,(T) -0 ب1
(53)
We would like to emphasize again that this result only holds when G3 G:[[maxess Tia)) is sufficiently small. By using a weaker assumption, controlling G3 G[[Ilmaxxes Ti.e)) is necessary. In Theorem B.3, we address this for our method by considering (t(n,(t) 2 (E r.,e) to ensure proper control.
Notably, in general, A, depends on (see Definition 3.1). Meaning that (og(T) A, does not necessarily
lead to logarithmic regret. However, in some special scenarios where the reward distributions have different supports, we ensure that A; b1 b; T approaches infinity, and logarithmic regret achievable.
Furthermore, Equation 53 shows that the parameter m controls (T))), the number of times suboptimal arm pulled asymptotically. When T very large, higher value of m (along with the optimal o) improves performance. However, it makes the algorithm more sensitive to the choice of a. As shown Equation 52, with increasing m, A, has a greater influence on the optimal a. Noting that A; varies across arms and is typically unknown for unseen task, finding the optimal is not feasible in practice. Therefore, there is a trade-off between performance and sensitivity. In the CASH setting, = performs empirically well, while exhibiting low sensitivity to Furthermore, as shown in Appendix D.4, we can find a range of a for which the MCB works well across different CASH tasks.
29

---

C More Details on Reward Distribution
C.1 Reward distribution analysis
In addition to the analysis in the main paper in Figure 2 in Section 3, we collected the observed rewards (the output of HPO) for all arms on each model class. We calculate each dataset's empirical survival function G' and provide the reward distribution analysis for all benchmark tasks, Notably, the shift in distribution (indicated by the thin lines) is low for all tasks, not contradicting the i.i.d. assumptions. For our method, we design our algorithm based on analyzing the distribution of raw rewards (in contrast to the distribution of maximum values over time).
Over time, the maximum value of samples generated from an i.i.d. distribution has an increasing trend, i.e., the extreme values get better. Notably, this strategy Liu et al. [2019], which assumes that the maximum observed value over time is not decreasing (and then analyses the trend this maximum observed value as (non i.i.d) reward).
contradictory with the Rising Bandits
TabRepo
1.0
Sunval fundiin
0.5
0.5
-002
0.0
0.0
0.0
0.6
0,8
1.0
0.00
0.25
0,50
0.75
1000
2
5
Reward
Reward
Sub oobiopttool am
TabRepoRaw
1.0
0.70
Santia function.
0.5
0.5
0.0
0.01
0.00
0.2
0.4
0..6
0.51
1.0
0.00
n125
0,50
0..66
1000
2
Roward
Reward
Sub optimal arm
YaHPOGym
1.01
Servial function
0.75
0.50
0.5
0.5
0.25
0.01
0.01
6.00
0.25
0.50
0.75
1.00
0.00
0.25
0,50
0.75
1.00
3
Reward
Reward
Sub-optimal arm
Reshuffling
1.0
0.73
Sunsial funcioon
0.5
0.5
-1
0.00
0.00
0.00
0.75
0.50
0.75
1.00
0.00
0.75
0.50
0.76
1.00
2
Reserl
Reward
Suboptimml amm
Optimal
2nd
3rd
4th
6th Worst
Figure C.1: (Left) The average empirical survival function of rewards (observed performances) per arm ranked per dataset. We divided the reward sequence into five segments over the budget (time horizon) to show the distribution change functions for different segments, visualizing the change over time. (Middle) The average empirical survival function per dataset for the best and worst arm with thin lines corresponding to individual datasets. (Right) The sub-optimality gap A,
time. Thin lines correspond empirical survival
30

---

C.2 More Details on Lemma 3.3
and U are lower and upper bounds for the tangent line approximation of the survival function G near the maximum value, indicating the shape of the distribution. We provide three examples to demonstrate this numerically.
Toy example: Assume two simple survival functions Gi = x² (left skewed, blue curve) and (2(x))
x:)² (right skewed, orange curve) with support [0, 1]. We calculate G(1 <)/c some values of c the Figure C.2. To compute I. and U, we determine the minimum and maximum values of G(1 <)/e over the range 0 {0.1, 0.3, 0.5, 0.7, 0.9}. It implies that the calculated values of L and U are valid for E [0.1, 0.9].
For clarity, we restricted
iterate only over the set
Gi(l-c)
G2(1-c)
0.9
0.7
0.5
0.3
0.1
0.10
1.90
0.10
G1(z) 1 x²
Ga(x) - (1 x²²
0.30
1.70
0.30
0.8
U/fe
y
0.50
1.50
0.50
0.70
1.30
0.70
0.4
0.90
1.10
0.90
L
1.10
0.10
0.2
Lge
U
1.90
0.90
0..00
0.2
0.1
0.6
0.8
1.0
Figure C.2: (Left) Determining L and U for G1 and G2. We calculate G0-o) over different ranges of The minimum and maximum values obtained from this ratio are assigned L and U, respectively, (Right) Showing two survival functions G and G2 along with their linear line approximations (gray lines). These tangent lines illustrate how and U effectively bound the survival function G near its maximum value.
Truncated uniform distribution: Assume that we have a truncated uniform distribution with support (a, b). We know G(x) = b-xt for x E (a, b). For every E [a, b) we have G(h-e) means L = --= b-o"
b-a which
b-a
Truncated Gaussian distribution: There is no closed-form solution to formulate L and U based on the parameters of the truncated Gaussian distribution. Thus, we show the results of simulations to estimate T. and U for truncated Gaussian within [0, 1] with various values and a, averaging over 1000 runs in Figure C.3.
μ
U
1.00
0.35
0.25
0.5
0.58 = 0.06
1.70 + 0.48
0.75
0.75
0.50
0.5
0.85 0.07
1.53 + 0.34
0.56,
0.50
0.75
0.5
1.01 0.01
1.64 + 0.25
0.25
0.2
0.34 = 0.07
1.54 + 0.28
0.25
0.50
0.2
0.44 - 0.08
1.36 1 0.04
0.00
0.75
0.2
1.01 = 0.00
1.95 - 0.04
0.00
0.25
0.50
0.75
1.00
Figure C.3: (Left) Determining L and U for truncated Gaussian within [0, 1] with different values for μ and a. Averaged over 000 runs. (Right) Showing survival function of truncated Gaussian distribution with different values for p and
31

---

TabRepo
Optimal arm
2nd arm
3rd arm
4th arm
5th arm
6th arm
Worst arm
10
1.0
10"
0.0
0.5
20
10
0
0.1 1
10
0.1 10
0.1 1 10
0.1 10
0.1 1 10
0.1 10
0.1 1 10
Values for
Values for
Values for
Values for
Values for
Values for
Values for
Froquueccy
01
100
0.01
0.03
100
0.01
100
0.03
100
Values f
Values for U
Values for
Values for
Values for
Valluss for U
Values for
Averaage Stt-e!!
(per dataset!
minn (ib-dt)
Figure C.4: Arms are ordered by sub-optimality gap. (Top) Thin orange lines represent G(b-r), while the blue and red points correspond to L and U for our empirical reward distributions (see Lemma 3.3 for details). (Middle) Histogram of values for (Bottom) Histogram of values for U.
C.3 Empirical Validation of Lemma 3.3
To study the empirical values for L and U in Lemma 3.3, we leverage the calculated empirical survival function G for each dataset in Appendix C.1. Specifically, we evaluate G(b-c) over the range (0.99) < < G0.00., where (x) denotes the inverse of the survival function G(x)). Focusing on this range allows us achieve a more robust estimation. Additionally, for TabRepo dataset, we exclude 23 datasets containing arm with a standard deviation smaller than 0.001, further enhancing the robustness of our analysis. Figures C.4, C.5, C.6, and C.7, the evaluated values of G(b-c) for different benchmarks are shown. Additionally, the values for and U, corresponding min( G(b=e)) and max( G(b-s)), respectively, are presented. Finally, the histograms of these two variables also included.
32

---

TabRepoRaw
Optimal
2nd
3rd amm
4th
5th arm
6th
Worst
10
100
0.0
0.5
Frequency
Vallues
Values
Values
Values for
Values
Values
Fresuency 6
100
0.01
0.03
100
0.01
0.01
100
0.03
0.01
100
Average
(per dataset)
ming
max
Figure C.5: Arms are ordered by sub- optimalttylyty gap. (Top) Thin orange lines represent G(b-r) while the blue and red points correspond to and U for our empirical reward distributions (see Lemma 3.3 for details). (Middle) Histogram of values for L. (Bottom) Histogram of values for U.
YaHPOGym
Optimal
arm
arm
arm
10P
10a
1.0.0.0
1.00.0
1.0.0.0
0.5
0.0
0.5
1.00.0
Deeqancy
10
10
10
10
16
Values for
Values for
Values for
Values for
Values for
Values for
Erequeeng
0.01
Values for
Values for
Wilues for
Vilues for U
Values for U
Viluus for U
Average
(per dataset!
Figure C.6: Arms are ordered by sub-optimality gap. (Top) Thin orange lines represent G(b-e) while the blue and red points correspond to L. and U for our empirical reward distributions (see Lemma 3.3 for details). (Middle) Histogram of values for (Bottom) Histogram of values for
33

---

Reshuffling
Optimal
2nd
3rd
Worst
10a
1.0
10
0.0
0.2
0.4
0.6
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00 0.00
0.25
0.50
0.75
1.00
0.1
10
0.1
10
0.1
10
0.1
10
Values for
Values for
Values for
Values for
01
100
0.01
100
100
100
Values For U
Values for
Valluss for U
Vallues for U
Figure C.7: Arms are ordered by sub-optimality gap. (Top) Thin orange lines represent G(b-c) while the blue and red points correspond to L and U for our empirical reward distributions (see Lemma 3.3 for details). (Middle) Histogram values for (Bottom) Histogram of values for
34

---

#models
#tasks
type
HPO meth. (rep.)
budget reference
YaHPOGym
6
103
surrogate
SMAC (32)
200
[Pfisterer et al., 2022]
TabRepo
7
200
tabular
random search (32)
200
[Salinas and Erickson, 2024]
TabRepoRaw
7
30
raw
SMAC (32)
200
Reshuffling
4
raw HEBO (30)
250
[Nagler et al., 2024]
Table D.I: Overview of AutoML tasks. For TabRepo and Reshuffling, we use pre-computed HPO trajectories. TapRep resembles the same model space as TabRepo, but instead random search, run HPO ourselves. Similarly, run HPO across provided surogate HPO benchmark tasks YaHPOGym. We use SMAC [Lindauer et al., 2022, Hutter et al., 2011], implementing Bayesian optimization using Random forests for both tasks.
D More Details on the Experiments
D.1 Metric calculation
Average ranking calculation. We use bootstrapping with Monte Carlo sampling calculate the average ranking plot with confidence intervals. For each time step and each task in every dataset, we resample the performance of each repetition (with replacement) and compute the average performance. We then rank the algorithms based on these averaged performances and repeat this process for all tasks. Finally, we average the rankings across tasks. This entire procedure was repeated 1000 times to estimate the confidence interval.
Number of wins, ties, and losses. To determine the number of wins, ties, and losses for each task in every dataset, we first compute the average performance of cach algorithm over all repetitions at the final time step. We then perform pairwise comparisons of these averaged performances among all algorithms versus combined search. To account for negligible differences that are not statistically significant, we consider two performances to be tied if they sufficiently close. Specifically, NumPy's isclose function to compare the averaged performances, treating values within a default tolerance of x 10-8 as equal.
D.2
Experimental Setup
Here, we provide details on our experimental setups. We used several well-established and widely used benchmark sets (as described Table D.1) that were developed to compare HPO methods. Each benchmark contained different datasets, tasks, and search spaces to ensure that our empirical distribution analysis was not limited to a single source or problem type.
YaHPOGym [Pfisterer et al., 2022], a surrogate benchmark, covers 6 ML models (details in Table D.2) on 103 datasets and queried hyperparameter settings. We use Bayesian optimization as implemented by SMAC [Lindauer al., 2022] using Random Forests to conduct HPO. Additionally, we compare our two-level approach to combined search using SMAC, SMAC without initial design (SMAC-no-ini)) and Random Search. We run 32 repetitions and use a budget of 200 iterations for each evaluation.
regression model (surrogate model) predict performances for
TabRepo [Salinas and Erickson, 2024] consists of pre-evaluated performance scores for 200 iter- ations of random search for ML models (details in Table D.3) on 200 datasets (context name: D244_ F3__F33CC333 C153002000. We run 32 repetitions and use budget of 200 iterations for each task.
RapRe which uses the search space from TabRepo (details in Table D.3) and allows HPO to evaluate all configurations. For constructing TabRepo [Salinas and Erickson, 2024], each configura- tion was evaluated with one-hour time limit and 8-fold cross-validation. To reduce computational requirements for TabRepoRaw, we reduced this to minutes and 4-fold gross-validation and we provide it for 30 datasets (context name: D244_FFS F3 33__C1330_30 implemented by SMAC [Lindauer et al., 2022] using Random Forests to conduct HPO. Additionally, compare our two-level approach to combined search using SMAC, Random Search. We run 32 repetitions and use a budget 200 iterations for the mentioned task.
We use Bayesian optimization as
To enable fair comparison, we always evaluate the default configuration for each model first and then allow SMAC to run an initial design of 50 #arms configurations the upper level and 50 Tarms-I
in the lower level.
35

---

Table D.2: Hyperparameter spaces for ML models in YaHPOGym.
ML model
Hyperparameler
Type
Range
Info
trainsize imputation
continuous
[0.03, 1]
=0.525 (fixed)
categorical
{mean, median, hist)
=mean (fixed)
alpha
continuous
[0. 1] [0.001, 1097]
Glmnet
continuous
log
cp
continuous
[0.001,
log
maxdepth
integer
[1, 301
Rpart
minbucket minsplit
integer
[1, 100]
integer
[1, 100]
kernel
categorical
[linear. polynomial, radial)
cost
continuous
[4.5c-05, 2.2c4]
log
SVM
gamma
continuous
[4.5c-05, 2.2c4]
log. kernel
tolerance
continuous
[4.5c-05,
log
degree
integer
[2.
kerell
integer
[1, 50]
distance
categorical
[12, cosine, ip)
AKNN
M ef
integer
[18, 50]
integer
[7. 403]
log
ef_construction
integer
17, 403]
log
num.trees
integer
[1. 2000]
sample.fraction
continuous
[0.1,
mtry.power
integer
[0. 1]
Ranger
bonpecttuoordred..ooo
categorical
fignore, order, partition)
min.node.size
integer
[1, 100]
splitrulc
categorical
[gini, extratrees]
num.random.split
integer
[1. 100]
splitrule
booster
categorical
(gblinear, ghtree, dart)
nrounds
integer
[7. 2980]
log
eta gamma
continuous
[0.001, 1]
log, booster
continuous
(4.5e-05. 7.4]
log. booster
lambda
continuous
[0.001, 1097]
log
alpha
continuous
[0.001, 1097]
log
XGBoost
subsample
continuous
[0.1, 1]
max depth
integer
[1. 15]
booster
min child weight
continuous
[2.72, 148.4]
log, booster
colsample bytree
continuous
[0.01, 1]
booster
colsample_byloo rate_drop skip_drop
continuous
[0.01, 11
booster
continuous
[0, 1]
booster
continuous
[0, 1]
booster
Reshuffling [Nagler et al., 2024] which uses Heteroscedastic and Evolutionary Bayesian Optimization solver (HEBO) [Cowen-Rine Riverss et al., 2022] for HPO. This benchmark includes HPO runs for 4 ML models (details in Table D.4) across 10 datasets, with 10 repetitions and different validation split ratios within budget of 250 iterations. Although the benchmark does not support HPO over the entire search space, it offers valuable opportunity to compare the performance of bandit methods in realistic setting.
36

---

Table D.3: Hyperparameter spaces for ML models in TabRepo and TabRepoRaw.
ML model
Hyperparameter
Type
Range
Info
Default value
learning rate
continuous
[Ic-4, 3c-2]
log
3e-4
weight decay dropout prob
continuous
[1c-12, 0.1]
log
le-6
continuous
[0, 0.4]
0.1
NN(PyTorch)
batchnorm num layers
categorical
False, True
integer
[1.
hidden size
integer
[8, 256] relu, elu
128
activation
categorical
learning rate
continuous
[5c-4, lc-1]
log
1c-2
layers
categorical
[200], [400], [200, 100),
[400, 200), [800, 400),
[200, 100, 50], [400, 200, 100]
NN(FastAI)
emb drop ps
continuous
[0.0, 0.7]
0.1
continuous
[0.0, 0.7]
0.1
bs epochs
categorical
256, 128, 512, 1024, 2048
integer
[20, 50]
30
learning rate depth
continuous
[Se-3 ,0.1]
log
0.05
integer
[4,
12 leaf reg max ctr complexity one hot size grow policy
continuous
[1.5]
CatBoost
integer
[].
categorical
3, 10
categorical
Symmetric/Tree, Depthwise
learning rate feature fraction min data leaf num leaves extra trees
continuous
[5e-3 ,0.1]
log
0.05
continuous
[0.4, 1.0]
1.0
LightGBM
integer
[2. 60]
20
integer
[16, 255]
31
categorical
False, Truc
learning rate depth
continuous
[5e-3 .0.1]
log
0.1
integer
[4. 10]
XGBoost
min child weight colsample bytree enable categorical
continuous
[0.5, 1.5]
continuous
[0.5, 1.0]
1.0
categorical
False, True
max leaf nodes min samples leaf features
integer
[5000, 50000]
Extra-trees
categorical
2, 3, 4, 5, 10, 20, 40, 80 sqrt, log2, 0.5, 0.75, 1.0
categorical
leaf nodes min samples leaf max features
integer categorical categorical
[5000, 50000] 4, 5, 10, 20, sqrt, log2, 0.5, 0.75, 1.0
Random-forest
37

---

Table D.4: Hyperparameter spaces for ML models in Reshuffling.
ML model
Hyperparameter
Type
Range
Info
learning rate
continuous
[lc-4, le-1]
log
num layers
integer
[].
max units
categorical
64, 128, 256, 512
Funnel-Shaped MLP
batch size
categorical.
16, 32, ... max_ max_batchhssi size
momentum
continuous.
[0.1, 0.99]
alpha
continuous.
[le-6, le-1]
log
C
continuous
[1e-6, 10e4]
log
Elastic Net
11 ratio
continuous
[0.0, 1.0]
max depth
integer
[2. 12]
log
alpha lambda
continuous
[le-8, 1.5]
log
XGBoost
continuous
[le-8, 1.0]
log
eta
continuous
[0.01, 0.3]
log
learning rate depth
continuous
[0.01 .0.3]
log
CatBoost
integer
[2. 12]
12 leaf reg
continuous
[0.5, 30]
38

---

D.3 Baselines and their hyperparameters
We use several bandit algorithms as baselines. Table D.5 summarizes the hyperparameters and their
values.
Table D.5: Hyperparameters Bandit Baselines.
Algorithm
Hyperparameter
Valuc
Reference
MaxUCB
0.5
Ours
1.0
Quantile Bayes UCB
0,2
0.95
Balef et al. [2024]
0.5
Quantile UCB
0.95
0.6
ER-UCB-S
0.01
20.0
Hu [2021]
1.0
ER-UCB-N
0.01
20.0
C
7
Rising Bandits
et al. [2020]
T
Time horizon
Max-Median
1/(1), is iteration
Bhatt et al. [2022]
QoMax-SDA
0.5
2/3
DTC
0.5
Baudry et al. [2022]
bT
4
3
Time horizon
UCB
0.5
Auer [2002]
ThresholdAscent
0.1
20
Streeter and Smith [2006b]
T
Time horizon
2.0
Successive Halving
Karnin et al. [2013]
T
Time horizon
R-SR
0.25
T
Time horizon
R-UCBE
57.12
Mussi et al. [2024]
0.25
0.05
Time horizon
MaxSearch
1.0
(Gaussian)
Kikkawa and Ohno [2024]
MaxSearch
0.27
(SubGaussian)
39

---

D.4 More Results on the Sensitivity Analysis of Hyperparameter
In addition to the results shown Figure in Section we provide additional results here. We evaluated the performance of MaxUCB for E [0, 2.9] with step size 0.1. We plot the performance over the number of iterations for different values of Figures D.1, D.2, D.3, D.4. Green indicates better performance, showing the impact of at different stages of the optimization procedure. Furthermore, we provide a comparison between MaxUCB with different values of with combined Search(SMAC) in Table D.6. For the experiments in the main paper, we choose 0.5 as robust choice over all datasets. Notably, a 0.5 selected based on the assumption that the reward distribution support is [0, 1]. For other supports, recommend scaling according to the range of the support.
Normalized loss
TabRepo
Ranking TabRepo
0.0
0.0
0.2
0.2
0.4
0.20
0.4
0.6
0.6
0.8
20
1.0
0.15
1.0
1.2
1.4
1.6
15
0.10
2.0
2.2
10
0.05
2.6
2.8
20
40
60
80
100 120
140 160 180 200
40
80
120 140 160 180 Itcration
100
Itcration
Figure D.1: Heatmap showing the performance of our algorithm with different values of a for TabRepo dataset.
Normalized loss TabRepoRaw/SMAR
Ranking SabRepoRaw(SMAC
0.0
0.0
0.2
0.30
0.2
0,4
0.4
0.6
0.6
0.8
0.25
0.8
1.0
1.0
1.2
0.20
1.2
1.4
144
1.6
1.6
18
00.15
1.8
2.0
2.0
2.2
0.
2.2
10
2.4
2.4
2.6
2.8
40
80
120
160 180 200
40
80
120
160
Iteration
Iteration
Figure D.2: Heatmap showing the performance of our algorithm with different values of for Tab dataset.
40

---

Normalized loss YaHPOGGy(SMAC
Ranking YaHPOGGm|SMAC]
0.0
0.21
0.0
0.2
0.2
0.4
0.4
25
0.6
0.6
0.8
0.8
1.0
1.0
20
1.2
1.2
1.4
1.4
1.6
1.6-
18
1.8
2.0
O.1
2.2
24
2.6
0.00
2.8
5
20
80 100 120 140 160
200
20
60
100 Iteration
120
140
160
180
Iteration
Figure D.3: Heatmap showing the performance of our algorithm with different values of for YaHPOGym dataset.
Normalized loss BishuffflngHHEBBO
Ranking Reshuffling [HEBO]
0.0
0.0
0.2
0.2
0.4
0.4
0.5
0.1
0.6
0.8
0.8
1.0
0.1:
1.0
12.
1.2
1.4
0.1
1.4
1.6
18
1.8
2.0
2.
244
2.6
2.8
0.0.
25
100 125 150 175 200 225 250
25
75
100
125
150
175
200
225
Iteration
Iteration
Figure D.4: Heatmap showing the performance of our algorithm with different values of for Reshufiling dataset.
41

---

Table D.6: Comparing MaxUCB with combined search(SMAC) for different values of a and time steps. P-values from sign test assessing whether bandit methods outperform combined search. P-values below 0.05 are underlined, while those below a 0.05 after multiple comparison correction (adjusting a by the number of comparisons) are boldfaced and underlined indicating that the two-level approach is superior to combined search. Additionally, we report the normalized loss and the number of wins, ties, and losses (w/t/l) of bandit methods.
Time
-=0.0
a=0.1
a=0.2
a=0.3
o=0.4
a=0.5
o=0.6
a=0.7
a=0.8
TabRepoRaw(SMMN (SMAC)
v-vulue
0.1002
0.0214
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0,0000
50
whll
19AV11
21/09
27/03
29/01
29/11
29/V1
290/1
28/0/2
27/0/3
27/03
0,2555
0.2172
0.1965
0.2134
0.2203
0.2229
0.2296
p-value 0.9974
0.9919
0,8998
0.1808
0.0081
0.0214
0.1002
0.5722
0.8192
0.9919
100
w/ll 8/V/2
9/021
12//18
15/0/12
22/088
21/099
19/V/1
15/0/15
13/0/17
9/021
0.2138
0.2053
0.1832
0.1346
0.1283
0.1113
0.1164
0.1208
0.1279
0.1512
p-value 0.9993
0.9919
0,9506
0,2923
0.0007
0.0007
0.0026
0.0081
0,1002
0.7077
150
w//l 7/0/23
9/V/1
11/0/19
17/0/3
24/046
24/V6
23/077
22/0/8
19/1/11
14AV16
loss 0.1994
0.1911
0.1671
0.1020
0.0898
0.0752
0.0775
0,08419
0.0887
0.0973
p-value 0.9998
0.9993
0.9786
0.1808
0.0214
0.0007
0.0026
0.0026
0.0081
200
w/ll 6/021
7/0/23
10/0/20
18/0/12
21/099
2
23/077
23/0/7
22/0/8
22/0/8
loss 0.1864
0.1790
0.1489
0,0686
0.0651
0.0563
0.0622
0.0698
0.0703
0.0751
p-value 0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
50
w/ll
T4/1/28
83/1/19
95/1/7
102/1/0
102/1/0
102/1/0
102/1/0
102/1/0
102/1/0
loss
0.1853
0.1532
0.1071
0.0930
0.0942
0.0978
0.1047
0.1101
0.1151
0.1190
p-value
0.3833
0.3833
0.3833
0. 0.0159
0.0112
0.0112
0.0088
0,0572
0.2153
0.1220
wh/l 531/49
53/1/49
53/1/49
60V1/42
63/1339
63/1/19
64/039
600044
56AV47
53/V50
loss
0.1494
0.1177
0.0876
0,0813
0.0782
0.0713
0. 06088
0.0702
0.0718
0.0749
p-value
0.3833
0.6167
0.8135
0.0G86
O 0,0036
0.0065
0.0028
0.0005
O 0002
0.0148
150
w/vl 53/1/19
50/1/52
47/1/5
59/1/13
65/1/37
64/1/38
66/W37
68/1/31
66/037
63/0/10
loss 0.1378
0.1013
0.0758
0.0722
0.0716
0.0551
0.0518
0.0507
0.0520
0.0500
p-value 0.5394
0.8135
0.6896
0,2442
0.0185
0. 0.0088
0.0015
0.0002
0 0,0000
O. 0.0001
200
w/vl
51/1/51
47/1/55
49/1/53
55/1/17
62/1/10
64/0/99
67/0/36
70/1/3
75/0/28
71/032
loss
0.1190
0.0856
0.0697
0,0660
0.061-1
0.0157
0.0143
0.0418
0.0123
0.0121
42

---

D.5 More Results for the Empirical Evaluation
In addition the analysis in the main paper in Figure in Section 5, we report the averaged normalized loss over time in Figure D.5, the average ranking in Figure D.6, the normalized loss per task in Figure D.7, the ranking per task in Figure D.8 and critical distance plots described by Demšar [2006] in Figure D.9. Additionally, we report results for Random Policy (yellow) that selects arms to pull at random.
[RbS
TabRepoRaw[SMAC]
YaHIOOGm([SMAC
ReshufTing(HERO)
Quamle Bayss
Nornalized loss
ER-UCS-5
Brong flass
CoMac SEA
Max Medus
0.1
Polay
SMAC
0.1
Runsor Sarth
Grade
0.01
200
Iteration
Iteration
Iteration
Iteration
Figure D.5: Average normalized loss of algorithms different benchmarks, lower is better. SMAC and random search perform combined search across the joint space.
TabRRepo RSI
TabRepoRRaw
YaHPOOym/SMMCI
ReshufflingHHHEBB0
Ranking 9
10.0
MaxUCB
Quentk
6-
7.5
Raing Bands
7.5-
QuMacS3A
Max Nador
UCB
4-
5.0-
Ravin Pelcy
2
2.5
2.5
2
Soon
Crede Am
0
200
200
200
0
200
Iteration
Iteration
Iteration
Iteration
Figure D.6: Average ranking of algorithms on different benchmarks, lower is better. SMAC and random search perform combined search across the joint space.
MaxUCB
Quantile Bayes UCB
FR-UCa-S
Riing Bandi
QoMax SDA
Max Median
UCB
Random Policy
Randem Search
SMAC-mn-int
TabRepo(RS]
TrRRepaRaw(MMc]
YaHPOGy [SMAC]
Reshuiing(HEBO)
Figure D.7: Heatmap showing the normalized loss of algorithms per task of each benchmark, sorted by the oracle arm performance, lower is better. SMAC and random search perform combined search across the joint space.
43

---

Quantile
SMWC
SMAC
(SMAC)
Rechufing(HEBO)
Figure D.8: Heatmap showing the ranking of algorithms per task of each benchmark, sorted by the oracle arm performance, lower is better. SMAC and random search perform combined search across the joint space.
TabRepo
TabRepoRaw
CD 6 4 2
6 3
UCB ER UCB ODMaX Max Median
Rising Bandit
MaxUCB Kising Bayes UCB
SDA Maj. SDA
Quantie Bayes UCB
ER-UCB-S
CD
Random Search
Oracle Arm
Random Search
Oracle Arm MaxUCB
YaHPOGym
Reshuffling
CD
$
2
6 4
2
MaxUCB Rising Sendit Quantlle Bayes UCB
SDA EN-UCB-S
QoMak-SDa SDA Quandile Bayes UCB
Max- Rising Bandit
CD
4
Random Search SMAC-no-inE MB
Oracle Arm
Figure D.9: Diagrams to compare the performance (ranking) of different algorithms using the Critical Distance (CD). For each benchmark top, compare bandit methods, and on the bottom, compare MaxUCB against combined search and the oracle arm.
44

---

D.6 More Baselines for the Empirical Evaluation
Max K-armed Bandit Baselines. We compare MaxUCB against MaxSearch Gaussian [Kikkawa and Ohno, 2024], MaxSearch SubGaussian [Kikkawa and Ohno, 2024], QoMax-ETC [Baudry et al., 2022], QoMax- SDA [Baudry et al., 2022]. Max-Median [Bhatt al., 2022] and Threshold Ascent [Streeter and Smith, 2006b]. We report the averaged normalized loss over time in Figure D.10, the average ranking in Figure D.11. As shown, our algorithm outperforms all extreme bandit algorithms in these benchmarks.
TabRepo|RS]
TabbRepoRaw (SMAC]
YaHPOGynlSMACI
ReshufllnggH HEBB]
Nadaord
Nadieth Subtuum
QullanETTC
Normalized
Deltbu
0.1
0.1.
0.1
0.1
SMAG-wiit
Rudkw Seart
Oncls Ant
200
200
200
Iteration
Iteration
Iteration
Iteration
Figure D.10: Average normalized loss of MKB algorithms different benchmarks, lower is better. SMAC and random search perform combined search across the joint space.
[abRepo[RS]
TabRepoRaw/SMAC)
YaHPOGym[SMAC
Reshufflin(HEBB)
10
MaxUCB
10.0
Madworch Goanzee
ScCCazniar
Ranking sr
QTM
7.5-
MarModar
Tiredoki Acaet
4-
5.0
Randon Poloy
SMAC
2-
fendon
Grade Arm
200
200
200
200
Iteration
Iteration
Itcration
Iteration
Figure D.11: Average ranking of MKB algorithms on different benchmarks, lower is better. SMAC and random search perform combined search across the joint space.
Few More Relevant Bandit Baselines. We compare Max against Quantile UCB [Balef et al., 2024], ER- UCB-N [Hu et al., 2021], R-SR [Mussi al., 2024], R-UCBE [Mussi et al., 2024], Successive Halving [Karnin et al., 2013] and EXP3 [Auer et al., 2002]. We report the averaged normalized loss over time in Figure D.12, the average ranking in Figure D.13.
TabRepo[RS]
TahRepoRaw (SMAC]
YaHPOGGy|(SMAC)
Reshufiling(HEEBO0)
MaxtiCa
Normalized loss
R:SR
RJUGBE
Suceesive Halking
Exp3
0.1-
Ranker Pulicy
0.1
0.1
SMACGooiit
Bander Searc
Oncc Ave
200
200
200
0
200
Iteration
Iteration
Iteration
Iteration
Figure D.12: Average normalized loss of algorithms on different benchmarks, lower is better. SMAC and random search perform combined search across the joint space.
45

---

TabRepo(RS]
TahRepoRaw(SMAAC
IaHPOCGm|SMMCC
Reshufling(UIBBO
10
BRAUCEIN
B:Sit
Ranking 6
7.5
R-ULBE
Halvin
+
4-
5.0
SMA
2-
2-
2.5
2
Ranken Search
200
200
0
200
0
200
Iteration
Iteration
Iteration
Iteration
Figure D.13: Average ranking of algorithms different benchmarks, lower is better. SMAC and random search perform combined search across the joint space.
46

---

E
More Details on the Empirical Behaviour of MaxUCB
Here, we provide further analysis of MaxUCB, Concretely, we study how often our algorithm pulls the optimal arm and compare it to the theoretical results. Furthermore, we evaluate an extension of MaxUCB handle non-stationary rewards and finally study MaxUCB performance on common synthetic benchmarks used in the extreme bandit literature.
E.1 The number of times each arm is pulled
Proposition 4.1 shows that the number of times the optimal arm pulled can be viewed as good metric for measuring the performance of algorithms. Figure E.I, E.2,E.3,E.4 shows the average number of pulling arms on different benchmarks. They indicate that, on average, MaxUCB, Rising Bandits, and Max-Median algorithms often choose the optimal arm. However, for Max-Median, the number of pulls of the optimal arm either very close to to T, leading non-robust performance, which has already been observed in Baudry et al. [2022] experiments. UCB and ER-UCB-S perform almost similarly.
TabRepo [SS]
200
2001
Optimal Arm Pull Count
1.0
Number pulls
150
100
50
MaxUCB
Quantik Bayes UCB
BR-UGR-S
Heing Bandi
QuMan=S00 SDA
MocMMelion
UCB
0
1
2
3 arms
4
5
Figure E.1: (Right) The number of all arm pulls, with each bar graph showing the average and the error bars indicating additional statistical information. (Left) The number of best arm pulls for different bandit algorithms.
TabRepoRaw/SMAC
200
2001
Optimal Arm Pull Count
150
Number of pulls
150
200
100
50
MaxUCB
Quantike Bayes UCB
ERAUCB-S
Roiing Bandis
QoMav-SDS SDA
Max Median
UCB
0
1
2
3
arms
Figure E.2: (Right) The number of all arm pulls, with each bar graph showing the average and the error bars indicating additional statistical information. (Left) The number of best arm pulls for different bandit algorithms.
47

---

YaHPOGym(SMAC
200
Optmal Arm Pull Count
150
Number of pulls
150
100
100
60
50
MaxUCD
Quantile Bays UCB
Reing Bandit
QoMaasSDD SDA
MaxMadiaa
2
3
arms
Figure E.3: (Right) The number of all pulls, with each bar graph showing the average and the error bars indicating additional statistical information. (Left) The number best arm pulls for different bandit algorithms.
(aanfflllingHEBOO
250
250
200
Optimal Arm Pull Count
200
Number of pulls
150
150
100
100
50
MaxUCa
Quantile Bays VCB
Bandie
QoMax-SD SDA
Max Modion
2
arms
Figure E.4: (Right) The number of all pulls, with each bar graph showing the average and the error bars indicating additional statistical information. (Left) The number best arm pulls for different bandit algorithms.
48

---

E.2 From theory to practice
To validate theorem against practical outcomes, we applied our algorithm all benchmarks and plotted the number of pulls for each arm, denoted as "Real Experiment." Additionally, we computed the upper bound the number of pulls by using the empirical values of L1 and U, and A, Notably, we report the first term of Equation 22 since the second term is nearly constant across all arms according calculation. The results demonstrate that although the empirical pull counts much less than the theoretical bounds of Equation 22, both follow a similar decreasing pattern as the rank of suboptimality increases.
TabRepo[RS]
TabRepoRaw (SMA]
150
Number of pulls
Number of pulls
50
0
2
3
4
6
0
2
3
4
6
arms
arms
YaHPOGym [MMC]]
BachufflingHHEBBOO
200
Number pulls
Number pulls
100
100
Real Experiment
Theory
arms
arms
Figure E.5: The number of pulls for each arm in our algorithm, labeled as "Real Experiment" and the theoretical values of this number
E.3 Addressing Non-stationary Rewards
To handle non-stationary rewards, pull each arm C times without observing the rewards before running MaxUCB. This "burn-in" allows the Markov Chain to reach equilibrium, especially from a poor starting point. Algorithm E.1 shows the adapted version of our algorithm. Therefore, empirically, this allows MaxUCB to operate after a fixed exploration phase of all arms until the reward distribution is stationary.
We run Algorithm E. with different parameters of C E (5, 6, 7,8) using up to 48 iterations corresponding to almost 25% of the total budget. Figure E.6 shows normalized loss per task where columns are sorted by the maximum change of the mean the reward distributions the optimal arm computed every 10 HPO iterations (as an indicator of non-stationarity; shown at the top panel in Figure E.6. Figure E.7 shows the average ranking and normalized loss over time for different values of the hyperparameter C.
The initial burn-in improves final performance for the few tasks where we observe a high shift (right part of Figure E.6) while the initial performance is worse across all tasks (as shown in Figure E.7). However, the results are not sensitive to the exact value of C. Overall, this naive solution can improve performance for some tasks at the cost of not using potentially valuable information obtained from initial exploration. Thus optimally addressing non-stationary rewards could be a promising direction for future work.
49

---

Algorithm E.1 MaxUCB-Burnin
Require: o(exploration parameter), C (bur-in rounds). T(rime horizon), R (arms)
Burn-in phase
1: for j S. C, for each arm i & K do
2:
3: end for
Initial phase
4: for cach arm & K do
5:
6: set vı, <- 1. observe reward 1
7: end
phase
8: for (CK + K 11 7o do
9:
for each arm
do
10:
Update policy Us max (f2,), ... Tr,n,) + (mlog(t) ya end for Select amm 1 arg max U,
11:
ASK
13:
U. 4- nie + Observe reward 1Ig.0
15:
end
Maximum shift of mean
1.0
0.5
0.5
MaxUCB
MaxUCB Burn 5)
0.1
MaxUCCB-Bunniing 66))
MaxUCB Burn-in(C-TTy T
MaxUCB B)
Riing Bandit
SMAC
0.1
Random Search-
0.0
Oracle Arm-
Tasks YaHPOGym|5MMC
Figure E.6: Heat map shows normalized loss per task, sorted by the distribution shift.
10
MaxUCB
8-
Normalized loss
MarUCB Bursin(C-5)
ManUCB-BursinCCCa
Ranking
MarUCB- BarUCB-BurniinCCam
Raig Bardi
0.1
SMiC
0
100 Iteration
200
100 Iteration
200
Figure E.7: Average rank and normalized loss of algorithms YaHPOGym benchmark, lower is better.
50

---

E.4 Toy examples from the extreme bandit's literature
In this section, we provide additional results on commonly used benchmark functions used in the extreme bandit literature. Concretely, we use similar setup to [Baudry et al., 2022] and report the following four tasks:
1. K = 5 Pareto distributions with tail parameters A [2.1, 2.3, 1.3, 1.1, 1.9. Results are shown Figure E.8.
2. K Exponential arms with survival function Gạ(x) ~ with parameters λς [2.1, 1.9, 1.3, 1.1, 2.9, 1.5, 2.2, 2.6, 1.4]. Results are shown in Figure E.9.
3. = 20 Gaussian arms, with same mean μ4 = 1, vk, and different variances
2.29, 2.29, 1.79, 2.67, 1.70, 1.36, 1.90, 2.19, 0.80, 0.12, 1.65, 1.19, 1.88, 0.89,...33.. 3.35, 1.5, 2.22, 3.03, 1.08, 0.48). The dominant arm has a standard deviation of 3.35. Results are shown in Figure 10
4. (our toy example)
5 power distributions with domain parameter [3, 4, 5, 4] and shape parameter [1.01, 1.01, 1.01, 1.1, 1]. Results are shown in Figure 1.
For each task, we run (50, 100, 200, 500, 1000, 2000}. We show the CDF of the rewards for cach arm. the number of times the optimal arm was pulled, and the proxy empirical regret. Notably, the proxy empirical regret introduced by Baudry et al. [2022] overcome the issue of high variance in the maximum values of distributions.
1000 independent repetitions for six time horizons T
1.0
0.8
Suurvival function
Arm
Arm
0.4
Arm
Arm
0.0
100
'000
Reward
101
1.0-
MaxUCB
Procy Empinial Regret
QoMaxe ETC
Best Arm gulls rate
0.8
QoMax-SDA
MaxMedian
0.6
ExtremeETC
ExtremeHHunter
0.4-
Breshald-Ascont
0.2
MaxSearch- Shaserch-Gaussinn
500
1000
2000
50
100
200
1000
2000
lteration
Iteration
Figure E.8: Experiment 1: (Top) Survival function of distribution of each arm (left) Number of pulls
of the optimal arm. (Right) Proxy Empirical Regret
51

---

1.0
Arm 1
Arm 2
Sauvival function
Arm
Arm 4
0.6
Arm 5
Arm 6
0.4
Arm
Arm 8
Arm 9
Arm
0.04
10
Reward
MaxUCB
Best Arm pulls rate
0.8
Prony Empiriaal Regeet
QoMaxe ETC
QuMax-DA
0.5
0.4
MaxMedian
ExtremeETC
0.4-
ExtremeHHnnter
11:2
Aweshald-Ascom
0.2
MaxSearch-SubGrnee
MaxSearch- Gaaschh--aasaann
500
1000
2000
50
100
200
1000
2000
lteration
Iteration
Figure E.9: Experiment 2: (Top) Survival function of distribution of each arm (left) Number of pulls of the optimal arm. (Right) Proxy Empirical Regret
1.0
Arm 11
Arm 12
Saurvial function
0.8
Arm
Arm
0.6
Arm 15
Arm 16
0.4
Arm
Arm
Arm 19
Arm 20
0.0
7.5
-2.5
0.0
7.5
Reward
0.8
MaxUCB
0.5
Empirical Regret
QoMax ETC
Best Ann pulls rate
0.6
QaMax-SDA
MaxMedian
ExtremeETC
ExtremeHHunter
0.2
Threshold-Accont
0.2
0.1
MaxSearch-Gausee
0.0
500
1000
2000
50
100
200
500
1000
2000
Iteration
Itoration
Figure E. 10: Experiment 3: (Top) Survival function distribution of some arms (left) Number of pulls of the optimal arm. (Right) Proxy Empirical Regret
52

---

1.0
Suurvival function
Arm
Arm
Arm
0.4
Arm
Arm
0.04
0.4
0.8
Reward
1.08
MaxUCCB
Procy Empirical Regret
ETC
Bes Am polls rate
0.8
QoMax-SDA
MaxMadian
0.5-
ExtremeETC
ExtremeHunter
0.4
Threshold-Aseen
0.2
ManSearch-SubbGausiie
MaxSearch-Gaussin
100
200
1000
2000
50
100
200
500
1000
2000
Iteration
Iteration
Figure E.11: Experiment 4: (Top) Survival function of distribution each arm (left) Number of pulls of the optimal arm. (Right) Proxy Empirical Regret
E.5 Supernet selection in Few-Shot Neural Architecture Search
In one-shot NAS, single supernet approximates all architectures. However, this estimation could be inaccurate. To address this, few-shot NAS splits the supernet into smaller sub-supernets [Hu al., 2022, Ly-Manson al., 2024]. To further improve performance, [Hu al., 2022] introduced supernet selection, which identifies the most promising sub-supernet and its optimal architecture using techniques such as Successive Halving. We aim identify the best-performing architecture among several subspaces, each corresponding to sub-supernet. This problem is analogous to the MKB problems, where each arm represents a sub-supernet.
Dataset Preparation. We use data provided in [Ly-Manson et al., 2024] for three benchmark datasets: CIFAR-1O, CIFAR-IO0. and ImageNet
Each dataset's search space is split using 10 different metrics. The splitting follows a binary tree structure with a depth of 3, where operations are divided into groups each branch. This process results in 8 sub-supernets per metric. Consequently, for each dataset, we have one full search space and 8 sub-search spaces.
Each combination of dataset and splitting metric is treated tasks (3 datasets x 10 metrics), each with arms. Following the setup of [Ly-Manson et al., 2024], randomly sample 600 architectures from both the full search space and each sub-search space. This process is repeated 32 times using different random seeds to ensure variability and robustness in the results.
separate task, yielding total of 30
Analyzing the reward distribution. Figure 1. illustrates the empirical survival functions of rewards and sub-optimality gaps for the benchmark. As shown, the distribution shape is similar to that of HPO tasks: both are bounded and left-skewed. However, the sub-optimality gap is considerably smaller than HPO tasks, suggesting that identifying the optimal arm is more challenging and may require additional iterations, In Figure 13, we show values of and U from Lemma 3.3 for this benchmark.
Performance Analysis. Figure E.14 presents the average ranking and normalized loss of various bandit algorithms in this benchmark. As shown, Successive Halving, Max-Median, and ER-UCB-S perform well with a small time budget fail to explore sufficiently to identify the optimal arm. Rising Bundits, fixed-confidence best-arm identification method, struggles to find the optimal arm. contrast, MaxUCB outperforms all other baselines, demonstrating better performance when searching the entire search space with higher budget.
53

---

Supernet
Sunvoal function
0.10
0.5
0.5
0.00
0.00
11.26
0.50
01.75
1.30
0,00
1120
0.50
11.76
1310
Reward
Reward
Sub Lib-optimal am
Optinal
2nd
3rd 4th
5th
6ch 7th
Worst am
Figure E. (Left) The average empirical survival function of the reward (observed performances) per arm ranked per dataset. We divided the reward sequence into five segments over the budget to show the distribution change over time. Thin lines correspond to the survival function of different
segments, visualizing the change over time. (Middle) The average ECDF per dataset for the best and worst arm with thin lines corresponding to individual datasets. (Right) The sub-optimality gap A,
Supernet
Optimal arm
2nd arm
3rd arm
4th arm
5th arm
6th am
7th am
Worst am
100
frequency
7.5
5.0
0.1 1 10 Values for
0.1 1 10
0.1 10
0.1 10
0.1 10
0.1 10
0.1 10
0.1 1 10
Values for L
Values for L
Values for L
Values for L
Values for
Values for
Values for
Frequency
6.
9.
8.01
100 0.01 1
100 0.01
100 0.01
100
0.01
100
0.01
100
0.01
100
0.01
100
Values U
Values for U
Values for
Values for
Values for
Values for
Values for
Values for
Average
(per datasot)
Li mim (60
Ui max
Figure E. Arms ordered by sub-optimality gap. (Top) Thin orange lines represent G(b-c) while the blue and red points correspond to and U for our empirical reward distributions (see Lemma 3.3 for details). (Middle) Histogram of values for L. (Bottom) Histogram of values for U.
54

---

MaxUCB
Normalized loss
Quantil Bayes UCB
Ranking
6
Raing Bandi
QoMax
Max Med
0.1:
UCB
Random Segech
2
Oracle Arm
200
400
600
0
200
400
600
Iteration
Iteration
Figure 1.14 Average rank and normalized loss of algorithms on Supernet Selection benchmark.
lower is better.
55


Reviews:
[{"review_id": "DoP4gVGxiK", "reviewer": "Reviewer_7Zgt", "summary": "This paper addresses the combined algorithm selection and hyperparameter optimization (CASH) problem using an extreme bandit framework with novel assumptions derived from empirical observations on AutoML benchmarks. Based on these assumptions, the authors propose a new extreme bandit algorithm, MaxUCB. The paper provides theoretical regret guarantees for the algorithm and offers guidance on selecting the exploration parameter alpha. Experimental results demonstrate state-of-the-art performance on several benchmark AutoML tasks.", "questions": "a)\tThe discussion in the introduction (lines 25–39) is somewhat confusing, especially the distinction between \"combined algorithm\" and \"individual search-based algorithm,\" along with their respective pros and cons.\n\nb)\tWhat exactly is the difference between Eq. (1) and Eq. (2)? Are the optimization problems themselves different?\n\nc)\tIs the proposed algorithm completely agnostic to the inner HPO method?\n\nd)\tTypo in line 78: \"trades off trade off\" \n\ne)\tRegarding the earlier point on assumptions, while I appreciate the discussion in Section 3, my impression is that the effectiveness of algorithms for CASH will heavily depend on the task or data characteristics, as CASH is such a broad problem. What are the characteristics of the tasks and datasets used in the empirical analysis in Section 3? How do your observations vary across tasks or data types? More detailed analysis is needed here.\n\nf)\tSimilarly, the authors mention that the choice of alpha may depend on the dataset characteristics. Can you elaborate on this? Is there any analysis or guidance on choosing alpha based on the task or data types?\n\ng)\tIn Assumption 3.2, the random variable is assumed to be i.i.d., but line 86 suggests that the reward process is not i.i.d. Could you clarify?\n\nh)\tTypo in line 207: \"property the maxima\" \n\ni)\tIn Section 5, I assume that the “two-level approach” and “single-level” correspond to “individual” and “combined” methods from the Introduction. Please unify the terminology throughout to avoid confusion, or explicitly define these terms.\n\nj)\tTypo in line 268: \"study study\"", "limitations": "Yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 2, "strengths_and_weaknesses": "2.\tStrength\na)\tThe paper is clearly written and well-organized.\nb)\tIt offers solid theoretical and algorithmic contributions.\nc)\tThe limitations of the proposed method are explicitly discussed, along with appropriate cautions.\n\nWeakness\na)\tA more in-depth discussion of the assumptions based on empirical observations is needed. Since the algorithmic contribution relies heavily on these new assumptions and the resulting modification, further analysis would strengthen the work. Specific concerns are detailed in the Questions section below.\nb)\tFrom a purely algorithmic perspective, the originality of the proposed algorithm is somewhat unclear. It may be a minor modification of existing methods, though I acknowledge I am not an expert in AutoML or related bandit algorithms.", "was_revised": true, "final_justification": "I had rated this submission at accept. The authors provided some further clarifications to my questions, and as such at this point, I am leaving my score at accept.", "rebuttal": "Thanks a lot for the detailed review and acknowledging our contributions. We will fix all minor comments in a revised version and address your questions in the following.\n\n---\n### “From a purely algorithmic perspective, the originality of the proposed algorithm is somewhat unclear.”\n\nThe UCB principle is central to dealing with decision-making under uncertainty. We agree it is not original in this sense. However, as Reviewer Vu3f noted, the regret definition in Eq. (4), which corresponds to the Max K-armed Bandit problem, differs from the common regret used in classical bandit settings. The main challenge lies in getting the details right in the modelling assumptions. Our main contribution, and what makes the method work ultimately, is to identify a semi-parametric model of the distribution of the maxima we aim to optimize. We discuss this in more detail in our response to Reviewer PkJH.\n\n\n---\n### “a) … distinction between \"combined algorithm\" and \"individual search-based algorithm”\n\nWith the “combined search” approach, we refer to an optimization method that searches the entire space of all K models’ hyperparameters, while an “individual search-based algorithm” only searches hyperparameters for a single model (and without budget allocation, needs to be conducted K times). The main challenge for “combined search” is efficiently searching **the entire high-dimensional and heterogeneous combination of K search spaces**. The main challenge for “individual search-based algorithms” is to **allocate the budget between the K runs** by an additional optimizer.\n\nAs you correctly pointed out, the “two-level” and “single-level” terminology corresponds to the “individual” (i.e., decomposed CASH) and “combined search” approaches introduced earlier. We agree that terminology might be confusing, but we wanted to highlight the combined term in CASH; we will revise and unify the terminology.\n\n---\n### “b) difference between Eq. (1) and Eq. (2)?...”\nEq.(1) and Eq.(2) are equivalent and describe the same optimization problem (and thus also share the same solution): finding the best-performing configuration of a model. In Eq. (2), we highlight the structure of CASH problems and that we can decompose the problem into a bi-level optimization problem.\n\n---\n### “c) agnostic to the inner HPO method ...”\nYes, absolutely. It’s a strength of our method that it would also allow using a different HPO method (e.g., random search or Bayesian optimization) per model class.\n\n\n---\n### “e) … the characteristics of the tasks and datasets used in the empirical analysis in Section 3 ...”\n\nYes, we agree. Tables D.1, D.2, and D.3 provide detailed information about the tasks, and Figures D.7 and D.8 report performance per task.  Each task corresponds to a different dataset. For YaHPOgym, the task is classification, with accuracy as the evaluation metric.  \n\nFor Reshuffling, the task is binary classification with AUC as the metric. In TabRepo and TabRepoRaw, the tasks include regression, multiclass classification, and binary classification, with RMSE, log loss, and AUC used as the respective metrics (we also discuss this in our response to reviewer PkJH)\n\nIn general, linking MaxUCB's performance to task characteristics or using meta-learning to exploit similarities across tasks would be promising future directions. However, here, we first focused on designing and analysing a principled algorithm that works empirically well on average.\n\n---\n### “f) choice of alpha?”\n\nCorollary 4.3 theoretically gives the optimal value for $\\alpha$ when characteristics of the datasets and the budget are known. We find that a default of $\\alpha=0.5$ works empirically well (see Appendix D.4). Indeed, we can not provide a general rule for choosing the optimal alpha as it is a problem-dependent quantity. Similar to our answer to e), meta-learning the optimal alpha based on task characteristics could be an empirical approach to mitigate this issue.\n\n---\n### “g)  In Assumption 3.2, the random variable is assumed to be i.i.d., but line 86 suggests that the reward process is not i.i.d. Could you clarify?”\nYou’re correct. In Assumption 3.2, we assume that our random variable is i.i.d. In practice, our rewards are not strictly i.i.d. (unless we use random search), and we know that this assumption might not hold in practice (as stated in line 86). However, our data analysis shows that the distribution shift during HPO is small in most cases (line 146), and our empirical results confirm that we can model this process reasonably well to perform well in practice. **This simplifying assumption is key to designing a simple and effective algorithm.**"}, {"review_id": "T0aSmHcnka", "reviewer": "Reviewer_Vu3f", "summary": "This paper studies a challenging resource allocation problem in AutoML, i.e., Combined Algorithm Selection and Hyperparameter optimization (CASH). The authors propose MaxUCB, a max k-armed bandit method to trade off exploring different model classes and conducting hyperparameter optimization. MaxUCB is specifically designed for the light-tailed and bounded reward distributions arising in this setting and, thus, provides an efficient alternative compared to classic max k-armed bandit methods assuming heavy-tailed reward distributions. The authors theoretically and empirically evaluate this method on four standard AutoML benchmarks and demonstrate superior performance over prior approaches. They also release their code and data used in experiments.", "questions": "Please see the weaknesses above.", "limitations": "Please see the weaknesses above.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1.\tThis paper proposes a state-of-the-art method for the CASH problem based on an extreme bandit algorithm MaxUCB. The authors provide regret bounds for MaxUCB and also justify their choice of exploration bonus for the type of distributions relevant to the CASH problem.\n2.\tThe authors demonstrate the performance of the proposed method on four benchmarks, and corroborate that the proposed algorithm achieves good empirical performance on CASH.\n3.\tThe authors release their code and data, which guarantees reproductivity.\n\nWeaknesses:\n\n1.\tThe regret definition in Eq. (4) is unusual in the bandit literature. The authors should discuss more on the motivation of this regret definition, combining with realistic hyperparameter optimization applications. Why should we consider the maximum over $t \\leq T$?\n2.\tIn hyperparameter optimization applications, an arm corresponds to a hyperparameter choice/setup. Then, in practical applications, the number of possible hyperparameter choices is large, which is often combinatorial with respect to the number of hyperparameters. Can the proposed method and theoretical guarantees be applied to the scenario when the number of possible hyperparameter choices (arms) is large?\n3.\tI feel that the proposed method and theoretical guarantees rely too much on the properties of the reward distributions in hyperparameter optimization tasks (what the authors discussed in the second paragraph of Section 3). But these properties may not always hold in realistic hyperparameter optimization applications.\n4.\tTheoretically, the proposed algorithm does not know the optimal choice of exploration parameter $\\alpha$. So the regret bound in Corollary 4.3 may not be achieved by the proposed algorithm.\n5.\tThe writing of this paper needs to be improved. Some definitions are missing, which makes some parts of this paper hard to understand. For example, what is $L_{i^*}$ in Theorem 4.2? What is two-level and single-level approaches for hyperparameter optimization mentioned in Section 5?", "was_revised": true, "final_justification": "After reading the rebuttal and other reviewers' comments, I tend to weak accept.", "rebuttal": "Thanks a lot for the detailed review and the raised points. \n\n---\n### “1. The regret definition in Eq. (4) is unusual in the bandit literature.”\nWe very much appreciate this question and are happy to clarify. Indeed, our regret definition (known as extreme regret [1]) is unusual in the general bandit literature, but it is central in HPO literature.\n\nJamieson et al. (2015) [2] already state that max-value objectives should be the right ones for HPO, but rightfully state that they are “less well behaved”. Further, Nishihara et al. (2019) [3] stated that the **Max K-armed Bandit (Extreme Bandits) should be the valid framework for HPO** but also proved that without appropriate assumptions, it may be infeasible (lower bounds). More recently, Hu et al. (2021) [4] mentioned that the classic UCB algorithm is inappropriate for the CASH problem because of the regret definition. These very challenges motivated our study. A similar discussion can be found in lines 40-50, but we will extend it.\n\n---\n### “2. Can the proposed method and theoretical guarantees be applied to the scenario when the number of possible hyperparameter choices (arms) is large?”\nWe apologize, but we are confused by this question. To clarify: In our setup, an arm is an ML model class, and “pulling an arm” corresponds to running HPO on the chosen  ML model class (see Figure 1 and lines 82-84). So, arms are **not** hyperparameter choices.\n\nMaxUCB would not be directly applicable to this different setup where an arm corresponds to a hyperparameter configuration (especially since our regret bound in Corollary 4.3 grows linearly with the number of arms K). Other Bandit methods, like Hyperband, are designed and known to work well for this different setting with only one model class.\n\n---\n### “3. But these properties may not always hold in realistic hyperparameter optimization applications.”\n\nOur data analysis covers several benchmarks, with 300+ datasets representing realistic hyperparameter optimization tasks (see response to Reviewer PkJH). Indeed, different problems may exist, but one important contribution of our paper is to consider the broader set of assumptions for the most realistic space of HPO/CASH problems. \n\nWe derived theoretical guarantees under quite general semi-parametric assumptions, as stated in Theorem 4.2 and the accompanying discussion. Our assumptions allow for a wide range of reward distributions (we discuss typical distribution types in Appendix C.2). If a problem would have a very small L constant (in contrast to all the CASH problems we studied), then the performance of MaxUCB would be worse, as predicted by our theory. \n\n---\n### “4...So the regret bound in Corollary 4.3 may not be achieved by the proposed algorithm.”\n\nYes, we completely agree. The result of Corollary 4.3 shows how to choose optimal $\\alpha$ when these values are known or can be estimated in advance via meta-learning. In the discussion, we also mention that adapting $\\alpha$ by estimating these parameters on the fly is possible.\n\n---\n### “5..The writing of this paper needs to be improved.”\nThanks a lot for pointing this out. We will unify terminology in the revision:\n\n* $L_i$ refers to the value of $L$ from Lemma 3.3 for arm $i$, and $i^*$ denotes the optimal arm (see lines 224-225). \n* We refer to “combined search” as a single-level approach and with “two-level approach” to Bandit-based methods that address the bi-level optimization problem in Eq(2). See also our response to Reviewer 7Zgt.\n\n---\n###  References\n1) Carpentier, Alexandra, and Michal Valko. \"Extreme bandits.\" Advances in Neural Information Processing Systems 27 (2014).\n2) Jamieson, Kevin, and Ameet Talwalkar. \"Non-stochastic best arm identification and hyperparameter optimization.\" Artificial intelligence and statistics. PMLR, 2016.\n3) Nishihara, Robert, David Lopez-Paz, and Léon Bottou. \"No regret bound for extreme bandits.\" Artificial Intelligence and Statistics. PMLR, 2016.\n4) Hu, Yi-Qi, et al. \"Cascaded algorithm selection with extreme-region UCB bandit.\" IEEE Transactions on Pattern Analysis and Machine Intelligence 44.10 (2021): 6782-6794."}, {"review_id": "b4oq4FPRqa", "reviewer": "Reviewer_aB58", "summary": "This paper tackles the Combined Algorithm Selection and Hyperparameter Optimization (CASH) problem, a core challenge in Automated Machine Learning (AutoML). The authors propose MaxUCB, a novel max k-armed bandit algorithm that efficiently balances the exploration of model classes with hyperparameter optimization (HPO). A key insight of the paper is a thorough empirical analysis of reward distributions from real-world HPO tasks, showing that these are typically bounded, short-tailed, left-skewed, and nearly stationary—in contrast to assumptions underlying classical max bandit methods. Leveraging this, the authors design MaxUCB with a distribution-aware exploration bonus, supported by theoretical regret analysis and empirical validation on standard AutoML benchmarks. The proposed approach achieves strong performance improvements over existing methods.", "questions": "Please discuss or comment on the above weakness parts.", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n\n- **Addresses a Timely and Practical Problem:** The paper focuses on the CASH problem, which is fundamental to making ML more accessible by automating the joint selection of algorithms and hyperparameters. The authors clearly articulate the **inefficiencies of traditional HPO** in high-dimensional, hierarchical spaces and the limitations of naively treating each model class independently.\n- **Data-Driven Algorithm Design:** A standout contribution is the **empirical characterization of reward distributions** in HPO tasks. The authors show that these are **light-tailed, bounded, and nearly stationary**, and leverage these properties to **motivate a new exploration strategy**. This empirical grounding provides a solid justification for deviating from the classical heavy-tailed assumptions in prior work and **addresses a gap in understanding realistic bandit reward distributions in AutoML**.\n- **Strong Theoretical and Algorithmic Contributions:** The paper provides a well-structured theoretical analysis, including a **new sub-optimality gap definition** and a **distributional assumption (Assumption 3.2)** that is empirically supported. Lemma 3.3 further refines the distributional characterization near the maximum. The derived **regret bound (Proposition 4.1)** and **suboptimal pull bound (Theorem 4.2)** are tightly aligned with empirical observations, and the use of a **squared exploration bonus** $(\\alpha \\log(t)/n)^2$ is well-justified.\n- **Empirical Performance:** MaxUCB shows **consistent gains in both anytime and final performance** across four well-established AutoML benchmarks (TabRepo, TabRepoRaw, YaHPOGym, and Reshuffling). The **two-level optimization framework using MaxUCB** significantly outperforms joint-space HPO methods, especially under tight iteration budgets.\n\n---\n\n**Weaknesses and Suggestions for Improvement:**\n\n- **Assumptions on Reward Distributions and Stationarity:** While the assumptions of **boundedness and light-tailedness** are well-supported by data, the **near-stationarity assumption** may be restrictive. The paper notes that stationarity might not hold during early iterations of HPO, suggesting the need for a **burn-in phase**. Appendix E.3 explores this empirically, but a more **principled treatment of non-stationarity**, either algorithmically or theoretically, would enhance robustness and broaden applicability.\n- **Lack of Lower Bound Analysis:** The paper does not provide a **lower bound on regret**, which leaves open the question of **whether MaxUCB is minimax optimal** in the bounded, light-tailed setting. Including such a result, or at least a discussion of potential optimality gaps, would strengthen the theoretical contributions.", "was_revised": true, "final_justification": "I believe this paper is solid and is valuable for advancing the field of AutoML, so I vote for acceptance for the current paper.", "rebuttal": "Thanks a lot for the detailed positive assessment of our work. We are happy to comment on the pointed-out suggestions for improvement.\n\n---\n### “Regarding the near-stationarity assumption,”\nAs noted in our response to Reviewer 7Zgt, we acknowledge that this simplifying assumption may not strictly hold, but it provides a solid foundation for developing a strong algorithm. In classic bandits, non-stationarity is typically addressed by combining algorithms with i.i.d. assumptions with techniques such as sliding windows, discounting, or change-point detection, which have shown promising results in various applications. Since the max k-armed bandit has a different regret definition,  it may require specialized techniques. Designing such techniques is a promising research direction.\n\n\n---\n### “The paper does not provide a lower bound on regret,”\nThanks a lot for raising this point. The notion of optimality for max K-armed bandits is unclear, as Nishihara et al. (2016) [1] pointed out. Namely, as opposed to classical bandit problems, **the best arm, and thus, the optimal policy, depends on the time horizon, which is here our compute budget.** They argue that the existence of no-regret algorithms fully depends on the distributional assumptions and show impossibility results in the Bernoulli case. A notion of optimality, if it exists, would have to be fully distribution-dependent, but for which distribution family? Our study focuses on CASH and proposes a useful set of assumptions on useful distributions, but we do not claim, nor aim to be optimal, since this notion remains elusive for this problem. Bounded extreme bandits are not extensively studied, potentially because use cases were lacking, but our work may open avenues for more fundamental research questions. We will clarify it in the paper.\n\n---\n###  References\n1) Nishihara et al.: \"No regret bound for extreme bandits.\" Artificial Intelligence and Statistics. PMLR, 2016."}, {"review_id": "FjpCcHWucQ", "reviewer": "Reviewer_PkJH", "summary": "This paper proposes MaxUCB, a new max k-armed bandit algorithm designed to address CASH problem in AutoML. The authors analyze empirical performance distributions from AutoML benchmarks and find them to be left-skewed and short-tailed. Based on this observation, they derive a regret bound and develop MaxUCB, which uses a tailored exploration bonus that accounts for the bounded distribution shape.\n\nThe method is evaluated on AutoML benchmarks and shows superior anytime and final performance compared to several state-of-the-art baselines, including other bandit-based algorithms and combined search approaches. The paper also provides an extensive theoretical analysis and discusses the sensitivity of the algorithm’s hyperparameter $\\alpha$.", "questions": "Could the authors clarify how the tabular datasets used in the empirical distribution analysis were selected? For example, were these chosen to be representative of a specific class of AutoML problems, or were they selected based on convenience or availability?", "limitations": "While the paper frames MaxUCB as a novel contribution, the core idea using a UCB-style bandit strategy with an exploration bonus adapted to bounded reward distributions can be seen as a relatively straightforward extension of standard UCB principles.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 4, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n\nThe paper is logically organized, with a clear progression from problem formulation to method design, theoretical results, and empirical evaluation. The authors do a good job contextualizing prior work and explaining.\n\n\nThe combination of (i) empirical analysis of reward distributions, (ii) a tailored regret bound under bounded, left-skewed distributions, and (iii) the design of MaxUCB is a meaningful over prior work.\n\n\nThe paper includes thorough empirical comparisons across multiple benchmarks, careful analysis of the $\\alpha$ parameter, and ablation against several strong baselines.\n\n\nWeaknesses\n\n\nWhile the authors analyze reward distributions to motivate their assumptions, there is no clearly defined methodology for how the tabular datasets were selected, nor a principled justification that the chosen benchmarks are representative of the broader diversity of AutoML tasks. This raises questions about whether the conclusions about bounded, short-tailed distributions hold more generally.", "was_revised": false, "final_justification": "", "rebuttal": "Thanks a lot for the detailed review and the raised points. We particularly appreciate your highlighting the quality of explanation and clarity. \n\n---\n### “Could the authors clarify how the tabular datasets used in the empirical distribution analysis were selected? For example, were these chosen to be representative of a specific class of AutoML problems, or were they selected based on convenience or availability?”\nWe used several well-established and widely used benchmark sets that were developed to compare HPO methods. Each benchmark contained different datasets, tasks, and search spaces, to ensure our empirical distribution analysis was not limited to a single source or problem type.\n\n* For example, **TabRepo** is one of the largest tabular benchmarks, including **200 classification and regression datasets** and evaluating over 1,310 models and configurations. A full evaluation of TabRepo could require up to 4,066,576 CPU hours.\n\n* For **TabRepoRaw**, where we ran Bayesian optimization directly over TabRepo’s search space, we selected the D244_F3_C1530_30 subset due to cost limitations. This subset includes **30 datasets** that were specifically chosen by the TabRepo authors to represent a diverse yet computationally feasible set of tasks. We spent over 10,000 CPU hours to collect this benchmark.\n\n* **YaHPOgym** is a well-known and widely used surrogate benchmark for HPO in the tabular domain, containing 103 datasets from the OpenML collection.\n\n* We also added the **Reshuffling** benchmark which includes 10 datasets with and HEBO as the HPO method. We included this task to diversify the HPO methods in our study.\n\n* Furthermore, in Appendix E.5, we used Supernet selection in the Few-Shot Neural Architecture Search benchmark (containing CIFAR-10, CIFAR-100, and ImageNet16-120 datasets) to show that our analysis and algorithm can work beyond CASH tasks. \n\n---\n### “While the paper frames MaxUCB as a novel contribution, the core idea using a UCB-style bandit strategy with an exploration bonus adapted to bounded reward distributions can be seen as a relatively straightforward extension of standard UCB principles.”\n\nThe main novelty in MaxUCB is a distribution-adapted exploration bonus (which is a distinct approach compared to standard UCB literature). Our main contribution, and what makes the method work ultimately, is to identify a semi-parametric modelling of the distribution of the maxima we aim to optimize.\n\nThe main difficulty is getting the details right in the modelling assumptions. There may be alternative, smarter, and more complex algorithmic designs for this problem, but **isn’t it remarkable that a simple algorithm achieves such good empirical performance on such a widely studied problem?**"}]

Author rebuttal:

Meta-review: This work tackles the challenge of algorithm and hyperparameter selection in automated machine learning. The main contribution is an algorithm MaxUCB that can balance exploration of model classes with hyper-parameter optimization. The authors conduct a thorough evaluation of their experimental methods and derive regret bounds for their setting. The reviewers agreed that although the technical content behind the MaxUCB algorithm is not extremely technically challenge or novel, this work meets the bar for presentation at Neurips.
Decision: Accept (poster)