2019

On Finding Local Nash Equilibria (and Only Local Nash Equilibria) in Zero-Sum Games

Mazumdar, Eric V., Jordan, Michael I., Sastry, S. Shankar

Understand

We propose local symplectic surgery, a two-timescale procedure for finding local Nash equilibria in two-player zero-sum games.

We first show that previous gradient-based algorithms cannot guarantee convergence to local Nash equilibria due to the existence of non-Nash stationary points.
By taking advantage of the differential structure of the game, we construct an algorithm for which the local Nash equilibria are the only attracting fixed points.
We also show that the algorithm exhibits no oscillatory behaviors in neighborhoods of equilibria and show that it has the same per-iteration complexity as other recently proposed algorithms.

Dynamics of Morse-Smale urn processes
M. Benaïm and M. Hirsch · 1995
Earlier work this paper cites.
Learning processes, mixed equilibria and dynamical systems arising from repeated games
M. Benaim and M. Hirsch · 1997
Earlier work this paper cites.
Dynamic Noncooperative Game Theory
T. Basar and G. Olsder · 1998
Earlier work this paper cites.
Dynamics of stochastic approximation algorithms
M. Benaïm · 1999
Earlier work this paper cites.
Mixed equilibria and dynamical systems arising from fictitious play in perturbed games
M. Benaïm and M. Hirsch · 1999
Earlier work this paper cites.
Nonlinear Systems
S. S. Sastry · 1999
Earlier work this paper cites.
Adaptive policy gradient in multiagent learning
B. Banerjee and J. Peng · 2003
Earlier work this paper cites.
Prediction, Learning, and Games
N. Cesa-Bianchi and G. Lugosi · 2006
Earlier work this paper cites.
Algorithmic Game Theory
N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani · 2007
Earlier work this paper cites.

Stochastic Approximation: A Dynamical Systems Viewpoint
V. S. Borkar · 2008
Cited alongside, same era.
The complexity of computing a Nash equilibrium
C. Papadimitriou C. Daskalakis, P. Goldberg · 2009
Cited alongside, same era.
Robustness and regularization of support vector machines
H. Xu, C. Caramanis, and S. Mannor · 2009
Cited alongside, same era.
Active learning with a drifting distribution
L. Yang · 2011
Cited alongside, same era.
Multiple equilibria and limit cycles in evolutionary games with logit dynamics
C. H. Hommes and M. I. Ochea · 2012
Cited alongside, same era.
Characterization and computation of local Nash equilibria in continuous games
L. J. Ratliff, S. A. Burden, and S. S. Sastry · 2013
Cited alongside, same era.
Generative adversarial networks
Original
I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio · 2014
Cited alongside, same era.
Traning GANs with Optimism
Original
C. Daskalakis, A. Ilyas, V. Syrgkanis, and H. Zeng · 2017
Cited alongside, same era.
On the convergence of gradient-based learning in continuous games
E. Mazumdar and L. J. Ratliff
Cited in the paper.
Mirror descent in saddle-point problems: Going the extra (gradient) mile
Original
P. Mertikopoulos, H. Zenati, B. Lecouat, C. Foo, V. Chandrasekhar, and G. Piliouras
Cited in the paper.
Cycles in adversarial regularized learning
Panayotis Mertikopoulos, Christos H. Papadimitriou, and Georgios Piliouras
Cited in the paper.

Learning with opponent-learning awareness
Original
J. Foerster, R. Y. Chen, M. Al-Shedivat, S. Whiteson, P. Abbeel, and I. Mordatch · 2017
Later among the works it cites.
GANs trained by a two time-scale update rule converge to a local Nash equilibrium
M. Heusel, H. Ramsauer, T. Unterthiner, B. Nessler, and S. Hochreiter · 2017
Later among the works it cites.
The numerics of GANs
L. M. Mescheder, S. Nowozin, and A. Geiger · 2017
Later among the works it cites.
Gradient descent GAN optimization is locally stable
V. Nagarajan and Z. Kolter · 2017
Later among the works it cites.
The mechanics of n-player differentiable games
D. Balduzzi, S. Racaniere, J. Martens, J. Foerster, K. Tuyls, and T. Graepel · 2018
Later among the works it cites.
A variational inequality perspective on generative adversarial nets
Original
G. Gidel, H. Berard, P. Vincent, and S. Lacoste-Julien · 2018
Later among the works it cites.
Covariances, robustness, and variational Bayes
R. Giordano, T. Broderick, and M. I. Jordan · 2018
Later among the works it cites.
Artificial intelligence: The revolution hasn’t happened yet
M. I. Jordan · 2018
Later among the works it cites.

alphaXiv searches the wider corpus for related work and actual follow-ups.

alphaXiv is searching for related work…

Reading the bibliography…