Computing Optimal Strategies for Markov Decision Processes with Parity and Positive-Average Conditions

January 28, 2013

Youssouf Oualhadj (LIF, Marseille)

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 in polynomial time. We also show that optimal strategies exist, require only finite memory and can be effectively computed.