Comparison of algorithms for simple stochastic games
Publication type: Journal Article
Publication date: 2022-11-01
scimago Q2
wos Q3
SJR: 0.493
CiteScore: 2.2
Impact factor: 1.0
ISSN: 08905401, 10902651
Computer Science Applications
Computational Theory and Mathematics
Information Systems
Theoretical Computer Science
Abstract
Simple stochastic games are turn-based 2½-player zero-sum graph games with a reachability objective. The problem is to compute the winning probabilities as well as the optimal strategies of both players. In this paper, we compare the three known classes of algorithms – value iteration, strategy iteration and quadratic programming – both theoretically and practically. Further, we suggest several improvements for all algorithms, including the first approach based on quadratic programming that avoids transforming the stochastic game to a stopping one. Our extensive experiments show that these improvements can lead to significant speed-ups. We implemented all algorithms in PRISM-games 3.0, thereby providing the first implementation of quadratic programming for solving simple stochastic games.
Found
Nothing found, try to update filter.
Found
Nothing found, try to update filter.
Top-30
Journals
|
1
2
3
4
5
6
7
8
|
|
|
Lecture Notes in Computer Science
8 publications, 61.54%
|
|
|
Annual Reviews in Control
1 publication, 7.69%
|
|
|
Information and Computation
1 publication, 7.69%
|
|
|
Electronic Proceedings in Theoretical Computer Science, EPTCS
1 publication, 7.69%
|
|
|
1
2
3
4
5
6
7
8
|
Publishers
|
1
2
3
4
5
6
7
8
|
|
|
Springer Nature
8 publications, 61.54%
|
|
|
Institute of Electrical and Electronics Engineers (IEEE)
2 publications, 15.38%
|
|
|
Elsevier
2 publications, 15.38%
|
|
|
Open Publishing Association
1 publication, 7.69%
|
|
|
1
2
3
4
5
6
7
8
|
- We do not take into account publications without a DOI.
- Statistics recalculated weekly.
Are you a researcher?
Create a profile to get free access to personal recommendations for colleagues and new articles.
Metrics
13
Total citations:
13
Citations from 2024:
10
(76.92%)
Cite this
GOST |
RIS |
BibTex
Cite this
GOST
Copy
Křetínský J. et al. Comparison of algorithms for simple stochastic games // Information and Computation. 2022. Vol. 289. p. 104885.
GOST all authors (up to 50)
Copy
Křetínský J., Ramneantu E., Slivinskiy A., Weininger M. Comparison of algorithms for simple stochastic games // Information and Computation. 2022. Vol. 289. p. 104885.
Cite this
RIS
Copy
TY - JOUR
DO - 10.1016/j.ic.2022.104885
UR - https://doi.org/10.1016/j.ic.2022.104885
TI - Comparison of algorithms for simple stochastic games
T2 - Information and Computation
AU - Křetínský, Jan
AU - Ramneantu, Emanuel
AU - Slivinskiy, Alexander
AU - Weininger, Maximilian
PY - 2022
DA - 2022/11/01
PB - Elsevier
SP - 104885
VL - 289
SN - 0890-5401
SN - 1090-2651
ER -
Cite this
BibTex (up to 50 authors)
Copy
@article{2022_Křetínský,
author = {Jan Křetínský and Emanuel Ramneantu and Alexander Slivinskiy and Maximilian Weininger},
title = {Comparison of algorithms for simple stochastic games},
journal = {Information and Computation},
year = {2022},
volume = {289},
publisher = {Elsevier},
month = {nov},
url = {https://doi.org/10.1016/j.ic.2022.104885},
pages = {104885},
doi = {10.1016/j.ic.2022.104885}
}