Forward Looking Best-Response Multiplicative Weights Update Methods for Bilinear Zero-sum Games

Our work focuses on extra gradient learning algorithms for finding Nash\nequilibria in bilinear zero-sum games. The proposed method, which can be\nformally considered as a variant of Optimistic Mirror Descent\n\\cite{DBLP:conf/iclr/MertikopoulosLZ19}, uses a large learning rate for the\nintermediate gradient step which essentially leads to computing (approximate)\nbest response strategies against the profile of the previous iteration.\nAlthough counter-intuitive at first sight due to the irrationally large, for an\niterative algorithm, intermediate learning step, we prove that the method\nguarantees last-iterate convergence to an equilibrium. Particularly, we show\nthat the algorithm reaches first an $\\eta^{1/\\rho}$-approximate Nash\nequilibrium, with $\\rho > 1$, by decreasing the Kullback-Leibler divergence of\neach iterate by at least $\\Omega(\\eta^{1+\\frac{1}{\\rho}})$, for sufficiently\nsmall learning rate, $\\eta$, until the method becomes a contracting map, and\nconverges to the exact equilibrium. Furthermore, we perform experimental\ncomparisons with the optimistic variant of the multiplicative weights update\nmethod, by \\cite{Daskalakis2019LastIterateCZ} and show that our algorithm has\nsignificant practical potential since it offers substantial gains in terms of\naccelerated convergence.\n