No Regret Bound for Extreme Bandits
  Algorithms for hyperparameter optimization abound, all of which work well
under different and often unverifiable assumptions. Motivated by the general
challenge of sequentially choosing which algorithm to use, we study the more
specific task of choosing among distributions to use for random hyperparameter
optimization. This work is naturally framed in the extreme bandit setting,
which deals with sequentially choosing which distribution from a collection to
sample in order to minimize (maximize) the single best cost (reward). Whereas
the distributions in the standard bandit setting are primarily characterized by
their means, a number of subtleties arise when we care about the minimal cost
as opposed to the average cost. For example, there may not be a well-defined
"best" distribution as there is in the standard bandit setting. The best
distribution depends on the rewards that have been obtained and on the
remaining time horizon. Whereas in the standard bandit setting, it is sensible
to compare policies with an oracle which plays the single best arm, in the
extreme bandit setting, there are multiple sensible oracle models. We define a
sensible notion of "extreme regret" in the extreme bandit setting, which
parallels the concept of regret in the standard bandit setting. We then prove
that no policy can asymptotically achieve no extreme regret.
