论文标题
千里眼的遗憾最小化：与Nemirovski的概念代理方法和扩展到一般凸游戏的等效性
Clairvoyant Regret Minimization: Equivalence with Nemirovski's Conceptual Prox Method and Extension to General Convex Games
论文作者
论文摘要
Piliouras等人最近的一篇论文。 [2021，2022]引入了一种未耦合形式游戏的学习算法 - 称为Crairvoyant MWU（CMWU）。在本说明中，我们表明CMWU等同于Nemirovski [2004]所描述的概念代理方法。该连接立即表明，可以将CMWU算法扩展到任何凸面游戏，这是Piliouras等人打开的问题。我们称之为生成的算法 - 再次等同于概念代理方法 - 千里眼的OMD。同时，我们表明我们的分析与Piliouras等人的原始界面相比产生了改善的遗憾，因为CMWU的遗憾仅以玩家数量的平方根而不是球员本身的数量来缩放。
A recent paper by Piliouras et al. [2021, 2022] introduces an uncoupled learning algorithm for normal-form games -- called Clairvoyant MWU (CMWU). In this note we show that CMWU is equivalent to the conceptual prox method described by Nemirovski [2004]. This connection immediately shows that it is possible to extend the CMWU algorithm to any convex game, a question left open by Piliouras et al. We call the resulting algorithm -- again equivalent to the conceptual prox method -- Clairvoyant OMD. At the same time, we show that our analysis yields an improved regret bound compared to the original bound by Piliouras et al., in that the regret of CMWU scales only with the square root of the number of players, rather than the number of players themselves.
