Asymptotic convergence and performance of multi-agent Q-learning dynamics
File(s)Convergence_and_Optimality.pdf (1.48 MB)
Accepted version
Author(s)
Hussain, AA
Belardinelli, F
Piliouras, G
Type
Conference Paper
Abstract
Achieving convergence of multiple learning agents in general Nplayer games is imperative for the development of safe and reliable machine learning (ML) algorithms and their application to autonomous systems. Yet it is known that, outside the bounds of simple two-player games, convergence cannot be taken for granted. To make progress in resolving this problem, we study the dynamics of smooth Q-Learning, a popular reinforcement learning algorithm which quantifies the tendency for learning agents to explore their state space or exploit their payoffs. We show a sufficient condition on the rate of exploration such that the Q-Learning dynamics Is guaranteed to converge to a unique equilibrium in any game. We connect this result to games for which Q-Learning is known to converge with arbitrary exploration rates, including weighted Potential games and weighted zero sum polymatrix games. Finally, we examine the performance of the Q-Learning dynamic as measured by the Time Averaged Social Welfare, and comparing this with the Social Welfare achieved by the equilibrium. We provide a sufficient condition whereby the Q-Learning dynamic will outperform the equilibrium even if the dynamics do not converge.
Date Issued
2023-05-30
Date Acceptance
2023-05-29
Citation
Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS, 2023, 2023-May, pp.1578-1586
ISBN
9781450394321
ISSN
1548-8403
Publisher
ACM
Start Page
1578
End Page
1586
Journal / Book Title
Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS
Volume
2023-May
Copyright Statement
©ACM 2023 This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in AAMAS '23: Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems
Identifier
https://dl.acm.org/doi/10.5555/3545946.3598813
Source
The 22nd International Conference on Autonomous Agents and Multiagent Systems
Publication Status
Published
Start Date
2023-05-29
Finish Date
2023-06-02
Coverage Spatial
London, UK
Date Publish Online
2023-05-30