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

1 Introduction

• Robust Async-Fed-Q batches data into epochs to estimate the Bellman optimality operator with reduced variance, robustly aggregates estimates, and updates the Q-table once per epoch.This design uses asynchronous data to make synchronous updates to the entire Q-table.Source: §1 · p. 3
• With i.i.d. sampling, the high-probability error bound has terms scaling as 1/√(λminNT) and ε/√(λminT), with corruption bias vanishing as T grows.When ε = 0, the bound is order-optimal in λmin, N, and T and gives a linear speedup with N.Source: §1 · pp. 3–4
• An information-theoretic lower bound establishes the unavoidable cost of adversarial corruption, and the paper describes its upper and lower bounds as nearly matching.The lower-bound contribution addresses a gap in robust federated reinforcement learning.Source: §1 · p. 4
• The framework extends to single-trajectory Markovian sampling and partial coverage, where informative source agents and redundancy conditions yield finite-time rates analogous to full coverage.The Markovian extension uses a coupling argument.Source: §1 · p. 4
• Communication costs are logarithmic in both N and T, unlike prior asynchronous FRL costs that scale linearly with T or N.The paper notes that both quantities can be large in distributed learning.Source: §1 · p. 4
• Prior robust multi-agent TD/Q-learning work provides only asymptotic guarantees, while the cited robust policy-gradient work lacks global optimality, linear speedup, Markov sampling, partial coverage, and lower bounds.The paper also extends a preliminary version beyond i.i.d. synchronous sampling.Source: §1 · p. 4

2 Background and Problem Formulation

• Agents interact with a common MDP and share statistical summaries through a server, rather than raw trajectories, to estimate the optimal Q-function.The MDP has finite state and action spaces, stochastic rewards, and a discounted infinite horizon.Source: §2 · p. 5
• Under full coverage, each agent can sample the entire state-action space, observing only one state-action pair at each time step.The stated coverage condition requires irreducible, aperiodic behavior-policy chains and positive action probabilities for every state.Source: §2 · p. 5
• The analysis first uses asynchronous i.i.d. samples from each agent’s stationary state distribution, then considers single-trajectory Markovian sampling.The minimum visitation probability λmin is positive under the full-coverage condition.Source: §2 · p. 5
• A fraction ε ∈ [0, 1/2) of agents may be adversarial and transmit arbitrary, potentially unbounded messages to the server.The adversary may know the MDP, agents’ data, and algorithm.Source: §2 · p. 6
• The goal is an estimate whose ℓ∞ error vanishes with each agent’s sample count despite adversaries and achieves the optimal 1/NT rate without them.The section asks whether collaboration gains persist under asynchronous data, what communication they require, what corruption limits apply, and how partial coverage changes the problem.Source: §2 · p. 6
• Asynchronous visit-count variability can make honest agents’ estimates appear different, complicating separation of sampling uncertainty from adversarial corruption.Partial coverage adds heterogeneous observations, and Markovian data introduces temporal dependence.Source: §2 · p. 6

• The server uses a trimmed mean to robustly aggregate agents’ Bellman estimates, including when some agents send corrupted values.Source: §3 · pp. 6–7
• Each epoch, the server broadcasts Q_k; honest agents use H asynchronous samples to estimate T^*Q_k, and the server aggregates estimates into Q_{k+1}.Source: §3 · p. 6
• Agents average Bellman samples for each state-action pair at frozen Q_k, reducing estimate variance before server aggregation.The samples share the same Bellman target, helping the server distinguish statistical noise from adversarial corruption.Source: §3 · p. 7
• Freezing Q within epochs avoids cross-agent table drift; low-variance updates let adversarial bias vanish as T grows and require only K = eO(1) communication rounds.Source: §3 · p. 7

• With ε=0, the dominant statistical term is O~(1/√(λ_minNT)), yielding an optimal N-factor improvement over the single-agent case.The rate matches single-agent Q-learning when N=1.Source: §4 · p. 8
• The corruption term is O~(ε/√(λ_minT)); it decreases with per-agent T rather than leaving a fixed error floor.The authors attribute this vanishing effect to operator refinement and variance reduction.Source: §4 · p. 8
• Communication rounds avoid linear dependence on either T or N, an improvement attributed to refined low-variance Bellman operators.The paper contrasts this with prior work whose communication costs scale linearly with T or N.Source: §4 · p. 9
• Epoch-level variance reduction makes adversarial estimates less able to amplify uncertainty at the server, supporting the collaboration benefit and diminishing corruption bias.Within each epoch, honest agents use their samples to estimate the Bellman target; the variance scales inversely with λ_minH.Source: §4 · p. 9
• Theorem 2 makes the corruption-induced bias unavoidable; together with the upper bound, it gives the first nearly matching bounds for adversarially robust FRL.The lower-bound construction allows the server to observe raw reward samples.Source: §4 · pp. 9–10
• The current lower bound does not capture asynchronous sampling, and whether λ_min also enters the corruption bias remains conjectural.Making that dependence rigorous is described as ongoing work.Source: §4 · p. 10

