About: 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.

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: 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. Goto Sponge NotDistinct Permalink

An Entity of Type : fabio:Abstract, within Data Space : wasabi.inria.fr associated with source document(s)

Attributes	Values
type	abstract
value	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.
Subject	Algorithms Numerical analysis Graph theory Network theory Mathematical and quantitative methods (economics) Mathematical logic Theoretical computer science Computational problems in graph theory Graph algorithms Iterative methods Polynomial-time problems Glossaries of mathematics Game theory game classes
part of	Widest Paths and Global Propagation in Bounded Value Iteration for Stochastic Games
is abstract of	Widest Paths and Global Propagation in Bounded Value Iteration for Stochastic Games
is hasSource of	covid:ann/target/7bfd3e56b3a9311b3d74519df831950d82d046db covid:ann/target/d1d42ea993b1158d7748ad1f758d3cd6aee24dcc covid:ann/target/bb1431f867522fa17cc94e69704e1d5b615ca79d covid:ann/target/d95e5ad0f433d09d67c27bdc94117b7e2fa05b27 covid:ann/target/0349c0456898280f909c29a49fc9e37ba16d1f4d covid:ann/target/cdec89b2e3421f4ee1cbebac18e27d5b61d9ca2a

Faceted Search & Find service v1.13.91 as of Mar 24 2020

Alternative Linked Data Documents: Sponger | ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3229 as of Jul 10 2020, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (94 GB total memory)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software