Year: 2021

Abstract:
Hyperparameter optimization (HPO) is generally treated as a bi-level optimization problem that involves fitting a (probabilistic) surrogate model to a set of observed hyperparameter responses, e.g. validation loss, and consequently maximizing an acquisition function using a surrogate model to identify good hyperparameter candidates for evaluation. The choice of a surrogate and/or acquisition function can be further improved via knowledge transfer across related tasks. In this paper, we propose a novel transfer learning approach, defined within the context of modelbased reinforcement learning, where we represent the surrogate as an ensemble of probabilistic models that allows trajectory sampling. We further propose a new variant of model predictive control which employs a simple look-ahead strategy as a policy that optimizes a sequence of actions, representing hyperparameter candidates to expedite HPO. Our experiments on three meta-datasets comparing to state-of-the-art HPO algorithms including a model-free reinforcement learning approach show that the proposed method can outperform all baselines by exploiting a simple planning-based policy.

heading: 1 INTRODUCTION
text: Hyperparameter optimization (HPO) is a ubiquitous problem within the research community and an integral aspect of tuning machine learning algorithms to ensure generalization beyond the training data. HPO is often posed as a sequential decision-making process, however, it can be seen as a special use-case of model-based reinforcement learning (MbRL) (Sutton, 1991a; Henaff et al., 2017) developed under the guise of some idiosyncratic terms.
In MbRL the objective is to train a transition model to approximate an underlying transition function via interactions with an environment governed by some policy, e.g. random shooting (Nagabandi et al., 2018), to improve sample efficiency and learn from more useful interactions whereby the learned models are used as a simulator for sampling trajectories. An agent navigates the simulated environment to optimize a pre-defined reward function, while the transition model remains unchanged. Conventionally in HPO, a surrogate model is trained to estimate some black-box function, e.g. validation loss of a machine learning algorithm under investigation (Rasmussen, 2003; Snoek et al., 2015b; Springenberg et al., 2016). An acquisition function (Wilson et al., 2017b) interacts with the surrogate model to propose potential hyperparameters that optimize the black-box response, viewed as a reward function. Effectively, the surrogate model is the only unknown component for a transition model, that prevents HPO from being framed fully as MbRL problem.
In this paper, we present a novel formulation for HPO defined within the context of MbRL. Namely, we learn an ensemble of probabilistic neural network models (Lakshminarayanan et al., 2017) and show that using model predictive control (MPC) (Kamthe & Deisenroth, 2018) and a novel lookahead variant to navigate the simulated black-box environment, we can outperform conventional Bayesian optimization techniques with heuristic acquisition functions in both transfer and nontransfer learning settings. Thus, we elaborate on the importance of explicit planning in HPO that has been largely overlooked by the community. We also formally define HPO as a Markov decision process (MDP) with a simple, yet novel, state representation as the set of previously evaluated hyperparameters and their corresponding responses.
We argue that with a clearly defined transition model, we can replace the acquisition function with a simple policy that maximizes the reward across the simulated trajectories, and achieve better results
through proper planning, as shown in Figure 1. LookAhead MPC-5 is our look-ahead strategy with MPC that simulates 5 states ahead. We focus here on the motivation with more details in Section 6.
Our main contributions are summarized as i) a formal definition of HPO as an MDP which does not depend on any engineered heuristics, ii) a new transfer learning surrogate model represented by an ensemble of probabilistic neural networks, iii) a novel acquisition function that implements a look-ahead strategy paired with model predictive control, iv) clear motivation that highlights the impact of planning in HPO, which to the best of our knowledge, has never been addressed before.