• Partial coverage requires each state-action pair to have a nonempty source set and limits the adversarial share within each pair’s sources to ε.This supplies clean information redundancy locally, rather than requiring every agent to cover every pair.Source: §5 · p. 10
• For each pair, the server applies trimmed-mean aggregation only to messages from agents that can observe that pair.Agents compute local estimates only for the pairs they can observe; the remaining algorithm is unchanged.Source: §5 · p. 10
• The ℓ∞ rate is bottlenecked by the smallest source set and the least stationary visitation probability among its agents.The theorem uses the minimum source-set size and minimum visitation probability over source sets.Source: §5 · pp. 10–11
• The upper bounds establish collaborative statistical gains under both full and partial coverage, while the lower bound shows corruption-dependent terms are unavoidable.Source: §5 · p. 11

• The partial-coverage counterpart follows by the same argument, replacing λ_min with Λ_min.Source: §6 · p. 11
• Each honest agent uses every τ-th transition, with τ proportional to the worst mixing time, making the used samples approximately independent.The analysis reduces to the asynchronous i.i.d. case with effective epoch length H/τ.Source: §6 · p. 11
• The stated full-coverage guarantee assumes each agent’s trajectory is initialized from its stationary distribution.The theorem applies to the τ-subsampled version of Robust Async-Fed-Q.Source: §6 · p. 11
• The Markovian guarantee has effective sample size T/τ, with a √τ mixing-time slowdown in both statistical and corruption-dependent terms.Source: §6 · p. 11

7 Simulation Results

• Across full and partial coverage, Robust Async-Fed-Q remains stable under adversarial message corruption, converges near Q⋆, and reduces error with longer epochs and more contributing agents.The reported errors average 100 independent runs.Source: §7 · p. 12, Figure 1 · p. 12

7.1 Ablation Studies and Robustness Diagnostics

• At ε=0.001, arithmetic-mean aggregation becomes unusable, while robust aggregation remains stable through ε=0.01 with terminal error on the order of 10^-2.The robust method also showed nearly indistinguishable trajectories under negative-outlier, sign-flip, dispersion-shift, and adaptive-sign attacks.Source: §7.1 · p. 13, Figure 3 · p. 14
• Terminal error rises gradually with reward-noise scale, from below 10^-3 without noise to approximately 10^-2 at σ=5.No instability was observed over the tested noise range.Source: §7.1 · p. 13
• Under both fixed-fraction and fixed-number corruption, increasing the agent population lowers error, preserving the collaboration benefit despite adversarial messages.With a fixed number of corrupted agents, adding agents also reduces the realized corruption fraction.Source: §7.1 · p. 14, Figure 4 · p. 15
• Increasing per-epoch samples H from 500 to 64000 reduces the error floor by approximately one order of magnitude; error also decays with total sample budget T.The decay curves remain separated upward at larger corruption fractions.Source: §7.1 · pp. 14–15, Figure 5 · p. 15
• With partial coverage, more source agents, larger H, and higher Λmin reduce terminal error, while no individual agent needs to cover every state–action pair.The least-visited coordinate creates a statistical bottleneck when Λmin is small.Source: §7.1 · p. 15, Figure 6 · p. 16
• At fixed total samples T, error initially improves with more communication epochs K, then worsens after approximately K=40 as per-epoch batches become noisier.Increasing T lowers the error curve and weakens this allocation tradeoff.Source: §7.1 · p. 16

7.2 Robust Learning with Markovian Data

• At equal retained sample counts, thinning brings Markovian error near IID; at fixed physical budgets, aggressive thinning worsens error through sparse coverage, while more agents still help.At Tused=2880, τ=4 and τ=140 errors approach the IID result; under τ=140 thinning, increasing N from 1600 to 4800 lowers mean terminal error from 0.0373 to 0.0269.Source: §7.2 · pp. 17–19

8 Additional Experiments on Gymnasium Environments

• The sweeps ask whether error decreases with N, follows the O(1/N) guide, and rises with corruption, and whether more agents offset that degradation.The reference line is a visual slope guide, not a fit to the experimental data.Source: §8 · p. 19, §8.1 · p. 20

8.1 Environments and Evaluation Protocol

