---
res:
bibo_abstract:
- 'We consider Markov decision processes (MDPs) with specifications given as Büchi
(liveness) objectives. We consider the problem of computing the set of almost-sure
winning vertices from where the objective can be ensured with probability 1. 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 given
that all MDPs are equally likely, the probability that the classical algorithm
requires more than 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.4230/LIPIcs.FSTTCS.2012.461
bibo_volume: 18
dct_date: 2012^xs_gYear
dct_language: eng
dct_publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik@
dct_title: Average case analysis of the classical algorithm for Markov decision
processes with Büchi objectives@
...