# Best-Arm Identification in Correlated Multi-Armed Bandits

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 44 references that are in the map.
- First posted on arXiv 10 Sep 2021.

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

- [Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization](https://mlsanity.com/paper/1603.06560/) (2016)
- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [Time-uniform, nonparametric, nonasymptotic confidence sequences](https://mlsanity.com/paper/1810.08240/) (2018)
- [lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits](https://mlsanity.com/paper/1312.7308/) (2013)
- [Multi-armed Bandit Models for the Optimal Design of Clinical Trials: Benefits and Challenges](https://mlsanity.com/paper/1507.08025/) (2015)
- [Best-Arm Identification in Linear Bandits](https://mlsanity.com/paper/1409.6110/) (2014)
- [Non-Asymptotic Pure Exploration by Solving Games](https://mlsanity.com/paper/1906.10431/) (2019)
- [Minimal Exploration in Structured Stochastic Bandits](https://mlsanity.com/paper/1711.00400/) (2017)
- [Fixed-Confidence Guarantees for Bayesian Best-Arm Identification](https://mlsanity.com/paper/1910.10945/) (2019)
- [Multi-Armed Bandits with Correlated Arms](https://mlsanity.com/paper/1911.03959/) (2019)
- [The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime](https://mlsanity.com/paper/1702.05186/) (2017)
- [Bounded Regret for Finite-Armed Structured Bandits](https://mlsanity.com/paper/1411.2919/) (2014)
- [Optimal Learning for Structured Bandits](https://mlsanity.com/paper/2007.07302/) (2020)
- [Structured Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1706.05198/) (2017)
- [Best Arm Identification in Spectral Bandits](https://mlsanity.com/paper/2005.09841/) (2020)
- [On Finding the Largest Mean Among Many](https://mlsanity.com/paper/1306.3917/) (2013)
- [Regional Multi-Armed Bandits](https://mlsanity.com/paper/1802.07917/) (2018)
- [Correlated Multi-armed Bandits with a Latent Random Source](https://mlsanity.com/paper/1808.05904/) (2018)
- [Global Bandits with Holder Continuity](https://mlsanity.com/paper/1410.7890/) (2014)

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

- [Best Arm Identification in Restless Markov Multi-Armed Bandits](https://mlsanity.com/paper/2203.15236/) (2022)
- [Cutting LLM Evaluation Costs with SySRs: A Bandit Algorithm that Provably Exploits Model Similarity](https://mlsanity.com/paper/2606.07726/) (2026)
- [Hierarchical Multi-Agent Multi-Armed Bandit for Resource Allocation in Multi-LEO Satellite Constellation Networks](https://mlsanity.com/paper/2303.14351/) (2023)
- [Covariance Adaptive Best Arm Identification](https://mlsanity.com/paper/2306.02630/) (2023)
- [Best Agent Identification for General Game Playing](https://mlsanity.com/paper/2507.00451/) (2025)
- [Best-Arm Identification with Generative Proxy](https://mlsanity.com/paper/2607.06879/) (2026)
- [Fixed-Confidence Best Arm Identification with Decreasing Variance](https://mlsanity.com/paper/2502.07199/) (2025)
- [Representative Action Selection for Large Action Space Bandit Families](https://mlsanity.com/paper/2505.18269/) (2025)

## Abstract (arXiv)

In this paper we consider the problem of best-arm identification in multi-armed bandits in the fixed confidence setting, where the goal is to identify, with probability 1-δ for some δ>0, the arm with the highest mean reward in minimum possible samples from the set of arms K. Most existing best-arm identification algorithms and analyses operate under the assumption that the rewards corresponding to different arms are independent of each other. We propose a novel correlated bandit framework that captures domain knowledge about correlation between arms in the form of upper bounds on expected conditional reward of an arm, given a reward realization from another arm. Our proposed algorithm C-LUCB, which generalizes the LUCB algorithm utilizes this partial knowledge of correlations to sharply reduce the sample complexity of best-arm identification. More interestingly, we show that the total samples obtained by C-LUCB are of the form Oleft(sumk ∈ C logleft(frac1δright)right) as opposed to the typical Oleft(sumk ∈ K logleft(frac1δright)right) samples required in the independent reward setting. The improvement comes, as the O(log(1/δ)) term is summed only for the set of competitive arms C, which is a subset of the original set of arms K. The size of the set C, depending on the problem setting, can be as small as 2, and hence using C-LUCB in the correlated bandits setting can lead to significant performance improvements. Our theoretical findings are supported by experiments on the Movielens and Goodreads recommendation datasets.