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.