Sample Complexity of Decentralized Tabular Q-Learning for Stochastic Games

Zuguang Gao, Qianqian Ma, Tamer Başar, John R. Birge

Research output: Chapter in Book/Report/Conference proceedingConference contribution


In this paper, we carry out finite-sample analysis of decentralized Q-learning algorithms in the tabular setting for a significant subclass of general-sum stochastic games (SGs) - weakly acyclic SGs, which includes potential games and Markov team problems as special cases. In the practical while challenging decentralized setting, neither the rewards nor the actions of other agents can be observed by each agent. In fact, each agent can be completely oblivious to the presence of other decision makers. In this work, the sample complexity of the decentralized tabular Q-learning algorithm in [1] to converge to a Markov perfect equilibrium is developed.

Original languageEnglish (US)
Title of host publication2023 American Control Conference, ACC 2023
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages6
ISBN (Electronic)9798350328066
StatePublished - 2023
Event2023 American Control Conference, ACC 2023 - San Diego, United States
Duration: May 31 2023Jun 2 2023

Publication series

NameProceedings of the American Control Conference
ISSN (Print)0743-1619


Conference2023 American Control Conference, ACC 2023
Country/TerritoryUnited States
CitySan Diego

ASJC Scopus subject areas

  • Electrical and Electronic Engineering

Cite this