Kousha Etessami (Informatics, University of Edinburgh)

Adding recursion to Markov chains, Markov decision processes, and stochastic games: algorithms and complexity
Joint work with Mihalis Yannakakis (Columbia University).
Wednesday 13 October 2010 at 15.30, JCMB 6206

Abstract

I will decribe a family of finitely presented, but infinite-state, stochastic models and stochastic games that arise by adding a natural recursion feature to Markov Chains, Markov decision processes, and stochastic games. I will describe some algorithms for analysing such models, and I will discuss the computational complexity of key analysis problems.

These recursive models subsume a number of classic and heavily studied stochastic processes, including (multi-type) branching processes, (quasi-)-birth-death processes, stochastic context-free grammars, and various others. They also provide a natural abstract model of probabilistic procedural programs with recursion.

The algorithmic theory and computational complexity of analyzing these models has turned out to be a very rich subject, with connections to a number of areas of research. In particular, a key role is played in their analysis by fixed point computation and approximation problems for algebraically defined monotone functions over basis {+, *, max, min}, and there are connections to some long standing open problems in numerical computation. Newton's method and its variants play a key role in numerical algorithms for their analysis. There are also connections to the computation and approximation of Nash Equilibria in n-player (n > 2) strategic-form games.

I will survey highlights from our work on these recursive stochastic models and stochastic games. Many open questions remain. I will highlight a few open problems.

Seminars by year

Current 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996