Quantity vs. Quality: On Hyperparameter Optimization for Deep Reinforcement Learning

Random search is a simple and popular model-free hyperparameter search algorithm (Bergstra and Bengio, 2012). In particular, random search can often serve as a simple but robust baseline against more complex methods (Li and Talwalkar, 2019). In random search hyperparameter configurations $\operatorname*{\boldsymbol{\lambda}}$ are sampled uniformly at random from the specified hyperparameter space $\operatorname*{\boldsymbol{\Lambda}}$. At the end of the optimization, the best observed hyperparameter setting ${\operatorname*{\boldsymbol{\lambda}}}^{*}$ is picked.

When applying random search in a setting where there is uncertainty, the suggestion of hyperparameter configurations is not impacted. However, the choice of the final recommended configuration may be influenced. In the presence of uncertainty the best observed setting may not be the on-average best setting. This issue can be alleviated using repetition as described in Section 2.2, however at a higher computational cost. In experiments we denote random search as Random Search, Random Search x3, and Random Search x5 for using one, three, or five evaluations, respectively.

Another more recent approach to hyperparameter search is the bandit-based Successive Halving Algorithm (SHA) (Jamieson and Talwalkar, 2016), as well as its extensions Hyperband (Li et al., 2016), and Asynchronous Successive Halving (ASHA) (Li et al., 2018). SHA and Hyperband have been shown to outperform random search and state-of-the-art model-based search methods on many hyperparameter optimization benchmarks from the domain of supervised learning. SHA operates by randomly sampling configurations and allocating increasingly larger budgets to well-performing configurations. In the beginning, a small budget is allocated to each configuration. All configurations are evaluated and the top $1/\eta$ of configurations are promoted. Then the budget for each promoted configuration is increased by a factor of $\eta$. This is repeated until the maximum per-configuration budget is reached. When tuning neural networks with SHA, the budget is usually the number of training iterations. That way the algorithm can probe a lot of configurations without fully evaluating them. An algorithm that closely resembles SHA is used to tune hyperparameters of deep reinforcement learning algorithms in the Stable-baselines (Hill et al., 2018) package. We imitate the setup there by using the number of training steps as the resource. We refer to this as ASHA in experiments since we are using the asynchronous version of SHA.

Lastly, evolutionary algorithms have recently been successfully applied to hyperparameter optimization and architecture search and hyperparameter optimization for neural networks (Real et al., 2017; Loshchilov and Hutter, 2016; Hansen et al., 2019). Evolutionary algorithms such as CMA-ES (Hansen et al., 2003) can handle high-dimensional search spaces and actually have a principled way of handling uncertainty. Nevertheless, evolutionary algorithms tend to require a larger number of function evaluations that is out of the scope of this study and may also be infeasible for many practitioners. For this reason, we leave the comparison to evolutionary algorithms for future work.

One algorithm from this paradigm that is popular with practitioners is Population-Based Training (PBT) (Jaderberg et al., 2017). In PBT a population of models is trained jointly with optimizing their hyperparameters. Contrary to most other hyperparameter optimization approaches, PBT finds schedules of hyperparameters via perturbation and replacement between generations. PBT has shown strong results in multiple domains including the training of reinforcement learning agents. The crucial difference in the goal of PBT and the goal we are aiming for in this paper is that PBT delivers one optimally trained agent. In this paper we however aim to obtain an optimal hyperparameter setting. While it is possible to trace back the schedule of hyperparameters of the best agent in PBT, we believe that it is less common to share and reproduce these. In addition, due to the fact that PBT finds schedules instead of specific hyperparameter settings it is difficult to accurately compare it to standard hyperparameter optimization methods which find fixed hyperparameters. For these reasons we do not include PBT in the experiments in Section 3.

As mentioned before, Bayesian optimization chooses the next point to evaluate via the acquisition function. The most popular choice of acquisition function for hyperparameter optimization is the expected improvement (EI) (Mockus et al., 1978). The EI is given by

$$EI(\operatorname*{\boldsymbol{\lambda}})=\mathbb{E}_{f(\operatorname*{\boldsymbol{\lambda}})|\operatorname*{\mathcal{C}}}[\operatorname*{I}(\Psi_{min},f(\operatorname*{\boldsymbol{\lambda}}))].$$

(2)

where $\operatorname*{I}(r,s)=\max(0,r-s)$ and $\Psi_{min}=\min_{1\leq i\leq n}\Psi_{i}$ is the minimum observed validation loss. Part of why the EI is popular is that it can be computed analytically. However, if observations are uncertain $\mathrm{Var}(\Psi(\operatorname*{\boldsymbol{\lambda}}))$ may be large and $\Psi_{min}$ may just be low by chance. This can result in over-exploitation around $\Psi_{min}$ and the optimization getting "stuck" around this point. In experiments we refer to EI as GPyOpt-EI since we are using the GPyOpt (authors, 2016) implementation. We also show experiments for GPyOpt-EI x3, referring to EI with averaging across three repetitions for each hyperparameter setting.

