論文の概要: Fundamental Limitations of Fixed-Budget Best-Arm Identification

• arxiv url: http://arxiv.org/abs/2607.11635v1
• Date: Mon, 13 Jul 2026 14:50:32 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-14 17:47:21.5146
• Title: Fundamental Limitations of Fixed-Budget Best-Arm Identification
• Title（参考訳）: 固定予算ベストアーム同定の基礎的限界
• Authors: Motti Goldberger,
• Abstract要約: 固定予算のベストアーム識別では、ランキングとセレクションとしても知られ、アルゴリズムはK$アームに分散するサンプリング予算を持つ。 任意のアルゴリズムに対して、誤差崩壊率が静的オラクルの少なくとも$left(+ fraclog(K)8right)-1$である少なくとも1つの例が存在することを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In fixed-budget best-arm identification, also known as ranking and selection, an algorithm has a sampling budget to distribute across $K$ arms. Each sample provides noisy feedback about that arm's mean, and the goal is to identify the arm with the largest mean. A common performance benchmark is the static oracle: a non-adaptive strategy that knows the means in advance and chooses fixed sampling proportions to maximize the exponential decay rate of the probability of incorrect identification. Several adaptive algorithms have been constructed such that their sampling proportions converge to the static oracle proportions. However, it has remained open whether any algorithm could match the static oracle's error decay rate uniformly across all problem instances. We answer this in the negative. For any $K\ge 3$ and for rewards drawn from any one-parameter natural exponential family, we show that for any algorithm, there is at least one instance where the error decay rate is at most $\left(1 + \frac{\log(K)}{8}\right)^{-1}$ times that of the static oracle. This also answers the open question posed by Qin (2022), showing that fixed-budget best-arm identification does not admit a complexity.
• Abstract（参考訳）: 固定予算のベストアーム識別では、ランキングとセレクションとしても知られ、アルゴリズムはK$アームに分散するサンプリング予算を持つ。 それぞれのサンプルは、その腕の平均について騒々しいフィードバックを与え、最大の平均で腕を特定することを目的としています。 一般的な性能ベンチマークは静的オラクルであり、前もってその手段を知っており、不正確な識別の確率の指数的減衰率を最大化するために固定サンプリング比率を選択する非適応戦略である。 サンプル比が静的なオラクル比に収束するように、いくつかの適応アルゴリズムが構築されている。 しかしながら、任意のアルゴリズムが全ての問題インスタンスで静的オラクルの誤差崩壊率に均一に一致できるかは、まだ明らかではない。 私たちはこれを否定的に答える。 任意の$K\ge 3$および任意の1パラメータの自然指数族から引き出された報酬に対して、任意のアルゴリズムに対して、誤差減衰率が少なくとも$\left(1 + \frac{\log(K)}{8}\right)^{-1} が静的オラクルの2倍である場合が少なくとも1つ存在することを示す。 これはまた、Qin (2022) が提起したオープンな疑問に答え、固定予算のベストアーム識別が複雑さを認めないことを示す。

関連論文リスト

• Bayesian Best-Arm Identification with Abstention: A Polynomial-to-Exponential Phase Transition [51.253617466579335]
  本研究では,学習者が端末の推薦を控えることができるベイジアン固定予算のベストアーム識別問題について検討する。 本研究は,非検出誤りの確率を解析し,吸収を伴わない準最適腕を推奨するリスクについて考察する。
  論文  参考訳（メタデータ） (2026-06-28T05:07:27Z)
• Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget [55.938644481736446]
  本稿では,誤差確率の指数的減衰を保証し,最適な腕識別のための新しいアルゴリズムを提案する。 我々は,複雑性のレベルが異なる様々な問題インスタンスに対する包括的経験的評価を通じて,アルゴリズムの有効性を検証する。
  論文  参考訳（メタデータ） (2025-06-03T02:56:26Z)
• An Algorithm for Fixed Budget Best Arm Identification with Combinatorial Exploration [3.9901365062418312]
  我々は、K$$armed banditフレームワークにおける最適な腕識別問題を考察する。 エージェントは1つのアームではなく、各タイムスロットでアームのサブセットをプレイすることができる。 我々は、$log K$グループを構築し、最適なアームの存在を検出するための確率比テストを実行するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-02-03T15:10:08Z)
• Optimal Top-Two Method for Best Arm Identification and Fluid Analysis [15.353009236788262]
  最適な腕識別問題に対する最適トップ2型アルゴリズムを提案する。 提案アルゴリズムは$delta rightarrow 0$として最適であることを示す。
  論文  参考訳（メタデータ） (2024-03-14T06:14:07Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• On the Existence of a Complexity in Fixed Budget Bandit Identification [0.0]
  固定予算帯域識別では、アルゴリズムは複数の分布から与えられた最終時点までのサンプルを逐次観察する。 我々は,ベルヌーイの腕を2つの腕で識別するなど,いくつかの固定予算識別タスクにおいて,そのような複雑さは存在しないことを示した。
  論文  参考訳（メタデータ） (2023-03-16T16:39:00Z)
• On the Sample Complexity of Representation Learning in Multi-task Bandits with Global and Local structure [77.60508571062958]
  マルチタスク・バンディット問題に対する最適アーム学習の複雑さについて検討した。 アームは2つのコンポーネントで構成されます。1つはタスク間で共有され(表現と呼ばれます)、もう1つはタスク固有のもの(予測器と呼ばれます)です。 サンプルの複雑さが下界に近づき、最大で$H(Glog(delta_G)+ Xlog(delta_H))$でスケールするアルゴリズムOSRL-SCを考案する。
  論文  参考訳（メタデータ） (2022-11-28T08:40:12Z)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。 具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
  論文  参考訳（メタデータ） (2021-11-14T21:49:58Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。