CS Colloquium- Even-Dar

Title:Limitations and Challenges in No Regret AlgorithmsEyal Even-DarUniversity of PennsylvaniaAbstract:No regret algorithms have been studied extensively since the pioneering works of Blackwell, Hannan and Robbins in 1950s. In a sequential decision making problem where you are given an advice by N experts at each time step, the no regret algorithms guarantee that you will always do almost as good as the best expert in hindsight. Equipped with such strong theoretical guarantee, no regret algorithms have been applied successfully in many fields including machine learning, economics and game theory.In this talk I will present several challenges to and limitations of no regret algorithms. More specifically, I will consider adding natural constraints and adapting no regret algorithms to dynamic environments. Such scenarios will shed a light on how far these algorithms can be "pushed", while still satisfying the no regret property. Finally, I will consider a routing game where all users use no regret algorithms, and study the efficiency and the stability of such game.Biography:Eyal Even-Dar received his Ph.D. from Tel Aviv University in
2005 and is currently a postdoctoral fellow at the University of Pennsylvania. His interests include computational learning theory, machine learning, game theory and their intersection.Hosted by David KempeRefreshments will be served.

Location: Seaver Science Library (SSL) - 150

Audiences: Everyone Is Invited

Contact: Nancy Levien