Polynomial time algorithms for Branching Markov (Decision) Processes

Date: Thursday, June 6, 2013
Speaker: Alistair Stewart

We give polynomial-time algorithms for approximating the extinction probability of multi-type branching processes, and the optimal extinction probability for branching markov decision processes, where the controller is trying to either maximize or minimize the extinction probability. That is, we can approximate these probabilities to within ϵ > 0, in time polynomial in log(1/ϵ) and the encoding size of the model.

Branching processes (BPs) are a classic family of stochastic processes, with applications in several fields (including population biology and nuclear physics). Branching Markov Decision Processes(BMDPs) are a generalization of multi-type BPs, and form a family of infinite-state MDPs.

These models give rise to systems of equations – a system of probabilistic polynomials for BPs, and a system of (Bellman) equations containing max or min, as well as probabilistic polynomials, for BMDPs. Computing their optimal extinction probabilities is equivalent to computing the least fixed-point solution of the corresponding equations. We also consider some applications of these results to stochastic context-free grammars.

Posted in RiSE Seminar