zbMATH — the first resource for mathematics

Polynomial time algorithms for branching Markov decision processes and probabilistic min(max) polynomial Bellman equations. (English) Zbl 1272.68458
Czumaj, Artur (ed.) et al., Automata, languages, and programming. 39th international colloquium, ICALP 2012, Warwick, UK, July 9–13, 2012. Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-31593-0/pbk). Lecture Notes in Computer Science 7391, 314-326 (2012).
Summary: We show that one can approximate the least fixed-point solution for a multivariate system of monotone probabilistic max (min) polynomial equations, in time polynomial in both the encoding size of the system of equations and in \(\log (\frac{1}{\varepsilon})\), where \(\varepsilon > 0\) is the desired additive error bound of the solution. (The model of computation is the standard Turing machine model.)
These equations form the Bellman optimality equations for several important classes of infinite-state Markov decision processes (MDPs). Thus, as a corollary, we obtain the first polynomial time algorithms for computing to within arbitrary desired precision the optimal value vector for several classes of infinite-state MDPs which arise as extensions of classic, and heavily studied, purely stochastic processes. These include both the problem of maximizing and minimizing the termination (extinction) probability of multi-type branching MDPs, stochastic context-free MDPs, and 1-exit Recursive MDPs. We also show that we can compute in P-time an \(\varepsilon \)-optimal policy for any given desired \(\varepsilon > 0\).
For the entire collection see [Zbl 1268.68011].

68W25 Approximation algorithms
68Q25 Analysis of algorithms and problem complexity
68Q87 Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
90C40 Markov and semi-Markov decision processes
Full Text: DOI