# Online Learning with Abstention

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

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Mar 2017.

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

- [Machine Learning with a Reject Option: A survey](https://mlsanity.com/paper/2107.11277/) (2021)
- [Towards Unbiased and Accurate Deferral to Multiple Experts](https://mlsanity.com/paper/2102.13004/) (2021)
- [Knowing the No-match: Entity Alignment with Dangling Cases](https://mlsanity.com/paper/2106.02248/) (2021)
- [Measuring and Improving Model-Moderator Collaboration using Uncertainty Estimation](https://mlsanity.com/paper/2107.04212/) (2021)
- [Learning Personalized Decision Support Policies](https://mlsanity.com/paper/2304.06701/) (2023)
- [Split-kl and PAC-Bayes-split-kl Inequalities for Ternary Random Variables](https://mlsanity.com/paper/2206.00706/) (2022)
- [Adversarial Resilience in Sequential Prediction via Abstention](https://mlsanity.com/paper/2306.13119/) (2023)
- [Cascaded Language Models for Cost-effective Human-AI Decision-Making](https://mlsanity.com/paper/2506.11887/) (2025)
- [Reliable learning in challenging environments](https://mlsanity.com/paper/2304.03370/) (2023)
- [Online Selective Classification with Limited Feedback](https://mlsanity.com/paper/2110.14243/) (2021)
- [Confidence-aware Contrastive Learning for Selective Classification](https://mlsanity.com/paper/2406.04745/) (2024)
- [When Should We Orchestrate Multiple Agents?](https://mlsanity.com/paper/2503.13577/) (2025)
- [Online Decision Mediation](https://mlsanity.com/paper/2310.18601/) (2023)
- [Neural Pseudo-Label Optimism for the Bank Loan Problem](https://mlsanity.com/paper/2112.02185/) (2021)
- [Stochastic Online Learning with Feedback Graphs: Finite-Time and Asymptotic Optimality](https://mlsanity.com/paper/2206.10022/) (2022)
- [Bandits with Abstention under Expert Advice](https://mlsanity.com/paper/2402.14585/) (2024)
- [Adversarial Online Learning with Temporal Feedback Graphs](https://mlsanity.com/paper/2407.00571/) (2024)
- [Reliable Abstention under Adversarial Injections: Tight Lower Bounds and New Upper Bounds](https://mlsanity.com/paper/2602.20111/) (2026)
- [Online Learning with Sublinear Best-Action Queries](https://mlsanity.com/paper/2407.16355/) (2024)
- [Learning to Help in Multi-Class Settings](https://mlsanity.com/paper/2501.13810/) (2025)
- [Asymptotically and Minimax Optimal Regret Bounds for Multi-Armed Bandits with Abstention](https://mlsanity.com/paper/2402.15127/) (2024)
- [Safe Learning Under Irreversible Dynamics via Asking for Help](https://mlsanity.com/paper/2502.14043/) (2025)
- [Online Learning-to-Defer with Varying Experts](https://mlsanity.com/paper/2605.12340/) (2026)
- [Online Learning with LLM Experts from Limited Feedback](https://mlsanity.com/paper/2609.05820/) (2026)
- [Active learning with biased non-response to label requests](https://mlsanity.com/paper/2312.08150/) (2023)
- [Online Prediction with Limited Selectivity](https://mlsanity.com/paper/2508.09592/) (2025)
- [Policy Learning with Abstention](https://mlsanity.com/paper/2510.19672/) (2025)
- [Online Convex Optimization with Sublinear Noisy Probes](https://mlsanity.com/paper/2606.14640/) (2026)

## Abstract (arXiv)

We present an extensive study of the key problem of online learning where algorithms are allowed to abstain from making predictions. In the adversarial setting, we show how existing online algorithms and guarantees can be adapted to this problem. In the stochastic setting, we first point out a bias problem that limits the straightforward extension of algorithms such as UCB-N to time-varying feedback graphs, as needed in this context. Next, we give a new algorithm, UCB-GT, that exploits historical data and is adapted to time-varying feedback graphs. We show that this algorithm benefits from more favorable regret guarantees than a possible, but limited, extension of UCB-N. We further report the results of a series of experiments demonstrating that UCB-GT largely outperforms that extension of UCB-N, as well as more standard baselines.