用物理动力学方法在有限步内找到零和博弈的纳什均衡，且可并行化。
Characterizing Nash Equilibria in Zero-Sum Games: A Physics-Inspired, Parallelizable Approach with a Linear Number of Gradient Queries
- 基于哈密顿动力学设计新算法，通过交替梯度下降求解
- 在无界条件下仅需线性次数梯度查询即可定位所有纳什均衡
- 支持任意学习率且可并行，适用于大规模对抗学习场景
我们研究零和博弈中的在线优化方法，这是机器学习、经济学等领域中对抗学习的核心问题。传统方法要么基于遗憾的时均收敛，要么基于压缩映射的最后迭代收敛。本文提出一种受物理学哈密顿动力学启发的新方法，证明其可在无界设定下，以有限（线性）次交替梯度下降迭代刻画所有纳什均衡集合，此为在线优化领域的首次突破。与标准纳什均衡计算方法不同，该方法可并行化，且对任意学习率兼容，是算法博弈论中的首次实现。实验表明，该方法显著优于标准方法。
原文摘要 · Abstract (English)
We study online optimization methods for zero-sum games, a fundamental problem in adversarial learning in machine learning, economics, and many other domains. Traditional methods approximate Nash equilibria (NE) using either regret-based methods (time-average convergence) or contraction-map-based methods (last-iterate convergence). We propose a new method based on Hamiltonian dynamics in physics and prove that it can characterize the set of NE in a finite (linear) number of iterations of alternating gradient descent in the unbounded setting, modulo degeneracy, a first in online optimization. Unlike standard methods for computing NE, our proposed approach can be parallelized and works with arbitrary learning rates, both firsts in algorithmic game theory. Experimentally, we support our results by showing our approach drastically outperforms standard methods.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。