Stochastic Online Conformal Prediction with Semi-Bandit Feedback

We thank the reviewer for the thoughtful comments. We address the questions and major concerns below:

Concern 1: Line 285-287 Proof

We apologize for the confusion. We will fix the typo in the revised draft. We also note that the final regret bound is correct because we add the additional $\epsilon_t$ in line 290.

Concern 2: Reference Plot

We thank the reviewer for the helpful advice. We updated Figure 1 to add $f(T) = \sqrt{T \log T}$ as a reference. We also take the log of the y-axis to improve readability. The figure is uploaded here:
https://imgur.com/a/j05QwzS

Concern 3: Natural Metric

It is correct that $\tau$ serves as a surrogate for prediction set size, as the prediction set size is monotonic in $\tau$. In practice, we find that this surrogate performs reasonably well, and we use a variant of it in our experiments. The reason we do not directly use prediction set size is explained in lines 148–150 (right column): specifically, because prediction set size is a discontinuous function, it does not satisfy Assumption 2.1. We have also conducted experiments on the convergence behavior of the prediction set size and would be happy to share the results.

Alternatively, a guarantee that existing conformal prediction algorithms provide is that the coverage rate is also not too much higher than desired, which shows that the algorithm is not overly conservative. Indeed, our regret guarantee can be applied to obtain such a bound. Specifically, consider the loss function $\phi(\tau) = 1-\min\\{G^*(\tau),G^*(\tau^*)\\}$ (the min is to ensure the step-wise regret is non-negative). On the event that $\tau_t\le\tau^*$ for all $t$ (which holds with high probability, see Lemma 4.2), then $\min\\{G^*(\tau_t),G^*(\tau^*)\\}=G^*(\tau_t)$, so the step-wise regret is
$r_t := \phi(\tau_t) - \phi(\tau^*) = G^*(\tau^*) - G^*(\tau_t) = \mathbb{P}[\tau_t\le f(x_t,y_t^*)\le\tau^*].$

In other words, the step-wise regret $r_t$ equals the overcoverage probability -- i.e., the probability that our algorithm covers $y_t^*$ when the "oracle" algorithm (which knows $\tau^*$) does not. Then, by Theorem 3.1, we have $r_t = \mathbb{P}[\tau_t\le f(x_t,y_t^*)\le\tau^*] = O(\sqrt{\log t/t})$, implying that the overcoverage probability converges to zero. We are happy to add a discussion of this result to our paper.

Question 1: $\epsilon_t$ in Lemma 4.2

It is correct that $\epsilon_t$ is defined in Equation (4). We will include this definition in the statement of the lemma in the revised draft to avoid any ambiguity.

Question 2: Theorem 3.1 Stated Twice

We apologize for the confusion. We re-stated the theorem in the proof section to improve its readability. We are happy to remove it.

Question 3: $\delta$ in Lemma 4.1

We define $\delta = 1/T^2$ in line 199-200 (right column). We will include this definition in the revised proof to avoid future confusion.

Question 4: Assumption 2.1

We meant natural in the sense that it naturally captures relevant structure in our problem, not necessarily that it is a natural assumption. Specifically, this assumption is a natural way to avoid the pathological cases discussed in lines 143–150. To summarize, consider a CDF such that $G^*(\tau_0) = G^*(\tau^*) = 1 - \alpha$ with $\tau_0 < \tau^*$. Recall that $\tau^* = \sup\\{\tau \in R: G^*(\tau) \le 1 - \alpha\\}$. Since we almost surely never observe any scores between $\tau_0$ and $\tau^*$, it becomes extremely difficult to identify $\tau^*$ from $[\tau_0,\tau^*]$ with a finite sample. Even a small error in estimating the empirical CDF---e.g., $G_t(\tau^*) = G^*(\tau^*) + \epsilon$---can result in significant regret. We apologize for the confusion, and will clarify our explanation of this assumption.

