Learning Space Partitions for Path Planning
Authors: Kevin Yang
Tianjun Zhang
Chris Cummins
Brandon Cui
Benoit Steiner
Linnan Wang
Joseph E. Gonzalez
Dan Klein
Yuandong Tian
Venue: NeurIPS 2021 Poster (2021)
Keywords: Search
Path Planning
Optimization

Abstract: Path planning, the problem of efficiently discovering high-reward trajectories, often requires optimizing a high-dimensional and multimodal reward function. Popular approaches like CEM and CMA-ES greedily focus on promising regions of the search space and may get trapped in local maxima. DOO and VOOT balance exploration and exploitation, but use space partitioning strategies independent of the reward function to be optimized. Recently, LaMCTS empirically learns to partition the search space in a reward-sensitive manner for black-box optimization. In this paper, we develop a novel formal regret analysis for when and why such an adaptive region partitioning scheme works. We also propose a new path planning method LaP3 which improves the function value estimation within each sub-region, and uses a latent representation of the search space. Empirically, LaP3 outperforms existing path planning methods in 2D navigation tasks, especially in the presence of difficult-to-escape local optima, and shows benefits when plugged into the planning components of model-based RL such as PETS. These gains transfer to highly multimodal real-world tasks, where we outperform strong baselines in compiler phase ordering by up to 39% on average across 9 tasks, and in molecular design by up to 0.4 on properties on a 0-1 scale. Code is available at https://github.com/yangkevin2/neurips2021-lap3.

