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

CIF：小型：高效大规模蒙特卡罗树搜索的理论和算法

• 批准号: 2327013
• 负责人: Kwang-Sung Jun
• 金额: $ 59.92万
• 依托单位: University of Arizona
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-12-01 至 2026-11-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2327013&HistoricalAwards=false
• 关键词: CIF; Small; Theory; Algorithms; Efficient

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.

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