Projects per year
Abstract / Description of output
We give polynomial time algorithms for quantitative (and qualitative) reachability analysis for Branching Markov Decision Processes (BMDPs). Specifically, given a BMDP, and given an initial population, where the objective of the controller is to maximize (or minimize) the probability of eventually reaching a population that contains an object of a desired (or undesired) type, we give algorithms for approximating the supremum (infimum) reachability probability, within desired precision epsilon > 0, in time polynomial in the encoding size of the BMDP and in log(1/epsilon). We furthermore give Ptime algorithms for computing epsilonoptimal strategies for both maximization and minimization of reachability probabilities. We also give Ptime algorithms for all associated qualitative analysis problems, namely: deciding whether the optimal (supremum or infimum) reachability probabilities are 0 or 1. Prior to this paper, approximation of optimal reachability probabilities for BMDPs was not even known to be decidable.
Our algorithms exploit the following basic fact: we show that for any BMDP, its maximum (minimum) nonreachability probabilities are given by the greatest fixed point (GFP) solution g* in [0,1]^n of a corresponding monotone max (min) Probabilistic Polynomial System of equations (max/minPPS), x=P(x), which are the Bellman optimality equations for a BMDP with nonreachability objectives. We show how to compute the GFP of max/min PPSs to desired precision in Ptime.
Our algorithms exploit the following basic fact: we show that for any BMDP, its maximum (minimum) nonreachability probabilities are given by the greatest fixed point (GFP) solution g* in [0,1]^n of a corresponding monotone max (min) Probabilistic Polynomial System of equations (max/minPPS), x=P(x), which are the Bellman optimality equations for a BMDP with nonreachability objectives. We show how to compute the GFP of max/min PPSs to desired precision in Ptime.
Original language  English 

Title of host publication  Automata, Languages, and Programming 
Subtitle of host publication  42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 610, 2015, Proceedings, Part II 
Publisher  Springer 
Number of pages  12 
ISBN (Electronic)  9783662476666 
ISBN (Print)  9783662476659 
DOIs  
Publication status  Published  2015 
Fingerprint
Dive into the research topics of 'Greatest Fixed Points of Probabilistic Min/Max Polynomial Equations, and Reachability for Branching Markov Decision Processes?'. Together they form a unique fingerprint.Projects
 1 Finished

Sublinear Algorithms for Approximating Probability Distribution
Diakonikolas, I.
1/09/14 → 31/08/15
Project: Research