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

D 2018

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

KELMENDI, Edon, Julia KRÄMER, Jan KŘETÍNSKÝ a Maximilian WEININGER

Základní údaje

Originální název

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

Autoři

KELMENDI, Edon (8 Albánie), Julia KRÄMER (276 Německo), Jan KŘETÍNSKÝ (203 Česká republika, garant, domácí) a Maximilian WEININGER (276 Německo)

Vydání

Cham, Computer Aided Verification (CAV 2018), od s. 623-642, 20 s. 2018

Nakladatel

Springer

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Švýcarsko

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

tištěná verze "print"

Impakt faktor

Impact factor: 0.402 v roce 2005

Kód RIV

RIV/00216224:14330/18:00108290

Organizační jednotka

Fakulta informatiky

ISBN

978-3-319-96144-6

ISSN

DOI

http://dx.doi.org/10.1007/978-3-319-96145-3_36

UT WoS

000491481600036

Klíčová slova anglicky

Value Iteration; Simple Stochastic Games; Stopping Criterion; Learning

Štítky

core_A, firank_1

Změněno: 27. 4. 2020 23:49, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

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

GA18-11193S, projekt VaV

Název: Algoritmy pro diskrétní systémy a hry s nekonečně mnoha stavy

Investor: Grantová agentura ČR, Algoritmy pro diskrétní systémy a hry s nekonečně mnoha stavy

Citovat

KELMENDI, Edon, Julia KRÄMER, Jan KŘETÍNSKÝ a Maximilian WEININGER. Value Iteration for Simple Stochastic Games: Stopping Criterion and Learning Algorithm. In Computer Aided Verification (CAV 2018). Cham: Springer, 2018, s. 623-642. ISBN 978-3-319-96144-6. Dostupné z: https://dx.doi.org/10.1007/978-3-319-96145-3_36.

@inproceedings{1649042,
   author = {Kelmendi, Edon and Krämer, Julia and Křetínský, Jan and Weininger, Maximilian},
   address = {Cham},
   booktitle = {Computer Aided Verification (CAV 2018)},
   doi = {http://dx.doi.org/10.1007/978-3-319-96145-3_36},
   keywords = {Value Iteration; Simple Stochastic Games; Stopping Criterion; Learning},
   howpublished = {tištěná verze "print"},
   language = {eng},
   location = {Cham},
   isbn = {978-3-319-96144-6},
   pages = {623-642},
   publisher = {Springer},
   title = {Value Iteration for Simple Stochastic Games: Stopping Criterion and Learning Algorithm},
   year = {2018}
}

TY  - JOUR
ID  - 1649042
AU  - Kelmendi, Edon - Krämer, Julia - Křetínský, Jan - Weininger, Maximilian
PY  - 2018
TI  - Value Iteration for Simple Stochastic Games: Stopping Criterion and Learning Algorithm
PB  - Springer
CY  - Cham
SN  - 9783319961446
KW  - Value Iteration
KW  - Simple Stochastic Games
KW  - Stopping Criterion
KW  - Learning
N2  - 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.
ER  -

KELMENDI, Edon, Julia KRÄMER, Jan KŘETÍNSKÝ a Maximilian WEININGER. Value Iteration for Simple Stochastic Games: Stopping Criterion and Learning Algorithm. In \textit{Computer Aided Verification (CAV 2018)}. Cham: Springer, 2018, s.~623-642. ISBN~978-3-319-96144-6. Dostupné z: https://dx.doi.org/10.1007/978-3-319-96145-3\_{}36.

Podrobný výpis o publikaci