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
Abstract
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-G<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>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<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>NashQ algorithm accelerates the convergence of agents to the optimal policy.
BibTeX
@inproceedings{icassp2023_convergenceanaly,
title = {Convergence Analysis of Graphical Game-Based Nash Q-Learning using the Interaction Detection Signal of N-Step Return},
author = {Yunkai Zhuang and Shangdong Yang and Wenbin Li and Yang Gao},
booktitle = {ICASSP 2023},
year = {2023}
}