# Quantile Bandits for Best Arms Identification

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

## Key facts

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

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

- [A Survey of Risk-Aware Multi-Armed Bandits](https://mlsanity.com/paper/2205.05843/) (2022)
- [Neural Design for Genetic Perturbation Experiments](https://mlsanity.com/paper/2207.12805/) (2022)
- [Gaussian Process Bandits with Aggregated Feedback](https://mlsanity.com/paper/2112.13029/) (2021)
- [Distribution-Free Model-Agnostic Regression Calibration via Nonparametric Methods](https://mlsanity.com/paper/2305.12283/) (2023)
- [Max-Quantile Grouped Infinite-Arm Bandits](https://mlsanity.com/paper/2210.01295/) (2022)
- [Dominant Arm Identification with Mixing and Recycling Observed Samples](https://mlsanity.com/paper/2608.01545/) (2026)
- [The Price of Decentralization in Top-K Arm Identification](https://mlsanity.com/paper/2608.22120/) (2026)

## Abstract (arXiv)

We consider a variant of the best arm identification task in stochastic multi-armed bandits. Motivated by risk-averse decision-making problems, our goal is to identify a set of m arms with the highest τ-quantile values within a fixed budget. We prove asymmetric two-sided concentration inequalities for order statistics and quantiles of random variables that have non-decreasing hazard rate, which may be of independent interest. With these inequalities, we analyse a quantile version of Successive Accepts and Rejects (Q-SAR). We derive an upper bound for the probability of arm misidentification, the first justification of a quantile based algorithm for fixed budget multiple best arms identification. We show illustrative experiments for best arm identification.