CIF: Small: Theory and Algorithms for Efficient and Large-Scale Monte Carlo Tree Search

蒙特卡罗树搜索(MCTS)是一种通用的在线计划方法，用于顺序决策问题，如强化学习，最近在现实世界的问题中显示出经验上的成功，包括游戏、化学合成、材料/药物发现和数值算法。然而，现有的MCTS理论与实践之间存在着巨大的差距，这是因为(I)已知的称为树的上置信限(UCT)的事实上的标准MCTS算法是可证明次优的，(Ii)现有的理论仅限于渐近或最坏情况分析，以及(Iii)MCTS算法的最优性能比率未知。这意味着最先进的MCTS方法可能还远远没有充分发挥其潜力，需要进一步的发展来为下一代更大、更复杂的决策问题做准备。本项目致力于通过开发具有强大数学性能保证的新的MCTS算法，建立最优性能比率，并在现实应用中对它们进行评估，在MCTS方法的理论和实践之间架起一座桥梁。该项目将教育与研究相结合，开发了一个课程模块，并建立了本科生的跨学科团队，他们将与材料科学家密切合作，评估开发的材料发现任务算法。该项目包括三个主要方向：MCTS的基础、大规模MCTS和MCTS的实验设计。每个方向都包含几个主要目标：(I)对于MCTS的基础，重点是改进最大均值估计和利用相关问题(称为纯探索)的工具来开发具有强保证的算法，并研究MCTS的信息论极限；(Ii)对于大规模MCTS，重点是分析和改进现有的针对大规模MCTS问题的启发式算法，如渐进加宽、增量深度扩展和函数逼近；(Iii)对于MCTS的实验设计，重点是开发实验设计方法，以有效地训练小样本MCTS的函数逼近。除了理论和算法的发展，该项目还旨在实现所有作为开源软件开发的算法，使用基准数据集对它们进行评估，并通过本科生的跨学科团队将它们应用于材料科学任务，作为教育目标的一部分。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Monte Carlo tree search (MCTS) is a versatile online planning methodology for sequential decision-making problems such as reinforcement learning that has recently shown empirical success in real-world problems including games, chemical synthesis, materials/drug discovery, and numerical algorithms. However, there is a huge gap between existing MCTS theory and practice because (i) the de facto standard MCTS algorithm called upper confidence bound for trees (UCT) is known to be provably suboptimal, (ii) existing theories are limited to asymptotic or worst-case analyses, and (iii) the optimal performance rates of MCTS algorithms are not known. This implies that the state-of-the-art MCTS methods might still be far from realizing their full potential, and further developments are required to prepare for the next generations of much larger and more complex decision-making problems. This project focuses on bridging the gap between theory and practice in MCTS methodology by developing novel MCTS algorithms with strong mathematical performance guarantees, establishing the optimal performance rates, and evaluating them in real-world applications. This project integrates education into research by developing a course module and building interdisciplinary teams of undergraduates who will work closely with material scientists to evaluate the developed algorithms on materials discovery tasks. The project consists of three main directions: the foundations of MCTS, large-scale MCTS, and the design of experiments for MCTS. Each direction contains several main objectives: (i) for the foundations of MCTS, the focus is to improve maximum mean estimator and leverage tools from a related problem called pure exploration to develop algorithms with strong guarantees and study information-theoretic limits of MCTS; (ii) for the large-scale MCTS, the focus is to analyze and improve existing heuristics for large-scale MCTS problems such as progressive widening, incremental depth expansion, and function approximations; (iii) for the design of experiments for MCTS, the focus is to develop experimental design methods to efficiently train function approximations for MCTS with a small number of samples. In addition to theoretical and algorithmic developments, the project also aims at implementing all algorithms developed as open-source software, evaluating them using benchmark datasets, and applying them to material science tasks via the interdisciplinary teams of undergraduates as part of the educational aim.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.