Kiefer, Stefan, Mayr, Richard, Shirmohammadi, Mahsa and Totzke, Patrick 
ORCID: 0000-0001-5274-8190
(2020)
Strategy Complexity of Parity Objectives in Countable MDPs.
.
|
Text
2007.05065v1.pdf - Published version Download (1MB) | Preview |
|
|
Text
main.pdf - Author Accepted Manuscript Download (823kB) | Preview |
Abstract
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 $\varepsilon$-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 $\varepsilon$-optimal or optimal strategies. In particular, 1-bit Markov strategies are necessary and sufficient for $\varepsilon$-optimal (resp. optimal) strategies for general parity objectives.
| Item Type: | Conference or Workshop Item (Unspecified) |
|---|---|
| Additional Information: | urn: urn:nbn:de:0030-drops-128513 |
| Uncontrolled Keywords: | cs.LO, cs.LO |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 01 Sep 2020 09:32 |
| Last Modified: | 18 Jan 2023 23:35 |
| DOI: | 10.4230/LIPIcs.CONCUR.2020.39 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3099129 |
Dimensions
Dimensions
