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 proceedingConference 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 languageEnglish
Title of host publication47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
EditorsArtur Czumaj, Anuj Dawar, Emanuela Merelli
PublisherSchloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany
Pages1-18
Number of pages18
ISBN (Print)978-3-95977-138-2
DOIs
Publication statusPublished - 29 Jun 2020
Event47th International Colloquium on Automata, Languages and Programming - Virtual conference, Germany
Duration: 8 Jul 202011 Jul 2020
https://icalp2020.saarland-informatics-campus.de/

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
PublisherSchloss Dagstuhl--Leibniz-Zentrum für Informatik
Volume168
ISSN (Electronic)1868-8969

Conference

Conference47th International Colloquium on Automata, Languages and Programming
Abbreviated titleICALP 2020
CountryGermany
CityVirtual conference
Period8/07/2011/07/20
Internet address

Keywords

  • Markov decision processes

Fingerprint Dive into the research topics of 'How to Play in Infinite MDPs (Invited Talk)'. Together they form a unique fingerprint.

Cite this