Bandits with Abstention under Expert Advice
Stephen Pasteris Alberto Rumi Maximilian Thiessen Shota Saito Atsushi Miyauchi Fabio Vitale Mark Herbster
We study the classic problem of prediction with expert advice under bandit
feedback. Our model assumes that one action, corresponding to the learner's
abstention from play, has no reward or loss on every trial. We propose the CBA
algorithm, which exploits this assumption to obtain reward bounds that can
significantly improve those of the classical Exp4 algorithm. We can view our
problem as the aggregation of confidence-rated predictors when the learner has
the option of abstention from play. Importantly, we are the first to achieve
bounds on the expected cumulative reward for general confidence-rated
predictors. In the special case of specialists we achieve a novel reward bound,
significantly improving previous bounds of SpecialistExp (treating abstention
as another action). As an example application, we discuss learning unions of
balls in a finite metric space. In this contextual setting, we devise an
efficient implementation of CBA, reducing the runtime from quadratic to almost
linear in the number of contexts. Preliminary experiments show that CBA
improves over existing bandit algorithms.