Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper presents an extension of population based bandits (PB2) and the proposed method can handle both continuous variables and categorical variables at the same time. A new algorithm for parallel multi-armed bandits is also presented. The proposed hierarchical approach shows better empirical performance than other approaches. Authors also give theoretical results w.r.t. the cumulative regret bound. 
main_review: Jointly optimizing categorical and continuous parameters  is a very important problem.  I don't have much experience on RL, so the RL parts in this work will not be commented. 

advantages of this paper:
1. This paper is well-written. 
2. Empirical experiments are detailed and extensive.
3. Sound theoretical results are given w.r.t. the cumulative regret. 

limitations of this work:
1. The proposed PB2-Mult treats continuous parameters conditioned on different categorical variables are independent. It is equivalent to model Gaussian processes independently. However, the assumed independence usually doesn't hold in practice.  This explains why PB2-Mult performs best among all competing algorithms in Fig2 and it doesn't perform better than PB2-Mix in Fig3. For the synthetic function, the independence assumption is satisfied while in the RL experiments, possibility such an independence doesn't hold. See [1] for a possible solution, which is also a hierarchical approach and jointly models continuous and categorical variables. 
2. Maybe it is common in RL literature, I feel it is strange to use mean to measure performance instead of median in Fig 3 and Table2.  Median is a more common in BO  literature and is more robust. 


1.Ma, X., Blaschko, M.: Additive Tree-Structured Covariance Function for Conditional Parameter Spaces in Bayesian Optimization. In: International Conference on Artificial Intelligence and Statistics. pp. 1015–1025. PMLR (2020).


limitations_and_societal_impact: See the above review.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper extends the existing AutoRL algorithm, PB2, that was specifically designed to work with continuous hyperparameters by enabling it to efficiently search over both continuous and categorical hyperparameters of reinforcement learning solution methods. To do so, it first proposes a new multi-armed bandit algorithm called TV.EXP3.M (an extension of EXP3.M that varies with time) to select a subset of a given set of categories. Then, the paper incorporates this technique into the exploration stage of the PB2 algorithm to explore and select the categorical variables by taking into account the dependence of continuous variables on them. It takes two different approaches for modeling this dependency, one by incorporating it into the GP kernel and the other by filtering continuous variables based on the chosen categories that result in PB2-Mix and PB2-Mult algorithms. To evaluate the proposed algorithms, they first theoretically analyze PB2-Mult and TV.EXP3.M algorithm by showing they have cumulative regret bound and sublinear regret bound respectively. Then, they empirically evaluate their techniques along with PBT and original PB2 as the baselines on a toy environment and seven Procgen games and show that PB2-Mix achieves a similar or better performance compared to other baselines on these environments. 
main_review: This is an interesting paper and the proposed contributions seem useful for the RL community. However, there are some issues with the work that preclude acceptance in the current form. To elaborate, (1) there are many missing details in the paper and weakly supported claims that make it hard to understand the paper and proposed techniques, and (2) the empirical study done in the paper fails to justify the stated contributions.

Detailed comments below: 

There are some claims in the paper that needs further clarification. “As a result, many lauded approaches are impossible to reproduce without the vast resources required to sweep through hundreds or thousands of possible configurations [6].” The cited paper, [6], proposes an AutoML algorithm specifically designed to solve computer vision problems and not a reinforcement learning (RL) algorithm. This is happening while the main topic of the paragraph is about the practicality of RL techniques. This claim needs further justification. 

The main claim of the paper is that the proposed algorithms enable the search over the space of categorical variables. Nevertheless, TV.EXP3.M seems to only consider selecting categorical variables that are binary. In another word, it can select whether a certain operation will be part of the algorithm or not. This observation is further supported by the hyperparameter search space that has been chosen for the categorical hyperparameters that are selecting a subset of different data augmentation operations. It is possible that I couldn’t understand this part really well, so I ask the following question. Is it possible to search over different data augmentations and optimizers using the proposed technique? If so, please describe how you would do it using the TV.EXP3.M algorithm. In this setting, you only get to select one optimizer out of n optimizers in your search space. But, it seems that TV.EXP3.M would select a subset of optimizers by taking multiple arms and this problem is not addressed in the paper.

