Towards Instance Optimal Bounds for Best Arm Identification

Abstract

In the classical best arm identification (Best-$1$-Arm) problem, we are given $n$ stochastic bandit arms, each associated with a reward distribution with an unknown mean. We would like to identify the arm with the largest mean with probability at least $1-\delta$, using as few samples as possible. Understanding the sample complexity of Best-$1$-Arm has attracted significant attention since the last decade. However, the exact sample complexity of the problem is still unknown. Recently, Chen and Li made the gap-entropy conjecture concerning the instance sample complexity of Best-$1$-Arm. Given an instance $I$, let ${\mu }_{[i]}$ be the $i$th largest mean and ${\Delta }_{[i]}={\mu }_{[1]}-{\mu }_{[i]}$ be the corresponding gap. $H(I)={\sum }_{i=2}^n{\Delta }_{[i]}^{-2}$ is the complexity of the instance. The gap-entropy conjecture states that $\Omega \left(H(I)\cdot \left(\ln {\delta }^{-1}+\mathsf{Ent}(I)\right)\right)$ is an instance lower bound, where $\mathsf{Ent}(I)$ is an entropy-like term determined by the gaps, and there is a $\delta$-correct algorithm for Best-$1$-Arm with sample complexity $O\left(H(I)\cdot \left(\ln {\delta }^{-1}+\mathsf{Ent}(I)\right)+{\Delta }_{[2]}^{-2}\ln \ln {\Delta }_{[2]}^{-1}\right)$. If the conjecture is true, we would have a complete understanding of the instance-wise sample complexity of Best-$1$-Arm. We make significant progress towards the resolution of the gap-entropy conjecture. For the upper bound, we provide a highly nontrivial algorithm which requires \[O\left(H(I)\cdot\left(\lnδ^{-1} +\mathsf{Ent}(I)\right)+Δ_{[2]}^{-2}\ln\lnΔ_{[2]}^{-1}\mathrm{polylog}(n,δ^{-1})\right)\] samples in expectation. For the lower bound, we show that for any Gaussian Best-$1$-Arm instance with gaps of the form $2^{-k}$, any $\delta$-correct monotone algorithm requires $\Omega \left(H(I)\cdot \left(\ln {\delta }^{-1}+\mathsf{Ent}(I)\right)\right)$ samples in expectation.

Accepted to COLT 2017

References in corpus (5)

• lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits
• On the Optimal Sample Complexity for Best Arm Identification
• Multiple Identifications in Multi-Armed Bandits
• Nearly Instance Optimal Sample Complexity Bounds for Top-k Arm Selection
• Pure Exploration of Multi-armed Bandit Under Matroid Constraints

Cited by in corpus (11)

• Nearly Minimax-Optimal Regret for Linearly Parameterized Bandits
• Quantum exploration algorithms for multi-armed bandits
• A Bandit Approach to Multiple Testing with False Discovery Control
• Nearly Optimal Sampling Algorithms for Combinatorial Pure Exploration
• Adaptive Multiple-Arm Identification
• Learning the distribution with largest mean: two bandit frameworks
• Collaborative Learning with Limited Interaction: Tight Bounds for Distributed Exploration in Multi-Armed Bandits
• Collaborative Top Distribution Identifications with Limited Interaction
• Variance-Dependent Best Arm Identification
• Exploration with Limited Memory: Streaming Algorithms for Coin Tossing, Noisy Comparisons, and Multi-Armed Bandits
• Collaborative Pure Exploration in Kernel Bandit