Almost Optimal Variance-Constrained Best Arm Identification
Yunlong Hou, Vincent Y. F. Tan, Zixin Zhong · IEEE Transactions on Information Theory · 2022
We design and analyze Variance-Aware-Lower and Upper Confidence Bound (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_{\mathrm {VA}}$. By proving an information-theoretic lower bound, we show that sample complexity of VA-LUCB is optimal up to a factor logarithmic in$H_{\mathrm {VA}}$. Extensive experiments corroborate the dependence of the sample complexity on the various terms in$H_{\mathrm {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.