Learning Mean Field Control on Sparse Graphs¶

会议: ICML2025
arXiv: 2501.17079
作者: Christian Fabian, Kai Cui, Heinz Koeppl (TU Darmstadt) 代码: 未公开
领域: reinforcement_learning
关键词: mean field control, sparse graphs, multi-agent reinforcement learning, local weak convergence, graphon

一句话总结¶

提出 Local Weak Mean Field Control (LWMFC) 框架，利用局部弱收敛理论将平均场控制扩展到幂律系数 γ>2 的极稀疏图上，配合两系统近似与可扩展 RL 算法，在合成和真实网络上大幅超越基于 Lp graphon 和 graphex 的方法。

研究背景与动机¶

问题定义¶

大规模多智能体网络中的协作优化问题（Mean Field Control）：N 个智能体通过图 \(G_N\) 连接，共同最大化全局目标 \(J^N(\pi) = \sum_{t=1}^{T} r(\mu_t^N)\)，其中 \(\mu_t^N\) 是经验平均场分布。

现有方法的局限¶

Graphon MFG/MFC：仅适用于稠密图（完全图极限），大量真实网络不满足此假设

Lp Graphon MFG (LPGMFG)：扩展到中等稀疏图，但仍要求平均度趋向无穷

Graphex MFG (GXMFG)：同样限于平均期望度发散到无穷的图序列

这三类方法均不覆盖幂律系数 γ>2 的稀疏网络（如互联网、共著网络、生物网络），因为这些网络的平均期望度是有限的。

核心动机¶

许多高实际价值的经验网络（互联网 γ≈2.1-2.5、共著图、YouTube 社交网络等）远比上述方法能处理的拓扑稀疏得多。在幂律图 γ=2.5 中，约 96% 的节点度数≤5，但这些低度节点仅占期望度的约 68%，高度节点尾部的重要性使得简单截断不可行。

方法详解¶

1. 局部弱收敛（Local Weak Convergence）¶

核心图论工具：图序列 \((G_N)_N\) 在局部弱意义下收敛到随机元素 \(G\)，即对所有连续有界函数 \(f\)：

\[\lim_{N\to\infty} \frac{1}{N} \sum_{i \in [N]} f(C_{v_i}(G_N)) = \mathbb{E}[f(G)] \quad \text{in probability}\]

满足此收敛性的图模型包括：

Configuration Model (CM)：任意度序列的随机多图
Barabási-Albert 模型：优先连接，生成幂律系数恰为3的网络
Chung-Lu (CL) 模型：节点权重 \(w_i\) 决定连接概率 \(w_i \cdot w_j / \bar{w}\)，可高效生成 γ>2 的幂律网络

关键优势：局部弱收敛覆盖有限平均期望度的图序列，即 Lp graphon 和 graphex 无法处理的区域。

2. LWMFC 有限模型与极限系统¶

有限模型：N 个智能体按度数 k 分组，共享策略 \(\pi_t^k\)。度为 k 的经验平均场定义为：

\[\mu_t^{N,k} = \frac{1}{|V_N^k|} \sum_{i: v_i \in V_N^k} \delta_{X_{i,t}^N}\]

每个智能体的转移动力学取决于自身状态、动作和邻域状态分布 \(\mathbb{G}_{i,t}^N\)。

极限系统（\(N \to \infty\)）：每个度 k 的平均场按确定性方程演化：

\[\mu_{t+1}^k = \sum_{x \in \mathcal{X}} \mu_t^k(x) \sum_{G \in \mathcal{G}^k} P_\pi(\mathbb{G}_t^k = G | x_t = x) \cdot \sum_{u \in \mathcal{U}} \pi_t^k(u|x,G) P(\cdot|x,u,G)\]

3. 理论保证¶

Theorem 3.1 (MF 收敛)：在 Assumption 2.2 下，\(\mu_t^{N,k} \to \mu_t^k\) in probability
Proposition 3.3 (目标收敛)：\(J^N(\pi) \to J(\pi)\) in probability
Corollary 3.4 (最优策略迁移)：极限系统的最优策略在所有足够大的有限系统中也是最优的

4. 两系统近似（Two Systems Approximation）¶

直接求解极限系统不可行——Lemma 4.1 证明 t-hop 邻域复杂度为 \(\Omega(2^{\text{poly}(k)})\)。

Heuristic 1（邻居度分布近似）：

