We study federated reinforcement learning in which multiple agents interact with a common Markov decision process and communicate through a central server to collaboratively learn the optimal state-action value function. Our goal is to understand whether the sample-efficiency benefits of collaboration can be retained when a fraction of the agents behave adversarially and transmit arbitrarily corrupted information. To address this problem, we introduce Robust Async-Fed-Q, an epoch-based federated learning algorithm that combines variance-reduced estimation of the Bellman optimality operator at the agents with robust aggregation at the server. We establish high-probability finite-time guarantees showing that the proposed method preserves the statistical gains of collaboration among the honest agents while tolerating adversarial corruption. In particular, the effect of the adversarial agents decreases as the amount of data collected by each honest agent grows and eventually vanishes in the infinite-sample limit. We complement these guarantees with information-theoretic lower bounds that characterize the unavoidable statistical cost of adversarial corruption, leading to the first nearly matching upper and lower bounds for adversarially robust federated reinforcement learning. We further extend our framework to accommodate single-trajectory Markovian sampling and heterogeneous partial coverage, where different agents may explore different regions of the state-action space and learning relies on their collective coverage. Finally, our epoch-based design substantially improves the best known communication complexity for federated Q-learning under asynchronous sampling.
Figures & tables
Figure 1: (Upper Left) Asynchronous federated Q -learning with standard averaging under varying corruption fractions ε∈{0.001,0.01,0.1,0.2} and a fixed number of agents N=2000 , where each corrupted agent adds a bias of magnitude 104 to its messages. (Upper Right) Robust Async-Fed-Q under the same values of ε and with N=2000 . (Lower Left) Federated Q -learning with standard averaging for N∈{100,500,1000} , with a fixed number of corrupted agents ∣B∣=25 , each introducing a bias of magnitude 103 . (Lower Right) Robust Async-Fed-Q under the same fixed-corruption setting ∣B∣=25 . The results demonstrate that the standard-averaging baseline is highly sensitive to corrupted messages, whereas our proposed algorithm remains stable, converges to a neighborhood of Q⋆ , and achieves lower estimation error as the number of agents increases, demonstrating clear collaborative gains.
Figure 2: Performance of Robust Async-Fed-Q under partial coverage ({\color[rgb]{0.8,0,0}\texttt{S}_{2}}) . (Left) The error Ek for H∈{1000,5000,10000,20000} , with N=500 total agents and N=100 agents covering each state-action pair. (Right) The error for N∈{250,500,1000,2000} , corresponding to N∈{50,100,200,400} , with H=4000 . In both panels, ε=0.02 , corrupted messages are replaced by −106 , and the reward-noise variance is σ2=5 .
Figure 3: (Upper Left) Convergence of Robust Async-Fed-Q for different corruption fractions ε∈{0,0.001,0.0025,0.005,0.01} . (Upper Right) Performance of standard arithmetic-mean aggregation under the same corruption levels. (Lower Left) Performance under negative-outlier, sign-flip, dispersion-shift, and adaptive-sign attacks. (Lower Right) Terminal error as a function of the reward-noise standard deviation σ .
Figure 4: Collaboration ablations under full coverage ( S1 ). (Left) Evolution of the worst-agent error for different network sizes at a fixed positive corruption fraction, showing that larger networks converge to lower error levels despite corrupted messages. (Middle) Terminal error as a function of N for several corruption fractions, together with the O(1/N) reference slope. The error decreases with N throughout the corruption sweep, demonstrating that the collaboration benefit persists under corruption. (Right) Evolution of the error as N varies while the absolute number of corrupted agents is held fixed. In this setting, increasing N adds honest agents and reduces the realized corruption fraction, leading to a progressively lower error floor.
Figure 5: Sample-size ablations under full coverage ( S1 ). (Left) Convergence under corruption for H∈{500,1000,4000,16000,64000} . (Right) Terminal error versus the total sample budget T for different corruption fractions, together with the O(1/T) reference curve.
Figure 6: Ablations under partial coverage ( S2 ). (Upper Left) Clean convergence for different minimum source-set sizes N . (Upper Right) Convergence under corruption for the same values of N . (Lower Left) Dependence on the per-epoch sample budget H . (Lower Right) Terminal error as a function of the minimum positive source visitation probability Λmin , together with the O(1/Λmin) reference curve.
Figure 7: (Left) Terminal error versus the minimum source-set size N in the clean and corrupted partial-coverage settings, together with the O(N−1/2)) reference curve. (Right) Terminal error versus the number of epochs K for three fixed total sample budgets T .
Figure 8: Markovian-data experiments under full coverage ( S1 ). (Left) Convergence against the retained transition count Tused , comparing IID data with continuous Markov trajectories using τ∈{1,4,τth} . (Middle) Terminal error as a function of τ at the fixed physical budget Traw=8400 . (Right) Collaboration benefit for N∈{1600,2400,3200,4800} under the same Markovian sampling and corruption setting.
Figure 9: Retained-sample and physical-sample views of the Markovian-data experiment under full coverage ( S1 ). (Left) Terminal error versus Tused=K(H/τ) for IID observations and Markov trajectories with τ∈{1,4,τth} . (Right) Terminal error versus the physical budget Traw=KH for IID observations and theoretically thinned Markov trajectories. The dashed black curves are vertically rescaled inverse-square-root slope guides.
Figure 10: Results on CliffWalking-v0 under full coverage ( S1 ). (Upper Left) Collaboration benefit at the fixed corruption level ε=0.0025 as the number of agents varies over N∈{1600,2400,3200,4800} . The dashed black curve represents the vertically rescaled O(1/N) reference slope. (Upper Right) Corruption sensitivity at the fixed network size N=3200 as the corruption level varies over ε∈{0,0.001,0.0025,0.005,0.01} . (Lower Left) Terminal worst-agent error as a function of N , with one curve for each corruption level. (Lower Right) Terminal worst-agent error as a function of ε , with one curve for each network size. Increasing N consistently reduces the error, while increasing ε raises the error envelope. The collaboration-induced decay remains visible at every tested corruption level.
Figure 11: Results on FrozenLake-v1 under full coverage ( S1 ). (Upper Left) Collaboration benefit at the fixed corruption level ε=0.0025 as the number of agents varies over N∈{1600,2400,3200,4800} , together with the vertically rescaled O(1/N) reference slope. (Upper Right) Corruption sensitivity at the fixed network size N=3200 as ε∈{0,0.001,0.0025,0.005,0.01} . (Lower Left) Terminal worst-agent error as a function of N , with one curve for each tested corruption level. (Lower Right) Terminal worst-agent error as a function of ε , with one curve for each N . The error decreases with N throughout the corruption sweep, showing that additional collaboration offsets a substantial portion of the corruption-induced degradation.
Figure 12: Results on Taxi-v3 under full coverage ( S1 ). (Left) Collaboration benefit at the fixed corruption level ε=0.0025 as the number of agents varies over N∈{1600,2400,3200,4800} , together with the vertically rescaled O(1/N) reference slope. (Middle) Terminal worst-agent error as a function of N , with one curve for each corruption level. Every curve decreases as the number of agents increases, demonstrating that collaboration remains beneficial under corruption. (Right) Terminal worst-agent error as a function of ε , with one curve for each network size.
Figure 13: Results on Blackjack-v1 under full coverage ( S1 ). (Left) Terminal error as a function of the number of agents N∈{1600,2400,3200,4800} , with one curve for each corruption level ε∈{0,0.001,0.0025,0.005,0.01} . (Middle) Collaboration benefit at the fixed corruption level ε=0.0025 , together with the O(1/N) reference curve. (Right) Terminal error as a function of ε , with one curve for each network size N . The results show that increasing the number of agents initially reduces the terminal error, after which the error approaches an environment-dependent floor. Increasing the corruption level consistently raises the terminal error across the tested network sizes.
We consider a federated reinforcement learning setting involving M agents, all of whom interact with a common Markov Decision Process (MDP). The agents exchange information via a central server to learn the optimal value function. Our goal is to understand to what extent one can hope for collaborative sample-complexity speedups in such a setting, when a small fraction of the agents are adversarial and can act arbitrarily. To that end, we propose Robust Fed-Q}, a federated Q-learning algorithm that blends ideas from both model-based and model-free RL, along with the median-of-means device from robust statistics. We prove that despite corruption, with high-probability, Robust Fed-Q (i) guarantees exact convergence to the optimal value function in the limit of infinite samples, and (ii) enjoys near-optimal finite-time rates that benefit from collaboration. In addition, our approach requires just O~(1) rounds of communication to achieve each of the above guarantees, a feature of independent interest in FL where communication is the major bottleneck.
Sreejeet Maity, Aritra Mitra
Department of Electrical and Computer Engineering, North Carolina State University
Motivated by reinforcement learning in harsh environments, we consider the problem of learning an optimal policy subject to adversarially corrupted feedback. Specifically, at each time-step, an adversary can perturb both the reward and state observations of the learner following the Huber contamination model. To defend against such data corruption, we propose BR-Async-Q: a novel, epoch-based, robust Q-learning algorithm built upon two key ideas: (i) partitioning the online data stream into batches to reduce variance, and (ii) constructing robust estimates of the Bellman optimality operator using such batched data. We prove a high-probability ℓ∞ error bound for BR-Async-Q that matches that for vanilla Q-learning, up to a small additive term that scales with the fraction of corrupted samples. To our knowledge, this provides the first robustness guarantee for asynchronous Q-learning subject to both reward and state corruption. Furthermore, when only rewards are corrupted, the dependence of our algorithm's bound on the corruption fraction is minimax optimal.
Sreejeet Maity, Aritra Mitra
Department of Electrical and Computer Engineering, North Carolina State University.
Federated reinforcement learning enables decentralized agents to collaboratively improve policies or value estimates without exchanging raw trajectories. However, FedAvg-style parameter averaging is not function-space consistent: when clients use heterogeneous encoders or even identical nonlinear networks, averaged parameters need not correspond to the weighted average of client value functions in any common function space. We propose FedQHD, a federated Q-learning method using hyperdimensional (random-feature) state encoders with a linear readout, so that Q-functions are nonlinear in state yet linear in trainable parameters. This linear structure enables closed-form aggregation. With a shared encoder, the function-space consensus update coincides exactly with weighted averaging of local readout matrices. With heterogeneous encoders, the server constructs a global teacher by averaging client Q-values on a shared anchor-state set, and each client compiles this teacher into its local representation via a single ridge projection. We formalize the federation gap -- the error incurred when compiling a federated teacher into a heterogeneous client representation -- relative to a client-specific oracle projection. We show that this gap decomposes into subspace misalignment, anchor-set conditioning, and regularization bias. We further identify the anchor-to-dimension ratio m≥Di as the well-conditioned regime in which the gap reduces to a multiple of the encoder heterogeneity floor. On four continuous-state, discrete-action control benchmarks, FedQHD matches or outperforms FedAvg-style baselines and distillation-based alternatives while requiring substantially less computation, and the empirical dependence of the federation gap on encoder dimension matches our theoretical analysis.
Yuchen Hou, Yongshan Chen, Zhuowen Zou +4
Northeastern University · University of California, Irvine · The George Washington University