heading: 2 RELATED WORK
text: Hyperparameter optimization has been extensively studied in the community within two main settings: single task (non-transfer learning) HPO and transfer learning HPO.
For single task HPO, solutions often involve estimating the hyperparameter response surface using a (probabilistic) surrogate, such as a Gaussian process (Rasmussen, 2003; Bergstra et al., 2011), random forests (Hutter et al., 2011), Bayesian neural networks (Springenberg et al., 2016), or some hybrid approach (Snoek et al., 2015a). Hyperparameter candidates are then selected via an acquisition function (Wilson et al., 2017a), e.g. expected improvement, that satisfies some well-motivated assumptions and utilizes the statistics from the posterior to score each hyperparameter.
Transfer learning solutions on the other hand leverage available data from experiments on related tasks to expedite HPO. Simple solutions involve initializing the surrogate using hyperparameters that perform well on datasets that have similar meta-features (Feurer et al., 2014; Jomaa et al., 2021a), i.e. dataset statistics. The response surface can also be modeled jointly in a multi-task setting (Bardenet et al., 2013; Yogatama & Mann, 2014; Perrone et al., 2018). For example, Salinas et al. (2020) transforms the hyperparameter response into a similar distribution and learns a shared Gaussian Copula. Another way to achieve transfer learning is through a weighted combination of the surrogates (Wistuba et al., 2016; Feurer et al., 2018). More recently, it has been shown that meta-learning an initialization of the surrogate by training to estimate the response across the training tasks, and subsequently fine-tuning to the target task improves generalization and leads to better performance (Wistuba & Grabocka, 2021; Jomaa et al., 2021b). Additionally one can learn a transferable acquisition function (Wistuba et al., 2018; Jomaa et al., 2019; Volpp et al., 2020). Jomaa et al. (2019) propose to learn a policy based on Deep Q-learning (Watkins & Dayan, 1992) where they assume a temporal dependency between the hyperparameters and propose an LSTM (Hochreiter & Schmidhuber, 1997) to model it. Volpp et al. (2020) propose a transferable acquisition function, MetaBO, as a policy that is meta-trained on related tasks. As another model-free RL approach, MetaBO is trained by interacting with the environment and observes an engineered state representation that is heavily influenced by underlying surrogates. MetaBO however is very sensitive to the number of trials (Wistuba & Grabocka, 2021). We discuss the proposed MDPs and their relationship to our proposed approach in Section 4.
Model-based reinforcement learning aims to learn a model of the environment by estimating the next state given a state-action pair. It is applied with great success in areas such as robotics and video games. Existing methods similarly involve learning a (probabilistic) model of the dynamics (Chua et al., 2018; Nagabandi et al., 2018; Ko et al., 2007). Moreover, several methods improve the policy
in a Dyna style approach (Sutton, 1991a), by leveraging the generated trajectories from the model to mitigate the distribution shift.

