No More Pesky Hyperparameters:
Offline Hyperparameter Tuning for RL

A calibration model is a simulator of the environment—learned from an offline batch of data—used to specify (or calibrate) hyperparameters in the agent. With the calibration model, the agent can test different hyperparameter settings. It evaluates the online performance of different hyperparameter choices in the calibration model and selects the best one. It can then be deployed into the true environment without any remaining hyperparameters to tune.

The basic strategy is simple: we train a calibration model, then do grid search in the calibration model and pick the top hyperparameter, as summarized in Algorithm 1. For each hyperparameter, we obtain a measure of the online performance of the agent across $n_{\text{runs}}$ in the calibration model, assuming it gets to learn for $n_{\text{steps}}$ of interaction. The pseudocode for AgentPerfInEnv is in Algorithm 2, for the episodic setting where we report average returns during learning. Note that we add a cutoff in the evaluation scheme to guarantee that at least 30 episodes are seen by the agent during training in the calibration model. We cut off episodes that run longer than $n_{\text{steps}}/30$ steps, teleporting the agent back to a start state.

Many components in this approach are modular, and can be swapped with other choices. For example, instead of expected return during learning (online performance), optimizing the hyperparameters might be more desirable to find the best policy after a budget of steps. This would make sense if cumulative reward during learning in deployment was not important. We might also want a more robust agent, and instead of expected return, we may want median return. Finally, the grid search can be replaced with a more efficient hyperparameter selection method; we discuss this further in Section 7.

We can also make this hyperparameter search more robust to error in the calibration model by obtaining performance across an ensemble of calibration models. This involves using $n_{\text{ensembles}}$ random subsets of the log data, say by dropping at random 10% of samples, and training $n_{\text{ensembles}}$ calibration models. The hyperparameter performance can either be averaged across these models, or a more risk-averse criterion could be used like worst-case performance. Using an average across models is like using a set of source environments to select hyperparameters—rather than a single source—and so could improve transfer to the real environment.

These are all additions to this new Data2Online strategy. The central idea is to use this calibration model to evaluate hyperparameters, as if we had a simulator. We, therefore, investigate this idea first in its simplest form with expected returns, grid search and only one calibration model.

This section highlights three conceptual criteria for designing the calibration model and selecting agents for which Data2Online should be effective. This includes 1) stability under model iteration, 2) handling actions with low data coverage and 3) selecting agent algorithms that only have initialization hyperparameters, namely those that affect early learning but diminish in importance over time.

Producing reasonable transitions under many steps of model iteration is key for the calibration model. The calibration model is iterated for many steps, because the agent interacts with the calibration model as if it were the true environment—for an entire learning trajectory. It is key, therefore, that the calibration model be stable and self-correcting. A stable model is one where, starting from any initial state in a region, the model remains in that region. A self-correcting model is one that, even if it produces a few non-real states, it comes back to the space of real states. Otherwise, model iteration can produce increasingly non-sensical states, as has been repeatedly shown in model-based RL (Talvitie, 2017; Jafferjee et al., 2020; Abbas et al., 2020; Chelu et al., 2020).

The model also needs to handle actions with no coverage, or low coverage. For unvisited or unknown states, the model simply does not include such states. The actions, however, can be queried from each state. If an action has not been taken in a state, nor a similar state, the model cannot produce a reasonable transition. Any choice will have limitations, because inherently we are filling in this data gap with an inductive bias. A common choice in offline RL is to assume pessimistic transitions: if an action is not observed, it is assumed to have a bad outcome. This ensures the learned, fixed policy avoids these unknown areas.

The choice is even more nuanced in Data2Online. Just like offline RL, it can be sensible to avoid these unknown actions, to answer: in the space known to the agent, what hyperparameters allow the agent to learn quickly? But, another plausible alternative is that we want to select hyperparameters to encourage the agent to explore unknown areas, since once deployed the agent can update its policy in these unknown areas. In other words, a principle of optimism could also be sensible. Selecting the right inductive bias will depend on the environment and the types of hyperparameters we are selecting. This question will likely be one of the largest questions in Data2Online, similarly to how it remains an open question in offline RL.

The third criterion is a condition on the agent, rather than the model. Practically, we can only test each hyperparameter setting for a limited number of steps in the calibration model. So, the calibration model is only simulating early learning. This suggests that this approach will be most effective if we tune initialization hyperparameters: those that provide an initial value for a constant but wash away over time. Examples include an initial learning rate which is then adapted; policy initialization; and an initial architecture that is grown and pruned over time.

