# Approximate Top-m Arm Identification with Heterogeneous Reward Variances

arXiv: https://arxiv.org/abs/2204.05245 · HTML: https://mlsanity.com/paper/2204.05245/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 36 references that are in the map.
- First posted on arXiv 11 Apr 2022.

## Builds on (most cited first, 13 of 13)

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits](https://mlsanity.com/paper/1312.7308/) (2013)
- [Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem](https://mlsanity.com/paper/1605.09004/) (2016)
- [The True Sample Complexity of Identifying Good Arms](https://mlsanity.com/paper/1906.06594/) (2019)
- [The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime](https://mlsanity.com/paper/1702.05186/) (2017)
- [Nearly Instance Optimal Sample Complexity Bounds for Top-k Arm Selection](https://mlsanity.com/paper/1702.03605/) (2017)
- [Exploration with Limited Memory: Streaming Algorithms for Coin Tossing, Noisy Comparisons, and Multi-Armed Bandits](https://mlsanity.com/paper/2004.04666/) (2020)
- [On the Optimal Sample Complexity for Best Arm Identification](https://mlsanity.com/paper/1511.03774/) (2015)
- [PAC Identification of Many Good Arms in Stochastic Multi-Armed Bandits](https://mlsanity.com/paper/1901.08386/) (2019)
- [An Optimal Elimination Algorithm for Learning a Best Arm](https://mlsanity.com/paper/2006.11647/) (2020)
- [Variance-Dependent Best Arm Identification](https://mlsanity.com/paper/2106.10417/) (2021)

## Built on by (most cited first, 5 of 5)

- [Fixed-Budget Best-Arm Identification with Heterogeneous Reward Variances](https://mlsanity.com/paper/2306.07549/) (2023)
- [Only Pay for What Is Uncertain: Variance-Adaptive Thompson Sampling](https://mlsanity.com/paper/2303.09033/) (2023)
- [Optimal Arm Elimination Algorithms for Combinatorial Bandits](https://mlsanity.com/paper/2510.23992/) (2025)
- [Multi-Metric Adaptive Experimental Design Under a Fixed Budget with Validation](https://mlsanity.com/paper/2506.03062/) (2025)
- [Cost-Aware Optimal Pairwise Pure Exploration](https://mlsanity.com/paper/2503.07877/) (2025)

## Abstract (arXiv)

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 σ2i-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 Thetaleft( sumi =1n fracσi2ε2 lnfrac1δ + sum_i ∈ Gm fracσi2ε2 ln(m) + sum_j ∈ Gl fracσj2ε2 Ent(σ2_Gr) right), where Gm, Gl, Gr are certain specific subsets of the overall arm set 1, 2, ldots, 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.