CRII: RI: Characterizing Algorithm-Relative Difficulty of Agent Benchmarks

有各种各样的人工智能（AI）算法被设计用来为许多不同的现实世界问题做出决策。人工智能研究的一个重要任务是确定这些算法解决各种问题的效果。研究人员经常使用游戏等较小的问题来研究算法决策。例如，围棋可以用来测试战略决策，街机游戏可以用来测试战术决策。这些测试问题的难度可能因不同的算法而异，并且可能取决于可用的计算时间等因素。该项目的目的是系统地理解人工智能挑战问题对标准决策算法构成的困难，以及这些结论对问题设计、问题规模、计算资源和算法配置的变化的鲁棒性。该项目将使用三种方法来开发算法相关基准难度的度量，研究实时统计规划和强化学习的标准决策算法。首先，系统地生成每个基准问题的缩放曲线，显示性能如何随给定给代理的计算资源以及问题大小、动作空间大小和其他可配置参数而缩放。其次，识别可靠区分算法性能的问题，即某些算法表现非常好而其他算法表现非常差的问题，阐明它们的相对优势。第三，应用最新的算法，将分析解决方法扩展到更大的问题，可能接近那些用作最新人工智能基准的方法，以便在可能计算最优时，将缩放曲线与最优性能进行比较。这样做有可能提高我们对广泛使用的人工智能和机器学习算法的理解，特别是某些问题特征如何影响这些算法的性能。这些信息可以潜在地用于设计更好、更健壮的算法，这些算法可以在各种问题设置中表现良好。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

There are a wide variety of artificial intelligence (AI) algorithms designed to make decisions for a number of different real-world problems. One important task of AI research is to determine how well these algorithms solve various problems. Researchers often use smaller problems such as games to study algorithmic decision-making. For example, the game Go can be used to test strategic decision-making, or arcade games to test tactical decision-making. How hard these test problems are may vary for different algorithms, and can depend on factors such as how much computation time is available. The purpose of this project is to systematically understand the difficulty that AI challenge problems pose to standard decision-making algorithms, as well as how robust such conclusions are to variations in problem design, problem size, computational resources, and algorithm configuration.This project will use three methods to develop metrics for algorithm-relative benchmark difficulty, studying standard decision-making algorithms for both real-time statistical planning and reinforcement learning. First, systematic generation of scaling curves on each benchmark problem showing how performance scales with computational resources given to an agent, as well as with problem size, size of the action space, and other configurable parameters. Second, identification of problems that reliably differentiate algorithm performance, i.e., those on which some algorithms perform very well but others very poorly, illuminating their relative strengths. Third, applying recent algorithms that scale up analytical solution methods to larger problems, possibly approaching those used as more recent AI benchmarks, in order to compare scaling curves with optimal performance, when optima are possible to compute. Doing so has the potential to improve our understanding of broadly used AI and machine-learning algorithms, particularly how certain problem features impact the performance of these algorithms. Such information can potentially be used to design better and more robust algorithms that perform well across a variety of problem settings.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.