Abstract

In this paper, we seek robust policies for uncertain Markov Decision Processes (MDPs). Mostrobust optimization approaches for these problems have focussed on the computation of maximinpolicies which maximize the value corresponding to the worst realization of the uncertainty. Recentwork has proposed minimax regret as a suitable alternative to the maximin objective for robust op-timization. However, existing algorithms for handling minimax regret are restricted to models withuncertainty over rewards only. We provide algorithms that employ sampling to improve across mul-tiple dimensions: (a) Handle uncertainties over both transition and reward models; (b) Dependenceof model uncertainties across state, action pairs and decision epochs; (c) Scalability and qualitybounds. Finally, to demonstrate the empirical effectiveness of our sampling approaches, we pro-vide comparisons against benchmark algorithms on two domains from literature. We also provide aSample Average Approximation (SAA) analysis to compute a posteriori error bounds.