TY - JOUR
T1 - Polynomial Time Algorithms for Branching Markov Decision Processes and Probabilistic Min(Max) Polynomial Bellman Equations
AU - Etessami, Kousha
AU - Stewart, Alistair
AU - Yannakakis, Mihalis
PY - 2020/2/28
Y1 - 2020/2/28
N2 - We show that one can compute the least non-negative solution (a.k.a., least fixed point) for a system of probabilistic min (max) polynomial equations, to any desired accuracy > 0, in time polynomial in both the encoding size of the system and in log(1=). These are Bellman optimality equations for important classes of infinite-state Markov Decision Processes (MDPs), including Branching MDPs (BMDPs), which generalize classic multitype branching stochastic processes. We thus obtain the first polynomial time algorithm for computing, to any desired precision, optimal (maximum and minimum) extinction probabilities for BMDPs. Our algorithms are based on a novel generalization of Newton’s method which employs linear programming in each iteration.We also provide P-time algorithms for computing an ε-optimal policy for both maximizing and minimizing extinction probabilities in a BMDP, whereas we note a hardness result for computing an exact optimal policy. Furthermore, improving on prior results, we provide more efficient P-time algorithms for qualitative analysis of BMDPs, i.e., for determining whether the maximum or minimum extinction probability is 1, and, if so, computing a policy that achieves this. We also observe some complexity consequences of our results for branching simple stochastic games, which generalize BMDPs.
AB - We show that one can compute the least non-negative solution (a.k.a., least fixed point) for a system of probabilistic min (max) polynomial equations, to any desired accuracy > 0, in time polynomial in both the encoding size of the system and in log(1=). These are Bellman optimality equations for important classes of infinite-state Markov Decision Processes (MDPs), including Branching MDPs (BMDPs), which generalize classic multitype branching stochastic processes. We thus obtain the first polynomial time algorithm for computing, to any desired precision, optimal (maximum and minimum) extinction probabilities for BMDPs. Our algorithms are based on a novel generalization of Newton’s method which employs linear programming in each iteration.We also provide P-time algorithms for computing an ε-optimal policy for both maximizing and minimizing extinction probabilities in a BMDP, whereas we note a hardness result for computing an exact optimal policy. Furthermore, improving on prior results, we provide more efficient P-time algorithms for qualitative analysis of BMDPs, i.e., for determining whether the maximum or minimum extinction probability is 1, and, if so, computing a policy that achieves this. We also observe some complexity consequences of our results for branching simple stochastic games, which generalize BMDPs.
U2 - 10.1287/moor.2018.0970
DO - 10.1287/moor.2018.0970
M3 - Article
SN - 0364-765X
VL - 45
SP - 34
EP - 62
JO - Mathematics of Operations Research
JF - Mathematics of Operations Research
IS - 1
ER -