10.1007/11817949_25
Krishnendu Chatterjee
Krishnendu
Chatterjee0000-0002-4561-241X
Thomas Henzinger
Thomas A
Henzinger0000−0002−2985−7724
Strategy improvement for stochastic Rabin and Streett games
LNCS
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
2006
2018-12-11T12:05:43Z
2019-08-02T12:38:20Z
conference
/record/3888
/record/3888.json
A stochastic graph game is played by two players on a game graph with probabilistic transitions. We consider stochastic graph games with omega-regular winning conditions specified as Rabin or Streett objectives. These games are NP-complete and coNP-complete, respectively. The value of the game for a player at a state s given an objective Phi is the maximal probability with which the player can guarantee the satisfaction of Phi from s. We present a strategy-improvement algorithm to compute values in stochastic Rabin games, where an improvement step involves solving Markov decision processes (MDPs) and nonstochastic Rabin games. The algorithm also computes values for stochastic Streett games but does not directly yield an optimal strategy for Streett objectives. We then show how to obtain an optimal strategy for Streett objectives by solving certain nonstochastic Streett games.