論文の概要: Decentralized Multi-Armed Bandit Can Outperform Classic Upper Confidence Bound: A Homogeneous Case over Strongly Connected Graphs
- arxiv url: http://arxiv.org/abs/2111.10933v3
- Date: Sat, 23 Mar 2024 03:41:10 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-28 23:39:03.218215
- Title: Decentralized Multi-Armed Bandit Can Outperform Classic Upper Confidence Bound: A Homogeneous Case over Strongly Connected Graphs
- Title(参考訳): 分散化されたマルチArmed Banditは、古典的アッパー信頼境界を上回り得る: 強い連結グラフ上の均一なケース
- Authors: Jingxuan Zhu, Ji Liu,
- Abstract要約: 本稿では、複数のエージェントのネットワークが同じアームの集合に直面する均質な分散化されたマルチアームバンディット問題について検討する。
隣接関係を有向グラフで記述したマルチエージェントネットワークに対して,完全分散上界信頼度(UCB)アルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 9.84486119211443
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper studies a homogeneous decentralized multi-armed bandit problem, in which a network of multiple agents faces the same set of arms, and each agent aims to minimize its own regret. A fully decentralized upper confidence bound (UCB) algorithm is proposed for a multi-agent network whose neighbor relations are described by a directed graph. It is shown that the decentralized algorithm guarantees each agent to achieve a lower logarithmic asymptotic regret compared to the classic UCB algorithm, provided the neighbor graph is strongly connected. The improved asymptotic regret upper bound is reciprocally related to the maximal size of a local neighborhood within the network. The roles of graph connectivity, maximum local degree, and network size are analytically elucidated in the expression of regret.
- Abstract(参考訳): 本稿では,複数のエージェントのネットワークが同一のアームの集合に直面し,各エージェントが自身の後悔を最小限に抑える,均質な分散化されたマルチアームバンディット問題について検討する。
隣接関係を有向グラフで記述したマルチエージェントネットワークに対して, 完全分散上信頼境界(UCB)アルゴリズムを提案する。
この分散化アルゴリズムは, 隣接するグラフが強く連結されている場合, 従来のUTBアルゴリズムと比較して, 各エージェントが対数漸近的不一致を達成することを保証している。
改善された漸近的後悔の上界は、ネットワーク内の局所的近傍の最大サイズと相互に関連している。
グラフ接続,最大局所次数,ネットワークサイズの役割は,後悔の表現において解析的に解明される。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。