heading: 3 PRELIMINARIES
text: Hyperparameter Optimization: Let D denote the space of all datasets and Λ ∈ RN the space of hyperparameters associated with an unknown black-box function `(D) : Λ → R where `(D) represents the response `(D)(λ), e.g. validation loss, of a certain model under investigation trained on a dataset D ∈ D with hyperparameters λ ∈ Λ. For example, we might be interested in a neural network model where Λ := R+ × R+0 × N represents the learning rate, dropout rate, and the number of layers, respectively. The objective of HPO is hence to find the optimal hyperparameter configuration λ∗ := arg minλ∈Λ `(D)(λ) given a fixed budget of T trials.
HPO is commonly treated as sequential decision-making process, where a surrogate model ˆ̀ : Λ→ R is iteratively fit to the history H(D)t := {λi, `(D)(λi)}ti=1 of evaluated hyperparameters and an acquisition function ŵ : (Λ × R)∗ → Λ is used to select the next candidate which minimizes the expected hyperparameter response:
arg min ŵ
ED∼ρD `(D)({λ1, . . . , λt}), (1)
where `(D)({λ1, . . . , λt}) := mini∈{1,...,t} `(D) (λi), λi := ŵ({(λj , `(D)(λj)}i−1j=1) and ρD is some distribution over the available datasets. Among the variety of acquisition functions, the expected improvement is widely adopted (Mockus, 1974). Although HPO algorithms can be applied on both continuous and discrete search spaces, here we focus on discrete spaces because they allow for faster training in transfer learning settings (Schilling et al., 2016; Jomaa et al., 2021b).
Model-based reinforcement learning: MbRL uses interactions with the environment to learn a parameterized approximation of the underlying transition function which subsequently can be used for planning. The learning task can be formulated as a discrete-time Markov decision process (MDP) defined by the tuple 〈S,A, τ, r〉 with state space S, action space A, unknown transition function τ : S × A → S and reward function r : S × A → R. The general approach in RL is to learn the optimal policy π maximizing the expected cumulative discounted reward given by J(π) := E [∑T
t=1 γ tr(st, at) | st = τ(st−1, at−1), a ∼ π(st) ] where st ∈ S and at ∈ A with discount
factor γ ∈ [0, 1]. We note that the explicit reward function or an approximate reward model is necessary for planning actions under some learned transition model. During inference, the optimal sequence of actions is commonly presented as the solution to the following optimization problem:
arg max a1,...,aT T−1∑ t=0 r̂ (τ̂(st, at), at+1) , (2)
which leverages the transition model τ̂ to predict the next state st+1 given a state st and action at.

heading: 4 HYPERPARAMETER OPTIMIZATION VIA MODEL-BASED RL
text: In the following we formulate HPO as an MDP which in turn facilitates the use of a variety of RL approaches to solve the problem. As a sequential decision-making process, hyperparameters λ ∈ Λ are iteratively selected and evaluated forming a simple MDP. Particularly, the state space is defined as S := (Λ× R)∗ with
s (D) t := ( (λ1, ` (D) 1 ), . . . , (λt, ` (D) t ) ) (3)
where `(D)i := ` (D)(λi) and action spaceA := Λ. The ground truth transition function τ : S×Λ→ S simply appends the new observations to the previous ones,
τ(s (D) t , λ) := ( (λ1, ` (D) 1 ), . . . , (λt, ` (D) t ), (λ, ` (D)(λ)) )
(4)
for dataset D ∈ D and a ground truth reward function, r := S × Λ → R, that returns the loss reduction of the new hyperparameters over the best loss so far,
r(s (D) t , λ) := max{0, min i=1:t ` (D) i −min{` (D) 1 , . . . , ` (D) t , ` (D)(λ)}} (5)
To estimate both, the transition function and the reward function, as done in MbRL, the only missing piece is a model for the validation loss, the so called surrogate model. Given ˆ̀(D) : Λ → R, the transition and reward models are just: τ̂ : S × Λ→ S where
τ̂(s (D) t , λ) := ( (λ1, ` (D) 1 ), . . . , (λt, ` (D) t ), (λ, ˆ̀(D)(λ)) )
(6)
and r̂ : S × Λ→ R with
r̂(s (D) t , λ) := max{0, min i=1:t ` (D) i −min{` (D) 1 , . . . , ` (D) t , ˆ̀(D)(λ)}}. (7)
In this sense, HPO using a surrogate model can be seen as a special case of MbRL, and thus all approaches researched for MbRL can be directly applied to HPO. When learning a joint surrogate across several datasets in D, the superscript is dropped and ˆ̀(D) → ˆ̀. To the best of our knowledge, so far there exist two prior publications which attempt to solve HPO using RL by defining distinct MDPs. Jomaa et al. (2019) originally define the state as the dynamic history of evaluated hyperparameters and their respective responses as S := (Λ × R)∗ and s(D)t as defined earlier. However, they suggest that the order by which the hyperparameters are selected impacts the decision on which action to take next, which is why they model this temporal aspect via an LSTM in their policy, which is conditioned on some engineered meta-features. Their transition function generates new states by appending the action and the observed response to the previous state according to τ(s(D)t , λ) := ( (λ1, ` (D) 1 ), . . . , (λ (D) t , `t), (λ, ` (D)(λ))) ) . Volpp et al. (2020) represent the state space as S := (RM )∗ with st := ((µt(λi), σ2t (λi), λi, ψi)) |Λ| i=1 where µt and σ2t are the mean and variance of the posterior distribution of an underlying surrogate and ψi are some engineered attributes. The transition function simply updates the parameters of the surrogate based on the new observations. Both approaches define the action space as the discrete grid of hyperparameters, A := Λ, whereas the reward function is computed in terms of the regret. In strong contrast to these methods that replace the standard acquisition function with a policy trained via model-free RL approaches, we adopt the powerful yet simple MDP proposed by Jomaa et al. (2019) to train a transition model that allows planning to improve HPO in the context of MbRL.

heading: 5 METAPETS ALGORITHM
text: In this section, we present our model-based reinforcement learning algorithm. Namely, we define the transition function, our novel look-ahead acquisition function, and the associated training procedure.