In algorithms 2 and 5, it is not clear how the output of this algorithm, D_t, is chosen. It is not mentioned in the algorithms’ procedure, but it suddenly appears as output. Also, whereas this output is denoted by D_t in these algorithms, it is denoted by A_t in equation 4. Is there a reason for this notational difference here? Also, the style of “D” (D_{t-1}) used in equation 4 and the one in the output of Algorithm 4 (D_t) is different. Are they refer to different collections or datasets? Furthermore, there are not enough details about Algorithm 3 in the paper to understand how the filtering dataset procedure takes place. This part needs further explanation. “For the exploit step, the weights of the bottom agents are replaced by those from a randomly sampled agent from the set of best-performing agents, in what is called truncation selection.” The truncation selection procedure is not mentioned in the paper and there is not talk about its hyperparameters in the paper. Does this technique use any hyperparameter, such as the number of bottom agents that their weights should be replaced?


The experiments done in the paper do not fully support the stated contributions. In the abstract, it is mentioned: “where we show that explicitly modeling dependence between data augmentation and other hyperparameters improves generalization.” However, there is no baseline in the paper that uses TV.EXP3.M algorithm for selecting categories without modeling the dependence between continuous and categorical variables. In another part, it is stated “Despite using a small population size, we are able to train policies that match or outperform state-of-the-art methods which used a much larger grid search.” However, the evidence in the paper does not support this claim because the comparison with the UCB-DrAC algorithm in Table 2 is not justified. As is shown in Table 2, the proposed techniques in the paper and the UCB-DrAC algorithm have a highly similar performance to PB2-Mix and PB2-Mult, by their standard deviations overlapping each other in most of the environments. Also, based on the citation [21] in the paper, only 5 seeds for deep RL algorithms do not necessarily result in statistically significant results. So, to make a better comparison, the number of seeds needs to be increased. 


Finally, this is a list of questions that need to be answered about the empirical study:
1. What is the value of \omega (in the equation on page 4) in your experiments? Also, how much your algorithm is sensitive to this hyperparameter?
2. A lot of new modules have been added to PB2 and eventually your algorithm to do AutoRL makes the original algorithm more computationally expensive. For instance, the computational cost of the gradient-based optimization approach that you take to optimize the GP hyperparameters can increase by the number of points in the training set. So, I wonder whether have you done any study to show how much computational cost these new modules add to the original algorithm that in this case is PPO?
3. Why this specific hyperparameter search space has been chosen for the empirical study? There are only four continuous hyperparameters in the paper, while there the used algorithm has much more hyperparameters to tune such as \beta_1 and \beta_2 for Adam optimizer. So, a better question would be: how does this algorithm scale as the number of hyperparameters increases?
4. What model is used in the paper to run the experiments and what specific hyperparameters have been used for training this model? The details of the neural architecture and Adam optimizer’s parameters are missing, such as the value of \beta_1 and the number of layers.


Minor comments:
1. Thus, if it wasn’t enough that PPO -> Thus, if it was not enough that PPO (Line 115)
2. Notation inconsistency in line 155: r_t is getting x_t as input while in line 153 it is defined without any input. So, replacing r_t to r_t(x_t) can clarify it here.
3. Line 90: “provides the agent with an observation s_t” -> “provides the agent with a state s_t”
4. Line 104: for a previous policy -> for the behavior policy. It is good to also add a brief definition of behavior policy such as the policy used to gather the data.
5. Line 259: PB2-R -> PB2-Rand
5. The name of the paper does not reflect the content of the paper and requires modification: “Tuning Mixed Input Hyperparameters on the Fly for Efficient Population Based AutoRL”. Based on the current name, it seems that the hyperparameter selection is designed for the AutoRL algorithm while it is an AutoRL algorithm that is designed for tuning the parameters of the RL algorithm.


limitations_and_societal_impact: The paper stated its limitations in section 6.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper presents a population-based approach for learning hyperparameter schedules on the fly. Its contribution to the field is to allow both continuous and categorical variables to be optimized in a non-random way.
main_review: ### Overview

I had trouble understanding the paper, in part due to my background (no prior experience with PPO and PB2), but I’ve provided some suggestions that I believe would have helped with my understanding. 

The justification for where this method fits among other population-based methods was clear and at a very high level the theory seemed like a great advancement, but most of the theory was in the appendix, which I didn’t review. 

The empirical evidence was not great. I’m not convinced the performance was meaningfully different between the baseline and the two new methods. The theory might justify the poor performance, but I didn’t assess the theory in detail.

### Major

* The new approaches (PB2-Mult and PB2-Mix) were both within 1 standard deviation of the baseline (PB2-Rand) according to Table 2. The PB2-Mix improvement was statistically significant (line 298), but the p-value was a barely acceptable 0.044 (i.e. if PB2-Mix was equal to the baseline, we’d see a difference as large as this once every 23 times we ran the experiment). Furthermore, if a p-value is being used to consider significance, it is often scaled by the number of comparisons done (i.e. two: PB2-Mult and PB2-Mix), which would put this above the significance threshold.

