Polynomial Time Algorithms for Branching Markov Decision Processes and Probabilistic Min(Max) Polynomial Bellman Equations

References

• [1] Allender E, Bürgisser P, Kjeldgaard-Pedersen J, Miltersen PB (2009) On the complexity of numerical analysis. SIAM J. Comput. 38(5):1987–2006.Crossref, Google Scholar
• [2] Brázdil T, Brozek V, Etessami K, Kucera A (2011) Approximating the termination value of one-counter MDPs and stochastic games. Proc. 38th Internat. Colloquium Automata, Languages and Programming, Lecture Notes in Computer Science, vol. 6756 (Springer, New York), 332–343.Crossref, Google Scholar
• [3] Brázdil T, Brozek V, Forejt V, Kucera A (2008) Reachability in recursive Markov decision processes. Inform. Comput. 206(5):520–537.Crossref, Google Scholar
• [4] Condon A (1992) The complexity of stochastic games. Inform. Comput. 96(2):203–224.Crossref, Google Scholar
• [5] Courcoubetis C, Yannakakis M (1998) Markov decision processes and regular events. IEEE Trans. Automatic Control 43(10):1399–1418.Crossref, Google Scholar
• [6] Denardo E, Rothblum U (2005) Totally expanding multiplicative systems. Linear Algebra Appl. 406:142–158.Crossref, Google Scholar
• [7] Esparza J, Kiefer S, Luttenberger M (2010) Computing the least fixed point of positive polynomial systems. SIAM J. Comput. 39(6):2282–2355.Crossref, Google Scholar
• [8] Esparza J, Kučera A, Mayr R (2006) Model checking probabilistic pushdown automata. Logical Methods Comput. Sci. 2(1):1–31.Google Scholar
• [9] Esparza J, Gawlitza T, Kiefer S, Seidl H (2008) Approximative methods for monotone systems of min-max-polynomial equations. Proc. 35th Internat. Colloquium Automata, Languages and Programming, Lecture Notes in Computer Science, vol. 5125 (Springer, New York), 698–710.Crossref, Google Scholar
• [10] Etessami K, Yannakakis M (2009) Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations. J. ACM 56(1):1–66.Crossref, Google Scholar
• [11] Etessami K, Yannakakis M (2015) Recursive Markov decision processes and recursive stochastic games. J. ACM 62(2):1–69.Crossref, Google Scholar
• [12] Etessami K, Stewart A, Yannakakis M (2012) Polynomial-time algorithms for multi-type branching processes and stochastic context-free grammars. Proc. 44th ACM Sympos. Theory Comput. (ACM, New York).Google Scholar
• [13] Etessami K, Stewart A, Yannakakis M (2012) Polynomial-time algorithms for branching Markov decision processes, and probabilistic min(max) polynomial Bellman equations. Proc. 39th Internat. Colloquium Automata, Languages and Programming, Lecture Notes in Computer Science, vol. 7391 (Springer, New York).Crossref, Google Scholar
• [14] Etessami K, Stewart A, Yannakakis M (2015) Greatest fixed points of probabilistic min/max polynomial equations, and reachability for branching Markov decision processes. Proc. 42nd Internat. Colloquium Automata, Languages Programming, Lecture Notes in Computer Science, vol. 9135 (Springer, New York).Crossref, Google Scholar
• [15] Etessami K, Stewart A, Yannakakis M (2017) A polynomial-time algorithm for computing extinction probabilities of multi-type branching processes. SIAM J. Comput. 46(5):1515–1553.Crossref, Google Scholar
• [16] Etessami K, Wojtczak D, Yannakakis M (2008) Recursive stochastic games with positive rewards. Aceto L, Damgård I, Goldberg LA, Halldórsson MM, Ingólfsdóttir A, Walukiewicz I, eds. Automata, Languages and Programming, Lecture Notes in Computer Science, vol. 5125 (Springer, Berlin), 711–723.Crossref, Google Scholar
• [17] Etessami K, Wojtczak D, Yannakakis M (2010) Quasi-birth–death processes, tree-like QBDs, probabilistic 1-counter automata, and pushdown systems. Performance Evaluation 67(9):837–857.Crossref, Google Scholar
• [18] Feinberg E, Shwartz A, eds. (2002) Handbook of Markov Decision Processes: Methods and Applications (Springer, New York).Crossref, Google Scholar
• [19] Haccou P, Jagers P, Vatutin VA (2005) Branching Processes: Variation, Growth, and Extinction of Populations (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [20] Harris TE (1963) The Theory of Branching Processes (Springer-Verlag, Berlin).Crossref, Google Scholar
• [21] Horn RA, Johnson CR (1985) Matrix Analysis (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [22] Kimmel M, Axelrod DE (2002) Branching Processes in Biology (Springer, New York).Crossref, Google Scholar
• [23] Kolmogorov AN, Sevastyanov BA (1947) The calculation of final probabilities for branching random processes [in Russian]. Doklady 56:783–786.Google Scholar
• [24] Pliska S (1976/77) Optimization of multitype branching processes. Management Sci. 23(2):117–124.Link, Google Scholar
• [25] Puterman ML (1994) Markov Decision Processes (Wiley, Hoboken, NJ).Crossref, Google Scholar
• [26] Rothblum U, Whittle P (1982) Growth optimality for branching Markov decision chains. Math. Oper. Res. 7(4):582–601.Link, Google Scholar
• [27] Stewart A, Etessami K, Yannakakis M (2015) Upper bounds for Newton’s method on monotone polynomial systems, and P-time model checking of probabilistic one-counter automata. J. ACM 62(4):1–33.Crossref, Google Scholar