Deng, Xiaotie;
Li, Ningyuan;
Mguni, David;
Wang, Jun;
Yang, Yaodong;
(2023)
On the complexity of computing Markov perfect equilibrium in general-sum stochastic games.
National Science Review
, 10
(1)
, Article nwac256. 10.1093/nsr/nwac256.
Preview |
Text
nwac256.pdf - Published Version Download (325kB) | Preview |
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.
| Type: | Article |
|---|---|
| Title: | On the complexity of computing Markov perfect equilibrium in general-sum stochastic games |
| Location: | China |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1093/nsr/nwac256 |
| Publisher version: | https://doi.org/10.1093/nsr/nwac256 |
| Language: | English |
| Additional information: | © The Author(s) 2022. Published by Oxford University Press on behalf of China Science Publishing & Media Ltd. This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0/), which permits unrestricted reuse, distribution, and reproduction in any medium, provided the original work is properly cited. |
| Keywords: | Markov game, multi-agent reinforcement learning, Markov perfect equilibrium, PPAD-completeness, stochastic game |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10171444 |
Archive Staff Only
 |
View Item |