### Clarity

* Lines 134–136 consider a *convex* hyperparameter space. Why is this assumption being made? This seems like a very strong assumption I’d like to see defended (even if just to say this is the assumption made by prior work, e.g. PBT).
* Figure 1 (near line 140) was not helpful to me. I'm not sure exactly how to improve it, but I think I would have appreciated seeing the entire pipeline of hyperparameter selection and evaluation. (Perhaps familiarity with the background, such as the Procgen protocol mentioned in line 286–287, would obviate this.)
* I didn’t find algorithm 2 (near line 198) to provide the right amount of high-level detail. I had to go to the appendix because on its own, Alg2 didn’t give me enough understanding. For example, I thought “normalize $\omega$” might be a simple [0,1] normalization, but it’s a more complex scaling that ensures no $\omega_c$ is larger than $\eta$ percent of the sum of weights. Perhaps indicate that $\eta$ is used as a scaling factor? Alg2 doesn’t indicate what $\eta$ is used for.
* I suggest wording line 198 as “Algorithm 5 *in* Sec. D.1” to indicate that Alg5 is in the appendix. I assumed Algorithm 5 was coming later in the paper after this high-level summary.

### Minor (typos and improved phrasing)

Some of these points are trivial, but you might find them helpful...
* Some acronyms were undefined. E.g. GP was used on lines 7, 42, 71, and 133 before finally being defined on line 158. DrAC on line 272 was never defined.
* Some hyphens were missing. Consider reading about how to [hyphenate compound adjectives](https://www.grammarly.com/blog/hyphen/). E.g. I suggest “population-based AutoRL”, “time-varying problem”, “high-level summary”, and “code-level hyperparameters”.
* Line 75 discusses data augmentation as a categorical variable. I’d have appreciated a couple of examples or a bit more background here.
* Line 100 says PPO is “one of the most widely used RL algorithms”. Compared to what? Sarsa? If “one of the most widely used” changes to “a widely used”, I can’t argue anymore and I won’t ask for a citation. :D 
* Line 104 says “As can be seen,” but so far the paper has only pointed out one hyperparameter ($\epsilon$), so maybe delete that phrase.
* Line 106 would be more clear as “there is also often another hyperparameter, $\lambda$, in the advantage function [60].” (As written, it implied that $\lambda$ is the advantage function.)
* Lines 107–108: it’s unclear to me whether the “recent study” and the “recent work” referenced here are the same work or a different one. Since there’s only one citation [17], I think they both refer to the same study? Either the phrasing should be improved or this sentence needs another citation.
* On line 114, “they” should be deleted.
* Lines 114–115 refers to methods (plural), but only one citation [51] is provided.
limitations_and_societal_impact: There's an acknowledgement of limitations (i.e. that the performance wasn't that great).

Societal Impact: N/A
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper extends PB2 to allow for categorical hyperparameters in two different ways (direct integration into the kernel or two-step exploration depending on categorical choices). The authors show regret and convergence properties similar to PB2. In their evaluations, they show the benefits of integrating categorical hyperparameters by tuning the data augmentation alongside agent hyperparameters.
main_review: This is a well-written and technically sound paper extending an existing promising approach in hyperparameter optimization in RL. Incorporating categorical hyperparameters into PB2 in a way that allows for optimization with regards to dependencies between categorical and continuous variables will increase the utility of the algorithm and be of interest to its users. The paper gives the core insights into the extensions, mostly through its experiments which focus on the ProcGen benchmark. On one hand, this shows the improvements in a very challenging setting within RL. On the other, its computational expense leads to a less thorough exploration of the research questions. Overall an interesting addition.

## Novelty
The paper extends an existing approach in an important and useful way.

## Significance / Impact
PB methods are an important approach for hyperparameter optimization in AutoRL, so this will be very useful and probably have a large impact for existing users of automated HPO methods in RL (especially since it will also be integrated into Ray). The impact on the research community overall depends on how well AutoRL methods in general will be adopted.

I wonder a bit about the limited scope to AutoRL. PB2 and this extension could also be very well applied to other continuous adaptation problems, right? I think it would make the paper stronger and increase its impact outside of RL, if the authors could show the generic applicability to many problems and not only AutoRL.

