CONVERGENCE ANALYSIS OF GRAPHICAL GAME-BASED NASH $Q-$LEARNING USING THE INTERACTION DETECTION SIGNAL OF $\mathcal{N}-$STEP RETURN

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 $\epsilon$-Nash equilibrium which guarantees the convergence of the proposed NSR-G$^2$NashQ 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-G$^2$NashQ algorithm accelerates the convergence of agents to the optimal policy.