CaltechAUTHORS
  A Caltech Library Service

Polymatrix Competitive Gradient Descent

Ma, Jeffrey and Letcher, Alistair and Schäfer, Florian and Shi, Yuanyuan and Anandkumar, Anima (2021) Polymatrix Competitive Gradient Descent. . (Unpublished) https://resolver.caltech.edu/CaltechAUTHORS:20220714-224639640

[img] PDF - Submitted Version
See Usage Policy.

1MB

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20220714-224639640

Abstract

Many economic games and machine learning approaches can be cast as competitive optimization problems where multiple agents are minimizing their respective objective function, which depends on all agents' actions. While gradient descent is a reliable basic workhorse for single-agent optimization, it often leads to oscillation in competitive optimization. In this work we propose polymatrix competitive gradient descent (PCGD) as a method for solving general sum competitive optimization involving arbitrary numbers of agents. The updates of our method are obtained as the Nash equilibria of a local polymatrix approximation with a quadratic regularization, and can be computed efficiently by solving a linear system of equations. We prove local convergence of PCGD to stable fixed points for n-player general-sum games, and show that it does not require adapting the step size to the strength of the player-interactions. We use PCGD to optimize policies in multi-agent reinforcement learning and demonstrate its advantages in Snake, Markov soccer and an electricity market game. Agents trained by PCGD outperform agents trained with simultaneous gradient descent, symplectic gradient adjustment, and extragradient in Snake and Markov soccer games and on the electricity market game, PCGD trains faster than both simultaneous gradient descent and the extragradient method.


Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription
https://doi.org/10.48550/arXiv.2111.08565arXivDiscussion Paper
ORCID:
AuthorORCID
Shi, Yuanyuan0000-0002-6182-7664
Anandkumar, Anima0000-0002-6974-6797
Additional Information:AA is supported in part by the Bren endowed chair, Microsoft, Google, and Adobe faculty fellowships. FS gratefully acknowledge support by the Air Force Office of Scientific Research under award number FA9550-18-1-0271 (Games for Computation and Learning) and the Ronald and Maxine Linde Institute of Economic and Management Sciences at Caltech.
Funders:
Funding AgencyGrant Number
Bren Professor of Computing and Mathematical SciencesUNSPECIFIED
Microsoft Faculty FellowshipUNSPECIFIED
Google Faculty Research AwardUNSPECIFIED
AdobeUNSPECIFIED
Air Force Office of Scientific Research (AFOSR)FA9550-18-1-0271
Linde Institute of Economic and Management ScienceUNSPECIFIED
Record Number:CaltechAUTHORS:20220714-224639640
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20220714-224639640
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:115603
Collection:CaltechAUTHORS
Deposited By: George Porter
Deposited On:15 Jul 2022 23:15
Last Modified:15 Jul 2022 23:15

Repository Staff Only: item control page