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

Thomas Dueholm Hansen, Peter Bro Miltersen, Uri Zwick

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 con…