无正则化下，乐观虚报博弈仍可实现恒定遗憾，突破传统认知。
Optimism Without Regularization: Constant Regret in Zero-Sum Games
- 采用无正则化的乐观虚报博弈，通过双空间几何分析证明其收敛性
- 在两策略博弈中，无论何种规则，遗憾值恒定，不随时间增长
- 适用于研究非后悔算法在博弈学习中的快速收敛机制
本文研究了两人零和博弈中虚报博弈的乐观变体。尽管已知带正则化的乐观FTRL（步长有界）可在该设定下实现恒定遗憾，但本文首次证明：无需正则化，同样可达到最优遗憾率。我们证明，在两策略博弈中，无论采用何种破局规则，乐观虚报博弈的遗憾始终为常数，揭示了非后悔算法在博弈学习中快速收敛的新可能。证明方法基于收益向量对偶空间中的几何视角，展示了迭代过程中的能量函数保持有界。此外，我们还证明交替虚报博弈的遗憾下界为Ω(√T)。在无正则化情形下，这区分了乐观性与交替性在实现o(√T)遗憾上的不同能力。
原文摘要 · Abstract (English)
This paper studies the optimistic variant of Fictitious Play for learning in two-player zero-sum games. While it is known that Optimistic FTRL -- a regularized algorithm with a bounded stepsize parameter -- obtains constant regret in this setting, we show for the first time that similar, optimal rates are also achievable without regularization: we prove for two-strategy games that Optimistic Fictitious Play (using any tiebreaking rule) obtains only constant regret, providing surprising new evidence on the ability of non-no-regret algorithms for fast learning in games. Our proof technique leverages a geometric view of Optimistic Fictitious Play in the dual space of payoff vectors, where we show a certain energy function of the iterates remains bounded over time. Additionally, we also prove a regret lower bound of $Ω(\sqrt{T})$ for Alternating Fictitious Play. In the unregularized regime, this separates the ability of optimism and alternation in achieving $o(\sqrt{T})$ regret.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。