REINFORCEMENT LEARNING

CORE MACHINE LEARNING

Learning Search Space Partition for Path Planning

November 02, 2021

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 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 [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.

Download the Paper

AUTHORS

Written by

Kevin Yang

Tianjun Zhang

Chris Cummins

Brandon Cui

Benoit Steiner

Linnan Wang

Joseph E. Gonzalez

Dan Klein

Yuandong Tian

Publisher

NeurIPS

Research Topics

Reinforcement Learning

Core Machine Learning

Related Publications

December 06, 2021

COMPUTER VISION

CORE MACHINE LEARNING

Debugging the Internals of Convolutional Networks

Bilal Alsallakh, Narine Kokhlikyan, Vivek Miglani, Shubham Muttepawar, Edward Wang (AI Infra), Sara Zhang, David Adkins, Orion Reblitz-Richardson

December 06, 2021

December 06, 2021

CORE MACHINE LEARNING

Revisiting Graph Neural Networks for Link Prediction

Yinglong Xia

December 06, 2021

December 06, 2021

INTEGRITY

CORE MACHINE LEARNING

BulletTrain: Accelerating Robust Neural Network Training via Boundary Example Mining

Weizhe Hua, Yichi Zhang, Chuan Guo, Zhiru Zhang, Edward Suh

December 06, 2021

December 06, 2021

THEORY

CORE MACHINE LEARNING

Learning on Random Balls is Sufficient for Estimating (Some) Graph Parameters

Takanori Maehara, Hoang NT

December 06, 2021

Help Us Pioneer The Future of AI

We share our open source frameworks, tools, libraries, and models for everything from research exploration to large-scale production deployment.