Approximating values of generalized-reachability stochastic games

DOI10.1145/3373718.3394761MaRDI QIDQ5145624zbMATH OpenOpenAlexFDO

Authors Pranav Ashok, Krishnendu Chatterjee, Jan Křetínský, Maximilian Weininger, Tobias Winkler

Publication date 21 January 2021

Published in Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1908.05106

zbMATH Keywords

anytime algorithmmultiple reachability objectivesPareto frontierstochastic games

Mathematics Subject Classification ID

Approximation algorithms (68W25) Analysis of algorithms (68W40) Stochastic games, stochastic differential games (91A15)

Abstract: Simple stochastic games are turn-based 2.5-player games with a reachability objective. The basic question asks whether one player can ensure reaching a given target with at least a given probability. A natural extension is games with a conjunction of such conditions as objective. Despite a plethora of recent results on the analysis of systems with multiple objectives, the decidability of this basic problem remains open. In this paper, we present an algorithm approximating the Pareto frontier of the achievable values to a given precision. Moreover, it is an anytime algorithm, meaning it can be stopped at any time returning the current approximation and its error bound.

Recommendations

• On stochastic games with multiple objectives
• Decidability results for multi-objective stochastic games
• New algorithms for solving simple stochastic games
• Termination criteria for solving concurrent safety and reachability games
• New results on simple stochastic games

Cited in

(14)

• Decidability results for multi-objective stochastic games
• Multi-objective optimization of long-run average and total rewards
• Comparison of algorithms for simple stochastic games
• Verification of multiplayer stochastic games via abstract dependency graphs
• Automatic verification of concurrent stochastic systems
• Value iteration for simple stochastic games: stopping criterion and learning algorithm
• Determinacy and optimal strategies in infinite-state stochastic reachability games
• Comparison of algorithms for simple stochastic games
• Improved pseudo-polynomial bound for the value problem and optimal strategy synthesis in mean payoff games
• Simulation Hemi-metrics between Infinite-State Stochastic Games
• Stochastic games with lexicographic objectives
• Different strokes in randomised strategies: revisiting Kuhn's theorem under finite-memory assumptions
• Stochastic games with disjunctions of multiple objectives
• Learning algorithms for verification of Markov decision processes

This page was built for publication: Approximating values of generalized-reachability stochastic games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5145624)