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

In federated reinforcement learning (FRL), agents must learn an optimal policy while keeping their raw data local to ensure privacy and minimize communication overhead. The authors address the challenge of designing a sample-efficient and communication-efficient algorithm for online reinforcement learning with linear function approximation, where agents cannot share raw trajectories.

The authors introduce Fed-LSVI, a federated algorithm that utilizes two key mechanisms to solve the stale-response problem inherent in federated settings. First, they employ a determinant-based event-triggered synchronization rule that limits communication rounds to a logarithmic scale relative to the total number of episodes. Second, they implement a stepwise backward synchronization protocol. Instead of aggregating data in a single batch, the central server and agents perform updates recursively from the final step of the horizon back to the first. This ensures that the regression targets for each step are computed using the most up-to-date global value function estimates.

Fed-LSVI achieves a regret bound of O(sqrt(Md^3H^4T)), matching the best-known regret guarantees for multi-agent online reinforcement learning with linear function approximation. Crucially, the algorithm reduces communication costs from linear to logarithmic in the number of episodes (T), significantly improving upon prior methods that require sharing raw trajectories. The authors also demonstrate that the algorithm is robust to mild agent-wise heterogeneity in misspecified settings, maintaining its performance guarantees even when local MDPs deviate from a common reference model.

This work provides a rigorous theoretical foundation for federated reinforcement learning with linear function approximation. By enabling collaborative learning without the need to transmit sensitive raw data, Fed-LSVI offers a scalable and privacy-preserving solution for real-world applications such as healthcare, mobile edge computing, and distributed recommender systems.