Analysis of Recursive Markov Chains, Recursive Markov Decision Processes, and Recursive Stochastic Games

Kousha Etessami
Laboratory for Foundations of Computer Science, School of Informatics, University of Edinburgh
Friday, 14 April, 2006 (All day)

Recursive Markov Chains (RMCs) are a natural abstract model of procedural probabilistic programs and other systems involving both recursion and probability. RMCs define a class of denumerable Markov chains with a rich theory generalizing that of multi-type Branching (stochastic) Processes and Stochastic Context-Free Grammars, and they are tightly related to probabilistic Pushdown Systems. Recursive Markov Decision Processes (RMDPs) and Recursive Stochastic Games (RSGs) extend RMCs with a controller and two adversarial players, respectively.

In a series of recent papers we have studied central algorithmic analysis and verification questions for RMCs, RMDPs, and RSGs, providing some strong upper and lower bounds on the complexity of key algorithmic problems.

I will provide a broad survey of this work, indicate some of the main techniques involved in our analyses, discuss potential application domains, and indicate some of the many directions for future research.

This talk describes joint work with Mihalis Yannakakis (Columbia U.) contained in a series of recent papers that appear at: STACS'05, TACAS'05, ICALP'05, QEST'05, and STACS'06, and in a submitted paper.