技术摘要：可扩展多智能体强化学习中局部性的统一框架

问题陈述

网络化系统中的可扩展多智能体强化学习（MARL）面临着维度灾难，即联合状态和动作空间随智能体数量 $n$ 的增加呈指数级增长。虽然存在一些可扩展方法允许智能体仅利用智能体图中的 $\kappa$-跳邻域进行规划，但这些方法的有效性取决于系统是否表现出价值局部性（value-locality）。价值局部性意味着一个智能体的扰动对远处智能体长期价值的影响会随其图距离呈指数级衰减。

在标准的 $\gamma$-折扣设置中，由于时间折扣因子 $\gamma < 1$，价值局部性是自动成立的。然而，在平均奖励设置（$\gamma = 1$）中，不存在这样的时间乘数。在此场景下，价值函数的作用由偏差函数（bias function）$h_\pi$ 取代，其由平均奖励泊松方程 $h_\pi - T^\pi h_\pi = r_\pi - \bar{r}_\pi$ 定义。要在这种设置下建立局部性，需要证明单步影响算子 $T^\pi$ 会诱导 $h_\pi$ 的指数级衰减。

现有方法依赖于矩阵 $C_\pi$ 的 Dobrushin 行和界限（row-sum bound），该矩阵捕捉了在给定智能体 $i$ 的状态变化时，智能体 $j$ 的下一状态分布的最大变化。该矩阵通常通过对所有联合动作取上确界来获得。虽然这提供了一个与策略无关的证书，但它通常过于保守（松散），因为它忽略了特定策略的行为。如果一个策略很少选择“最坏情况”下的动作，那么即使最坏情况下的界限暗示了全局耦合，实际系统可能仍具有价值局部性。

本文提出了一个统一框架，将策略诱导的影响矩阵 $C_\pi$ 分解为不同的环境组件和策略相关组件，以推导出更紧凑、具备策略感知能力的局部性证书。

1. 影响分解

论文引入了三个 $n \times n$ 非负矩阵来建模单步耦合：

• $E_s$（状态通道）： 衡量在保持动作不变的情况下，给定智能体 $i$ 的状态变化时，智能体 $j$ 的下一状态的最大全变差（TV）距离。
• $E_a$（动作通道）： 衡量在保持状态不变的情况下，给定智能体 $i$ 的动作变化时，智能体 $j$ 的下一状态的最大全变差距离。
• $\Pi(\pi)$（策略反应性）： 衡量智能体 $k$ 的动作分布对智能体 $i$ 状态变化的 TV 敏感度。

核心理论见解（命题 1）是逐元素分解：
$$C_\pi \preceq E_s + E_a \Pi(\pi)$$
该不等式将环境固有的敏感性（$E_s, E_a$）与策略的反应性（$\Pi(\pi)$）分离。它表明，即使动作通道 $E_a$ 很大（表示存在强烈的潜在耦合），如果策略是平滑的（即 $\Pi(\pi)$ 很小），闭环影响也会很小。

2. 谱半径证书

与其依赖行和范数 $\|H_\pi\|_\infty < 1$（其中 $H_\pi = E_s + E_a \Pi(\pi)$），作者提出了一个谱半径条件：
$$\rho(H_\pi) < 1$$
由于对于任何非负矩阵 $M$，都有 $\rho(M) \le \|M\|_\infty$，因此该条件比 Dobrushin 行和界限严格更弱。定理 3 确立了如果 $\rho(H_\pi) < 1$，则偏差函数 $h_\pi$ 满足：
$$\delta(h_\pi) \le (I - (H_\pi)^\top)^{-1} \delta(r_\pi)$$
其中 $\delta(f)$ 表示坐标分量的振荡。这意味着扰动的影响会沿着 $H_\pi$ 支持图中的路径呈指数级衰减。

3. 通过 Softmax 温度控制局部性

