EUVIMEDEUVIMED entdecken
Crossref

Learning in Zero-Sum Markov Games: Relaxing Strong Reachability and Mixing Time Assumptions

Reda Ouhamma, Maryam Kamgarpour

Proceedings of the AAAI Conference on Artificial Intelligence · 14.03.2026 · 40 (20) · 17170-17178

DOI: 10.1609/aaai.v40i20.38767 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the AAAI Conference on Artificial Intelligence, online erschienen am 14.03.2026. Verfasst von Reda Ouhamma und 1 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We address payoff-based decentralized learning in infinite-horizon zero-sum Markov games. In this setting, each player makes decisions based solely on received rewards, without observing the opponent's strategy or actions, nor sharing information. Prior works established polynomial-time convergence to an approximate Nash equilibrium under strong reachability and mixing time assumptions. We propose a convergent algorithm that significantly relaxes these assumptions, requiring only the existence of a single policy with bounded reachability and mixing time. Our key algorithmic novelty is introducing Tsallis entropy regularization to smooth the best-response policy updates. By suitably tuning this regularization, we ensure sufficient exploration, thus bypassing previous stringent assumptions on the MDP. We prove a polynomial-time convergence to an approximate Nash equilibrium by establishing novel properties of the value and policy updates induced by the Tsallis entropy regularizer.

Zitieren

APA

Ouhamma, R., & Kamgarpour, M. (2026). Learning in Zero-Sum Markov Games: Relaxing Strong Reachability and Mixing Time Assumptions. Proceedings of the AAAI Conference on Artificial Intelligence, 40(20), 17170-17178. https://doi.org/10.1609/aaai.v40i20.38767

Vancouver

Ouhamma R, Kamgarpour M. Learning in Zero-Sum Markov Games: Relaxing Strong Reachability and Mixing Time Assumptions. Proceedings of the AAAI Conference on Artificial Intelligence. 2026;40(20):17170-17178. doi:10.1609/aaai.v40i20.38767

BibTeX
@article{Ouhamma2026,
  author = {Ouhamma, Reda and Kamgarpour, Maryam},
  title = {Learning in Zero-Sum Markov Games: Relaxing Strong Reachability and Mixing Time Assumptions},
  journal = {Proceedings of the AAAI Conference on Artificial Intelligence},
  year = {2026},
  volume = {40},
  number = {20},
  pages = {17170--17178},
  doi = {10.1609/aaai.v40i20.38767}
}
Kostenlos starten →