Research map / Bandits and online learning / Online convex optimization and games
Efficient Online Set-valued Classification with 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 Bandit Class-specific Conformal Prediction (BCCP), which uses an unbiased indicator estimator from single-arm bandit feedback to train a ResNet50 and update class-wise conformal quantiles via SGD, with an expert ensemble over learning rates.
Problem
Conformal prediction needs fully labeled data for training and calibration, but in online bandit feedback a learner only learns whether the pulled class is correct, not the true label, and calibration data shrinks to correct-arm instances.
Approach
Replace the unobserved indicator 1{Y_t=k} with an inverse-propensity estimator Delta_{t,k}=1{A_t=k}/pi_t(k|X_t)*1{A_t=Y_t}, which is unbiased, and use it both in a weighted cross-entropy training loss and in SGD updates of class-specific quantiles under the check loss; an expert ensemble over several learning rates removes manual tuning of the quantile learning rate.
Key results
- Under the bandit setting, class-specific accumulative coverage converges toward the 95% target (alpha=0.05) across three datasets, three scores (softmax, APS, RAPS) and softmax and uniform policies.
- Theory: class-specific coverage gap and check-loss regret both shown to be O(T^{-1/2}) under bounded-policy and learning-rate conditions.
- Expert ensemble over learning rates [0.1, 0.01, 0.001, 0.0001] yields prediction set sizes only marginally larger than a carefully tuned single learning rate with softmax policy, and smaller sets with the uniform policy on CIFAR10 and SVHN.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use BCCP for online set-valued classification with bandit feedback | BCCP · CIFAR10, CIFAR100, and SVHN | class-specific coverage: 95% | Helped |
| Use the softmax policy instead of the uniform policy | BCCP model training · CIFAR10, CIFAR100, and SVHN | cross-entropy loss reduction speed | Helped |
| Use the uniform policy instead of the softmax policy | BCCP set-valued classification · CIFAR10, CIFAR100, and SVHN | prediction set size | Helped |
| Use the uniform policy instead of the softmax policy | BCCP set-valued classification · CIFAR10, CIFAR100, and SVHN | coverage convergence | Helped |
| Use Bandit Conformal with Experts rather than a manually tuned learning rate | BCCP · CIFAR10 and SVHN with uniform policy | prediction set size | Helped |
| Use Bandit Conformal with Experts rather than a manually tuned learning rate | BCCP · Experiments with softmax policy | prediction set size | Hurt |
| Use RAPS instead of the other score functions | BCCP · CIFAR100 | prediction set size | Helped |
| Increase the quantile learning rate η₂ (ablation) | BCCP · Experiments varying η₂ | coverage control speed | Helped |
| Increase the quantile learning rate η₂ (ablation) | BCCP · Experiments varying η₂ | prediction set size | Hurt |
Surprising findings
- The uniform policy converges faster to the desired coverage and gives slightly smaller prediction sets than the softmax policy, even though the softmax policy reduces cross-entropy loss faster and pulls the correct arm more often.
Limitations
- Theoretical guarantees require the policy to be bounded strictly away from zero and a specific learning-rate order, which the authors note is hard to pick in practice.
- Learning rate for quantile updates requires manual tuning in the single-rate version; the expert ensemble is needed to avoid this.
- Experiments use only image classification benchmarks with ResNet50 and a single base model.
Experimental setup
Datasets: CIFAR10 CIFAR100 SVHN
Benchmarks: CIFAR10 CIFAR100 SVHN
Metrics: accumulative class-specific coverage (min/max) accumulative prediction set size
Baselines: softmax score APS RAPS full-feedback oracle
Builds on: class-conditional conformal prediction adaptive conformal inference APS RAPS
Closest papers by meaning
- Stochastic Online Conformal Prediction with Semi-Bandit Feedback (ICML 2025 · similarity 0.91)
- Counterfactual Online Conformal Prediction Under Adaptive Logging (NeurIPS 2026 · similarity 0.87)
- Online Conformal Prediction via Online Optimization (ICML 2025 · similarity 0.87)
- Optimal transport-based conformal prediction (ICML 2025 · similarity 0.87)
- Co-optimization for Adaptive Conformal Prediction (NeurIPS 2026 · similarity 0.86)
- Conformal Prediction with Learned Features (ICML 2024 · similarity 0.86)
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.