# Best Arm Identification in Bandits with Limited Precision Sampling

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 20 references that are in the map.
- First posted on arXiv 10 May 2023.

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

- [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)
- [Optimal Best-arm Identification in Linear Bandits](https://mlsanity.com/paper/2006.16073/) (2020)
- [Lipschitz Bandits: Regret Lower Bounds and Optimal Algorithms](https://mlsanity.com/paper/1405.4758/) (2014)
- [Almost Cost-Free Communication in Federated Best Arm Identification](https://mlsanity.com/paper/2208.09215/) (2022)
- [Federated Best Arm Identification with Heterogeneous Clients](https://mlsanity.com/paper/2210.07780/) (2022)
- [Detecting an Odd Restless Markov Arm with a Trembling Hand](https://mlsanity.com/paper/2005.06255/) (2020)
- [Sequential Community Mode Estimation](https://mlsanity.com/paper/2111.08535/) (2021)

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

- [Information Capacity Regret Bounds for Bandits with Mediator Feedback](https://mlsanity.com/paper/2402.10282/) (2024)
- [Cost-Aware Best-LLM Identification using Dueling Feedback](https://mlsanity.com/paper/2609.30360/) (2026)

## Abstract (arXiv)

We study best arm identification in a variant of the multi-armed bandit problem where the learner has limited precision in arm selection. The learner can only sample arms via certain exploration bundles, which we refer to as boxes. In particular, at each sampling epoch, the learner selects a box, which in turn causes an arm to get pulled as per a box-specific probability distribution. The pulled arm and its instantaneous reward are revealed to the learner, whose goal is to find the best arm by minimising the expected stopping time, subject to an upper bound on the error probability. We present an asymptotic lower bound on the expected stopping time, which holds as the error probability vanishes. We show that the optimal allocation suggested by the lower bound is, in general, non-unique and therefore challenging to track. We propose a modified tracking-based algorithm to handle non-unique optimal allocations, and demonstrate that it is asymptotically optimal. We also present non-asymptotic lower and upper bounds on the stopping time in the simpler setting when the arms accessible from one box do not overlap with those of others.