Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor

TY - GEN

T1 - Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor

AU - Hansen, Thomas Dueholm

AU - Miltersen, Peter Bro

AU - Zwick, Uri

PY - 2011

Y1 - 2011

N2 - Ye showed recently that the simplex method with Dantzig pivoting rule, as well as Howard's policy iteration algorithm, solve discounted Markov decision processes (MDPs), with a constant discount factor, in strongly polynomial time. More precisely, Ye showed that both algorithms terminate after at most О iterations, where n is the number of states, m is the total number of actions in the MDP, and 0 < γ < 1 is the discount factor. We improve Ye's analysis in two respects. First, we improve the bound given by Ye and show that Howard's policy iteration algorithm actually terminates after at most О iterations. Second, and more importantly, we show that the same bound applies to the number of iterations performed by the strategy iteration (or strategy improvement) algorithm, a generalization of Howard's policy iteration algorithm used for solving 2-player turn-based stochastic games with discounted zero-sum rewards. This provides the first strongly polynomial algorithm for solving these games, resolving a long standing open problem.

AB - Ye showed recently that the simplex method with Dantzig pivoting rule, as well as Howard's policy iteration algorithm, solve discounted Markov decision processes (MDPs), with a constant discount factor, in strongly polynomial time. More precisely, Ye showed that both algorithms terminate after at most О iterations, where n is the number of states, m is the total number of actions in the MDP, and 0 < γ < 1 is the discount factor. We improve Ye's analysis in two respects. First, we improve the bound given by Ye and show that Howard's policy iteration algorithm actually terminates after at most О iterations. Second, and more importantly, we show that the same bound applies to the number of iterations performed by the strategy iteration (or strategy improvement) algorithm, a generalization of Howard's policy iteration algorithm used for solving 2-player turn-based stochastic games with discounted zero-sum rewards. This provides the first strongly polynomial algorithm for solving these games, resolving a long standing open problem.

M3 - Article in proceedings

SN - 978-7-302-24517-9

SP - 253

EP - 263

BT - Proceedings of the Second Symposium on Innovations in Computer Science

PB - Tsinghua University Press, Beijing

T2 - Innovations in Computer Science. ICS 2011

Y2 - 6 January 2011 through 9 January 2011

ER -