Strategy Complexity of Parity Objectives in Countable MDPs

Stefan Kiefer, Richard Mayr, Mahsa Shirmohammadi, Patrick Totzke

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.
Original languageEnglish
Title of host publication31st International Conference on Concurrency Theory (CONCUR 2020)
PublisherSchloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany
Pages39:1--39:17
Number of pages17
ISBN (Electronic)978-3-95977-160-3
DOIs
Publication statusPublished - 26 Aug 2020
Event31st International Conference on Concurrency Theory - Vienna, Vienna, Austria
Duration: 1 Sep 20204 Sep 2020
https://concur2020.forsyte.at/

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
ISSN (Electronic)1868-8969

Conference

Conference31st International Conference on Concurrency Theory
Abbreviated titleCONCUR 2020
CountryAustria
CityVienna
Period1/09/204/09/20
Internet address

Keywords

  • Markov decision processes
  • Parity objectives
  • Levy’s zero-one law

Fingerprint Dive into the research topics of 'Strategy Complexity of Parity Objectives in Countable MDPs'. Together they form a unique fingerprint.

Cite this