Stochastic Online Conformal Prediction with Semi-Bandit Feedback
Authors: Haosen Ge
Hamsa Bastani
Osbert Bastani
Venue: ICML 2025 poster (2025)
Keywords: Online Conformal Prediction
Semi-bandit Feedback
Primary area: general_machine_learning->online_learning_active_learning_and_bandits

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.

Stochastic Online Conformal Prediction with Semi-Bandit Feedback
Haosen Ge Hamsa Bastani 2 Osbert Bastani
Abstract
tainty quantification due to its ability to provide theoretical guarantees for arbitrary blackbox models. They modify a given blackbox model f X + y to a conformal predictor C: X 2n' that predicts sets of labels. the batch setting, it does so by using held-out calibration datasel 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..
Conformal prediction has emerged as an effective strategy for uncertainty quantification by modi- fying& model to output sets of labels instead of 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.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 in- stance, consider calibrating a document retrieval model a new domain; in this setting, user would only be able to provide the true label if the target document is in the prediction set of re- trieved 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 clas- sification task, and an auction price-setting task, and demonstrate that it empirically achieves good performance compared to several baselines.
Ply E C(x) a a,
where is the desired coverage rate, and the probability is taken over the random sample (I, y²) ~ D and the calibra- tion dataset Z = {(x,, u))} ~ D
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 be large obtain good performance. In many settings, such labeled data may not be easy to obtain. As motivating setting, we consider a document retrieval problem, where the input & might be 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 al., 2020; Shuster et al., 2021; Ji et al., 2023). A common practice is to use retrieval model trained on a large dataset in different domain in zero-shot manner; for instance, a user might use the dense passage retrieval (DPR) model (Karpukhin et al., 2020) directly on their own dataset without finetuning. Thus, labeled data from the target domain may not be available.
1. Introduction
Uncertainty quantification is an effective strategy for im- proving trustworthiness of machine learning models by pro- viding users with a measure of confidence of each prediction to better inform their decisions. Conformal prediction (Vovk et al., 2005; Tibshirani al., 2019; Park et al., 2019; Bates al., 2021) has emerged as a promising strategy for uncer-
We propose online conformal prediction algorithm that sequentially constructs prediction sets C. inputs æ, are given. We consider semi-bandi feedback, where we only observe the true label yf if it is included in our prediction set (i.e., yf E Ct). Otherwise, we observe an indicator that yf & C., but do not observe yf" In the document retrieval example, users might sequentially provide queries 2, the DPR model, and our algorithm responds with prediction set C, of potentially relevant documents. Then, the user selects the ground truth document yī if it appears in this set, and indicates that their query was unsuccessful otherwise.
Equul contribution 'Wharton AI Analytics Initiative, University of Pennsylvania "Operations, Information and De- cisions Department, The Wharton School, University of Penn- sylvania "Department of Computer and Information Science, University of Peunsylvania. Correspondence to: Haosen Ge <hec@ whaartonuupenneduu.....
Proceedings of the 4nnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
As in conformal prediction, we aim to ensure that we achieve the desired coverage rate a with high probability. Letting

---

Stochastic Online Conformal Prediction with Semi-Bandit Feedback
C denote the optimal prediction sets (i.e., the prediction sets given infinite calibration data), our algorithm ensures that with high probability, Cj S C on all time steps t. Since C2 achieves the desired coverage rate with high prob- ability, this property ensures C. does so as well.
loss and gradient update. As the authors point out, they do not need to update the quantile function every step. However, the steps where they update Qr cannot be chosen in a way that depends on y/, 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 Q. when yi is in the prediction set can create such bias that leads ACI to fail to achieve coverage.
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 O in the limit of infinite data, and consider a loss function encoding how much worse our prediction set C2 is compared to C₁. Then, our algorithm ensures this loss goes to zero as sufficiently many samples become available-iee. the prediction sets Ce converge to the optimal ones C over time. Formally, our algorithm guarantees sublinear regret of ((VT).
Similarly, the SAOCP algorithm proposed by Bhatnagar et al. (2023) requires observing Vr at every step to construct the prediction set S; = inf (s E R : yt E Cx(X,, $)), which is then used to compute the loss and gradient, and the Conformal PID control algorithm proposed by An- gelopoulos et al. (2024a) uses V/ to compute the score St ent. In contrast, which is needed to compute the gradi- motivated by the active learning setting, where users are interested in constructing confor- mal predictors on-the-fly rather than providing calibration set ahead-of-time. Thus, in our setting, it is reasonable to assume that the data arrives ii.d;; however, we need to han- dle semi-bandit feedback since the user may be unable to provide the true label y if not in the prediction set.
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 opti- mal ones while maintaining the desired coverage rate. More- over, our algorithm significantly outperforms three natural baselines; each baseline either achieves worse cumulative expected regret or does not satisfy the desired coverage rate.
Angelopoulos et al. (2024b) points out that ACI still works if we take the "quantile function"' to be the identity function i.e., Qa(a) = a. This strategy achieves the desired coverage rate without requiring observing the ground truth labels yi: instead, they only need to observe whether y is contained in the prediction set-i.e. 1 E C.). However, because they forego estimating the quantile function, the resulting algorithm is extremely sensitive to the structure of the scor- ing 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.
Contributions. We formalize and solve the problem of on- line conformal prediction with semi-bandit feedback. Our algorithm constructs compact prediction sets, ensuring high coverage probability. The algorithm also provides an effi- cient 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 our algorithm's 's performance on image classification, document retrieval and reservation price-setting in auctions, showcasing its effectiveness in wide variety of real world applications, which highlights its practical utility.
Angelopoulos et al. (2024b) 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. (2022), this issue is reflected in the fact that achieving a coverage (the guar- antee satisfied by the ACI algorithm) can be achieved by the "cheating" strategy that outputs C, = y with probabil- ity 1 a and C = with probability a. To remedy this issue, Angelopoulos et al. (2024b) proposes modification to their algorithm that is guaranteed to converge to the opti- mal threshold in the setting of i..dd. 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 much stronger regret guarantee; the best of our knowl- edge, this is the first regret guarantee on the performance of the prediction sets in terms of convergence of to T"
Related work. Recent work has studied conformal predic- tion in the online setting (Gibbs& & Candes, 2021; Bastani et al., 2022; Gibbs& & Candès, 2024: Angelopoulos et al., 2024a:b). They are motivated by conformal prediction for time series data, where the labels can shift in complex and potentially adversarial ways. Thus, they make very different assumptions than ours; in particular, they allow for adver- sarial 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 & Candes (2021) requires observing vi at every step since it is needed to update the quantile function (+).), which is needed to compute the prediction set Ca(ax) as well as the
2

---

