Symbolic Algorithms for Qualitative Analysis of Markov Decision Processes with Büchi Objectives

Details Symbolic Algorithms for Qualitative Analysis of Markov Decision Processes with Büchi Objectives Symbolic Algorithms for Qualitative Analysis of Markov Decision Processes with Büchi Objectives

2011-04-17

arxiv.org/abs/1104.3348v1

Computer Science

Computer Science and Game Theory

Scientific paper

We consider Markov decision processes (MDPs) with \omega-regular specifications given as parity objectives. We consider the problem of computing the set of almost-sure winning states from where the objective can be ensured with probability 1. The algorithms for the computation of the almost-sure winning set for parity objectives iteratively use the solutions for the almost-sure winning set for B\"uchi objectives (a special case of parity objectives). Our contributions are as follows: First, we present the first subquadratic symbolic algorithm to compute the almost-sure winning set for MDPs with B\"uchi objectives; our algorithm takes O(n \sqrt{m}) symbolic steps as compared to the previous known algorithm that takes O(n^2) symbolic steps, where $n$ is the number of states and $m$ is the number of edges of the MDP. In practice MDPs have constant out-degree, and then our symbolic algorithm takes O(n \sqrt{n}) symbolic steps, as compared to the previous known $O(n^2)$ symbolic steps algorithm. Second, we present a new algorithm, namely win-lose algorithm, with the following two properties: (a) the algorithm iteratively computes subsets of the almost-sure winning set and its complement, as compared to all previous algorithms that discover the almost-sure winning set upon termination; and (b) requires O(n \sqrt{K}) symbolic steps, where K is the maximal number of edges of strongly connected components (scc's) of the MDP. The win-lose algorithm requires symbolic computation of scc's. Third, we improve the algorithm for symbolic scc computation; the previous known algorithm takes linear symbolic steps, and our new algorithm improves the constants associated with the linear number of steps. In the worst case the previous known algorithm takes 5n symbolic steps, whereas our new algorithm takes 4n symbolic steps.

Affiliated with

Also associated with

No associations

Rating

Symbolic Algorithms for Qualitative Analysis of Markov Decision Processes with Büchi Objectives does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Symbolic Algorithms for Qualitative Analysis of Markov Decision Processes with Büchi Objectives, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Symbolic Algorithms for Qualitative Analysis of Markov Decision Processes with Büchi Objectives will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-71108