Timezone: »
Poster
Minimax Optimal Algorithms for Fixed-Budget Best Arm Identification
Junpei Komiyama · Taira Tsuchiya · Junya Honda
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 minimax optimal rate as a result of an optimization over all possible parameters. We introduce two rates, $R^{\mathrm{go}}$ and $R^{\mathrm{go}}_{\infty}$, corresponding to lower bounds on the probability of misidentification, 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 address 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).
Author Information
Junpei Komiyama (New York University)
Taira Tsuchiya (Kyoto University)
Junya Honda (Kyoto University / RIKEN)
More from the Same Authors
-
2021 : Deviation-Based Learning »
Junpei Komiyama · Shunya Noda -
2021 : Deviation-Based Learning »
Junpei Komiyama · Shunya Noda -
2022 Poster: Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with Feedback Graphs »
Shinji Ito · Taira Tsuchiya · Junya Honda -
2021 : Deviation-Based Learning (Komiyama Junpei) »
Junpei Komiyama -
2020 Poster: Analysis and Design of Thompson Sampling for Stochastic Partial Monitoring »
Taira Tsuchiya · Junya Honda · Masashi Sugiyama -
2017 Poster: Position-based Multiple-play Bandit Problem with Unknown Position Bias »
Junpei Komiyama · Junya Honda · Akiko Takeda -
2015 Poster: Regret Lower Bound and Optimal Algorithm in Finite Stochastic Partial Monitoring »
Junpei Komiyama · Junya Honda · Hiroshi Nakagawa