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

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

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.