About: Widest Paths and Global Propagation in Bounded Value Iteration for Stochastic Games

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

About: Widest Paths and Global Propagation in Bounded Value Iteration for Stochastic Games Goto Sponge NotDistinct Permalink

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

Attributes	Values
type	Academic Article research paper schema:ScholarlyArticle
isDefinedBy	Covid-on-the-Web dataset
has title	Widest Paths and Global Propagation in Bounded Value Iteration for Stochastic Games
Creator	Hasuo, Ichiro Haas, Thomas Phalakarn, Kittiphon Takisaka, Toru
Source	PMC
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.
has issue date	2020-06-16(xsd:dateTime)
bibo:doi	10.1007/978-3-030-53291-8_19
has license	cc-by
sha1sum (hex)	094b3839f2e003f9646c1ab42c7edf2255499315
schema:url	https://doi.org/10.1007/978-3-030-53291-8_19
resource representing a document's title	Widest Paths and Global Propagation in Bounded Value Iteration for Stochastic Games
has PubMed Central identifier	PMC7363239
schema:publication	Computer Aided Verification
resource representing a document's body	covid:094b3839f2e003f9646c1ab42c7edf2255499315#body_text
is schema:about of	covid:arg/094b3839f2e003f9646c1ab42c7edf2255499315 named entity 'weighted graph' named entity 'stochastic games' named entity 'iterative method' named entity 'widest path problem' named entity 'tuple' named entity 'greatest element' named entity 'Algorithm' named entity 'weighted graph' named entity 'Stochastic games' named entity 'fixed point' named entity 'Minimizer' named entity 'ss 1' named entity 'proper subset' named entity 'widest path problem' named entity 'MDP' named entity 'MDP' named entity 'Algorithm' named entity 'widest path' named entity 'weighted graph' named entity 'widest paths' named entity 'non-zero' named entity 'dynamic programming' named entity 'widest path problem' named entity 'upper bound' named entity 'widest path' named entity 'theoretical computer science' named entity 'arg min' named entity 'widest path' named entity 'algorithm' named entity 'iterative approximation' named entity 'stochastic games' named entity 'stochastic game' named entity 'Algorithm' named entity 'Markov' named entity 'intuition' named entity '4.7' named entity 'Algorithm' named entity 'sound approximation' named entity 'iterative approximation' named entity 'graph-theoretic' named entity 'arg min' named entity 'fixed point theorem' named entity 'Minimizer' named entity 'Algorithm' named entity 'weighted graph' named entity 'algorithm' named entity 'pseudocode' named entity 'MDP' named entity 'transition function' named entity 'solution methods' named entity 'pigeonhole principle' named entity 'reinforcement learning' named entity 'upper bound' named entity 'greatest fixed point' named entity 'graph-theoretic' named entity 'two-player game' named entity 'pigeonhole principle' named entity 'Algorithm' named entity 'running time' named entity 'Minimizer' named entity 'upper bound' named entity 'Algorithm' named entity 'Markov' named entity 'algorithm' named entity 'graph-theoretic' named entity 'algorithm' named entity 'dynamic programming' named entity 'state space' named entity 'Dijkstra' named entity 'algorithm' named entity 'eventually converge' named entity 'Algorithm' named entity 'algorithm' named entity 'algorithm' named entity 'modulo' named entity 'deterministic' named entity 'Minimizer' named entity 'MDP' named entity '0.9'

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