Approximate Top-$m$ Arm Identification with Heterogeneous Reward Variances
This work addresses a specific challenge in bandit algorithms for decision-making under uncertainty, offering theoretical insights but is incremental as it builds on existing top-m arm identification frameworks.
The paper tackles the problem of identifying the top-m arms with heterogeneous reward variances in a multi-armed bandit setting, deriving a worst-case sample complexity bound that includes terms for variance heterogeneity and providing matching upper and lower bounds.
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 $σ^2_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 $$Θ\left( \sum_{i =1}^n \frac{σ_i^2}{ε^2} \ln\frac{1}δ + \sum_{i \in G^{m}} \frac{σ_i^2}{ε^2} \ln(m) + \sum_{j \in G^{l}} \frac{σ_j^2}{ε^2} \text{Ent}(σ^2_{G^{r}}) \right),$$ where $G^{m}, G^{l}, G^{r}$ are certain specific subsets of the overall arm set $\{1, 2, \ldots, n\}$, and $\text{Ent}(\cdot)$ 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.