heading: 5.1 PROBABILISTIC TRANSITION FUNCTION
text: Model-based reinforcement learning is mainly concerned with learning a parameterized model of the environment which approximates the underlying dynamics, or transition function, τ : S × A → S, such that the next state can be estimated given the current state-action pair. Following the standard RL notation, we denote by actions a hyperparameters λ, i.e. `(D)(a) = `(D)(λ). Accordingly, the choice of the model class plays an important role. A common approach to model the environment is through Gaussian processes (GP) (Rasmussen & Kuss, 2003; Ko et al., 2007; Boedecker et al., 2014) or a mixture of GPs (Khansari-Zadeh & Billard, 2011) which provide uncertainty estimates for the predictions and, more importantly, for unexplored areas. However, such models suffer from the curse of dimensionality and thus are difficult to scale to high-dimensional domains. Deep neural networks on the other hand have shown great success in handling uncertainty estimation (Springenberg et al., 2016; Gal & Ghahramani, 2016; Lakshminarayanan et al., 2017), with success in predictive modeling of images (Watter et al., 2015) and short-horizon control tasks for high-dimensional data.
In our case, the state is represented as the history of selected hyperparameters and their responses, up to a given time, while the actions consist of the available hyperparameters to be evaluated. Hence there is only one missing piece of information that is required to establish the next state, and that is the response of the respective selected action (Figure 2). This missing element we acquire by training the transition model to directly estimate the response for a given state-action pair.
Specifically, we parameterize our transition function τ̂θ(s (D) t , at) : S ×A → R+0 ×R+ as a probabilistic neural network with parameters θ, which takes as input the current state-action pair (s(D)t , at) and outputs the defining parameters of a probability distribution function, e.g. a Gaussian distribution. The governing assumption for this well-established approach is that the instance is derived from a heteroscedastic Gaussian distribution, i.e. the variance is not fixed between instances. Accordingly, the network outputs the respective mean µ̂θ ∈ R0 and variance σ̂2θ ∈ R+ and is trained by minimizing the negative log-likelihood:
ED∼ρD [ − log σ̂θ(s (D), a)2
2 +
(`(D)(a)− µ̂θ(s(D), a))2
2σ̂θ(s(D), a)2 + ct
] . (8)
Thus, we define the predicted hyperparameter response as ˆ̀(a) ∼ N ( µ̂θ(·, a), σ̂θ2(·, a) ) . We then estimate ŝ(D)t = τ̂θ(s (D) t , a) = s (D) t−1 ⋃ (a, ˆ̀(a)). A simulated rollout is presented in Algorithm 1.
The Case for Ensembles: Probabilistic neural networks can capture and model the aleatoric uncertainty of the environment (e.g. observation noise) by parameterizing a suitable distribution. However, a single probabilistic network is not capable of capturing any epistemic uncertainties (e.g. lack of a sufficient amount of data to completely determine the real dynamics). In particular, the epistemic uncertainty vanishes in the limit of infinite data but can have a major impact in low data regimes like HPO. For that reason, it is of major importance to account for epistemic uncertainty.
A principled approach to deal with this issue is by bootstrapping models in an ensemble. An ensemble of deterministic models, such as standard neural networks, reduces bias and epistemic uncertainty. Therefore, to capture both, aleatoric as well as epistemic uncertainty, we employ a simple bootstrapped ensemble of probabilistic neural networks, which has been shown to outperform single probabilistic networks as well as other Bayesian approaches (Chua et al., 2018).
Given such an ensemble of probabilistic transition models denoted as {τ̂θi} NE i=1, we can observe a mixture of NE distributions, i.e. {N ( µ̂θi , σ̂ 2 θi ) }NEi=1. Following Lakshminarayanan et al. (2017) we aggregate the outputs as
µ∗(·, a) = 1
NE NE∑ i=1 µ̂θi(·, a), and σ2∗(·, a) = 1 NE NE∑ i=1 ( σ̂2θi(·, a) + µ̂ 2 θi(·, a) ) − µ2∗(·, a) (9)
leading to a predicted hyperparameter response in the form of ˆ̀(a) ∼ N ( µ∗(·, a), σ2∗(·, a) ) . The explicit advantage of the ensemble approach in particular is the simple but excellent estimation of uncertainty which constitutes one of the main performance drivers in HPO in recent years.

heading: 5.2 TRAINING THE DYNAMICS MODEL
text: The first step in our MbRL approach is to generate a dataset of transitions as training dataset for our dynamics model. We denote by E := { ( Dn, {λi, `(Dn)(λi)} TDn i=1 ) }Nn=1 a meta-dataset of primary
datasets, hyperparameters and their responses sampled from some unknown distribution of datasets ρD and some unknown distribution of hyperparameters ρΛ. We generate our training dataset E train from the meta-dataset by sampling a quadruple (Dn, s (Dn) t , at, `
(Dn)(at)) of datasets Dn, sets of hyperparameters and their responses as states s(Dn)t , unobserved hyperparameters as actions at, and the missing element from the next state s(Dn)t+1 as the response to at, i.e. `
(Dn)(at). This is similar to the usually used approach of implementing a random policy to generate the trajectories (Nagabandi et al., 2018). Although it is possible to augment the E train with trajectories generated using MPC, we noticed that it is i) time-consuming and ii) does not lead to a significant improvement compared to using simple random trajectories. We conjecture that this is due to the nature of our transition function. Specifically, because the sequence of hyperparameters selected (by any policy) does not
immediately affect the output of the transition model, i.e. τ(s(D)t−1, a) = τ(s (D) t , a) ∀a ∈ A but rather the output is only affected by the selected action.
Since our state st is defined as the collection of previously evaluated hyperparameters and their corresponding responses, we employ a deep set (Zaheer et al., 2017) formulation to encode st into a fixed-size vector representation. In contrast to the common approach of conventional model-based RL algorithms which are concerned with predicting the state difference ∆ŝt+1, we estimate the response `(D)(a) to a given action a while considering the state as context information (Kim et al., 2019). Concretely, the transition model is defined as :
µ̂, σ̂2 = f ([ at, 1
t t∑ i g ([λi, `i])
]) , (10)
such that τ̂ := f ◦g where g := Λ×R→ RNg and f : Λ×RNg → R+0 ×R+ are feed-forward neural network models, and [ ] represents standard concatenation. Given the variety of primary datasets, we use first-order meta-learning (Nichol et al., 2018) to optimize the parameters of our transition model. We summarize the training procedure in Algorithm 2.

