A unified worst case for classical simplex and policy iteration pivot rules

Yann Disser, Nils Mosis

We construct a family of Markov decision processes for which the policy iteration algorithm needs an exponential number of improving switches with Dantzig's rule, with Bland's rule…