On iterative optimization of structural Markov decision processes with discounted rewards

The paper gives a survey on solution techniques for Markov decision processes with respect to the total reward criterion. We discuss briefly a number of problem structures which guarantee that the optimal policy possesses a specific structure which can be exploited in numerical solution procedures. However, the main emphasis is on iterative methods. It is shown by examples that the effect of a number of modifications of the standard iterative method, which are advocated in the literature, is limited in some realistic situations. Numerical evidence is provided to show that exploiting the structure of a problem under consideration often yields a more substantial reduction of the required computational effort than some of the existing acceleration procedures. We advocate that this structure should be analyzed and used in choosing the appropriate solution procedure. The appropriate procedure might be composed on one hand by blending several of the acceleration concepts that are described in literature. On the other hand it should exploit the structure of optimal policies. This latter can often be done by using monotonicity properties of the computer value vector or policy. To illustrate the influence of the structure of a problem and if available, the structure of optimal policies, we sketch and solve four test problems with several successive approximation methods. In the final part of the paper, the required computational efforts are compared