Kiefer, Stefan
[Verfasser:in];
Mayr, Richard
[Verfasser:in];
Shirmohammadi, Mahsa
[Verfasser:in];
Totzke, Patrick
[Verfasser:in]
;
Stefan Kiefer and Richard Mayr and Mahsa Shirmohammadi and Patrick Totzke
[Mitwirkende:r]
Strategy Complexity of Parity Objectives in Countable MDPs
Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
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.