Fugu-MT 論文翻訳(概要): Graph-SND: Sparse Aggregation for Behavioral Diversity in Multi-Agent Reinforcement Learning

論文の概要: Graph-SND: Sparse Aggregation for Behavioral Diversity in Multi-Agent Reinforcement Learning

arxiv url: http://arxiv.org/abs/2605.05020v1
Date: Wed, 06 May 2026 15:18:42 GMT
ステータス: 翻訳完了
システム内更新日: 2026-05-07 18:41:07.899497
Title: Graph-SND: Sparse Aggregation for Behavioral Diversity in Multi-Agent Reinforcement Learning
Title（参考訳）: グラフSND:マルチエージェント強化学習における行動多様性のためのスパースアグリゲーション
Abstract要約: グラフSNDを導入し、任意のグラフのエッジ上の重み付き平均をG$で置き換える。固定されたスパースグラフに対して、拡大器のフォワード・インデックス歪み境界と低ランク距離構造の下でのスペクトル改善を証明した。ランダム $d$-正則グラフに対して、非条件確率 $widetildemathcalO(D_max/sqrtn)$bound を証明する。 VMASでは、リカバリ、不偏性、濃度、壁時計のスケーリングを検証する。
参考スコア（独自算出の注目度）: 0.0
License: http://creativecommons.org/licenses/by/4.0/
Abstract: System Neural Diversity (SND) measures behavioral heterogeneity in multi-agent reinforcement learning by averaging pairwise distances over all $\binom{n}{2}$ agent pairs, making each call quadratic in team size. We introduce Graph-SND, which replaces this complete-graph average with a weighted average over the edges of an arbitrary graph $G$. Three regimes follow: $G=K_n$ recovers SND exactly; a fixed sparse $G$ defines a localized diversity measure at $O(|E|)$ cost; and random edge samples yield an unbiased Horvitz-Thompson estimator and a normalized sample mean with $O(1/\sqrt{m})$ concentration in the sampled edge count $m$. For fixed sparse graphs we prove forwarding-index distortion bounds for expanders and a spectral refinement under low-rank distance structure; for random $d$-regular graphs we prove an unconditional probabilistic $\widetilde{\mathcal{O}}(D_{\max}/\sqrt{n})$ bound. On VMAS we verify recovery, unbiasedness, concentration, and wall-clock scaling, with a PettingZoo TVD panel checking non-Gaussian transfer. In a 500-iteration $n=100$ PPO run, Bernoulli-$0.1$ Graph-SND tracks full SND while reducing per-call metric time by about $10\times$, and frozen-policy GPU timing up to $n=500$ follows the predicted $\binom{n}{2}/|E|$ speedup. Random $d$-regular expanders empirically achieve $\mathrm{SND}_{G}^{\mathrm{u}}/\mathrm{SND} \in [0.9987, 1.0013]$ at $Θ(n \log n)$ edges. In DiCo diversity control at $n=50$, Bernoulli-$0.1$ Graph-SND preserves set-point tracking with paired reward differences indistinguishable from zero across nine matched cells while cutting per-call metric cost by ${\sim}9.5\times$. Together, these results show that the SND aggregation bottleneck can be removed without changing the metric's semantics, yielding a drop-in sparse alternative that scales beyond complete-graph SND and supports both passive measurement and closed-loop diversity control.
Abstract（参考訳）: システムニューラルダイバーシティ(SND)は、すべての$\binom{n}{2}$エージェントペアのペア距離を平均化することにより、マルチエージェント強化学習における振る舞いの不均一性を測定する。グラフSNDを導入し、この全グラフ平均を任意のグラフのエッジ上の重み付き平均に置き換える。固定スパース$G$は局所的多様性尺度を$O(|E|)$コストで定義し、ランダムエッジサンプルは非バイアスのホルヴィッツ=トンプソン推定器、正規化されたサンプル平均は$O(1/\sqrt{m})$濃度を$m$とする。固定されたスパースグラフに対しては、拡張子に対するフォワード・インデックスの歪み境界と低ランク距離構造の下でのスペクトル洗練を証明し、ランダム$d$正則グラフに対しては、非条件確率$\widetilde{\mathcal{O}}(D_{\max}/\sqrt{n})$バウンドを証明する。 VMASでは、非ガウス移動をチェックするPettingZoo TVDパネルを用いて、回復、不偏性、濃度、壁面のスケーリングを検証する。 500-iteration $n=100$ PPO runでは、Bernolli-$0.1$ Graph-SNDがフルSNDをトラックし、コール単位のメトリックタイムを約10\times$に削減し、フリーズポリシーGPUのタイミングを最大$n=500$は予測された$\binom{n}{2}/|E|$のスピードアップに従っている。 Random $d$-regular expander は、経験的に $\mathrm{SND}_{G}^{\mathrm{u}}/\mathrm{SND} \in [0.9987,1.0013]$ at $(n \log n)$ edges を達成する。 In DiCo diversity control at $n=50$, Bernoulli-$0.1$ Graph-SND maintains set-point tracking with paired reward difference indistinguishable from zero from nine matched cells while cut per-call metric cost by ${\sim}9.5\times$. これらの結果から、SND凝集ボトルネックは、計量のセマンティクスを変えることなく除去でき、完全なグラフSNDを超えてスケールし、受動的測定と閉ループの多様性制御の両方をサポートするドロップインスパース(英語版)の代替となることを示した。

