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.60085
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^\ast \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 non-reachability objectives. We show how to compute the GFP of max/minPPSs to desired precision in P-time.
We also study more general branching simple stochastic games (BSSGs) with (non-)reachability objectives. We show that: (1) the value of these games is captured by the GFP, \(g^\ast\), of a corresponding max-minPPS, \(x = P(x)\); (2) the quantitative problem of approximating the value is in TFNP; and (3) the qualitative problems associated with the value are all solvable in P-time.
60J80 Branching processes (Galton-Watson, birth-and-death, etc.)
Full Text: DOI
[1] Bozic, Evolutionary dynamics of cancer in response to targeted combination therapy, eLife, 2, (2013)
[2] Bonnet, R.; Kiefer, S.; Lin, A. W., Analysis of probabilistic basic parallel processes, (Proc. of FoSSaCS’14, (2014)), 43-57 · Zbl 1405.68208
[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
[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
[5] Chatterjee, K.; Henzinger, M., Efficient and dynamic algorithms for alternating Büchi games and maximal end-component decomposition, J. ACM, 61, 3, (2014), pp. 1-40 · Zbl 1295.91019
[6] Chen, T.; Dräger, K.; Kiefer, S., Model checking stochastic branching processes, (Proc. of MFCS’12, LNCS, vol. 7464, (2012), Springer), 271-282 · Zbl 1365.68320
[7] Courcoubetis, C.; Yannakakis, M., Markov decision processes and regular events, IEEE Trans. Autom. Control, 43, 10, 1399-1418, (1998) · Zbl 0954.90061
[8] Denardo, E.; Rothblum, U., Totally expanding multiplicative systems, Linear Algebra Appl., 406, 142-158, (2005) · Zbl 1078.15017
[9] Esparza, J.; Gawlitza, T.; Kiefer, S.; Seidl, H., Approximative methods for monotone systems of MIN-MAX-polynomial equations, (Proc. of 35th ICALP (1), (2008)), 698-710 · Zbl 1153.65337
[10] Esparza, J.; Kučera, A.; Mayr, R., Model checking probabilistic pushdown automata, Log. Methods Comput. Sci., 2, 1, 1-31, (2006) · Zbl 1126.68053
[11] Etessami, K.; Stewart, A.; Yannakakis, M., Polynomial-time algorithms for multi-type branching processes and stochastic context-free grammars, (Proc. 44th ACM Symposium on Theory of Computing (STOC), (2012)), (*version 2*), available at: · Zbl 1286.68188
[12] Etessami, K.; Stewart, A.; Yannakakis, M., Polynomial-time algorithms for branching Markov decision processes, and probabilistic MIN(MAX) polynomial Bellman equations, (Proc. 39th Int. Coll. on Automata, Languages and Programming (ICALP), (2012)), (*version 2*), available at: · Zbl 1272.68458
[13] Etessami, K.; Wojtczak, D.; Yannakakis, M., Recursive stochastic games with positive rewards, (Proc. of 35th ICALP (1), LNCS, vol. 5125, (2008), Springer), 711-723, See full tech report at · Zbl 1153.91328
[14] Etessami, K.; Yannakakis, M., Recursive Markov decision processes and recursive stochastic games, J. ACM, 62, 2, 1-69, (2015) · Zbl 1333.91005
[15] Etessami, K.; Yannakakis, M., Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations, J. ACM, 56, 1, (2009) · Zbl 1325.68091
[16] Harris, T. E., The theory of branching processes, (1963), Springer-Verlag · Zbl 0117.13002
[17] Horn, R. A.; Johnson, C. R., Matrix analysis, (1985), Cambridge U. Press · Zbl 0576.15001
[18] Komarova, N. L.; Boland, C. R., Cancer: calculated treatment, Nature, 499, 291-292, (2003), (News and Views article.)
[19] Pliska, S., Optimization of multitype branching processes, Manag. Sci., 23, 2, 117-124, (1976/77) · Zbl 0345.90043
[20] Reiter, G.; Bozic, I.; Chatterjee, K.; Nowak, M. A., TTP: tool for tumor progression, (Proc. of CAV’2013, LNCS, vol. 8044, (2013), Springer), 101-106
[21] Rothblum, U.; Whittle, P., Growth optimality for branching Markov decision chains, Math. Oper. Res., 7, 4, 582-601, (1982) · Zbl 0498.90082
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.