Transience in Countable MDPs

Stefan Kiefer; Richard Mayr; Mahsa Shirmohammadi; Patrick Totzke

doi:10.4230/LIPIcs.CONCUR.2021.11

Transience in Countable MDPs

Stefan Kiefer, Richard Mayr, Mahsa Shirmohammadi, Patrick Totzke

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English
Title of host publication	32nd International Conference on Concurrency Theory (CONCUR 2021)
Editors	Serge Haddad, Daniele Varacca
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages	11:1-11:15
Number of pages	15
ISBN (Electronic)	978-3-95977-203-7
DOIs	https://doi.org/10.4230/LIPIcs.CONCUR.2021.11
Publication status	Published - 13 Aug 2021
Event	32nd International Conference on Concurrency Theory - Online, Paris, France Duration: 23 Aug 2021 → 27 Aug 2021 https://qonfest2021.lacl.fr/concur21.php

Publication series

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

Conference

Conference	32nd International Conference on Concurrency Theory
Abbreviated title	CONCUR 2021
Country/Territory	France
City	Paris
Period	23/08/21 → 27/08/21
Internet address	https://qonfest2021.lacl.fr/concur21.php

Keywords

Markov decision processes
Parity
Transience

Access to Document

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

Transcience in Countable MDPs_KIEFER_DOA14072021_VOR_CC-BYFinal published version, 828 KBLicence: Creative Commons: Attribution (CC-BY)

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

Cite this

Kiefer, S., Mayr, R., Shirmohammadi, M., & Totzke, P. (2021). Transience in Countable MDPs. In S. Haddad, & D. Varacca (Eds.), 32nd International Conference on Concurrency Theory (CONCUR 2021) (pp. 11:1-11:15). (LIPIcs - Leibniz International Proceedings in Informatics; Vol. 203). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.CONCUR.2021.11

@inproceedings{e7ebd4acce754c08b5a7a527a2b5e34c,

title = "Transience in Countable MDPs",

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{\"u}chi and optimal strategies for {0,1,2}-Parity (where they exist) can be chosen MD, even if the MDP is infinitely branching. ",

keywords = "Markov decision processes, Parity, Transience",

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

year = "2021",

month = aug,

day = "13",

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

language = "English",

series = "LIPIcs - Leibniz International Proceedings in Informatics",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

pages = "11:1--11:15",

editor = "Serge Haddad and Daniele Varacca",

booktitle = "32nd International Conference on Concurrency Theory (CONCUR 2021)",

note = "32nd International Conference on Concurrency Theory, CONCUR 2021 ; Conference date: 23-08-2021 Through 27-08-2021",

url = "https://qonfest2021.lacl.fr/concur21.php",

}

Kiefer, S, Mayr, R, Shirmohammadi, M & Totzke, P 2021, Transience in Countable MDPs. in S Haddad & D Varacca (eds), 32nd International Conference on Concurrency Theory (CONCUR 2021). LIPIcs - Leibniz International Proceedings in Informatics, vol. 203, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 11:1-11:15, 32nd International Conference on Concurrency Theory, Paris, France, 23/08/21. https://doi.org/10.4230/LIPIcs.CONCUR.2021.11

Transience in Countable MDPs. / Kiefer, Stefan; Mayr, Richard; Shirmohammadi, Mahsa et al.

32nd International Conference on Concurrency Theory (CONCUR 2021). ed. / Serge Haddad; Daniele Varacca. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. p. 11:1-11:15 (LIPIcs - Leibniz International Proceedings in Informatics; Vol. 203).

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

TY - GEN

T1 - Transience in Countable MDPs

AU - Kiefer, Stefan

AU - Mayr, Richard

AU - Shirmohammadi, Mahsa

AU - Totzke, Patrick

PY - 2021/8/13

Y1 - 2021/8/13

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

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

KW - Markov decision processes

KW - Parity

KW - Transience

U2 - 10.4230/LIPIcs.CONCUR.2021.11

DO - 10.4230/LIPIcs.CONCUR.2021.11

M3 - Conference contribution

T3 - LIPIcs - Leibniz International Proceedings in Informatics

SP - 11:1-11:15

BT - 32nd International Conference on Concurrency Theory (CONCUR 2021)

A2 - Haddad, Serge

A2 - Varacca, Daniele

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

T2 - 32nd International Conference on Concurrency Theory

Y2 - 23 August 2021 through 27 August 2021

ER -

Transience in Countable MDPs

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this