関連論文リスト

On Large-Scale Multiple Testing Over Networks: A Non-Asymptotic Approach [0.0]
N$のサイトは、厳しい予算の下でグローバルな偽発見率(FDR)を制御するよう求められている。我々は,BONuS-GAがノード単位の中間から大きいサンプルで,CFGAが小さなサンプルでは適応帯域幅で支配的であることを示す。すべての変種は、e-CFGAの$O(GreebarRlog m)$レポートラウンドまで、$O(sqrtmlog m)$通信予算を維持している。
論文参考訳（メタデータ） (2026-09-12T22:05:15Z)
Quantum Query Complexity of Persistence Statistics in Graph Zigzags [2.895030292351388]
本研究では、スナップショット・アジャシエンスビットからジグザグバー寿命のスカラーサマリーを推定するクエリ複雑性について検討した。ランクがグラフの回路ランクであるグラフの場合、非線形バーコード関数はエッジと成分数の平均となる。すべての固定パワーウェイトに対して$xr$,$rge2$、均一ウィンドウ平均では、最悪のケースの複雑さは$widetilde(nsqrt m/varepsilon)$ Quantumと$(n2m)$ classicalである。
論文参考訳（メタデータ） (2026-09-05T02:16:28Z)
Proving the Limited Scalability of Centralized Distributed Optimization via a New Lower Bound Construction [57.93371273485736]
我々は、すべての労働者が同一の分布にアクセスする均質な(すなわちd.d.)場合であっても、すべての労働者が非バイアス付き境界 LDeltaepsilon2,$$$$$ のポリ対数的により良いポリ対数を求める集中型分散学習環境を考える。
論文参考訳（メタデータ） (2025-06-30T13:27:39Z)
Improved convergence rate of kNN graph Laplacians [11.93971616098517]
k$NNグラフの一般クラスで、グラフ親和性は$W_ij = epsilon-d/2 である。制限多様体作用素に対する$k$NNグラフ Laplacian の点収束性を証明する。
論文参考訳（メタデータ） (2024-10-30T17:01:00Z)
Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP [58.13930707612128]
この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
論文参考訳（メタデータ） (2022-12-01T15:57:58Z)
DADAO: Decoupled Accelerated Decentralized Asynchronous Optimization [0.0]
DADAOは、L$-smooth と $mu$-strongly convex 関数の和を最小化する最初の分散化、高速化、非同期化、プライマリ化、一階述語アルゴリズムである。我々のアルゴリズムは、$mathcalO(nsqrtchisqrtfracLmulog(frac1epsilon)$ localと$mathcalO(nsqrtchisqrtfracLmulog()のみを必要とすることを示す。
論文参考訳（メタデータ） (2022-07-26T08:47:54Z)
Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions [51.19236668224547]
テンソルの低階近似について検討し,テンソルトレインとタッカー分解に着目した。テンソル列車の分解には、小さなビクリテリアランクを持つビクリテリア$(1 + eps)$-approximationアルゴリズムと、O(q cdot nnz(A))$ランニングタイムを与える。さらに、任意のグラフを持つテンソルネットワークにアルゴリズムを拡張します。
論文参考訳（メタデータ） (2022-07-15T11:55:09Z)
(Nearly) Optimal Private Linear Regression via Adaptive Clipping [22.639650869444395]
固定されたガウス型分布から各データ点をサンプリングする微分プライベート線形回帰問題について検討する。本稿では,各イテレーションの点を置換せずにサンプリングする1パスのミニバッチ勾配勾配法(DP-AMBSSGD)を提案し,解析する。
論文参考訳（メタデータ） (2022-07-11T08:04:46Z)
Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning [77.22019100456595]
通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
論文参考訳（メタデータ） (2022-06-16T17:10:57Z)
Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization [59.65871549878937]
実用的な単一ループ加速勾配追跡には$O(fracgamma1-sigma_gamma)2sqrtfracLepsilon)$が必要であることを証明している。我々の収束率は$O(frac1epsilon5/7)$と$O(fracLmu)5/7frac1(1-sigma)1.5logfrac1epsilon)$よりも大幅に改善した。
論文参考訳（メタデータ） (2021-04-06T15:34:14Z)
Sparse sketches with small inversion bias [79.77110958547695]
逆バイアスは、逆の共分散に依存する量の推定を平均化するときに生じる。本研究では、確率行列に対する$(epsilon,delta)$-unbiased estimatorという概念に基づいて、逆バイアスを解析するためのフレームワークを開発する。スケッチ行列 $S$ が密度が高く、すなわちサブガウスのエントリを持つとき、$(epsilon,delta)$-unbiased for $(Atop A)-1$ は $m=O(d+sqrt d/ のスケッチを持つ。
論文参考訳（メタデータ） (2020-11-21T01:33:15Z)
Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
論文参考訳（メタデータ） (2020-05-29T07:20:35Z)

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

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