Další formáty:
BibTeX
LaTeX
RIS
@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.
|