On strategy improvement algorithms for simple stochastic games

D. Andersson, Extending Friedmannʼs lower bound to the Hoffman–Karp algorithm, preprint, June 2009. Condon, 1992, The complexity of stochastic games, Information and Computation, 96, 203, 10.1016/0890-5401(92)90048-K Condon, 1993, On algorithms for simple stochastic games, 51 Derman, 1970, Finite State Markov Decision Processes, vol. 67 Friedmann, 2009, An exponential lower bound for the parity game strategy improvement algorithm as we know it, 145 Gimbert, 2009, Solving simple stochastic games with few random vertices, Logical Methods in Computer Science, 5, 1, 10.2168/LMCS-5(2:9)2009 E. Grädel, T. Wolfgang, Automata, Logics, and Infinite Games, Lecture Notes in Computer Science, vol. 2500, 2002. Halman, 2007, Simple stochastic games, parity games, mean payoff games and discounted payoff games are all LP-type problems, Algorithmica, 49, 37, 10.1007/s00453-007-0175-3 Hoffman, 1966, On nonterminating stochastic games, Management Science, 12, 359, 10.1287/mnsc.12.5.359 Howard, 1960 B. Juba, On the hardness of simple stochastic games, Masterʼs thesis, Carnegie Mellon University, 2005. Jukna, 2001 Ludwig, 1995, A subexponential randomized algorithm for the simple stochastic game problem, Information and Computation, 117, 151, 10.1006/inco.1995.1035 Melekopoglou, 1994, On the complexity of the policy improvement algorithm for Markov decision processes, ORSA Journal of Computing, 6, 188, 10.1287/ijoc.6.2.188 Mansour, 1999, On the complexity of Policy Iteration, 401 Poon, 2003, Verifying minimal stable circuit values, Information Processing Letters, 86, 27, 10.1016/S0020-0190(02)00453-2 A. Puri, Theory of hybrid systems and discrete event systems, PhD thesis, EECS, University of Berkley, 1995. Shapley, 1953, Stochastic games, Proceedings of National Academy of Sciences (U.S.A.), 39, 1095, 10.1073/pnas.39.10.1095 Somla, 2005, New algorithms for solving simple stochastic games, Electronic Notes in Theoretical Computer Science, 119, 51, 10.1016/j.entcs.2004.07.008 Tripathi, 2010, On strategy improvement algorithms for simple stochastic games, vol. 6078, 240 Vöge, 2000, A discrete strategy improvement algorithm for solving parity games, vol. 1855, 202 Zwick, 1996, The complexity of mean payoff games on graphs, Theoretical Computer Science, 158, 343, 10.1016/0304-3975(95)00188-3