論文の概要: Fixed-Budget Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit

• arxiv url: http://arxiv.org/abs/2310.15681v1
• Date: Tue, 24 Oct 2023 09:47:32 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-25 19:30:08.835889
• Title: Fixed-Budget Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit
• Title（参考訳）: 多要素バンドの固定予算実値組合せ純粋探索
• Authors: Shintaro Nakamura and Masashi Sugiyama
• Abstract要約: このアルゴリズムは,アクションクラスのサイズが指数関数的に大きい場合でも,最良のアクションを識別できる最初のアルゴリズムである。 CSAアルゴリズムの誤差確率の上限は指数の対数係数までの下界と一致することを示す。 提案手法を従来手法と実験的に比較し,アルゴリズムの性能が向上したことを示す。
• 参考スコア（独自算出の注目度）: 65.268245109828
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the real-valued combinatorial pure exploration of the multi-armed bandit in the fixed-budget setting. We first introduce the Combinatorial Successive Asign (CSA) algorithm, which is the first algorithm that can identify the best action even when the size of the action class is exponentially large with respect to the number of arms. We show that the upper bound of the probability of error of the CSA algorithm matches a lower bound up to a logarithmic factor in the exponent. Then, we introduce another algorithm named the Minimax Combinatorial Successive Accepts and Rejects (Minimax-CombSAR) algorithm for the case where the size of the action class is polynomial, and show that it is optimal, which matches a lower bound. Finally, we experimentally compare the algorithms with previous methods and show that our algorithm performs better.
• Abstract（参考訳）: 固定予算設定におけるマルチアームバンディットの実測値について検討した。 まず,動作クラスのサイズがアーム数に対して指数関数的に大きい場合でも,最善の動作を識別できる最初のアルゴリズムであるコンビネートアル・逐次アサイン(csa)アルゴリズムを導入する。 CSAアルゴリズムの誤差確率の上限は指数の対数係数までの下界と一致することを示す。 次に、アクションクラスのサイズが多項式である場合には、minimax combinatorial sequential accepts and rejects(minimax-combsar)アルゴリズムという別のアルゴリズムを導入し、それが最適であることを示し、下界に一致することを示す。 最後に,提案手法を従来の手法と実験的に比較し,アルゴリズムの性能が向上したことを示す。

関連論文リスト

• On Universally Optimal Algorithms for A/B Testing [49.429419538826444]
  ベルヌーイ報奨を伴う多腕バンディットにおける固定予算によるベストアーム識別の問題について検討する。 A/Bテスト問題としても知られる2つのアームの問題に対して,各アームを等しくサンプリングするアルゴリズムが存在しないことを証明した。
  論文  参考訳（メタデータ） (2023-08-23T08:38:53Z)
• An Optimal Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [65.268245109828]
  多武装バンディット(R-CPE-MAB)の真価純探査問題について検討する。 既存のR-CPE-MABの手法は、いわゆるトランスダクティブ線形帯域の特殊な場合と見なすことができる。 本稿では,差分探索アルゴリズム (CombGapE) を提案する。
  論文  参考訳（メタデータ） (2023-06-15T15:37:31Z)
• Practical, Provably-Correct Interactive Learning in the Realizable Setting: The Power of True Believers [12.09273192079783]
  我々は、対話型学習を実現可能な設定で検討し、最適な腕の識別からアクティブな分類に至るまでの問題に対処する一般的な枠組みを開発する。 我々は,最小限の値と対数係数とを一致させる,計算効率のよい新しいアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2021-11-09T02:33:36Z)
• Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback [51.21673420940346]
  コンビナーシャルバンディットはマルチアームバンディットを一般化し、エージェントが腕のセットを選択し、選択したセットに含まれる各腕の騒々しい報酬を観察します。 我々は, 最善の腕を一定の信頼度で識別する純粋爆発問題と, 応答集合の構造が動作集合の1つと異なるような, より一般的な設定に注目する。 有限多面体に対するプロジェクションフリーオンライン学習アルゴリズムに基づいて、凸的に最適であり、競争力のある経験的性能を持つ最初の計算効率の良いアルゴリズムである。
  論文  参考訳（メタデータ） (2021-01-21T10:35:09Z)
• Upper Confidence Bounds for Combining Stochastic Bandits [52.10197476419621]
  バンディットアルゴリズムを結合する簡単な手法を提案する。 私たちのアプローチは、個々のbanditアルゴリズムのそれぞれを、より高いレベルのn$-armed bandit問題のアームとして扱う"meta-ucb"手順に基づいています。
  論文  参考訳（メタデータ） (2020-12-24T05:36:29Z)
• On Regret with Multiple Best Arms [12.315392649501101]
  バンディット設定における複数のベスト/ニア最適アームの存在に関する後悔問題について検討する。 我々の目標は、問題の未知の硬さに自動的に適応できるアルゴリズムを設計することです。
  論文  参考訳（メタデータ） (2020-06-26T04:01:46Z)
• An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Bandits [34.06611065493047]
  本稿では、信頼度と予算設定の固定化において、純探索線形帯域問題に対する近似アルゴリズムを提案する。 サンプルの複雑性がインスタンスの幾何でスケールし、アームの数に縛られた明示的な結合を避けるアルゴリズムを提供する。 また,固定予算設定における線形帯域幅に対する最初のアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-21T00:56:33Z)
• Corralling Stochastic Bandit Algorithms [54.10645564702416]
  相関アルゴリズムの後悔は、最も報酬の高い腕を含む最高のアルゴリズムの後悔よりも悪くはないことを示す。 最高報酬と他の報酬の差は、最高報酬と他の報酬の差に依存することを示す。
  論文  参考訳（メタデータ） (2020-06-16T15:33:12Z)

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

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