Markov Decision Processes and Deterministic Büchi Automata

Article type: Research Article

Authors: Beauquier, Danièle

Affiliations: Laboratory of Algorithmics, Complexity and Logic, University Paris-12, 61 Avenue du Gnl de Gaulle, 94 010 Créteil, France

Abstract: We prove that given a Markov Decision Process (MDP) and a fixed subset of its states~F, there is a Markov policy which maximizes everywhere the probability to reach F infinitely often. Moreover such a maximum policy is computable in polytime in the size of the MDP. This result can be applied in order to control a system with randomized or uncertain behavior with respect to a given property to optimize.

Keywords: Markov Decision Processes, Büchi automata, performance evaluation

Journal: Fundamenta Informaticae, vol. 50, no. 1, pp. 1-13, 2002