\[P(\deg(v)=k | (v',v) \in E) \approx \frac{k \cdot P(\deg(v)=k)}{\sum_{k''} k'' \cdot P(\deg(v)=k'')}\]

基于此，将智能体分为低度系统（度≤k）和高度系统（度>k）：

高度智能体共享统一邻域分布 \(\hat{\mathbb{G}}_t^\infty\)，其动力学简化为：

\[\hat{\mu}_{t+1}^\infty = \sum_{x,u} \hat{\mu}_t^\infty(x) \pi_t^\infty(u|x, \hat{\mathbb{G}}_t^\infty) P(\cdot|x,u,\hat{\mathbb{G}}_t^\infty)\]

低度智能体（度 k≤k*）的邻域从多项分布采样：\(\hat{\mathbb{G}}_t^k \sim \text{Mult}(k, \hat{\mathbb{G}}_t^\infty)\)

论文还推导了更精细的 extensive approximation (LWMFC*)，使用状态-度邻域分布，精度更高但计算复杂度显著增加。

5. 学习算法¶

Algorithm 1 (LWMFC Policy Gradient)：将两系统近似转化为 MFC MDP，系统状态 \(\boldsymbol{\mu}_t = (\mu_t^1, \ldots, \mu_t^{k^*}, \mu_t^\infty)\)，动作为策略集合 \(\boldsymbol{\pi}_t\)。用 PPO 求解单智能体 MFC MDP。

Algorithm 2 (LWMFMARL Policy Gradient)：不假设模型知识，直接在真实网络上采样替代 MF 方程。每个节点按采样策略执行动作，由单智能体理论严格保证。此方法避免了两系统近似的不精确性。

实验设置与主要结果¶

实验设置¶

四个问题：SIS（传染病传播）、SIR（含恢复的传染病）、Graph Coloring（图着色）、Rumor（谣言传播）
八个真实网络：CAIDA (~26k节点)、Cities (~14k)、Digg Friends (~280k)、Enron (~87k)、Flixster (~2.5M)、Slashdot (~50k)、Yahoo (~653k)、YouTube (~3.2M)
合成网络：Chung-Lu 幂律图，规模 N∈{167, 406, 860, 1598}
基线：LPGMFG、GXMFG、IPPO
训练：约 80,000 CPU core 小时，每次训练约一天（96 并行 CPU 核心），PPO 配置：2×256 tanh 隐层，lr=5e-5，γ=0.99，GAE λ=1.0

主要结果 — MF 近似精度（Table 1）¶

平均期望总变差 \(\Delta\mu = \frac{1}{2T}\mathbb{E}[\sum_t \|\hat{\mu}_t - \mu_t\|_1]\)（×100%，50 trials），值越小越好：

问题	模型	CAIDA	Enron	Flixster	YouTube
SIS	LPGMFG	24.02	24.77	22.48	22.94
SIS	GXMFG	9.07	4.73	3.78	6.43
SIS	LWMFC	2.59	3.39	1.60	3.53
SIS	LWMFC*	1.75	2.67	0.90	2.93
SIR	LPGMFG	9.11	9.51	8.99	8.90
SIR	GXMFG	2.81	0.99	0.99	1.79
SIR	LWMFC	1.31	0.91	0.58	1.07
Color	LPGMFG	38.73	39.83	39.55	38.52
Color	GXMFG	11.33	4.91	6.38	8.76
Color	LWMFC	0.70	0.36	0.39	0.19

关键发现：LWMFC 在所有网络和所有问题上均全面优于 LPGMFG 和 GXMFG。在 Color 问题上提升尤为显著（如 CAIDA 上从 11.33→0.70，降低94%）。

主要结果 — 学习算法性能（Table 2）¶

在合成 CL 图上训练 24 小时后最优目标值：

问题	LWMFC	LWMFMARL	IPPO
SIS (N=860)	-19.70	-12.42	-9.11
SIS (N=1598)	-22.42	-13.51	-11.13
SIR (N=860)	-10.64	-6.86	-5.15
Color (N=860)	-8.48	-7.08	-5.85
Rumor (N=860)	0.25	1.47	1.35

LWMFMARL 和 IPPO 在直接网络交互时表现较好，但在较大规模网络（N=860, 1598）上，LWMFC 方法族整体优于 IPPO。

局限与展望¶

两系统近似的精度损失：低度/高度智能体的分割阈值 k 是手动设定的，不同问题的最优 k 不同
LWMFC 在极限系统而非真实系统上评估：Algorithm 1 学到的策略是极限系统最优，但可能与真实有限系统存在差异
Heuristic 1 的适用范围：邻居度分布近似仅在 CL 类图上有理论支撑，对其他拓扑可能不准确
Extensive 近似计算开销过大：LWMFC* 精度更高但在 Color 和 Rumor 问题上无法在合理时间内完成
仅考虑合作场景：论文聚焦 MFC（协作），未扩展到竞争性 MFG 设定
策略参数化简化：实验中使用仅依赖节点状态的策略（而非完整邻域信息），可能损失表达力
缺少对中等稀疏度图的对比：未系统研究在 LPGMFG/GXMFG 也适用的中等稀疏区域两者的性能对比

个人点评¶

论文的核心贡献是填补了稀疏图上 MFC 的理论和算法空白。将局部弱收敛引入平均场框架的思路自然且有说服力，两系统近似虽然是启发式的，但实验证明在大量真实网络上效果远超现有方法。Table 1 中 LWMFC 相对 GXMFG 在 Color 问题上的数量级提升（例如 YouTube 上 8.76→0.19）是很有力的实验证据。不过 Algorithm 1（MFC MDP 路线）在小规模图上不如 IPPO，说明平均场近似在节点数不够大时存在 gap。整体来看是一篇理论和实验都扎实的工作。

评分¶

新颖性: ⭐⭐⭐⭐ — 首次将局部弱收敛引入 MFC，覆盖此前完全未解决的极稀疏图类
实验充分度: ⭐⭐⭐⭐ — 4个问题×8个真实网络+合成网络，基线对比充分，但缺少 ablation（如 k* 选择）
写作质量: ⭐⭐⭐⭐ — 理论推导严谨，符号略重但结构清晰
价值: ⭐⭐⭐⭐ — 对网络 MARL 社区有明确推动作用，真实网络实验增强实用价值