Fault-Tolerant Federated Reinforcement Learning with Theoretical Guarantee
Year: 2021

Abstract:
The growing literature of Federated Learning (FL) has recently inspired Federated Reinforcement Learning (FRL) to encourage multiple agents to federatively build a better decision-making policy without sharing raw trajectories. Despite its promising applications, existing works on FRL fail to I) provide theoretical analysis on its convergence, and II) account for random system failures and adversarial attacks. Towards this end, we propose the first FRL framework the convergence of which is guaranteed and tolerant to less than half of the participating agents being random system failures or adversarial attackers. We prove that the sample efficiency of the proposed framework is guaranteed to improve with the number of agents and is able to account for such potential failures or attacks. All theoretical results are empirically verified on various RL benchmark tasks.

heading: 1 Introduction
text: Reinforcement learning (RL) has recently been applied to many real-world decision-making problems such as gaming, robotics, healthcare, etc. [1–3]. However, despite its impressive performances in simulation, RL often suffers from poor sample efficiency, which hinders its success in real-world applications [4, 5]. For example, when RL is applied to provide clinical decision support [3, 6, 7], its performance is limited by the number (i.e., sample size) of admission records possessed by a hospital, which cannot be synthetically generated [3]. As this challenge is usually faced by many agents (e.g., different hospitals), a natural solution is to encourage multiple RL agents to share their trajectories, to collectively build a better decision-making policy that one single agent can not obtain by itself. However, in many applications, raw RL trajectories contain sensitive information (e.g., the medical records contain sensitive information about patients) and thus sharing them is prohibited. To this end, the recent success of Federated Learning (FL) [8–11] has inspired the setting of Federated Reinforcement Learning (FRL) [12], which aims to federatively build a better policy from multiple RL agents without requiring them to share their raw trajectories. FRL is practically appealing for addressing the sample inefficiency of RL in real systems, such as autonomous driving [13], fast personalization [14], optimal control of IoT devices [15], robots navigation [16], and resource management in networking [17]. Despite its promising applications, FRL is faced by a number of major challenges, which existing works are unable to tackle.
Firstly, existing FRL frameworks are not equipped with theoretical convergence guarantee, and thus lack an assurance for the sample efficiency of practical FRL applications, which is a critical drawback
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
due to the high sampling cost of RL trajectories in real systems [4]. Unlike FL where training data can be collected offline, FRL requires every agent to sample trajectories by interacting with the environment during learning. However, interacting with real systems can be slow, expensive, or fragile. This makes it critical for FRL to be sample-efficient and hence highlights the requirement for convergence guarantee of FRL, without which no assurance on its sample efficiency is provided for practical applications. To fill this gap, we establish on recent endeavors in stochastic variance-reduced optimization techniques to develop a variance-reduced federated policy gradient framework, the convergence of which is guaranteed. We prove that the proposed framework enjoys a sample complexity of O(1/ 5/3) to converge to an -stationary point in the single-agent setting, which matches recent results of variance-reduced policy gradient [18, 19]. More importantly, the aforementioned sample complexity is guaranteed to improve at a rate of O(1/K2/3) upon the federation of K agents. This guarantees that an agent achieves a better sample efficiency by joining the federation and benefits from more participating agents, which are highly desirable in FRL.
Another challenge inherited from FL is that FRL is vulnerable to random failures or adversarial attacks, which poses threats to many real-world RL systems. For example, robots may behave arbitrarily due to random hardware issues; clinical data may provide inaccurate records and hence create misleading trajectories [3]; autonomous vehicles, on which RL is commonly deployed, are subject to adversarial attacks [20]. As we will show in experiments, including such random failures or adversary agents in FRL can significantly deteriorate its convergence or even result in unlearnability. Of note, random failures and adversarial attacks in FL systems are being encompassed by the Byzantine failure model [21], which is considered as the most stringent fault formalism in distributed computing [22, 23] – a small fraction of agents may behave arbitrarily and possibly adversarially, with the goal of breaking or at least slowing down the convergence of the system. As algorithms proven to be correct in this setting are guaranteed to converge under arbitrary system behavior (e.g., exercising failures or being attacked) [9, 24], we study the fault tolerance of our proposed FRL framework using the Byzantine failure model. We design a gradient-based Byzantine filter on top of the variance-reduced federated policy gradient framework. We show that, when a certain percentage (denoted by α < 0.5) of agents are Byzantine agents, the sample complexity of the FRL system is worsened by only an additive term of O(α4/3/ 5/3) (Section 4). Therefore, when α→ 0, (i.e., an ideal system with zero chance of failure), the filter induces no impact on the convergence.
Contributions. In this paper, we study the federated reinforcement learning problem with theoretical guarantee in the potential presence of faulty agents. We introduce Federated Policy Gradient with Byzantine Resilience (FedPG-BR), the first FRL framework that is theoretically principled and practically effective for the FRL setting, accounting for random systematic failures and adversarial attacks. In particular, FedPG-BR (a) enjoys a guaranteed sample complexity which improves with more participating agents, and (b) is tolerant to the Byzantine fault in both theory and practice. We discuss the details of problem setting and the technical challenges (Section 3) and provide theoretical analysis of FedPG-BR (Section 4). We also demonstrate its empirical efficacy on various RL benchmark tasks (Section 5).

