Algorithms for Branching Markov Decision Processes and Branching Stochastic Games

Multi-type branching processes (BPs) are classic stochastic processes, with many applications in different fields.  They describe a random process that generates a node-labeled, possibly infinite, tree.Branching Markov decision processes (BMDPs) extend BPs with a controller.  Two key objectives for BMDPs are to optimize (maximize or minimize) the probability of extinction, i.e., the probability that the generated tree is finite, and the probability of reaching a target type, i.e., the probability that the generated tree contains a given node label. We give polynomial time algorithms for computing these quantities. Our algorithms solve certain min/max probabilistic polynomial systems of equations (max/minPPSs), which form Bellman optimality equations for these models. It turns out that the least (respectively, greatest) fixed point solution of the corresponding max/minPPSs gives the optimal extinction (respectively, non-reachability) probabilities. These vector values are in general irrational. We give P-time algorithms for computing these quantities to desired accuracy epsilon > 0, and for computing epsilon-optimal policies (strategies) for them.  Our algorithms involve, crucially, a novel generalization of Newton's method that uses linear programming in each iteration. We also study branching (simple) stochastic games, a 2-player extension of BMDPs, and we derive algorithms and complexity results for them. (Joint work with Alistair Stewart and Mihalis Yannakakis.)