Computational Methods for Finite State Finite Valued Markovian Decision Problems

摘要

Markov and semi-Markov decision problems with a finite number of states and a finite number of actions are considered. A two phase computational system is developed. The first phase is an analysis phase which can be applied to an n state K action problem at a cost of betwen 5nK and 9nK multiplies and adds. The second phase of the computational method uses successive improvement of upper and lower bounds to eliminate nonoptimal actions until the optimal action is determined for one or more states. At this point, the analysis phase is used to eliminate these states and generate improved upper and lower bounds for the reduced problem. (Author)