Globally Optimal Algorithms for Fixed-Budget Best Arm Identification. (arXiv:2206.04646v2 [stat.ML] UPDATED)

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, …

algorithms arm arxiv budget identification ml