Research map / Bandits and online learning / Online convex optimization and games
Stochastic Online Conformal Prediction with Semi-Bandit Feedback
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes SPS, an online conformal prediction algorithm that uses a DKW-based upper confidence bound on a truncated empirical CDF to set prediction-set thresholds from semi-bandit feedback, with sublinear regret and high-probability conservative coverage.
Problem
Online conformal prediction where the true label is only observed when it falls inside the prediction set (semi-bandit feedback), so calibration must be done on-the-fly without full labels.
Approach
Replace unobserved scores below the current threshold with the threshold itself, estimate a truncated empirical CDF, take a DKW upper confidence bound to choose a conservative threshold that stays below the optimal tau*, and enforce monotone thresholds; this yields O~(sqrt T) regret and never undercovers with high probability.
Key results
- SPS achieves the lowest cumulative regret across all three tasks, with regret bound R_T <= K(2 log T + 4 sqrt(T log T) + 1) + 4 phi_max.
- With alpha=0.9 and T=10000, DLR and SPS both achieve the desired coverage, while SPS converges faster; greedy and ACI undercover.
- SPS never undercovers (tau_t stays below tau*), whereas ACI oscillates above and below tau* producing high undercoverage counts.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SPS instead of greedy | Online conformal prediction · ImageNet | cumulative regret | Helped |
| Use SPS instead of ACI | Online conformal prediction · ImageNet | coverage rate | Helped |
| Use SPS instead of greedy | Online conformal prediction · SQuAD document retrieval | cumulative regret | Helped |
| Use SPS instead of ACI | Online conformal prediction · SQuAD document retrieval | coverage rate | Helped |
| Use SPS instead of DLR | Online conformal prediction · SQuAD document retrieval | convergence speed | Helped |
| Use SPS instead of greedy | Online conformal prediction · Second-price auctions | cumulative regret | Helped |
| Use SPS instead of ACI | Online conformal prediction · Second-price auctions | coverage rate | Helped |
| Use SPS instead of DLR | Online conformal prediction · Second-price auctions | convergence speed | Helped |
| Use greedy instead of SPS | Online conformal prediction · ImageNet, SQuAD document retrieval, and second-price auctions | coverage rate | Hurt |
| Update the ACI quantile function only when the label is observed | ACI · ImageNet, SQuAD document retrieval, and second-price auctions | coverage rate | Hurt |
| Use DLR instead of SPS | Online conformal prediction · ImageNet, SQuAD document retrieval, and second-price auctions | convergence speed | Hurt |
| Use ETC instead of an adaptive threshold | Online conformal prediction · Additional experiments | coverage rate | Hurt |
Surprising findings
- ACI, when its quantile function is updated only on observed labels, fails to achieve the desired coverage due to biased updates.
- Using logits instead of softmax probabilities as the score significantly degrades DLR performance.
Limitations
- Regret analysis relies on assumptions: loss is Lipschitz in the CDF and the optimal threshold has exact coverage G*(tau*)=1-alpha.
- Prediction set size itself is not directly used as the loss; the regret loss is a coverage-deviation surrogate.
- Guarantees are for i.i.d. data; no explicit coverage convergence bound is provided.
Experimental setup
Datasets: ImageNet (16x16 downsampled) SQuAD (DPR-processed retrieval version) eBay auction bids (synthetic simulation)
Benchmarks: ImageNet SQuAD (DPR retrieval) second-price auction simulation
Metrics: cumulative regret coverage rate undercoverage count
Baselines: greedy ACI DLR ETC Con-ETC
Builds on: Adaptive Conformal Inference (ACI) Dvoretzky-Kiefer-Wolfowitz inequality Decaying learning rate online conformal prediction
Closest papers by meaning
- Efficient Online Set-valued Classification with Bandit Feedback (ICML 2024 · similarity 0.91)
- Exploring the Noise Robustness of Online Conformal Prediction (NeurIPS 2025 · similarity 0.90)
- Online Conformal Prediction via Online Optimization (ICML 2025 · similarity 0.89)
- Adaptive Conformal Inference by Betting (ICML 2024 · similarity 0.88)
- Multi-model Ensemble Conformal Prediction in Dynamic Environments (NeurIPS 2024 · similarity 0.88)
- An Information Theoretic Perspective on Conformal Prediction (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.