Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergence
Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergence
复制标题
DOI：
--
复制
发表时间：
2022-02
期刊：
影响因子：
--
通讯作者：
Dongsheng Ding;Chen-Yu Wei;K. Zhang;M. Jovanovi'c
中科院分区：
文献类型：
--
作者：
Dongsheng Ding;Chen-Yu Wei;K. Zhang;M. Jovanovi'c
研究了马尔可夫势博弈(MPG)中多智能体强化学习(RL)问题的策略梯度方法的全局非渐近收敛性质。为了学习MPG的纳什均衡，其中状态空间的大小和/或参与者的数量可能非常大，我们提出了新的独立的策略梯度算法，该算法由所有参与者协同运行。在梯度估计不存在不确定性的情况下，我们证明了我们的算法找到了一个迭代复杂度为O(1/)且不依赖于状态空间大小的-Nash均衡。当精确梯度不存在时，我们在一个潜在无限大的状态空间中为一个基于样本的算法建立了O(1/)个样本复杂度的界。此外，我们还给出了一类独立的策略梯度算法，这类算法对于零和马尔可夫对策和马尔可夫合作对策都是收敛的，且参与者不知道所玩的博弈类型。最后，我们提供了计算实验，以证实我们的理论发展的优点和有效性。
We examine global non-asymptotic convergence properties of policy gradient methods for multiagent reinforcement learning (RL) problems in Markov potential games (MPGs). To learn a Nash equilibrium of an MPG in which the size of state space and/or the number of players can be very large, we propose new independent policy gradient algorithms that are run by all players in tandem. When there is no uncertainty in the gradient evaluation, we show that our algorithm finds an -Nash equilibrium with O(1/ ) iteration complexity which does not explicitly depend on the state space size. When the exact gradient is not available, we establish O(1/ ) sample complexity bound in a potentially infinitely large state space for a sample-based algorithm that utilizes function approximation. Moreover, we identify a class of independent policy gradient algorithms that enjoy convergence for both zero-sum Markov games and Markov cooperative games with the players that are oblivious to the types of games being played. Finally, we provide computational experiments to corroborate the merits and the effectiveness of our theoretical developments.