Rolling horizon procedures in nonhomogeneous Markov decision processes

By far the most common planning procedure found in practice is to approximate the solution to an infinite horizon problem by a series of rolling finite horizon solutions. Although many empirical studies have been done, this so-called rolling horizon procedure has been the subject of a few analytic studies. The authors provide a cost error bound for a general rolling horizon algorithm when applied to infinite horizon nonhomogeneous Markov decision processes, both in the discounted and average cost cases. They show that a Doeblin coefficient of ergodicity acts much like a discount factor to reduce this error. In particular, the authors show that the error goes to zero for any fixed rolling horizon as this Doeblin measure of control over the future decreases. The thoery is illustrated through an application to vehicle deployment.