Randomized Weighted Majority in the Continuous Setting


Sascha Geulen (Informatik 1)

Title Randomized Weighted Majority in the Continuous Setting
When 20.04.2011, 10:00
Where Room 5052
Abstract In online learning, given a set of strategies, a decision maker has to follow at each time step the decision of one strategy. The aim of an online learning algorithm is to minimize the cost difference between the decision maker and the best strategy chosen in hindsight, the so-called regret. A well-known algorithm for this problem is the Randomized Weighted Majority Algorithm, whose regret per time step converges against zero.

Unfortunately, in many situations the restriction to a discrete set of strategies prevents an online learning algorithm from achieving reasonable results. But, if some informations about the cost functions are known, our approach can find a discretization, for which an online learning algorithm can achieve nearly optimal costs.