We thank the reviewer for the thoughtful comments. We address the questions and major concerns below:

Concern 1: Lemma 4.2

We apologize for the confusion. A more detailed proof is included below:

Base case: when $t = 1$, we set $\tau_1 = -\infty$. Thus, $\tau_1 \le \tau^*$.

Inductive Hypothesis: Assume $\tau_k \le \tau^*$ for some $k \ge 1$.

We prove $\tau_{k+1} \le \tau^*$ under our assumption $\sup_{\tau \in R}|G_t(\tau) - G_t^*(\tau)| \le \epsilon_t$ for all $t \in [T]$. Note that $\tau_k \le \tau^*$ by the inductive hypothesis, so we have $G_k^*(\tau) = G^*(\tau)$ for all $\tau \ge \tau^*$. Thus, we have

$$|G_k(\tau^*) - G^*(\tau^*)| = |G_k(\tau^*) - G_k^*(\tau^*)| \le \sup_{\tau \in R}|G_k(\tau) - G_k^*(\tau)| \le \epsilon_k,$$

where the last inequality follows from our assumption.

Thus, we have $\overline{G}_k(\tau^*) = G_k(\tau^*) + \epsilon_k \ge G^*(\tau^*) = 1 - \alpha$. Recall we define

$$\tau_{1-\alpha, k} = \sup\\{\tau \in R \mid \overline{G}_k(\tau) \le 1 - \alpha\\};$$

thus, we have $\tau_{1-\alpha, k} \le \tau^*$. Since $\tau_{k+1} = \max\\{\tau_{1-\alpha, k}, \tau_k\\}$ with $\tau_{1-\alpha, k} \le \tau^*$ and $\tau_k \le \tau^*$, we have $\tau_{k+1} \le \tau^*$.

We are happy to further elaborate on any portion of the proof.

We thank the reviewer for the thoughtful comments. We address the questions and major concerns below:

Concern 1: Additional Comparative Analysis

We appreciate the reviewer’s suggestion. In both our discussions and experiments, we have considered a comprehensive set of popular online conformal prediction algorithms from recent literature that operate in similar contexts, and we demonstrate that our algorithm outperforms them in the semi-bandit setting. We believe these scenarios already demonstrate challenging and practical applications of our techniques, but we are happy to consider additional scenarios the reviewer might have in mind.

Concern 2: Key Assumptions

Assumption 2.1 rules out cases where the reward varies substantially in regions where the CDF $G^*$ is very flat. In such regions, the number of observed samples is typically small. Therefore, if $\tau^*$ lies in a flat region of $G^*$ and the reward fluctuates significantly, the accrued regret can be large. This type of regularity condition is common in regret analyses within the bandit literature, where some assumptions on the reward mechanism are required to ensure meaningful guarantees (e.g., see [1]).

The bounded reward assumption in Assumption 2.2 typically holds in practice. First, since the CDF $G^*$ is a bounded function, it is natural to assume that the reward $\phi(\tau) = \psi(G^*(\tau))$ is also bounded. Alternatively, if we consider $\phi$ as representing the prediction set size, the assumption still holds because prediction set sizes are inherently bounded. The bounded reward condition is also standard in regret analyses (e.g., see [2]).

Next, we show that Assumption 2.3 can be removed with some additional technical work. We begin by redefining $\tau^*$ as $\tau^* = \sup\\{\tau: G^*(\tau) \le 1 - \alpha\\}$, and let $1 - \alpha' = G^*(\tau^*)$. The proof then proceeds almost identically as before, with $1 - \alpha'$ substituted for $1 - \alpha$. The only complication is that $\tau_t$ is still computed using $\alpha$. However, since the DKW inequality applies to arbitrary CDFs, we can still show that $\tau_t \le \tau^*$ with probability at least $1/T^2$. As a result, we obtain that $G(\tau_t) \to 1 - \alpha'$, i.e., our algorithm maintains and converges to an $\alpha'$-coverage rate. With these modifications, our regret guarantee continues to hold.

