Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1007/978-3-662-54580-5_16 | TACAS |
DocType | Volume | ISSN |
Conference | abs/1701.05389 | 0302-9743 |
Citations | PageRank | References |
5 | 0.38 | 23 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Christel Baier | 1 | 3053 | 185.85 |
| Joachim Klein | 2 | 118 | 9.33 |
| Sascha Klüppelholz | 3 | 287 | 20.48 |
| Sascha Wunderlich | 4 | 43 | 3.43 |