論文の概要: Gamification of Pure Exploration for Linear Bandits

• arxiv url: http://arxiv.org/abs/2007.00953v1
• Date: Thu, 2 Jul 2020 08:20:35 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-14 13:16:12.130982
• Title: Gamification of Pure Exploration for Linear Bandits
• Title（参考訳）: リニアバンディットのための純粋探査のゲーム化
• Authors: R\'emy Degenne, Pierre M\'enard, Xuedong Shang, Michal Valko
• Abstract要約: 線形バンディットの文脈において、ベストアーム識別を含む活発な純粋探索環境について検討する。 標準的なマルチアームバンディットには最適アルゴリズムが存在するが、リニアバンディットにおけるベストアーム識別のためのアルゴリズムの存在は明白である。 線形帯域における固定信頼純粋探索のための第一の洞察的最適アルゴリズムを設計する。
• 参考スコア（独自算出の注目度）: 34.16123941778227
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We investigate an active pure-exploration setting, that includes best-arm identification, in the context of linear stochastic bandits. While asymptotically optimal algorithms exist for standard multi-arm bandits, the existence of such algorithms for the best-arm identification in linear bandits has been elusive despite several attempts to address it. First, we provide a thorough comparison and new insight over different notions of optimality in the linear case, including G-optimality, transductive optimality from optimal experimental design and asymptotic optimality. Second, we design the first asymptotically optimal algorithm for fixed-confidence pure exploration in linear bandits. As a consequence, our algorithm naturally bypasses the pitfall caused by a simple but difficult instance, that most prior algorithms had to be engineered to deal with explicitly. Finally, we avoid the need to fully solve an optimal design problem by providing an approach that entails an efficient implementation.
• Abstract（参考訳）: 線形確率的包帯の文脈において、ベストアーム識別を含む活発な純粋探索環境について検討する。 標準のマルチアームバンディットには漸近的に最適なアルゴリズムが存在するが、線形バンディットにおける最良アーム識別のためのアルゴリズムの存在は、それに対処するいくつかの試みにもかかわらず、解明されてきた。 まず,G最適性,最適設計からの帰納的最適性,漸近的最適性など,線形の場合における最適性の異なる概念について,徹底的な比較と新たな知見を提供する。 第2に,線形帯域における固定信頼純粋探索のための漸近最適化アルゴリズムを設計する。 その結果、我々のアルゴリズムは、単純だが難解な例による落とし穴を自然に回避し、ほとんどの先行アルゴリズムを明示的に扱うように設計しなければならなかった。 最後に、効率的な実装を伴うアプローチを提供することで、最適な設計問題を解決する必要性を回避します。

関連論文リスト

• Optimal Multi-Fidelity Best-Arm Identification [65.23078799972188]
  バンディットのベストアーム識別において、アルゴリズムは、できるだけ早く特定の精度で、最高平均報酬の腕を見つけることを任務とする。 マルチフィデリティのベストアーム識別について検討し、低コストで低いフィデリティ(正確な平均推定値を持たない)で腕をサンプリングすることを選択できる。 この問題に対処するためのいくつかの方法が提案されているが、その最適性は、特に最適な腕を特定するのに必要な総コストのゆるやかな下限のため、未解決のままである。
  論文  参考訳（メタデータ） (2024-06-05T08:02:40Z)
• Dual-Directed Algorithm Design for Efficient Pure Exploration [11.492736493413103]
  有限の選択肢からなる逐次適応実験の文脈における純粋探索問題を考える。 サンプルの最適な割り当てに対する強い収束の概念の観点から、最適性の十分な条件を導出する。 我々のアルゴリズムは、$epsilon$-best-armの識別としきい値の帯域幅問題に最適である。
  論文  参考訳（メタデータ） (2023-10-30T07:29:17Z)
• Information-Directed Selection for Top-Two Algorithms [13.339829037245963]
  マルチアームバンディットにおける最良のk腕識別問題について考察する。 目的は、測定努力を逐次割当てることにより、最高の平均報酬でk腕の正確なセットを選択することである。 情報ゲインの尺度に基づいて上位2候補の1つを選択する情報指向選択(IDS)を提案する。
  論文  参考訳（メタデータ） (2022-05-24T14:07:13Z)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。 具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
  論文  参考訳（メタデータ） (2021-11-14T21:49:58Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• An Index-based Deterministic Asymptotically Optimal Algorithm for Constrained Multi-armed Bandit Problems [0.0]
  制約付きマルチアームバンディットのモデルでは、インデックスベースの決定論的最適アルゴリズムが存在することを示す。 我々は、T が地平線サイズ、A がバンディットの腕の集合であるような 1-O(|A|Te-T) として与えられる最適性の確率に制限された有限時間を与える。
  論文  参考訳（メタデータ） (2020-07-29T01:54:22Z)
• Optimal Best-arm Identification in Linear Bandits [79.3239137440876]
  サンプルの複雑さが既知のインスタンス固有の下界と一致する単純なアルゴリズムを考案する。 既存のベストアーム識別戦略とは異なり、我々のアルゴリズムは武器の数に依存しない停止規則を用いる。
  論文  参考訳（メタデータ） (2020-06-29T14:25:51Z)
• Double Explore-then-Commit: Asymptotic Optimality and Beyond [101.77632893858063]
  ガウス級報酬を用いたマルチアームバンディット問題について検討する。 本研究では,探索-then-commit (ETC) アルゴリズムの変種により,マルチアームバンディット問題に対する最適性が得られることを示す。
  論文  参考訳（メタデータ） (2020-02-21T08:07:56Z)

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

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