Sample Complexity of Decentralized Tabular Q-Learning for Stochastic Games

被引：2

作者：

Gao, Zuguang ^{[1
]}

Ma, Qianqian ^{[2
]}

Basar, Tamer ^{[3
]}

Birge, John R. ^{[1
]}

机构：

[1] Univ Chicago, Booth Sch Business, Chicago, IL 60637 USA

[2] Boston Univ, Dept Elect & Comp Engn, Boston, MA 02215 USA

[3] Univ Illinois, Coordinated Sci Lab, Urbana, IL 61801 USA

来源：

2023 AMERICAN CONTROL CONFERENCE, ACC | 2023年

基金：

美国国家科学基金会;

关键词：

D O I：

10.23919/ACC55779.2023.10155822

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

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.

引用

页码：1098 / 1103

页数：6

共 50 条

[21] Smooth Q-Learning: An Algorithm for Independent Learners in Stochastic Cooperative Markov Games
Amhraoui, Elmehdi
Masrour, Tawfik
JOURNAL OF INTELLIGENT & ROBOTIC SYSTEMS, 2023, 108 (04)
[22] Decentralized Q-Learning for Uplink Power Control
Dzulkifly, Sumayyah
Giupponi, Lorenza
Said, Fatin
Dohler, Mischa
2015 IEEE 20TH INTERNATIONAL WORKSHOP ON COMPUTER AIDED MODELLING AND DESIGN OF COMMUNICATION LINKS AND NETWORKS (CAMAD), 2015, : 54 - 58
[23] Individual Q-learning in normal form games
Leslie, DS
Collins, EJ
SIAM JOURNAL ON CONTROL AND OPTIMIZATION, 2005, 44 (02) : 495 - 514
[24] On the Sample Complexity of Learning Graphical Games
Honorio, Jean
2017 55TH ANNUAL ALLERTON CONFERENCE ON COMMUNICATION, CONTROL, AND COMPUTING (ALLERTON), 2017, : 830 - 836
[25] I2Q: A Fully Decentralized Q-Learning Algorithm
Jiang, Jiechuan
Lu, Zongqing
ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 35 (NEURIPS 2022), 2022,
[26] Stochastic Variance Reduction for Deep Q-learning
Zhao, Wei-Ye
Peng, Jian
AAMAS '19: PROCEEDINGS OF THE 18TH INTERNATIONAL CONFERENCE ON AUTONOMOUS AGENTS AND MULTIAGENT SYSTEMS, 2019, : 2318 - 2320
[27] ASYNCHRONOUS STOCHASTIC-APPROXIMATION AND Q-LEARNING
TSITSIKLIS, JN
MACHINE LEARNING, 1994, 16 (03) : 185 - 202
[28] Q-Learning in Regularized Mean-field Games
Anahtarci, Berkay
Kariksiz, Can Deha
Saldi, Naci
DYNAMIC GAMES AND APPLICATIONS, 2023, 13 (01) : 89 - 117
[29] Q-Learning in Regularized Mean-field Games
Berkay Anahtarci
Can Deha Kariksiz
Naci Saldi
Dynamic Games and Applications, 2023, 13 : 89 - 117
[30] Autonomous Decentralized Traffic Control Using Q-Learning in LPWAN
Kaburaki, Aoto
Adachi, Koichi
Takyu, Osamu
Ohta, Mai
Fujii, Takeo
IEEE ACCESS, 2021, 9 : 93651 - 93661

← 1 2 3 4 5 →