---
res:
bibo_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.@eng'
bibo_authorlist:
- foaf_Person:
foaf_givenName: Krishnendu
foaf_name: Chatterjee, Krishnendu
foaf_surname: Chatterjee
foaf_workInfoHomepage: http://www.librecat.org/personId=2E5DCA20-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-4561-241X
- foaf_Person:
foaf_givenName: Manas
foaf_name: Joglekar, Manas
foaf_surname: Joglekar
- foaf_Person:
foaf_givenName: Nisarg
foaf_name: Shah, Nisarg
foaf_surname: Shah
bibo_doi: 10.1016/j.tcs.2015.01.050
bibo_issue: '3'
bibo_volume: 573
dct_date: 2015^xs_gYear
dct_language: eng
dct_publisher: Elsevier@
dct_title: Average case analysis of the classical algorithm for Markov decision
processes with Büchi objectives@
...