Online Conformal Prediction with Adversarial Semi-bandit Feedback via Regret Minimization
Authors: Junyoung Yang
Kyungmin Kim
Sangdon Park
Venue: ICLR 2026 Poster (2026)
Keywords: Online Conformal Prediction
Adversarial Bandit
Semi-bandit Feedback
Regret
Primary area: learning theory

Abstract: Uncertainty quantification is crucial in safety-critical systems, where decisions must be made under uncertainty. 
In particular, we consider the problem of online uncertainty quantification, 
where data points arrive sequentially. 
Online conformal prediction is a principled online uncertainty quantification method that dynamically constructs a prediction set at each time step.
While existing methods for online conformal prediction provide long-run coverage guarantees without any distributional assumptions, they typically assume a *full feedback* setting in which the true label is always observed. 
In this paper, we propose a novel learning method for online conformal prediction with *partial feedback* from an adaptive adversary—a more challenging setup where the true label is revealed only when it lies inside the constructed prediction set.
Specifically, we formulate online conformal prediction as an adversarial bandit problem by treating each candidate prediction set as an arm. 
Building on an existing algorithm for adversarial bandits, 
our method achieves a long-run coverage guarantee by explicitly establishing its connection to the regret of the learner.
Finally, we empirically demonstrate the effectiveness of our method in both independent and identically distributed (i.i.d.) and non-i.i.d. settings, 
showing that it successfully controls the miscoverage rate while maintaining a reasonable size of the prediction set.

Published as a conference paper at ICLR 2026
ONLINE CONFORMAL PREDICTION WITH ADVERSAR- IAL SEMI-BANDIY FEEDBACK VIA REGRET MINIMIZA-
TION
Junyoung Yang' CSE POSTECH
Kyungmin Kim GSAI POSTECH
Sangdon Park GSAI & CSE POSTECH
ABSTRACT
Uncertainty quantification is crucial in safety-critical systems, where decisions must be made under uncertainty. particular, we consider the problem online uncertainty quantification, where data points arrive sequentially. Online conformal prediction a principled online uncertainty quantification method that dynamically constructs a prediction conformal prediction provide long-run coverage guarantees without any distribu- tional assumptions, they typically assume a full feedback setting in which the true label is always observed. In this paper, we propose a novel learning method for online conformal prediction with partial feedback from an adaptive adversary more challenging setup where the true label is revealed only when it lies inside the constructed prediction set. Specifically, we formulate online conformal prediction an adversarial bandit problem by treating each candidate prediction set as arm. Building on an existing algorithm for adversarial bandits, our method achieves a long-run coverage guarantee by explicitly establishing its connection to the regret of the learner. Finally, we empirically demonstrate the effectiveness of our method both independent and identically distributed (i.i..) and non-i.i.d. settings, showing that successfully controls the miscoverage rate while maintaining a reasonable size of the prediction set.
each time step. While existing methods for online
INTRODUCTION
Uncertainty quantification is essential in safety-critical domains such as autonomous driving (Linde- mann al. 2023), healthcare (Lin al. 2022), and finance (Park & Cho 2025), where uncertainty- aware decision making is required. Unlike point prediction methods that return the most likely outcome, conformal prediction (Vovk et al.) 2005) is promising uncertainty quantification method that constructs a conformal set for a given input, set of outcomes that is guaranteed to contain the true label with user-specified probability. We refer to the guarantee as a coverage guarantee. Here, the size of the conformal set quantifies the uncertainty in terms of making prediction.
Moreover, the coverage guarantee is model-agnostic the sense that the guarantee holds irrespective of the choice of the prediction model. Exchangeability assumption the data generating process (Vovk et al. 2005) is the only requirement for the guarantee, where typical independent and identically distributed (i.i.d.) scenario is the that satisfies such assumption. Specifically, under the exchangeability assumption, the coverage guarantee of the conformal set constructed from training samples holds for an unseen test sample (Vovk 2013). Therefore, since the coverage guarantee holds for any prediction models, conformal prediction has been applied to complex and large-scale models such large language models (Mohri & Hashimoto 2024 Cherian al. 2024 Lee al. 2024).
However, the exchangeability assumption is easily violated under scenarios such as distribution shift, where the training and test distributions differ. A number of conformal prediction methods have been proposed to provide coverage guarantees under such settings (Tibshirani et al. 2019 Podkopaev &
Ramdas 2021
Park al. 2022 Gendler et 2022 Si et al. 2024). contrast the aforementioned
Equal contribution

---

Published as a conference paper at ICLR 2026
batch conformal prediction methods which require batch of samples for training, methods for online conformal prediction are proposed to tackle online uncertainty quantification problems, where data points arrive sequentially (Gibbs & Candès, 202T Bastani et al.) 2022 Angelopoulos et al. [023] 2024). Even in adversarial settings, where no distributional assumptions are made on the data stream or the functional form of the scoring functions, these methods provide long-run coverage guarantee such that the empirical coverage reaches the target level after sufficiently many time steps.
Meanwhile, existing methods for online conformal prediction typically assume a full feedback scenario, where the true label is revealed every time step. Indeed, these methods are tailored to the full feedback setting, since they require a scoring function evaluated on the true label either for its quantile estimation or for the evaluation of the miscoverage loss over multiple conformal set candidates. Recently, [e al. (2025) proposed method for online conformal prediction with partial feedback, specifically feedback referred to as semi-bandit feedback, where the true label is revealed only when it lies within the chosen conformal set. While it is a more challenging learning setting compared to the full feedback scenario, their coverage guarantee holds only under i.i.d. data streams. Figure L provides an illustration of different feedback settings in online conformal prediction.
In this paper, we present the first study of online conformal prediction with adversarial partial feedback. Specifically, by discretizing the continuous hypothesis space of thresholds that parameterize conformal set, and then treating each candidate conformal set as arm, formulate the problem as a multi-armed adversarial bandit problem. A bandit problem is a sequential game between learner and environment. In each round, the learner chooses arm, and the environment provides feedback on the chosen arm. In particular, the adversarial bandit problem removes almost all assumptions about how the environment provides feedback, where the environment is often called the adversary accordingly. The performance of the learner is evaluated based on the regret, which typically quantifies how well the learner performs with respect to the best arm in hindsight (Bubeck et al., 2012 Lattimore & Szepesvári] 2020). There is rich literature on adversarial bandit problems, devising algorithms with sublinear regret. EXP3. . P algorithm Auer et al. (2002) is one of the algorithms that provides high-probability sublinear regret even under the adaptive adversary, an adversary that can generate feedback based on the previous history.
Building on the EXP3. algorithm, we propose novel algorithm for online conformal prediction with adversarial partial feedback, in which we consider a semi-bandit feedback scenario, similar to Ge et al. (0225). Specifically, by devising loss function tailored to conformal prediction, we explicitly establish a connection between the regret of the learner and a long-run coverage (Lemmal) [ which in turn provides a long-run coverage guarantee of our algorithm. We further improve the performance in terms of the speed approaching the target coverage, by fully exploiting the monotonicity property of the miscoverage loss with respect to the threshold parameterizingg conformal set. Specifically, it enables partial inference of feedback from candidate conformal sets that are not chosen, even when the true label is unavailable. We empirically demonstrate the efficacy of our method on both classification and regression tasks, conducting experiments in i.i.d. and non-i.i.d. settings for each task. In particular, we show that our method approaches long-run coverage while maintaining a moderate average conformal set size, achieving performance comparable to Bastani et al. (2022). an online conformal prediction method with adversarial full feedback.
RELATED WORK
2.1 ONLINE CONFORMAL PREDICTION
Gibbs & Candès (02T)) first proposed an online conformal prediction method for arbitrary data streams. Based on online gradient descent, their method provides a long-run coverage guarantee over arbitrary sequences. While the method relies only on single step size parameter, the optimal parameter requires knowledge of the degree of distribution shift, which an unrealistic assumption. The same authors have resolved the issue by aggregating results from multiple experts, running in parallel with different step sizes, making the method adaptive to the type of distribution shift in a data-driven manner Gibbs & Candès (2024). While providing a biased result in terms of the long-run coverage, they provide a local coverage guarantee over all time intervals of a given width, under mild assumptions on the smoothness of the distribution of the scoring function and its quantile estimates. Building on the strongly adaptive online learning method, Bhatnagar et al. (2023) further improved the method by providing simultaneous coverage guarantee over all local intervals of arbitrary
2

---

