TY - GEN
T1 - Optimistic and Topological Value Iteration for Simple Stochastic Games
AU - Azeem, Muqsit
AU - Evangelidis, Alexandros
AU - Křetínský, Jan
AU - Slivinskiy, Alexander
AU - Weininger, Maximilian
N1 - Publisher Copyright:
© 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.
PY - 2022
Y1 - 2022
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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85142702337&partnerID=8YFLogxK
U2 - 10.1007/978-3-031-19992-9_18
DO - 10.1007/978-3-031-19992-9_18
M3 - Conference contribution
AN - SCOPUS:85142702337
SN - 9783031199912
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 285
EP - 302
BT - Automated Technology for Verification and Analysis - 20th International Symposium, ATVA 2022, Proceedings
A2 - Bouajjani, Ahmed
A2 - Holík, Lukáš
A2 - Wu, Zhilin
PB - Springer Science and Business Media Deutschland GmbH
T2 - 20th International Symposium on Automated Technology for Verification and Analysis, ATVA 2022
Y2 - 25 October 2022 through 28 October 2022
ER -