Source-linked AI summary
Learning Search Space Partition for Black-box Optimization using Monte Carlo Tree Search
Linnan Wang, Rodrigo Fonseca, Yuandong Tian
TL;DR
High-dimensional black-box optimization is difficult because global models require many samples, while purely greedy search can miss better regions. LA-MCTS addresses this by recursively learning nonlinear, objective-dependent partitions and using local optimizers such as BO or TuRBO within selected regions. Across challenging black-box and reinforcement-learning benchmarks, LA-MCTS paired with TuRBO outperforms state-of-the-art Bayesian, evolutionary, and tree-search solvers, though exploration can reduce sample efficiency on high-dimensional MuJoCo tasks.
Problem
High-dimensional, highly nonlinear black-box objectives require large model classes and many samples, while fixed space partitions do not adapt to the objective.
Method
LA-MCTS recursively partitions the search space using function-value clusters and nonlinear classifiers, then uses UCB and local optimizers to select promising regions and candidates.
Results
LA-MCTS paired with TuRBO outperforms state-of-the-art Bayesian, evolutionary, and Monte Carlo tree-search solvers across MuJoCo, trajectory-optimization, reinforcement-learning, and high-dimensional synthetic benchmarks.
Takeaways & Limitations
LA-MCTS is an effective meta-method for improving BO by learning search-space partitions that focus optimization on promising regions.
Takeaways & Limitations
LA-MCTS is less sample-efficient than gradient-based methods on high-dimensional MuJoCo tasks because exploration imposes an excessive burden.
Abstract
from arXiv · showhide
High dimensional black-box optimization has broad applications but remains a challenging problem to solve. Given a set of samples $\{\vx_i, y_i\}$, 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 \emph{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.
1 Introduction
High-dimensional black-box optimization is difficult because global models require many samples and fixed partitions do not adapt to the objective. LA-MCTS recursively learns objective-dependent partitions and uses local optimizers to focus sampling on promising regions.
- Motivation: Without structure beyond local smoothness, black-box optimization can require exponential time because every candidate may need evaluation.Learning a surrogate can reduce samples when the model class is small and approximates the objective well.
- Motivation: High-dimensional, highly nonlinear objectives require large model classes that need many samples before generalizing well.Prior work also observes that myopic BO can over-explore search-space boundaries.
- Motivation: Existing space-partitioning methods use fixed criteria independent of the objective, motivating partitions learned from sampled function values.A recursively learned classifier can require less accuracy than a global regressor if it assigns samples to the right subregion.
- LA-MCTS: LA-MCTS recursively learns hierarchical partitions by clustering samples by function value, training a classifier, and separating good from bad subregions.UCB balances exploration and exploitation by assigning more samples to promising regions while retaining exploration.
- LA-MCTS: LA-MCTS replaces LaNAS's linear boundary and uniform sampling with nonlinear boundaries and local models such as BO, making it a meta-algorithm for broader black-box optimization.The method is presented as extending LaNAS beyond neural architecture search to generic black-box problems.
- Results: LA-MCTS paired with TuRBO outperforms state-of-the-art Bayesian, evolutionary, and tree-search solvers across several challenging benchmarks.The reported benchmarks include MuJoCo locomotion, trajectory optimization, reinforcement learning, and high-dimensional synthetic functions.
2 Related works
Related work addresses high-dimensional black-box optimization through scalable Bayesian models, low-dimensional embeddings, evolutionary methods, and space-partitioning search. LA-MCTS extends these directions by learning objective-dependent partitions and combining them with local Bayesian optimization.
- Bayesian optimization: Bayesian optimization has broad use but typically succeeds with fewer than 15 parameters and a few thousand evaluations, motivating scalable approximations.Examples replace or approximate Gaussian processes with random forests, Bayesian neural networks, or tree-structured density estimators.
- Bayesian optimization: High-dimensional BO methods decompose objectives or embed them in low-dimensional subspaces, but decomposition remains challenging and scalability can depend on the number of structures.REMBO and related methods optimize in low-dimensional spaces and project candidates back into the original space.
- Bayesian optimization: Trust-region BO uses local Gaussian-process modeling and has outperformed other high-dimensional BO methods across varied tasks.Local modeling targets promising regions rather than fitting one global model over the entire search space.
- Evolutionary algorithms: Evolutionary algorithms such as CMA-ES and Differential Evolution generate candidates through adaptive covariance modeling or population-vector perturbations.Shiwa is described as a meta-method for automatically selecting evolutionary algorithms based on hyperparameters.
- Monte Carlo tree search: MCTS-related methods partition search spaces recursively, using optimistic bounds, relaxed smoothness assumptions, stochastic variants, or Voronoi partitions.LA-MCTS instead learns partitions from the distribution of objective values and improves sampling within selected regions using BO.
3 Methodology
LA-MCTS progressively partitions the search space into high- and low-performing regions, selects among them with UCB, and applies Bayesian optimization within the selected region. Its latent actions use learned nonlinear boundaries from sampled inputs and function values to refine promising regions during optimization.
- Search-tree construction: LA-MCTS represents search-space regions as tree nodes and recursively splits each region into high- and low-performing disjoint subregions.The tree grows as optimization proceeds, allowing leaves to focus increasingly on promising regions.
- Latent actions: Latent actions cluster sampled inputs by performance with K-means, then train an SVM to generalize the resulting good/bad partition to unseen points.The higher-average-value cluster defines the good region, while the learned nonlinear SVM boundary forms the latent action.
- Dynamic refinement: The tree dynamically splits leaves when their sample count exceeds threshold θ, refining value estimates and deepening toward promising regions.New samples reduce regional-value regret until a plateau, after which splitting continues the search refinement.
- Region selection: UCB selects a root-to-leaf path by balancing exploration and exploitation instead of greedily choosing only the currently best region.When C_p = 0, UCB becomes a purely greedy policy; the ablation identifies exploration as critical to performance.
- Local sampling: After selection, LA-MCTS optimizes f(x) within the constrained region using Bayesian optimization, with SVMs along the path defining the constraint.The workflow consists of dynamic splitting, UCB-based selection, and local BO sampling.
- Local sampling: For arbitrary selected regions, rejected sampling generates feasible initialization or acquisition-optimization points by sampling within an expanding hyper-cube and rejecting outliers.This procedure addresses the difficulty of sampling inside SVM-defined regions, especially in high-dimensional spaces.
- Empirical behavior: On six MuJoCo locomotion tasks, LA-MCTS outperforms baselines, with stronger benefits on higher-dimensional Ant and Humanoid problems after 30k samples.The reported advantage accompanies relatively high variance from built-in exploration, while other methods can become trapped in local optima.
4 Experiments
Experiments evaluate LA-MCTS across black-box optimization benchmarks, reinforcement-learning tasks, synthetic functions, and ablations. Results show strong performance and consistent improvements over several baselines, while revealing reduced sample efficiency against gradient methods on high-dimensional MuJoCo tasks.
- Benchmark comparisons: LA-MCTS outperforms various state-of-the-art black-box solvers across MuJoCo, trajectory optimization, reinforcement learning, and high-dimensional synthetic benchmarks.The comparisons include Bayesian optimization, evolutionary algorithms, and Monte Carlo tree search methods.
- MuJoCo locomotion tasks: On MuJoCo locomotion tasks, LA-MCTS consistently outperforms baselines, with the clearest advantage on high-dimensional ant and humanoid problems.The humanoid task has 6392 parameters, illustrating the scale of the evaluated problems.
- MuJoCo locomotion tasks: LA-MCTS improves TuRBO by shrinking the modeled region and initializing each restart from a promising region.The learned partitions allow TuRBO to fit a better local model in smaller regions.
- Small-scale benchmarks: LA-MCTS consistently boosts TuRBO and BO on Ackley and Rosenbrock, especially in high-dimensional tasks.For synthetic functions, solver performance varies by function, but LA-MCTS improves TuRBO on both functions.
- Validation of LA-MCTS: The selected-region regret decreases as the number of splits increases, while regret spikes indicate exploration of less promising regions.This behavior is reported for Ackley-20d.
- Validation of LA-MCTS: On 2d-Ackley, LA-MCTS catches the global optimum after initialization and progressively shrinks the selected region through SVM-defined boundaries.The initial selected region misses the optimum because of random initialization.
- Ablations on hyper-parameters: Too little exploration performs worst, while excessive exploration is also undesirable; the authors recommend Cp at 10% to 1% of max f(x).This ablation identifies a practical exploration range for HalfCheetah.
- Ablations on hyper-parameters: Polynomial and RBF SVM kernels yield more flexible boundaries and better performance than linear boundaries in the ablation.The threshold θ also trades off faster tree growth against unreliable boundary estimation when made too small.
5 Conclusion and future research
The paper presents LA-MCTS as a meta-method for partitioning high-dimensional black-box search spaces and improving Bayesian Optimization. It reports comprehensive evaluations and identifies multi-objective optimization as future work.
- LA-MCTS learns to partition the search space for Bayesian Optimization so it can focus on promising regions.
- Comprehensive evaluations show that LA-MCTS improves Bayesian Optimization as an effective meta-method.
- The authors plan to extend space partitioning to Multi-Objective Optimizations.
6 Broader impact
The paper situates black-box optimization in diverse practical applications involving heterogeneous, high-dimensional problems. It suggests LA-MCTS may improve productivity at minimal cost when gradients are unavailable and reports no anticipated negative social consequences.
- Black-box optimization is used for hyper-parameter tuning, integrated-circuit design, reinforcement learning, and other applications.
- Many real-world optimization problems are heterogeneous and high-dimensional, while existing black-box solvers struggle to achieve reasonable performance.
- Switching to LA-MCTS may improve productivity at minimal cost when optimizing functions without known gradients.
- The authors do not foresee negative social consequences from the method.
A.1 Hyper-parameter settings for all baselines in benchmarks
The appendix documents benchmark configurations for LA-MCTS, TuRBO, LaNAS, and baseline optimizers across MuJoCo, synthetic functions, lunar landing, and trajectory optimization. Settings include batch size, initialization, kernels, thresholds, and runtime details.
- MuJoCo experiments use batch size 1 and reuse ARS policy and evaluation code alongside implementations from cited repositories and SciPy.
- LA-MCTS uses 30 initialization samples, RBF or linear SVM kernels by task difficulty, Cp=10, and splitting threshold θ=100 in MuJoCo.
- LA-MCTS uses TuRBO-1 for sampling, while TuRBO uses 30 initialization samples and MuJoCo experiments use TuRBO-20 with 20 independent trust regions.
- LaNAS uses 30 initialization samples, search-tree height 8, and Cp=10; other baselines generally use reference or library default settings.
- Synthetic-function, lunar-landing, and trajectory-optimization experiments use batch size 1, Cp=1, and splitting threshold θ=20 for LA-MCTS.
- LaNAS and several derivative-free methods collect thousands of samples quickly, whereas LA-MCTS and TuRBO collect 104 samples in an hour using 1 V100 GPU.
A.2 Additional experiment results
Additional experiments compare LA-MCTS with TuRBO and other methods on synthetic functions, lunar landing, and trajectory optimization. The results show consistent improvement over TuRBO and baselines, while visualizations track selected regions and the global optimum.
- On synthetic functions, the best method varies by function, but LA-MCTS consistently improves TuRBO and ranks among the top methods overall.
- On Lunar landing and Trajectory Optimization, LA-MCTS consistently outperforms the baselines.
- The iteration visualization identifies the selected region with purple and the global optimum with a red star.