Paths to Equilibrium in Games
Not on the map. Why?
Abstract (arXiv)
In multi-agent reinforcement learning (MARL) and game theory, agents repeatedly interact and revise their strategies as new data arrives, producing a sequence of strategy profiles. This paper studies sequences of strategies satisfying a pairwise constraint inspired by policy updating in reinforcement learning, where an agent who is best responding in one period does not switch its strategy in the next period. This constraint merely requires that optimizing agents do not switch strategies, but does not constrain the non-optimizing agents in any way, and thus allows for exploration. Sequences with this property are called satisficing paths, and arise naturally in many MARL algorithms. A fundamental question about strategic dynamics is such: for a given game and initial strategy profile, is it always possible to construct a satisficing path that terminates at an equilibrium? The resolution of this question has implications about the capabilities or limitations of a class of MARL algorithms. We answer this question in the affirmative for normal-form games. Our analysis reveals a counterintuitive insight that reward deteriorating strategic updates are key to driving play to equilibrium along a satisficing path.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 18 of its 54 references that are in the map. First posted on arXiv 26 Mar 2024.
Builds on
18 of 54 references.
References · 18
- 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 555
- 2021A Practical Guide to Multi-Objective Reinforcement Learning and Planningcited by 240
- 2017Cycles in adversarial regularized learningcited by 122
- 2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 97
- 2021Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibriumcited by 51
- 2020No-regret learning and mixed Nash equilibria: They do not mixcited by 49
- 2018On Gradient-Based Learning in Continuous Gamescited by 46
- 2015Decentralized Q-Learning for Stochastic Teams and Gamescited by 34
- 2020Adversarial Example Gamescited by 34
- 2020Fictitious play in zero-sum stochastic gamescited by 24
- 2013Nash Convergence of Gradient Dynamics in Iterated General-Sum Gamescited by 18
- 2022Two-Scale Gradient Descent Ascent Dynamics Finds Mixed Nash Equilibria of Continuous Games: A Mean-Field Perspectivecited by 13
6 more
- 2019Decentralized Learning for Optimality in Stochastic Dynamic Teams and Games with Local Control and Global State Informationcited by 12
- 2021Satisficing Paths and Independent Multi-Agent Reinforcement Learning in Stochastic Gamescited by 9
- 2021Best-Response Dynamics and Fictitious Play in Identical-Interest and Zero-Sum Stochastic Gamescited by 9
- 2022Fictitious Play in Markov Games with Single Controllercited by 9
- 2022Nash Equilibria and Pitfalls of Adversarial Training in Adversarial Robustness Gamescited by 8
- 2016Distributed Inertial Best-Response Dynamicscited by 3
Built on by
Citing papers per year: 2025: 1.
1 paper.