2021/06/07 by Michail Fasoulakis, Evangelos Markakis, Fasoulakis, Michail +5 · 1 citation
Computer Science · Decision Sciences · Physics and Astronomy · #Advanced Bandit Algorithms Research #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning and Algorithms #Quantum many-body systems #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2106.03579
openalex publication_date 2021/06/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Our work focuses on extra gradient learning algorithms for finding Nash equilibria in bilinear zero-sum games. The proposed method, which can be formally considered as a variant of Optimistic Mirror Descent \citeDBLP:conf/iclr/MertikopoulosLZ19, uses a large learning rate for the intermediate gradient step which essentially leads to computing (approximate) best response strategies against the profile of the previous iteration. Although counter-intuitive at first sight due to the irrationally large, for an iterative algorithm, intermediate learning step, we prove that the method guarantees last-iterate convergence to an equilibrium. Particularly, we show that the algorithm reaches first an η1/ρ-approximate Nash equilibrium, with ρ> 1, by decreasing the Kullback-Leibler divergence of each iterate by at least Ω(η^1+\frac1ρ), for sufficiently small learning rate, η, until the method becomes a contracting map, and converges to the exact equilibrium. Furthermore, we perform experimental comparisons with the optimistic variant of the multiplicative weights update method, by \citeDaskalakis2019LastIterateCZ and show that our algorithm has significant practical potential since it offers substantial gains in terms of accelerated convergence.