2026-08-08T03:43:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12851 2024-03-06T10:50:51Z ddc:004 open_access

Strategy Complexity of Parity Objectives in Countable MDPs Kiefer, Stefan Mayr, Richard Shirmohammadi, Mahsa Totzke, Patrick Markov decision processes Parity objectives Levy’s zero-one law We study countably infinite MDPs with parity objectives. Unlike in finite MDPs, optimal strategies need not exist, and may require infinite memory if they do. We provide a complete picture of the exact strategy complexity of ε-optimal strategies (and optimal strategies, where they exist) for all subclasses of parity objectives in the Mostowski hierarchy. Either MD-strategies, Markov strategies, or 1-bit Markov strategies are necessary and sufficient, depending on the number of colors, the branching degree of the MDP, and whether one considers ε-optimal or optimal strategies. In particular, 1-bit Markov strategies are necessary and sufficient for ε-optimal (resp. optimal) strategies for general parity objectives. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Stefan Kiefer and Richard Mayr and Mahsa Shirmohammadi and Patrick Totzke 2020 Is Part Of LIPIcs, Volume 171, 31st International Conference on Concurrency Theory (CONCUR 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CONCUR.2020.39 urn:nbn:de:0030-drops-128513 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2020.39 eng https://creativecommons.org/licenses/by/3.0/legalcode