論文の概要: Ballooning Multi-Armed Bandits

• arxiv url: http://arxiv.org/abs/2001.10055v3
• Date: Mon, 22 Feb 2021 12:33:14 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-07 04:38:59.593825
• Title: Ballooning Multi-Armed Bandits
• Title（参考訳）: バルーン式マルチアーマッドバンド
• Authors: Ganesh Ghalme, Swapnil Dhamal, Shweta Jain, Sujit Gujar, Y. Narahari
• Abstract要約: バルーン式マルチアーマッドバンド(BL-MAB)について紹介する。 BL-MABでは、利用可能なアームのセットは時間とともに成長する。 ベストアームが任意のタイミングで到着する確率が等しく高い場合、サブリニアな後悔は達成できないことを示す。
• 参考スコア（独自算出の注目度）: 12.205797997133397
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we introduce Ballooning Multi-Armed Bandits (BL-MAB), a novel extension of the classical stochastic MAB model. In the BL-MAB model, the set of available arms grows (or balloons) over time. In contrast to the classical MAB setting where the regret is computed with respect to the best arm overall, the regret in a BL-MAB setting is computed with respect to the best available arm at each time. We first observe that the existing stochastic MAB algorithms result in linear regret for the BL-MAB model. We prove that, if the best arm is equally likely to arrive at any time instant, a sub-linear regret cannot be achieved. Next, we show that if the best arm is more likely to arrive in the early rounds, one can achieve sub-linear regret. Our proposed algorithm determines (1) the fraction of the time horizon for which the newly arriving arms should be explored and (2) the sequence of arm pulls in the exploitation phase from among the explored arms. Making reasonable assumptions on the arrival distribution of the best arm in terms of the thinness of the distribution's tail, we prove that the proposed algorithm achieves sub-linear instance-independent regret. We further quantify explicit dependence of regret on the arrival distribution parameters. We reinforce our theoretical findings with extensive simulation results. We conclude by showing that our algorithm would achieve sub-linear regret even if (a) the distributional parameters are not exactly known, but are obtained using a reasonable learning mechanism or (b) the best arm is not more likely to arrive early, but a large fraction of arms is likely to arrive relatively early.
• Abstract（参考訳）: 本稿では,従来の確率MABモデルの拡張であるBallooning Multi-Armed Bandits (BL-MAB)を紹介する。 BL-MABモデルでは、利用可能なアームのセットは時間とともに成長する。 全体的なベストアームに対して後悔が計算される古典的MAB設定とは対照的に、BL−MAB設定における後悔は、最高の腕に対して各タイミングで計算される。 まず,既存の確率MABアルゴリズムがBL-MABモデルに線形後悔をもたらすことを示す。 最善の腕が瞬時に着く確率が等しく高いならば、それ以下の後悔は達成できないことが証明される。 次に、最善腕が早期ラウンドに到達する確率が高い場合、サブ線形後悔を実現することができることを示す。 提案するアルゴリズムは,(1)新たに到着するアームの時間軸のごく一部を探索し,(2)探索したアームのうちの活用段階におけるアームプルのシーケンスを決定づける。 分布の尾の薄さの観点から、最適アームの到着分布を合理的に仮定し、提案アルゴリズムがサブ線形のインスタンス非依存の後悔を実現することを証明した。 さらに,到着分布パラメータに対する後悔の明示的依存性を定量化する。 より広範なシミュレーション結果で理論的知見を補強する。 我々は,アルゴリズムがたとえそのアルゴリズムが線形的後悔を達成できることを示すことで結論付けた。 (a)分布パラメータは正確には知られていないが、合理的な学習機構を用いて得られるか (b)最善の腕は早く到着する可能性は低いが、相当な数の腕が比較的早く到着する可能性が高い。

関連論文リスト

• Best Arm Identification with Minimal Regret [55.831935724659175]
  最高の腕識別問題 優雅にアマルガメートは、最小化とBAIを後悔している。 エージェントの目標は、所定の信頼度で最高の腕を特定することである。 二重KL-UCBアルゴリズムは、信頼度がゼロになる傾向があるため、最適性を達成する。
  論文  参考訳（メタデータ） (2024-09-27T16:46:02Z)
