# Efficient Online Set-valued Classification with Bandit Feedback

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 47 references that are in the map.
- First posted on arXiv 7 May 2024.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Distribution-Free Predictive Inference For Regression](https://mlsanity.com/paper/1604.04173/) (2016)
- [Conformalized Quantile Regression](https://mlsanity.com/paper/1905.03222/) (2019)
- [Conformal Prediction Under Covariate Shift](https://mlsanity.com/paper/1904.06019/) (2019)
- [Classification with Valid and Adaptive Coverage](https://mlsanity.com/paper/2006.02544/) (2020)
- [Adaptive Conformal Inference Under Distribution Shift](https://mlsanity.com/paper/2106.00170/) (2021)
- [Uncertainty Sets for Image Classifiers using Conformal Prediction](https://mlsanity.com/paper/2009.14193/) (2020)
- [Least Ambiguous Set-Valued Classifiers with Bounded Error Levels](https://mlsanity.com/paper/1609.00451/) (2016)
- [Adaptive Conformal Predictions for Time Series](https://mlsanity.com/paper/2202.07282/) (2022)
- [Conformal Inference for Online Prediction with Arbitrary Distribution Shifts](https://mlsanity.com/paper/2208.08401/) (2022)
- [Class-Conditional Conformal Prediction with Many Classes](https://mlsanity.com/paper/2306.09335/) (2023)
- [A Conformal Prediction Approach to Explore Functional Data](https://mlsanity.com/paper/1302.6452/) (2013)
- [Improved Online Conformal Prediction via Strongly Adaptive Online Learning](https://mlsanity.com/paper/2302.07869/) (2023)
- [Neural Contextual Bandits with Deep Representation and Shallow Exploration](https://mlsanity.com/paper/2012.01780/) (2020)
- [Classification with Rejection Based on Cost-sensitive Classification](https://mlsanity.com/paper/2010.11748/) (2020)
- [Prediction and outlier detection in classification problems](https://mlsanity.com/paper/1905.04396/) (2019)
- [Cautious Deep Learning](https://mlsanity.com/paper/1805.09460/) (2018)
- [MOTS: Minimax Optimal Thompson Sampling](https://mlsanity.com/paper/2003.01803/) (2020)
- [Bayesian Optimization with Conformal Prediction Sets](https://mlsanity.com/paper/2210.12496/) (2022)
- [Conformal Off-Policy Prediction in Contextual Bandits](https://mlsanity.com/paper/2206.04405/) (2022)
- [Contextual Recommendations and Low-Regret Cutting-Plane Algorithms](https://mlsanity.com/paper/2106.04819/) (2021)
- [Beyond Bandit Feedback in Online Multiclass Classification](https://mlsanity.com/paper/2106.03596/) (2021)
- [Conformal Off-policy Prediction](https://mlsanity.com/paper/2206.06711/) (2022)
- [On Reject and Refine Options in Multicategory Classification](https://mlsanity.com/paper/1701.02265/) (2017)
- [Learning Confidence Sets using Support Vector Machines](https://mlsanity.com/paper/1809.10818/) (2018)

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

- [Online Conformal Prediction with Adversarial Semi-bandit Feedback via Regret Minimization](https://mlsanity.com/paper/2604.17984/) (2026)
- [Online Conformal Prediction Beyond Feedback](https://mlsanity.com/paper/2608.07139/) (2026)
- [Efficient Online Conformal Selection with Limited Feedback](https://mlsanity.com/paper/2605.14953/) (2026)

## Abstract (arXiv)

Conformal prediction is a distribution-free method that wraps a given machine learning model and returns a set of plausible labels that contain the true label with a prescribed coverage rate. In practice, the empirical coverage achieved highly relies on fully observed label information from data both in the training phase for model fitting and the calibration phase for quantile estimation. This dependency poses a challenge in the context of online learning with bandit feedback, where a learner only has access to the correctness of actions (i.e., pulled an arm) but not the full information of the true label. In particular, when the pulled arm is incorrect, the learner only knows that the pulled one is not the true class label, but does not know which label is true. Additionally, bandit feedback further results in a smaller labeled dataset for calibration, limited to instances with correct actions, thereby affecting the accuracy of quantile estimation. To address these limitations, we propose Bandit Class-specific Conformal Prediction (BCCP), offering coverage guarantees on a class-specific granularity. Using an unbiased estimation of an estimand involving the true label, BCCP trains the model and makes set-valued inferences through stochastic gradient descent. Our approach overcomes the challenges of sparsely labeled data in each iteration and generalizes the reliability and applicability of conformal prediction to online decision-making environments.