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

AF：小：高维游戏中的平衡计算和多智能体学习

• 批准号: 2342642
• 负责人: Yang Cai
• 金额: $ 59.97万
• 依托单位: Yale University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2024
• 资助国家: 美国
• 起止时间: 2024-03-01 至 2027-02-28
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2342642&HistoricalAwards=false
• 关键词: AF; Small; Equilibrium; Computation; Multi

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.

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