Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper introduces GIBO, a modification of Bayesian Optimization (BO) that performs local policy search. Compared to classic BO, the strengths of this method are that it does not require storing all the past data points, making it more computational efficient, and that it is more stable when moving to higher dimensional problems. The authors compare their method with standard BO and Augmented Random Search, an approach based on finite difference policy search.
main_review: 
I found the paper well written and easy to follow. The authors related their method to previous approaches using BO for Reinforcement Learning. Since the experiments compare GIBO with CMA-ES and ARS, I would have expected to see a discussion about the similarities and differences with other evolutionary approaches.  Another method that is closely related is Parameter-based Value Functions [1], which directly tries to estimate $J(\theta)$ using a deterministic function. They also include a comparison with ARS using linear and nonlinear policies. 
Besides the related work section that could be improved, there are some main issues that prevents acceptance:

- Section 3.3 presents many improvements on the basic idea of GIBO, but there are no ablations in the paper supporting these additions. Is also Vanilla BO using these improvements? Ablating these components in GIBO and Vanilla BO seems necessary here to understand why the proposed method can be considered as an improvement

- One main claim in the paper is that it has low variance compare with other methods (ARS). However, in the experimental evaluation, only 3 trails are used for each environment. I would expect to see at least 10 or 20 runs, especially in these relatively small tasks involving very low dimensional linear policies. Using 3 runs is not enough to assess if the variances are really difference. 
 
- I am a bit concerned about the hyperparameters for GIBO in Table 3. How were these chosen? Are the 3 runs in Figure 6 using different seeds with respect to those that found when optimizing the hyperparameters?

If the authors can expand their related work section and solve the main concerns in the experimental section, I am willing to increase the score for this submission.

[1] Francesco Faccio, Louis Kirsch, and Jurgen Schmidhuber. Parameter-based value functions. In ¨ Int. Conf. on Learning Representations (ICLR), Virtual only, May 2021.

------------------------------------------------------------------------------------------------------------------------------------------------------------
Edit post-rebuttal: The authors clarified my concerns
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper concerns the high sample complexity of policy gradient methods and the computational complexity of Bayesian optimization. The authors propose a novel algorithm called GIBO (and its local variants) to minimize uncertainty in gradient estimation. Experiments are conducted and compared with some naive baselines.
main_review: Originality and significance:
The idea itself is interesting. However, the contributions and improvements over GP algorithms are unknown. See detailed comments below.

Clarity:
The paper has clear structures and is easy to follow.

Detailed comments:

1. The authors claim that BO methods have been restricted to low-dimensional problems. But there are modern Bayesian RL algorithms that are both theoretically grounded and verified experimentally in high-dimensional tasks such as Mujoco [1]. It's thus not clear the contributions of this work.

2. The experiments are conducted and compared with only very simple baselines. Since the paper aims to address the drawbacks of policy gradient with random perturbations algorithms and BO algorithms, it will be more convincing to compare with more SOTA methods in these two areas.

3. In Fig. 3, it seems that the curves are not converging in the plots. So the improvements of GIBO are not clear.


[1] Sebastian Curi et al. Efficient Model-Based Reinforcement Learning through Optimistic Policy Search and Planning. NeurIPS 2020.

limitations_and_societal_impact: The authors state the limitations of their algorithms that rely on prior knowledge of the objective. Negative social impacts are also listed in the paper.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: In this paper, the authors propose a new acquisition function for Bayesian optimization based on gradient information. A GP model estimates the Jacobian and its estimation is used for gradient update. This method is implemented in the setting of policy search for reinforcement learning. Empirical evaluations are provided for a synthetic setting, LQR and MuJoCo gym environments.
main_review: Post-rebuttal comments: thanks for providing a detailed response. I still think the comparison with [1] is valuable. Or as the authors mentioned, demonstrate how GIBO can be used in conjunction with [1]. As a result, I will keep my score.

Originality: I really like the perspective the authors have taken to connect policy search with Bayesian optimization. The acquisition function based on uncertainty reduction on gradient is novel and fits the use case quite well. 

The related work section is comprehensive. I would like to draw the authors’ attention to the following paper [1] Learning Search Space Partition for Black-box Optimization using Monte Carlo Tree Search, Linnan Wang, Rodrigo Fonseca, Yuandong Tian, NeurIPS 2020, which also considers a blackbox setting for policy search. 

