Minimax and Bayes Optimal Best-Arm Identification

Masahiro Kato。2025年。プレプリント（arXiv:2506.24007）。 English

試行回数が固定された最適腕識別で、最悪の場合に備えるミニマックス基準と、事前分布のもとで平均的な良さを測るベイズ基準は、これまで別々の戦略設計につながってきました。この研究は、一つの戦略が simple regret について両方の漸近最適性を同時に達成することを、定数まで一致する上界と下界を示して証明しました。

研究が扱う問題

固定予算の最適腕識別では、決められた試行回数で標本を集める段階と、最良と考える腕を推薦する段階からなる適応的な手続きを設計します。戦略は、推薦した腕の期待成果が真の最良からどれだけ劣るか（simple regret）で評価します。ミニマックス最適な戦略とベイズ最適な戦略が一致するのか、一つの戦略で両立できるのかは、基準の異なる二つの理論の間に残されていた問いです。

提案した方法

標本を集める段階を二つに分けます。最初のパイロット段階では腕へ一様に標本を割り当て、明らかに劣る腕を除きながら、成果の分散を推定します。次の段階に入る前に、ガウス分布を用いたミニマックスゲームを解き、そこから標本の配分方針と最終的な決定規則を得ます。第二段階ではこの配分方針に従って標本を集め、実験終了後に決定規則で腕を推薦します。

主な結果と成立条件

この一つの戦略が、simple regret について漸近的にミニマックス最適かつベイズ最適であることを示しました。上界は下界と定数まで一致します。下界は、腕の数を固定したうえで、あらゆる適応的実験に対して成り立つ形で導いています。最適性は試行回数を大きくしたときの漸近的な保証であり、有限の試行回数での性能は実験的な検証に基づきます。

先行研究との関係

最適腕識別の複雑さの理論は、固定信頼度の設定を中心に Kaufmann らが確立しました（2016年、On the Complexity of Best-Arm Identification in Multi-Armed Bandit Models）。固定予算の設定では Carpentier と Locatelli の下界が知られています（2016年、Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem）。分野の体系は Lattimore と Szepesvári の教科書（2020年、Bandit Algorithms）にまとまっています。この研究の貢献は、固定予算の simple regret について、ミニマックスとベイズという二つの最適性基準を一つの戦略で同時に達成し、上下界を定数まで一致させた点にあります。

利用できる状況

複数の施策案や設定から最良の一つを選ぶ実験で、試行回数が固定されている場面を想定しています。最悪ケースへの備えと平均的な性能のどちらを重視するかを選ばずに済む戦略である点が、実務での使いやすさにつながります。

論文と資料

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