These criteria are conceptual, based on reasoning through when we expect success or failure. We use these conceptual criteria to propose an appropriate approach to learn a calibration model in the next section. In addition to conceptual reasoning, theoretical understanding of the Data2Online problem setting is also critical. We provide a first step in that direction in the next section.

This problem has aspects that both make it harder and potentially easier than a standard offline RL problem. One aspect that makes this problem harder is that we have to evaluate a learning policy offline, rather than a fixed learned one. A fixed policy can be assessed using policy evaluation, and there exists a variety of theoretical results on the quality of those estimates, many based on the foundational simulation lemma (Kearns & Singh, 2002). No such results exist for evaluating a policy that will be changing online.

At the same time, intuitively, the problem could be easier than the offline RL problem, because the policy adapts online. Instead, we only have to select from a potentially small number of hyperparameters, rather than from a potentially large policy space. For example, it may be relatively easy to identify the best stepsize out of a set of three stepsizes. Further, if a policy learning algorithm is chosen that is robust to its hyperparameter settings, then the problem may be even simpler. For example, it may be simple to select the initial stepsize for an adaptive stepsize algorithm, where the initial stepsize only influences the magnitude of updates for the first few steps.

We first extend the foundational simulation lemma to the Data2Online setting, in Theorem 1. Then, in Theorem 2, we show how to use this result, to bound how far the value of the hyperparameters chosen in the learned calibration model are from the best hyperparameters. Finally, we discuss how it might be possible to formalize this second intuition, for future theoretical investigation.

We start by defining some needed terms. An online learner can be characterized by a history dependent policy (see Chapter 38 of (Lattimore & Szepesvári, 2020)). A history dependent policy is $\pi=(\pi_{0},\pi_{1},\pi_{2},\dots)$ where $\pi_{t}:\mathcal{H}_{t}\to\Delta(\mathcal{A})$ and $\mathcal{H}_{t}=(\mathcal{S}\times\mathcal{A}\times{\mathbb{R}})^{t}\times\mathcal{S}$ is the history at time step $t$. For simplicity, we assume the rewards are deterministic in $[0,{r_{\text{max}}}]$ and the MDP has one initial state $s_{0}$. The online learning agent interacts with the environment for $T$ steps in total, in either a continuing or fixed-horizon setting.

The value function for this online learner $\pi$ is the sum of rewards from time $t$ to the end of learning at $T-1$

where the expectation is under $A_{t}\sim\pi_{t}(\cdot\mid H_{t})$, $S_{t+1}\sim P(\cdot\mid S_{t},A_{t})$. Note that $V^{\pi}_{0}(s_{0})$ is the $T$ step objective that we use to select hyperparameters. For the fixed-horizon setting where episodes are of length horizon, $T=K\cdot\textit{horizon}$ where $K$ is the number of episodes. In this setting, the expectation is under $S_{t+1}\sim P(\cdot\mid S_{t},A_{t})$ if $t$ is not the last step of an episode and $S_{t+1}=s_{0}$ if $t$ is the last step of an episode. Dividing $V^{\pi}_{0}(s_{0})$ by $K$ gives the average episodic return over $K$ episodes.

Theorem 1 says that if we have a good model of the environment, we can evaluate the $T$ step objective for any online learner with bounded error. In particular, we can control this evaluation error by controlling the error of the learned model. Note that $v_{\text{max}}\doteq T{r_{\text{max}}}$ is the maximum value, so the last term $\frac{\varepsilon_{p}{r_{\text{max}}}T^{2}}{2}$ can be interpreted as $\tfrac{\varepsilon_{p}v_{\text{max}}T}{2}$, meaning the bound scales with $T$: $(\varepsilon_{r}+\tfrac{\varepsilon_{p}v_{\text{max}}}{2})T$.

This result is a sanity check that we can reason about error in identifying hyperparameters based on model error. However, it has several limitations. One limitation is that the result is for continuing problems and fixed-horizon episodic problems, but not variable length episodic problems. The analysis does not address variable length episodic problems, because it would impact both the histories on which policies are conditioned as well as the definition of the value function for this learning policy. The more important limitation, however, is that the bound depends on the length of interaction $T$, and worse on the squared length of interaction $T^{2}$ if we assume $v_{\text{max}}\doteq T{r_{\text{max}}}$. Even if episodes are short, we expect the agent to learn for thousands of steps and so $T$ can be quite large. It may be difficult to obtain sufficiently low $\varepsilon$ (model error) to control for this accumulating error over many steps.