Stochastic Online Conformal Prediction with Semi-Bandit Feedback
Another advantage of our algorithm is that it guarantees that 7. S -" with high probability. This guarantee mirrors the distinction between marginal guarantees (Vovk et al., 2005) and probably approximately correct (PAC) (or train- ing conditional) guarantees (Vovk, 2012; Park et al., 2019). Marginal guarantees have the form P2~DD" (x..r)))l E Cz Cx(x)] 2 a, i.e., a coverage over randomness in both the calibration set Z and the new example (z. v/"). They also have the advantage that coverage converges to with the number of calibration examples. In contrast, PAC guaran- tees disentangle these two sources of randomness:
cover the true label with probability at least a on all steps:
vt E .T]. E C. 2 a.
(1)
We want (1) to hold with high probability. A trivial solution to the problem so far is to always take Ti = -o0 Thus, we additionally want to minimize some measure of prediction set size. We consider a loss function Φ + IR, where (Tr) encodes the loss incurred on step t. Then, our goal is to converge the best possible prediction sets over time, which we formalize by aiming to achieve sublinear regret. Consider the optimal prediction set C7 S ) defined by
P PD~D" [P (aay'' E Cz(z)) 2 al 2-
C = E f > +"):
for a given 5 E Rzo- In other words, coverage holds with high probability over Z. Our guarantee Ti S TT is equiva- lent to the coverage guarantee F "'..""""''>""" E Cr,, (x)] 2 a for every t with probability at least 1 - over the whole time horizon. To the best of our knowledge, existing online conformal prediction algorithms all provide marginal cov- erage 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, PAC guarantee makes sense since it ensures our algorithm satisfies the desired coverage rate for every user-provided input. Finally, while we do not provide an explicit guarantee that the coverage converges to a, our regret bound ensures that T. + r", which ensures coverage converges to a.
where 7" is defined by
arg m FER
subj. to Pff vi) 2 2T|
Note that f(rr, v/) 2 7 iff yf E Ci, so this property says that Flył E Cū] 2 By definition, C is the smallest possible prediction set for I, that achieves a coverage rate of a. Then, the expected cumulative regret is
R Σ B(O(T)) "(T")]. LE(T
Intuitively, we need to impose an assumption on our loss because if the loss @ is discontinuous T", then we may achieve linear regret since d(T=)) - <(T*) 2 >> 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(z, y²), where (z,y") ~ D. Then, we have the following assumption:
2. Problem Formulation
Let X' denote the inputs and y denote the labels. Let [T] = =11,2.... ,.). and let E [T] be the steps on which examples (Ie. arrive, where I; is the input on step and 37 is the corresponding ground truth label. We assume given scoring function f= X x y + IR (also called the non-conformity score). The scoring function captures the confidence in whether is the ground truth label for x.
Assumption 2.1. ((T) = (b (T)) for some K Lipschitz continuous function vi (with K E Ro)).
That is, if G*(T) is very flat in some region, then @(7) cannot vary much in that region. For example, consider CDF such that (To = G* = Since we never observe any scores between To and T", we cannot identify r" from (ro.7) from finitely many samples; even a small error in estimating the empirical CDF (e.g.. G.(7*) = G* (7*) + e) can result in significant regret.
We consider a fixed distribution D over X' x V; let P(r, y) be the corresponding probability measure. On each step I, a sample (z+,, v/)) ~ D is drawn. Then, our algorithm observes Ft, and constructs a prediction set C, S y of form
with TO < <"
C. = = E f(x,,) > Tc),
One caveat is this assumption precludes prediction set size as loss, since prediction set size is discontinuous. Next, we assume our loss is bounded:
where T5 E IR is a parameter to be chosen. In other words, our prediction set C, include all labels with score at least Tı in round t. Note that a smaller (resp., larger) T. corresponds to larger (resp., smaller) prediction set C.. Then, our algo- rithm receives semi-bunde feedback-i.e.. it only observes oi if vt E C.. If vi & Cr, it receives feedback in the form of a binary indicator that vf & C..
Assumption 2.2. Φmaz == || < oc.
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. These two assumptions are standard in the bandit literature (Kleinberg et al., 2008). Finally, we make the following assumption:
Next, we describe our desired correctness properties. First, given a coverage rate a E [0, 1), our goal is to ensure we
3

---

