Bandits with Abstention under Expert Advice
This work addresses a specific problem in online learning and bandit algorithms, offering incremental improvements for scenarios where abstention is allowed.
The paper tackles the problem of prediction with expert advice under bandit feedback by introducing an abstention action with no reward or loss, proposing the CBA algorithm that improves reward bounds over classical methods like Exp4 and SpecialistExp, with an efficient implementation reducing runtime from quadratic to almost linear in contextual settings.
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.