Asymptotic Convergence and Performance of Multi-Agent Q-Learning Dynamics
This addresses the challenge of safe and reliable ML algorithms for autonomous systems, though it appears incremental as it builds on known convergence results for specific game types.
The paper tackles the problem of ensuring convergence of multi-agent Q-learning in general N-player games, showing a sufficient condition on exploration rates for guaranteed convergence to a unique equilibrium and analyzing performance via time-averaged social welfare.
Achieving convergence of multiple learning agents in general $N$-player 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.