# Average case analysis of the classical algorithm for Markov decision processes with Büchi objectives

Chatterjee K, Joglekar M, Shah N. 2015. Average case analysis of the classical algorithm for Markov decision processes with Büchi objectives. Theoretical Computer Science. 573(3), 71–89.

Download (ext.)

*Journal Article*|

*Published*|

*English*

**Scopus indexed**

Author

Chatterjee, Krishnendu

^{IST Austria}^{}; Joglekar, Manas; Shah, NisargDepartment

Grant

Abstract

We consider Markov decision processes (MDPs) with specifications given as Büchi (liveness) objectives, and examine the problem of computing the set of almost-sure winning vertices such that the objective can be ensured with probability 1 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 Büchi 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.

Publishing Year

Date Published

2015-03-30

Journal Title

Theoretical Computer Science

Acknowledgement

The research was supported by FWF Grant No. P 23499-N23, FWF NFN Grant No. S11407-N23 (RiSE), ERC Start Grant (279307: Graph Games), and the Microsoft Faculty Fellows Award. Nisarg Shah is also supported by NSF Grant CCF-1215883.

Volume

573

Issue

3

Page

71 - 89

IST-REx-ID

### Cite this

Chatterjee K, Joglekar M, Shah N. Average case analysis of the classical algorithm for Markov decision processes with Büchi objectives.

*Theoretical Computer Science*. 2015;573(3):71-89. doi:10.1016/j.tcs.2015.01.050Chatterjee, K., Joglekar, M., & Shah, N. (2015). Average case analysis of the classical algorithm for Markov decision processes with Büchi objectives.

*Theoretical Computer Science*. Elsevier. https://doi.org/10.1016/j.tcs.2015.01.050Chatterjee, Krishnendu, Manas Joglekar, and Nisarg Shah. “Average Case Analysis of the Classical Algorithm for Markov Decision Processes with Büchi Objectives.”

*Theoretical Computer Science*. Elsevier, 2015. https://doi.org/10.1016/j.tcs.2015.01.050.K. Chatterjee, M. Joglekar, and N. Shah, “Average case analysis of the classical algorithm for Markov decision processes with Büchi objectives,”

*Theoretical Computer Science*, vol. 573, no. 3. Elsevier, pp. 71–89, 2015.Chatterjee, Krishnendu, et al. “Average Case Analysis of the Classical Algorithm for Markov Decision Processes with Büchi Objectives.”

*Theoretical Computer Science*, vol. 573, no. 3, Elsevier, 2015, pp. 71–89, doi:10.1016/j.tcs.2015.01.050.**All files available under the following license(s):**

**Copyright Statement:**

**This Item is protected by copyright and/or related rights.**[...]

**Link(s) to Main File(s)**

Access Level

Open Access

**Material in IST:**

**Earlier Version**

### Export

Marked PublicationsOpen Data IST Research Explorer

### Sources

arXiv 1202.4175