Monte Carlo Tree Search based Variable Selection for High Dimensional Bayesian Optimization
This addresses the challenge of scaling Bayesian optimization to high-dimensional problems, which is crucial for applications like neural architecture search and robotics, though it appears incremental as it builds on existing variable selection and MCTS techniques.
The paper tackles the curse of dimensionality in Bayesian optimization by proposing MCTS-VS, a variable selection method based on Monte Carlo tree search, which achieves state-of-the-art performance on high-dimensional synthetic functions and real-world problems like NAS-bench and MuJoCo tasks.
Bayesian optimization (BO) is a class of popular methods for expensive black-box optimization, and has been widely applied to many scenarios. However, BO suffers from the curse of dimensionality, and scaling it to high-dimensional problems is still a challenge. In this paper, we propose a variable selection method MCTS-VS based on Monte Carlo tree search (MCTS), to iteratively select and optimize a subset of variables. That is, MCTS-VS constructs a low-dimensional subspace via MCTS and optimizes in the subspace with any BO algorithm. We give a theoretical analysis of the general variable selection method to reveal how it can work. Experiments on high-dimensional synthetic functions and real-world problems (i.e., NAS-bench problems and MuJoCo locomotion tasks) show that MCTS-VS equipped with a proper BO optimizer can achieve state-of-the-art performance.