Minimax Regret Optimisation for Robust Planning in Uncertain Markov Decision Processes

The parameters for a Markov Decision Process (MDP) often cannot be specified\nexactly. Uncertain MDPs (UMDPs) capture this model ambiguity by defining sets\nwhich the parameters belong to. Minimax regret has been proposed as an\nobjective for planning in UMDPs to find robust policies which are not overly\nconservative. In this work, we focus on planning for Stochastic Shortest Path\n(SSP) UMDPs with uncertain cost and transition functions. We introduce a\nBellman equation to compute the regret for a policy. We propose a dynamic\nprogramming algorithm that utilises the regret Bellman equation, and show that\nit optimises minimax regret exactly for UMDPs with independent uncertainties.\nFor coupled uncertainties, we extend our approach to use options to enable a\ntrade off between computation and solution quality. We evaluate our approach on\nboth synthetic and real-world domains, showing that it significantly\noutperforms existing baselines.\n