Average case analysis of the classical algorithm for Markov decision processes with Bachi objectives

作者：Chatterjee Krishnendu; Joglekar Manas; Shah Nisarg^*

来源：Theoretical Computer Science, 2015, 573: 71-89.

DOI：10.1016/j.tcs.2015.01.050

• Average-case analysis
• Buchi objectives
• Markov decision processes (MDPs)
• Random graphs

We consider Markov decision processes (MDPs) with specifications given as Buchi (liveness) objectives, and examine the problem of computing the set of almost-sure winning vertices such that the objective can be ensured with probability I from these vertices. We study for the first time the average-case complexity of the classical algorithm for computing the set of almost-sure winning vertices for MDPs with Buchi 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, for the average-case analysis over all MDPs we show that 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 when all MDPs are equally likely, the probability that the classical algorithm requires more than a constant number of iterations is exponentially small.

• 出版日期2015-3-30