         
|
GRASP Lab Seminar 2004-2005
December 10, 11:00 AM, Levine Hall 307.
Laurent
El Ghaoui
EECS, Berkeley
The Curse of Uncertainty in Dynamic Programming, and How to Fix It.
Abstract: Optimal solutions to Markov decision problems may be very sensitive with respect to the state transition probabilities. In many practical problems, the estimation of these probabilities is far from accurate. Hence, estimation errors are limiting factors in applying Markov decision processes to real-world problems. We consider a robust control problem for a finite-state, finite-action Markov decision process, where uncertainty on the transition matrices is described in terms of possibly non-convex sets. We show that perfect duality holds for this problem, and that as a consequence, it can be solved with a variant of the classical dynamic programming algorithm, the "robust dynamic programming" algorithm. We show that a particular choice of the uncertainty sets, involving likelihood regions or entropy bounds, leads to both a statistically accurate representation of uncertainty, and a complexity of the robust recursion that is almost the same as that of the classical recursion. Hence, robustness can be added at practically no extra computing cost. We derive similar results for other uncertainty sets, including one with a finite number of possible values for the transition matrices. We describe in a practical path planning example the benefits of using a robust strategy instead of the classical optimal strategy; even if the uncertainty level is only crudely guessed, the robust strategy yields a much better worst-case expected travel time. (Joint work with A.Nilim)
Biography: Laurent El Ghaoui graduated from Ecole Polytechnique (Palaiseau, France) in 1985, and obtained his PhD in Aeronautics and Astronautics at Stanford University in March 1990. He was a faculty member of the Ecole Nationale Superieure de Techniques Avancees (Paris, France) from 1992 until 1999, and held part-time teaching appointments at Ecole Polytechnique within the Applied Mathematics department and Universite de Paris-I (La Sorbonne) in the Mathematics in Economy program. In 1998, he was awarded the Bronze Medal for Engineering Sciences, from the Centre National de la Recherche Scientifique, France. He joined the Berkeley faculty in April 1999 as an Acting Associate Professor, and obtained his tenure in May 2001. He obtained the Career Award in April 2001. Since July 2003, he has been on industrial leave with SAC Capital Management, a company based in New York, NY and Stamford, CT.
