How to Play in Infinite MDPs (Invited Talk)

Stefan Kiefer; Richard Mayr; Mahsa Shirmohammadi; Patrick Totzke; Dominik Wojtczak

doi:10.4230/LIPIcs.ICALP.2020.3

How to Play in Infinite MDPs (Invited Talk)

Stefan Kiefer, Richard Mayr, Mahsa Shirmohammadi, Patrick Totzke, Dominik Wojtczak

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

Abstract

Markov decision processes (MDPs) are a standard model for dynamic systems that exhibit both stochastic and nondeterministic behavior. For MDPs with finite state space it is known that for a wide range of objectives there exist optimal strategies that are memoryless and deterministic. In contrast, if the state space is infinite, optimal strategies may not exist, and optimal or ε-optimal strategies may require (possibly infinite) memory. In this paper we consider qualitative objectives: reachability, safety, (co-)Büchi, and other parity objectives. We aim at giving an introduction to a collection of techniques that allow for the construction of strategies with little or no memory in countably infinite MDPs.

Original language	English
Title of host publication	47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Editors	Artur Czumaj, Anuj Dawar, Emanuela Merelli
Publisher	Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany
Pages	1-18
Number of pages	18
ISBN (Print)	978-3-95977-138-2
DOIs	https://doi.org/10.4230/LIPIcs.ICALP.2020.3
Publication status	Published - 29 Jun 2020
Event	47th International Colloquium on Automata, Languages and Programming - Virtual conference, Germany Duration: 8 Jul 2020 → 11 Jul 2020 https://icalp2020.saarland-informatics-campus.de/

Publication series

Name	Leibniz International Proceedings in Informatics (LIPIcs)
Publisher	Schloss Dagstuhl--Leibniz-Zentrum für Informatik
Volume	168
ISSN (Electronic)	1868-8969

Conference

Conference	47th International Colloquium on Automata, Languages and Programming
Abbreviated title	ICALP 2020
Country/Territory	Germany
City	Virtual conference
Period	8/07/20 → 11/07/20
Internet address	https://icalp2020.saarland-informatics-campus.de/

Keywords

Markov decision processes

Access to Document

10.4230/LIPIcs.ICALP.2020.3Licence: Creative Commons: Attribution (CC-BY)

How to Play_KIEFER_DOA15042020_VOR_CC-BYFinal published version, 560 KBLicence: Creative Commons: Attribution (CC-BY)

https://drops.dagstuhl.de/opus/volltexte/2020/12410/Licence: Creative Commons: Attribution (CC-BY)

Cite this

Kiefer, S., Mayr, R., Shirmohammadi, M., Totzke, P., & Wojtczak, D. (2020). How to Play in Infinite MDPs (Invited Talk). In A. Czumaj, A. Dawar, & E. Merelli (Eds.), 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) (pp. 1-18). [3] (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 168). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany. https://doi.org/10.4230/LIPIcs.ICALP.2020.3

Kiefer, Stefan ; Mayr, Richard ; Shirmohammadi, Mahsa et al. / How to Play in Infinite MDPs (Invited Talk). 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). editor / Artur Czumaj ; Anuj Dawar ; Emanuela Merelli. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, 2020. pp. 1-18 (Leibniz International Proceedings in Informatics (LIPIcs)).

@inproceedings{305e5bf3c66e482e891df04a3e70bb1a,

title = "How to Play in Infinite MDPs (Invited Talk)",

abstract = "Markov decision processes (MDPs) are a standard model for dynamic systems that exhibit both stochastic and nondeterministic behavior. For MDPs with finite state space it is known that for a wide range of objectives there exist optimal strategies that are memoryless and deterministic. In contrast, if the state space is infinite, optimal strategies may not exist, and optimal or ε-optimal strategies may require (possibly infinite) memory. In this paper we consider qualitative objectives: reachability, safety, (co-)B{\"u}chi, and other parity objectives. We aim at giving an introduction to a collection of techniques that allow for the construction of strategies with little or no memory in countably infinite MDPs. ",

keywords = "Markov decision processes",

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

year = "2020",

month = jun,

day = "29",

doi = "10.4230/LIPIcs.ICALP.2020.3",

language = "English",

isbn = "978-3-95977-138-2",

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

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

pages = "1--18",

editor = "Artur Czumaj and Anuj Dawar and Emanuela Merelli",

booktitle = "47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)",

note = "47th International Colloquium on Automata, Languages and Programming, ICALP 2020 ; Conference date: 08-07-2020 Through 11-07-2020",

url = "https://icalp2020.saarland-informatics-campus.de/",

}

