Convergence Guarantees for Federated SARSA with Local Training and Heterogeneous Agents¶
会议: NeurIPS 2026
arXiv: 2512.17688
代码: https://github.com/pmangold/fed-sarsa
领域: 其他
关键词: 联邦强化学习, 异构智能体, 联邦SARSA, 局部更新, 马尔可夫采样
一句话总结¶
本文首次建立了带线性函数逼近与多步局部训练的异构联邦SARSA（FedSARSA）有限时间收敛性理论保证，证明了其在智能体数量上的线性加速比，并给出了严谨的样本与通信复杂度界。
研究背景与动机¶
联邦强化学习（Federated RL）旨在协调多个智能体在不共享原始轨迹交互数据的约束下协同求解策略，以有效克服通信、存储与隐私壁垒。然而，在真实分布式物理系统与异构设备中，不同智能体所处的转移环境与奖励机制往往存在不可忽视的异构性（Heterogeneity）。为减少昂贵的高频中心化通信，联邦算法普遍引入局部多步训练机制，但这会在异构环境下引发严重的客户端漂移（Client Drift），导致全局聚合更新产生显著的优化偏差。
以往的联邦强化学习理论研究绝大多数聚焦于生成模型或同策/异策离线策略评估（如联邦 TD 学习），亦或离散状态空间的 Q-learning 与策略梯度方法；而作为强化学习奠基性基础算法之一的同策（On-Policy）SARSA 算法，在联邦环境下的理论刻画长期滞后。此前唯一探讨异构联邦 SARSA 的工作依赖于“虚拟平均环境”的简化假设，其推导得出的收敛界中包含无论怎样缩小步长都无法消除的永久性偏差（Persistent Bias），即使在单步局部更新下依然无法实现任意高精度的收敛。
本文切入的角度在于摒弃脱离实际的虚拟平均环境构造，直接从异构智能体的局部马尔可夫误差展开出发，精确追踪由策略演变、局部多步漂移与马尔可夫噪声耦合带来的误差动态。核心 idea：通过构建单智能体与多智能体 SARSA 的精确多步动力学误差展开式，严密刻画异构多智能体固定点方程及其漂移界，首次证明了 FedSARSA 在多步局部更新下能够收敛至任意给定精度，且主导方差项随智能体数量 \(N\) 呈现完全线性加速（Linear Speed-up）。
方法详解¶
整体框架¶
FedSARSA 面向 \(N\) 个异构马尔可夫决策过程（MDP）协同优化线性状态-动作价值函数 \(Q_\theta(s,a) = \phi(s,a)^\top \theta\)。每个全局通信轮次 \(t\) 开始时，中心服务端将最新的全局参数 \(\theta_t\) 下发至所有智能体；各智能体同步采用带温度系数 \(\beta\) 的 Softmax 策略 \(\pi_{\theta_t}\) 在各自的局部环境（转移核 \(P^{(c)}\)、奖励函数 \(r^{(c)}\)）中执行 \(H\) 步连续采样与局部 TD 更新。在局部训练阶段保持采样策略恒定，使得各智能体在全过程中维持严格一致的行为分布；完成 \(H\) 步迭代后，各节点将局部参数上传至中心服务器进行均值聚合与凸集投影截断，随后执行全局策略改进步。
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["输入: 初始参数 θ₀, 步长 η, 局部步数 H"] --> B["全局轮次 t 广播共享策略 π_θt"]
B --> C["局部多步TD更新<br/>固定策略采样+马尔可夫连续更新"]
C --> D["全局参数聚合与紧凸集投影<br/>θ̄_{t+1} = Σ θ^{(c)}_{t,H} / N"]
D --> E["真实异构极限点收敛与策略改进<br/>π_{θ_{t+1}} = Imp_β(Q_{θ_{t+1}})"]
E -->|未达轮数 T| B
E -->|终止| F["输出: 最终收敛参数 θ_T"]关键设计¶
1. 局部多步TD更新：抑制策略振荡并解耦马尔可夫采样误差 在每个通信轮次 \(t\) 的局部 \(H\) 步迭代中，智能体 \(c\) 依据当前固定的全局策略 \(\pi_{\theta_t}\) 采样动作，并执行局部时序差分更新：\(\theta_{t,h+1}^{(c)} = \theta_{t,h}^{(c)} + \eta_t (\mathbf{A}^{(c)}(Z_{t,h+1}^{(c)}) \theta_{t,h}^{(c)} + \mathbf{b}^{(c)}(Z_{t,h+1}^{(c)}))\)，其中特征矩阵和向量分别为 \(\mathbf{A}^{(c)}(z) = \phi(s,a)(\gamma \phi(s',a')^\top - \phi(s,a)^\top)\) 与 \(\mathbf{b}^{(c)}(z) = \phi(s,a) r^{(c)}(s,a)\)。传统逐样本更新策略会导致各智能体策略频繁演变，无法在联邦拓扑中维持一致的分布式评估基准。FedSARSA 巧妙地在局部 \(H\) 步内冻结策略生成分布，将更新动态严格解耦为马尔可夫遍历链向平稳分布的收缩，避免了局部策略与全局策略的混合混淆。
2. 真实异构极限点收敛方程：摒弃虚拟环境偏差并建立唯一解存在性 以往方法通常假设智能体收敛到平均 MDP 所对应的参数，这在强异构下引入了结构性死锁。本文将 FedSARSA 的真实极限点 \(\theta_\star\) 严格定义为各局部真实稳态期望矩阵与向量的联合零点： $\(\frac{1}{N} \sum_{c=1}^N \bar{\mathbf{A}}^{(c)}(\theta_\star) \theta_\star + \frac{1}{N} \sum_{c=1}^N \bar{\mathbf{b}}^{(c)}(\theta_\star) = 0\)$ 作者利用 Brouwer 不动点定理与策略改进算子 \(\operatorname{Imp}_\beta\) 的 Lipschitz 连续性，证明了在负定条件下该方程在紧凸集 \(\mathcal{W}\) 内存在唯一的极限点 \(\theta_\star\)。定义局部理想点 \(\vartheta_\star^{(c)}\) 满足 \(\bar{\mathbf{A}}^{(c)}(\theta_\star) \vartheta_\star^{(c)} + \bar{\mathbf{b}}^{(c)}(\theta_\star) = 0\)，将环境转移异构性 \(\epsilon_p\) 和奖励异构性 \(\epsilon_r\) 精确映射为漂移常数 \(\zeta_{\bar{\mathbf{A}}} = 4\mathrm{C}_A (1+\tau_{\mathrm{mix}})\epsilon_p\) 与 \(\zeta_{\theta_\star} = 6(1+\tau_{\mathrm{mix}})(\epsilon_p \|\theta_\star\| + \epsilon_r)\)，使得异构误差直接与矩阵扰动对齐。
3. 精细多步误差展开与马尔可夫相关性控制：实现智能体数目线性加速比 为消除以往分析中马尔可夫噪声随局部步数 \(H\) 线性放大的松弛界，作者基于精确极小化展开（Claim 2）将单步与通信块误差展开为压缩项、马尔可夫波动项、策略偏离项和异构漂移项 \(\Delta_{1:H} = \frac{1}{N}\sum_{c=1}^N (\mathrm{I} - \Gamma_{1:H}^{(c)})(\vartheta_\star^{(c)} - \theta_\star)\)。通过构造最大精确耦合（Exact Coupling）与 Berbee 引理，严密控制多重重叠时间步上的马尔可夫协方差总和，证明了均方误差的主导方差项由单智能体的 \(\mathcal{O}(\eta \tau_{\mathrm{mix}} \mathrm{G}^2 / a)\) 严格降为 \(\mathcal{O}(\eta \tau_{\mathrm{mix}} \mathrm{G}^2 / (N a))\)，而由局部更新 \(H\) 引起的异构漂移项以 \(\mathcal{O}(\eta^2 (H-1)^2 \zeta_{\bar{\mathbf{A}}}^2 \zeta_{\theta_\star}^2 / a^2)\) 衰减。这保证了步长收缩时异构偏差完全渐近消失，实现了在无偏收敛下的线性加速。
损失函数 / 训练策略¶
算法以均方时序差分误差（Mean Squared Bellman Error 投影）为隐式优化目标。步长满足 \(\eta H \mathrm{C}_A \le 1/6\) 且 \(\eta a \le 1/2\)。全局更新采用投影算子 \(\Pi_\mathcal{W}(\cdot)\) 约束参数范数上界 \(C_{\mathrm{proj}}\)。策略采用带参数 \(\beta\) 的 Softmax 策略改进算子 \(\pi_\theta(a|s) \propto \exp(\beta \phi(s,a)^\top \theta)\)，要求 Lipschitz 常数满足 \(80 \mathrm{G} \mathrm{C}_{\mathrm{lip}} |\mathcal{A}| \tau_{\mathrm{mix}} \le a\)，以彻底防止策略震荡（Chattering）。
实验关键数据¶
主实验¶
论文在具有随机拓扑转移的合成 Garnet 环境（\(|\mathcal{S}|=10, |\mathcal{A}|=3\)）上评估了表格型 FedSARSA 的收敛性，将 \(N\) 个智能体平分为具有完全不同转移与奖励矩阵的两组，考察智能体数量扩展（\(N \in \{2, 10, 50, 100\}\)）与局部步数（\(H \in \{1, 100, 10000\}\)）对均方误差（MSE）的影响；并在非线性控制环境 CartPole 上测试了深度神经网络参数化的 Deep FedSARSA。
下表呈现了合成 Garnet 异构环境下各算法在估计真值参数 \(\theta_\star\)（本文提出定义）与虚拟平均环境极限参数 \(\chi_\star\) 时的渐近均方误差（MSE）对比：
| 智能体规模 \(N\) | 局部迭代数 \(H\) | 目标点定义 | 最终 MSE 估计 | 收敛精度与理论预测偏差 | 理论吻合性评价 |
|---|---|---|---|---|---|
| \(N = 2\) | \(H = 1\) | 真实固定点 \(\theta_\star\) (Ours) | \(< 10^{-3}\) | 无渐近残留偏差 | 随步长与通信轮次线性收敛 |
| \(N = 2\) | \(H = 1\) | 虚拟平均点 \(\chi_\star\) (Prior) | \(\approx 2.5 \times 10^{-1}\) | 存在显著下界偏差壁垒 | 无法收敛到预想虚拟平衡点 |
| \(N = 10\) | \(H = 100\) | 真实固定点 \(\theta_\star\) (Ours) | \(< 10^{-4}\) | 误差随智能体数量 \(N\) 成比例下降 | 呈现明显的 \(1/N\) 线性加速 |
| \(N = 50\) | \(H = 100\) | 真实固定点 \(\theta_\star\) (Ours) | \(< 2 \times 10^{-5}\) | 方差进一步削减 5 倍 | 验证了主方差界随 \(N\) 严格缩减 |
| \(N = 100\) | \(H = 100\) | 真实固定点 \(\theta_\star\) (Ours) | \(< 10^{-5}\) | 达到极高精度收敛平台 | 多步局部更新下漂移完全可控 |
| \(N = 100\) | \(H = 10000\) | 真实固定点 \(\theta_\star\) (Ours) | \(\approx 5.0 \times 10^{-2}\) | 异构累积漂移项随 \(H^2\) 显现 | 验证了理论中 \(\mathcal{O}(\eta^2 H^2)\) 漂移项 |
消融实验¶
下表对比了在单智能体 SARSA 与多智能体 FedSARSA 架构下，不同算法设定对样本复杂度、通信轮次与渐近偏差特性的理论及实测影响：
| 算法与配置变体 | 样本复杂度 (per agent) | 通信轮次复杂度 \(T\) | 异构极限点偏差项 | 关键特性说明 |
|---|---|---|---|---|
| 单智能体 SARSA (\(N=1\)) | \(\mathcal{O}(\frac{\mathrm{G}^2 \tau_{\mathrm{mix}}}{a^2 \epsilon^2} \log \frac{1}{\epsilon})\) | 不涉及 (单机连续) | 无环境异构偏差 | 基础 baseline，依赖大量单机样本采样 |
| Prior FedSARSA (Zhang et al. 2024) | 未给出可达任意 \(\epsilon\) 界 | 无法任意收缩通信 | 存在非零下界 \(\mathcal{O}(\epsilon_p + \epsilon_r)\) | 受制于平均环境假设，存在永久性不可消偏差 |
| FedSARSA (\(H=1\), 单步通信) | \(\mathcal{O}(\frac{\mathrm{G}^2 \tau_{\mathrm{mix}}}{N a^2 \epsilon^2} \log \frac{1}{\epsilon})\) | \(\mathcal{O}(\frac{\mathrm{C}_A}{a} \log \frac{1}{\epsilon})\) | 零异构漂移 (\(\zeta\) 项为 0) | 通信极其昂贵，但完全消除局部漂移误差 |
| FedSARSA (\(H > 1\), 适度多步) | \(\mathcal{O}(\frac{\mathrm{G}^2 \tau_{\mathrm{mix}}}{N a^2 \epsilon^2} \log \frac{1}{\epsilon})\) | \(\mathcal{O}(\frac{\zeta_{\bar{\mathbf{A}}} \zeta_{\theta_\star}}{a^2 \epsilon} \log \frac{1}{\epsilon})\) | \(\mathcal{O}(\frac{\eta^2 H^2}{a^2} \zeta_{\bar{\mathbf{A}}}^2 \zeta_{\theta_\star}^2)\) | 兼顾线性加速比与低通信开销，可达任意精度 \(\epsilon\) |
| Deep FedSARSA (CartPole 控制) | 样本利用效率提升 \(4\times\) | 相比单机减少 \(10\times\) | 聚合后短暂轻微抖动 | 深度网络加持下平稳收敛至高奖励 (\(>450\)) |
关键发现¶
- 收敛点本质辨析：实测表明算法参数 \(\theta_t\) 迅速逼近本文由联合方程导出的不动点 \(\theta_\star\)，而相对于虚拟平均环境参数 \(\chi_\star\) 的距离始终保持在无法逾越的常数界。这决定性地推翻了以往文献关于“联邦强化学习收敛到虚拟平均环境”的直觉猜想。
- 线性加速比实证：在固定步长下，各智能体达到相同精度所需的单机样本数严格与总节点数 \(N\) 成反比，主导方差项展现了极其清晰的 \(1/N\) 抑制效应。
- 局部步数 \(H\) 的容忍临界：在 \(H \le 100\) 时，异构漂移几乎完全被方差缩减增益所掩盖；仅当局部步数过度放大至 \(H = 10000\) 时，\(\mathcal{O}(\eta^2 H^2)\) 的累积漂移才会成为制约高精度收敛的主要瓶颈。
亮点与洞察¶
- 多步误差递推的代数分解：通过 Claim 1 与 Claim 2 创新性地引入矩阵乘积差分因式分解 \(\Gamma_{t,k:h}^{(c)}\)，将高度复杂的非平稳多步马尔可夫轨迹误差拆解为正交的收缩主干与扰动余项，具有独立的方法论理论价值。
- 高阶马尔可夫噪声紧界分析：借助 Berbee 引理与精确耦合分析，证明了高阶噪声方差项仅依赖于链的混合时间 \(\tau_{\mathrm{mix}}^2\)，成功消除了既往分析中致命的 \(\mathcal{O}(\eta^2 \tau_{\mathrm{mix}} H)\) 混合爆炸项。
- 多智能体到深度强化学习的平滑泛化：提供了基于 JAX 与 gymnax 的全功能深度 FedSARSA 实现，表明冻结策略与局部多步更新不仅在理论上自洽，在结合小规模回放缓冲区与目标网络后同样能稳定解决深度连续控制任务。
局限与展望¶
- Lipschitz 策略改进常数受限：理论推导依赖 Assumption 5（\(80 \mathrm{G} \mathrm{C}_{\mathrm{lip}} |\mathcal{A}| \tau_{\mathrm{mix}} \le a\)），该条件限制了 Softmax 锐度参数 \(\beta\) 的取值范围，在强贪婪（Greedy）策略下的收敛性尚未被本框架覆盖。
- 通信复杂度对精度的多项式依赖：在异构环境下，为压制累积局部漂移，通信轮次规模随误差倒数呈现 \(\mathcal{O}(1/\epsilon)\) 多项式依赖；未来引入 SCAFFOLD 或 Scafflsa 类型的局部控制变量（Control Variates）有望将通信复杂度降低至对数级 \(\mathcal{O}(\log(1/\epsilon))\)。
相关工作与启发¶
- vs Zhang et al. (2024)：以往针对异构 FedSARSA 的分析构建在平均 MDP 目标之上，导致收敛界包含不可消除的 \(\mathcal{O}(\epsilon_p + \epsilon_r)\) 静态偏差；本文通过重构实际异构不动点方程，首次实现了可达任意目标精度 \(\epsilon^2\) 的无偏有限时间保证。
- vs Wang et al. (2024) & Mangold et al. (2024)：上述工作专注于异构环境下的联邦 TD 策略评估；本文则拓展至带动态策略改进的广义控制场景（On-policy SARSA），成功化解了参数更新与数据生成分布双重移动的耦合难题。
评分¶
- 新颖性: ⭐⭐⭐⭐⭐ 首次建立带多步局部更新与异构智能体的 FedSARSA 样本/通信复杂度与线性加速理论。
- 实验充分度: ⭐⭐⭐⭐ 包含合成 Garnet 环境的理论边界严密对齐与基于 JAX 的深度 CartPole 泛化验证。
- 写作质量: ⭐⭐⭐⭐⭐ 数学论证严谨，定理阐释条理清晰，附录证明链条完备扎实。
- 价值: ⭐⭐⭐⭐⭐ 填补了同策联邦强化学习理论长期存在的关键空白，为分布式具身智能与多智能体协作提供了坚实的理论基石。