Ideally, we should be able to obtain a better result by considering smoothness in performance with respect to hyperparameters. Empirical studies do suggest performance changes smoothly as a function of hyperparameters, whenever hyperparameter sensitivity plots are shown. We hypothesize that there exists a subset of hyperparameters such that $V^{\pi_{\lambda}}_{0}(s_{0})$ is smooth w.r.t. the hyperparameters in the subset, and hyperparameters outside the subset have very low $V^{\pi_{\lambda}}_{0}(s_{0})$. Therefore, the error bound from Theorem 2 just needs to be smaller than the performance gap between hyperparameters in the good subset and hyperparameters outside the good subset to guarantee finding a nearly optimal hyperparameter setting. This direction is an important next step.

The calibration model needs to produce a (stochastic) outcome next state and reward $r,s^{\prime}$, given a state and action $s,a$. We can produce novel trajectories from a dataset, by noting that if a state-action pair $(s_{t},a_{t})$ is similar to $(s_{i},a_{i})$ for a stored tuple $(s_{i},a_{i},r_{i},s^{\prime}_{i})$, then it is plausible that $r_{i},s^{\prime}_{i}$ could also have been observed from $(s_{t},a_{t})$. To allow for stochastic transitions, the $k$ most similar pairs to $(s_{t},a_{t})$ can be found, and the next state and reward selected amongst these by sampling proportionally to similarity.

More formally, given the current state-action pair $(s_{t},a_{t})$, the model searches through all tuples $(s,a,s^{\prime},r)$ and selects the $k$ nearest neighbors, according to similarity between $(s_{t},a_{t})$ and $(s,a)$. (We will discuss how to compute similarity in Section 5.2.) Let $\{(s_{i},a_{i},r_{i},s^{\prime}_{i})\}_{i=1}^{k}$ correspond to these tuples, and $d_{i}$ to the distance between $(s_{t},a_{t})$ and $(s_{i},a_{i})$. Then these $(r_{i},s^{\prime}_{i})$ are all possible outcome rewards and next states, where the likelihood corresponds to similarity to $(s_{i},a_{i})$. If $(s_{t},a_{t})$ is very similar to $(s_{i},a_{i})$, then $(r_{i},s^{\prime}_{i})$ is a likely outcome. Otherwise, the more dissimilar, the more unlikely it is that $(r_{i},s^{\prime}_{i})$ is a plausible outcome. The tuple $i$ is sampled proportionally to the probability $p_{i}=1-\frac{d_{i}}{\Sigma_{j\in[1,k]}d_{j}}$, where a smaller distance indicates higher similarity.

This procedure is summarized in Figure 2. At the start of each episode, a start state $s_{0}$ is sampled randomly from the set of start states in the dataset. The agent takes its first action $a_{0}$, to get the first pair $(s_{0},a_{0})$ and the $k$ nearest neighbors are found. This process continues until the agent reaches a terminal state, or the episode is cutoff and the agent teleported back to a start state. An overview of learning the KNN calibration model is given in Algorithm 3 and sampling the model in Algorithm 4.

There are several details worth mentioning in the algorithms. First, a KNN model relies heavily on an appropriate distance. For example, for input states that correspond to $(x,y)$ position, Euclidean distance can be a poor measure of similarity. If there is a wall in the environment, two states might be similar in Euclidean distance, but far in terms of reachability with notably different dynamics. We ameliorate this by learning a new representation—called a Laplace representation—$\psi(s)$ and using Euclidean distance in this new space that better reflects similarity in transition dynamics, as described in Section 5.2.

Second, there may be no similar pairs in the data for a given $(s,a)$. The state is one that is observed in the dataset, but the action may not be since it is selected by the agent running in the calibration model. When the next outcome state $s_{t+1}$ is chosen from $s_{t}$, the agent selects action $\tilde{a}_{t+1}$. The dataset might contain multiple transitions from states like $s_{t+1}$—including of course the transition that includes $s_{t+1}$—but these may be for only a subset of the actions. If none of these transitions uses $\tilde{a}_{t+1}$, then the dataset has insufficient coverage to infer what might occur when taking that action in the environment. When this occurs in Algorithm 4—when the closest point (minimum distance) is too far away (above a threshold)—we set the return to a default return and terminate the episode. We discuss an appropriate choice for this default return in Section 5.3.

Finally, we want to ensure that the model is efficient to query, even if we have a large dataset. For the discrete action setting, it is possible to get an $O(1)$ look-up by caching the nearest neighbors upfront. For $n$ datapoints, for each action we construct a table with $n$ rows and $k$ columns for the nearest neighbors, where each neighbor is stored as its index from 1 to $n$. Each transition consists of jumping between rows, using these indices. The detailed pseudocode is provided in Appendix A.1. More generally, for continuous actions, we can use a k-d tree (Bentley, 1975) to search for the k-nearest neighors. The k-d tree takes the transformed state-action pair, $(\psi(s),a)$ as the key for the search. For a dataset of size $n$, it costs $O(n\log n)$ to construct the k-d tree and $O(\log n)$ to query for a nearest neighbor. This low computational complexity is key to allow us to use all of the data to create our calibration model.