heading: 5.3 PLANNING WITH THE LEARNED TRANSITION FUNCTION
text: Given the learned dynamics model, we subsequently require an approach that can effectively leverage the acquired information to predict the optimal sequence of hyperparameters to evaluate. For example, Dyna-style algorithms (Sutton, 1991b) use the simulated experience to mitigate the distribution shift (Luo et al., 2019; Kurutach et al., 2018; Clavera et al., 2018) by integrating trajectories that have been generated via the policy to further train the transition model.

heading: 5.3.1 MODEL PREDICTIVE CONTROL
text: For simplicity, here we consider the well-known approach of model-predictive control (MPC) which has been used in many complex control scenarios (Bouffard et al., 2012; Lenz et al., 2015; Amos et al., 2018). Furthermore, it is easy to implement and does not require any gradient computation.
The general idea of MPC is to solve an optimization problem in a specific horizon on top of the learned transition model to produce a sequence of actions. In particular we employ a simple random shooting (RS) (Zhou & Yan, 2014) technique to solve the following optimization objective:
arg max {at′}Tt′=t
r̂(ŝ (D) t′ , at′). (11)
Notice that since the reward is measured in terms of the regret we do not need to sum over the rewards at each simulated state, as presented in Equation 2, but simply observe the reward at the final state in the rollout.
The RS policy generates K random action sequences with a horizon of length H from a uniform distribution and evaluates them via the learned transition function. Then usually only the first action of the best candidate sequence is executed and the procedure is repeated from the new state. Finally, we also fine-tune the transition model(s) given the newly evaluated hyperparameters on the test datasets to mitigate the distribution shift, which is common practice in all Bayesian-based optimization techniques.
5.3.2 LOOKAHEAD MPC
Conventional acquisition functions are agnostic to the order by which the previous hyperparameters have been selected, i.e. â(Ht) = â(φ(Ht)), where φ is some permutation function since they are only concerned with the immediate improvement and do not account for how the optimization process evolves. MPC on the other hand normally selects the first action from the trajectory that had the highest reward at the end of the rollout. This can be slightly misleading as it implies that to arrive at the best hyperparameter
6
configuration it is necessary to sequentially evaluate bad configurations. However, this is not true since the selection of hyperparameter configurations is independent and all configurations can be selected at all times. Thus, we propose to directly select the action that provides the highest estimated reward, i.e. lowest regret, from all the actions observed across all the simulated trajectories (Figure 3).

heading: 5.3.3 TRAJECTORY SAMPLING
text: The learned transition model outputs a distribution over the next state ŝ(D)t+1. To leverage the uncertainty associated with the output response, we create particles by randomly sampling p variations as ŝ
(D),p t+1 ∼ τ̂(s (D) t , at) and propagate through the trajectory of every particle. At each step, the reward
is then estimated as the average of the rewards across all particles:
r̂(ŝ (D) t , at) =
1
P P∑ p=1 r̂(ŝ (D),p t , at). (12)

heading: 6 EXPERIMENTS
text: The experiments are designed to address the following questions: 1)Does the learned transition model generalize to new unseen tasks? 2) What is the importance of planning when doing HPO?

