論文の概要: Bridging Rested and Restless Bandits with Graph-Triggering: Rising and Rotting

• arxiv url: http://arxiv.org/abs/2409.05980v1
• Date: Mon, 9 Sep 2024 18:23:07 GMT
• ステータス: 処理完了
• システム内更新日: 2024-09-11 20:02:25.046974
• Title: Bridging Rested and Restless Bandits with Graph-Triggering: Rising and Rotting
• Title（参考訳）: グラフトリガーによるブリジングとレストレスバンド:上昇と回転
• Authors: Gianmarco Genalti, Marco Mussi, Nicola Gatti, Marcello Restelli, Matteo Castiglioni, Alberto Maria Metelli,
• Abstract要約: Graph-Triggered Banditsは、安静と安静のバンディットを一般化するフレームワークである。 本研究は,2種類の単調包帯に焦点をあてる: 立ち上がり, 腕の期待される報酬が増加する, 引き金の数が増える, 回転する, 反対の行動が起こる。
• 参考スコア（独自算出の注目度）: 67.1631453378926
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Rested and Restless Bandits are two well-known bandit settings that are useful to model real-world sequential decision-making problems in which the expected reward of an arm evolves over time due to the actions we perform or due to the nature. In this work, we propose Graph-Triggered Bandits (GTBs), a unifying framework to generalize and extend rested and restless bandits. In this setting, the evolution of the arms' expected rewards is governed by a graph defined over the arms. An edge connecting a pair of arms $(i,j)$ represents the fact that a pull of arm $i$ triggers the evolution of arm $j$, and vice versa. Interestingly, rested and restless bandits are both special cases of our model for some suitable (degenerated) graph. As relevant case studies for this setting, we focus on two specific types of monotonic bandits: rising, where the expected reward of an arm grows as the number of triggers increases, and rotting, where the opposite behavior occurs. For these cases, we study the optimal policies. We provide suitable algorithms for all scenarios and discuss their theoretical guarantees, highlighting the complexity of the learning problem concerning instance-dependent terms that encode specific properties of the underlying graph structure.
• Abstract（参考訳）: Rested and Restless Banditsは、2つのよく知られたバンディット設定で、現実のシーケンシャルな意思決定問題をモデル化するのに役立ちます。 本研究では,グラフトリガーバンド(GTB)を提案する。これは安静時および安静時バンディットを一般化・拡張するための統合フレームワークである。 この設定では、腕の期待される報酬の進化は、腕の上に定義されたグラフによって制御される。 一対のアーム(i,j)$を接続するエッジは、アーム$i$がアーム$j$の進化を引き起こし、その逆も引き起こすという事実を表している。 興味深いことに、レストとレストレスのバンディットはどちらも、適切な(生成された)グラフに対する我々のモデルの特別なケースである。 この設定に関する関連するケーススタディとして、我々は2つの特定のモノトニック・バンディットに焦点を当てる:立ち上がり、腕の期待される報酬が増加するとトリガーの数が増えると増加し、反対の振る舞いが起こると腐る。 これらの場合、最適政策について検討する。 我々は,全てのシナリオに適切なアルゴリズムを提供し,それらの理論的保証について議論し,基礎となるグラフ構造の特定の特性を符号化するインスタンス依存項に関する学習問題の複雑さを強調した。

関連論文リスト

• A General Framework for Clustering and Distribution Matching with Bandit Feedback [81.50716021326194]
  我々は,帯域幅フィードバックを用いたクラスタリングと分散マッチング問題のための一般的なフレームワークを開発する。 誤り確率が$delta$を超えない任意のオンラインアルゴリズムに対して、平均アームプル数に基づいて漸近的でない下界を導出する。
  論文  参考訳（メタデータ） (2024-09-08T12:19:12Z)
• Imprecise Multi-Armed Bandits [0.0]
  そこで本研究では,各アームが,結果空間上の固定された未知の干潟と結びついている,新しいマルチアーム・バンディット・フレームワークを提案する。 次に、これらのクレダル集合によって定義される下述の前提に対応する後悔の概念を定義する。
  論文  参考訳（メタデータ） (2024-05-09T10:58:40Z)
• Indexability of Finite State Restless Multi-Armed Bandit and Rollout Policy [5.64327489637232]
  有限状態定常多武装バンディット問題を考える。 レスレス・バンディットに対する古典的なアプローチは、Whittle Index Policyである。 本稿では,単一武装バンディットモデルの指標基準を検証するための代替手法を提案する。
  論文  参考訳（メタデータ） (2023-04-30T06:53:44Z)
• Best Arm Identification in Restless Markov Multi-Armed Bandits [85.55466536537293]
  マルチアームバンディット環境における最適な腕を特定することの問題点について検討する。 決定エンティティは、上限誤差確率を条件として、ベストアームのインデックスをできるだけ早く見つけることを希望する。 このポリシーは、$R$に依存する上限を達成し、$Rtoinfty$として単調に増加しないことを示す。
  論文  参考訳（メタデータ） (2022-03-29T04:58:04Z)
• Combinatorial Blocking Bandits with Stochastic Delays [33.65025386998747]
  最近の研究は、各腕の報酬が最後の引き抜きから経過した時間の特別な機能であるマルチアームバンディット問題の自然変化を考察している。 本研究では, 上記のモデルを2つの方向に拡張する。 (i) 各ラウンドで複数の腕を演奏できる汎用的な設定を, 実現可能性制約の下で検討する。 我々は、利用可能な(非ブロック化された)アームの中で、常に最大で期待される報酬を再生する自然な欲求部分集合の近似を厳密に分析する。 腕の期待報酬が不明な場合、上記のアルゴリズムを盗賊に適応させる。
  論文  参考訳（メタデータ） (2021-05-22T02:46:04Z)
• Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy [71.17938026619068]
  我々は、腕の総数が膨大であることができるトップ$ k$極端な文脈的包帯問題を研究します。 まず,Inverse Gap Weighting戦略を用いて,非極端に実現可能な設定のアルゴリズムを提案する。 我々のアルゴリズムは、$O(ksqrt(A-k+1)T log (|mathcalF|T))$である。
  論文  参考訳（メタデータ） (2021-02-15T19:10:52Z)
• Online Model Selection: a Rested Bandit Formulation [49.69377391589057]
  静止したバンディット設定における最善のアーム識別問題を紹介し,解析する。 我々は、この問題の後悔の新しい概念を定義し、ゲームの終わりに最小の期待損失を持つ腕を常に再生するポリシーと比較します。 最近のバンディット文献における既知のモデル選択の試みとは異なり、アルゴリズムは問題の特定の構造を利用して、予想される損失関数の未知のパラメータを学習する。
  論文  参考訳（メタデータ） (2020-12-07T08:23:08Z)
• Robustness Guarantees for Mode Estimation with an Application to Bandits [131.21717367564963]
  平均ではなく報酬分布のモードを値とするマルチアームバンディットの理論を導入する。 我々は,我々のアルゴリズムが逆雑音列による腕の摂動に頑健であることを示すシミュレーションで示す。
  論文  参考訳（メタデータ） (2020-03-05T21:29:27Z)

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

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