Second-Order Mirror Descent: Convergence in Games Beyond Averaging and Discounting

• 成果类型: Article
• 署名作者: Gao, Bolin; Pavel, Lacra
• 署名单位: University of Toronto
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2023.3291953
• 发表日期: 2024
• 页码: 2143-2157
• 关键词: Autonomous system; game theory; gradient methods; Multi-agent systems; nonlinear dynamical systems; Reinforcement Learning

摘要

In this article, we propose a second-order extension of the continuous-time game-theoretic mirror descent (MD) dynamics, referred to as MD2, which provably converges to mere (but not necessarily strict) variationally stable states (VSS) without using common auxiliary techniques, such as time-averaging or discounting. We show that MD2 enjoys no-regret as well as an exponential rate of convergence toward strong VSS upon a slight modification. MD2 can also be used to derive many novel continuous-time primal-space dynamics. We then use stochastic approximation techniques to provide a convergence guarantee of discrete-time MD2 with noisy observations toward interior mere VSS. Selected simulations are provided to illustrate our results.