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 Plus annual

Presents the access of premium content as premium feature

Premium Content

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 Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

A classic solution technique for Markov decision processes (MDP) andstochastic games (SG) is value iteration (VI). Due to its good practicalperformance, this approximative approach is typically preferred over exacttechniques, even though no practical bounds on the imprecision of the resultcould be given until recently. As a consequence, even the most used modelcheckers could return arbitrarily wrong results. Over the past decade,different works derived stopping criteria, indicating when the precisionreaches the desired level, for various settings, in particular MDP withreachability, total reward, and mean payoff, and SG with reachability.  In this paper, we provide the first stopping criteria for VI on SG with totalreward and mean payoff, yielding the first anytime algorithms in thesesettings. To this end, we provide the solution in two flavours: First through areduction to the MDP case and second directly on SG. The former is simpler andautomatically utilizes any advances on MDP. The latter allows for more localcomputations, heading towards better practical efficiency.  Our solution unifies the previously mentioned approaches for MDP and SG andtheir underlying ideas. To achieve this, we isolate objective-specificsubroutines as well as identify objective-independent concepts. Thesestructural concepts, while surprisingly simple, form the very essence of theunified solution.

Stopping Criteria for Value Iteration on Stochastic Games with Quantitative Objectives