ORIE Colloquium on 11/29/2011 - John Birge: Monte Carlo and Bayesian Methods for Stochastic Dynamic Programs

Standard approaches to solving stochastic dynamic programs suffer from the curse of dimensionality. Taking advantage of structural properties such as convexity can help reduce the effect of dimension for certain problems, but the dimensionality effect often persists. An alternative is to consider methods based on Markov chain Monte Carlo (MCMC) and Bayesian approaches including particle filters and expectation-maximization (EM) methods. This talk will discuss these approaches and give a few general results including: the consistency of MCMC with fixed particle sizes when estimates are unbiased, equivalences to the Kalman filter for linear-quadratic Gaussian models, equivalence of MCMC to value iteration and of EM to policy iteration for infinite horizon models, related convergence implications, and equivalent representations to Gaussian mixtures for general classes of objectives.