論文の概要: Constrained Best Arm Identification with Tests for Feasibility

• arxiv url: http://arxiv.org/abs/2511.09808v1
• Date: Fri, 14 Nov 2025 01:10:41 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-14 22:53:22.497657
• Title: Constrained Best Arm Identification with Tests for Feasibility
• Title（参考訳）: 適合性テストによる制約付きベストアーム識別
• Authors: Ting Cai, Kirthevasan Kandasamy,
• Abstract要約: ベストアーム識別(BAI)は、各アームからサンプルを集めることで、一組のK$アームの中で最高のパフォーマンスのアームを識別することを目的としている。 本稿では,本アルゴリズムが問題の難易度に自然に適応できることを示すアルゴリズムを提案する。 我々のアルゴリズムは、合成と実世界の両方のデータセットにおいて、他の最先端のBAIアルゴリズムよりも優れていることを実証的に示す。
• 参考スコア（独自算出の注目度）: 7.968868442731488
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Best arm identification (BAI) aims to identify the highest-performance arm among a set of $K$ arms by collecting stochastic samples from each arm. In real-world problems, the best arm needs to satisfy additional feasibility constraints. While there is limited prior work on BAI with feasibility constraints, they typically assume the performance and constraints are observed simultaneously on each pull of an arm. However, this assumption does not reflect most practical use cases, e.g., in drug discovery, we wish to find the most potent drug whose toxicity and solubility are below certain safety thresholds. These safety experiments can be conducted separately from the potency measurement. Thus, this requires designing BAI algorithms that not only decide which arm to pull but also decide whether to test for the arm's performance or feasibility. In this work, we study feasible BAI which allows a decision-maker to choose a tuple $(i,\ell)$, where $i\in [K]$ denotes an arm and $\ell$ denotes whether she wishes to test for its performance ($\ell=0$) or any of its $N$ feasibility constraints ($\ell\in[N]$). We focus on the fixed confidence setting, which is to identify the \textit{feasible} arm with the \textit{highest performance}, with a probability of at least $1-δ$. We propose an efficient algorithm and upper-bound its sample complexity, showing our algorithm can naturally adapt to the problem's difficulty and eliminate arms by worse performance or infeasibility, whichever is easier. We complement this upper bound with a lower bound showing that our algorithm is \textit{asymptotically ($δ\rightarrow 0$) optimal}. Finally, we empirically show that our algorithm outperforms other state-of-the-art BAI algorithms in both synthetic and real-world datasets.
• Abstract（参考訳）: ベストアーム識別(BAI)は、各アームから確率的なサンプルを収集することで、一組のK$アームの中で最高のパフォーマンスの腕を識別することを目的としている。 現実世界の問題では、最高のアームは追加の実現可能性の制約を満たす必要がある。 実現可能性制約を伴うBAIの事前作業には制限があるが、通常は、腕の各プルでパフォーマンスと制約が同時に観測されると仮定する。 しかしながら、この仮定は、例えば、薬物発見において、毒性と溶解度が一定の安全性閾値以下である最も強力な薬物を見つけるために、最も実用的なユースケースを反映していない。 これらの安全実験は、有効性測定とは別々に行うことができる。 従って、どのアームをプルするかを判断するだけでなく、腕のパフォーマンスや実現可能性をテストするBAIアルゴリズムを設計する必要がある。 そこで、i\in [K]$は腕を表し、$\ell$は、そのパフォーマンスのためにテストしたいかどうかを示す($\ell=0$)か、または、その$N$のファシビリティ制約($\ell\in[N]$)のいずれかを示す。 固定された信頼設定は、少なくとも1-δ$の確率で、 \textit{feasible} アームと \textit{highest performance} を識別するものである。 提案アルゴリズムは, アルゴリズムが問題の難易度に自然に適応し, より悪い性能や不実現性によって武器を除去できることを示す。 この上界を下界で補うと、アルゴリズムが \textit{asymptotically ($δ\rightarrow 0$) optimal} であることが示される。 最後に、我々のアルゴリズムは、合成と実世界の両方のデータセットにおいて、他の最先端のBAIアルゴリズムよりも優れていることを実証的に示す。

