In response to the computational complexity of the dynamic programming/backwards induction approach to the development of optimal policies for semi-Markov decision processes, we propose a class of heuristics which result from an inductive process which proceeds forwards in time. These heuristics always choose actions in such a way as to maximize some measure of the current cost rate. We describe a procedure for calculating such cost-rate heuristics. The quality of the performance of such policies is related to the speed of evolution (in a cost sense) of the process. These ideas find natural expression in a dass of Bayesian sequential decision problems. One such ( a simple model of preventive maintenance) is described in detail . Cost-rate heuristics for this problem are calculated and assessed computationally.

Approved for public release; distribution is unlimited.

Naval Postgraduate School Research Foundation

Naval Weapons Support Center, Crane, IN.

National Research Council