Online Conformal Prediction Beyond Feedback

Abstract

Online conformal prediction (OCP) provides theoretically principled uncertainty quantification for arbitrary black-box classifiers and non-i.i.d. data streams by constructing prediction sets that are guaranteed to contain the true label at a user-specified frequency. OCP usually updates prediction sets using feedback from previously deployed predictions. We instead study an OCP setting *beyond feedback*: on each round, the learner can *either* output a prediction set *or* query the correct label, but not both. Thus, no deployed prediction is ever evaluated directly. We reduce this problem to a partial monitoring game in which prediction actions return no observation and a separate query action reveals the label. To solve this game, we develop *OCP with queries* (OCPQ), a label-efficient forecasting algorithm designed for this beyond-feedback setting. Using an adequate reward construction, for any black-box classifier and any (non-i.i.d.) oblivious data stream of length $T$, OCPQ has $O(T^{2/3})$ expected regret and expected coverage of at least $\beta -O(T^{-1/3})$ for a user-defined $\beta$, while querying only an expected $T^{-1/3}$ fraction of rounds. This provides coverage comparable to bandit-based OCP methods while requiring no feedback from deployed predictions. Experiments on real-world datasets demonstrate the effectiveness of our approach.