TY - GEN
T1 - Sample Complexity of Decentralized Tabular Q-Learning for Stochastic Games
AU - Gao, Zuguang
AU - Ma, Qianqian
AU - Başar, Tamer
AU - Birge, John R.
N1 - Publisher Copyright:
© 2023 American Automatic Control Council.
PY - 2023
Y1 - 2023
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85167819390&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85167819390&partnerID=8YFLogxK
U2 - 10.23919/ACC55779.2023.10155822
DO - 10.23919/ACC55779.2023.10155822
M3 - Conference contribution
AN - SCOPUS:85167819390
T3 - Proceedings of the American Control Conference
SP - 1098
EP - 1103
BT - 2023 American Control Conference, ACC 2023
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2023 American Control Conference, ACC 2023
Y2 - 31 May 2023 through 2 June 2023
ER -