# Representative Arm Identification: A fixed confidence approach to identify cluster representatives

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 29 references that are in the map.
- First posted on arXiv 26 Aug 2024.

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

- [Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization](https://mlsanity.com/paper/1603.06560/) (2016)
- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Multi-armed Bandit Models for the Optimal Design of Clinical Trials: Benefits and Challenges](https://mlsanity.com/paper/1507.08025/) (2015)
- [Pure Exploration with Multiple Correct Answers](https://mlsanity.com/paper/1902.03475/) (2019)
- [An optimal algorithm for the Thresholding Bandit Problem](https://mlsanity.com/paper/1605.08671/) (2016)
- [PAC Identification of Many Good Arms in Stochastic Multi-Armed Bandits](https://mlsanity.com/paper/1901.08386/) (2019)
- [On the Complexity of A/B Testing](https://mlsanity.com/paper/1405.3224/) (2014)
- [Almost Cost-Free Communication in Federated Best Arm Identification](https://mlsanity.com/paper/2208.09215/) (2022)
- [Comparison Lift: Bandit-based Experimentation System for Online Advertising](https://mlsanity.com/paper/2009.07899/) (2020)
- [Regret of Age-of-Information Bandits](https://mlsanity.com/paper/2001.09317/) (2020)
- [A bandit approach to curriculum generation for automatic speech recognition](https://mlsanity.com/paper/2102.03662/) (2021)

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

- [A General Framework for Clustering and Distribution Matching with Bandit Feedback](https://mlsanity.com/paper/2409.05072/) (2024)
- [Near Optimal Best Arm Identification for Clustered Bandits](https://mlsanity.com/paper/2505.10147/) (2025)

## Abstract (arXiv)

We study the representative arm identification (RAI) problem in the multi-armed bandits (MAB) framework, wherein we have a collection of arms, each associated with an unknown reward distribution. An underlying instance is defined by a partitioning of the arms into clusters of predefined sizes, such that for any j > i, all arms in cluster i have a larger mean reward than those in cluster j. The goal in RAI is to reliably identify a certain prespecified number of arms from each cluster, while using as few arm pulls as possible. The RAI problem covers as special cases several well-studied MAB problems such as identifying the best arm or any M out of the top K, as well as both full and coarse ranking. We start by providing an instance-dependent lower bound on the sample complexity of any feasible algorithm for this setting. We then propose two algorithms, based on the idea of confidence intervals, and provide high probability upper bounds on their sample complexity, which orderwise match the lower bound. Finally, we do an empirical comparison of both algorithms along with an LUCB-type alternative on both synthetic and real-world datasets, and demonstrate the superior performance of our proposed schemes in most cases.