Quantile Bandits for Best Arms Identification
  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 $\tau$-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.
