Globally Optimal Algorithms for Fixed-Budget Best Arm Identification
We consider the fixed-budget best arm identification problem where the goal
is to find the arm of the largest mean with a fixed number of samples. It is
known that the probability of misidentifying the best arm is exponentially
small to the number of rounds. However, limited characterizations have been
discussed on the rate (exponent) of this value. In this paper, we characterize
the optimal rate as a result of global optimization over all possible
parameters. We introduce two rates, $R^{\mathrm{go}}$ and
$R^{\mathrm{go}}_{\infty}$, corresponding to lower bounds on the
misidentification probability, each of which is associated with a proposed
algorithm. The rate $R^{\mathrm{go}}$ is associated with
$R^{\mathrm{go}}$-tracking, which can be efficiently implemented by a neural
network and is shown to outperform existing algorithms. However, this rate
requires a nontrivial condition to be achievable. To deal with this issue, we
introduce the second rate $R^{\mathrm{go}}_\infty$. We show that this rate is
indeed achievable by introducing a conceptual algorithm called delayed optimal
tracking (DOT).