論文の概要: Heterogeneous Multi-agent Multi-armed Bandits on Stochastic Block Models

• arxiv url: http://arxiv.org/abs/2502.08003v1
• Date: Tue, 11 Feb 2025 22:57:19 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-13 13:47:47.357160
• Title: Heterogeneous Multi-agent Multi-armed Bandits on Stochastic Block Models
• Title（参考訳）: 確率ブロックモデル上での不均一なマルチエージェントマルチアームバンド
• Authors: Mengfan Xu, Liren Shan, Fatemeh Ghaffari, Xuchuang Wang, Xutong Liu, Mohammad Hajiesmaili,
• Abstract要約: ブロックモデルにより誘導されるクラスタ構造を持つ異種マルチエージェント・マルチエージェント・バンドイット問題について検討する。 本稿では,既知のクラスタ設定と未知のクラスタ設定の両方に適用可能な新しいアルゴリズムを提案する。 ガウス代入の報酬の下で、最適のインスタンス依存後悔上限$logT$を導出する。
• 参考スコア（独自算出の注目度）: 8.668244156922809
• License:
• Abstract: We study a novel heterogeneous multi-agent multi-armed bandit problem with a cluster structure induced by stochastic block models, influencing not only graph topology, but also reward heterogeneity. Specifically, agents are distributed on random graphs based on stochastic block models - a generalized Erdos-Renyi model with heterogeneous edge probabilities: agents are grouped into clusters (known or unknown); edge probabilities for agents within the same cluster differ from those across clusters. In addition, the cluster structure in stochastic block model also determines our heterogeneous rewards. Rewards distributions of the same arm vary across agents in different clusters but remain consistent within a cluster, unifying homogeneous and heterogeneous settings and varying degree of heterogeneity, and rewards are independent samples from these distributions. The objective is to minimize system-wide regret across all agents. To address this, we propose a novel algorithm applicable to both known and unknown cluster settings. The algorithm combines an averaging-based consensus approach with a newly introduced information aggregation and weighting technique, resulting in a UCB-type strategy. It accounts for graph randomness, leverages both intra-cluster (homogeneous) and inter-cluster (heterogeneous) information from rewards and graphs, and incorporates cluster detection for unknown cluster settings. We derive optimal instance-dependent regret upper bounds of order $\log{T}$ under sub-Gaussian rewards. Importantly, our regret bounds capture the degree of heterogeneity in the system (an additional layer of complexity), exhibit smaller constants, scale better for large systems, and impose significantly relaxed assumptions on edge probabilities. In contrast, prior works have not accounted for this refined problem complexity, rely on more stringent assumptions, and exhibit limited scalability.
• Abstract（参考訳）: 確率ブロックモデルによって誘導されるクラスタ構造を持つ新しい異種マルチエージェントのバンドイット問題について検討し、グラフトポロジーだけでなく、不均一性にも影響を及ぼす。 具体的には、エージェントは確率ブロックモデルに基づいてランダムグラフ上に分散される - 異種エッジ確率を持つ一般化されたエルドス・レニーモデル:エージェントはクラスタ(未知または未知)にグループ化される。 さらに、確率ブロックモデルにおけるクラスタ構造は、我々の異種報酬も決定する。 同じアームの逆流分布は、異なるクラスタ内のエージェントによって異なるが、クラスタ内では一貫しており、均一な設定と不均一な設定を統一し、報酬はこれらの分布から独立したサンプルである。 目的は、すべてのエージェントに対するシステム全体の後悔を最小限にすることである。 そこで本研究では,既知のクラスタ設定と未知のクラスタ設定の両方に適用可能な新しいアルゴリズムを提案する。 このアルゴリズムは、平均的なコンセンサスアプローチと、新たに導入された情報集約と重み付け手法を組み合わせることで、UCB型戦略を実現する。 グラフのランダム性を考慮し、報酬やグラフからクラスタ内(均一)とクラスタ間(異種)の情報の両方を活用し、未知のクラスタ設定に対してクラスタ検出を組み込む。 我々は、準ガウス報酬の下で、最適のインスタンス依存後悔上界を$\log{T}$に導出する。 重要なことは、我々の後悔の限界はシステムの不均一性の度合い(さらなる複雑性の層)を捉え、より小さな定数を示し、大規模システムにとってより良いスケールを示し、エッジ確率に関する非常に緩やかな仮定を課す。 対照的に、以前の研究は、この洗練された問題複雑さを考慮せず、より厳密な仮定に依存し、限られたスケーラビリティを示している。

