技术摘要：异构环境下联邦 Q 学习的收敛速率

问题陈述

大规模多智能体系统（如自动驾驶或工业自动化中的系统）通常运行在广阔的地理区域，智能体与异构环境进行交互。虽然联邦强化学习（FRL）提供了一种无需共享原始数据即可进行协同训练的框架，但环境异构性对经典算法（如 Q 学习）收敛性的影响尚未得到充分探索。

现有文献已确立，在同构环境（所有智能体共享相同的转移动力学）中，联邦 Q 学习可以实现相对于智能体数量（$K$）的线性加速。然而，在异构设置中，智能体遭遇不同的转移概率（$P_k$），导致学习信号错位。本文解决的核心问题是刻画**同步联邦 Q 学习（FQL）**的收敛速率，具体条件为：智能体在执行 $E$ 次局部更新后同步其 Q 估计值，且环境存在异构性。

方法论

作者分析了一种同步 FQL 算法，其中 $K$ 个智能体分别从其局部马尔可夫决策过程（MDP）$\mathcal{M}_k = \langle \mathcal{S}, \mathcal{A}, \mathcal{P}_k, \gamma, R \rangle$ 中独立收集样本。智能体执行 $E$ 次局部 Q 学习更新，随后通过参数服务器平均其 Q 估计值。

关键技术组件包括：

1. 误差分解：作者定义误差 $\Delta_t = Q^* - \bar{Q}_t$，其中 $Q^*$ 是由平均转移核 $\bar{P}$ 定义的全局 MDP 的最优 Q 函数，$\bar{Q}_t$ 是平均后的局部估计值。他们推导出了一个递归误差迭代公式（引理 1），将误差分解为三个部分：
   • 初始误差衰减。
   • 采样噪声（采样转移与真实转移之间的偏差）。
   • 异构性引起的扰动（局部转移 $P_k$ 与全局平均 $\bar{P}$ 之间的偏差）。
2. 异构性度量：异构程度由 $\kappa = \sup_{k,s,a} \|\bar{P}(\cdot|s,a) - P_k(\cdot|s,a)\|_\infty$ 量化。
3. 下界构造：为了证明根本局限性，作者构建了一个具体的反例，包含两个状态和二元动作，其中转移核在单位矩阵和置换矩阵之间交替。该设置隔离了 $E > 1$ 在异构环境中的影响。

主要贡献

1. 误差演化与样本复杂度的刻画

本文提供了误差演化的紧确刻画，表明收敛行为关键性地依赖于乘积 $K(E-1)$ 与由异构性 $\kappa$ 和目标精度 $\epsilon$ 决定的阈值之间的关系。

• 区域 1（线性加速）：当 $K(E-1)$ 低于阈值 $\tilde{\mathcal{O}}((\kappa\epsilon)^{-1}(1-\gamma)^{-2})$ 时，系统行为类似于同构设置。样本复杂度为 $\tilde{\mathcal{O}}\left(\frac{|\mathcal{S}||\mathcal{A}|}{K(1-\gamma)^5\epsilon^2}\right)$，表现出相对于智能体数量 $K$ 的线性加速。
• 区域 2（性能退化）：当 $K(E-1)$ 超过阈值时，异构性占主导地位。样本复杂度退化为 $\tilde{\mathcal{O}}\left(\frac{\kappa|\mathcal{S}||\mathcal{A}|E}{(1-\gamma)^3\epsilon}\right)$。在此区域，增加局部更新次数 $E$ 会线性增加样本复杂度，从而抵消并行化的优势。

2. 局部更新（$E > 1$）的根本局限性

本文证明，在异构环境中 $E > 1$ 导致的收敛减慢是根本性的，而不仅仅是分析的人为产物。

• 定理 2 建立了误差 $\ell_\infty$ 范数的下界：$\|\Delta_T\|_\infty \geq \Theta_R\left(\frac{E}{(1-\gamma)T}\right)$。
• 这意味着对于广泛的步长范围，误差无法以快于与 $E/T$ 成正比的速率衰减。因此，执行多次局部更新（$E > 1$）最终需要比执行单次更新（$E=1$）多 $E$ 倍的样本才能达到相同的目标精度。

3. 两阶段收敛现象

通过数值实验，作者识别出在具有恒定步长的异构设置中存在独特的两阶段现象：

• 阶段 1：误差迅速衰减，由初始误差的减少驱动。
• 阶段 2：误差“反弹”并稳定在由异构性和局部更新的集体扰动决定的残差水平。
• 本文建议采用两阶段训练策略——在阶段 1 使用较大的步长，在阶段 2 使用较小（或衰减）的步长——以减轻这种残差误差，并与使用单一恒定步长相比改善整体收敛性。

结果与实验验证

理论发现通过在 $K=20$ 个智能体与随机生成的 5x5 迷宫环境（具有不同的转移概率，模拟高异构性，$\kappa \approx 1.2$）交互的实验中得到了验证。

• 步长敏感性：在异构环境中，大的恒定步长会导致显著的误差反弹和高残差误差。相比之下，同构环境无论步长如何均不显示此类反弹。
• $E$ 的影响：在异构设置中增加同步周期 $E$ 会导致更高的最终误差，证实了理论上的退化。
• 两阶段策略：实验表明，在估计的阶段转换点（$t_0$）切换步长，与均匀步长策略相比，能产生更快的收敛速度和更低的最终误差。

意义与主张

本文声称是首个为联邦 Q 学习提供紧确样本复杂度分析的工作，该分析明确考虑了环境异构性和同步周期 $E$。

• 理论差距：与先前工作（如 Zhang 等人，2024；Wang 等人，2023）提供的未必衰减至零的上界，或未能刻画 $E$ 和 $\kappa$ 根本影响的工作不同，本文提供了衰减至零的界限，并明确指出了通信频率与收敛速度之间的权衡。
• 根本洞察：本文挑战了联邦设置中“更多局部更新总是更好”的直觉。它表明，在存在环境异构性的情况下，增加 $E$ 会从根本上阻碍收敛，对误差率施加了一个仅靠调整步长无法克服的下界。
• 实际意义：研究结果表明，对于异构多智能体系统，需要频繁同步（小 $E$）或自适应步长策略才能实现鲁棒性能，因为在同构设置中观察到的“异构性之福”并未扩展到这些条件下的 Q 学习收敛速率。