On the complexity of Policy Iteration (for deterministic problems)

Policy Iteration is an algorithm that is very efficient in practice for solving discrete-time optimal control problems. Until the recent works of Ye (2012) and Post & Ye (2013), the reasons of its efficiency were essentially mysterious. I will present this algorithm, and some of the state of the art results concerning its complexity. I will end by describing small progress on a question that is still open: the complexity of this algorithm for determinisitc problems (the best lower bound is quadratic, while the best upper bound is exponential).