License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2012.461
URN: urn:nbn:de:0030-drops-38817
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2012/3881/
Go to the corresponding LIPIcs Volume Portal

Chatterjee, Krishnendu ; Joglekar, Manas ; Shah, Nisarg

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

pdf-format:
42.pdf (0.5 MB)

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 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 given that all MDPs are equally likely, the probability that the classical algorithm requires more than constant number of iterations is exponentially small.

BibTeX - Entry

@InProceedings{chatterjee_et_al:LIPIcs:2012:3881,
  author =	{Krishnendu  Chatterjee and Manas Joglekar and Nisarg Shah},
  title =	{{Average Case Analysis of the Classical Algorithm for Markov Decision Processes with B{\"u}chi Objectives}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012) },
  pages =	{461--473},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-47-7},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{18},
  editor =	{Deepak D'Souza and Telikepalli Kavitha and Jaikumar Radhakrishnan},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2012/3881},
  URN =		{urn:nbn:de:0030-drops-38817},
  doi =		{10.4230/LIPIcs.FSTTCS.2012.461},
  annote =	{Keywords: MDPs, Buchi objectives, Average case analysis}
}

Keywords: MDPs, Buchi objectives, Average case analysis
Collection: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)
Issue Date: 2012
Date of publication: 14.12.2012

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI