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系统提供了新的方法。该项目包括一项教育计划，该计划纳入了研究生和本科课程的课程发展，以及对研究生的培训以及本科生的研究机会。 该项目的第一部分着重于凹面游戏，其中包括传统游戏理论所研究的许多游戏，包括所有有限的游戏。如果每个代理商从凸组中选择策略，则游戏是凹面的，而他们的效用是他们自己策略的凹功能。研究人员旨在开发高维游戏中计算和学习均衡的最佳取消偶联算法。这些游戏在ML应用中很常见，高维度通常来自众多代理或复杂的可用操作。未耦合的算法需要对游戏和小玩家协调的最少知识，这使得它们特别适合于高维游戏和实践中首选的算法类型。该项目的第二部分将重点转移到了非concave游戏中，在该游戏中，代理商可能具有非concave实用程序。鉴于常规平衡的存在通常会取决于实用程序功能的凹陷，因此研究人员计划彻底重新评估基础解决方案概念。这部分的主要目标是确定针对非concave游戏的适当解决方案概念，并了解其计算复杂性。该奖项反映了NSF的法定任务，并认为使用基金会的知识分子优点和更广泛的影响评估标准，认为值得通过评估来获得支持。