两方零和马尔科夫博弈下的策略梯度算法

在两方零和马尔科夫博弈中，由于玩家策略会受到另一个玩家策略的影响，传统的策略梯度定理只适用于交替训练两个玩家的策略.为了实现同时训练两个玩家的策略，文中给出两方零和马尔科夫博弈下的策略梯度定理.然后，基于该策略梯度定理，提出基于额外梯度的REINFORCE算法，可使玩家的联合策略收敛到近似纳什均衡.文中从多个维度分析算法的优越性.首先，在同时移动博弈游戏上的对比实验表明，文中算法的收敛性和收敛速度较优.其次，分析文中算法得到的联合策略的特点，并验证这些联合策略达到近似纳什均衡.最后，在不同难度等级的同时移动博弈游戏上的对比实验表明，文中算法在更大的难度等级下仍能保持不错的收敛速度.

Policy Gradient Algorithm in Two-Player Zero-Sum Markov Games

In two-player zero-sum Markov games, the traditional policy gradient theorem is only applied to alternate training of two players due to the influence of one player's policy on the other player's policy. To train two players at the same time, the policy gradient theorem in two-player zero-sum Markov games is proposed. Then, based on the policy gradient theorem, an extra-gradient based REINFORCE algorithm is proposed to achieve approximate Nash convergence of the joint policy of two players. The superiority of the proposed algorithm is analyzed in multiple dimensions. Firstly, the comparative experiments on simultaneous-move game show that the convergence and convergence speed of the proposed algorithm are better. Secondly, the characteristics of the joint policy obtained by the proposed algorithm are analyzed and these joint policies are verified to achieve approximate Nash equilibrium. Finally, the comparative experiments on simultaneous-move game with different difficulty levels show that the proposed algorithm holds a good convergence speed at higher difficulty levels.