Paper deep dive
Provably Efficient Federated Reinforcement Learning with Linear Function Approximation and Logarithmic Communication Cost
Zihang Liang, Haochen Zhang, Lingzhou Xue
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 94%
Last extracted: 9/2/2026, 4:24:32 AM
Summary
The paper introduces Fed-LSVI, a provably efficient federated reinforcement learning algorithm for online RL with linear function approximation in episodic Markov decision processes. It addresses the high communication cost and privacy issues of sharing raw trajectories by using compressed sufficient statistics and a determinant-based event-triggered synchronization mechanism. Fed-LSVI achieves a regret bound of O~(sqrt(Md^3H^4T)) and reduces communication cost to logarithmic dependence on the number of episodes T.
Entities (12)
Relation Signals (9)
Fed-LSVI → achieves → Regret Bound
confidence 95% · We prove that Fed-LSVI achieves a regret bound of \widetilde{\mathcal O}(\sqrt{Md^3H^4T})
Lingzhou Xue → affiliatedwith → Pennsylvania State University
confidence 95% · Lingzhou Xue ... Affiliation: Department of Statistics, The Pennsylvania State University
Zihang Liang → affiliatedwith → Pennsylvania State University
confidence 95% · Zihang Liang Affiliation: Department of Statistics, The Pennsylvania State University
Haochen Zhang → affiliatedwith → Pennsylvania State University
confidence 95% · Haochen Zhang Affiliation: Department of Statistics, The Pennsylvania State University
Fed-LSVI → appliesto → Episodic Markov Decision Processes
confidence 95% · Fed-LSVI ... in episodic Markov decision processes
Fed-LSVI → reduces → Communication Cost
confidence 95% · Fed-LSVI reduces the communication cost to only logarithmic dependence on T
Fed-LSVI → uses → Linear Function Approximation
confidence 95% · Fed-LSVI is the first provably efficient federated algorithm for online reinforcement learning with linear function approximation
Fed-LSVI → usesmechanism → Event-Triggered Synchronization
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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 $\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.
Tags
Links
- Source: https://arxiv.org/abs/2609.00193v1
- Canonical: https://arxiv.org/abs/2609.00193v1
Trouble viewing inline? Open PDF directly →
Full Text
124,882 characters extracted from source content.
Expand or collapse full text
Provably Efficient Federated Reinforcement Learning with Linear Function Approximation and Logarithmic Communication Cost Zihang Liang Affiliation: Department of Statistics, The Pennsylvania State University Haochen Zhang Affiliation: Department of Statistics, The Pennsylvania State University Lingzhou Xue †thanks: Zihang Liang and Haochen Zhang are co-first authors who contributed equally to this paper. Lingzhou Xue is the corresponding author (Email: lzxue@psu.edu). Affiliation: Department of Statistics, The Pennsylvania State University 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) O( 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 Reinforcement learning (RL) studies sequential decision-making in unknown environments and is typically formulated as learning an optimal policy within a Markov decision process (MDP) (Sutton and Barto, 2018). In modern RL, designing sample-efficient algorithms for problems with large state and action spaces remains a central challenge. A widely adopted approach is function approximation, which enables scalable learning by representing value functions within a restricted function class. To build a rigorous foundation for this paradigm, recent work has focused on establishing provable regret guarantees for online RL with linear function approximation, where value functions are modeled as linear functions of known features. This literature is largely anchored by two prominent frameworks. The first is the linear MDP setting (Jin et al., 2020; He et al., 2023), which assumes that both transition dynamics and reward functions admit linear representations in terms of known features. The second is the linear mixture MDP setting (Ayoub et al., 2020; Zhou et al., 2021a; Zhou and Gu, 2022), which instead models transitions as a mixture over a set of base kernels. In many real-world applications, the data collection capacity of a single agent is a primary bottleneck. This motivates cooperative multi-agent reinforcement learning (MARL), where multiple agents collaboratively explore a shared environment and jointly learn an optimal policy. By sharing exploration across agents, cooperative MARL can improve sample efficiency. Theoretical foundations for MARL have recently begun to emerge in the literature. Notably, Dubey and Pentland (2021) proposed the first provably efficient cooperative MARL algorithm with function approximation, extending the single-agent LSVI-UCB framework (Jin et al., 2020) to demonstrate that parallel exploration can be achieved with low communication overhead. Building on this work, Min et al. (2023) studied cooperative linear MDPs with asynchronous communication via a central server and established both regret and communication guarantees. More recently, Hsu et al. (2024) introduced randomized exploration strategies with provable guarantees for broader function classes. However, these cooperative approaches typically require agents to share raw trajectories for collaborative policy learning. This reliance introduces substantial communication overhead and privacy concerns, particularly in real-world applications where sequential decision-making is distributed across institutions or personal devices. In healthcare, for example, RL is increasingly used to optimize dynamic treatment regimes (Murphy, 2003), where treatment decisions are sequentially adapted to patient histories, such as sepsis management in intensive care units (Komorowski et al., 2018). In such settings, because patient-level trajectories are highly sensitive and often distributed across different hospitals or clinical sites, transmitting raw clinical data to a central learner is often rendered impractical by privacy regulations and institutional constraints. Similar bottlenecks exist in mobile edge computing and recommender systems, where local user interaction histories are generated locally and may contain sensitive behavioral patterns (Kairouz and McMahan, 2021). To circumvent these barriers, it is critical to develop collaborative RL algorithms that do not rely on raw data exchange. Federated learning (FL) (McMahan et al., 2017) provides a natural paradigm to achieve this goal: agents keep raw data locally and only transmit aggregated summary statistics or model updates to a central server. This naturally raises the following question: Can we design federated algorithms for online RL with linear function approximation that are simultaneously sample-efficient and communication-efficient? Designing such federated algorithms presents two primary technical challenges. First, to satisfy the privacy and communication constraints of the federated setting, agents cannot transmit their local raw trajectories to the server. Instead, the algorithm must identify compressed sufficient statistics that allow the central server to perform policy and value-function updates. While this is straightforward in tabular MDPs through statistics such as state-action visitation counts (Zheng et al., 2024; Zheng et al., 2025a), online RL with linear function approximation makes this process more challenging, and constructing the corresponding statistics becomes non-trivial. Second, and more fundamentally, classical LSVI-type algorithms rely on a backward update structure: the regression response at step h depends on the updated value-function estimate at step h+1h+1. Because the central server lacks access to local raw trajectories, a conventional one-shot communication scheme would force the step-h update to rely on sufficient statistics computed using stale value estimates at step h+1h+1. This staleness introduces a severe bias term, which is difficult to control in the regret analysis and may even destroy the sublinear regret guarantee. Therefore, designing a successful federated LSVI algorithm requires a carefully designed synchronization mechanism to address this stale-response issue. In this work, we provide an affirmative answer to this important open question. We propose the first federated reinforcement learning (FRL) algorithm for online RL with linear function approximation, and our algorithm achieves sublinear regret while incurring a communication cost that scales only logarithmically with the total number of episodes. Our results show that, even when raw trajectories remain strictly local, agents can collaboratively achieve statistically efficient exploration without suffering from a communication bottleneck. Our main contributions are summarized as follows: Algorithm Design. We propose Fed-LSVI, the first provably efficient federated algorithm for online RL with linear function approximation in the literature. Our algorithm relies on two core components: a determinant-based event-triggered synchronization mechanism and a stepwise backward synchronization protocol. The event-triggered mechanism prevents redundant communication, bounding the total communication rounds logarithmically. Meanwhile, the stepwise backward protocol introduces a dedicated solution to address the stale-response issue in a federated LSVI-type algorithm. Rather than aggregating all response statistics in a single batch, synchronization proceeds backward through the steps. Once the server updates and broadcasts the step-(h+1)(h+1) model, agents use this latest global value function to construct the step-h summary statistics, which are then transmitted to the server for the step-h model update. This carefully designed stepwise backward procedure keeps each regression target consistent with the most up-to-date global value estimate, achieving statistically efficient exploration while maintaining local trajectories private. Regret Guarantees. We establish regret upper bounds for Fed-LSVI in both homogeneous and misspecified settings, matching the best-known regret scaling in online MARL with linear function approximation (Min et al., 2023; Hsu et al., 2024). In the homogeneous setting, Fed-LSVI achieves a regret bound of ~(Md3H4T) O( Md^3H^4T) (Theorem 1), confirming that our communication-efficient protocol does not compromise statistical efficiency. Furthermore, we extend our analysis to a misspecified setting with agent-wise heterogeneity (Theorem 2), where each agent interacts with a ξ-approximate linear MDP. We show that Fed-LSVI remains robust to mild agent-wise heterogeneity. In particular, when the misspecification level satisfies ξ=~(d/(MT))ξ= O( d/(MT)), our algorithm recovers the same regret bound as in the homogeneous setting. Communication Cost. We prove that Fed-LSVI incurs a communication cost, measured by the total number of transmitted scalars, that scales only logarithmically with T in both the homogeneous and misspecified settings. This logarithmic dependence is driven by two properties: Our event-triggered mechanism ensures that the total number of communication rounds is logarithmic in T (Theorem 3), and each round requires transmitting only (Md2H)O(Md^2H) scalars between the agents and the server. This represents an exponential improvement over prior cooperative RL algorithms(Dubey and Pentland, 2021; Min et al., 2023; Hsu et al., 2024), which require sharing local raw trajectories and then suffer from communication costs that scale linearly with T. Thus, Fed-LSVI significantly reduces communication overhead without transmitting raw trajectories, strictly respecting the privacy constraints inherent in federated learning. 2 Related Work Near-Optimal Reinforcement Learning. In the single-agent setting, the literature most relevant to our work spans near-optimal tabular RL and RL with linear function approximation. In tabular RL, algorithms are typically categorized into model-based and model-free approaches. A large body of work has focused on model-based algorithms (Agarwal et al., 2020; Agrawal and Jia, 2017; Auer et al., 2008; Azar et al., 2017; Dann et al., 2019; Zanette and Brunskill, 2019; Zhang et al., 2024b; Zhang et al., 2021; Zhou et al., 2023). Notably, Zhang et al. (2024b) proposed an algorithm achieving a regret bound of O~(minSAH2T,T) O( \ SAH^2T,\,T\), which matches the information-theoretic lower bound. There is also a large body of work on model-free methods that has progressively narrowed the theoretical gap, including Jin et al. (2018); Li et al. (2023); Ménard et al. (2021); Yang et al. (2021); Zhang et al. (2020); Zheng et al. (2025b); Zhang et al. (2025b); Zhang et al. (2026b). Several works (Zhang et al., 2020; Ménard et al., 2021; Li et al., 2023; Zhang et al., 2025b) achieved the near-optimal regret bound O~(SAH2T) O( SAH^2T). The literature on RL with linear function approximation can in turn be divided according to the structural assumptions imposed on the MDP. One line studies linear MDPs (Yang and Wang, 2019; Jin et al., 2020; Wei et al., 2021; Wagenmaker et al., 2022; He et al., 2023; Zhang et al., 2024c; Zhang et al., 2026a). Foundational works established sample-efficient learning under generative-model or feature-space assumptions (Yang and Wang, 2019; Yang and Wang, 2020), and Jin et al. (2020) later introduced LSVI-UCB, the first provably efficient online algorithm without access to a generative model. Subsequent works substantially sharpened the regret guarantees for linear MDPs, culminating in nearly minimax-optimal results (Hu et al., 2022; He et al., 2023). Another line studies linear-mixture MDPs (Jia et al., 2020; Ayoub et al., 2020; Modi et al., 2020; Zhou et al., 2021a; Zhou et al., 2021b; Zhou and Gu, 2022). The near-minimax-optimal regret guarantees are also available (Zhou et al., 2021a). Furthermore, Zhou and Gu (2022) proposed a near-optimal, horizon-free algorithm for time-homogeneous linear mixture MDPs. Zhang et al. (2023) provided the near-optimal horizon-free sample complexity in the reward-free time-homogeneous setting. Low-Switching Reinforcement Learning. A closely related direction studies learning with limited switching or adaptivity, motivated by the cost of frequent policy deployment. In the tabular setting, Bai et al. (2019) established Q-learning with low switching cost, Qiao et al. (2022) characterized near-optimal regret–switching trade-offs up to logarithmic factors, and Velegkas et al. (2022) showed that positive-gap instances permit both logarithmic regret and logarithmically many policy switches. Under linear function approximation, Wang et al. (2021) proved that rare policy updates can still be combined with statistically efficient learning. Multi-Agent RL (MARL) with Event-Triggered Communications. In the multi-agent setting, the literature most relevant to our work can be divided into two directions: cooperative or parallel exploration with a shared objective, and decentralized equilibrium learning in Markov games under function approximation. The first direction is closest to our setting. Dubey and Pentland (2021) initiated provably efficient cooperative multi-agent reinforcement learning with function approximation and showed that parallel exploration can be combined with limited inter-agent communication. Building on this line, Min et al. (2023) studied cooperative linear MDPs with asynchronous communication through a central server and established regret and communication guarantees, while Hsu et al. (2024) introduced randomized exploration in cooperative multi-agent reinforcement learning and analyzed its performance under approximately linear transitions. Federated Reinforcement Learning. Recent finite-time analyses of federated reinforcement learning have mainly focused on tabular control, policy evaluation, or policy-gradient methods. In tabular value-based RL, prior works established linear speedup, communication efficiency, and heterogeneity-dependent guarantees for federated Q-learning and related methods (Khodadadian et al., 2022; Woo et al., 2023; Zheng et al., 2024; Zheng et al., 2025a; Salgia and Chi, 2024; Labbi et al., 2025; Zhang et al., 2025a; Zhang et al., 2025b). A complementary line studies federated policy evaluation or on-policy learning with function approximation, including TD-learning under Markovian sampling and heterogeneous environments (Dal Fabbro et al., 2023; Wang et al., 2024; Zhang et al., 2024a), as well as federated policy-gradient and actor-critic methods (Yang et al., 2024; Ganesh et al., 2024; Lan et al., 2025). 3 Preliminaries Episodic Markov Decision Processes. In this paper, we consider a finite-horizon episodic Markov decision process ℳ=(,,H,ℙhh=1H,rhh=1H)M=(X,A,H,\P_h\_h=1^H,\r_h\_h=1^H), where X is a measurable, possibly infinite state space, A is a finite action set, H is the horizon length, each deterministic reward function satisfies rh:×→[0,1]r_h:X×A→[0,1], and ℙh(⋅∣x,a)P_h(· x,a) denotes the transition kernel at step h∈[H]h∈[H]. Here, For any C∈ℕC , we use [C][C] to denote the set 1,2,…C\1,2,… C\. In each episode, the agent starts from an initial state x1x_1. At each step h∈[H]h∈[H], it observes a state xhx_h, chooses an action ah∈a_h , receives reward rh(xh,ah)r_h(x_h,a_h), and transitions to xh+1∼ℙh(⋅∣xh,ah)x_h+1 _h(· x_h,a_h) for each h∈[H]h∈[H]. Policies, Value Functions, and Bellman Equations. A policy is a collection π=πhh=1Hπ=\ _h\_h=1^H with πh:→Δ() _h:X→ (A), where Δ() (A) denotes the set of probability distributions over A. To evaluate the performance of different policies, we define the Q-value function and V-value function under a policy π as follows: for any (x,a)∈×(x,a) ×A, Qhπ(x,a)≔π[∑h′=hHrh′(xh′,ah′)|xh=x,ah=a],Vhπ(x)=π[∑h′=hHrh′(xh′,ah′)|xh=x].Q^π_h(x,a) _π [ _h =h^Hr_h (x_h ,a_h )|x_h=x,a_h=a ],\ V^π_h(x)=E_π [ _h =h^Hr_h (x_h ,a_h )|x_h=x ]. For any bounded function V:→ℝV:X , define [ℙhV](x,a)=x′∼ℙh(⋅∣x,a)[V(x′)].[P_hV](x,a)=E_x _h(· x,a)[V(x )]. Since the action space and the horizon are all finite, there exists an optimal policy π⋆π that achieves the optimal value Vh⋆(x)=supπVhπ(x)=Vhπ⋆(x)V_h (x)= _πV_h^π(x)=V_h^π (x) for all (x,h)∈×[H](x,h) ×[H] (Azar et al., 2017). For any (x,a,h)∈×[H](x,a,h) ×A×[H], the Bellman equation can be expressed as (VH+1π(⋅)≡VH+1⋆(⋅)≡0V_H+1^π(·)≡ V_H+1 (·)≡ 0) Vhπ(x)=a′∼πh(x)[Qhπ(x,a′)]Qhπ(x,a):=rh(x,a)+[ℙhVh+1π](x,a), \ array[]lV_h^π(x)=E_a _h(x)[Q_h^π(x,a )]\\ Q_h^π(x,a):=r_h(x,a)+[P_hV_h+1^π](x,a), array . Vh⋆(x)=maxa′∈Qh⋆(x,a′)Qh⋆(x,a):=rh(x,a)+[ℙhVh+1⋆](x,a). \ array[]lV_h (x)= _a Q_h (x,a )\\ Q_h (x,a):=r_h(x,a)+[P_hV_h+1 ](x,a). array . (1) Linear Markov Decision Processes. Let ϕ:×→ℝdφ:X×A ^d be a known feature map satisfying ‖ϕ(x,a)‖2≤1\|φ(x,a)\|_2≤ 1 for all (x,a)(x,a). We adopt the standard linear MDP assumption from the literature on linear function approximation (Yang and Wang, 2020; Jin et al., 2020; Wang et al., 2021). Definition 1 (Linear MDPs). For each step h∈[H]h∈[H], there exist an unknown vector θh∈ℝd _h ^d and an unknown vector of signed measures μh=(μh(1),…,μh(d)) _h=( _h^(1),…, _h^(d)) over X such that, for every (x,a)∈×(x,a) ×A and every measurable set ℬ⊆B , rh(x,a)=⟨ϕ(x,a),θh⟩,ℙh(ℬ∣x,a)=⟨ϕ(x,a),μh(ℬ)⟩.r_h(x,a)= φ(x,a), _h , _h(B x,a)= φ(x,a), _h(B) . Moreover, ‖θh‖2≤d\| _h\|_2≤ d and ‖μh()‖≤d\| _h(X)\|≤ d for all h∈[H]h∈[H]. Federated Reinforcement Learning. We consider an FRL setting with a central server and M agents, each interacting with an independent linear MDP ℳM. The paper studies a synchronous protocol: at common episode index t∈[T]t∈[T], each agent executes its t-th episode, starting from an initial state x1m,tx_1^m,t that may be arbitrary. Thus T is the number of episodes per agent, the total number of agent-episodes is MTMT, and the total number of interaction steps is MTHMTH. In episode t, agent m∈[M]m∈[M] generates a trajectory (xhm,t,ahm,t,rhm,t,xh+1m,t)h=1H\(x_h^m,t,a_h^m,t,r_h^m,t,x_h+1^m,t)\_h=1^H. A central server coordinates occasional synchronizations, while raw trajectories always remain on the agents. Specifically, we partition the learning process into K rounds with boundaries 1=τ1<τ2<⋯<τK+1=T+1,1= _1< _2<·s< _K+1=T+1, where round k consists of episodes τk,…,τk+1−1 _k,…, _k+1-1. All agents execute the same policy πkπ^k throughout round k. The cumulative regret over T synchronized episodes is defined as Regret(T):=∑t=1T∑m=1M(Vm,1⋆(x1m,t)−Vm,1πk(t)(x1m,t)),Regret(T):= _t=1^T _m=1^M (V_m,1 (x_1^m,t)-V_m,1^π^k(t)(x_1^m,t) ), where Vm,1⋆V_m,1 and Vm,1πV_m,1^π denote the optimal value function and V-value function of agent m’s local MDP and k(t)k(t) denotes the round containing episode t. In the homogeneous setting, where all agents share the same MDP, we omit the subscript m and write V1⋆V_1 and V1πV_1^π for simplicity. We also define the communication cost of an FRL algorithm as the number of scalars (integers or real numbers) communicated between the server and agents. 4 Algorithm Design 4.1 The Fed-LSVI Algorithm We now present Fed-LSVI under the federated reinforcement learning setting described in Section 3. The complete algorithm is given in Algorithm 1 and Algorithm 2. At the beginning of learning, the central server specifies the total number of episodes per agent T, the regularization parameter λ, the trigger parameter γ≥1γ≥ 1, and the exploration bonus parameter β>0β>0. Fed-LSVI then proceeds over communication rounds indexed by k∈1,2,…,Kk∈\1,2,…,K\. Algorithm 1 Central server 1: Input: regularizer λ>0λ>0, trigger parameter γ≥1γ≥ 1, bonus scale β>0β>0, hard episode budget T. 2: Init: for each h∈[H]h∈[H], set Λhser←λId _h^ser←λ I_d and wh←0w_h← 0; set the common episode counter t←0t← 0. 3: Broadcast parameters wh,Λhser,γ,β,T\w_h, _h^ser,γ,β,T\ to all agents. 4: while t<Tt<T do 5: Wait until receiving a synchronization signal and set t to the received current episode counter. 6: Broadcast the synchronization signal to all agents. 7: for h=H,H−1,…,1h=H,H-1,…,1 do 8: Receive (Λhm,loc,bhm)m=1M\( _h^m,loc,b_h^m)\_m=1^M from all agents. 9: Λhser←Λhser+∑m=1MΛhm,loc _h^ser← _h^ser+ _m=1^M _h^m,loc. 10: bh←∑m=1Mbhmb_h← _m=1^Mb_h^m. 11: Update wh←(Λhser)−1bhw_h←( _h^ser)^-1b_h. 12: Broadcast (wh,Λhser)(w_h, _h^ser) to all agents. 13: end for 14: end while Global Coordination. At the beginning of round k, each agent holds the current global model (wh,Λhser)h=1H\(w_h, _h^ser)\_h=1^H. In the special case k=1k=1, this model is initialized and broadcast by the central server before data collection begins. For k≥2k≥ 2, it is the model updated and broadcast by the central server at the end of round k−1k-1. Here, wh∈ℝdw_h ^d is the regression parameter and Λhser∈ℝd×d _h^ser ^d× d is the server-side covariance matrix at step h. Algorithm 2 Agent m 1: Init: Set hm←∅D_h^m← for all h∈[H]h∈[H] and t=0t=0. 2: Receive parameters wh,Λhser,γ,β,T\w_h, _h^ser,γ,β,T\ from the central server and then initialize QhQ_h and VhV_h by (2). 3: while t<Tt<T do 4: Set the round length counter Δt←0 t← 0. 5: for h=1,2,…,Hh=1,2,…,H do 6: Λhm,loc←0 _h^m,loc← 0. 7: end for 8: while no synchronization signal has been received and t<Tt<T do 9: t←t+1t← t+1 and Δt←Δt+1 t← t+1. 10: Observe the initial state x1m,tx_1^m,t. 11: for h=1,2,…,Hh=1,2,…,H do 12: Evaluate the latest optimistic model and pick ahm,t←argmaxaQh(xhm,t,a)a_h^m,t← _aQ_h(x_h^m,t,a). 13: Execute ahm,ta_h^m,t, observe reward rhm,tr_h^m,t and next state xh+1m,tx_h+1^m,t. 14: Append (xhm,t,ahm,t,rhm,t,xh+1m,t)(x_h^m,t,a_h^m,t,r_h^m,t,x_h+1^m,t) to hmD_h^m. 15: Λhm,loc←Λhm,loc+ϕ(xhm,t,ahm,t)ϕ(xhm,t,ahm,t)⊤ _h^m,loc← _h^m,loc+φ(x_h^m,t,a_h^m,t)φ(x_h^m,t,a_h^m,t) . 16: end for 17: if t<Tt<T and ∃h∈[H]∃ h∈[H] such that det(Λhser+Λhm,loc)det(Λhser)≥γΔt ( _h^ser+ _h^m,loc) ( _h^ser)≥ γ t then 18: Send synchronization signal and current episode counter t to the server. 19: end if 20: end while 21: if t=Tt=T then 22: Send synchronization signal and current episode counter t to the server. 23: end if 24: Synchronization (backward, stepwise): set VH+1(⋅)≡0V_H+1(·)≡ 0. 25: for h=H,H−1,…,1h=H,H-1,…,1 do 26: Compute the full-history target bhmb_h^m as (5). 27: Send (Λhm,loc,bhm)( _h^m,loc,b_h^m) to the server. 28: Receive the updated step-h model (wh,Λhser)(w_h, _h^ser) from the server. 29: Update QhQ_h and VhV_h according to (2). 30: end for 31: end while Local Exploration. Using the known feature mapping ϕ(x,a)φ(x,a) together with the broadcast global model (wh,Λhser)h=1H\(w_h, _h^ser)\_h=1^H, for any (x,h)∈×[H](x,h) ×[H], each agent can reconstruct the optimistic value estimates Qh(x,a)Q_h(x,a), Vh(x)V_h(x) according to Qh(x,a)=Π[0,H](ϕ(x,a)⊤wh+β‖ϕ(x,a)‖(Λhser)−1).Vh(x)=maxa∈Qh(x,a),Q_h(x,a)= _[0,H] (φ(x,a) w_h+β\,\|φ(x,a)\|_( _h^ser)^-1 ). V_h(x)= _a Q_h(x,a), (2) Here, Π[0,H]:=minmaxz,0,H _[0,H]:= \ \z,0\,H\. This projection ensures 0≤Qh(x,a)≤H0≤ Q_h(x,a)≤ H and hence 0≤Vh(x)≤H0≤ V_h(x)≤ H. The policy at (x,h)(x,h) is then defined by πh(x)=argmaxa∈Qh(x,a). _h(x)= _a Q_h(x,a). During round k, all agents execute the policy π and repeatedly collect trajectories over multiple episodes. Each agent maintains and updates a local copy of the common episode counter t, together with a current-round episode counter Δt t, which records the number of episodes collected since the beginning of round k. Under the synchronous protocol, the local copies of t remain identical across agents. We denote the trajectory collected by agent m in episode t as (xhm,t,ahm,t,rhm,t,xh+1m,t)h=1H\(x_h^m,t,a_h^m,t,r_h^m,t,x_h+1^m,t)\_h=1^H. During data collection, each agent m maintains two types of local information for each step h∈[H]h∈[H]: a persistent buffer hmD_h^m and a round-wise local covariance matrix Λhm,loc _h^m,loc. The buffer hmD_h^m stores all historical transition tuples (xhm,t,ahm,t,rhm,t,xh+1m,t)(x_h^m,t,a_h^m,t,r_h^m,t,x_h+1^m,t) observed at step h throughout the learning process. In contrast, during each round k, the matrix Λhm,loc _h^m,loc accumulates only the step-h covariance increments from episodes collected in that round, namely ϕ(xhm,t,ahm,t)ϕ(xhm,t,ahm,t)⊤φ(x_h^m,t,a_h^m,t)φ(x_h^m,t,a_h^m,t) for each such episode t, and is reset to zero at the beginning of the next round. Determinant-Based Event-Triggered Synchronization. In round k, synchronization is triggered if there exists an agent m∈[M]m∈[M] such that one of the following two events occurs: (i) the determinant-based trigger condition is satisfied, namely, for some h∈[H]h∈[H], det(Λhser+Λhm,loc)det(Λhser)≥γΔt; \! ( _h^ser+ _h^m,loc ) \! ( _h^ser )≥ γ t; (3) (i) the total episode counter reaches the overall episode budget, that is, t=Tt=T. In either case, the triggering agent m sends a synchronization signal together with the current episode counter t to the central server, which then broadcasts the signal to all agents and terminates the exploration in round k. Agent-Server Synchronization and Policy Update. At the end of each round, the central server updates the value-function estimates and the policy through communication with the agents. To update the step-h value-function estimate, similar to LSVI-UCB (Jin et al., 2020), the central server solves a ridge regression problem whose targets are labeled by the next-step value function Vh+1V_h+1: wh w_h =argminw∈ℝd∑m=1M∑(x,a,r,x′)∈hm(w⊤ϕ(x,a)−r−Vh+1(x′))2+λ‖w‖22. = _w ^d _m=1^M _(x,a,r,x ) _h^m (w φ(x,a)-r-V_h+1(x ) )^2+λ\|w\|_2^2. (4) The resulting estimator whw_h is then used to update the value-function estimates and the policy at step h. Importantly, the value function Vh+1V_h+1 used in this regression should be the newly updated one, computed using all historical samples, including those collected in the current round. Therefore, the updates must be carried out backward over the horizon. This motivates an interleaved, stepwise backward synchronization procedure. Specifically, at each step, the agents first send the necessary statistics to the central server. The server then immediately updates the corresponding value-function and policy estimates and broadcasts the updated stepwise model back to the agents before proceeding to the previous step. Specifically, to solve the above regression problem, each agent m forms the full-history response vector bhmb_h^m from its local buffer hmD_h^m: bhm=∑(x,a,r,x′)∈hmϕ(x,a)(r+Vh+1(x′)),b_h^m= _(x,a,r,x ) _h^mφ(x,a) (r+V_h+1(x ) ), (5) and sends it, together with its local covariance matrix Λhm,loc _h^m,loc, to the central server. The server aggregates the uploaded statistics (Λhm,loc,bhm)m=1M\( _h^m,loc,b_h^m)\_m=1^M and updates the global covariance matrix Λhser _h^ser and global response vector bhb_h according to Λhser←Λhser+∑m=1MΛhm,loc,bh←∑m=1Mbhm, _h^ser← _h^ser+ _m=1^M _h^m,loc, b_h← _m=1^Mb_h^m, (6) and then updates the regression coefficient whw_h by solving the ridge regression problem in (4), which admits the closed-form solution: wh=(Λhser)−1bh.w_h=( _h^ser)^-1b_h. (7) The central server broadcasts the updated step-h model (wh,Λhser)(w_h, _h^ser) to all agents before proceeding to step h−1h-1. Using this newly updated step-h model, all agents can construct the same value function VhV_h with (2), which is then used to form the response vectors bh−1mb_h-1^m by (5) for the model update at step h−1h-1. In this way, synchronization and model updating are carried out recursively from step H down to step 11. This backward, stepwise order ensures that all agents label their historical step-h samples using the same freshly updated value function Vh+1V_h+1 as in LSVI-UCB. 5 Theoretical Guarantees 5.1 Homogeneous Setting We first consider the homogeneous setting, where all agents interact with identical copies of the same linear MDP. In this setting, we present the regret and communication guarantees of Fed-LSVI. Theorem 1 (Regret in the Homogeneous Setting). For Algorithms 1 and 2 with trigger parameter γ≥1γ≥ 1 and regularization parameter λ=1λ=1, there exists a positive constant cβ>0c_β>0 such that, for any confidence level p∈(0,1)p∈(0,1), if we choose β=cβHdlog(1+dMHT/p)β=c_βHd (1+dMHT/p), then with probability at least 1−2p1-2p, Regret(T)≤~(Md3H4T+MH2d2γ).Regret(T)\;≤\; O\! ( Md^3H^4T+MH^2d^2 γ ). The complete expression is provided in (12) of Appendix C. To the best of our knowledge, this is the first regret guarantee for online federated reinforcement learning under linear function approximation. The proof of Theorem 1 is provided in Appendix C. Compared with best-known multi-agent results under linear function approximation (Min et al., 2023; Hsu et al., 2024), our guarantee matches their ~(Md3H4T) O( Md^3H^4T) regret scaling while being tailored to the stricter federated regime, where raw trajectories are not shared and only stage-wise sufficient statistics are communicated. When T≥MdT≥ Md and choose γ=T/Mdγ=T/Md, Theorem 1 implies Regret(T)≤~(Md3H4T).Regret(T)≤ O( Md^3H^4T). Therefore, the average regret per agent is of order ~(d3H4T/M) O( d^3H^4T/M), exhibiting a M M-type multi-agent speedup, consistent with worst-case results in federated tabular RL (Zheng et al., 2024; Zheng et al., 2025a; Labbi et al., 2025; Zhang et al., 2025b) and in multi-agent RL with linear function approximation (Dubey and Pentland, 2021; Min et al., 2023; Hsu et al., 2024). 5.2 Misspecified Setting We next consider a heterogeneous extension under the misspecified setting, where agents interact with agent-specific MDPs, each of which is ξ-approximate to a common reference linear MDP. We show that the proposed algorithm is robust to such mild agent-wise heterogeneity. Definition 2 (Misspecified Setting). For any 0<ξ≤10<ξ≤ 1, and for any agent m∈[M]m∈[M], the corresponding MDP (,,H,ℙm,rm)(X,A,H,P_m,r_m) is a ξ-approximate linear MDP with a feature map ϕ:×→ℝdφ:X×A ^d. Specifically, for each step h∈[H]h∈[H], there exist d unknown measures μh=(μh(1),…,μh(d)) _h= ( _h^(1),…, _h^(d) ) over X and an unknown vector θh∈ℝd _h ^d such that, for all (x,a)∈×(x,a) ×A, ∥ℙm,h(⋅∣x,a)−⟨ϕ(x,a),μh(⋅)⟩∥TV≤ξ,|rm,h(x,a)−⟨ϕ(x,a),θh⟩|≤ξ. \|P_m,h(· x,a)- φ(x,a), _h(·) \|_TV≤ξ, |r_m,h(x,a)- φ(x,a), _h |≤ξ. Here, we assume ‖ϕ(x,a)‖≤1\|φ(x,a)\|≤ 1 for all (x,a)∈×(x,a) ×A, and max‖μh()‖,‖θh‖≤d \\| _h(X)\|,\| _h\| \≤ d. Note that the misspecified setting in Definition 2 coincides with the setting considered in Hsu et al. (2024), which generalizes the single-agent misspecified setting in Jin et al. (2020). Moreover, it also covers the small heterogeneity setting studied in Dubey and Pentland (2021). We now present the regret guarantee under the misspecified setting described in Definition 2. Theorem 2 (Regret in the Misspecified Setting). Under Definition 2, for Algorithms 1 and 2 with trigger parameter γ≥1γ≥ 1 and regularization parameter λ=1λ=1, there exists a positive constant cβ′>0c_β >0 such that, for any confidence level p¯∈(0,1) p∈(0,1), if we choose β=cβ′Hdlog(1+2dMHT/p¯)+2HξdMTβ=c_β Hd (1+2dMHT/ p)+2Hξ dMT, then with probability at least 1−2p¯1-2 p, Regret(T)≤~(Md3H4T+Md2H2γ+ξMdH2T+ξM3d3H4γT).Regret(T)\;≤\; O\! ( Md^3H^4T+Md^2H^2 γ+ξ MdH^2T+ξ M^3d^3H^4γ T ). The complete expression is provided in (29) of Appendix D. The proof is deferred to Appendix D. This result establishes a regret guarantee for the misspecified setting that matches the best-known multi-agent RL result in Hsu et al. (2024), and demonstrates that the proposed algorithm is robust to bounded agent-wise heterogeneity. In particular, when ξ=~(d/(MT))ξ= O( d/(MT)), the regret bound matches that of the homogeneous setting in Theorem 1. 5.3 Communication Cost We next present a unified result of the communication cost of Fed-LSVI in both the homogeneous and misspecified settings. Theorem 3. For Algorithms 1 and 2, with λ=1λ=1 and a total of T episodes per agent, the total number of communication rounds K satisfies K≤ 1+2Tγ+dHlog2log(1+MTd).K\;≤\;1+ 2Tγ+ dH 2 \! (1+ MTd ). The proof is deferred to Appendix E. If we choose the trigger parameter as γ=maxT/(Md),1γ= \T/(Md),1\, then Theorem 3 yields K≤ 1+2Md+dHlog2log(1+MTd).K\;≤\;1+2Md+ dH 2 \! (1+ MTd ). Compared with the communication-round bounds of ~(dHM) O(dHM) in Dubey and Pentland (2021) and Hsu et al. (2024), and ~(dHM2) O(dHM^2) in Min et al. (2023) for the asynchronous setting, our result improves the dependence on the number of agents M in the leading logarithmic term. Moreover, in each round, our algorithm communicates only (MHd2)O(MHd^2) scalars between the agents and the central server. Consequently, the total communication cost of Fed-LSVI is (M2d3H+Md3H2log(1+MTd)).O\! (M^2d^3H+Md^3H^2 \! (1+ MTd ) ). In contrast, existing multi-agent online RL methods (Dubey and Pentland, 2021; Min et al., 2023; Hsu et al., 2024) typically require sharing raw trajectories from local agents, leading to a communication cost of (MHT)O(MHT), which scales linearly with T. Therefore, Fed-LSVI reduces the communication cost from linear to logarithmic in T, yielding a significant improvement. When M=1M=1, Theorems 1 to 3 together imply that our method reduces to a low-switching-cost variant of LSVI-UCB (Jin et al., 2020), achieving the same ~(d3H4T) O( d^3H^4T) regret while incurring only a logarithmic policy switching cost. 6 Conclusion In this paper, we introduced Fed-LSVI, the first provably efficient algorithm for federated online reinforcement learning under linear MDPs. By seamlessly integrating a determinant-based event trigger synchronization rule with a stepwise backward update mechanism, Fed-LSVI achieves both statistical and communication efficiency without sharing raw local trajectories. Theoretically, Fed-LSVI attains T T-type regret guarantees with a provable multi-agent speedup, while incurring only a logarithmic communication cost. We further extend our analysis to the misspecified setting, showing that Fed-LSVI remains robust to mild agent-wise heterogeneity.Our results establish a principled and communication-efficient framework for optimistic exploration in federated reinforcement learning. References Abbasi-Yadkori et al. (2011) Y. Abbasi-Yadkori, D. Pál, and C. Szepesvári Improved algorithms for linear stochastic bandits. Advances in Neural Information Processing Systems 24. Cited by: Lemma B.1, Lemma B.4, Lemma B.6. Agarwal et al. (2020) A. Agarwal, S. Kakade, and L. F. Yang Model-based reinforcement learning with a generative model is minimax optimal. In Conference on Learning Theory, p. 67–83. Cited by: §2. Agrawal and Jia (2017) S. Agrawal and R. Jia Optimistic posterior sampling for reinforcement learning: worst-case regret bounds. Advances in Neural Information Processing Systems 30. Cited by: §2. Auer et al. (2008) P. Auer, T. Jaksch, and R. Ortner Near-optimal regret bounds for reinforcement learning. Advances in Neural Information Processing Systems 21. Cited by: §2. Ayoub et al. (2020) A. Ayoub, Z. Jia, C. Szepesvari, M. Wang, and L. Yang Model-based reinforcement learning with value-targeted regression. In International Conference on Machine Learning, p. 463–474. Cited by: §1, §2. Azar et al. (2017) M. G. Azar, I. Osband, and R. Munos Minimax regret bounds for reinforcement learning. In Proceedings of the 34th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 70, p. 263–272. External Links: Link Cited by: §2, §3. Bai et al. (2019) Y. Bai, T. Xie, N. Jiang, and Y. Wang Provably efficient Q-learning with low switching cost. In Advances in Neural Information Processing Systems, Vol. 32. External Links: Link Cited by: §2. Dal Fabbro et al. (2023) N. Dal Fabbro, A. Mitra, and G. J. Pappas Federated td learning over finite-rate erasure channels: linear speedup under markovian sampling. IEEE Control Systems Letters 7, p. 2461–2466. External Links: Link Cited by: §2. Dann et al. (2019) C. Dann, L. Li, W. Wei, and E. Brunskill Policy certificates: towards accountable reinforcement learning. In International Conference on Machine Learning, p. 1507–1516. Cited by: §2. Dubey and Pentland (2021) A. Dubey and A. Pentland Provably efficient cooperative multi-agent reinforcement learning with function approximation. arXiv preprint arXiv:2103.04972. External Links: Link Cited by: §1, §1, §2, §5.1, §5.2, §5.3, §5.3. Ganesh et al. (2024) S. Ganesh, J. Chen, G. Thoppe, and V. Aggarwal Global convergence guarantees for federated policy gradient methods with adversaries. Transactions on Machine Learning Research. External Links: Link Cited by: §2. He et al. (2023) J. He, H. Zhao, D. Zhou, and Q. Gu Nearly minimax optimal reinforcement learning for linear markov decision processes. In Proceedings of the 40th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 202, p. 12790–12822. External Links: Link Cited by: §1, §2. Hsu et al. (2024) H. Hsu, W. Wang, M. Pajic, and P. Xu Randomized exploration in cooperative multi-agent reinforcement learning. In Advances in Neural Information Processing Systems, External Links: Link Cited by: §1, §1, §1, §2, §5.1, §5.1, §5.2, §5.2, §5.3, §5.3. Hu et al. (2022) P. Hu, Y. Chen, and L. Huang Nearly minimax optimal reinforcement learning with linear function approximation. In Proceedings of the 39th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 162, p. 8971–9019. External Links: Link Cited by: §2. Jia et al. (2020) Z. Jia, L. Yang, C. Szepesvari, and M. Wang Model-based reinforcement learning with value-targeted regression. In Learning for Dynamics and Control, p. 666–686. Cited by: §2. Jin et al. (2018) C. Jin, Z. Allen-Zhu, S. Bubeck, and M. I. Jordan Is Q-learning provably efficient?. In Advances in Neural Information Processing Systems, Vol. 31. External Links: Link Cited by: §2. Jin et al. (2020) C. Jin, Z. Yang, Z. Wang, and M. I. Jordan Provably efficient reinforcement learning with linear function approximation. In Proceedings of the Thirty Third Conference on Learning Theory, Proceedings of Machine Learning Research, Vol. 125, p. 2137–2143. External Links: Link Cited by: Lemma B.2, Lemma B.7, §1, §1, §2, §3, §4.1, §5.2, §5.3. Kairouz and McMahan (2021) P. Kairouz and H. B. McMahan Advances and open problems in federated learning. Foundations and trends in machine learning 14 (1-2), p. 1–210. Cited by: §1. Khodadadian et al. (2022) S. Khodadadian, P. Sharma, G. Joshi, and S. T. Maguluri Federated reinforcement learning: linear speedup under markovian sampling. In Proceedings of the 39th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 162, p. 10997–11057. External Links: Link Cited by: §2. Komorowski et al. (2018) M. Komorowski, L. A. Celi, O. Badawi, A. C. Gordon, and A. A. Faisal The artificial intelligence clinician learns optimal treatment strategies for sepsis in intensive care. Nature medicine 24 (11), p. 1716–1720. Cited by: §1. Labbi et al. (2025) S. Labbi, D. Tiapkin, L. Mancini, P. Mangold, and E. Moulines Federated ucbvi: communication-efficient federated regret minimization with heterogeneous agents. In Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, Proceedings of Machine Learning Research, Vol. 258, p. 1315–1323. External Links: Link Cited by: §2, §5.1. Lan et al. (2025) G. Lan, D. Han, A. Hashemi, V. Aggarwal, and C. G. Brinton Asynchronous federated reinforcement learning with policy gradient updates: algorithm design and convergence analysis. In The Thirteenth International Conference on Learning Representations, External Links: Link Cited by: §2. Li et al. (2023) G. Li, L. Shi, Y. Chen, and Y. Chi Breaking the sample complexity barrier to regret-optimal model-free reinforcement learning. Information and Inference: A Journal of the IMA 12 (2), p. 969–1043. Cited by: §2. McMahan et al. (2017) B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. Agüera y Arcas Communication-efficient learning of deep networks from decentralized data. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, Proceedings of Machine Learning Research, Vol. 54, p. 1273–1282. External Links: Link Cited by: §1. Ménard et al. (2021) P. Ménard, O. D. Domingues, X. Shang, and M. Valko UCB momentum q-learning: correcting the bias without forgetting. In Proceedings of the 38th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 139, p. 7609–7618. External Links: Link Cited by: §2. Min et al. (2023) Y. Min, J. He, T. Wang, and Q. Gu Cooperative multi-agent reinforcement learning: asynchronous communication and linear function approximation. In Proceedings of the 40th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 202, p. 24785–24811. External Links: Link Cited by: §1, §1, §1, §2, §5.1, §5.1, §5.3, §5.3. Modi et al. (2020) A. Modi, N. Jiang, A. Tewari, and S. Singh Sample complexity of reinforcement learning using linearly combined model ensembles. In International Conference on Artificial Intelligence and Statistics, p. 2010–2020. Cited by: §2. Murphy (2003) S. A. Murphy Optimal dynamic treatment regimes. Journal of the Royal Statistical Society Series B: Statistical Methodology 65 (2), p. 331–355. Cited by: §1. Qiao et al. (2022) D. Qiao, M. Yin, M. Min, and Y. Wang Sample-efficient reinforcement learning with loglog(T) switching cost. In Proceedings of the 39th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 162, p. 18031–18061. External Links: Link Cited by: §2. Salgia and Chi (2024) S. Salgia and Y. Chi The sample-communication complexity trade-off in federated q-learning. In Advances in Neural Information Processing Systems, External Links: Link Cited by: §2. Sutton and Barto (2018) R. S. Sutton and A. G. Barto Reinforcement learning: an introduction. 2 edition, MIT Press. Cited by: §1. Velegkas et al. (2022) G. Velegkas, Z. Yang, and A. Karbasi Reinforcement learning with logarithmic regret and policy switches. In Advances in Neural Information Processing Systems, Vol. 35. External Links: Link Cited by: §2. Wagenmaker et al. (2022) A. J. Wagenmaker, Y. Chen, M. Simchowitz, S. Du, and K. Jamieson First-order regret in reinforcement learning with linear function approximation: a robust estimation approach. In International Conference on Machine Learning, p. 22384–22429. Cited by: §2. Wang et al. (2024) H. Wang, A. Mitra, H. Hassani, G. J. Pappas, and J. Anderson Federated td learning with linear function approximation under environmental heterogeneity. Transactions on Machine Learning Research. External Links: Link Cited by: §2. Wang et al. (2021) T. Wang, D. Zhou, and Q. Gu Provably efficient reinforcement learning with linear function approximation under adaptivity constraints. In Advances in Neural Information Processing Systems, Vol. 34, p. 13524–13536. External Links: Link Cited by: §2, §3. Wei et al. (2021) C. Wei, M. J. Jahromi, H. Luo, and R. Jain Learning infinite-horizon average-reward mdps with linear function approximation. In International Conference on Artificial Intelligence and Statistics, p. 3007–3015. Cited by: §2. Woo et al. (2023) J. Woo, G. Joshi, and Y. Chi The blessing of heterogeneity in federated q-learning: linear speedup and beyond. In Proceedings of the 40th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 202, p. 37157–37216. External Links: Link Cited by: §2. Yang et al. (2021) K. Yang, L. Yang, and S. Du Q-learning with logarithmic regret. In International Conference on Artificial Intelligence and Statistics, p. 1576–1584. Cited by: §2. Yang and Wang (2019) L. F. Yang and M. Wang Sample-optimal parametric q-learning using linearly additive features. In Proceedings of the 36th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 97, p. 6995–7004. External Links: Link Cited by: §2. Yang and Wang (2020) L. F. Yang and M. Wang Reinforcement learning in feature space: matrix bandit, kernels, and regret bound. In Proceedings of the 37th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 119, p. 10746–10756. External Links: Link Cited by: §2, §3. Yang et al. (2024) T. Yang, S. Cen, Y. Wei, Y. Chen, and Y. Chi Federated natural policy gradient and actor critic methods for multi-task reinforcement learning. In Advances in Neural Information Processing Systems, External Links: Link Cited by: §2. Zanette and Brunskill (2019) A. Zanette and E. Brunskill Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds. In International Conference on Machine Learning, p. 7304–7312. Cited by: §2. Zhang et al. (2024a) C. Zhang, H. Wang, A. Mitra, and J. Anderson Finite-time analysis of on-policy heterogeneous federated reinforcement learning. In The Twelfth International Conference on Learning Representations, External Links: Link Cited by: §2. Zhang et al. (2025a) H. Zhang, Z. Zheng, and L. Xue Gap-dependent bounds for federated $q$-learning. In Forty-second International Conference on Machine Learning, External Links: Link Cited by: §2. Zhang et al. (2025b) H. Zhang, Z. Zheng, and L. Xue Regret-optimal q-learning with low cost for single-agent and federated reinforcement learning. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, External Links: Link Cited by: §2, §2, §5.1. Zhang et al. (2026a) H. Zhang, Z. Zheng, and L. Xue Gap-dependent bounds for nearly minimax optimal reinforcement learning with linear function approximation. arXiv preprint arXiv:2602.20297. Cited by: §2. Zhang et al. (2026b) H. Zhang, Z. Zheng, and L. Xue Q-learning with fine-grained gap-dependent regret. In International Conference on Learning Representations, Vol. 2026, p. 48118–48162. Cited by: §2. Zhang et al. (2023) J. Zhang, W. Zhang, and Q. Gu Optimal horizon-free reward-free exploration for linear mixture mdps. In International Conference on Machine Learning, p. 41902–41930. Cited by: §2. Zhang et al. (2024b) Z. Zhang, Y. Chen, J. D. Lee, and S. S. Du Settling the sample complexity of online reinforcement learning. In Conference on Learning Theory, p. 5213–5219. Cited by: §2. Zhang et al. (2021) Z. Zhang, X. Ji, and S. Du Is reinforcement learning more difficult than bandits? a near-optimal algorithm escaping the curse of horizon. In Conference on Learning Theory, p. 4528–4531. Cited by: §2. Zhang et al. (2024c) Z. Zhang, J. D. Lee, Y. Chen, and S. S. Du Horizon-free regret for linear markov decision processes. In The Twelfth International Conference on Learning Representations, Cited by: §2. Zhang et al. (2020) Z. Zhang, Y. Zhou, and X. Ji Almost optimal model-free reinforcement learning via reference-advantage decomposition. Advances in Neural Information Processing Systems 33, p. 15198–15207. Cited by: §2. Zheng et al. (2024) Z. Zheng, F. Gao, L. Xue, and J. Yang Federated q-learning: linear regret speedup with low communication cost. In The Twelfth International Conference on Learning Representations, External Links: Link Cited by: §1, §2, §5.1. Zheng et al. (2025a) Z. Zheng, H. Zhang, and L. Xue Federated q-learning with reference-advantage decomposition: almost optimal regret and logarithmic communication cost. In The Thirteenth International Conference on Learning Representations, Cited by: §1, §2, §5.1. Zheng et al. (2025b) Z. Zheng, H. Zhang, and L. Xue Gap-dependent bounds for q-learning using reference-advantage decomposition. In International Conference on Learning Representations, Vol. 2025, p. 86127–86179. Cited by: §2. Zhou et al. (2021a) D. Zhou, Q. Gu, and C. Szepesvári Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Proceedings of the Thirty Fourth Conference on Learning Theory, Proceedings of Machine Learning Research, Vol. 134, p. 4532–4576. External Links: Link Cited by: §1, §2. Zhou and Gu (2022) D. Zhou and Q. Gu Computationally efficient horizon-free reinforcement learning for linear mixture mdps. Advances in neural information processing systems 35, p. 36337–36349. Cited by: §1, §2. Zhou et al. (2021b) D. Zhou, J. He, and Q. Gu Provably efficient reinforcement learning for discounted mdps with feature mapping. In International Conference on Machine Learning, p. 12793–12802. Cited by: §2. Zhou et al. (2023) R. Zhou, Z. Zhang, and S. S. Du Sharp variance-dependent bounds in reinforcement learning: best of both worlds in stochastic and deterministic environments. In International Conference on Machine Learning, p. 42878–42914. Cited by: §2. Appendix A Auxiliary Notation We collect the notation used throughout the proofs. The index m∈[M]m∈[M] denotes an agent, k∈[K]k∈[K] denotes a communication round, and t∈[T]t∈[T] denotes the common episode index shared by all agents. The function k(t)k(t) returns the index of the round containing episode t. For a vector u,v∈ℝdu,v ^d and a positive semi-definite matrix A∈ℝd×dA ^d× d, we define ⟨u,v⟩A=u⊤Av u,v _A=u Av and ‖u‖A:=u⊤Au\|u\|_A:= u Au. To define a single filtration over all agents and episodes, we use the linearization ℓ(m,t)≔m+M(t−1),νT(ζ)≔⌈ζM⌉,νM(ζ)≔((ζ−1)modM)+1. (m,t) m+M(t-1), _T(ζ) ζM , _M(ζ) ((ζ-1) M)+1. Then (m,t)↦ℓ(m,t)(m,t) (m,t) and ζ↦(νM(ζ),νT(ζ))ζ ( _M(ζ), _T(ζ)) form a pair of inverse mappings. Accordingly, we define the ordering (m,t)≤(m′,t′)(m,t)≤(m ,t ) to mean ℓ(m,t)≤ℓ(m′,t′) (m,t)≤ (m ,t ). For each step h∈[H]h∈[H], let Λhk _h^k denote the server-side Gram matrix Λhser _h^ser at the beginning of round k, and let Λhm,k,loc _h^m,k,loc denote the information increment collected by agent m during round k. By the design of the algorithm, these quantities satisfy Λhk≔λId+∑m=1M∑t=1τk−1ϕ(xhm,t,ahm,t)ϕ(xhm,t,ahm,t)⊤, _h^k λ I_d+ _m=1^M _t=1 _k-1φ(x_h^m,t,a_h^m,t)φ(x_h^m,t,a_h^m,t) , Λhm,k,loc≔∑t=τkτk+1−1ϕ(xhm,t,ahm,t)ϕ(xhm,t,ahm,t)⊤. _h^m,k,loc _t= _k _k+1-1φ(x_h^m,t,a_h^m,t)φ(x_h^m,t,a_h^m,t) . By the definitions above, for any k∈[K]k∈[K], the quantities Λhk+1 _h^k+1, Λhk _h^k, and Λhm,k,loc _h^m,k,loc further satisfy Λhk+1=Λhk+∑m=1MΛhm,k,loc, _h^k+1= _h^k+ _m=1^M _h^m,k,loc, where ΛhK+1≔λId+∑m=1M∑t=1Tϕ(xhm,t,ahm,t)ϕ(xhm,t,ahm,t)⊤. _h^K+1 λ I_d+ _m=1^M _t=1^Tφ(x_h^m,t,a_h^m,t)φ(x_h^m,t,a_h^m,t) . (8) In addition, we define the following three auxiliary statistics, which will be used in the subsequent analysis: Λ¯hm,t _h^m,t ≔Λhk(t)+∑j=τk(t)tϕ(xhm,j,ahm,j)ϕ(xhm,j,ahm,j)⊤,∀t∈[T] _h^k(t)+ _j= _k(t)^tφ(x_h^m,j,a_h^m,j)φ(x_h^m,j,a_h^m,j) ,\ ∀ t∈[T] Λ~hm,t _h^m,t ≔λId+∑(n,j)≤(m,t)ϕ(xhn,j,ahn,j)ϕ(xhn,j,ahn,j)⊤,∀t∈[T] λ I_d+ _(n,j)≤(m,t)φ(x_h^n,j,a_h^n,j)φ(x_h^n,j,a_h^n,j) ,\ ∀ t∈[T] Λˇht _h^t ≔λId+∑m=1M∑j=1t−1ϕ(xhm,j,ahm,j)ϕ(xhm,j,ahm,j)⊤,∀t∈[T+1]. λ I_d+ _m=1^M _j=1^t-1φ(x_h^m,j,a_h^m,j)φ(x_h^m,j,a_h^m,j) ,\ ∀ t∈[T+1]. The value of whw_h at the beginning of round k, denoted by whkw_h^k, is given by whk=(Λhk)−1∑m=1M∑t=1τk−1ϕ(xhm,t,ahm,t)[rh(xhm,t,ahm,t)+Vh+1k(xh+1m,t)].w_h^k=( _h^k)^-1 _m=1^M _t=1 _k-1φ(x_h^m,t,a_h^m,t) [r_h(x_h^m,t,a_h^m,t)+V_h+1^k(x_h+1^m,t) ]. In the heterogeneous setting, it can be written as whk=(Λhk)−1∑m=1M∑t=1τk−1ϕ(xhm,t,ahm,t)[rm,h(xhm,t,ahm,t)+Vh+1k(xh+1m,t)].w_h^k=( _h^k)^-1 _m=1^M _t=1 _k-1φ(x_h^m,t,a_h^m,t) [r_m,h(x_h^m,t,a_h^m,t)+V_h+1^k(x_h+1^m,t) ]. Appendix B Auxiliary Lemmas Lemma B.1 (Lemma 12 in Abbasi-Yadkori et al. [2011]). Let V∈ℝd×dV ^d× d be a positive definite matrix and x∈ℝdx ^d. Then, min1,‖x‖V−12≤ 2logdet(V+xx⊤)det(V). \1,\;\|x\|_V^-1^2 \\;≤\;2 \! (V+x ) (V). Lemma B.2 (Proposition 2.3 and Lemma B.1 in Jin et al. [2020]). Assume the linear MDP parameters satisfy ‖θh‖2≤d\| _h\|_2≤ d and ‖μh()‖2≤d\| _h(X)\|_2≤ d for all h∈[H]h∈[H]. For any policy π, define whπ≔θh+∫Vh+1π(x′)μh(dx′).w_h^π _h+ _XV_h+1^π(x )\, _h(dx ). Then Qhπ(x,a)=⟨ϕ(x,a),whπ⟩Q_h^π(x,a)= φ(x,a),w_h^π for any (x,a,h)∈×[H](x,a,h) ×A×[H] and ‖whπ‖2≤2Hd\|w_h^π\|_2≤ 2H d for any h∈[H]h∈[H]. Lemma B.3 (Norm control for the step-wise regression vector). For every step h∈[H]h∈[H] and round k∈[K]k∈[K], it holds that ‖whk‖2≤2HdMτkλ.\|w_h^k\|_2≤ 2H dM _kλ. Proof of Lemma B.3. For any vector v∈ℝdv ^d, since whk=(Λhk)−1∑m=1M∑j=1τk−1ϕ(xhm,j,ahm,j)[rh(xhm,j,ahm,j)+Vh+1k(xh+1m,j)],w_h^k=( _h^k)^-1 _m=1^M _j=1 _k-1φ(x_h^m,j,a_h^m,j) [r_h(x_h^m,j,a_h^m,j)+V_h+1^k(x_h+1^m,j) ], we have |⟨v,whk⟩|=|⟨v,∑m=1M∑j=1τk−1ϕ(xhm,j,ahm,j)[rh(xhm,j,ahm,j)+Vh+1k(xh+1m,j)]⟩(Λhk)−1|. | v,w_h^k |= | v, _m=1^M _j=1 _k-1φ(x_h^m,j,a_h^m,j) [r_h(x_h^m,j,a_h^m,j)+V_h+1^k(x_h+1^m,j) ] _( _h^k)^-1 |. Since rewards are bounded in [0,1][0,1] and 0≤Vh+1k≤H0≤ V_h+1^k≤ H, each regression target satisfies |rh(xhm,j,ahm,j)+Vh+1k(xh+1m,j)|≤2H. |r_h(x_h^m,j,a_h^m,j)+V_h+1^k(x_h+1^m,j) |≤ 2H. Applying this bound gives |⟨v,whk⟩| | v,w_h^k | ≤2H∑m=1M∑j=1τk−1|⟨v,ϕ(xhm,j,ahm,j)⟩(Λhk)−1| ≤ 2H _m=1^M _j=1 _k-1 | v,φ(x_h^m,j,a_h^m,j) _( _h^k)^-1 | ≤2H∑m=1M∑j=1τk−1⟨v,v⟩(Λhk)−1⟨ϕ(xhm,j,ahm,j),ϕ(xhm,j,ahm,j)⟩(Λhk)−1 ≤ 2H _m=1^M _j=1 _k-1 v,v _( _h^k)^-1\, φ(x_h^m,j,a_h^m,j),φ(x_h^m,j,a_h^m,j) _( _h^k)^-1 ≤2H∥v∥2λ−1/2Mτk∑m=1M∑j=1τk−1ϕ(xhm,j,ahm,j)⊤(Λhk)−1ϕ(xhm,j,ahm,j). ≤ 2H\,\|v\|_2\,λ^-1/2 M _k _m=1^M _j=1 _k-1φ(x_h^m,j,a_h^m,j) ( _h^k)^-1φ(x_h^m,j,a_h^m,j). (9) The second inequality follows from Cauchy–Schwarz inequality. The last inequality follows from ⟨v,v⟩(Λhk)−1≤‖v‖22/λ v,v _( _h^k)^-1≤\|v\|^2_2/λ since Λhk⪰λId _h^k λ I_d. Since Λhk _h^k is a positive-definite matrix, we further note that, ∑m=1M∑j=1τk−1ϕ(xhm,j,ahm,j)⊤(Λhk)−1ϕ(xhm,j,ahm,j) _m=1^M _j=1 _k-1φ(x_h^m,j,a_h^m,j) ( _h^k)^-1φ(x_h^m,j,a_h^m,j) =tr((Λhk)−1∑m=1M∑j=1τk−1ϕ(xhm,j,ahm,j)ϕ(xhm,j,ahm,j)⊤) =tr (( _h^k)^-1 _m=1^M _j=1 _k-1φ(x_h^m,j,a_h^m,j)φ(x_h^m,j,a_h^m,j) ) =tr((Λhk)−1(Λhk−λId)) =tr (( _h^k)^-1( _h^k-λ I_d) ) =tr(Id−λ(Λhk)−1)≤d. =tr (I_d-λ( _h^k)^-1 )≤ d. (10) Combining (9) and (10) yields |⟨v,whk⟩|≤2H‖v‖2dMτkλ. | v,w_h^k |≤ 2H\,\|v\|_2 dM _kλ. Taking the supremum over all ‖v‖2=1\|v\|_2=1 concludes the proof. ∎ Lemma B.4 (Self-Normalized Concentration Inequality, Theorem 1 in Abbasi-Yadkori et al. [2011]). Let ηtt≥1\ _t\_t≥ 1 be a real-valued martingale difference sequence adapted to a filtration ℱt\F_t\, such that ηt _t is conditionally R-sub-Gaussian, i.e., [exp(ληt)∣ℱt−1]≤exp(λ2R22)for all λ∈ℝ.E\! [ (λ _t) _t-1 ]≤ \! ( λ^2R^22 ) all λ . Let xtt≥1\x_t\_t≥ 1 be an ℝdR^d-valued predictable process (i.e., xtx_t is ℱt−1F_t-1-measurable), and define Vt=λI+∑s=1txsxs⊤,St=∑s=1txsηs,V_t=λ I+ _s=1^tx_sx_s , S_t= _s=1^tx_s _s, for some λ>0λ>0. Then, for any δ∈(0,1)δ∈(0,1), with probability at least 1−δ1-δ, for all t≥0t≥ 0 simultaneously, ‖St‖Vt−12≤ 2R2log(det(Vt)1/2det(λI)1/2δ).\|S_t\|_V_t^-1^2\;≤\;2R^2 ( (V_t)^1/2 (λ I)^1/2\,δ ). Lemma B.5 (Self-normalized concentration for a fixed target function). Fix a step h∈[H]h∈[H] and a function V:→[0,H]V:X→[0,H]. Then, for any confidence level p∈(0,1)p∈(0,1), with probability at least 1−p1-p, simultaneously for all t∈1,…,T+1t∈\1,…,T+1\, ‖∑m=1M∑j=1t−1ϕ(xhm,j,ahm,j)[V(xh+1m,j)−ℙhV(xhm,j,ahm,j)]‖(Λˇht)−1 \| _m=1^M _j=1^t-1φ(x_h^m,j,a_h^m,j) [V(x_h+1^m,j)-P_hV(x_h^m,j,a_h^m,j) ] \|_( _h^t)^-1 ≤2Hd2log(1+MTdλ)+2log(1p). ≤ 2H d2 (1+ MTdλ )+2 ( 1p ). Proof of Lemma B.5. Recall that m,t,h=σ((xℓn,j,aℓn,j)(n,j)<(m,t),ℓ∈[H]∪(xℓm,t,aℓm,t)ℓ≤h),G_m,t,h=σ\! (\(x_ ^n,j,a_ ^n,j)\_(n,j)<(m,t),\, ∈[H]∪\(x_ ^m,t,a_ ^m,t)\_ ≤ h ), ηm,j≔V(xh+1m,j)−ℙhV(xhm,j,ahm,j) _m,j V(x_h+1^m,j)-P_hV(x_h^m,j,a_h^m,j) is a bounded martingale difference with respect to m,t,hG_m,t,h. Applying Lemma B.4 gives that with probability at least 1−p1-p, simultaneously for all t, ‖∑m=1M∑j=1t−1ϕ(xhm,j,ahm,j)ηm,j‖(Λˇht)−12≤4H2log(det(ΛˇhT+1)1/2p2det(Λˇh1)1/2). \| _m=1^M _j=1^t-1φ(x_h^m,j,a_h^m,j) _m,j \|_( _h^t)^-1^2≤ 4H^2 ( ( _h^T+1)^1/2p^2 ( _h^1)^1/2 ). Finally, we upper bound the log-determinant term by using det(λI+∑i=1MTϕiϕi⊤)≤λd(1+MT/(λd))d (λ I+ _i=1^MT _i _i )≤λ^d (1+MT/(λ d) )^d. This yields log(det(ΛˇhT+1)p2det(Λˇh1))≤d2log(1+MTdλ)+2log(1p), ( ( _h^T+1)p^2 ( _h^1) )≤ d2 (1+ MTdλ )+2 ( 1p ), which concludes the proof. ∎ Lemma B.6 (Elliptical potential lemma, Lemma 11 in Abbasi-Yadkori et al. [2011]). Let xtt=1T⊂ℝd\x_t\_t=1^T ^d with ‖xt‖2≤1\|x_t\|_2≤ 1, and define Vt=λI+∑s=1txsxs⊤,V_t=λ I+ _s=1^tx_sx_s , for some λ>0λ>0. Then, ∑t=1Tmin1,‖xt‖Vt−1−12≤ 2logdet(VT)det(λI)≤ 2dlog(1+Tdλ). _t=1^T \1,\|x_t\|_V_t-1^-1^2 \\;≤\;2 (V_T) (λ I)\;≤\;2d (1+ Tdλ ). Lemma B.7 (Covering-number bound for optimistic value functions, Lemma D.6 in Jin et al. [2020]). Let V denote a class of functions of the form V(⋅)=minmaxa∈[w⊤ϕ(⋅,a)+βϕ(⋅,a)⊤Λ−1ϕ(⋅,a)],H,V(·)= \ _a [w φ(·,a)+β φ(·,a) ^-1φ(·,a) ],H \, where the parameters satisfy ‖w‖2≤L\|w\|_2≤ L, β∈[0,B]β∈[0,B], and λmin(Λ)≥λ _ ( )≥λ. Assume ‖ϕ(x,a)‖2≤1\|φ(x,a)\|_2≤ 1 for all (x,a)(x,a). Let ϵN_ε be the ϵε-covering number of V under dist(V,V′)=supx|V(x)−V′(x)|dist(V,V )= _x|V(x)-V (x)|. Then logϵ≤dlog(1+4Lϵ)+d2log(1+8dB2λϵ2). _ε≤ d (1+ 4Lε )+d^2 (1+ 8 d\,B^2λε^2 ). Lemma B.8 (Covering-number bound for optimistic value functions). Let V denote a class of functions of the form V(⋅)=Π[0,H](maxa∈[w⊤ϕ(⋅,a)+βϕ(⋅,a)⊤Λ−1ϕ(⋅,a)]),V(·)= _[0,H] ( _a [w φ(·,a)+β φ(·,a) ^-1φ(·,a) ] ), where the parameters satisfy ‖w‖2≤L\|w\|_2≤ L, β∈[0,B]β∈[0,B], and λmin(Λ)≥λ _ ( )≥λ. Assume ‖ϕ(x,a)‖2≤1\|φ(x,a)\|_2≤ 1 for all (x,a)(x,a). Let ϵN_ε be the ϵε-covering number of V under dist(V,V′)=supx|V(x)−V′(x)|dist(V,V )= _x|V(x)-V (x)|. Then logϵ≤dlog(1+4Lϵ)+d2log(1+8dB2λϵ2). _ε≤ d (1+ 4Lε )+d^2 (1+ 8 d\,B^2λε^2 ). Proof. Let ¯ V denote the value-function class before the additional lower clipping, namely V¯(⋅)=minmaxa∈(w⊤ϕ(⋅,a)+βϕ(⋅,a)⊤Λ−1ϕ(⋅,a)),H. V(·)= \ _a (w φ(·,a)+β φ(·,a) ^-1φ(·,a) ),H \. After adding the projection onto [0,H][0,H], the new value-function class can be written as =V(⋅)=[V¯(⋅)]+:V¯∈¯,V= \V(·)=[ V(·)]_+: V∈ V \, where [z]+=maxz,0[z]_+= \z,0\. Since the map z↦[z]+z [z]_+ is 11-Lipschitz, for any V¯,V¯′∈¯ V, V ∈ V, ‖[V¯]+−[V¯′]+‖∞≤‖V¯−V¯′‖∞.\|[ V]_+-[ V ]_+\|_∞≤\| V- V \|_∞. Therefore, if V¯ii=1Nϵ\ V_i\_i=1^N_ε is an ϵε-net of ¯ V under the sup norm, then [V¯i]+i=1Nϵ\[ V_i]_+\_i=1^N_ε is an ϵε-net of V. Hence Nϵ()≤Nϵ(¯).N_ε(V)≤ N_ε( V). Applying Lemma B.7 gives the same bound for the projected class V. ∎ Lemma B.9 (Uniform concentration for the data-dependent target Vh+1kV_h+1^k). Fix any confidence level p∈(0,1)p∈(0,1) and λ=1λ=1, and set β=cβHdlog(1+dMHT/p)β=c_βHd (1+dMHT/p), where cβc_β is a sufficiently large positive constant. Define event C that simultaneously for all rounds k∈[K]k∈[K] and steps h∈[H]h∈[H], ‖∑m=1M∑j=1τk−1ϕ(xhm,j,ahm,j)[Vh+1k(xh+1m,j)−ℙhVh+1k(xhm,j,ahm,j)]‖(Λˇhτk)−12≤CH2d2χ. \| _m=1^M _j=1 _k-1φ(x_h^m,j,a_h^m,j) [V_h+1^k(x_h+1^m,j)-P_hV_h+1^k(x_h^m,j,a_h^m,j) ] \|_( _h _k)^-1^2≤ CH^2d^2χ. where χ=log(1+(cβ+1)dMHT/p)χ= (1+(c_β+1)dMHT/p). Then, ℙ()≥1−pP(C)≥ 1-p. Proof of Lemma B.9. The challenge is that Vh+1kV_h+1^k is data dependent. We therefore discretize the relevant function class and then transfer the bound from the net to the whole class. By construction, every Vh+1kV_h+1^k belongs to the class V in Lemma B.8. Moreover, Lemma B.3 implies that the regression parameter can be taken in a ball of radius L=2HdMT/λL=2H dMT/λ, because τk≤T _k≤ T for all k. Let V(1),…,V(ϵ)\V^(1),…,V^(N_ε)\ be an ϵε-net of V under the sup norm. Applying Lemma B.5 to each V(i)V^(i) and taking a union bound over i and h shows that, with probability at least 1−p1-p, for every h∈[H]h∈[H], every k∈[K]k∈[K], and every net point V(i)V^(i), ‖Sh,k(i)‖(Λˇhτk)−12≤2H2dlog(1+MTdλ)+8H2log(Hϵp).\|S_h,k^(i)\|_( _h _k)^-1^2≤ 2H^2d (1+ MTdλ )+8H^2 ( HN_εp ). Here, Sh,k(i):=∑m=1M∑j=1τk−1ϕ(xhm,j,ahm,j)[V(i)(xh+1m,j)−ℙhV(i)(xhm,j,ahm,j)].S_h,k^(i):= _m=1^M _j=1 _k-1φ(x_h^m,j,a_h^m,j) [V^(i)(x_h+1^m,j)-P_hV^(i)(x_h^m,j,a_h^m,j) ]. Fix any V∈V and choose V(i)V^(i) in the net such that ‖V−V(i)‖∞≤ϵ\|V-V^(i)\|_∞≤ε. For every sample, |(V−V(i))(xh+1m,j)−ℙh(V−V(i))(xhm,j,ahm,j)|≤2ϵ. | (V-V^(i) )(x_h+1^m,j)-P_h (V-V^(i) )(x_h^m,j,a_h^m,j) |≤ 2ε. Therefore, ‖∑m=1M∑j=1τk−1ϕ(xhm,j,ahm,j)[(V−V(i))(xh+1m,j)−ℙh(V−V(i))(xhm,j,ahm,j)]‖(Λˇhτk)−12≤4M2T2ϵ2λ, \| _m=1^M _j=1 _k-1φ(x_h^m,j,a_h^m,j) [(V-V^(i))(x_h+1^m,j)-P_h(V-V^(i))(x_h^m,j,a_h^m,j) ] \|_( _h _k)^-1^2≤ 4M^2T^2ε^2λ, where we used Λˇhk⪰λId _h^k λ I_d and ‖ϕ(xhm,j,ahm,j)‖2≤1\|φ(x_h^m,j,a_h^m,j)\|_2≤ 1. Combining the net bound with this approximation error, we have ‖∑m=1M∑j=1τk−1ϕ(xhm,j,ahm,j)[Vh+1k(xh+1m,j)−ℙhVh+1k(xhm,j,ahm,j)]‖(Λˇhτk)−12≤Γp. \| _m=1^M _j=1 _k-1φ(x_h^m,j,a_h^m,j) [V_h+1^k(x_h+1^m,j)-P_hV_h+1^k(x_h^m,j,a_h^m,j) ] \|_( _h _k)^-1^2≤ _p. where Γp≔8H2(d2log(1+MTdλ)+2log(Hp)+2logϵ)+8M2T2ϵ2λ, _p 8H^2 ( d2 (1+ MTdλ )+2 ( Hp )+2 _ε )+ 8M^2T^2ε^2λ, and ϵN_ε is the covering number of the value-function class from Lemma B.8. Let λ=1λ=1, ϵ=Hd/MTε=Hd/MT, β=cβHdlog(1+dMHT/p)β=c_βHd (1+dMHT/p). The Γp _p becomes Γp=8 _p=8 H2(d2log(1+MTd)+2log(Hp)+2dlog(1+8(MT)3/2d)CLOSE H^2 ( d2 (1+ MTd )+2 ( Hp )+2d (1+ 8(MT)^3/2 d ) (11) OPEN+2d2log(1+8cβdM2T2log(1+dMHT/p)))+8H2d2. +2d^2 (1+8c_β dM^2T^2 (1+dMHT/p) ) )+8H^2d^2. Thus, we have: Γp≤CH2d2χ, _p≤ CH^2d^2χ, where χ=log(1+(cβ+1)dMHT/p)χ= (1+(c_β+1)dMHT/p) and C is an absolute constant independent of cβc_β. ∎ Appendix C Proof of Theorem 1 C.1 Supporting Lemmas For the trajectory generated by agent m in episode t, define δhm,t _h^m,t ≔Vhk(t)(xhm,t)−Vhπk(t)(xhm,t), V_h^k(t)(x_h^m,t)-V_h^π^k(t)(x_h^m,t), m,t,h _m,t,h ≔σ((xℓn,j,aℓn,j)(n,j)<(m,t),ℓ∈[H]∪(xℓm,t,aℓm,t)ℓ≤h), σ\! (\(x_ ^n,j,a_ ^n,j)\_(n,j)<(m,t),\, ∈[H]∪\(x_ ^m,t,a_ ^m,t)\_ ≤ h ), ζh+1m,t _h+1^m,t ≔[δh+1m,t∣m,t,h]−δh+1m,t. [ _h+1^m,t _m,t,h ]- _h+1^m,t. Equivalently, ζh+1m,t=ℙh(Vh+1k(t)−Vh+1πk(t))(xhm,t,ahm,t)−(Vh+1k(t)−Vh+1πk(t))(xh+1m,t). _h+1^m,t=P_h (V_h+1^k(t)-V_h+1^π^k(t) )(x_h^m,t,a_h^m,t)- (V_h+1^k(t)-V_h+1^π^k(t) )(x_h+1^m,t). Lemma C.1 (Uniform confidence decomposition for the regression error). Set λ=1λ=1. There exists an absolute constant cβ>0c_β>0 such that for any confidence level p∈(0,1)p∈(0,1), if we take β=cβHdlog(1+dMHT/p)β=c_βHd (1+dMHT/p), then conditioned on the event C defined in Lemma B.9, the following statement holds simultaneously for all rounds k∈[K]k∈[K], steps h∈[H]h∈[H], and state-action pairs (x,a)∈×(x,a) ×A, |ϕ(x,a)⊤whk−Qhπ(x,a)−ℙh(Vh+1k−Vh+1π)(x,a)|≤β‖ϕ(x,a)‖(Λhk)−1, |φ(x,a) w_h^k-Q_h^π(x,a)-P_h (V_h+1^k-V_h+1^π )(x,a) |≤β\,\|φ(x,a)\|_( _h^k)^-1, Lemma C.2. Conditioned on the event C defined in Lemma B.9, for every round k∈[K]k∈[K], step h∈[H]h∈[H] and state-action pair (x,a)∈×(x,a) ×A, the optimistic estimates upper bound the corresponding value functions: Qhk(x,a)≥Qh∗(x,a),Vhk(x)≥Vh∗(x).Q_h^k(x,a)≥ Q_h^*(x,a), V_h^k(x)≥ V_h^*(x). Lemma C.3. For every agent m∈[M]m∈[M], episode t∈[T]t∈[T], and step h∈[H]h∈[H], δhm,t≤δh+1m,t+ζh+1m,t+2β‖ϕ(xhm,t,ahm,t)‖(Λhk(t))−1. _h^m,t≤ _h+1^m,t+ _h+1^m,t+2β\,\|φ(x_h^m,t,a_h^m,t)\|_( _h^k(t))^-1. Lemma C.4 (Concentration of the martingale correction term). For any confidence level p∈(0,1)p∈(0,1), define the event ℰE such that, ∑m=1M∑t=1T∑h=1Hζh+1m,t≤8H3MTlog(2p), _m=1^M _t=1^T _h=1^H _h+1^m,t≤ 8H^3MT ( 2p ), Then ℙ(ℰ)≥1−pP(E)≥ 1-p. Lemma C.5 (Elliptical potential bound). For any λ≥1λ≥ 1 and γ≥1γ≥ 1, ∑h=1H∑k=1K∑t=τkτk+1−1∑m=1M‖ϕ(xhm,t,ahm,t)‖(Λhk)−1≤ _h=1^H _k=1^K _t= _k _k+1-1 _m=1^M\|φ(x_h^m,t,a_h^m,t)\|_( _h^k)^-1≤ H(6dMTlog(1+MTdλ)+Mdlog3γlogγlog(1+MTdλ)+Mdλlog3log(1+MTdλ)). H ( 6dMT (1+ MTdλ )+ Md 3 γ γ\, (1+ MTdλ )+ Md λ\, 3\, (1+ MTdλ ) ). C.2 Proof of Theorem 1 Proof of Theorem 1. The event ∩ℰC holds with probability at least 1−2p1-2p. We now prove Theorem 1 under the event ∩ℰC , under which all supporting lemmas in Section C.1 hold. We first expand the regret and reduce it to bounding ∑m,tδ1m,t _m,t _1^m,t. For each episode t and each agent m, the executed policy is exactly πk(t)π^k(t). Lemma C.2 implies V1∗(x)≤V1k(t)(x)V_1^*(x)≤ V_1^k(t)(x) for every state x, hence Regret(T) (T) =∑m=1M∑t=1T(V1∗(x1m,t)−V1πk(t)(x1m,t)) = _m=1^M _t=1^T (V_1^*(x_1^m,t)-V_1^π^k(t)(x_1^m,t) ) ≤∑m=1M∑t=1T(V1k(t)(x1m,t)−V1πk(t)(x1m,t)) ≤ _m=1^M _t=1^T (V_1^k(t)(x_1^m,t)-V_1^π^k(t)(x_1^m,t) ) =∑m=1M∑t=1Tδ1m,t. = _m=1^M _t=1^T _1^m,t. Summing Lemma C.3 over h=1,…,Hh=1,…,H and using δH+1m,t=0 _H+1^m,t=0 gives δ1m,t≤∑h=1Hζh+1m,t+2β∑h=1H‖ϕ(xhm,t,ahm,t)‖(Λhk(t))−1. _1^m,t≤ _h=1^H _h+1^m,t+2β _h=1^H\|φ(x_h^m,t,a_h^m,t)\|_( _h^k(t))^-1. Summing over all (m,t)(m,t) and regrouping by rounds yields ∑m=1M∑t=1Tδ1m,t≤∑m=1M∑t=1T∑h=1Hζh+1m,t⏟martingale term+2β∑k=1K∑t=τkτk+1−1∑m=1M∑h=1H‖ϕ(xhm,t,ahm,t)‖(Λhk)−1⏟elliptical-potential term. _m=1^M _t=1^T _1^m,t≤ _m=1^M _t=1^T _h=1^H _h+1^m,t_martingale term+2β _k=1^K _t= _k _k+1-1 _m=1^M _h=1^H\|φ(x_h^m,t,a_h^m,t)\|_( _h^k)^-1_elliptical-potential term. On the event ∩ℰC , we have Regret(T) (T) ≤8H3MTlog(2p)+2Hβ(6dMTlog(1+MTdλ)CLOSE ≤\; 8H^3MT ( 2p )+2Hβ ( 6dMT (1+ MTdλ ) OPEN+Mdlog3γlogγlog(1+MTdλ)+Mdλlog3log(1+MTdλ)). + Md 3 γ γ\, (1+ MTdλ )+ Md λ\, 3\, (1+ MTdλ ) ). where β=cβHdlog(1+dMHT/p)β=c_βHd (1+dMHT/p). By setting λ=1λ=1 and plugging in β, the above bound directly recovers the regret bound stated in Theorem 1: Regret(T) (T) ≤(2cβ6+42)Md3H4Tlog(1+dMHTp)log(1+MTd) ≤\;(2c_β 6+4 2) Md^3H^4T (1+ dMHTp ) (1+ MTd ) +2cβMd2H2log3(γlogγ+1)log(1+MTd). + 2c_βMd^2H^2 3( γ γ+1)\, (1+ MTd ). (12) ∎ C.3 Proof of Supporting Lemmas C.3.1 Proof of Lemma C.1 Proof of Lemma C.1. Fix a round k, a step h, a policy π, and a state-action pair (x,a)(x,a). We begin from an exact algebraic decomposition of whk−whπw_h^k-w_h^π. By (1) and Lemma B.2, we have Qhπ(x,a)=rh(x,a)+ℙhVh+1π(x,a)=ϕ(x,a)⊤whπ,Q_h^π(x,a)=r_h(x,a)+P_hV_h+1^π(x,a)=φ(x,a) w_h^π, we obtain whk−whπ=(Λhk)−1∑m=1M∑j=1τk−1ϕ(xhm,j,ahm,j)[rh(xhm,j,ahm,j)+Vh+1k(xh+1m,j)]−whπ w_h^k-w_h^π=( _h^k)^-1 _m=1^M _j=1 _k-1φ(x_h^m,j,a_h^m,j) [r_h(x_h^m,j,a_h^m,j)+V_h+1^k(x_h+1^m,j) ]-w_h^π =(Λhk)−1∑m=1M∑j=1τk−1ϕ(xhm,j,ahm,j)[Vh+1k(xh+1m,j)−ℙhVh+1π(xhm,j,ahm,j)]−λ(Λhk)−1whπ =( _h^k)^-1 _m=1^M _j=1 _k-1φ(x_h^m,j,a_h^m,j) [V_h+1^k(x_h+1^m,j)-P_hV_h+1^π(x_h^m,j,a_h^m,j) ]-λ( _h^k)^-1w_h^π =(Λhk)−1∑m=1M∑j=1τk−1ϕ(xhm,j,ahm,j)[Vh+1k(xh+1m,j)−ℙhVh+1k(xhm,j,ahm,j)] =( _h^k)^-1 _m=1^M _j=1 _k-1φ(x_h^m,j,a_h^m,j) [V_h+1^k(x_h+1^m,j)-P_hV_h+1^k(x_h^m,j,a_h^m,j) ] +(Λhk)−1∑m=1M∑j=1τk−1ϕ(xhm,j,ahm,j)ℙh(Vh+1k−Vh+1π)(xhm,j,ahm,j)−λ(Λhk)−1whπ. +( _h^k)^-1 _m=1^M _j=1 _k-1φ(x_h^m,j,a_h^m,j)\,P_h (V_h+1^k-V_h+1^π )(x_h^m,j,a_h^m,j)-λ( _h^k)^-1w_h^π. (13) Now define νhk,π≔∫(Vh+1k(s′)−Vh+1π(s′))μh(ds′). _h^k,π _X (V_h+1^k(s )-V_h+1^π(s ) )\, _h(ds ). By linearity of the transition probability, ℙh(Vh+1k−Vh+1π)(x,a)=ϕ(x,a)⊤νhk,π.P_h (V_h+1^k-V_h+1^π )(x,a)=φ(x,a) _h^k,π. (14) Therefore, (Λhk)−1∑m=1M∑j=1τk−1ϕ(xhm,j,ahm,j)ℙh(Vh+1k−Vh+1π)(xhm,j,ahm,j) ( _h^k)^-1 _m=1^M _j=1 _k-1φ(x_h^m,j,a_h^m,j)\,P_h (V_h+1^k-V_h+1^π )(x_h^m,j,a_h^m,j) =(Λhk)−1(Λhk−λId)νhk,π =( _h^k)^-1( _h^k-λ I_d) _h^k,π =νhk,π−λ(Λhk)−1νhk,π. = _h^k,π-λ( _h^k)^-1 _h^k,π. Combined with the (13) and (14), we arrive at ϕ(x,a)⊤whk−Qhπ(x,a)−ℙh(Vh+1k−Vh+1π)(x,a) φ(x,a) w_h^k-Q_h^π(x,a)-P_h (V_h+1^k-V_h+1^π )(x,a) (15) =⟨ϕ(x,a),whk−whπ−νhk,π⟩ = φ(x,a),w_h^k-w_h^π- _h^k,π =⟨ϕ(x,a),∑m=1M∑j=1τk−1ϕ(xhm,j,ahm,j)[Vh+1k(xh+1m,j)−ℙhVh+1k(xhm,j,ahm,j)]⟩(Λhk)−1 = φ(x,a), _m=1^M _j=1 _k-1φ(x_h^m,j,a_h^m,j) [V_h+1^k(x_h+1^m,j)-P_hV_h+1^k(x_h^m,j,a_h^m,j) ] _( _h^k)^-1 −λ⟨ϕ(x,a),whπ+νhk,π⟩(Λhk)−1. -λ\, φ(x,a),w_h^π+ _h^k,π _( _h^k)^-1. For the first term of (15), Cauchy-Schwarz and conditioned on the event C give |⟨ϕ(x,a),∑m=1M∑j=1τk−1ϕ(xhm,j,ahm,j)[Vh+1k(xh+1m,j)−ℙhVh+1k(xhm,j,ahm,j)]⟩(Λhk)−1| | φ(x,a),\, _m=1^M _j=1 _k-1φ(x_h^m,j,a_h^m,j) [V_h+1^k(x_h+1^m,j)-P_hV_h+1^k(x_h^m,j,a_h^m,j) ] _( _h^k)^-1 | ≤‖ϕ(x,a)‖(Λhk)−1‖∑m=1M∑j=1τk−1ϕ(xhm,j,ahm,j)[Vh+1k(xh+1m,j)−ℙhVh+1k(xhm,j,ahm,j)]‖(Λhk)−1 ≤\|φ(x,a)\|_( _h^k)^-1 \| _m=1^M _j=1 _k-1φ(x_h^m,j,a_h^m,j) [V_h+1^k(x_h+1^m,j)-P_hV_h+1^k(x_h^m,j,a_h^m,j) ] \|_( _h^k)^-1 ≤CHdχ‖ϕ(x,a)‖(Λhk)−1. ≤ CHd χ\,\|φ(x,a)\|_( _h^k)^-1. (16) For the second term of (15), note that whπ+νhk,π=θh+∫Vh+1k(s′)μh(ds′).w_h^π+ _h^k,π= _h+ _XV_h+1^k(s )\, _h(ds ). Similar with the proof in Lemma B.2, we have ‖whπ+νhk,π‖2≤2Hd\|w_h^π+ _h^k,π\|_2≤ 2H d. Using again Λhk⪰Id _h^k I_d, λ|⟨ϕ(x,a),whπ+νhk,π⟩(Λhk)−1| λ\, | φ(x,a),w_h^π+ _h^k,π _( _h^k)^-1 | ≤‖ϕ(x,a)‖(Λhk)−1‖whπ+νhk,π‖(Λhk)−1≤2Hd‖ϕ(x,a)‖(Λhk)−1. ≤\|φ(x,a)\|_( _h^k)^-1\,\|w_h^π+ _h^k,π\|_( _h^k)^-1≤ 2H d\,\|φ(x,a)\|_( _h^k)^-1. (17) Combining the two bounds (16) and (17), we have |ϕ(x,a)⊤whk−Qhπ(x,a)−ℙh(Vh+1k−Vh+1π)(x,a)|≤(2Hd+CHdχ)‖ϕ(x,a)‖(Λhk)−1. |φ(x,a) w_h^k-Q_h^π(x,a)-P_h (V_h+1^k-V_h+1^π )(x,a) |≤(2H d+CHd χ)\,\|φ(x,a)\|_( _h^k)^-1. (18) There exists an absolute constant cβ>0c_β>0 such that for all d,H,M,T≥1d,H,M,T≥ 1, 2Hd+CHdχ≤cβHdlog(1+dMHT/p).2H d+CHd χ\;≤\;c_βHd (1+dMHT/p ). Indeed, it suffices to verify that there exists cβ>0c_β>0 such that for all x≥1x≥ 1, 2+Clog(1+(cβ+1)x)≤cβlog(1+x).2+C (1+(c_β+1)x )\;≤\;c_β (1+x). This condition can be satisfied by choosing cβ=8(C+1)2c_β=8(C+1)^2. ∎ C.3.2 Proof of Lemma C.2 Proof of Lemma C.2. We prove optimism by backward induction on h. Base case h=Hh=H. At the last step, VH+1k≡VH+1∗≡0V_H+1^k≡ V_H+1^*≡ 0. Applying Lemma C.1 with π=π∗π=π^* gives ϕ(x,a)⊤wHk≥QH∗(x,a)−β‖ϕ(x,a)‖(ΛHk)−1.φ(x,a) w_H^k≥ Q_H^*(x,a)-β\,\|φ(x,a)\|_( _H^k)^-1. By the definition of the optimistic estimator, for any (x,a,k)∈×[K](x,a,k) ×A×[K], it holds that QHk(x,a)=Π[0,H](ϕ(x,a)⊤wHk+β‖ϕ(x,a)‖(ΛHk)−1)≥QH∗(x,a).Q_H^k(x,a)= _[0,H] (φ(x,a) w_H^k+β\,\|φ(x,a)\|_( _H^k)^-1 )≥ Q_H^*(x,a). Therefore VHk(x)=maxaQHk(x,a)≥maxaQH∗(x,a)=VH∗(x)V_H^k(x)= _aQ^k_H(x,a)≥ _aQ^*_H(x,a)=V_H^*(x). Induction step. Assume that Qh+1k(x,a)≥Qh+1∗(x,a)Q_h+1^k(x,a)≥ Q_h+1^*(x,a) and Vh+1k(x)≥Vh+1∗(x)V_h+1^k(x)≥ V_h+1^*(x) for any (x,a,k)∈×[K](x,a,k) ×A×[K]. Then ℙh(Vh+1k−Vh+1∗)(x,a)≥0P_h(V_h+1^k-V_h+1^*)(x,a)≥ 0 for any (x,a,k)(x,a,k). Applying Lemma C.1 with π=π∗π=π^* yields ϕ(x,a)⊤whk φ(x,a) w_h^k ≥Qh∗(x,a)+ℙh(Vh+1k−Vh+1∗)(x,a)−β‖ϕ(x,a)‖(Λhk)−1 ≥ Q_h^*(x,a)+P_h (V_h+1^k-V_h+1^* )(x,a)-β\,\|φ(x,a)\|_( _h^k)^-1 ≥Qh∗(x,a)−β‖ϕ(x,a)‖(Λhk)−1. ≥ Q_h^*(x,a)-β\,\|φ(x,a)\|_( _h^k)^-1. Therefore, for any (x,a,k)∈×[K](x,a,k) ×A×[K], we have Qhk(x,a)=Π[0,H](ϕ(x,a)⊤whk+β‖ϕ(x,a)‖(Λhk)−1)≥Qh∗(x,a)Q_h^k(x,a)= _[0,H] (φ(x,a) w_h^k+β\,\|φ(x,a)\|_( _h^k)^-1 )≥ Q_h^*(x,a) and thus Vhk(x)=maxaQhk(x,a)≥maxaQh∗(x,a)=Vh∗(x).V_h^k(x)= _aQ^k_h(x,a)≥ _aQ^*_h(x,a)=V_h^*(x). This completes the proof for step h, and hence the conclusion follows by backward induction. ∎ C.3.3 Proof of Lemma C.3 Proof of Lemma C.3. Let k=k(t)k=k(t) be the round index that the t-th episode is in. Fix an agent m, an episode t. Since πk(t)π^k(t) is greedy with respect to QhkQ_h^k, Vhk(t)(xhm,t)=Qhk(t)(xhm,t,ahm,t),Vhπk(t)(xhm,t)=Qhπk(t)(xhm,t,ahm,t).V_h^k(t)(x_h^m,t)=Q_h^k(t)(x_h^m,t,a_h^m,t), V_h^π^k(t)(x_h^m,t)=Q_h^π^k(t)(x_h^m,t,a_h^m,t). Therefore, δhm,t=Qhk(t)(xhm,t,ahm,t)−Qhπk(t)(xhm,t,ahm,t). _h^m,t=Q_h^k(t)(x_h^m,t,a_h^m,t)-Q_h^π^k(t)(x_h^m,t,a_h^m,t). Applying Lemma C.1 with π=πk(t)π=π^k(t) and using the definition of Qhk(t)Q_h^k(t) gives δhm,t≤ℙh(Vh+1k(t)−Vh+1πk(t))(xhm,t,ahm,t)+2β‖ϕ(xhm,t,ahm,t)‖(Λhk)−1. _h^m,t _h (V_h+1^k(t)-V_h+1^π^k(t) )(x_h^m,t,a_h^m,t)+2β\,\|φ(x_h^m,t,a_h^m,t)\|_( _h^k)^-1. The preceding argument applies unless the lower clipping is active, namely when the unprojected optimistic score is negative. In this case Qhk=0Q_h^k=0, and thus δhm,t=−Qhπk(t)(xhm,t,ahm,t) _h^m,t=-Q_h^π^k(t)(x_h^m,t,a_h^m,t) =−rh(xhm,t,ahm,t)−ℙhVh+1πk(t)(xhm,t,ahm,t) =-r_h(x_h^m,t,a_h^m,t)-P_hV_h+1^π^k(t)(x_h^m,t,a_h^m,t) ≤ℙh(Vh+1k(t)−Vh+1πk(t))(xhm,t,ahm,t), _h (V_h+1^k(t)-V_h+1^π^k(t) )(x_h^m,t,a_h^m,t), because rh≥0r_h≥ 0 and Vh+1k(t)≥0V_h+1^k(t)≥ 0. Combining the two cases and noting that ℙh(Vh+1k(t)−Vh+1πk(t))(xhm,t,ahm,t)=[δh+1m,t∣m,t,h]=δh+1m,t+ζh+1m,t,P_h (V_h+1^k(t)-V_h+1^π^k(t) )(x_h^m,t,a_h^m,t)=E [ _h+1^m,t _m,t,h ]= _h+1^m,t+ _h+1^m,t, we finish the proof of the conclusion. ∎ C.3.4 Proof of Lemma C.4 Proof of Lemma C.4. By construction, [ζh+1m,t∣m,t,h]=0E[ _h+1^m,t _m,t,h]=0, so the sequence ζh+1m,tm,t,h\ _h+1^m,t\_m,t,h is a martingale-difference array under the linearized ordering. Moreover, both Vh+1k(t)V_h+1^k(t) and Vh+1πk(t)V_h+1^π^k(t) lie in [0,H][0,H], hence |ζh+1m,t|≤2H| _h+1^m,t|≤ 2H. Applying Azuma–Hoeffding to the sum over all MTHMTH terms gives ℙ(|∑m=1M∑t=1T∑h=1Hζh+1m,t|>u)≤2exp(−u28H3MT).P ( | _m=1^M _t=1^T _h=1^H _h+1^m,t |>u )≤ 2 (- u^28H^3MT ). Setting u=8H3MTlog(2/p)u= 8H^3MT (2/p) yields the claim. ∎ C.3.5 Proof of Lemma C.5 Proof of Lemma C.5. Fix a step h∈[H]h∈[H]. We bound ∑k=1K∑t=τkτk+1−1∑m=1M‖ϕ(xhm,t,ahm,t)‖(Λhk)−1, _k=1^K _t= _k _k+1-1 _m=1^M\|φ(x_h^m,t,a_h^m,t)\|_( _h^k)^-1, and then sum the result over h=1,…,Hh=1,…,H. Step 1: Split rounds by global determinant growth. Define 1(h)≔k:det(Λhk+1)det(Λhk)≤3,2(h)≔k:det(Λhk+1)det(Λhk)>3.K_1(h) \k: ( _h^k+1) ( _h^k)≤ 3 \, _2(h) \k: ( _h^k+1) ( _h^k)>3 \. Step 2: Analysis for rounds with small determinant growth. Fix k∈1(h)k _1(h) and any (m,t)(m,t) with t∈[τk,τk+1−1]t∈[ _k, _k+1-1]. Since Λhk⪯Λhk+1 _h^k _h^k+1, by Lemma B.1, for any x∈ℝdx ^d ‖x‖(Λhk)−12≤det(Λhk+1)det(Λhk)‖x‖(Λhk+1)−12.\|x\|_( _h^k)^-1^2≤ ( _h^k+1) ( _h^k)\,\|x\|_( _h^k+1)^-1^2. Hence ‖x‖(Λhk)−1≤3‖x‖(Λhk+1)−1.\|x\|_( _h^k)^-1≤ 3\,\|x\|_( _h^k+1)^-1. (19) Recall that Λ~hm,t _h^m,t =λId+∑(n,j)≤(m,t)ϕ(xhn,j,ahn,j)ϕ(xhn,j,ahn,j)⊤ =λ I_d+ _(n,j)≤(m,t)φ(x_h^n,j,a_h^n,j)φ(x_h^n,j,a_h^n,j) =Λhk+∑(n,j)≤(m,t)k(j)=kϕ(xhn,j,ahn,j)ϕ(xhn,j,ahn,j)⊤. = _h^k+ _ subarrayc(n,j)≤(m,t)\\ k(j)=k subarrayφ(x_h^n,j,a_h^n,j)φ(x_h^n,j,a_h^n,j) . Here the last summation is over those pairs (n,j)≤(m,t)(n,j)≤(m,t) such that episode j lies in round k. Hence, it holds that Λhk+1⪰Λ~hm,t⪰Λhk. _h^k+1 _h^m,t _h^k. and thus together with (19), we have ‖ϕ(xhm,t,ahm,t)‖(Λhk)−1≤3‖ϕ(xhm,t,ahm,t)‖(Λhk+1)−1≤3‖ϕ(xhm,t,ahm,t)‖(Λ~hm,t)−1.\|φ(x_h^m,t,a_h^m,t)\|_( _h^k)^-1≤ 3\,\|φ(x_h^m,t,a_h^m,t)\|_( _h^k+1)^-1≤ 3\,\|φ(x_h^m,t,a_h^m,t)\|_( _h^m,t)^-1. Summing the inequality above and applying Cauchy–Schwarz inequality yields ∑k∈1(h)∑t=τkτk+1−1∑m=1M‖ϕ(xhm,t,ahm,t)‖(Λhk)−1 _k _1(h) _t= _k _k+1-1 _m=1^M\|φ(x_h^m,t,a_h^m,t)\|_( _h^k)^-1 ≤3∑t=1T∑m=1M‖ϕ(xhm,t,ahm,t)‖(Λ~hm,t)−1 ≤ 3 _t=1^T _m=1^M\|φ(x_h^m,t,a_h^m,t)\|_( _h^m,t)^-1 ≤3MT∑t=1T∑m=1M‖ϕ(xhm,t,ahm,t)‖(Λ~hm,t)−12. ≤ 3MT _t=1^T _m=1^M\|φ(x_h^m,t,a_h^m,t)\|_( _h^m,t)^-1^2. Because Λ~hm,t ^m,t_h is updated sequentially in (m,t)(m,t), we can apply Lemma B.6 here and get ∑t=1T∑m=1M‖ϕ(xhm,t,ahm,t)‖(Λ~hm,t)−12≤2logdet(Λ~hM,T)det(λId)≤2dlog(1+MTdλ). _t=1^T _m=1^M\|φ(x_h^m,t,a_h^m,t)\|_( _h^m,t)^-1^2≤ 2 ( _h^M,T) (λ I_d)≤ 2d (1+ MTdλ ). Therefore, ∑k∈1(h)∑t=τkτk+1−1∑m=1M‖ϕ(xhm,t,ahm,t)‖(Λhk)−1≤6dMTlog(1+MTdλ). _k _1(h) _t= _k _k+1-1 _m=1^M\|φ(x_h^m,t,a_h^m,t)\|_( _h^k)^-1≤ 6dMT (1+ MTdλ ). (20) Step 3: Analysis for rounds with large determinant growth. Fix k∈2(h)k _2(h) and suppose first that τk+1−τk≥2 _k+1- _k≥ 2. For one agent m, define the agent-wise pseudo covariance matrix Λ¯hm,t=Λhk+∑j=τktϕ(xhm,j,ahm,j)ϕ(xhm,j,ahm,j)⊤,t∈[τk,τk+1−1]. _h^m,t= _h^k+ _j= _k^tφ(x_h^m,j,a_h^m,j)φ(x_h^m,j,a_h^m,j) , t∈[ _k, _k+1-1]. Recall that Λhm,k,loc=∑t=τkτk+1−1ϕ(xhm,t,ahm,t)ϕ(xhm,t,ahm,t)⊤ _h^m,k,loc= _t= _k _k+1-1φ(x_h^m,t,a_h^m,t)φ(x_h^m,t,a_h^m,t) and Λhk+1=Λhk+∑m=1MΛhm,k,loc, _h^k+1= _h^k+ _m=1^M _h^m,k,loc, we have Λ¯hm,t⪯Λhk+Λhm,k,loc⪯Λhk+1. _h^m,t _h^k+ _h^m,k,loc _h^k+1. For any t∈[τk,τk+1−2]t∈[ _k, _k+1-2], by (19), we have ‖ϕ(xhm,t,ahm,t)‖(Λhk)−1≤det(Λ¯hm,τk+1−2)det(Λhk)‖ϕ(xhm,t,ahm,t)‖(Λ¯hm,t)−1.\|φ(x_h^m,t,a_h^m,t)\|_( _h^k)^-1≤ ( _h^m, _k+1-2) ( _h^k)\,\|φ(x_h^m,t,a_h^m,t)\|_( _h^m,t)^-1. Summing this inequality over t=τk,…,τk+1−2t= _k,…, _k+1-2 and applying Cauchy–Schwarz inequality, we reach ∑t=τkτk+1−2‖ϕ(xhm,t,ahm,t)‖(Λhk)−1 _t= _k _k+1-2\|φ(x_h^m,t,a_h^m,t)\|_( _h^k)^-1 ≤[(τk+1−τk−1)det(Λ¯hm,τk+1−2)det(Λhk)⋅∑t=τkτk+1−2‖ϕ(xhm,t,ahm,t)‖(Λ¯hm,t)−12]1/2 ≤ [( _k+1- _k-1)\, ( _h^m, _k+1-2) ( _h^k)· _t= _k _k+1-2\|φ(x_h^m,t,a_h^m,t)\|_( _h^m,t)^-1^2 ]^1/2 ≤[(τk+1−τk−1)det(Λ¯hm,τk+1−2)det(Λhk)⋅logdet(Λ¯hm,τk+1−2)det(Λhk)]1/2. ≤ [( _k+1- _k-1)\, ( _h^m, _k+1-2) ( _h^k)· ( _h^m, _k+1-2) ( _h^k) ]^1/2. (21) The last inequality is by Lemma B.6. Here, we note that the construction of Λ¯hm,t _h^m,t guarantees the use of Lemma B.6, because the sum grows in episode order. Now use the stopping rule. At time t=τk+1−2t= _k+1-2 the round has not yet stopped, so the determinant trigger has not fired. Hence det(Λ¯hm,τk+1−2)det(Λhk)≤γτk+1−τk−1. ( _h^m, _k+1-2) ( _h^k)≤ γ _k+1- _k-1. Combining this bound and (21) yields ∑t=τkτk+1−2‖ϕ(xhm,t,ahm,t)‖(Λhk)−1≤γlog(γτk+1−τk−1)≤γlogγ. _t= _k _k+1-2\|φ(x_h^m,t,a_h^m,t)\|_( _h^k)^-1≤ γ ( γ _k+1- _k-1 )≤ γ γ. Summing over m and then over k∈2(h)k _2(h) gives ∑k∈2(h)∑t=τkτk+1−2∑m=1M‖ϕ(xhm,t,ahm,t)‖(Λhk)−1≤M|2(h)|γlogγ. _k _2(h) _t= _k _k+1-2 _m=1^M\|φ(x_h^m,t,a_h^m,t)\|_( _h^k)^-1≤ M\,|K_2(h)|\, γ γ. To bound |2(h)||K_2(h)|, note that |2(h)|log3≤∑k∈2(h)logdet(Λhk+1)det(Λhk)≤logdet(ΛhK+1)det(Λh1)≤dlog(1+MTdλ).|K_2(h)| 3≤ _k _2(h) ( _h^k+1) ( _h^k)≤ ( _h^K+1) ( _h^1)≤ d (1+ MTdλ ). Therefore, ∑k∈2(h)∑t=τkτk+1−2∑m=1M‖ϕ(xhm,t,ahm,t)‖(Λhk)−1≤Mdlog3γlogγlog(1+MTdλ). _k _2(h) _t= _k _k+1-2 _m=1^M\|φ(x_h^m,t,a_h^m,t)\|_( _h^k)^-1≤ Md 3 γ γ\, (1+ MTdλ ). (22) Step 4: Analysis for residual last-episode terms. For the remaining terms at t=τk+1−1t= _k+1-1 with k∈2(h)k _2(h), we simply use ‖ϕ(x,a)‖(Λhk)−1≤1λ,\|φ(x,a)\|_( _h^k)^-1≤ 1 λ, which follows from Λhk⪰λId _h^k λ I_d and ‖ϕ(x,a)‖2≤1\|φ(x,a)\|_2≤ 1. Hence ∑k∈2(h)∑m=1M‖ϕ(xhm,τk+1−1,ahm,τk+1−1)‖(Λhk)−1≤Mλ|2(h)|≤Mdλlog3log(1+MTdλ). _k _2(h) _m=1^M\|φ(x_h^m, _k+1-1,a_h^m, _k+1-1)\|_( _h^k)^-1≤ M λ\,|K_2(h)|≤ Md λ\, 3 (1+ MTdλ ). (23) Step 5: combine and sum over steps. Adding the bounds (20), (22), (23) and then summing over h=1,…,Hh=1,…,H proves the lemma. ∎ Appendix D Proof of Theorem 2 Throughout this section, we consider the misspecified setting in Definition 2. Define (rh,ℙh)h=1H\(r_h,P_h)\_h=1^H to be the common reference linear reward and transition kernel in Definition 2, where rh(x,a)=⟨ϕ(x,a),θh⟩,ℙh(B∣x,a)=⟨ϕ(x,a),μh(B)⟩.r_h(x,a)= φ(x,a), _h , _h(B x,a)= φ(x,a), _h(B) . For each agent m∈[M]m∈[M], we write Qm,hπQ_m,h^π and Vm,hπV_m,h^π for the value functions induced by the local MDP of agent m under policy π, and Qm,h⋆,Vm,h⋆Q_m,h ,V_m,h for the corresponding optimal functions under the optimal policy πm⋆ _m . D.1 Heterogeneity-Specific Lemmas Lemma D.1. For any agent m∈[M]m∈[M], policy π, and step h∈[H]h∈[H], define wm,hπ:=θh+∫Vm,h+1π(x′)μh(dx′).w_m,h^π:= _h+ _XV_m,h+1^π(x )\, _h(dx ). Then, for every (x,a)∈×(x,a) ×A, |Qm,hπ(x,a)−ϕ(x,a)⊤wm,hπ|≤Hξ. |Q_m,h^π(x,a)-φ(x,a) w_m,h^π |≤ Hξ. Moreover, ‖wm,hπ‖2≤2Hd\|w_m,h^π\|_2≤ 2H d. Proof of Lemma D.1. By the linearity of the reference model, ϕ(x,a)⊤wm,hπ=rh(x,a)+ℙhVm,h+1π(x,a).φ(x,a) w_m,h^π=r_h(x,a)+P_hV_m,h+1^π(x,a). Therefore, |Qm,hπ(x,a)−ϕ(x,a)⊤wm,hπ| |Q_m,h^π(x,a)-φ(x,a) w_m,h^π | ≤|rm,h(x,a)−rh(x,a)|+|(ℙm,h−ℙh)Vm,h+1π(x,a)| ≤ |r_m,h(x,a)-r_h(x,a) |+ | (P_m,h-P_h )V_m,h+1^π(x,a) | ≤ξ+(H−h)ξ≤Hξ, ≤ξ+(H-h)ξ≤ Hξ, where we used 0≤Vm,h+1π≤H−h0≤ V_m,h+1^π≤ H-h. The norm bound follows from ‖wm,hπ‖2≤‖θh‖2+‖∫Vm,h+1π(x′)μh(dx′)‖2≤d+Hd≤2Hd.\|w_m,h^π\|_2≤\| _h\|_2+ \| _XV_m,h+1^π(x )\, _h(dx ) \|_2≤ d+H d≤ 2H d. ∎ Lemma D.2. Let εm,tm∈[M],t∈[T]\ ^m,t\_m∈[M],\,t∈[T] be any collection satisfying |εm,t|≤B| ^m,t|≤ B for all (m,t)(m,t). Then, for every step h∈[H]h∈[H], round k∈[K]k∈[K], and vector u∈ℝdu ^d, |u⊤(Λhk)−1∑m=1M∑t=1τk−1ϕ(xhm,t,ahm,t)εm,t|≤BdMτk‖u‖(Λhk)−1. |u ( _h^k)^-1 _m=1^M _t=1 _k-1φ(x_h^m,t,a_h^m,t)\, ^m,t |≤ B dM _k\,\|u\|_( _h^k)^-1. Proof of Lemma D.2. Using the triangle inequality, |u⊤(Λhk)−1∑m=1M∑t=1τk−1ϕ(xhm,t,ahm,t)εm,t| |u ( _h^k)^-1 _m=1^M _t=1 _k-1φ(x_h^m,t,a_h^m,t)\, ^m,t | ≤B∑m=1M∑t=1τk−1|u⊤(Λhk)−1ϕ(xhm,t,ahm,t)| ≤ B _m=1^M _t=1 _k-1 |u ( _h^k)^-1φ(x_h^m,t,a_h^m,t) | ≤B∑m=1M∑t=1τk−1(‖u‖(Λhk)−1ϕ(xhm,t,ahm,t)⊤(Λhk)−1ϕ(xhm,t,ahm,t)) ≤ B _m=1^M _t=1 _k-1 (\|u\|_( _h^k)^-1 φ(x_h^m,t,a_h^m,t) ( _h^k)^-1φ(x_h^m,t,a_h^m,t) ) ≤BM(τk−1)‖u‖(Λhk)−1[∑m=1M∑t=1τk−1ϕ(xhm,t,ahm,t)⊤(Λhk)−1ϕ(xhm,t,ahm,t)]1/2. ≤ B M( _k-1)\,\|u\|_( _h^k)^-1 [ _m=1^M _t=1 _k-1φ(x_h^m,t,a_h^m,t) ( _h^k)^-1φ(x_h^m,t,a_h^m,t) ]^1/2. The last two inequalities hold due to the Cauchy–Schwarz inequality. Moreover, note that ∑m=1M∑t=1τk−1ϕ(xhm,t,ahm,t)⊤(Λhk)−1ϕ(xhm,t,ahm,t) _m=1^M _t=1 _k-1φ(x_h^m,t,a_h^m,t) ( _h^k)^-1φ(x_h^m,t,a_h^m,t) =tr((Λhk)−1(Λhk−λId))≤d. =tr\! (( _h^k)^-1( _h^k-λ I_d) )≤ d. Combining the two displays and using M(τk−1)≤MτkM( _k-1)≤ M _k proves the claim. ∎ Lemma D.3 (Uniform concentration with agent-dependent transitions). Fix p¯∈(0,1) p∈(0,1) and set λ=1λ=1. Suppose the optimistic estimates are formed with bonus parameter β=cβ′Hdlog(1+dMHTp¯)+2HξdMT,β=c_β Hd (1+ dMHT p )+2Hξ dMT, where cβ′>0c_β >0 is a sufficiently large positive constant. Then there exists an absolute constant C>0C>0 such that, if we define an event hetC_het as, simultaneously for all steps h∈[H]h∈[H] and rounds k∈[K]k∈[K], ∥∑m=1M∑t=1τk−1ϕ(xhm,t,ahm,t) \| _m=1^M _t=1 _k-1φ(x_h^m,t,a_h^m,t) [Vh+1k(xh+1m,t)−ℙm,hVh+1k(xhm,t,ahm,t)]∥(Λhk)−1 [V_h+1^k(x_h+1^m,t)-P_m,hV_h+1^k(x_h^m,t,a_h^m,t) ] \|_( _h^k)^-1 ≤CHdlog(1+(cβ′+1)dMHTp¯). ≤ CHd (1+ (c_β +1)dMHT p ). Then ℙ(het)≥1−p¯P(C_het)≥ 1- p. Proof of Lemma D.3. The proof follows the same argument as in Lemma B.9. The only differences are the choice of β and the replacement of the common transition kernel ℙhP_h by the agent-dependent transition kernel ℙm,hP_m,h. Neither difference affects the proof, since the argument only relies on boundedness and the martingale property. ∎ Lemma D.4. Assume λ=1λ=1. There exists an absolute constant cβ′>0c_β >0 such that, for every confidence level p¯∈(0,1) p∈(0,1), if β=cβ′Hdlog(1+dMHTp¯)+2HξdMT,β=c_β Hd (1+ dMHT p )+2Hξ dMT, then conditioned on the event hetC_het defined in Lemma D.3, simultaneously for all agents m∈[M]m∈[M], rounds k∈[K]k∈[K], steps h∈[H]h∈[H], policies π, and state-action pairs (x,a)(x,a), |ϕ(x,a)⊤whk−Qm,hπ(x,a)−ℙh(Vh+1k−Vm,h+1π)(x,a)|≤β‖ϕ(x,a)‖(Λhk)−1+Hξ. |φ(x,a) w_h^k-Q_m,h^π(x,a)-P_h (V_h+1^k-V_m,h+1^π )(x,a) |≤β\,\|φ(x,a)\|_( _h^k)^-1+Hξ. Proof of Lemma D.4. Fix m,k,h,πm,k,h,π, and (x,a)(x,a). Define νm,hk,π:=∫(Vh+1k(x′)−Vm,h+1π(x′))μh(dx′). _m,h^k,π:= _X (V_h+1^k(x )-V_m,h+1^π(x ) )\, _h(dx ). Then ℙh(Vh+1k−Vm,h+1π)(x,a)=ϕ(x,a)⊤νm,hk,π.P_h (V_h+1^k-V_m,h+1^π )(x,a)=φ(x,a) _m,h^k,π. (24) In the misspecified setting, we have whk w_h^k =(Λhk)−1∑n=1M∑t=1τk−1ϕ(xhn,t,ahn,t)[rn,h(xhn,t,ahn,t)+Vh+1k(xh+1n,t)] =( _h^k)^-1 _n=1^M _t=1 _k-1φ(x_h^n,t,a_h^n,t) [r_n,h(x_h^n,t,a_h^n,t)+V_h+1^k(x_h+1^n,t) ] =(Λhk)−1∑n=1M∑t=1τk−1ϕ(xhn,t,ahn,t)[Δn,t,hk+ηn,t,hk+rh(xhn,t,ahn,t)+ℙhVh+1k(xhn,t,ahn,t)], =( _h^k)^-1 _n=1^M _t=1 _k-1φ(x_h^n,t,a_h^n,t) [ _n,t,h^k+ _n,t,h^k+r_h(x_h^n,t,a_h^n,t)+P_hV_h+1^k(x_h^n,t,a_h^n,t) ], where Δn,t,hk:=[rn,h−rref,h](xhn,t,ahn,t)+(ℙn,h−ℙh)Vh+1k(xhn,t,ahn,t), _n,t,h^k:= [r_n,h-r_ref,h ](x_h^n,t,a_h^n,t)+ (P_n,h-P_h )V_h+1^k(x_h^n,t,a_h^n,t), ηn,t,hk:=Vh+1k(xh+1n,t)−ℙn,hVh+1k(xhn,t,ahn,t). _n,t,h^k:=V_h+1^k(x_h+1^n,t)-P_n,hV_h+1^k(x_h^n,t,a_h^n,t). According to the definition of wm,hπw_m,h^π and νm,hk,π _m,h^k,π, we have rh(x,a)+ℙhVh+1k(x,a)=ϕ(x,a)⊤(wm,hπ+νm,hk,π),r_h(x,a)+P_hV_h+1^k(x,a)=φ(x,a) (w_m,h^π+ _m,h^k,π ), and then together with (24), ϕ(x,a)⊤whk−ϕ(x,a)⊤wm,hπ−ℙh(Vh+1k−Vm,h+1π)(x,a) φ(x,a) w_h^k-φ(x,a) w_m,h^π-P_h (V_h+1^k-V_m,h+1^π )(x,a) =ϕ(x,a)⊤(Λhk)−1∑n=1M∑t=1τk−1ϕ(xhn,t,ahn,t)Δn,t,hk+ϕ(x,a)⊤(Λhk)−1∑n=1M∑t=1τk−1ϕ(xhn,t,ahn,t)ηn,t,hk =φ(x,a) ( _h^k)^-1 _n=1^M _t=1 _k-1φ(x_h^n,t,a_h^n,t)\, _n,t,h^k+φ(x,a) ( _h^k)^-1 _n=1^M _t=1 _k-1φ(x_h^n,t,a_h^n,t)\, _n,t,h^k +ϕ(x,a)⊤(Λhk)−1∑n=1M∑t=1τk−1ϕ(xhn,t,ahn,t)ϕ(xhn,t,ahn,t)⊤(wm,hπ+νm,hk,π) +φ(x,a) ( _h^k)^-1 _n=1^M _t=1 _k-1φ(x_h^n,t,a_h^n,t)φ(x_h^n,t,a_h^n,t) (w_m,h^π+ _m,h^k,π ) −ϕ(x,a)⊤(wm,hπ+νm,hk,π) -φ(x,a) (w_m,h^π+ _m,h^k,π ) =ϕ(x,a)⊤(Λhk)−1∑n=1M∑t=1τk−1ϕ(xhn,t,ahn,t)Δn,t,hk+ϕ(x,a)⊤(Λhk)−1∑n=1M∑t=1τk−1ϕ(xhn,t,ahn,t)ηn,t,hk =φ(x,a) ( _h^k)^-1 _n=1^M _t=1 _k-1φ(x_h^n,t,a_h^n,t)\, _n,t,h^k+φ(x,a) ( _h^k)^-1 _n=1^M _t=1 _k-1φ(x_h^n,t,a_h^n,t)\, _n,t,h^k −λϕ(x,a)⊤(Λhk)−1(wm,hπ+νm,hk,π). -λ\,φ(x,a) ( _h^k)^-1 (w_m,h^π+ _m,h^k,π ). (25) In the last equation, we use ∑n=1M∑t=1τk−1ϕ(xhn,t,ahn,t)ϕ(xhn,t,ahn,t)⊤=Λhk−λId. _n=1^M _t=1 _k-1φ(x_h^n,t,a_h^n,t)φ(x_h^n,t,a_h^n,t) = _h^k-λ I_d. For the first term in (25), Definition 2 and 0≤Vh+1k≤H0≤ V_h+1^k≤ H imply |Δn,t,hk|≤2Hξ| _n,t,h^k|≤ 2Hξ, so Lemma D.2 gives |ϕ(x,a)⊤(Λhk)−1∑n=1M∑t=1τk−1ϕ(xhn,t,ahn,t)Δn,t,hk|≤2HξdMT‖ϕ(x,a)‖(Λhk)−1. |φ(x,a) ( _h^k)^-1 _n=1^M _t=1 _k-1φ(x_h^n,t,a_h^n,t)\, _n,t,h^k |≤ 2Hξ dMT\,\|φ(x,a)\|_( _h^k)^-1. For the second martingale term in (25), Cauchy-Schwarz inequality and Lemma D.3 yields |ϕ(x,a)⊤(Λhk)−1∑n=1M∑t=1τk−1ϕ(xhn,t,ahn,t)ηn,t,hk| |φ(x,a) ( _h^k)^-1 _n=1^M _t=1 _k-1φ(x_h^n,t,a_h^n,t)\, _n,t,h^k | ≤‖ϕ(x,a)‖(Λhk)−1‖∑n=1M∑t=1τk−1ϕ(xhn,t,ahn,t)ηn,t,hk‖(Λhk)−1 ≤\|φ(x,a)\|_( _h^k)^-1 \| _n=1^M _t=1 _k-1φ(x_h^n,t,a_h^n,t)\, _n,t,h^k \|_( _h^k)^-1 ≤CHdlog(1+(cβ+1)dMHTp¯)‖ϕ(x,a)‖(Λhk)−1. ≤ CHd (1+ (c_β+1)dMHT p )\,\|φ(x,a)\|_( _h^k)^-1. Moreover, for the last term in (25) ‖wm,hπ+νm,hk,π‖2 \|w_m,h^π+ _m,h^k,π \|_2 =‖θh+∫Vh+1k(x′)μh(dx′)‖2≤d+Hd≤2Hd, = \| _h+ _XV_h+1^k(x )\, _h(dx ) \|_2≤ d+H d≤ 2H d, so by Cauchy-Schwarz inequality and Λhk⪰λI _h^k λ I, λ|ϕ(x,a)⊤(Λhk)−1(wm,hπ+νm,hk,π)| λ\, |φ(x,a) ( _h^k)^-1(w_m,h^π+ _m,h^k,π) | ≤λ‖ϕ(x,a)‖(Λhk)−1‖wm,hπ+νm,hk,π‖(Λhk)−1 ≤λ\,\|φ(x,a)\|_( _h^k)^-1\|w_m,h^π+ _m,h^k,π\|_( _h^k)^-1 ≤2Hdλ‖ϕ(x,a)‖(Λhk)−1. ≤ 2H dλ\,\|φ(x,a)\|_( _h^k)^-1. Finally, Lemma D.1 gives |ϕ(x,a)⊤wm,hπ−Qm,hπ(x,a)|≤Hξ. |φ(x,a) w_m,h^π-Q_m,h^π(x,a) |≤ Hξ. Combining this with the preceding upper bounds for the three terms in (25), and using τk≤T _k≤ T and λ=1λ=1, we obtain |ϕ(x,a)⊤whk−Qm,hπ(x,a)−ℙh(Vh+1k−Vm,h+1π)(x,a)| |φ(x,a) w_h^k-Q_m,h^π(x,a)-P_h (V_h+1^k-V_m,h+1^π )(x,a) | ≤(CHdlog(1+(cβ′+1)dMHTp¯)+2HξdMT+2Hd)‖ϕ(x,a)‖(Λhk)−1+Hξ. ≤ (CHd (1+ (c_β +1)dMHT p )+2Hξ dMT+2H d )\|φ(x,a)\|_( _h^k)^-1+Hξ. Choosing cβ′c_β sufficiently large absorbs the first and third terms into the displayed value of β, which proves the claim. ∎ Lemma D.5. Under the event hetC_het, for every agent m∈[M]m∈[M], round k∈[K]k∈[K], step h∈[H]h∈[H], and state-action pair (x,a)(x,a), Qhk(x,a)≥Qm,h⋆(x,a)−H(H+1−h)ξ,Vhk(x)≥Vm,h⋆(x)−H(H+1−h)ξ.Q_h^k(x,a)≥ Q_m,h (x,a)-H(H+1-h)ξ, V_h^k(x)≥ V_m,h (x)-H(H+1-h)ξ. Proof of Lemma D.5. We argue by backward induction on h. For h=Hh=H, we have VH+1k≡Vm,H+1⋆≡0V_H+1^k≡ V_m,H+1 ≡ 0. Applying Lemma D.4 with π=πm⋆π= _m gives ϕ(x,a)⊤wHk≥Qm,H⋆(x,a)−β‖ϕ(x,a)‖(ΛHk)−1−Hξ.φ(x,a) w_H^k≥ Q_m,H (x,a)-β\,\|φ(x,a)\|_( _H^k)^-1-Hξ. Hence, by the definition of QHkQ_H^k, QHk(x,a)=Π[0,H](ϕ(x,a)⊤wHk+β‖ϕ(x,a)‖(ΛHk)−1)≥Qm,H⋆(x,a)−Hξ.Q_H^k(x,a)= _[0,H] (φ(x,a) w_H^k+β\,\|φ(x,a)\|_( _H^k)^-1 )≥ Q_m,H (x,a)-Hξ. and thus VHk(x)=maxaQHk(x,a)≥maxaQm,H∗(x,a)−Hξ=Vm,H∗(x)−Hξ.V_H^k(x)= _aQ^k_H(x,a)≥ _aQ^*_m,H(x,a)-Hξ=V_m,H^*(x)-Hξ. Now assume the claim holds at step h+1h+1. Then, by induction, for all (x,k)∈×[K](x,k) ×[K], we have Vh+1k(x)≥Vm,h+1⋆(x)−H(H−h)ξ.V_h+1^k(x)≥ V_m,h+1 (x)-H(H-h)ξ. Therefore, ℙh(Vh+1k−Vm,h+1⋆)(x,a)≥−H(H−h)ξ.P_h (V_h+1^k-V_m,h+1 )(x,a)≥-H(H-h)ξ. Applying Lemma D.4 with π=πm⋆π= _m yields ϕ(x,a)⊤whk≥Qm,h⋆(x,a)−H(H−h)ξ−Hξ−β‖ϕ(x,a)‖(Λhk)−1.φ(x,a) w_h^k≥ Q_m,h (x,a)-H(H-h)ξ-Hξ-β\,\|φ(x,a)\|_( _h^k)^-1. Thus, Qhk(x,a)=Π[0,H](ϕ(x,a)⊤whk+β‖ϕ(x,a)‖(Λhk)−1)≥Qm,h⋆(x,a)−H(H+1−h)ξ.Q_h^k(x,a)= _[0,H] (φ(x,a) w_h^k+β\,\|φ(x,a)\|_( _h^k)^-1 )≥ Q_m,h (x,a)-H(H+1-h)ξ. and thus Vhk(x)=maxaQhk(x,a)≥maxaQm,h∗(x,a)−H(H+1−h)ξ=Vm,h∗(x)−H(H+1−h)ξ.V_h^k(x)= _aQ^k_h(x,a)≥ _aQ^*_m,h(x,a)-H(H+1-h)ξ=V_m,h^*(x)-H(H+1-h)ξ. This completes the proof for step h, and hence the conclusion follows by backward induction. ∎ For the trajectory generated by agent m in episode t, define δhm,t _h^m,t :=Vhk(t)(xhm,t)−Vm,hπk(t)(xhm,t), :=V_h^k(t)(x_h^m,t)-V_m,h^π^k(t)(x_h^m,t), m,t,h _m,t,h :=σ((xℓn,j,aℓn,j)(n,j)<(m,t),ℓ∈[H]∪(xℓm,t,aℓm,t)ℓ≤h), :=σ\! (\(x_ ^n,j,a_ ^n,j)\_(n,j)<(m,t),\, ∈[H]∪\(x_ ^m,t,a_ ^m,t)\_ ≤ h ), ζh+1m,t _h+1^m,t :=[δh+1m,t∣m,t,h]−δh+1m,t. :=E [ _h+1^m,t _m,t,h ]- _h+1^m,t. Equivalently, ζh+1m,t=ℙm,h(Vh+1k(t)−Vm,h+1πk(t))(xhm,t,ahm,t)−(Vh+1k(t)−Vm,h+1πk(t))(xh+1m,t). _h+1^m,t=P_m,h (V_h+1^k(t)-V_m,h+1^π^k(t) )(x_h^m,t,a_h^m,t)- (V_h+1^k(t)-V_m,h+1^π^k(t) )(x_h+1^m,t). Lemma D.6. Conditioned on hetC_het, for every agent m∈[M]m∈[M], episode t∈[T]t∈[T], and step h∈[H]h∈[H], δhm,t≤δh+1m,t+ζh+1m,t+2β‖ϕ(xhm,t,ahm,t)‖(Λhk(t))−1+3Hξ. _h^m,t≤ _h+1^m,t+ _h+1^m,t+2β\,\|φ(x_h^m,t,a_h^m,t)\|_( _h^k(t))^-1+3Hξ. Proof of Lemma D.6. Fix m,tm,t. Let k=k(t)k=k(t) be the round index that the t-th episode is in. Since πk(t)π^k(t) is greedy with respect to Qhk(t)Q_h^k(t), Vhk(t)(xhm,t)=Qhk(t)(xhm,t,ahm,t),Vm,hπk(t)(xhm,t)=Qm,hπk(t)(xhm,t,ahm,t).V_h^k(t)(x_h^m,t)=Q_h^k(t)(x_h^m,t,a_h^m,t), V_m,h^π^k(t)(x_h^m,t)=Q_m,h^π^k(t)(x_h^m,t,a_h^m,t). Hence δhm,t=Qhk(t)(xhm,t,ahm,t)−Qm,hπk(t)(xhm,t,ahm,t). _h^m,t=Q_h^k(t)(x_h^m,t,a_h^m,t)-Q_m,h^π^k(t)(x_h^m,t,a_h^m,t). Under the event hetC_het, Lemma D.4 implies δhm,t≤ℙh(Vh+1k(t)−Vm,h+1πk(t))(xhm,t,ahm,t)+2β‖ϕ(xhm,t,ahm,t)‖(Λhk)−1+Hξ. _h^m,t _h (V_h+1^k(t)-V_m,h+1^π^k(t) )(x_h^m,t,a_h^m,t)+2β\,\|φ(x_h^m,t,a_h^m,t)\|_( _h^k)^-1+Hξ. (26) Now compare the reference and local transition operators. For any (x,a)(x,a), ℙh(Vh+1k(t)−Vm,h+1πk(t))(x,a)−ℙm,h(Vh+1k(t)−Vm,h+1πk(t))(x,a) _h (V_h+1^k(t)-V_m,h+1^π^k(t) )(x,a)-P_m,h (V_h+1^k(t)-V_m,h+1^π^k(t) )(x,a) =(ℙh−ℙm,h)Vh+1k(t)(x,a)+(ℙm,h−ℙh)Vm,h+1πk(t)(x,a). = (P_h-P_m,h )V_h+1^k(t)(x,a)+ (P_m,h-P_h )V_m,h+1^π^k(t)(x,a). Since both value functions lie in [0,H][0,H], the right-hand side has upper bound at most 2Hξ2Hξ. Therefore, ℙh(Vh+1k(t)−Vm,h+1πk(t))(xhm,t,ahm,t)≤ℙm,h(Vh+1k(t)−Vm,h+1πk(t))(xhm,t,ahm,t)+2Hξ.P_h (V_h+1^k(t)-V_m,h+1^π^k(t) )(x_h^m,t,a_h^m,t) _m,h (V_h+1^k(t)-V_m,h+1^π^k(t) )(x_h^m,t,a_h^m,t)+2Hξ. Substituting this inequality into (26) gives δhm,t≤ℙm,h(Vh+1k(t)−Vm,h+1πk(t))(xhm,t,ahm,t)+2β‖ϕ(xhm,t,ahm,t)‖(Λhk)−1+3Hξ. _h^m,t _m,h (V_h+1^k(t)-V_m,h+1^π^k(t) )(x_h^m,t,a_h^m,t)+2β\,\|φ(x_h^m,t,a_h^m,t)\|_( _h^k)^-1+3Hξ. The only additional point caused by the lower clipping is the case where the unprojected optimistic score is negative. In this case Qhk(t)=0Q_h^k(t)=0, so δhm,t _h^m,t =−Qm,hπk(t)(xhm,t,ahm,t) =-Q_m,h^π^k(t)(x_h^m,t,a_h^m,t) =−rm,h(xhm,t,ahm,t)−Pm,hVm,h+1πk(t)(xhm,t,ahm,t) =-r_m,h(x_h^m,t,a_h^m,t)-P_m,hV_m,h+1^π^k(t)(x_h^m,t,a_h^m,t) ≤Pm,h(Vh+1k(t)−Vm,h+1πk(t))(xhm,t,ahm,t). ≤ P_m,h (V_h+1^k(t)-V_m,h+1^π^k(t) )(x_h^m,t,a_h^m,t). because rm,h≥0r_m,h≥ 0 and Vh+1k(t)≥0V_h+1^k(t)≥ 0. Hence the same recursion follows, since the bonus term and the heterogeneity error term are nonnegative. Finally, by noting that ℙm,h(Vh+1k(t)−Vm,h+1πk(t))(xhm,t,ahm,t)=[δh+1m,t∣m,t,h]=δh+1m,t+ζh+1m,t,P_m,h (V_h+1^k(t)-V_m,h+1^π^k(t) )(x_h^m,t,a_h^m,t)=E [ _h+1^m,t _m,t,h ]= _h+1^m,t+ _h+1^m,t, we finish the proof of the recursion. ∎ D.2 Proof of Theorem 2 Proof of Theorem 2. We first note that similar to Lemma C.4, the following event ℰhetE_het holds with probability at least 1−p¯1- p: ∑m=1M∑t=1T∑h=1Hζh+1m,t≤8H3MTlog(2p¯). _m=1^M _t=1^T _h=1^H _h+1^m,t≤ 8H^3MT ( 2 p ). (27) Then the event het∩ℰhetC_het _het holds with probability at least 1−2p¯1-2 p. We now prove Theorem 2 under the event het∩ℰhetC_het _het, under which all lemmas in Section D.1 hold. Lemma D.5 with h=1h=1 gives Vm,1⋆(x1m,t)≤V1k(t)(x1m,t)+H2ξ.V_m,1 (x_1^m,t)≤ V_1^k(t)(x_1^m,t)+H^2ξ. Hence Regret(T) (T) =∑m=1M∑t=1T(Vm,1⋆(x1m,t)−Vm,1πk(t)(x1m,t)) = _m=1^M _t=1^T (V_m,1 (x_1^m,t)-V_m,1^π^k(t)(x_1^m,t) ) ≤∑m=1M∑t=1T(V1k(t)(x1m,t)−Vm,1πk(t)(x1m,t))+H2MTξ ≤ _m=1^M _t=1^T (V_1^k(t)(x_1^m,t)-V_m,1^π^k(t)(x_1^m,t) )+H^2MTξ =∑m=1M∑t=1Tδ1m,t+H2MTξ. = _m=1^M _t=1^T _1^m,t+H^2MTξ. (28) Next, summing Lemma D.6 over h=1,…,Hh=1,…,H and using δH+1m,t=0 _H+1^m,t=0 yields δ1m,t≤∑h=1Hζh+1m,t+2β∑h=1H‖ϕ(xhm,t,ahm,t)‖(Λhk(t))−1+3H2ξ. _1^m,t≤ _h=1^H _h+1^m,t+2β _h=1^H\|φ(x_h^m,t,a_h^m,t)\|_( _h^k(t))^-1+3H^2ξ. Summing over all (m,t)(m,t) and regrouping by rounds, ∑m=1M∑t=1Tδ1m,t≤∑m=1M∑t=1T∑h=1Hζh+1m,t+2β∑h=1H∑k=1K∑t=τkτk+1−1∑m=1M‖ϕ(xhm,t,ahm,t)‖(Λhk)−1+3H2MTξ. _m=1^M _t=1^T _1^m,t≤ _m=1^M _t=1^T _h=1^H _h+1^m,t+2β _h=1^H _k=1^K _t= _k _k+1-1 _m=1^M\|φ(x_h^m,t,a_h^m,t)\|_( _h^k)^-1+3H^2MTξ. Therefore, together with (28), we have Regret(T)≤ (T)≤ ∑m=1M∑t=1T∑h=1Hζh+1m,t+2β∑h=1H∑k=1K∑t=τkτk+1−1∑m=1M‖ϕ(xhm,t,ahm,t)‖(Λhk)−1+4H2MTξ. _m=1^M _t=1^T _h=1^H _h+1^m,t+2β _h=1^H _k=1^K _t= _k _k+1-1 _m=1^M\|φ(x_h^m,t,a_h^m,t)\|_( _h^k)^-1+4H^2MTξ. Applying the martingale bound in (27) and Lemma C.5 (which is unchanged because it depends only on the Gram matrices and the synchronization rule) gives Regret(T)≤ (T)≤ 8H3MTlog(4p¯)+4H2MTξ 8H^3MT ( 4 p )+4H^2MTξ +2βH(6dMTlog(1+MTd)+Mdlog3(γlogγ+1)log(1+MTd)). +2β H ( 6dMT (1+ MTd )+ Md 3( γ γ+1)\, (1+ MTd ) ). Substituting β=cβ′Hdlog(1+2dMHTp¯)+2HξdMTβ=c_β Hd (1+ 2dMHT p )+2Hξ dMT and collecting terms yield Regret(T)≤(2cβ′6+42)Md3H4Tlog(1+2dMHTp¯)log(1+MTd) (T)≤\; (2c_β 6+4 2 ) Md^3H^4T\, (1+ 2dMHT p )\, (1+ MTd ) +2cβ′Md2H2log3(γlogγ+1)log(1+2dMHTp¯)log(1+MTd) + 2c_β Md^2H^2 3 ( γ γ+1 )\, (1+ 2dMHT p )\,\, (1+ MTd ) +4(6+1)ξMdH2Tlog(1+MTd)+4ξM3d3H4Tlog3(γlogγ+1)log(1+MTd). +4( 6+1)\,ξ MdH^2T\, (1+ MTd )+ 4ξ M^3d^3H^4T 3\, ( γ γ+1 )\, (1+ MTd ). (29) which is exactly the claimed bound in Theorem 2. ∎ Extending our communication-efficient federated RL guarantees in the misspecified setting to broader heterogeneity and participation models, such as stronger distributional shifts across agents or asynchronous and partial client participation, remains an interesting direction for future work. Appendix E Proof of Theorem 3 Proof of Theorem 3. Fix any α∈(0,γ)α∈(0,γ) and divide the rounds into three classes: Ilong≔k:τk+1−τk>α,I_long \k: _k+1- _k>α\, Ishort,tr≔k:τk+1−τk≤αand round k ends because the determinant trigger fires,I_short,tr \k: _k+1- _k≤α\ and round $k$ ends because the determinant trigger fires \, Ishort,term≔k:τk+1−τk≤αand round k ends only because the hard cap T is reached.I_short,term \k: _k+1- _k≤α\ and round $k$ ends only because the hard cap $T$ is reached \. By definition, these three sets form a partition of [K][K]. Moreover, |Ishort,term|≤1|I_short,term|≤ 1, because only the final round can terminate solely due to the hard stop. Long rounds. For each k∈Ilongk∈ I_long we have τk+1−τk>α _k+1- _k>α. Summing the round lengths and using that the total number of episodes per agent is T gives α|Ilong|≤∑k∈Ilong(τk+1−τk)≤∑k=1K(τk+1−τk)=T,α|I_long|≤ _k∈ I_long( _k+1- _k)≤ _k=1^K( _k+1- _k)=T, so |Ilong|≤Tα.|I_long|≤ Tα. (30) Short rounds that end by a determinant trigger. Fix any k∈Ishort,trk∈ I_short,tr. Then some agent m and some step h satisfy the trigger condition at the end of round k: det(Λhk+Λhm,k,loc)det(Λhk)≥γτk+1−τk≥γα. ( _h^k+ _h^m,k,loc) ( _h^k)≥ γ _k+1- _k≥ γα. Since the global update dominates the single-agent update in the Loewner order, Λhk+1=Λhk+∑m=1MΛhm,k,loc⪰Λhk+Λhm,k,loc, _h^k+1= _h^k+ _m=1^M _h^m,k,loc _h^k+ _h^m,k,loc, and the determinant is monotone over positive semidefinite matrices. Therefore, det(Λhk+1)det(Λhk)≥det(Λhk+Λhm,k,loc)det(Λhk)≥γα. ( _h^k+1) ( _h^k)≥ ( _h^k+ _h^m,k,loc) ( _h^k)≥ γα. For every other step ℓ≠h ≠ h, we still have det(Λℓk+1)/det(Λℓk)≥1 ( _ ^k+1)/ ( _ ^k)≥ 1. Hence ∏ℓ=1Hdet(Λℓk+1)det(Λℓk)≥γα. _ =1^H ( _ ^k+1) ( _ ^k)≥ γα. Multiplying over all k∈Ishort,trk∈ I_short,tr yields (γα)|Ishort,tr|≤∏k∈Ishort,tr∏ℓ=1Hdet(Λℓk+1)det(Λℓk)≤∏ℓ=1Hdet(ΛℓK+1)det(Λℓ1). ( γα )^|I_short,tr|≤ _k∈ I_short,tr _ =1^H ( _ ^k+1) ( _ ^k)≤ _ =1^H ( _ ^K+1) ( _ ^1). (31) By the arithmetic-geometric mean inequality applied to the eigenvalues of λ−1ΛℓK+1λ^-1 _ ^K+1, det(ΛℓK+1)≤λd(tr(ΛℓK+1)λd)d≤λd(1+MTλd)d. ( _ ^K+1)≤λ^d ( tr( _ ^K+1)λ d )^d≤λ^d (1+ MTλ d )^d. (32) The last inequality holds due to the definition in (8) with ‖ϕ(xhm,t,ahm,t)‖2≤1\|φ(x_h^m,t,a_h^m,t)\|_2≤ 1. Since Λℓ1=λId _ ^1=λ I_d, we further obtain det(ΛℓK+1)det(Λℓ1)≤(1+MTλd)d. ( _ ^K+1) ( _ ^1)≤ (1+ MTλ d )^d. Consequently, back to (31), we have |Ishort,tr|≤dHlog(γ/α)log(1+MTλd).|I_short,tr|≤ dH (γ/α) (1+ MTλ d ). (33) Put the three classes together. Combining the previous bounds (30) and (33) gives K=|Ilong|+|Ishort,tr|+|Ishort,term|≤Tα+dHlog(γ/α)log(1+MTλd)+1.K=|I_long|+|I_short,tr|+|I_short,term|≤ Tα+ dH (γ/α) (1+ MTλ d )+1. Choosing α=γ/2α=γ/2 yields the claimed bound K≤1+2Tγ+dHlog2log(1+MTdλ).K≤ 1+ 2Tγ+ dH 2 (1+ MTdλ ). ∎