Transience in Countable MDPs

Stefan Kiefer, Richard Mayr, Mahsa Shirmohammadi, Patrick Totzke

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The Transience objective is not to visit any state infinitely often. While this is not possible in 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.
Original languageEnglish
Title of host publicationProceedings of the 32nd International Conference on Concurrency Theory
Number of pages34
Volume203
Publication statusAccepted/In press - 14 Jul 2021
Event32nd International Conference on Concurrency Theory - Online, Paris, France
Duration: 23 Aug 202127 Aug 2021
https://qonfest2021.lacl.fr/concur21.php

Publication series

NameLIPIcs - Leibniz International Proceedings in Informatics

Conference

Conference32nd International Conference on Concurrency Theory
Abbreviated titleCONCUR 2021
Country/TerritoryFrance
CityParis
Period23/08/2127/08/21
Internet address

Keywords

  • Markov decision processes
  • Parity
  • Transience

Fingerprint

Dive into the research topics of 'Transience in Countable MDPs'. Together they form a unique fingerprint.

Cite this