Provably Efficient Federated Reinforcement Learning with Linear Function Approximation and Logarithmic Communication Cost
Abstract
We study federated online reinforcement learning with linear function approximation. While recent multi-agent reinforcement learning algorithms achieve strong regret guarantees, they typically require sharing raw trajectories. This reliance incurs a communication cost that scales linearly with the number of episodes and violates 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 integrating a determinant-based event-triggered synchronization with a stepwise backward update mechanism, Fed-LSVI enables agents to collaboratively learn an optimal policy by exchanging only compressed sufficient statistics. We prove that Fed-LSVI achieves a regret bound of 𝒪̃(√(Md3H4T)), 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, matching the best-known regret for multi-agent online reinforcement learning with linear function approximation. Moreover, by following the stringent communication and privacy constraints of the federated setting, Fed-LSVI reduces the communication cost to only logarithmic dependence on T, representing a significant improvement over prior methods.
Related
- Gaussian Approximation and Multiplier Bootstrap for Federated Linear Stochastic Approximation
- Federated learning with heavy-tailed gradient noise and communication noise: a variance-reduction based algorithm
- Uncertainty-Aware Federated Learning for Joint Communication and Computation in XR Systems
- Irrationality exponents of logarithmic numbers: Values, quotients, and graded approximation
- Reinforcement Learning with Markov Risk Measures and Multipattern Risk Approximation
BibTeX
@misc{liang2026provably,
title = {{Provably Efficient Federated Reinforcement Learning with Linear Function Approximation and Logarithmic Communication Cost}},
author = {Zihang Liang and Haochen Zhang and Lingzhou Xue},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.00193},
eprint = {2609.00193},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.00193},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Provably Efficient Federated Reinforcement Learning with Linear Function Approximation and Logarithmic Communication Cost
AU - Zihang Liang
AU - Haochen Zhang
AU - Lingzhou Xue
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.00193
UR - https://arxiv.org/abs/2609.00193
AB - We study federated online reinforcement learning with linear function approximation. While recent multi-agent reinforcement learning algorithms achieve strong regret guarantees, they typically require sharing raw trajectories. This reliance incurs a communication cost that scales linearly with the number of episodes and violates 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 integrating a determinant-based event-triggered synchronization with a stepwise backward update mechanism, Fed-LSVI enables agents to collaboratively learn an optimal policy by exchanging only compressed sufficient statistics. We prove that Fed-LSVI achieves a regret bound of 𝒪̃(√(Md^3H^4T)), 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, matching the best-known regret for multi-agent online reinforcement learning with linear function approximation. Moreover, by following the stringent communication and privacy constraints of the federated setting, Fed-LSVI reduces the communication cost to only logarithmic dependence on T, representing a significant improvement over prior methods.
ER -