Provably Efficient Federated Reinforcement Learning with Linear Function Approximation and Logarithmic Communication Cost

We study federated online reinforcement learning with linear function approximation. Although recent multi-agent reinforcement learning algorithms achieve strong regret guarantees, they typically require agents to share raw trajectories. This requirement leads to communication costs that scale linearly with the number of episodes and conflicts with the privacy constraints of federated settings. To address these limitations, we propose **Fed-LSVI**, the first provably efficient federated algorithm for online reinforcement learning with linear function approximation in episodic Markov decision processes. By combining determinant-based event-triggered synchronization with a stepwise backward update mechanism, **Fed-LSVI** enables agents to collaboratively learn an optimal policy while exchanging only compressed sufficient statistics, without sharing raw trajectories. We prove that **Fed-LSVI** achieves a regret bound of $\tilde{\mathcal{O}}\left(\sqrt{M{d}^3{H}^{4}T}\right)$, where $d$ is the feature dimension, $H$ is the horizon length, $M$ is the number of agents, and $T$ is the number of episodes per agent. This bound matches the best-known regret guarantee for multi-agent online reinforcement learning with linear function approximation. Moreover, **Fed-LSVI** incurs a communication cost that grows only logarithmically with $T$ while adhering to the stringent communication and privacy constraints of federated settings, substantially improving upon prior methods. Numerical experiments further corroborate our theoretical findings and demonstrate the effectiveness of the proposed algorithm.