heading: 2 Background
text: Stochastic Variance-Reduced Gradient aims to solve minθ∈Rd [J(θ) , 1B ∑B i=1 Ji(θ)]. Under the common assumption of all function components Ji being smooth and convex in θ, gradient descent (GD) achieves linear convergence in the number of iterations of parameter updates [25, 26]. However, every iteration of GD requires B gradient computations, which can be expensive for large B. To overcome this problem, stochastic GD (SGD) [27, 28] samples a single data point per iteration, which incurs lower per-iteration cost yet results in a sub-linear convergence rate [29]. For a better trade-off between convergence rate and per-iteration computational cost, the stochastic variancereduced gradient (SVRG) method has been proposed, which reuses past gradient computations to reduce the variance of the current gradient estimate [30–33]. More recently, stochastically controlled stochastic gradient (SCSG) has been proposed for convex [34] or smooth non-convex objective function [35], to further reduce the computational cost of SVRG especially when required is small in finding -approximate solution. Refer to Appendix A.1 for more details on SVRG and SCSG.
Reinforcement Learning (RL) can be modelled as a discrete-time Markov Decision Process (MDP) [36]: M , {S,A,P,R, γ, ρ}. S represents the state space, A is the action space, P(s′|s, a)
defines the transition probability from state s to s′ after taking action a,R(s, a) : S × A 7→ [0, R] is the reward function for state-action pair (s, a) and some constant R > 0, γ ∈ (0, 1) is the discount factor, and ρ is the initial state distribution. An agent’s behavior is controlled by a policy π, where π(a|s) defines the probability that the agent chooses action a at state s. We consider episodic MDPs with trajectory horizon H . A trajectory τ , {s0, a0, s1, a1, ..., sH−1, aH−1} is a sequence of state-action pairs traversed by an agent following any stationary policy, where s0 ∼ ρ. R(τ) , ∑H−1 t=0 γ
tR (st, at) gives the cumulative discounted reward for a trajectory τ . Policy Gradient (PG) methods have achieved impressive successes in model-free RL [37, 38, ,etc.]. Compared with deterministic value-function based methods such as Q-learning, PG methods are generally more effective in high-dimensional problems and enjoy the flexibility of stochasticity. In PG, we use πθ to denote the policy parameterized by θ ∈ Rd (e.g., a neural network), and p(τ |πθ) to represent the trajectory distribution induced by policy πθ. For brevity, we use θ to denote the corresponding policy πθ. The performance of a policy θ can be measured by J(θ) , Eτ∼p(·|θ)[R(τ)|M ]. Taking the gradient of J(θ) with respect to θ gives
∇θJ(θ) = ∫ τ R(τ)∇θp(τ | θ)dτ = Eτ∼p(·|θ) [∇θ log p(τ | θ)R(τ) |M ] (1)
Then, the policy θ can be optimized by gradient ascent. Since computing (1) is usually prohibitive, stochastic gradient ascent is typically used. In each iteration, we sample a batch of trajectories {τi}Bi=1 using the current policy θ, and update the policy by θ ← θ + η∇̂BJ (θ), where η is the step size and ∇̂BJ(θ) is an estimate of (1) using the sampled trajectories {τi}Bi=1: ∇̂BJ(θ) = 1B ∑B i=1∇θ log p (τi | θ)R (τi). The most common policy gradient estimators, such as REINFORCE [39] and GPOMDP [40], can be expressed as
∇̂BJ(θ) = 1
B B∑ i=1 g(τi|θ) (2)
where τi = {si0, ai0, si1, ai1, . . . , siH−1, aiH−1} and g(τi|θ) is an unbiased estimate of ∇θ log p(τi | θ)R(τi). We provide formal definition of g(τi|θ) in Appendix A.2. SVRPG. A key issue for PG is the high variance of the estimator based on stochastic gradients (2) which results in slow convergence. Similar to SGD for finite-sum optimization, PG requires O(1/ 2) trajectories to find an -stationary point such that E[‖∇J(θ)‖2] ≤ [19]. That is, PG typically requires a large number of trajectories to find a well-performing policy. To reduce the variance of the gradient estimator in PG (2), SVRG has been applied to policy evaluation [41, 42] and policy optimization [43]. The work of Papini et al. [18] has adapted the theoretical analysis of SVRG to PG to introduce the stochastic variance-reduced PG (SVRPG) algorithm. More recently, Xu et al. [19] has refined the analysis of SVRPG [18] and shown that SVRPG enjoys a sample complexity of O(1/ 5/3). These works have demonstrated both theoretically and empirically that SVRG is a promising approach to reduce the variance and thus improve the sample efficiency of PG methods.
Fault tolerance refers to the property that enables a computing system to continue operating properly without interruption when one or more of its workers fail. Among the many fault formalisms, the Byzantine failure model has a rich history in distributed computing [22, 23] and is considered as the most stringent fault formalism in fault-tolerant FL system design [9, 24]. Originated from the Byzantine generals problem [21], the Byzantine failure model allows an α-fraction (typical α < 0.5) of workers to behave arbitrarily and possibly adversarially, with the goal of breaking or at least slowing down the convergence of the algorithm. As algorithms proven to be resilient to the Byzantine failures are guaranteed to converge under arbitrary system behavior (hence fault-tolerant) [22, 23], it has motivated a significant interest in providing distributed supervised learning with Byzantine resilience guarantees [e.g., 44–49]. However, there is yet no existing work studying the correctness of Byzantine resilience in the context of FRL.