(Letham et al., 2019) extended expected improvement to handle uncertainty in observations by taking the expectation over observations. Ignoring constraint handling also introduced by the authors, the noisy expected improvement (NEI) can be written as:

$$NEI(\operatorname*{\boldsymbol{\lambda}})=\mathbb{E}_{f(\operatorname*{\boldsymbol{\lambda}}_{1:n})|\operatorname*{\mathcal{C}}}\{\mathbb{E}_{f(\operatorname*{\boldsymbol{\lambda}})|\mathcal{C^{*}}}[\operatorname*{I}(\Psi_{min}^{*},f(\operatorname*{\boldsymbol{\lambda}}))]\}.$$

(3)

where $\mathcal{C^{*}}=\{(\operatorname*{\boldsymbol{\lambda}}_{i},\Psi^{*}(\operatorname*{\boldsymbol{\lambda}}_{i})):\Psi^{*}(\operatorname*{\boldsymbol{\lambda}}_{i})\sim f(\operatorname*{\boldsymbol{\lambda}}_{i})|\mathcal{C}\}_{i=1}^{n}$ is a fantasy dataset sampled from the posterior and $\Psi_{min}^{*}$ is the minimum of the fantasy dataset. In practice, this approach fits a GP model. GP samples are drawn from the posterior at the observed points. These samples represent fantasy datasets. Each fantasy dataset is treated as in the regular EI, that is, a GP is fitted and the EI is computed across the space $\operatorname*{\boldsymbol{\Lambda}}$. The EI values are then averaged across the fantasy datasets to obtain the NEI. Balandat et al. (2019) simplify this approach by taking the expectation over the joint posterior:

$$qNEI(\operatorname*{\boldsymbol{\lambda}})=\mathbb{E}_{f(\operatorname*{\boldsymbol{\lambda}}),f(\operatorname*{\boldsymbol{\lambda}}_{1:n})|\operatorname*{\mathcal{C}}}[\operatorname*{I}(\min f(\boldsymbol{\lambda}_{1:n}),f(\operatorname*{\boldsymbol{\lambda}})].$$

(4)

We note that Equation 3 and 4 are both computationally intensive and non-trivial to implement. However, Letham et al. (2019) showed that NEI outperforms regular EI on objective functions with Gaussian noise and given the true variance. In our experiments we use the qNEI implemented in BoTorch¹¹1https://botorch.org/ to calculate the noisy expected improvement. Contrary to the experiments in (Letham et al., 2019) we infer the variance $\tau^{2}$. We refer to this approach as BoTorch-qNEI.

An alternative to the EI criterion is the Lower(/Upper) Confidence Bound (LCB) criterion (Srinivas et al., 2009). The LCB takes the form

$$LCB({\operatorname*{\boldsymbol{\lambda}}})=\mu_{n}(\operatorname*{\boldsymbol{\lambda}})+\beta\sigma_{n}(\operatorname*{\boldsymbol{\lambda}})$$

(5)

where $\beta$ is a coefficient set by the user. This coefficient is sometimes termed the exploration weight. Tuning the exploration weight may improve the performance of LCB. However, since in practice the computational budget to tune this parameter is rarely available, we use a default value of $\beta=2$. While LCB has been shown to be outperformed by EI on noise-less objective functions (Snoek et al., 2012), contrary to EI it is not impacted by uncertainty in the observations. This is due to the fact that it only depends on the posterior mean and variance. In all experiments we refer to LCB as GPyOpt-LCB.

We note that there are more available acquisition functions than the ones presented in this section. In particular, the knowledge gradient (Scott et al., 2011; Wu and Frazier, 2016) is an acquisition function that, while difficult to compute, can handle uncertainty and has been shown to outperform the presented acquisition functions (Balandat et al., 2019). Furthermore, entropy-search-based methods (Hennig and Schuler, 2012; Hernández-Lobato et al., 2014; Wang and Jegelka, 2017) also naturally handle uncertainty. We leave the evaluation of these methods to future work.

While the choice of acquisition function determines how to choose the next point, one still needs to pick a best setting at the end of the optimization. In the noise-less case this is often done by picking the best observed hyperparameter $\operatorname*{\boldsymbol{\lambda}}_{i}$. Frazier (2018) suggested to rely on the GP model and pick the best predicted $\operatorname*{\boldsymbol{\lambda}}$. Since this approach is robust to uncertainty we use the predicted best $\operatorname*{\boldsymbol{\lambda}}$ in all experiments. To make this feasible in multi-dimensional tasks we find the best predicted by optimizing an LCB acquisition with $\beta=0$, thereby utilizing existing optimization tools in BoTorch and GPyOpt.