EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

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

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

National Science Review · 14.01.2023 · 10 (1)

DOI: 10.1093/nsr/nwac256 ↗

Kurz gefasst

Fachartikel in der Zeitschrift National Science Review, online erschienen am 22.11.2022. Verfasst von Xiaotie Deng und 4 weiteren Autor:innen. Beteiligte Einrichtung: Center on Frontiers of Computing Studies, School of Computer Science, Peking University, Beijing 100091, China. Die Arbeit wurde bisher 29-mal zitiert (Crossref) und nennt 54 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Science and Technology Innovation.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Schlagwörter

Stichwörter der Autor:innen

Markov gameMarkov perfect equilibriumPPAD-completenessmulti-agent reinforcement learningstochastic game

Autor:innen und Institutionen

  • Center on Frontiers of Computing Studies, School of Computer Science, Peking University, Beijing 100091, China.
  • Center for Multi-Agent Research, Institute for AI, Peking University, Beijing 100091, China.
  • Huawei UK, London WC1E 6BT, UK.
  • Computer Science, University College London, London WC1E 6BT, UK.

Förderung

  • Science and Technology Innovation

Zitieren

APA

Deng, X., Li, N., Mguni, D., Wang, J., & Yang, Y. (2023). On the complexity of computing Markov perfect equilibrium in general-sum stochastic games. National Science Review, 10(1). https://doi.org/10.1093/nsr/nwac256

Vancouver

Deng X, Li N, Mguni D, Wang J, Yang Y. On the complexity of computing Markov perfect equilibrium in general-sum stochastic games. National Science Review. 2023;10(1). doi:10.1093/nsr/nwac256

BibTeX
@article{Deng2023,
  author = {Deng, Xiaotie and Li, Ningyuan and Mguni, David and Wang, Jun and Yang, Yaodong},
  title = {On the complexity of computing Markov perfect equilibrium in general-sum stochastic games},
  journal = {National Science Review},
  year = {2023},
  volume = {10},
  number = {1},
  doi = {10.1093/nsr/nwac256}
}
Kostenlos starten →