The simplex method is strongly polynomial for deterministic Markov decision processes.

Ian Post, Yinyu Ye

Browse the full SODA paper archive.