Stochastic Online Conformal Prediction with Semi-Bandit Feedback

## Abstract

Abstract 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, an image classification task, and an auction price-setting task, and demonstrate that it empirically achieves good performance compared to several baselines.

## 1 Introduction

Uncertainty quantification is an effective strategy for improving trustworthiness of machine learning models by providing users with a measure of confidence of each prediction to better inform their decisions. Conformal prediction [Vovk et al., , Tibshirani et al., , Park et al., , Bates et al., ] has emerged as a promising strategy for uncertainty quantification due to its ability to provide theoretical guarantees for arbitrary blackbox models. They modify a given blackbox model $f:\mathcal{X}\to\mathcal{Y}$ to a conformal predictor $C:\mathcal{X}\to 2^{\mathcal{Y}}$ that predicts sets of labels. In the batch setting, it does so by using a held-out *calibration dataset* to assess the accuracy of $f$; it constructs smaller prediction sets if $f$ is more accurate and larger ones otherwise. Then, conformal prediction guarantees that the true label is contained in the prediction set with high probability—i.e.,

$$ $\displaystyle\mathbb{P}[y^{*}\in C(x)]\geq\alpha,$ $$

where $\alpha$ is the desired coverage rate, and the probability is taken over the random sample $(x,y^{*})\sim D$ and the calibration dataset $Z=\{(x_{i},y_{i})\}_{i=1}^{n}\sim D^{n}$.

Traditional conformal prediction require the calibration set to consist of i.i.d. or exchangeable samples from the target distribution; furthermore, the calibration set may need to be large to obtain good performance. In many settings, such labeled data may not be easy to obtain. As a motivating setting, we consider a document retrieval problem, where the input $x$ might be a question and the goal is to retrieve a passage $y$ from a knowledge base such as Wikipedia that can be used to answer $x$; this strategy is known as retrieval-augmented question answering, and can mitigate issues such as hallucinations [Lewis et al., , Shuster et al., , Ji et al., ]. A common practice is to use a retrieval model trained on a large dataset in a different domain in a zero-shot manner; for instance, a user might use the dense passage retrieval (DPR) model [Karpukhin et al., ] directly on their own dataset without finetuning. Thus, labeled data from the target domain may not be available.

In this paper, we propose an online conformal prediction algorithm that sequentially constructs prediction sets $C_{t}$ as inputs $x_{t}$ are given. We consider semi-bandit feedback, where we only observe the true label $y_{t}^{*}$ if it is included in our prediction set (i.e., $y_{t}^{*}\in C_{t}$). Otherwise, we observe an indicator that $y_{t}^{*}\not\in C_{t}$, but do not observe $y_{t}^{*}$. In the document retrieval example, users might sequentially provide queries $x_{t}$ to the DPR model, and our algorithm responds with a prediction set $C_{t}$ of potentially relevant documents. Then, the user selects the ground truth document $y_{t}^{*}$ if it appears in this set, and indicates that their query was unsuccessful otherwise.

As in conformal prediction, we aim to ensure that we achieve the desired coverage rate $\alpha$ with high probability. Letting $C_{t}^{*}$ denote the optimal prediction sets (i.e., the prediction sets given infinite calibration data), our algorithm ensures that with high probability, $C_{t}^{*}\subseteq C_{t}$ on all time steps $t$. Since $C_{t}^{*}$ achieves the desired coverage rate with high probability, this property ensures $C_{t}$ does so as well.

A trivial solution is to always include all documents in the prediction set. However, this would be unhelpful for the user, who needs to manually examine all documents to identify the ground truth one. Thus, an additional goal is to minimize the prediction set size. Formally, we consider the optimal prediction set $C_{t}^{*}$ in the limit of infinite data, and consider a loss function encoding how much worse our prediction set $C_{t}$ is compared to $C_{t}^{*}$. Then, our algorithm ensures this loss goes to zero as sufficiently many samples become available—i.e., the prediction sets $C_{t}$ converge to the optimal ones $C_{t}^{*}$ over time. Formally, our algorithm guarantees sublinear regret of $\tilde{\mathcal{O}}(\sqrt{T})$.

Finally, we empirically evaluate our algorithm on three tasks: image classification, document retrieval, and setting reservation prices in auctions. Our experiments demonstrate that our algorithm generates prediction sets that converge to the optimal ones while maintaining the desired coverage rate. Moreover, our algorithm significantly outperforms three natural baselines; each baseline either achieves worse cumulative expected regret or does not satisfy the desired coverage rate.

Contributions.
We formalize and solve the problem of online conformal prediction with semi-bandit feedback. Our algorithm constructs compact prediction sets, ensuring high coverage probability. The algorithm also provides an efficient method for collecting large datasets that are expensive to label. Instead of asking the user to select the ground truth label from the set of all candidate labels, our approach only requires the user to select from a subset. This efficiency gain can be substantial when the label space is large. We assess the algorithm’s performance on image classification, document retrieval and reservation price-setting in auctions, showcasing its effectiveness in a wide variety of real world applications, which highlights the practical utility of our approach.

Related work.
Recent work has studied conformal prediction in the online setting [Gibbs and Candes, , Bastani et al., , Gibbs and Candès, , Angelopoulos et al., , ]. These approaches are motivated by conformal prediction for time series data, where the labels can shift in complex and potentially adversarial ways. As a consequence, they make very different assumptions. In particular, they allow for adversarial rather than i.i.d. assumptions; however, almost all of them assume that the ground truth label is observed at every step, regardless of whether it is contained in the prediction set. For example, the ACI algorithm proposed in Gibbs and Candes [] requires observing $y_{t}^{*}$ at every step since it is needed to update the quantile function $\hat{Q}_{t}(\cdot)$, which is needed to compute the prediction set $\hat{C}_{t}(\alpha_{t})$ as well as the loss and gradient update. As the authors point out, they do not need to update the quantile function at every step. However, the steps where they update $\hat{Q}_{t}$ cannot be chosen in a way that depends on $y_{t}^{*}$, since doing so would lead to a biased estimate of the quantile function. In our experiments, we demonstrate that in the semi-bandit feedback setting, updating $\hat{Q}_{t}$ when $y_{t}^{*}$ is in the prediction set can create such a bias that leads ACI to fail to achieve coverage.

Similarly, the SAOCP algorithm proposed by Bhatnagar et al. [] requires observing $y^{*}_{t}$ at every step to construct the prediction set $S_{t}=\inf\{s\in R:y^{*}_{t}\in\hat{C}_{t}(X_{t},s)\}$, which is then used to compute the loss and gradient, and the Conformal PID control algorithm proposed by Angelopoulos et al. [] uses $y^{*}_{t}$ to compute the score $s_{t}=s_{t}(x_{t},y^{*}_{t})$, which is needed to compute the gradient. In contrast, we are motivated by the active learning setting, where users are interested in constructing conformal predictors on-the-fly rather than providing a calibration set ahead-of-time. Thus, in our setting, it is reasonable to assume that the data arrives i.i.d.; however, we need to handle semi-bandit feedback since the user may be unable to provide the true label $y_{t}^{*}$ if it is not in the prediction set.