• The evaluation uses four tabular Gymnasium benchmarks under full coverage, with each agent sampling every active state-action coordinate once per epoch.The environments are FrozenLake-v1, CliffWalking-v0, Taxi-v3, and Blackjack-v1; the protocol uses K = 120, γ = 0.9, and unit update stepsize unless stated otherwise.Source: §8.1 · p. 19

8.2 Collaboration Benefit under Corruption

• Across all four environments, increasing the number of agents produces an overall reduction in terminal error at ε = 0.0025.CliffWalking-v0 falls from approximately 2.6×10^-1 to 1.3×10^-1, and FrozenLake-v1 from approximately 2.1×10^-1 to 1.0×10^-1 as N rises from 1600 to 4800.Source: §8.2 · p. 20

8.3 Sensitivity to the Corruption Level

• Across all four environments, terminal error generally increases with corruption, with the clearest separation at ε = 0.01.CliffWalking-v0 rises from approximately 1.9 × 10^-1 to 2.5 × 10^-1, and FrozenLake-v1 from approximately 1.1 × 10^-1 to 1.8 × 10^-1 as ε increases from 0 to 0.01.Source: §8.3 · pp. 20–21

8.4 Joint Effect of Agent Population and Corruption Fraction

• Across all four environments and tested corruption levels, increasing N produces an overall reduction in terminal error.Blackjack-v1’s curves approach an environment-dependent floor after the largest reduction occurs between N = 1600 and 2400; local crossings are comparable to run-to-run variation.Source: §8.4 · pp. 21–23
• At (N, ε) = (4800, 0.01), error is lower than the clean error at N = 1600 in all four environments.The results therefore show that, within the tested range, additional collaboration can more than compensate for corruption-induced degradation.Source: §8.4 · p. 23

8.5 Summary of Empirical Findings

• The empirical findings are that collaboration reduces worst-agent terminal error under every tested corruption level, while corruption raises the error floor.The decay with N remains close to the predicted O(1/N) scaling in the benchmark environments, and the corruption effect can be offset by increasing the number of agents.Source: §8.5 · pp. 23–24

9 Conclusion

• Robust Async-Fed-Q preserves collaborative gains under adversarial corruption while requiring only e O(1) communication rounds.The guarantees cover full and partial coverage and Markovian sampling, and are supported by a nearly matching lower bound and numerical results.Source: §9 · p. 24
• Future work will consider function approximation and heterogeneous MDPs.Source: §9 · p. 24

A Standard Results

• Bernstein’s inequality is included for independent, bounded random variables with a common mean.Source: A Standard Results · p. 24
• Hoeffding’s inequality is included for independent random variables bounded within a common interval and sharing a mean.Source: A Standard Results · p. 24
• Pinsker’s inequality is stated for probability measures P and Q when every event of zero Q-probability also has zero P-probability.The section defines total variation distance and Kullback–Leibler divergence for its statement.Source: A Standard Results · p. 24

B Additional Technical Background

• The least-sampled state-action pairs set asynchronous i.i.d. Q-learning’s effective sample size, motivating parallel agents that can cover different regions.Each pair receives about λ(s, a)T updates; uniform guarantees require λmin > 0.Source: B Additional Technical Background · p. 25

B.1 Graph-Theoretic Interpretation of Assumptions 1 and 2

• Full coverage requires every agent to visit every state-action pair, whereas collective coverage requires each pair to be covered by at least one agent.A bipartite assignment graph represents collective coverage; assigned pairs must be reachable and selected with positive probability under the agent’s behavior policy.Source: §B.1 · pp. 25–26

C Robust Mean Estimation under Independent Sub-Gaussian Inliers

• trimSC clips observations using thresholds from one random half of the data and averages the other half to robustly estimate a common mean.For independent, possibly non-identically distributed sub-Gaussian clean observations, its error is of order ε log(1/ε) + M^-1/2.Source: C Robust Mean Estimation under… · p. 27

D Proof of Theorem 1: Full Coverage Setting

• The honest messages, clipped server aggregate, and next Q-iterate remain bounded in sup norm by B = R̄/(1 − γ).The server’s clipping thresholds lie within the honest-message bound, and the update is a convex combination.Source: D Proof of Theorem 1: Full Coverage… · p. 29
• For confidence δ ∈ (0, 1), if H ≥ (104/3λmin) log(2NT|S||A|/δ), the uniform-visitation event in S1 holds with probability at least 1 − δ/2.The proof bounds P(Vc) ≤ NT|S||A| exp(−3λminH/104) using K ≤ T, and the prescribed H bound makes this at most δ/2.Source: D Proof of Theorem 1: Full Coverage… · pp. 29–30
• With probability at least 1 − δ, robust aggregation error is controlled simultaneously across epochs and state-action pairs despite random, heterogeneous visitation counts.Conditioned on admissible visit counts, honest messages share the Bellman-operator mean and satisfy a common sub-Gaussian bound before robust aggregation.Source: D Proof of Theorem 1: Full Coverage… · pp. 30–32
• The proof combines a one-step error recursion, Bellman contraction, and uniform aggregation control to derive a high-probability finite-time bound.With the stated step size, the initialization contribution is reduced by a factor of 1/(NT).Source: D Proof of Theorem 1: Full Coverage… · pp. 32–33

