# Poincar'e Recurrence, Cycles and Spurious Equilibria in Gradient-Descent-Ascent for Non-Convex Non-Concave Zero-Sum Games

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Oct 2019.

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

- [Stackelberg Actor-Critic: Game-Theoretic Reinforcement Learning Algorithms](https://mlsanity.com/paper/2109.12286/) (2021)
- [Derivative-Free Policy Optimization for Linear Risk-Sensitive and Robust Control Design: Implicit Regularization and Sample Complexity](https://mlsanity.com/paper/2101.01041/) (2021)
- [Learning in Matrix Games can be Arbitrarily Complex](https://mlsanity.com/paper/2103.03405/) (2021)
- [Online Learning in Periodic Zero-Sum Games](https://mlsanity.com/paper/2111.03377/) (2021)
- [First-Order Algorithms for Min-Max Optimization in Geodesic Metric Spaces](https://mlsanity.com/paper/2206.02041/) (2022)
- [Solving Min-Max Optimization with Hidden Structure via Gradient Descent Ascent](https://mlsanity.com/paper/2101.05248/) (2021)
- [Symmetric (Optimistic) Natural Policy Gradient for Multi-agent Learning with Parameter Convergence](https://mlsanity.com/paper/2210.12812/) (2022)
- [Fast Convergence of Optimistic Gradient Ascent in Network Zero-Sum Extensive Form Games](https://mlsanity.com/paper/2207.08426/) (2022)
- [STay-ON-the-Ridge: Guaranteed Convergence to Local Minimax Equilibrium in Nonconvex-Nonconcave Games](https://mlsanity.com/paper/2210.09769/) (2022)
- [Online Optimization in Games via Control Theory: Connecting Regret, Passivity and Poincar'e Recurrence](https://mlsanity.com/paper/2106.04748/) (2021)
- [A Survey of Decision Making in Adversarial Games](https://mlsanity.com/paper/2207.07971/) (2022)
- [Exploiting hidden structures in non-convex games for convergence to Nash equilibrium](https://mlsanity.com/paper/2312.16609/) (2023)
- [Towards convergence to Nash equilibria in two-team zero-sum games](https://mlsanity.com/paper/2111.04178/) (2021)
- [Constants of Motion: The Antidote to Chaos in Optimization and Game Dynamics](https://mlsanity.com/paper/2109.03974/) (2021)
- [Online Learning on Hidden-Convex Losses via Algorithmic Equivalence: Optimal Regret, Geometric Barrier, and Bandit Feedback](https://mlsanity.com/paper/2605.26373/) (2026)

## Abstract (arXiv)

We study a wide class of non-convex non-concave min-max games that generalizes over standard bilinear zero-sum games. In this class, players control the inputs of a smooth function whose output is being applied to a bilinear zero-sum game. This class of games is motivated by the indirect nature of the competition in Generative Adversarial Networks, where players control the parameters of a neural network while the actual competition happens between the distributions that the generator and discriminator capture. We establish theoretically, that depending on the specific instance of the problem gradient-descent-ascent dynamics can exhibit a variety of behaviors antithetical to convergence to the game theoretically meaningful min-max solution. Specifically, different forms of recurrent behavior (including periodicity and Poincar'e recurrence) are possible as well as convergence to spurious (non-min-max) equilibria for a positive measure of initial conditions. At the technical level, our analysis combines tools from optimization theory, game theory and dynamical systems.