## Soundness (method and experimental setup)
The authors use a very thorough setup for the toy example, but time constraints of course limit this on ProcGen. Still, 5 repetitions are an acceptable compromise and including the PB2 results without reruns is a fine trade-off in this case. 

The research questions are interesting, relevant to the method and answered well for the most part. I’m only a bit disappointed in the scaling study since it does not show how well it would perform with different population sizes. This could have been done on a different benchmark than ProcGen if time constraints were the deciding factor, maybe by reducing the number of ProcGen games used by one or two. That would have given the research questions beside improved performance more space.

As the paper extends PB2, it addresses points like the regret bounds of that paper as it should. Overall, the experiments are done soundly and answer the most important questions of this extension. A comparison to similar non-population-based methods (especially CoCaBO) would have been nice, but given the computational budget it is understandable the authors chose not to include any.

## Clarity
The authors used a clear language; critical points are addressed straightforwardly (e.g. details of the experiments) and the visuals help with understanding. Background is sufficiently explained to researchers familiar with RL methods. Overall very good.

## Minor Comments

* For Table 1, I wondered whether it is important in practice whether it is population-based or not. I think this is not as important as whether the methods are efficient on categorical and continuous spaces. If the authors think there is a relevant difference, the text should reflect that and explicitly mention why e.g. CaCoBO suffers from not being population-based.
* Similarly, in the discussion it is stated that the paper makes a strong case for population-based methods specifically. I don’t really see how this is true as there is no comparison to other HPO methods or a strong demonstration that dynamic hyperparameter settings are important on ProcGen. In fact, UCB-DrAC is very close to the PB2 extensions in performance. So I would argue the results are more indicative of the extensions improving over vanilla PB2 and PBT-style training being a viable option on ProcGen rather than making a case for it over any others.
* Sometimes the authors call s_t a state and sometimes an observation. Should be consistent.
* I wouldn’t call reward scaling an implementation detail as it can decide whether an agent can learn efficiently or not (Section 3.2)
* What is meant by “combinatorially large search space”? If the space includes continuous hyperparameters, it is infinitely large anyway.
* I think that it is very unfortunate to call the compact, convex subset $\mathcal{D}$ which is typically used for datasets. This confused me at first.
* Since $r$ is normally used for the reward in RL, I would propose to use $\rho$ for the regret to not confuse readers.

## Questions for Rebuttal

* Eq 3: Is it possible to also use other acquisition functions (such as EI) instead of LCB?
* Section 6.1: The synthetic benchmark was not quite clear to me since it seems that h_t^b does not really depend on t and therefore, there is no real advantage to use PBT/PB2 over other HPO approaches
* Section 6.2. Why have you chosen a linear regression model? Is it a reasonable assumption that a linear model can fit the data well?
limitations_and_societal_impact: Yes, adequately addressed in view of that the paper deals with a meta-problem and not with a specific application.
review_title: null

Meta-review: There was extensive discussion between the authors and reviewers, and amongst the reviewers privately. Many concerns were raised, and largely addressed. This is particularly the case with the number of runs and statistical significance, which is a concern that has largely been allayed.

The primary remaining concern is simply in the simplicity of the BO (Bayesian optimization) results. An expert in BO assessed the BO theory to be relatively solid, but not particularly exciting in the BO literature. The claims about novelty for addressing both categorial and continuous variables is a bit overstated, considering there are several works that already address this problem in BO (that can be used here). This work extends an existing algorithm, developed for the RL setting, that only works for continuous hyperparameters, so the contribution is placed relative to that. But, the limitation of this previous approach does not imply that these existing BO algorithms could not have already been applied to RL to solve this issue of mixed hyperparameters. This claim on the technical novelty should be clarified, especially given that there appears to be more effective BO algorithms for mixed hyperparameters. 

Additionally, the work begins by highlighting the importance of making RL more usable in practice. But, the work focuses on the setting where you can have populations of agents learning in parallel. The primary setting where it is feasible to train many agents in parallel is in simulation. Many real-world RL settings are restricted to a single stream of experience. This contrasts AutoML, which is typically done on a dataset, and so many hyperparameters can be tested. In RL, it is often not feasible to test many hyperparameters, except (a) in experiments to better understand our algorithms (not a deployment setting) and (b) learning in simulators (a useful but relatively restricted setting). The paper should better place the problem setting for which you are developing AutoRL algorithms. This statement may seem to be more generally about AutoRL (where many papers do not do this); but we are here to discuss and improve this paper, and clarity of problem setting is critical. 

Decision: Accept (Poster)