对于温度为 $\tau$ 的 Softmax 策略（常用于熵正则化控制），作者推导出了策略反应性矩阵的界限：
$$\Pi_{k \leftarrow i}(\pi) \le \min\left\{1, \frac{L_{k \leftarrow i}}{2\tau}\right\}$$
其中 $L_{k \leftarrow i}$ 是 Logit 函数的 Lipschitz 常数。这一结果（引理 6）表明，增加温度 $\tau$ 会直接降低 $\Pi(\pi)$，从而收紧谱半径证书 $\rho(H_\pi) < 1$。这创造了一个可调的权衡：通过高 $\tau$ 来保证局部性，或通过低 $\tau$ 来接近无正则化的最优解。

4. 局部化改进的 Oracle 框架

利用衰减结果，作者构建了一个用于**块坐标 KL 近似策略改进（block-coordinate KL-proximal policy improvement）**的确定性 Oracle 框架。

• 局部性证书： 智能体通过仅使用 $\kappa$-跳消息传递来计算截断的 Neumann 级数 $\hat{\delta}(\kappa) = \sum_{t=0}^\kappa ((H_\pi)^\top)^t \delta(r_\pi)$。
• 截断偏差： 由于截断引入的误差随 $O(\lambda^{\kappa+1})$ 衰减，其中 $\lambda$ 与谱半径相关。
• 改进保证： 论文提供了使用截断泊松代理进行单智能体更新时的平均奖励改进界限。该界限显式包含了一个项用于描述截断偏差，表明相同的半径 $\kappa$ 同时控制了证书的有效性和算法的性能。

核心贡献

1. 策略依赖型谱半径证书： 本文引入了第一个针对平均奖励网络化 MARL 中价值局部性的策略依赖型谱半径证书。它用更弱的条件 $\rho(E_s + E_a \Pi(\pi)) < 1$ 取代了保守的、与策略无关的 Dobrushin 行和界限。
2. 影响分解： 它正式将闭环影响分解为环境敏感性和策略反应性，证明了平滑策略可以抵消强烈的环境耦合。
3. 温度与局部性的联系： 它建立了 Softmax 温度 $\tau$ 与局部性证书之间的直接数学联系，表明 $\tau$ 可作为保证局部性的超参数。
4. Oracle 改进模板： 它为块坐标 KL 近似改进算法提供了一个确定性 Oracle 保证，并将截断偏差量化为与 Neumann 尾部项 $\lambda^{\kappa+1}$ 相关。

结果

• 理论紧致性： 证明了谱半径条件 $\rho(H_\pi) < 1$ 严格弱于行和条件 $\|H_\pi\|_\infty < 1$。论文提供了一个数值示例，在该示例中，行和条件失效（值 > 1），而谱半径远低于 1（0.6），从而在以往方法无法认证局部性的情况下成功认证了局部性。
• 衰减率： 证明了偏差函数 $h_\pi$ 在 $H_\pi$ 支持图的距离上呈指数级衰减。衰减率由 $H_\pi$ 的谱半径决定。
• 算法保证： 所提出的块坐标更新保证了平均奖励的改进，且误差项由 $\lambda^{\kappa+1}$ 显式界定。这使得从业者能够选择截断半径 $\kappa$，使偏差降至预期的精度阈值以下。

意义与主张

本文声称为何时以及如何认证并利用可扩展 MARL 方法中的局部性，提供了一个更精确且灵活的理解。通过摆脱基于最坏情况且与策略无关的界限，该框架允许在系统仅在特定平滑策略下才表现出“局部耦合”的机制中认证局部性。

作者强调，其框架将结构局部性与统计估计及函数逼近问题分离开来。证书 $\hat{\delta}(\kappa)$ 是真正的局部且可通过消息传递计算，而用于改进步骤的截断泊松代理被视为一个 Oracle 对象。本文认为，这种结构化分析为开发去中心化算法提供了必要的理论基础，并指出在实践中使该代理变为局部可计算的实现，需要额外的假设（例如受限的观测范围或特定的函数逼近器），这属于未来的工作。

该工作并不声称解决了规模化问题本身，而是提供了一个严谨的理论工具，用于确定何时以及如何认证并利用局部性，特别强调了通过策略正则化（通过温度）来确保系统稳定性和局部性的作用。