Almost Optimal Variance-Constrained Best Arm Identification
  We design and analyze VA-LUCB, a parameter-free algorithm, for identifying
the best arm under the fixed-confidence setup and under a stringent constraint
that the variance of the chosen arm is strictly smaller than a given threshold.
An upper bound on VA-LUCB's sample complexity is shown to be characterized by a
fundamental variance-aware hardness quantity $H_{VA}$. By proving a lower
bound, we show that sample complexity of VA-LUCB is optimal up to a factor
logarithmic in $H_{VA}$. Extensive experiments corroborate the dependence of
the sample complexity on the various terms in $H_{VA}$. By comparing VA-LUCB's
empirical performance to a close competitor RiskAverse-UCB-BAI by David et al.
(2018), our experiments suggest that VA-LUCB has the lowest sample complexity
for this class of risk-constrained best arm identification problems, especially
for the riskiest instances.
