Abstract
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.
Abstract (translated)
实现多个学习代理在一般 $N$ player games 中的收敛对于安全且可靠的机器学习算法(机器学习算法)的发展和将其应用于自主系统至关重要。然而,众所周知,在简单的两个玩家游戏中之外,收敛不可视为理所当然。为了解决这个问题,我们对平滑 Q-Learning 的动态特性进行研究,这是一个流行的强化学习算法,衡量学习代理探索其状态空间或利用其收益的趋势。我们提供了探索率足够的充分条件,以确保 Q-Learning 动态特性在任何游戏中都收敛到独特的均衡。我们将其与已知的以任意探索率探索的游戏中,包括加权潜在游戏和加权零Sum 多矩阵游戏之间的联系。最后,我们检查 Q-Learning 动态的性能,通过时间平均的社会福利来衡量,并将其与均衡的社会福利实现进行比较。我们提供了足够的条件,使得 Q-Learning 动态即使动态不收敛,也能比均衡表现更好。
URL
https://arxiv.org/abs/2301.09619
