Markov Decision Processes with Sure Parity and Multiple Reachability Objectives
<|reference_start|>Markov Decision Processes with Sure Parity and Multiple Reachability Objectives: 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 $\omega$-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.<|reference_end|>
@article{berthon2024markov,
    title={Markov Decision Processes with Sure Parity and Multiple Reachability
  Objectives},
    author={Rapha"el Berthon, Joost-Pieter Katoen, Tobias Winkler},
    journal={arXiv preprint arXiv:2408.01212},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.01212},
    primaryClass={cs.GT}
}