heading: 6.1 META-DATASET
text: We evaluate our approach on three hyperparameter search spaces for feed-forward neural networks (Jomaa et al., 2021b), that includes 120 UCI classification datasets (Asuncion & Newman, 2007). We refer to the meta-datasets as Layout Md-v2, Regularization Md, and Optimization Md-v2 which include the Cartesian product of the individual hyperparameters with a total of 324, 288, and 432 unique configurations, and 10, 7, and 12-dimensional hyperparameters, respectively. More information is presented in Appendix B.

heading: 6.2 TRAINING THE TRANSITION MODEL
text: The transition model is trained via first-order meta-learning. Each meta-dataset is divided into 5 splits with 80 training datasets, 16 for validation and 24 for testing. We used a task batch size of 8 and 64 mini-batches per task. The number of inner iterations was set to 5. We use the ADAM (Kingma & Ba, 2015) optimizer with a learning rate of 0.001. The hyperparameters were tuned on the validation set and trained for 10000 outer iterations with early stopping. We trained a total of 5 distinctly initialized models for the ensemble using Tensorflow (Abadi et al., 2016).

heading: 6.3 BASELINE MODELS
text: We compare against several single tasks and transfer learning baselines for HPO designed for blackbox function optimization that rely only on the hyperparameters and the corresponding response. As such, some methods were not considered, e.g. Jomaa et al. (2021b); Falkner et al. (2018). Particularly, we compare against, Random sampling (Bergstra & Bengio, 2012), GP (Rasmussen, 2003), SMAC (Hutter et al., 2011), BOHAMIANN (Springenberg et al., 2016), TST-R (Wistuba et al., 2016), ABLR (Perrone et al., 2018), CTS (Salinas et al., 2020), and FSBO (Wistuba & Grabocka, 2021). A detailed overview can be found in Appendix C.
We denote by LookAhead MPC-HX, our approach, which employs LookAhead MPC by navigating the simulated environment using random shooting up to the defined horizon X and then selects the first action of the trajectory that achieves the highest reward. We sample 1000 trajectories for our method. The models of the ensemble are iteratively fine-tuned to the new hyperparameters as all baseline models. In Algorithm 3 we present the pseudo-code for our MetaPETS algorithm and provide the source code in the Supplementary material.

heading: 6.4 EVALUATION METRICS
text: We report two performance metrics to evaluate the effectiveness of the different baselines: normalized regret that represents the distance between the response of the evaluated hyperparameters and the optimal performance for each dataset, and the rank that measures the relative performance of each method compared to the rest of the baselines at each trial. The rank is computed at the task level and is agnostic to the heterogeneous ranges of the target response surfaces, thus can better signify the difference in performance.

heading: 6.5 RESULTS AND DISCUSSION
text: We report in Tables 1 and 2 the average rank and normalized regret, respectively, over 5 runs for 50 trials with three different seeds per run for all methods. Each transfer learning approach had access to the same training datasets and all models were initialized via the same three seeds to fit the initial surrogate. Overall, our LookAhead method outperforms the baselines across all meta-datasets. We use the horizon of H3 and H5 in this section, and study the contribution of LookAhead and the importance of planning in Section 6.6.
LookAhead MPC-3 and LookAhead MPC-5 demonstrate clear gains in the average rank with consistent performance against the baselines. Looking at the normalized regret, FSBO outperforms our model in some cases, e.g. Layout Md-v2, however, the associated average rank is still lower. This can be attributed to the fact that different tasks have heterogeneous response distributions. When there is a clear contradiction between the rank and the normalized regret, this signifies that the margin of difference of the normalized regret on the few tasks where FSBO shows stronger performance, is higher than where it has lost.
Comparing LookAhead MPC-3 and LookAhead MPC-5, we notice that a shorter horizon is sufficient to explore smaller search spaces. Albeit, early exploration in the form of longer horizons can still turn out to be more favorable, e.g in Regularization Md.
It is also worth mentioning that MetaBO, the model-free RL approach, is the worst across all metadatasets. This is attributed to the asymptotic degradation of the performance with the increasing number of trials, as pointed out in Wistuba & Grabocka (2021). Contrary to MetaBO, which relies on an underlying surrogate to generate the state which is bound by a fixed grid, our approach is
agnostic to the size of the grid and improves with more trials, leading to an improved state representation.