We can contrast this KNN calibration model to two natural alternatives: a kernel density estimator (KDE) model and a neural network model. A KDE model is a non-parametric estimator, that has even been investigated for model-based RL (Pan et al., 2018). Like our KNN calibration model, it should also stably remain within the region defined by the dataset. However, unlike the KNN calibration model, a KDE calibration model could produce non-existent states. It effectively interpolates between observed datapoints, and so results in significant generalization. If we consider again the example with $(x,y)$ position in a gridworld with walls, then the KDE calibration model could produce transitions within the wall.

Another alternative is to use a neural network (NN) to learn a calibration model. The dataset can be used to learn the expected next state and reward, for given a state and action, using regression on inputs $(s,a)$ and targets $(r,s^{\prime})$. Or, to obtain a distribution over next states and rewards, a conditional distribution can be learned using mixture density networks or stochastic networks. Such NN models can produce non-existent states, just like the KDE model. Worse, however, is that iteration under the NN model may not be stable. Several works in model-based RL have illustrated that iterating such models can produce less and less plausible outcomes states (Talvitie, 2017; Jafferjee et al., 2020; Abbas et al., 2020; Chelu et al., 2020).

Avoiding such issues is an active area of research, such as by training models to be correct over multiple steps of iteration (Talvitie, 2014; Venkatraman et al., 2015; Talvitie, 2017; Williams et al., 2017; Ke et al., 2019). For our Data2Online setting, this is difficult to use, because the number of steps of iteration is much larger than what is typically used in model-based RL. A model in model-based RL may be rolled out for 100 steps, whereas here it needs to be rolled out for the entire length of training. Though there is some work investigating learning neural networks that are guaranteed to be stable under iteration (Manek & Kolter, 2019), the approach requires a specialized architecture. We are hopeful that, with more research, NN models will become a viable choice for learning calibration models. We include NNs in our experiments, as a baseline.

It is not hard to imagine examples where Euclidean distance on states or observations does not appropriately reflect similarity of states. For example, in a maze environment, if inputs correspond to $(x,y)$, two nearby points in Euclidean distance may actually be on opposite sides of a wall, thus far apart in terms of transition dynamics. Similarly, Euclidean distance does not apply to images, since pixel-wise difference can make every image look very different from all the others in the dataset.

Instead, we exploit a standard approach in metric learning: we first map the inputs to a new space where Euclidean ($\ell_{2}$) distance is meaningful. In particular, we would like a new representation $\psi(s)$ where states $s_{i}$ and $s_{j}$ that have similar outcomes in terms of states and rewards are mapped to similar vectors $\psi(s_{i})\approx\psi(s_{j})$, and ones with dissimilar outcomes are mapped to different representations.

Such representations that reflect similarity in terms of transition dynamics have been explored under what are called Laplace representations (Wu et al., 2019a). The approach relies on having a stored trajectory that maintains the order of interaction. The objective includes two components: an attractive term that encourages two states that are nearby in the trajectory to have similar representations, and a repulsive term that encourages randomly sampled states to have different representations. For a neural network $\psi_{\theta}$ with parameters $\theta$, the last layer of the NN $\psi_{\theta}(s)$ has loss

The inclusion of representation norms $-\|\psi_{\theta}(s_{i})\|_{2}^{2}$ ensures that the representation is not simply decreased to zero to satisfy the first attractive term. Minimizing this objective encourages $\|\psi_{\theta}(s_{t})-\psi_{\theta}(s_{t+1})\|_{2}^{2}$ to be small for states right beside each other in the trajectory—temporally close. The second term $(\psi_{\theta}(s_{i})^{T}\psi_{\theta}(s_{j}))^{2}$ is the repulsive term that encourage random pairs to have orthogonal representations. It is possible for $s_{t},s_{t+1}$ to be randomly selected for the second term, but this is not that likely under the possible $n^{2}$ pairs; the first term dominates, ensuring these nearby points have similar representations. More details on learning the Laplace representation are given in Appendix A.1.1.

The distance for a state-action pair is defined differently for discrete and continuous actions. For discrete actions, two actions are considered similar only when they are exactly the same. The resulting distance is