• Optimal Best Arm Identification with Fixed Confidence in Restless Bandits [66.700654953613]
  本研究は,有限個の腕を持つレスレス・マルチアーム・バンディット・セッティングにおけるベスト・アーム識別について検討する。 各アームによって生成された離散時間データは、共通の有限状態空間で値を取る同質マルコフ連鎖を形成する。 その結果,あるマルコフ決定過程の長期的挙動の追跡とその状態-行動的訪問比率が,逆および達成可能性境界を解析するための重要な要素であることが示唆された。
  論文  参考訳（メタデータ） (2023-10-20T10:04:05Z)
• Best Arm Identification in Bandits with Limited Precision Sampling [14.011731120150124]
  学習者が腕選択の精度に限界がある多腕バンディット問題の変種における最適な腕識別について検討する。 非特異な最適アロケーションを処理するために,修正されたトラッキングベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-05-10T12:07:48Z)
• Best Arm Identification in Restless Markov Multi-Armed Bandits [85.55466536537293]
  マルチアームバンディット環境における最適な腕を特定することの問題点について検討する。 決定エンティティは、上限誤差確率を条件として、ベストアームのインデックスをできるだけ早く見つけることを希望する。 このポリシーは、$R$に依存する上限を達成し、$Rtoinfty$として単調に増加しないことを示す。
  論文  参考訳（メタデータ） (2022-03-29T04:58:04Z)
• Best Arm Identification under Additive Transfer Bandits [49.69203462561861]
  提案手法は, 未知であるにもかかわらず, ソースとターゲットMABインスタンスの間には, 付加的な関係があることが知られている。 本稿では,LUCBスタイルのアルゴリズムを理論的に解析し,高い確率で$epsilon$-optimal target armを同定する。
  論文  参考訳（メタデータ） (2021-12-08T02:20:18Z)
• The Countable-armed Bandit with Vanishing Arms [8.099977107670918]
  我々は、数え切れないほど多くの腕を有限個の「型」に分割したバンドイット問題を考える。 非定常分布は、腕の個体群における各腕型の相対的な存在量を支配しており、いわゆる「腕貯水池」である。
  論文  参考訳（メタデータ） (2021-10-23T02:47:55Z)
• Achieving the Pareto Frontier of Regret Minimization and Best Arm Identification in Multi-Armed Bandits [91.8283876874947]
  本稿では,BoBW-lil'UCB$(gamma)$アルゴリズムの設計と解析を行う。 i) RMとBAIの両方の目的に対して最適なアルゴリズムを同時に実行できないことを示す。 また、BoBW-lil'UCB$(gamma)$は、時間複雑性と後悔の点で競合よりも優れていることを示す。
  論文  参考訳（メタデータ） (2021-10-16T17:52:32Z)
• Combinatorial Blocking Bandits with Stochastic Delays [33.65025386998747]
  最近の研究は、各腕の報酬が最後の引き抜きから経過した時間の特別な機能であるマルチアームバンディット問題の自然変化を考察している。 本研究では, 上記のモデルを2つの方向に拡張する。 (i) 各ラウンドで複数の腕を演奏できる汎用的な設定を, 実現可能性制約の下で検討する。 我々は、利用可能な(非ブロック化された)アームの中で、常に最大で期待される報酬を再生する自然な欲求部分集合の近似を厳密に分析する。 腕の期待報酬が不明な場合、上記のアルゴリズムを盗賊に適応させる。
  論文  参考訳（メタデータ） (2021-05-22T02:46:04Z)
• Optimal Best-arm Identification in Linear Bandits [79.3239137440876]
  サンプルの複雑さが既知のインスタンス固有の下界と一致する単純なアルゴリズムを考案する。 既存のベストアーム識別戦略とは異なり、我々のアルゴリズムは武器の数に依存しない停止規則を用いる。
  論文  参考訳（メタデータ） (2020-06-29T14:25:51Z)

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

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