Wednesday, September 5, 2012

Hedging when the Number of Good Experts is Small

In many of the online decision making algorithms such as Weighted Majority and Hedge algorithms, we treat all the experts in a same way and the regret bounds are dependent on the number of experts. But in many applications, we know that the number of good experts (i.e., experts with small cumulative loss) is small or experts have similar behavior such that we can group them in a small number of expert groups. Then, this question arises that can we bound the regret in terms of number of the good experts or the number of clusters of experts. Although in full information setting the regret bound depends logarithmically on the number of experts, having bound with logarithmic dependence on the number of good experts makes a significant improvement in applications with combinatorial structure or exponential number of decisions.