Markov decision processes with uncertain parameters

Abstract

Markov decision processes model stochastic uncertainty in systems and allow one to construct strategies which optimize the behaviour of a system with respect to some reward function. However, the parameters for this uncertainty, that is, the probabilities inside a Markov decision model, are derived from empirical or expert knowledge and are themselves subject to uncertainties such as measurement errors or limited expertise. This work considers second-order uncertainty models for Markov decision processes and derives theoretical and practical results. Among other models, this work considers two main forms of uncertainty. One form is a set of discrete scenarios with a prior probability distribution and the task to maximize the expected reward under the given probability distribution. Another form of uncertainty is a continuous uncertainty set of scenarios and the task to compute a policy that optimizes the rewards in the optimistic and pessimistic cases. The work provides two kinds of results. First, we establish complexity-theoretic hardness results for the considered optimization problems. Second, we design heuristics for some of the problems and evaluate them empirically. In the first class of results, we show that additional model uncertainty makes the optimization problems harder to solve, as they add an additional party with own optimization goals. In the second class of results, we show that even if the discussed problems are hard to solve in theory, we can come up with efficient heuristics that can solve them adequately well for practical applications.