Value iteration for simple stochastic games: Stopping criterion and learning algorithm

EISENTRAUT, Julia; Edon KELMENDI; Jan KŘETÍNSKÝ a Maximilian WEININGER. Value iteration for simple stochastic games: Stopping criterion and learning algorithm. Information and Computation. Amsterdam: Elsevier, 2022, roč. 285, č. 104886, s. 1-32. ISSN 0890-5401. Dostupné z: https://doi.org/10.1016/J.IC.2022.104886.

Základní údaje

Originální název

Value iteration for simple stochastic games: Stopping criterion and learning algorithm

Autoři

EISENTRAUT, Julia; Edon KELMENDI; Jan KŘETÍNSKÝ a Maximilian WEININGER

Vydání

Information and Computation, Amsterdam, Elsevier, 2022, 0890-5401

---

Další údaje

Typ výsledku

Článek v odborném periodiku

Impakt faktor

Impact factor: 1.000

Označené pro přenos do RIV

Ne

Organizační jednotka

Fakulta informatiky

DOI

https://doi.org/10.1016/J.IC.2022.104886

---

Anotace

V originále

The classical problem of reachability in simple stochastic games is typically solved by value iteration (VI), which produces a sequence of under-approximations of the value of the game, but is only guaranteed to converge in the limit. We provide an additional converging sequence of over-approximations, based on an analysis of the game graph. Together, these two sequences entail the first error bound and hence the first stopping criterion for VI on simple stochastic games, indicating when the algorithm can be stopped for a given precision. Consequently, VI becomes an anytime algorithm returning the approximation of the value and the current error bound. We further use this error bound to provide a learning-based asynchronous VI algorithm; it uses simulations and thus often avoids exploring the whole game graph, but still yields the same guarantees. Finally, we experimentally show that the overhead for computing the additional sequence of over-approximations often is negligible.