证明了在博弈中逼近相关均衡所需迭代次数的下界，说明现有算法已接近最优。
Computational Lower Bounds for Regret Minimization in Normal-Form Games
- 采用平方和松弛与验证预言机框架，分析学习算法的计算极限。
- 证明在ε=多项式1/log n时，无法高效计算log n稀疏的相关均衡。
- 结果揭示了多乘子权重更新等算法的近似最优性，适合博弈论与在线学习研究者。
在线学习与博弈论之间的经典联系表明，最小化交换后悔的玩家会收敛到相关均衡（CE）——一个重要的博弈论解概念。尽管该问题历史悠久且近年备受关注，但一个基本问题仍未解决：在标准正常形式表示下，逼近均衡需要多少轮迭代？本文提供了证据，表明现有学习算法（如多乘子权重更新）已接近最优。具体而言，我们证明了计算均匀混合的T个乘积分布构成的均匀T-稀疏相关均衡的下界；这些下界直接限制了博弈中计算受约束的后悔最小化算法。我们的结果基于Kothari和Mehta（STOC 2018）提出的算法框架，该框架结合平方和（SoS）松弛与验证预言机访问，目标是下界确定SoS松弛的阶数或验证预言机的查询次数。本文获得两个硬性结果：当ε = 多项式(1/log n)时，无法计算均匀log n-稀疏相关均衡；当ε = 多项式(1/n)时，无法计算均匀n^{1−o(1)}-稀疏相关均衡。
原文摘要 · Abstract (English)
A celebrated connection in the interface of online learning and game theory establishes that players minimizing swap regret converge to correlated equilibria (CE) -- a seminal game-theoretic solution concept. Despite the long history of this problem and the renewed interest it has received in recent years, a basic question remains open: how many iterations are needed to approximate an equilibrium under the usual normal-form representation? In this paper, we provide evidence that existing learning algorithms, such as multiplicative weights update, are close to optimal. In particular, we prove lower bounds for the problem of computing a CE that can be expressed as a uniform mixture of $T$ product distributions -- namely, a uniform $T$-sparse CE; such lower bounds immediately circumscribe (computationally bounded) regret minimization algorithms in games. Our results are obtained in the algorithmic framework put forward by Kothari and Mehta (STOC 2018) in the context of computing Nash equilibria, which consists of the sum-of-squares (SoS) relaxation in conjunction with oracle access to a verification oracle; the goal in that framework is to lower bound either the degree of the SoS relaxation or the number of queries to the verification oracle. Here, we obtain two such hardness results, precluding computing i) uniform $\text{log }n$-sparse CE when $ε=\text{poly}(1/\text{log }n)$ and ii) uniform $n^{1 - o(1)}$-sparse CE when $ε= \text{poly}(1/n)$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。