为多人博弈设计加速学习算法，收敛速度比传统方法快得多。
Accelerated regularized learning in finite N-person games
- 在正则化学习框架中引入动量机制，实现加速学习。
- 在严格纳什均衡处实现超线性收敛，比传统方法快得多。
- 适用于多种信息反馈场景，包括仅知自身收益的盲打情况。
受Nesterov加速梯度算法在凸优化中成功启发，本文探究在线博弈学习中能否实现类似性能提升。为此，提出一类名为“跟随加速领导者”（FTXL）的加速学习方法，将动量机制融入正则化学习框架，特别是指数/乘法权重算法及其变体。借鉴Nesterov算法的连续时间分析思想，证明FTXL在局部收敛至严格纳什均衡时达到超线性速率，相比传统正则化方法（几何收敛，线性速率）实现了指数级加速。重要的是，FTXL在广泛反馈结构下保持超线性收敛：从确定性全信息模型到随机、基于实现的反馈，甚至在仅能观测自身实际收益的博弈者（带奖赏基信息）情况下依然有效。
原文摘要 · Abstract (English)
Motivated by the success of Nesterov's accelerated gradient algorithm for convex minimization problems, we examine whether it is possible to achieve similar performance gains in the context of online learning in games. To that end, we introduce a family of accelerated learning methods, which we call "follow the accelerated leader" (FTXL), and which incorporates the use of momentum within the general framework of regularized learning - and, in particular, the exponential/multiplicative weights algorithm and its variants. Drawing inspiration and techniques from the continuous-time analysis of Nesterov's algorithm, we show that FTXL converges locally to strict Nash equilibria at a superlinear rate, achieving in this way an exponential speed-up over vanilla regularized learning methods (which, by comparison, converge to strict equilibria at a geometric, linear rate). Importantly, FTXL maintains its superlinear convergence rate in a broad range of feedback structures, from deterministic, full information models to stochastic, realization-based ones, and even when run with bandit, payoff-based information, where players are only able to observe their individual realized payoffs.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。