heading: 6.6 ABLATION
text: We further investigate the effect of LookAhead on MPC with different horizons and trajectory samples to evaluate the impact of planning under such conditions. Moreover, we compare against a vanilla version, that does not involve fine-tuning the transition model to the observations of the target dataset. We summarize the performance in Figures 4 and share the following insights: i) Fine-tuning plays a crucial role in improving performance. Contrary to existing MbRL solutions that evaluate a policy’s performance on the environment which the transition model has been trained to estimate, we evaluate our policy on new environments, i.e. new tasks, with varying response surfaces. We notice that with a few gradient update steps, (LookAhead) MPC-X outperforms the vanilla variant. ii) Using LookAhead MPC is better than standard MPC. This reinforces the notion that via proper planning the evaluation of bad hyperparameter configurations can be avoided. iii) Increasing the number of sampled trajectories leads to a better outcome. This is to be expected, considering that for random shooting, we sample a fixed number of trajectories to evaluate. At any given trial t, the number of possible trajectories for a horizon H on a grid of size N is ( N−t H ) , so for a horizon H = 1, we default to maximization over the grid.In Appendix D, we further discuss the effect of various plausible dynamics by bootstrapping different sets of models as part of the ensemble.

heading: 7 CONCLUSION
text: In this paper, we present a novel solution for HPO within the context of MbRL. Specifically, we design a new surrogate as an ensemble of neural networks, which is initialized through meta-learning and thus can adapt quickly to new target datasets with few observations. We propose a novel acquisition function based on model predictive control that utilizes a simple lookahead strategy to select good hyperparameter candidates from simulated trajectories. To the best of our knowledge, we are the first to investigate the impact of planning on HPO and present an extensive ablation study that motivates research in that direction.

