On discounted approximations of undiscounted stochastic games and Markov decision processes with limited randomness

DOI10.1016/j.orl.2013.04.006zbMath1286.91019OpenAlexW1984782272WikidataQ59560516 ScholiaQ59560516MaRDI QIDQ2450666

Endre Boros, Kazuhisa Makino, Khaled M. Elbassioni, Vladimir A. Gurvich

Publication date: 14 May 2014

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2013.04.006

zbMATH Keywords

Markov decision processessaddle pointzero-sum stochastic gamesdiscounted stochastic gamespseudo-polynomial algorithms

Mathematics Subject Classification ID

2-person games (91A05) Stochastic games, stochastic differential games (91A15) Markov and semi-Markov decision processes (90C40)

Related Items (2)

A potential reduction algorithm for two-person zero-sum mean payoff stochastic games ⋮ A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On canonical forms for zero-sum stochastic mean payoff games
• Positional strategies for mean payoff games
• The complexity of stochastic games
• Extensions of two person zero sum games
• A characterization of the minimum cycle mean in a digraph
• The complexity of mean payoff games on graphs
• Simple stochastic games, parity games, mean payoff games and discounted payoff games are all LP-type problems
• Mean Cost Cyclical Games
• Cyclic games and an algorithm to find minimax cycle means in directed graphs
• A Pumping Algorithm for Ergodic Stochastic Mean Payoff Games with Perfect Information
• The Complexity of Solving Stochastic Games on Graphs
• Simple Stochastic Games with Few Random Vertices Are Easy to Solve
• On Nonterminating Stochastic Games
• Stochastic Games with Perfect Information and Time Average Payoff

This page was built for publication: On discounted approximations of undiscounted stochastic games and Markov decision processes with limited randomness