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

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

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.