Stochastic Online Conformal Prediction with Semi-Bandit Feedback
Assumption 2.3. (² =
Algorithm Semi-bandit Prediction Set (SPS)
Input: horizon T, desired quantile a
Note that (T) is the miscoverage rate of our algorithm for parameter 7. Thus, this assumption says the optimal param- eter value r" achieves coverage rate of exactly a, which simplifies our analysis. Then, our goal is to find the optimal prediction sets Of with coverage rate a. Intuitively, C2 is the smallest set that contains the ground truth label with a high probability. At each step, the algorithm observes dt and returns set C, of candidate labels, and the user either (I) selects the ground truth label yi from Cr or (2) indi- cates that the ground truth label is not in C.. In a document retrieval setting, Zt is a query sent by the user, and Vi is the ground truth document, while in an image classification setting, Te is an image and yf is the ground truth class.
T1 -00 for / to 7 do
if 2 Tr then observe St else St Tt
Compute G. according to (4)
T1-a,1 <- sup(T E IR (T(T) I 1 - a}
Ti f- max (T-att Tt)
end for
One remaining issue is how to handle steps where yi g C,. On these steps, our algorithm substitutes тı for the observation fzr, V²") Intuitively, the reason this strategy works is that the learner does not need to accurately estimate G in the interval [0, r") to recover r"; it is sufficient to include the right fraction of samples in this interval. As long algorithm maintains the property that Ti S r", then Tt lies in this interval, so substituting is sufficient.
3. Algorithm
Next, we describe online conformal prediction algorithm (summarized in Algorithm 1). As before, let f(z be the random variable that is the score of a random sample (ac, y² ~ D, and let G be its CDF By definition, G* (T)= P(f < r] is the miscoverage rate, so
Also, our algorithm includes constraint T-+1 2 Tr for all t. We include this constraint because our estimate G. of the CDF in the interval [O, TE) may be flawed due to semi-bandi feedback. By avoiding going backwards, we ensure that these flaws do not affect our choice of Te+ Again, long Ti S r", this constraint does not prevent convergence.
T* = sup(T G (T) al.
Thus, if we know G*, then our problem can be solved by choosing Ti- = T" 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 f as G.. A naive solution is to choose
Now, we formally define G. as follows. First, define the truncated CDF (T) by
0 (T)
if < if 2 T.
G2(T)
(2)
sup(r E GR) (T)
This CDF captures the CDF where we replace samples 8 S T. with Te- In particular, (T) shifts all the probability mass of G* in the region [0, r²] to a point mass at 7.. Next, the corresponding empirical CDF G. is
However, this strategy may fail to satisfy our desired cov- erage rate due to randomness in our estimate G.- of G*, Failing to account for miscovered examples can exacerbate this problem-if we ignore samples where we failed to cover vr, then our estimate G2 becomes worse, thereby increasing the chance that we will continue to fail to cover yr- This feedback loop can lead to linear regret.
G.(T) = tatte J=1
1 (max (Te, ST).
(3)
Finally, letting 8 = 2/T2 and 6 Vog(2/5)/21, the
To address this challenge, we instead use a high-probabillyy upper bound on G". In particular, for enror bound & E R to be specified, we construct a - confidence bound for the empirical CDF G2 using the Sooreeeky-KKffeeeWoollll (DKW) inequality (Massart, 1990). Letting G. be the upper confidence bound, we instead aim to choose
upper bound G2 on G, from DKW is
(r G.(T) +
(4)
We use this G. to compute T. in Algorithm 1.
Finally, Algorithm 1 satisfies the following theoretical guar- antee: (i) it incurs sublinear regret Ø(VT). and (ii) sat- isfies Cj S C, for all t with probability at least 1-13 2/T:
T; = sup(T E R (T) < a..
On the event that G.-1 is a valid upper bound, then we have S 7* This property ensures that we always cover the ground truth label, which ensures that our subsequent CDF estimate G is valid. As a consequence, our algorithm converges to the true 7*
Theorem 3.1. Algorithm I satisfies
RT S K (2log T Tog + +1) 46 mman
Also, with probability at least 2/T, T. S 7" for aolall t.
4

---

Stochastic Online Conformal Prediction with Semi-Bandit Feedback
4. Proof of Theorem 3.1
Proof. By Lemma 4.2, Ti S S²" implying that (* S (* ). For the upper bound, we have
Our first lemma shows that G, defined in (3) converges uni- formly to Gł defined in (2). Note that the randomness comes from the sequence of random variables 8) f W5).
Gr(TT) S (T)) + 2e, - (Ti) + 22, (T" + 2
=1-a+ 20
Lemma 4.1. For any E Rz0 P[E.]
- 2e 2
20c, where
Next, we consider the lower bound. When 1 1, the inequality trivially holds. Otherwise. at step f 1, To is at least the [(1 - a)(t - 1)J-th order statistic. On the event that 8 2 7r, then Ty is at least the (L(1 a)(( 1)] - 1) order statistic. Thus, we have
E. sup G((T) - - {J rEB
Proof. Let the empirical CDF of s be (T(T) = E 188 s T), and define the events
(T))) 2 ((1 - --)aa-11 2 (1 (1-a)t 2
1 t
If 8t < Tr, then Te is at least the (l(1 - a)t order statistic. Then, we have
Ax sup [G((T) - G]()) >
T<T
G((T22 (11 (11-a)t] (1 at)
2
A2 sup [G+(T) - G;(+)
t t²
claimed.
First, consider Az. For r 2 Tr. by definition of G2 and Gt, we have (T) = (T) and GT(T) = (T). Thus, by the DKW inequality, P[A>]] S 2e 2te", 22-2t' Next, consider Ae. By definition of G. and G2, we have GT( = (T) = 0, so P[Az]= = 0. Thus, by a union bound, we have
Theorem 3.1. Algorithm I satisfies
Ry S K (2log T + + + +1) + 40 moas
Also, with probability at least - 2/T, TE S T for all t.
P[E] & P[A>] + +[Ax]] < 2e 200²
Proof. Define the good event
E Vt E (T)
sup
- GGt)) a.
as claimed.
FEB
By union bound and by Lemma 4.1, we have
Our next lemma shows that with high probability, the desired invariant 7, ~ holds for all E [T].
T
2
F
S
2e
2tr²
< =
T
Lemma 4.2. Suppose sup,e3 [+((T) - (T) S et for all t E [7] with = Vlog(2/8)/2t _Thn, Ti S T* for all t e [T].
(=1
Now, we have
T
R = E
16(+)) - x(T))
E P[E]
Proof. We prove by induction. For the base case, when t == 1, we set Ti -00. Thus, TI I 7- For the in- ductive case, note that Tы < r" by the inductive hypoth- esis, so we have (T) = G (T) for all T 2 T". Then, we have [Gx(T") - (T(r")] = [Gx(T") - Gz(r") & supreR (T+ - (T) S Eg. where the last inequality follows from our assumption. Thus, we have (T*) = Gx(TT) + ex 2 (r")
T
+ E
Σ (((*)) - -o(7))
-E Pl-E]
T
Σ
E [|((T") - p(T:)) E|P
1 a. Recall that we de- fine T1 supfr E IR (T(T) < a); thus, we have o 5 T", Since Th+11 max raJ with Ti-ak S 7" and < r", we have Tk+1 TT
E [|0(TT)) ((T.)) 1-
T
O
E [l( - ((T))) []
Our next lemma bounds the range of (T)) Lemma 4.3. Suppose suP-Er [G((T) - (T) S for all
T
+
E 120max | -E
E [ with e, Vlog(2/ 211 Then, for all L E [T], we have
1=1
T
Σ
E Bl(((T)) - ((T))) E
+ 40maz.
2 (T) t
1 - a
< ---a-k a
Xx
5

---

Stochastic Online Conformal Prediction with Semi-Bandit Feedback
The first inequality follows from Assumption 2.2. Using
questions and documents by 2 and D, respectively, then DPR consists of question encoder Eq Q - R and document encoder ED D + I2 7678,, Given question and set of candidate documents D _ D, the similarity score between document d E D and question q is
Lemma 4.3, can bound X₁ follows:
X, = E - E]]
(G E]
S KF" Gr []]
En(g) sq.d [b [ED(d)
KE
[1 - G((n) + +..))) G" (T)) E]
KE
a
+ - ( E
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.
2
KE
max
7 22t
+ +.((TT)) - GG((T] E
2
S K max
+ +2KE
sup
G((T) (T)
E
Our dataset is SQuAD question-answering dataset (Ra- jpurkar et al., 2016), popular reading comprehension benchmark. Each question in SQuAD can be answered by finding the relevant information in corresponding Wikipedia paragraph known as the context. The authors of DPR make a few changes to adapt SQuAD to document retrieval. First, paragraphs are further split into multiple, dis- joint 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 set of irrelevant documents." 2 In our experiments, for each question, we include one ground truth document and all the irrelevant documents to create the set of candidate documents.
JER
2
(2/()
log(2/8)
S K max
2
2K
8
2t
2t
2K + 4Kv
1og(2/8)
21
where the first incquality follows from Assumption 2.1 and the third inequality follows from Lemma 4.3. Thus, we have
T
T
2K
log T
Σ
X1
+ 4K
1
1
1=1
S
K
2 2oog T + 1 + 4v 4//Tlog
Recond-price auctions task. Lastly, we consider the sce- nario of setting reservation prices in second-price auctions, well-studied problem that has semi-bandit feedback (Cesa- Bianchi et al., 2014; Zhao & Chen, 2020). In this problem, seller (the auctioneer) repeatedly sells the same type of items to a group of bidders. In each round 4, she publicly announces a reservation price p', while bidders draw their private values of from a fixed distribution that is unknown to the seller. For each bidder i, she will submit the bid B; of if and only if of 2 p². The seller obtains reward R.:
The claim follows.
5. Experiments
5.1. Experimental Setup
Image classification task. We use the Vision Trans- former (Dosovitskiy et al., 2020) model on the ImageNet dataset (Deng et al., 2009).' Each image from the dataset be- longs to exactly one class out of the 1,000 candidate classes. Consequently, the cardinality of the label domain is 1,000 (i.e., | = 1000). In the experiments, images arrive se- quentially, and our algorithm aims to construet 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 fi we use the logits instead of the softmax function to evaluate sensitivity to the choice of scoring function.
0
if > B(A)) if BB22 < $ BB1) if < (22))
R₁
pz
B(2)
where B("), .x(2) denote the highest and second-highest bid received by the seller in round implying that the seller only observes bids that are higher than p². We consider a seller that aims to learn
Document retrieval task. Next, we consider the Dense Passage Retriever (DPR) model (Karpukhin et al., 2020) the SQuAD ceastioonanswering dataset. DPR leverages dual-encoder architecture that maps questions and candidate documents to embedding vectors. Denoting the space of
p" arg maxp p subj. to PP(B()) pl a. PER
"In the data, all questions are paired with 50 irrelevant docu- ments, We construct the candidate documents set by including all 50 irrelevant documents and ground truth document. We exclude questions that have 0 ground truth documents. The data were obtained from DPR's 's public Github Repo: https: / com/ f acebookreeearrch /DR with licenses CC BY-SA 4.0 and CC BY-NC 4.0
OOtaained from https:/ //www image- image-net.cc pret.org// with custom and non-commercial license; we use the 16 x 16 down sampled version.
6

---

Stochastic Online Conformal Prediction with Semi-Bandit Feedback
Log Expected Cumulativve Regret
Log Expected Curullativs Regret
Log Expected Cumuletive Regret
-0-
10
Algerithm dlogt ACI DLR Greedy
Algorithim /Blog ACI DLR
Algerithm
Vdlgg ACI DLR
Greedy
Gready
0-
SP5
SPS
SPS
2500
5000
7530
10000
2500
5000
7500
10000
2500
5000
7500
10000
Step
Step
Step
(a) IetgeNet
(b) SQuAD
(c) Auction
Figure 1. Cumulative Regret
0.9
Coverage Rate
0.8-
Coverage Rate
Coverage Rate
Nlgoiihh DLR Creedy
Aigortthm DLR Greedy SPS
Algorithm XCI DLR
0.8
Greedy SP5
0.7
0.6
0.6
0.5
2500
5000
7500
10000
2500
5000
7500
10000
2500
5000 Step
7500
10000
(a) ImageNet
(h) SQuAD
(c) Auction
Figure 2. Coverage Rate
That is, the seller aims to find the highest reservation price such that she can sell the item with probability at least a. This problem can be solved using online conformal predic- tion. Following standard practice (Mohri & Medina, 2014), we use a synthetic dataset that adapts from eBay auction data (Jank& & Shmueli, 2010). Specifically, we simulate the distribution of v by using the empirical distribution of the observed bids in the dataset.
Lastly, we consider the Decaying Learning Rate (DLR) algorithm proposed in (Angelopoulos et al., 2024b). In contrast to ACI, DLR directly performs gradient descent on the cutoffs T instead of the quantiles ay; it can be viewed as running ACI with (( = a. We set the learning rate to the one used the experiments from the original paper-i.e.. 7) 1/2- with 0.1. We show results for two additional basclines, explore-then then--mmthe-- (ETC) and conservative ETC, in Appendix A.
Baselines. We compare to greedy, Adaptive Conformal Inference (ACI) (Gibbs & Candes, 2021), and Decaying Learning Rate (DLR) (Angelopoulos et al., 2024b). The greedy strategy chooses
Experiment parameters. We use a = 0.9 and = 10000, and report averages across 10 runs. The shaded areas are the 95% confidence intervals computed from 10 runs.
Metries. First, we consider the cumulative regret for the following reward function d:
Ti = supfr E R (((T) 1-
at every step, which cannot guarantee the a coverage rate, leading it to undercover significantly more than desired. Next, Adaptive Conformal Inference (ACI) adjusts a (and then T() based on whether the ground truth label in the previous round's prediction set. We choose the learning rate y from grid search in a candidate set proposed in (Gibbs& & Candès, 2024). To run ACI in our semi-bandit feedback setting, we only update the quantile function Q when ground-truth label yf observed; as we show, this biased strategy for updating Qu leads it to fail to achieve the desired coverage rate.
((T) A) (1) i < (1 a) x2) - -a) if (1 a),
for some 0 < A1 < A2; we take \ = 0.1 and X 10. Note this loss imposes a larger penalty for undercovering compared to overcovering. Next, we consider coverage rate:
T
Coverage Rate
1 E Ct).

---

Stochastic Online Conformal Prediction with Semi-Bandit Feedback
10000
100C0
10000
Undercoverage Count
Undercoverage Count
7500
7500
7500
Undercoverage
Algorithm DUR Greedy
Algorithi ACI DLR Greedy SPS
Algerithm ACI DUR
5000
Greedy
2500
2500
2500
0
2500
5000 Step
7500
10000
2500
5000
7500
10000
0
2500
5000
7500
10000
Step
Step
(a) ImageNet
(b) SQuAD
(c) Auction
Figure 3. Undercoverage Count
Third, we consider the number of times > r" which
Undercoverage count. Finally, Figure 3 shows the un- dercoverage count. Note that greedy and ACI frequently undercover. ACI has high undercoverage count because the prediction set oscillates between being too small (i.e., Tt > 7²) and too large (i.e., T₁ < <²). This behavior can be undesirable since it means that different inputs have differ- ent coverage probabilities. In contrast, undercovers since is guaranteed to converge to r" from below. Interestingly, DLR also does not undercover. While their algorithm is not guaranteed to satisfy this property, it incrementally estimates T by starting from a conservative т. Thus, if the learning rate is small enough, would not undercover until 7. gets significantly closer the true r".
measures the violation of our safety condition:
Undercoverage Count = E((T)TT).
1=1
Our goals are to (i) achieve Ö(VT) regret, while (ii) main- taining the desired a coverage rate, and (iii) achieving zero undercoverage count with probability at least 1 d over the entire time horizon.
algorithm never
5.2. Results
Regret. First, Figure 1 shows the cumulative regret of each approach on each task. We applied the log-scale for better readability, As can be seen, our algorithm consistently ob- tains the lowest regret. The ACI algorithm attains a regret level comparable to the greedy algorithm because its quan- tile function is updated with 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-bandin feedback- particu- lar, the empirical estimate G2 of the distribution becomes increasingly truncated. Moreover, the poor performance of DLR can be attributed to the fact that 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 the optimal prediction sets. For many scoring functions, we do not have prior knowledge of the score's range, which exacerbates these is- sues. These issues are particularly salient when we consider tasks such as the second-pric price auction, where the score's 's range (i.e., the range of bids) can difficult to predict in advance. In contrast, our algorithm consistently performs and does not have any hyperparamters to tune.
Summary. These results show that our algorithm achieves (and converges to) the desired coverage rate while achieving sublinear regret and maintaining т: < r". In contrast, ACI and greedy fail to achieve the desired coverage rate, and DLR converges much more slowly than our algorithm.
6. Conclusion
We have proposed a novel conformal prediction algorithm for constructing online prediction sets under stochastic semi- bandit feedback. We have shown our algorithm can be ap- plied to learn optimal prediction sets in image classification, document retrieval, and second-price auction reservation price prediction. Our experiments show we achieve the de- sired coverage level while achieving prediction set sizes that achieve sublinear regret and zero undercoverage count.
Impact Statement
Our approach aims to improve the trustworthiness of ma- chine learning models via reliably uncertainty quantification; do not foresee any ethical concerns.
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.
8

---

Stochastic Online Conformal Prediction with Semi-Bandit Feedback
References
Karpukhin, V., Oguz, B., Min, S., Lewis, S., Wu, L.,
Edunov, S., Chen, D., and Yih, W.-t. Dense passage retrieval for open-domain question answering. In EMNLP (1), Pp. 6769-6781, 2020.
Angelopoulos, A., Candes, E., and Tibshirani, R. J. Confor- mal pid control for time series prediction. Advances in neural information processing systems, 36, 2024a.
Kleinberg, R., Slivkins, A., and Upfal, E. Multi-armed bandits in metrie spaces. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pp. 681 190, 2008
Angelopoulos, A. N., Barber, R., and Bates, S. Online con- formal prediction with decaying step sizes. In Salakhut- dinov, R., Kolter, Z., Heller, K., Weller, A., Oliver, N., Scarlett, J., and Berkenkamp, F. (eds.), Proceedings of the 4sst International Conference on Machine Learning, vol- ume 235 of Proceedings of Machine Learning Research, pp. 1616-1630. PMLR, 21-27 Jul 2024b.
Lewis, P., Perez, E., Piktus, A., Petroni, F., Karpukhin, V., Goyal, N., Küttler, H., Lewis, M., Yih, W.-t,, Rocktäschel, T., et al. Retrieval-augmented generation for knowledge- intensive nlp tasks. Advances in Neural Information Pro- cessing Systems, 33:9459-9474, 2020.
Bastani, O., Gupta, V., Jung, C., Noarov, G., Ramalingam, R., and Roth, A. Practical adversarial multivalid confor- mal prediction. Advances in Neural Information Process- ing Systems, 15:29362-293773 2022.
Massart, P. The tight constant in the dvoretzky kiefer- wolfowitz inequality. The annals of Probability, pp. 1269- 1283, 1990.
Bates, S., Angelopoulos. A., Lei, L., Malik, J., and Jor- dan, M. Distribution-free, risk-controlling prediction sets. Journal of the ACM (JACM), 68(6):1-3,, 2021.
Mohri, M. and Medina, A. M. Learning theory and algo- rithms for revenue optimization in second price auctions with reserve. In International conference machine learning, pp. 262-270. PMLR, 2014.
Bhatnagar, A., Wang. H., Xiong, C., and Bai, Y. Improved online conformal prediction via strongly adaptive online learning. In International Conference on Machine Learn- ing. pp. 2337-2363 PMLR, 2023.
Park, S., Bastani, O., Matni, N., and Lee, I. Pac confidence sets for deep neural networks via calibrated prediction. arXiv preprint wrXiv:2001.00//0 2019.
Cesa-Bianchi N., Gentile, C.,, and Mansour, Y. Regret minimization for reserve prices in second-prict auctions. IEEE Transactions on Information Theory, 61 61(1):549- 564, 2014.
Rajpurkar, P., Zhang. J., Lopyrev, K., and Liang, P. SQuAD: 100,000+ questions for machine comprehension of text. In Su, J., Duh, K., and Carreras, X. (eds.), Proceedings of the 2016 Conference on Empirical Methods in Natu- ral Language Processing, pp. 2383-2392, Austin, Texas, November 2016. Association for Computational Linguis- tics. doi: 10.118533/1IDDU 1264.
Deng, J., Dong. W., Socher, R., Li, L.-J,, Li, K., and Fei-Fei, I. Imagenet: A large-scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pp. 248-255. leee, 2009.
Dosovitskiy, A., Beyer, L., Kolesnikov, A., Weissenbom, D., Zhai, X., Unterthiner, T., Dehghani, M., Minderer, M., Heigold, G., Gelly, S., et al. An image is worth 16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010.1 1929, 2020.
Shuster, K., Poff, S., Chen, M., Kicla, D., and Weston, J. Retrieval augmentation reduces hallucination in con- versation. In Moens, M.-F., Huang, X., Specia, L., and Yih, S. W.-t. (eds.), Findings of the Association for Computational Linguistics: EMNLP 2021, pp. 3784- 3803, Punta Cana, Dominican Republic, November 2021. Association for Computational Linguistics. doi: 10.18653/ 1/25533/112221111 htt.:///w//222....mmin--eeemmmi findiing---mmlp..2....
Gibbs, I. and Candes, E. Adaptive conformal inference under distribution shift, Advances in Neural Information Processing Systems, 34: 14:666616 2021.
Gibbs, I. and Candès, E. J. Conformal inference for online prediction with arbitrary distribution shifts. Journal of Machine Learning Research, 25(162):1-36,, 2024.
Tibshirani, R. J., Foygel Barber, R., Candes, E., and Ramdas, A. Conformal prediction under covariate shift. Advances in neural information processing systems, 32, 2019.
Jank, W. and Shmueli, G. Modeling online auctions. John Wiley& & Sons, 2010.
Vovk, V. Conditional validity of inductive conformal pre- dictors. In Asian conference on machine learning, pp. 475-490. PMLR, 2012.
Ji, Z., Lee, N., Frieske, R., Yu, T., Su, D., Xu, Y., Ishii, E., Bang, Y. J., Madotto, A., and Fung, P. Survey of halluci- nation in natural language generation. ACM Computing Surveys, 55(12):1-38, 2023.
Vovk, V., Gammerman, A., and Shafer, G. Algorithmic learning in a random world. Springer Science & Business Media, 2005.

---

Stochastic Online Conformal Prediction with Semi-Bandit Feedback
Zhao, H. and Chen, W. Online second price auction with semi-bandit feedback under the non-stationary setting. In Proceedings of the AAAI Conference Artificial Intelli-
gence, volume 34, pp.
2020.
10

---

Stochastic Online Conformal Prediction with Semi-Bandit Feedback
A. Additional Experiments
consider two additional baselines, First, explore-then- commit (ETC) chooses T -00 in the first m steps, and then commits to
T: = sup(T (T) I a.).
Next, conservative ETC (Con-ETC) uses the same strategy, except commits
Tt sup(r T E R G. (T) $1 a}
after the exploration period. In other words, it commits to a conservative choice of т that satisfies our coverage guarantee, and also guarantees S 7" with probability at least 1 2/T.. The number of exploration rounds are chosen via 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 does not adaptively choose 7r over time.

---

Stochastic Online Conformal Prediction with Semi-Bandit Feedback
Expected Curulaative Regret
Log Expertod Currulative Regret
Log Expected Currulative Regret
Con
Con-k IC ETC SPS
Con-eIc
ETC SPS
ETC
SPS
-2.5
-3
-5
5000
Step
Step
Step
(a) ImageNet
(b) SQuAD
(c) Auction
Figure 4. Cumulative Regret
Coverage Rate
0.9/5
Coverage Rate
0.3/5
Coverage Rate
0.9/5
Algorithm Con-ETC ETC SPS
Algorithm Con-ETC ETC
Algorithm
0.950
Con-ETC
0.925
0.925
0.925
2500
5000 Step
7500
10000
2500
5000
7500
10000
2500
5000
7500
10000
(a) ImageNet
(b) SQuAD
(c) Auction
Figure 5. Coverage Rate
Undercoverage Count
4000
Undercoverage Count
3000
4000
Undercoverage
Algorithm CTC-ETC CTC SPS
3000
Algenthm LTC CTC
2000
Con-CTC CTC SPS
2000
2000
SP5
1000
1000
0
2300
5600 Step
7500
10000
2500
5000 Step
7500
10000
2500
5000 Step
7500
10000
(a) ImageNet
(b) SQuAD
(c) Auction
Figure 6. Undercoverage Count
12


Reviews:
[{"review_id": "YLz9xUstHs", "reviewer": "Reviewer_EvQo", "summary": "This paper introduces an online conformal prediction method with semi-bandit feedback (i.e. we only observe the true label if it is contained in the prediction set). Authors show that, under the iid setting, their method controls the expected cumulative regret and that $\\tau_t$ (the threholding value at time $t$) converges to $\\tau^*$ the optimal one at $t$ goes to infinity. More importantly, they show that $\\tau_t \\leq \\tau^*$ for all $t$ with high probability. They finally We evaluate the algorithm on several task to empirically show that they achieve performance compared to several baselines.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thoughtful comments; we address major concerns below.\n\n**Concern 1: Comparison to [1]**\n\nBy our understanding, the algorithm in [1] cannot be straightforwardly modified to handle semi-bandit feedback. Specifically, they use a strangeness measure $A_t:(z_1,...,z_t)\\mapsto(\\alpha_1,...,\\alpha_t)$ (Eq (8) in [1]) to construct prediction sets, where $z_i=(x_i,y_i)$ is a calibration example; e.g.:\n$$\\alpha_i=\\frac{\\min_{j\\neq i:y_j=y_i}d(x_i,x_j)}{\\min_{j\\neq i:y_j\\neq y_i}d(x_i, x_j)}.$$\n\nClearly, computing $\\alpha_i$ requires the true label $y_i$. Next, given a new input $x_t$, they return the prediction set of all labels $y$ such that $\\alpha$ satisfies  \n$$\\frac{\\\\#\\\\{i=1,...,t:\\alpha_i\\ge\\alpha\\\\}}{t} \\ge\\delta,$$\nwhere  \n$$(\\alpha_1,...,\\alpha_{t-1},\\alpha)=A_t((x_1,y_1),...,(x_{t-1},y_{t-1}),(x_t,y))$$  \nis the strangeness measure assuming the true label for $x_t$ is $y$ (Eqs (9) to (11) in [1]). Thus, to construct $\\alpha$, they require $\\alpha_i$ for all $i$, so all true labels $y_i$ are required. This requirement persists in their modifications (Eqs (16), (20)–(21) in [1]).\n\nOur main contribution is precisely to handle semi-bandit feedback. We will add a discussion.\n\n**Concern 2: i.i.d.**\n\nWe believe the i.i.d. assumption is reasonable in our active learning setting. We agree that extending our work to the adversarial setting is an important direction, but it is beyond the scope of our paper.\n\n**Concern 3: Re-learn $f$**\n\nWe believe there are practical settings where training is decoupled from calibration, especially when training is costly (e.g., LLMs). One of our applications involves using a pretrained document retriever in a new domain where fine-tuning may be infeasible. However, we agree that extending to settings where the model $f$ is updated is important and will add a discussion.\n\n**Concern 4: Simple use of DKW**\n\nAs discussed above, we do not believe [1] can easily be adapted to semi-bandit feedback. Also, we emphasize that a naïve application of DKW is insufficient; we have introduced additional novel techniques to handle semi-bandit feedback.\n\n**Concern 5: Image Readability**\n\nWe have updated Figure 1 to use a log scale:  \n<https://imgur.com/a/j05QwzS>\n\n**Q3: Line 213 $\\tau_t$ convergence**\n\nOur convergence guarantee is based on the fact that the empirical CDF converges to the true CDF, i.e., $\\overline{G}_t$ converges to $G^*$ for $\\tau\\in[\\tau^*,+\\infty)$. For intuition, consider full feedback. Let $G'_t$ denote the empirical CDF. Similar to Eq (4), define  \n$$\\overline{G}'_t(\\tau)=G'_t(\\tau)+\\epsilon_t$$  \n\nwhere $\\epsilon_t=\\sqrt{\\log(2/\\delta)/2t}$, and choose  \n$$\\tau_t=\\sup\\\\{\\tau\\in\\mathbb{R}\\mid\\overline{G}'_{t-1}(\\tau)\\le1-\\alpha\\\\}.$$  \nBy DKW, $\\overline{G}'_t(\\tau^*)$ converges to $G^*(\\tau^*)$, so $\\tau_t$ converges to $\\tau^*$. The convergence rate $O(t^{-1/2})$ comes from DKW.\n\nWith semi-bandit feedback, convergence is not guaranteed a priori. However, Lemmas 4.1 and 4.2 show our CDF upper bound $\\overline{G}_t(\\tau^*)$ still converges to $G^*(\\tau^*)$. Thus, $\\tau_t$ converges to $\\tau^*$, with the same convergence rate.\n\n**Q4: FCP**\n\nApologies, we are not sure what \"FCP\" means. The false negative rate (FNR) is controlled by the coverage guarantee (assuming a false negative is a miscovered example). We are not aware of an analog of false positive rate (FPR) in conformal prediction. One guarantee of existing conformal prediction algorithms is the coverage rate is also not too much higher than desired, i.e., they are not overly conservative. Our regret guarantee provides such a bound. Consider the loss $\\phi(\\tau)=1-\\min\\\\{G^*(\\tau),G^*(\\tau^*)\\\\}$ (the min ensures the step-wise regret is non-negative). On the event $\\tau_t\\le\\tau^*$ for all $t$ (which holds with high probability by Lemma 4.2), the step-wise regret is  \n$$r_t=\\phi(\\tau_t)-\\phi(\\tau^*)=G^*(\\tau^*)-G^*(\\tau_t)=\\mathbb{P}[\\tau_t\\le f(x_t,y_t^*)\\le\\tau^*],$$  \ni.e., $r_t$ is the overcoverage probability that we cover $y_t^*$ but the oracle does not. By Theorem 3.1, $r_t=O(\\sqrt{\\log t/t})$, so the overcoverage probability converges to zero. We will add a discussion.\n\n**Q5: Example on $\\phi$**\n\nNote that Algorithm 1 does not depend on $\\phi$; it is introduced solely to evaluate the algorithm's performance. The example in our experiments is a practical choice; the overcoverage rate above is another.\n\n**Q6: Conservativeness**\n\nThis is a consequence of our PAC guarantee and semi-bandit. Our algorithm ensures $\\alpha$-coverage at every $t$, which implies $\\tau_t\\le\\tau^*$ for all $t$. However, as shown in our regret analysis, $\\tau_t$ is guaranteed to converge to $\\tau^*$, with convergence rate given by DKW.\n\n**Q7: Dynamic Regret**\n\nSince we consider the i.i.d. setting, the optimal policy is static (i.e., $\\tau_t=\\tau^*$), so our regret equals dynamic regret. We believe extensions to the adversarial setting (where static and dynamic regret are distinct) is beyond the scope of our paper.", "claims_and_evidence": "Yes, the claims are clear. However, in my opinion, the iid assumption is an important one (especially in online CP) and should appear in the theorem.", "methods_and_evaluation_criteria": "Yes, the evaluation makes sense.", "theoretical_claims": "Yes, I partially check the proofs and it seems that this is ok.", "experimental_designs_or_analyses": "Yes, the experimental design seems correct to me.", "relation_to_broader_scientific_literature": "The article assumes an iid framework, which is a bit different from the previous article on online CP. Furthermore, my main concern on this point is that I don't understand how this article compares to [1]. My first impression is that [1] does the same thing as this article but better (I think the semi-bandit feedback can be easily handled by [1]'s technique). But maybe I am wrong and I would like to hear the authors' opinion on this point.\n\n[1] “On-Line Confidence Machines Are Well-Calibrated” by Vladimir Vovk.", "essential_references_not_discussed": "No, everything is ok (except maybe [1] ; see previous point).", "other_strengths_and_weaknesses": "Strenghts:\n\n1\\ The subject is of huge interest for the CP community.\n\n2\\ The paper is well written and quite easy to follow.\n\nWeaknesses:\n\n1\\ The paper only consider the iid setting\n\n2\\ The $f$ function is not time-dependent. In a real-life scenario, we probably want to use the new points to improve our $f$ function.\n\n3\\ This point could also be a strenght (depending on your point of view), but the method is in the end an application of DKW inequality (reason why I think that [1] is better -- but I could be wrong).\n\n4\\ The figures are not very easy to read. Maybe a logarithmic scale or something like that would be better.\n\n5\\ The code is not provided.", "other_comments_or_suggestions": "Minor:\n\n1\\ Line 75: \"Angelopoulos et al. (2024b) points out that ACI still works if we take the “quantile function” to be the identity function ..\" I do not understand this remark. Do you mean that the update in ACI can be made on $q_t$ and not on $\\alpha_t$?\n\n2\\ Line 84: \"we show that a standard variation the scoring function\" problem in the sentence.\n\n3\\ Line 104: \"convergence of $\\tau_t$ to $\\tau^*$\" They are never defined before this paragraph. Therefore, on first reading, we cannot understand this statement. Overall, the text sometimes refers to mathematical objects that are not yet defined.\n\n4\\ Line 433: \"hyperparamters\"", "questions_for_authors": "1\\ My first concern is about the paper [1]. It seems to me that because you assume that the data are iid, then the method of [1] is better bu maybe I am wrong. Can you elaborate on this?\n\n2\\ Throughout the paper, $f$ is fixed at the beginning. Do you think it is possible to “relearn” the score function as new points are observed?\n\n3\\ Line 213 \"As a consequence, our algorithm converges to the true $\\tau^*$\". Why? can you elaborate on this? Furthermore, do you think that it is possible to obtain a rate of convergence?\n\n4\\ In general, papers in online CP control the FCP. Do you think it could be possible to have such result here? (Perhaps it is trivial due to the fact that $\\tau_t \\leq \\tau^*$).\n\n5\\ Can you give some important examples on $\\phi$?\n\n6\\ In the experiment, it seems that the method is relatively conservative with coverage around 0.95 even with $T=10000$ points. Can you elaborate on this?\n\n7\\ Minor question: In the online literature, they also control dynamic regret. Do you think it is possible to do that here?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "AjyeYc7Eaz", "reviewer": "Reviewer_tSo8", "summary": "The paper proposes a novel stochastic online conformal prediction algorithm designed for constructing prediction sets under semi-bandit feedback. It addresses the challenge of sequential decision-making where feedback is limited to partial information (e.g., only observing certain bids or labels). The algorithm ensures desired coverage rates while achieving sublinear regret and maintaining zero undercoverage count. The authors demonstrate the algorithm's effectiveness across three tasks: image classification (ImageNet), document retrieval (SQuAD), and second-price auctions. The key contributions include a new approach to conformal prediction that is robust to semi-bandit feedback and does not require hyperparameter tuning. Experimental results show that the proposed method outperforms existing strategies in terms of regret, coverage rate, and undercoverage.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful comments. We address the questions and major concerns below:\n\n**Concern 1: Additional Comparative Analysis**  \n\nWe appreciate the reviewer’s suggestion. In both our discussions and experiments, we have considered a comprehensive set of popular online conformal prediction algorithms from recent literature that operate in similar contexts, and we demonstrate that our algorithm outperforms them in the semi-bandit setting. We believe these scenarios already demonstrate challenging and practical applications of our techniques, but we are happy to consider additional scenarios the reviewer might have in mind.\n\n**Concern 2: Key Assumptions**  \n\nAssumption 2.1 rules out cases where the reward varies substantially in regions where the CDF $G^*$ is very flat. In such regions, the number of observed samples is typically small. Therefore, if $\\tau^*$ lies in a flat region of $G^*$ and the reward fluctuates significantly, the accrued regret can be large. This type of regularity condition is common in regret analyses within the bandit literature, where some assumptions on the reward mechanism are required to ensure meaningful guarantees (e.g., see [1]).\n\nThe bounded reward assumption in Assumption 2.2 typically holds in practice. First, since the CDF $G^*$ is a bounded function, it is natural to assume that the reward $\\phi(\\tau) = \\psi(G^*(\\tau))$ is also bounded. Alternatively, if we consider $\\phi$ as representing the prediction set size, the assumption still holds because prediction set sizes are inherently bounded. The bounded reward condition is also standard in regret analyses (e.g., see [2]).\n\nNext, we show that Assumption 2.3 can be removed with some additional technical work. We begin by redefining $\\tau^*$ as $\\tau^* = \\sup\\\\{\\tau: G^*(\\tau) \\le 1 - \\alpha\\\\}$, and let $1 - \\alpha' = G^*(\\tau^*)$. The proof then proceeds almost identically as before, with $1 - \\alpha'$ substituted for $1 - \\alpha$. The only complication is that $\\tau_t$ is still computed using $\\alpha$. However, since the DKW inequality applies to arbitrary CDFs, we can still show that $\\tau_t \\le \\tau^*$ with probability at least $1/T^2$. As a result, we obtain that $G(\\tau_t) \\to 1 - \\alpha'$, i.e., our algorithm maintains and converges to an $\\alpha'$-coverage rate. With these modifications, our regret guarantee continues to hold.\n\nIn the experiments section, we choose a loss function (lines 374–377, right column) that satisfies Assumptions 2.1 and 2.2. Since relaxing Assumption 2.3 does not impact our regret or coverage guarantees, we use the observed empirical distribution of scores as the ground-truth distribution.\n\n[1] Kleinberg, Robert, Aleksandrs Slivkins, and Eli Upfal. \"Multi-armed bandits in metric spaces.\" In Proceedings of the fortieth annual ACM symposium on Theory of computing, pp. 681-690. 2008.  \n[2] Auer, P. \"Finite-time Analysis of the Multiarmed Bandit Problem.\" (2002).\n\n**Concern 3: Limitations**  \n\nOne limitation of our algorithm is that it currently operates under the i.i.d. assumption, whereas several existing online conformal prediction approaches are designed to work in adversarial setting; however, these existing techniques cannot handle semi-bandit feedback. With respect to different feedback mechanisms, our algorithm also functions in the full-information feedback setting without modification; however, in this case, there may be more effective strategies than our algorithm. Finally, one might also consider bandit (instead of semi-bandit) feedback, but it is not clear what that would look like in the conformal prediction setting. We are happy to add a discussion to our paper.\n\n**Question 1: Noisy and Sparse Labels**  \n\nIn general, conformal prediction naturally handles label noise, since the ground truth label $y^*$ is assumed to be a random variable even conditioned on $x$. In terms of \"extreme cases\", our coverage and regret guarantees still hold but the prediction sets may be large. Regarding sparsity, we note our conformal prediction setting is special, and our semi-bandit feedback cannot be sparse -- we only fail to observe the true label when it is miscovered, which happens with probability at least $\\alpha$. We are happy to add a discussion to our paper.\n\n**Question 2: Computation Efficiency**  \n\nAs our algorithm only needs access to the empirical score distributions, the computational efficiency does not depend on the choice of the coverage rate $\\alpha$. For the same reason, the scaling of our algorithm does not depend on the data dimensionality except through how long it takes to evaluate the predictive model. Since it is an online algorithm, its computation time scales linearly in the size of the dataset (with constant compute per iteration) and uses constant memory. These scalability properties are similar to existing conformal prediction algorithms. We are happy to add a discussion to our paper.", "claims_and_evidence": "Yes, the claims made in the submission are supported by convincing evidence. The paper provides experimental results across multiple tasks (ImageNet, SQuAD, second-price auctions) demonstrating that the proposed algorithm outperforms existing methods (e.g., ACI, greedy, and DLR) in terms of cumulative regret, coverage rate, and undercoverage count. The results are backed by quantitative metrics and comparisons, including regret, coverage rate, and undercoverage count, which show the algorithm’s superior performance.", "methods_and_evaluation_criteria": "Yes, the proposed methods and evaluation criteria are well-suited for the problem. The use of benchmark datasets like ImageNet, SQuAD, and second-price auctions aligns with the tasks being evaluated (image classification, document retrieval, and auction reservation price prediction). The evaluation criteria, including cumulative regret, coverage rate, and undercoverage count, effectively measure the algorithm's performance in achieving reliable prediction sets under stochastic semi-bandit feedback.", "theoretical_claims": "High-level the proofs presented, particularly the bounds on cumulative regret and coverage rate, appear mathematically sound based on the assumptions and lemmas provided, but want to acknowledge that I did not check everything in details for the correctness of the proofs.", "experimental_designs_or_analyses": "based on the description, the experimental setup appears appropriate for evaluating the proposed method, with tasks like image classification, document retrieval, and second-price auction reservation price prediction used to assess the algorithm's performance across different domains. The metrics (cumulative regret, coverage rate, and undercoverage count) are well-suited for the problem.", "relation_to_broader_scientific_literature": "The paper's key contributions—developing a stochastic online conformal prediction algorithm with semi-bandit feedback—build upon and extend prior work in conformal prediction, online learning, and semi-bandit feedback. Specifically, it relates to prior methods like Adaptive Conformal Inference (ACI), Decaying Learning Rate (DLR), and greedy strategies, highlighting the limitations of these approaches (e.g., failure to maintain coverage rate and suboptimal regret). The paper builds on existing work in these areas by proposing a method that guarantees coverage rate, sublinear regret, and zero undercoverage, addressing issues like biased updates and slow convergence in existing algorithms. This contributes to improving prediction set reliability and uncertainty quantification in various machine learning tasks.", "essential_references_not_discussed": "The paper sufficiently cites foundational works such as ACI, DLR, and greedy algorithms, but it could benefit with further discussion on more recent advancements in conformal prediction and semi-bandit feedback. Specifically, recent work on the adaptation of conformal prediction methods to deep learning models (such as those applied to large-scale image or text datasets) could further strengthen the background context.", "other_strengths_and_weaknesses": "Strengths:\n- The paper presents an original approach by combining conformal prediction with semi-bandit feedback, addressing a gap in the existing literature.\n- It demonstrates a practical application to real-world tasks (image classification, document retrieval, second-price auctions) which adds significant relevance.\n- The experimental results are thorough, showing that the proposed method outperforms several baselines, particularly in maintaining coverage and achieving sublinear regret.\n\nWeaknesses:\n- While the proposed method is effective, the paper could benefit from additional comparative analysis against a broader set of methods or more challenging scenarios.", "other_comments_or_suggestions": "- The paper would benefit from a clearer explanation of the key assumptions and how they relate to the experimental setup.\n- It would be useful to provide a more detailed discussion on the limitations of the proposed method, especially in edge cases or different types of feedback.", "questions_for_authors": "How does your proposed algorithm handle extreme cases where the semi-bandit feedback is highly noisy or sparse? A more detailed explanation of its robustness in such scenarios would clarify its practical applicability.\n\nCan you provide a more in-depth explanation of the trade-off between computational efficiency and the desired coverage rate in your method, especially when dealing with large-scale datasets?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "P6RR0eWIPR", "reviewer": "Reviewer_D2GR", "summary": "The paper introduces a novel algorithm for online conformal prediction in settings where only partial feedback is available, specifically semi-bandit feedback. Conformal prediction is a framework for uncertainty quantification that outputs prediction sets with guaranteed coverage probabilities. The key challenge addressed in this work is the lack of a large calibration dataset, which is typically required for conformal prediction. Instead, the authors consider an online setting where examples arrive sequentially, and the true label is only observed if it is contained in the prediction set.\n\nThe proposed algorithm, Semi-bandit Prediction Set (SPS), dynamically constructs prediction sets over time. It uses a high-probability upper bound on the cumulative distribution function (CDF) of the scoring function to ensure that the prediction sets maintain the desired coverage rate. The algorithm guarantees sublinear regret, providing strong theoretical guarantees and empirical performance. The algorithm is applicable to a wide range of real-world tasks, including document retrieval, image classification, and auction price-setting.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful comments. We address the questions and major concerns below:\n\n**Concern 1: Lemma 4.2** \n\nWe apologize for the confusion. A more detailed proof is included below:\n\n*Base case:* when $t = 1$, we set $\\tau_1 = -\\infty$. Thus, $\\tau_1 \\le \\tau^*$.\n\n*Inductive Hypothesis:* Assume $\\tau_k \\le \\tau^*$ for some $k \\ge 1$.\n\nWe prove $\\tau_{k+1} \\le \\tau^*$ under our assumption $\\sup_{\\tau \\in R}|G_t(\\tau) - G_t^*(\\tau)| \\le \\epsilon_t$ for all $t \\in [T]$. Note that $\\tau_k \\le \\tau^*$ by the inductive hypothesis, so we have $G_k^*(\\tau) = G^*(\\tau)$ for all $\\tau \\ge \\tau^*$. Thus, we have\n\n$$\n|G_k(\\tau^*) - G^*(\\tau^*)| = |G_k(\\tau^*) - G_k^*(\\tau^*)| \\le \\sup_{\\tau \\in R}|G_k(\\tau) - G_k^*(\\tau)| \\le \\epsilon_k,\n$$\n\nwhere the last inequality follows from our assumption.\n\nThus, we have $\\overline{G}_k(\\tau^*) = G_k(\\tau^*) + \\epsilon_k \\ge G^*(\\tau^*) = 1 - \\alpha$. Recall we define\n\n$$\n\\tau_{1-\\alpha, k} = \\sup\\\\{\\tau \\in R \\mid \\overline{G}_k(\\tau) \\le 1 - \\alpha\\\\};\n$$\n\nthus, we have $\\tau_{1-\\alpha, k} \\le \\tau^*$. Since $\\tau_{k+1} = \\max\\\\{\\tau_{1-\\alpha, k}, \\tau_k\\\\}$ with $\\tau_{1-\\alpha, k} \\le \\tau^*$ and $\\tau_k \\le \\tau^*$, we have $\\tau_{k+1} \\le \\tau^*$.\n\nWe are happy to further elaborate on any portion of the proof.", "claims_and_evidence": "The claims made in the submission are well-supported by both theoretical proofs and empirical results. The authors provide clear evidence for the effectiveness of their algorithm in maintaining the desired coverage rate, achieving sublinear regret, and ensuring zero undercoverage. The empirical evaluation is thorough, and the theoretical analysis is rigorous, making the claims convincing and credible.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria are well-suited for the problem of online conformal prediction with semi-bandit feedback. The algorithm is designed to handle the challenges of this setting, and the evaluation criteria align with the goals of the application. The benchmark datasets and baselines are appropriate and provide a thorough evaluation of the algorithm’s performance.", "theoretical_claims": "The inductive step in Lemma 4.2 could be more detailed. Specifically, it would be helpful to explicitly state how the inductive hypothesis is used which is not so clear to me.\n\nOverall, the theoretical analysis is rigorous and supports the claims made in the paper.", "experimental_designs_or_analyses": "The experimental design and analyses are sound and valid. The tasks, datasets, baselines, and metrics are well-chosen and relevant to the problem of online conformal prediction with semi-bandit feedback.", "relation_to_broader_scientific_literature": "The key contributions of the paper are closely related to the broader scientific literature in conformal prediction, online learning, and bandit feedback.", "essential_references_not_discussed": "no", "other_strengths_and_weaknesses": "Strengths:\nProviding the first regret guarantee for online conformal prediction with semi-bandit feedback.\n\nWeaknesses:\nThe writing should be improved and well-organized.", "other_comments_or_suggestions": "See the Theoretical Claims above.", "questions_for_authors": "See the Theoretical Claims above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QbR1pSwiai", "reviewer": "Reviewer_hTaD", "summary": "The paper studies the problem of conformal prediction with semi-bandit feedback. In this setting, it formulates an online learning problem where the algorithm must generate conformal sets that maintain valid coverage guarantees in each round. The authors propose an algorithm that satisfies this requirement and demonstrate that it achieves sublinear regret under a regret definition based on score thresholds.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful comments. We address the questions and major concerns below:\n\n**Concern 1: Line 285-287 Proof**\n\nWe apologize for the confusion. We will fix the typo in the revised draft. We also note that the final regret bound is correct because we add the additional $\\epsilon_t$ in line 290.\n\n**Concern 2: Reference Plot**\n\nWe thank the reviewer for the helpful advice. We updated Figure 1 to add $f(T) = \\sqrt{T \\log T}$ as a reference. We also take the log of the y-axis to improve readability. The figure is uploaded here:  \n<https://imgur.com/a/j05QwzS>\n\n**Concern 3: Natural Metric** \n\nIt is correct that $\\tau$ serves as a surrogate for prediction set size, as the prediction set size is monotonic in $\\tau$. In practice, we find that this surrogate performs reasonably well, and we use a variant of it in our experiments. The reason we do not directly use prediction set size is explained in lines 148–150 (right column): specifically, because prediction set size is a discontinuous function, it does not satisfy Assumption 2.1. We have also conducted experiments on the convergence behavior of the prediction set size and would be happy to share the results.\n\nAlternatively, a guarantee that existing conformal prediction algorithms provide is that the coverage rate is also not too much *higher* than desired, which shows that the algorithm is not overly conservative. Indeed, our regret guarantee can be applied to obtain such a bound. Specifically, consider the loss function $\\phi(\\tau) = 1-\\min\\\\{G^*(\\tau),G^*(\\tau^*)\\\\}$ (the min is to ensure the step-wise regret is non-negative). On the event that $\\tau_t\\le\\tau^*$ for all $t$ (which holds with high probability, see Lemma 4.2), then $\\min\\\\{G^*(\\tau_t),G^*(\\tau^*)\\\\}=G^*(\\tau_t)$, so the step-wise regret is  \n$$r_t := \\phi(\\tau_t) - \\phi(\\tau^*) = G^*(\\tau^*) - G^*(\\tau_t) = \\mathbb{P}[\\tau_t\\le f(x_t,y_t^*)\\le\\tau^*].$$\n\nIn other words, the step-wise regret $r_t$ equals the overcoverage probability -- i.e., the probability that our algorithm covers $y_t^*$ when the \"oracle\" algorithm (which knows $\\tau^*$) does not. Then, by Theorem 3.1, we have $r_t = \\mathbb{P}[\\tau_t\\le f(x_t,y_t^*)\\le\\tau^*] = O(\\sqrt{\\log t/t})$, implying that the overcoverage probability converges to zero. We are happy to add a discussion of this result to our paper.\n\n**Question 1: $\\epsilon_t$ in Lemma 4.2**\n\nIt is correct that $\\epsilon_t$ is defined in Equation (4). We will include this definition in the statement of the lemma in the revised draft to avoid any ambiguity.\n\n**Question 2: Theorem 3.1 Stated Twice**\n\nWe apologize for the confusion. We re-stated the theorem in the proof section to improve its readability. We are happy to remove it.\n\n**Question 3: $\\delta$ in Lemma 4.1**\n\nWe define $\\delta = 1/T^2$ in line 199-200 (right column). We will include this definition in the revised proof to avoid future confusion.\n\n**Question 4: Assumption 2.1** \n\nWe meant natural in the sense that it naturally captures relevant structure in our problem, not necessarily that it is a natural assumption. Specifically, this assumption is a natural way to avoid the pathological cases discussed in lines 143–150. To summarize, consider a CDF such that $G^*(\\tau_0) = G^*(\\tau^*) = 1 - \\alpha$ with $\\tau_0 < \\tau^*$. Recall that $\\tau^* = \\sup\\\\{\\tau \\in R: G^*(\\tau) \\le 1 - \\alpha\\\\}$. Since we almost surely never observe any scores between $\\tau_0$ and $\\tau^*$, it becomes extremely difficult to identify $\\tau^*$ from $[\\tau_0,\\tau^*]$ with a finite sample. Even a small error in estimating the empirical CDF---e.g., $G_t(\\tau^*) = G^*(\\tau^*) + \\epsilon$---can result in significant regret. We apologize for the confusion, and will clarify our explanation of this assumption.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes, I checked all the proofs in the paper. \n\nI believe there is a minor issue in the proof of Theorem 3.1. In the transition from line 285 to 287, the notation switches from $\\overline{G}_t$ to $G_t$. If we use the equality $\\overline{G}_t(\\tau) = G_t(\\tau) + \\epsilon_t$, an additional application of the triangle inequality is required, which introduces an extra contribution of $\\varepsilon_t$.\n\n Going through the proof, it seems to me that the proof easily generalizes to the case where $\\psi$ is $\\alpha$-Holder for $\\alpha \\leq 1$. The regret should still be sublinear but with a rate slower than $\\sqrt{T}$ and perhaps approaching $T$ as $\\alpha \\to 0$.", "experimental_designs_or_analyses": "Yes, I think the experiments are good and comprehensive. One additional aspect I would like to see is a $\\log$-$\\log$ plot of regret along with the corresponding slope parameter to verify whether the rate is indeed smaller than $\\sqrt{T \\log{T}}$. From the results, it appears that the rate is approximately $\\sim \\sqrt{T}$, but a formal verification would be helpful. Alternatively, the authors could include a reference plot of $f(T) = \\sqrt{T \\log{T}}$ in Figure 1 for comparison.", "relation_to_broader_scientific_literature": "The paper seems to improve on existing results.", "essential_references_not_discussed": "Not that I am aware of.", "other_strengths_and_weaknesses": "The paper is generally well-written and is easy to follow. The theoretical results are nice and verified with experiments.\n\nRegarding potential weaknesses, I am not entirely convinced by the notion of regret as defined in the paper. Why is $\\tau$ given such emphasis? It seems more like a means to an end rather than the ultimate objective. What truly matters is the size of the conformal sets. Would it be a big deal if the conformal set remains nearly the same for $\\tau = \\tau^{\\star}$ and $\\tau = 2\\tau^{\\star}$? A more natural metric might be the size of the conformal set in classification with finite labels or, for regression, its Lebesgue measure.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "What is $\\epsilon_t$ in Lemma 4.2? I assume it corresponds to the $\\epsilon_t$ defined before Equation (4), but it should be explicitly referenced to avoid ambiguity.  \n\nAdditionally, why is Theorem 3.1 stated twice in the paper?  \n\nIn the proof of Theorem 3.1, immediately after the line “By a union bound and by Lemma 4.1, we have”, what is $\\delta$ here?  \n\nAssumption 2.1 seems to appear without sufficient justification. The authors state that ``A natural way to formalize the continuity assumption is based on the cumulative distribution function (CDF) of the scoring function” and then assume $\\phi(\\tau) = \\psi(G^{*}(\\tau))$. Why is this considered natural? A more intuitive assumption, in my view, would be to require that $\\phi$ is a Lipschitz continuous function of $\\tau$.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper addresses online conformal prediction with semi-bandit feedback, where calibration is performed in online setting and with the feedback observed only when the true label is contained in the prediction set. A novel conformal prediction algorithm is presented at this setting and is shown to achieve sublinear regret. Empirical evaluation demonstrated the validity in image classification, document retrieval, and second-price auction reservation price prediction. All reviewers feel that online conformal prediction under the semi-bandit feedback setting is original and the method is well supported by both theories and experiments. Although there were some concerns in clarity and writing, the author response resolved up to some extent.
Decision: Accept (poster)