arXiv:2602.11857cs.GTcs.LG2026-02被引 2

提出无需先验信息的快速收敛学习算法,适应不同收益尺度。

Scale-Invariant Fast Convergence in Games

  • 用自适应学习率和梯度路径长度设计新动态,实现无尺度依赖。
  • 零和博弈下收敛速度达 $\tilde{O}(A_{\mathrm{diff}} / T)$,多人博弈为 $O(U_{\mathrm{max}} \log T / T)$。
  • 适合收益尺度未知的博弈场景,尤其适用于多智能体强化学习。

尺度不变性在博弈学习中日益受到重视,但现有快速收敛结果大多依赖对效用尺度的先验知识。本文提出无需先验信息且尺度不变的学习动态:在双人零和博弈中,外部后悔界为 $\tilde{O}(A_{\mathrm{diff}})$,收敛至纳什均衡速率为 $\tilde{O}(A_{\mathrm{diff}} / T)$;在 $n$ 人、$m$ 动作的一般和博弈中,交换后悔界为 $O(U_{\mathrm{max}} \log T)$,收敛至相关均衡速率为 $O(U_{\mathrm{max}} \log T / T)$。核心方法为带自适应学习率的乐观跟随正则化领导者,结合对手梯度路径长度,并引入新型停止时间分析以利用后悔界中的负项,避免依赖尺度的调参。对于一般和博弈,通过双重截断技术(doubling clipping)实现无尺度学习,该技术基于历史观测截断梯度。

原文摘要 · Abstract (English)

Scale-invariance in games has recently emerged as a widely valued desirable property. Yet, almost all fast convergence guarantees in learning in games require prior knowledge of the utility scale. To address this, we develop learning dynamics that achieve fast convergence while being both scale-free, requiring no prior information about utilities, and scale-invariant, remaining unchanged under positive rescaling of utilities. For two-player zero-sum games, we obtain scale-free and scale-invariant dynamics with external regret bounded by $\tilde{O}(A_{\mathrm{diff}})$, where $A_{\mathrm{diff}}$ is the payoff range, which implies an $\tilde{O}(A_{\mathrm{diff}} / T)$ convergence rate to Nash equilibrium after $T$ rounds. For multiplayer general-sum games with $n$ players and $m$ actions, we obtain scale-free and scale-invariant dynamics with swap regret bounded by $O(U_{\mathrm{max}} \log T)$, where $U_{\mathrm{max}}$ is the range of the utilities, ignoring the dependence on the number of players and actions. This yields an $O(U_{\mathrm{max}} \log T / T)$ convergence rate to correlated equilibrium. Our learning dynamics are based on optimistic follow-the-regularized-leader with an adaptive learning rate that incorporates the squared path length of the opponents' gradient vectors, together with a new stopping-time analysis that exploits negative terms in regret bounds without scale-dependent tuning. For general-sum games, scale-free learning is enabled also by a technique called doubling clipping, which clips observed gradients based on past observations.

博弈学习快速收敛无尺度依赖多智能体

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。