On the Generation of Markov Decision Processes

Comparisons of the performance of solution algorithms for Markov decision processes rely heavily on problem generators to provide sizeable sets of test problems. Existing generation techniques allow little control over the properties of the test problems and often result in problems which are not typical of real-world examples. This paper identifies the properties of Markov decision processes which affect the performance of solution algorithms, and also describes a new problem generation technique which allows all of these properties to be controlled.