DOS Seminar- William B. Haskell

Primary tabs

TITLE: Markov chain methods for analyzing algorithms


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.



  • Workflow Status: Published
  • Created By: nhendricks6
  • Created: 09/20/2017
  • Modified By: nhendricks6
  • Modified: 09/20/2017


No categories were selected.


No keywords were submitted.

Target Audience

No target audience selected.