提出最优收敛率算法，解决零和博弈中无通信下的最后迭代收敛问题。
The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback
- 设计两类无耦合算法，平衡探索与利用，实现最优收敛率。
- 证明最后迭代收敛率下界为Ω(T^{-1/4})，劣于平均迭代的Ω(T^{-1/2})。
- 适用于无通信、仅带通反馈的多智能体零和博弈学习场景。
我们研究在重复博弈和带通反馈下零和矩阵博弈中的学习问题。重点关注无需玩家间通信的无耦合算法，确保策略分布的最后迭代收敛至纳什均衡。尽管非带通情形已有广泛研究，但该设定最近才被探索，此前最佳可实现的可利用差距界为𝒪(T^{-1/8})。我们证明：对于无耦合算法，保证策略分布收敛至纳什均衡会损害性能，其最优可达收敛率为Ω(T^{-1/4})，远低于平均迭代常见的Ω(T^{-1/2})。随后提出两种算法，分别基于探索-利用权衡和两步镜面下降正则化，均达到该最优率（常数与对数因子内）。
原文摘要 · Abstract (English)
We study the problem of learning in zero-sum matrix games with repeated play and bandit feedback. Specifically, we focus on developing uncoupled algorithms that guarantee, without communication between players, the convergence of the last-iterate to a Nash equilibrium. Although the non-bandit case has been studied extensively, this setting has only been explored recently, with a bound of $\mathcal{O}(T^{-1/8})$ on the exploitability gap. We show that, for uncoupled algorithms, guaranteeing convergence of the policy profiles to a Nash equilibrium is detrimental to the performance, with the best attainable rate being $Ω(T^{-1/4})$ in contrast to the usual $Ω(T^{-1/2})$ rate for convergence of the average iterates. We then propose two algorithms that achieve this optimal rate up to constant and logarithmic factors. The first algorithm leverages a straightforward trade-off between exploration and exploitation, while the second employs a regularization technique based on a two-step mirror descent approach.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。