AF: Small: Equilibrium Computation and Multi-Agent Learning in High-Dimensional Games

在过去的十年中，机器学习（ML）在许多应用中取得了重大进展。这一成功在很大程度上归功于通过使用高效优化算法最小化单个损失函数来训练ML系统的范例。然而，形势正在发生变化，许多新兴的机器学习应用被更好地描述为多个智能代理或算法之间的游戏。这些游戏可以是显式的，如在市场、交通路由、游戏解决系统（如AlphaZero）和多智能体强化学习（RL）系统中看到的，也可以是隐式的，如在生成对抗网络、对抗示例、鲁棒优化等情况下。虽然博弈论提供了一个理解这些代理相互作用的镜头，但其经典形式难以解决当代ML应用中的挑战。这是因为传统博弈论通常专注于更简单、低维度的游戏，而ML则经常处理复杂、高维的游戏。该项目旨在为这些复杂的高维博弈提供一种新的理论，从而为分析、训练和设计多智能体ML系统提供新的方法。该项目包括一个教育计划，包括研究生和本科课程的课程开发，以及研究生的培训和本科生的研究机会。项目的第一部分侧重于凹博弈，它包含了许多传统博弈论所研究的内容，包括所有有限博弈。如果每个代理都从凸集中选择策略，那么游戏就是凹的，并且他们的效用在他们自己的策略中是凹函数。研究者的目标是开发最优解耦算法的计算和学习均衡在高维游戏。这些游戏在ML应用程序中很常见，高维通常来自大量代理或复杂的可用操作。非耦合算法需要最少的游戏知识和很少的玩家协作，这使得它们特别适合高维游戏和实践中的首选算法类型。该项目的第二部分将重点转移到非凹博弈，其中代理可能具有非凹效用。考虑到传统的均衡存在往往取决于效用函数的凹性，研究者计划彻底重新评估基本的解概念。这部分的主要目标是确定非凹游戏的适当解决方案概念，并了解其计算复杂性。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Over the last decade, Machine Learning (ML) has made significant strides in numerous applications. This success is largely attributed to the paradigm of training ML systems by minimizing a single loss function using efficient optimization algorithms. Yet, the landscape is shifting, with many emerging ML applications being better described as games played between multiple intelligent agents or algorithms. These games can be explicit, as seen in markets, traffic routing, game-solving systems (such as AlphaZero), and multi-agent Reinforcement Learning (RL) systems, or implicit, as in the case of generative adversarial networks, adversarial examples, robust optimization, and so on. While game theory offers a lens to understand these agent interactions, its classical form struggles to address challenges in contemporary ML applications. This is because traditional game theory often focuses on simpler, low-dimensional games, while ML frequently grapples with complex, high-dimensional ones. This project aims to provide a new theory for these complex, high-dimensional games, and as a result, offer new methods to analyze, train, and design multi-agent ML systems. This project includes an education plan that incorporates course development of both graduate and undergraduate courses, as well as training for graduate students and research opportunities for undergraduates. The first part of the project focuses on concave games, which encompass many that traditional game theory has studied, including all finite games. A game is concave if each agent chooses their strategy from a convex set, and their utility is a concave function in their own strategy. The investigator aims to develop optimal uncoupled algorithms for computing and learning equilibria in high-dimensional games. These games are common in ML applications, and the high-dimensionality often arises from numerous agents or complex available actions. Uncoupled algorithms require minimal knowledge about the game and little player coordination, making them especially suited for high-dimensional games and the preferred type of algorithms in practice. The second part of the project shifts focus to non-concave games, where agents may have non-concave utilities. The investigator plans to thoroughly reassess foundational solution concepts, given that conventional equilibrium existence often hinges on the concavity of utility functions. The main goal of this part is to identify appropriate solution concepts for non-concave games and understand their computational complexity.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.