Recently, Angelopoulos et al. [] has pointed out that ACI still works if we take the “quantile function” to be the identity function—i.e., $\hat{Q}_{t}(\alpha)=\alpha$. This strategy achieves the desired coverage rate without requiring observing the ground truth labels $y_{t}^{*}$; instead, they only need to observe whether $y_{t}^{*}$ is contained in the prediction set—i.e., $\mathbbm{1}(y_{t}^{*}\in\hat{C}_{t})$. However, because they forego estimating the quantile function, the resulting algorithm is extremely sensitive to the structure of the scoring function as well as their choice of hyperparameters (in particular, the learning rate). In our experiments, we show that a standard variation the scoring function (in particular, using logits instead of prediction probabilities) causes their performance to significantly degrade.

Angelopoulos et al. [] also point out an additional shortcoming of ACI, which is that it does not guarantee that prediction sets converge to the “optimal” ones in the i.i.d. setting. As noted by Bastani et al. [], this issue is reflected in the fact that achieving $\alpha$ coverage (the guarantee satisfied by the ACI algorithm) can be achieved by the “cheating” strategy that outputs $\hat{C}_{t}=\mathcal{Y}$ with probability $1-\alpha$ and $\hat{C}_{t}=\varnothing$ with probability $\alpha$. To remedy this issue, Angelopoulos et al. [] proposes a modification to their algorithm that is guaranteed to converge to the optimal threshold in the setting of i.i.d. observations. However, their result is asymptotic (in addition to suffering from the sensitivity of the scoring function discussed above). Under certain assumptions, we prove that our algorithm satisfies a much stronger regret guarantee; to the best of our knowledge, this is the first regret guarantee on the performance of the prediction sets in terms of convergence of $\tau_{t}$ to $\tau^{*}$.

An additional advantage of our algorithm is that it guarantees that $\tau_{t}\leq\tau^{*}$ with high probability. This guarantee mirrors the distinction between marginal guarantees [Vovk et al., ] and probably approximately correct (PAC) (or training conditional) guarantees in the batch setting [Vovk, , Park et al., ]. Marginal guarantees have the form $\mathbb{P}_{Z\sim D^{n},(x,y^{*})\sim D}[y^{*}\in C_{Z}(x)]\geq\alpha$, i.e., $\alpha$ coverage over randomness in both the calibration set $Z$ and the new example $(x,y^{*})$. They have the additional advantage that coverage converges to $\alpha$ with the number of calibration examples. In contrast, PAC guarantees disentangle these two sources of randomness:

$$ $\displaystyle\mathbb{P}_{Z\sim D^{n}}[\mathbb{P}_{(x,y^{*})\sim D}[y^{*}\in C_ {Z}(x)]\geq\alpha]\geq 1-\delta,$ $$

for a given $\delta\in\mathbb{R}_{>0}$. In other words, coverage holds with high probability over $Z$. Our guarantee that $\tau_{t}\leq\tau^{*}$ is equivalent to providing the coverage guarantee $\mathbb{P}_{(x,y^{*})\sim D}[y^{*}\in C_{\tau_{t}}(x)]\geq\alpha$ for *every* $t$ with probability at least $1-\delta$ over the whole time horizon. To the best of our knowledge, existing online conformal prediction algorithms all provide a marginal coverage guarantee (it is not even clear how a PAC guarantee would look in the adversarial setting since the calibration examples are not random). For the active learning setting, a PAC guarantee makes sense since it ensures that our algorithm satisfies the desired coverage rate for every user-provided input. Finally, while we do not provide an explicit guarantee that the coverage rate converges to $\alpha$, our regret bound ensures that $\tau_{t}\to\tau^{*}$, which effectively ensures convergence to an $\alpha$ coverage rate.

## 2 Problem Formulation

Let $\mathcal{X}$ denote the inputs and $\mathcal{Y}$ denote the labels. Let $[T]=\{1,2,\cdots,T\}$, and let $t\in[T]$ be the steps on which examples $(x_{t},y_{t}^{*})$ arrive, where $x_{t}$ is the input on step $t$ and $y_{t}^{*}$ is the corresponding ground truth label. We assume given a scoring function $f:\mathcal{X}\times\mathcal{Y}\mapsto\mathbb{R}$ (also called the *non-conformity score*). The scoring function captures the confidence in whether $y$ is the ground truth label for $x$.

We consider a fixed distribution $D$ over $\mathcal{X}\times\mathcal{Y}$; let $\mathbb{P}(x,y)$ be the corresponding probability measure. On each step $t$, a sample $(x_{t},y_{t}^{*})\sim D$ is drawn. Then, our algorithm observes $x_{t}$, and constructs a prediction set $C_{t}\subseteq\mathcal{Y}$ of form

$$ $\displaystyle C_{t}=\{y\in\mathcal{Y}\mid f(x_{t},y)>\tau_{t}\},$ $$

where $\tau_{t}\in\mathbb{R}$ is a parameter to be chosen. In other words, our prediction set $C_{t}$ include all labels with score at least $\tau_{t}$ in round $t$. Note that a smaller (resp., larger) $\tau_{t}$ corresponds to a larger (resp., smaller) prediction set $C_{t}$. Then, our algorithm receives *semi-bandit feedback*—i.e., it only observes $y_{t}^{*}$ if $y_{t}^{*}\in C_{t}$. If $y_{t}^{*}\not\in C_{t}$, it receives feedback in the form of a binary indicator that $y_{t}^{*}\not\in C_{t}$.

Next, we describe our desired correctness properties. First,
given a coverage rate $\alpha\in[0,1)$, our goal is to ensure that we cover the ground truth label with probability at least $\alpha$ on all time steps:

$$ $\displaystyle\forall t\in[T]\;.\;\mathbb{P}[y_{t}^{*}\in C_{t}]\geq\alpha.$ (1) $$

We want (1) to hold with high probability. A trivial solution to the problem described so far is to always take $\tau_{t}=-\infty$. Thus, we additionally want to minimize some measure of the prediction set size. We consider a loss function $\phi:\mathbb{R}\to\mathbb{R}$, where $\phi(\tau_{t})$ encodes the loss incurred on step $t$. Then, our goal is to converge to the best possible prediction sets over time, which we formalize by aiming to achieve sublinear regret. To this end, consider the optimal prediction set $C_{t}^{*}\subseteq\mathcal{Y}$ defined by

