Reward Revision for Discounted Markov Decision Problems

Chelsea C. White, Lyn C. Thomas and William T. Scherer
Additional contact information
Chelsea C. White: University of Virginia, Charlottesville, Virginia
Lyn C. Thomas: The University of Manchester, Manchester, England
William T. Scherer: University of Virginia, Charlottesville, Virginia

Operations Research, 1985, vol. 33, issue 6, 1299-1315

Abstract: We present a numerical procedure for determining the optimal total expected discounted reward vector f * for an infinite horizon, discrete stage, finite state and action Markov decision process (MDP). This procedure exploits the fact that many MDPs generate the same vector f *. The objective of the procedure is to simultaneously construct and solve one such MDP that has a computationally attractive transition structure. The construction of this MDP requires the periodic revision of its reward structure. We then present a simple, a priori method for estimating the impact of the new procedure on operation counts as compared to standard successive approximations. This method is useful for determining whether or not the new procedure should be used and for selecting an important design parameter. We also describe two extensions of the new procedure, one generalizing a standard extrapolation and the other a modified policy iteration algorithm. A numerical evaluation indicates that for MDPs having transition structures with a small number of dominant probabilities per row, the new procedure can significantly reduce CPU time.

Keywords: 111 dynamic programming; 116 Markov finite state (search for similar items in EconPapers)
Date: 1985
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.33.6.1299 (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:33:y:1985:i:6:p:1299-1315

Access Statistics for this article

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