In practice, we simply keep separate data structures for each action, to find nearest neighbors. For continuous action problems, the Laplace representation can actually be learned on $(s,a)$ directly, to obtain $\psi(s,a)$.

We do not require the dataset to have perfect state and action space coverage. We only query the KNN calibration model from states $s$ that are in the dataset, by construction. But, for a given action $a$, there may be no state-action pair that is similar to $(s,a)$ and so there is insufficient information about the outcome for that pair. What then should the model return?

A natural choice is to truncate the episode, provide a default return—as if the agent had managed to visit future states in the environment—and transition back to the start state. This synthetic interaction in the calibration model is inaccurate, so we encourage the agent to learn within the parts of the calibration model that meaningfully reflect the true environment and avoid these unknown areas. This suggests using a pessimistic default return. The default return can be set to the minimal return experienced in the dataset. When the agent reaches these unknown state-action pairs, it receives a low return and on the next episode is less likely to come back to this unknown state-action pair.

Pessimism has also been used in offline RL, but for a subtly different purpose than here. The goal of pessimism in offline RL is to avoid unknown areas, as it is unlikely for the fixed policy to be good in a region that it has never observed and further that unknown region may be dangerous. It is much safer to stay within the data distribution, and simply improve performance within that region.

For us, the policy can adapt online if it reaches unknown areas, so it is not necessary to ensure the agent avoids them in the environment. But, we avoid encouraging the agent to visit these unknown areas in the calibration model because they are not reflective of the true environment, potentially skewing hyperparameter selection. For example, if the agent was instead encouraged to visit these state-action pairs (using optimism), then it might find an unknown state-action pair and spend most of its time visiting it. The hyperparameters would be tuned to work well for this interaction, with short episodes and (default) Monte-carlo return from this state-action that do not require any bootstrapping. Our primary purpose with this choice, therefore, is to make interaction in the calibration model more similar to interaction in the environment, under the unavoidable limitations of insufficient data coverage.

In this experiment we investigate the benefits of our approach with different choices of model in two classic control environments. We compare our KNN calibration model with learned Laplace similarity metric to an NN model trained to predict the next state and reward given input state and action observed in the calibration data. In addition, we also test an NN calibration model that takes the Laplacian encoding (see Section 5) of the current state as input and predicts the next state and reward to provide the network with a better transition-aware input representation. We used two continuous state, discrete action, episodic deployment environments, Acrobot and Puddle World, as described in the appendix and in introductory texts (Sutton & Barto, 2018).

In this first experiment we select the hyperparameters for a linear softmax-policy Expected Sarsa agent (from here on, linear Sarsa) from data generated by a simple policy with good coverage. The agent uses tile coding to map the continuous state variables to binary feature vectors (see Sutton & Barto (Sutton & Barto, 2018) for a detailed discussion of tile coding). This on-policy, Sarsa agent learns quickly but is sensitive to several important hyperparameters. We investigate several dimensions of hyperparameters including the step-size and momentum parameters of the Adam optimizer, the temperature parameter of the policy, and the value function weight initialization. We choose these hyperparameters because their impact on performance is somewhat transient and can be overcome by continued learning; this reflects our desire for the agent to continually learn and adapt in deployment.

We used a near-optimal policy for each environment to collect data for building the calibration models. The near-optimal data collection policy for Acrobot can solve the task in 100 steps, and the near-optimal data collection policy in Puddle World achieves an average return of -25. In both cases the policy will provide the system with many examples of successful trajectories to the goal states in the 5000 transition data log.

Our evaluation pipeline involves several steps. First we evaluate the true performance (steps per episode for Acrobot and return per episode in Puddle World) of each hyperparameter combination in the deployment environment: running for 15,000 steps in Acrobot and 30,000 steps in Puddle World, averaging over 30 runs. We then use the data collection policy to generate the calibration data log and learn each model. We record the true performance of the selected hyperparameters to summarize the performance. This whole process—running the data collection policy to generate a data log, learning the calibration model, and evaluating the hyperparameters—is repeated 30 times (giving 30 datasets with 30 corresponding hyperparameter selections). The statistic of interest is the median and distribution of the true performance for the hyper-parameters selected across runs. In the ideal case, if there is one truly best set of hyperparameters, the system will choose those every time and the variance in true performance would be zero.

We also included two baselines. The first is randomly selecting hyperparameters, called Random, to get a sense of the spread in performance; all methods should outperform Random. We also include an Offline RL algorithm, called Fitted-Q Iteration (FQI) (Ernst et al., 2005), that learns a policy from the calibration data and then deploys the learned policy fixed in the deployment environment. For the FQI baseline we simply plot the distribution of performance of each of the 30 extracted policies on the deployment environment. For each policy, we average the performance over 30 random seeds. We tested FQI with a tile coded representation and a NN representation; the tile coded version performed best and we report that result.

