A METHODOLOGY FOR COMPUTATION REDUCTION FOR SPECIALLY STRUCTURED LARGE-SCALE MARKOV DECISION-PROBLEMS

Markov Decision Processes (MDP's) deal with sequential decision making in stochastic systems. Existing solution techniques provide powerful tools for determining the optimal policy set in such systems. However, many problems have extremely large state and action spaces making them computationally intractable. The purpose of this paper is both to present a methodology which takes advantage of the structure of many large scale problems (i. e. , problems with a high percentage of transient states under optimal control), and to provide computational results indicating the value of the approach.