Rolling Horizon Procedures in Nonhomogeneous Markov Decision Processes

Jeffrey M. Alden and Robert L. Smith
Additional contact information
Jeffrey M. Alden: General Motors Research Laboratories, Warren, Michigan
Robert L. Smith: The University of Michigan, Ann Arbor, Michigan

Operations Research, 1992, vol. 40, issue 3-supplement-2, S183-S194

Abstract: 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 few analytic studies. We 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. We show that a Doeblin coefficient of ergodicity acts much like a discount factor to reduce this error. In particular, we show that the error goes to zero for any fixed rolling horizon as this Doeblin measure of control over the future decreases. The theory is illustrated through an application to vehicle deployment.

Keywords: dynamic programming; Markov infinite state: rolling horizon solution of nonhomogeneous MDPs (search for similar items in EconPapers)
Date: 1992
References: Add references at CitEc
Citations: View citations in EconPapers (22)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.40.3.S183 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:40:y:1992:i:3-supplement-2:p:s183-s194

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().