---
abstract: 'We study the best arm identification ([<span style="font-variant:small-caps;">Best-$1$-Arm</span>]{}) problem, which is defined as follows. We are given $n$ stochastic bandit arms. The $i$th arm has a reward distribution ${\mathcal{D}}_i$ with an unknown mean $\mu_{i}$. Upon each play of the $i$th arm, we can get a reward, sampled i.i.d. from ${\mathcal{D}}_i$. We would like to identify the arm with the largest mean with probability at least $1-\delta$, using as few samples as possible. We provide a nontrivial algorithm for [<span style="font-variant:small-caps;">Best-$1$-Arm</span>]{}, which improves upon several prior upper bounds on the same problem. We also study an important special case where there are only two arms, which we call the [<span style="font-variant:small-caps;">Sign</span>-$\xi$]{} problem. We provide a new lower bound of [<span style="font-variant:small-caps;">Sign</span>-$\xi$]{}, simplifying and significantly extending a classical result by Farrell in 1964, with a completely new proof. Using the new lower bound for [<span style="font-variant:small-caps;">Sign</span>-$\xi$]{}, we obtain the first lower bound for [<span style="font-variant:small-caps;">Best-$1$-Arm</span>]{} that goes beyond the classic Mannor-Tsitsiklis lower bound, by an interesting reduction from [<span style="font-variant:small-caps;">Sign</span>-$\xi$]{} to [<span style="font-variant:small-caps;">Best-$1$-Arm</span>]{}. We propose an interesting conjecture concerning the optimal sample complexity of [<span style="font-variant:small-caps;">Best-$1$-Arm</span>]{}  from the perspective of instance-wise optimality.'
author:
- |
    Lijie Chen Jian Li\
    Institute for Interdisciplinary Information Sciences (IIIS), Tsinghua University
bibliography:
- 'team.bib'
title: On the Optimal Sample Complexity for Best Arm Identification
---

Concluding Remarks
==================

The most interesting open problem from this paper is to obtain an almost instance optimal algorithm for [<span style="font-variant:small-caps;">Best-$1$-Arm</span>]{}, in particular to prove (or disprove) Conjecture \[conj:optimal\]. Note that for the clustered instances, and the instances where the gap entropy is $\Omega(\ln\ln n)$, we already have such an algorithm. Our techniques may be helpful for obtaining better bounds for the [<span style="font-variant:small-caps;">Best-$k$-Arm</span>]{} problem, or even the combinatorial pure exploration problem. In an ongoing work, we already have some partial results on applying some of the ideas in this paper to obtain improved upper and lower bounds for [<span style="font-variant:small-caps;">Best-$k$-Arm</span>]{}.