heading: A ALGORITHM
text: Algorithm 1 Simulated Rollout
1: Require: state s(D)t , rollout horizon H , transition model τ̂θ, actions (ah)Hh=0 2: R← ∅ 3: ŝ(D)t ← s (D) t 4: for h = 0 to H 5: µ̂θ, σ̂2θ ← τ̂θ(ŝ (D) t+h, ah)
6: ˆ̀(ah) ∼ N ( µ̂θ, σ̂ 2 θ ) 7: R← R ⋃ (ˆ̀(ah)) 8: ŝ(D)t+h+1 ← ŝ (D) t+h ⋃ (ah, ˆ̀(ah)) 9: return R
Meta-learning has found resounding success in the research community as an initialization scheme, which allows for fast adaption to new domains. We want to emphasize that during meta-training the meta-test datasets are not observed and in that way remain strictly held out.
Algorithm 2 Model-based Reinforcement Learning
1: Require: training meta-dataset E train, parameters θ, learning rate η, inner update steps v, metabatch size n, minimum history length Tmin, maximum history length Tmax 2: while not converged do 3: t ∼ Unif ([Tmin, Tmax]) 4: D1, . . . , Dn ∼ Unif([1, . . . , N ]) 5: for i = 1 to n do 6: ( s
(Di) t , at, ` (Di)(at) ) ∼ Unif ( E train | Di, t ) 7: θi ← θ 8: for j = 1 to v do 9: θi ← θi + η∇θ ( pθ(s (Di) t | s (Di) t , at)
) 10: Update θ ← θ + η 1n ∑n i=1 (θi − θ) 11: return θ

heading: B META-DATASET
text: A meta-dataset is a collection of hyperparameters, typically defined on a discretized grid (Schilling et al., 2016; Jomaa et al., 2019), associated with a model under investigation, that have been evaluated offline by training the model with the mentioned hyperparameters on numerous primary datasets, and reporting some observed evaluation metric, e.g. validation loss.
We evaluate our approach on three hyperparameter search spaces for feed-forward neural networks (Jomaa et al., 2021b), that includes 120 UCI classification datasets (Asuncion & Newman, 2007). Jomaa et al. (2021b) propose a pruning strategy that eliminates redundant configurations. Specifically, they drop certain hyperparameter combinations, e.g. non- layouts with 1 hidden layer, which we see here as unnecessary. Therefore we do not prune Layout Md and Optimization Md and refer to the meta-datasets as Layout Md-v2, Regularization Md, and Optimization Md-v2 where each meta-dataset includes the Cartesian product of the individual hyperparameters with a total of 324, 288, and 432 unique configurations, respectively.
The aforementioned hyperparameters are encoded as follows:

heading: C BASELINES
text: 1. Random sampling (Bergstra & Bengio, 2012),
Algorithm 3 MetaPETS Algorithm
1: Require: target dataset D; training meta-dataset E train, transition model τ̂θ, parameters θ, learning rate η, inner update steps v, meta-batch size n, minimum history length Tmin, maximum history length Tmax, initial budget b, total budget B, planning horizon H , lookahead indicator z, vanilla indicator w 2: Initialize θ randomly 3: θ ←Algorithm 2 ( E train, θ, η, v, n
) 4: a0, . . . , ab ∼ Unif(Λ) 5: s(D)0 ← ( (a0, ` (D) 0 ), . . . , (ab, ` (D) b )
) 6: a∗ ← arg min{ai}bi=0 ` (D)(ai) 7: for i = 0 to B do 8: Sample sequence of actions (aih) H h=0 randomly 9: Perform simulated rollout, R←Algorithm 1(s(D)b+i , H, τ̂θ, (aih)Hh=0)
10: ai ← { ai0 if z = 0 (selects first action from sequence) aiarg minR otherwise (selects best action from sequence)
11: a∗ ← { ai if `(D)(ai) < `(D)(a∗) a∗ otherwise

heading: 12: if w = 0 do
text: 13: while not converged (Comment: Fine-tuning) 14: for t = 0 to b+ i 15: θ ← θ + η∇θ (pθ(st | st, at+1)) 16: s(D)b+i+1 ← s (D) b+i ⋃ (ai, `(ai)) 17: return a∗

heading: D EVALUATING VARIOUS STATE PROPAGATION DYNAMICS
text: In the main experiment, we predict plausible state trajectories using a bootstrap of B = 5 models in the ensemble. We investigate here the impact of changing the models in the ensemble, i.e. bootstrapping subsets of these models, to understand the stability and robustness of probabilistic neural networks. We propose as a variant EX , where we re-sample at every trial uniformly at random a different subset of B = X models. Effectively, we would be continually re-sampling from the approximate marginal posterior of plausible dynamics. We summarize the results in Figure 5.
We notice primarily that increasing that bootstrapping more models generally leads to better performance. In Layout Md-v2, MPC-3 and MPC-3 (E3) are better than MPC-3 (E1), especially at the early stages. We also notice that increasing the horizon leads to worse results. The same behavior is noticeable with Optimization Md-v2. Although MPC-5 in Regularization Md is better than the rest, discussed in Section 6.6, we notice that with the increasing number of trials, re-sampling a single probabilistic neural network starts to deteriorate.

heading: E LIMITATIONS
text: The proposed MetaPETS algorithm is designed as a transfer learning solution for HPO. The transition model is trained on a set of correlated source tasks to approximate the joint response surface. One of the limitations of this approach is that it does not work properly in non-transfer learning settings due to the lack of abundant data for training the surrogate throughout the HPO process. It is possible however to design another experimental protocol where a transition model is trained to estimate a partially observable search space on a particular dataset ( i.e. no transfer learning required), however, planning and navigation would have to be done in the unexplored search space.

Review summaries:
The authors establish the equivalency of hyperparameter optimization (HPO) and model-based reinforcement learning (MRL). On one hand, hyperparameter optimization is seen as an optimization of a sequence of actions (hyperparameter candidates) that improves a reward function. On the other hand, planning replaces the acquisition function of HPO. The sequence is constructed by a transition function driving the optimization towards its extremum. The transition function can be represented by a Markov Decision Process, while the reward function can be approximated by a surrogate. Within this frame, they explore the effect of planning on the performance of this approach on the task of hyperparameter optimization.

This paper proposes a method for hyperparameter optimization (HO) drawing inspiration from model-based RL (MBRL). They recast the HO problem in a markov decision process (MDP) formulation. This formulation permits the use of MBRL methods to solve the HO problem.   Concretely, having reframed HO using this MDP formulation, they propose to: (1) train an ensemble of probabilistic neural networks to model the transition function (using first order meta learning), which maps a set consisting of previous hyperparam-response value pairs and the current hyperparam setting to the associated response value (eg val loss); (2) use this transition model in Model Predictive Control (MPC) with random shootouts to obtain an effective hyperparameter setting. Given the nature of their MDP and the fact that successive states are independent of one another, they use a variant of MPC that selects the best hyperparameter setting (or action) seen (rather than use the first action, as is common in MPC).  In experiments, they demonstrate their method improves on various baselines on three different settings. They perform some ablation studies showing the importance of finetuning their model on the target domains and the importance of planning. 

The paper presents a novel transfer learning approach to hyperparameter optimization (HPO) by formulating the problem in a model-based reinforcement learning (MbRL) framework. In this setting, the transition function serves as a surrogate model for learning the validation loss of any black-box ML model which is trained via an ensemble of probabilistic neural networks. The authors further introduce a lookahead search strategy to sample trajectories for a model predictive control problem. Experiments demonstrate that the proposed method outperforms several competitors on a few meta-datasets for HPO tasks.