Markov Decision Processes with Sure Parity and Multiple Reachability Objectives
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909277973643264 |
|---|---|
| author | Berthon, Raphaël Katoen, Joost-Pieter Winkler, Tobias |
| author_facet | Berthon, Raphaël Katoen, Joost-Pieter Winkler, Tobias |
| contents | This paper considers the problem of finding strategies that satisfy a mixture of sure and threshold objectives in Markov decision processes. We focus on a single $ω$-regular objective expressed as parity that must be surely met while satisfying $n$ reachability objectives towards sink states with some probability thresholds too. We consider three variants of the problem: (a) strict and (b) non-strict thresholds on all reachability objectives, and (c) maximizing the thresholds with respect to a lexicographic order. We show that (a) and (c) can be reduced to solving parity games, and (b) can be solved in $\sf{EXPTIME}$. Strategy complexities as well as algorithms are provided for all cases. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_01212 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Markov Decision Processes with Sure Parity and Multiple Reachability Objectives Berthon, Raphaël Katoen, Joost-Pieter Winkler, Tobias Computer Science and Game Theory This paper considers the problem of finding strategies that satisfy a mixture of sure and threshold objectives in Markov decision processes. We focus on a single $ω$-regular objective expressed as parity that must be surely met while satisfying $n$ reachability objectives towards sink states with some probability thresholds too. We consider three variants of the problem: (a) strict and (b) non-strict thresholds on all reachability objectives, and (c) maximizing the thresholds with respect to a lexicographic order. We show that (a) and (c) can be reduced to solving parity games, and (b) can be solved in $\sf{EXPTIME}$. Strategy complexities as well as algorithms are provided for all cases. |
| title | Markov Decision Processes with Sure Parity and Multiple Reachability Objectives |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2408.01212 |