論文の概要: Decentralized Multi-Armed Bandits Can Outperform Centralized Upper Confidence Bound Algorithms

• arxiv url: http://arxiv.org/abs/2111.10933v2
• Date: Fri, 6 Oct 2023 02:46:01 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-13 17:23:06.754096
• Title: Decentralized Multi-Armed Bandits Can Outperform Centralized Upper Confidence Bound Algorithms
• Title（参考訳）: 集中型マルチアームバンディットは集中型上信頼度バウンドアルゴリズムに勝る
• Authors: Jingxuan Zhu, Ethan Mulle, Christopher Salomon Smith, Alec Koppel, Ji Liu
• Abstract要約: この問題は、NエージェントがMアームの共通集合に直面し、同じアームの報酬分布を共有することを仮定して同時に解決される。 古典的アッパー信頼境界(UCB)アルゴリズムと最先端のKL-UCBアルゴリズムに基づいて,2つの完全に分散化されたマルチアームバンディットアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 17.207371368421764
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper studies a decentralized 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 an undirected graph. Two fully decentralized multi-armed bandit algorithms are proposed, respectively based on the classic upper confidence bound (UCB) algorithm and the state-of-the-art KL-UCB algorithm. The proposed decentralized 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.
• Abstract（参考訳）: 本稿では,マルチエージェントネットワークにおける分散マルチアームドバンディット問題について検討する。 この問題は、NエージェントがMアームの共通集合に直面し、同じアームの報酬分布を共有することを仮定して同時に解決される。 各エージェントは隣人からのみ情報を受け取ることができ、エージェント間の隣人関係は無向グラフによって記述される。 古典的アッパー信頼境界(UCB)アルゴリズムと最先端KL-UCBアルゴリズムに基づいて、2つの完全に分散化されたマルチアームバンドアルゴリズムを提案する。 提案する分散アルゴリズムにより,ネットワーク内の各エージェントは,そのエージェントが少なくとも1つの隣人を持ち,そのエージェントが持つ隣人が多くなるほど,その合計がコンポーネント部分以上である場合において,ネットワーク内の各エージェントに対して,より優れた対数的漸近的後悔を実現することができる。

関連論文リスト

• 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)

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

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