Sound Value Iteration for Simple Stochastic Games

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Sound Value Iteration for Simple Stochastic Games

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Sound Value Iteration for Simple Stochastic Games

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10200 - Computer and information sciences

Projekt

—

Návaznosti

V - Vyzkumna aktivita podporovana z jinych verejnych zdroju

Rok uplatnění

2025

Kód důvěrnosti údajů

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

Název statě ve sborníku

ELECTRONIC PROCEEDINGS IN THEORETICAL COMPUTER SCIENCE

ISBN

—

ISSN

2075-2180

e-ISSN

—

Počet stran výsledku

16

Strana od-do

29-44

Název nakladatele

OPEN PUBL ASSOC

Místo vydání

SYDNEY

Místo konání akce

Valletta, MALTA

Datum konání akce

1. 1. 2025

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

001602118100002