Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This work proposes a new path planning method PlaLaM, which is an extension of the LaMCTS algorithm.
The authors provide a novel regret analysis of adaptive region partitioning schemes. 

The authors demonstrate that the PlaLam method improves performance in toy 2D navigation tasks. The approach is also be applied to compiler phase ordering and molecular design achieving comparable performance to a solution based on proximal policy optimization at 4000 episodes.

The authors show comparisons to a number of baseline methods, but do not include a comparison the the LaMCTS method, which there approach is an extension of. I look forward to their explanation in the rebuttal.

Model-free RL and planning are my domains of expertise. Evolutionary algorithms are not, so please consider my review according.
main_review: Strengths:
1. The paper is well written, with clear and detailed explainations.
2. The authors provide a reference codebase which they plan to share with the community
3. The changes over the LaMCTS are clearly descrive in algoritm 1.


Weaknesses
1. The method seems an incremental improvement of the LaMCTS algorithm, is Neurips the most appropriate venue for such a work?
2. The method is comparable or outperformed by the PPO-4000 results, what advantage does this method have, sample efficiency?
3. For the 2D navigation problems, why not compare against a RL approach in addition to  ES?
4. In the all of the experiments, the authors do not include a comparison to LaMCTS, why is the comparison not possible?

Update: The authors answers my questions and addressed my main concern of a comparison with LaMCTS. Score raised to 7.

limitations_and_societal_impact: I am not sure why the authors do no include a comparison to LaMCTS, surely this is the most comparable method. I look forward to their explanation in the rebuttal.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper introduces the algorithm PlaLaM, which extends Latent Space Monte Carlo Tree Search (LaMCTS) for tasks ranging from generating paths for mazes, to finding molecular design. The authors explore the partition of LaMCTS, and provide theoretical evidence that lower-dimensional and smoother representations lead to lower regret.
main_review: Strengths:
The authors test their algorithm on a variety of synthetic and real world planning problems and provide better results with different baselines. The algorithm’s ability to plan in large state-space is one of the biggest strengths of this method. The authors also provide empirical evidence for their choice of design for choosing maximum as a measure of goodness, and data-driven partitions. 

Weaknesses:
The choice of the transformer function for the partition and sampling space seems arbitrary. For example, it is not clear why for the Maze3D environment an identity transformer was used for the sample space while for the MiniGrid environment a reversible flow model is used. 

Clarity:
The algorithm itself is very well explained, but it was hard to follow the various setups for the different experiments. 

Relation to Prior Work:
PlaLaM is built upon LaMCTS, but uses the maximum value rather than the mean for the measure of goodness for each partition. 

Additional Feedback:
- Visualization of the state space for the synthetic environments would be nice.
- More specifics or explanation about the results for Compiler Phase ordering can be provided since not all experiments have 61%-245% speedup.
- In figure 3, the goal location is reported incorrectly as a square

Update (after revision): Increasing score!

limitations_and_societal_impact: Limitations: design choices for different environments should be discussed.
Societal Impact: N/A
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper presents a black-box optimization method that efficiently searches the parameter by partitioning the parameter space using a latent space. The proposed method is built upon LaMCTS proposed by Wang et al. [2020]. This paper provides theoretical analysis of LaMCTS and proposed the modifications. The proposed algorithm, PlaLaM, was tested in synthetic tasks and real-world tasks, including compiler optimization and molecular design tasks. The proposed algorithm outperformed baseline algorithms in those experiments. 
main_review: Strong points:
-	Theoretical analysis of LaMCTS provides a better understanding of LaMCTS.
-	The proposed modification is grounded on the theoretical analysis.

Weak points:
-	Although the proposed algorithm PlaLaM outperformed well-known baseline methods such as CEM and CMA-ES, comparison with LaMCTS is not provided.

