Stochastic Online Conformal Prediction with Semi-Bandit Feedback

I am surprised that questions are not answered from the authors.

Thank you for the thoughtful comments. We address your concerns below:

• Convergence Rate:
  There is no fundamental way to accelerate the convergence rate, as it is determined by the DKW inequality, which is tight in general. If smaller prediction sets are preferred, one can always select a lower coverage probability $\alpha$. We run our algorithm on ImageNet for 200K steps and present the results in the following table:

Thank you for the thoughtful comments. We address your concerns below:

• Assumptions:
  Both Assumption 2.1 and 2.2 are standard in regret analyses within the bandit literature (e.g., [1] and [2]).

  Next, we can remove Assumption 2.3 with some extra work. First, we redefine $\tau^*$ as:

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

  Furthermore, define $\alpha' = G^*(\tau^*)$. Now, the proof proceeds almost the same as before with $\alpha'$ substituted as $\alpha$. The only issue is that $\tau_t$ is computed using $\alpha$. However, because the DKW inequality applies to arbitrary CDFs, we can still show that $\tau_t \leq \tau^*$ with probability at least $1/T^2$. As a consequence, we can show 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 goes through as before. We are happy to update our paper with this relaxation.

  [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).

• Theoretical Contributions:
  Our main theoretical contribution is to formalize and solve the stochastic online conformal prediction problem with semi-bandit feedback. To the best of our knowledge, our strategy for handling the truncated CDF is novel.

• Presentation of the Paper:
  We appreciate the reviewer's suggestion. Due to space constraints, most of the theoretical results have been deferred to the appendix. However, we will improve the organization of the paper in the next draft.

Response to Reviewer 2:

Thank you for the thoughtful comments. We address the listed concerns below:

• Regret, Coverage Rate, and Prediction Set Size:
  Our regret guarantee ensures that our algorithm achieves the desired coverage rate and that its prediction set size converges to the size of the optimal prediction set. As explained in Section 3, we can recover the optimal prediction set by choosing $\tau_t = \tau^*$ for any $t$ if the true distribution $G^*$ is known. Since $G^*$ is unknown, we estimate it using our DKW inequality upper bound $\overline{G}_t$ and select its $1-\alpha$ cutoff as $\tau_t$. Note that we achieve sub-linear regret if and only if our estimates $\tau_t$ converge in probability to $\tau^*$. Consequently, we guarantee learning the optimal prediction set over time.

• Extension to Non-i.i.d. Settings:
  Extensions to the (adversarial) online learning setting are challenging due to the lack of an extension of the DKW inequality to this setting. For instance, learning thresholds is a closely related problem to ours, and the Littlestone dimension of thresholds is infinite (finite Littlestone dimension is a standard way to provide bounds in the online learning setting). Significantly different techniques would be needed, which we leave to future work.

• Interpretation of the Loss Function:
  The function $\phi$ represents the loss incurred when selecting a particular cutoff $\tau$. The bounded reward assumption in Assumption 2.2 typically holds in practice. For example, if $\phi$ corresponds to the prediction set size, the assumption holds because prediction set sizes are generally bounded. Alternatively, if $\phi$ measures the error of $\tau$ relative to $\tau^*$, then $\tau$ lies within a bounded range determined by the smallest possible score $f(x,y^*)$ (which is typically $\geq 0$ if $f(x,y^*)$ represents a probability).

I would like to thank the authors for the detailed responses. They help me better understand your paper. However, as also pointed out by other reviewers, the writing quality, including the experimental part, can be improved. Hence, I tend to not raise my rating.

Thank you for the thoughtful comments. We address the listed concerns below:

• Source of Randomness:
  Note that $\mathbb{P}_{(x,y^*)\sim D}(y^* \in C_Z(x)) \geq \alpha$ indicates that for any i.i.d. point sampled from $D$, the prediction set constructed using the cutoff $Z$ contains the ground-truth label with probability at least $\alpha$. The randomness originates from the test point sampling distribution, not from the choice of the cutoff $Z$. A second layer of randomness comes from the cutoff $Z$ itself, which is a random variable derived from the calibration dataset.

• Assumptions 2.2 and 2.3:
  The bounded reward assumption in Assumption 2.2 typically holds in practice. For example, if $\phi$ represents the prediction set size, this assumption holds because prediction set sizes are generally bounded. Alternatively, if $\phi$ measures the error of $\tau$ compared to $\tau^*$, then $\tau$ lies within a bounded range depending on the smallest possible score $f(x,y^*)$ (which is typically $\geq 0$ if $f(x,y^*)$ represents a probability).

  Next, we can remove Assumption 2.3 with some extra work. First, we redefine $\tau^*$ as:

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

  Furthermore, define $\alpha' = G^*(\tau^*)$. Now, the proof proceeds almost the same as before with $\alpha'$ substituted as $\alpha$. The only issue is that $\tau_t$ is computed using $\alpha$. However, because the DKW inequality applies to arbitrary CDFs, we can still show that $\tau_t \leq \tau^*$ with probability at least $1/T^2$. As a consequence, we can show 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 goes through as before. We are happy to update our paper with this relaxation.

• Active Learning and Coverage Rate:
  On average, the size of our coverage set decreases over time because the chosen cutoff $\tau_t$ increases with the number of observed samples. In our framework, one can always select a lower coverage threshold $\alpha$ if annotation cost is a primary concern. However, explicitly incorporating a constraint on prediction set size would be an interesting direction for future work.

• PAC Bound and Our Results:
  As we briefly mentioned in the introduction, our theoretical guarantee is stronger than the marginal guarantee typically seen in the conformal prediction literature. Specifically, our algorithm ensures the $\alpha$ coverage guarantee for every $t$ with probability at least $1 - \delta$ over the entire horizon. In contrast, the marginal guarantee only maintains $\alpha$ coverage on average over the horizon. This means that algorithms relying solely on marginal guarantees may fail to maintain coverage for an arbitrary number of steps.

• Convergence of $\tau_t$:
  Our convergence guarantee is based on the empirical CDF converging to the true CDF (i.e., $\overline{G}_t$ converges to $G^*$ in probability).

• Modification of ACI:
  We believe there is no straightforward way to modify ACI to achieve our results. Furthermore, even in scenarios favorable to ACI, it can only provide a marginal guarantee, which is weaker than our guarantee, which is comparable to PAC.

• Coverage Rate of ACI:
  We believe the reason ACI's coverage rate initially increases and then decreases is that its estimate of the underlying CDF becomes increasingly biased over time due to the semi-bandit feedback. Conducting gradient descent in the quantile space is insufficient to correct this bias.