Quality: The paper is technically sound. I have some technical questions on the algorithm. 
1. Can the authors provide more details on how the optimization for equation (7) is done? The appendix mentioned Cholesky factorization to model K(\hat{X}, \hat{X}) but it is unclear to me how the whole equation is optimized. Were you able to compute the gradient analytically and perform gradient descent?

2. Notation-wise, should the \theta_t in equation (7) be \theta_n instead since \hat{X} indicates that n different thetas have been queries?

3. In section 3.3 for the uncertainty threshold, the Sigma’s are matrices, what does it mean to bound the difference between two matrices with a scalar \epsilon?

4. On the hyperparameters in section 3.3, e.g., the bound (\delta) and the threshold (\epsilon), how sensitive is the performance of the GIBO algorithm to them?

5. Can you include error bars for the experiment in section 4.1?

Clarity:This paper is well-written and easy to read. Good job! 

Significance: I enjoy the novelty of this paper. However, I think the significance can be improved by improving the empirical section. Comparison with [1] should be included as it is competitive with ARS on Swimmer and Hopper for MuJoCo. 

Moreover, I would like to know if it is possible to consider higher dimensional environments, such as the humanoid. Is there a potential scalability issue with the proposed method?
limitations_and_societal_impact: The potential scalability limitation needs more discussion.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper modifies the standard BayesOpt pipeline in 2 ways:

1. Defines a new acquisition function, the "Gradient Information" (GI) which is the reduction in the variance of the Jacobian variance of $J$.
2. Exploration and Exploitation become disjointed: During the BayesOpt process, a batch of $M$ queries are made via argmax of the GI acquisition, purely for exploration (rather than a mix of exploitation and exploration as is standard in BayesOpt), with the goal of producing a final gradient update step $\nabla_{\theta}J$. 

This defines a "GIBO" algorithm, which is then experimentally evaluated over the following benchmarks: 

1. Sampled functions from GP's
2. LQR Controllers
3. Linear controllers for standard Mujoco tasks.

which show that GIBO outperforms previous ES/ARS and standard BayesOpt methods especially in high dimensional settings, most likely due to the use of "local search"/gradients.
main_review: Pros:
1. I overall think this is a promising and good paper, with many potential future directions in BayesOpt + ES/RL research, especially due to its strengths on high dimensional optimization.
2. In some sense, the method can be seen as a way of "intelligently" picking a batch of neighborhood points to form a gradient, rather than e.g. simply via sampling perturbations from an Isotropic Gaussian (as is standard in ARS/ES methods).
3. Paper is well-written, and well-understandable in general for someone familiar with BayesOpt methods.

Questions/Cons:
1. I'm assuming that because the acquisition function is based on the variance of the Jacobian at the "current" point $\theta_{t}$, this means that future argmax query points in the batch would likely be very close to $\theta_{t}$ right? (Since local information around $\theta_{t}$ probably contributes more to the gradient estimation at $\theta_{t}$). I believe that this could potentially cause problems with global exploration / have the same issues with gradient estimation methods converging too fast to local minima.
2. Citation requests: You may want to cite/compare e.g. [1] (which uses a k-DPP to maintain unbiased gradient estimation in ES, but reduce variance and improve exploration) and other related "manual" methods on improving the variance of ES gradient estimation. Similar to the previous point as well: how "exploratory" are the queries really, when optimizing the GI acquisition?
3. How well does GIBO perform in the basic neural network policy setting (where there will be ~200-1000 parameters from a e.g. 2-layer MLP)? Such scenarios are still quite common even in ES + RL methods (e.g. A nonlinear network is needed for training on Pendulum with ES from my experience; a linear policy doesn't always work)
4. How parallelizable is the method, especially with the $M$ batch query section? A major benefit of ARS/ES is that they can be parallelized with an arbitrary number of workers, (analogous to "$M$"), but it seems like the dataset update $\mathcal{D} \leftarrow  (\theta,y) $ forces sequentiality. Could this be moved outside of the batch-for-loop? 

[1] Structured Monte Carlo Sampling for Nonisotropic Distributions via Determinantal Point Processes 

Small notation issues:
* In Algorithm 1, $m$ is already used as a variable denoting the mean function before; perhaps change it for clarity.
limitations_and_societal_impact: Yes
review_title: null

Meta-review: The reviewers appreciate the novelty of the main contribution of the paper, ie the acquisition function defined as reduction in gradient variance under a GP model. The paper could be strengthened further by applying the proposed method to higher-dimensional problems.
Nevertheless, the paper is acceptance.
Decision: Accept (Poster)