标题： 基于马尔可夫采样的异构联邦随机逼近的更紧有限时间界 显示英文标题

标题： Achieving Tighter Finite-Time Rates for Heterogeneous Federated Stochastic Approximation under Markovian Sampling

摘要： 受协作强化学习（RL）和具有时间相关数据的优化问题的启发，我们研究了一个通用的联邦随机逼近问题，涉及$M$个代理，其中每个代理由特定于代理的（可能是非线性的）局部算子表征。 目标是让代理通过服务器间歇性通信，找到代理局部算子平均值的根。 我们的设定之所以具有通用性，是因为允许（i）每个代理处存在马尔可夫数据，以及（ii）代理局部算子的根存在异质性。 最近的少数工作虽然考虑了联邦设置中的这两个特性，但未能保证收敛到期望点，也无法展示协作的任何好处；此外，它们依赖算法中的投影步骤来保证迭代有界。 我们的工作克服了这些限制。 我们开发了一种新的算法，名为\texttt{FedHSA}，并证明它可以确保收敛到正确点，同时由于协作获得了$M$倍的线性样本复杂度加速。 据我们所知，\emph{这是同类中的第一个有限时间结果}的建立（且无需依赖投影步骤）需要相当复杂的论证，这需要考虑到马尔可夫采样导致的复杂的时间相关性、多步本地计算以节省通信量，以及由异构局部算子引起的漂移效应之间的相互作用。 我们的结果对一类广泛的异构联邦RL问题（例如，策略评估与控制）具有影响，在这些问题中，代理的马尔可夫决策过程可以在概率转移核和奖励函数上有所不同。 显示英文摘要

摘要： Motivated by collaborative reinforcement learning (RL) and optimization with time-correlated data, we study a generic federated stochastic approximation problem involving $M$ agents, where each agent is characterized by an agent-specific (potentially nonlinear) local operator. The goal is for the agents to communicate intermittently via a server to find the root of the average of the agents' local operators. The generality of our setting stems from allowing for (i) Markovian data at each agent and (ii) heterogeneity in the roots of the agents' local operators. The limited recent work that has accounted for both these features in a federated setting fails to guarantee convergence to the desired point or to show any benefit of collaboration; furthermore, they rely on projection steps in their algorithms to guarantee bounded iterates. Our work overcomes each of these limitations. We develop a novel algorithm titled \texttt{FedHSA}, and prove that it guarantees convergence to the correct point, while enjoying an $M$-fold linear speedup in sample-complexity due to collaboration. To our knowledge, \emph{this is the first finite-time result of its kind}, and establishing it (without relying on a projection step) entails a fairly intricate argument that accounts for the interplay between complex temporal correlations due to Markovian sampling, multiple local steps to save communication, and the drift-effects induced by heterogeneous local operators. Our results have implications for a broad class of heterogeneous federated RL problems (e.g., policy evaluation and control) with function approximation, where the agents' Markov decision processes can differ in their probability transition kernels and reward functions.