Generalizing Markov decision processes to imprecise probabilities

This paper is a first step towards generalizing the concept of a Markov decision process to imprecise probabilities. A concept of a generalized Markov decision process is defined and motivated. Finite horizon, fully observable models with total cumulative reward optimality criterion are studied. The imprecision in the model opens up a possibility of indecision. A solution procedure, that generalizes the backward induction method from the classical theory, is developed. This procedure finds all maximal (i.e., undominated) policies for a given generalized Markov decision process. An example illustrating the solution method is given. The directions for further research are discussed. (C) 2002 Elsevier Science B.V. All rights reserved.