Almost Optimal Variance-Constrained Best Arm Identification

Yunlong Hou, Vincent Y. F. Tan, Zixin Zhong

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 c…