論文の概要: Towards Minimax Optimal Best Arm Identification in Linear Bandits

• arxiv url: http://arxiv.org/abs/2105.13017v1
• Date: Thu, 27 May 2021 09:19:10 GMT
• ステータス: 処理完了
• システム内更新日: 2021-05-29 04:17:48.634024
• Title: Towards Minimax Optimal Best Arm Identification in Linear Bandits
• Title（参考訳）: 線形バンディットにおけるミニマックス最適腕同定に向けて
• Authors: Junwen Yang, Vincent Y. F. Tan
• Abstract要約: 固定予算設定における線形包帯における最適な腕識別の問題について検討する。 G-最適設計の特性を活用し、アーム割り当て規則に組み込むことにより、パラメータフリーなアルゴリズムを設計する。 OD-LinBAIの故障確率に関する理論的解析を行った。
• 参考スコア（独自算出の注目度）: 95.22854522340938
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the problem of best arm identification in linear bandits in the fixed-budget setting. By leveraging properties of the G-optimal design and incorporating it into the arm allocation rule, we design a parameter-free algorithm, Optimal Design-based Linear Best Arm Identification (OD-LinBAI). We provide a theoretical analysis of the failure probability of OD-LinBAI. While the performances of existing methods (e.g., BayesGap) depend on all the optimality gaps, OD-LinBAI depends on the gaps of the top $d$ arms, where $d$ is the effective dimension of the linear bandit instance. Furthermore, we present a minimax lower bound for this problem. The upper and lower bounds show that OD-LinBAI is minimax optimal up to multiplicative factors in the exponent. Finally, numerical experiments corroborate our theoretical findings.
• Abstract（参考訳）: 固定予算設定における線形包帯における最適な腕識別の問題について検討する。 g-optimal designの特性を活用し、アーム割り当てルールに組み込むことにより、パラメータフリーな最適設計に基づく線形最良アーム識別(od-linbai)を設計する。 OD-LinBAIの故障確率に関する理論的解析を行った。 既存の方法(例えばベイズガップ)のパフォーマンスはすべての最適性ギャップに依存するが、od-linbai は最上位の$d$ arms のギャップに依存しており、ここで $d$ はリニア・バンディット・インスタンスの有効次元である。 さらに,この問題に対してミニマックス下限を提案する。 上と下の境界は、OD-LinBAI が指数の乗算因子まで極小であることを示している。 最後に,数値実験によって理論的知見が一致した。

関連論文リスト

• Minimum Empirical Divergence for Sub-Gaussian Linear Bandits [10.750348548547704]
  LinMEDは、アームサンプリング確率のクローズドフォーム計算を許容するランダム化アルゴリズムである。 我々の実証研究は、LinMEDが最先端のアルゴリズムと競合する性能を持っていることを示している。
  論文  参考訳（メタデータ） (2024-10-31T21:54:44Z)
• Optimal Multi-Fidelity Best-Arm Identification [65.23078799972188]
  バンディットのベストアーム識別において、アルゴリズムは、できるだけ早く特定の精度で、最高平均報酬の腕を見つけることを任務とする。 マルチフィデリティのベストアーム識別について検討し、低コストで低いフィデリティ(正確な平均推定値を持たない)で腕をサンプリングすることを選択できる。 この問題に対処するためのいくつかの方法が提案されているが、その最適性は、特に最適な腕を特定するのに必要な総コストのゆるやかな下限のため、未解決のままである。
  論文  参考訳（メタデータ） (2024-06-05T08:02:40Z)
• Indexed Minimum Empirical Divergence-Based Algorithms for Linear Bandits [55.938644481736446]
  Indexed Minimum Empirical Divergence (IMED)は、マルチアームバンディット問題に対する非常に効果的なアプローチである。 UCBベースのアルゴリズムとトンプソンサンプリングを実証的に上回ることが観察されている。 我々は、LinIMEDアルゴリズムのファミリーと呼ぶIMEDアルゴリズムの新しい線形バージョンを提案する。
  論文  参考訳（メタデータ） (2024-05-24T04:11:58Z)
• Fixed-Budget Best-Arm Identification in Sparse Linear Bandits [69.6194614504832]
  固定予算設定下での疎線形包帯のベストアーム識別問題について検討した。 我々は2相アルゴリズムであるLassoとOptimal-Design-(Lasso-OD)をベースとした線形ベストアーム識別を設計する。 我々はラッソODが指数においてほぼ極小であることを示す。
  論文  参考訳（メタデータ） (2023-11-01T12:32:17Z)
• PopArt: Efficient Sparse Regression and Experimental Design for Optimal Sparse Linear Bandits [29.097522376094624]
  そこで我々はPopArtと呼ばれる単純で効率的なスパース線形推定法を提案する。 我々は, 粗い線形バンディットアルゴリズムを導出し, 美術品の状態に対する後悔の上界の改善を享受する。
  論文  参考訳（メタデータ） (2022-10-25T19:13:20Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Fixed-Budget Best-Arm Identification in Structured Bandits [33.27743152847947]
  固定予算設定におけるベストアーム識別(BAI)は、学習エージェントが一定の回数の観測後に最適な(ベスト)腕を特定する確率を最大化する盗賊問題である。 結合一般化モデルから平均報酬推定値に基づいて最適アームを除去し,構造を組み込んだ一般トラクタブルアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-06-09T01:32:43Z)
• Optimal Best-arm Identification in Linear Bandits [79.3239137440876]
  サンプルの複雑さが既知のインスタンス固有の下界と一致する単純なアルゴリズムを考案する。 既存のベストアーム識別戦略とは異なり、我々のアルゴリズムは武器の数に依存しない停止規則を用いる。
  論文  参考訳（メタデータ） (2020-06-29T14:25:51Z)

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

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