Online Conformal Prediction Quantifies Uncertainty Without Direct Feedback.

Uncertainty quantification is crucial for deploying machine learning models in safety-critical domains. Online Conformal Prediction (OCP) offers a theoretically sound way to provide prediction sets that guarantee a user-specified frequency of containing the true label, even with non-i.i.d. data. Traditionally, OCP relies on feedback from previously deployed predictions to update these sets. This research introduces a novel OCP setting, "beyond feedback," where the learner can either output a prediction set or query the correct label, but never both for the same instance. This means deployed predictions are never directly evaluated. The problem is reframed as a partial monitoring game where prediction actions yield no observation, and a separate query action reveals the label. To solve this, the OCP with Queries (OCPQ) method is developed, adapting an existing label-efficient forecaster. OCPQ achieves an expected regret of O(T^(2/3)) and expected coverage of at least beta - O(T^(-1/3)) over a data stream of length T, while querying only an expected T^(-1/3) fraction of rounds. This provides robust uncertainty quantification comparable to bandit-based OCP methods but without needing feedback on deployed predictions, as demonstrated by experiments on real-world datasets.