# Optimistic Gradient Descent Ascent in Zero-Sum and General-Sum Bilinear Games

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Aug 2022.

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

- [Local convergence of simultaneous min-max algorithms to differential equilibrium on Riemannian manifold](https://mlsanity.com/paper/2405.13392/) (2024)
- [Learnable Mixed Nash Equilibria are Collectively Rational](https://mlsanity.com/paper/2510.14907/) (2025)
- [Solving Parameter-Robust Avoid Problems with Unknown Feasibility using Reinforcement Learning](https://mlsanity.com/paper/2602.15817/) (2026)

## Abstract (arXiv)

We study the convergence of Optimistic Gradient Descent Ascent in unconstrained bilinear games. In a first part, we consider the zero-sum case and extend previous results by Daskalakis et al. in 2018, Liang and Stokes in 2019, and others: we prove, for any payoff matrix, the exponential convergence of OGDA to a saddle point and also provide a new, optimal, geometric ratio for the convergence. We also characterize the step sizes inducing convergence, and are able to deduce the optimal step size for the speed of convergence. In a second part, we introduce OGDA for general-sum bilinear games: we show that in an interesting class of games, either OGDA converges exponentially fast to a Nash equilibrium, or the payoffs for both players converge exponentially fast to +∞ (which might be interpreted as endogenous emergence of coordination, or cooperation, among players). We also give sufficient conditions for convergence of OGDA to a Nash equilibrium. These conditions are used to increase the speed of convergence of a min-max problem involving a matrix A, by introducing a general-sum game using the Moore-Penrose inverse matrix of A. This shows for the first time, at our knowledge, that general-sum games can be used to optimally improve algorithms designed for min-max problems. We finally illustrate our results on simple examples of Generative Adversarial Networks.