静5青年讲座 | Fast swap regret minimization and applications...
Fast swap regret minimization and applications to approximate correlated equilibria
报告人
Dr. Binghui Peng
Columbia University
时 间
2024年6月18日 星期二 4:00pm
地 点
静园五院204
Host
邓小铁 教授
Abstract
We give a simple and computationally efficient algorithm that, for any constant , obtains distributional swap regret within only rounds; this is an exponential improvement compared to the super-linear number of rounds required by the state-of-the-art algorithm, and resolves the main open problem of [Blum-Mansour JMLR'07]. Our algorithm has an exponential dependence on , but we prove a new, matching lower bound.
Our algorithm for swap regret implies faster convergence to -Correlated Equilibrium ( -CE) in several regimes: For normal form two-player games with actions, it implies the first uncoupled dynamics that converges to the set of -CE in polylogarithmic rounds; a -bit communication protocol for -CE in two-player games (resolving an open problem mentioned by [Babichenko-Rubinstein STOC'2017, Ganor-CS APPROX'18, Goos-Rubinstein FOCS'2018}; and an -query algorithm for -CE (resolving an open problem of [Babichenko 2020] and obtaining the first separation between -CE and -Nash equilibrium in the query complexity model). For extensive-form games, our algorithm implies a PTAS for normal form correlated equilibria, a solution concept widely conjectured to be computationally intractable (e.g. [Stengel-Forges MOR'08, Fujii'23]).
Based on joint work with Aviad Rubinstein.
Biography
Binghui Peng recently obtains his Ph.D. from Columbia University, advised by Christos Papadimitriou and Xi Chen. Previously, he studied Computer Science with the Yao Class in Tsinghua. He studies the theory of computation and develops algorithms and complexity theory for machine learning, artificial intelligence and game theory. His research works have addressed long-standing questions in learning theory and game theory, and his research papers were published in theory conferences (STOC/FOCS/SODA; in the latter he has best student paper award) and ML conferences (NeurIPS/ICLR/ACL).
往 期 讲 座
— 版权声明 —
本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。
点“阅读原文”查看海报