Invited Talk

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

Kousha Etessami

University of Edinburgh

Abstract

Recursive Markov Chains (RMCs) ([Etessami-Yannakakis'05a]) are a natural abstract model of procedural probabilistic programs and related systems involving 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 are intimately related to probabilistic Pushdown Systems. Recursive Markov Decision Processes (RMDPs) and Recursive Simple Stochastic Games (RSSGs) extend RMCs with a controller and two adversarial players, respectively. In a series of recent papers, we have studied central algorithmic analysis and model checking questions for RMCs, RMDPs, and RSSGs, providing some strong upper and lower bounds on the complexity of key problems. In this talk I will provide a survey of this work, indicate some of the main techniques involved in our analyses, and indicate some of the many directions for future research.

This talk describes joint work with Mihalis Yannakakis (Columbia U.).