Sample Efficient Stochastic Policy Extragradient Algorithm for Zero-Sum Markov Game
Sample Efficient Stochastic Policy Extragradient Algorithm for Zero-Sum Markov Game
复制标题
DOI：
--
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Ziyi Chen;Shaocong Ma;Yi Zhou
中科院分区：
文献类型：
--
作者：
Ziyi Chen;Shaocong Ma;Yi Zhou
两人零和马尔可夫博弈是强化学习和博弈论中的一个基本问题。虽然在现有文献中已经提出了许多算法来解决零和马尔可夫博弈，但其中许多算法要么需要对环境的充分了解，要么不是样本有效的。在本文中，我们开发了一个完全分散和样本有效的随机策略超梯度算法解决表格零和马尔可夫博弈。特别地，我们的算法利用多个随机估计器来准确地估计随机更新中涉及的值函数，并利用熵正则化来加速收敛。具体地说，在适当的熵正则化参数下，我们证明了随机策略超梯度算法的样本复杂度为（cid：101）O（A max µ min（cid：15）5。5（1 − γ）13。5）寻找一个达到（cid：15）-纳什均衡对偶差距的解决方案，其中A max是参与者之间的最大行动次数，µ min是状态平稳分布的下限，γ是折扣因子。这样的样本复杂度结果实质上改进了现有技术的复杂度结果。
Two-player zero-sum Markov game is a fundamental problem in reinforcement learning and game theory. Although many algorithms have been proposed for solving zero-sum Markov games in the existing literature, many of them either require a full knowledge of the environment or are not sample-efficient. In this paper, we develop a fully decentralized and sample-efficient stochastic policy extragradient algorithm for solving tabular zero-sum Markov games. In particular, our algorithm utilizes multiple stochastic estimators to accurately estimate the value functions involved in the stochastic updates, and leverages entropy regularization to accelerate the convergence. Specifically, with a proper entropy-regularization parameter, we prove that the stochastic policy extragradient algorithm has a sample complexity of the order (cid:101) O ( A max µ min (cid:15) 5 . 5 (1 − γ ) 13 . 5 ) for finding a solution that achieves (cid:15) -Nash equilibrium duality gap, where A max is the maximum number of actions between the players, µ min is the lower bound of state stationary distribution, and γ is the discount factor. Such a sample complexity result substantially improves the state-of-the-art complexity result.