Best-Arm Identification
Pick out the option with the highest expected outcome, using a limited number of trials. That problem is called best-arm identification, a branch of the multi-armed bandit literature with close ties to experimental design. My work on this topic concerns sample allocation and decision rules when the number of trials is fixed in advance. The main paper is Minimax and Bayes Optimal Best-Arm Identification (Kato, 2025, arXiv:2506.24007).
Problems addressed
In fixed-budget best-arm identification, a strategy spends its allotted trials, recommends one arm, and is graded by how far that arm falls short of the true best one, its simple regret. The minimax criterion protects against the worst case and the Bayes criterion averages over a prior, and the two have led to different strategy designs. I take a two-stage strategy: a uniform pilot stage narrows the candidates and estimates the variances, and a Gaussian minimax game is then solved to fix the allocation and the decision rule. This strategy attains optimality under both criteria at once, with upper and lower bounds that agree up to the constant.
Core research
The Minimax and Bayes Optimal Best-Arm Identification page explains how the strategy is put together and what the optimality amounts to.
Research thread
- 2026
- The Role of Contextual Information in Best Arm Identification. How contextual information affects the efficiency of identification.
- 2024
- Generalized Neyman Allocation for Locally Minimax Optimal Best-Arm Identification. Local optimality of a sample allocation that follows the variances.
- 2024
- Rate-Optimal Bayesian Simple Regret in Best Arm Identification (Mathematics of Operations Research). Rate optimality of simple regret under the Bayes criterion.
Relation to earlier work
Work on the statistical limits of best-arm identification has centered on the fixed-confidence setting, where Kaufmann and coauthors developed the sample complexity theory (2016, On the Complexity of Best-Arm Identification in Multi-Armed Bandit Models). For the fixed-budget setting, Carpentier and Locatelli give a lower bound on the probability of misidentification (2016, Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem). Bandit problems as a whole are covered in the textbook by Lattimore and Szepesvári (2020, Bandit Algorithms). My work sits in the fixed-budget setting and attains optimality under both the minimax and the Bayes criteria with a single strategy.