# Variance-Dependent Best Arm Identification

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 19 references that are in the map.
- First posted on arXiv 19 Jun 2021.

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

- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits](https://mlsanity.com/paper/1312.7308/) (2013)
- [Towards Instance Optimal Bounds for Best Arm Identification](https://mlsanity.com/paper/1608.06031/) (2016)
- [On the Optimal Sample Complexity for Best Arm Identification](https://mlsanity.com/paper/1511.03774/) (2015)

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

- [Almost Optimal Variance-Constrained Best Arm Identification](https://mlsanity.com/paper/2201.10142/) (2022)
- [Contextual Bandits in a Survey Experiment on Charitable Giving: Within-Experiment Outcomes versus Policy Learning](https://mlsanity.com/paper/2211.12004/) (2022)
- [Fixed-Budget Best-Arm Identification with Heterogeneous Reward Variances](https://mlsanity.com/paper/2306.07549/) (2023)
- [Approximate Top-m Arm Identification with Heterogeneous Reward Variances](https://mlsanity.com/paper/2204.05245/) (2022)
- [Only Pay for What Is Uncertain: Variance-Adaptive Thompson Sampling](https://mlsanity.com/paper/2303.09033/) (2023)
- [Worst-Case Optimal Multi-Armed Gaussian Best Arm Identification with a Fixed Budget](https://mlsanity.com/paper/2310.19788/) (2023)
- [Adaptive Data Depth via Multi-Armed Bandits](https://mlsanity.com/paper/2211.03985/) (2022)
- [Fixed Budget is No Harder Than Fixed Confidence in Best-Arm Identification up to Logarithmic Factors](https://mlsanity.com/paper/2602.03972/) (2026)
- [Best-Arm Identification with Generative Proxy](https://mlsanity.com/paper/2607.06879/) (2026)

## Abstract (arXiv)

We study the problem of identifying the best arm in a stochastic multi-armed bandit game. Given a set of n arms indexed from 1 to n, each arm i is associated with an unknown reward distribution supported on [0,1] with mean θi and variance σi2. Assume θ1 > θ2 ≥ cdots ≥θn. We propose an adaptive algorithm which explores the gaps and variances of the rewards of the arms and makes future decisions based on the gathered information using a novel approach called textitgrouped median elimination. The proposed algorithm guarantees to output the best arm with probability (1-δ) and uses at most O left(sumi = 1n left(fracσi2Deltai2 + frac1Deltairight)(ln δ-1 + ln ln Deltai-1)right) samples, where Deltai (i ≥ 2) denotes the reward gap between arm i and the best arm and we define Delta1 = Delta2. This achieves a significant advantage over the variance-independent algorithms in some favorable scenarios and is the first result that removes the extra ln n factor on the best arm compared with the state-of-the-art. We further show that Omega left( sumi = 1n left( fracσi2Deltai2 + frac1Deltai right) ln δ-1 right) samples are necessary for an algorithm to achieve the same goal, thereby illustrating that our algorithm is optimal up to doubly logarithmic terms.