Minimax and Bayes Optimal Best-Arm Identification

Masahiro Kato. 2025. Preprint (arXiv:2506.24007). 日本語版

In best-arm identification with a fixed number of trials, the minimax criterion prepares for the worst case, while the Bayes criterion measures average quality under a prior. The two have so far led to separate strategy designs. We prove that a single strategy attains both asymptotic optimality properties for simple regret, by exhibiting an upper bound and a lower bound that agree up to the constant.

The problem

Fixed-budget best-arm identification asks for an adaptive procedure with two parts, one that collects samples within a set number of trials and one that recommends the arm taken to be best. A strategy is scored by simple regret, which measures how far the expected outcome of the recommended arm falls short of the true best. Whether the minimax optimal strategy and the Bayes optimal strategy coincide, and whether one strategy can meet both, was a question left open between two theories built on different criteria.

The proposed method

The sampling stage splits in two. A pilot stage allocates samples uniformly across the arms, drops the arms that are clearly inferior, and estimates the variance of the outcomes. Before the next stage begins, the strategy solves a minimax game over Gaussian distributions, which yields an allocation rule for the samples together with the final decision rule. The second stage then samples according to that allocation, and once the experiment ends the decision rule recommends an arm.

Main results and conditions

This one strategy is asymptotically minimax optimal and Bayes optimal for simple regret. Its upper bound agrees with the lower bound up to the constant. The lower bound is derived so that it holds against every adaptive experiment, for each fixed number of arms. Optimality here is an asymptotic guarantee as the number of trials grows, and the performance at a finite number of trials rests on experimental verification.

Relation to earlier work

The complexity theory of best-arm identification was established by Kaufmann and coauthors, centered on the fixed-confidence setting (2016, On the Complexity of Best-Arm Identification in Multi-Armed Bandit Models). For the fixed-budget setting, the lower bound of Carpentier and Locatelli is known (2016, Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem). The textbook by Lattimore and Szepesvári collects what the field has settled (2020, Bandit Algorithms). What we contribute is a single strategy that meets the minimax and the Bayes criteria at once for fixed-budget simple regret.

Where it applies

The setting we have in mind is an experiment that picks the best of several candidate policies or configurations under a fixed number of trials. A practitioner does not have to choose in advance between guarding against the worst case and optimizing average performance, since one strategy serves both. That is what makes it easy to use in practice.

Paper and materials

BibTeX

@misc{minimax-bayes-optimal-best-arm-identification,
  author       = {Masahiro Kato},
  title        = {Minimax and Bayes Optimal Best-Arm Identification},
  year         = {2025},
  eprint       = {2506.24007},
  archivePrefix = {arXiv},
  url          = {https://arxiv.org/abs/2506.24007},
}