提出新算法，更快收敛到马尔可夫博弈中的均衡。
Near Optimal Convergence to Coarse Correlated Equilibrium in General-Sum Markov Games
- 用分阶段自适应步长优化学习策略，改进了传统方法。
- 收敛率从 O(log⁵T/T) 提升至 O(log T/T)，速度显著加快。
- 适合研究多智能体强化学习与博弈均衡的学者参考。
无悔学习动态在博弈论中至关重要，可实现去中心化收敛至粗相关均衡（CCE）或相关均衡（CE）。本文改进了通用和博弈中到 CCE 的收敛速率，将其从此前最优的 $\mathcal{O}(\log^5 T / T)$ 降低至更优的 $\mathcal{O}(\log T / T)$，达到与 CE 相同的 $T$ 阶收敛率。同时，将动作集大小的依赖从多项式降至多对数级，在高维场景下实现指数级提升。方法基于正常形式博弈中自适应步长技术的最新进展，通过分阶段机制将之拓展至马尔可夫设置，将策略更新建模为面向值迭代学习的乐观正则化追随领袖（OFTRL），所提出的自洽学习算法在马尔可夫博弈中实现了目前已知最快的 CCE 收敛速度。
原文摘要 · Abstract (English)
No-regret learning dynamics play a central role in game theory, enabling decentralized convergence to equilibrium for concepts such as Coarse Correlated Equilibrium (CCE) or Correlated Equilibrium (CE). In this work, we improve the convergence rate to CCE in general-sum Markov games, reducing it from the previously best-known rate of $\mathcal{O}(\log^5 T / T)$ to a sharper $\mathcal{O}(\log T / T)$. This matches the best known convergence rate for CE in terms of $T$, number of iterations, while also improving the dependence on the action set size from polynomial to polylogarithmic-yielding exponential gains in high-dimensional settings. Our approach builds on recent advances in adaptive step-size techniques for no-regret algorithms in normal-form games, and extends them to the Markovian setting via a stage-wise scheme that adjusts learning rates based on real-time feedback. We frame policy updates as an instance of Optimistic Follow-the-Regularized-Leader (OFTRL), customized for value-iteration-based learning. The resulting self-play algorithm achieves, to our knowledge, the fastest known convergence rate to CCE in Markov games.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。