New results on simple stochastic games
Publication
, Journal Article
Dai, D; Ge, R
Published in: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
December 1, 2009
We study the problem of solving simple stochastic games, and give both an interesting new algorithm and a hardness result. We show a reduction from fine approximation of simple stochastic games to coarse approximation of a polynomial sized game, which can be viewed as an evidence showing the hardness to approximate the value of simple stochastic games. We also present a randomized algorithm that runs in time, where is the number of RANDOM vertices and ignores polynomial terms. This algorithm is the fastest known algorithm when and and it works for general (non-stopping) simple stochastic games. © 2009 Springer-Verlag Berlin Heidelberg.
Duke Scholars
Published In
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
DOI
EISSN
1611-3349
ISSN
0302-9743
Publication Date
December 1, 2009
Volume
5878 LNCS
Start / End Page
1014 / 1023
Related Subject Headings
- Artificial Intelligence & Image Processing
- 46 Information and computing sciences
Citation
APA
Chicago
ICMJE
MLA
NLM
Dai, D., & Ge, R. (2009). New results on simple stochastic games. Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 5878 LNCS, 1014–1023. https://doi.org/10.1007/978-3-642-10631-6_102
Dai, D., and R. Ge. “New results on simple stochastic games.” Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 5878 LNCS (December 1, 2009): 1014–23. https://doi.org/10.1007/978-3-642-10631-6_102.
Dai D, Ge R. New results on simple stochastic games. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2009 Dec 1;5878 LNCS:1014–23.
Dai, D., and R. Ge. “New results on simple stochastic games.” Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5878 LNCS, Dec. 2009, pp. 1014–23. Scopus, doi:10.1007/978-3-642-10631-6_102.
Dai D, Ge R. New results on simple stochastic games. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2009 Dec 1;5878 LNCS:1014–1023.
Published In
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
DOI
EISSN
1611-3349
ISSN
0302-9743
Publication Date
December 1, 2009
Volume
5878 LNCS
Start / End Page
1014 / 1023
Related Subject Headings
- Artificial Intelligence & Image Processing
- 46 Information and computing sciences