Independent Natural Policy Gradient Methods for Potential Games: Finite-time Global Convergence with Entropy Regularization
Independent Natural Policy Gradient Methods for Potential Games: Finite-time Global Convergence with Entropy Regularization
复制标题
DOI：
10.1109/cdc51059.2022.9993175
复制
发表时间：
2022-04
期刊：
影响因子：
--
通讯作者：
Shicong Cen;Fan Chen;Yuejie Chi
中科院分区：
文献类型：
--
作者：
Shicong Cen;Fan Chen;Yuejie Chi
多智能体系统中的一个主要挑战是，系统复杂性随着智能体的数量以及它们的动作空间大小急剧增加，这在现实世界的场景中很常见，比如自动驾驶车辆、机器人团队、网络路由等。因此，迫切需要设计分散式或独立的算法，其中每个智能体的更新仅基于其局部观测，而无需引入复杂的通信/协调机制。在这项工作中，我们研究了用于势博弈的独立熵正则化自然策略梯度（NPG）方法的有限时间收敛性，在势博弈中，由于单边偏离导致的智能体效用函数的差异与一个公共势函数的差异完全匹配。所提出的熵正则化NPG方法使每个智能体能够根据自身收益进行对称、分散和乘法更新。我们表明，所提出的方法以次线性速率收敛到量子响应均衡（QRE）——熵正则化博弈的均衡，该速率与动作空间大小无关，并且随着智能体数量至多呈次线性增长。令人感兴趣的是，对于利益相同博弈这一重要特殊情况，收敛速率进一步与智能体数量无关，从而产生了第一种以无维度速率收敛的方法。我们的方法可以用作一种平滑技术，在不假设平稳策略是孤立的情况下找到未正则化问题的近似纳什均衡（NE）。
A major challenge in multi-agent systems is that the system complexity grows dramatically with the number of agents as well as the size of their action spaces, which is typical in real world scenarios such as autonomous vehicles, robotic teams, network routing, etc. It is hence in imminent need to design decentralized or independent algorithms where the update of each agent is only based on their local observations without the need of introducing complex communication/coordination mechanisms. In this work, we study the finite-time convergence of independent entropy-regularized natural policy gradient (NPG) methods for potential games, where the difference in an agent’s utility function due to unilateral deviation matches exactly that of a common potential function. The proposed entropy-regularized NPG method enables each agent to deploy symmetric, decentralized, and multiplicative updates according to its own payoff. We show that the proposed method converges to the quantal response equilibrium (QRE)— the equilibrium to the entropy-regularized game—at a sublinear rate, which is independent of the size of the action space and grows at most sublinearly with the number of agents. Appealingly, the convergence rate further becomes independent with the number of agents for the important special case of identical-interest games, leading to the first method that converges at a dimension-free rate. Our approach can be used as a smoothing technique to find an approximate Nash equilibrium (NE) of the unregularized problem without assuming that stationary policies are isolated.