Maximizing the Conditional Expected Reward for Reaching the Goal

Christel BaierChristel Baier, Joachim KleinJoachim Klein, Sascha KlüppelholzSascha Klüppelholz, Sascha WunderlichSascha Wunderlich

DOI Link

Christel Baier, Joachim Klein, Sascha Klüppelholz, Sascha Wunderlich
Maximizing the Conditional Expected Reward for Reaching the Goal
Proc. of the 23rd International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS), Part II, volume 10206 of Lecture Notes in Computer Science, 269--285, 2017. Springer

Details
Bibtex

KurzfassungAbstract
The paper addresses the problem of computing maximal conditional expected accumulated rewards until reaching a target state (briefly called maximal conditional expectations) in finite-state Markov decision processes where the condition is given as a reachability constraint. Conditional expectations of this type can, e.g., stand for the maximal expected termination time of probabilistic programs with non-determinism, under the condition that the program eventually terminates, or for the worst-case expected penalty to be paid, assuming that at least three deadlines are missed. The main results of the paper are (i) a polynomial-time algorithm to check the finiteness of maximal conditional expectations, (ii) PSPACE-completeness for the threshold problem in acyclic Markov decision processes where the task is to check whether the maximal conditional expectation exceeds a given threshold, (iii) a pseudo-polynomial-time algorithm for the threshold problem in the general (cyclic) case, and (iv) an exponential-time algorithm for computing the maximal conditional expectation and an optimal scheduler.
Forschungsgruppe:Research Group: Algebraische und logische Grundlagen der InformatikAlgebraic and Logical Foundations of Computer Science

The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-662-54580-5_16.

@inproceedings{BKKW2017,
  author    = {Christel Baier and Joachim Klein and Sascha Kl{\"{u}}ppelholz and
               Sascha Wunderlich},
  title     = {Maximizing the Conditional Expected Reward for Reaching the Goal},
  booktitle = {Proc. of the 23rd International Conference on Tools and
               Algorithms for the Construction and Analysis of Systems (TACAS),
               Part {II}},
  series    = {Lecture Notes in Computer Science},
  volume    = {10206},
  publisher = {Springer},
  year      = {2017},
  pages     = {269--285},
  doi       = {10.1007/978-3-662-54580-5_16}
}