First-order algorithm with ${mathcal{O}({rm ln}(1{/}epsilon))}$ convergence for ${epsilon}$ -equilibrium in two-person zero-sum games

摘要

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} {x}^{rm T}{Ay} = max_{y in Q_2} min_{x in Q_1} {x}^{rm T}{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 ${mathcal {O}left(frac{|A|}{delta(A)} , {rm ln}(1{/}epsilon)right)}$ first-order iterations, where δ(A) is a certain condition measure of the matrix A. This improves upon the previous first-order methods which required ${mathcal {O}(1{/}epsilon)}$ iterations, and it matches the iteration complexity bound of interior-point methods in terms of the algorithm’s dependence on ${epsilon}$ . Unlike 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 method with an outer loop that lowers the target ${epsilon}$ between iterations (this target affects the amount of smoothing in the inner loop). 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).