Strategy Complexity of Parity Objectives in Countable MDPs

Stefan Kiefer; Richard Mayr; Mahsa Shirmohammadi; Patrick Totzke

doi:10.4230/LIPIcs.CONCUR.2020.39

Strategy Complexity of Parity Objectives in Countable MDPs

Stefan Kiefer, Richard Mayr, Mahsa Shirmohammadi, Patrick Totzke

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English
Title of host publication	31st International Conference on Concurrency Theory (CONCUR 2020)
Publisher	Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany
Pages	39:1--39:17
Number of pages	17
ISBN (Electronic)	978-3-95977-160-3
DOIs	https://doi.org/10.4230/LIPIcs.CONCUR.2020.39
Publication status	Published - 26 Aug 2020
Event	31st International Conference on Concurrency Theory - Vienna, Vienna, Austria Duration: 1 Sep 2020 → 4 Sep 2020 https://concur2020.forsyte.at/

Publication series

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

Conference

Conference	31st International Conference on Concurrency Theory
Abbreviated title	CONCUR 2020
Country/Territory	Austria
City	Vienna
Period	1/09/20 → 4/09/20
Internet address	https://concur2020.forsyte.at/

Keywords

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

Access to Document

10.4230/LIPIcs.CONCUR.2020.39Licence: Creative Commons: Attribution (CC-BY)

2007.05065Accepted author manuscript, 982 KBLicence: Creative Commons: Attribution (CC-BY)
Strategy Complexity_KIEFER_DOA20072020_VOR_CC-BYFinal published version, 704 KBLicence: Creative Commons: Attribution (CC-BY)

Richard Mayr
- Mayr36.teaching-admined.acuk
Person: Academic: Research Active

Cite this

Kiefer, S., Mayr, R., Shirmohammadi, M., & Totzke, P. (2020). Strategy Complexity of Parity Objectives in Countable MDPs. In 31st International Conference on Concurrency Theory (CONCUR 2020) (pp. 39:1--39:17). [39] (Leibniz International Proceedings in Informatics (LIPIcs)). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany. https://doi.org/10.4230/LIPIcs.CONCUR.2020.39

@inproceedings{a1743b040c5f41b0b72c9b02562eca59,

title = "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. ",

keywords = "Markov decision processes, Parity objectives, Levy{\textquoteright}s zero-one law",

author = "Stefan Kiefer and Richard Mayr and Mahsa Shirmohammadi and Patrick Totzke",

year = "2020",

month = aug,

day = "26",

doi = "10.4230/LIPIcs.CONCUR.2020.39",

language = "English",

series = "Leibniz International Proceedings in Informatics (LIPIcs)",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany",

pages = "39:1----39:17",

booktitle = "31st International Conference on Concurrency Theory (CONCUR 2020)",

note = "31st International Conference on Concurrency Theory, CONCUR 2020 ; Conference date: 01-09-2020 Through 04-09-2020",

url = "https://concur2020.forsyte.at/",

}

Kiefer, S, Mayr, R, Shirmohammadi, M & Totzke, P 2020, Strategy Complexity of Parity Objectives in Countable MDPs. in 31st International Conference on Concurrency Theory (CONCUR 2020)., 39, Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, pp. 39:1--39:17, 31st International Conference on Concurrency Theory, Vienna, Austria, 1/09/20. https://doi.org/10.4230/LIPIcs.CONCUR.2020.39

Strategy Complexity of Parity Objectives in Countable MDPs. / Kiefer, Stefan; Mayr, Richard; Shirmohammadi, Mahsa et al.

31st International Conference on Concurrency Theory (CONCUR 2020). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, 2020. p. 39:1--39:17 39 (Leibniz International Proceedings in Informatics (LIPIcs)).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Strategy Complexity of Parity Objectives in Countable MDPs

AU - Kiefer, Stefan

AU - Mayr, Richard

AU - Shirmohammadi, Mahsa

AU - Totzke, Patrick

PY - 2020/8/26

Y1 - 2020/8/26

N2 - 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.

AB - 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.

KW - Markov decision processes

KW - Parity objectives

KW - Levy’s zero-one law

U2 - 10.4230/LIPIcs.CONCUR.2020.39

DO - 10.4230/LIPIcs.CONCUR.2020.39

M3 - Conference contribution

T3 - Leibniz International Proceedings in Informatics (LIPIcs)

SP - 39:1--39:17

BT - 31st International Conference on Concurrency Theory (CONCUR 2020)

PB - Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany

T2 - 31st International Conference on Concurrency Theory

Y2 - 1 September 2020 through 4 September 2020

ER -

Strategy Complexity of Parity Objectives in Countable MDPs

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Profiles

Richard Mayr

Cite this