×

zbMATH — the first resource for mathematics

Greatest fixed points of probabilistic min/max polynomial equations, and reachability for branching Markov decision processes. (English) Zbl 1394.60084
Halldórsson, Magnús M. (ed.) et al., Automata, languages, and programming. 42nd international colloquium, ICALP 2015, Kyoto, Japan, July 6–10, 2015. Proceedings. Part II. Berlin: Springer (ISBN 978-3-662-47665-9/pbk; 978-3-662-47666-6/ebook). Lecture Notes in Computer Science 9135, 184-196 (2015).
Summary: 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 P-time algorithms for computing \(\epsilon \)-optimal strategies for both maximization and minimization of reachability probabilities. We also give P-time 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) non-reachability 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/min-PPS), \(x=P(x)\), which are the Bellman optimality equations for a BMDP with non-reachability objectives. We show how to compute the GFP of max/min PPSs to desired precision in P-time.
For the entire collection see [Zbl 1316.68013].

MSC:
60J80 Branching processes (Galton-Watson, birth-and-death, etc.)
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Bozic, I., et al.: Evolutionary dynamics of cancer in response to targeted combination therapy. Elife 2, e00747 (2013) · doi:10.7554/eLife.00747
[2] Bonnet, R., Kiefer, S., Lin, A.W.: Analysis of probabilistic basic parallel processes. In: Muscholl, A. (ed.) FOSSACS 2014 (ETAPS). LNCS, vol. 8412, pp. 43-57. Springer, Heidelberg (2014) · Zbl 1405.68208 · doi:10.1007/978-3-642-54830-7_3
[3] Brázdil, T., Brozek, V., Kucera, A., Obdrzálek, J.: Qualitative reachability in stochastic BPA games. Inf. Comput. 209(8), 1160-1183 (2011) · Zbl 1237.91035 · doi:10.1016/j.ic.2011.02.002
[4] Brázdil, T., Brozek, V., Forejt, V., Kucera, A.: Reachability in recursive Markov decision processes. Inf. Comput. 206(5), 520-537 (2008) · Zbl 1145.91011 · doi:10.1016/j.ic.2007.09.002
[5] Chen, T., Dräger, K., Kiefer, S.: Model checking stochastic branching processes. In: Rovan, B., Sassone, V., Widmayer, P. (eds.) MFCS 2012. LNCS, vol. 7464, pp. 271-282. Springer, Heidelberg (2012) · Zbl 1365.68320 · doi:10.1007/978-3-642-32589-2_26
[6] Esparza, J., Gawlitza, T., Kiefer, S., Seidl, H.: Approximative methods for monotone systems of min-max-polynomial equations. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol. 5125, pp. 698-710. Springer, Heidelberg (2008) · Zbl 1153.65337 · doi:10.1007/978-3-540-70575-8_57
[7] Esparza, J., Kučera, A., Mayr, R.: Model checking probabilistic pushdown automata. Logical Methods in Computer Science 2(1), 1-31 (2006) · Zbl 1126.68053
[8] Etessami, K., Stewart, A., Yannakakis, M.: Polynomial-time algorithms for multi-type branching processes and stochastic context-free grammars. In: Proc. 44th ACM Symposium on Theory of Computing (STOC) (2012) · Zbl 1286.68188
[9] Etessami, K., Stewart, A., Yannakakis, M.: Polynomial time algorithms for branching markov decision processes and probabilistic min(max) polynomial bellman equations. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part I. LNCS, vol. 7391, pp. 314-326. Springer, Heidelberg (2012) · Zbl 1272.68458 · doi:10.1007/978-3-642-31594-7_27
[10] Full preprint of this paper (2015).
[11] Etessami, K., Wojtczak, D., Yannakakis, M.: Recursive stochastic games with positive rewards. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol. 5125, pp. 711-723. Springer, Heidelberg (2008) · Zbl 1153.91328 · doi:10.1007/978-3-540-70575-8_58
[12] Etessami, K., Yannakakis, M.: Recursive Markov decision processes and recursive stochastic games. Journal of the ACM (2015) · Zbl 1333.91005
[13] Etessami, K., Yannakakis, M.: Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations. Journal of the ACM 56(1) (2009) · Zbl 1325.68091
[14] Pliska, S.: Optimization of multitype branching processes. Management Sci., 23(2), 117-124 (1976/1977) · Zbl 0345.90043
[15] Reiter, J.G., Bozic, I., Chatterjee, K., Nowak, M.A.: · Zbl 06233028 · doi:10.1007/978-3-642-39799-8_6
[16] Rothblum, U., Whittle, P.: Growth optimality for branching Markov decision chains. Math. Oper. Res. 7(4), 582-601 (1982) · Zbl 0498.90082 · doi:10.1287/moor.7.4.582
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.