Please use this identifier to cite or link to this item:
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.
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
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.


checked on Aug 13, 2018

Page view(s)

checked on Jul 6, 2018

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.