Please use this identifier to cite or link to this item: https://doi.org/978-1-57735-516-8/IJCAI11-341
Title: Probabilistic goal Markov decision processes
Authors: Xu, H. 
Mannor, S.
Issue Date: 2011
Source: 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/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: 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.

Page view(s)

13
checked on Dec 9, 2017

Google ScholarTM

Check

Altmetric


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