$$ $\displaystyle C_{t}^{*}$ $\displaystyle=\{y\in\mathcal{Y}\mid f(x_{t},y)>\tau^{*}\},$ $$

where $\tau^{*}$ is defined by

$$ $\displaystyle\tau^{*}=\operatorname*{\arg\max}_{\tau\in\mathbb{R}}\tau\quad \text{subj. to}\quad\mathbb{P}[f(x_{t},y_{t}^{*})\geq\tau]\geq\alpha.$ $$

Note that $f(x_{t},y_{t}^{*})\geq\tau$ iff $y_{t}^{*}\in C_{t}^{*}$, so this property says that $\mathbb{P}[y_{t}^{*}\in C_{t}^{*}]\geq\alpha$. By definition, $C_{t}^{*}$ is the smallest possible prediction set for $x_{t}$ that achieves a coverage rate of $\alpha$. Then, the expected cumulative regret is

$$ $\displaystyle R_{T}=\mathbb{E}\left[\sum_{t\in[T]}\phi(\tau_{t})-\phi(\tau^{*} )\right].$ $$

For technical reasons, we need to impose an assumption on our loss. Intuitively, if the loss $\phi$ is discontinuous at $\tau^{*}$, then we may achieve linear regret since $\phi(\tau_{t})-\phi(\tau^{*})\geq c>0$ for some constant $c$. A natural way to formalize the continuity assumption is based on the cumulative distribution function (CDF) of the scoring function. In particular, let $G^{*}$ be the CDF of the random variable $s=f(x,y^{*})$, where $(x,y^{*})\sim D$. Then, we have the following assumption:

###### Assumption 2.1 .

$\phi(\tau)=\psi(G^{*}(\tau))$ for some $K$ Lipschitz continuous function $\psi$ (with $K\in\mathbb{R}_{>0}$).

That is, if $G^{*}(\tau)$ is very flat in some region, then $\phi(\tau)$ cannot vary very much in that region. Intuitively, if $G^{*}(\tau)$ is flat in some region, then we obtain very few samples in that region, so it becomes very hard to estimate $\tau$ in that region. If $\phi(\tau)$ varies a lot in this region, then the regret can be large if $\tau^{*}$ lies in that region. One caveat is this assumption precludes prediction set size as a loss, since prediction set size is discontinuous. Next, we assume our loss is bounded:

###### Assumption 2.2 .

$\phi_{max}\coloneqq\|\phi\|_{\infty}<\infty$.

Intuitively, Assumption 2.2 says that the overall reward is bounded, so we cannot accrue huge regret early on in our algorithm when we have very little data. Finally, we make the following assumption:

###### Assumption 2.3 .

$G^{*}(\tau^{*})=1-\alpha$.

Note that $G^{*}(\tau)$ is the miscoverage rate of our algorithm for parameter $\tau$. Thus, this assumption says the optimal parameter value $\tau^{*}$ achieves a coverage rate of exactly $\alpha$, which simplifies our analysis.

Then, our goal is to find the optimal prediction sets $C_{t}^{*}$ with coverage rate $\alpha$. Intuitively, $C_{t}^{*}$ is the smallest set that contains the ground truth label with a high probability. At each step, the algorithm observes $x_{t}$ and returns a set $C_{t}$ of candidate labels, and the user either (1) selects the ground truth label $y_{t}^{*}$ from $C_{t}$, or (2) indicates that the ground truth label is not in $C_{t}$. In a document retrieval setting, $x_{t}$ is a query sent by the user, and $y_{t}^{*}$ is the ground truth document, while in an image classification setting, $x_{t}$ is an image and $y_{t}^{*}$ is the ground truth class.

###### Assumption 2.1 .

###### Assumption 2.2 .

###### Assumption 2.3 .

## 3 Algorithm

Next, we describe our online conformal prediction algorithm (summarized in Algorithm 1). As before, let $s=f(x,y^{*})$ be the random variable that is the score of a random sample $(x,y^{*})\sim D$, and let $G^{*}$ be its CDF. By definition, $G^{*}(\tau)=\mathbb{P}[f(x,y^{*})\leq\tau]$ is the miscoverage rate, so

$$ $\displaystyle\tau^{*}=\sup\{\tau:G^{*}(\tau)\leq 1-\alpha\}.$ $$

Thus, if we know $G^{*}$, then our problem can be solved by choosing $\tau_{t}=\tau^{*}$ for all $t$. However, since we do not know $G^{*}$, we can solve the problem by estimating it from samples. Denote the estimated CDF after step $t$ as $G_{t}$. A naïve solution is to choose

$$ $\displaystyle\tilde{\tau}_{t}=\sup\{\tau\in\mathbb{R}\mid G_{t-1}(\tau)\leq 1- \alpha\}.$ $$

However, this strategy may fail to satisfy our desired coverage rate due to randomness in our estimate $G_{t-1}$ of $G^{*}$. Failing to account for miscovered examples can exacerbate this problem—if we ignore samples where we failed to cover $y_{t}^{*}$, then our estimate $G_{t}$ becomes worse, thereby increasing the chance that we will continue to fail to cover $y_{t}^{*}$. This feedback loop can lead to linear regret.

To address this challenge, we instead use a high-probability upper bound on $G^{*}$. In particular, for a error bound $\delta\in\mathbb{R}_{>0}$ to be specified, we construct a $1-\delta$ confidence bound for the empirical CDF $G_{t}$ using the Dvoretzky–Kiefer–Wolfowitz (DKW) inequality [Massart, ]. Letting $\overline{G}_{t}$ be the upper confidence bound, we instead aim to choose

$$ $\displaystyle\tau_{t}=\sup\{\tau\in\mathbb{R}\mid\overline{G}_{t-1}(\tau)\leq 1 -\alpha\}.$ $$

On the event that $\overline{G}_{t-1}$ is a valid upper bound, then we have $\tau_{t}\leq\tau^{*}$. This property ensures that we always cover the ground truth label, which ensures that our subsequent CDF estimate $\overline{G}_{t}$ is valid. As a consequence, our algorithm converges to the true $\tau^{*}$.

One remaining issue is how to handle steps where $y_{t}^{*}\not\in C_{t}$. On these steps, our algorithm substitutes $\tau_{t}$ for the observation $f(x_{t},y_{t}^{*})$. Intuitively, the reason this strategy works is that the learner does not need to accurately estimate $G^{*}$ in the interval $[0,\tau^{*})$ to recover $\tau^{*}$; it is sufficient to include the right fraction of samples in this interval. As long as our algorithm maintains the property that $\tau_{t}\leq\tau^{*}$, then $\tau_{t}$ lies in this interval, so substituting $\tau_{t}$ is sufficient.

