English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We consider concurrent games played on graphs. At every round of a game, eachplayer simultaneously and independently selects a move; the moves jointlydetermine the transition to a successor state. Two basic objectives are thesafety objective to stay forever in a given set of states, and its dual, thereachability objective to reach a given set of states. First, we present asimple proof of the fact that in concurrent reachability games, for all$\epsilon>0$, memoryless $\epsilon$-optimal strategies exist. A memorylessstrategy is independent of the history of plays, and an $\epsilon$-optimalstrategy achieves the objective with probability within $\epsilon$ of the valueof the game. In contrast to previous proofs of this fact, our proof is moreelementary and more combinatorial. Second, we present a strategy-improvement(a.k.a.\ policy-iteration) algorithm for concurrent games with reachabilityobjectives. We then present a strategy-improvement algorithm for concurrentgames with safety objectives. Our algorithms yield sequences of player-1strategies which ensure probabilities of winning that converge monotonically tothe value of the game. Our result is significant because thestrategy-improvement algorithm for safety games provides, for the first time, away to approximate the value of a concurrent safety game from below. Previousmethods could approximate the values of these games only from one direction,and as no rates of convergence are known, they did not provide a practical wayto solve these games.

Strategy Improvement for Concurrent Reachability and Safety Games