Abstract
We formulate a general framework for competitive gradient-based learning thatencompasses a wide breadth of multi-agent learning algorithms, and analyze thelimiting behavior of competitive gradient-based learning algorithms usingdynamical systems theory. For both general-sum and potential games, wecharacterize a non-negligible subset of the local Nash equilibria that will beavoided if each agent employs a gradient-based learning algorithm. We also shedlight on the issue of convergence to non-Nash strategies in general- andzero-sum games, which may have no relevance to the underlying game, and arisesolely due to the choice of algorithm. The existence and frequency of suchstrategies may explain some of the difficulties encountered when using gradientdescent in zero-sum games as, e.g., in the training of generative adversarialnetworks. To reinforce the theoretical contributions, we provide empiricalresults that highlight the frequency of linear quadratic dynamic games (abenchmark for multi-agent reinforcement learning) that admit global Nashequilibria that are almost surely avoided by policy gradient.