E Proof of Theorem 3: Partial Coverage Setting

• Under partial coverage, each agent sends messages only for assigned state-action pairs, and the server aggregates each pair’s messages from its source set I(s, a).An individual agent need not cover every pair; the relevant coverage parameter is Λmin, the weakest visitation probability among admissible agents.Source: E Proof of Theorem 3: Partial Coverage… · p. 33
• If H ≥ (104/3Λmin) log(2NT|S||A|/δ), admissible agents meet the uniform per-epoch visitation threshold with probability at least 1 − δ/2.The threshold is (3/4)ΛminH visits for each admissible agent and state-action pair.Source: E Proof of Theorem 3: Partial Coverage… · p. 34
• With probability at least 1 − δ, the robust aggregation error is bounded simultaneously for every epoch and state-action pair under partial coverage.The proof conditions on source-agent visit counts and applies robust mean estimation to the pair-specific messages, whose honest members share the Bellman-operator mean.Source: E Proof of Theorem 3: Partial Coverage… · p. 35
• Theorem 3’s finite-time bound follows the full-coverage proof after establishing that each pair receives enough honest aggregate samples from agents that can observe it.The proof identifies this sufficient-sample step as the additional argument for partial coverage.Source: E Proof of Theorem 3: Partial Coverage… · pp. 33, 36

F Proof of Theorem 2: Fundamental Lower Bound

• Corruption can make two MDPs with separated optimal Q-values produce identical server observations, forcing any estimator to err on at least one instance.The proof uses a two-point indistinguishability argument and the Bretagnolle–Huber inequality to translate identical observation laws into estimation error.Source: F Proof of Theorem 2: Fundamental… · pp. 36–38
• The constructed MDPs have optimal Q-functions separated by order ε Rbar/((1 − γ) T), despite their indistinguishable corrupted transcripts.The instances share a single state, action, and deterministic self-transition, differing only in Gaussian reward means.Source: F Proof of Theorem 2: Fundamental… · p. 37

F.1 Lower bound with the asynchronous full coverage factor λmin

• In asynchronous sampling, the hard state-action pair is observed with probability λmin, so a length-T transcript contains only order λminT informative samples.The dummy action has the same reward law in both instances; only observations of the hard action distinguish them.Source: §F.1 · p. 39
• The asynchronous construction still separates the optimal Q-functions while keeping the honest transcript laws close enough for adversarial contamination to hide the difference.The resulting Q-function separation depends on λmin, reflecting the reduced effective sample count.Source: §F.1 · pp. 39–41
• Under the attack strategy, the server observes identical corrupted transcript distributions under M and M′.This indistinguishability holds in the asynchronous setting.Source: §F.1 · p. 42
• The proof reduces estimation error for any transcript-based estimator to distinguishing M from M′ using an event based on separation from Q⋆.On the event Aλ, the estimator is within distance ∆λ/2 of Q⋆; the proof then applies the Bretagnolle-Huber inequality to the corrupted transcript laws.Source: §F.1 · p. 43
• The lower bound’s λmin factor reflects that the hard state-action pair is sampled with probability λmin, giving a length-T transcript effective size λminT.This is the asynchronous coverage factor in the fundamental lower bound.Source: §F.1 · p. 43

G Proof of Theorem 4

• Thinning each Markovian trajectory at interval τ lets the analysis transfer to i.i.d. stationary samples under the stated Markovian conditions.The interval is chosen using the chains’ mixing time and the confidence level.Source: G Proof of Theorem 4 · p. 44
• Geometric mixing decay supports choosing a subsampling interval large enough for high-probability agreement with the i.i.d. stationary sequence.The coupling is needed for the state-action-next-state process; rewards are handled as independent auxiliary randomness conditional on the visited pair.Source: G Proof of Theorem 4 · pp. 44–45
• On the coupling event H, the retained Markovian and i.i.d. datasets agree, so the algorithm outputs are identical.The proof uses the same auxiliary randomness for both executions.Source: G Proof of Theorem 4 · p. 45
• With coupling failure probability at most δ/2, the i.i.d. bound applies using the effective epoch length, yielding the Markovian guarantee.The proof adds the coupling failure probability to the bound for the coupled i.i.d. output.Source: G Proof of Theorem 4 · p. 45