*banner
 

Strategy Improvement for Stochastic Rabin and Streett Games
Krishnendu Chatterjee, Tom Henzinger

Citation
Krishnendu Chatterjee, Tom Henzinger. "Strategy Improvement for Stochastic Rabin and Streett Games". CONCUR 2006 - Concurrency Theory, 17th International Conference, Christel Baier and Holger Hermanns (eds.), 375-389, August, 2006.

Abstract
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.

Electronic downloads

Citation formats  
  • HTML
    Krishnendu Chatterjee, Tom Henzinger. <a
    href="http://chess.eecs.berkeley.edu/pubs/232.html"
    >Strategy Improvement for Stochastic Rabin and Streett
    Games</a>, CONCUR 2006 - Concurrency Theory, 17th
    International Conference, Christel Baier and Holger Hermanns
    (eds.), 375-389, August, 2006.
  • Plain text
    Krishnendu Chatterjee, Tom Henzinger. "Strategy
    Improvement for Stochastic Rabin and Streett Games".
    CONCUR 2006 - Concurrency Theory, 17th International
    Conference, Christel Baier and Holger Hermanns (eds.),
    375-389, August, 2006.
  • BibTeX
    @inproceedings{ChatterjeeHenzinger06_StrategyImprovementForStochasticRabinStreettGames,
        author = {Krishnendu Chatterjee and Tom Henzinger},
        title = {Strategy Improvement for Stochastic Rabin and
                  Streett Games},
        booktitle = {CONCUR 2006 - Concurrency Theory, 17th
                  International Conference},
        editor = {Christel Baier and Holger Hermanns},
        pages = {375-389},
        month = {August},
        year = {2006},
        abstract = {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. },
        URL = {http://chess.eecs.berkeley.edu/pubs/232.html}
    }
    

Posted by Krishnendu Chatterjee, PhD on 13 May 2007.
Groups: chesslocal
For additional information, see the Publications FAQ or contact webmaster at chess eecs berkeley edu.

Notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright.

©2002-2018 Chess