Strategy Improvement for Concurrent Reachability Games

Krishnendu Chatterjee, Luca de Alfaro, and Thomas A. Henzinger

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 ε>0, memoryless ε-optimal strategies exist. A memoryless strategy is independent of the history of plays, and an ε-optimal strategy achieves the objective with probability within ε 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.

Proceedings of the Third Annual Conference on Quantitative Evaluation of Systems (QEST), IEEE Computer Society Press, 2006, pp. 291-300.

Download inofficial, sometimes updated PostScript / PDF document. © 2006 IEEE.