論文の概要: Decentralized Upper Confidence Bound Algorithms for Homogeneous Multi-Agent Multi-Armed Bandits
- arxiv url: http://arxiv.org/abs/2111.10933v4
- Date: Sat, 28 Dec 2024 08:10:19 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-31 15:59:41.099573
- Title: Decentralized Upper Confidence Bound Algorithms for Homogeneous Multi-Agent Multi-Armed Bandits
- Title(参考訳): 均質なマルチエージェント・マルチアーマッド帯域に対する分散化上部信頼境界アルゴリズム
- Authors: Jingxuan Zhu, Ethan Mulle, Christopher S. Smith, Alec Koppel, Ji Liu,
- Abstract要約: この問題はN$エージェントによって同時に解決され、M$の共通の武器のセットに直面し、同じ武器の報酬分布を共有すると仮定される。
非方向性グラフに対して2つの完全分散上信頼境界(UCB)アルゴリズムを提案する。
提案されたUCB1およびKL-UCBアルゴリズムにより、ネットワーク内の各エージェントは、シングルエージェントよりも対数的後悔をより良く達成できる。
- 参考スコア(独自算出の注目度): 16.038995442397972
- License:
- Abstract: This paper studies a decentralized homogeneous multi-armed bandit problem in a multi-agent network. The problem is simultaneously solved by $N$ agents assuming they face a common set of $M$ arms and share the same arms' reward distributions. Each agent can receive information only from its neighbors, where the neighbor relationships among the agents are described by a fixed graph. Two fully decentralized upper confidence bound (UCB) algorithms are proposed for undirected graphs, respectively based on the classic algorithm and the state-of-the-art Kullback-Leibler upper confidence bound (KL-UCB) algorithm. The proposed decentralized UCB1 and KL-UCB algorithms permit each agent in the network to achieve a better logarithmic asymptotic regret than their single-agent counterparts, provided that the agent has at least one neighbor, and the more neighbors an agent has, the better regret it will have, meaning that the sum is more than its component parts. The same algorithm design framework is also extended to directed graphs through the design of a variant of the decentralized UCB1 algorithm, which outperforms the single-agent UCB1 algorithm.
- Abstract(参考訳): 本稿では,マルチエージェントネットワークにおける分散均質なマルチアームバンディット問題について検討する。
この問題はN$エージェントによって同時に解決され、M$の共通の武器のセットに直面し、同じ武器の報酬分布を共有すると仮定される。
各エージェントは隣人からのみ情報を受け取ることができ、エージェント間の隣人関係は固定グラフによって記述される。
古典的アルゴリズムと最先端のKL-UCBアルゴリズムに基づいて,2つの完全分散上信頼境界(UCB)アルゴリズムを提案する。
提案された分散UPB1およびKL-UCBアルゴリズムは、エージェントが少なくとも1つの隣人を持ち、エージェントがより多くの隣人を持つとすれば、ネットワーク内の各エージェントが1つのエージェントよりも対数的な漸近的後悔を達成することができる。
同じアルゴリズム設計フレームワークは、単一エージェント UCB1 アルゴリズムよりも優れた分散 UCB1 アルゴリズムの変種を設計することで、有向グラフにも拡張される。
関連論文リスト
- A Multiagent Path Search Algorithm for Large-Scale Coalition Structure Generation [61.08720171136229]
結合構造生成はマルチエージェントシステムにおける基本的な計算問題である。
我々はCSGの多エージェントパス探索アルゴリズムであるSALDAEを開発し、連立構造グラフ上で運用する。
論文 参考訳(メタデータ) (2025-02-14T15:21:27Z) - Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
離散部分モジュラー問題を連続的に最適化するために,$textbfMA-OSMA$アルゴリズムを提案する。
また、一様分布を混合することによりKLの発散を効果的に活用する、プロジェクションフリーな$textbfMA-OSEA$アルゴリズムも導入する。
我々のアルゴリズムは最先端OSGアルゴリズムによって提供される$(frac11+c)$-approximationを大幅に改善する。
論文 参考訳(メタデータ) (2025-02-07T15:57:56Z) - Byzantine-Resilient Decentralized Multi-Armed Bandits [25.499420566469098]
エージェント間の情報混合ステップを不整合および極端な値の切り離しで融合するアルゴリズムを開発する。
このフレームワークは、コンピュータネットワークの攻撃者をモデル化したり、攻撃的なコンテンツをレコメンデーターシステムに攻撃したり、金融市場のマニピュレータとして利用することができる。
論文 参考訳(メタデータ) (2023-10-11T09:09:50Z) - Distributed Consensus Algorithm for Decision-Making in Multi-agent
Multi-armed Bandit [7.708904950194129]
動的環境におけるマルチエージェント・マルチアーム・バンディット(MAMAB)問題について検討する。
グラフはエージェント間の情報共有構造を反映し、腕の報酬分布はいくつかの未知の変化点を持つ断片的に定常である。
目的は、後悔を最小限に抑えるエージェントのための意思決定ポリシーを開発することである。
論文 参考訳(メタデータ) (2023-06-09T16:10:26Z) - On the Complexity of Multi-Agent Decision Making: From Learning in Games
to Partial Monitoring [105.13668993076801]
マルチエージェント強化学習(MARL)理論における中心的な問題は、構造条件やアルゴリズムの原理がサンプル効率の学習保証につながるかを理解することである。
本稿では,複数のエージェントを用いた対話型意思決定のための一般的な枠組みとして,この問題について考察する。
マルチエージェント意思決定における統計的複雑性を特徴付けることは、単一エージェント決定の統計的複雑性を特徴付けることと等価であることを示す。
論文 参考訳(メタデータ) (2023-05-01T06:46:22Z) - Optimal Clustering with Bandit Feedback [57.672609011609886]
本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。
これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。
合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
論文 参考訳(メタデータ) (2022-02-09T06:05:05Z) - Distributed Bandits with Heterogeneous Agents [38.90376765616447]
本稿では、M$エージェントが協力して$K$武器の盗賊問題を解くマルチエージェントの盗賊設定に取り組む。
本稿では,ucbo と AAE の2つの学習アルゴリズムを提案する。
Oleft(sum_i:tildeDelta_i>0 log T/tildeDelta_iright)$, $tildeDelta_i$は報酬平均の最小部分最適差である。
論文 参考訳(メタデータ) (2022-01-23T20:04:15Z) - Mean-based Best Arm Identification in Stochastic Bandits under Reward
Contamination [80.53485617514707]
本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。
具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
論文 参考訳(メタデータ) (2021-11-14T21:49:58Z) - Bayesian Algorithms for Decentralized Stochastic Bandits [12.350564981588063]
我々は,ネットワーク上で接続された$K$アームと$N$エージェントを用いた分散協調型マルチエージェントマルチエージェントバンディット問題について検討した。
我々のモデルでは、各アームの報酬分布は全てのエージェントで同じであり、報酬はエージェントや時間経過とともに独立して引き出される。
目標は、ネットワーク全体の平均的な累積的後悔を最小限にすることである。
論文 参考訳(メタデータ) (2020-10-20T19:14:20Z) - F2A2: Flexible Fully-decentralized Approximate Actor-critic for
Cooperative Multi-agent Reinforcement Learning [110.35516334788687]
分散マルチエージェント強化学習アルゴリズムは複雑なアプリケーションでは実践的でないことがある。
本稿では,大規模で汎用的なマルチエージェント設定を扱える,柔軟な完全分散型アクター批判型MARLフレームワークを提案する。
当社のフレームワークは,大規模環境におけるスケーラビリティと安定性を実現し,情報伝達を低減できる。
論文 参考訳(メタデータ) (2020-04-17T14:56:29Z) - Distributed Cooperative Decision Making in Multi-agent Multi-armed
Bandits [6.437761597996503]
複数のエージェントが同じバンディット(MAB)に直面している分散意思決定問題について検討する。
我々は,各アームの平均報酬を協調的に推定するための動的,コンセンサスに基づく分散推定アルゴリズムを設計する。
両アルゴリズムが中心核融合センターの性能に近いグループ性能を達成することを示す。
論文 参考訳(メタデータ) (2020-03-03T03:20:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。