Constrained Markov decision processes with uncertain transition probabilities

Abstract

We consider a constrained Markov decision process with uncertain transition probabilities, where the uncertainty is driven by a single parameter which belongs to an interval. We model it using a robust optimization framework and show that it is equivalent to a bilinear programming problem. We propose a linear programming-based algorithm to compute its global optimal solution. The numerical experiments are performed on a well-known class of Markov decision problems called Garnets using our algorithm as well as Gurobi bilinear solver. We observe that for the case of dense transition probabilities, our algorithm outperforms Gurobi bilinear solver.