Learning Space Partitions for Path Planning
Kevin Yang
Tianjun Zhang Chris Cummins Brandon Cui
Benoit Steiner?
Linnan Wang² Joseph E. Gonzalez' Dan Klein' Yuandong Tian?
'UC Berkeley FFacebook AI Research BBrown University
[yangk, tianjunz, sianjunz,jegonzze jegonzal beerneeer edu {cummins, bcui, benoitsteiner yuandong) (raandong@@fbb.. @fb. linnan, waihaanwan@bboonn.c.
Abstract
Path planning, the problem of efficiently discovering high-reward trajectories, often requires optimizing high- nigh-dimensional and multimodal reward function. Pop- ular approaches like CEM (37] and CMA-ES [16] greedily focus on promising regions of the search space and may get trapped in local maxima. DOO [3] and VOOT 12 balance exploration and exploitation, but use space partitioning strate- gies independent of the reward function to be optimized. Recently, LaMCTS [45] empirically learns to partition the search space in seward-sensitiv manner for black-box optimization.
this paper, we develop a novel formal regret analysis for when and why such an adaptive region partitioning scheme works. We also propose a new path planning method LaP which improves the function value estimation within each sub-region, and uses latent representation of the search space. Empir- ically, LaP$ outperforms existing path planning methods in 2D navigation tasks, especially in the presence of difficult-to-esapp local optima, and shows benefits when plugged into the planning components model-based RL such as PETS [7]. These gains transfer to highly multimodal real-world tasks, where strong baselines in compiler phase ordering by up to 39% on average across tasks, and in molecular design by up to 0.4 properties 0-1 scale. Code is available at hhttps://gitien
outperform
Introduction
Path planning has been used extensively in many applications, ranging from reinforcement learning 7
13 [4] and roboties (7 35 26 to biology (24) chemistry [40). material design [2I], and compiler optimization [42). The goal is to find the most rewarding trajectory (i.e., state-action sequence)
x (80, dg ,1,..., 8n.) the search space Ω: x" = arg maxxen / (x), where f(x) is the reward.
In this work, we focus on deterministic path planning problems with long trajectories x, and dis- continuous and/or multimodal reward functions f. Such high-ddmensional non-convex optimization problems exist in many real domains, both continuous and discrete. While we could always find near- optimal x by random sampling given an infinite query budget, practice we prefer sample-efficient method that achieves high-reward trajectories with fewer queries of the reward function f.
While global methods like Bayesian Optimization (BO) may struggle with limited samples and high-dimensional spaces, classic approaches like CEM 37 and CMA-ES [16] learn a local model around promising trajectories. For example, CEM tracks population of trajectories and repeatedly re- samples its population according to the nighest-performing trajectories from the previous generation. On the other hand, such focus can trap CEM in local optima, as confirmed empirically (Sec. 5)
Other recent approaches, such as VOOT [22 and DOO [31] use a (recursive) region partitioning scheme: they split the search space Ω into sub-regions Ω Ω U... Usg then invest more samples into promising sub-regions while continuing to explore other regions via an upper confidence bound
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

(UCB). While such pegloration-epplotaaaii procedures adaptively focus on promising sub sub-regions and lead to sub-linear regret and optimality guarantees, their region partition procedure manually designed by humans and remains non-adaptive. For example, DOO partitions the space with uniform axis-aligned grids and VOOT with Voronoi cells, both independent of the reward f to be optimized.
Recendly Wang et al. proposed LaNAS [46] and LaMCTS [45], which adaptively partition the search regions based on sampled function values, and focus on good regions. They achieve strong empirical performance on Neural Architecture Search (NAS) and black-box optimization, outperforming many existing methods including evolutionary algorithms and BO. Notably, recent NeurlPS' 20 black-box optimization challenges, two teams that use variants of LaMCTS ranked 3rd (38 and 8th [23).
In this paper, provide simple theoretical amalysis of LaMCTS to reveal the underlying principles of adaptive region partitioning, an analysis missing in the original work. Based on this analysis, propose Latent Space Partitions for Path Planning (LaP*), novel optimization technique for path-planning. Unlike LaMCTS, LaP uses a latent representation of the search space. Additionally, we use the maximum (instead of the mean) as the node score to improve sample efficiency, verified empirically in Sec. 5.3 Both changes are motivated by our theoretical analysis.
We verify LaP* on several challenging path-planning tasks, including 2D navigation environments from past work with difficult-to eoffccee local optima, and real-world planning problems in compiler optimization and molecular design. In all tasks, LaP* demonstrates substantially stronger exploration ability to escape from local optima compared to several baselines including CEM, CMA-ES and VOOT. On compiler phase ordering, we achieve on average 39% and 31 % speedup in execution cycles comparing to -03 optimization and Open'Tune []] two widely used optimization techniques in compilers. On molecular design, LaP² outperforms all of our baselines in generating molecules with high values of desirable properties, beating the best baseline in average property value by to 0.4 on properties in [0, 1] range. Additionally, extensive ablation studies show factors that affect the quality of planning and verify the theoretical analysis.
LaP3 is general planning technique and can be readily plugged into existing algorithms with path planning components. For example, we apply LaP to PETS [7] in model-based RL and observe substantially improved performance for high-dimensional continuous control and navigation, compared to CEM as used the original PETS framework.
2
Latent Space Monte Carlo Tree Search (LaMCTS)
LaMCTS 45 is recently proposed to solve black-box optimization problems x = arg maxx fx) via recursively learning f-dependent region partitions. Fig. [ and Alg. I show the details of LaMCTS as well as our proposed approach Lap (formally introduced in Sec. for comparison.
Algorithm Lap3 Pseudocode for Path Planning. Improvements over LaMCTS green.
I: Input: Number of rounds T, Environment Oracle: f(x), Dataset D, Sampling Latent Model h(x),
Partitioning Latent Model s(x).
Parameters: Initial #samples Ninit, Re-partitioning interval Npar Node partition threshold Nehress UCB parameter Cp.
3: Pre-train h()) on D when D + 0.
4: Set region partition Vi= {
5: Draw Nimi samples uniformly from So = [(x)) C Ω.
6: for i O,..., Ni.. do
if divides Npar then
8: Train/finc-tnne latent model ht-)) using samples S, U (Eqn. ??).
9: Re-learn region partition V, +- Partition(22, St, Nehres; s(-) in latent space 4 of s(-).
10: end if
11:
for k k:= root, & Viaa do
12:
k + arg
max b.. where b. = n(Re) (L,)
[(,) max f(x:) + Cpy X.eR
2log ((B))) R(De))
x,
13:
end for
14: Initialize CMA-ES using encodings of S n Ss via l(()). Here Su is the chosen leaf sub-region.
15: S. + S U f(x))), where x, is drawn from CMA-ES and decoded via h -1-(.).
16: end for

---

(a)
Instance x E f2
(b)
Root
(c)
f2
Q2
ft
Sample flx and value (xr
(())
Good action
Bad
fl
Good
action
S2
(x))()))
High (x)
Explotation Exploration
Search Space Q
Qg
n4
Space partition
45] to path planning. (a) Starting from search space ft both Lap" and LaMCTS first draw few samples x 22, then learn to partition S2 into sub-region ?2 with good samples (high f(x)) and a sub-region 12g with bad samples (low f(x)). Compared LaMCTS, LaP uses latent space and reduces the dimensionality of the search space. (b) Sampling follows the learned recursive space partition, focusing on good regions while still exploring bad regions using UCB. LaP" uses the moximum of the sampled value in a region emaxx,en fxx)) as the node value, while LaMCTS uses the mean. (c) Upon reaching leaf, new data points are sampled within the region and the space partition is relearned.
Figure 1:
LaP" extends LaMCTS
1. For region S2g, let n(42)) be the number of samples within. LaMCTS dictates that, if n(2g,) N Nihres then 9. is partitioned into disjoint sub-regions Qa Qgond U Daad its children (Fig. T ab)(b)) line 9 Alg. T the function Partition). Intuitively, Qgood contains promising samples with high S. while Bad contains samples with low f. Unlike DOO and VOOT, such a partition is learned using S, 52g our samples so far in the region, and is thus dependent on the function f to be optimized.
LaMCTS starts with Nuai random samples of the entire search space Q (line 5 in Alg.
Given tree-structured sub-regions, new samples are mostly drawn from promising regions and occasionally from other regions for exploration. This is achieved by Monte Carlo Tree Search (MCTS) 4 (line 11-13): at each tree branching, the UCB score b is computed to balance exploration and exploitation (line 12). Then the subregion with highest UCB score is selected (e-g., may have high f and/or low 11). This is done recursively until a leaf sub-region U is reached. Then new sample x is drawn from S (line 15) either uniformly, or from a local model constructed by an existing optimizer (e.g.. TuRBO I0). CMA-ES [16),, in which case LaMCTS becomes meta-algorithm. When more samples are collected, regions are further partitioned and the tree gets deeper.
Finally, the function Partition in Alg. is defined as follows: first a 2-class K-means on (x, fxx) is used create positive/negative sample groups. Next, a SVM classifier used learn the decision boundary (hence the partition), so that samples with high f(x) fall into Sgyood, and samples with low fx) fall into Paad (Fig. T a)). See Appendix A for the pseudo code. The partition boundary can also be re-learned after more samples are collected (line 9).
3 A Theoretical Understanding of Space Partitioning
While LaMCTS [45 shows strong empirical performance, it contains several components with no clear theoretical justification. Here we attempt to give a formal regret analysis when sub-regions {[c)} are fixed and all the same tree level, and the function f is deterministic. We leave further analysis of tree node splitting and evolution of hierarchical structure to future work.
Despite the drastic simplification, regret bound still shows why an f f-dependent region partition is helpful. By showing that a better regret bound can be achieved by a clever region partition as empirically used in the Partition function in Alg. we justify the design of LaMCTS. Furthermore, our analysis suggests several empirical improvements over LaMCTS and motivates the design of LaP3, which outperforms multiple classic approaches hard path planning problems.
3.1 Regret Analysis with Fixed Sub-Regions
We consider the following setting. Suppose we have K d-dimensional regions { and (24) is the visitation count at iteration t. The global optimum x" resides in some unknown region Sg= At each iteration I, we visit a region Ωg sample (uniformly or otherwise) a data point X₁ E Qr and retrieve its deterministic function value Se f(x)). In each region Qg. define X == arg maxxes, f(x) and the maximal value g (Sax) = [xx]) The maximal value so far at iteration is gi (ft) maxese f(xx). It is clear that gt S g" and 9t + g" when t - toc.
3

---

(a) P²))) = Problf s -y]
(b)
(c)
Upper bound
Low f()
1
x"
Fis (eat
Fx
Fxz
F k
Akz
High (x)
0
Agz
0
Figure 2: Theoretical understanding of space partitioning. (a) Definition of (#z, Ct )-diluted region S2 (Def. 1. (b) Partition of region Qg into good region f21 and had region l22. Optimal solution x" E fag (c) After space partitioning, Fs is split into FRI and Fkz. The good region FAI has much smaller c&1 while the bad region has much larger best-to-optimality gap Auz. As result, the expected total regret decreases.
We define the confidence bound r; = re(2))) so that with high probability, the following holds: 9e (Rx) 9" (92) - (92x)
At iteration I, we pick region ky to sample based on the upper confidence bound: hi arg max Io (8x) + (Stg) Many different confidence bounds can be applied; for convenience in this analysis, we use the "ground truth" bound from the cumulative density function (CDF) of f within the region S2 (Please check Appendix for all proofs):
Lemma 1. Let Fx( == P. (J(x) I g2{x)) y|x x E S4k be a strictly decreasing function, and let (92x) == Fx (Re)). Then Eqn. holds with probability
Here F 1 is the inverse function of Fj and randomness arises from sampling within 2t. Since Fj. is strictly decreasing function, F/-1 exists and is also strictly decreasing. By definition, F& [0. 1]. Fa (0) 1 and F (1) 0. We then define the dilution of each region follows:
Definition ((zu, C&) -dilution,. A region St is (Zu, ek ddiluued if there exist 2k, Cj such that F&(y) S 1 - (y/cx)* for E [0, cx(1 > 1/"), where zę is the smallest F& (y) to make the inequality hold.
The intuition for dilution for given region, as depicted in Fig. a[),, is that all but zu fraction of the region has function value close to the maximum, with "close" defined based on ds (smaller es implies stricter definition of "close"). Obviously Q4 is (2g,C) -diluted then it is (2/- de )diluted for any c 2 Ck and 2/K 2 2ạ. Therefore, we often look for the smallest 2 and C₁ to satisfy the condition. If region Ωg has small Cs and 2k, we say it is highly concentrated. For example, f fxx mostly constant within a region, then is very small since F3 (y) drops to 0 very quickly. In such a case, most of the region's 's function values are concentrated near the maximum, making it easier to optimize.
While the definition of concentration may be abstract, we show it is implied by Lipschitz continuity: Corollary 1. Ifa region Q4 L3 Lipischhittz continuous, i.e., |f(x) (f(x)=((xx) f(x)) < Lx x|xxx|X\le x'112, and there exists an En-ball B(x,, <o) S S4. then with uniform sampling, S4 is (1 - V Ta V-)--iluted.. Here Vr Vv is the relative volume with respect to the unit sphere volume Vo-
Typically, a smoother function (with small L2) and large cn yield a less diluted (and more concentrated) region. However, the concept of dilution (Def. I is much broader. For example, if we shuffle function values within 2g. Lipschitz continuity is likely to break but Def. still holds.
f - 9: (P,,) > 0 be the regret of pick- ing Piz and R(I') = Σt= (az) be the total regret, where T' is the total number of sam- ples (queries to f). Define the gap of each region A == f g (St)) and split the region indices into Kgood : {K: A I Ao} and Kbad = {k: A 2 Ao) by threshold Ag-
Now we will bound the total regret. Let Ra,a.)
Ggond (Ekek x4)
1/d
and Obad (EREKIN 4) 1/a
are the fa-norms of the Cg in these
two sets. Finally, M = supxen f(x) infxen f(x) is the maximal gap between function values. Treating each region 22 as an arm and applying regret analysis similar multi-arm bandits 41.. we obtain the following theorem:
Theorem 1. Suppose all {S+} are (zK, Ck) -dilute with 2t S T/T3 for some n > O. The total expected regret E [R(T)) = O Cgood VTd-1In' In + M (Cbbaa/ Do) ld In T + KM

---

3.2 Implications of Theorem 1
The effect of space partitioning. Reducing {cr results in a smaller regret R(T). Thus we can partition Q2 into two sub-regions 941 and f42 such that the good partition S211 has smaller Ck1 < ck and the bad partition Q22 has larger Ax2 > Dg and falls into Kbsd. then we can improve the regret bound (Fig. (b)-(c)). This coincides with the Partition function of LaMCTS very well: it samples a few points S2 and trains a classifier to separate high f from low f. On the other hand, if we partition region Ω4 randomly, e.g., each f(x) is assigned to either 9211 or 92z at random, then statistically F&1 = Fx2 = F3 and 6b1 = C22 = Ck. which increases the regret bound. Therefore, the partition needs to be informed by data that have already been sampled within the region Sn.
Recursive region partitioning. In Theorem D we assume all regions {Ωa } have fixed c, and 2ke so the bound breaks for large enough T (as 77 T eventually becomes smaller than any fixed 2*). However, as LaMCTS conducts further internal partitioning within Qk. its og and 24 keep shrinking with more samples T. If each split leads to slightly fewer bad f (i.e., lighter "tail"), with the ratio being y < 1, then by the definition of CDF, z& is the probability mass of the tail and thus Zn ~ ? T/Nparr This would yield žạ S n/T for all T, since y decays faster than 1/7 and Theorem would hold for all T. See Appendix E2 for empirical verification of decaying zk.
3.3 Related Work and Limitations
While related to Lipschitz bandits 28 and coarse-to-fine deterministic function optimization like DOO and SOO 32), our analysis is fundamentally different. We have discussed how f-dependent region partitioning and data-driven learning procedure affect the regret bound, which our knowledge has not been previously addressed. See Appendix B.5 for further remarks on Theorem []
There is more work to be done to fully understand how LaMCTS works. In particular, did not analyze when to split node (e.g. how many samples we need to collect before making a decision), or the effect of relearning the space partition. We also have not considered stochastic reward functions, where the maximum function value in the sub-region may no longer be the best metric of goodness. We leave these to future work.
4 LaP3 for Path Planning
Based on our analysis, we propose LaP3, which extends LaMCTS to path planning, a problem with temporal structure. LaP outperforms baseline path planning approaches in both continuous and discrete path planning problems. Here we represent trajectories as action sequences x = (ao, Oi,..., an-1) 1) and treat them high-dimensional vectors x in the trajectory space Ω.
Thus, LaP searches over the space Ω, recursively partitioning Ω into subregions based on trajectory reward, and sampling from subregions using CMA-ES [66] (which is faster than TuRBO [10] used in the original LaMCTS). We emphasize again that LaP* 's region partitioning procedure is fully adaptive, in contrast to traditional MCTS approaches such VOOT, which only partition the trajectory space based on one action at a time.
Additionally, we have made several improvements over the original LaMCTS, as detailed in Algorithm 1 First, we use the maximal value maxigs, fx,,, rather than the mean value n().)) Eien. f(x;) as The metric of goodness for each node & (and its associated region Qx). This is driven by Theorem [] which gives a regret bound based on maximum values. Intuitively, using the mean value would cause the algorithm to be slow to respond to newly discovered territory: it takes time for the mean metric to boost, and we may miss important leaves. We show the difference empirically in Sec. 5.3
Second, Theorem I suggests that a power-dimensional (smaller d) and smoother (smaller c₁) repre- sentation leads to lower regret. Therefore, LaP' employs a latent space as described below.
4.1 Latent Spaces For Partitioning and Sampling
LaP3 leverages a latent space Φ. for the partition space, by passing Ω through some encoder s. That is, we disentangle the sampling space Ω from which we sample new candidate trajectories, from the partition space 4. on which we construct the search space partition. Critically, we do not need s -1. never decode from & back to Ω. Thus can dramatically reduce the dimension of the partition
5

---

space, which may improve regularization due to the small number of samples, without suffering large reconstruction loss, will be fixed rather than learned this case. Once the partition has been constructed on 4,, and we select leaf region to propose from, we sample new x from Si as before |
In principle, the sampling space itself be latent space 4 with encoder h and decoder h-1 That is, one runs the inner solver in 4 to propose samples before decoding back to S2 / could be principal component analysis (PCA) [49], random network encoding [43, or a reversible flow [9], depending on the environment's 's particular S2 and state/action structure. While some latent representations can be fixed by specifying the inductive bias (e.g., random network encoding), others can be learned from data, optimizing reconstruction loss ming Ex [wox)][h [m(xx)]/='(((x/
(h(x)) - x| where w(x) is weighting function emphasizing trajectories with high cumulative reward fxx). In this case, h and h-1 may be fine-tuned using each new (x, [x)) pair when LaP proposes and queries new trajectory x. or they may be pre-trained using set of unlabeled x with w(x) = 1. For consistency in our main experiments, we do not use latent 4, although we observe that using this second latent space can yield slight performance in some environments (Appendix F.7).
5 LaP's on Synthetic Environments
We test LaP' diverse set of environments to evaluate its performance in different settings.
Baselines. We compare LaP* to several baselines. LaMCTS is the original LaMCTS algorithm using CMA-ES as an inner solver, like LaP", Random Shooting (RS) (36 samples random tra- jectories and returns the best one. Cross-Entropy Methods (CEM) 2 use the top-k samples to fit a local model to guide future sampling. A related approach, Covariance matrix adaptation evolution strategy (CMA-ES) [16), tracks additional variables for improved local model fitting. Voronoi optimistic optimization applied to trees (VOOT) [22] is "traditional" MCTS method for continuous action spaces that builds a tree on actions at each timestep. iLQR [26] is seminal gradient-based local optimization approach used extensively in controls. Finally, proximal policy optimization (PPO) 39] is a standard reinforcement learning algorithm.
LaP does not require substantially more tuning effort than CEM or CMA-ES, the best-performing among our baselines experimentally. The only additional hyperparameter tuned in LaP* is the Cp controlling exploration when selecting regions to sample from, which is dependent on the scale of the reward function. However, our Cp only varies by factor of up to 10 across our diverse environments, and performance is not overly sensitive to small changes (Appendix F.5).
We MiniWorld [S]
for continuous path planning and MiniGrid 6 for discrete.
5.1 MiniWorld
(a) RS
(b) CEM
(c) Lap
Figure 3: MazeS3 environment. Start: Orange circle. Goal: Red circle. Dots indicate final agent positions of 2,000 proposed trajectories (green: first iteration, blue: last iteration). CEM gets stuck in a local optimum of reward (shown concentration of blue dots), while Lap" succeeds in reaching the goal.
We consider the following 2D navigation tasks in MiniWorld. MazeS3: Agent navigates in a by 3 maze to goal. Greedy path planning gets stuck in local optima (Figure 3. FourRooms: Agent navigates from one room a by 2 configuration to a goal in the diagonally opposite room. Greedy path planning gets stuck in corner. SelectObj: Open space with two goals. Large final reward when
'Specifically, we initialize the inner solver (CMA-ES in our experiments) using the pre-existing samples corresponding to the selected leaf' region in &., and then propose new samples using that initialization.

---

60
50
LAMETS
R5
CEM
Success
30
20
LOR
20
PPO
500
1060
1500
2000
0
5:0
1000
1500
2000
0
1.0n
2000
3:00
4000
Func Evals
Func Evals
Func Func Evais
(a) MazeS3
(h) FourRooms
(c) SelectOhj
Figure 4: Mean, and standard deviation of mean (256 trials; fewer for VOOT and PPO due to speed), of success rate across Mini World tasks. Lap significantly outperforms all baselines on all three tasks.
25
80-
20
PETS-LaP:
Training
Training
(a) PETS FourRooms
(b) PETS SclectObj
Figure 5: LaP' in PETS compared to original PETS planners Mini environments, using PETS-learned world models. Sliding length- 64 window of success percentage against number of training seeds for world model. LaP significantly outperforms all baselines on both tasks.
reaching the farther goal, while distance- based reward misleadingly points the closer goal. For full environment specifics, see Appendix H.I
We modify the original setup to use continuous action space (Az and Ay), and provide sparse reward (proximity to goal, with an additional bonus for reaching the goal) at end-of-episode. We high- nigh-dimmesional top-down image view the state. We featurize this image using randomly initialized convolutional neural network, a reasonable feature extractor as shown in [43]. Lap uses periodic snapshots of the featurized state the partition space .,. That is, collect all the observed states over the course of the full trajectory, and then form the latent space by concatenating every n state (here 20), while discarding the rest reduce overall dimensionality. Success is defined using a binary indicator for reaching the goal (far goal for SelectObj).
Results. LaP² substantially outperforms all baselines all three tasks, despite heavily tuning the baselines' hyperparameters (Appendix G showing that LaP works for challenging tasks containing suboptimal local maxima. In MazeS3, LaP succeeds but CEM gets stuck (Figure 3 VOOT, which builds an MCTS tree on actions at each timestep, struggles on all environments; LaP can be viewed extension of MCTS that performs better such long- horizoo tasks. PPO also performs poorly, perhaps due to the sparse reward given only at the end of an episode, and the relatively small (for RL) number of episodes. In the most difficult SelectObj task, LaP solves nearly half of environment seeds the original LaMCTS LMMCTS-qicklly quickly
within 4,000 queries of the oracle, whereas most reach the near goal but struggle to escape this local optimum.
We also evaluate LaP3 when combined with a model-based approach, PETS 77.. on FourRooms and SelectObj (omitting MazeS3 because the changing maze walls for each seed make it difficult to learn a world model), Following PETS* setting and due to difficulty in learning image-based world models use 2D agent position the state. As shown in Fig. LaP substantially outperforms the authors' original CEM implementation in the PETS framework, demonstrating that it is not reliant access to the oracle model but can work with learned models as well.
12 14,
5.2 MiniGrid
MiniGrid ( popular sparse-reward symbolic environment for benchmarking RI. algorithms. It contains tasks with discrete states and actions such as DoorKey (DK): pick up key and open

---

the door connecting two rooms; MultiRoom (MR): traverse several rooms by opening doors; and KeyCorridos (KC), combination of MR and DK: some doors are locked and require key, As in MiniWorld, we add proximity to the goal to the final sparse reward.
In discrete action spaces, LaP² optimizes the vector of all action probabilities over all timesteps, and action at each step. As in MiniWorld, we use periodic state snapshots
takes the featurized by a randomly initialized CNN as the partition space 2.. We compare LaP' to the same baselines as in MiniWorld, except VOOT and iLQR which are designed for continuous tasks.
Results. Lap is equal or better than baselines all six tasks (Table D. Especially in the hardest tasks with the most rooms (MR-N4S5, MR-N6), LaP" improves substantially over baselines.
DK-6
DK-8
KC-S3R3
KC-S3R4
MR-N4S5
MR-N6
LaMCTS
0.96=0.02
0.09 + 0.17
-2.63+00.09
-4.4340.13
-1..71
-118,70+44.6
RS
0.97=0.01
0.34
-2.38=0.09
.4.27=0.12
118.16
-119,39:t4664
CEM
0.03=0.12
-3.44=0.34
-3.40
-..33+0.13
-22.88+1.00
-131.32: .24
CMA-ES
0.93=00033
0.23=0014
-2.4610.09
-..4410.12
+1..31+0.78
-117.50+:4.61
Lap
0.05
0.13
-2.27
0.13
-1..68:10.75
-113.53:14.49
Table
Results for LaP3 in MiniGrid. LaP3 equal better on all tasks (higher is better).
5.3
Analysis
We several ablations LaP3 in MiniWorld to justify our methodological choices. See Appendix for further analysis on hyperparameter sensitivity, UCB metric, and latent spaces.
Region Selection in LaP3. We consider four alternative region selection methods. (1) Lap"-mean using mean function value rather than max for UCB, as in LaMCTS [5]; : (2) Lap -ols-nolatent: not
using latent space for partitioning; (3) -notrec directly selecting the leaf with the highest
UCB score; and (4) LaP* -COBCB only using node value rather than UCB. Lap greatly outperforms all variations in Mini MiniWorld, justifying design.
100
MazeS3
FourRooms
SelectObj
[xFt
LiFt iniitant
Lift outioe
L
87.5
100.0
100.0
60-
Laft isuica
C
81.3
93.8
100.0
Table 2: Percentage out of 32 environment seeds MiniWorld environments where LaP" yields bet- ter estimated Lipschitz and e compared to random partitioning on the same nodes.
Sclod00yy
MiniWorld success percentages with different region selection methods.
Figure 6:
Data-driven space partition in Lap3 random partitioning. We examine e in Def. and Lipschitz constant L2 in Corollary [ to verify the theory. We conduct preliminary analysis on LaP*'s tree after the full 2,000 queries (4,000 for SelectObj). At each intermediate node, we estimate LA and og of its children from the LaP3 partition, against random partition that divides the node's samples with the same ratio (see Appendix [F.T for estimation details). We then average the values for both LaP' and random partitions over all nodes in the tree. We find that LaP3 does yield lower average La and e (Table 2). indicating that data-driven space partition is effective.
LaP3 on Real-World Applications
6.1 Compiler Phase Ordering
Compiler optimization applies series of program transformations from set of predefined optimiza- tions (e.g., loop invariant code fonicti,unction inlining (30) to improve code performance. Since these optimizations are not commutative, the order which they are applied is extremely important. This problem, known as phase ordering, is core challenge in the compiler community. Current

---

2.0
4080
LAMTTT
PPg
15
0.9
Figure 7: Compiler phase ordering results, in terms of normalized execution cycles with respect Open- Tuner [1 a widely used method for program autotuning. LaP consistently equal or better compared to baselines. We omitted the matmul task since it doesn't fit the scale with its 245% speedup over Open' Open'Tuner.
solutions to this NP-hard problem rely heavily on heuristics: groups of optimizations are often packed into "optimization levels" (such as -O3 or -O0) hand-picked by developers 33 42)
We apply LaP² the standard CHStone benchmarks 17 and use periodic snapshots of states 4, and the identity as 2,. See Appendix H.2 for full environment details.
Results. LaP is 31% faster average compared Open and 39% compared to -03 (not shown in figure). Compared to a stronger PPO baseline using 50 samples (PPO_50) (0_50 and to CMA-ES, achieve up to 10% and 7% speedup respectively. Finally, compared to final PPO results at convergence after 4000 samples (PPO 4000) as an oracle, Lap does similarly on most tasks, despite being much more sample efficient (only 50 samples). Full results in Appendix B
6.2 Molecular Design
1.0
67
LIMETS
8.5
CMA
64
Fanc
OvER
Punc kess
(a)
QED
(b) DRD2
(c) HIV
(d) SARS
Figure 8: Mean and standard deviation (128 trials), of max property value discovered in molecular design tasks.
LaP significantly outperforms baselines all properties.
Finally, we evaluate LaP on molecular design. Given an oracle for a desired molecular property. the goal is to generate molecules with high property score after the fewest trials. This is critical to pharmaceutical drug development
as property evaluations require expensive wet-lab assays.
Similar to 18]. we fix a query budget and optimize several properties: QED: synthetic measure of like-liseeess, relatively simpler optimize; DRD2: measure of binding affinity to a human dopamine receptor; HIV. the probability of inhibition potential for HIV; and SARS: the same probability for variant of the SARS virus, related
SARS-CoV-2 virus responsible for COVID- 19. All four properties have range of [0. 1]: higher is better. For DRD2, HIV, and SARS, we evaluate using computational predictors from [33 (DRD2) and [51] (HIV, SARS) in lieu wet-lab assays.
To run Lap3 on molecular design, we view the molecular string representation (SMILES string [48) as the action sequence, similar how many generative models generate molecules autoregressively
25 g 150 Following the state-ofttee the-art HierG2G model from [19]. we learn a latent representation from subset of ChEMBL 22 dataset of 1.8 million drug-like like molecules. without using any of its property labels (e.g., effectiveness in binding to particular receptor). During this unsupervised training, we only use the 500k molecules with the lowest property scores to ensure a good molecule is discovered by search rather than a simple retrieval from the dataset. Our setting differs from many existing methods for molecular design, which assume a large preexisting set of molecules with the
desired property for training the generator B3 20 52 50).

---

On this task only, the latent space is trained on additional unlabeled data, and is used as both the partition space L. and sampling space 4, for Lap". All baselines operate in the same space for fair comparison. Otherwise, all methods struggle to generate well-formed molecules of reasonable length.
shows Results. Figure shows the highest property score discovered by each method for each property. The absolute difference is small in the relatively simple synthetic QED task. However, LaP* outperforms all baselines by a much greater margin-up to 0.4 in DRD2-in the more challenging and realistic DRD2, HIV, and SARS tasks, where CEM and CMA-ES quickly plateau but LaP continues to improve with more function evaluations.
Conclusion
We propose LaPå, novel meta-algorithm for path planning that learns to partition the search space so that subsequent sampling focuses more on promising regions. We provide a formal regret analysis of region partitioning, motivating improvements that yield large empirical gains. LaPa particularly excels in environments with many difficult-t--scapee local optima, substantially outperforming strong baselines 2D navigation tasks well real-world compiler optimization and molecular design.
Acknowledgments and Disclosure of Funding
We thank the members of the Berkeley NLP group well four anonymous reviewers for their helpful feedback. This work was supported by Berkeley Al Research, and the NSF through a fellowship to the first author.
References
[1] Jason Ansel, Shoaib Kamil, Kalyan Veeramachaneni, Jonathan Ragan-Kelley, Jeffrey Bosboom, Una-May O'Reilly, and Saman Amarasinghe. Opentuner: An extensible framework for program autotuning. In Proceedings of the 23rd international conference Parallel architectures and compilation, pages 303-316, 2014.
[2] Zdravko Botev, Dirk Kroese, Reuven Y Rubinstein, and Pierre L'Ecuyer. The cross-entropy method for optimization. In Handbook of statistics, volume 31, pages 35-59. Elsevier, 2013.
[3] Eric Brochu, Vlad M Cora, and Nando De Freitas. A tutorial on bayesian optimization of expensive cost functions, with application active user modeling and hierarchical reinforcement remaoeeeeeerininorreeent learning. arXiv preprint arXiv: /012.2599 2010.
[4] Cameron B Browne, Edward Powley, Daniel Whitehouse, Simon M Lucas, Peter Cowling, Philipp Rohlfshagen, Stephen Tavener, Diego Perez, Spyridon Samothrakis, and Simon Colton. A survey of monte carlo tree search methods. JEEE Transactions on Computational Intelligence and Al in games, 4(1):1 (0):1443,222 2012.
[5] Maxime Chevalier- gym-miniworld environment for openai gym. https://githu: com wwwpaaaiiinnooggmmmiiiiiieeeeeee
2018.
[6] Maxime Chevalier-Boisvert and Lucas Willems. Minimalistic gridworld environment for openai
gym. htttp://ggttai ctw.taa.ooooooooooooaaaaoooo.eoe www./axiimm//acccccccccccoo.cooe ge/ggyymmmmm wwt-mmiiiiii iiiiiiiridd 2018.
[7] Kurtland Chua, Roberto Calandra, Rowan McAllister, and Sergey Levine. Deep reinforcement learning in a handful of trials using probabilistic dynamics models. NeurIPS, 2018.
[8] Hanjun Dai, Yingtao Tian, Bo Dai, Steven Skiena, and Le Song. Syntax-directed variational autoencoder for structured data. arXiv preprint arXiv: het::8802.07800 2018.
[9] Laurent Dinh, Jascha Sohl- Sibl-Dickstein, and Samy Bengio. Density estimation using real nvp.
arXiv preprint 1rXiv: 08800, 2016.
[10] David Eriksson, Michael Pearce, Jacob R Gardner, Ryan Turner, and Mathhis Poloczek.
Scalable global optimization via local bayesian optimization. arXiv preprint arXiv:1910.01739, 2019.
[11] Rafael
Jennifer Wei, David Duvenaud, José Miguel Hernández-Lohenn Benjamín Sánchez-Lengeling Dennis Sheberla, Jorge eguilera-Iparraguing Timothy D Hirzel,
10

---

Ryan P Adams, and Alán Aspuru-Guzik, Automatic chemical design using a data-driven continuous representation of molecules. ACS central science, 4(2):268-22) 276, 2018.
[12] Danijar Hafner, Timothy Lillicrap, Jimmy Ba, and Mohammad Norouzi. Dream to control: Learning behaviors by latent imagination. arXiv preprini urXiv:
2019.
[13] Danijar Hafner, Timothy Lillicrap, Ian Fischer, Ruben Villegas, David Ha, Honglak Lee, and James Davidson. Learning latent dynamics for planning from pixels. In International Conference Machine Learning, pages
PMLR, 2019.
[14] Danijar Hafner, Timothy Lillicrap. Mohammad Norouzi, and Jimmy Ba. Mastering atari with discrete world models. arXiv preprint arXiv:2010.02193, 2020.
[15] Ameer Haj-Ali, Qijing Jenny Huang. John Xiang, William Moses, Krste Asanovic, John Wawzzynek, and Ion Stoica. Autophase: Juggling his phase orderings in random forests with deep reinforcement learning. Proceedings of Machine Learning and Systems, 2:70-81, 81, 2020.
[16] Nikolaus Hansen. The ema evolution strategy: A tutorial. arXiv preprint (rXiv1664.00072 2016.
[17] Yuko Hara, Hiroyuki Tomiyama, Shinya Honda, Hiroaki Takada, and Katsuya Ishii. Chstone: A benchmark program suite for practical c-based high-level synthesis. In 2008 IEEE International Symposium on Circuits and Systems, pages 1192-1195, IEEE, 2008
[18] Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Junction tree variational autoencoder for molecular graph generation. In International Conference on Machine Learning, pages 1323-2332. PMLR, 2018
[19] Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Hierarchical generation of molecular graphs using structural motifs. In International Conference on Machine Learning, pages 4839-4848. PMLR, 2020.
[20] Wengong Jin, Kevin Yang, Regina Barzilay, and Tommi Jaakkola. Learning multimodal graph-to-graph translation for molecular optimization. arXiv preprint arXiv: 1VXiv:/812.010700 2018.
[21] Seiji Kajita, Tomoyuki Kinjo, and Tomoki Nishi. Autonomous molecular design by monte-carlo tree search and rapid evaluations using molecular dynamics simulations. Communications Physics, 3(1):1-11, 2020.
[22] Beomjoon Kim, Kyungjae Lee, Sungbin Lim, Leslie Kaelbling, and Tomas Lozano-Perez, Monte carlo tree search in continuous spaces using voronoi optimistic optimization with regret bounds. Proceedings of the AAAI Conference on Artificial Intelligence, 34(06):991699924, Apr. 2020.
[23] Tachyeon Kim, Jaeyeon Ahn, Nakyil Kim, and Seyoung Yun. Adaptive local bayesian opti- mization over multiple discrete variables. Workshop at NeurIPS 2020 Competition Track on Black-Box Optimization Challenge, 2020.
[24] Christian Kroer and Tuomas Sandholm. Sequential planning for steering immune system adaptation. In IJCAI, pages 31 3177-3184, 2016.
[25] Matt Kusner, Brooks Paige, and José Miguel Hernández-Lobato Grammar variational autoencoder. In International Conference on Machine Learning, pages 1945-1954, PMLR, 2017.
[26] Weiwei Li and Emanuel Todorov. Iterative linear quadratic regulator design for nonlinear biological movement systems. In ICINCO (1), pages 222-229. Citeseer, 2004.
[27] Thi Thoa Mac, Cosmin Copot, Due Trung Tran, and Robin De Keyser. Heuristic approaches in robot path planning: A survey. Robotics and Autonomous Systems, 36:13-28, 2016.
[28] Stefan Magureanu, Richard Combes, and Alexandre Proutiere. Lipschitz bandits: Regret lower bound and optimal algorithms. In Maria Florina Balcan, Vitaly Feldman, and Csaba Szepesvári, editors, Proceedings of The 27th Conference on Learning Theory, volume 35 of Proceedings of Machine Learning Research, pages 975-999, Barcelona, Spain, 13-15 Jun 2014. PMLR.
[29] David Mendez, Anna Gaulton, A Patrícia Bento, Jon Chambers, Marleen De Veij. Eloy Félix, María Paula Magariños, Juan F Mosquera, Prudence Mutowo, Michat Nowotka, María Gordillo- Marañón, Fiona Hunter, Laura Junco, Grace Mugumbate, Milagros Rodriguez-Lopez, Fran- cis Atkinson, Nicolas Bosc, Chris J Radoux, Aldo Segura-Cabrera, Anne Hersey, and An- drew R Leach. ChEMBL: towards direct deposition of bioassay data. Nucleic Acids Research, D9900))D900 11 2018.
11

---

[30] Steven Muchnick et al. Advanced compiler design implementation. Morgan kaufmann, 1997.
[31]
Rémi Munos. Optimistic optimization of a deterministic function without the knowledge of its smoothness. In Proceedings of the 24th International Conference Neural Information Processing Systems, NIPS' 11, page 783-791, Red Hook, NY, USA, 2011. Curran Associates
Inc.
[32] Rémi Munos. From bandits to monte-carlo tree search: The optimistic principle applied to optimization and planning. 2014.
[33] Marcus Olivecrona, Thomas Blaschke, Ola Engkvist, and Hongming Chen. Molecular de-novo design through deep reinforcement learning. Journal of cheminformaties, 9()::1114, 2017.
[34] Zhelong Pan and Rudolf Eigenmann. Fast and effective orchestration of compiler optimizations for automatic performance tuning. In International Symposium on Code Generation and Optimization (CGO (CG)) pages 12-pp. IEEE, 2006.
[35] Nathan Ratliff, Matt Zucker, J Andrew Bagnell, and Siddhartha Srinivasa. Chomp: Gradient optimization techniques for efficient motion planning. In 2009 IEEE International Conference on Robotics and Automation, pages 489-494, IEEE, 2009.
[36] Arthur George Richards. Robust constrained model predictive control. PhD thesis, Mas- sachusetts Institute of Technology, 2005.
[37] Reuven Rubinstein. The cross-entropy method for combinatorial and continuous optimization. pages 127, 190, 1999.
[38] Mikita Sazanovich, Anastasiya Nikolskaya, Yury Belousov, and Aleksei Shpilman. Solving black-box optimization challenge via learning search space partition for local bayesian opti- mization. workshop at NeurlPS 2020 Competition Track Black-Box Optimization Challenge, 2020.
[39] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov, Proximal policy optimization algorithms. arXiv preprint
06347, 2017.
[40] Marwin HS Segler, Mike Preuss, and Mark Waller. Planning chemical syntheses with deep neural networks and symbolic ai. Nature, 555(7698) 610, 2018.
[41] Alcksandrs Slivkins. Introduction to multi-armed bandits. arXiv preprint arXlv:1904.07272.
2019.
[42] Spyridon Triantafyllis, Manish Vachharajani, Neil Vachharajani, and David I August. Com- piler optimization space exploration. In International Symposium on Code Generation and Optimization, 2003. CGO 2003., pages 204-215. IEEE, 2003.
[43] Dmitry Ulyanov, Andrea Vedaldi, and Victor Lempitsky. Deep image prior. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 9446-9454, 2018.
[44] Jessica Vamathevan, Dominic Clark, Paul Czodrowski, Ian Dunham, Edgardo Ferran, George Lee, Bin Li, Anant Madabhushi, Parantu Shah, Michaela Spitzer, et al. Applications of machine learning in drug discovery and development. Nature Reviews Drug Discovery, 18(6):463-477, 2019.
[45] Linnan Wang. Rodrigo Fonseca, and Yuandong Tian. Learning search space partition for black-box optimization using monte carlo tree search. NeurlPS, 2020.
[46] Linnan Wang, Saining Xie, Teng Li, Rodrigo Fonseca, and Yuandong Tian. Sample-efficient neural architecture search by learning actions for monte carlo tree search. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021.
[47] Tingwu Wang and Jimmy Ba. Exploring model-based planning with policy networks. arXiv preprint arXiv: / /906. 08649, 2019.
[48] David Weininger. Smiles, chemical language and information system. 1. introduction to methodology and encoding rules. Journal of chemical information and computer sciences, 28(1):31-36, 1988.
[49] Svante Wold, Kim Esbensen, and Paul Geladi. Principal component analysis. Chemometrics and intelligent laboratory systems, 2(1-3):77-5, 1987.
[50] Kevin Yang, Wengong Jin, Kyle Swanson, Regina Barzilay, and Tommi Jaakkola. Improving molecular design by stochastic iterative target augmentation. In International Conference on Machine Learning, pages 107 10726. PMLR, 2020.
12

---

[51] Kevin Yang, Kyle Swanson, Wengong Jin, Connor Coley, Philipp Eiden, Hua Gao, Angel Guzman-Perez Timothy Hopper, Brian Kelley, Miriam Mathea, et al. Analyzing learned molec- ular representations for property prediction. Journal of chemical information and modeling, 59(8):337--3388, 2019.
[52] Jiaxuan You, Bowen Liu, Rex Ying, Vijay Pande, and Jure Leskovec. Graph convolutional policy network for goal-directed molecular graph generation. arXiv preprint 000.::/0000007777 2018.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] We claim to provide a theoretical explanation of region partitioning and empirical gains over baselines, which presented in Sec. and Secs.
$ respectively.
(b) Did you describe the limitations of your work? [Yes] We have discussed limitations of our preliminary theory in Sec. 3.2 Our latent spaces also inherently depend on the details of the environments, as described in each individual experiment section. While LaP could be easily modified for black-box optimization in principle, we have made clear that we empirically verify only on path planning.
(c) Did you discuss any potential negative societal impacts of your work? [No] We do not foresee any obvious negative societal impacts from our work, which contributes a general-purpose path planning algorithm.
(d) Have you read the ethies review guidelines and ensured that your paper conforms them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] In lemma/theorem statements in Sec. 3
(b) Did you include complete proof's of all theoretical results? [Yes] All proof's are in Appendix B
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] We upload code in the supplementary material.
(b) Did you specify all the training details (e.g., data splits, byperparameters, how they were chosen)? [Yes] We discuss all hyperparameter tuning details in Appendix G
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes] Included in all experiments in Secs. 516
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No]
4. If you using existing assets (e.g., code, data, models) curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [No]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A] Just code, which is in supplemental material.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [No] We use publicly available datasets/tasks.
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [No] We don't 't use data of this sort.
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "saAiycYQd5W", "reviewer": "Reviewer_vLZD", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\nThe 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. \n\nWeaknesses:\nThe 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. \n\nClarity:\nThe algorithm itself is very well explained, but it was hard to follow the various setups for the different experiments. \n\nRelation to Prior Work:\nPlaLaM is built upon LaMCTS, but uses the maximum value rather than the mean for the measure of goodness for each partition. \n\nAdditional Feedback:\n- Visualization of the state space for the synthetic environments would be nice.\n- More specifics or explanation about the results for Compiler Phase ordering can be provided since not all experiments have 61%-245% speedup.\n- In figure 3, the goal location is reported incorrectly as a square\n\nUpdate (after revision): Increasing score!\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations: design choices for different environments should be discussed.\nSocietal Impact: N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "baeSiuk8mwn", "reviewer": "Reviewer_vamd", "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. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strong points:\n-\tTheoretical analysis of LaMCTS provides a better understanding of LaMCTS.\n-\tThe proposed modification is grounded on the theoretical analysis.\n\nWeak points:\n-\tAlthough the proposed algorithm PlaLaM outperformed well-known baseline methods such as CEM and CMA-ES, comparison with LaMCTS is not provided.\n\nI 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. \n\nI 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.\n\n=== comments after the author response ===\n\nThe additional results provided by authors clearly demonstrate that how PlaLaM outperforms LaMCTS. I updated the score. \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "KE5L6uxnhy7", "reviewer": "Reviewer_rxG7", "summary": "This work proposes a new path planning method PlaLaM, which is an extension of the LaMCTS algorithm.\nThe authors provide a novel regret analysis of adaptive region partitioning schemes. \n\nThe 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.\n\nThe 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.\n\nModel-free RL and planning are my domains of expertise. Evolutionary algorithms are not, so please consider my review according.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n1. The paper is well written, with clear and detailed explainations.\n2. The authors provide a reference codebase which they plan to share with the community\n3. The changes over the LaMCTS are clearly descrive in algoritm 1.\n\n\nWeaknesses\n1. The method seems an incremental improvement of the LaMCTS algorithm, is Neurips the most appropriate venue for such a work?\n2. The method is comparable or outperformed by the PPO-4000 results, what advantage does this method have, sample efficiency?\n3. For the 2D navigation problems, why not compare against a RL approach in addition to  ES?\n4. In the all of the experiments, the authors do not include a comparison to LaMCTS, why is the comparison not possible?\n\nUpdate: The authors answers my questions and addressed my main concern of a comparison with LaMCTS. Score raised to 7.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "I5NGglrwHR9", "reviewer": "Reviewer_DXgW", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nI 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.\n\nThe experiments section is quite extensive and covers a variety of settings. The proposed method performs favorably in each scenario.\n\nThat 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).\n\nAnother 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.\n\nOverall 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:\n\n* Provide a comparison to La-MCTS. If possible across the entire experiment suite in this paper.\n* Compare to La-MCTS on some of the experiments that are in the experiments section of La-MCTS.\n\nI think the paper would be a clear accept if these could be fulfilled and the comparison is generally in PlaLaM's favor.\n\n**Other comments**\n\n* 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.\n\n* 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.\n\n**Edit following author response**\n\nGiven 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!", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No concerns here.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

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)