Back to Search
Start Over
On the complexity of computing Markov perfect equilibrium in general-sum stochastic games.
- Source :
-
National Science Review . Jan2023, Vol. 10 Issue 1, p1-14. 14p. - Publication Year :
- 2023
-
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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 20955138
- Volume :
- 10
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- National Science Review
- Publication Type :
- Academic Journal
- Accession number :
- 162394147
- Full Text :
- https://doi.org/10.1093/nsr/nwac256