A Robust Approach to Markov Decision Problems with Uncertain Transition Probabilities

This paper considers a discrete-time infinite horizon discounted cost Markov decision problem in which the transition probability vector for each state-control pair is uncertain. A popular approach to this problem has been to find a policy that performs best in the worst-case scenario. A policy obtained in this manner, however, tends to be conservative. We construct a robust formulation for the problem, which produces a less conservative policy. We characterize the performance of the robust formulation via the probability that the optimal cost of a random instance of the problem is at most that of the robust formulation. A congestion-dependent pricing problem for network services is examined as a numerical example.