Regret to the best vs. regret to the average

摘要

O(T~(1/2) log T) to the best expert and have only constant regret to any given fixed distribution over experts (that is, with no dependence on either T or the number of experts TV). The key to the first algorithm is the gradual increase in the "aggressiveness" of updates in response to observed divergences in expert performances. The second algorithm is a simple twist on standard exponential-update algorithms.