A Generic Strategy Improvement Method for Simple Stochastic Games

Autor: Auger, David, Montjoye, Xavier Badin De, Strozecki, Yann

Publikováno v: 46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021
46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021, Aug 2021, Tallinn, Estonia. ⟨10.4230/LIPIcs.MFCS.2021.12⟩

We present a generic strategy improvement algorithm (GSIA) to find an optimal strategy of simple stochastic games (SSG). We prove the correctness of GSIA, and derive a general complexity bound, which implies and improves on the results of several art

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::cd2e62523290b0682e077e5aa2d91bc0
https://hal.archives-ouvertes.fr/hal-03401817