# Conformal-Style Quantile Analyses for Stochastic Bandits

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

## Key facts

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

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

- [A Gentle Introduction to Conformal Prediction and Distribution-Free Uncertainty Quantification](https://mlsanity.com/paper/2107.07511/) (2021)
- [Distribution-Free Predictive Inference For Regression](https://mlsanity.com/paper/1604.04173/) (2016)
- [Conformalized Quantile Regression](https://mlsanity.com/paper/1905.03222/) (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)
- [Adaptive Conformal Predictions for Time Series](https://mlsanity.com/paper/2202.07282/) (2022)
- [Online conformal prediction with decaying step sizes](https://mlsanity.com/paper/2402.01139/) (2024)
- [Exploration vs Exploitation vs Safety: Risk-averse Multi-Armed Bandits](https://mlsanity.com/paper/1401.1123/) (2014)
- [Quantile Multi-Armed Bandits: Optimal Best-Arm Identification and a Differentially Private Scheme](https://mlsanity.com/paper/2006.06792/) (2020)
- [Stochastic Online Conformal Prediction with Semi-Bandit Feedback](https://mlsanity.com/paper/2405.13268/) (2024)

## Abstract (arXiv)

Stochastic bandit algorithms are usually analyzed under a mean-reward criterion, yet many problems favor arms with strong upper-tail performance, which we study herein. For a fixed miscoverage level (α), the natural upper-tail target of arm (j) is the upper endpoint (Fj-1(1-α/2)) of a central prediction interval. This target can rank arms differently from their means, creating a central mismatch with the classical bandit objective. To this end, we propose ACP-UCB1, a conformal-style policy that combines an adaptive conformal estimate of the upper endpoint with a UCB-type optimism bonus. The technical challenge is that the conformity scores used by ACP-UCB1 are recomputed from evolving empirical quantile estimates and evaluated at an adaptive level. We control this endpoint through reward-quantile concentration, a perturbation argument for recomputed score quantiles, and deterministic localization of the adaptive level. ACP-UCB1 achieves logarithmic upper-quantile regret with per-arm contribution (O(nicefraclog nDeltajACP)). We also provide metric-specific regret decompositions comparing ACP-UCB1 with UCB1 and use numerical experiments to validate performance and improvement.