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

arXiv: https://arxiv.org/abs/2106.03579 · HTML: https://mlsanity.com/paper/2106.03579/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 38 references that are in the map.
- First posted on arXiv 7 Jun 2021.

## Builds on (most cited first, 16 of 16)

- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Training GANs with Optimism](https://mlsanity.com/paper/1711.00141/) (2017)
- [Online Learning: A Comprehensive Survey](https://mlsanity.com/paper/1802.02871/) (2018)
- [Optimization, Learning, and Games with Predictable Sequences](https://mlsanity.com/paper/1311.1869/) (2013)
- [Fast Convergence of Regularized Learning in Games](https://mlsanity.com/paper/1507.00407/) (2015)
- [A Variational Inequality Perspective on Generative Adversarial Networks](https://mlsanity.com/paper/1802.10551/) (2018)
- [A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach](https://mlsanity.com/paper/1901.08511/) (2019)
- [Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile](https://mlsanity.com/paper/1807.02629/) (2018)
- [Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization](https://mlsanity.com/paper/1807.04252/) (2018)
- [On the convergence of single-call stochastic extra-gradient methods](https://mlsanity.com/paper/1908.08465/) (2019)
- [Interaction Matters: A Note on Non-asymptotic Local Convergence of Generative Adversarial Networks](https://mlsanity.com/paper/1802.06132/) (2018)
- [Fast Policy Extragradient Methods for Competitive Games with Entropy Regularization](https://mlsanity.com/paper/2105.15186/) (2021)
- [Last iterate convergence in no-regret learning: constrained min-max optimization for convex-concave landscapes](https://mlsanity.com/paper/2002.06768/) (2020)
- [Accelerating Smooth Games by Manipulating Spectral Shapes](https://mlsanity.com/paper/2001.00602/) (2020)
- [Chaos, Extremism and Optimism: Volume Analysis of Learning in Games](https://mlsanity.com/paper/2005.13996/) (2020)
- [Fast and Furious Learning in Zero-Sum Games: Vanishing Regret with Non-Vanishing Step Sizes](https://mlsanity.com/paper/1905.04532/) (2019)

## Built on by (most cited first, 6 of 6)

- [Asynchronous Gradient Play in Zero-Sum Multi-agent Games](https://mlsanity.com/paper/2211.08980/) (2022)
- [Min-Max Optimization Made Simple: Approximating the Proximal Point Method via Contraction Maps](https://mlsanity.com/paper/2301.03931/) (2023)
- [No-regret learning in harmonic games: Extrapolation in the face of conflicting interests](https://mlsanity.com/paper/2412.20203/) (2024)
- [Last-iterate Convergence Separation between Extra-gradient and Optimism in Constrained Periodic Games](https://mlsanity.com/paper/2406.10605/) (2024)
- [Optimism Without Regularization: Constant Regret in Zero-Sum Games](https://mlsanity.com/paper/2506.16736/) (2025)
- [Understanding Dynamics of Adam in Zero-Sum Games: An ODE Approach](https://mlsanity.com/paper/2605.19392/) (2026)

## Abstract (arXiv)

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 Omega(η^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.