Learning Space Partitions for Path Planning

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 [37] and CMA-ES [16] greedily focus on promising regions of the search space and may get trapped in local maxima. DOO [31] and VOOT [22] balance exploration and exploitation, but use space partitioning strategies independent of the reward function to be optimized. Recently, LaMCTS [45] 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 LaP which improves the function value estimation within each sub-region, and uses a latent representation of the search space. Empirically, LaP 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 [7]. 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.

heading: 1 Introduction
text: Path planning has been used extensively in many applications, ranging from reinforcement learning [7, 13, 14] and robotics [27, 35, 26] to biology [24], chemistry [40], material design [21], and compiler optimization [42]. The goal is to find the most rewarding trajectory (i.e., state-action sequence) x = (s0, a0, s1, . . . , sn) in the search space Ω: x∗ = arg maxx∈Ω f(x), where f(x) is the reward.
In this work, we focus on deterministic path planning problems with long trajectories x, and discontinuous and/or multimodal reward functions f . Such high-dimensional non-convex optimization problems exist in many real domains, both continuous and discrete. While we could always find nearoptimal x by random sampling given an infinite query budget, in practice we prefer a sample-efficient method that achieves high-reward trajectories with fewer queries of the reward function f .
While global methods like Bayesian Optimization (BO) [3] 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 a population of trajectories and repeatedly resamples its population according to the highest-performing trajectories from the previous generation. On the other hand, such a 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 Ω = Ω1 ∪ . . . ∪ Ωk, 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 (NeurIPS 2021).
(UCB). While such exploration-exploitation procedures adaptively focus on promising sub-regions and lead to sub-linear regret and optimality guarantees, their region partition procedure is 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.
Recently, 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, in recent NeurIPS’20 black-box optimization challenges, two teams that use variants of LaMCTS ranked 3rd [38] and 8th [23].
In this paper, we provide a simple theoretical analysis of LaMCTS to reveal the underlying principles of adaptive region partitioning, an analysis missing in the original work. Based on this analysis, we propose Latent Space Partitions for Path Planning (LaP3), a novel optimization technique for path-planning. Unlike LaMCTS, LaP3 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 LaP3 on several challenging path-planning tasks, including 2D navigation environments from past work with difficult-to-escape local optima, and real-world planning problems in compiler optimization and molecular design. In all tasks, LaP3 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 -O3 optimization and OpenTuner [1], two widely used optimization techniques in compilers. On molecular design, LaP3 outperforms all of our baselines in generating molecules with high values of desirable properties, beating the best baseline in average property value by up to 0.4 on properties in a [0, 1] range. Additionally, extensive ablation studies show factors that affect the quality of planning and verify the theoretical analysis.
LaP3 is a general planning technique and can be readily plugged into existing algorithms with path planning components. For example, we apply LaP3 to PETS [7] in model-based RL and observe substantially improved performance for high-dimensional continuous control and navigation, compared to CEM as used in the original PETS framework.

heading: 2 Latent Space Monte Carlo Tree Search (LaMCTS)
text: LaMCTS [45] is recently proposed to solve black-box optimization problems x∗ = arg maxx f(x) via recursively learning f -dependent region partitions. Fig. 1 and Alg. 1 show the details of LaMCTS as well as our proposed approach LaP3 (formally introduced in Sec. 4) for comparison.
Algorithm 1 LaP3 Pseudocode for Path Planning. Improvements over LaMCTS in green. 1: Input: Number of rounds T , Environment Oracle: f(x), Dataset D, Sampling Latent Model h(x),
Partitioning Latent Model s(x). 2: Parameters: Initial #samples Ninit, Re-partitioning interval Npar, Node partition threshold Nthres, UCB
parameter Cp. 3: Pre-train h(·) on D when D 6= ∅. 4: Set region partition V0 = {Ω}. 5: Draw Ninit samples uniformly from S0 = {(xi, f(xi))}Niniti=1 ⊂ Ω. 6: for t = 0, . . . , T −Ninit − 1 do 7: if t divides Npar then 8: Train/fine-tune latent model h(·) using samples St ∪ D (Eqn. ??). 9: Re-learn region partition Vt ← Partition(Ω,St, Nthres, s(·)) in latent space Φs of s(·).
10: end if 11: for k := root, k /∈ Vleaf do
12: k ← arg max Ωc∈child(Ωk) bc, where bc :=
 1
