論文の概要: Box Thirding: Anytime Best Arm Identification under Insufficient Sampling

• arxiv url: http://arxiv.org/abs/2602.18186v1
• Date: Fri, 20 Feb 2026 12:47:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-23 18:01:41.327366
• Title: Box Thirding: Anytime Best Arm Identification under Insufficient Sampling
• Title（参考訳）: Box Thirding: サンプリングが不十分な場合、いつでも最高の腕を識別できる
• Authors: Seohwa Hwang, Junyong Park,
• Abstract要約: 固定予算制約下でのベストアーム識別(BAI)のためのフレキシブルで効率的なアルゴリズムであるBox Thirding(B3)を紹介する。 B3は遺伝性Halving(SH)に匹敵するエプシロンベスト腕の誤同定確率を達成する 実証実験の結果、B3は単純な後悔という観点から、限られた予算制約の下で既存の手法よりも優れていた。
• 参考スコア（独自算出の注目度）: 0.3437656066916039
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce Box Thirding (B3), a flexible and efficient algorithm for Best Arm Identification (BAI) under fixed-budget constraints. It is designed for both anytime BAI and scenarios with large N, where the number of arms is too large for exhaustive evaluation within a limited budget T. The algorithm employs an iterative ternary comparison: in each iteration, three arms are compared--the best-performing arm is explored further, the median is deferred for future comparisons, and the weakest is discarded. Even without prior knowledge of T, B3 achieves an epsilon-best arm misidentification probability comparable to Successive Halving (SH), which requires T as a predefined parameter, applied to a randomly selected subset of c0 arms that fit within the budget. Empirical results show that B3 outperforms existing methods under limited-budget constraints in terms of simple regret, as demonstrated on the New Yorker Cartoon Caption Contest dataset.
• Abstract（参考訳）: 固定予算制約下でのベストアーム識別(BAI)のためのフレキシブルで効率的なアルゴリズムであるBox Thirding(B3)を紹介する。 アルゴリズムは反復3次比較を用いており、各反復において3つの腕を比較し、さらに最高の性能の腕を探索し、将来の比較のために中央値は遅延し、最も弱い腕は破棄される。 T の事前知識がなくても、B3 は Epsilon-best arm misidentification probability (SH) に匹敵する、T を予め定義されたパラメータとして必要とし、予算に適合するランダムに選択された c0 アームのサブセットに適用する。 ニューヨーク・カートゥーン・キャプション・コンテスト(New Yorker Cartoon Caption Contest)のデータセットで示されているように、経験的な結果から、B3は単純な後悔の観点から、限られた予算制約の下で既存の手法よりも優れていることが示されている。

関連論文リスト

• Constrained Best Arm Identification with Tests for Feasibility [7.968868442731488]
  ベストアーム識別(BAI)は、各アームからサンプルを集めることで、一組のK$アームの中で最高のパフォーマンスのアームを識別することを目的としている。 本稿では,本アルゴリズムが問題の難易度に自然に適応できることを示すアルゴリズムを提案する。 我々のアルゴリズムは、合成と実世界の両方のデータセットにおいて、他の最先端のBAIアルゴリズムよりも優れていることを実証的に示す。
  論文  参考訳（メタデータ） (2025-11-12T23:20:10Z)
• Rate-optimal Design for Anytime Best Arm Identification [19.803714682639903]
  目的は、限られたサンプリング予算の下で、一組のKドルアームから、最も高い平均報酬で腕を識別することである。 この問題はA/Bテストのような多くの実践シナリオをモデル化する。 この問題に対するアルゴリズムのクラスを考えるが、これは定数係数まで確実に最小限のアルゴリズムである。
  論文  参考訳（メタデータ） (2025-10-27T10:36:56Z)
• Balancing Performance and Costs in Best Arm Identification [5.558508644689221]
  本研究は、推奨アームの性能と、このアームを学習することで得られるコストとを明示的にバランスさせるリスク関数を最小化する新しいフォーマリズムを提案する。 この枠組みでは、サンプリングフェーズの各観察にコストがかかり、アームを推奨すると、最適下腕を特定するためにパフォーマンスペナルティが生じる。 性能ペナルティの2つの選択のリスク、誤識別の確率、単純な後悔のリスクについて理論的に下位境界を導出し、DBCAREと呼ばれるアルゴリズムを提案し、これらの下位境界をほぼ全ての問題インスタンス上のポリログ因子に一致させる。
  論文  参考訳（メタデータ） (2025-05-26T23:33:43Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Optimal Batched Best Arm Identification [29.635422073014638]
  バッチ化されたベストアーム識別(BBAI)問題について検討し、学習者のゴールは、ポリシーをできるだけ少なく変更しながら、最適なアームを識別することである。 本稿では, 最適なサンプル複雑性を実現する最初のバッチアルゴリズムである3バッチベストアーム識別(Tri-BBAI)を提案する。 さらに,非漸近的条件下での準最適サンプルとバッチ複雑性を初めて達成した,ほぼ最適なバッチ化されたベストアーム識別アルゴリズム(Opt-BBAI)を提案する。
  論文  参考訳（メタデータ） (2023-10-21T22:55:50Z)
• Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
  本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。 本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。 我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
  論文  参考訳（メタデータ） (2023-10-02T08:15:52Z)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。 具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
  論文  参考訳（メタデータ） (2021-11-14T21:49:58Z)
• Optimal Best-arm Identification in Linear Bandits [79.3239137440876]
  サンプルの複雑さが既知のインスタンス固有の下界と一致する単純なアルゴリズムを考案する。 既存のベストアーム識別戦略とは異なり、我々のアルゴリズムは武器の数に依存しない停止規則を用いる。
  論文  参考訳（メタデータ） (2020-06-29T14:25:51Z)
• The Unreasonable Effectiveness of Greedy Algorithms in Multi-Armed Bandit with Many Arms [10.662105162882526]
  本研究は,Emphmany-armed regimeにおける$k$-armed bandit問題について考察する。 以上の結果から,多腕の環境下での強欲なアルゴリズムには,新たなエフェフリー探索法が有用であることが示唆された。
  論文  参考訳（メタデータ） (2020-02-24T08:59:34Z)

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

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