Adversarially Robust Federated Q-Learning: Learning Optimal Policies from Unreliable Trajectories

Federated reinforcement learning is emerging as an important paradigm for multi-agent collaborative training — multiple agents interact with the same Markov Decision Process (MDP), exchange information through a central server, and jointly learn an optimal state-action value function. But a fundamental challenge arises in practice: if some agents are malicious and deliberately upload corrupted or entirely fabricated data, can the sample efficiency advantages of collaborative training still be preserved?

A study published on arXiv (arXiv:2610.06918v1) directly addresses this question, proposing an algorithm called Robust Async-Fed-Q that establishes the theoretical foundations for adversarially robust federated Q-learning.

Background: The Fragility of Collaborative Learning

The core appeal of federated learning lies in distributing the sampling cost. Each agent only needs to explore part of the environment; through server-side aggregation, the collective system can approximate the optimal policy with far fewer samples per agent. This statistical gain is the fundamental source of value in federated reinforcement learning.

However, this gain rests on an implicit assumption: all participants are honest. Once some agents are compromised or inherently malicious, they can send arbitrarily corrupted information to the server — not random noise, but adversarially constructed malicious data. Naive averaging aggregation is easily defeated in this scenario; a small number of malicious nodes can steer the entire training process away from the optimal solution.

The core research question becomes clear: when some agents behave adversarially, can honest agents still retain the sample efficiency benefits of collaboration?

The Design of Robust Async-Fed-Q

The algorithm proposed in the paper adopts an epoch-based federated learning framework, with key innovations at two levels:

Agent Side: Variance-Reduced Bellman Estimation

Locally on each agent, the algorithm applies variance-reduced estimation to the Bellman optimality operator. Variance reduction is a classic technique in reinforcement learning for improving sample efficiency — it stabilizes value function updates at each step and reduces fluctuations caused by single-sample randomness. In the federated setting, this step provides more reliable inputs for the subsequent robust aggregation.

Variance reduction techniques have a well-established lineage in stochastic optimization, with representative methods including SVRG and SARAH. The core idea is to maintain a "reference gradient" (or reference estimate), using periodic full-batch estimates to correct the bias in current stochastic estimates, thereby keeping variance at a controllable level. In reinforcement learning, estimating the Bellman operator naturally carries dual stochasticity: the sampling randomness of the current state-action pair, and the transition randomness of the next state. Directly updating Q-values with single-step Monte Carlo samples typically yields extremely high variance and slow convergence. Variance-reduced estimation periodically constructs a low-variance "baseline Q-value" and uses it as an anchor to correct stochastic errors during each local update round. This property is especially critical in the federated setting: each agent uploads to the server not a high-noise single-step estimate, but a variance-compressed stable signal. This enables the robust aggregation algorithm to more accurately distinguish "normal fluctuations" from "adversarial corruption," thereby improving overall robustness.

Server Side: Robust Aggregation

At the central server, the algorithm replaces naive averaging with robust aggregation. The core of robust aggregation is identifying and suppressing abnormal uploads that deviate from the normal distribution, thereby weakening the influence of malicious agents. This agent-server co-design is the key to the method's ability to resist adversarial corruption.

Robust aggregation is the central tool for defending against Byzantine failures and has been extensively studied in the federated learning literature. Common methods include coordinate-wise median, trimmed mean, Krum, and its variants. The shared logic of these methods is to abandon arithmetic averaging over all uploaded values, instead selecting or constructing a statistic that is insensitive to extreme outliers. In trimmed mean, for example, the server sorts each coordinate separately, removes a certain proportion of the highest and lowest values, and then computes the mean — bounding the bias that malicious nodes can inject. The theoretical guarantees of robust aggregation typically rely on a key assumption: the proportion of malicious nodes is below some threshold (e.g., no more than half the total nodes). In this paper's framework, robust aggregation is not used in isolation but works in tandem with variance-reduced estimation — the latter compresses the variance of honest agents' uploads, making the statistical characteristics of malicious uploads easier for anomaly detection logic to identify. The two mechanisms form a complementary defense.

