Sémidoc 24 février 2011

Youssouf Oualhadj (LaBRI)


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






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.