{"id":"fea5e065-214c-405b-bbe4-dc0cb4042588","arxiv_id":"2411.15014","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"The paper proves that personalized federated temporal-difference learning with a shared linear representation converges at rate O(1/(N^{2/3} T^{2/3})), yielding linear speedup in the number of agents under Markovian noise.","lead":"This paper proposes a personalized federated reinforcement learning framework in which agents share a common feature representation but keep their own policy weights, and proves a convergence guarantee for its temporal-difference instantiation. If the proof is correct, doubling the number of agents cuts the number of communication rounds needed for a target accuracy by half, the first such linear-speedup guarantee for personalized federated RL under Markovian noise.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 4.10's uniform strong-monotonicity is both unproven and incompatible with the paper's own non-uniqueness remark; the O(N^{-2/3}T^{-2/3}) rate rests on it.","rationale":"The reader identified Lemma 4.10 as the weakest point, and my stress-test concurs: the strong-monotonicity constant omega is the pivot of the entire Lyapunov argument. I sharpen the concern by noting that the lemma's global formulation is not merely unproved but internally inconsistent with the paper's acknowledgement of rotational non-uniqueness: at any second equilibrium the required inequality is 0 <= -omega ||Phi' - Phi*_0||^2 < 0. Appendix E.4's convexity argument cannot establish a uniform positive omega, because convexity gives only monotonicity (omega = 0), and hbar(y_i(Phi), Phi) is not the gradient of a fixed convex function in Phi once y_i(Phi) is substituted. The missing omega enters directly in the drift bound of Lemma F.3 and in the final contraction step, so without it the O(N^{-2/3}(T+2)^{-2/3}) rate and the linear-speedup corollary are not established as written. I still do not recommend REJECT: the empirical sections support the qualitative personalization and speedup claims, and the theoretical gap may be repairable by adding strong monotonicity as an explicit local assumption or by proving a local contractivity result around a suitably chosen equilibrium. Since the reader already returned CONDITIONAL with the same root concern, the verdict is unchanged.","tokens_in":50356,"tokens_out":8010,"duration_ms":85426,"concrete_test":"Take a small heterogeneous example exhibiting the claimed rotational symmetry: N = 2 agents, |S| = 3, d = 2, with distinct transition kernels. Compute the mean-field maps gbar_i(theta, Phi) and hbar_i(theta, Phi), solve y_i(Phi) from E[g_i(y_i(Phi), Phi)] = 0, and evaluate R(Phi) = <Phi - Phi*_0, (1/N) sum_i hbar_i(y_i(Phi), Phi)> / ||Phi - Phi*_0||^2 on a grid of Phi near Phi*_0, with rows normalized as in Algorithm 2. If sup over Phi of -R(Phi) has infimum 0, or if a rotated equilibrium Phi' = Phi*_0 Q gives R(Phi') = 0, Lemma 4.10's uniform omega does not exist. Alternatively, compute the minimum eigenvalue of the symmetric part of the Jacobian at Phi*_0 and check whether it is strictly positive uniformly in the number of agents; if not, the claimed contraction is absent.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 4.13 and Corollary 4.15 depend on Lemma 4.10, which asserts a uniform omega > 0 with <Phi - Phi*_0, hbar(y_i(Phi), Phi)> <= -omega ||Phi - Phi*_0||^2 for all Phi (and similarly for gbar). The proof in Appendix E.4 establishes only that the per-argument Hessians are positive semidefinite, i.e. monotonicity with omega = 0; positive coercivity does not follow. More seriously, the statement as written conflicts with the paper's own Remark 4.1: if rotations produce another equilibrium (Phi', theta') with hbar(y_i(Phi'), Phi') = 0 and Phi' != Phi*_0, then the left side is 0 while the right side is -omega ||Phi' - Phi*_0||^2 < 0, so no uniform omega can exist globally. Since hbar(y_i(Phi), Phi) is not the gradient of a single convex function in Phi — y_i(Phi) itself depends on Phi — separate convexity cannot be patched without new structure. The negative drift in Lemma F.3 and the D1 <= omega beta_t step in Appendix F.1.3 use exactly this omega; without it the Lyapunov recursion does not close at the claimed rate. A local version near an isolated equilibrium might suffice, but it is neither stated nor proved.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes PFedRL-Rep, a personalized federated reinforcement learning framework in which agents learn a shared feature representation collaboratively and an agent-specific weight vector locally. The main instantiation, PFedTD-Rep, is analyzed for temporal-difference learning with linear representations; the authors model the coupled local-weight/global-feature updates as a federated two-timescale stochastic approximation under Markovian noise and claim a Lyapunov error bound of order O(1/(N^{2/3}(T+2)^{2/3})), which they interpret as the first linear convergence speedup in the number of agents for personalized FedRL with shared representations. The proof is a Lyapunov drift analysis with a detailed appendix, and the paper includes experiments on CliffWalking, CartPole, Acrobot, and Hopper, plus a direct speedup experiment with duplicated environments.","tokens_in":50628,"tokens_out":12822,"duration_ms":121763,"significance":"If the convergence claim were fully established, the paper would make a valuable contribution: it would provide the first linear speedup guarantee for personalized federated reinforcement learning with shared representations under Markovian noise, and the two-timescale Lyapunov analysis would be of independent interest. The empirical protocol used to verify the speedup, duplicating environments so that cross-environment constants are held fixed, is a thoughtful design. The paper also gives full proof details in the appendix and honestly states that the analysis does not cover control settings. However, the central convergence theorem rests on a strong-monotonicity assertion that is not proved, on a step-size order claim that appears false, and on an analysis that ignores the normalization step present in Algorithm 2. Because these issues are load-bearing for the linear speedup claim, the significance is currently conditional.","major_comments":[{"comment":"Lemma 4.10 asserts a uniform omega > 0 such that <Phi - Phi*_0, hbar(y_i(Phi), Phi)> <= -omega ||Phi - Phi*_0||^2 for all Phi, and a corresponding inequality for gbar. The proof in Appendix E.4 only establishes that the TD loss is convex separately in Phi(s) with theta fixed and in theta with Phi fixed; convexity gives monotonicity with omega = 0, not the uniform coercivity used in Lemma F.3 and in the contraction step. Moreover, hbar(y_i(Phi), Phi) is not the gradient of a single convex function in Phi because y_i(Phi) itself depends on Phi, so separate convexity does not imply the displayed inequality. The statement also conflicts with Remark 4.1: if rotations produce another equilibrium (Phi', theta') with hbar(y_i(Phi'), Phi') = 0 and Phi' != Phi*_0, then the left-hand side is 0 while the right-hand side is -omega ||Phi' - Phi*_0||^2 < 0, so no uniform global omega can exist. A local version near an isolated equilibrium would require new assumptions and a basin-of-attraction argument; neither is supplied.","section":"Section 4.2, Lemma 4.10 and Appendix E.4"},{"comment":"The proof states that D1 is o(beta_t) and D2 is o(alpha_{t+1}), so that D1 <= omega beta_t and D2 <= K omega alpha_{t+1}. But D1 contains the term beta_t L / alpha_t. With alpha_t = alpha_0/(t+2)^{5/6} and beta_t = beta_0/(t+2), we have beta_t L / alpha_t = (beta_0 L / alpha_0)(t+2)^{-1/6}, while beta_t = beta_0/(t+2). The ratio (beta_t L / alpha_t) / beta_t = (L/alpha_0)(t+2)^{5/6} tends to infinity, so D1 is not o(beta_t). Consequently the inequality D1 <= omega beta_t and the contraction M({theta^i_{t+2}}, Phi_{t+1}) <= (1 - omega beta_t) M({theta^i_{t+1}}, Phi_t) in (54) are not justified. The Lyapunov recursion therefore does not close at the claimed rate with the stated step sizes unless additional conditions or a different weighting are introduced.","section":"Appendix F.1.3, Eqs. (52)-(54)"},{"comment":"Algorithm 2 normalizes each local feature update before averaging (line 11) and initializes feature rows as unit-norm vectors, but the theoretical update analyzed in Eqs. (9)-(11) is Phi_{t+1} = Phi_t + beta_t (1/N) sum_i h(theta^i_{t+1}, Phi_t, ...) with no normalization. The proof never accounts for the normalization step. Since normalization is a nonlinear map that changes the mean-field direction and can affect the Lipschitz and strong-monotonicity properties used in Lemmas 4.6-4.10, Theorem 4.13 as written applies to a different algorithm from the one implemented and simulated. The paper should either remove normalization from Algorithm 2, prove that the normalization is asymptotically negligible under the paper's assumptions, or incorporate a projection step into the analysis.","section":"Algorithm 2 and Section 4.1, Eqs. (9)-(11)"},{"comment":"Corollary 4.15 states only beta_0 = o(N^{-2/3}) and T^2 > N, but the proof in Appendix F.2 begins 'If alpha_0 = beta_0 = o(N^{-1/3} K^{-1/2})' and relies on that additional condition to suppress the alpha_0^2 K^2 terms in C1. Without an N-dependent condition on alpha_0 (or on the constants K, B, L), the term 2 alpha_0^2 (3 K^2 B^2 + 3 K^2 delta^2 + 2 L^2 K^2 B^2) (T+2)^{-2/3} in (16) is an O(T^{-2/3}) error that is independent of N and dominates, so the N^{-2/3} speedup does not follow. The hypotheses stated in Corollary 4.15 do not imply the claimed bound.","section":"Corollary 4.15 and Appendix F.2"}],"minor_comments":[{"comment":"The second inequality in Lemma 4.10 has mismatched variables: the left-hand side uses theta^i_t and Phi_{t-1}, while the right-hand side uses arbitrary theta and y_i(Phi). The statement should be written uniformly for a single pair (theta, Phi).","section":"Lemma 4.10"},{"comment":"The mixing time tau_delta is defined before the Lipschitz constants L_g and L_h are introduced, and Lemma 4.12 later defines L1 in terms of L_g, L_h, and the steady-state gradients. Reordering these definitions would improve readability.","section":"Definition 4.5 and Lemma 4.12"},{"comment":"The theorem writes M({theta^i_{T+2}}, Phi_{T+1}) on the left but bounds it in terms of M({theta^i_1}, Phi_0); using a consistent time subscript, for example t and t+1, would avoid confusion.","section":"Theorem 4.13, Eq. (16)"},{"comment":"The proof first observes that the norm-scaling step gives ||y_i(Phi_1) - y_i(Phi_2)|| <= 2B and then asserts the existence of Ly such that the Lipschitz bound holds. This is only immediate on a bounded parameter domain; the compactness assumption or a direct argument from the implicit function theorem should be stated.","section":"Appendix E.3, proof of Lemma 4.8"}],"recommendation":"major_revision","confidential_remarks":"To the editor: the paper is within scope and the main idea is attractive, but I cannot certify the linear speedup claim in its current form. The strong-monotonicity lemma, the step-size order claim in Appendix F.1.3, the normalization mismatch, and the missing alpha_0 condition in Corollary 4.15 are all load-bearing. I see no circularity problem: the authors' related DepRL paper is used for motivation only, and the convergence proof does not fit constants to data. The issues are technical and potentially repairable within the paper's scope, so I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my read. The genuinely new thing is the first finite-time linear speedup guarantee for personalized federated RL with shared representations under Markovian noise. That is a meaningful step for the FedRL subfield, and the machinery—casting PFedTD-Rep as a federated two-timescale stochastic approximation and using a Lyapunov drift with a mixing-time argument—is a sensible way to get there. The experiments, including the duplicated-environment speedup check in Appendix G.2, support the qualitative claims, and the limitations paragraph is honest about the control extension. No code, but for a theory paper that is not a blocker.\n\nThe soft spot is load-bearing. Lemma 4.10 asserts a uniform strong-monotonicity constant omega for the mean-field hbar and gbar. The proof in Appendix E.4 only shows the TD loss is convex in each argument separately, which gives monotonicity with omega=0, not the uniform coercivity needed to make the Lyapunov drift negative. Worse, the statement as written conflicts with Remark 4.1: if rotations give another equilibrium Phi', then hbar(y_i(Phi'),Phi') = 0, and the inequality becomes 0 <= -omega ||Phi'-Phi*_0||^2 < 0. No global uniform omega can exist. The negative drift in Lemma F.3 and the D1 <= omega beta_t step in F.1.3 use exactly this omega, so the O(T^{-2/3}) rate and Corollary 4.15 do not close as written. A local version near an isolated equilibrium might rescue the claim, but it is neither stated nor proved. This is a fixable gap—state omega as an explicit local assumption or prove it under a non-degeneracy condition—but it is not a cosmetic one.\n\nTwo smaller issues: Algorithm 2 normalizes Phi locally, but the analysis tracks the unnormalized update; and Lemma 4.8's proof asserts the Lipschitz constant Ly rather than deriving it. The second is minor; the first means the analyzed update does not exactly match the implemented one, which the authors should reconcile.\n\nWho should read this: anyone working on federated RL theory or representation learning in RL. It deserves a serious referee because the claim is important and the gap is addressable. I would not personally cite the linear speedup result until the lemma is fixed, but I would bring the paper to our reading group to pick at the proof structure.","headline":"First linear speedup claim for personalized FedRL with shared representations, but the rate rests on an unproven strong-monotonicity lemma that contradicts the paper's own non-uniqueness remark.","tokens_in":51160,"tokens_out":2357,"would_cite":false,"duration_ms":22874,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32","68T05"],"pacs":[],"model":"deepseek-v4-flash","headline":"A personalized federated RL algorithm achieves linear speedup with more agents, under Markovian noise.","keywords":["personalized federated reinforcement learning","shared representation learning","linear convergence speedup","two-timescale stochastic approximation","Markovian noise","temporal difference learning","linear function approximation","heterogeneous environments"],"falsifier":"Run PFedTD-Rep in a finite MDP with a linear representation where the mean-field feature update can be computed exactly, and measure the Lyapunov drift in (14) directly. If the empirical drift is not consistently negative across the parameter region, or if the convergence time in communication rounds does not decrease roughly as $1/N$ when duplicating environments, the claimed linear speedup would be contradicted.","tokens_in":50101,"feed_emoji":"🤖","tokens_out":4458,"duration_ms":33037,"temperature":0.7,"pith_summary":"This paper introduces a personalized federated reinforcement learning framework in which agents in heterogeneous environments share a common feature representation while keeping agent-specific weights. It proves that a temporal-difference instantiation, PFedTD-Rep, converges at a rate that improves linearly as the number of agents grows, despite the non-i.i.d., Markovian data that each agent collects. This is the claimed first linear speedup for personalized federated RL with shared representations. The framework also extends to control, with experiments on DQN-based variants showing faster learning in heterogeneous settings and better generalization to new environments.","feed_headline":"Personalized federated RL proves linear speedup with agents","feed_subtitle":"A shared-representation TD method converges faster as agents join, under real Markovian noise.","key_machinery":"The central object is the weighted Lyapunov function $M(\\{\\theta^i_{t+1}, \\forall i\\}, \\Phi_t) := \\|\\Phi_t - \\Phi^*\\|^2 + \\frac{\\beta_{t-1}}{\\alpha_t}\\frac{1}{N}\\sum_{i=1}^N \\|\\theta^i_{t+1} - y_i(\\Phi_t)\\|^2$, which couples the slow feature iterate $\\Phi_t$ and the fast local weight iterates $\\theta^i_{t+1}$ through the mapping $y_i(\\Phi)$ that gives the optimal weight for a fixed representation. Its drift is decomposed into separate terms for the representation update and the weight update, bound using Lipschitz continuity of the TD gradients, the mixing time of the Markov chains, and a strong monotonicity condition on the mean-field updates. Choosing the step sizes $\\alpha_t = \\alpha_0/(t+2)^{5/6}$ and $\\beta_t = \\beta_0/(t+2)$ makes the drift contractive and yields the $O(T^{-2/3})$ rate after telescoping.","core_discovery":"PFedTD-Rep is cast as a federated nonlinear two-timescale stochastic approximation with Markovian noise, where local weight vectors update on a fast timescale and the shared feature representation updates on a slow timescale. The paper's central bound, Theorem 4.13, shows the Lyapunov error $M$ decays as $\\tilde{O}\\big(N^{-2/3}(T+2)^{-2/3}\\big)$ when $\\alpha_t = \\alpha_0/(t+2)^{5/6}$, $\\beta_t = \\beta_0/(t+2)$, $\\beta_0 = o(N^{-2/3})$ and $T^2 > N$. Reaching $\\epsilon$ accuracy then requires $T = O(N^{-1}\\epsilon^{-3/2})$ communication rounds, which is a linear convergence speedup in the number of agents. The proof uses a weighted Lyapunov function that couples the representation error with the average local-weight error, and leverages Markov chain mixing time to control the bias from Markovian samples.","pith_inferences":["The linear speedup result relies on the strong monotonicity assumption of Lemma 4.10; if that assumption fails for the feature update, the rate may degrade, so a useful extension would be to verify or replace the uniform coercivity condition with a weaker geometric condition.","The theory is proved for linear representations and TD; a natural testable extension is whether the same two-timescale Lyapunov argument can be carried to nonlinear function approximation or to Q-learning, where the update is not linear in the representation.","The empirical speedup experiment duplicates environments to keep cross-environment parameters fixed, so a tighter practical test would vary environment diversity while measuring the constant in the rate, to see when the speedup degrades.","The framework suggests a general recipe for personalized federated learning in Markovian settings: share a slow-timescale representation and personalize fast weights, which could be applied to policy-gradient methods with a similar drift analysis."],"forward_implications":["If correct, PFedTD-Rep is the first algorithm for personalized federated RL with shared representations that provably achieves linear convergence speedup in the number of agents under Markovian noise.","The framework generalizes beyond TD: the same two-timescale shared-representation design applies to Q-learning and DQN variants, and experiments indicate faster convergence and better generalization in control tasks.","The result implies that adding more agents proportionally reduces the number of communication rounds needed for a target accuracy, making massive parallelism beneficial in heterogeneous settings.","The convergence rate matches the best-known rate for nonlinear two-timescale stochastic approximation under i.i.d. noise, even though the federated Markovian setting is more challenging.","The analysis shows that multiple local weight updates do not hurt global convergence when learning rates are chosen appropriately, similar to the supervised federated learning setting."],"supporting_citations":[{"why":"Provides the FedTD/FedQ baseline with linear speedup under Markovian sampling in homogeneous settings that this work extends to heterogeneous personalized settings.","marker":"Khodadadian et al., 2022"},{"why":"Analyzes federated TD over erasure channels with Markovian sampling and linear speedup, providing techniques and bounds for mixing-time-based analysis reused in the drift proof.","marker":"Dal Fabbro et al., 2023"},{"why":"Analyzes federated TD with linear function approximation under environmental heterogeneity, the closest precursor without personalization or shared representation learning.","marker":"Wang et al., 2023a"},{"why":"Supplies the finite-time analysis framework for nonlinear two-timescale stochastic approximation under i.i.d. noise that the paper extends to the federated Markovian setting.","marker":"Doan, 2020"},{"why":"Extends nonlinear two-timescale stochastic approximation to Markovian noise with monotone mean fields, the direct theoretical foundation for the Lyapunov drift approach.","marker":"Doan, 2021"},{"why":"Provides the Lyapunov drift technique for single-timescale TD learning under Markovian noise that is adapted to handle the coupled two-timescale updates.","marker":"Srikant & Ying, 2019"},{"why":"Establishes the shared-representation personalization model in supervised federated learning that this paper transfers to the RL setting.","marker":"Collins et al., 2021"},{"why":"Introduces environment heterogeneity in federated RL and the PerDQNAvg heuristic baseline used in the control experiments.","marker":"Jin et al., 2022"},{"why":"Provides a heterogeneous federated Q-learning baseline with linear speedup but without personalization, used as a comparison and motivation.","marker":"Woo et al., 2023"},{"why":"Establishes the unique fixed point of TD with linear function approximation for a fixed representation, justifying the mapping $y_i(\\Phi)$ used in the Lyapunov function.","marker":"Tsitsiklis & Van Roy, 1996"}],"fun_headline_variants":["Personalized FedRL proves linear speedup with agents","Shared representations enable linear speedup in federated RL","Linear speedup proven for personalized federated RL","First linear speedup result for federated reinforcement learning","PFedTD-Rep achieves linear speedup in number of agents"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof assumes there is a uniform positive constant $\\omega$ such that the mean-field TD updates are strongly monotone in both the representation and the local weights; if that uniform coercivity does not actually hold for the feature update, the contractions that produce the $O(T^{-2/3})$ rate are not guaranteed.","fun_headline_variants_meta":{"raw":{"variants":["Personalized FedRL proves linear speedup with agents","Shared representations enable linear speedup in federated RL","Linear speedup proven for personalized federated RL","First linear speedup result for federated reinforcement learning","PFedTD-Rep achieves linear speedup in number of agents"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00016,"raw_usage":{"total_tokens":1260,"prompt_tokens":1002,"completion_tokens":258,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":618,"completion_tokens_details":{"reasoning_tokens":180}},"tokens_in":618,"tokens_out":258,"duration_ms":2999,"temperature":1.0,"reasoning_tokens":180,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T14:37:00.956864+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run PFedTD-Rep in a finite MDP with a linear representation where the mean-field feature update can be computed exactly, and measure the Lyapunov drift in (14) directly. If the empirical drift is not consistently negative across the parameter region, or if the convergence time in communication rounds does not decrease roughly as $1/N$ when duplicating environments, the claimed linear speedup would be contradicted.","supporting_citations":[],"review_version":1}