Theoretical Guarantees: First Near-Matching Upper and Lower Bounds

The most noteworthy contribution of this work is theoretical. The authors establish high-probability finite-time guarantees, proving several key results:

• The collaborative statistical gains among honest agents are preserved;
• The negative influence of adversarial agents diminishes as the amount of data collected by each honest agent grows;
• In the infinite-sample limit, the adversarial influence vanishes entirely.

In other words, malicious nodes cannot indefinitely corrupt the learning process — as long as honest agents accumulate sufficient data, the cost of contamination is progressively diluted.

Going further, the paper establishes information-theoretic lower bounds that characterize the unavoidable statistical cost imposed by adversarial corruption. The near-matching of upper and lower bounds represents the first nearly tight upper-lower bound result in adversarially robust federated reinforcement learning, marking a milestone in theoretical completeness.

Lower bound construction typically employs hypothesis testing reductions: two hard-to-distinguish problem instances are constructed, and it is shown that any algorithm that performs well on one instance must incur a specific cost on the other. In the adversarially robust learning context, the lower bound characterizes the statistical loss that even the optimal algorithm cannot avoid — determined jointly by the proportion of malicious nodes, the size of the state-action space, and the sample count. When the upper bound (the error actually achieved by the algorithm) and the lower bound (the theoretically optimal error) match in order of magnitude, the result is called "near-matching," meaning the algorithm is optimal up to constant factors with no room for order-of-magnitude improvement. This paper establishes such a matching for the first time in adversarially robust federated Q-learning. The significance is twofold: it proves not only that Robust Async-Fed-Q is effective, but that it is essentially optimal in statistical efficiency, setting a theoretical benchmark for future research.

Framework Extensions: More Realistic Sampling Scenarios

Theoretical analysis often rests on idealized assumptions, and this work extends in two more realistic directions:

Single-trajectory Markovian sampling: Real agents typically do not sample in an i.i.d. fashion but instead continuously explore along a Markov trajectory, with correlations between samples. The algorithm framework accommodates this more practical sampling regime.

Heterogeneous partial coverage: Different agents may explore different regions of the state-action space, with no single agent capable of covering the whole space — learning relies on their collective coverage. This is precisely the value of federated collaboration: assembling a complete knowledge map through a division of labor.

The analytical challenge under single-trajectory Markovian sampling is that temporal dependencies between samples break the independence assumption, making classical concentration inequalities no longer directly applicable. The standard tool for handling this is mixing time — the number of steps required for a Markov chain to converge from an arbitrary initial distribution to its stationary distribution. The longer the mixing time, the stronger the correlation between adjacent samples and the fewer effectively independent samples, requiring an additional sample cost proportional to the mixing time in the analysis. Heterogeneous partial coverage introduces another core concept: the collective coverage coefficient, which characterizes the proportion of state-action pairs jointly explored by all honest agents relative to the global state-action space. An individual agent's local coverage may be poor, but as long as collective coverage is sufficient, federated collaboration can fill individual blind spots. Together, these two extensions broaden the algorithm's applicability from idealized i.i.d. settings to scenarios more aligned with real deployment conditions.

Communication Efficiency Improvements

Beyond robustness and theoretical guarantees, the epoch-based design also delivers practical value: it significantly improves the best-known communication complexity of federated Q-learning under asynchronous sampling. Communication overhead has long been a bottleneck for deploying federated learning in practice, and this improvement makes the method more feasible to implement in engineering settings.

Significance and Impact

This research unifies two core concerns of federated reinforcement learning — robustness and efficiency — within a single algorithmic framework, backed by rigorous theoretical proofs. It answers not only the question of "can malicious nodes be defended against," but the deeper question of "at what cost can they be defended against."

For scenarios requiring multi-agent learning systems to be deployed in untrusted, distributed environments — such as cross-institutional collaboration and joint training on edge devices — algorithms with adversarial robustness provide crucial theoretical support. As federated learning moves toward more open deployment environments with increasingly complex participants, learning reliable policies in the presence of unreliable collaborators will remain a persistently important research direction.