Partitioning and Gaussian Processes for Accelerating Sampling in Monte Carlo Tree Search for Continuous Decisions
Partitioning and Gaussian Processes for Accelerating Sampling in Monte Carlo Tree Search for Continuous Decisions
复制标题
DOI：
10.1109/wsc52266.2021.9715405
复制
发表时间：
2021-12
期刊：
影响因子：
--
通讯作者：
Menghan Liu;Giulia Pedrielli;Yumeng Cao
中科院分区：
文献类型：
--
作者：
Menghan Liu;Giulia Pedrielli;Yumeng Cao
我们提出了Part-MCTS，用于在蒙特卡罗树搜索算法的每个阶段对连续决策进行采样。在每个MCTS阶段，Part-MCTS依次划分决策空间，并保留高斯过程的集合来描述目标函数的景观。基于最小值估计的分类标准使我们能够将注意力集中在具有更好预测行为的区域，从而减少其他地方的评估工作。在每个子区域内，我们可以使用任何抽样分布，我们建议使用贝叶斯优化抽样。我们将我们的方法与KR-UCT（Yee et al. 2016）作为最先进的竞争产品进行了比较。Part-MCTS在一组非线性测试函数上实现了更好的准确性，并且能够在单次运行中识别多个有希望的解决方案。当来自一个阶段的多个解决方案可以在后续阶段保留和扩展时，这可能很重要。
We propose Part-MCTS for sampling continuous decisions at each stage of a Monte Carlo Tree Search algorithm. At each MCTS stage, Part-MCTS sequentially partitions the decision space and keeps a collection of Gaussian processes to describe the landscape of the objective function. A classification criteria based on the estimation of the minimum allows us to focus the attention on regions with better predicted behavior, reducing the evaluation effort elsewhere. Within each subregion, we can use any sampling distribution, and we propose to sample using Bayesian optimization. We compare our approach to KR-UCT (Yee et al. 2016) as state of the art competitor. Part-MCTS achieves better accuracy over a set of nonlinear test functions, and it has the ability to identify multiple promising solutions in a single run. This can be important when multiple solutions from a stage can be preserved and expanded at subsequent stages.