論文の概要: 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$の直径であることを示す。
最後に,このアルゴリズムを代替手法と比較して数値的に検証する。
関連論文リスト
- Finite-Time Frequentist Regret Bounds of Multi-Agent Thompson Sampling
on Sparse Hypergraphs [11.024467775280193]
マルチエージェントマルチアーム・バンドイット(MAMAB)問題について検討し,$m$エージェントを$rho$オーバーラップするグループに分解する。
そこで本稿では,MATS の効率的な変種として$epsilon$-exploring Multi-Agent Thompson Sampling (epsilon$-MATS) アルゴリズムを提案する。
我々は、$epsilon$-MATSが、時間地平線と局所アームサイズの両方においてサブ線形である最悪の頻繁な後悔境界を達成することを証明した。
論文 参考訳(メタデータ) (2023-12-24T21:41:01Z) - 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) - Multi-armed Bandit Learning on a Graph [0.0]
そこで,エージェントがグラフの上を移動して,異なるノードから収集した報酬を最大化するグラフバンドイットと呼ばれるMABの拡張について検討する。
我々は,楽観主義の原理を用いて長期探査・探索のバランスをとる学習アルゴリズムG-UCBを設計する。
提案アルゴリズムは,ノード数として$O(sqrt|S|Tlog(T)+D|S|log T)$学習後悔を実現する。
論文 参考訳(メタデータ) (2022-09-20T02:31:42Z) - Causal Bandits for Linear Structural Equation Models [58.2875460517691]
本稿では,因果図形モデルにおける最適な介入順序を設計する問題について検討する。
グラフの構造は知られており、ノードは$N$である。
頻繁性(UCBベース)とベイズ的設定に2つのアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-08-26T16:21:31Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。