Alternating Mirror Descent for Constrained Min-Max Games
In this paper we study two-player bilinear zero-sum games with constrained
strategy spaces. An instance of natural occurrences of such constraints is when
mixed strategies are used, which correspond to a probability simplex
constraint. We propose and analyze the alternating mirror descent algorithm, in
which each player takes turns to take action following the mirror descent
algorithm for constrained optimization. We interpret alternating mirror descent
as an alternating discretization of a skew-gradient flow in the dual space, and
use tools from convex optimization and modified energy function to establish an
$O(K^{-2/3})$ bound on its average regret after $K$ iterations. This
quantitatively verifies the algorithm's better behavior than the simultaneous
version of mirror descent algorithm, which is known to diverge and yields an
$O(K^{-1/2})$ average regret bound. In the special case of an unconstrained
setting, our results recover the behavior of alternating gradient descent
algorithm for zero-sum games which was studied in (Bailey et al., COLT 2020).