論文の概要: Cooperative Multi-Agent Graph Bandits: UCB Algorithm and Regret Analysis

• arxiv url: http://arxiv.org/abs/2401.10383v1
• Date: Thu, 18 Jan 2024 21:36:17 GMT
• ステータス: 処理完了
• システム内更新日: 2024-01-22 17:33:38.713578
• Title: Cooperative Multi-Agent Graph Bandits: UCB Algorithm and Regret Analysis
• Title（参考訳）: 協調型多エージェントグラフバンディット:ucbアルゴリズムと後悔分析
• Authors: Phevos Paschalidis, Runyu Zhang, and Na Li
• Abstract要約: Zhang, Johansson, Li が導入したグラフバンディット問題のマルチエージェント拡張として,マルチエージェントグラフバンディット問題を定式化する。 上信頼境界(UCB)に基づく学習アルゴリズムであるMulti-G-UCBを提案し、T$のステップに対する期待された後悔が$O(Nlog(T)[sqrtKT + DK])$で束縛されていることを証明した。
• 参考スコア（独自算出の注目度）: 5.02063914741425
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we formulate the multi-agent graph bandit problem as a multi-agent extension of the graph bandit problem introduced by Zhang, Johansson, and Li [CISS 57, 1-6 (2023)]. In our formulation, $N$ cooperative agents travel on a connected graph $G$ with $K$ nodes. Upon arrival at each node, agents observe a random reward drawn from a node-dependent probability distribution. The reward of the system is modeled as a weighted sum of the rewards the agents observe, where the weights capture the decreasing marginal reward associated with multiple agents sampling the same node at the same time. We propose an Upper Confidence Bound (UCB)-based learning algorithm, Multi-G-UCB, and prove that its expected regret over $T$ steps is bounded by $O(N\log(T)[\sqrt{KT} + DK])$, where $D$ is the diameter of graph $G$. Lastly, we numerically test our algorithm by comparing it to alternative methods.
• Abstract（参考訳）: 本稿では,Zhang, Johansson, Li [CISS 57, 1-6 (2023)] が導入したグラフバンディット問題のマルチエージェント拡張として,マルチエージェントグラフバンディット問題を定式化する。 我々の定式化では、$n$の協力エージェントは$k$ノードで接続されたグラフを旅します。 各ノードに着くと、エージェントはノード依存確率分布から引き出されたランダムな報酬を観察する。 システムの報酬は、エージェントが観察する報酬の重み付けされた合計としてモデル化され、重み付けは複数のエージェントが同時に同じノードをサンプリングする際の限界報酬の減少を捉える。 上信頼境界(UCB)に基づく学習アルゴリズムであるMulti-G-UCBを提案し、T$のステップに対する期待された後悔は$O(N\log(T)[\sqrt{KT} + DK])$で、D$はグラフ$G$の直径であることを示す。 最後に,このアルゴリズムを代替手法と比較して数値的に検証する。

関連論文リスト

• Individual Regret in Cooperative Stochastic Multi-Armed Bandits [44.34612921224053]
  ここでは、$A$はアクションの数、$T$は時間軸、$m$はエージェントの数です。 特に、十分な数のエージェントを仮定すると、通信グラフの準最適ギャップと直径に依存しない$tildeO(A)$の後悔境界が得られる。
  論文  参考訳（メタデータ） (2024-11-10T15:54:23Z)
• Cooperative Multi-Agent Constrained Stochastic Linear Bandits [2.099922236065961]
  N$エージェントのネットワークがローカルに通信し、期待されるコストを所定の閾値$tau$で保持しながら、全体的な後悔を最小限に抑える。 我々は、textitMA-OPLBと呼ばれる安全な分散上信頼度有界アルゴリズムを提案し、そのT$ラウンドの後悔に基づく高い確率を確立する。 我々の後悔の限界は次数$ MathcalOleft(fracdtau-c_0fraclog(NT)2sqrtNsqrtTlog (1/|lambda|)であることを示す。
  論文  参考訳（メタデータ） (2024-10-22T19:34:53Z)
• Federated Combinatorial Multi-Agent Multi-Armed Bandits [79.1700188160944]
  本稿では,Banditを用いたオンライン最適化に適したフェデレーション学習フレームワークを提案する。 この設定では、エージェントのアームサブセットは、個々のアーム情報にアクセスせずにこれらのサブセットに対するノイズの多い報酬を観察し、特定の間隔で協力して情報を共有することができる。
  論文  参考訳（メタデータ） (2024-05-09T17:40:09Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Fair Multi-Agent Bandits [14.614647884175657]
  残念な$Oleft(N3 log fracBDelta f(log T) log T right)$, where $f(t)$ は infinity に $t$ で分岐する任意の関数である。 これにより、オーダー$O(f(log T) log T )$と同じ上限を持つ前の結果を大幅に改善するが、エージェントの数に指数関数的に依存する。
  論文  参考訳（メタデータ） (2023-06-07T15:05:53Z)
• Communication-Constrained Bandits under Additive Gaussian Noise [111.06688156723018]
  クライアントが学習者にコミュニケーション制約のあるフィードバックを提供する分散マルチアームバンディットについて検討する。 我々は、この下限を小さな加法係数にマッチさせるマルチフェーズ帯域幅アルゴリズム、$mathtUEtext-UCB++$を提案する。
  論文  参考訳（メタデータ） (2023-04-25T09:31:20Z)
• On the Sample Complexity of Representation Learning in Multi-task Bandits with Global and Local structure [77.60508571062958]
  マルチタスク・バンディット問題に対する最適アーム学習の複雑さについて検討した。 アームは2つのコンポーネントで構成されます。1つはタスク間で共有され(表現と呼ばれます)、もう1つはタスク固有のもの(予測器と呼ばれます)です。 サンプルの複雑さが下界に近づき、最大で$H(Glog(delta_G)+ Xlog(delta_H))$でスケールするアルゴリズムOSRL-SCを考案する。
  論文  参考訳（メタデータ） (2022-11-28T08:40:12Z)
• Collaborative Multi-agent Stochastic Linear Bandits [28.268809091816287]
  我々は,ネットワークを構成するN$エージェントが局所的に通信し,全体的な後悔を最小限に抑える,協調的マルチエージェント線形帯域設定について検討する。 すべてのエージェントは、プレイされたアクションの対応する報酬を観察し、加速されたコンセンサス手順を使用して、すべてのエージェントが取得した報酬の平均の見積もりを計算する。
  論文  参考訳（メタデータ） (2022-05-12T19:46:35Z)
• Adversarial Linear Contextual Bandits with Graph-Structured Side Observations [80.95090605985042]
  学習エージェントは、$d$-dimensionalコンテキストベクトルで提示された後、一連の$k$アクションから繰り返し選択する。 エージェントは選択されたアクションの損失を誘発し、観察するが、観察構造における隣り合うアクションの損失も観察する。 textttEXP3に基づく2つの効率的なアルゴリズムが開発された。
  論文  参考訳（メタデータ） (2020-12-10T15:40:07Z)
• Distributed Bandits: Probabilistic Communication on $d$-regular Graphs [5.33024001730262]
  我々は、$d$-regular graphで定義されたネットワーク上の確率と通信するエージェントに対して、分散マルチエージェントのマルチアームバンディット問題について検討する。 エージェントベースの手法がグループ後悔の最小化にどのように貢献するかを解析し、新しいアッパー信頼境界(UCB)に基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-11-16T04:53:54Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)

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

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