Convergence Analysis of Graphical Game-Based Nash Q−Learning using the Interaction Detection Signal of N−Step Return
Yunkai Zhuang, Shangdong Yang, Wenbin Li, Yang Gao · 2023
The graphical game provides an effective method for modeling different kinds of sparse interactions in multi-agent reinforcement learning. Most previous work on game abstraction lacks theoretical guarantees of convergence. In this paper, we adopt the ${\mathcal{N}}$-step return signal to detect interactions between agents and build the Markov graphical game based on it. We analyze that the solution of the Markov graphical game is an ϵ-Nash equilibrium which guarantees the convergence of the proposed NSR-G2NashQ algorithm theoretically. Also, we have done experiments in different multi-agent reinforcement learning tasks with both tabular and function approximation solutions. The results show the NSR-G2NashQ algorithm accelerates the convergence of agents to the optimal policy.