heading: 3 Fault-tolerant federated reinforcement learning

heading: 3.1 Problem statement
text: Our problem setting is similar to that of FL [8] where a central server is assumed to be trustworthy and governs the federation of K distributed agents k ∈ {1, ...,K}. In each round t ∈ {1, ..., T},
the central server broadcasts its parameter θt0 to all agents. Each agent then independently samples a batch of trajectories {τ (k)t,i } Bt i=1 by interacting with the environment using the obtained policy, e.g., {τ (k)t,i } Bt i=1 ∼ p(·|θ t 0). However, different from FL where each agent computes the parameter updates and sends the updated parameter to the server for aggregation [8], agents in our setup do not compute the updates locally, but instead send the gradient computed w.r.t. their local trajectories µ
(k) t , ∇̂BtJ(θ t 0) directly to the server. The server then aggregates the gradients, performs a policy
update step, and starts a new round of federation.
Of note, every agent including the server is operating in a separate copy of the MDP. No exchange of raw trajectories is required, and no communication between any two agents is allowed. To account for potential failures and attacks, we allow an α-fraction of agents to be Byzantine agents with α ∈ [0, 0.5). That is, in each round t, a good agent always sends its computed µ(k)t back to the server, while a Byzantine agent may return any arbitrary vector.1 The server has no information regarding whether Byzantine agents exist and cannot track the communication history with any agent. In every round, the server can only access the K gradients received from agents, and thereby uses them to detect Byzantine agents so that it only aggregates the gradients from those agents that are believed to be non-Byzantine agents.
Notations. Following the notations of SCSG [35], we use θt0 to denote the server’s initial parameter in round t and θtn to represent the updated parameter at the n-th step in round t. τ (k) t,i represents agent k’s i-th trajectory sampled using θt0. ‖ · ‖ denotes Euclidean norm and Spectral norms for vectors and matrices, respectively. O(·) hides all constant terms.

heading: 3.2 Technical challenges
text: There is an emerging interest in Byzantine-resilient distributed supervised learning [e.g., 44–50]. However, a direct application of those works to FRL is not possible due to that the objective function J(θ) of RL, which is conditioned on τ ∼ p(·|θ), is different from the supervised classification loss seen in the aforementioned works, resulting in the following issues:
Non-stationarity: unlike in supervised learning, the distribution of RL trajectories is affected by the value of the policy parameter which changes over time (e.g., τ ∼ p(·|θ)). We deal with the non-stationarity using importance sampling [51] (Section 3.3).
Non-concavity: the objective function J(θ) is typically non-concave. To derive the theoretical results accounting for the non-concavity, we need the L-smoothness assumption on J(θ), which is a reasonable assumption and commonly made in the literature [52] (Section 4). Hence we aim to find an -approximate solution (i.e., a commonly used objective in non-convex optimization):
Definition 1 ( -approximate solution). A point θ is called -stationary if ‖∇J(θ)‖2 ≤ . Moreover, the algorithm is said to achieve an -approximate solution in t rounds if E[‖∇J(θ)‖2] ≤ , where the expectation is with respect to all randomness of the algorithm until round t.
High variance in gradient estimation: the high variance in estimating (2) renders the FRL system vulnerable to variance-based attacks which conventional Byzantine-resilient optimization works fail to defend [47]. To combat this issue, we adapt the SCSG optimization [35] to federated policy gradient for a refined control over the estimation variance, hence enabling the following assumption which we exploit to design our Byzantine filtering step:
Assumption 2 (On bounded variance of the gradient estimator). There is a constant σ such that ‖g(τ |θ)−∇J(θ)‖ ≤ σ for any τ ∼ p(τ |θ) for all policy πθ. Remark. Assumption 2 is also seen in Byzantine-resilient optimization [46, 48] and may be relaxed to E‖g(τ |θ)−∇J(θ)‖ ≤ θ which is a standard assumption commonly used in stochastic non-convex optimization [e.g. 35, 53]. In this work, the value of σ is the maximum difference between optimal gradient ∇J(θ) and the gradient estimate g(τ |θ) w.r.t. any trajectories induced by policy πθ. For complex real-world problems with continuous, high-dimensional controls, σ may be upper-bounded, provided that the MDP is Lipschitz continuousPirotta et al. [52]. The deviation can be obtained by referring to Proposition 2 of Pirotta et al. [52].2
1A Byzantine agent may not be Byzantine in every round. 2The value of σ can be estimated at the server.

