On the stability of learning in network games with many players
File(s)
Published version
Author(s)
Hussain, A
Belardinelli, F
Leonte, D
Piliouras, G
Type
Conference Paper
Abstract
Multi-agent learning algorithms have been shown to display complex, unstable behaviours in a wide array of games. In fact, previous works indicate that convergent behaviours are less likely to occur as the total number of agents increases. This seemingly prohibits convergence to stable strategies, such as Nash Equilibria, in games with many players. To make progress towards addressing this challenge we study the Q-Learning Dynamics, a classical model for exploration and exploitation in multi-agent learning. In particular, we study the behaviour of Q-Learning on games where interactions between agents are constrained by a network. We determine a number of sufficient conditions, depending on the game and network structure, which guarantee that agent strategies converge to a unique stable strategy, called the Quantal Response Equilibrium (QRE). Crucially, these sufficient conditions are independent of the total number of agents, allowing for provable convergence in arbitrarily large games. Next, we compare the learned QRE to the underlying NE of the game, by showing that any QRE is an n-approximate Nash Equilibrium. Wefi rst provide tight bounds on n and show how these bounds lead naturally to a centralised scheme for choosing exploration rates, which enables independent learners to learn stable approximate Nash Equilibrium strategies. We validate the method through experiments and demonstrate its effectiveness even in the presence of numerous agents and actions. Through these results, we show that independent learning dynamics may converge to approximate Nash Equilibria, even in the presence of many agents.
Date Issued
2024-05-06
Date Acceptance
2024-05-01
Citation
Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS, 2024, pp.861-870
ISBN
9798400704864
ISSN
1548-8403
Publisher
International Foundation for Autonomous Agents and Multiagent Systems
Start Page
861
End Page
870
Journal / Book Title
Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS
Volume
2024-May
Copyright Statement
© 2024 International Foundation for Autonomous Agents and Multiagent Systems. This work is licensed under a Creative Commons Attribution International 4.0 Licence (https://creativecommons.org/licenses/by/4.0/)
License URL
Source
AAMAS '24
Subjects
Multi-Agent Learning
Quantal Response Equilibrium
Online Learning in Games This work is licensed under a Creative Commons Attribution International 4.0 License
Publication Status
Published
Start Date
2024-05-06
Finish Date
2024-05-10
Coverage Spatial
Auckland New Zealand