論文の概要: Identifying All ε-Best Arms in (Misspecified) Linear Bandits

• arxiv url: http://arxiv.org/abs/2510.00073v1
• Date: Mon, 29 Sep 2025 22:26:52 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-03 16:59:20.161859
• Title: Identifying All ε-Best Arms in (Misspecified) Linear Bandits
• Title（参考訳）: 線形帯域におけるε-Bestアームの同定
• Authors: Zhekai Li, Tianyi Ma, Cheng Hua, Ruihao Zhu,
• Abstract要約: LinFACT (LinFACT) は、リニアバンディットにおける全てのエプシロンベストアームの識別を最適化するために設計されたアルゴリズムである。 我々は、LinFACTが、この下界を対数係数にマッチングすることで、インスタンス最適性を達成することを示す。 合成および実薬品発見データを含む数値実験により、LinFACTはサンプルの複雑さを減らしたより有望な候補を同定することを示した。
• 参考スコア（独自算出の注目度）: 9.638337713545065
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Motivated by the need to efficiently identify multiple candidates in high trial-and-error cost tasks such as drug discovery, we propose a near-optimal algorithm to identify all {\epsilon}-best arms (i.e., those at most {\epsilon} worse than the optimum). Specifically, we introduce LinFACT, an algorithm designed to optimize the identification of all {\epsilon}-best arms in linear bandits. We establish a novel information-theoretic lower bound on the sample complexity of this problem and demonstrate that LinFACT achieves instance optimality by matching this lower bound up to a logarithmic factor. A key ingredient of our proof is to integrate the lower bound directly into the scaling process for upper bound derivation, determining the termination round and thus the sample complexity. We also extend our analysis to settings with model misspecification and generalized linear models. Numerical experiments, including synthetic and real drug discovery data, demonstrate that LinFACT identifies more promising candidates with reduced sample complexity, offering significant computational efficiency and accelerating early-stage exploratory experiments.
• Abstract（参考訳）: 薬物発見のような高い試行錯誤コストのタスクにおいて、複数の候補を効率的に特定する必要性から、我々は、全ての「エプシロン」ベストアーム(すなわち、最も多くは「エプシロン」ベストアーム)を識別する、準最適アルゴリズムを提案する。 具体的には,LinFACTを導入し,リニアバンディットにおける全エプシロンベストアームの識別を最適化するアルゴリズムを提案する。 この問題のサンプル複雑性に基づいた新しい情報理論的下界を確立し、LinFACTがこの下界を対数係数に整合させることで、インスタンス最適性を達成することを示す。 この証明の鍵となる要素は、下界を上界導出のスケーリングプロセスに直接統合し、終端ラウンドを判定し、したがってサンプルの複雑さを決定することである。 また、モデル不特定性や一般化線形モデルを用いた設定まで分析を拡張した。 合成および実薬品発見データを含む数値実験は、LinFACTがより有望な候補を特定し、サンプルの複雑さを減らし、計算効率を著しく向上し、早期の探索実験を加速することを示した。

関連論文リスト

• Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget [55.938644481736446]
  本稿では,誤差確率の指数的減衰を保証し,最適な腕識別のための新しいアルゴリズムを提案する。 我々は,複雑性のレベルが異なる様々な問題インスタンスに対する包括的経験的評価を通じて,アルゴリズムの有効性を検証する。
  論文  参考訳（メタデータ） (2025-06-03T02:56:26Z)
• Optimal Multi-Fidelity Best-Arm Identification [65.23078799972188]
  バンディットのベストアーム識別において、アルゴリズムは、できるだけ早く特定の精度で、最高平均報酬の腕を見つけることを任務とする。 マルチフィデリティのベストアーム識別について検討し、低コストで低いフィデリティ(正確な平均推定値を持たない)で腕をサンプリングすることを選択できる。 この問題に対処するためのいくつかの方法が提案されているが、その最適性は、特に最適な腕を特定するのに必要な総コストのゆるやかな下限のため、未解決のままである。
  論文  参考訳（メタデータ） (2024-06-05T08:02:40Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。 本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-08T16:06:29Z)
• Dual-Directed Algorithm Design for Efficient Pure Exploration [9.728332815218181]
  我々は、最良腕識別を超えたトップ2のアプローチを拡張する純粋探索問題のための新しい設計原理を開発する。 情報指向選択と組み合わせて、トップ2のトンプソンサンプリングがベストアーム識別に最適であることを示す。 また,しきい値と$varepsilon$-best-arm識別のための最適なアルゴリズムも作成する。
  論文  参考訳（メタデータ） (2023-10-30T07:29:17Z)
• Learning to Select and Rank from Choice-Based Feedback: A Simple Nested Approach [10.293894471295205]
  本研究では、動的アソートによる選択に基づくフィードバックから学習する際のランク付けと選択の問題について検討する。 両学習目標に対して,新しい,シンプルなアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-07-13T05:05:30Z)
• Dealing With Misspecification In Fixed-Confidence Linear Top-m Identification [0.0]
  固定誤差率$delta$(固定信頼度Top-m識別)の下で最大の手段を持つmアームの識別問題について検討する。 この問題は、特に医療やレコメンデーションシステムにおける実践的な応用によって動機付けられている。
  論文  参考訳（メタデータ） (2021-11-02T10:27:17Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Bandits [34.06611065493047]
  本稿では、信頼度と予算設定の固定化において、純探索線形帯域問題に対する近似アルゴリズムを提案する。 サンプルの複雑性がインスタンスの幾何でスケールし、アームの数に縛られた明示的な結合を避けるアルゴリズムを提供する。 また,固定予算設定における線形帯域幅に対する最初のアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-21T00:56:33Z)

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

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