About: Optimistic Value Iteration

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

About: Optimistic Value Iteration Goto Sponge NotDistinct Permalink

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

Attributes	Values
type	Academic Article research paper schema:ScholarlyArticle
isDefinedBy	Covid-on-the-Web dataset
title	Optimistic Value Iteration
Creator	Hartmanns, Arnd Kaminski, Benjamin
source	PMC
abstract	Markov decision processes are widely used for planning and verification in settings that combine controllable or adversarial choices with probabilistic behaviour. The standard analysis algorithm, value iteration, only provides lower bounds on infinite-horizon probabilities and rewards. Two “sound” variations, which also deliver an upper bound, have recently appeared. In this paper, we present a new sound approach that leverages value iteration’s ability to usually deliver good lower bounds: we obtain a lower bound via standard value iteration, use the result to “guess” an upper bound, and prove the latter’s correctness. We present this optimistic value iteration approach for computing reachability probabilities as well as expected rewards. It is easy to implement and performs well, as we show via an extensive experimental evaluation using our implementation within the mcsta model checker of the Modest Toolset.
has issue date	2020-06-16(xsd:dateTime)
bibo:doi	10.1007/978-3-030-53291-8_26
has license	cc-by
sha1sum (hex)	64f67a4f67919cf13d086ee38c103dfccf665436
schema:url	https://doi.org/10.1007/978-3-030-53291-8_26
resource representing a document's title	Optimistic Value Iteration
has PubMed Central identifier	PMC7363440
schema:publication	Computer Aided Verification
resource representing a document's body	covid:64f67a4f67919cf13d086ee38c103dfccf665436#body_text
is schema:about of	named entity 'VALUE' named entity 'PLANNING' named entity 'EVALUATION' named entity 'USED' named entity 'EXTENSIVE' named entity 'computing' named entity 'upper bound' named entity 'convergence problem' named entity 'upper bound' named entity 'edge set' named entity 'supremum' named entity 'powerset' named entity 'algorithm' named entity 'denominator' named entity 'Algorithm' named entity 'algorithm' named entity 'DTMC' named entity 'lower bound' named entity 'fixed point' named entity 'fixed point' named entity 'fixed point' named entity 'discrete-time Markov chains' named entity 'Gaussian elimination' named entity 'Markov decision processes' named entity 'algorithm' named entity 'algorithm' named entity 'model checker' named entity 'model checkers' named entity 'fixed point' named entity 'domain theory' named entity 'infinite sequence' named entity 'u-value' named entity 'continuous time' named entity 'scatter plots' named entity 'MDP' named entity 'model checker' named entity 'CTMC' named entity 'domain theory' named entity 'algorithm' named entity 'probability distributions' named entity 'graph' named entity 'rational arithmetic' named entity 'clock constraints' named entity 'MDP' named entity 'Gauss-Seidel' named entity 'lower bound' named entity 'MDP' named entity 'fixed point' named entity 'monotonicity' named entity 'histograms' named entity 'convergence problem' named entity 'MDP' named entity 'policy iteration' named entity 'Scott-continuous' named entity 'MDP' named entity 'complete lattices' named entity 'Ethernet' named entity 'Algorithm' named entity 'model checkers' named entity 'space exploration' named entity 'complete lattices' named entity 'Algorithm' named entity 'lower bound' named entity 'x-axis' named entity 'MDP' named entity 'Gauss-Seidel' named entity 'subset' named entity 'MDP' named entity 'stochastic' named entity 'state space' named entity 'automata' named entity 'y-axis' named entity 'MDP' named entity 'fixed point' named entity 'EXPTIME' named entity 'algorithm' named entity 'desired precision' named entity 'MDP' named entity 'fixed point' named entity 'non-negative' named entity 'probability' named entity 'probability 1'

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-2025 OpenLink Software