Figure 3 summarizes the results. In both environments the KNN calibration model performed well, selecting the same hyperparameters as would a sweep directly in the deployment environment. The NN calibration models perform poorly overall. The NN calibration model using raw inputs (no Laplacian encoding) was not as effective, and so we only include results for the NN with the Laplacian encoding in Figure 3 and relegate the other to Appendix D.1. Their performance can be unstable, choosing hyperparameters with good performance in some runs, but often choosing poor hyperparameters. FQI generally performs worse than even Random. Note that we spent quite a bit of time improving FQI, as well as optimizing over several stepsize and regularization hyperparameters. This suggests the calibration data log is too limited to extract a good policy and deploy it without additional learning, but the data appears useful for selecting hyperparameters with the KNN calibration model.

We also used our approach to tune both step-size parameters of a linear Actor-critic agent with tile coding. The KNN calibration model was able to select top performing hyperparameters for Actor-critic in both Acrobot and Puddle World—though the agent performed worse than linear Sarsa (results in Appendix D.2).

The objective of this experiment was to evaluate the robustness of our approach to changing both the amount of offline data available and the quality of the policy used to collect the data. We experimented with three different policies corresponding to near-optimal, medium, and naive performance to collect 5000 transitions for training our KNN Laplacian calibration model. The near-optimal policy was identical to the one used in the previous experiment. The medium policy was designed to achieve roughly half the visits to goal states after 5000 steps (approximately 90 for Puddle World & 25 for Acrobot) compared to the near optimal policy. The naive policy was designed such that it achieved significantly fewer visits (approximately 35 for Puddle World & 12 for Acrobot). We also tried different data log sizes of 500, 1000, and 5000 samples using the medium policy, all shown in Figure 4.

The results in Figure 4 show that our approach is largely insensitive to data log size and policy in these classic environments. Even 500 transitions contains enough coverage of the state-space and successful terminations to produce a useful calibration model. This is in stark contrast to the FQI results in Experiment 1, where a policy trained offline from the same size data log failed to solve either task. Exploration in both these environments is not challenging; therefore, the success of the calibration model is not surprising. This positive outcome, however, reflects that it may be simpler to pick hyperparameters in some environments. In Experiment 4, we investigate a failure case in Cartpole.

Learning online is critical when we expect the environment to change. This can happen due to wear and tear on physical hardware, un-modelled seasonal changes, or the environment may appear non-stationary to the agent because the agent’s state representation does not model all aspects of the true state of the MDP. In this latter case it is often best to track rather than converge; to never stop learning (see (Sutton et al., 2007)). In our problem setting, the deployment environment could change significantly between (a) calibration data collection and (b) the deployment phase. Intuitively we would expect batch approaches that simply deploy a fixed policy learned from data to do poorly in such settings. The following experiment simulates such a scenario with the Acrobot environment.

The experiment involves two variants of the environment. As before, we collected 5000 transitions using the near-optimal policy in Acrobot and then applied our approach to select good hyperparameters for the linear Sarsa agent. Unlike before, we evaluate the hyperparameters selected on a second, changed Acrobot environment. In the changed Acrobot environment we doubled the length and mass of the first link length. Our two phase setup changes the dynamics of Acrobot but does not prevent learning reasonably good policies as you will see in the results below. This whole process was repeated 30 times (generating 30 datasets with a corresponding 30 calibration models) to aggregate the results presented in Figure 5.

We included three baselines to help contextualize the results: (1) transferring the policy from the first environment, (2) transferring the policy learned in the calibration model, and (3) FQI. The first baseline, called Sarsa (True), simply transfers the policy learned in the first Acrobot environment to the changed Acrobot environment (no calibration model was used, hence the label true). The second baseline, called Sarsa (Calibration) simply uses the best performing policy learned by Sarsa in our calibration model, where the calibration model is created with data from the first Acrobot environment. Finally, we also included a FQI baseline. We trained a policy using FQI with tile coding on the data generated from the first environment (the same data used to build the calibration model). Then we evaluated the policy learned by FQI on the changed Acrobot environment. These baselines are meant to illustrate how performance might be effected if the environment dynamics changed but a prelearned policy was applied without taking the changes into account, perhaps because no one noticed the environment had changed. In all three baselines the policy evaluated in the second environment is fixed (no learning in deployment).

