For Learning in Symmetric Teams, Local Optima are Global Nash Equilibria

Scott Emmons, Caspar Oesterheld, Andrew Critch, Vincent Conitzer, Stuart Russell
Proceedings of the 39th International Conference on Machine Learning, PMLR 162:5924-5943, 2022.

Abstract

Although it has been known since the 1970s that a globally optimal strategy profile in a common-payoff game is a Nash equilibrium, global optimality is a strict requirement that limits the result’s applicability. In this work, we show that any locally optimal symmetric strategy profile is also a (global) Nash equilibrium. Furthermore, we show that this result is robust to perturbations to the common payoff and to the local optimum. Applied to machine learning, our result provides a global guarantee for any gradient method that finds a local optimum in symmetric strategy space. While this result indicates stability to unilateral deviation, we nevertheless identify broad classes of games where mixed local optima are unstable under joint, asymmetric deviations. We analyze the prevalence of instability by running learning algorithms in a suite of symmetric games, and we conclude by discussing the applicability of our results to multi-agent RL, cooperative inverse RL, and decentralized POMDPs.

Cite this Paper

BibTeX
@InProceedings{pmlr-v162-emmons22a, title = {For Learning in Symmetric Teams, Local Optima are Global {N}ash Equilibria}, author = {Emmons, Scott and Oesterheld, Caspar and Critch, Andrew and Conitzer, Vincent and Russell, Stuart}, booktitle = {Proceedings of the 39th International Conference on Machine Learning}, pages = {5924--5943}, year = {2022}, editor = {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan}, volume = {162}, series = {Proceedings of Machine Learning Research}, month = {17--23 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v162/emmons22a/emmons22a.pdf}, url = {https://proceedings.mlr.press/v162/emmons22a.html}, abstract = {Although it has been known since the 1970s that a globally optimal strategy profile in a common-payoff game is a Nash equilibrium, global optimality is a strict requirement that limits the result’s applicability. In this work, we show that any locally optimal symmetric strategy profile is also a (global) Nash equilibrium. Furthermore, we show that this result is robust to perturbations to the common payoff and to the local optimum. Applied to machine learning, our result provides a global guarantee for any gradient method that finds a local optimum in symmetric strategy space. While this result indicates stability to unilateral deviation, we nevertheless identify broad classes of games where mixed local optima are unstable under joint, asymmetric deviations. We analyze the prevalence of instability by running learning algorithms in a suite of symmetric games, and we conclude by discussing the applicability of our results to multi-agent RL, cooperative inverse RL, and decentralized POMDPs.} }
Endnote
%0 Conference Paper %T For Learning in Symmetric Teams, Local Optima are Global Nash Equilibria %A Scott Emmons %A Caspar Oesterheld %A Andrew Critch %A Vincent Conitzer %A Stuart Russell %B Proceedings of the 39th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2022 %E Kamalika Chaudhuri %E Stefanie Jegelka %E Le Song %E Csaba Szepesvari %E Gang Niu %E Sivan Sabato %F pmlr-v162-emmons22a %I PMLR %P 5924--5943 %U https://proceedings.mlr.press/v162/emmons22a.html %V 162 %X Although it has been known since the 1970s that a globally optimal strategy profile in a common-payoff game is a Nash equilibrium, global optimality is a strict requirement that limits the result’s applicability. In this work, we show that any locally optimal symmetric strategy profile is also a (global) Nash equilibrium. Furthermore, we show that this result is robust to perturbations to the common payoff and to the local optimum. Applied to machine learning, our result provides a global guarantee for any gradient method that finds a local optimum in symmetric strategy space. While this result indicates stability to unilateral deviation, we nevertheless identify broad classes of games where mixed local optima are unstable under joint, asymmetric deviations. We analyze the prevalence of instability by running learning algorithms in a suite of symmetric games, and we conclude by discussing the applicability of our results to multi-agent RL, cooperative inverse RL, and decentralized POMDPs.
APA
Emmons, S., Oesterheld, C., Critch, A., Conitzer, V. & Russell, S.. (2022). For Learning in Symmetric Teams, Local Optima are Global Nash Equilibria. Proceedings of the 39th International Conference on Machine Learning, in Proceedings of Machine Learning Research 162:5924-5943 Available from https://proceedings.mlr.press/v162/emmons22a.html.

Related Material