Value Iteration for Simple Stochastic Games: Stopping Criterion and Learning Algorithm
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F18%3A00108290" target="_blank" >RIV/00216224:14330/18:00108290 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1007/978-3-319-96145-3_36" target="_blank" >http://dx.doi.org/10.1007/978-3-319-96145-3_36</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-319-96145-3_36" target="_blank" >10.1007/978-3-319-96145-3_36</a>
Alternative languages
Result language
angličtina
Original language name
Value Iteration for Simple Stochastic Games: Stopping Criterion and Learning Algorithm
Original language description
Simple stochastic games can be solved by value iteration (VI), which yields a sequence of under-approximations of the value of the game. This sequence is guaranteed to converge to the value only in the limit. Since no stopping criterion is known, this technique does not provide any guarantees on its results. We provide the first stopping criterion for VI on simple stochastic games. It is achieved by additionally computing a convergent sequence of over-approximations of the value, relying on an analysis of the game graph. Consequently, VI becomes an anytime algorithm returning the approximation of the value and the current error bound. As another consequence, we can provide a simulation-based asynchronous VI algorithm, which yields the same guarantees, but without necessarily exploring the whole game graph.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GA18-11193S" target="_blank" >GA18-11193S: Algorithms for Infinite-State Discrete Systems and Games</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2018
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Computer Aided Verification (CAV 2018)
ISBN
9783319961446
ISSN
0302-9743
e-ISSN
—
Number of pages
20
Pages from-to
623-642
Publisher name
Springer
Place of publication
Cham
Event location
Cham
Event date
Jan 1, 2018
Type of event by nationality
CST - Celostátní akce
UT code for WoS article
000491481600036