# Efficient Online Conformal Selection with Limited Feedback

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 22 of its 38 references that are in the map.
- First posted on arXiv 14 May 2026.

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

- [A Gentle Introduction to Conformal Prediction and Distribution-Free Uncertainty Quantification](https://mlsanity.com/paper/2107.07511/) (2021)
- [Conformal Prediction Under Covariate Shift](https://mlsanity.com/paper/1904.06019/) (2019)
- [Adaptive Conformal Inference Under Distribution Shift](https://mlsanity.com/paper/2106.00170/) (2021)
- [Conformal prediction beyond exchangeability](https://mlsanity.com/paper/2202.13415/) (2022)
- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [Provably Efficient Safe Exploration via Primal-Dual Policy Optimization](https://mlsanity.com/paper/2003.00534/) (2020)
- [Conformal PID Control for Time Series Prediction](https://mlsanity.com/paper/2307.16895/) (2023)
- [Bandits with concave rewards and convex knapsacks](https://mlsanity.com/paper/1402.5758/) (2014)
- [Adversarial Bandits with Knapsacks](https://mlsanity.com/paper/1811.11881/) (2018)
- [Online conformal prediction with decaying step sizes](https://mlsanity.com/paper/2402.01139/) (2024)
- [Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneously](https://mlsanity.com/paper/1901.08779/) (2019)
- [Online Multivalid Learning: Means, Moments, and Prediction Intervals](https://mlsanity.com/paper/2101.01739/) (2021)
- [Achieving Risk Control in Online Learning Settings](https://mlsanity.com/paper/2205.09095/) (2022)
- [Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regression](https://mlsanity.com/paper/2211.07484/) (2022)
- [Gradient Equilibrium in Online Learning: Theory and Applications](https://mlsanity.com/paper/2501.08330/) (2025)
- [The Relationship between No-Regret Learning and Online Conformal Prediction](https://mlsanity.com/paper/2502.10947/) (2025)
- [Volume Optimality in Conformal Prediction with Structured Prediction Sets](https://mlsanity.com/paper/2502.16658/) (2025)
- [Stochastic Online Conformal Prediction with Semi-Bandit Feedback](https://mlsanity.com/paper/2405.13268/) (2024)
- [Online Conformal Prediction with Efficiency Guarantees](https://mlsanity.com/paper/2507.02496/) (2025)
- [A Lyapunov-Based Methodology for Constrained Optimization with Bandit Feedback](https://mlsanity.com/paper/2106.05165/) (2021)
- [Online Conformal Prediction with Adversarial Semi-bandit Feedback via Regret Minimization](https://mlsanity.com/paper/2604.17984/) (2026)
- [Efficient Online Set-valued Classification with Bandit Feedback](https://mlsanity.com/paper/2405.04393/) (2024)

## Abstract (arXiv)

We address the problem of conformal selection, where an agent must select a low-cost subset of options to ensure that at least one "success" is identified at a pre-specified target rate φ. While traditional online conformal prediction focuses on maintaining validity for the observed sequence, minimizing the resource cost (efficiency) of such selections, especially under limited feedback, remains a significant challenge. In this work, we consider highly restricted "bandit" feedback, where the agent only observes feedback about the subset it selected, and not the true label, point, or outcomes of unchosen options. We demonstrate that the simple Adaptive Conformal Inference (ACI) update rule, when applied to the appropriate control parameter or dual variable and paired with explicit boundary actions, is both adversarially valid, ensuring the success target is met on average for any input sequence (and hence under distribution shifts), and stochastically efficient, achieving sublinear efficiency regret for i.i.d. inputs against an optimal stochastic benchmark. The key algorithmic idea is to avoid the projected updates standard in constrained bandits: projections break the exact telescoping identity behind ACI validity, whereas boundary actions stabilize the unprojected update through actual decisions. We show these guarantees under canonical models capturing bandit feedback via a unified algorithmic technique and Lyapunov-based analysis. Our approach handles more general settings than prior work, while requiring significantly less feedback, and provides a new theoretical bridge between efficient online learning with limited feedback and distribution-free uncertainty quantification.