Optimistic and Topological Value Iteration for Simple
Stochastic Games

D 2022

Optimistic and Topological Value Iteration for Simple Stochastic Games

AZEEM, Muqsit; Alexandros EVANGELIDIS; Jan KŘETÍNSKÝ; Alexander SLIVINSKIY; Maximilian WEININGER et al.

Základní údaje

Originální název

Optimistic and Topological Value Iteration for Simple Stochastic Games

Autoři

AZEEM, Muqsit; Alexandros EVANGELIDIS; Jan KŘETÍNSKÝ; Alexander SLIVINSKIY a Maximilian WEININGER

Vydání

Automated Technology for Verification and Analysis - 20th International Symposium, ATVA 2022, Virtual Event, October 25-28, 2022, Proceedings, od s. 285-302, 18 s. 2022

Nakladatel

Springer

Další údaje

Typ výsledku

Stať ve sborníku

Označené pro přenos do RIV

Organizační jednotka

Fakulta informatiky

ISBN

9783031199912

ISSN

DOI

https://doi.org/10.1007/978-3-031-19992-9_18

Změněno: 17. 3. 2025 14:43, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

While value iteration (VI) is a standard solution approach to simple stochastic games (SSGs), it suffered from the lack of a stopping criterion. Recently, several solutions have appeared, among them also “optimistic” VI (OVI). However, OVI is applicable only to one-player SSGs with no end components. We lift these two assumptions, making it available to general SSGs. Further, we utilize the idea in the context of topological VI, where we provide an efficient precise solution. In order to compare the new algorithms with the state of the art, we use not only the standard benchmarks, but we also design a random generator of SSGs, which can be biased towards various types of models, aiding in understanding the advantages of different algorithms on SSGs.

Citovat

AZEEM, Muqsit; Alexandros EVANGELIDIS; Jan KŘETÍNSKÝ; Alexander SLIVINSKIY a Maximilian WEININGER. Optimistic and Topological Value Iteration for Simple Stochastic Games. In Automated Technology for Verification and Analysis - 20th International Symposium, ATVA 2022, Virtual Event, October 25-28, 2022, Proceedings. Springer, 2022, s. 285-302. ISBN 9783031199912. Dostupné z: https://doi.org/10.1007/978-3-031-19992-9_18.

@inproceedings{2484773,
   author = {Azeem, Muqsit and Evangelidis, Alexandros and Křetínský, Jan and Slivinskiy, Alexander and Weininger, Maximilian},
   booktitle = {Automated Technology for Verification and Analysis - 20th International Symposium, ATVA 2022, Virtual Event, October 25-28, 2022, Proceedings},
   doi = {https://doi.org/10.1007/978-3-031-19992-9_18},
   isbn = {9783031199912},
   pages = {285-302},
   publisher = {Springer},
   title = {Optimistic and Topological Value Iteration for Simple Stochastic Games},
   year = {2022}
}

TY  - CONF
ID  - 2484773
AU  - Azeem, Muqsit - Evangelidis, Alexandros - Křetínský, Jan - Slivinskiy, Alexander - Weininger, Maximilian
PY  - 2022
TI  - Optimistic and Topological Value Iteration for Simple Stochastic Games
PB  - Springer
SN  - 9783031199912
N2  - While value iteration (VI) is a standard solution approach to simple stochastic games (SSGs), it suffered from the lack of a stopping criterion. Recently, several solutions have appeared, among them also “optimistic” VI (OVI). However, OVI is applicable only to one-player SSGs with no end components. We lift these two assumptions, making it available to general SSGs. Further, we utilize the idea in the context of topological VI, where we provide an efficient precise solution. In order to compare the new algorithms with the state of the art, we use not only the standard benchmarks, but we also design a random generator of SSGs, which can be biased towards various types of models, aiding in understanding the advantages of different algorithms on SSGs.
ER  -

AZEEM, Muqsit; Alexandros EVANGELIDIS; Jan KŘETÍNSKÝ; Alexander SLIVINSKIY a Maximilian WEININGER. Optimistic and Topological Value Iteration for Simple Stochastic Games. In \textit{Automated Technology for Verification and Analysis - 20th International Symposium, ATVA 2022, Virtual Event, October 25-28, 2022, Proceedings}. Springer, 2022, s.~285-302. ISBN~9783031199912. Dostupné z: https://doi.org/10.1007/978-3-031-19992-9\_{}18.

Přehled o publikaci