Another sub-exponential algorithm for the simple stochastic game

DOI10.1007/S00453-010-9413-1MaRDI QIDQ652540zbMATH OpenOpenAlexFDO

Authors Decheng Dai, Rong Ge

Publication date 14 December 2011

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-010-9413-1

zbMATH Keywords

subexponential algorithmsimple stochastic game

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Stochastic games, stochastic differential games (91A15)

Recommendations

• New results on simple stochastic games
• A subexponential randomized algorithm for the simple stochastic game problem
• Simple Stochastic Games with Few Random Vertices Are Easy to Solve
• scientific article; zbMATH DE number 549853
• Solving Simple Stochastic Games

Cites work

• scientific article; zbMATH DE number 549853 (Why is no real title available?)
• A subexponential randomized algorithm for the simple stochastic game problem
• New algorithms for solving simple stochastic games
• Solving Simple Stochastic Games
• Stochastic Games
• The complexity of stochastic games

Cited in

(15)

• New results on simple stochastic games
• A subexponential randomized algorithm for the simple stochastic game problem
• Simple Stochastic Games with Few Random Vertices Are Easy to Solve
• Value iteration for simple stochastic games: stopping criterion and learning algorithm
• New algorithms for solving simple stochastic games
• scientific article; zbMATH DE number 549853 (Why is no real title available?)
• An improved heuristic for the ``Ulam-Rényi game
• Comparison of algorithms for simple stochastic games
• Comparison of algorithms for simple stochastic games
• Solving Simple Stochastic Games
• On strategy improvement algorithms for simple stochastic games
• On strategy improvement algorithms for simple stochastic games
• Solving simple stochastic games with few coin toss positions
• Approximation schemes for stochastic mean payoff games with perfect information and few random positions
• Stochastic limit-average games are in EXPTIME

This page was built for publication: Another sub-exponential algorithm for the simple stochastic game

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q652540)