On the complexity of computing Markov perfect equilibrium in general-sum stochastic games

Xiaotie Deng; Ningyuan Li; David Mguni; Jun Wang; Yaodong Yang

doi:10.1093/nsr/nwac256

On the complexity of computing Markov perfect equilibrium in general-sum stochastic games

Xiaotie Deng^*
, Ningyuan Li^*
, David Mguni
, Jun Wang
, Yaodong Yang^*

^*Corresponding author for this work

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

38 Citations (Scopus)

1 Downloads (CityUHK Scholars)

Abstract

Similar to the role of Markov decision processes in reinforcement learning, Markov games (also called stochastic games) lay down the foundation for the study of multi-agent reinforcement learning and sequential agent interactions. We introduce approximate Markov perfect equilibrium as a solution to the computational problem of finite-state stochastic games repeated in the infinite horizon and prove its PPAD-completeness. This solution concept preserves the Markov perfect property and opens up the possibility for the success of multi-agent reinforcement learning algorithms on static two-player games to be extended to multi-agent dynamic games, expanding the reign of the PPAD-complete class. © The Author(s) 2022. Published by Oxford University Press on behalf of China Science Publishing & Media Ltd.

Original language	English
Article number	nwac256
Number of pages	14
Journal	National Science Review
Volume	10
Issue number	1
Online published	22 Nov 2022
DOIs	https://doi.org/10.1093/nsr/nwac256
Publication status	Published - Jan 2023
Externally published	Yes

Funding

This work was partially supported by the Science and Technology Innovation 2030 New Generation of Artificial Intelligence Major Project (2018AAA0100901). We would like to thank Yuhao Li for his early work, when he was an undergraduate student at Peking University.

Research Keywords

Markov game
Markov perfect equilibrium
multi-agent reinforcement learning
PPAD-completeness
stochastic game

Publisher's Copyright Statement

This full text is made available under CC-BY 4.0. https://creativecommons.org/licenses/by/4.0/

Access Output

10.1093/nsr/nwac256

502773937.pdfFinal Published version, 452 KBLicence: CC BY

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{1264b90441e54b4daae27402c0ea84fd,

title = "On the complexity of computing Markov perfect equilibrium in general-sum stochastic games",

abstract = "Similar to the role of Markov decision processes in reinforcement learning, Markov games (also called stochastic games) lay down the foundation for the study of multi-agent reinforcement learning and sequential agent interactions. We introduce approximate Markov perfect equilibrium as a solution to the computational problem of finite-state stochastic games repeated in the infinite horizon and prove its PPAD-completeness. This solution concept preserves the Markov perfect property and opens up the possibility for the success of multi-agent reinforcement learning algorithms on static two-player games to be extended to multi-agent dynamic games, expanding the reign of the PPAD-complete class. {\textcopyright} The Author(s) 2022. Published by Oxford University Press on behalf of China Science Publishing \& Media Ltd.",

keywords = "Markov game, Markov perfect equilibrium, multi-agent reinforcement learning, PPAD-completeness, stochastic game",

author = "Xiaotie Deng and Ningyuan Li and David Mguni and Jun Wang and Yaodong Yang",

year = "2023",

month = jan,

doi = "10.1093/nsr/nwac256",

language = "English",

volume = "10",

journal = "National Science Review",

issn = "2095-5138",

publisher = "Oxford University Press",

number = "1",

}

TY - JOUR

T1 - On the complexity of computing Markov perfect equilibrium in general-sum stochastic games

AU - Deng, Xiaotie

AU - Li, Ningyuan

AU - Mguni, David

AU - Wang, Jun

AU - Yang, Yaodong

PY - 2023/1

Y1 - 2023/1

N2 - Similar to the role of Markov decision processes in reinforcement learning, Markov games (also called stochastic games) lay down the foundation for the study of multi-agent reinforcement learning and sequential agent interactions. We introduce approximate Markov perfect equilibrium as a solution to the computational problem of finite-state stochastic games repeated in the infinite horizon and prove its PPAD-completeness. This solution concept preserves the Markov perfect property and opens up the possibility for the success of multi-agent reinforcement learning algorithms on static two-player games to be extended to multi-agent dynamic games, expanding the reign of the PPAD-complete class. © The Author(s) 2022. Published by Oxford University Press on behalf of China Science Publishing & Media Ltd.

AB - Similar to the role of Markov decision processes in reinforcement learning, Markov games (also called stochastic games) lay down the foundation for the study of multi-agent reinforcement learning and sequential agent interactions. We introduce approximate Markov perfect equilibrium as a solution to the computational problem of finite-state stochastic games repeated in the infinite horizon and prove its PPAD-completeness. This solution concept preserves the Markov perfect property and opens up the possibility for the success of multi-agent reinforcement learning algorithms on static two-player games to be extended to multi-agent dynamic games, expanding the reign of the PPAD-complete class. © The Author(s) 2022. Published by Oxford University Press on behalf of China Science Publishing & Media Ltd.

KW - Markov game

KW - Markov perfect equilibrium

KW - multi-agent reinforcement learning

KW - PPAD-completeness

KW - stochastic game

UR - http://www.scopus.com/inward/record.url?scp=85159639070&partnerID=8YFLogxK

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85159639070&origin=recordpage

U2 - 10.1093/nsr/nwac256

DO - 10.1093/nsr/nwac256

M3 - RGC 21 - Publication in refereed journal

SN - 2095-5138

VL - 10

JO - National Science Review

JF - National Science Review

IS - 1

M1 - nwac256

ER -

On the complexity of computing Markov perfect equilibrium in general-sum stochastic games

Abstract

Funding

Research Keywords

Publisher's Copyright Statement

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Corrigendum to On the complexity of computing Markov perfect equilibrium in general-sum stochastic games

Cite this