論文の概要: 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 アルゴリズムの変種を設計することで、有向グラフにも拡張される。

関連論文リスト

• TSC: A Simple Two-Sided Constraint against Over-Smoothing [17.274727377858873]
  グラフ畳み込みニューラルネットワーク(GCN)のための単純な2次元制約(TSC)を導入する。 ランダムマスキングは、隣人からの情報の集約の度合いを調整するために、表現行列の列に作用する。 表現行列の行に適用される対照的な制約は、ノードの識別可能性を高める。
  論文  参考訳（メタデータ） (2024-08-06T12:52:03Z)
• Lower Bounds and Optimal Algorithms for Non-Smooth Convex Decentralized Optimization over Time-Varying Networks [57.24087627267086]
  通信ネットワークのノード間で分散的に格納された凸関数の総和を最小化するタスクについて検討する。 この問題を解決するのに必要な分散通信数と(サブ)漸進計算の下位境界が確立されている。 我々は,これらの下界に適合する最初の最適アルゴリズムを開発し,既存の最先端技術と比較して理論性能を著しく向上させる。
  論文  参考訳（メタデータ） (2024-05-28T10:28:45Z)
• Distributed Optimization via Kernelized Multi-armed Bandits [6.04275169308491]
  分散最適化問題を異種報酬設定によるマルチエージェントカーネル化されたマルチアームバンディット問題としてモデル化する。 我々は,カーネルの一般的なクラスに対して,サブ線形なリフレッシュバウンドを実現するために,完全に分散化されたアルゴリズムであるマルチエージェントIGP-UCB(MA-IGP-UCB)を提案する。 また,Multi-agent Delayed IGP-UCB (MAD-IGP-UCB)アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-07T21:57:48Z)
• Optimal Clustering with Bandit Feedback [57.672609011609886]
  本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。 これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。 合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
  論文  参考訳（メタデータ） (2022-02-09T06:05:05Z)
• Acceleration in Distributed Optimization Under Similarity [72.54787082152278]
  集中ノードを持たないエージェントネットワーク上での分散(強い凸)最適化問題について検討する。 $varepsilon$-solutionは$tildemathcalrhoObig(sqrtfracbeta/mu (1-)log1/varepsilonbig)$通信ステップ数で達成される。 この速度は、関心のクラスに適用される分散ゴシップ-アルゴリズムの、初めて(ポリログ因子まで)より低い複雑性の通信境界と一致する。
  論文  参考訳（メタデータ） (2021-10-24T04:03:00Z)
• Multi-resource allocation for federated settings: A non-homogeneous Markov chain model [2.552459629685159]
  連合設定において、エージェントは中央エージェントまたはサーバと協調し、エージェントが互いに情報を共有しない最適化問題を解決する。 本稿では,アジェント間通信のない単一共有リソースのフェデレーション設定における最適化問題のクラスを解決するために,AIMDアルゴリズムを簡単な方法で変更する方法について述べる。 シングルリソースのアルゴリズムを、スマートシティや共有エコノミー、その他多くのアプリケーションに出現する複数の異種共有リソースに拡張する。
  論文  参考訳（メタデータ） (2021-04-26T19:10:00Z)
• Reinforced Neighborhood Selection Guided Multi-Relational Graph Neural Networks [68.9026534589483]
  RioGNNはReinforceed, recursive, flexible neighborhood selection guided multi-relational Graph Neural Network architectureである。 RioGNNは、各関係の個々の重要性の認識により、説明性を高めた差別的なノード埋め込みを学ぶことができる。
  論文  参考訳（メタデータ） (2021-04-16T04:30:06Z)
• Bayesian Algorithms for Decentralized Stochastic Bandits [12.350564981588063]
  我々は,ネットワーク上で接続された$K$アームと$N$エージェントを用いた分散協調型マルチエージェントマルチエージェントバンディット問題について検討した。 我々のモデルでは、各アームの報酬分布は全てのエージェントで同じであり、報酬はエージェントや時間経過とともに独立して引き出される。 目標は、ネットワーク全体の平均的な累積的後悔を最小限にすることである。
  論文  参考訳（メタデータ） (2020-10-20T19:14:20Z)
• Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networks [50.42141893913188]
  本稿では,ニューラルネットワークを用いた大規模AUCのための分散変数について検討する。 我々のモデルは通信ラウンドをはるかに少なくし、理論上はまだ多くの通信ラウンドを必要としています。 いくつかのデータセットに対する実験は、我々の理論の有効性を示し、我々の理論を裏付けるものである。
  論文  参考訳（メタデータ） (2020-05-05T18:08:23Z)
• A Decentralized Policy with Logarithmic Regret for a Class of Multi-Agent Multi-Armed Bandit Problems with Option Unavailability Constraints and Stochastic Communication Protocols [0.0]
  本稿では,複数の移動体エージェントが,帯域幅と呼ばれる空間分散プロセスの集合からサンプリングして報酬を受け取る,マルチアーム・バンディット(MAB)問題について考察する。 目標は、すべてのエージェントに対する総累積報酬を最大化するために、オプションの可用性とエージェント間通信の制約を条件として、各エージェントに対して分散されたポリシーを定式化することである。 我々の知る限り、これは通信制約のある非完全連結空間グラフに対する、このような分散化ポリシーとしては初めてのものである。
  論文  参考訳（メタデータ） (2020-03-29T08:12:49Z)
• Quantized Decentralized Stochastic Learning over Directed Graphs [52.94011236627326]
  有向グラフ上で通信する計算ノード間でデータポイントが分散される分散学習問題を考える。 モデルのサイズが大きくなるにつれて、分散学習は、各ノードが隣人にメッセージ(モデル更新)を送信することによる通信負荷の大きなボトルネックに直面します。 本稿では,分散コンセンサス最適化におけるプッシュサムアルゴリズムに基づく有向グラフ上の量子化分散学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-02-23T18:25:39Z)

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

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