In the experiments section, we choose a loss function (lines 374–377, right column) that satisfies Assumptions 2.1 and 2.2. Since relaxing Assumption 2.3 does not impact our regret or coverage guarantees, we use the observed empirical distribution of scores as the ground-truth distribution.

[1] Kleinberg, Robert, Aleksandrs Slivkins, and Eli Upfal. "Multi-armed bandits in metric spaces." In Proceedings of the fortieth annual ACM symposium on Theory of computing, pp. 681-690. 2008.
[2] Auer, P. "Finite-time Analysis of the Multiarmed Bandit Problem." (2002).

Concern 3: Limitations

One limitation of our algorithm is that it currently operates under the i.i.d. assumption, whereas several existing online conformal prediction approaches are designed to work in adversarial setting; however, these existing techniques cannot handle semi-bandit feedback. With respect to different feedback mechanisms, our algorithm also functions in the full-information feedback setting without modification; however, in this case, there may be more effective strategies than our algorithm. Finally, one might also consider bandit (instead of semi-bandit) feedback, but it is not clear what that would look like in the conformal prediction setting. We are happy to add a discussion to our paper.

Question 1: Noisy and Sparse Labels

In general, conformal prediction naturally handles label noise, since the ground truth label $y^*$ is assumed to be a random variable even conditioned on $x$. In terms of "extreme cases", our coverage and regret guarantees still hold but the prediction sets may be large. Regarding sparsity, we note our conformal prediction setting is special, and our semi-bandit feedback cannot be sparse -- we only fail to observe the true label when it is miscovered, which happens with probability at least $\alpha$. We are happy to add a discussion to our paper.

Question 2: Computation Efficiency

As our algorithm only needs access to the empirical score distributions, the computational efficiency does not depend on the choice of the coverage rate $\alpha$. For the same reason, the scaling of our algorithm does not depend on the data dimensionality except through how long it takes to evaluate the predictive model. Since it is an online algorithm, its computation time scales linearly in the size of the dataset (with constant compute per iteration) and uses constant memory. These scalability properties are similar to existing conformal prediction algorithms. We are happy to add a discussion to our paper.

Thank you for the thoughtful comments; we address major concerns below.

Concern 1: Comparison to [1]

By our understanding, the algorithm in [1] cannot be straightforwardly modified to handle semi-bandit feedback. Specifically, they use a strangeness measure $A_t:(z_1,...,z_t)\mapsto(\alpha_1,...,\alpha_t)$ (Eq (8) in [1]) to construct prediction sets, where $z_i=(x_i,y_i)$ is a calibration example; e.g.: $\alpha_i=\frac{\min_{j\neq i:y_j=y_i}d(x_i,x_j)}{\min_{j\neq i:y_j\neq y_i}d(x_i, x_j)}.$

