2026-08-10T18:11:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14452 2024-03-06T10:54:02Z ddc:004 open_access

A Generic Strategy Improvement Method for Simple Stochastic Games Auger, David Badin de Montjoye, Xavier Strozecki, Yann Simple Stochastic Games Strategy Improvement Parametrized Complexity Stopping Meta Algorithm f-strategy 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 articles. First, we remove the assumption that the SSG is stopping, which is usually obtained by a polynomial blowup of the game. Second, we prove a tight bound on the denominator of the values associated to a strategy, and use it to prove that all strategy improvement algorithms are in fact fixed parameter tractable in the number r of random vertices. All known strategy improvement algorithms can be seen as instances of GSIA, which allows to analyze the complexity of converge from below by Condon [Condon, 1993] and to propose a class of algorithms generalising Gimbert and Horn’s algorithm [Gimbert and Horn, 2008; Gimbert and Horn, 2009]. These algorithms terminate in at most r! iterations, and for binary SSGs, they do less iterations than the current best deterministic algorithm given by Ibsen-Jensen and Miltersen [Ibsen-Jensen and Miltersen, 2012]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik David Auger and Xavier Badin de Montjoye and Yann Strozecki 2021 Is Part Of LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2021.12 urn:nbn:de:0030-drops-144524 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.12 eng https://creativecommons.org/licenses/by/4.0/legalcode