  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 hold for the total reward and the average
reward criteria. The constructions are robust in the sense that the
subexponential bound holds not only on the average for independent random
perturbations of the MDP parameters (transition probabilities and rewards), but
for all arbitrary perturbations within an inverse polynomial range. We show
also an exponential lower bound on the worst-case complexity for the simple
reachability objective.

Computational Complexity;Computer Science and Game Theory