Strategy improvement for concurrent reachability and turn based stochastic safety games Chatterjee, Krishnendu ; https://orcid.org/0000-0002-4561-241X De Alfaro, Luca Henzinger, Thomas A ; https://orcid.org/0000−0002−2985−7724 ddc:000 We consider concurrent games played on graphs. At every round of a game, each player simultaneously and independently selects a move; the moves jointly determine the transition to a successor state. Two basic objectives are the safety objective to stay forever in a given set of states, and its dual, the reachability objective to reach a given set of states. First, we present a simple proof of the fact that in concurrent reachability games, for all ε&gt;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, our proof is more elementary and more combinatorial. Second, we present a strategy-improvement (a.k.a. policy-iteration) algorithm for concurrent games with reachability objectives. Finally, we present a strategy-improvement algorithm for turn-based stochastic games (where each player selects moves in turns) with safety objectives. Our algorithms yield sequences of player-1 strategies which ensure probabilities of winning that converge monotonically (from below) to the value of the game. © 2012 Elsevier Inc. Elsevier 2013 info:eu-repo/semantics/article doc-type:article text http://purl.org/coar/resource_type/c_2df8fbb1 https://research-explorer.ista.ac.at/record/2854 https://research-explorer.ista.ac.at/download/2854/5370 Chatterjee K, De Alfaro L, Henzinger TA. Strategy improvement for concurrent reachability and turn based stochastic safety games. <i>Journal of Computer and System Sciences</i>. 2013;79(5):640-657. doi:<a href="https://doi.org/10.1016/j.jcss.2012.12.001">10.1016/j.jcss.2012.12.001</a> eng info:eu-repo/semantics/altIdentifier/doi/10.1016/j.jcss.2012.12.001 info:eu-repo/semantics/altIdentifier/wos/000316837300011 https://creativecommons.org/licenses/by-nc-nd/4.0/ info:eu-repo/semantics/openAccess