# Learning Search Space Partition for Black-box Optimization using Monte Carlo Tree Search

arXiv: https://arxiv.org/abs/2007.00708 · HTML: https://mlsanity.com/paper/2007.00708/

## Key facts

- Cited by 89 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Jul 2020.

## Built on by (most cited first, 30 of 89)

- [Bayesian Optimization is Superior to Random Search for Machine Learning Hyperparameter Tuning: Analysis of the Black-Box Optimization Challenge 2020](https://mlsanity.com/paper/2104.10201/) (2021)
- [Vanilla Bayesian Optimization Performs Great in High Dimensions](https://mlsanity.com/paper/2402.02229/) (2024)
- [Efficient Planning in a Compact Latent Action Space](https://mlsanity.com/paper/2208.10291/) (2022)
- [Increasing the Scope as You Learn: Adaptive Bayesian Optimization in Nested Subspaces](https://mlsanity.com/paper/2304.11468/) (2023)
- [Pareto Set Learning for Expensive Multi-Objective Optimization](https://mlsanity.com/paper/2210.08495/) (2022)
- [Neural Feature Search for RGB-Infrared Person Re-Identification](https://mlsanity.com/paper/2104.02366/) (2021)
- [LLaMoCo: Instruction Tuning of Large Language Models for Optimization Code Generation](https://mlsanity.com/paper/2403.01131/) (2024)
- [CompilerGym: Robust, Performant Compiler Optimization Environments for AI Research](https://mlsanity.com/paper/2109.08267/) (2021)
- [Local policy search with Bayesian optimization](https://mlsanity.com/paper/2106.11899/) (2021)
- [Monte Carlo Tree Search based Variable Selection for High Dimensional Bayesian Optimization](https://mlsanity.com/paper/2210.01628/) (2022)
- [Prioritized Architecture Sampling with Monto-Carlo Tree Search](https://mlsanity.com/paper/2103.11922/) (2021)
- [Model-Based Diffusion for Trajectory Optimization](https://mlsanity.com/paper/2407.01573/) (2024)
- [Local Bayesian optimization via maximizing probability of descent](https://mlsanity.com/paper/2210.11662/) (2022)
- [Bounce: Reliable High-Dimensional Bayesian Optimization for Combinatorial and Mixed Spaces](https://mlsanity.com/paper/2307.00618/) (2023)
- [Conditioning Sparse Variational Gaussian Processes for Online Decision-making](https://mlsanity.com/paper/2110.15172/) (2021)
- [SurCo: Learning Linear Surrogates For Combinatorial Nonlinear Optimization Problems](https://mlsanity.com/paper/2210.12547/) (2022)
- [The Behavior and Convergence of Local Bayesian Optimization](https://mlsanity.com/paper/2305.15572/) (2023)
- [Understanding High-Dimensional Bayesian Optimization](https://mlsanity.com/paper/2502.09198/) (2025)
- [Deep Learning for Bayesian Optimization of Scientific Problems with High-Dimensional Structure](https://mlsanity.com/paper/2104.11667/) (2021)
- [Posterior Inference with Diffusion Models for High-dimensional Black-box Optimization](https://mlsanity.com/paper/2502.16824/) (2025)
- [Continuation Path Learning for Homotopy Optimization](https://mlsanity.com/paper/2307.12551/) (2023)
- [Efficient Planning with Latent Diffusion](https://mlsanity.com/paper/2310.00311/) (2023)
- [We Still Don't Understand High-Dimensional Bayesian Optimization](https://mlsanity.com/paper/2512.00170/) (2025)
- [Triangulation candidates for Bayesian optimization](https://mlsanity.com/paper/2112.07457/) (2021)
- [Monte Carlo Tree Search based Hybrid Optimization of Variational Quantum Circuits](https://mlsanity.com/paper/2203.16707/) (2022)
- [Improving sample efficiency of high dimensional Bayesian optimization with MCMC](https://mlsanity.com/paper/2401.02650/) (2024)
- [Multi-objective Optimization by Learning Space Partitions](https://mlsanity.com/paper/2110.03173/) (2021)
- [Self-focusing virtual screening with active design space pruning](https://mlsanity.com/paper/2205.01753/) (2022)
- [Learning Regions of Interest for Bayesian Optimization with Adaptive Level-Set Estimation](https://mlsanity.com/paper/2307.13371/) (2023)
- [Constrained Bayesian Optimization Under Partial Observations: Balanced Improvements and Provable Convergence](https://mlsanity.com/paper/2312.03212/) (2023)

## Abstract (arXiv)

High dimensional black-box optimization has broad applications but remains a challenging problem to solve. Given a set of samples vxi, yi, building a global model (like Bayesian Optimization (BO)) suffers from the curse of dimensionality in the high-dimensional search space, while a greedy search may lead to sub-optimality. By recursively splitting the search space into regions with high/low function values, recent works like LaNAS shows good performance in Neural Architecture Search (NAS), reducing the sample complexity empirically. In this paper, we coin LA-MCTS that extends LaNAS to other domains. Unlike previous approaches, LA-MCTS learns the partition of the search space using a few samples and their function values in an online fashion. While LaNAS uses linear partition and performs uniform sampling in each region, our LA-MCTS adopts a nonlinear decision boundary and learns a local model to pick good candidates. If the nonlinear partition function and the local model fits well with ground-truth black-box function, then good partitions and candidates can be reached with much fewer samples. LA-MCTS serves as a meta-algorithm by using existing black-box optimizers (e.g., BO, TuRBO) as its local models, achieving strong performance in general black-box optimization and reinforcement learning benchmarks, in particular for high-dimensional problems.