*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
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.
