论文标题
网络零和广泛表格游戏中乐观梯度上升的快速收敛
Fast Convergence of Optimistic Gradient Ascent in Network Zero-Sum Extensive Form Games
论文作者
论文摘要
迄今为止，游戏中的学习研究主要集中在正常形式游戏上。相比之下，尽管它们在许多现实世界的应用中更加接近，但我们以广泛的形式游戏（EFG），尤其是在许多代理商远远落后的EFG中对学习的理解。我们考虑了网络零和广泛表单游戏的自然类别，该游戏结合了代理收益的全球零和属性，图形游戏的有效表示以及EFG的表达能力。我们研究了这些游戏中乐观梯度上升（OGA）的收敛属性。我们证明，这种在线学习动力学的时间平均值表现出$ O（1/t）$费率收敛到NASH Equilibria集合。此外，我们表明，对于某些与游戏有关的常数$ c> 0 $，日常行为也与速率$ o（c^{ - t}）$收敛到nash。
The study of learning in games has thus far focused primarily on normal form games. In contrast, our understanding of learning in extensive form games (EFGs) and particularly in EFGs with many agents lags far behind, despite them being closer in nature to many real world applications. We consider the natural class of Network Zero-Sum Extensive Form Games, which combines the global zero-sum property of agent payoffs, the efficient representation of graphical games as well the expressive power of EFGs. We examine the convergence properties of Optimistic Gradient Ascent (OGA) in these games. We prove that the time-average behavior of such online learning dynamics exhibits $O(1/T)$ rate convergence to the set of Nash Equilibria. Moreover, we show that the day-to-day behavior also converges to Nash with rate $O(c^{-t})$ for some game-dependent constant $c>0$.
