Differentiable Game Mechanics

By Alistair Letcher, David Balduzzi, Sébastien Racanière, James Martens, Jakob N. Foerster, Karl Tuyls, Thore Graepel. 2019

95 citations recorded by the source corpus.

Deep learning is built on the foundational guarantee that gradient descent on an objective function converges to local minima. Unfortunately, this guarantee fails in settings, such as generative adversarial nets, that exhibit multiple interacting losses. The behavior of gradient-based methods in games is not well understood -- and is becoming increasingly important as adversarial and multi-objective architectures proliferate. In this paper, we develop new tools to understand and control the dynamics in n-player differentiable games. The key result is to decompose the game Jacobian into two components. The first, symmetric component, is related to potential games, which reduce to gradient descent on an implicit function. The second, antisymmetric component, relates to Hamiltonian games, a new class of games that obey a conservation law akin to conservation laws in classical mechanical systems. The decomposition motivates Symplectic Gradient Adjustment (SGA), a new algorithm for finding stable fixed points in differentiable games. Basic experiments show SGA is competitive with recently proposed algorithms for finding stable fixed points in GANs -- while at the same time being applicable to, and having guarantees in, much more general cases.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Statistical and Nonlinear Physics, Optimization & Training, Game & Decision Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Statistical and Nonlinear Physics

In Optimization & Training

In Game & Decision Theory

Citations in the corpus

Stochastic Hamiltonian Gradient Methods for Smooth Games (2020, methodology): “We use standard notation used previously in Mescheder et al. (2017); Balduzzi et al. (2018); Abernethy et al. (2019); Letcher et al. (2019).”
LOGAN: Latent Optimisation for Generative Adversarial Networks (2019, methodology): “To understand how latent optimisation improves GAN training, we analyse LOGAN as a 2-player differentiable game following Balduzzi et al. (2018); Gemp & Mahadevan (2018); Letcher et al. (2019).”
Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods (2019, background): “Despite its popularity, this algorithm fails to converge even for simple bilinear zero-sum games [41, 39, 14, 2, 32].”
Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms (2019, background): “Even though some remedies have been advocated (Balduzzi et al., 2018; Letcher et al., 2019; Chasnov et al., 2019; Fiez et al., 2019) to stabilizing the convergence in general continuous games, these assumptions are not easily verified/satisfied in MARL, e.”
Competitive Gradient Descent (2019, methodology): “, 2017), or by attempting to disentangle convergent potential parts from rotational Hamiltonian parts of the vector field (Balduzzi et al., 2018; Letcher et al., 2019; Gemp and Mahadevan, 2018).”
Accelerating Smooth Games by Manipulating Spectral Shapes (2020, background): “, 2017) and can be attracted to unstable equilibria in non-monotone landscapes (Letcher et al., 2019).”