Provably Efficient Policy Optimization for Two-Player Zero-Sum Markov Games
Provably Efficient Policy Optimization for Two-Player Zero-Sum Markov Games
复制标题
DOI：
--
复制
发表时间：
2021-02
期刊：
影响因子：
--
通讯作者：
Yulai Zhao;Yuandong Tian;Jason D. Lee;S. Du
中科院分区：
文献类型：
--
作者：
Yulai Zhao;Yuandong Tian;Jason D. Lee;S. Du
基于策略的函数逼近方法被广泛用于求解具有较大状态和/或动作空间的两人零和博弈。然而，它仍然难以捉摸如何获得优化和统计保证这样的算法。我们提出了一个新的政策优化算法与函数逼近，并证明了在标准的正则性条件下的马尔可夫博弈和函数逼近类，我们的算法发现一个接近最优的政策内的多项式数量的样本和迭代。据我们所知，这是第一个证明有效的政策优化算法与函数近似，解决两个球员零和马尔可夫游戏。
Policy-based methods with function approximation are widely used for solving two-player zero-sum games with large state and/or action spaces. However, it remains elusive how to obtain optimization and statistical guarantees for such algorithms. We present a new policy optimization algorithm with function approximation and prove that under standard regularity conditions on the Markov game and the function approximation class, our algorithm finds a near-optimal policy within a polynomial number of samples and iterations. To our knowledge, this is the first provably efficient policy optimization algorithm with function approximation that solves two-player zero-sum Markov games.