Back to Search
Start Over
On the complexity of computing Markov perfect equilibrium in general-sum stochastic games.
- Source :
-
National science review [Natl Sci Rev] 2022 Nov 22; Vol. 10 (1), pp. nwac256. Date of Electronic Publication: 2022 Nov 22 (Print Publication: 2023). - Publication Year :
- 2022
-
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.<br /> (© The Author(s) 2022. Published by Oxford University Press on behalf of China Science Publishing & Media Ltd.)
Details
- Language :
- English
- ISSN :
- 2053-714X
- Volume :
- 10
- Issue :
- 1
- Database :
- MEDLINE
- Journal :
- National science review
- Publication Type :
- Academic Journal
- Accession number :
- 36684520
- Full Text :
- https://doi.org/10.1093/nsr/nwac256