License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CONCUR.2020.39
URN: urn:nbn:de:0030-drops-128513
URL: https://drops.dagstuhl.de/opus/volltexte/2020/12851/
Go to the corresponding LIPIcs Volume Portal

Kiefer, Stefan ; Mayr, Richard ; Shirmohammadi, Mahsa ; Totzke, Patrick

Strategy Complexity of Parity Objectives in Countable MDPs

pdf-format:
LIPIcs-CONCUR-2020-39.pdf (0.7 MB)

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.

BibTeX - Entry

@InProceedings{kiefer_et_al:LIPIcs:2020:12851,
  author =	{Stefan Kiefer and Richard Mayr and Mahsa Shirmohammadi and Patrick Totzke},
  title =	{{Strategy Complexity of Parity Objectives in Countable MDPs}},
  booktitle =	{31st International Conference on Concurrency Theory (CONCUR 2020)},
  pages =	{39:1--39:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-160-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{171},
  editor =	{Igor Konnov and Laura Kov{\'a}cs},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12851},
  URN =		{urn:nbn:de:0030-drops-128513},
  doi =		{10.4230/LIPIcs.CONCUR.2020.39},
  annote =	{Keywords: Markov decision processes, Parity objectives, Levy’s zero-one law}
}

Keywords: Markov decision processes, Parity objectives, Levy’s zero-one law
Collection: 31st International Conference on Concurrency Theory (CONCUR 2020)
Issue Date: 2020
Date of publication: 26.08.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI