Source-linked AI summary
Provably Efficient Federated Reinforcement Learning with Linear Function Approximation and Logarithmic Communication Cost
Zihang Liang, Haochen Zhang, Lingzhou Xue
TL;DR
Federated reinforcement learning must support collaborative learning without sharing sensitive raw trajectories, while linear function approximation makes compressed sufficient statistics and backward updates technically challenging. Fed-LSVI addresses these challenges with event-triggered and stepwise backward synchronization, achieving sublinear regret with logarithmic communication and robustness to mild agent-wise heterogeneity.
Problem
Federated reinforcement learning requires compressed sufficient statistics instead of raw trajectories, while linear function approximation makes those statistics and backward regression updates non-trivial.
Method
Fed-LSVI combines determinant-based event-triggered synchronization with a stepwise backward update mechanism for federated online reinforcement learning with linear function approximation.
Results
Fed-LSVI matches the best-known regret scaling for online multi-agent reinforcement learning with linear function approximation and reduces communication cost to logarithmic dependence on T.
Takeaways & Limitations
Agents can collaboratively achieve statistically efficient exploration while keeping raw trajectories local, with a communication-efficient framework that remains robust to mild agent-wise heterogeneity.
Takeaways & Limitations
The heterogeneous analysis assumes each agent's MDP is a ξ-approximate linear MDP relative to a common reference linear MDP.
Abstract
from arXiv · showhide
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 $\widetilde{\mathcal O}(\sqrt{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.
1 Introduction
The paper addresses whether federated online reinforcement learning with linear function approximation can be both sample-efficient and communication-efficient without sharing raw trajectories. It proposes Fed-LSVI, combining event-triggered and backward stepwise synchronization to obtain efficient regret and logarithmic communication.
- Motivation: Raw-trajectory sharing in cooperative reinforcement learning creates communication overhead and privacy concerns for distributed applications.The paper highlights healthcare settings where patient-level trajectories are sensitive and distributed across institutions.
- Technical challenges: Federated linear-function-approximation RL must construct compressed sufficient statistics while resolving stale responses caused by backward LSVI updates.These are identified as the two primary technical challenges in the federated setting.
- Algorithm Design: Fed-LSVI combines determinant-based event-triggered synchronization with a stepwise backward synchronization protocol.The event trigger limits redundant communication, while backward synchronization addresses stale responses.
- Regret Guarantees: Under misspecification ξ = e O(d/(MT)), Fed-LSVI recovers the same regret bound as in the homogeneous setting.The analysis allows agent-wise heterogeneity through ξ-approximate linear MDPs.
- Communication Cost: Communication scales logarithmically with T while transmitting compressed statistics instead of raw trajectories.Each round transmits O(Md^2H) scalars, whereas prior cooperative methods have communication costs linear in T.
2 Related Work
Related work spans near-optimal single-agent RL, low-switching learning, cooperative multi-agent exploration, and federated RL. The paper situates Fed-LSVI at the intersection of linear-function-approximation MARL and communication-efficient federated learning.
- Near-Optimal Reinforcement Learning: Single-agent RL with linear function approximation is organized around structural assumptions such as linear MDPs and linear mixture MDPs.The cited literature develops provable regret guarantees under these different MDP structures.
- Low-Switching Reinforcement Learning: Low-switching reinforcement learning studies regret–switching trade-offs motivated by the cost of frequent policy deployment.Prior results include logarithmic switching in positive-gap instances.
- Multi-Agent RL: Cooperative MARL uses parallel exploration and limited communication to improve sample efficiency with function approximation.This line of work extends single-agent approaches to multiple agents sharing an objective.
- Federated Reinforcement Learning: Federated RL analyses have mainly addressed tabular control, policy evaluation, and policy-gradient methods.The cited tabular value-based results include linear speedup, communication efficiency, and heterogeneity-dependent guarantees.
3 Preliminaries
The paper studies synchronous federated learning across agents interacting with finite-horizon episodic MDPs, using linear features to represent rewards and transitions. Performance is measured through regret against optimal policies and communication through transmitted scalars.
- Episodic Markov Decision Processes: Each agent interacts with an episodic MDP over horizon H, observing states, choosing actions, receiving rewards, and transitioning according to Ph.The state space may be measurable and possibly infinite, while the action set is finite.
- Policies and Value Functions: Policies map states to action distributions, and value functions evaluate policy performance through Q-values and V-values.An optimal policy exists because the action space and horizon are finite.
- Linear Markov Decision Processes: A linear MDP represents rewards and transition kernels through known features ϕ(x,a) and unknown parameters and signed measures.The defining relations are rh(x,a)=⟨ϕ(x,a),θh⟩ and Ph(B|x,a)=⟨ϕ(x,a),µh(B)⟩.
- Federated Reinforcement Learning: The federated protocol uses M agents, T episodes per agent, and MTH total interaction steps.A central server coordinates occasional synchronizations while raw trajectories remain on the agents.
- Federated Reinforcement Learning: Learning is partitioned into synchronized rounds in which all agents execute the same policy, and regret compares local optimal values with the round policies.Communication cost is defined as the number of transmitted integer or real scalars.
4 Algorithm Design
Fed-LSVI coordinates local exploration with a central server that synchronizes compressed statistics only when a determinant trigger fires or the episode budget is reached. Its backward stepwise updates keep regression targets aligned with freshly updated value functions.
- Initialization and Coordination: Fed-LSVI initializes server models, regularization, trigger, exploration, and episode-budget parameters before proceeding through communication rounds.The server maintains regression parameters and covariance matrices for each horizon step.
- Local Exploration: During each round, agents execute a shared policy and maintain persistent historical buffers plus round-local covariance increments.The round-local covariance is reset at the beginning of the next round.
- Event-Triggered Synchronization: Synchronization is triggered by determinant growth at some step or when the total episode counter reaches T.The triggering agent signals the server, which broadcasts the signal and ends the current exploration round.
- Agent-Server Synchronization: At synchronization, agents send local covariance matrices and full-history response vectors, which the server aggregates to solve ridge regressions.The server broadcasts each updated step-h model before moving to the preceding step.
- Stepwise Backward Update: The server updates models backward from step H to step 1 so each regression uses the newly updated next-step value function.This interleaved procedure prevents stale-response issues by broadcasting each stepwise model before constructing preceding-step responses.
5 Theoretical Guarantees
Fed-LSVI provides regret guarantees in homogeneous and mildly heterogeneous federated settings while preserving logarithmic communication dependence on the number of episodes. Its guarantees retain multi-agent statistical efficiency and use compressed communication rather than raw trajectories.
- Homogeneous Setting: In the homogeneous setting, Fed-LSVI matches the best-known multi-agent regret scaling while operating under federated restrictions on trajectory sharing.Only stage-wise sufficient statistics are communicated, rather than raw trajectories.
- Homogeneous Setting: Fed-LSVI achieves a provable M-type multi-agent speedup in the homogeneous setting.The result is consistent with worst-case guarantees in federated tabular reinforcement learning and multi-agent reinforcement learning with linear function approximation.
- Misspecified Setting: Under agent-wise heterogeneity, Fed-LSVI remains robust when each agent’s MDP is ξ-approximate to a common reference linear MDP.The misspecified setting uses a shared feature map and agent-specific MDPs that satisfy the approximate linear-MDP definition.
- Misspecified Setting: When ξ = e O(d/(MT)), the misspecified regret bound matches the homogeneous-setting bound.This result matches the best-known multi-agent reinforcement-learning result cited for the misspecified setting.
- Communication Cost: Fed-LSVI reduces communication dependence on T from linear to logarithmic compared with methods that share raw trajectories.Existing multi-agent online reinforcement-learning methods are described as incurring O(MHT) communication cost.
- Single-Agent Specialization: When M = 1, Fed-LSVI reduces to a low-switching-cost variant of LSVI-UCB with the same regret scaling and logarithmic policy switching cost.This specializes the theoretical guarantees to the single-agent setting.
6 Conclusion
Fed-LSVI is presented as a provably efficient federated algorithm that combines event-triggered synchronization with stepwise backward updates. The analysis also establishes logarithmic communication and robustness to mild agent-wise heterogeneity.
- Conclusion: Fed-LSVI combines determinant-based event-trigger synchronization with stepwise backward updates without sharing raw local trajectories.The method is designed to provide statistical and communication efficiency in federated online reinforcement learning under linear MDPs.
- Conclusion: Fed-LSVI provides T-type regret guarantees with a provable multi-agent speedup and only logarithmic communication cost.
- Conclusion: Fed-LSVI remains robust to mild agent-wise heterogeneity in the misspecified setting.
C Proof of Theorem 1
The proof establishes uniform high-probability control of regression errors, optimism, and related quantities across rounds, steps, agents, and state-action pairs.
- Supporting lemmas: Uniform confidence decomposition controls regression errors simultaneously over rounds, steps, and state-action pairs under event C.
- Supporting lemmas: Optimistic estimates upper-bound the corresponding value functions conditioned on event C.
- Supporting lemmas: The martingale correction event E holds with probability at least 1 −p.
- Supporting lemmas: An elliptical potential bound is introduced to control cumulative feature-dependent terms in the analysis.
C.2 Proof of Theorem 1
The proof decomposes regret under a joint high-probability event, then bounds optimism errors, martingale fluctuations, and elliptical-potential terms to recover Theorem 1.
- Regret proof: The events C ∩ E hold with probability at least 1−2p, providing the basis for the regret proof.
- Regret proof: Regret is expanded and bounded by summing confidence-based terms across agents, episodes, and horizon steps.
- Regret proof: The resulting decomposition separates a martingale term from an elliptical-potential term.
- Regret proof: The proof recovers the regret bound stated in Theorem 1 after setting λ = 1 and substituting β.
- Optimism proof: Optimism is established by backward induction on the horizon step.
C.3.4 Proof of Lemma C.4
The proof treats the correction terms as a martingale-difference array under a linearized ordering and applies Azuma–Hoeffding across all agent-step-episode terms.
- Martingale concentration: The correction terms form a martingale-difference array under the linearized ordering.
- Martingale concentration: Each correction term is bounded in magnitude by 2H.
- Martingale concentration: Azuma–Hoeffding is applied to the sum over all MTH terms to obtain the concentration claim.
C.3.5 Proof of Lemma C.5
The proof bounds the relevant terms by splitting rounds according to determinant growth, handling short and long rounds separately, and summing the resulting inequalities across steps. In the misspecified setting, concentration and backward-induction arguments control agent-dependent transition errors and value estimates.
- Rounds are divided into classes according to determinant growth, separating small-growth and large-growth cases for the analysis.
- Cauchy–Schwarz and sequential matrix-update arguments bound cumulative terms within each round.
- The stopping rule converts the absence of a determinant trigger into a bound on the final interval's growth.
- In the misspecified setting, the proof combines reference-model linearity, martingale bounds, and heterogeneity terms to control regression and value-function errors.
- Uniform concentration events hold simultaneously across agents, rounds, steps, policies, and state-action pairs with probability at least 1 − p̄.
- Backward induction establishes the recursion from the terminal step through earlier steps, including the effect of clipping and nonnegative bonus terms.
D.2 Proof of Theorem 2
Theorem 2 is proved on the intersection of concentration events, then by summing per-step error recursions across agents, episodes, and rounds. The resulting expression is identified with the claimed misspecified-setting regret bound.
- The events Chet and Ehet hold jointly with probability at least 1 − 2p̄, enabling the subsequent lemmas.
- Per-step bounds are summed over the horizon and then regrouped over all agents, episodes, and synchronization rounds.
- Martingale concentration and the Gram-matrix communication analysis are applied to control the accumulated terms.
- The collected terms yield exactly the regret bound stated in Theorem 2.
- Extending the guarantee to stronger cross-agent distribution shifts or asynchronous and partial participation remains future work.
E Proof of Theorem 3
Theorem 3 bounds communication by partitioning synchronization rounds into long rounds, trigger-terminated short rounds, and a final hard-cap round. Determinant monotonicity and eigenvalue inequalities control the number of rounds in these classes.
- Rounds are partitioned into long rounds, trigger-terminated short rounds, and short rounds ending at the hard episode cap.
- At most one round can terminate solely because the hard stop is reached.
- Long rounds have length greater than α, so their count is bounded using the total of T episodes per agent.
- For trigger-terminated short rounds, a determinant-trigger condition from some agent and step initiates the bound.
- Loewner-order domination and determinant monotonicity relate single-agent updates to global covariance growth.
- An arithmetic-geometric mean inequality applied to covariance eigenvalues completes the round-count control.