Strategy complexity of parity objectives in countable MDPs
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 sub...
| Main Authors: | , , , |
|---|---|
| Format: | Conference item |
| Language: | English |
| Published: |
Schloss Dagstuhl
2020
|
| _version_ | 1797080475456503808 |
|---|---|
| author | Kiefer, S Mayr, R Shirmohammadi, M Totzke, P |
| author_facet | Kiefer, S Mayr, R Shirmohammadi, M Totzke, P |
| author_sort | Kiefer, S |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-07T01:00:36Z |
| format | Conference item |
| id | oxford-uuid:89939a66-a99e-4318-9d30-bd7671ec15d5 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T01:00:36Z |
| publishDate | 2020 |
| publisher | Schloss Dagstuhl |
| record_format | dspace |
| spelling | oxford-uuid:89939a66-a99e-4318-9d30-bd7671ec15d52022-03-26T22:25:38ZStrategy complexity of parity objectives in countable MDPsConference itemhttp://purl.org/coar/resource_type/c_5794uuid:89939a66-a99e-4318-9d30-bd7671ec15d5EnglishSymplectic ElementsSchloss Dagstuhl2020Kiefer, SMayr, RShirmohammadi, MTotzke, PWe 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. |
| spellingShingle | Kiefer, S Mayr, R Shirmohammadi, M Totzke, P Strategy complexity of parity objectives in countable MDPs |
| title | Strategy complexity of parity objectives in countable MDPs |
| title_full | Strategy complexity of parity objectives in countable MDPs |
| title_fullStr | Strategy complexity of parity objectives in countable MDPs |
| title_full_unstemmed | Strategy complexity of parity objectives in countable MDPs |
| title_short | Strategy complexity of parity objectives in countable MDPs |
| title_sort | strategy complexity of parity objectives in countable mdps |
| work_keys_str_mv | AT kiefers strategycomplexityofparityobjectivesincountablemdps AT mayrr strategycomplexityofparityobjectivesincountablemdps AT shirmohammadim strategycomplexityofparityobjectivesincountablemdps AT totzkep strategycomplexityofparityobjectivesincountablemdps |