heading: 3.3 Algorithm description
text: The pseudocode for the proposed Federated Policy Gradient with Byzantine Resilience (FedPG-BR) is shown in Algorithm 1. FedPG-BR starts with a randomly initialized parameter θ̃0 at the server. At the beginning of the t-th round, the server keeps a snapshot of its parameter from the previous round (i.e., θt0 ← θ̃t−1) and broadcasts this parameter to all agents (line 3). Every (good) agent k samples Bt trajectories {τ (k)t,i } Bt i=1 using the policy θ t 0 (line 5), computes a gradient estimate µ (k) t , 1/Bt ∑Bt i=1 g(τ (k) t,i |θ t 0) where g is either the REINFORCE or the GPOMDP estimator (line 6), and sends µ(k)t back to the server. For a Byzantine agent, it can send an arbitrary vector instead of the correct gradient estimate. After all gradients are received, the server performs the Byzantine filtering step, and then computes the batch gradient µt by averaging those gradients that the server believes are from non-Byzantine agents (line 7). For better clarity, we present the subroutine FedPGAggregate for Byzantine filtering and gradient aggregation in Algorithm 1.1, which we discuss in detail separately.
The aggregation is then followed by the SCSG inner loop [35] with Nt steps, where Nt is sampled from a geometric distribution with parameter BtBt+bt (line 8). At step n, the server independently samples bt (bt Bt) trajectories {τ tn,j} bt j=1 using its current policy θ t n (line 10), and then updates the policy parameter θtn based on the following semi-stochastic gradient (lines 11 and 12):
vtn , 1
bt bt∑ j=1 [ g(τ tn,j |θ t n)− ω(τ tn,j |θ t n,θ t 0)g(τ t n,j |θ t 0) ] + µt. (3)
The last two terms serve as a correction to the gradient estimate to reduce variance and improve the convergence rate of Algorithm 1. Of note, the semi-stochastic gradient above (3) differs from that used in SCSG due to the additional term of ω(τ |θtn,θ t 0) , p(τ |θ t 0)/p(τ |θ t n). This term is known as the importance weight from p(τ |θtn) to p(τ |θ t 0) to account for the aforementioned non-stationarity of the distribution in RL [18, 19]. In particular, directly computing g(τ tn,j |θ t 0) results in a biased estimation because the trajectories {τ tn,j} bt j=1 are sampled from the policy θ t n instead of θ t 0. We prove in Lemma 8 (Appendix E) that this importance weight results in an unbiased estimate of the gradient, i.e., Eτ∼p(·|θn)[ω(τ |θn,θ0)g(τ |θ0)] = ∇J(θ0). Here we describe the details of our Byzantine filtering step (i.e., the subroutine FedPG-Aggregate in Algorithm 1.1), which is inspired by the works of Alistarh et al. [46] and Khanduri et al. [48] in distributed supervised learning. In any round t, we use G to denote the set of true good agents and use Gt to denote the set of agents that are believed to be good by the server. Our Byzantine filtering
Algorithm 1 FedPG-BR
1: Input: θ̃0 ∈ Rd, batch size Bt, mini batch size bt, step size ηt 2: for t = 1 to T do 3: θt0 ← θ̃t−1 ; broadcast to all agents 4: for k = 1 to K do 5: Sample Bt trajectories {τ (k)t,i } Bt i=1 from p(·|θ t 0)
6: µ(k)t ,
{ 1 Bt ∑Bt i=1 g(τ (k) t,i |θ t 0) for k ∈ G
∗ for k /∈ G ; push µ(k)t to server
7: µt ← FedPG-Aggregate({µ(k)t }Kk=1) 8: Sample Nt ∼ Geom( BtBt+bt ) 9: for n = 0 to Nt − 1 do
10: Sample bt trajectories {τ tn,j} bt j=1 from p(·|θ t n) 11: vtn , 1 bt ∑bt j=1[g(τ t n,j |θ t n)− ω(τ tn,j |θ t n,θ t 0)g(τ t n,j |θ t 0)] + µt 12: θtn+1 = θ t n + ηtv t n 13: θ̃t ← θtNt 14: Output: θ̃a uniformly randomly picked from {θ̃t}Tt=1
Algorithm 1.1 FedPG-Aggregate
1: Input: Gradient estimates from K agents in round t: {µ(k)t }Kk=1, variance bound σ, filtering threshold Tµ , 2σ √ V Bt , where V , 2 log(2Kδ ) and δ ∈ (0, 1)
2: S1 , {µ(k)t } where k ∈ [K] s.t. ∣∣∣{k′ ∈ [K] : ∥∥∥µ(k′)t − µ(k)t ∥∥∥ ≤ Tµ}∣∣∣ > K2
3: µmomt ← argminµ(k̃)t ‖µ(k̃)t −mean(S1)‖ where k̃ ∈ S1 4: R1: Gt , { k ∈ [K] : ∥∥∥µ(k)t − µmomt ∥∥∥ ≤ Tµ} 5: if |Gt| < (1− α)K then 6: S2 , {µ(k)t } where k ∈ [K] s.t.
∣∣∣{k′ ∈ [K] : ∥∥∥µ(k′)t − µ(k)t ∥∥∥ ≤ 2σ}∣∣∣ > K2 7: µmomt ← argminµ(k̃)t ‖µ(k̃)t −mean(S2)‖ where k̃ ∈ S2
8: R2: Gt , { k ∈ [K] : ∥∥∥µ(k)t − µmomt ∥∥∥ ≤ 2σ} 9: Return: µt , 1|Gt| ∑ k∈Gt µ (k) t
consists of two filtering rules denoted by R1 (lines 2-4) and R2 (lines 6-8). R2 is more intuitive to understand, so we start by introducing R2. Firstly, in line 6, the server constructs a set S2 of vector medians [46] where each element of S2 is chosen from {µ(k)t }Kk=1 if it is close (within 2σ in Euclidean distance) to more than K/2 elements. Next, the server finds a Mean of Median vector
µmomt from S2, which is defined as any µ (k̃) t ∈ S2 that is the closet to the mean of the vectors in S2. After µmomt is selected, the server can construct the set Gt by filtering out any µ (k) t whose distance to µmomt is larger than 2σ (line 8). This filtering rule is designed based on Assumption 2 which implies that the maximum distance between any two good agents is 2σ, and our assumption that at least half of the agents are good (i.e., α < 0.5). We show in Appendix D that under these two assumptions, R2 guarantees that all good agents are included in Gt (i.e., |Gt| ≥ (1− α)K). We provide a graphical illustration (Fig. 4 in Appendix D) on that if any Byzantine agent is included in Gt, its distance to the true gradient ∇J(θt0) is at most 3σ, which ensures that its impact on the algorithm is limited. Note that the pairwise computation among the weights of all the agents can be implemented using the Euclidean Distance Matrix Trick [54].
R1 (lines 2-4) is designed in a similar way: R1 ensures that all good agents are highly likely to be included in Gt by exploiting Lemma 14 (Appendix E) to guarantee that with high probability, all good agents are concentrated in a smaller region. That is, define V , 2 log(2K/δ) and δ ∈ (0, 1), then with probability of≥ 1− δ, the maximum distance between any two good agents is Tµ , 2σ √ V/Bt. Having all good agents in a smaller region improves the filtering strategy, because it makes the Byzantine agents less likely to be selected and reduces their impact even if they are selected. Therefore, R1 is applied first such that if R1 fails to include all good agents in Gt (line 4) which happens with probability < δ, R2 is then employed as a backup to ensure that Gt always include all good agents. Therefore, these two filtering rules ensure in any round t that (a) gradients from good agents are never filtered out, and that (b) if gradients from Byzantine agents are not filtered out, their impact is limited since their maximum distance to∇J(θt0) is bounded by 3σ.

heading: 4 Theoretical results
text: Here, we firstly put in place a few assumptions required for our theoretical analysis, all of which are common in the literature. Assumption 3 (On policy derivatives). Let πθ(a|s) be the policy of an agent at state s. There exist constants G,M > 0 s.t. the log-density of the policy function satisfies, for all a ∈ A and s ∈ S
|∇θ log πθ(a|s)| ≤ G, ‖∇2θ log πθ(a|s)‖ ≤M, ∀a ∈ A,∀s ∈ S
Assumption 3 provides the basis for the smoothness assumption on the objective function J(θ) commonly used in non-convex optimization [32, 33] and also appears in Papini et al. [18], Xu et al. [19]. Specifically, Assumption 3 implies:
Proposition 4 (On function smoothness). Under Assumption 3, J(θ) isL-smooth withL , HR(M+ HG2)/(1 − γ). Let g(τ |θ) be the REINFORCE or GPOMDP gradient estimators. Then for all θ,θ1,θ2 ∈ Rd, it holds that
‖g(τ |θ)‖ ≤ Cg, ‖g (τ | θ1)− g (τ | θ2)‖ ≤ Lg ‖θ1 − θ2‖
where Lg , HM(R+ |Cb|)/(1− γ), Cg , HG(R+ |Cb|)/(1− γ) and Cb is the baseline reward.
Proposition 4 is important for deriving a fast convergence rate and its proof can be found in Xu et al. [19]. Next, we need an assumption on the variance of the importance weights (Section 3). Assumption 5 (On variance of the importance weights). There exists a constant W <∞ such that for each policy pairs in Algorithm 1, it holds
Var(ω(τ |θ1,θ2)) ≤W, ∀θ1,θ2 ∈ Rd, τ ∼ p(·|θ1)
Assumption 5 has also been made by Papini et al. [18], Xu et al. [19]. Now we present the convergence guarantees for our FedPG-BR algorithm: Theorem 6 (Convergence of FedPG-BR). Assume uniform initial state distribution across agents, and the gradient estimator is set to be the REINFORCE or GPOMDP estimator. Under Assumptions 2, 3, and 5, if we choose ηt ≤ 1
2ΨB 2/3 t
, bt = 1, and Bt = B ≥ 4ΦL−2 where Φ , Lg + C2gCw,
Ψ , (L(Lg + C2gCw)) 1/3, L,Lg, Cg are defined in Proposition 4 and Cw is defined in Lemma 9, δ ∈ (0, 1) such that e δBt
2(1−2δ) ≤ 2Kδ ≤ e Bt 2 and δ ≤ 15KBt , then the output θ̃a of Algorithm 1 satisfies
E[‖∇J(θ̃a)‖2] ≤ 2Ψ [ J(θ̃ ∗ )− J(θ̃0) ] TB1/3 + 8σ2 (1− α)2KB + 96α2σ2V (1− α)2B
where 0 ≤ α < 0.5 and θ̃ ∗ is a global maximizer of J .
This theorem leads to many interesting insights. When K = 1, α = 0, Theorem 6 reduces to E‖∇J(θ̃a)‖2 ≤ 2Ψ[J(θ̃ ∗ ) − J(θ̃0)]/TB1/3 + 8σ2/B. The second term here O(1/B), which also shows up in SVRPG [18, 19], results from the full gradient approximation in Equation (2) in each round. In this case, our theorem implies that E‖∇J(θ̃a)‖2 = O(Ψ[J(θ̃ ∗ ) − J(θ̃0)]/TB1/3) which is consistent with SCSG for L-smooth non-convex objective functions [35]. Moreover, using E[Traj( )] to denote the expected number of trajectories required by each agent to achieve E[‖∇J(θ̃a)‖2] ≤ , Theorem 6 leads to: Corollary 7 (Sample complexity of FedPG-BR). Under the same assumptions as Theorem 6, let > 0, we have: (i) E[Traj( )] = O( 1
5/3K2/3 + α
4/3 5/3 ); (ii) When α = 0, we have E[Traj( )] =
O( 1 5/3K2/3 ); (iii) When K=1, we have E[Traj( )] = O( 1 5/3 )
We present a straightforward comparison of the sample complexity of related works in Table 1. Both REINFORCE and GPOMDP have a sample complexity of O(1/ 2) since they use stochastic gradientbased optimization. Xu et al. [19] has made a refined analysis of SVRPG to improve its sample
complexity from O(1/ 2) [18] to O(1/ 5/3). Corollary 7 (iii) reveals that the sample complexity of FedPG-BR in the single-agent setup agrees with that of SVRPG derived by Xu et al. [19].
When K > 1, α = 0, Corollary 7 (ii) implies that the total number of trajectories required by each agent is upper-bounded by O(1/( 5/3K2/3)). This result gives us the theoretical grounds to encourage more agents to participate in the federation, since the number of trajectories each agent needs to sample decays at a rate of O(1/K2/3). This guaranteed improvement in sample efficiency is highly desirable in practical systems with a large number of agents.
Next, for a more realistic system where an α-fraction (α > 0) of the agents are Byzantine agents, Corollary 7 (i) assures us that the total number of trajectories required by each agent will be increased by only an additive term of O(α4/3/ 5/3). This term is unavoidable due to the presence of Byzantine agents in FRL systems. However, the bound implies that the impact of Byzantine agents on the overall convergence is limited, which aligns with the discussions on our Byzantine filtering strategy (Section 3.3), and will be empirically verified in our experiments. Moreover, the impact of Byzantine agents on the convergence vanishes when α → 0. That is, when the system is ideal (α = 0), our Byzantine filtering step induces no effect on the convergence.

heading: 5 Experiments
text: We evaluate the empirical performances of FedPG-BR with and without Byzantine agents on different RL benchmarks, including CartPole balancing [55], LunarLander, and the 3D continuous locomotion control task of Half-Cheetah [56]. In all experiments, we measure the performance online such that in each iteration, we evaluate the current policy of the server by using it to independently interact with the test MDP for 10 trajectories and reporting the mean returns. Each experiment is independently repeated 10 times with different random seeds and policy initializations, both of which are shared among all algorithms for fair comparisons. The results are averaged over the 10 independent runs with 90% bootstrap confidence intervals. Due to space constraints, some experimental details are deferred to Appendix F.
Performances in ideal systems with α = 0. We firstly evaluate the performances of FedPG-BR in ideal systems with α = 0, i.e., no Byzantine agents. We compare FedPG-BR (K=1, 3, 10) with vanilla policy gradient using GPOMDP3 and SVRPG. The results in all three tasks are plotted in Fig. 1. The figures show that FedPG-BR (K = 1) and SVRPG perform comparably, both outperforming GPOMDP. This aligns with the results in Table 1 showing that FedPG-BR (K=1) and SVRPG share the same sample complexity, and both are provably more sample-efficient than GPOMDP. Moreover, the performance of FedPG-BR is improved significantly with the federated of only K = 3 agents, and improved even further when K = 10. This corroborates our theoretical insights implying that the federation of more agents (i.e., larger K) improves the sample efficiency of FedPG-BR (Section 4), and verifies the practical performance benefit offered by the participation of more agents.
Performances in practical systems with α > 0. Next, we investigate the impact of Byzantine agents (i.e., random failures or adversarial attacks) on the sample efficiency, which is critical for the practical deployment of FRL algorithms. In this experiment, we use K = 10 agents among which 3 are Byzantine agents, and we simulate different types of Byzantine failures: (a) Random Noise (RN): each Byzantine agent sends a random vector to the server; (b) Random Action (RA): every Byzantine agent ignores the policy from the server and takes actions randomly, which is used to
3Since GPOMDP has been repeatedly found to be comparable to or better than REINFORCE [18, 19].
simulate random system failures (e.g., hardware failures) and results in false gradient computations since the trajectories are no longer sampled according to the policy; (c) Sign Filliping (SF): each Byzantine agent computes the correct gradient but sends the scaled negative gradient (multiplied by −2.5),which is used to simulate adversarial attacks aiming to manipulate the direction of policy update at the server.
For comparison, we have adapted both GPOMDP and SVRPG to the FRL setting (pseudocode is provided in Appendix A.3). Fig. 2 shows the results using the HalfCheetah task. We have also included the performances of GPOMDP, SVRPG and FedPG-BR in the single-agent settting (K=1) as dotted-line (mean value of 10 independent runs) for reference. The figures show that for both GPOMDP and SVRPG, the 3 Byzantine agents cause the performance of their federated versions to be worse than that in the single-agent setting. Particularly, RA agents (middle figure) render GPOMDP and SVRPG unlearnable, i.e., unable to converge at all. In contrast, our FedPG-BR is robust against all three types of Byzantine failures. That is, FedPG-BR (K = 10 B = 3) with 3 Byzantine agents still significantly outperforms the single-agent setting, and more importantly, performs comparably to FedPG-BR (K=10) with 10 good agents. This is because our Byzantine filtering strategy can effectively filter out those Byzantine agents. These results demonstrate that even in practical systems which are subject to random failures or adversarial attacks, FedPG-BR is still able to deliver superior performances. This provides an assurance on the reliability of our FedPG-BR algorithm to promote its practical deployment, and significantly improves the practicality of FRL. The results for the CartPole and LunarLander tasks, which yield the same insights as discussed here, can be found in Appendix G.
Performance of FedPG-BR against FedPG attack. We have discussed (Section 3.3) and shown through theoretical analysis (Section 4) that even when our Byzantine filtering strategy fails, the impact of the Byzantine agents on the performance of our algorithm is still limited. Here we verify this empirically. To this end, we design a new type of Byzantine agents who have perfect knowledge about our Byzantine filtering strategy, and call it FedPG attacker. The goal of FedPG attackers are to collude with each other to attack our algorithm without being filtered out. To achieve this, FedPG attackers firstly estimate∇J(θt0) using the mean of their gradients µ̄t, and estimate σ by calculating the maximum Euclidean distance between the gradients of any two FedPG attackers as 2σ̄. Next, all FedPG attackers send the vector µ̄t + 3σ̄ to the server. Recall we have discussed in Section 3.3 that if a Byzantine agent is not filtered out, its distance to the true gradient∇J(θt0) is at most 3σ. Therefore, if µ̄t and σ̄ are estimated accurately, the vectors from the FedPG attackers can exert negative impact on the convergence while still evading our Byzantine filtering.
We again use K = 10 agents, among which 3 are FedPG attackers. The results (Fig. 3) show that in all three tasks, even against such stong attackers with perfect knowledge of our Byzantine filtering strategy, FedPG-BR (K=10 B=3) still manages to significantly outperform FedPG-BR (K=1) in the single-agent setting. Moreover, the performance of FedPG-BR (K=10 B=3) is only marginally worsened compared with FedPG-BR (K=10) with 10 good agents. This corroborates our theoretical analysis showing that although we place no assumption on the gradients sent by the Byzantine agents, they only contribute an additive term of O(α4/3/ 5/3) to the sample complexity (Section 4). These results demonstrate the empirical robustness of FedPG-BR even against strong attackers, hence further highlighting its practical reliability.

heading: 6 Conclusion and future work
text: Federation is promising in boosting the sample efficiency of RL agents, without sharing their trajectories. Due to the high sampling cost of RL, the design of FRL systems appeals for theoretical guarantee on its convergence which is, however, vulnerable to failures and attacks in practical setup, as demonstrated. This paper provides the theoretical ground to study the sample efficiency of FRL with respect to the number of participating agents, while accounting for faulty agents. We verify the empirical efficacy of the proposed FRL framework in systems with and without different types of faulty agents on various RL benchmarks.
Variance control is the key to exploiting Assumption 2 on the bounded variance of PG estimators in our filter design. As a result, our framework is restricted to the variance-reduced policy gradient methods. Intuitively, it is worth studying the fault-tolerant federation of other policy optimization methods. Another limitation of this work is that agents are assumed to be homogeneous, while in many real-world scenarios, RL agents are heterogeneous. Therefore, it would be interesting to explore the possibility of heterogeneity of agents in fault-tolerant FRL in future works. Moreover, another interesting future work is to apply our Byzantine filtering strategy to other federated sequential decision-making problems such as federated bandit [57–59] and federated/collaborative Bayesian optimization [60–62], as well as other settings of collaborative multi-party ML [63–75], to equip them with theoretically guaranteed fault tolerance.
Acknowledgments and Disclosure of Funding
This research/project is supported by A*STAR under its RIE2020 Advanced Manufacturing and Engineering (AME) Industry Alignment Fund – Pre Positioning (IAF-PP) (Award A19E4a0101) and its A*STAR Computing and Information Science Scholarship (ACIS) awarded to Flint Xiaofeng Fan. Wei Jing is supported by Alibaba Innovative Research (AIR) Program.

Review summaries:
This paper aims to propose an algorithm for federated reinforcement learning with fault tolerance against Byzantine failure. The paper mainly considers the policy gradient method and proposes a server aggregation method with a Byzantine filter to reduce the effect of gradients from malicious agents. The paper also provides a theoretical analysis to support the design decision of the filter. 

This paper describes a federated reinforcement learning architecture that is expected to be tolerant to adversarial attacks or faulty agents. The architecture assumes a percent of the nodes are Byzantine agents that are actively trying to fool the central server, and assesses algorithm convergence and performance. Theoretical guarantees support empirical performance evaluation on some benchmark domains.  I have read the other reviews and the author responses. I agree that its difficult to do anything about the exploration policy without having further information. Although I still think this will be a limitation in the real world, drowning out interesting or unique outputs. My score remains borderline on this one.

The authors propose a federated reinforcement learning approach that combines existing stochastic variance-reduced policy gradient method with a robust aggregation method to achieve fault tolerance. Theoretically, the authors provide convergence and sample complexity results under reasonable assumptions. The proposed approach is tested empirically on various benchmark tasks.

This paper proposes a federated reinforcement learning (FRL) algorithm that uses a variance-reduced federated policy gradient framework. The proposed framework is proven to have convergence and robustness guatantees (can tolerant the failures of up to half of the agents), with some assumptions on the environment and the agents. Both theoretical results and empirical results justify that the proposed federation can boost the sample efficiency of RL agents.