In this paper, we perform a non-asymptotic analysis of the federated linear
stochastic approximation (FedLSA) algorithm. We explicitly quantify the bias
introduced by local training with heterogeneous agents, and investigate the
sample complexity of the algorithm. We show that the communication complexity
of FedLSA scales polynomially with the desired precision $\epsilon$, which
limits the benefits of federation. To overcome this, we propose SCAFFLSA, a
novel variant of FedLSA, that uses control variates to correct the bias of
local training, and prove its convergence without assumptions on statistical
heterogeneity. We apply the proposed methodology to federated temporal
difference learning with linear function approximation, and analyze the
corresponding complexity improvements.

本文对联邦线性随机逼近（FedLSA）算法进行了非渐进分析，定量化了异质代理的本地训练引入的偏差，并调查了算法的样本复杂度。我们展示了 FedLSA 的通信复杂度与所需精度 ε 的多项式缩放，从而限制了联邦的好处。为了克服这一问题，我们提出了 SCAFFLSA，这是 FedLSA 的一种新变体，它使用控制变量来校正本地训练的偏差，并证明其在统计异质性方面没有假设的收敛性。我们将所提出的方法应用于使用线性函数逼近的联邦时序差异学习，并分析了相应的复杂度改进。