Accession Number : AD0655893

Title :   ALTERNATIVE SCHEMES FOR INVESTIGATING MARKOV DECISION PROCESSES.

Descriptive Note : Technical rept.,

Corporate Author : MASSACHUSETTS INST OF TECH CAMBRIDGE OPERATIONS RESEARCH CENTER

Personal Author(s) : Odoni,Amedeo R.

Report Date : JUN 1967

Pagination or Media Count : 74

Abstract : The report is concerned with the problem of finding optimal policies for infinite-horizon Markovian decision models. Several algorithms applicable to discrete time, discrete state, single-chain Markov processes with undiscounted rewards are described. One of these algorithms, called 'the iterative method with limits,' is proved and its properties are discussed. The method consists of finding upper and lower limits for the optimal gain per transition of the infinite-horizon process. These limits improve on each iteration of the algorithm, and converge to the final value of the optimal gain, ultimately. Simultaneously, the algorithm produces the 'relative value' variables, as well as the optimal policy. The computational efficiency of the aforementioned algorithms was compared by solving several test problems. It was found that for problems for which the number of alternatives per state is considerably less than the number of states, the iterative method with limits enjoys a serious speed advantage over the well-known policy iteration algorithms. The former method also produces very accurate results with very little programming effort. (Author)

Descriptors :   (*DECISION THEORY, *STATISTICAL PROCESSES), ALGORITHMS, ITERATIONS, OPTIMIZATION, EFFICIENCY, DYNAMIC PROGRAMMING, MATHEMATICAL MODELS, THESES

Subject Categories : Statistics and Probability
      Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE