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

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

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.