Regret Minimization for Online Buffering Problems

Speaker

Melanie Winkler
Title Regret Minimization for Online Buffering Problems
When 20.05.2010, 15:00
Where Seminarraum Informatik 11
Abstract Suppose a decision maker has to purchase a commodity with varying prices and demands over time. The price per unit might depend on the amount purchased and this price function might vary from step to step. The decision maker is given a buffer of bounded size, which can be used to safe units which are used to satisfy demands at later points in time. This kind of problem occurs in many applications, for example battery management in hybrid cars and economical caching policies for mobile devices. A simplified ed but illustrative example is a frugal car driver thinking about at which occasion to buy which amount of gasoline.

We study this problem by using online learning algorithms. An online learning algorithm is given a set of n experts which solve the problem. The algorithm can choose one of the experts strategies in every point of time. The objective is that the algorithms achieves cost which are not much higher than that of the best expert chosen in hindsight. The difference between the cost of the online algorithm and those of the best expert is called regret. Hence, we want to minimize the regret of the online algorithm.
Slides