The simplex method is strongly polynomial for deterministic Markov decision processes

Ian Post, Yinyu Ye

We prove that the simplex method with the highest gain/most-negative-reduced cost pivoting rule converges in strongly polynomial time for deterministic Markov decision processes (M…