A generalized algorithm for Markovian decision problems



Journal Title

Journal ISSN

Volume Title



Solution methods for both the discounted and undiscounted Markov-renewal decision problems are reviewed, and the decision model is generalized to a new problem structure without probability restrictions, called the independent decision, stationary-policy (IDSP) problem. Existing Markovian algorithms are readily adapted to solve the IDSP problem. Theorems are developed to yield a test quantity, which in turn, yields a one-iteration algorithm for both the IDSP problem and a general linear programming problem. Due to two unresolved difficulties, the algorithm is more useful as a standard of comparison than a practical solution method; however, it is easily shown that many existing solution methods are but special weakened cases of the test quantity developed here. Two solution algorithms are developed for the IDSP problem, and all methods are compared against two criteria: fastest convergence and least error. Using empirical constants from previous studies, the conclusion is reached: for speed, choose the simplex-type method; for least error, choose the grea.test-change method; for best all-around, choose either the simplex-type method or the BLKAL method.