Seminar Details
2013-04-16 (14.00) : Policy Iteration has exponential complexity for solving Markov Decision Processes. But there is more to the story...
At Euler building
Organized by Mathematical Engineering
Speaker :
Hollanders, Romain
Abstract :
Many decision problems can be formulated as Markov Decision Processes and solved efficiently using the Policy Iteration algorithm, an algorithm
that is closely related to the simplex algorithm for Linear Programming.
Efficiently... unfortunately only in practice since it has been shown, like the simplex algorithm, to require an exponential number of steps to
converge in the worst case. However, the story does not end here. In this talk, we highlight particular problem structures for which Policy
Iteration is guaranteed to converge in polynomial time. We also propose an elegant combinatorial problem whose solution would provide tighter upper
bounds on the real worst case complexity of Policy Iteration.