Relatedly, our algorithm includes a constraint that $\tau_{t+1}\geq\tau_{t}$ for all $t$. We include this constraint because our estimate $G_{t}$ of the CDF in the interval $[0,\tau_{t})$ may be flawed due to semi-bandit feedback. By avoiding going backwards, we ensure that these flaws do not affect our choice of $\tau_{t+1}$. Again, as long as $\tau_{t}\leq\tau^{*}$, this constraint does not prevent convergence.

Now, we formally define $\overline{G}_{t}$ as follows. First, define the truncated CDF $G_{t}^{*}(\tau)$ by

$$ $\displaystyle G_{t}^{*}(\tau)=\begin{cases}0&\text{if }\tau<\tau_{t}\\ G^{*}(\tau)&\text{if }\tau\geq\tau_{t}.\end{cases}$ (2) $$

This CDF captures the CDF where we replace samples $s\leq\tau_{t}$ with $\tau_{t}$.
In particular, $G_{t}^{*}(\tau)$ shifts all the probability mass of $G^{*}$ in the region $[0,\tau_{t}]$ to a point mass at $\tau_{t}$.
Next, the corresponding empirical CDF $G_{t}$ is

$$ $\displaystyle G_{t}(\tau)=\frac{1}{t}\cdot\sum_{j=1}^{t}\mathbbm{1}(\max\{\tau _{t},s_{j}\}\leq\tau).$ (3) $$

Finally, letting $\delta=2/T^{2}$ and $\epsilon_{t}=\sqrt{\log(2/\delta)/2t}$, the upper bound $\overline{G}_{t}$ on $G_{t}$ from DKW is

$$ $\displaystyle\overline{G}_{t}(\tau)=G_{t}(\tau)+\epsilon_{t}.$ (4) $$

We use this $\overline{G}_{t}$ to compute $\tau_{t}$ in Algorithm 1.

Finally, Algorithm 1 satisfies the following theoretical guarantee: (i) it incurs sublinear regret $\tilde{\mathcal{O}}(\sqrt{T})$, and (ii) it satisfies $C_{t}^{*}\subseteq C_{t}$ for all $t$ with probability at least $1-2/T$ (see Appendix A for a proof):

###### Theorem 3.1 .

The expected cumulative regret of Algorithm 1 satisfies

$$ $R_{T}\leq K\left(2\log T+4\sqrt{T\log T}+1\right)+4\phi_{max},$ $$

In addition, with probability at least $1-2/T$, we have $\tau_{t}\leq\tau^{*}$ for all $t$.

Figure: Algorithm 1 Semi-bandit Prediction Set (SPS)

###### Theorem 3.1 .

## 4 Experiments

### 4.1 Experimental Setup