The results in Figure 5 highlight that transferring fixed policies can be problematic when the environment changes. Our calibration-based approach performs best and appears robust under the abrupt non-stationarity tested here. Clearly, the difference between the two environments is significant enough such that transferring a policy directly learned on the first environment (the Sarsa-True baseline) performs worse than using our approach to select hyperparameters in the calibration model and then learning a new policy from scratch. Interestingly, learning and transferring a policy from the calibration model was worse than using than training on the first environment or training from the calibration data (as in FQI). It is not surprising that transferring hyperparameters and learning in deployment is more robust than transferring fixed policies, in these non-stationary settings.

Our approach is not robust to all environments and data collection schemes. In this section we investigate when it can fail. One obvious way our approach can fail is if the agent’s performance in the calibration model is always the same: no matter what hyperparameter we try, the system thinks they all perform similarly. To illustrate this phenomenon we use the Cartpole environment. In Cartpole, the agent must balance a pole in an unstable equilibrium as long as it can. If the cart reaches the end of the track or the pole reaches a critical angle, failure is inevitable. Near-optimal policies can balance the pole for hundreds of steps rarely experiencing failures and, thus, visit only a small fraction of the state-action space. A data log collected from the near-optimal policy would likely produce a calibration model where failures are impossible and all hyperparameters appear excellent.

We test this hypothesis by looking at three data collection policies. We used a random policy, a near-optimal policy with random initial pole angles, a medium policy that was half as good as the near-optimal policy (twice as many failures). We expect the random policy to provide useful data for the calibration model, whereas the near-optimal policy will cause failure due to the above reason. The interim policy helps understand sensitivity to this issue: we might expect the issue to be resolved with a less optimal policy.

Figure 6 indeed shows that the dynamics of Cartpole combined with particular data collection policies can render the calibration model ineffective We see in the left-hand plot that the hyperparameter chosen with the calibration model using random data performs somewhat reasonably, but fails for both the medium and near-optimal policies. Even with random starting states the calibration model for near-optimal policy: the calibration model never simulated dropping the pole. The random policy produced the best calibration model. Unsurprisingly, the random policy drops the pole every few steps and thus the log contained many failures and higher state coverage. Nevertheless, the performance was still poor because there were no examples of balancing the pole for many consecutive steps: the model constructed from random data was still a poor model of the true deployment environment.

We can see this further, by looking at the performance estimates under the three calibration models. The right-hand plot in Figure 6 shows the performance of all the hyperparameters according to the calibration model (before deployment). The blue dots show that most hyperparameters appear good in calibration when the model is constructed with data from a near-optimal policy. At the other extreme the grey dots show a large spread in performance of hyperparameters when the model is constructed with data from a the random policy. Note that none of the grey dots appear as low on the y-axis compared with the blue and orange dots corresponding to the other two policies. This indicates that calibration with the medium and near-optimal policy models incorrectly inflate the performance of many hyperparameter combinations, whereas calibration with the random-policy model potentially undervalues some hyperparameter combinations.

One could certainly argue that many applications might not exhibit this behavior—especially since it is largely caused by a task with two modes of operation (failing or balancing). Extracting a policy initialization from the calibration data (perhaps via behavior cloning) and then using this initial policy in both hyperparameter selection and deployment could avoid these problems in Cartpole, but we leave these experiments to future work. Regardless, this experiment provides an important reminder that we will not anticipate all situations in the deployment of RL in the real world; there is no general black-box strategy for deployment and failures will happen.

A variety of hyperparameter search approaches were introduced under sequential model-based optimization (SMBO) (Hutter et al., 2011), but methods built on Bayesian optimization (BO) (Snoek et al., 2012) have become more popular. Complementary to these approaches are those that direct computation to promising hyperparameters and stop performance evaluations of poor hyperparameters early, as in Hyperband (Li et al., 2018), or that design the algorithm to do both (Klein et al., 2017; Falkner et al., 2018). All these approaches attempt to find the maximum of the performance function, assuming that function is expensive to query.

BO algorithms approximate the performance function $f(\lambda)$, and use this approximation to decide what hyperparameter setting $\lambda$ to test next. The general approach is to (1) maintain a posterior distribution over the performance function $f$, (2) find a candidate set of optimal hyperparameters $\lambda_{c}$ according to a criteria like expected improvement under the current posterior over $f$, (3) evaluate $\lambda_{c}$, obtaining $y=f(\lambda_{c})$ and (4) update the posterior with sample $(\lambda_{c},y)$. Once the algorithm terminates—typically by reaching a time limit—the best $\lambda_{c}$ out of all the candidates tested is returned, according to the maximal $y$. The primary purpose of learning the posterior $f$ is to direct which $\lambda_{c}$ should be tested, though some algorithms do solve an optimization at the very end of this procedure to find $\lambda$ with the maximal posterior mean (see (Frazier, 2018) for a nice overview).

