Computing Optimal Strategies for Markov Decision Processes with Parity and Positive-Average Conditions
Hugo Gimbert, Youssouf Oualhadj, Soumya Paul · HAL (Le Centre pour la Communication Scientifique Directe) · 2011
We study Markov decision processes (one-player stochastic games) equipped with parity and positive-average conditions. In these games, the goal of the player is to maximize the probability that both the parity and the positive-average conditions are fulfilled. We show that the values of these games are computable. We also show that optimal strategies exist, require only finite memory and can be effectively computed.