Regret to the Best vs. Regret to the Average
par/by Eyal Even-dar
Computer and Information Science Department
University of Pennsylvania
We study online regret minimization algorithms in a bicriteria
setting, examining not only the standard notion of regret to the best
expert, but also the regret to the average of all experts, the regret
to any fixed mixture of experts, and the regret to the worst expert.
This study leads both to new understanding of the limitations of
existing no-regret algorithms, and to new algorithms with novel
performance guarantees. More specifically, we show that _any_
algorithm that achieves only O(T^(1/2)) regret to the best expert
on a sequence of T trials must, in the worst case, suffer regret
Omega(T^(1/2)) to the average, and that for a wide class of update
rules that includes many existing no-regret algorithms (such as
Exponential Weights and Follow the Perturbed Leader), the product of
the regret to the best and the regret to the average is
Omega(T). We then describe and analyze a new multi-phase algorithm,
which achieves cumulative regret only O(T^(1/2) log T) to the best
expert and has only _constant_ regret to any fixed distribution
over experts (that is, with no dependence on either T or the number
of experts N). The key to the new algorithm is the gradual increase
in the ``aggressiveness'' of updates in response to observed
divergences in expert performances.
Joint work with Michael Kearns, Yishay Mansour and Jennifer Wortman