---
title: "Probabilistic Goal Markov Decision Processes"
authors:
  - "Huan Xu"
  - "Shie Mannor"
doi: "10.5591/978-1-57735-516-8/IJCAI11-341"
url: "https://ijcai.org/proceedings/2011/341"
pdf: "https://ijcai.org/proceedings/2011/0341.pdf"
venue: "Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence"
year: 2011
pages: "2046-2051"
track: ""
keywords:
---

# Probabilistic Goal Markov Decision Processes

Huan Xu, Shie Mannor

*Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence*, pages 2046-2051. DOI: [10.5591/978-1-57735-516-8/IJCAI11-341](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.