Due to the importance of hyperparameter optimization for machine learning—in a growing field called Auto ML—the development of BO methods has been focused on large numbers of hyperparameters, for training large models on large datasets. For this highly expensive setting, it is worth carefully crafting advanced algorithms that minimize the need to train and evaluate large models. These complex methods can then be released within packages, to facilitate their use, as they may be difficult to implement from scratch.

BO in our experiments: We use an open-source package (Nogueira, 2014–), which uses gaussian processes for optimizing the hyperparameter setting. We chose to use upper confidence bounds, with a confidence level of 2.576—the default in the package—as the acquisition method. The queue is initialized with 5 random samples and the algorithm is run for 200 iterations.

For our setting, each evaluation is not as complex and we need not use such advanced approaches. Instead, our primary goal is simply to answer: if we allow hyperparameters to be optimized over a continuous set, can we improve on a basic grid search? For this question, we also test two simple approaches: random search and the cross-entropy method (CEM). Random search involves simply testing a fixed number of hyperparameter settings, and selecting the one with maximal performance. Though simple, it is a common baseline because it has been shown to be competitive with more complex search strategies (Bergstra & Bengio, 2012).

CEM (Rubinstein, 1999) is an approach to global optimization of functions, like BO, but is based on a simpler strategy of (1) maintaining a distribution over the inputs (hyperparameters), (2) increasing the likelihood of the top percentile of sampled values under this distribution, according to the performance function. The distribution is simple to sample, and the percentile easy-to-compute, making this approach simpler to use than BO.

CEM has not been used for hyperparameter optimization, to the best of our knowledge. Likely the reason is that BO strategies provide a more powerful way to carefully reason about what candidate points to sample. CEM instead slowly narrows a distribution over hyperparameters, and does not reason about confidence intervals nor about a criterion (acquisition function) to identify ideal candidates. Nonetheless, we include it as a simpler strategy, to investigate performance of using calibration models with a hyperparameter search in-between naive random search and the more advanced BO search. We emphasize that it is not critical which hyperparameter optimization approach is used within our framework; any method can be swapped in.

CEM in our experiments: Our setting has two nuances compared to the typical setting where CEM is used: our function is expensive to query and we only get a stochastic sample. We provide a modified CEM algorithm, that still reflects the general framework for CEM, but using an incremental update—similar to stochastic gradient descent—to account for the stochasticity in our function query. The algorithm is summarized in Algorithm 13 in Appendix C.1.

In this section we compare grid search, random search, Bayesian optimization, and our simple CEM approach for hyperparameter selection. Are these approaches interchangeable in our setup? Does searching a continuous hyperparameter space result in performance gains and at what cost? The goal of the experiment is to highlight that alternative hyperparameter optimization approaches beyond a basic grid search are possible and to investigate if they are beneficial.

In this experiment, we use the same settings as above, but now optimize the temperature $\tau$ and stepsize $\alpha$ as continuous values in the ranges [0.0001, 5.0] and (0.0, 0.1] respectively for Acrobot, and [0.0001, 10.0] and [0.0, 1.0] respectively for Puddle World. The random search approach simply generates $k$ possible hyperparameters from the continuous ranges above and evaluates each in parallel in the calibration model. The best performing hyperparameters according to the calibration phase are used in deployment. Both random search and CEM use 100 iterations, to make computation used comparable to grid search, while Bayesian optimization uses 200 iterations.

Random search, Bayesian optimization and CEM outperform grid search, as we can see in Figure 7. The performance improvements are especially stark in Puddle World. Even when tuning only on the calibration model, the agent can outperform the best hyperparameters found by a grid search on the true environment. This is why the return for CEM is higher than the dotted line showing the performance of the best hyperparameters within the set used for the grid search. These results are promising, in that they show more carefully optimizing hyperparameters on the calibration model helps rather than hurts. A possible hypothesis, apriori, could have been that optimizing more carefully to the calibration model could cause odd or very poor hyperparameters to be chosen and that the restricted set in the grid search actually helped avoid this failure. These results suggest otherwise, and in fact highlight that our previous results could have been produced even more consistent performance with a smarter hyperparameter algorithm.

This experiments in this paper highlight the generality and flexibility of our approach. The calibration model can take different forms. Data collection can be done in a number of different ways. Hyperparameters can be systematically searched or optimized. In the end, numerous other specializations and algorithmic innovations could be included to further optimize performance in real deployment scenarios.