Clearly, computing $\alpha_i$ requires the true label $y_i$. Next, given a new input $x_t$, they return the prediction set of all labels $y$ such that $\alpha$ satisfies
\frac{\\#\\{i=1,...,t:\alpha_i\ge\alpha\\}}{t} \ge\delta, where
$(\alpha_1,...,\alpha_{t-1},\alpha)=A_t((x_1,y_1),...,(x_{t-1},y_{t-1}),(x_t,y))$
is the strangeness measure assuming the true label for $x_t$ is $y$ (Eqs (9) to (11) in [1]). Thus, to construct $\alpha$, they require $\alpha_i$ for all $i$, so all true labels $y_i$ are required. This requirement persists in their modifications (Eqs (16), (20)–(21) in [1]).

Our main contribution is precisely to handle semi-bandit feedback. We will add a discussion.

Concern 2: i.i.d.

We believe the i.i.d. assumption is reasonable in our active learning setting. We agree that extending our work to the adversarial setting is an important direction, but it is beyond the scope of our paper.

Concern 3: Re-learn $f$

We believe there are practical settings where training is decoupled from calibration, especially when training is costly (e.g., LLMs). One of our applications involves using a pretrained document retriever in a new domain where fine-tuning may be infeasible. However, we agree that extending to settings where the model $f$ is updated is important and will add a discussion.

Concern 4: Simple use of DKW

As discussed above, we do not believe [1] can easily be adapted to semi-bandit feedback. Also, we emphasize that a naïve application of DKW is insufficient; we have introduced additional novel techniques to handle semi-bandit feedback.

Concern 5: Image Readability

We have updated Figure 1 to use a log scale:
https://imgur.com/a/j05QwzS

Q3: Line 213 $\tau_t$ convergence

Our convergence guarantee is based on the fact that the empirical CDF converges to the true CDF, i.e., $\overline{G}_t$ converges to $G^*$ for $\tau\in[\tau^*,+\infty)$. For intuition, consider full feedback. Let $G'_t$ denote the empirical CDF. Similar to Eq (4), define
$\overline{G}'_t(\tau)=G'_t(\tau)+\epsilon_t$

where $\epsilon_t=\sqrt{\log(2/\delta)/2t}$, and choose
$\tau_t=\sup\\{\tau\in\mathbb{R}\mid\overline{G}'_{t-1}(\tau)\le1-\alpha\\}.$
By DKW, $\overline{G}'_t(\tau^*)$ converges to $G^*(\tau^*)$, so $\tau_t$ converges to $\tau^*$. The convergence rate $O(t^{-1/2})$ comes from DKW.

With semi-bandit feedback, convergence is not guaranteed a priori. However, Lemmas 4.1 and 4.2 show our CDF upper bound $\overline{G}_t(\tau^*)$ still converges to $G^*(\tau^*)$. Thus, $\tau_t$ converges to $\tau^*$, with the same convergence rate.

Q4: FCP

Apologies, we are not sure what "FCP" means. The false negative rate (FNR) is controlled by the coverage guarantee (assuming a false negative is a miscovered example). We are not aware of an analog of false positive rate (FPR) in conformal prediction. One guarantee of existing conformal prediction algorithms is the coverage rate is also not too much higher than desired, i.e., they are not overly conservative. Our regret guarantee provides such a bound. Consider the loss $\phi(\tau)=1-\min\\{G^*(\tau),G^*(\tau^*)\\}$ (the min ensures the step-wise regret is non-negative). On the event $\tau_t\le\tau^*$ for all $t$ (which holds with high probability by Lemma 4.2), the step-wise regret is
$r_t=\phi(\tau_t)-\phi(\tau^*)=G^*(\tau^*)-G^*(\tau_t)=\mathbb{P}[\tau_t\le f(x_t,y_t^*)\le\tau^*],$
i.e., $r_t$ is the overcoverage probability that we cover $y_t^*$ but the oracle does not. By Theorem 3.1, $r_t=O(\sqrt{\log t/t})$, so the overcoverage probability converges to zero. We will add a discussion.

Q5: Example on $\phi$

Note that Algorithm 1 does not depend on $\phi$; it is introduced solely to evaluate the algorithm's performance. The example in our experiments is a practical choice; the overcoverage rate above is another.

Q6: Conservativeness

This is a consequence of our PAC guarantee and semi-bandit. Our algorithm ensures $\alpha$-coverage at every $t$, which implies $\tau_t\le\tau^*$ for all $t$. However, as shown in our regret analysis, $\tau_t$ is guaranteed to converge to $\tau^*$, with convergence rate given by DKW.

Q7: Dynamic Regret

Since we consider the i.i.d. setting, the optimal policy is static (i.e., $\tau_t=\tau^*$), so our regret equals dynamic regret. We believe extensions to the adversarial setting (where static and dynamic regret are distinct) is beyond the scope of our paper.