Finite-sample Guarantees for Nash Q-learning with Linear Function Approximation

Autor:	Cisneros-Velarde, Pedro, Koyejo, Sanmi
Rok vydání:	2023
Předmět:	Computer Science - Machine Learning Computer Science - Artificial Intelligence
Druh dokumentu:	Working Paper
Popis:	Nash Q-learning may be considered one of the first and most known algorithms in multi-agent reinforcement learning (MARL) for learning policies that constitute a Nash equilibrium of an underlying general-sum Markov game. Its original proof provided asymptotic guarantees and was for the tabular case. Recently, finite-sample guarantees have been provided using more modern RL techniques for the tabular case. Our work analyzes Nash Q-learning using linear function approximation -- a representation regime introduced when the state space is large or continuous -- and provides finite-sample guarantees that indicate its sample efficiency. We find that the obtained performance nearly matches an existing efficient result for single-agent RL under the same representation and has a polynomial gap when compared to the best-known result for the tabular case. Comment: 25 pages. arXiv admin note: text overlap with arXiv:2205.15891
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2303.00177 Zobrazit plný text záznamu View this record from Arxiv