Fast Policy Extragradient Methods for Competitive Games with Entropy Regularization
Fast Policy Extragradient Methods for Competitive Games with Entropy Regularization
复制标题
DOI：
--
复制
发表时间：
2021-05
期刊：
影响因子：
--
通讯作者：
Shicong Cen;Yuting Wei;Yuejie Chi
中科院分区：
文献类型：
--
作者：
Shicong Cen;Yuting Wei;Yuejie Chi
本文研究了计算竞争游戏均衡的问题，竞争游戏的均衡通常被建模为具有概率单纯性约束的鞍点优化问题。尽管最近在不受约束的设置中理解外部方法的最后近期收敛性，但这些方法在受约束的设置中的理论基础，尤其是使用乘法更新的设置中的理论基础，即使目标函数是双线性的，即使是使用乘法更新的理论基础。由熵正则化在单器官增强学习和游戏理论中的算法作用的动机，我们开发了可证明有效的外部方法，以找到量子响应平衡（QRE） - 这是对零和两种玩家矩阵游戏的解决方案 - 以线性速率。所提出的算法可以以分散的方式实现，每个玩家都可以使用自己的回报执行对称和乘法更新，而无需直接观察对手的动作。此外，通过控制熵正则化的旋钮，所提出的算法可以以均匀的速率定位非注册矩阵游戏的近似NASH平衡，而不会假设NASH平衡是唯一的。我们的方法还导致有效的政策外算法以相似的速度解决（熵调查）零和马尔可夫游戏。我们所有的收敛速率几乎不含尺寸，它们与状态的大小和动作空间无关，直至对数因素，从而强调了熵正则化加速收敛的积极作用。
This paper investigates the problem of computing the equilibrium of competitive games, which is often modeled as a constrained saddle-point optimization problem with probability simplex constraints. Despite recent efforts in understanding the last-iterate convergence of extragradient methods in the unconstrained setting, the theoretical underpinnings of these methods in the constrained settings, especially those using multiplicative updates, remain highly inadequate, even when the objective function is bilinear. Motivated by the algorithmic role of entropy regularization in single-agent reinforcement learning and game theory, we develop provably efficient extragradient methods to find the quantal response equilibrium (QRE) -- which are solutions to zero-sum two-player matrix games with entropy regularization -- at a linear rate. The proposed algorithms can be implemented in a decentralized manner, where each player executes symmetric and multiplicative updates iteratively using its own payoff without observing the opponent's actions directly. In addition, by controlling the knob of entropy regularization, the proposed algorithms can locate an approximate Nash equilibrium of the unregularized matrix game at a sublinear rate without assuming the Nash equilibrium to be unique. Our methods also lead to efficient policy extragradient algorithms for solving (entropy-regularized) zero-sum Markov games at similar rates. All of our convergence rates are nearly dimension-free, which are independent of the size of the state and action spaces up to logarithm factors, highlighting the positive role of entropy regularization for accelerating convergence.