# Online Conformal Prediction with Adversarial Semi-bandit Feedback via Regret Minimization

arXiv: https://arxiv.org/abs/2604.17984 · HTML: https://mlsanity.com/paper/2604.17984/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 30 references that are in the map.
- First posted on arXiv 20 Apr 2026.

## Builds on (most cited first, 20 of 20)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Conformal Prediction Under Covariate Shift](https://mlsanity.com/paper/1904.06019/) (2019)
- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Adaptive Conformal Inference Under Distribution Shift](https://mlsanity.com/paper/2106.00170/) (2021)
- [Language Models with Conformal Factuality Guarantees](https://mlsanity.com/paper/2402.10978/) (2024)
- [Conformal Inference for Online Prediction with Arbitrary Distribution Shifts](https://mlsanity.com/paper/2208.08401/) (2022)
- [Safe Planning in Dynamic Environments using Conformal Prediction](https://mlsanity.com/paper/2210.10254/) (2022)
- [Distribution-free uncertainty quantification for classification under label shift](https://mlsanity.com/paper/2103.03323/) (2021)
- [Large language model validity via enhanced conformal prediction methods](https://mlsanity.com/paper/2406.09714/) (2024)
- [Conformal PID Control for Time Series Prediction](https://mlsanity.com/paper/2307.16895/) (2023)
- [Improved Online Conformal Prediction via Strongly Adaptive Online Learning](https://mlsanity.com/paper/2302.07869/) (2023)
- [Practical Adversarial Multivalid Conformal Prediction](https://mlsanity.com/paper/2206.01067/) (2022)
- [Online conformal prediction with decaying step sizes](https://mlsanity.com/paper/2402.01139/) (2024)
- [PAC Prediction Sets Under Covariate Shift](https://mlsanity.com/paper/2106.09848/) (2021)
- [Conformal Prediction with Temporal Quantile Adjustments](https://mlsanity.com/paper/2205.09940/) (2022)
- [PAC Prediction Sets Under Label Shift](https://mlsanity.com/paper/2310.12964/) (2023)
- [Selective Generation for Controllable Language Models](https://mlsanity.com/paper/2307.09254/) (2023)
- [Semiparametric conformal prediction](https://mlsanity.com/paper/2411.02114/) (2024)
- [Stochastic Online Conformal Prediction with Semi-Bandit Feedback](https://mlsanity.com/paper/2405.13268/) (2024)
- [Efficient Online Set-valued Classification with Bandit Feedback](https://mlsanity.com/paper/2405.04393/) (2024)

## Built on by (most cited first, 4 of 4)

- [Online Conformal Prediction Beyond Feedback](https://mlsanity.com/paper/2608.07139/) (2026)
- [Efficient Online Conformal Selection with Limited Feedback](https://mlsanity.com/paper/2605.14953/) (2026)
- [Online Conformal Prediction for Non-Exchangeable Panel Data](https://mlsanity.com/paper/2605.17705/) (2026)
- [Counterfactual Online Conformal Prediction Under Adaptive Logging](https://mlsanity.com/paper/2609.30811/) (2026)

## Abstract (arXiv)

Uncertainty quantification is crucial in safety-critical systems, where decisions must be made under uncertainty. In particular, we consider the problem of online uncertainty quantification, where data points arrive sequentially. Online conformal prediction is a principled online uncertainty quantification method that dynamically constructs a prediction set at each time step. While existing methods for online conformal prediction provide long-run coverage guarantees without any distributional assumptions, they typically assume a full feedback setting in which the true label is always observed. In this paper, we propose a novel learning method for online conformal prediction with partial feedback from an adaptive adversary-a more challenging setup where the true label is revealed only when it lies inside the constructed prediction set. Specifically, we formulate online conformal prediction as an adversarial bandit problem by treating each candidate prediction set as an arm. Building on an existing algorithm for adversarial bandits, our method achieves a long-run coverage guarantee by explicitly establishing its connection to the regret of the learner. Finally, we empirically demonstrate the effectiveness of our method in both independent and identically distributed (i.i.d.) and non-i.i.d. settings, showing that it successfully controls the miscoverage rate while maintaining a reasonable size of the prediction set.