Citation
Krishnendu Chatterjee, Luca de Alfaro and Thomas A. Henzinger. "Strategy Improvement for Concurrent Reachability Games". QEST 06, September, 2006.

Abstract
A concurrent reachability game is a two-player game played on a graph: at each state, the players simultaneously and independently select moves; the two moves determine jointly a probability distribution over the successor states. The objective for player 1 consists in reaching a set of target states; the objective for player 2 is to prevent this, so that the game is zero-sum. Our contributions are two-fold. First, we present a simple proof of the fact that in concurrent reachability games, for all epsilon>0, memoryless epsilon-optimal strategies exist. A memoryless strategy is independent of the history of plays, and an epsilon-optimal strategy achieves the objective with probability within epsilon of the value of the game. In contrast to previous proofs of this fact, which rely on the limit behavior of discounted games using advanced Puisieux series analysis, our proof is elementary and combinatorial. Second, we present a strategy-improvement (a.k.a. policy-iteration) algorithm for concurrent games with reachability objectives.

Electronic downloads

• main.ps · application/postscript · 282 kbytes

• HTML

  Krishnendu Chatterjee, Luca de Alfaro and Thomas A.
  Henzinger. <a
  href="http://chess.eecs.berkeley.edu/pubs/234.html"
  >Strategy Improvement for Concurrent Reachability
  Games</a>, QEST 06, September, 2006.

• Plain text

  Krishnendu Chatterjee, Luca de Alfaro and Thomas A.
  Henzinger. "Strategy Improvement for Concurrent
  Reachability Games". QEST 06, September, 2006.

• BibTeX

  @inproceedings{ChatterjeeAlfaroHenzinger06_StrategyImprovementForConcurrentReachabilityGames,
      author = {Krishnendu Chatterjee, Luca de Alfaro and Thomas
                A. Henzinger},
      title = {Strategy Improvement for Concurrent Reachability
                Games},
      booktitle = {QEST 06},
      month = {September},
      year = {2006},
      abstract = {A concurrent reachability game is a two-player
                game played on a graph: at each state, the players
                simultaneously and independently select moves; the
                two moves determine jointly a probability
                distribution over the successor states. The
                objective for player 1 consists in reaching a set
                of target states; the objective for player 2 is to
                prevent this, so that the game is zero-sum. Our
                contributions are two-fold. First, we present a
                simple proof of the fact that in concurrent
                reachability games, for all epsilon>0, memoryless
                epsilon-optimal strategies exist. A memoryless
                strategy is independent of the history of plays,
                and an epsilon-optimal strategy achieves the
                objective with probability within epsilon of the
                value of the game. In contrast to previous proofs
                of this fact, which rely on the limit behavior of
                discounted games using advanced Puisieux series
                analysis, our proof is elementary and
                combinatorial. Second, we present a
                strategy-improvement (a.k.a. policy-iteration)
                algorithm for concurrent games with reachability
                objectives. },
      URL = {http://chess.eecs.berkeley.edu/pubs/234.html}
  }
  

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