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

Krishnendu Chatterjee, Manas Joglekar, Nisarg Shah

We consider Markov decision processes (MDPs) with $\omega$-regular specifications given as parity objectives. We consider the problem of computing the set of almost-sure winning vertice…