論文の概要: Best Arm Identification for Cascading Bandits in the Fixed Confidence Setting

• arxiv url: http://arxiv.org/abs/2001.08655v3
• Date: Mon, 15 Jun 2020 16:26:18 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-07 12:46:46.960640
• Title: Best Arm Identification for Cascading Bandits in the Fixed Confidence Setting
• Title（参考訳）: 固定信頼設定におけるカスケードバンディットの最適アーム識別法
• Authors: Zixin Zhong, Wang Chi Cheung, and Vincent Y. F. Tan
• Abstract要約: CascadeBAIを設計し、分析する。これは、$K$アイテムのベストセットを見つけるアルゴリズムである。 CascadeBAIの時間的複雑さの上限は、決定的な分析課題を克服することによって導かれる。 その結果,カスケードBAIの性能は,時間的複雑性の低い境界の導出により,いくつかの実践的状況において最適であることが示唆された。
• 参考スコア（独自算出の注目度）: 81.70513857417106
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We design and analyze CascadeBAI, an algorithm for finding the best set of $K$ items, also called an arm, within the framework of cascading bandits. An upper bound on the time complexity of CascadeBAI is derived by overcoming a crucial analytical challenge, namely, that of probabilistically estimating the amount of available feedback at each step. To do so, we define a new class of random variables (r.v.'s) which we term as left-sided sub-Gaussian r.v.'s; these are r.v.'s whose cumulant generating functions (CGFs) can be bounded by a quadratic only for non-positive arguments of the CGFs. This enables the application of a sufficiently tight Bernstein-type concentration inequality. We show, through the derivation of a lower bound on the time complexity, that the performance of CascadeBAI is optimal in some practical regimes. Finally, extensive numerical simulations corroborate the efficacy of CascadeBAI as well as the tightness of our upper bound on its time complexity.
• Abstract（参考訳）: 私たちはcascading banditsのフレームワーク内で,$k$項目の最高のセットを見つけるアルゴリズムであるcascadebaiを設計し,分析します。 カスケードバイの時間的複雑性の上限は、決定的な分析課題、すなわち各ステップで利用可能なフィードバックの量を確率的に見積もることによって導かれる。 そのため、我々は、左辺のガウス代名詞 r.v.'s と呼ばれる新しい確率変数(r.v.'s)を定義する。これらは、累積生成関数(CGFs)が CGF の非正の引数に対してのみ有界な二次函数によって境界付けられる r.v.'s である。 これにより、十分に厳密なベルンシュタイン型濃度不等式が適用できる。 我々は,時間複雑性に対する下限の導出を通じて,カスケードバイの性能が実用的手法において最適であることを示す。 最後に,広範な数値シミュレーションにより,カスケードベイの有効性と,その時間的複雑性に対する上限のきつくさが一致した。

関連論文リスト

• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。 本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-08T16:06:29Z)
• 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)
• Optimal PAC Bounds Without Uniform Convergence [11.125968799758436]
  我々は、一様収束論の極限を超えるフレームワークを通して、最適な高確率リスク境界を提供する。 我々のフレームワークは、置換不変予測器の残余誤差を高い確率リスク境界に変換する。 具体的には, 1-inclusion graph アルゴリズムの特定のアグリゲーションが最適であることを示す。
  論文  参考訳（メタデータ） (2023-04-18T17:57:31Z)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。 予測と高い確率で、新しい過剰なリスク境界を提供する。 我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
  論文  参考訳（メタデータ） (2022-11-03T12:40:24Z)
• On Kernelized Multi-Armed Bandits with Constraints [16.102401271318012]
  一般に未知の報酬関数と一般未知の制約関数を併用した帯域幅問題について検討する。 本稿では,アルゴリズムの性能解析のための一般的なフレームワークを提案する。 本稿では,数値実験により提案アルゴリズムの優れた性能を示す。
  論文  参考訳（メタデータ） (2022-03-29T14:02:03Z)
• A Unifying Theory of Thompson Sampling for Continuous Risk-Averse Bandits [91.3755431537592]
  本稿では,多腕バンディット問題に対するリスク-逆トンプソンサンプリングアルゴリズムの解析を統一する。 大規模偏差理論における収縮原理を用いることで、連続リスク汎関数に対する新しい濃度境界が証明される。 リスク関数の幅広いクラスと「ニセ」関数が連続性条件を満たすことを示す。
  論文  参考訳（メタデータ） (2021-08-25T17:09:01Z)
• Structure Adaptive Algorithms for Stochastic Bandits [22.871155520200773]
  構造化多武装バンディット問題のクラスにおける報酬最大化について検討する。 平均的な武器の報酬は、与えられた構造的制約を満たす。 我々は、反復的なサドルポイントソルバを用いて、インスタンス依存の低バウンドからのアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2020-07-02T08:59:54Z)
• An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Bandits [34.06611065493047]
  本稿では、信頼度と予算設定の固定化において、純探索線形帯域問題に対する近似アルゴリズムを提案する。 サンプルの複雑性がインスタンスの幾何でスケールし、アームの数に縛られた明示的な結合を避けるアルゴリズムを提供する。 また,固定予算設定における線形帯域幅に対する最初のアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-21T00:56:33Z)

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

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