- Rating
- 3
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The paper proposes Fed-LSVI for federated online reinforcement learning in episodic linear MDPs. It combines determinant-triggered synchronization with backward, stepwise exchanges of covariance matrices. and response vectors. It keeps trajectory locally and ensuring consistent Bellman regression targets. For , it establishes regret and communication cost logarithmic in with an extension to mildly heterogeneous environments. Synthetic experiments verifies regret, collaboration gains and communication scaling.
Critical strengths
-
Protocol for learning without trajectory exchange. Recomputing local response vectors using freshly broadcast next step value estimates reproduces the pooled LSVI regression exactly. It addresses a consequential obstacle to implementing cooperative LSVI with data-locality constraints.
-
Joint statistical and communication guarantees. The algorithm retain the regret scaling of the cited cooperative methods and it communicates only logarithmically in the episode budget. The delayed-covariance analysis provides meaningful theoretical support beyond the protocol.
Critical weaknesses
-
Low-switching LSVI needs sharper justification. Determinant-triggered policy updates and backward LSVI already appear in existing low-switching methods. Although the federated implementation and its analysis is potentially useful, the paper needs to clarify which guarantees cann't follow from a straightforward distributed adaptation of the methods.
-
Limited comparative evidence. Appendix B only evaluates small synthetic environments without competing methods or synchronization ablations. It uses differing from the theoretical choices and tests heterogeneity only at . The experiments doesn't establish comparative efficiency and robustness to fixed heterogeneity. Transmitted scalar count and runtime also better expose the cost of sequential backward exchanges, and full history re-computation.
Questions for authors
-
What additional technical obstacle prevent a straightforward federated implementation of LSVI-UCB-RareSwitch from obtaining comparable regret, and communication guarantee?
-
Could you provide comparisons with relevant cooperative baseline and a stale-response synchronization variant, reporting regret, transmitted scalars, and runtime? Does the conclusion persist with the prescribed exploration bonus, and fixed heterogeneity?
-
[1] also studies provably communication-efficient federated RL without sharing local trajectories, reducing per-iteration communication from quadratic to linear in the policy parameter dimension while preserving the convergence rate of standard FedNPG. A brief comparison would help distinguish the present contribution and clarify how the communication guarantees differ.
[1] Improved Communication Efficiency in Federated Natural Policy Gradient via ADMM-based Gradient Updates, NeurIPS 2023.
6 comments
3. Local triggering and parallel sampling require additional analysis.
Our analysis connects each agent's local trigger condition to a bound on the cumulative exploration bonuses across all parallel agents. RareSwitch evaluates its determinant test using the full current covariance matrix. In Fed-LSVI, each agent observes the last synchronized covariance and its own newly collected information, while the server receives the combined increments only at synchronization. Controlling the pooled regret therefore requires relating these local observations to the global covariance growth.
Furthermore, all agents collect trajectories in parallel under the shared policy. Even if their samples are ordered sequentially for analysis, the policy cannot react between the trajectories collected in one parallel episode. The regret analysis must therefore control sums of the form
\|\|\phi_{m,t,h}\|\|_{(\Lambda_h^k)^{-1}},$$ where the normalization remains fixed throughout each communication round. **Lemma H.5 and its proof in Appendix H.3.5** address this issue by separating rounds according to global determinant growth and introducing agent-wise auxiliary covariance matrices. These matrices permit sequential normalization along each agent's samples, while the inverse-round-length threshold controls the conversion from the stale covariance to these auxiliary matrices. The final parallel batch is handled separately. This analysis connects the locally implementable trigger to the joint guarantees in **Theorems 1 and 3**, preserving multi-agent speedup while bounding both synchronization rounds and total communication.W2 and Q2: Comparative experiments, communication and computation costs, and robustness checks
The new experiments show that Fed-LSVI achieves comparable regret and synchronization counts to Coop-LSVI with substantially lower communication volume and shorter training time. The requested checks also show decreasing normalized regret with the logarithmically scaled exploration bonus and in a larger MDP, together with deterioration as fixed heterogeneity becomes stronger. We provide the controlled comparisons and supporting results below.
1. Comparative performance, communication volume, and training time.
Fed-LSVI's advantage over Coop-LSVI is lower communication volume and shorter training time at comparable regret and synchronization counts. In Appendix C.5, Figure 13, the methods use identical environments, agent counts, and episode budgets. Fed-LSVI obtains lower regret, and their synchronization counts become close at larger budgets.
In Appendix C.6, Figure 14, Coop-LSVI transmits substantially more data and requires noticeably longer training time than Fed-LSVI. Coop-LSVI exchanges raw transition records, whereas Fed-LSVI exchanges fixed-dimensional sufficient statistics. This difference explains the communication-volume advantage even when synchronization counts are comparable.
Figure 14 reports application-layer bytes transmitted in both directions, including model or trajectory data and control messages. Training time includes both computation and communication, accounting for the costs of historical-data recomputation and sequential backward exchanges. These measurements complement the scalar-count analysis in Section 4.3, which gives transmitted scalars per communication round.
The stale-response ablation shows the learning benefit of fresh targets, with similar measured training time on the runtime test instance. In Appendix C.4, Figure 12, the stale variant retains the same determinant-based trigger rule but constructs targets using value functions from the previous synchronization. It performs similarly to Fed-LSVI on and , but incurs substantially higher regret on and . In the runtime comparison, stale update and Fed-LSVI have similar training times, while stale update transmits slightly fewer bytes through message batching. These results expose both the learning benefit and the communication overhead of fresh-target backward synchronization.
2. Sensitivity to the exploration-bonus scaling.
The decreasing normalized-regret trend persists when the exploration coefficient incorporates the theoretically motivated logarithmic dependence on . Appendix D.2, Figure 16 compares this scaled coefficient with the original fixed coefficient. Both choices produce decreasing over the larger tested episode budgets. The scaled bonus yields higher regret, consistent with the additional exploration induced by its larger magnitude. The numerical prefactor remains empirically chosen; this experiment specifically tests the logarithmic scaling in the theoretical bonus.
3. Robustness to fixed heterogeneity.
Under mild fixed heterogeneity, normalized regret decreases over the larger tested budgets; stronger heterogeneity produces an earlier crossover from decreasing to increasing normalized regret. In Appendix D.1, Figure 15, we replace the shrinking-heterogeneity setup with several fixed heterogeneity levels alongside the homogeneous baseline. For each level, we keep the reference MDP, the agent-specific MDPs, and the number of agents fixed as the episode budget increases.
The smallest tested nonzero heterogeneity remains close to the homogeneous baseline. The earlier crossover at larger fixed heterogeneity is consistent with the heterogeneity-dependent error in Theorem 2.
4. Evaluation on a larger MDP instance.
On the larger MDP instance, Fed-LSVI retains decreasing normalized regret over larger episode budgets and decreasing average per-agent regret as more agents participate. Appendix B.5, Figure 6 evaluates a homogeneous linear MDP with more states and actions, a longer horizon, and a larger feature dimension. The episode-budget sweep holds the environment and number of agents fixed, while the agent-number sweep holds the environment and episode budget fixed. Communication growth remains consistent with the trends observed in the smaller instances.
W1 and Q1: Algorithmic novelty and the distinction from LSVI-UCB-RareSwitch
Fed-LSVI's algorithmic novelty lies in the round-length-adaptive triggering threshold and the stepwise backward synchronization protocol, which jointly preserve multi-agent speedup with infrequent sufficient-statistic communication. The determinant ratio itself is a standard ingredient. Our threshold controls regret under local triggering and parallel sampling, while the stepwise protocol coordinates statistic construction with the latest Vh+1 to eliminate stale-response drift. These are the key technical designs needed to obtain our joint guarantees when extending LSVI to the federated setting.
1. Adaptive threshold design.
The inverse-round-length threshold in Equation (4) preserves the leading regret order while controlling synchronization frequency. Determinant ratios are also used by Rarely-Switching OFUL, which triggers updates at a fixed determinant-growth threshold. In our analysis, Equation (23) contains a round-length factor multiplying the determinant ratio in the cumulative-bonus bound. A fixed threshold leaves this additional round-length dependence in the bound. Fed-LSVI's inverse-round-length threshold offsets this factor before the final episode of the round, as shown in Lemma H.5 and Appendix H.3.5. The parameter γ then controls the resulting regret–communication trade-off.
2. Stepwise synchronization is needed to implement fresh-target backward updates without trajectory exchange.
Stepwise backward synchronization makes the latest Vh+1 available before agents construct their step-h response vectors, eliminating stale-response drift while keeping raw trajectories local. LSVI-UCB-RareSwitch performs its backward updates using centralized access to historical next states; see Algorithm 2, Lines 9–13 of Wang et al. (2021). In the federated setting, these states remain distributed across agents, so constructing the response statistics must be coordinated with the server's backward value updates.
Specifically, if agents upload the response vectors for all steps simultaneously, the fresh step-(h+1) value function is not yet available when the step-h response vector is constructed. Using the previous value function introduces the mismatch Δbhm=∑(x,a,r,x′)∈Dhmϕ(x,a)[Vh+1stale(x′)−Vh+1fresh(x′)]. This term is not a martingale difference and is not controlled by the usual self-normalized concentration argument. Moreover, the server cannot correct it from the uploaded response vector alone without access to the historical next states.
Our stepwise backward synchronization in Section 3.2 resolves this dependency. The server first updates and broadcasts the fresh step-(h+1) model. Each agent then reevaluates its historical next states using this model and uploads the resulting step-h response vector. Repeating this procedure backward from H to 1 reproduces the centralized regression updates through fixed-dimensional statistics.
The new experiments in Appendix C.4, Figure 12 provide empirical failure cases: on C2 and C4, the stale-target variant exhibits sustained regret growth over the tested budgets, while fresh-target Fed-LSVI achieves substantially lower regret. These examples demonstrate that stale-response errors can materially affect learning performance.