n(Ωc) ∑ xi∈Ωc f(xi) max xi∈Ωc f(xi) + Cp √ 2 log n(Ωk) n(Ωc) . 13: end for 14: Initialize CMA-ES using encodings of St ∩ Ωk via h(·). Here Ωk is the chosen leaf sub-region. 15: St ← St−1 ∪ {(xt, f(xt))}, where xt is drawn from CMA-ES and decoded via h−1(·). 16: end for
Good action
Bad action
Instance 𝒙 ∈ Ω
Space partition
High 𝑓(𝒙)
Low 𝑓(𝒙)
Search Space Ω
Root
Good action
(a) (b) 𝜴𝟐
Ω"
𝜴𝟑
𝜴𝟒 Ω% Ω&
Ω'
Ω
Exploitation Exploration
(c)
𝜴𝟒 (𝒙, 𝑓 𝒙 )
Sample 𝒙 ∈ Ω! and get the function value 𝑓(𝒙)
Figure 1: LaP3 extends LaMCTS [45] to path planning. (a) Starting from a search space Ω, both LaP3 and LaMCTS first draw a few samples x ∈ Ω, then learn to partition Ω into a sub-region Ω1 with good samples (high f(x)) and a sub-region Ω2 with bad samples (low f(x)). Compared to LaMCTS, LaP3 uses a 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. LaP3 uses the maximum of the sampled value in a region (maxxi∈Ω f(xi)) as the node value, while LaMCTS uses the mean. (c) Upon reaching a leaf, new data points are sampled within the region and the space partition is relearned.
LaMCTS starts with Ninit random samples of the entire search space Ω (line 5 in Alg. 1). For a region Ωk, let n(Ωk) be the number of samples within. LaMCTS dictates that, if n(Ωk) ≥ Nthres, then Ωk is partitioned into disjoint sub-regions Ωk = Ωgood ∪ Ωbad as its children (Fig. 1(a)-(b), line 9 in Alg. 1, the function Partition). Intuitively, Ωgood contains promising samples with high f , while Ωbad contains samples with low f . Unlike DOO and VOOT, such a partition is learned using St ∩ Ωk, our samples so far in the region, and is thus dependent on the function f to be optimized. 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., it may have high f and/or low n). This is done recursively until a leaf sub-region Ω′ is reached. Then a new sample x is drawn from Ω′ (line 15) either uniformly, or from a local model constructed by an existing optimizer (e.g., TuRBO [10], CMA-ES [16]), in which case LaMCTS becomes a meta-algorithm. When more samples are collected, regions are further partitioned and the tree gets deeper.
Finally, the function Partition in Alg. 1 is defined as follows: first a 2-class K-means on (x, f(x)) is used to create positive/negative sample groups. Next, a SVM classifier is used to learn the decision boundary (hence the partition), so that samples with high f(x) fall into Ωgood, and samples with low f(x) fall into Ωbad (Fig. 1(a)). See Appendix A for the pseudo code. The partition boundary can also be re-learned after more samples are collected (line 9).

heading: 3 A Theoretical Understanding of Space Partitioning
text: 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 {Ωk} are fixed and all at 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, our regret bound still shows why an 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. 1, 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 on hard path planning problems.

