Export Citations
- Author:
- Arnab Nilim,
- Chair:
- Laurent El Ghaoui
Optimal solutions to Markov decision problems may be very sensitive with respect to the state transition probabilities. In many practical problems, the estimation of these probabilities is far from accurate. Hence, estimation errors are limiting factors in applying Markov decision processes to real-world problems.
We consider a robust control problem for a finite-state, finite-action Markov decision process, where uncertainty on the transition matrices is described in terms of possibly non-convex sets. We show that perfect duality holds for this problem, and that as a consequence, it can be solved with a variant of the classical dynamic programming algorithm, the “robust dynamic programming” algorithm. We show that a particular choice of the uncertainty sets, involving likelihood regions or entropy bounds, leads to both a statistically accurate representation of uncertainty, and a complexity of the robust recursion that is almost the same as that of the classical recursion. Hence, robustness can be added at practically no extra computing cost. We derive similar results for other uncertainty sets, including one with a finite number of possible values for the transition matrices.
We describe in a practical path planning example the benefits of using a robust strategy instead of the classical optimal strategy; even if the uncertainty level is only crudely guessed, the robust strategy yields a much better worst-case expected travel time.
Cited By
- Yu P, Zhu S, De Giacomo G, Kwiatkowska M and Vardi M The trembling-hand problem for LTLf planning Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence, (3631-3641)
- Bernini N, Bessa M, Delmas R, Gold A, Goubault E, Pennec R, Putot S and Sillion F A few lessons learned in reinforcement learning for quadcopter attitude control Proceedings of the 24th International Conference on Hybrid Systems: Computation and Control, (1-11)
- Gohari P, Hale M and Topcu U Privacy-Preserving Policy Synthesis in Markov Decision Processes 2020 59th IEEE Conference on Decision and Control (CDC), (6266-6271)
- Pal R, Datta A and Dougherty E (2009). Bayesian robustness in the control of gene regulatory networks, IEEE Transactions on Signal Processing, 57:9, (3667-3678), Online publication date: 1-Sep-2009.
- Doshi F and Roy N Efficient model learning for dialog management Proceedings of the ACM/IEEE international conference on Human-robot interaction, (65-72)
Recommendations
Robust Control of Markov Decision Processes with Uncertain Transition Matrices
Optimal solutions to Markov decision problems may be very sensitive with respect to the state transition probabilities. In many practical problems, the estimation of these probabilities is far from accurate. Hence, estimation errors are limiting factors ...
Distributionally robust Markov decision processes
NIPS'10: Proceedings of the 24th International Conference on Neural Information Processing Systems - Volume 2We consider Markov decision processes where the values of the parameters are uncertain. This uncertainty is described by a sequence of nested sets (that is, each set contains the previous one), each of which corresponds to a probabilistic guarantee for a ...
Distributionally Robust Markov Decision Processes
We consider Markov decision processes where the values of the parameters are uncertain. This uncertainty is described by a sequence of nested sets (that is, each set contains the previous one), each of which corresponds to a probabilistic guarantee for ...