Partial and Conditional Expectations in Markov Decision Processes with Integer Weights
Publikation: Beitrag in Buch/Konferenzbericht/Sammelband/Gutachten › Beitrag in Konferenzband › Beigetragen › Begutachtung
Beitragende
Abstract
The paper addresses two variants of the stochastic shortest path problem (“optimize the accumulated weight until reaching a goal state”) in Markov decision processes (MDPs) with integer weights. The first variant optimizes partial expected accumulated weights, where paths not leading to a goal state are assigned weight 0, while the second variant considers conditional expected accumulated weights, where the probability mass is redistributed to paths reaching the goal. Both variants constitute useful approaches to the analysis of systems without guarantees on the occurrence of an event of interest (reaching a goal state), but have only been studied in structures with non-negative weights. Our main results are as follows. There are polynomial-time algorithms to check the finiteness of the supremum of the partial or conditional expectations in MDPs with arbitrary integer weights. If finite, then optimal weight-based deterministic schedulers exist. In contrast to the setting of non-negative weights, optimal schedulers can need infinite memory and their value can be irrational. However, the optimal value can be approximated up to an absolute error of ϵ in time exponential in the size of the MDP and polynomial in log(1/ϵ).
Details
Originalsprache | Englisch |
---|---|
Titel | Foundations of Software Science and Computation Structures |
Redakteure/-innen | Mikołaj Bojańczyk, Alex Simpson |
Herausgeber (Verlag) | Springer, Berlin [u. a.] |
Seiten | 436–452 |
ISBN (Print) | 978-3-030-17126-1 |
Publikationsstatus | Veröffentlicht - 2019 |
Peer-Review-Status | Ja |
Publikationsreihe
Reihe | Lecture Notes in Computer Science, Volume 11425 |
---|---|
ISSN | 0302-9743 |
Konferenz
Titel | Foundations of Software Science and Computation Structures 2019 |
---|---|
Kurztitel | FoSSaCS’19 |
Veranstaltungsnummer | |
Dauer | 6 - 11 April 2019 |
Webseite | |
Bekanntheitsgrad | Internationale Veranstaltung |
Ort | |
Stadt | Prag |
Land | Tschechische Republik |
Externe IDs
ORCID | /0000-0002-5321-9343/work/142236714 |
---|---|
Scopus | 85064910623 |
ORCID | /0000-0003-4829-0476/work/165453936 |
Schlagworte
Schlagwörter
- partial and conditional expectations, Markov cecision processes, integer weights