Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper proposes a method for Black-Box Optimization which incorporates the idea of UCT in sampling.
The proposed method, MCDescent, shows promising results in several benchmarks.

strengths_and_weaknesses: Strengths:
The idea is simple, and the algorithm is easy to understand.
Probably the implementation is also not complex.

Weaknesses:
The algorithm has eight hyperparameters, and their values vary for different benchmarks.
Also, there is no explanation about how they are tuned.
I would be happy to give the paper a better score if this weakness is solved.

---
Post rebuttal.
Thank you very much for the detailed comments on my concerns.
I changed my score.
questions: There should be a discussion focusing on the hyperparameters.
For example, if possible, I would like to see the following explanation.
1. How sensitive the performances are to the hyperparameters.
1. How the authors chose the values in Table 2.
1. Is there any guideline for tuning the hyperparameters?

Where is the definition of $C_d$?
I may have overlooked it, but I could not find it in the main material.
(It is mentioned in the supplementary as "weight of recent improvement.")

I think there are better citations for CMA-ES.
Please explain the reason if it is meaningful to cite this specific implementation.

This is not a question, but I would like to see Figure 1 of the appendix
in the main material if possible because it is very helpful for understanding the algorithm.
limitations: I could not think of any direct possibility of potential negative societal impact.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper focuses on the problem of Black-Box-Optimization, optimizing a function while only being able to sample its value at different points.  The authors propose a novel combination of building a tree to organize different regions that are being searched, and uses modifications of STP and TuRBO to optimize from a given point.  The entire method balances exploring new regions for more promising spots with exploiting and optimizing in a good spot.  Modified UCT is used to guide traversal of the tree, which also includes an option to create a new child at each node.  This overall method is experimentally evaluated in many settings and shown to be competitive with previous approaches, while surpassing their performance on many problems. 

strengths_and_weaknesses: Strengths: 
- I quite liked this paper and felt that its approach to combining MCTS with BO was unique and makes a very solid contribution. 
- The evaluation is thorough and complete and is very convincing as to the strengths of the proposed methods. 
- I appreciated the ablation studies that were done.  Overall the evaluation feels solid. 
- The paper is well-written and clear.  

Weaknesses: 
- The fact that the proposed methods are focused on deterministic functions wasn't made explicit until Line 216 on page 6, and later in the conclusion.  I think this would have been good to make clear from the very beginning. 
- The uncertainty regions in some of the results are very large.  Could more runs have been performed to bring down this uncertainty? 
- I am not sure that Figure 4 conveyed much meaning to me.  It was hard to understand the point you were trying to get across. 

Minor feedback: 
- Line 67-68 - This sentence doesn't make very much sense to me as written. 
- Line 122 - "... have similar values..." might better be: "... have more similar values..."
- Algorithm 1 - "GP.correlation lengh" seems like it should be "GP.correlation length" 
- Line 176 - "In the scene the ..." might sound better as "In the event that the ..."
- Line 227 - "...we create following ..." perhaps should be "...we create the following..."


questions: - On line 267 you state that some high dimensional spaces are inhospitable to descent approachs?  What are the characteristics of these inhospitable spaces? How can you tell if a space is inhospitable?

limitations: This was addressed to my satisfaction.
review_title: null

final_score: rating: 2: Strong Reject: For instance, a paper with major technical flaws, and/or poor evaluation, limited impact, poor reproducibility and mostly unaddressed ethical considerations.
review_content: summary: The paper considers optimization of deterministic black-box functions. The proposed algorithm combines Monte Carlo tree search with local descent/bayesian optimization. Empirical work shows elicits strong performance of the proposed method compared to various baselines on a diverse set of domains.
strengths_and_weaknesses: The article is poorly written, and often it is difficult to figure out the intention of the authors. For instance, in Algorithm 1, the index i is undefined and probably is different from the index i in (2), which probably is j in Alg.1. dy is also undefined in the algorithm, although (2) gives sufficient hint about it. Other variables are undefined as well, but familiarity with MCTS is sufficient to have a reasonable guess. The authors often inform us what the algorithm is not, instead of focusing on a clear description of the algorithm, and explaining the differences subsequently. 

Therefore, while the algorithm could be interesting, it is fairly difficult to evaluate the strength of it.

The empirical results seem to indicate that the proposed algorithm performs well. Some of the domain choices seem a bit strange for black-box optimization (why would we want to optimize a linear policy on a MuJoCo domain this way, and not a more complex policy by reinforcement learning?), but ultimately it is possible to use these domains as well for testing. 

-------------------------
After rebuttal:

I appreciate the effort of the authors to improve the paper according to the suggestions of the reviewers. I hope, it will become a better paper after a few more iterations.
questions: -
limitations: -
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper proposes a new MCTS-based optimization method that combines descent methods and BO. Different from LA-MCTS, the proposed MCDescent does not use partition due to the limitation of high-dimensional space and uses a set of unique mechanisms in the MCTS framework. Expeirments show the MCDescent can outperform baselines and sota black-box optimization methods.
strengths_and_weaknesses: Although the experimental results show the superior performance of the proposed method, I have the following concerns.

1. The novelty of the proposed method is limited. Authors may need to highlight the motivation and make it reasonable, explain in detail why you combine the two approaches.

2. The writing of this paper should be improved. For example,  Algorithm 1 should be rewritten for clarity, the notations used in the current version are very confusing and inconsistent.

3. More experiments should be done to test the sensitivity of the hyper-parameters in the MCDescent, e.g., $C_p$. 

4. The number of samples is too small for the RL tasks. Although the authors want to examine the performance of different algorithms under a limited number of evaluations, the too-small budgets lead to inferior performance, and the policy does not converge on some tasks. For example, in the Walker environment, the number of samples used in LA-MCTS paper is 40000. However, it is only 3000 in this paper. 

5. The authors said, " the performance of MCDescent may be limited in some high dimensional spaces that are inhospitable to descent
approaches". It is better to examine MCDescent on high-dimensional synthetic functions.

There are also some minor problems.

1. More references are needed, such as lines 34-35.

2. The experiments of Tree expansion and Optimization route can not be named "Ablation study."
questions: How does MCDescent compare to other methods in terms of running time? The author should discuss this and shows it in the experiments.
limitations: Yes.
review_title: null

Meta-review: metareview: This paper proposes a novel combination of Bayesian optimization and Monte Carlo Tree Search for more sample-efficient black-box optimization. The method is adding complexity, but the empirical results are thorough and show a clear benefit.

The reviewers on this paper did not come to unanimous decision, but the clear majority advocated for acceptance, and I concur, especially because reviewer 6Fro did not spell out their concerns with sufficient concreteness.
confidence: Less certain
Decision: Accept