Average Case Analysis of the Classical Algorithm for Markov Decision Processes with Büchi Objectives

Details Average Case Analysis of the Classical Algorithm for Markov Decision Processes with Büchi Objectives Average Case Analysis of the Classical Algorithm for Markov Decision Processes with Büchi Objectives

2012-02-19

arxiv.org/abs/1202.4175v1

Computer Science

Logic in Computer Science

arXiv admin note: text overlap with arXiv:1104.3348

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 vertices 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). We study for the first time the average case complexity of the classical algorithm for computing almost-sure winning vertices for MDPs with B\"uchi objectives. Our contributions are as follows: First, we show that for MDPs with constant out-degree the expected number of iterations is at most logarithmic and the average case running time is linear (as compared to the worst case linear number of iterations and quadratic time complexity). Second, we show that for general MDPs the expected number of iterations is constant and the average case running time is linear (again as compared to the worst case linear number of iterations and quadratic time complexity). Finally we also show that given all graphs are equally likely, the probability that the classical algorithm requires more than constant number of iterations is exponentially small.

Affiliated with

Also associated with

No associations

Rating

Average Case Analysis of the Classical Algorithm for 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 Average Case Analysis of the Classical Algorithm for 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 Average Case Analysis of the Classical Algorithm for Markov Decision Processes with Büchi Objectives will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-419611