Reward Revision for Discounted Markov Decision Problems

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.