Asynchronous Gradient Play in Zero-Sum Multi-agent Games
Asynchronous Gradient Play in Zero-Sum Multi-agent Games
复制标题
DOI：
10.48550/arxiv.2211.08980
复制
发表时间：
2022-11
期刊：
影响因子：
--
通讯作者：
Ruicheng Ao;Shicong Cen;Yuejie Chi
中科院分区：
文献类型：
--
作者：
Ruicheng Ao;Shicong Cen;Yuejie Chi
近年来，在竞争性多智能体博弈中通过梯度博弈寻找均衡吸引了越来越多的关注，重点是设计有效的策略，其中智能体以分散和对称的方式运行，并保证收敛。虽然在理解零和两人矩阵游戏方面已经做出了重大努力，但零和多智能体游戏的性能仍然没有得到充分的探索，特别是在存在延迟反馈的情况下，这使得梯度游戏的可扩展性和弹性受到质疑。在本文中，我们取得了进展，通过研究异步梯度播放零和多矩阵对策下的延迟反馈。我们首先建立了熵正则化的乐观乘性权重更新（OMWU）方法的最后一步线性收敛到量子响应平衡（QRE），有限理性下的解决方案的概念，在没有延迟。虽然在温和的统计假设下，即使反馈被随机延迟，线性收敛仍然保持不变，但由于学习率的可容忍范围较小，它的收敛速度明显较慢。除此之外，我们还证明了熵正则化OMWU -通过以延迟感知的方式采用两个时间尺度的学习率-在固定延迟下具有更快的最后收敛速度，并且即使延迟以平均延迟的方式任意有界，也能继续证明收敛。我们的方法还导致有限时间的保证，以近似纳什均衡（NE）的调节量的正规化。据我们所知，这项工作是第一个旨在了解异步梯度发挥在零和多矩阵游戏在广泛的延迟假设下，突出学习率分离的作用。
Finding equilibria via gradient play in competitive multi-agent games has been attracting a growing amount of attention in recent years, with emphasis on designing efficient strategies where the agents operate in a decentralized and symmetric manner with guaranteed convergence. While significant efforts have been made in understanding zero-sum two-player matrix games, the performance in zero-sum multi-agent games remains inadequately explored, especially in the presence of delayed feedbacks, leaving the scalability and resiliency of gradient play open to questions. In this paper, we make progress by studying asynchronous gradient plays in zero-sum polymatrix games under delayed feedbacks. We first establish that the last iterate of entropy-regularized optimistic multiplicative weight updates (OMWU) method converges linearly to the quantal response equilibrium (QRE), the solution concept under bounded rationality, in the absence of delays. While the linear convergence continues to hold even when the feedbacks are randomly delayed under mild statistical assumptions, it converges at a noticeably slower rate due to a smaller tolerable range of learning rates. Moving beyond, we demonstrate entropy-regularized OMWU -- by adopting two-timescale learning rates in a delay-aware manner -- enjoys faster last-iterate convergence under fixed delays, and continues to converge provably even when the delays are arbitrarily bounded in an average-iterate manner. Our methods also lead to finite-time guarantees to approximate the Nash equilibrium (NE) by moderating the amount of regularization. To the best of our knowledge, this work is the first that aims to understand asynchronous gradient play in zero-sum polymatrix games under a wide range of delay assumptions, highlighting the role of learning rates separation.