We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
On the complexity of computing Markov perfect equilibrium in general-sum stochastic games.
- Authors
Deng, Xiaotie; Li, Ningyuan; Mguni, David; Wang, Jun; Yang, Yaodong
- 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.
- Subjects
MACHINE learning; REINFORCEMENT learning; SEQUENTIAL learning; MARKOV processes; EQUILIBRIUM; GAMES
- Publication
National Science Review, 2023, Vol 10, Issue 1, p1
- ISSN
2095-5138
- Publication type
Article
- DOI
10.1093/nsr/nwac256