Markov Decision Processes and Deterministic Büchi Automata

• Autorzy: Beauquier D.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

Markov decision processes; Büchi automata; performance evaluation

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2002
• Tom: Vol. 50, nr 1
• Strony: 1--13
• Opis fizyczny: bibliogr. 23 poz.

Twórcy

autor

Beauquier D.

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