# Quantile Multi-Armed Bandits: Optimal Best-Arm Identification and a Differentially Private Scheme

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jun 2020.

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

- [Risk Verification of Stochastic Systems with Neural Network Controllers](https://mlsanity.com/paper/2209.09881/) (2022)
- [On the Complexity of Differentially Private Best-Arm Identification with Fixed Confidence](https://mlsanity.com/paper/2309.02202/) (2023)
- [STL Robustness Risk over Discrete-Time Stochastic Processes](https://mlsanity.com/paper/2104.01503/) (2021)
- [Conditionally Risk-Averse Contextual Bandits](https://mlsanity.com/paper/2210.13573/) (2022)
- [CRIMED: Lower and Upper Bounds on Regret for Bandits with Unbounded Stochastic Corruption](https://mlsanity.com/paper/2309.16563/) (2023)
- [Fixed-Budget Differentially Private Best Arm Identification](https://mlsanity.com/paper/2401.09073/) (2024)
- [DP-SPRT: Differentially Private Sequential Probability Ratio Tests](https://mlsanity.com/paper/2508.06377/) (2025)
- [Optimal Rates for Differentially Private Hypothesis Testing with E-values](https://mlsanity.com/paper/2605.28952/) (2026)
- [Conformal-Style Quantile Analyses for Stochastic Bandits](https://mlsanity.com/paper/2605.07115/) (2026)

## Abstract (arXiv)

We study the best-arm identification problem in multi-armed bandits with stochastic, potentially private rewards, when the goal is to identify the arm with the highest quantile at a fixed, prescribed level. First, we propose a (non-private) successive elimination algorithm for strictly optimal best-arm identification, we show that our algorithm is δ-PAC and we characterize its sample complexity. Further, we provide a lower bound on the expected number of pulls, showing that the proposed algorithm is essentially optimal up to logarithmic factors. Both upper and lower complexity bounds depend on a special definition of the associated suboptimality gap, designed in particular for the quantile bandit problem, as we show when the gap approaches zero, best-arm identification is impossible. Second, motivated by applications where the rewards are private, we provide a differentially private successive elimination algorithm whose sample complexity is finite even for distributions with infinite support-size, and we characterize its sample complexity. Our algorithms do not require prior knowledge of either the suboptimality gap or other statistical information related to the bandit problem at hand.