English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

We consider Markov decision processes (MDPs) with $\omega$-regularspecifications given as parity objectives. We consider the problem of computingthe set of almost-sure winning vertices from where the objective can be ensuredwith probability 1. The algorithms for the computation of the almost-surewinning set for parity objectives iteratively use the solutions for thealmost-sure winning set for B\"uchi objectives (a special case of parityobjectives). We study for the first time the average case complexity of theclassical algorithm for computing almost-sure winning vertices for MDPs withB\"uchi objectives. Our contributions are as follows: First, we show that forMDPs with constant out-degree the expected number of iterations is at mostlogarithmic and the average case running time is linear (as compared to theworst case linear number of iterations and quadratic time complexity). Second,we show that for general MDPs the expected number of iterations is constant andthe average case running time is linear (again as compared to the worst caselinear number of iterations and quadratic time complexity). Finally we alsoshow that given all graphs are equally likely, the probability that theclassical algorithm requires more than constant number of iterations isexponentially small.

Average Case Analysis of the Classical Algorithm for Markov Decision Processes with B\"uchi Objectives