License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CONCUR.2021.11
URN: urn:nbn:de:0030-drops-143881
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14388/
Go to the corresponding LIPIcs Volume Portal

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

Transience in Countable MDPs

pdf-format:
LIPIcs-CONCUR-2021-11.pdf (0.7 MB)

Abstract

The Transience objective is not to visit any state infinitely often. While this is not possible in any finite Markov Decision Process (MDP), it can be satisfied in countably infinite ones, e.g., if the transition graph is acyclic.
We prove the following fundamental properties of Transience in countably infinite MDPs.
1) There exist uniformly ε-optimal MD strategies (memoryless deterministic) for Transience, even in infinitely branching MDPs.
2) Optimal strategies for Transience need not exist, even if the MDP is finitely branching. However, if an optimal strategy exists then there is also an optimal MD strategy.
3) If an MDP is universally transient (i.e., almost surely transient under all strategies) then many other objectives have a lower strategy complexity than in general MDPs. E.g., ε-optimal strategies for Safety and co-Büchi and optimal strategies for {0,1,2}-Parity (where they exist) can be chosen MD, even if the MDP is infinitely branching.

BibTeX - Entry

@InProceedings{kiefer_et_al:LIPIcs.CONCUR.2021.11,
  author =	{Kiefer, Stefan and Mayr, Richard and Shirmohammadi, Mahsa and Totzke, Patrick},
  title =	{{Transience in Countable MDPs}},
  booktitle =	{32nd International Conference on Concurrency Theory (CONCUR 2021)},
  pages =	{11:1--11:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-203-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{203},
  editor =	{Haddad, Serge and Varacca, Daniele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14388},
  URN =		{urn:nbn:de:0030-drops-143881},
  doi =		{10.4230/LIPIcs.CONCUR.2021.11},
  annote =	{Keywords: Markov decision processes, Parity, Transience}
}

Keywords: Markov decision processes, Parity, Transience
Collection: 32nd International Conference on Concurrency Theory (CONCUR 2021)
Issue Date: 2021
Date of publication: 13.08.2021

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