Zhu et al. (2025) — ARXIV-2504.11645
Key takeaways
Proposes FedHSA, the first federated stochastic approximation algorithm that simultaneously handles agent heterogeneity (different local operator roots), Markovian data, and sparse communication, while achieving an M-fold linear speedup in sample complexity with no heterogeneity-induced bias term. Closes a fundamental open problem in federated reinforcement learning theory.
- Proposition 1 (FedAvg-style SA bias under heterogeneity). Vanilla local-update federated SA with constant step size converges to a point that differs from the global root theta* by a non-vanishing bias proportional to the discrepancy between local operator roots and the global root. Holds when: Noiseless case (sigma=0); constant step size; heterogeneous agents with distinct local roots.
- Theorem 2 (FedHSA convergence). FedHSA converges exponentially fast to a ball around theta* with radius proportional to the step size; no heterogeneity-induced bias term appears in the bound. Holds when: Strongly monotone, Lipschitz SA operators; Markovian data; H local steps; two-timescale step sizes.
- Corollary 1 (Sample complexity with decaying step size). With linearly decaying global step size, FedHSA achieves sample complexity O-tilde(1/(MHT)) to reach epsilon-accuracy, giving M-fold linear speedup over single-agent SA. Holds when: Linearly decaying alpha_g; same operator and sampling assumptions as Theorem 2; complexity hides log factors and mixing time tau_mix.
What the evidence does not cover
- Requires agents to transmit their local operator evaluated at the new global parameter each round, adding one extra communication per round compared to vanilla FedAvg.
- Convergence guarantees require Lipschitz and strong-monotonicity assumptions that may not hold for general nonlinear RL operators.
- Agents’ Markov chains must share a common finite state space, limiting applicability to some continuous-state RL settings.
- Analysis assumes independent data across agents; correlated inter-agent data is not handled.
Standing in the anthology
Read — the reading is NOTE-128. Arrived in the imported batch, which brought in the federated branch, where the workers hold different data.