Please use this identifier to cite or link to this item:
https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-341
Title: | Probabilistic goal Markov decision processes | Authors: | Xu, H. Mannor, S. |
Issue Date: | 2011 | Citation: | Xu, H., Mannor, S. (2011). Probabilistic goal Markov decision processes. IJCAI International Joint Conference on Artificial Intelligence : 2046-2052. ScholarBank@NUS Repository. 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. | Source Title: | IJCAI International Joint Conference on Artificial Intelligence | URI: | http://scholarbank.nus.edu.sg/handle/10635/73777 | ISBN: | 9781577355120 | ISSN: | 10450823 | DOI: | 10.5591/978-1-57735-516-8/IJCAI11-341 |
Appears in Collections: | Staff Publications |
Show full item record
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.