Stochastic Shortest Paths and Weight-Bounded Properties in Markov Decision Processes

Christel BaierChristel Baier, Nathalie BertrandNathalie Bertrand, Clemens DubslaffClemens Dubslaff, Daniel GburekDaniel Gburek, Ocan SankurOcan Sankur

DOI Link

Christel Baier, Nathalie Bertrand, Clemens Dubslaff, Daniel Gburek, Ocan Sankur
Stochastic Shortest Paths and Weight-Bounded Properties in Markov Decision Processes
Proc. of 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 86--94, 2018. ACM

Details
Bibtex

KurzfassungAbstract
The paper deals with finite-state Markov decision processes (MDPs) with integer weights assigned to each state-action pair. New algorithms are presented to classify end components according to their limiting behavior with respect to the accumulated weights. These algorithms are used to provide solutions for two types of fundamental problems for integer-weighted MDPs. First, a polynomial-time algorithm for the classical stochastic shortest path problem is presented, generalizing known results for special classes of weighted MDPs. Second, qualitative probability constraints for weight-bounded (repeated) reachability conditions are addressed. Among others, it is shown that the problem to decide whether a disjunction of weight-bounded reachability conditions holds almost surely under some scheduler belongs to NP ∩ coNP, is solvable in pseudo-polynomial time and is at least as hard as solving two-player mean-payoff games, while the corresponding problem for universal quantification over schedulers is solvable in polynomial time.
Forschungsgruppe:Research Group: Algebraische und logische Grundlagen der InformatikAlgebraic and Logical Foundations of Computer Science

@inproceedings{BBDGS2018,
  author    = {Christel Baier and Nathalie Bertrand and Clemens Dubslaff and
               Daniel Gburek and Ocan Sankur},
  title     = {Stochastic Shortest Paths and Weight-Bounded Properties in Markov
               Decision Processes},
  booktitle = {Proc. of 33rd Annual {ACM/IEEE} Symposium on Logic in Computer
               Science (LICS)},
  publisher = {ACM},
  year      = {2018},
  pages     = {86--94},
  doi       = {10.1145/3209108.3209184}
}