Fast Policy Extragradient Methods for Competitive Games with Entropy
  Regularization
  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.
