Conference item icon

Conference item

Strategy complexity of parity objectives in countable MDPs

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 ε-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.
Publication status:
Published
Peer review status:
Peer reviewed

Actions

  • Cite

  • Print

Access Document

Files:
Publisher copy:
10.4230/LIPIcs.CONCUR.2020.39

Authors

More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Oxford college:
St John's College
Role:
Author
ORCID:
0000-0003-4173-6877

Publisher:
Schloss Dagstuhl
Journal:
LIPIcs More from this journal
Volume:
171
Pages:
1-17
Publication date:
2020-08-28
Acceptance date:
2020-06-29
Event title:
31st International Conference on Concurrency Theory (CONCUR 2020)
Event website:
https://concur2020.forsyte.at/
Event start date:
2020-09-01
Event end date:
2020-09-04
DOI:
ISSN:
1868-8969
ISBN:
9783959771603

Language:
English
Keywords:
Pubs id:
1119181
Local pid:
pubs:1119181
Deposit date:
2020-07-16
ARK identifier:

Terms of use

Views and Downloads





If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP