  Conformal prediction has emerged as an effective strategy for uncertainty
quantification by modifying a model to output sets of labels instead of a
single label. These prediction sets come with the guarantee that they contain
the true label with high probability. However, conformal prediction typically
requires a large calibration dataset of i.i.d. examples. We consider the online
learning setting, where examples arrive over time, and the goal is to construct
prediction sets dynamically. Departing from existing work, we assume
semi-bandit feedback, where we only observe the true label if it is contained
in the prediction set. For instance, consider calibrating a document retrieval
model to a new domain; in this setting, a user would only be able to provide
the true label if the target document is in the prediction set of retrieved
documents. We propose a novel conformal prediction algorithm targeted at this
setting, and prove that it obtains sublinear regret compared to the optimal
conformal predictor. We evaluate our algorithm on a retrieval task and an image
classification task, and demonstrate that it empirically achieves good
performance.