Image classification task.
We use the Vision Transformer [Dosovitskiy et al., ] model on the ImageNet dataset [Deng et al., ].(^1^11Obtained from [https://www.image-net.org/](https://www.image-net.org/) with a custom and non-commercial license; we use the $16\times 16$ down sampled version.)
Each image from the dataset belongs to exactly one class out of the 1,000 candidate classes. Consequently, the cardinality of the label domain is 1,000 (i.e., $|\mathcal{Y}|=1000$). In the experiments, images arrive sequentially, and our algorithm aims to construct the smallest candidate label set that achieves the desired coverage.
We use the logits score returned by a ViT model (pretrained on the ImageNet training set) as our scoring function $f$; we use the logits instead of the softmax function to evaluate sensitivity to the choice of scoring function.

Document retrieval task.
Next, we consider the Dense Passage Retriever (DPR) model [Karpukhin et al., ] on the SQuAD question-answering dataset. DPR leverages a dual-encoder architecture that maps questions and candidate documents to embedding vectors. Denoting the space of questions and documents by $\mathcal{Q}$ and $\mathcal{D}$, respectively, then DPR consists of a question encoder $E_{Q}:\mathcal{Q}\mapsto\mathbb{R}^{768}$ and a document encoder $E_{D}:\mathcal{D}\mapsto\mathbb{R}^{768}$. Given a question $q$ and a set of candidate documents $D\subseteq\mathcal{D}$, the similarity score between each document $d\in D$ and the question $q$ is defined as:

$$ $\displaystyle s_{q,d}=\frac{{E_{Q}(q)\cdot E_{D}(d)}}{|E_{Q}(q)|\cdot|E_{D}(d) |}.$ $$

We use this score as our scoring function. Then, our goal is to construct the smallest set of candidate documents while guaranteeing that they contain the ground truth document with high probability.

Our dataset is SQuAD question-answering dataset [Rajpurkar et al., ], which is a popular benchmark for reading comprehension. Each question in SQuAD can be answered by finding the relevant information in a corresponding Wikipedia paragraph known as the context. The authors of DPR make a few additional changes to adapt SQuAD better for document retrieval. First, paragraphs are further split into multiple, disjoint text blocks of 100 words, serving as the basic retrieval unit (i.e., candidate documents). Second, each question is paired with ground truth documents and a set of irrelevant documents.(^2^22In the data, all questions are paired with 50 irrelevant documents. We construct the candidate documents set by including all 50 irrelevant documents and 1 ground truth document. We exclude questions that have 0 ground truth documents. The data were obtained from DPR’s public Github Repo: [https://github.com/facebookresearch/DPR](https://github.com/facebookresearch/DPR) with licenses CC BY-SA 4.0 and CC BY-NC 4.0) In our experiments, for each question, we include one ground truth document and all the irrelevant documents to create the set of candidate documents.

Second-price auctions task.
Lastly, we consider the scenario of setting reservation prices in second-price auctions, a well-studied problem that has semi-bandit feedback [Cesa-Bianchi et al., , Zhao and Chen, ]. In this problem, a seller (the auctioneer) repeatedly sells the same type of items to a group of bidders. In each round $t$, she publicly announces a reservation price $p^{t}$, while bidders draw their private values $v^{t}$ from a fixed distribution that is unknown to the seller. For each bidder $i$, she will submit the bid $B^{t}_{i}=v^{t}_{i}$ if and only if $v^{t}_{i}\geq p^{t}$. The seller obtains reward $R_{t}$:

$$ $\displaystyle R_{t}=\begin{cases}0&\text{if }p^{t}>B_{t}^{(1)}\\ p^{t}&\text{if }B_{t}^{(2)}<p^{t}\leq B_{t}^{(1)}\\ B_{t}^{(2)}&\text{if }p^{t}\leq B_{t}^{(2)},\end{cases}$ $$

where $B_{t}^{(1)},B_{t}^{(2)}$ denote the highest and second-highest bid received by the seller in round $t$, implying that the seller only observes bids that are higher than $p^{t}$. We consider a seller that aims to learn

$$ $\displaystyle p^{*}=\operatorname*{\arg\max}_{p\in\mathbb{R}}p\quad\text{subj. to}\quad\mathbb{P}[B^{(1)}\geq p]\geq\alpha.$ $$

That is, the seller aims to find the highest reservation price $p$ such that she can sell the item with probability at least $\alpha$. This problem can be solved using online conformal prediction. Following standard practice [Mohri and Medina, ], we use a synthetic dataset that adapts from eBay auction data [Jank and Shmueli, ]. Specifically, we simulate the distribution of $v_{i}$ by using the empirical distribution of the observed bids in the dataset.

Baselines.
We compare to greedy, Adaptive Conformal Inference (ACI) [Gibbs and Candes, ], and Decaying Learning Rate (DLR) [Angelopoulos et al., ]. The greedy strategy chooses

$$ $\displaystyle\tau_{t}=\sup\{\tau\in\mathbb{R}\mid G_{t}(\tau)\leq 1-\alpha\}$ $$

at every step, which cannot guarantee the $\alpha$ coverage rate, leading it to undercover significantly more than desired. Next, Adaptive Conformal Inference (ACI) adjusts $\alpha_{t}$ (and then $\tau_{t}$) based on whether the ground truth label is in the previous round’s prediction set. We choose the learning rate $\gamma$ from a grid search in a candidate set proposed in [Gibbs and Candès, ]. To run ACI in our semi-bandit feedback setting, we only update the quantile function $\hat{Q}_{t}$ when ground-truth label $y_{t}^{*}$ is observed; as we show, this biased strategy for updating $\hat{Q}_{t}$ leads it to fail to achieve the desired coverage rate.

Lastly, we consider the Decaying Learning Rate (DLR) algorithm proposed in [Angelopoulos et al., ]. In contrast to ACI, DLR directly performs gradient descent on the cutoffs $\tau_{t}$ instead of the quantiles $\alpha_{t}$; it can be viewed as running ACI with $\hat{Q}_{t}(\alpha)=\alpha$. We set the learning rate to the one used in the experiments from the original paper—i.e., $\eta_{t}=t^{-1/2-\epsilon}$ with $\epsilon=0.1$. We show results for two additional baselines, explore-then-commit (ETC) and conservative ETC, in Appendix B.

Experiment parameters.
We use $\alpha=0.9$ and $T=10000$, and report the averages across 5 runs.

Metrics.
First, we consider the cumulative regret for the following reward function $\phi$:

$$ $\displaystyle\phi(\tau)=\begin{cases}-\lambda_{1}\cdot\lvert G^{*}(\tau)-(1- \alpha)\rvert&\text{if $G^{*}(\tau)\leq(1-\alpha)$ }\\ -\lambda_{2}\cdot\lvert G^{*}(\tau)-(1-\alpha)\rvert&\text{if $G^{*}(\tau)>(1- \alpha)$},\end{cases}$ $$

for some $0<\lambda_{1}<\lambda_{2}$; we take $\lambda_{1}=0.1$ and $\lambda_{2}=10$. Note this loss imposes a larger penalty for undercovering compared to overcovering.
Next, we consider coverage rate:

$$ $\displaystyle\text{Coverage Rate}=\frac{1}{T}\sum_{t=1}^{T}\mathbbm{1}(y^{*}_{ t}\in C_{t}).$ $$

Third, we consider the number of times $\tau_{t}>\tau^{*}$, which measures the violation of our safety condition:

$$ $\displaystyle\text{Undercoverage Count}=\sum_{t=1}^{T}\mathbbm{1}(\tau_{t}> \tau^{*}).$ $$

Our goals are to (i) achieve $\tilde{\mathcal{O}}(\sqrt{T})$ regret, while (ii) maintaining the desired $\alpha$ coverage rate, and (iii) achieving zero undercoverage count with probability at least $1-\delta$ over the entire time horizon.

Figure: (a) ImageNet
Refer to caption: extracted/5897208/fig/comparison_regret_10000_0.9_squad.png

Figure: (a) ImageNet
Refer to caption: extracted/5897208/fig/comparison_coverage_10000_0.9_imagenet.png

Figure: (a) ImageNet
Refer to caption: extracted/5897208/fig/comparison_undercover_10000_0.9_imagenet.png

### 4.2 Results

Regret.
First, Figure 1 shows the cumulative regret of each approach on each task. As can be seen, our algorithm consistently obtains the lowest regret.
The ACI algorithm attains a regret level comparable to the greedy algorithm because its quantile function is updated with a bias. Furthermore, note that the curves for both ACI and the greedy algorithm appear to be superlinear. This can happen since these algorithms do not properly account for semi-bandit feedback—in particular, the empirical estimate $G_{t}$ of the distribution becomes increasingly truncated.

Moreover, the poor performance of DLR can be attributed to the fact that it does not make use of a quantile function. As a consequence, without score-specific hyperparameter tuning (i.e., tuning the learning rate), it can converge very slowly to the optimal prediction sets. For many scoring functions, we do not have prior knowledge of the score’s range, which exacerbates these issues. These issues are particularly salient when we consider tasks such as the second-price auction, where the score’s range (i.e., the range of bids) can be difficult to predict in advance. In contrast, our algorithm consistently performs and does not have any hyperparamters to tune.

Coverage rate.
Next, Figure 2 shows the coverage rate achieved by each algorithm for each task. Both ACI and greedy fail to maintain the desired coverage rate in all three tasks. DLR and SPS both achieve the desired coverage rate; however, SPS converges more quickly.

Undercoverage count.
Finally, Figure 3 shows the undercoverage count. Note that greedy and ACI frequently undercover. ACI has high undercoverage count because the prediction set oscillates between being too small (i.e., $\tau_{t}>\tau^{*}$) and too large (i.e., $\tau_{t}<\tau^{*})$. This behavior can be undesirable since it means that different inputs have different coverage probabilities. In contrast, our algorithm never undercovers since $\tau_{t}$ is guaranteed to converge to $\tau^{*}$ from below. Interestingly, DLR also does not undercover. While their algorithm is not guaranteed to satisfy this property, it incrementally estimates $\tau_{t}$ by starting from a conservative $\tau$. Thus, if the learning rate is small enough, it would not undercover until $\tau_{t}$ gets significantly closer to the true $\tau^{*}$.

Summary.
These results demonstrate that our algorithm achieves (and converges to) the desired coverage rate while achieving sublinear regret and maintaining $\tau_{t}<\tau^{*}$. In contrast, ACI and greedy fail to achieve the desired coverage rate, and DLR converges much more slowly than our algorithm.

## 5 Conclusion

We have proposed a novel conformal prediction algorithm for constructing online prediction sets under stochastic semi-bandit feedback. We have shown our our algorithm can be applied to learn optimal prediction sets in image classification, document retrieval, and second-price auction reservation price prediction. Our experiments demonstrate that we maintain the desired $\alpha$ coverage level while achieving prediction set sizes that achieve sublinear regret and zero undercoverage count.

## Appendix A Proof of Theorem 3.1

We begin by proving several helper lemmas, and then establish our main result. Our first lemma shows that $G_{t}$ defined in (3) converges uniformly to $G_{t}^{*}$ defined in (2). Note that the randomness comes from the sequence of random variables $s_{j}=f(x_{j},y_{j}^{*})$.

###### Lemma A.1 .

For any $\epsilon\in\mathbb{R}_{>0}$, we have

$$ $\displaystyle\mathbb{P}\left[\sup_{\tau\in\mathbb{R}}|G_{t}(\tau)-G_{t}^{*}( \tau)|>\epsilon\right]\leq 2e^{-2t\epsilon}.$ $$

###### Proof.

Let the full empirical CDF of $s$ be
$G^{\prime}_{t}(\tau)=\frac{1}{t}\sum_{j=1}^{t}\mathbbm{1}(s_{j}\leq\tau)$,
and define the events

$$ $\displaystyle A_{<}$ $\displaystyle=\left\{\sup_{\tau<\tau_{t}}|G_{t}(\tau)-G_{t}^{*}(\tau)|> \epsilon\right\}\qquad\text{and}\qquad A_{\geq}=\left\{\sup_{\tau\geq\tau_{t}} |G_{t}(\tau)-G_{t}^{*}(\tau)|>\epsilon\right\}.$ $$

First, consider $A_{\geq}$. For $\tau\geq\tau_{t}$, by definition of $G_{t}^{*}$ and $G_{t}$, we have $G_{t}^{*}(\tau)=G^{*}(\tau)$ and $G_{t}(\tau)=G^{\prime}_{t}(\tau)$. Thus, by the DKW inequality, we have
$\mathbb{P}[A_{\geq}]\leq 2e^{-2t\epsilon^{2}}$.
Next, consider $A_{<}$. By definition of $G_{t}^{*}$ and $G_{t}$, we have $G_{t}(\tau)=G_{t}^{*}(\tau)=0$, so
$\mathbb{P}[A_{<}]=0$.
Thus, by a union bound, we have

$$ $\displaystyle\mathbb{P}\left[\sup_{\tau\in\mathbb{R}}|G_{t}(\tau)-G_{t}^{*}( \tau)|>\epsilon\right]$ $\displaystyle\leq\mathbb{P}[A_{\geq}]+\mathbb{P}[A_{<}]\leq 2e^{-2t\epsilon^{2 }},$ $$

as claimed.
∎

Our next lemma shows that with high probability, the desired invariant $\tau_{t}\leq\tau^{*}$ holds for all $t\in[T]$.

###### Lemma A.2 .

Suppose $\sup_{\tau\in\mathbb{R}}|G_{t}(\tau)-G_{t}^{*}(\tau)|\leq\epsilon_{t}$ for all $t\in[T]$. Then, $\tau_{t}\leq\tau^{*}$ for all $t\in[T]$.

###### Proof.

We prove by induction. For the base case $t=1$, we choose $\tau_{1}=-\infty$, so $\tau_{1}\leq\tau^{*}$. For the inductive case, assume that $\tau_{k}\leq\tau^{*}$. Now, by our assumption that $\sup_{\tau\in\mathbb{R}}|G_{k}(\tau)-G_{k}^{*}(\tau)|\leq\epsilon_{k}$ for all $k\in[T]$, we have

$$ $\displaystyle G^{*}_{k-1}(\tau)\leq G_{k-1}(\tau)+\epsilon_{k-1}=\overline{G}_ {k-1}(\tau).$ $$

Because $\tau_{k}\leq\tau^{*}$, we also have $G^{*}_{k-1}(\tau)=G^{*}(\tau)$ for all $\tau\geq\tau^{*}$. Together, we have

$$ $\displaystyle\overline{G}_{k-1}(\tau^{*})\geq G^{*}(\tau^{*})=1-\alpha.$ $$

Thus, we have $\tau_{1-\alpha,k}\leq\tau^{*}$. Since $\tau_{k}\leq\tau^{*}$, it follows that:

$$ $\displaystyle\tau_{k+1}=\max\{\tau_{k-1},\tau_{1-\alpha,k}\}\leq\tau^{*},$ $$

as claimed.
∎

Our next lemma bounds the range of $\overline{G}_{t}(\tau_{t})$.

###### Lemma A.3 .

Suppose $\sup_{\tau\in\mathbb{R}}|G_{t}(\tau)-G_{t}^{*}(\tau)|\leq\epsilon_{t}$ for all $t\in[T]$. Then, for all $t\in[T]$, we have

$$ $\displaystyle 1-\alpha-\frac{2}{t}\leq\overline{G}_{t}(\tau_{t})\leq 1-\alpha+ 2\epsilon_{t}.$ $$

###### Proof.

By Lemma A.2, $\tau_{t}\leq\tau^{*}$, implying that $G^{*}(\tau_{t})\leq G^{*}(\tau^{*})$. For the upper bound, we have

$$ $\displaystyle\overline{G}_{t}(\tau_{t})\leq G_{t}^{*}(\tau_{t})+2\epsilon_{t}= G^{*}(\tau_{t})+2\epsilon_{t}\leq G^{*}(\tau^{*})+2\epsilon_{t}=1-\alpha+2 \epsilon_{t}.$ $$

Next, we consider the lower bound. When $t=1$, the inequality trivially holds. Otherwise, at step $t-1$, $\tau_{t}$ is at least the $\lfloor(1-\alpha)(t-1)\rfloor$-th order statistic. On the event that $s_{t}\geq\tau_{t}$, then $\tau_{t}$ is at least the $(\lfloor(1-\alpha)(t-1)\rfloor-1)$-th order statistic. Thus, we have

$$ $\displaystyle\overline{G}_{t}(\tau_{t})$ $\displaystyle\geq\frac{\lfloor(1-\alpha)t\rfloor-1}{t}\geq\frac{(1-\alpha)t}{t }-\frac{2}{t}.$ $$

If $s_{t}<\tau_{t}$, then $\tau_{t}$ is at least the $(\lfloor(1-\alpha)t\rfloor$)-th order statistic. Then, we have

$$ $\displaystyle\overline{G}_{t}(\tau_{t})$ $\displaystyle\geq\frac{\lfloor(1-\alpha)t\rfloor}{t}\geq\frac{(1-\alpha)t}{t}- \frac{2}{t},$ $$

as claimed.
∎

See 3.1

###### Proof.

Define the good event

$$ $\displaystyle E$ $\displaystyle=\forall t\in[T]\;.\;\sup_{\tau\in\mathbb{R}}|G_{t}^{*}(\tau)-G_{ t}(\tau)|\leq\epsilon_{t}.$ $$

By a union bound and by Lemma A.1, we have

$$ $\displaystyle\mathbb{P}[\neg E]\leq\sum_{t=1}^{T}2e^{-2t\epsilon_{t}^{2}}\leq T \delta=\frac{2}{T}.$ $$

Now, we have

$$ $\displaystyle R_{T}$ $\displaystyle=\mathbb{E}\left[\sum_{t=1}^{T}|\phi(\tau^{*})-\phi(\tau_{t})| \biggm{|}E\right]\cdot\mathbb{P}[E]+\mathbb{E}\left[\sum_{t=1}^{T}|\phi(\tau^{ *})-\phi(\tau_{t})|\biggm{|}\neg E\right]\cdot\mathbb{P}[\neg E]$ $\displaystyle=\sum_{t=1}^{T}\mathbb{E}\left[|\phi(\tau^{*})-\phi(\tau_{t})| \mid E\right]\cdot\mathbb{P}[E]+\sum_{t=1}^{T}\mathbb{E}\left[|\phi(\tau^{*})- \phi(\tau_{t})|\mid\neg E\right]\cdot\mathbb{P}[\neg E]$ $\displaystyle\leq\sum_{t=1}^{T}\mathbb{E}\left[|\phi(\tau^{*})-\phi(\tau_{t})| \mid E\right]\cdot\mathbb{P}[E]+\sum_{t=1}^{T}\mathbb{E}\left[2\phi_{max}\mid \neg E\right]\cdot\mathbb{P}[\neg E]$ $\displaystyle\leq\left(\sum_{t=1}^{T}\underbrace{\mathbb{E}\left[|\phi(\tau^{* })-\phi(\tau_{t})|\mid E\right]}_{\eqqcolon X_{t}}\right)+4\phi_{max}.$ $$

The first inequality follows from Assumption 2.2. Using Lemma A.3, we can bound $X_{t}$ as follows:

$$ $\displaystyle X_{t}$ $\displaystyle=\mathbb{E}\left[|\phi(\tau^{*})-\phi(\tau_{t})|\mid E\right]$ $\displaystyle=\mathbb{E}[\psi(G^{*}(\tau^{*}))-\psi(G^{*}({\tau_{t}}))\mid E]$ $\displaystyle\leq K\cdot\mathbb{E}[|G^{*}(\tau^{*})-G^{*}(\tau_{t})|\mid E]$ $\displaystyle=K\cdot\mathbb{E}\left[|1-\alpha-\overline{G}_{t}(\tau_{t})+ \overline{G}_{t}(\tau_{t})-G^{*}(\tau_{t})|\mid E\right]$ $\displaystyle\leq K\cdot\mathbb{E}\left[|1-\alpha-\overline{G}_{t}(\tau_{t})|+ |\overline{G}_{t}(\tau_{t})-G^{*}(\tau_{t})|\mid E\right]$ $\displaystyle\leq K\cdot\mathbb{E}\left[\max\left\{\frac{2}{t},2\epsilon_{t} \right\}+|\overline{G}_{t}(\tau_{t})-G_{t}^{*}(\tau_{t})|\biggm{|}E\right]$ $\displaystyle\leq K\cdot\max\left\{\frac{2}{t},2\epsilon_{t}\right\}+K\cdot \mathbb{E}\left[\sup_{\tau\in\mathbb{R}}|G_{t}(\tau)-G_{t}^{*}(\tau)|\biggm{|} E\right]$ $\displaystyle\leq K\cdot\max\left\{\frac{2}{t},2\sqrt{\frac{\log(2/\delta)}{2t }}\right\}+2K\sqrt{\frac{\log(2/\delta)}{2t}}$ $\displaystyle\leq\frac{2K}{t}+4K\sqrt{\frac{\log(2/\delta)}{2t}},$ $$

where the first inequality follows from Assumption 2.1 and the third inequality follows from Lemma A.3.
Thus, we have

$$ $\displaystyle\sum_{t=1}^{T}X_{t}$ $\displaystyle\leq\sum_{t=1}^{T}\left\{\frac{2K}{t}+4K\cdot\sqrt{\frac{\log T}{ t}}\right\}\leq K\left[2\log T+1+4\sqrt{T\log T}\}\right].$ $$

The claim follows.
∎

###### Lemma A.1 .

###### Proof.

###### Lemma A.2 .

###### Proof.

###### Lemma A.3 .

###### Proof.

###### Proof.

## Appendix B Additional Experiments

We consider two additional baselines. First, explore-then-commit (ETC) chooses $\tau_{t}=-\infty$ in the first $m$ steps, and then commits to

$$ $\displaystyle\tau_{t}=\sup\{\tau\in\mathbb{R}\mid G_{m}(\tau)\leq 1-\alpha\}.$ $$

Next, conservative ETC (Con-ETC) uses the same strategy, except it commits to

$$ $\tau_{t}=\sup\{\tau\in\mathbb{R}\mid\overline{G}_{m}(\tau)\leq 1-\alpha\}$ $$

after the exploration period. In other words, it commits to a conservative choice of $\tau$ that satisfies our coverage guarantee, and also guarantees $\tau_{t}\leq\tau^{*}$ with probability at least $1-2/T$. The number of exploration rounds are chosen via a grid search. Results are shown in Figures 4, 5, & 6. As can be seen, ETC fails to achieve the desired coverage rate since it does not account for uncertainty; conversely, Con-ETC achieves very high regret since it does not adaptively choose $\tau_{t}$ over time.

Figure: (a) ImageNet
Refer to caption: extracted/5897208/fig/comparison_regret_10000_0.9_squad_appendix.png

Figure: (a) ImageNet
Refer to caption: extracted/5897208/fig/comparison_coverage_10000_0.9_imagenet_appendix.png

Figure: (a) ImageNet
Refer to caption: extracted/5897208/fig/comparison_undercover_10000_0.9_imagenet_appendix.png

## Peer Reviews

confidence: 4
contribution: 2
initial_rating: 5
presentation: 2
questions: 1. What happens to the algorithm in practice if assumptions 2 and 3 are unsatisfied? Where does the regret analysis fail?

2. “As a consequence, our algorithm converges to the true \tau^*” Is the convergence a consequence of tau being a monotonic increasing sequence?

3. Are there changes to the aci algorithm that can achieve the same thing? What is the advantage of giving \tau_t as a feedback?

4. Why does the coverage rate increase and then decrease for ACI?
soundness: 3
strengths: 1. To the best of my knowledge, the paper is the first to deal with the problem of online conformal prediction with semi bandit feedback. Therefore there is originality to the work. 

2. The quality of some aspects of the paper is decent, especially the mathematical notation used is clean and easy to understand. The coverage of conformal prediction is sufficient. The introduction section is also well-written and provides intuitive exposure to conformal prediction. 

3. The applications of the paper, especially in document retrieval, can be significant in a contemporary interactive document setting and even the annotation example for the image classification setting could be potentially useful in an active learning setting. Conformal prediction is also useful in creating prediction sets for black box models in general, and such a problem set has sufficient motivation in general. 

4. The three metrics in the results are complementary to each other and match well with the claims of the paper.
summary: - The paper studies the problem of conformal prediction in an online setting with semi-bandit feedback. The semi-bandit feedback is conditioned on whether or not the true label was present in the confidence set, if it is the true label is given back (and used for computing the score) for further refinement otherwise we only recieve that the true label is not present. 
- The main contribution of this paper is an algorithm which performs online conformal prediciton, which the authors show achieves sub-linear regret upto a constant factor. 
- The authors use the DFW inequality to construct upper bounds for the empirical CDF of the coverage parameter and adaptively update this upper bound using the semi bandit feedback.
- The authors show experiments on three different tasks including an image classification task, a document retrieval task and a second price auction task for three key metrics regret, coverage rate, undercoverage count. The tasks are benchmarked with 2 techniques: ACI and DLR.
weaknesses: 1. The writing, in general, is a bit unclear and sloppy. Here a few examples:
- a. What is the source of randomness in the two levels of probability decomposition (The pac and the coverage)? 
- b. The proof of theorem 1 can use some intuition
- c. The description of the Experiment is not well-written, for example, the desired coverage rate or other parameters? Does the paper use all the samples from imagenet or is their a subsampling?
- d. The theorem is not self-complete, everything referenced in the theorem should be defined the assumptions should be mentioned, 
- e. The full form of PID and ACI is not mentioned in their first reference.
2. Assumption 2.2 might not hold in practice, especially in an active learning setting, where the loss function might be ill-defined for the first few rounds when the model lacks confidence.
3. In an active learning setting, do you ideally want a coverage set to decrease with time? Also in general, in active learning there is a constraint on the size of the samples that can be annotated. How much effort will be spent in identifying if the true label is there or not? 
4.  The PAC bound does not reappear again in the paper or the theoretical results, what is the point of presenting it? Usually, there is a relation between the number of samples and the error probability, what is the relation in this case?
5. There are no margin-of-errors mentioned in the experimental results, therefore, it is difficult to establish the significance of these results. Also, the ACI line on cumulative regret is not discernible.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 2
questions: 1. Can the framework be extended to non-i.i.d setting? Such as black-box optimization, where the optimal x is searched for.
2. In assumption 2.1, the definition of loss is a bit abstract. Can the authors elaborate a bit more on how to interpret this loss in different practical applications?
soundness: 3
strengths: The algorithm enjoys a sublinear regret bound. It constructs compact prediction sets, while ensuring high coverage probability. The experimental results show significant improvement over the other baselines.
summary: The paper proposes an online conformal prediction method with semi-bandit feedback. The algorithm is based on an upper estimate of the score function's CDF, with sublinear regret bound under certain loss functions. Several experiments are conducted to show the effectiveness of the algorithm.
weaknesses: 1. The theoretical result seems not very sufficient. From my understanding, coverage rate and the size of the prediction set are the two key metrics of practical interest. However, it is unclear how the result in Theorem 3.1 relates to these two metrics.
2. The sizes of the prediction sets are not reflected in the experimental results either.  
3. The presentation quality can be improved. For example, in Fig. 1, error bars can be added, and I only observe 3 curves while 4 algorithms are in the legend. There are also some typos. For example, in line 429, "our our".

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 2
questions: 1. Are your assumptions made in the paper common in the conformal prediction setting and the semi-bandit setting?
2. What is the theoretical novelty of your paper compared with the existing work? The analysis seems not very difficult for me. It is better to summarize the theoretical contributions in a small paragraph since I feel most techniques or results are similar to existing work under your assumptions.
soundness: 2
strengths: 1. This paper studies an interesting and timely topic on conformal prediction with online learning.
2. I did not check the appendix in detail, but I feel the theoretical results are proper.
3. Several real-world experiments are conducted to validate the high performance of the proposed method.
summary: This paper considers the conformal prediction problem in the online learning setting with semi-bandit feedback. The authors proposed a new algorithm targeted at this setting and prove that it obtains sublinear regret bound. Then, the authors conduct some experiments to validate the high efficiency of the proposed algorithm over existing approaches based on conformal prediction in the online learning framework.
weaknesses: 1. I feel the presentation of this paper can be improved, The current version is still hard to follow. For example:
1.1 More background information on conformal prediction should be provided, such as the studies on conformal prediction in statistics and its recent applications on the online learning problem. 
1.2 There are many definitions/notations in your work, and it is better to recall their definitions sometimes. For instance, in the second paragraph of page 3, it is better to define $\tau$ and $\tau_t$ there and I feel they are not previously defined. And in the pseudocode it is better to define $s_t$ there. The current version is hard to read.

2. Running time of algorithms should be reported in the paper since conformal prediction may lead to heavy computation, e.g. providing runtime comparisons between their proposed method and the baselines for each of the experimental tasks.

3. It is better to give some more real-world applications under your problem setting: a combination of conformal prediction and semi-bandit framework.

---

confidence: 2
contribution: 2
initial_rating: 6
presentation: 2
questions: Can you provide results for longer time horizons to show if/when the coverage rate stabilizes?

Can you also discuss potential modifications to their algorithm that could accelerate convergence of the coverage rate, and any tradeoffs these modifications might introduce?
soundness: 2
strengths: 1. Considered a novel setup where true label can be observed only when prediction set covers it

2. Established a regret bound for the problem of interest

3. Conducted experiments in different tasks demonstrating the utility of the proposed method
summary: The authors propose a novel conformal prediction algorithm for constructing online prediction sets under a novel setting called stochastic semi-bandit feedback. They prove that the developed algorithm can achieve sub-linear regret and demonstrate the applicability of their method in different tasks including a retrieval task, an image classification task, and an auction price-setting task.
weaknesses: 1. While authors established a regret bound for the problem of interest, the author didn't mention related regret bounds in the existing work. Besides, the author did not mention how good the regret bound is compared to the existing work. 

2. In the experiments, I observe the coverage rate is relatively conservative for the proposed method. Does the coverage rate stabilize if step is large enough? Is it possible to speed up the coverage convergence?

Meta-review: This paper introduces a novel online conformal prediction algorithm with semi-bandit feedback, achieving sublinear regret and demonstrating its applicability across tasks like image classification, document retrieval, and auction price-setting. The main contribution is the development of a regret bound for this new setting.

Reviewers praised the paper's novelty, but raised concerns about its clarity, noting difficulties in following the arguments and defining key notations. The theoretical contributions were considered limited, with a need for more comparison to existing work. Additionally, experimental details such as error margins, running time comparisons, and longer-term results were missing.

Decision: Reject