関連論文リスト

• Rate-optimal Design for Anytime Best Arm Identification [19.803714682639903]
  目的は、限られたサンプリング予算の下で、一組のKドルアームから、最も高い平均報酬で腕を識別することである。 この問題はA/Bテストのような多くの実践シナリオをモデル化する。 この問題に対するアルゴリズムのクラスを考えるが、これは定数係数まで確実に最小限のアルゴリズムである。
  論文  参考訳（メタデータ） (2025-10-27T10:36:56Z)
• Optimal Multi-Objective Best Arm Identification with Fixed Confidence [62.36929749450298]
  我々は、各アームが選択時にM$Dのベクトル報酬を得られる多腕バンディット設定を考える。 最終的なゴールは、最も短い(予想される)時間において、エラーの確率の上限に従属する全ての目的の最良のアームを特定することである。 本稿では,各ステップでアームをサンプリングするために,エミュロゲート比例という新しいアイデアを用いたアルゴリズムを提案し,各ステップにおける最大最小最適化問題を解く必要をなくした。
  論文  参考訳（メタデータ） (2025-01-23T12:28:09Z)
• Optimal Multi-Fidelity Best-Arm Identification [65.23078799972188]
  バンディットのベストアーム識別において、アルゴリズムは、できるだけ早く特定の精度で、最高平均報酬の腕を見つけることを任務とする。 マルチフィデリティのベストアーム識別について検討し、低コストで低いフィデリティ(正確な平均推定値を持たない)で腕をサンプリングすることを選択できる。 この問題に対処するためのいくつかの方法が提案されているが、その最適性は、特に最適な腕を特定するのに必要な総コストのゆるやかな下限のため、未解決のままである。
  論文  参考訳（メタデータ） (2024-06-05T08:02:40Z)
• Optimal Top-Two Method for Best Arm Identification and Fluid Analysis [15.353009236788262]
  最適な腕識別問題に対する最適トップ2型アルゴリズムを提案する。 提案アルゴリズムは$delta rightarrow 0$として最適であることを示す。
  論文  参考訳（メタデータ） (2024-03-14T06:14:07Z)
• Cost Aware Best Arm Identification [13.380383930882784]
  emphCost Aware Best Arm Identification (CABAI)と呼ぶ。 平方根規則に基づくemphChernoff Overlap (CO)と呼ばれる単純なアルゴリズムを提案する。 この結果から,不均一な動作コストを無視すると,実行時の準最適性が得られ,また,簡単なアルゴリズムにより,幅広い問題に対してほぼ最適性能が得られることがわかった。
  論文  参考訳（メタデータ） (2024-02-26T16:27:08Z)
• PAC Best Arm Identification Under a Deadline [101.10352416022559]
  我々は、$(epsilon, delta)$-PACベストアーム識別について研究し、意思決定者は、アームプル(サンプル)の数を最小化しながら、少なくとも1 - delta$の確率で最適なアームを識別しなければならない。 この作業では、決定者はT$ラウンドの期限が与えられ、各ラウンドで、どのアームを引っ張るか、何回引っ張るかを適応的に選ぶことができる。 本稿では,この設定のための新しいアルゴリズムであるElastic Batch Racing (EBR)を提案する。
  論文  参考訳（メタデータ） (2021-06-06T19:48:32Z)
• Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy [71.17938026619068]
  我々は、腕の総数が膨大であることができるトップ$ k$極端な文脈的包帯問題を研究します。 まず,Inverse Gap Weighting戦略を用いて,非極端に実現可能な設定のアルゴリズムを提案する。 我々のアルゴリズムは、$O(ksqrt(A-k+1)T log (|mathcalF|T))$である。
  論文  参考訳（メタデータ） (2021-02-15T19:10:52Z)

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

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