Kiefer, S, Mayr, R, Shirmohammadi, M, Totzke, P & Wojtczak, D 2020, How to Play in Infinite MDPs (Invited Talk). in A Czumaj, A Dawar & E Merelli (eds), 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)., 3, Leibniz International Proceedings in Informatics (LIPIcs), vol. 168, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, pp. 1-18, 47th International Colloquium on Automata, Languages and Programming, Virtual conference, Germany, 8/07/20. https://doi.org/10.4230/LIPIcs.ICALP.2020.3

How to Play in Infinite MDPs (Invited Talk). / Kiefer, Stefan; Mayr, Richard; Shirmohammadi, Mahsa et al.

47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). ed. / Artur Czumaj; Anuj Dawar; Emanuela Merelli. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, 2020. p. 1-18 3 (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 168).

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

TY - GEN

T1 - How to Play in Infinite MDPs (Invited Talk)

AU - Kiefer, Stefan

AU - Mayr, Richard

AU - Shirmohammadi, Mahsa

AU - Totzke, Patrick

AU - Wojtczak, Dominik

PY - 2020/6/29

Y1 - 2020/6/29

N2 - Markov decision processes (MDPs) are a standard model for dynamic systems that exhibit both stochastic and nondeterministic behavior. For MDPs with finite state space it is known that for a wide range of objectives there exist optimal strategies that are memoryless and deterministic. In contrast, if the state space is infinite, optimal strategies may not exist, and optimal or ε-optimal strategies may require (possibly infinite) memory. In this paper we consider qualitative objectives: reachability, safety, (co-)Büchi, and other parity objectives. We aim at giving an introduction to a collection of techniques that allow for the construction of strategies with little or no memory in countably infinite MDPs.

AB - Markov decision processes (MDPs) are a standard model for dynamic systems that exhibit both stochastic and nondeterministic behavior. For MDPs with finite state space it is known that for a wide range of objectives there exist optimal strategies that are memoryless and deterministic. In contrast, if the state space is infinite, optimal strategies may not exist, and optimal or ε-optimal strategies may require (possibly infinite) memory. In this paper we consider qualitative objectives: reachability, safety, (co-)Büchi, and other parity objectives. We aim at giving an introduction to a collection of techniques that allow for the construction of strategies with little or no memory in countably infinite MDPs.

KW - Markov decision processes

U2 - 10.4230/LIPIcs.ICALP.2020.3

DO - 10.4230/LIPIcs.ICALP.2020.3

M3 - Conference contribution

SN - 978-3-95977-138-2

T3 - Leibniz International Proceedings in Informatics (LIPIcs)

SP - 1

EP - 18

BT - 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

A2 - Czumaj, Artur

A2 - Dawar, Anuj

A2 - Merelli, Emanuela

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

T2 - 47th International Colloquium on Automata, Languages and Programming

Y2 - 8 July 2020 through 11 July 2020

ER -

Kiefer S, Mayr R, Shirmohammadi M, Totzke P, Wojtczak D. How to Play in Infinite MDPs (Invited Talk). In Czumaj A, Dawar A, Merelli E, editors, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany. 2020. p. 1-18. 3. (Leibniz International Proceedings in Informatics (LIPIcs)). doi: 10.4230/LIPIcs.ICALP.2020.3

How to Play in Infinite MDPs (Invited Talk)

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this