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

Kousha Etessami, Alistair Stewart, Mihalis Yannakakis

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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(1/ ε ), where ε > 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 ε-optimal policy for any given desired ε > 0.
Original languageEnglish
Title of host publicationAutomata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part I
Subtitle of host publication39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part I
EditorsArtur Czumaj, Kurt Mehlhorn, Andrew Pitts, Roger Wattenhofer
PublisherSpringer Berlin Heidelberg
Pages314-326
Number of pages41
Volume7391
ISBN (Electronic)978-3-642-31594-7
ISBN (Print)978-3-642-31593-0
DOIs
Publication statusPublished - 2012

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin / Heidelberg
Volume7391
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Fingerprint Dive into the research topics of 'Polynomial Time Algorithms for Branching Markov Decision Processes and Probabilistic Min(Max) Polynomial Bellman Equations'. Together they form a unique fingerprint.

Cite this