Abstract
We study the effect of reward variance heterogeneity in the approximate top-m arm identification setting. In this setting, the reward for the i-th arm follows a σ²_i-sub-Gaussian distribution, and the agent needs to incorporate this knowledge to minimize the expected number of arm pulls to identify m arms with the largest means within error ε out of the n arms, with probability at least 1-δ. We show that the worst-case sample complexity of this problem is Θ( Σ_i =1ⁿ σ_i²/ε² ln1/δ + Σ_i ∈ G^m σ_i²/ε² ln(m) + Σ_j ∈ G^l σ_j²/ε² Ent(σ²_G^r) ), where G^m, G^l, G^r are certain specific subsets of the overall arm set {1, 2, …, n}, and Ent(·) is an entropy-like function which measures the heterogeneity of the variance proxies. The upper bound of the complexity is obtained using a divide-and-conquer style algorithm, while the matching lower bound relies on the study of a dual formulation.