The cornerstone underpinning deep learning is the guarantee that gradient descent on an objective converges to local minima. Unfortunately, this guarantee fails in settings, such as generative adversarial nets, where there are multiple interacting losses. The behavior of gradient-based methods in games is not well understood – and is becoming increasingly important as adversarial and multiobjective architectures proliferate. In this paper, we develop new techniques to understand and control the dynamics in general games. The key result is to decompose the second-order dynamics into two components. The first is related to potential games, which reduce to gradient descent on an implicit function; the second 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 general games. Basic experiments show SGA is competitive with recently proposed algorithms for finding stable fixed points in GANs – whilst at the same time being applicable to – and having guarantees in – much more general games.


    Access

    Download


    Export, share and cite



    Title :

    The Mechanics of n-Player Differentiable Games


    Contributors:

    Publication date :

    2018-01-01


    Remarks:

    In: Dy, JG and Krause, A, (eds.) Proceedings of the 35th International Conference on Machine Learning. (pp. pp. 363-372). JMLR.org (2018)


    Type of media :

    Paper


    Type of material :

    Electronic Resource


    Language :

    English


    Classification :

    DDC:    629



    Differentiable Game Mechanics

    Letcher, A / Balduzzi, D / Racaniere, S et al. | BASE | 2019

    Free access

    Stable Opponent Shaping in Differentiable Games

    Letcher, A / Foerster, J / Balduzzi, D et al. | BASE | 2019

    Free access

    Optimal Player Policies for Continuous Ambush Games

    Boidot, Emmanuel / Marzuoli, Aude / Feron, Eric | AIAA | 2018


    Multi-player equilibria verification for concurrent stochastic games

    Kwiatkowska, M / Norman, G / Parker, D et al. | BASE | 2020

    Free access

    Neural Auto-Curricula in Two-Player Zero-Sum Games

    Feng, X / Slumbers, O / Wan, Z et al. | BASE | 2021

    Free access