Name
Abstract | ||
|---|---|---|
Gimbert and Horn gave an algorithm for solving simple stochastic games with running time O(r! n) where n is the number of positions of the simple stochastic game and r is the number of its coin toss positions. Chatterjee et al. pointed out that a variant of strategy iteration can be implemented to solve this problem in time 4rnO(1). In this paper, we show that an algorithm combining value iteration with retrograde analysis achieves a time bound of O(r 2r (r logr+n)), thus improving both time bounds. We also improve the analysis of Chatterjee et al. and show that their algorithm in fact has complexity 2rnO(1). |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/978-3-642-33090-2_55 | european symposium on algorithms |
Keywords | DocType | Volume |
time bound,time o,value iteration,retrograde analysis,simple stochastic game,strategy iteration | Conference | abs/1112.5255 |
ISSN | Citations | PageRank |
0302-9743 | 5 | 0.57 |
References | Authors | |
9 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Rasmus Ibsen-Jensen | 1 | 69 | 12.65 |
| Peter Bro Miltersen | 2 | 1146 | 94.49 |