# Recursive Reasoning in Minimax Games: A Level k Gradient Play Method

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 41 of its 64 references that are in the map.
- First posted on arXiv 29 Oct 2022.

## Builds on (most cited first, 30 of 41)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [A Style-Based Generator Architecture for Generative Adversarial Networks](https://mlsanity.com/paper/1812.04948/) (2018)
- [Analyzing and Improving the Image Quality of StyleGAN](https://mlsanity.com/paper/1912.04958/) (2019)
- [Towards Evaluating the Robustness of Neural Networks](https://mlsanity.com/paper/1608.04644/) (2016)
- [Progressive Growing of GANs for Improved Quality, Stability, and Variation](https://mlsanity.com/paper/1710.10196/) (2017)
- [Improved Techniques for Training GANs](https://mlsanity.com/paper/1606.03498/) (2016)
- [Large Scale GAN Training for High Fidelity Natural Image Synthesis](https://mlsanity.com/paper/1809.11096/) (2018)
- [Improved Training of Wasserstein GANs](https://mlsanity.com/paper/1704.00028/) (2017)
- [Photo-Realistic Single Image Super-Resolution Using a Generative Adversarial Network](https://mlsanity.com/paper/1609.04802/) (2016)
- [Spectral Normalization for Generative Adversarial Networks](https://mlsanity.com/paper/1802.05957/) (2018)
- [Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments](https://mlsanity.com/paper/1706.02275/) (2017)
- [StarGAN: Unified Generative Adversarial Networks for Multi-Domain Image-to-Image Translation](https://mlsanity.com/paper/1711.09020/) (2017)
- [Which Training Methods for GANs do actually Converge?](https://mlsanity.com/paper/1801.04406/) (2018)
- [StyleGAN-XL: Scaling StyleGAN to Large Diverse Datasets](https://mlsanity.com/paper/2202.00273/) (2022)
- [Differentiable Augmentation for Data-Efficient GAN Training](https://mlsanity.com/paper/2006.10738/) (2020)
- [Geometric GAN](https://mlsanity.com/paper/1705.02894/) (2017)
- [Learning with Opponent-Learning Awareness](https://mlsanity.com/paper/1709.04326/) (2017)
- [Training GANs with Optimism](https://mlsanity.com/paper/1711.00141/) (2017)
- [Unrolled Generative Adversarial Networks](https://mlsanity.com/paper/1611.02163/) (2016)
- [Projected GANs Converge Faster](https://mlsanity.com/paper/2111.01007/) (2021)
- [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)
- [Cycles in adversarial regularized learning](https://mlsanity.com/paper/1709.02738/) (2017)
- [The Mechanics of n-Player Differentiable Games](https://mlsanity.com/paper/1802.05642/) (2018)
- [The Numerics of GANs](https://mlsanity.com/paper/1705.10461/) (2017)
- [Interaction Matters: A Note on Non-asymptotic Local Convergence of Generative Adversarial Networks](https://mlsanity.com/paper/1802.06132/) (2018)
- [Reducing Noise in GAN Training with Variance Reduced Extragradient](https://mlsanity.com/paper/1904.08598/) (2019)
- [Negative Momentum for Improved Game Dynamics](https://mlsanity.com/paper/1807.04740/) (2018)

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

- [K-Level Policy Gradients for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2509.12117/) (2025)
- [Almost Sure Convergence of Networked Policy Gradient over Time-Varying Networks in Markov Potential Games](https://mlsanity.com/paper/2410.20075/) (2024)

## Abstract (arXiv)

Despite the success of generative adversarial networks (GANs) in generating visually appealing images, they are notoriously challenging to train. In order to stabilize the learning dynamics in minimax games, we propose a novel recursive reasoning algorithm: Level k Gradient Play (Lv.k GP) algorithm. In contrast to many existing algorithms, our algorithm does not require sophisticated heuristics or curvature information. We show that as k increases, Lv.k GP converges asymptotically towards an accurate estimation of players' future strategy. Moreover, we justify that Lv.∞ GP naturally generalizes a line of provably convergent game dynamics which rely on predictive updates. Furthermore, we provide its local convergence property in nonconvex-nonconcave zero-sum games and global convergence in bilinear and quadratic games. By combining Lv.k GP with Adam optimizer, our algorithm shows a clear advantage in terms of performance and computational overhead compared to other methods. Using a single Nvidia RTX3090 GPU and 30 times fewer parameters than BigGAN on CIFAR-10, we achieve an FID of 10.17 for unconditional image generation within 30 hours, allowing GAN training on common computational resources to reach state-of-the-art performance.