  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.
