Value Iteration for Simple Stochastic Games: Stopping Criterion and Learning Algorithm

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

Výsledek na webu

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

Jazyk výsledku

angličtina

Název v původním jazyce

Value Iteration for Simple Stochastic Games: Stopping Criterion and Learning Algorithm

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Value Iteration for Simple Stochastic Games: Stopping Criterion and Learning Algorithm

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA18-11193S" target="_blank" >GA18-11193S: Algoritmy pro diskrétní systémy a hry s nekonečně mnoha stavy</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2018

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

Computer Aided Verification (CAV 2018)

ISBN

9783319961446

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

20

Strana od-do

623-642

Název nakladatele

Springer

Místo vydání

Cham

Místo konání akce

Cham

Datum konání akce

1. 1. 2018

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

CST - Celostátní akce

Kód UT WoS článku

000491481600036