I think that the paper is overall well-written, and the theoretical analysis of LaMCTS is beneficial to the community. My main and only concern is that the proposed algorithm, PlaLaM is not compared with LaMCTS in the experiments, if I understand correctly. As the main contribution of the paper is analysis of LaMCTS and its modifications, the comparison between LaMCTS and PlaLaM is crucial to support the claims in the paper. 

I recommend authors to add ablation study to investigate the effect of the proposed modifications, e.g., evaluating PlaLaM with mean values like LaMCTS, PlaLaM without a latent model, and PlaLam with TuRBO instead of CMA-ES. If the ablation study is added, I'm happy to increase the score.

=== comments after the author response ===

The additional results provided by authors clearly demonstrate that how PlaLaM outperforms LaMCTS. I updated the score. 


limitations_and_societal_impact: Although the proposed method exhibits promising performance in this study, I do not think that the proposed method always outperforms CMA-ES because PlaLaM itself uses CMA-ES in its inner process. I recommend to clarify when to employ PlaLaM instead of CMA-ES and vice versa, which would be useful for practitioners.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper proposes a new path planning algorithm that extends an existing algorithm in two ways: a) using a latent space for dimensionality reduction b) using the maximum observed reward instead of the mean, which allows for faster convergence in deterministic environments. A theoretical analysis is provided to justify the latter modification.
main_review: The paper is good at establishing the ideas of space-partitioning, as well as the difference between adaptive and non-adaptive partitioning methods.

I must admit that I have difficulty following the theoretical analysis. Specifically the concept of $(z_k, c_k)$-dilution is not very clear to me. Perhaps an intuitive explanation would be helpful here.

The experiments section is quite extensive and covers a variety of settings. The proposed method performs favorably in each scenario.

That being said, I'm concerned with the baselines. I would have expected a comparison to La-MCTS, since it is the closest related work. The closest thing to a comparison to La-MCTS are the ablations on MiniWorld, where the mean is used instead of the max. That at least covers one of the two modifications proposed, but the other is missing (using a latent space for partitioning).

Another issue is that La-MCTS was originally tested on a different experiment suite, which has no overlap with the experiments in this paper. Since this paper is proposing modifications on top of La-MCTS, I believe that a comparison on at least some of the experiments of La-MCTS' original experiment section is necessary.

Overall I think the paper is promising and I strongly encourage the authors to continue this line of work. Unfortunately, I believe that the comparison to La-MCTS is currently not very clear, which is the main reason why I see this paper as "marginally above the threshold". I would definitely revise my opinion if the authors could address the following points:

* Provide a comparison to La-MCTS. If possible across the entire experiment suite in this paper.
* Compare to La-MCTS on some of the experiments that are in the experiments section of La-MCTS.

I think the paper would be a clear accept if these could be fulfilled and the comparison is generally in PlaLaM's favor.

**Other comments**

* The paper seems to focus on deterministic reward functions. I think it's worth discussing or at least mentioning this as a limitation, since taking the maximum might under-perform compared to the mean under stochastic rewards.

* The paper never explains what "periodic snapshots" are. I'm not familiar with this term. I think it should be introduced somewhere in the text.

**Edit following author response**

Given the favorable comparison to La-MCTS, I've increased my rating from 6 to 7. Thank you to the authors for providing such extensive additional results in a short time frame!
limitations_and_societal_impact: No concerns here.
review_title: null

Meta-review: The paper focuses on a black-box search approach to planning problems. The paper provides a theoretical analysis of an existing method in this space - La-MCTS - and suggests a modification of that method grounded in their analysis, resulting in a new approach called PlaLam. This analysis was valued by all reviewers and considered technically sound. And of course, planning problems are a relevant problem to the machine learning community.

Although the authors did compare their method to various method on a variety of planning problems, initially, it was unclear how the performance of the proposed 'PlaLam' modification compares to the original La-MCTS. This was brought up in review and was addressed by the authors in their reply. Other, minor, concerns of the reviewers were also satisfactorily addressed by the authors. 

The paper was considered to be well written.
Decision: Accept (Poster)