Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: On the Optimal Sample Complexity for Best Arm Identification   We study the best arm identification (BEST-1-ARM) problem, which is defined
as follows. We are given $n$ stochastic bandit arms. The $i$th arm has a reward
distribution $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 $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 BEST-1-ARM,
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 sign problem. We provide a new lower bound of sign, simplifying and
significantly extending a classical result by Farrell in 1964, with a
completely new proof. Using the new lower bound for sign, we obtain the first
lower bound for BEST-1-ARM that goes beyond the classic Mannor-Tsitsiklis lower
bound, by an interesting reduction from Sign to BEST-1-ARM. We propose an
interesting conjecture concerning the optimal sample complexity of BEST-1-ARM
from the perspective of instance-wise optimality.

33
The categories of this paper are: plasm-ph
22
The categories of this paper are: chao-dyn
16
The categories of this paper are: stat
31
The categories of this paper are: ao-sci
21
The categories of this paper are: adap-org
25
The categories of this paper are: patt-sol
12
The categories of this paper are: nucl-th
28
The categories of this paper are: alg-geom
29
The categories of this paper are: funct-an
14
The categories of this paper are: math-ph
26
The categories of this paper are: bayes-an
5
The categories of this paper are: gr-qc
11
The categories of this paper are: hep-lat
17
The categories of this paper are: q-fin
18
The categories of this paper are: econ
24
The categories of this paper are: dg-ga