Published as a conference paper at ICLR 2026
Which animals could x be? 101
Choose n, C,, (xx, (y (c
n fe( Wolf)
(x Frog)
(x, Lion)
Dog) Dog)
fi(x,, Cat)
Case my (rt,) 0 Dog (x,(x)) = (Lion, Dog, Wolf, Cat)
Case2: (m, 1
Dog é (x,(x,) [Wolt, Cat)
1. Observe the true label
Full Feedback
Observe the label y;= Dog Full Faedback
2. Full Feedback of
Vir aT (x Dog)
s (xp, Dog) E fx Dog)
vi II a fi Dog)
Seml-bandit Feedback (Ours)
Partial Feedback of
Bandit
Partial of
Feedback
Figure 1: Online conformal prediction under different feedback scenarios characterized by the amount of feedback received at each time step
window size. Gibbs & Candès (2024), they considered dynamic set of experts. where each expert is active only for specific period of time. Inspired by control theory, |Angelopoulos et al. (2023) extended existing online gradient descent-based methods by incorporating online gradient descent steps, which they refer to as quantile tracking, as one of the components for the online quantile update.
Besides, there have been works to provide stronger theoretical guarantees. |Bstanii et al. (2022) proposed method with threshold-calibrated multivalid coverage guarantee, a group- and threshold- conditional coverage guarantee where a set of groups can be arbitrarily defined. Angelopoulos et al. (2024) proposed a simple online gradient-descent method that has simultaneous guarantees both on the adversarial and i.i.d. settings. Recently, Zhang et al. (2025) devised an online conformal prediction algorithm, providing both privacy and coverage guarantees under arbitrary data streams.
In this paper, we also consider online conformal prediction under arbitrary data stream. Specifically, we consider an adaptive adversary that can generate data based on the learner's 's past actions.
2.2 ONLINE CONFORMAL PREDICTION WITH PARTIAL FEEDBACK
Existing methods for online conformal prediction with adversarial feedback typically assume the full feedback setting, where the true label revealed at every time step. One exceptiooal case is Angelopoulos et al. (2024), where the algorithm itself only requires the feedback whether chosen conformal set contains the true label. However, the authors are basically considering a full feedback scenario, and some of their thcoretical results assume problem setup where the scoring function is trained online, using the labeled data pairs from previous time steps.
On the other hand, there have been few papers addressing online conformal prediction with partial feedback, a scenario where access to the true label is limited. [Wag & Qiao (2024) considered bandit feedback scenario. where the true label observed only when the predicted label corresponds to the true label. Recently, Ge et al. (2025) proposed method under a semi- aani-bandit feedback scheme, a less rigid partial feedback scenario where the true label is revealed as the true label lies within chosen conformal set. Although partial feedback is inherently more challenging than full feedback, prior works still rely on the i..d. data gettaaaennraiing assumption, which restricts their applicability to real-world, non-i.i.d. data streams.
As such, we consider an online conformal prediction with adversarial partial feedback, where data streams deviate from the i.i.d. process and at the same time the true label is difficult to obtain.
3 ONLINE CONFORMAL PREDICTION WITH ADVERSARIAL FEEDBACK
We consider online conformal prediction with adversarial partial feedback. Let X' be set of examples and y be set of labels. At each time step E [T), learner chooses conformal set On,, X - 2",
3

---

Published as a conference paper at ICLR 2026
which is parameterized by the threshold parameter TT E [0, 1] as follows:
f( mz).
Here, ft: :x x + [0. is a scoring function that measures the conformity of a label for given input. Note that the functional form of .)(::)) may evolve over time.
Specifically, we consider the following learning protocol: an example (zt, ye) E X' x y is chosen by an adversary, where only the input 2; revealed to learner. Here, we assume that the adversary can be adaptive, in the sense that it may select a sample based on the learner's previous decisions. Once Te given, the learner outputs conformal set Cs,, (Iz). The threshold parameter ne is selected according to the learner's 's current stochastic strategy, which is updated online based on past interactions with the adversary. Then, the learner receives feedback from the adversary on whether C+, (24) contains the true label yt. which we denote as m²(TT) = (1: & Oz2 (xx)). We refer to the term as miscoverage henceforth.
Here, we consider semi-bandit feedback scenario (Ge et al. 2025). one of the partial feedback settings where true label y/2 is additionally revealed when m, (5)
In other words, each instance has an associated true label /r. which exists but is not labeled at the time the adversary chooses the sample. Having an access to yt enables the learner to evaluate the miscoverage m²(x) for all E [0, 1.. since the scoring function fe( 3t) of the true label-a quantity sufficient to evaluate the miscoverage of a threshold- threshold-paramettrre parameterized conformal set-cam be computed. Although we have coined the term partial feedback, in contrast to full feedback, encompass both bandit and cemi-bandit feedback settings, we will use to refer exclusively to the semi-bandit feedback scenario in the following sections for simplicity.
Under such online conformal prediction problem with adversarial partial feedback, our goal is to design learner that provides long-run coverage guarantee by controlling the miscoverage rate defined as follows:
1 MC(T) T
Σ (m)))
(2)
where is the time horizon. Specifically, given a target miscoverage level a E (0, 0.5). we aim to upper bound the miscoverage rate as MC(T) & a =(T) such that e(7) - 0 as T + co. Additionally, we aim to minimize the average size of constructed conformal sets at the same time, which is defined
T
[Teff(T)= = T
Σ Cr, (#+)),
since a learner that always returns the vacuous conformal set y by choosing गे = 0 for all t e [T] trivially achieves the target miscoverage level.
ONLINE CONFORMAL PREDICTION AS ADVERSARIAL BANDIT PROBLEM
We formulate the online conformal prediction problem with adversarial partial feedback as multi- armed adversarial bandit problem, by treating each candidate conformal set as an arm (Section 4.1) Defining finely discretized subset II of the continuous hypothesis space [0, 1] as action space, we improve the E.P3. algorithm (Auer al., 2002). > which an algorithm that provides high-probability sublinear regret under adversarial bandit environments, for conformal prediction.
To this end, we first design a loss function tailored to conformal prediction (Section 4.2 which in turn provides an explicit leanner-agnostic relationship between a regret from learner and its miscoverage rate MC(T') (Section 4.3 This relationship ensures the long-run coverage to achieve the target level a, for any learner that achieves sublinear regret. However, directly applying an existing learner, e.g., EXP3 PP, does not make full use of the available information under the bandit feedback setting. Therefore, additional information and the monotonicity property of a threshold pareeedtrrammmeeeddeee conformal set with respect to the miscoverage (Section 4.4).
further improve the algorithm by fully exploiting such
4

---

Published as a conference paper at ICLR 2026
4.1 PROBLEM RE-FORMULATION
Discretization of the hypothesis space [0, 1 into II allows us to reformulate online conformal prediction with adversarial feedback (Section 3 multi-armed adversarial bandit problem. Each arm corresponds to a threshold parameter π E that specifies a thresholddparamettrizee conformal set Cr,, Specifically, for each time step t, learner chooses a threshold parameter πT, from K possible candidates, where
[IT] defined as the discretization level of the original hypothesis space [0. 1]. As we consider partial feedback scenario, we observe the true label Yr E y in addition to the miscoverage feedback (m+)))) when (z, = O. This reformulation enables us to leverage existing learners under multi-armed adversarial bandit environments, where each learner's performance is measured by its regret relative to the best arm in hindsight, defined as
(Tg(T)
((()) min TEll
(T)..
Here, 4, = (le(T)) E
Table I:
Comparison online conformal prediction with adversarial feedback and typical mulli-armee adversarial bandit problems
[emin fmax] K is a loss vec- tor chosen by an adversary at time t, with each entry lying in the bounded inter- val [emin: m Note that the online conformal predic- tion problem with adversar- ial feedback (Gibbs & Can-
Online Conformal Prediction with Adversarial Feedback
Multi-arme Adversarial Bandit
Problem
Adversary Controls
Sample: (1z,8e), where 3/t is unlabeled
Loss Vector: (4(()))En
Miscoverage: (e(e)e)
Feedback
Loss: (T(e))
True Label: ye if mm
dès [202 2024] Angelopou- los et al.] 2024) assumes that the environment controls the choice of (Zz, yt) instead of the loss vector b, where (T) is fully determined by (aras y1) for all
Loss Defined by
Learner and Adversary
Adversary
Miscoverage Rate: MC(T) Inefficiency: Ineff(T)
Objective
Regret: Reg(T)
II. Unlike the typical adversarial bandit problem, the learner has control over the design of the loss function & II + [e mmax]. Nevertheless, while the adversary does not directly control the loss sequence, the adaptive adversary we consider can choose (Iz, ye) based on
the previous interaction with the learner. See Table [oor details on the problem reformulation and the following section for details on the loss design.
4.2 DESIGN OF THE LOSS FUNCTION
In online conformal prediction with adyersarial feedback, the only feedback we observe at each time step / is on the miscoverage m+(T;) of the chosen threshold गe. However, additional feedback on the size of conformal set is necessary keep the constructed set compact and informative, since lazy learner that always returns the label space y as a conformal set by letting म. = 0 for all t E [T] achieves MC(T)) 0. Therefore, we define a loss function composed of miscoverage term and an inefficiency term, capturing the miscoverage and the size of a conformal set, respectively, as follows:
( a) = (T; + ae(TT),
(5)
where a E (0, 0.5) is a target miscoverage level. The miscoverage term de (T;; is defined in terms of the miscoverage feedback mx( as
de( ax) = m=)=) + (m, ())(a) + ( 1)h(a)
(6)
(T) + (me((T) () + a<l1 - a)) + (m) = 1)(-a(1 ()).
Here, g(a) > 0 and h(a) < 0 jointly control the miscoverage term in a-adaptive manner. Taking the miscoverage control as a primary objective, the miscoverage term satisfies de ( < de (T a) for all II; and 72 E (II)), where II; = {- E II (T) = 03. In particular, g(a) and h(a) are designed such that (T2: - 4T(1;;0 a) h1a)(a)) g(a) decreases to 0 as a increases, prioritizing the miscoverage for smaller a. We henceforth write d, (T) for simplicity, indicating the dependence on a only when needed. Additionally, we consider the inefficiency term or (T) of an arbitrary functional form, long penalizes large conformal sets.
5

---

Published as a conference paper at ICLR 2026
4.3 FROM REGRET BOUNDS TO COVERAGE GUARANTEES
By reformulating online conformal prediction with adversarial feedback as multi-armed adversarial bandit problem, reduce our problem to minimizing regret with respect the loss defined in 3 However, while both the miscoverage and the size of a conformal set are incorporated into the loss design (Section 4.2 minimizing regret (Eq. ! does not necessarily guarantee control of the miscoverage rate (Eq. at the target level a, which Is our primary objective.
Given a target miscoverage level learner-agnostic guarantee that bounds the deviation of the miscoverage rate MC(T) from in terms of the per-round regret {.Reg(T) (Lemma I inspired by prior work that derives analogous regret-based bounds for false discovery rate control in selective generation (Lee et al., 2025). The proof deferred to Appendix B
(0, 0.5), we therefore specify the condition that yields
Lemma 1. For any T E N, E (0, 0.5), under the design choice that (T) is of order o(T) (1 for all π E II, any learner incurring regret (Tg( with respect to the loss defined in Eq. Satisfies
MC(T)
Reg (T) CMc(T),
T
where (TC is a constant term of order o(T)-
Specifically, (Tc = Ta,(0)- - (<(m)) + (Cppl E. ((m,(())=) (T)-1 wwhre where Cgap (T) is
constant that characterizes the tightness of the learner that satisfies the relationship (T))(
1-
[(m)()))=) Note that the empirical analysis reveals that Cgap(T) decreases as T (x),
increases (Appendix Roughly speaking, any learner with sublinear regret achieves long-run coverage at least a. For example, we can employ the EXP 3. P algorithm (Auer et al. 2002) which provides high-probability sublinear regret even under an adaptive adversary.
4.4 TAILORING EXP 3. FOR ONLINE CONFORMAL PREDICTION
We propose modifications to the EXP3. P algorithm tailored to online conformal prediction with adversarial partial feedback. First, we consider the following inefficiency term a (T;T,,, [0, 1] for all baselines:
1(m,(T)= =0 (-co (1+ 2² 11+1-aa + (mmm(())=)) )0(T)=))+(m(()))==)))))))))))))) (- (- (c)
(7)
1+
a(1 ( 2a.
where 0. Here, balances the trade-off between miscoverage and inefficiency terms. We henceforth write (=))) for simplicity, indicating the dependence on a and c only when needed. See Appendix H for details on the choice of c. For æ II; ax(z) is monotonically increasing function the size of the corresponding conformal set JC, (z+)], since the set size decreases as m increases (Eq. I. This encourages smaller conformal sets as long as m²(T) = 0. In contrast, for (II;)S, (x( decreases as |C= (a:x) increases. When mx(x) 1, the primary role of az (TT) is to penalize the miscoverage. while the set size is of secondary importance. The design leverages the monotonic structure of single-thie thaelhhhhrhhddedd conformal sets (Eq. [ in which the miscoverage term m4 (T) monotonically decreases (2:():) increases. Since EXP P-based algorithms are formulated in terms of gains, we additionally introduce a normalized gain term (T() E [0, 1]. defined
(T( = Lmax Le(TT) emin
(8)
Emax
OCP-Bandit. It is direct modification of the EXP3. .P algorithm (Algorithm 2 for online conformal prediction with adversarial partial feedback (Algorithm 3). -SP-Bandit provides a sublinear regret with probability at least Ó, where ö E (0. is confidence parameter (Theorem B). Following EXP P.P, CCC--Bandi t adopts biased gain estimator ( { }) for all π E II to update the leamnr's 's strategy P. [0, 1]
as:
(x)( 1(x= mT) (e((T) + 3
B
( # mT)
(m
(T(T))

---

Published as a conference paper at ICLR 2026
where Pt lies in the probability simplex defined over the action space II. It is importance-weighted estimator of the corresponding normalized gain 9e (T), augmented with an additional exploration term [ > O, to ensure high-pun seeehprbbbbility sublinear regret against adaptive adversary. Note that the normalized gain can be computed only for the chosen arm Re.
weighted
However, unlike the standard bandit feedback setting assumed by EXP3. P, we consider partial feedback scenario which the true label y/ is additionally observed when (T, = 0. In this case, the scoring function fi (xt, Mt) of the true label can be computed, which allows to evaluate m, mz(*) for all π E II. Moreover, exploiting the monotonicity of (π)( with respect to я, we can partially evaluate miscoverage terms even when my ( 1. This additional information, which is ignored by OCP -CP-iand can be exploited to achieve the target coverage level with fewer time steps.
OCP-Unlockt. We propose novel algorithm that fully exploits the additional information available when my ( 0 and uses the monotonicity of the miscoverage term m.( with respect to the threshold E to obtain additional feedback when (T+) (T.))) 1, then m²(=T) 1 for all E II such that 2 Te, since m²(T) in non-decreasing as ı increases. Therefore, we can evaluate mx( for the subset (T,( C II, which we refer to as unlocking set, defined as follows:
(Algorithm T.. Specifically,
if ( =
[T(T)) ( (f =
(10)
As such, we propose new biased gain estimator (II that is designed in accordance with the amount of additional feedback available, as characterized by the unlocking set II, (Tz). In particular, since the degree of additional feedback varies with mi (Te). we design separate estimators for each case where mi (T)) = 0 and me(TT) = 1, i.e.,
ge (ιr (T+)) = (m)) 0) x (A) + (m) 1) (B)
(11)
full unlocking
partial unlocking
In what follows, we provide high-level description of our estimator and refer the reader to Ap- pendix ffr further details.
First, when (Te) = O, we design the biased gain estimator as follows:
(C( E Exen; (c( + ("TExen Pc( B)
1
3 & m²) + Eesa Pe Pc(
(4)= (
where we can compute the normalized gain yt (T)) for all π E II due to semi-bandit feedback. The estimator designed to have different importance weights for normalized gains of thresholds from two groups, II; and its complement, where larger weight is assigned to those from the former. This is consistent with our design rationale for the loss function (Sec. 4.2 and Eq. 7. which prioritizes miscoverage control. Also, for IT; we further strengthen this miscoverage-fixs rationale by placing less weight on the exploration term B for larger conformal sets via the denominator Easa (
On the other hand, when me(Tre) 1, feedhack be evaluated only the subset (T, {TT 11: 2 m of (II;). In this case, we define the estimator as follows:
1 ) (B) = ( & (T()) (((T)+ + (1+ P((T)) 3 1( (((TT)) { (((T) + Easa Pe
3
Here, the term (T) is introduced for all x & (TTe) since (T())) cannot be computed, as follows:
lmax (x(
(e(
(12)
l mmin
with (T)) = - a(1 - a) (+)) (T)-1 We refer to (e(T)) as a pseudo-gain, since it serves approximation of the true normalized gain (T()). Unlike the my(Fe) 0 case where II; can be explicitly characterized, (T,) 9 is decomposed as [1, (II, n II; U (m, n (T;))) ITद U (T.(=.)) n (Tz)*} when m.(m)) 1. Since IT: cannot be correctly
co
7

---

Published as a conference paper at ICLR 2026
Algorithm 1 OCP-Unlocc
procedure OCP-UNLOCK+(IL, n. n, c,, 2: Initialize cumulative estimated gain: Go(z) for E IT for & E {l...., do
3:
exp(nG. Update strategy: Pe(TT) + (1 11 Enen exp(nGe- + T where K = [11]
4:
5:
Sample arm: ne ~ Pt Receive my m - (tt & Oz, (zi)) where On, (24) is defined as Eq.
6:
7:
if my (m)) then
(D) Full unlocking: Observe the true label y
8:
(1 t II
9:
else
(p) Partial unlocking
10:
11:
for
(m. do
(D) Evaluate m²(x) for all E (T+)
12:
(T) & COMPUTELOSS(T: me(T), ( a
Compute normalized gain ge (z), defined as Eq. for ı E do
14:
15:
Construct biased gain estimator ( [I] (T.,) )). defined as Eq. 11 Update cumulative gain: (x G.- (TT) (x(
17:
procedure COMPUTELOSS(T, m, a. c)
18:
return dT; a) + ar (T; a; c). defined as Eq. 6 and Eq.
specified, we do not upweight the pseudo-gain as we did for the normalized gain in the first term of (A). Nevertheless, the construction of the pseudo-gain is again aligned with miscoverage- first rationale. Specifically, (TT))) is defined so that (T(T) 2 (T(2)) for all ग E (lT)))) and T2 E (TT,, thereby incorporating the monotonicity property that the miscoverage term is non- decreasing as increases. For π E (1,())), the biased gain estimator is defined in the same manner as the second term of (A).
Building on the biased gain esitmator as defined in Eq. [1 our OCP-Unlock+ algorithm provides long-run coverage guarantee with high probability, by controlling the deviation of the miscoverage rate MC(T) from a as in the following theorem.
Theorem For any a E (0, 0.5), T N, K 2 5, and 6 E (0, run OCP-Unlock- (Algorithm) !
with 3 = v
in KT = 1.05 T
Kln
and = 0.95
K Then, the deviation of the miscoverage KT
rate (C(T) from a satisfies
(V
CluK
K In K T
K
In(6- 20( + + CMc((T)
MC(T) aa Staff Eag
4.15%
+
T
Thi
with probability at least
where the constant defined in Eg. 43 and Lag == Cmax Emin-
Note that this results from Lemma
1 where the upper bound of MC(T) is the sum of CMc (T) and the per-round regret 1 Reg(() OCP-Un1 ockk with respect the loss defined in Eq, 5 and
Eq. 7 (Theorem 5). See Appendix G for proof and additional details, including the introduction of
as offset terms in Eq. 11
EXPERIMENT
In this section, we empirically evaluate the performance of constructed conformal sets from OCP-Unlocks Uockk+ (Algorithm [ in online conformal prediction with semi-bandit feedback, both in terms of the long-run miscoverage (Eq. 2 and inefficiency (Eq. 3 addition to the above algorithm, we additionally consider the following baselines: Semi-bandit Prediction Sets (SPS), and MultiValid Prediction (. While SPS (Ge al. 2025) provides long-run miscoverage guarantee in the partial feedback setting, the guarantee valid under the i..d. assumption. In particular, consider MVP (Bastani et al.) 2022) as an oracle baseline, since the algorithm is constructed under the full feedback setting. See Section 2 for detail.
8

---

Published as a conference paper at ICLR 2026
040
120
170
825-
20-
100
33809
23000
33000
40000
50000
10000
20000
30000
40000
50600
(a) (C (i.i.d)
(b) Ineff(t) (i.i.d.)
0.35
118-
OCP-Urtec-
00-
0.35
0.27
0.2
0.5
009
Teme
(c) MC(() (Non-i.dd)
(d) Ineff(t) (Non-i.id.)
Figure 2: Long-run miscoverage MC(() and inefficiency Ineff(() as a function of time / E [7) on the ImageNet dataset under both the i...d and non-i.dd. settings, averaged over 50 independent runs
We conduct experiments on both classification and regression tasks, where both i.i.d. and non-i.i.d. settings are considered for each task. In Experiment 1 (Section 5.1). we consider classification task using ImageNet dataset. simulate the non-i.i.d. setting by evolving the functional form of scoring function fi(-.)) over time. In Experiment 2 (Section 5.2 consider regression task using the Airfoil Self-Noise dataset (Dua & Graff, 2017) from UCI repository. For the non-i.i.d. scenario, consider covariate shift setup where the input distribution changes after the first one-third of the data stream. Moreover, in Experiment 3 (Appendix D. we present an ablation study on the discretization level K E N. In Experiment (Appendix D. we further compare OCP Unn-nnok with its variants, OCP -rP-Bandit (Algorithm 3 and OCP Unlock (Algorithm 4 In addition, Experiment (Appendix K) examines the sensitivity of oCP-Unlock+ to the target miscoverage level a. Finally. in Experiment 6 (Appendix [L.
we empirically analyze the additional term (Tc that appears in the upper bound on the deviation of the miscoverage rate MC(T) from (Lemma T). See Appendix for additional experimental details.
5.1 EXPERIMENT 1: COVERAGE VS INEFFICIENCY ON IMAGENET
For both i.i.d. and non-i.i.d. settings, we evaluate average miscoverage rate MC(() and inefficiency Ineff(() function of time / E [T]. which is averaged over 50 random trials for 0.15, K = 200, and T = 50, 000 (Figure 2). II is uniformly discretized set over [0, 1]. consisting of K candidate thresholds.
Under the i..dd setting, -- MC(() MVP and SPS closely approach the target coverage level 1 1-a, a, where MVP has the lowest Inef[(() for all [T]. Smaller conformal sets from MVP compared to the other baselines are the result of the different amount of feedback available, where MVP can evaluate the miscoverage (T) for all π E II every time step. SPS has MC(t) S a for all [T] which is aligned with its high-probability any-time coverage guarantee under the i.i.d. setting (Ge al. 2025). Since OCP-Un lock+ lock exploits additional feedback when mz( = 0, highlights the importance of incorporating the miscoverage- first rationale in the design of biased gain estimator Gr (r(TT (T:)) as illustrated Section
Meanwhile, under the non-i.i.d. setting, both MC(() and Ineff(t) show fluctuating patterns over time across all baselines. Notably, MC(t) of SPS consistently decreases, having difficulty adapting to the dynamic environment in which the long-run coverage guarantee longer holds. Similar to the i... setting, MC(t) of MVP and OCP -CC-Unnock approach the target coverage level, where MVP once again consistently achieves the lowest Ineff()).

---

Published as a conference paper at ICLR 2026
0.225
0.200
0.175
0.150
0.125
12-
6.100
0.075
10
10P
OCP Unlock
OCP
(a) MC(T) (i..d.)
(b) Ineff( (i..d.)
0.225
0.175
15
Micoverags
14
0.125
0.300
0.755
MPP
MPP
OCP Unfocce
(c) MC(T) (Covariate Shift)
(d) Ineff(T)) (Covariate Shift)
Figure 3: Long-run miscoverage MC(T) and inefficiency IT) on the Airfoil Self-Noise dataset
under the i..dd and covariate shift settings, averaged over 50 independent runs
5.2 EXPERIMENT 2: COVERAGE VS INEFFICIENCY ON AIRFOIL SELF-NOISE
For both the i.i.d. and covariate-shin settings, we evaluate the long-run miscoverage MC(T) and inefficiency Ine on the Airfoil Self-Noise dataset, averaged over 50 independent runs with a = 0.1, K = 20, and T = 50,000 (Figure The policy class a uniformly discretized subset of [0, 1] with K candidate thresholds.
In the i.i.d. setting, MVP closest to the target miscoverage level and also attains the smallest inefficiency. SPS and OCP-Unlock+ both produce miscoverage below the target level, with OCP-Unl lock+ exhibiting a larger inefficiency. Under covariate shift, MVP continues to remain near the target miscoverage level, whereas becomes less reliable and OCP-Ualock4 remains conservative with larger set size.
CONCLUSION
We propose the first algorithms for online conformal prediction under adversarial semi-bandit feedback. By formulating the problem as multi-armed adversarial bandit problem and designing loss function tailored to online conformal prediction, we show that any learner achieving sublinear regret with respect to this loss also guarantees long-run coverage at the target level. In particular, our algorithm, OCP-Unlock- fully exploits the feedback available in the semi-bandit setting and leverages the monotonicity property of single-threshold conformal sets with respect to miscoverage. As result, it not only achieves sublincar regret but also demonstrates performance comparable to an oracle baseline with full feedback both i.i.d. and non-i.id. settings. Unlike most online conformal prediction methods that assume full feedback, realistic human-in-the-loon the conformal set. Finally, while algorithms information, extending them to contextual semi-bandit settings presents a promising direction for future research. We also believe that the bound in Theorem T may not be tight and that sharper analysis is possible.
approach supports more workflows in which the true label is observed only when it lies within
context-free and do not leverage additional
10

---

Published as a conference paper at ICLR 2026
ACKNOWLED
We appreciate constructive feedback by anonymous reviewers. This work was supported by Institute of Information & communications Technology Planning & Evaluation (IIP)) and the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (RS-2019- I191906, Artificial Intelligence Graduate School Program (POSTECH) (5%); RS-2024-00457888. National AI Research Lab Project (15%); No. RS-2024-00509258 and No. RS- RS-2024-00066482, Global AI Frontier Lab (50%); RS ASS22025-00060065 (30%)).
REFERENCES
Anastasios Angelopoulos, Emmanuel Candes, and Ryan Tibshirani. Conformal PID Control for Time Series Prediction. In NeurIPS, 2023.
Anastasios Nikolas Angelopoulos, Rina Barber, and Stephen Bates. Online Conformal Prediction with Decaying Step Sizes. In ICML, 2024.
Peter Auer, Nicolo Resa-Bianchi, Yoav Freund, and Robert E Schapire. The Nonstochastic Multi- armed Bandit Problem. SIAM Journal on Computing. 32(1):48-77) 2002.
Osbert Bastani, Varun Gupta, Christopher Jung, Georgy Noarov, Ramya Ramalingam, and Aaron Roth. Practical Adversarial Multivalid Conformal Prediction. In NeurlPS, 2022.
Aadyot Bhatnagar, Huan Wang, Caiming Xiong, and Yu Bai. Improved Online Conformal Prediction via Strongly Adaptive Online Learning. In ICML, 2023.
Sébastien Bubeck, Nicolo Cesa-Bianchi, al. Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems. Foundations and Trends@ in Machine Learning, 5(1):1-122, 2012.
John Cherian, Isaac Gibbs, and Emmanuel Candes. Large Language Model Validity via Enhanced Conformal Prediction Methods, In NeurlPS, 2024.
Dheeru Dua and Casey Graff. UCI Machine Learning Repository. https: ics
uci mm] 2017. Accessed: 2025-09-22.
Haosen Ge, Hamsa Bastani, and Osbert Bastani. Stochastic Online Conformal Prediction with
Semi-bandit Feedback. In ICML, 2025.
Asaf Gendler, Tsui-Wei Weng, Luca Daniel, and Yaniv Romano. Adversarially Robust Conformal Prediction. In ICLR, 2022.
Isaac Gibbs and Emmanuel Candès. Adaptive Conformal Inference under Distribution Shift. In NeurlPS, 2021.
Isaac Gibbs and Emmanuel Candès. Conformal Inference for Online Prediction with Arbitrary Distribution Shifts. JMLR, 25(162):1-36, 2024.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep Residual Learning for Image Recognition. In CVPR, 2015.
Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.
Minjae Lee, Kyungmin Kim, Taesoo Kim, and Sangdon Park. Selective Generation for Controllable Language Models. In NeurIPS, 2024.
Minjae Lee, Yoonjae Jung, and Sangdon Park. A Regret Perspective on Online Selective Generation. In arXiv, 2025.
Zhen Lin, Shubhendu Trivedi, and Jimeng Sun. Conformal Prediction with Temporal Quantile Adjustments. In NeurlPS, 2022.
Lars Lindemann, Matthew Cleaveland, Gihyun Shim, and George Pappas. Safe Planning in Dynamic Environments using Conformal Prediction. IEEE Robotics and Automation Letters, 8(8): 51 5116-5123, 2023.
11

---

Published as a conference paper at ICLR 2026
Christopher Mohri and Tatsunori Hashimoto. Language Models with Conformal Factuality Guaran- tees. In JCML, 2024.
Ji Won Park and Kyunghyun Cho. Semiparametric Conformal Prediction. In AISTATS, 2025.
Sangdon Park, Edgar Dobriban, Insup Lee, and Osbert Bastani. PAC Prediction Sets under Covariate Shift. In ICLR, 2022.
Aleksandr Podkopaev and Aaditya Ramdas. Distribution-fres Uncertainty Quantification for Classifi- cation under Label Shift. In UAI, 2021.
Wenwen Si. Sangdon Park. Insup Lee, Edgar Dobriban, and Osbert Bastani. PAC Prediction Sets under Label Shift. In ICLR, 2024.
Aleksandrs Slivkins, Introduction to Multi-armed Bandits. Foundations and Trends@ in Machine Learning, 12(1-2):1-286, 2019.
Ryan Tibshirani, Rina Foygel Barber, Emmanuel Candes, and Aaditya Ramdas. Conformal Prediction under Covariate Shift. In NeurIPS, 2019.
Vladimir Vovk. Conditional Validity of Inductive Conformal Predictors. Machine learning, 92(2-3): 349-376, 2013.
Vladimir Vovk, Alex Gammerman, and Glenn Shafer. Algorithmic Learning in a Random World. Springer Science Business Media, 2005.
Zhou Wang and Xingye Qiao. Efficient Online Set-valued Classification with Bandit Feedback. In ICML, 2024.
Qiangqiang Zhang, Ting Li, Xinwei Feng, Xiaodong Yan, and Jinhan Xie. Online Differentially Private Conformal Prediction for Uncertainty Quantification. ICML, 2025.
12

---

Published as a conference paper at ICLR 2026
A PRELIMINARY
A.1 ADVERSARIAL BANDIT PROBLEM
The multi-armed bandit problem is sequential game between a learner and an environment (Slivkins 2019 Lattimore & Szepesvári, 2020), where the game proceeds over T N rounds. At each round t 7 the learner chooses arm Re from a given set II, where we refer to the problem K-armed bandit problem when [II] K. Then, the environment reveals loss la (TTe) E [Cmin max) from which the learner updates strategy to choose an arm in the next round.
In contrast to the full feedback setting where a learner observes a whole loss vector & E R at each round, the multi-armed bandit problem assumes the bandit feedback setting such that only the loss of chosen arm is observed. Specifically, the adversarial bandit problem makes almost no assumptions on the generation loss vectors. We often refer to the environment as the adversary in the adversarial bandit problem, where two different types of adversaries First, an oblivious adversary chooses loss vectors & for all E [T] at the start of the game. On the other hand, adaptive adversary chooses loss vector l at round based the previous interaction L,, T 1, 1 with learner.
usually considered.
In the adversarial bandit problem, the performance of learner is measured by its expected regret, where the regret is defined as the difference between the cumulative loss of the learner and that of the best arm hindsight
Reg(T) (T)
Σ (m))))
min WEll
(T))
Under the adaptive adversary setup, the expectation is taken with respect two sources of randomness: the learner's ' randomized strategy and the adversary's 's choice of loss vectors. The main goal of adversarial bandit algorithms is to design learner that provides sublinear expected regret. In the next section, we provide a simple algorithm under the adaptive adversary that not only achieves sublinear expected regret, but also guarantees sublinear regret with high probability.
13

---

Published as a conference paper at ICLR 2026
A.2 EXP3.2
EXP3. (Algorithm 2) is a variant of EXP3 (Auer et al. 2002) that achieves sublinear expected regret under both oblivious and adaptive adversaries. While both algorithms consider importance- weighted gain estimator Ht (=) of (x( (Eq. 8 to update their strategy. EXP3. P introduces an additional bonus term 3 thereby making it biased gain estimator. This enables EXP3. to further achieve sublinear regret with high probability (Theorem 2) by controlling the variance of regret.
Theorem 2 (Auer al. (2002). For any ô E (0, and (x(TT) [kmins Emar] EXP3. P (Algo-
rithm 2 with V In KT:7 1.05
and n 0.95 / KT Then, with probability at least
in
1 8, the regret Reg(T) satisfies
TK (V
Reg (T) (Cmax Emin)
I
5..55kkkn
Algorithm E.P
1: procedure EXP3.P(IT T, n, 7,8)
2: Initialize cumulative estimated gain: Go(zt) 0 for all π E II
3: for / E (1....,7) do
exp(nG.-1
4:
Update strategy: PT(TT) (1 (1-n)) Eren expl exp(ncr- + +V R where K = |[]]
5:
Sample arm: n. ~ Pt
6:
Ohserve loss: (Tr))
Compute normalized gain (TT)). defined as Eq.
Construct biased gain estimator: (e(T)) <- [ for all
8:
(T)
9:
Update cumulative gain: G((z) + GT-((T) + (T( for all π E II
14

---

Published as a conference paper at ICLR 2026
B
PROOF OF LEMMA 1
Let
(((T) = de(T) + (T(TT)
mT( + (mm+(T))= = (a a(1 - a)) + +1(m((T) = 1) (- a)) tar(
s(a)
M(a)
(m+(w) + (m) 0)g(a) 1 (m) 1)h(a))
(
Miscoverage Tern (Discrepancy decreases
Inefficiency Term
where Lemma assumes that dx(z)) is of order o(T') for all II.
Then,
Reg
& (m)) min & (x)
Σ
(Ta) + Σ & (Ti)
min
4 (x)
well
me(m)))
Σ (m))
Σ (())
Σ 1-1
& (0) (:: Simply choose π = 0)
(ma( + (e((T)))
Σ g(a)
Σ
h(a)
Tía + aall - a) (0))
meirelmu
(ma(me) + a(())))
Σ
(-a 2a(1 - al)
(0)
magine-l
T
me (m)
Σ
(-a 2a(1 - a))
Ta:(0)
Σ (T))TT
metreim1
TC1
Σ my mp)
E
Σ
a Σ
(-a 20(1 a]) TC2
melre)=0
me mesnet
Σ (m,)
Ta
+
Σ a+ Σ (-2a(1 - a))) TC₁. me(*t--!
Note that C₁ is of order o(T)) (TT) is of order o(T)-1 for all E II.
For given learner, there exists a constant Cgap(7) (T) that satisfies the following relationship:
Σr (mm)(T))) 0)
Cgnp (T)))((())) a
Σ 1 (()((T)) 1)
Then,
Reg(T) 2
Σ m)(m))
Σ (1 (1)20) a) -a Σ (on(T)o(TT)] TC
m.(T)==
metoglal
2 Σ mi())) - Ta
TC, Σ
(T)
melvelml
Dividing each side by T, we have
Σt 1(m((T)) =1) -1)
MC(T) S Reg(T) + +C + a
Cgup (T))
T
Cxc(T)
15

---

Published as a conference paper at ICLR 2026
C EXP3. 1PP3.P-STYLE P-STYLE ALGORITHMS FOR ONLINE CONFORMAL PREDICTION WITH ADVERSARIAL PARTIAL FEEDBACK
We propose three modifications to the EXP algorithm tailored to the setting of online conformal prediction with adversarial partial feedback: OCP-Bandit (Algorithm 3). OCP-Unlock (Algo- 4) and OCP-Unlock: (Algorithm [). While sharing the same algorithmic structure, the three variants differ in their specification of the unlocking set IT, (Tt) and in the definition of the biased gain estimator de [TT, (T+e).
Before describing each algorithm in detail, Table 2 and 3 provide a high-level overview of these differences. The difference in the design of gr (T [1, (T₂)) between OCP- and OCF-Unloch Ucck is highlighted in red, while the additional difference between CCP-Un lnck and OCP-Unloch Un on top of the difference between the first two baselines, is highlighted in blue. The offset term 1 of Ge(T I II (T))) in OCP- -rp-Unloc-- (Eq. I1 is omitted from the tables solely to highlight the differences among the three methods.
Table Comparison of the unlocking set IT, (T,,) and the biased gain estimator 9e( IT. (x+)))) for
each method when my (Tx) = 0
Feedback Type
Meihod
Wlmm)
Bandit Feedback
OCP-Bandit
(x))
1(x
1(x
Semi Feedbuck
OCP-Inlock
I1 112 (11)f
1I2)
anto Ereng + s.l0)
(11)),
OCF-Onlockr
1/x
Ersa 218
(1I))
(a((r)
Eng. woRt
Table 3: Comparison of the unlocking set 11, (T..) and the biased gain estimator (e( (l((T))) for each method when my (Tt) =
Feodback Type
ll(s.)
(x.)
Bandit Foelback
OCP-Bendit
(x)
1 = mx)
+ ppls + is # pi
Semi-bandit Feedback
OCP-Unlock
(r 11 Pond
( e (xx))
Eeorins + ppte/ + 16x He(m)))
oiter
oCE-Unlock+
1( (1()))
(r()) +
# + 1(x He(m))) (n())) si
C.1 OCP-BANDIT
As illustrated in Section OCP-Randit (Algorithm 3) is direct modification of EXP 3.P. (Algorithm 2} for online conformal prediction with adversarial partial feedback. Accordingly, irrespective of the miscoverage feedback mm(T).) from the chosen arm, the unlocking set is defined as a singleton set containing the chosen arm Ny:
(Tee) {me)-
(13)
The biased gain estimator (T(T(II((TT) is then defined as in Eq. ge (TT Il, (Tt)) = (m, = 0) x (A) + 1 (TT) x(B),
(14)
no unlocking
no unlocking
where
(T(
B
3
( ( me) ((
(x(
(t(
While applicable to the partial feedback setting, OCP -Bandia is tailored to the bandit feedback set- ting EXP3 P. thereby ignoring additional information available. Under this design, OCP- -Bandit satisfies the following high-probability bound.
Theorem 3 Auer et al. 2002). For any E (.,),),, N, and 8 E (0, 1), run OCP-Bandit
(Algorithm 39 with V
In 7 1.05 KlnK T and n 0.95 In Then, with probability at least 1 - 8, the regret Reg(T) with respect to the loss defined in Eq.
and Eq. 7 satisfies
Reg(T) < (Amax Emin) (..55VKKlnK +
TK In(5-1)
In K
See Appendix D for proof and additional details.
16

---

Published as a conference paper at ICLR 2026
Algorithm 3 ACCP-Bandis
procedure SCP-BANDIT(II, n. 7, a, a, (ft)
2: Initialize cumulative estimated gain: Go(z) for E for & E (1...., } do
3:
4:
Update strategy: Pe(TT) + (1 1) Enen exp(nGe- + T where K [1]]
(xp(nGr-1(x))
5:
Sample arm: ne ~ Pt Receive me( 5 Ut & Oz,, (211) where Cr, (2t) is defined as Eq.
6:
7:
(T.) -
No unlocking
8:
for क E (T do
(D) Evaluate m²(T) for all π E 11,(T))
9:
(T()) + COMPUTELOSS(n mT(T), a,
10:
Compute normalized gain 9 (T), defined as Eq.
11:
for IT do
12:
Construct biased gain estimator ( (T(())))) defined as Eq.
13:
Update cumulative gain: G,( + - (T) + (T)
14:
procedure COMPUTRLOSSS(T, m,
15:
return de(T;; or) + (T;; at, c), defined as Eq. 6 and Eq.
C.2 OCP-UNLOCE
In contrast to COP-OCPP---Beee -BandBtn CCP-Unlocc (Algorithm 4 utilizes additional information available when my
(T)) ( 0, and leverages the monotonicity of the miscoveraee term my(a) with respect the threshold ı E II to obtain additional feedback when mz( = 1. As such, the unlocking set II, (
defined as Eq. 10
π
if m)
(T.))) =
if mx
The biased gain estimator (T.(I( is then defined as
go (T (Te)) (mm)( = 0) x(A) + (044)(1mmmmm) 11 (B).
(15)
unlocking
partial unlocking
where
ge(TT)
3 Pc(TT)
+ 1( E (1I))) B (r((T)
(A) = 1(T 117)
+
Σ Exem; Pr(
and
(e(TT)
3 Pt(TT)
B
(B) = 1(T E (T())))
+
+ L(x (L,()))) (T(TT)
(m)) (((
As highlighted in red in Table 2 and Table 3 note that Unck OCF-Bandit under a bandit feedback setting, where the unlocking set is defined as in Eq. The following theorem establishes a high nigh-probbbility bound for SCP-Unlock.
ock is designed such that it reduces
Theorem 4. For any a E (0, 0.5). E N. 8 E (0. and X > 0, run OCP-Un (Algorithm
with 3
KT lnK 7 1.05 KlnK and 0.95,
In KT
Then, with probability at least 8, the
regret RTg(T) with respect to the loss defined in Eq. 5 and Eq. satisfies
TK In In(8-1) + o(T)-(T)
Reg(T)) S (Emar - Lmin) 5.15VTKInK +
See Appendix | for proof and additional details.
17

---

Published as a conference paper at ICLR 2026
Algorithm 4 OCP-Unlock
procedure OCP-UNLOCK(L) T, n, a,
2: Initialize cumulative estimated gain: Go(z) 0 for π E for & E {l....,77 do
3:
exp(nG. Update strategy: Pe(TT) + (1 11 Enen exp(nGe- + T where K [1]]
4:
5:
Sample arm: ne ~ Pt Receive my m -
Ut & Oz, (zx)) where On, (24) is defined as Eq.
6:
7:
if my (m)) then (1 t II
(D) Full unlocking: Observe the true label y
8:
9:
else
(p) Partial unlocking
10:
(1T( { x
11:
for
(T. do (T) & COMPUTELOSS(T: me(T), ( a
(D) Evaluate m²(x) for all E (Ta)
12:
Compute normalized gain g (z)) defined as Eq. for ı E do
14:
15:
Construct biased gain estimator ( II, (T., )) defined as Eq. 15 Update cumulative gain: (x) G.- (T) (x(
17:
procedure COMPUTELOSS(T, m, a. c)
18:
return (T; a) + ar (TT; a; c), defined as Eq. 6 and Eq.
C.3
OCP OCP-URLOCK+
OCP-Unl ock (Algorithm uses the same definition of the unlocking set (T, (Fq. 10 as OCP-Unlock:
if (x+)) = (T.) ( if (Em((T))
However, we further strengthen the mixcoverage-first rationale in the design of the biased gain estimator (x.)) (Eq. 11), defined as follows:
gc (T (T())))) = ( = 0) x ((A) 1
full unlocking
partial unlocking
where
(T(
3 ΣxEn; Pe(
(A) = 1 ( [T;)
+ +1 (11))) (((T)) + EESO Po(
ExENy Pe(
and
Eesh ((( 1 E (.(()))))) { (e((T)
3
3 pe(x))
(B) 1(T (
(((T))
The main difference from OCP-Unlock is that OcP-Unlock++ additionally introduces a pseudo- gain (x) when mx( = 1. Unlike OCP-Unlock, the introduction of (r(m) ensures Tr (r( (T)))) 2 ge (T2 (T))) for all E [m,())) and T2 E [1{(TT)) when my mx(m)) = 1, which aligns with the monotonicity property that the miscoverage term decreases |Č (x:)) increases. Despite the use of additional information under partial feedback setting, the lack of the pseudo-gen -aain results in the misalignment with the monotonicity property, which may be the cause of sub-optimal empirical performance of OCP-Unlock in terms of approaching the target coverage level (Section
In addition, for both cases when m, (Tx.) and (m.)) 1, importance weights on both normalized gains (pseudo-gain) -ainns and exploration parameter 3 are designed such that both gain and exploration terms for E II; larger than those from E (II;). Furthermore, for & II; further strengthen this miscoverage-firy rationale by placing more weight on the exploration term 3 for larger conformal sets through the denominator Σast (t()). See Figure 4 for illustration.
18

---

Published as a conference paper at ICLR 2026
Iteration t
4. Update the strategy P
1. Which animals could X, be? x; Tos
Unlocking
fe Y.)
Choose Pt
Observable mi)
Environment
Learner
Update Rule
3. Receive (,,, Observe the true iabel Dog
Efficiency First
Miscoverage First
Cr (x,) f4(x,)) mT) (Lion, Dog, Wolf, Cat)
8: (4: 1)
11:
fe Frug) frOt, Uon) &&ke. Dog) fe0x, Woir) f,Ck,, Cat)
(a) Full unlocking when me(m
Iteration t
4. Update the strategy
Which animals could x, be? Tnd
Partial Unlocking
fx y,) T
Choose TTr
Non-Observable Observable
my (Rt
m
Environment
Learner
Receive (n,)
Cannot observe the true label y
Update Rule
Be 1 (f: 4)
T
C.g (xt,) (y )) 2 m.) (Wolr, Cal) n,
Miscoverage First
4 (P,
66ts &&x,
(b) Partial unlocking when mm =
Figure 4: Overview of OCP Unnockk for online conformal prediction with semi-bandii feedback
We now state a high-probability bound for OCF-Unlockt.
Theorem 5. For any E (0,
EN 2 5, and E (0, run OCP-Unlock+ (Algorithm and 1j = 0.95.
with 3 mn KT = /
KlnKK T
k.K. KT
Then, with probability at least
the regret (Tg(T) with respect the loss defined in Eq. and Eq. saaissiiss
(VTCliK + 4.15 TKIK
TK In In(6 20(T))-T))
Reg(T)) S (Emax mmia)
where C' is the constant defined in Eq.
43 See Appendix G for proof and additional details.
Note that OCP-Unlon lock+ achieves the tightest bound long as VV 2T. to derive the high-probabilityy upper bound of MC(T) (Theorem 1}, we can show that both long-run coverage results of OCP-Bandit and OCP- 1al--Unlee ock are at least a with bigh-probability.
addition, using the same argument based on Lemmaaand Theorem
19

---

Published as a conference paper at ICLR 2026
D PROOF OF THEOREM 3
The proof based on that of Theorem Auer et al. 2002). where we have slightly modified the original proof to accommodate arbitrary bounded loss functions. Specifically, first provide arm-wise high-probability bound (Lemma 2). which is then used to derive Theorem
Note that both the proofs of OCP OCP-Unlock (Theorem 4 and OCP-Unlocks (Theorem follow similar structure to that of OCP DCP-Bandit t (Theorem 3 accompanied by additional technical details
due to the introduction of the unlocking set II, (Tz) and the modification of the biased gain estimator 9e( (T]II,(TT) accordingly. See Appendix E and Appendix for for detail.
First, we show that the biased gain estimator ğe (IT)) of OCP Bandit (Eq. 14) satisfies the following high-prow sesh-probability inequality for all E II. Note that Eq. [4]is is equivalent to Eq. 9 which re-expressed to clarify the difference between the biased gain estimators of -CP-Unlose lock and detailed in Appendix [
OCP-Unlock.
Lemma 2. Let B < and 8 E (0, 1). Then, for each æ E II, the following holds with probability at least 1 - 8:
T
T
+ In(5-1) B
Σ ( (T)
S Σ (x
Proof. Let E6, be the expectation with respect the distribution Pt, from which कy is sampled. Since
exp(x) I 1 + x + x² for x I 1, for 3 < 1, by letting (x(T) = (ge(x) (x)(
< 1, we
pc(n)
have
8² (T(
)
B
E.
exp
(T)
(.).(TT) + E. (A)
exp
(((TT
(T(())
82
Pe(T))
exp
Pt(TT)
32
1
(T(
exp
Pe(T))
(:: ge()) [0.
$ (::1 + exp(u)).
By sequentially applying the double expectation rule for t T.....1
g²
TE exp
Σ (m)
1.
(16)
(T(
Moreover, from the Markov's inequality, we have P P(X > lm(1/0)) = F(exp(X) > 1/8) s
oE exp( Combined with Eq. 16 we have
Σ
(g( < Σ (T(T(II + In(8-))
with probability at least - 8. This completes the proof.
Now, we derive the the regret bound of Bandit (Algorithm) 3). which consists of three steps.
First, our goal is to show that, if 7 and (1 + 33+3)K S
Reg(T) S (Emax min) (K3T + XI + (1 3)nKn+ In(K8-1)
lnk)
In
B +
(17)
Irrespective of the hyperparameter setup, note that Theorem 3 always holds if <
I In (01
TK
5. 5.15%TKlnK. IFT which makes it suffice to show that Eq. 17 holds for y I 1 and (1 + 3)Kn S
15.5-1)+5.15TKKKmm TK
this implies that S 1 and (1+3)K S7.
20

---

Published as a conference paper at ICLR 2026
Step 1: Simple equalities. For all II, the following equality holds:
Encp (T()((( ge(TT) 3K.
(18)
Then, for all iT E II. the following equality holds:
T
T
Rx = Σ ((T)))
(T))
T
T
(fmax
Eminn)
Σ (c(T))
Σ (u(T)))
(:
Eq.
8
(19)
t=1
t=1
T
T
(fmax
(min))
3KT +
Σ (T)
Σ
E (+ (.(()))))) (:: Eq. 18).
Using the definition of cumulant generating function and the relationship that pr (1 7)w + yu and u is the uniform distribution over K arms, the following where Wi (TT) = Exen esp(1G(-1(R))
exp (1())_((()))
holds:
- IE Dr. ( (T+))
=- )) Dr (T [le(T))) ( (:
(1 >) + ru)
= (1 - 7)
Inll In exp (Tl - Ex (((
(20)
exp.x
- P 9 (T)))
Step 2: Bounding the first term of Eq. 20
Since In x S x - exp(x) I + x for all r S 1,
and ng. ( I
I+0
(+)+7) S (:: (1 3)nk Sn),
pe(#)
In Es exp (n(ād
B Jr (
= In Eg exp (n (7 - - 11, (T.))
< Enaur fexp ng. (
ng. III (T+))
(: x
< Erruw "1 ( (TT))) (:. exp(x) 1 x x²)
(21)
w
1
$ 1/
(T
Pr
#Ell
Step 3: Summing. Let (+) = 0. Then, combining Eq.
20 Eq 21 and summing over t yield
Σ Pap dr (T.))
T
< 511 8)
1-7
In
Σ (x( (xp((n
1-7 In
(:: Definition of (4()), G#)) Even exp(n)r((t)
= =(1+ +)+
(()))
een exp(1)(((#))
t=1 REll
In 1- 7 In
<(1 +1+ B)nk max (+)
exp(nG)(#))
1=1- 1-1-7- 7 < and Go(#)
7
Fell
Iu K
$ 5-(1 - 7 (1+ K)
max
(F)
(::
Property of log-sum-exxpomeniaa)
#ell
In(K811) K
$ <-(1 7- (1 (1+3))/ max (() +
n
(22)
21

---

Published as a conference paper at ICLR 2026
where the last inequality holds due to the Lemma and the initial assumption that y I and (1+ K)Kn S ?. Plugging Eq. into Eq. 19 the following holds with probability 8 for all
E II:
[KBT+TT+ (1+ ()nKK) + In(K6-1) In K
(T) S (fmax mmin)
1
Since Reg(T) max R2 (T), this completes the proof by taking the union bound.
22

---

Published as a conference paper at ICLR 2026
E USEFUL PROPERTIES FOR THE PROOF OF THEOREM 4 AND THEOREM 5
E. MONOTONIC STRUCTURE OF SINGLE-TIRESIOLDDER CONFORMAL SETS
We consider a class of conformal sets parameterized by single threshold и E II, defined as Eq 1 Within the model class, the miscoverage term m₂(x) is monotonically non-increasing as the size of the corresponding conformal set (C,, increases. Equivalently, m²(T)) is a monotonically non-decreasing function with respect to the threshold parameter
E.2 PROPERTIES OF THE LOSS FUNCTION
The followings are the properties of the loss function
( a, (T; (T;
defined in Eq. Eq. and Eq. 7 We henceforth write (((x),, de(r), and (x()) for simplicity, indicating the dependence on a and c only when needed.
By the definition of a.) (Eq. 60. ((Tra)) = a a(1 a) for all x E IT, and (T; a(1 - a) for all (II;).. Note that for (0,0.5).
a a+a(1 a) < a(1 a).
(23)
For all T1, n2 E II such that æ1 S π2
a<(m1) 2 (T2))
Therefore, for all mı, n2 MT such that क S n2.
((m)) 2 & (T2).
(24)
For all Æ1, n2 E (II;)* such that πı S T22
(1(TT) v (T2))
Therefore, for all Ni, T2 II such that TΣ S π22
4(m)) S & (T2).
(25)
Let t,0 = max ((T) and l,1 == m (T). By letting Tr,0 == min, El;; = and ne,1 = (m;)e
4,0 (((T)))) (:: Eq 24
4,1 ((T,)) (:: Eq.
25
Since controlling the miscoverage is the primary objective, the loss estimator will be most satisfactory when l,, S l,,1 for all [T]. Indeed,
E,,1 l,0 (1 2nx (1 - a) + (a (=(
> (caa)o(T)) + (ca)o(T)--
0.
Therefore,
4(m)) S ((T2), Vm E I, Vn, E (I;)).
(26)
bmax a(l -a) I+all- -aal1-2a) o(T)- o(T))
mmin = a a) - (1+ (+a (T))
23

---

Published as a conference paper at ICLR 2026
E.3 PROPERTIES OF THE NORMALIZED GAIN
The followings are properties of the normalized gain (T( (Eq. 8 and the pseudo-gain Ør (T) (Eqq. 12 terms under the partial feedback setting.
Case I (T+) = 0)
1. E II and S Te: (((x) 2 ((()) + (((T) S ((( (:: Eq 24
2. 11; and π nii (TT) S (T(T)) + 9((T) (T().. In addition, since (e(
- A(T))
O(T)
ge (m+)
Enm Emia
[1 (1-2a)1 10a
2nj (ca)o(7)-T)
(x) ((( + o(T) (: Eq. 24 & Taylor expansion).
3. (IT)): ((m) 2 (m+) (x) () (:: Eq. 26
Additionally, for all (II)),
(x(
fmx (x)
mmax (T()
o(T)- o(T)-
1+o(1 20)=
1+o - 20)
(1 11-2a)(11 a) (1 T-a T+a(1-20) (C)
=(T) -1 (:: Taylor expansion).
Therefore,
9x(x) = o(T) -g()) Vn (II)).
Therefore,
(x( S
Vr II;,
(27)
(((T) S o(T)) VT (II)).
Case 2 (m)((T)) = 1) 1. (T())) (II)): 4(t) (()) + (T( s (x)))) (:: Eq. 25
2. ITT)
o(T)-
o(T')
ca
1+o 20
I+a(1 - 20)
- (((())
=
(1 2a) a) (1 1-a + 20) (ca))((T)-
= = (:: Taylor expansion)
Therefore,
(T(T)) s ((( VT E II((T)).
(.(T) s (m)) + - E (T.)))..
(28)
24

---

Published as a conference paper at ICLR 2026
F PROOF OF THEOREM 4
The biased gain estimator 9: (T))) of (Eq. 15
satisfies the following inequality,
Case (my (T+) = 0)
T Pp- (T(
Eren (TT
=Erey Pe ((
(29)
=Eren; p((a)
air) Pazm 25t pp(ा) + Kemppy pi(t) (m)))
Sa(l)))o(I)) LKB (2
27
Case 2 (Te)
Ex-p ii (F))) Pe
(30)
-E P((
scim)
+ Cenneee pe(m)
Enenatee) PrtRy
petal
pet7
(a(()))88 (V Eq.
Combining Eq. 29 and Eq.
30,
the following upper bound holds irrespective of the choice of me
T Pe (T.))) (T()) + o(T) K8.
(31)
Arm-wise High-probability Bound. following lemma, a variant of Lemma
Before moving to the regret analysis, provide the
Lemma 3. Let B < and 8 E 1). Then, for each æ E II, the following holds with probability at least 1 - 8:
T
+ In(8-1)
(T(T))
<
B
1=1
Proof. Step 1:
Useful Decomposition.
Let E, be the expectation with respect to the distribution Pt, from which is sampled. For each II. the biased gain estimator can be decomposed the following:
ge (T (T.))
1 (me( (T.) = 0) (A) 1 (T+) (m+ x) x(B
full unlocking
partial unlocking
(mm+(T)) = 0) x (AA)) + (A2)) + (TMe(TT) =
(B2))
full unlocking
partial unlocking
22mmm/////b///aaaaaa////////x/a + +1imitt====xx/4))Hmmmmmmsm)sm)
(C1)
(C2)
where
(
B
(A) 1( E II))
Σxem; Pr(
(T(
(AL)
(A2)
and
(((TT)
B
(B) = 1(T (l.)))
Enetl (((
(T(
(B1)
(B2)
Step 2: Show (T(T) < 1.
Next, we show the following claims.
25

---

Published as a conference paper at ICLR 2026
Claim (me( 0)
Bg((T) - 3 (A1) = -g((T) - 3 ge(
S1 1
EiET: Pe(
Claim 2 (mee(Te)= = 1)
ge (T)
(g((TT) - 3 x (B1) = (T)(TT) B
S 1
(m.) (t(
Given II, Claim 1 and Claim 2 always hold irrespective of the choice of Te by the algorithm. Then, by letting ( = (T) - 3 x (C & for all π E II.
Step 3: Show E exp
E (A,(T) x (C2)) 1
Therefore, since (1) exp(x) I 1++++=+* for æ 1 1 and (2) (+) S for B 2 we have
Fy [exp (A,(T) - (C2))) s 12 (1 (m) + (T) exp( x (C2))
-32
F2 (1 (T) + (+)) x exp Pc(
Since π is fixed, we consider each case where π E II and π E (IT)).
Now, our goal is to show that
Ex [exp (A.(T) - x (C2)) sive (7..
Step 3-1: π E II;
Step 3-1-1: E, (T(T)
Σ (() = 3gc(TT) - p((f x 3(C1)
REll
REll
gT(
= (T) - 3 Σ ( iT)
Σ ETEE Pt (T²)
REM:;
0
Step 3-1-2: Ey [m)m))]
Σ p. (()) = Σ Pe( (#)² +
Σ (()))
REll
#EIl;
RE(U))
2
(T)
Σ (T(
1 1- Exren; Pe( {
+ (Bge(T))² Σ pt(T)) #E(1)))
REll:
B2
Σ Exen; (r( (:: (e(T)) [0.
(x(
Step 3-1-3: Combine. Combining the above results and applying the fact that 1 + x S exp(x).
E2 [exp (Ae(T)) 3 (C2))) < E2, (1
+ A, (T())
exp(-3 x (C2))
g2
exp
E,
(1 + (T) + (m)
(t(TT)
g2
S exp
1+
(r((T)
(T(
$ (:: 1 exp(x)).
26

---

Published as a conference paper at ICLR 2026
Step 3-2: (I
Step 3-2-1: E, A A
Σ (a) = 3g((T) Σ p((F) x 3(C1)
#Ell
REll
9t (T)
= -g((()) -
Σ )E(TI))
Pr(#t)
2' Pr(T')
ge(
- (g((T)) - 3
Σ (((
Σ >
#
=0
Step 3-2-2: Ey [m(m))]
E (R) Exen = ((()
=Emnn (( (t) (())) (a) (())
=Esenp ((())(g((M)) (5) ( (()((())))))))
Bade)
+ EA
Seen 2 Simena (5) (+)((8)(())_a )
+ P (+))
82 $ Sate (2 (.)()))())1))
Step 3-2-3: Combine. Combining the above results and applying the fact that + x S exp(x))
E2 [exp (Ac(T) 3 (C2))] E, (1 (T))
(x( exp(- - x (C2))
exp(
)E,
(1 +
A TT (T)
(T(
,32
32
S exp
1+
((((T)
Pe(T))
$ (:: 1
exp(x:)).
By sequentially applying the double expectation rule for = T ,,...,,. 1,
E Eexp
Σ (A.(T) B -(x
51.
(32)
Moreover, from the Markov's inequality, we have IP P(X > Im(1/6)) = ((exp(X) > 1/8) < òE ex)( Combined with Eq. 32 for every π 11,
Σ
(1( Σ (()T In(8
with probability at least 8. This completes the proof.
Proof of Theorem 4 Now, we derive the regret bound of OCP-Unloch (Algorithm which consists of three steps.
First, our goal show that, if 7 S and (1+ %
Reg(T < (fmax (min (KBT+ +T
+ + (1 + KT
In(K8 1)
K
(33)
27

---

Published as a conference paper at ICLR 2026
Irrespective of the hyperparameter setup, note that Theorem 4 Jalwass holds if V In
IK
In(6 (1) +
5.15vTKlnK + VT. If (1+ K) S 7 which makes it suffice to show that Eq. holds for y s 2 and (1 K) %
TK In(6-)) lo
+ vT, this implies that y S 2/ and
Step 1: Simple equalities. For all и E II, the following equality holds:
R2 (T' = Σ (m)) 1=1
(T())
t=1
T
(6max Lmin)
Σ
(T( Σ (((Tt))
(:: Eq.
1=1
1=1
$ (fmax mmin
KBT + o(T) o(T) 'T -TT Σ (e(T))
Σ E Ex 9e(# [T((TT)) (: Eq. 31
Using the definition of cumulant generating function and the relationship that pr = (1 7) + yu
exp(1G, 1x+))
and u is the uniform distribution over K arms, the following where wr(T) (TT) Eien (1{())._1(8))
holds:
-Eap,, (e [T))
=- B (T()) -yE [e(T))) (: Pt (1 7)wr, + 7
[ InlE Aower exp (n( (T.)) 5i II{(T)))))
(1 7)
In exp [c(Te))) -EE ( (x.))
(35)
Step 2: Bounding the first term of Eq. 35 First, show that irrespective of the choice of mes
ng. (T (Te)) S 1 Vi e I1.
m((T)) = 0, π E I1;
De (T))
B
19 ( (T+ =
ExEnç Pt(
(((
(((((T) + 3)
Pe (T(
771 + 3)
$ (1 ( +
(:: (x)) E (0.
$1(: (1+)))))
m(m) 1, π E (1x(T))
(T(
(T( = EteH (( (c(
(T) +
(TT)
11( 9)
5 (1 7)w:(()) + 1
(:: (T) E 10.
(1(:(11 B) 59)
28

---

Published as a conference paper at ICLR 2026
((())) 0, (II;);; m(Te) 1, E (m)))
13
(T((T = 17 pe(
n1( +
$ (1 - ()= 7 1
< (:: (1 3) 5)
Since (1) I S x 1, (2) exp(x) 1++1+ x x² for all 1, and (3) nge [l(( S 1
In Ex exp (n(āe(# ( I1 En 9i I1, (T))))
In Fa exp(ngel
(m)))) = ( (T())))
< Fanw (exp(1ge
(T(m)) - 1- 1-1--19 n) (T(m)))) x
(36)
< Barwr n @ (T,))))) (:: exp(x) S x+x+2²)
- 1+
REll
where the last inequality holds due to the following.
m((+) =0
E E v (((
Ereny (i(
Er mil + mies) t (())
<n²² E Erm (z)
Lig de (ra w1t) (Mi ( (1)(())))).1))
<1 Exenp ((([))(()))))) Eeempy (((M))(()))) (: (
= 144 Eeen (m)))
m(TT) =
Enau, o (x
=/ Eren(ta (F)
Ee Peley ,ा(.))
21(0)
+ " wi() (nim))
< ( (+))
P2 ( w)
(+ (19:(#))(0.1))
<n 14d Enen (())
Step 3: Summing, Let G)(+) = 0. Then, combining Eq.
35 Eq. 36 and summing over t yield
Ba ((
$ 51 8)n
(T))
In
Σ (*) (x | ((()))))
wen
1-7 In
xen exp(n)r(#t)
= -11+ 8)m
(:: Definition of (#)) G,())
snn exp(nGn(#t)
flll
< (1 + 8)nk max ())
IK
1-7 In
Σ exp(nnG((a))
(: 1 S and Go(#) = 0)
17
7
Fen
lnK
(1 ())
max
(7)
(:: Property of log-sum-cxpomential)
Fell
"
In(K611)
In K n
$ - (1 max
g((5)
8
(37)
29

---

Published as a conference paper at ICLR 2026
where the last inequality holds due to the Lemma and the initial assumption that y I and
(1 K)Kn S ?. Plugging Eq. 37 into Eq. 34 the following holds with probability 8 for all
E II:
(T) S (fmax min))
KØT + ((T)
( -T + Σ 9r (e Σ
E p. 9c(# [T,
In(K8-1)
In K
$ (feax min)
+ o + + (1 8T +
+
B
n
Since Reg(T)
= -ax R (T), this completes the proof by taking the union bound. =EIl
30

---

Published as a conference paper at ICLR 2026
G PROOF OF THEOREM 5
The biased gain estimator Gr ( (T]LL((TT)) OCPOOCPP--- -Unlokkk (Eq.
satisfies the following inequality,
Case I (Te) = 0)
Ha-p (T: (
=en Pr (x)) Eemp ((()),((((
=m (x))
pe(x)))ee(())))e)))))))))))) + + Emcapp pi(z) 91(=)) Enge pe())
(38)
Eeen; Pelm) (a
Drenp p((R) (:
Case 2 (m2((Te) = 1)
Ez 3e (= > en (x
=n Pe(m)aa(= (m)))))) E cu (((T))((T((L((m)))
= Ee Pe(1) ( Eege + Eem Pa(t) का( +.3
(a( (+) Eseme
(v Eq.
(39)
Combining Eq. 38 and Eq. 39 (x)p.
the following upper bound holds irrespective of the choice of me:
((T) (m())))) + o(T)
Ex Pi(#)
+ 1 + (1(m(()) 0)1 + (m)(m))))))))))))))))))))))))))) = (x)
B.
Exen; Pc(
(40)
Arm-wise High-probabilityy Bound. following lemma, a variant of Lemma
Before moving the regret analysis, provide the
Lemma 4. Let B < 1 and 8 (0,1). Then, for each æ E II, the following holds with probability least 1 8:
T
( + In(8-1
Σ (T)
Proof. Step 1: Useful Decomposition.
Let E, be the expectation with respect the distribution Pt, from which ne is sampled. For each E II, the biased gain estimator can be decomposed as the following:
ge (TT [l,((T)) 1 (T, = 0) (A) + 11mmmmmmmm)) (T. = x(B)
full unlocking
partial unlocking
((m)(Tt) = 0) x (((A1) + (A2)) + (Te) =
(B) (B2)}
full unlocking
partial unlocking
(1mm + +4
(C1)
(C2)
where
S adm) (A)=1(=El1)) Deen; Pett) (1(E((1))))))))) ((sen;) Hovel) P((s) ( (Teel)))
(A1)
(42)
and
(92)
Step 2: Show A (TT) < 1. Next, we show the following claims.
31

---

Published as a conference paper at ICLR 2026
Claim (me(T))) 0)
- II
(9((T) - x (A1) - (gc(T) - B ge(
EETT Pr (T) 5
(117)=
(B((T) - 3 (A1) = -B(((T) (ge(T) =
Claim 2 (m)( =
- T E (I(TT))
(T) - 3 x (B1) = (g) - -Bg((T) =
E (T))) 3g((T)) - 3 (B1) 3g((T)) (T) S 1 (:: 8 and ()) [0.
Given π E II, Claim 1 and Claim 2 always hold irrespective of the choice of ne by the algorithm. Then, by letting (T(T) = (T) - 8 x (C1). (T( for all æ E IT.
Step 3: Show E exp
Σ T
(1) B x (C2)) 1.
Therefore, since (1) exp(x) < 1 11++ 2 for x S 1 and (2) (T(T) s for 3 S have
E2 |exp (Ax(T) - 3 x (C2)) < E (1 ( exp(-3 x (C2)) 92 E ाहं - +I( jeap Eas Pelmi)
3²
xTa (1))
Since is fixed, we consider each case where и E II; and π E (II)). Now, our goal is to show that
Eg [exp
- B BB (C2)) S 1 Vt E [7].
Step 3-1: ı E II;
Step 3-1-1: IF (m)
Σ (() = (T((TT) - Σ p(( x ((C1)
REl
#ENl
gt(
S (g((T) 3 Σ Pt
Σ 'EI; Pt (7²)
REll;
=0
Step 3-1-2: 15, [m)])]]
Σ (,(
Σ (x))+
Σ (()
FETl
REm
REMTEE
(T)
Σ (+)
Σ ((( - -))(7))2
Exen; (r()))
xel
*E(TE))
+ 8² (v (.()). e [0.1])
ERem; Pt(
32

---

Published as a conference paper at ICLR 2026
Step 3-1-3: Combine. Combining the above results and applying the fact that + exp(x))
Er (exp (AT(T) - 3 x (C2))] < Er (1 + + x exp(-3 x (C2))
g²
Fy (1 (x(T) + A{(T)))
exp
Σ Ren; Pc(
g2
-2 )
(1+ EREN; Pc +
B
$ exp
Σ Ell; Pt(T)
1 (::
+ x S exp(x)))
Step 3-2: E (II)).
Step 3-2-1: E,, (T(T)
Eren (1)) Eeen; (f) E E Pi (R)
= (f) ( P: (T) (F))
E Eeny (()) (m) P
(1
+ (0
- Px (:
12
Step 3-2-2: E, [(()))
Esen -ien; Scamr (18))
Esen; Eo ((+)4 Pe ((T)) 200
Enen (0000)00000)))0)000(((000()))))) aimen 2i
+ P
E4 12
=0
Step 3-2-3: Combine. Combining the above results,
E, [exp (A+ - 3 x (C2)) < E, (1 + (T(T) + ((())) x exp(-8 (C2))
B
= exp(
E, (1+ A.( + A(())))
Σ
Etsa (()
g2
= exp(
(t(
1.
By sequentially applying the double expectation rule for f. T,
LL exp
Σ (A)
1.
(41)
Moreover, from the Markov's inequality, we have P(X In(16)) (exp((X) 1/8) < eEexp(X). Combined with Eq.
41 we have
T
T
3
gl(
3
+ In(511) +n(
(T
1=1
t=1
with probability at least - 8. This completes the proof.
33

---

Published as a conference paper at ICLR 2026
Proof of the Theorem 5
First, re-exss Eq. 40 for the simplicity of proof as the following:
{
(me( $ 1 o(T)
Exempy (i(
3)
(42)
(1(m((m)) 0 ( (=))
3
Σxem; pT(
62
Now, we derive the regret bound of OCP-Unlock. (Algorithm Tb. which consists of three steps. First, our goal is show that, if y and (1 2:3) < %
laxx min
CBT + 20( RT' + (1 23mKT In(Ko-1)
In K
Reg(T)= - 1 1+
+
3
(43)
(Zize Ci K)
where C = min
Irrespective of the hyperparameter setup, note that Theorem S always holds if T
TK In(5-1)
In
VTClk 4.1.
+ 2. If 2 V
TK In(ō-1) + VTCIn 4.15v 2VT,
In
this implies that 7 S 1 and (1 + 2m S 7 which makes suffice to show that Eq. 7 S and (1 + k3) S.
43 holds for
Step 1: Simple equalities. For all E II, the following equality holds:
RT(T) (m)
((x))
(faax - kmin!
(((T)) Σ (m)))) (:: Eq.
fmoxx Emin
CST o(T) IT (1 oTT)
(e(
Σ 9e [(((z))) (: Eq
1+ o(T)-
(44)
Using the definition of cumulant generating function and the relationship that Pt = (1 7) + yu
exp (I))...(()))
and u is the uniform distribution over K arms, the following where (T)) Even exp(nG, 1(5)
holds:
- -E (n (Te))
= Bg Ic (TT [le(T))) 7e [l(()))) (: = (1 - 7)wr + yu)
= (1 - 7)
In ww, exp (f [T:()))) - ERNw ( (l(())))))
In
[((T))))) - -REaaau (T())))
(45)
7
Step 2: Bounding the first term of Eq. 45 First, show that irrespective of the choice of m.
nō. (T (Tt)) < 1 Vo E IT.
mm(T)) = 0, π E 11;
( +
(Tx(T([1((TTT) =
+ 3 Σxen; (+(
7/1 + 2,9)
Σ Σxen; ((1 - - + (: (1 23m s and (.(T)) [0, 1))
34

---

Published as a conference paper at ICLR 2026
. m(m)) O, (IIG);; m(T)) 1, π E [m))))
n9. (T( = 7j gi(TT) + Σ Exs Pc(
(T) + B
5n
Eigr Pr (T)
1/(1 + () Eas ((1 - -)) x
(: (1 (::11
23) 5 and gx(x) 1))
1
-((+) = 1, l1)
3
(T 17 (e(TT)+ +
p((z))
(T( + B
(:: Eq. 8 Eq. 12, and Eq. 26
(T)
17(1 + B)
(:: (1+ 28) S and (c(T) E [0,
( +
<1
Since (1) In S x (2) exp(x) s + x x² for all 1, and (3) n (xx))) S 1,
In LE exp (f(ār(# 11e((T)) (T+)) - BBnww g: 11. (T:())
In Eg exp (n [I,(T))) nw ( [((T))
s Eaowi (exp (nge [. - 1 nāe ((())) (: S
(46)
< Banw 11 ( (=x)) (t. exp()) < +1x++0
2,3
Σ (.()))
< 1/ 1 1-7 REll
where the last inequality holds due to the following.
m(T)) =
Ea Ea 1a (())))
Eireen Pater +3) - Ee w.( (c((+)) xi (s((t)+ ((or)) ) )²}
=
Exen; wx(+)
Sn² EEeey (F) (1+3))
(T))) Ee (n( 1428 (=( (=)(())))))))
Sn² 148 Enen (F(I.())) ( 2A )
m(T))
Es 1² (. (1)
Yeel uz( (2)) (d(5)t
+E (a)(()))))) ii to)²
59
Exemtio in (m))) we( (1420 (z))) (1eee))
S9p
Enen (M))) (it
35

---

Published as a conference paper at ICLR 2026
Step 3: Summing, Let Gu( 0. Then, combining Eq. 45 Eq. 46
and summing over t yield
( [l((m)))
$ (1+ 28)n
9e (x))
In
Σ (x( exp(ni (((a)))
(1+ 2
Σ
S (x.)
1-7
E Fen exp(nGr(#t)
(: Definition of (1))
Ezen exp(n
t= RET
In 1-7 In
1 (1 Gmx RENl
exp(yGr(f))
(v1-75 S and Co(R)
In
--(1-r- < - (1+ 2
Imax FElf
(:: Property log-sum-exponeetaal)
In(Ko-)) l
< -1 r- (1 22)nk)mmm
max REll
(()))
(47)
where the last inequality holds due to the Lemma and the initial assumption that 7 < and
(1+ + Kn & n. Plugging Eq. 47 into Eq, 44 the following holds with probability K for all
E II:
R. (T) $ fmax Emin o(T')-
CBBT+ 'T (1 ((T)
T E (()
Σ
T
E Einpie [((me))
maxx Lmin
a -77777777- 7T
(1 + 28ynKT + In(Ko-t)
In K
+
o(1')-1
7
C/3T++20077 '7' + +M' + + 23) IkK--11) In
< (Emux - mmin)
8 +
17
Since Reg(T) = max R,, (T), this completes the proof by taking the union bound.
36

---

Published as a conference paper at ICLR 2026
H ADDITIONAL EXPERIMENTAL DETAIL
H.1 EXPERIMENT IMAGENET
We use a pretrained ResNet-18 (He et al. 2015| as an image classifier, where pe (a(y(z) its estimated probability of label y given input z. In the i.id. setting, we use ft(2,, = ( /3 scoring function for all E y and f E [TT. Meanwhile, we simulate the non-i.idd setting by changing the functional form of the scoring function for every 10, 000 time steps. Specifically, unlike the i..dd setting, we define the scoring function using different exponents of the estimated probability po(y)x4)** for y V/ where
1/6
E [1, 10, 000]
1/4
t e (10, 000, 20, 000]
04
1/2
t e (20, 000, 30, 000]
1/1.2
t E (30, 000, 40, 000]
1/3
t (40, 000, 50, 000].
Note that the scoring function concentrates to I as decreases to 0, simulating the non-i.idd setting where the range of the scoring function and the difficulty evolve over time.
H.2 EXPERIMENT 2: AIRFOIL SELF-NOISE
We linear regression model ((z), which is trained using the recursive least squares algorithm. For both i..d. and non-i.i.d settings, we use the following normalized residual score as a scoring function:
by 5(x,)]
f(
where / and u denote lower and upper bounds on the residuals y - [x)]. respectively. Unlike Experiment 1, simulate the non-i.i.d. setting by changing the input distribution after the first one-third of the datastream, as illustrated in Section
For all subsequent experiments, unless otherwise specified, use the same i.i.d. and non-i.i.d. setups for ImageNet as in Experiment 1, and the same i.i.d. and non-i.idd setups for Airfoil Self-Noise as in Experiment 2.
37

---

Published as a conference paper at ICLR 2026
H.3 CHOICE HYPERPARAMETER
For all experiments, we set c 40 in the loss function a(;aa, = (T; a:) + (x; c). as defined in Eq. 5 Eq. 6 and Eq. 7
We report the long-run miscoverage MC(T) and inefficiency Ine averaged over 50 independent trials, across various 7' and settings for both classification and regression tasks. For the discretization level, we use A = 200 for ImageNet and K = 20 for Airfoil Self-Noise. The results show that our method consistently achieves decent performance for fixed e, uniformly across different datasets, data generating processes, and T, settings (Table and Table
Table 4: Long-run miscoverage MC(T) and inefficiency Ineff (T) on ImageNet for different choices of T and target miscoverage level o, under the i.i.d. and non-i.i.d. settings
i.d.
Non-iid.
T
Metric
a=0.1
a=0.2
a=0.3
o=0.4
a=0.1
a=0.2
a=0.3
a=0.4
MC(T)
0.131
0.230
0.303
0.340
0.156
0.250
0.318
0,352
50,000
Ineff(T)
46.73
16.77
8.47
6.25
56.32
27.30
18.08
14.88
MC(T)
0.123
0.226
0.307
0.346
0.147
0.249
0.322
0.357
60,000
Ineff(T)
51.29
17.69
7.99
5.77
61.20
27.41
17.39
13.88
MC(T)
0.116
0.222
0.310
0.350
0.141
0.246
0.324
0.361
70,000
Ineff(T")
54.90
18.25
7.70
5.55
64.84
27.69
16.54
13.23
Table 5: Long-run miscoverage MC(T) and inefficiency Inef(( on Airfoil Self-Noise for different choices of 7' and target miscoverage level a, under the i.i.d. and non-i.idd settings
i..d
Non-i.id
Metric
n=0.1
m=0.2
0-3.3
o=0.4
e=0.1
0=0.2
0-0.3
o=0.4
MC(T)
0.062
0.129
0.193
0,243
0.084
0.174
0,263
0,329
30,000
Ineff (
13.29
9.62
7.84
7.12
15.37
10.90
8.82
7.51
MC(T)
0.057
0.123
0.191
0.243
0.077
0.168
0.261
0.330
40,000
Ineff(T))
13.41
9.70
7.84
7.07
15.52
10.92
8.87
7.46
MC(T)
0.054
0.119
0.189
0.244
0.072
0.162
0.258
0.332
50,000
Ineff(T))
13.53
9.69
7.84
7.02
15.83
11.02
8.85
7.44
38

---

Published as a conference paper at ICLR 2026
I EXPERIMENT 3: ABLATION STUDY ON THE LEVEL OF DISCRETIZATION K
We provide an ablation study on the discretization level E N in implementing our bandit-based algorithms. In terms of theoretical guarantees, our regret bound is proportional K, so increasing K yields a finer threshold grid at the cost of a larger regret bound. Meanwhile, empirical results suggest that finer discretization of the hypothesis space necessary keep conformal sets compact. To quantify this trade-off, we conduct an ablation study on both classification and regression tasks by varying K while holding all other parameters fixed. For ImageNet, we set the horizon to T = 50,000, and the target miscoverage level to a 0.15. For Airfoil Self-Noise, we set the horizon T 50,000, and the target miscoverage level to 0.1.
We report the long-run run miscoverage MC(T) and inefficiency IT) averaged over 50 independent trials for classification and regression tasks, respectively (Table 6 and Table
Table 6: Ablation study on the level of discretization (K) on ImageNet
i..d
Non-i...
Method
Metric
K=180
K0200
K2220
K=180
K-200
K22
MC(T)
0.212
0.214
0.215
0,228
0.228
0.229
OCP-Bandit
[neff(T
21.02
20.25
19.84
33.16
32.77
32.47
MC(T)
0.209
0.211
0.212
0.225
0.226
0.227
OCP-Unlock
Ineff((T)
21.65
21.05
20.45
34.54
33.76
32.86
MC(T)
0.172
0.173
0.176
0.199
0.200
0.201
OCP-Unlock+
Ineff([)
31.21
29.85
28.52
40.45
39.11
38.17
Table 7: Ablation study on the level of discretization (K) on Airfoil Self-Noise
i.i.d.
Non-i.i.d
Method
Metric
K=10
K=20
K=30
K=10
K=20
K=30
MC(7)
0.056
0.064
0.070
0.071
0.084
0.092
OCP-Bandit
Ineff(T)
13.97
14.06
14.03
16.54
15.96
15.79
MC(T)
0.056
0,064
0.069
0.070
0.083
0.090
OCP-Unlock
Ineff(T))
13.71
13.81
13.94
16.49
15.97
15.79
MC(T)
0.050
0.054
0.056
0.064
0.072
0.076
OCP-Unlock+
Ineff(T)
13.28
13.53
13.60
16.37
15.83
15.74
While it is theoretically expected that longer time horizon is required to avoid undercoverage when the hypothesis space is more finely discretized. the goal of this experiment is not to maintain performance across different values of K, but rather to study the effect of varying K while keeping the other parameters (a, T) fixed.
39

---

Published as a conference paper at ICLR 2026
J EXPERIMENT 4: ABLATION STUDY ON OCP-UNLOCK+ AND ITS VARIANTS
We conduct an ablation study comparing three Sriants-OCP-Baddit OCP-Unloc and OCP PeP-Unnock+-a0 terms of (i) miscoverage rate MC(() and (ii) inefficiency Inef((t) over time t E [2]. In each plot, the solid curves show the average across independent runs, and the shaded regions indicate the min min-max max range. Overall, CCP-Unlock+ achieves tighter coverage under both the i.i.d. and non-i.id. settings. This improvement comes with mild cost: OCP-Unlock+ tends to output slightly larger prediction sets, yielding moderately higher [n)
For ImageNet, we set the horizon to T 50,000, the target miscoverage level to a 0.15, and the discretization level to K = 200. For Airfoil, we set the horizon to 50,000, the target miscoverage level to = 0.1, and the discretization level to K = 20.
640
120
OcF-dadd
OCP Uniok
20-
3.0
33903
23000
33000
43000
39300
10000
20000
30000
45900
30000
(a) MC(+) (i.i.d))
(h) Ineff(t)) (i.i.d.)
120
12 MOACE
8.55
(209 leea
120
OCF Unbokn
230-
Time
Tine
(c) MC(() (Non-ii.d.)
(d) Ineff(t) (Non-i.id.)
Figure 5: Ablation study on ImageNet: Long-run miscoverage MC(() and inefficiency Ineff(t) as a function of time e [T'. under the i.i.d. (top) and non-i.i.d. (bottom) settings. The solid curves denote the average over 50 independent runs, and the shaded regions indicate the min range.
40

---

Published as a conference paper at ICLR 2026
0C3-bandh
0CF-REE OCF-Umtdck
20-
0.25
05
6.00
10660
20803
20003
43000
50000
10000
3r86e
9000
45000
59933
(a) MC( (i.id.)
(b) Ineff(t) (i..d.)
0CR Rande
OCP
27-
0..0
00-
10003
20022
20003
43000 20000
(c) MC(() (Covariate Shift)
(d) [ne (Covariate Shift)
Figure 6: Ablation study on Airfoil Self-Noise: Long-run miscoverage MC(t) and inefficiency [n) as a function of time t E [T], under the i..d. (top) and covariate shift (bottom) settings. The solid curve denotes the average over 50 independent runs, and the shaded region indicates the min- max range.
41

---

Published as a conference paper at ICLR 2026
K EXPERIMENT 5: SENSITIVITY OF OCP-UNLOCK+ TO
We study the sensitivity of OCP-Unl +ckk+ to the target miscoverage level a. For both ImageNet and Airfoil Self-Noise datasets, we use {0.1, 0.2, 0.3, 0.43.
For ImageNet, we set the horizon to T = 50,000 and the discretization level to K = 200. For Airfoil Self-Noise, we set the horizon T 50,000 and the discretization level K 200
0.35
0.35
0.25
0.20
0.20
0:15
0.30
0.0
0.05
alpha
(a) MC(T) (Lidd.)
(b) MC(T) (Non-i.dd.)
Figure 7: Sensitivity of OC? Unlock+ to ImageNet. Box plots summarize the long-run miscoverage MC(T) across 50 independent runs for a E (0.1,0.2, 0.3, 0.4] under the i.i. (left) and non-i.i.d. (right) settings. Each box shows the interquartile range with the median marked inside, while the whiskers indicate the spread the results.
0.40
0.00
0.30
0.30
0.25
0.25
0.15
0.10
0.05
0.05
0.1
(a) MC(T) (Lidd)
(b) MC(T) (Covariate Shift)
Figure 8: Sensitivity of OCP-CCCPO Unnonnn to a on Airfoil Self-Noise. Box plots summarize the long- run miscoverage MC(T) across 50 independent runs for {0.1, 0.2, 0.3, 0.4) under the i.i.d. (left) and covariate shift (right) settings. Each box shows the interquartile range with the median marked inside, while the whiskers indicate the spread of the results.
42

---

Published as a conference paper at ICLR 2026
L EXPERIMENT 6: EMPIRICAL ANALYSIS ON (TC(T)
We empirically analyze the additional term CMc( that appears the upper bound on the deviation of the miscoverage rate MC(T") from (Lemma) validate the efficacy of OCP-Unlocks Unlockt.
Following the same experimental setup as in Experiment 5 (Appendix term, averaged over 50 independent runs (Table & and Table
K). we report the CMc(T)
Table 8: CMc(T) on ImageNet for different choices of target miscoverage level a, under the i.i.d. and non-i.i.d settings
i.i.d.
Non-i.i.d.
T
o=0.1
o=0.2
o=0.3
o=0.4
a=0.1
a=0.2
a=0.3
a=0.4
50,000
0.062
0.161
0.304
0.469
0.091
0.186
0.318
0.476
60,000
0.050
0.149
0.299
0.461
0.079
0.178
0.312
0.466
70,000
0.040
0.139
0.295
0.453
0.071
0.170
0.307
0.459
Table 9: CMC (7) on Airfoil Self-Noise for different choices of target miscoverage level a, under the i..d. and non-i.i.d. settings
Non-i.i..
T
a=0.1
a=0.2
a=0.3
a=0.44
am#0.1
a=00.2
a=0.3
a=0.4
30,000
0.020
0.131
0.291
0.500
0.025
0.130
0.276
0.451
40,000
0.010
0.115
0.267
0.465
0.014
0.115
0.258
0.425
50,000
0.002
0.099
0.248
0.438
0.006
0.102
0.243
0.406
43


Reviews:
[{"review_id": "cqbplQelHq", "reviewer": "Reviewer_KKfP", "summary": "The paper proposes a new framework for online conformal prediction under partial and adversarial feedback, where the learner only observes limited information about prediction correctness.  Conformal prediction has been connected to adversarial bandit learning by framing conformal set selection as an arm-selection problem. They develop a conversion lemma linking regret bounds to miscoverage guarantees, allowing the use of existing bandit algorithms for online conformal prediction.", "questions": "- Should it be “minimize the miscoverage rate” in line 128 on page 3?\n\n- There are no comparisons with other recent partial-feedback uncertainty quantification frameworks.\n\n- Please discuss how sensitive the results are to the choice of $λ$ and the discretization level $K$.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- Establishes a clear connection between regret minimization and coverage guarantees in conformal prediction.\n\n- The introduction of the EXP3.P-CP-UNLOCK algorithm effectively adapts the classic EXP3.P framework to the unique structure of conformal prediction feedback.\n\n- Provides regret and miscoverage bounds with detailed proofs.", "weaknesses": "- The review of online conformal prediction is insufficient. Important recent works are missing, including:\n   - Angelopoulos et al. (2023), Conformal PID Control for Time Series Prediction;\n   - Angelopoulos et al. (2024), Online Conformal Prediction with Decaying Step Sizes;\n   - Gibbs & Candès (2024), Conformal Inference for Online Prediction with Arbitrary Distribution Shifts;\n   - Zhang et al. (2025), Online Differentially Private Conformal Prediction for Uncertainty Quantification.\n\n\n- As $m_t$ is an indicator function, the regret formulation may not distinguish between observing or not observing $y_t$, potentially causing information loss. Clarification on how the true label feedback is used is needed.\n\n- A formal theorem explicitly stating the miscoverage rate bound would make the theoretical results clearer.\n\n- Please clarify whether specific techniques are used to address non-i.i.d. or non-exchangeable data.\n\n- The differences from Ge et al. (2025) should be highlighted more clearly in terms of assumptions,method, and theoretical guarantees.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "dBe3ixjh70", "reviewer": "Reviewer_d5vm", "summary": "The paper explores how regret minimization techniques from bandit and sequential prediction literature can be adapted to online conformal prediction under partial feedback. It establishes a theoretical link by deriving an upper bound on the miscoverage rate in terms of the learner’s regret, enabling the use of these methods in this setting. Building on this, the paper demonstrates the application of the EXP3.P algorithm and introduces a novel variant, EXP3.P-CP with Unlocking, which exploits additional partial feedback and the monotonicity of prediction set construction. For both methods, the paper provides miscoverage guarantees and evaluates their empirical performance on regression and classification tasks.", "questions": "1. After Lemma 1, it says that “the corresponding miscoverage rate converges to a desired level $\\alpha$”. However, we do not really see that in the results of Figure 1. Why is that?\n2. How are the set of candidate thresholds chosen? How does that affect the results in both theoretical and practical terms? I imagine that the resolution of the threshold might affect the convergence of the regret, for example.\n3. The results focus on the absolute coverage gap, treating undercoverage and overcoverage equally. Would it be possible to extend the analysis to penalize undercoverage more heavily than overcoverage? Relatedly, EXP3.P-CP with Unlocking appears more conservative than EXP3.P-CP, leading to overcoverage in Figure 1. Is this behavior expected?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The partial feedback setting in online conformal prediction is highly relevant, offering practical value to both the conformal prediction research community and real-world practitioners.\n- The paper’s connection to regret minimization methods is particularly compelling, as it unlocks a rich toolbox of established techniques that can be effectively applied to conformal prediction. I am not an expert in this specific area of conformal prediction, and I am surprised this connection has not appeared in the literature before, but to the best of my knowledge, it is novel.\n- The paper is generally clear and well-structured, making it easy to follow. The proofs are also well detailed and, I believe, sound.", "weaknesses": "- The experiments are somewhat limited in the sense that the only baselines considered operate under a different setting. This makes it hard to evaluate the effectiveness of the proposed method. Are there no other conformal prediction methods designed for partial feedback, or at least methods that could be adapted to this setting?\n- The presentation could be improved as there are a few minor typographic errors and occasional non-idiomatic phrasing (see minor issues below).\n\n### Minor issues\n\n- Line 16: “with fewer data generation assumptions” instead of “with less data generation assumption”\n- Line 18: \"mature literature\" or \"established literature\" instead of “matured literatures”\n- Line 41:  I am not sure “enjoyable” is a good word choice in “enjoyable guarantee”. Maybe just “guarantee” would read better.\n- Line 126: “minimizes” should be “minimize”.\n- Line 133: The sentence “due to exploiting the achievement of adversarial bandits under an adaptive adversary” is not clear. What does the “achievement of adversarial bandits” mean?\n- Line 159: “which we leverage this algorithm as our baseline” does not read well. Probably better to add a full stop and then “We leverage this algorithm as our baseline”.\n- Line 208: “method” instead of “methods”.\n- Line 209: “to use” instead of “to using”.\n- Line 568: Missing reference.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "KTsVwxV4BQ", "reviewer": "Reviewer_7ZrS", "summary": "The paper tackles online conformal prediction with semi-bandit feedback and adaptive adversaries by reducing threshold selection to an adversarial bandit problem. It designs a loss that trades off deviation from a target miscoverage level with efficiency (tuned by λ) and proves a conversion from bandit regret to miscoverage guarantees. Implementations with EXP3.P and an “unlocking” variant that reuses feedback via monotonicity provide high-probability bounds, and experiments on classification and regression show accurate coverage tracking with compact prediction sets, including under covariate shift.", "questions": "1. In both experiments, the choice of the hyperparameter $\\lambda$ is not specified. How is $\\lambda$ selected, and how sensitive are the results to different values of $\\lambda$? The paper lacks discussion on this critical design choice.\n2. What is the performance of the proposed method under low feedback rates (i.e., when semi-bandit feedback is rarely triggered)? The current experiments do not analyze or discuss scenarios with sparse feedback.\n3. Could there exist a more direct threshold-updating mechanism (e.g., standard online quantile tracking or reinforcement learning methods) that also achieves adversarial miscoverage control? Why is the bandit framework preferred here, and what are its concrete advantages over such alternatives?\n4. In the abstract (line 025), the word \"micoverage\" should be corrected to \"miscoverage\".\n5. In line 127, the definition of “size” is unclear. Why is it claimed to be proportional to exp(-$\\pi$)? Please provide a reasonable justification or reference.\n6. In line 172 (Equation 3), the definition of $a_t(\\pi_t)$ appears, but later discussions refer to $a_t(\\pi)$. Are they the same quantity? A unified and explicit definition for $a_t(\\pi)$ is missing.\n7. In line 213 under EXP3.P-CP, the parameters $\\delta$and $K$ are used without prior introduction or definition. Please clarify their meanings.\n8. In line 225, what is the valid range of the probability distribution $p_t$? It would be helpful to explicitly state its domain or constraints.\n9. In Figure 1, the blue curve (MVP) is barely visible or unidentifiable. Please consider adjusting the visualization for clarity.\n10. In line 568, there is an unexplained symbol or placeholder \"(?)\", which appears to be a typo.\n11. On the final page of the appendix (Page 18), there are punctuation issues in one of the equations. A thorough proofreading of all punctuation throughout the paper is recommended.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The paper introduces an adversarial semi bandit formulation for online conformal prediction and reduces threshold selection to an adversarial bandit with a transparent bridge from regret control to miscoverage control, together with an unlocking mechanism that exploits monotonicity to reuse feedback. It offers high probability guarantees and a clear analysis pipeline from loss design to regret bounds to miscoverage guarantees, implemented with practical EXP3.P algorithms. Experiments on classification and regression show close tracking of target miscoverage with strong sample efficiency, consistent with the theory. The writing is clear, and the modular design lets other bandit learners plug in, increasing impact in retrieval, selective prediction, and human in the loop systems.", "weaknesses": "See details in Questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:

Decision: Accept (Poster)