heading: 3.1 Regret Analysis with Fixed Sub-Regions
text: We consider the following setting. Suppose we have K d-dimensional regions {Ωk}Kk=1, and nt(Ωk) is the visitation count at iteration t. The global optimum x∗ resides in some unknown region Ωk∗ . At each iteration t, we visit a region Ωk, sample (uniformly or otherwise) a data point xt ∈ Ωk, and retrieve its deterministic function value ft = f(xt). In each region Ωk, define x∗k := arg maxx∈Ωk f(x) and the maximal value g ∗(Ωk) = f(x ∗ k). The maximal value so far at iteration t is gt(Ωk) = maxt′≤t f(xt′). It is clear that gt ≤ g∗ and gt → g∗ when t→ +∞.
We define the confidence bound rt = rt(Ωk) so that with high probability, the following holds:
gt(Ωk) ≥ g∗(Ωk)− rt(Ωk) (1) At iteration t, we pick region kt to sample based on the upper confidence bound: kt = arg maxk gt(Ωk) + rt(Ωk). 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 Ωk (Please check Appendix B for all proofs): Lemma 1. Let Fk(y) := P [f(x) ≤ g∗(Ωk)− y|x ∈ Ωk] be a strictly decreasing function, and let rk,t(Ωk) := F −1 k ( δ1/nt(Ωk) ) . Then Eqn. 1 holds with probability 1− δ.
Here F−1k is the inverse function of Fk and randomness arises from sampling within Ωk. Since Fk is a strictly decreasing function, F−1k exists and is also strictly decreasing. By definition, Fk ∈ [0, 1], Fk(0) = 1 and F−1k (1) = 0. We then define the dilution of each region as follows: Definition 1 ((zk, ck)-dilution). A region Ωk is (zk, ck)-diluted if there exist zk, ck such that Fk(y) ≤ 1− (y/ck)d for y ∈ [0, ck(1− zk)1/d], where zk is the smallest Fk(y) to make the inequality hold.
The intuition for dilution for a given region, as depicted in Fig. 2(a), is that all but zk fraction of the region has function value close to the maximum, with "close" defined based on ck (smaller ck implies a stricter definition of “close”). Obviously if Ωk is (zk, ck)-diluted then it is (z′k, c ′ k)-diluted for any c′k ≥ ck and z′k ≥ zk. Therefore, we often look for the smallest zk and ck to satisfy the condition. If a region Ωk has small ck and zk, we say it is highly concentrated. For example, if f(x) is mostly constant within a region, then ck is very small since Fk(y) drops to 0 very quickly. In such a case, most of the region’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. If a region Ωk is Lk-Lipschitz continuous, i.e., |f(x)−f(x′)| ≤ Lk‖x−x′‖2, and there exists an 0-ball B(x∗k, 0) ⊆ Ωk, then with uniform sampling, Ωk is (1− d0Ṽ −1 k , Lk d √ Ṽk)-diluted. Here Ṽk := Vk/V0 is the relative volume with respect to the unit sphere volume V0.
Typically, a smoother function (with smallLk) and large 0 yield a less diluted (and more concentrated) region. However, the concept of dilution (Def. 1) is much broader. For example, if we shuffle function values within Ωk, Lipschitz continuity is likely to break but Def. 1 still holds.
Now we will bound the total regret. Let Rt(at) := f∗ − gt(Ωat) ≥ 0 be the regret of picking Ωat and R(T ) := ∑T t=1Rt(at) be the total regret, where T is the total number of samples (queries to f ). Define the gap of each region ∆k := f∗ − g∗(Ωk) and split the region indices into Kgood := {k : ∆k ≤ ∆0} and Kbad := {k : ∆k ≥ ∆0} by a threshold ∆0.
Cgood := (∑
k∈Kgood c d k
)1/d and Cbad := (∑ k∈Kbad c d k )1/d are the `d-norms of the ck in these
two sets. Finally, M := supx∈Ω f(x)− infx∈Ω f(x) is the maximal gap between function values. Treating each region Ωk as an arm and applying a regret analysis similar to multi-arm bandits [41], we obtain the following theorem: Theorem 1. Suppose all {Ωk} are (zk, ck)-diluted with zk ≤ η/T 3 for some η > 0. The total expected regret E [R(T )] = O [ Cgood d √ T d−1 lnT +M(Cbad/∆0) d lnT +KMη/T ] .

heading: 3.2 Implications of Theorem 1
text: The effect of space partitioning. Reducing {ck} results in a smaller regret R(T ). Thus if we can partition Ωk into two sub-regions Ωk1 and Ωk2 such that the good partition Ωk1 has smaller ck1 < ck and the bad partition Ωk2 has larger ∆k2 > ∆0 and falls into Kbad, then we can improve the regret bound (Fig. 2(b)-(c)). This coincides with the Partition function of LaMCTS very well: it samples a few points in Ωk, and trains a classifier to separate high f from low f . On the other hand, if we partition a region Ωk randomly, e.g., each f(x) is assigned to either Ωk1 or Ωk2 at random, then statistically Fk1 = Fk2 = Fk and ck1 = ck2 = ck, which increases the regret bound. Therefore, the partition needs to be informed by data that have already been sampled within the region Ωk.
Recursive region partitioning. In Theorem 1, we assume all regions {Ωk} have fixed ck and zk, so the bound breaks for large enough T (as η/T 3 eventually becomes smaller than any fixed zk). However, as LaMCTS conducts further internal partitioning within Ωk, its ck and zk keep shrinking with more samples T . If each split leads to slightly fewer bad f (i.e., lighter “tail”), with the ratio being γ < 1, then by the definition of CDF, zk is the probability mass of the tail and thus zk ∼ γ−T/Npar . This would yield zk ≤ η/T 3 for all T , since γ−T decays faster than 1/T 3 and Theorem 1 would hold for all T . See Appendix F.2 for empirical verification of decaying zk.

heading: 3.3 Related Work and Limitations
text: 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 a data-driven learning procedure affect the regret bound, which to our knowledge has not been previously addressed. See Appendix B.5 for further remarks on Theorem 1.
There is more work to be done to fully understand how LaMCTS works. In particular, we did not analyze when to split a 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. LaP3 outperforms baseline path planning approaches in both continuous and discrete path planning problems. Here we represent trajectories as action sequences x = (a0, a1, . . . , an−1) and treat them as high-dimensional vectors x in the trajectory space Ω.
Thus, LaP3 searches over the space Ω, recursively partitioning Ω into subregions based on trajectory reward, and sampling from subregions using CMA-ES [16] (which is faster than TuRBO [10] used in the original LaMCTS). We emphasize again that LaP3’s region partitioning procedure is fully adaptive, in contrast to traditional MCTS approaches such as 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 maxi∈Ωk f(xi) rather than the mean value 1 n(Ωk) ∑ i∈Ωk f(xi) as the metric of goodness for each node k (and its associated region Ωk). This is driven by Theorem 1, 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 1 suggests that a lower-dimensional (smaller d) and smoother (smaller ck) representation leads to lower regret. Therefore, LaP3 employs a latent space as described below.

heading: 4.1 Latent Spaces For Partitioning and Sampling
text: LaP3 leverages a latent space Φs 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 Φs on which we construct the search space partition. Critically, we do not need s−1: we never decode from Φs back to Ω. Thus s can dramatically reduce the dimension of the partition
space, which may improve regularization due to the small number of samples, without suffering large reconstruction loss. s will be fixed rather than learned in this case. Once the partition has been constructed on Φs, and we select a leaf region to propose from, we sample new x from Ω as before.1
In principle, the sampling space can itself be a latent space Φh, with an encoder h and decoder h−1. That is, one runs the inner solver in Φh to propose samples before decoding back to Ω. h could be a principal component analysis (PCA) [49], a random network encoding [43], or a reversible flow [9], depending on the environment’s particular Ω 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 minh Ex [ w(x)‖h−1(h(x))− x‖2 ] , where w(x) is a weighting function emphasizing trajectories with high cumulative reward f(x). In this case, h and h−1 may be fine-tuned using each new (x, f(x)) pair when LaP3 proposes and queries a new trajectory x, or they may be pre-trained using a set of unlabeled x with w(x) ≡ 1. For consistency in our main experiments, we do not use a latent Φh, although we observe that using this second latent space can yield a slight performance in some environments (Appendix F.7).
5 LaP3 on Synthetic Environments
We test LaP3 on a diverse set of environments to evaluate its performance in different settings.
Baselines. We compare LaP3 to several baselines. LaMCTS is the original LaMCTS algorithm using CMA-ES as an inner solver, like LaP3. Random Shooting (RS) [36] samples random trajectories 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 a “traditional” MCTS method for continuous action spaces that builds a tree on actions at each timestep. iLQR [26] is a seminal gradient-based local optimization approach used extensively in controls. Finally, proximal policy optimization (PPO) [39] is a standard reinforcement learning algorithm.
LaP3 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 LaP3 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 a factor of up to 10 across our diverse environments, and performance is not overly sensitive to small changes (Appendix F.5).
We use MiniWorld [5] for continuous path planning and MiniGrid [6] for discrete.

heading: 5.1 MiniWorld
text: We consider the following 2D navigation tasks in MiniWorld. MazeS3: Agent navigates in a 3 by 3 maze to a goal. Greedy path planning gets stuck in local optima (Figure 3). FourRooms: Agent navigates from one room in a 2 by 2 configuration to a goal in the diagonally opposite room. Greedy path planning gets stuck in a corner. SelectObj: Open space with two goals. Large final reward when
1Specifically, we initialize the inner solver (CMA-ES in our experiments) using the pre-existing samples corresponding to the selected leaf region in Φs, and then propose new samples using that initialization.
reaching the farther goal, while a distance-based reward misleadingly points to the closer goal. For full environment specifics, see Appendix H.1.
We modify the original setup to use a continuous action space (∆x and ∆y), and provide a sparse reward (proximity to goal, with an additional bonus for reaching the goal) at end-of-episode. We use a high-dimensional top-down image view as the state. We featurize this image using a randomly initialized convolutional neural network, a reasonable feature extractor as shown in [43]. LaP3 uses periodic snapshots of the featurized state as the partition space Φs. That is, we collect all the observed states over the course of the full trajectory, and then form the latent space by concatenating every nth state (here n = 20), while discarding the rest to reduce overall dimensionality. Success is defined using a binary indicator for reaching the goal (far goal for SelectObj).
Results. LaP3 substantially outperforms all baselines on all three tasks, despite heavily tuning the baselines’ hyperparameters (Appendix G), showing that LaP3 works for challenging tasks containing suboptimal local maxima. In MazeS3, LaP3 succeeds but CEM gets stuck (Figure 3). VOOT, which builds an MCTS tree on actions at each timestep, struggles on all environments; LaP3 can be viewed as an extension of MCTS that performs better on such long-horizon 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, LaP3 solves nearly half of environment seeds within 4,000 queries of the oracle, whereas most baselines—including the original LaMCTS—quickly reach the near goal but struggle to escape this local optimum.
We also evaluate LaP3 when combined with a model-based approach, PETS [7], 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 [12, 14], we use 2D agent position as the state. As shown in Fig. 5, LaP3 substantially outperforms the authors’ original CEM implementation in the PETS framework, demonstrating that it is not reliant on access to the oracle model but can work with learned models as well.

heading: 5.2 MiniGrid
text: MiniGrid [6] is a popular sparse-reward symbolic environment for benchmarking RL algorithms. It contains tasks with discrete states and actions such as DoorKey (DK): pick up a key and open
the door connecting two rooms; MultiRoom (MR): traverse several rooms by opening doors; and KeyCorridor (KC), a combination of MR and DK: some doors are locked and require a key. As in MiniWorld, we add proximity to the goal to the final sparse reward.
In discrete action spaces, LaP3 optimizes the vector of all action probabilities over all timesteps, and takes the highest-probability action at each step. As in MiniWorld, we use periodic state snapshots featurized by a randomly initialized CNN as the partition space Φs. We compare LaP3 to the same baselines as in MiniWorld, except VOOT and iLQR which are designed for continuous tasks.
Results. LaP3 is equal to or better than baselines on all six tasks (Table 1). Especially in the hardest tasks with the most rooms (MR-N4S5, MR-N6), LaP3 improves substantially over baselines.

heading: 5.3 Analysis
text: We run several ablations on LaP3 in MiniWorld to justify our methodological choices. See Appendix F for further analysis on hyperparameter sensitivity, UCB metric, and latent spaces.
Region Selection in LaP3. We consider four alternative region selection methods. (1) LaP3-mean: using mean function value rather than max for UCB, as in LaMCTS [45]; (2) LaP3-nolatent: not using a latent space for partitioning; (3) LaP3-notree: directly selecting the leaf with the highest UCB score; and (4) LaP3-noUCB: only using node value rather than UCB. LaP3 greatly outperforms all variations in MiniWorld, justifying our design.
Data-driven space partition in LaP3 vs. random partitioning. We examine ck in Def. 1 and Lipschitz constant Lk in Corollary 1 to verify the theory. We conduct a preliminary analysis on LaP3’s tree after the full 2,000 queries (4,000 for SelectObj). At each intermediate node, we estimate Lk and ck of its children from the LaP3 partition, against a random partition that divides the node’s samples with the same ratio (see Appendix F.1 for estimation details). We then average the values for both LaP3 and random partitions over all nodes in the tree. We find that LaP3 does yield lower average Lk and ck (Table 2), indicating that our data-driven space partition is effective.
6 LaP3 on Real-World Applications

heading: 6.1 Compiler Phase Ordering
text: Compiler optimization applies a series of program transformations from a set of predefined optimizations (e.g., loop invariant code motion, function inlining [30]) to improve code performance. Since these optimizations are not commutative, the order in which they are applied is extremely important. This problem, known as phase ordering, is a core challenge in the compiler community. Current
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 [34, 42].
We apply LaP3 to the standard CHStone benchmarks [17], and use periodic snapshots of states as Φs and the identity as Φh. See Appendix H.2 for full environment details.
Results. LaP3 is 31% faster on average compared to OpenTuner, and 39% compared to -O3 (not shown in figure). Compared to a stronger PPO baseline using 50 samples (PPO_50) and to CMA-ES, we achieve up to 10% and 7% speedup respectively. Finally, compared to final PPO results at convergence after 4000 samples (PPO_4000) as an oracle, LaP3 does similarly on most tasks, despite being much more sample efficient (only 50 samples). Full results in Appendix E.

heading: 6.2 Molecular Design
text: Finally, we evaluate LaP3 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 [44], as property evaluations require expensive wet-lab assays.
Similar to [18], we fix a query budget and optimize several properties: QED: a synthetic measure of drug-likeness, relatively simpler to optimize; DRD2: a measure of binding affinity to a human dopamine receptor; HIV, the probability of inhibition potential for HIV; and SARS: the same probability for a variant of the SARS virus, related to the SARS-CoV-2 virus responsible for COVID19. All four properties have a 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 of wet-lab assays.
To run LaP3 on molecular design, we view the molecular string representation (SMILES string [48]) as the action sequence, similar to how many generative models generate molecules autoregressively [11, 25, 8, 50]. Following the state-of-the-art HierG2G model from [19], we learn a latent representation from a subset of ChEMBL [29], a dataset of 1.8 million drug-like molecules, without using any of its property labels (e.g., effectiveness in binding to a 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 [33, 20, 52, 50].
On this task only, the latent space is trained on additional unlabeled data, and is used as both the partition space Φs and sampling space Φh for LaP3. All baselines operate in the same space for fair comparison. Otherwise, all methods struggle to generate well-formed molecules of reasonable length.
Results. Figure 8 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, LaP3 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 LaP3 continues to improve with more function evaluations.

heading: 7 Conclusion
text: We propose LaP3, a 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. LaP3 particularly excels in environments with many difficult-to-escape local optima, substantially outperforming strong baselines on 2D navigation tasks as well as real-world compiler optimization and molecular design.
Acknowledgments and Disclosure of Funding
We thank the members of the Berkeley NLP group as well as our four anonymous reviewers for their helpful feedback. This work was supported by Berkeley AI Research, and the NSF through a fellowship to the first author.

Review summaries:
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.

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.