# Bandits with Abstention under Expert Advice

arXiv: https://arxiv.org/abs/2402.14585 · HTML: https://mlsanity.com/paper/2402.14585/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 41 references that are in the map.
- First posted on arXiv 22 Feb 2024.

## Builds on (most cited first, 12 of 12)

- [Machine Learning with a Reject Option: A survey](https://mlsanity.com/paper/2107.11277/) (2021)
- [A Second-order Bound with Excess Losses](https://mlsanity.com/paper/1402.2044/) (2014)
- [A Gang of Bandits](https://mlsanity.com/paper/1306.0811/) (2013)
- [Online Learning with Abstention](https://mlsanity.com/paper/1703.03478/) (2017)
- [Classification with abstention but without disparities](https://mlsanity.com/paper/2102.12258/) (2021)
- [Fast Rates for Online Prediction with Abstention](https://mlsanity.com/paper/2001.10623/) (2020)
- [Exact Recovery of Clusters in Finite Metric Spaces Using Oracle Queries](https://mlsanity.com/paper/2102.00504/) (2021)
- [A Survey on the Densest Subgraph Problem and Its Variants](https://mlsanity.com/paper/2303.14467/) (2023)
- [Faster unfolding of communities: speeding up the Louvain algorithm](https://mlsanity.com/paper/1503.01322/) (2015)
- [Nearest Neighbour with Bandit Feedback](https://mlsanity.com/paper/2306.13773/) (2023)
- [Multi-class Graph Clustering via Approximated Effective p-Resistance](https://mlsanity.com/paper/2306.08617/) (2023)
- [A Hierarchical Nearest Neighbour Approach to Contextual Bandits](https://mlsanity.com/paper/2312.09332/) (2023)

## Built on by (most cited first, 3 of 3)

- [Fairness with Exponential Weights](https://mlsanity.com/paper/2411.04295/) (2024)
- [Online Prediction with Limited Selectivity](https://mlsanity.com/paper/2508.09592/) (2025)
- [Policy Learning with Abstention](https://mlsanity.com/paper/2510.19672/) (2025)

## Abstract (arXiv)

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.