関連論文リスト

• HeNCler: Node Clustering in Heterophilous Graphs through Learned Asymmetric Similarity [55.27586970082595]
  HeNClerは、Heterophilous Node Clusteringの新しいアプローチである。 HeNClerは異種グラフコンテキストにおけるノードクラスタリングタスクの性能を大幅に向上させることを示す。
  論文  参考訳（メタデータ） (2024-05-27T11:04:05Z)
• Heteroskedastic Tensor Clustering [20.979358557219953]
  我々は、$mathsfHightext-orderHeteroClustering$$mathsfHHC$という2段階の手法を提案する。 まず、$mathsfThresholdedDeflatedtext-HeteroPCA$と呼ばれる新しいスペクトルアルゴリズムを使ってテンソル部分空間の推定を行い、続いてクラスタノードを取得するためにおよそ$k$-meansを実行する。 我々のアルゴリズムは、SNRが計算限界を超える限り、正確なクラスタリングを確実に達成する。
  論文  参考訳（メタデータ） (2023-11-04T02:50:40Z)
• Gap-Free Clustering: Sensitivity and Robustness of SDP [6.996002801232415]
  ブロックモデル(SBM)におけるグラフクラスタリングについて,大クラスタと小クラスタの両方の存在下で検討した。 以前の凸緩和アプローチは正確な回復を達成するため、$o(sqrtn)$の小さなクラスタを許可しないか、最小の回復クラスタと最大の非回復クラスタの間のサイズギャップを必要とする。 本研究では,これらの要求を除去し,クラスタサイズによらず,大規模クラスタを確実に復元する半定値プログラミング(SDP)に基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-08-29T21:27:21Z)
• Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [69.15976031704687]
  IAC (Instance-Adaptive Clustering, インスタンス適応クラスタリング) を提案する。 IACは$ MathcalO(n, textpolylog(n) $の計算複雑性を維持しており、大規模問題に対してスケーラブルで実用的なものである。
  論文  参考訳（メタデータ） (2023-06-18T08:46:06Z)
• Optimal Clustering with Bandit Feedback [57.672609011609886]
  本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。 これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。 合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
  論文  参考訳（メタデータ） (2022-02-09T06:05:05Z)
• Personalized Federated Learning via Convex Clustering [72.15857783681658]
  本稿では,局所凸型ユーザコストを用いた個人化フェデレーション学習のためのアルゴリズム群を提案する。 提案するフレームワークは,異なるユーザのモデルの違いをペナル化する凸クラスタリングの一般化に基づいている。
  論文  参考訳（メタデータ） (2022-02-01T19:25:31Z)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  クラスタリングは教師なし学習における基本的なプリミティブである。 最近の研究は、低次手法のクラスに対する低い境界を確立している。 意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
  論文  参考訳（メタデータ） (2021-12-07T18:50:17Z)
• Correlation Clustering Reconstruction in Semi-Adversarial Models [70.11015369368272]
  相関クラスタリングは多くのアプリケーションにおいて重要なクラスタリング問題である。 本研究では,ランダムノイズや対向的な修正によって崩壊した潜伏クラスタリングを再構築しようとする,この問題の再構築版について検討する。
  論文  参考訳（メタデータ） (2021-08-10T14:46:17Z)
• Exact Clustering in Tensor Block Model: Statistical Optimality and Computational Limit [10.8145995157397]
  高階クラスタリングは、マルチウェイデータセットの異種サブ構造を特定することを目的とする。 非計算と問題の性質は統計学と統計学の両方に重大な課題をもたらす。
  論文  参考訳（メタデータ） (2020-12-18T00:48:27Z)
• Blocked Clusterwise Regression [0.0]
  我々は、各ユニットが複数の潜伏変数を持つことを可能にすることで、離散的非観測的不均一性に対する以前のアプローチを一般化する。 我々は,クラスタの過剰な数のクラスタリングの理論に寄与し,この設定に対する新たな収束率を導出する。
  論文  参考訳（メタデータ） (2020-01-29T23:29:31Z)

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

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