Proceedings

Probabilistic Goal Markov Decision Processes

Huan Xu, Shie Mannor

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 2046-2051.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-341

Abstract

The Markov decision process model is a powerful tool in planing tasks and sequential decision making problems. The randomness of state transitions and rewards implies that the performance of a policy is often stochastic. In contrast to the standard approach that studies the expected performance, we consider the policy that maximizes the probability of achieving a pre-determined target performance, a criterion we term *probabilistic goal Markov decision processes*. We show that this problem is NP-hard, but can be solved using a pseudo-polynomial algorithm. We further consider a variant dubbed chance-constraint Markov decision problems, that treats the probability of achieving target performance as a constraint instead of the maximizing objective. This variant is NP-hard, but can be solved in pseudo-polynomial time.

Huan Xu, and Shie Mannor. 2011. Probabilistic Goal Markov Decision Processes. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 2046–2051. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-341
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards