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Ý and Maximilian WEININGER

Basic information

Original name

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

Authors

KELMENDI, Edon (8 Albania), Julia KRÄMER (276 Germany), Jan KŘETÍNSKÝ (203 Czech Republic, guarantor, belonging to the institution) and Maximilian WEININGER (276 Germany)

Edition

Cham, Computer Aided Verification (CAV 2018), p. 623-642, 20 pp. 2018

Publisher

Springer

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Switzerland

Confidentiality degree

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

Publication form

printed version "print"

Impact factor

Impact factor: 0.402 in 2005

RIV identification code

RIV/00216224:14330/18:00108290

Organization unit

Faculty of Informatics

ISBN

978-3-319-96144-6

ISSN

DOI

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

UT WoS

000491481600036

Keywords in English

Value Iteration; Simple Stochastic Games; Stopping Criterion; Learning

Abstract

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.

Links

GA18-11193S, research and development project

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

Investor: Czech Science Foundation

Citovat

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

Detailed Information on Publication Record