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

American University, Washington DC

Investigators

Abstract

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.