2026-08-25T22:09:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27360 2026-08-24T14:08:31Z ddc:004 open_access

Mean-Payoff-Parity and Lifting Strategies from MDPs to 2-Player Stochastic Games Dantam, Mohan Mayr, Richard MDPs Stochastic Games Parity Mean-payoff Strategy complexity We consider the strategy complexity (i.e., memory and randomization) of optimal strategies in turn-based 2-player zero-sum stochastic games. Results in [Gimbert and Kelmendi, 2023; Richard Mayr et al., 2021] show how to lift optimal memoryless strategies for shift-invariant inverse-submixing objectives from MDPs to 2-player stochastic games with an exponential increase in the number of memory modes. We show the corresponding lower bound, i.e., the extra exponential memory is required in general, even for randomized strategies. Moreover, we solve the strategy complexity of the well-studied mean-payoff-parity objective (MP > 0 ∩ EPAR) in 2-player stochastic games. This objective is also shift-invariant inverse-submixing, but easier than the worst case for this class. In MDPs, Maximizer has optimal memoryless randomized strategies, while optimal deterministic strategies require exponential memory. However, in stochastic games, optimal randomized strategies require, at least and at most, linear memory (equal to the number of even colors). Finally, we show that the different construction in [Gimbert and Zielonka, 2009; Patricia Bouyer et al., 2023] for lifting memoryless (resp. finite-memory) deterministic strategies from MDPs (resp. 1-player games) to 2-player games cannot be generalized even to memoryless randomized strategies. We construct a shift-invariant objective where Max and Min each have optimal memoryless randomized strategies in all MDPs, but optimal (randomized) Max strategies still require infinite memory in deterministic 2-player games. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mohan Dantam and Richard Mayr 2026 Is Part Of LIPIcs, Volume 391, 37th International Conference on Concurrency Theory (CONCUR 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CONCUR.2026.30 urn:nbn:de:0030-drops-273601 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2026.30 eng https://creativecommons.org/licenses/by/4.0/legalcode