High dimensional black-box optimization has broad applications but remains a\nchallenging problem to solve. Given a set of samples $\\{\\vx_i, y_i\\}$, building\na global model (like Bayesian Optimization (BO)) suffers from the curse of\ndimensionality in the high-dimensional search space, while a greedy search may\nlead to sub-optimality. By recursively splitting the search space into regions\nwith high/low function values, recent works like LaNAS shows good performance\nin Neural Architecture Search (NAS), reducing the sample complexity\nempirically. In this paper, we coin LA-MCTS that extends LaNAS to other\ndomains. Unlike previous approaches, LA-MCTS learns the partition of the search\nspace using a few samples and their function values in an online fashion. While\nLaNAS uses linear partition and performs uniform sampling in each region, our\nLA-MCTS adopts a nonlinear decision boundary and learns a local model to pick\ngood candidates. If the nonlinear partition function and the local model fits\nwell with ground-truth black-box function, then good partitions and candidates\ncan be reached with much fewer samples. LA-MCTS serves as a\n\\emph{meta-algorithm} by using existing black-box optimizers (e.g., BO, TuRBO)\nas its local models, achieving strong performance in general black-box\noptimization and reinforcement learning benchmarks, in particular for\nhigh-dimensional problems.\n