Widest paths and global propagation in bounded value iteration for stochastic games

DOI10.1007/978-3-030-53291-8_19MaRDI QIDQ2226749zbMATH OpenOpenAlexFDO

Authors Kittiphon Phalakarn, Toru Takisaka, Thomas Haas, Ichiro Hasuo

Publication date 9 February 2021

Copyright license Creative Commons Attribution 4.0 International

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

Mathematics Subject Classification ID

Specification and verification (program logics, model checking, etc.) (68Q60) Programming involving graphs or networks (90C35) Markov and semi-Markov decision processes (90C40) Stochastic games, stochastic differential games (91A15)

Abstract: Solving stochastic games with the reachability objective is a fundamental problem, especially in quantitative verification and synthesis. For this purpose, bounded value iteration (BVI) attracts attention as an efficient iterative method. However, BVI's performance is often impeded by costly end component (EC) computation that is needed to ensure convergence. Our contribution is a novel BVI algorithm that conducts, in addition to local propagation by the Bellman update that is typical of BVI, global propagation of upper bounds that is not hindered by ECs. To conduct global propagation in a computationally tractable manner, we construct a weighted graph and solve the widest path problem in it. Our experiments show the algorithm's performance advantage over the previous BVI algorithms that rely on EC computation.

Recommendations

• Value iteration for simple stochastic games: stopping criterion and learning algorithm
• Value iteration for simple stochastic games: stopping criterion and learning algorithm
• Optimistic and topological value iteration for simple stochastic games
• Value Iteration

Cited in

(6)

• Comparison of algorithms for simple stochastic games
• Value iteration for simple stochastic games: stopping criterion and learning algorithm
• Optimistic and topological value iteration for simple stochastic games
• A practitioner's guide to MDP model checking algorithms
• Strategy templates for almost-sure and positive winning of stochastic parity games towards permissive and resilient control
• A direct reduction from stochastic parity games to simple stochastic games

This page was built for publication: Widest paths and global propagation in bounded value iteration for stochastic games

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