Solving Simple Stochastic Games with Few Coin Toss Positions

Rasmus Ibsen-Jensen; Peter Bro Miltersen

doi:10.1007/978-3-642-33090-2_55

Solving Simple Stochastic Games with Few Coin Toss Positions

Rasmus Ibsen-Jensen, Peter Bro Miltersen

Institut for Datalogi

Publikation: Bidrag til tidsskrift/Konferencebidrag i tidsskrift /Bidrag til avis › Konferenceartikel › Forskning › peer review

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 4 r n O(1). In this paper, we show that an algorithm combining value iteration with retrograde analysis achieves a time bound of O(r 2 r (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 2 r n O(1)

Originalsprog	Engelsk
Bogserie	Lecture Notes in Computer Science
Vol/bind	7501
Sider (fra-til)	636-647
Antal sider	12
ISSN	0302-9743
DOI	https://doi.org/10.1007/978-3-642-33090-2_55
Status	Udgivet - 2012
Begivenhed	Annual European Symposium Algorithms - Ljubljana, Slovenien Varighed: 10 sep. 2012 → 12 dec. 2012 Konferencens nummer: 20

Konference

Konference	Annual European Symposium Algorithms
Nummer	20
Land/Område	Slovenien
By	Ljubljana
Periode	10/09/2012 → 12/12/2012

Adgang til dokumentet

10.1007/978-3-642-33090-2_55

Citationsformater

@inproceedings{d4ddc376f16446b2b2d6393995fdbdab,

title = "Solving Simple Stochastic Games with Few Coin Toss Positions",

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 4 r n O(1). In this paper, we show that an algorithm combining value iteration with retrograde analysis achieves a time bound of O(r 2 r (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 2 r n O(1)",

author = "Rasmus Ibsen-Jensen and Miltersen, {Peter Bro}",

note = "Title of the vol.: Algorithms – ESA 2012 : 20th Annual European Symposium, Ljubljana, Slovenia, September 10-12, 2012. Proceedings / ed. by Leah Epstein, Paolo Ferragina. ISBN: 978-3-642-33089-6, 978-3-642-33090-2; Annual European Symposium Algorithms, ESA ; Conference date: 10-09-2012 Through 12-12-2012",

year = "2012",

doi = "10.1007/978-3-642-33090-2_55",

language = "English",

volume = "7501",

pages = "636--647",

journal = "Lecture Notes in Computer Science",

issn = "0302-9743",

publisher = "Springer",

}

TY - GEN

T1 - Solving Simple Stochastic Games with Few Coin Toss Positions

AU - Ibsen-Jensen, Rasmus

AU - Miltersen, Peter Bro

N1 - Conference code: 20

PY - 2012

Y1 - 2012

N2 - 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 4 r n O(1). In this paper, we show that an algorithm combining value iteration with retrograde analysis achieves a time bound of O(r 2 r (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 2 r n O(1)

AB - 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 4 r n O(1). In this paper, we show that an algorithm combining value iteration with retrograde analysis achieves a time bound of O(r 2 r (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 2 r n O(1)

U2 - 10.1007/978-3-642-33090-2_55

DO - 10.1007/978-3-642-33090-2_55

M3 - Conference article

SN - 0302-9743

VL - 7501

SP - 636

EP - 647

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

T2 - Annual European Symposium Algorithms

Y2 - 10 September 2012 through 12 December 2012

ER -

Solving Simple Stochastic Games with Few Coin Toss Positions

Abstract

Konference

Adgang til dokumentet

Fingeraftryk

Citationsformater