Robust Solutions to Markov Decision Problems

Optimal solutions to Markov Decision Problems (MDPs) are very sensitive with respect to the state tran-sition probabilities. In many practical problems, the estimation of those probabilities is far from accurate. Hence, estimation errors are limiting factors in apply-ing MDPs to real-world problems. We propose an al-gorithm for solving £nite-state and £nite-action MDPs, where the solution is guaranteed to be robust with re-spect to estimation errors on the state transition proba-bilities. Our algorithm involves a statistically accurate yet numerically ef£cient representation of uncertainty via likelihood functions. The worst-case complexity of the robust algorithm is the same as the original Bellman recursion. Hence, robustness can be added at practically no extra computing cost