证明了无悔学习在博弈中逼近最优福利所需迭代次数的下界。
Barriers to Welfare Maximization with No-Regret Learning
- 提出计算稀疏近似协同均衡的下界，刻画学习迭代复杂度
- 证明在多项式时间内无法实现非平凡稀疏性，与最大团问题难解相关
- 适用于关注算法收敛性与福利优化的博弈学习研究者
在线学习与博弈论交叉领域的一个经典结果表明，重复交互的无悔玩家将收敛至粗略协同均衡（CCE），一种自然的博弈解概念。尽管该问题历史悠久且近年备受关注，一个基本问题仍未解决：无悔玩家需要多少轮迭代才能逼近均衡？本文首次建立了两玩家（一般和）博弈中，要求所达CCE近似最优社会福利时的计算下界。技术上，通过证明近似T-稀疏CCE（T个乘积分布的混合）的计算下界，限制了即使在集中式计算模型下无悔学习的迭代复杂度。方法扩展了Gilboa和Zemel（1989）从最优纳什均衡到稀疏近似CCE的经典归约。特别地，我们证明最大团问题的不可近似性意味着多项式时间内无法实现非平凡稀疏性。此外，借助植团猜想，进一步将硬性结果推广至低精度情形。
原文摘要 · Abstract (English)
A celebrated result in the interface of online learning and game theory guarantees that the repeated interaction of no-regret players leads to a coarse correlated equilibrium (CCE) -- a natural game-theoretic solution concept. Despite the rich history of this foundational problem and the tremendous interest it has received in recent years, a basic question still remains open: how many iterations are needed for no-regret players to approximate an equilibrium? In this paper, we establish the first computational lower bounds for that problem in two-player (general-sum) games under the constraint that the CCE reached approximates the optimal social welfare (or some other natural objective). From a technical standpoint, our approach revolves around proving lower bounds for computing a near-optimal $T$-sparse CCE -- a mixture of $T$ product distributions, thereby circumscribing the iteration complexity of no-regret learning even in the centralized model of computation. Our proof proceeds by extending a classical reduction of Gilboa and Zemel [1989] for optimal Nash to sparse (approximate) CCE. In particular, we show that the inapproximability of maximum clique precludes attaining any non-trivial sparsity in polynomial time. Moreover, we strengthen our hardness results to apply in the low-precision regime as well via the planted clique conjecture.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。