The Smoothed Complexity of Policy Iteration for Markov Decision Processes

Miranda Christ, Mihalis Yannakakis

We show subexponential lower bounds (i.e., $2^{\Omega (n^c)}$) on the smoothed complexity of the classical Howard's Policy Iteration algorithm for Markov Decision Processes. The bounds h…