We propose an iterated version of Nesterov's first-order smoothing method for the two-person zero-sum game equilibrium problem $$\min_{x\in Q_1} \max_{y\in Q_2} \ip{x}{Ay} = \max_{y\in Q_2} \min_{x\in Q_1} \ip{x}{Ay}.$$ This formulation applies to matrix games as well as sequential games. Our new algorithmic scheme computes an $\epsilon$-equilibrium to this min-max problem in $\Oh(\kappa(A) \ln(1/\epsilon))$ first-order iterations, where $\kappa(A)$ is a certain condition measure of the matrix $A$. This improves upon the previous first-order methods which required $\Oh(1/\epsilon)$ iterations, and it matches the iteration complexity bound of interior-point methods in terms of the algorithm's dependence on $\epsilon$. Unlike the interior-point methods that are inapplicable to large games due to their memory requirements, our algorithm retains the small memory requirements of prior first-order methods. Our scheme supplements Nesterov's algorithm with an outer loop that lowers the target $\epsilon$ between iterations (this target affects the amount of smoothing in the inner loop). We find it surprising that such a simple modification yields an exponential speed improvement. Finally, computational experiments both in matrix games and sequential games show that a significant speed improvement is obtained in practice as well, and the relative speed improvement increases with the desired accuracy (as suggested by the complexity bounds).

## Citation

23rd National Conference on Artificial Intelligence (AAAI'08)