TITLE: Markov chain methods for analyzing algorithms

ABSTRACT:

We are interested in using Markov chain methods to establish convergence in probability for various algorithms in dynamic programming and optimization.  We start by investigating simple "empirical" variants of classical value and policy iteration for dynamic programming.  In this case, we show that the progress of these algorithms is stochastically dominated by an easy to analyze Markov chain, from which we can extract a convergence rate for the original algorithms.  We continue by showing that this same line of reasoning covers several empirical algorithms in optimization as well.  We argue that the advantage of this approach lies in its simplicity and intuitive appeal.