License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2019.9
URN: urn:nbn:de:0030-drops-102488
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10248/
Go to the corresponding LIPIcs Volume Portal

Auger, David ; Coucheney, Pierre ; Strozecki, Yann

Solving Simple Stochastic Games with Few Random Nodes Faster Using Bland's Rule

pdf-format:
LIPIcs-STACS-2019-9.pdf (0.5 MB)

Abstract

The best algorithm so far for solving Simple Stochastic Games is Ludwig's randomized algorithm [Ludwig, 1995] which works in expected 2^{O(sqrt{n})} time. We first give a simpler iterative variant of this algorithm, using Bland's rule from the simplex algorithm, which uses exponentially less random bits than Ludwig's version. Then, we show how to adapt this method to the algorithm of Gimbert and Horn [Gimbert and Horn, 2008] whose worst case complexity is O(k!), where k is the number of random nodes. Our algorithm has an expected running time of 2^{O(k)}, and works for general random nodes with arbitrary outdegree and probability distribution on outgoing arcs.

BibTeX - Entry

@InProceedings{auger_et_al:LIPIcs:2019:10248,
  author =	{David Auger and Pierre Coucheney and Yann Strozecki},
  title =	{{Solving Simple Stochastic Games with Few Random Nodes Faster Using Bland's Rule}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{9:1--9:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Rolf Niedermeier and Christophe Paul},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10248},
  doi =		{10.4230/LIPIcs.STACS.2019.9},
  annote =	{Keywords: simple stochastic games, randomized algorithm, parametrized complexity, strategy improvement, Bland's rule}
}

Keywords: simple stochastic games, randomized algorithm, parametrized complexity, strategy improvement, Bland's rule
Collection: 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Issue Date: 2019
Date of publication: 12.03.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI