Sound Value Iteration for Simple Stochastic Games

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F25%3A00143681" target="_blank" >RIV/00216224:14330/25:00143681 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.4204/EPTCS.428.4" target="_blank" >http://dx.doi.org/10.4204/EPTCS.428.4</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4204/EPTCS.428.4" target="_blank" >10.4204/EPTCS.428.4</a>

Result language
angličtina
Original language name
Sound Value Iteration for Simple Stochastic Games
Original language description
Algorithmic analysis of Markov decision processes (MDP) and stochastic games (SG) in practice relies on value-iteration (VI) algorithms. Since basic VI does not provide guarantees on the precision of the result, variants of VI have been proposed that offer such guarantees. In particular, sound value iteration (SVI) not only provides precise lower and upper bounds on the result, but also converges faster in the presence of probabilistic cycles. Unfortunately, it is neither applicable to SG, nor to MDP with end components. In this paper, we extend SVI and cover both cases. The technical challenge consists mainly in proper treatment of end components, which require different handling than in the literature. Moreover, we provide several optimizations of SVI. Finally, we evaluate our prototype implementation experimentally to demonstrate its potential on systems with probabilistic cycles.
Czech name
—
Czech description
—

Publication year
2025
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection
ELECTRONIC PROCEEDINGS IN THEORETICAL COMPUTER SCIENCE
ISBN
—
ISSN
2075-2180
e-ISSN
—
Number of pages
16
Pages from-to
29-44
Publisher name
OPEN PUBL ASSOC
Place of publication
SYDNEY
Event location
Valletta, MALTA
Event date
Jan 1, 2025
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
001602118100002

Similar results(10)