Online Class-specific Conformal Prediction with Diluted Bandit Feedback

Conformal prediction is a distribution-free framework that constructs prediction sets with prescribed coverage guarantees by calibrating scoring thresholds. Standard online calibration of these thresholds relies on observing the ground truth after each prediction, yet many deployed systems reveal far less: the learner observes only whether the true label falls in the prediction set without knowing which element is the truth, a setting called $\text{diluted bandit feedback}$. Such a binary signal conflates the contributions of every label in the prediction set, making class-specific credit assignment ambiguous when training a base model for scoring and calibrating the thresholds. To address this challenge, we propose an online algorithm for multi-class classification, Diluted-bandit Class-specific Conformal Prediction ($\text{DCCP}$), which displays a $\text{randomized}$ prediction set whose label inclusion probabilities are controlled by the learner. DCCP capitalizes on a designed estimator to recover an unbiased class-specific signal from the binary feedback alone. This signal trains the base model and calibrates the thresholds, dedicating the prediction set to covering the true label at a prescribed rate for each class. We provide a theoretical analysis for coverage and prediction set size, and evaluate both empirically relative to reference methods.