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 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996