acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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 , where is the feature dimension, is the horizon length, is the number of agents, and 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 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.

Primary area:
reinforcement learning
Keywords:
Reinforcement Learning, Decision making

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_CCjEOpenReview ↗
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 �0��0�, it establishes �1��1� regret and communication cost logarithmic in �2��2� with an extension to mildly heterogeneous environments. Synthetic experiments verifies regret, collaboration gains and communication scaling.

Critical strengths
  1. 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.

  2. 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
  1. 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.

  2. Limited comparative evidence. Appendix B only evaluates small synthetic environments without competing methods or synchronization ablations. It uses β=Hd\beta=Hd differing from the theoretical choices and tests heterogeneity only at ξ=1/T\xi=1/\sqrt T. 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
  1. What additional technical obstacle prevent a straightforward federated implementation of LSVI-UCB-RareSwitch from obtaining comparable regret, and communication guarantee?

  2. 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?

  3. [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

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+1V_{h+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 γ\gamma 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+1V_{h+1} available before agents construct their step-hh 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)(h+1) value function is not yet available when the step-hh 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′)].\Delta b_h^m=\sum_{(x,a,r,x')\in\mathcal D_h^m}\phi(x,a) \left[V_{h+1}^{\mathrm{stale}}(x')-V_{h+1}^{\mathrm{fresh}}(x')\right]. 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)(h+1) model. Each agent then reevaluates its historical next states using this model and uploads the resulting step-hh response vector. Repeating this procedure backward from HH to 11 reproduces the centralized regression updates through fixed-dimensional statistics.

The new experiments in Appendix C.4, Figure 12 provide empirical failure cases: on C2C_2 and C4C_4, 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.

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 MM agents collect trajectories in parallel under the shared policy. Even if their samples are ordered sequentially for analysis, the policy cannot react between the MM 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 O(MHd2)O(MHd^2) 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 C1C_1 and C3C_3, but incurs substantially higher regret on C2C_2 and C4C_4. 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 TT. Appendix D.2, Figure 16 compares this scaled coefficient with the original fixed coefficient. Both choices produce decreasing Regret⁡(T)/T\operatorname{Regret}(T)/\sqrt T 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.

Reviewer_TcrAOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper investigates the problem of federated online reinforcement learning with linear function approximation and proposes an algorithm called Fed-LSVI, based on the classic LSVI-UCB framework. To reduce communication overhead, the method employs an event-triggered mechanism governed by the determinant of the covariance matrix. Furthermore, it utilizes a stepwise backward synchronization mechanism, which allows clients to compute Bellman regression targets using the most up-to-date value functions while exchanging only local statistics—thereby eliminating the need to upload raw trajectories. The authors prove that, in a homogeneous linear Markov Decision Process (MDP) setting, the algorithm achieves an upper bound on cumulative regret of O~(Md3H4T)\widetilde{O}(\sqrt{Md^3H^4T}), while keeping the number of communication rounds logarithmic with respect to TT. These results are also extended to scenarios involving mild environmental heterogeneity. Finally, the authors conduct numerical experiments across four synthetic linear MDP environments of varying scales. By varying the number of episodes and the number of clients, they empirically validate the growth trend of the regret, the multi-agent speedup in average regret, and the logarithmic scaling of communication rounds, while also providing experimental results for settings with mild heterogeneity.

Critical strengths
  1. This paper extends the classic LSVI-UCB algorithm to a federated reinforcement learning framework, proposing "Fed-LSVI"—a solution with theoretical guarantees for federated online reinforcement learning under linear function approximation. The paper provides a comprehensive theoretical analysis, including upper bounds on regret and communication complexity for both homogeneous and heterogeneous environments, with supporting lemmas and derivations detailed in the appendix.
  2. By employing an event-triggered synchronization mechanism and a stepwise backward synchronization mechanism, this approach reduces communication frequency while avoiding the transmission of raw trajectory data. Furthermore, it maintains regret bounds on the same order of magnitude as existing multi-agent linear reinforcement learning methods. Consequently, the algorithm is well-suited for federated scenarios characterized by decentralized data storage and communication constraints.
Critical weaknesses
  1. The theoretical innovation of the paper requires further emphasis. The core of the paper appears to extend a single-agent framework to a multi-agent setting, providing proofs within the context of federated learning and its associated constraints. The paper has yet to theoretically establish whether the proposed synchronization protocol offers a unique, irreplaceable advantage over other potential federated LSVI-UCB schemes—for instance, by providing a lower bound that characterizes the fundamental trade-off between the number of communication rounds and the regret. Consequently, while the current results demonstrate the effectiveness of the proposed method, they fall short of establishing the theoretical necessity or optimality of its communication mechanism.
  2. The experimental section lacks direct comparisons with alternative synchronization strategies. The primary contribution of this work lies in reducing communication overhead—via a determinant-based event-triggered synchronization mechanism and a stepwise backward synchronization mechanism—while maintaining low regret. However, the current experiments merely illustrate how regret and communication rounds evolve with the scale of training; they fail to benchmark the proposed approach against methods such as full synchronization at every round or fixed-interval synchronization. Furthermore, there is no analysis of the trade-off between regret and communication costs as a function of the trigger parameter γ\gamma. As a result, the experiments do not sufficiently demonstrate the practical advantages of the event-triggered mechanism over simpler synchronization strategies, nor do they adequately isolate the specific contribution of the stepwise backward synchronization mechanism.
Questions for authors
  1. Given that Coop-LSVI and Async-Coop-LSVI-UCB already achieve the same order of regret, what are the primary theoretical contributions of Fed-LSVI beyond these existing methods? Does its contribution lie mainly in achieving low regret and low communication complexity under statistics-only communication constraints, or does it offer other, stronger theoretical guarantees? Specifically, is the proposed synchronization mechanism optimal in terms of communication efficiency, or do other federated synchronization schemes exist that could yield the same theoretical results? Clarifying the distinction between "achieving existing theoretical guarantees under stricter communication constraints" and "proposing a learning mechanism with additional theoretical advantages" would help in better assessing the novelty of this work.
  2. The current paper evaluates the growth trends of regret and communication rounds separately, but it does not yet directly demonstrate the advantages of the proposed synchronization mechanism over other strategies. Could the authors include comparisons—under identical environments and training budgets—against strategies such as full synchronization at every episode and synchronization at fixed intervals? Furthermore, by varying the trigger parameter γ\gamma, could the authors illustrate the regret–communication trade-off under different communication budgets? Additionally, would it be possible to include an ablation study on the "Stepwise Backward Synchronization" to highlight its specific contribution to empirical performance compared to a synchronization scheme that relies on stale Bellman targets? Such results would help determine whether the two proposed synchronization mechanisms possess independent and significant practical value.
6 comments

W1: Theoretical novelty and the communication lower bound

Our theoretical contribution is a synchronization design that preserves multi-agent speedup while reducing both communication rounds and total communication volume. Achieving these guarantees requires controlling the interaction between parallel sampling, local triggering, and recursively updated Bellman targets. Our new lower bound further establishes that, after separating the O(Md)O(Md) burn-in term, Fed-LSVI's dependence on dHdH matches the communication requirement of the shared-policy class up to logarithmic factors. To the best of our knowledge, Fed-LSVI improves upon all previously known communication-round bounds in the same setting while preserving the cooperative regret guarantee.

1. The synchronization protocol and its analysis.

The adaptive threshold controls the regret accumulated during parallel sampling between synchronizations. All agents collect data concurrently, each trigger uses local statistics, and the shared policy and global covariance matrices remain fixed within a communication round. The analysis therefore needs to translate local trigger conditions into a bound on the cumulative bonuses across all agents. In Lemma H.5 and Appendix H.3.5, agent-wise auxiliary covariance matrices connect these bonuses to the locally accumulated samples. For rounds with large determinant growth, Equation (23) contains a round-length factor multiplying the determinant ratio. The inverse-round-length threshold in Equation (4) cancels this factor before the final episode of the round, yielding Equation (24). This threshold design links the frequency of communication to the regret incurred between synchronizations and supports the joint regret and communication guarantees.

Stepwise backward synchronization resolves the changing Bellman targets through fixed-dimensional statistic exchange. With a single upload of response statistics for all stages, the latest Vh+1V_{h+1} is still unavailable when agents construct bhmb_h^m. Using the previous value function introduces a stale-response drift into the regression targets. Our protocol first updates and broadcasts the step-(h+1)(h+1) model, then has each agent recompute its step-hh response vector from historical samples using the latest Vh+1V_{h+1}. Repeating this procedure backward eliminates this source of drift and reproduces the pooled regression update while keeping raw trajectories local; see Section 3.2 and Equations (6)–(8). The ablation in Appendix C.4, Figure 12 demonstrates the practical benefit: using the latest Vh+1V_{h+1} substantially reduces regret on C2C_2 and C4C_4 at larger episode budgets, with similar performance on C1C_1 and C3C_3.

2. A communication lower bound and matching dependence on dHdH.

After separating the TT-independent O(Md)O(Md) burn-in term, Fed-LSVI achieves O~(dH)\widetilde O(dH) communication rounds, matching the Ω(dH)\Omega(dH) lower bound up to logarithmic factors while preserving multi-agent speedup.

Our new Theorem 4 in Section 4.4, proved in Appendix K, establishes that achieving square-root expected regret in MTMT requires a deterministic communication budget of at least Ω(dH)\Omega(dH) for the class of algorithms that deploy a shared deterministic Markov policy and keep it fixed within each communication round.

Meanwhile, our main result in Theorems 1 and 3 preserves the cooperative regret guarantee and the M\sqrt M speedup in average per-agent regret, with K≤1+2Md+dHlog⁡2log⁡ ⁣(1+MTd).K\le 1+2Md+\frac{dH}{\log 2}\log\!\left(1+\frac{MT}{d}\right). Existing communication-round guarantees are O~(MdH)\widetilde O(MdH) for Coop-LSVI and O~(M2dH)\widetilde O(M^2dH) for Async-Coop-LSVI-UCB, carrying additional factors of MM and M2M^2, respectively; see Section 4.3.

3. Empirical evidence for the regret–communication trade-off.

The comparisons in Appendix C complement these theoretical results by evaluating Fed-LSVI against a broad set of natural alternatives, including independent Fed-LSVI, independent LSVI-UCB, full synchronization, periodic synchronization under a matched communication budget, stale-response updates under the same event-triggered schedule, and raw-data-sharing Coop-LSVI. Across these comparisons, the alternatives typically sacrifice either cooperative speedup, regret performance, communication frequency, or total communication volume. Together with Theorems 1 and 3, these results support that our synchronization mechanism achieves stronger joint regret and communication guarantees while maintaining a favorable empirical regret–communication trade-off.

Q1: Improvements over existing cooperative methods and communication efficiency

Fed-LSVI not only achieves existing regret guarantees under stricter communication constraints, but also proposes a learning mechanism with additional theoretical advantages in communication efficiency. It improves both communication rounds and total communication volume while preserving the cooperative regret order and multi-agent speedup. Statistics-only communication is the algorithmic design that enables the improvement in total communication volume, while our new lower bound further characterizes the communication efficiency of the proposed synchronization mechanism.

1. Stronger joint regret and communication guarantees.

Fed-LSVI achieves O~(Md+dH)\widetilde O(Md+dH) communication rounds and logarithmic growth in total communication volume with TT, while retaining the M\sqrt M speedup in average per-agent regret.

  • Communication rounds. Fed-LSVI improves the communication-round bound from O~(MdH)\widetilde O(MdH) to O~(Md+dH)\widetilde O(Md+dH) while preserving the cooperative regret guarantee. To the best of our knowledge, the existing communication-round guarantees are O~(MdH)\widetilde O(MdH) for Coop-LSVI and O~(M2dH)\widetilde O(M^2dH) for Async-Coop-LSVI-UCB, under the counting convention discussed in Section 4.3. With γ=T/(Md)\gamma=T/(Md) and T≥MdT\ge Md, Theorems 1 and 3 give =\widetilde O\left(\sqrt{Md^3H^4T}\right), \qquad K=\widetilde O(Md+dH).$$ Thus, Fed-LSVI improves the communication-round bound while retaining the $\sqrt M$ improvement in average per-agent regret. In particular, the multiplicative dependence on $M$ and $H$ in the $\widetilde O(MdH)$ bound is replaced by an additive dependence.
  • Total communication volume. Fed-LSVI improves the dependence of total communication volume on TT from O(T)O(T) to O(log⁡T)O(\log T) for fixed M,d,HM,d,H. Coop-LSVI and Async-Coop-LSVI-UCB exchange raw trajectory data, resulting in total communication that scales linearly with TT. Fed-LSVI instead communicates sufficient statistics, requiring O(MHd2)O(MHd^2) scalars per round. As established in Section 4.3, its total communication is M^2d^3H+ Md^3H^2\log\left(1+\frac{MT}{d}\right) \right),$$ which grows only logarithmically with $T$ for fixed $M,d,H$.

2. Communication efficiency and alternative synchronization schemes.

After separating the TT-independent O(Md)O(Md) burn-in term, Fed-LSVI achieves O~(dH)\widetilde O(dH) communication rounds, matching the Ω(dH)\Omega(dH) lower bound in Theorem 4 up to logarithmic factors for the shared-policy class while preserving the cooperative regret guarantee and multi-agent speedup. This establishes the near-optimality of the dHdH dependence of our communication-round complexity within this class.

The comparisons in Appendix C further show that natural alternatives may achieve performance comparable to Fed-LSVI along some dimensions, but each sacrifices another key aspect of the regret–communication trade-off. Full synchronization can achieve slightly lower regret at large episode budgets, but requires substantially more communication. Periodic synchronization uses the same final number of synchronization events, but incurs higher regret. The stale-response variant retains the same event-triggered communication schedule, but can suffer substantially larger regret, demonstrating the importance of fresh backward updates. Independent learning avoids communication, but loses the cooperative speedup. Raw-data-sharing Coop-LSVI achieves comparable regret and communication rounds, but requires substantially larger communication volume. Thus, while these common alternatives can match Fed-LSVI in individual aspects, none of them achieves the same combination of cooperative regret performance, low synchronization frequency, and low communication volume observed for Fed-LSVI.

W2 and Q2: Comparisons with alternative synchronization strategies and mechanism ablations

The new comparisons show that Fed-LSVI achieves comparable regret to full synchronization with substantially fewer rounds, and lower regret than periodic synchronization on C2C_2–C4C_4 under matched communication budgets. The ablation also shows the benefit of using the latest Vh+1V_{h+1} on C2C_2 and C4C_4, while the γ\gamma sweep demonstrates the regret–communication trade-off. These results appear in Appendices C and E. To address the requested controlled comparisons, the full-synchronization, periodic-synchronization, and stale-target experiments use identical environments, agent counts, and episode budgets across the methods being compared. The periodic comparison additionally matches the final number of synchronization rounds for each episode budget and training seed.

1. Comparison with synchronization after every episode.

Fed-LSVI retains comparable regret performance with substantially fewer synchronization rounds than full synchronization. In Appendix C.2, Figures 9–10, full synchronization performs the same stepwise backward update after every nonterminal episode.

Figure 9 shows that full synchronization achieves slightly lower regret at larger episode budgets. Its communication cost is substantially higher: in Figure 10, the normalized communication count K/log⁡(1+MT/d)K/\log(1+MT/d) remains nearly flat for Fed-LSVI after the initial phase, while increasing rapidly for full synchronization.

2. Comparison with periodic synchronization under matched communication budgets.

Under matched communication budgets, Fed-LSVI achieves substantially lower normalized regret than periodic synchronization at larger episode budgets in C2C_2–C4C_4. Appendix C.3, Figure 11 matches the final number of synchronization events for each episode budget and training seed. Both methods use fresh-target backward updates, so this comparison focuses on when communication occurs.

The excess regret of periodic synchronization is accumulated before its first synchronization, whereas the event-triggered schedule enables earlier policy improvement. This comparison supports the benefit of allocating a given communication budget according to the information collected during training.

3. Regret–communication trade-off through varying γ\gamma.

Smaller γ\gamma leads to more frequent synchronization and generally lower regret, while larger γ\gamma saves communication with higher regret. In Appendix E, Figure 17, we sweep γ\gamma on a logarithmic grid while holding the environment, number of agents, and episode budget fixed and using paired training seeds. We report both cumulative regret and synchronization counts to directly evaluate the regret–communication trade-off under these controlled conditions.

Smaller thresholds favor rapid policy improvement when communication is affordable, while larger thresholds favor communication savings when additional regret is acceptable.

4. Ablation of stepwise backward synchronization.

Using the latest Vh+1V_{h+1} in the stepwise backward update substantially reduces regret on C2C_2 and C4C_4 at larger episode budgets, with similar performance on C1C_1 and C3C_3. In Appendix C.4, Figure 12, we retain the same determinant-based trigger rule and replace the fresh-target backward update with a stale-target variant. This variant recomputes historical Bellman targets using value functions from the previous synchronization, instead of using the latest Vh+1V_{h+1} updated within the current synchronization.

Fed-LSVI also achieves comparable regret and synchronization counts to Coop-LSVI while transmitting substantially fewer bytes and requiring less training time on the tested instance. This comparison appears in Appendix C.5, Figure 13, with bidirectional communication volume and training time reported in Appendix C.6, Figure 14.

Reviewer_xUmqOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes Fed-LSVI for federated online learning in episodic linear MDPs. It combines determinant-based synchronization with backward, stepwise recomputation of regression targets, allowing agents to retain raw trajectories locally. The paper establishes regret and communication guarantees, extends the analysis to bounded model misspecification, and provides synthetic experiments.

Critical strengths
  • The paper identifies a substantive obstacle to statistics-only communication: regression targets change with downstream value estimates. The backward synchronization protocol addresses this issue directly.
  • The analysis accommodates policies that remain fixed between synchronizations and establishes logarithmic dependence on T in communication cost, with explicit dependence on the other problem parameters.
  • The algorithm and its motivation are clearly presented. The discussion of stale response statistics helps explain the distinction from prior cooperative RL methods.
Critical weaknesses
  1. A proof step in Appendix I needs clarification. Equation (36) gives a determinant ratio of at least γ/Δᵢ, whereas the argument leading to Equation (40) appears to require its logarithm to be at least γ/Δᵢ. The former only implies a logarithmic lower bound of log(γ/Δᵢ). As written, this does not justify the claimed correction to the prior communication analysis. This concern is specific to Appendix I; it does not by itself invalidate the separate proof in Appendix G.

  2. The experiments do not isolate the benefits of the proposed protocol. Appendix B examines scaling trends but provides no direct comparison with independent local learning, periodic synchronization, or stale-response updates. Matched-budget comparisons would help establish the practical contribution of the synchronization design.

  3. The computation–communication trade-off is insufficiently characterized. Agents revisit their historical buffers to recompute response vectors, and each synchronization requires H sequential update stages. The paper reports overall experimental runtime but does not quantify these costs or compare them with alternative synchronization schemes.

  4. The heterogeneity evidence is narrow. Appendix B.1 sets the heterogeneity level to ξ = 1/√T. This tests a shrinking-misspecification regime rather than robustness to fixed heterogeneity. A sweep over fixed ξ would clarify the method’s limitations.

  5. The novelty claims should also consistently specify the setting and communication restrictions. Likewise, retaining trajectories locally should be distinguished from providing a formal privacy guarantee, consistent with the qualification already made in the Ethics Statement.

Questions for authors
  1. What is the total local computation cost of repeatedly recomputing full-history response vectors?
  2. Can the algorithm be combined with secure aggregation or differential privacy mechanisms?
  3. How important is the stepwise backward synchronization empirically? A comparison with a stale-response variant would be helpful.
  4. Does the communication cost include server-to-agent broadcasts of (wh,Λh)(w_h, \Lambda_h)?
  5. How should one choose γ\gamma when T is unknown?
7 comments

W1: Clarification of the communication-round analysis

This concern appears to arise from a conflation of two different trigger conditions: Equation (36) in the submitted manuscript reproduces the log-determinant-ratio trigger of Hsu et al. (2024), rather than the determinant-ratio trigger of Fed-LSVI in Equation (4). We retain their original algorithm and trigger condition unchanged; our contribution in that appendix is solely to correct the communication-round analysis using our proof technique. In particular, the logarithm was already present in Equation (36) of the submitted manuscript, which is now Equation (40) in Appendix L of the revised manuscript.

Specifically, let σi\sigma_i denote the ii-th synchronization episode, Δi=σi−σi−1\Delta_i=\sigma_i-\sigma_{i-1}, and (mi,hi)(m_i,h_i) the agent-step pair that triggers synchronization. Hsu et al.'s original trigger condition and the fact that the aggregated covariance update dominates the triggering agent's update imply

\frac{\det\left(\Lambda_{h_i}^{\sigma_i+1,\mathrm{ser}}\right)} {\det\left(\Lambda_{h_i}^{\sigma_{i-1}+1,\mathrm{ser}}\right)} \ge \log \frac{\det\left(\Lambda_{h_i}^{\sigma_{i-1}+1,\mathrm{ser}} +\Lambda_{h_i}^{m_i,\sigma_i,\mathrm{loc}}\right)} {\det\left(\Lambda_{h_i}^{\sigma_{i-1}+1,\mathrm{ser}}\right)} \ge \frac{\gamma}{\Delta_i}.$$ Thus, the logarithmic lower bound follows directly from their existing synchronization condition. For $I_1=\{i:\Delta_i\le\alpha\}$, summing these inequalities and using the nonnegative log-determinant increments at all other steps gives $$|I_1|\frac{\gamma}{\alpha} \le \sum_{i\in I_1}\frac{\gamma}{\Delta_i} \le \sum_{h=1}^{H}\sum_{i=1}^{K} \log \frac{\det\left(\Lambda_h^{\sigma_i+1,\mathrm{ser}}\right)} {\det\left(\Lambda_h^{\sigma_{i-1}+1,\mathrm{ser}}\right)} \le dH\log\left(1+\frac{MT}{d}\right).$$ The last inequality follows by telescoping and applying the determinant upper bound with $\lambda=1$. This is Equation (40) in the submitted manuscript, now Equation (44) in Appendix M.2. The correction explicitly sums over all steps to accommodate the fact that the triggering pair $(m_i,h_i)$ may vary across synchronization episodes. **This is a correction to Hsu et al.'s proof under their unchanged log-ratio trigger.** Fed-LSVI's determinant-ratio trigger has a separate communication-round analysis in Appendix G of the submitted manuscript, now Appendix J.

W2 and Q3: Comparative experiments and the role of stepwise backward synchronization

Our synchronization design balances regret and communication cost: the event-triggered rule controls synchronization frequency, while the stepwise backward update avoids stale-response errors by constructing Bellman targets using the latest Vh+1V_{h+1} updated within the current synchronization. Together, these components support the joint regret and communication guarantees in Theorems 1 and 3. To demonstrate their benefits empirically, we have added five groups of comparisons with local independent learning, full synchronization, periodic synchronization, stale-response updates, and Coop-LSVI in Appendix C.1–C.5. We address the specific concerns below.

1. Comparison with local independent learning: the benefit of collaboration.

The independent baselines use only local trajectories: independent Fed-LSVI runs with M=1M=1 and determinant-based policy updates, while independent LSVI-UCB updates before every episode. As shown in Appendix C.1, Figure 7, Fed-LSVI achieves substantially lower final total regret than both baselines as the episode budget increases across the tested instances. We also vary the number of agents while holding the environment and episode budget fixed. Figure 8 shows that the total regret of both independent baselines grows approximately linearly with MM, whereas that of Fed-LSVI grows more slowly, resulting in decreasing average regret per agent. These comparisons demonstrate the multi-agent speedup enabled by sharing information across agents.

2. Comparison with full synchronization: communication savings with comparable regret.

The full-synchronization baseline performs the same stepwise backward update as Fed-LSVI after every nonterminal episode. As reported in Appendix C.2, Figures 9–10, full synchronization achieves slightly lower regret at large TT, but requires substantially more synchronization events. Fed-LSVI retains comparable regret performance while greatly reducing synchronization frequency. This comparison illustrates the regret–communication trade-off introduced by the determinant-based trigger.

3. Comparison with periodic synchronization: lower regret under a matched synchronization budget.

To directly address the request for matched-budget comparisons, Appendix C.3 matches the final number of synchronization events for each episode budget and training seed using the paired Fed-LSVI run. The periodic baseline performs the same fresh backward update at fixed intervals.

As shown in Figure 11, Fed-LSVI achieves lower normalized regret across all four settings under the matched synchronization count, with the advantage becoming substantial at larger episode budgets in C2C_2–C4C_4. In these instances, at the largest episode budget, the excess regret of periodic synchronization is accumulated before its first synchronization. This comparison highlights the importance of allocating communication adaptively according to the information collected: the event-triggered schedule enables earlier policy improvement while using the same final number of synchronization events.

4. Comparison with stale-response updates: the benefit of fresh Bellman targets.

In Appendix C.4, the stale-response variant retains the same determinant-based triggering rule, but recomputes the historical Bellman targets using value functions from the previous synchronization. Fed-LSVI instead constructs the step-hh targets using the latest Vh+1V_{h+1} updated within the current synchronization.

As shown in Figure 12, the two methods perform similarly in C1C_1 and C3C_3, while stale-response updates incur substantially higher regret as the episode budget increases in C2C_2 and C4C_4. In these latter instances, the regret of the stale-response variant exhibits an approximately linear growth with TT over the tested range, suggesting that the stale-response error can accumulate persistently rather than vanish with additional data. The empirical effect is therefore instance dependent, but can be substantial. These observations complement the discussion in Section 3.2, where using Vh+1V_{h+1} from the previous synchronization introduces an additional stale-response drift term. The ablation provides direct evidence that refreshing Bellman targets within each backward synchronization can materially improve learning performance.

W3, Q1: Local computation and sequential synchronization

Thank you for raising these questions. Recomputing historical Bellman targets is already part of the existing LSVI methods discussed below; it is not an additional computational burden introduced in exchange for our communication savings. Our stepwise update preserves the usual HH-stage backward recursion, while fewer synchronization events reduce how often this computation is performed.

1. Full-history recomputation and backward recursion are standard LSVI operations.

The original LSVI-UCB algorithm (Jin et al., 2020, Algorithm 1), Coop-LSVI (Dubey and Pentland, 2021, Algorithm 1 and Equation (3)), and the LSVI-based methods of Hsu et al. (2024, Equation (3.4) and Algorithms 2–3) all construct regression targets over their available historical samples using the latest value function Vh+1V_{h+1}. Since the target rh+Vh+1(x′)r_h+V_{h+1}(x') depends on the current value estimate, historical targets must also be refreshed when that estimate changes.

These methods already perform backward updates from h=Hh=H to h=1h=1. As described in Section 3.1 and Algorithms 1–2, Fed-LSVI distributes this same computation across agents: at stage hh, agents compute their local response vectors in parallel, the server aggregates them, and the updated model is broadcast before proceeding to stage h−1h-1. Splitting this recursion into HH communication stages does not introduce an additional factor of HH in the historical-target computation. Each stage processes the samples corresponding to that stage, and the complete synchronization performs one backward sweep.

This ordering ensures that each step-hh response vector uses the latest Vh+1V_{h+1} updated within the current synchronization, avoiding the stale-response error discussed in Section 3.2. The KK synchronization cycles do contain at most HKHK sequential stagewise exchanges; their communication latency is included in the runtime measurements below.

2. Fewer synchronizations reduce repeated computation, with a clear benefit in overall runtime.

Fed-LSVI performs the backward recomputation only at synchronization events. Let S≤KS\le K be the number of such updates and nk≤Tn_k\le T the number of episodes collected by each agent before update kk. Writing A=∣A∣A=|\mathcal A|, the total historical-response computation per agent, using dense value-function evaluations, is

\le O(HAd^2KT).$$ The factor $H$ already accounts for all stages of the backward sweep. Under the parameter choice in Theorem 3, $K$ grows logarithmically with $T$ for fixed problem dimensions, giving at most $O(T\log T)$ growth for this computation. By comparison, full synchronization performs the same backward recomputation every episode and revisits historical samples $\sum_{t=1}^{T}(t-1)=\Theta(T^2)$ times per stage. Thus, reducing synchronization frequency reduces both communication and repeated historical-target computation. The runtime results in **Appendix C.6, Figure 14b** support this benefit. With the environment, number of agents, and episode budget held identical across methods, full synchronization takes substantially longer than Fed-LSVI on the tested instance. Its more frequent synchronization requires more communication and more full-history backward updates, consistent with the larger measured training time. In addition, under the matched synchronization budget in **Appendix C.3**, the periodic-synchronization baseline and Fed-LSVI have the same number of synchronization events and perform the same fresh backward update at each synchronization. Thus, they perform the same number of full-history backward sweeps, providing a direct comparison between event-triggered and periodic synchronization under the same synchronization budget. These measurements include both computation and communication, while excluding process startup and offline policy evaluation. Finally, **Fed-LSVI and the stale-response variant have similar measured runtimes**. Thus, on this instance, propagating fresh Bellman targets through the sequential backward stages does not produce an appreciable runtime penalty. Together with the regret comparisons in **Appendix C.4, Figure 12**, this shows that fresh backward updates can improve learning performance while maintaining comparable training time.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.