Fault-Tolerant Federated Reinforcement Learning with Theoretical Guarantee
Authors: Flint Xiaofeng Fan
Yining Ma
Zhongxiang Dai
Wei Jing
Cheston Tan
Bryan Kian Hsiang Low
Venue: NeurIPS 2021 Poster (2021)
Keywords: Reinforcement learning
federated learning
Byzantine-tolerant optimization

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.

Fault-Tolerant Federated Reinforcement Learning with Theoretical Guarantee
Flint Xiaofeng Fan Yining Ma², Zhongxiang Dai', Wei Jing", Cheston Tan', Bryan Kian Hsiang Low!
Dept.. of Computer Science, National University of Singapore, Republic of Singapore
Dept. ISEM, National University of Singapore, Republic of Singapore IInstitute for Infocomm Research, A STAR. Republic of Singapore
*Alibaba DAMO Academy, Hangzhou, China
[xiaofeng, www.offenn.dzzzzogg.o..oo daizhong..ang, 1owkh] @comp edu. sg, 2 Pyiningmauu. nus edu (stufannxf cheston- 2i2r a-star. edu.sg, "ju3344050al bbab -nnh com "du.ssg""u33440500
Abstract
The growing literature of Federated Learning (FL) has recently inspired Federated Reinforcement Learning (FRL) to encourage multiple agents to federatively build belter 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 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.
Introduction
Reinforcement learning (RL. has recently been applied to many real-world pitiisioommaiing problems such as gaming, robotics, healtheare, 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 [5) For example, when RL is applied to provide clinical decision support B 6 (7), its performance is limited by the number (i.e., sample size) of admission records possessed by hospital, which cannot be synthetically generated [3]. As this challenge is usually faced by many agents (e.g., different hospitals), natural solution is to encourage multiple RL agents to share their trajectories, collectively build a better recision-making policy that one single agent can not obtain by itself. However, in many applications, raw RI. trajectories contain sensitive information (e.g.. the medical records contain sensitive information about patients) and thus sharing them prohibited. To this end, the recent success of Federated Learning (FL. [8 has inspired the setting of Federated Reinforcement Learning (FRL) [2). which aims to federatively build better policy from multiple RL agents without requiring them to share their raw trajectories. FRL is practically appealing addressing the sample inefficiency of RL in real systems, such as autonomous driving [3]. fast personalization [14, optimal control of IoT devices (15). robots navigation
[16], and resource management in networking [1].. 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 applicationn,, which is critical drawback
35th Conference on Neural Information Processing Systems (NcurIPS 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 FRI. to be sample-efficient and hence highlights the requirement for convergence guarantee of FRI., 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 variance-reduced federated policy gradient framework, the con- vergence of which is guaranteed. We prove that the proposed framework enjoys a sample complexity of O(1 /(1// 5/3) to converge to an e-stationary point in the single-agent setting, which matches recent results of variance-reducee policy gradient [1] 19. More importantly, the aforementioned sample complexity is guaranteed to improve at rate of ((1/K2/8) 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 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 33: autonomous vehicles, on which RI. 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 unlcarnability. 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 (2 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 certain percentage (denoted by a < 0.5) of agents are Byzantine agents, the sample complexity of the FRL system is worsened by only an additive term of (a /c5/3) (Section 4p. Therefore, when a - 0, (i.e., an ideal system with zero chance of failure), the filter induces no impact on the convergence.
Contributions. In this paper, 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 FRI. 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 B and provide theoretical analysis of FedPG-BB BR (Section 4. We also demonstrate its empirical efficacy on various RL benchmark tasks (Section 5
2 Background
Stochastic Variance-Reducee Gradient aims to solve mineer" (J()) ΣE J.(0)). Under the common assumption of all function components J; being smooth and convex in O, gradient descent (GD) achieves linear convergence in the number of iterations of parameter updates [6]] However, every iteration of GD requires B gradient computations, which can be expensive for large B. To overcome this problem, stochastic GD (SGD) [27 (88 samples single data point per iteration, which incurs lower per- -terrttttionn cost yet results in a sub-linear convergence rate [2].. For a better trade-off between convergence rate and per-iteration computational cost, the stochastic variance- reduced gradient (SVRG) method has been proposed, which reuses past gradient computations to reduce the variance of the current gradient estimate (0 More recently, stochastically controlled stochastic gradient (SCSG) has been proposed for convex (4] or smooth non-convex objective function [35). to further reduce the computational cost of SVRG especially when required e small in finding e- a-apprxximaee solution. Refer to Appendix A.I for more details on SVRG and SCSG.
Reinforcement Learning (RL) can be modelled discrete-time Markov Decision Process (MDP) [36] M e (S, A,S.A,PRO. R, 7, p.. S represents the state space, A is the action space, P(s'|s,a)

---

defines the transition probability from state to s' after taking action R(s, a) : x A R] the reward function for state-action pair (s, a) and some constant R 0, Y (0, is the dis- count factor, and / is the initial state distribution. An agent's 's behavior is controlled by policy T, where {{]s)) defines the probability that the agent chooses action a at state 8. We consider episodic MDPs with trajectory horizon H. A trajectory т _ {so, ao, 81, A1, -H-1. -- } is a sequence of state-action pairs traversed by an agent following any stationary policy, where 8g p.
(T)) ΣØ 7 y (st, (z) gives the cumulative discounted reward for trajectory
Policy Gradient (PG) methods have achieved impressive successes in model-free RL [3 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 stochasticity, In PG, use Te to denote the policy parameterized by O Rd (e.g., neural network), and p(T (T) to represent the trajectory distribution induced by policy Te. For brevity, we use 0 to denote the corresponding policy To- The performance of a policy @ can be measured by J(Ø) - 10 [R( Taking the gradient of (()) with respect to I gives
VoJ(0) [(( 0)dr Er-p( 0) /V log ()R(T) M]
(I)
Then, the policy O can be optimized by gradient ascent. Since computing ① is usually pro- hibitive, stochastic gradient ascent is typically used. In each iteration, we sample a batch of trajectories {Ti)-1 using the current policy 0, and update the policy by 0 0 + (O), where nj is the step size and (()) is an estimate of (T) using the sampled trajectories [
@ RO) = > Vo Po (T: 0 R (T:). The most common policy gradient estimators, such as REINFORCE (39 and GPOMDP 40 can be expressed as
1 Σ 9(1,0))
J
(2)
B
where T; = {sh ag. s1, ai...., - az -1 and () is an unbiased estimate of Ve log P(T, ():():) We provide formal definition of g(T: ()) in Appendix A.2
SVRPG. A key issue for PG is the high variance of the estimator based on stochastic gradients which results in slow convergence. Similar to SGD for finite-sum optimization. PG requires O(L/e" trajectories find an e-stationary point such that E ([)]ll S e [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 ariiaccereduced PG (SVRPG) algorithm. More recently, Xu et al. [1 has refined the analysis of SVRPG [18] and shown that SVRPG enjoys a sample complexity of ((1/55)3). These works have demonstrated both theoretically and empirically that SVRG is 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 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 211, the Byzantine failure model allows an o-fraction (typical o < 0.5) of workers to behave arbitrarily and possibly adversarially, with the goal of breaking 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.. 4 However, there is yet no existing work studying the correctness of Byzantine resilience in the context of FRL.
3 Fault-tolerant federated reinforcement learning
3.1 Problem statement
Our problem setting similar to that of FL. g where central server assumed to be trustworthy and governs the federation of K distributed agents A {l,..., K). In each round t E {l,..., T),
3

---

the central server broadcasts its parameter 0j to all agents. Each agent then independently samples a batch of trajectories {Tz, ) by interacting with the environment using the obtained policy, e.g..
( B, ~ p(-10)). However, different from FL where each agent computes the parameter (Te. li=1 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
(l) & V B.J (0() directly to the server. The server then aggregates the gradients, performs a policy Mg
update step, and starts 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 a-fraction of agents to be Byzantine agents with E [0, 0.5). That is, in each round f, a good agent always sends its computed 14 while a Byzantine agent may return any arbitrary vector 2 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.
(k) back to the server,
Notations. Following the notations of SCSG 35 we use 0 to denote the server's initial parameter (k)
in round and 0² to represent the updated parameter at the n-th step in round L. Tr, represents agent
k's i-th trajectory sampled using 0/ || denotes Euclidean norm and Spectral norms for vectors and matrices, respectively. (-) hides all constant terms.
3.2 Technical challenges
There is emerging interest in Byzantine-resilient distributed supervised learning [c.g..44/50 50)
However, a direct application of those works to FRL is not possible due to that the objective function (0) of RL, which is conditioned T ~ p(-10), is different from the supervised classification loss seen in the aforementioned works, resulting in the following issues:
von-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(-(0)). We deal with the non-stationarity using importance sampling [51] (Section 3.3
Non-concavity: the objective function (()) is typically non-concave. To derive the theoretical results accounting for the non-concavity, we need the T-smoothhnss assumption on J(0), which is a reasonable assumption and commonly made in the literature (52) (Section 4 Hence we aim to find an e-approximate solution (i.e., a commonly used objective in non-convex optimization):
Definition (c-approximate solution). A point f is called c-stationary if J 12 <.c. c. Moreover,
the algorithm is said achieve an c-approximate solution in rounds if E[][ J ( 1o S 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 renders the FRL system vulnerable to variance- sariance-based attacks which conventional Syyzantine-resilien 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 (On bounded variance of the gradient estimator). There constant such that (la(T(0) - v.(l))l < a for any T ~ p(T(0) for all policy ne.
Remark. Assumption 2 is also seen in Byzantine- resillent optimization |46 48 and may be relaxed El 0)- (() < which is a standard assumption commonly used in stochastic non-convex optimization [e.g. 35
533. In this work, the value of a is the maximum difference between optimal gradient (0) and the gradient estimate 0) w.t.. any trajectories induced by policy πe. For complex real-world problems with continuous, high-dimensiooal controls, a may be upper-bounded, provided that the MDP is Lipschitz continuous Pirotta et al. (52g. The deviation can be obtained by referring to Proposition 2 of Pirotta et al. [52]
A Byzantine agent may not Byzantine in every round.
2 The value of a be estimated at the server.

---

3.3 Algorithm description
The pseudocode for the proposed Federated Policy Gradient with Byzantine Resilience (FedPG-BR) shown in Algorithm|| [ FedPG-BR starts with a randomly initialized parameter Og at the server. At the beginning of the i-th round, the server keeps snapshot of its parameter from the previous round (i.e., 8 + 0)-1) and broadcasts this parameter to all agents (line 3). Every (good) agent samples B, trajectories (Tz,) ( using the policy O (line 5), computes gradient estimate 14
(0)) (k) A 1/B, E g(T,,) (0)) where g is either the REINFORCE or the GPOMDP estimator (line
6), and sends ! back to the server. For Byzantine agent, 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-Byzen non-Byzantine agents (line 7). For better clarity, we present the subroutine FedPG- Aggregate for Byzantine filtering and gradient aggregation in Algorithm L.1 which we discuss in detail separately.
The aggregation is then followed by the SCSG inner loop 35] with N₂ steps, where N, sampled B__ from geometric distribution with parameter Be+b, (line 8). At step n, the server independently samples b, (be < B,) trajectories { using its current policy 0% (line 10), and then updates the policy parameter 0², based on the following semi-stochastic gradient (lines 11 and 12):
be
2 A
(9(7))
(0')) w(T 1 0% (0)
+ p4-
(3)
be
The last convergence rate of Algorithm] [ Of note, the semi-stochastic gradient above (3) differs from that used in SCSG due to the additional term of w(T 0¹) A p(T(0))/p(e p)())" This term is known as the importance weight from p(T(0",) to p(T(0") to account for the aforementioned non-stationarity of the distribution in RL 18 19 In particular, directly computing y results a biased
correction to the gradient estimate reduce variance and improve the
estimation because the trajectories (r 1 are sampled from the policy 0% instead of 0% We prove in Lemma 8 ( (Appendix Eb that this importance weight results in an unbiased estimate of the gradient, i..., E.- (..) [T (r)g(T((o))
{ri,
v.().).
Here we describe the details of our Byzantine filtering step (i.c., the subroutine BedPG--Agregatt 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 & to denote the set of true good agents and use Gr to denote the set of agents that are believed to be good by the server. Our Byzantine filtering
Algorithm FedPG-BR
1: Input: 0n E Rdd, batch size B,, mini batch size bt, step size п)
2: for 1 to do
3: 0 < 0,-1
broadcast all agents
4: for k to K do
5: Sample B, trajectories
(k) B. [Tr J from p(- ((-(0)) (k)
(K) B. EE
( 0%)
for le E G for l: & g
6:
push pt to server
7:
Me FedPG- (11
(K) 1k=1)
8:
Sample N, Geoml B.tb, B.)
B,
9:
for = 0 to N, do
10: Sample b, trajectories (Th 1 from p( (0%))
of A b, Eh E) 10th) w(T 00,, 0%)g [6)l
12:
of 0 O¹, + neoh
0%,
14:
Output: 0, uniformly randomly picked from (
5

---

Algorithm 1.1 FedPG-Aggreeate
1: Input: Gradient estimates from K agents in round t: {14 (8) K
variance bound filtering
J 1k=1
threshold Sy _ 20 B. where V 2 (2K)
V V
8. and 5 E (0,1)
2: S1
{ug (10) where & [K] s.t. { [K] | Mi (k)
S TN
K
3: p argmin (E) l (k) mean(Si)) where i E Si
4: RI: G, A { E 14 (8)
mom
5: if [g < (1 K
then
(14 (k)) where & E [K] s.t. 1s {[K] 1
- v4/0
s $20 /<00|/>
6: S2
t argmin (6) l| (k) mean(S2) where To E S2
7: Pt mmm
8: R2: G
- [K] |1( 14:
mmmm - 20
9: Return: 14 poc Exeg, 14 (1))
consists of two filtering rules denoted by RI (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 S₂ of vector medians 46 where each element of S2 is chosen from (x(4)) Jk=1 if it is close (within 2o in Fuclidean distance) to more than K/2 elements. Next, the server finds a Mean of Median vector
14 44tm from 52, which is defined as any 14 (R)
E S2 that is the closet to the mean of the vectors in S2-
After pa is selected, the server can construct the set G. by filtering out any p4: (k) whose distance to 14: 14. is larger than 2o (line 8). This filtering rule is designed based on Assumption 2 which implies that the maximum distance between any two good agents is 2a, and our assumption that at least half of the agents are good (i.e., a < 0.5). We show in Appendix that under these two assumptions, R2 guarantees that all good agents are included in Ge (i.e., Gel (1 K). We provide graphical D) on that if any Byzantine agent is included in Gr, its distance to the true gradient (O,) at most 3o, which ensures that its impact 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].
illustration (Fig. 4 in Appendix
RI (lines 2-4) is designed in a similar way: R1 ensures that all good agents are highly likely to be included in G. by exploiting Lemma 14 (Appendix ED to guarantee that with high probability, all good agents are concentrated in smaller region. That is, define V & 2 (og(2K/5) and 8 E (0, 1), then with probability of > 1 8, the maximum distance between any two good agents is Sp 22 20 VV//V/B. 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, RI is applied first such that if R1 fails to include all good agents in G. (line 4) which happens with probability < 6, R2 is then employed as a backup to ensure that G. always include all good agents. Therefore, these two filtering rules ensure in any round f that (a) gradients from good agents are never filtered out, and that (b) if gradients from Byzantine agents are not filtered out, their impact limited since their maximum distance to V JJ ((())) is bounded by 3o.
4 Theoretical results
Here, we firstly put in place few assumptions required for our theoretical analysis, all of which 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 > S.s.I. the log-density of the policy function satisfies, for all E A and & E S
Vo log (o(ass) S.G. G,
ViVà log (a)s))] S M, Va E A
Assumption 3 provides the basis for the smoothness assumption on the objective function J(0) commonly used in non-convex optimization 332 33 and also appears in Papini et [8], Xu et al.
19]. Specifically, Assumption implies:

---

Proposition 4 (On function smoothness). Under Assumption 3 J(0) is L-smooth with L - HR(M- H/1 -7). Let g(T be the REINFORCE or GPOMDP gradient estimators. Then for all 0.01.02 E Rd, it holds that
|19(+10)| S Cg: where Lg HMMR+ (C6))(1 & HG(R + (1 7) and C. is the baseline reward.
[T 02) - L 10, - -2ll l1 01) (
Proposition 4 is important for deriving a fast convergence rate and its proof can be found in Xu et al. 19]. Next, need assumption the variance of the importance weights (Section 3
Assumption 5 (On variance of the importance weights). There exists constant W oo such that holds
for each policy pairs in Algorithm 7
Var(w 00, 02)) W,
vO,, 02 E EBA
- T p(-10,)
Assumption haas also been made by Papini et al. [18. Xu et al. [9] Now we present the convergence
guarantees for our FedPG-BR algorithm:
Theorem (Convergence of FedPG-BR). Assume uniform initial state distribution across agents,
and the gradient estimator is set be the REINFORCE GPOMDP estimator. Under Assumptions
2 and 5 if we choose N S 24 b, and B, B 2 4 where & Lg + C.
(I(Tgg + (m L, L.g: Og are defined in Proposition 4 and C. is defined in Lemma
68, 8 E (0, 1) such that 201
S
2K S Se and S TKह, then the output O, of Algorithm satisfies
2 ((Ø") - ((Oo)
80²
96a2a²V
E[I
+ (1 a1-a)2KB
TB1/3
(1-a) a1
where 0 S a < 0.5 and 0" is a global maximizer of J.
This theorem leads many interesting insights. When K = 1, Theorem reduces to (())) < [ ((oo))/TBB// + 802/B: The second term here O() 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 E which is consistent with SCSG for L-smooth non non-convex objective functions [35). Moreover, using (T)a((()) denote the expected number of trajectories required by each agent achieve [[[[ S e, Theorem 6 leads to:
( (
Corollary (Sample complexity of FedPG-BR). Under the same assumptions as Theorem let
<> O, we have: (i) [[Traj(s)] = 0 277 ); (ii) When a = O, we have R(Traj((c)
O ( ); (iii When K = 1, have [[[raaj(e) = 0 (++)s)
We present a straightforward comparison of the sample complexity of related works in Table Both REINFORCE and GPOMDP have sample complexity of O(1/e²) since they use stochastic gradient- based optimization. Xu et al. [19 has made a refined analysis of SVRPG to improve its sample
Table 1: Sample complexities of relevant works achieve E/ <..
SETTINGS
METHODS
COMPLEXITY
REINFORCE 39
O(1/e)
GPOMDP 40
0(1/22)
K=1
SVRPG 18
0(1/22)
SVRPG 19
0(1/6//3
FedPG-BR
0(1/65/3)
K> 1,a=0
FedPG-BR
0 (178877773
K>1,a>0
FedPG-BR
0 2733K275
4/3
2578
7

---

complexity from (11/e²) [8] to ((1/e2))) 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, a = 0, Corollary 7 (ii) implies that the total number of trajectories required by each agent is upper-bounded by (e//((//////)))) 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 rate of ( ((1/K2/// /22/)). This guaranteed improvement in sample efficiency highly desirable in practical systems with a large number of agents.
Next. for a more realistic system where an a-fraction (a > 0) of the agents are Byzantine agents, Corollary (i) assures us that the total number of trajectories required by each agent will be increased by only additive term of (/44/3 ((a4/3/55/3) /c/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 a - 0. That is, when the system ideal (a 0), our Byzantine filtering step induces no effect on the convergence.
5 Experiments
We evaluate the empirical performances of FedPG-BR with and without Byzantine agents on different RL benchmarks, including CartPole balancing [55], Lunarl ander, and the 3D) continuous locomotion control task of Half-Cheetah [56]. all experiments, we measure the performance online such that in each iteration, 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
evaluate the current policy of the server by using it to independently interact with
Performances in ideal systems with a = O. We firstly evaluate the performances of FedPG-BR in ideal systems with a = 0, i.e., no Byzantine agents. We compare FedPG-BR (K 1, 10) with vanilla policy gradient using GPOMDI and SVRPG. The results in all three tasks are plotted in Fig. The figures show that FedPG-BR (K = 1) and SVRPG perform comparably, both outperforming GPOMDP. This aligns with the results in Table D 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 BRRPG-BR is improved significantly with the federated of only K = 3 agents, and improved even further when = 10. This corroborates our theoretical insights implying that the federation of more agents (i.c., larger K) improves the sample efficiency of FedPG-BR (Section 4). and verifies the practical performance benefit offered by the participation of more agents.
CartPole-vI
LunarLander-v2
HalfCheetah-vz
3000
400
2000
300
Returrn
Returnn
10000
1000
100
-1500
Trajectorles GPOMDP
Trajectories
Trajectoress
SVRPG
FodPG.BR
FedPG-BR (K=3)
FedPC-BR BR (K=10)
Figure 1: Performance of FedPG-BR in ideal systems with 0 for the three tasks.
Performances in practical systems with a 0. Next, we investigate the impact of Byzantine agents (i.c., 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
Since GPOMDP has been repeatedly found to be comparable better than REINFORCE B 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 AA.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-agen ageet settting (K 1) as dotted-line (mean value of 10 independent runs) for reference. The figures show that for both GPOMDP and SVRPG, the 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 BedPG-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 PedPG-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-Bi -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 Fe against FedPG attack. We have discussed (Section 3.3 and shown through theoretical analysis (Section 3 that even when our Byzantine filtering strategy fails, the impact 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 v((())) using the mean of their gradients Fi, and estimate a by calculating the maximum Euclidean distance between the gradients of any two FedPG attackers as 27. Next, all FedPG attackers send the vector f4 + 3ō to the server. Recall we have discussed in Section 333 that Byzantine agent is not filtered out, its distance to the true gradient V ((()) is most 30. Therefore, tu and ā are estimated accurately, the vectors from the FedPG attackers can exert negative impact on the convergence while still evading our Byzantine filtering.
Random Noise
Random Action
Sign Flipping
3000
Rastum 2000
2000
2000
Reture
1500
1000
1000
500
Trajector
Trajectories
Trajectories
GPOMDP (K-10
SVRPG IK-10
FedPG (K-10
GRONDP (K-1)
SURAG (K=1)
FedPG-BR (K-1)
Figure 2: Performance of BBR in practical systems with > 0 for HalfCheetah. Each subplot corresponds to a different type of Byzantine failure exercised by the Byzantine agents.
CartPole-v1
LunarLander-v2
HalfCheetah-v2
300
2300
400
2000
300
nettum
-500
1300
-1000
1000
100
-1500
2030
3000
4000
8030
15000
2030
5020
10000
Trajectories
Trajectriess
Trajectories
FedPG-BR
[K=10
Figure 3: Performance of FedPG-BR -R in practical systems against FedPG attack.

---

We again use K = 10 agents, among which 3 are FedPG attackers. The results (Fig. P show that in all three tasks, even against such stong attackers with perfect knowledge of our Byzantine filtering strategy. FedPG-BR (K = B ==3) 3) still manages to significantly outperform FedPG-BR 1K= in the single-agent setting. Moreover, the performance of FedPG-BR (K 10 B 3) 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 ((a /c5/3) the sample complexity (Section 4 These results demonstrate the empirical robustness of FedPG-BA G-B even against strong attackers, hence further highlighting its practical reliability.
6 Conclusion and future work
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 FRL with respect to the number of participating agents, while accounting for faulty agents. We verify the empirical efficacy of proposed FRL framework systems with and without different types of faulty agents various RI. benchmarks.
Variance control is the key exploiting Assumption on the bounded variance of PG estimators in our filter design. As result, our framework is restricted to the variance-reduced policy gradient methods. Intuitively, 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 other federated sequential decision-making problems such as federated bandit (57-59 and federated/coollaboratve Bayesian
optimization 62), as well as other settings of collaborative multi-party MI. them with theoretically guaranteed fault tolerance.
(3 75
to equip
Acknowledgments and Disclosure of Funding
This research/project is supported by A 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.
References
[1] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv:1312.5602, 2013.
[2] Levine Sergey, Nolan Wagener, and Pieter Abbeel. Learning contact-rich manipulation skills with guided policy search. In Proceedings of the 2015 IEEE International Conference on Robotics and Automation (ICRA), Seattle, WA, USA, pages 26-30, 2015.
[3] Siqi Liu, Kay Choong See, Kee Yuan Ngiam, Leo Anthony Celi, Xingzhi Sun, and Mengling Feng. Reinforcement learning for clinical decision support critical care: comprehensive review, Journal of Medical Internet Research, 22(7))e18477, 2020.
[4] Gabriel Dulac-Arnoid, Daniel Mankowitz, and Todd Hester. Challenges of real-world reinforce- ment learning. arXiv: 1904::199..111 12901, 2019.
[5] Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tutorial, review, and perspectives open problems. arXiv:2005.01 00160,, 2020.
10

---

[6] Matthicu Komorowski, Leo A Celi, Omar Badawi, Anthony C Gordon, and A Aldo Faisal. The artificial intelligence clinician learns optimal treatment strategies for sepsis in intensive care. 2018.
Nature medicine,
[7] Rongmei Lin, Matthew D Stanley, Mohammad M Ghassemi, and Shamim Nemati. A deep deterministic policy gradient approach to medication dosing and surveillance in the icu. In 2018 40th Annual International Conference of the IEEE Engineering in Medicine and Biology Society (EMBC), pages 4927-4931 IEEE, 2018.
[8] Jakub Konečný, H Brendan McMahan, Daniel Ramage, and Peter Richtárik. Federated opti- mization: Distributed machine learning for on-device intelligence. arXiv:1610.02527, 2016.
(9) Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Ar- jun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems in federated learning. arXiv:1912.04977, 2019.
[10] Qinbin Li, Zeyi Wen, Zhaomin Wu, Sixu Hu, Naibo Wang, Yuan Li, Xu Liu, and Bingsheng He. A survey on federated learning systems: vision, hype and reality for data privacy and protection. MKKiv11977009993 2019.
[11] Qinbin Li, Zeyi Wen, and Bingsheng He. Practical federated gradient boosting decision trees. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 2020.
[12] Hankz Hankui Zhuo, Wenfeng Feng, Qian Xu, Qiang Yang, and Yufeng Lin. Federated reinforcement learning. arXiv:1901.02211 2019.
[13] Xinle Liang, Yang Liu, Tianjian Chen, Ming Liu, and Qiang Yang. Federated transfer reinforce- ment learning for autonomous driving. arXiv: 19 10.000001, 2019.
[14] Chetan Nadiger, Anil Kumar, and Sherine Abdelhak. Federated reinforcement learning for fast personalization. In 2019 IEEE Second International Conference on Artificial Intelligence and Knowledge Engineering (AIKE), pages 123-127. IEEE, 2019.
[15] Kyo Lim, Ju-Bong Kim, Joo-Seong Heo, and Youn-Hee Han. Federated reinforcement learning for training control policies multiple iot devices. Sensors, 20(5):1359, 2020.
[16] Boyi Liu, Lujia Wang, and Ming Liu. Lifelong federated reinforcement learning: a learning architecture for navigation in cloud robotic systems. IEEE Robotics and Automation Letters, (4):4555 2019.
[17] Shuai Yu, Xu Chen, Zhi Zhou, Xiaowen Gong, and Di Wu. When deep reinforcement learning meets federated learning: Intelligent multi-timescal resource management for multi-access edge computing in 5G ultra dense network. IEEE Internet of Things Journal, 2020.
[18] Matteo Papini, Damiano Binaghi, Giuseppe Canonaco, Matteo Pirotta, and Marcello Restelli, Stochastic variance-reduced policy gradient. arXiv:1806.0555 05618. 2018
[19] Pan Xu, Felicia Gao, and Quanquan Gu. An improved convergence analysis of stochastic variance-reduced policy gradient. In Uncertainty in Artificial Intelligence, pages 541-551. PMLR, 2020.
[20] Yulong Cao, Chaowei Xiao, Benjamin Cyr, Yimeng Zhou, Won Park, Sara Rampazzi, Qi Alfred Chen, Kevin Fu, and Z Morley Mao. Adversarial sensor attack on lidar-based perception in autonomous driving. In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, pages 2267-2281, 2019.
[21] LESLIE Lamport, ROBERT SHOSTAK, and MARSHALL PEASE. The byzantine generals problem. ACM Transactions Programming Languages and Systems, 4(3):382 401, 1982.
[22] Nancy A. Lynch. Distributed Algorithms. Morgan Kaufmann Publishers Inc., San Francisco,
CA, USA, 1996. ISBN 9780080504704.
[23] Miguel Castro and Barbara Liskov. Practical byzantine fault tolerance. In OSDI, volume 99, pages 173-186, 1999.

---

[24]
Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Chal- lenges, methods, and future directions. IEEE Signal Processing Magazine, 37(3):50-60, 2020.
[25] Augustin Cauchy, Méthode générale pour la résolution des systemes d' d'équations simultanées. Comp. Rend. Sci. Paris, 25(184)) 538, 1847.
[26] Yurii Nesterov. Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media, 2013.
[27] Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathematical statistics, pages 400-407, 1951.
[28] Léon Bottou and Yann Cun. Large scale online learning. Advances in neural information processing systems, 16:217-224, 2003.
[29] Arkadi Semenovich Nemirovsky and David Borisovich Yudin. Problem complexity and method efficiency in optimization. 1983.
[30] Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances in neural information processing systems, pages 315-323, 2013.
[31] Lin Xiao and Tong Zhang. proximal stochastic gradient method with progressive variance reduction. SIAM Journal on Optimization, (((4):207720075 2014.
[32] Zeyuan Allen-Zhu and Elad Hazan. Variance reduction for faster non-convex optimization. In International conference on machine learning, pages 699-707, 2016.
[33] Sashank J Reddi, Ahmed Hefny, Suvrit Sra, Barnabas Poczos, and Alex Smola. Stochastic variance reduction for nonconvex optimization. In International conference on machine learning, pages 314-323, 2016.
[34] Lihua Lei and Michael Jordan. Less than a single pass: Stochastically controlled stochastic gradient method.
2016.
[35] Lihua Lei, Cheng Ju, Jianbo Chen, and Michael I Jordan. Non-convex finite-sum optimization via scsg methods. In Advances in Neural Information Processing Systems, pages 2017.
[36] Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
[37] John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. International conference on machine learning, pages 1889-1897, 2015.
[38] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. 7XXiv:1707.063477 2017.
[39] Ronald J Williams. Simple statistical fradient algorithms for connectionist reinforce- ment learning. Machine learning, 8(3-4):229-256, 1992.
[40] Jonathan Baxter and Peter Bartlett. Infinite-horizon volicy-gradies estimation. Journal of Artificial Intelligence Research, 15:319-350, 2001.
[41] Simon S Du, Jianshu Chen, Lihong Li, Lin Xiao, and Dengyong Zhou. Stochastic variance reduction methods for policy evaluation. arXiv:1702.079.0 2017.
[42] Zilun Peng, Ahmed Touati, Pascal Vincent, and Doina Precup. Svrg for policy evaluation with fewer gradient evaluations. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20, pages 2697-2703. International Joint Conferences on Artificial Intelligence Organization, 2020.
[43] Tianbing Xu, Qiang Liu, and Jian Peng. Stochastic variance reduction for policy gradient estimation. 1tXiv:1710.06000 2017.
12

---

[44] Peva Blanchard, EI Mahdi EI Mhamdi, Rachid Guerraoui, and Julien Stainer. Machine learning with adversaries; Byzantine tolerant gradient descent. Proceedings of the 31st International Conference Neural Information Processing Systems, pages 118-128, 2017.
[45] Dong Yin, Yudong Chen, Kannan Ramchandran, and Peter Bartlett. Byzantine-robust distributed learning: Towards optimal statistical rates. arXiv: 1 1803.01498, 2018.
[46] Dan Alistarh, Zeyuan Allen-Zhu, and Jerry Li. Byzantine stochastic gradient descent. In Advances in Neural Information Processing Systems, pages 6613-4623, 2018.
[47] Gilad Baruch, Moran Baruch, and Yoav Goldberg. A little is enough:
Circumventing defenses for distributed learning. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL httptttt///occeediiiii htwp:oceeddinnnn.niii.e....... www.nneurruuccueooooo cccprppp.cc/paper/2015 Fi11/ccdcs11006cdd6bbbbtttbobbld Paper pdf
[48] Prashant Khanduri, Saikiran Bulusu, Pranay Sharma, and Pramod K Varshney, Byzantine resilient non-convex svig with distributed batch gradient computations. arXiv:1912004531, 2019.
[49] Zeyuan Allen-Zhu, Faeze Ebrahimian, Jerry Li, and Dan Alistarh. Byzantine-resilient non- convex stochastic gradient descent. urXiv:2012.14366 2020.
[50] Cong Xie, Sanmi Koyejo, and Indranil Gupta. Zeno: Distributed stochastic gradient descent with suspicion-basee bassdd fault-tolerance. In International Conference Machine Learning, pages 1893-6901. PMLR, 2019.
[51] Alberto Maria Metelli, Matteo Papini, Francesco Faccio, and Marcello Restelli. Policy opti- mization via importance sampling. In Advances Neurul Information Processing Systems, pages 5442-5454, 2018.
[52] Matteo Pirotta, Marcello Restelli, and Luca Bascetta. Policy gradient in lipschitz markov decision processes. Machine Learning, 100(2-3):255--22 283, 2015.
[53] Zeyuan Ahu and Elad Hazan. Variance reduction for faster non-convex optimization. In International conference on machine learning, pages 699-707. PMLR, 2016.
[54] Samuel Albanie. Euclidean distance matrix trick. Technical report, 2019. URL https
o.. www.uukkaaa////aaaaaaaaaa noteee///o/e//eeeeeeeeeeeeeeeeee http///eee/eeeeeennnnneeee waaellldea_ddistannee trick. .dd
[55] Andrew G Barto, Richard S Sutton, and Charles W Anderson. Neuronlike adaptive elements that can solve difficult learning control problems. IEEE transactions on systems, man, and cybernetics, (5):834 15:6834846, 1983.
[56] Yan Duan, Xi Chen, Rein Houthooft, John Schulman, and Pieter Abbeel. Benchmarking deep reinforcement learning for continuous control. In International Conference on Machine Learning, pages 1329-1338, 2016.
[57] Abhimanyu Dubey and Alex Pentland. Differrentially-rriaaee federated linear bandits. In Proc. NeurlPS, 2020.
[58] Chengshuai Shi, Cong Shen, and Jing Yang. Federated multi-armon armtid bandits with personalization. In Proc. AISTATS, pages 2917-2925. PMLR, 2021.
[59] Zhaowei Zhu, Jingxuan Zhu, Ji Liu, and Yang Liu. Federated bandit: A gossiping approach. In Abstract Proceedings of the 2021 ACM SICMETRICS//temation Conference on Measurement and Modeling of Computer Systems, pages 3-4, 2021.
[60] Zhongxiang Dai, Bryan Kian Hsiang Low, and Patrick Jaillet. Federated Bayesian optimization via Thompson sampling. In Proc. NeurlPS, 2020.
[61] Zhongxiang Dai, Bryan Kian Hsiang Low, and Patrick Jaillet. Differentially private federated Bayesian optimization with distributed exploration. In Proc. NeurIPS, 2021.
13

---

[62] Rachael Hwee Ling Sim, Yehong Zhang, Bryan Kian Hsiang Low, and Patrick Jaillet. Col- laborative Bayesian optimization with fair regret. In Proc. ICML, pages 9691-9701, PMLR. 2021.
[63] Xinyi Xu, Lingjuan Lyu, Xingjun Ma Chenglin Miao, Chuan-Sheng Foo, and Bryan Kian Hsiang Low. Gradient driven rewards to guarantee faireess in collaborative machine learning. In Proc. NeurlPS, 2021.
[64] Xinyi Xu, Zhaoxuan Wu, Chuan-Shena Foo, and Bryan Kian Hsiang Low. Validation free and replication robust volume-based data valuation. In Proc. NeurIPS, 2021.
[65] Trong Nghia Hoang, Shenda Hong, Cao Xiao, Bryan Kian Hsiang Low, and Jimeng Sun. Aid: Active distillation machine leverage pre-trained black-box models in private data settings, In Proc. The WheConn, pages 3569-3581, 2021.
[66] Thanh Chi Lam, Nghia Hoang, Bryan Kian Hsiang Low, and Patrick Jaillet. Model fusion for personalized learning. Proc. ICML., pages 1948-5955 PMLR, 2021.
[67] Rachael Hwee Ling Sim, Yehong Zhang, Mun Choon Chan, and Bryan Kian Hsiang Low. Collaborative machine learning with incentive-aware model rewards. In Proc. ICML, pages 8927-8936. PMLR, 2020.
[68] Nghia Hoang, Thanh Lam, Bryan Kian Hsiang Low, and Patrick Jaillet. Learning task-agnostic embedding of multiple black-box experts for multi-task model fusion. In Proc. ICML,, pages 4282-4292. PMLR, 2020.
[69] Ruofei Ouyang and Bryan Kian Hsiang Low. Gaussian process decentralized data fusion meets transfer learning in large-scale distributed cooperative perception. Autonomous Robots, 44(3): 359-376 2020.
[70] Minh Hoang, Nghia Hoang, Bryan Kian Hsiang Low, and Carleton Kingsford. Collective model fusion for multiple black-box experts. Proc. ICML, pages 2742-2750. PMLR, 2019.
[71] Trong Nghia Hoang, Quang Minh Hoang, Bryan Kian Hsiang Low, and Jonathan How. Col- lective online learning of Gaussian processes in massive multi-agent systems. In Proc. AAAI, volume 33, pages 7850-7857, 2019.
[72] Ruofei Ouyang and Bryan Kian Hsiang Low. Gaussian process decentralized data fusion meets transfer learning large-scale distributed cooperative perception. Proc. AAAI, 2018.
[73] Jie Chen, Bryan Kian Hsiang Low, Yujian Yao, and Patrick Jaillet. Gaussian process decen- tralized data fusion and active sensing for spatiotemporal traffic modeling and prediction in mobility-on-demaal systems. IEEE Transactions on Automation Science and Engineering, 12 (3):901-921, 2015.
[74] Jie Chen, Bryan Kian Hsiang Low, and Colin Keng-Yan Tan. Gaussian process-based de- centralized data fusion and active sensing for mobility-on mobiliy--on-demand -n-demnnd system. In Proc. RSS, 2013.
[75] Jie Chen, Bryan Kian Hsiang Low, Colin Keng- Yan Tan, Ali Oran, Patrick Jaillet, John M Dolan, and Gaurav Sukhatme. Decentralized data fusion and active sensing with mobile sensors for modeling and predicting spatiotemporal traffic phenomena. In Proc. UAI, 2012.
[76] losif Pinelis. Optimum bounds for the distributions of martingales banach spaces. The Annals of Probability, pages 1679-1706, 1994.
[77] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. 11Xiv:1412.6980, 2014.
14

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section 6
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions of all theoretical results? [Yes] See Theorem 6
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix and Appendix fCr complete proofs of Theorem and Corollary respectively.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main ex- perimental results (either in the supplemental material or as URL)? [Yes] The code and instructions to reproduce the results are given in our github repository: fatatr-at-aaaa//yzatiineeee -ewpetttee---eeeeeeeee-e-----e
https://github.
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes] See S and Appendix F
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [Yes) 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. We report the mean of the 10 independent runs with 90% bootstrap confidence intervals.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Appendix F22
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes] See the github page given above for
details.
(c) Did you include any assets either in the supplemental material See the github page given above for details.
URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A] See the github page given above for details.
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "cGt_C36r6R", "reviewer": "Reviewer_Y3yr", "summary": "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.\n\nI 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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The main idea of the paper seems to be to cluster good agents and bad agents using some form of variance based clustering. This idea is pretty intuitive,  and the paper is well written. Overall, I think this paper does a good job of advancing federated RL. However, I do have some questions:\n\n1. In the situation when the agents are exploring, that is in the early stage of learning, it is possible that some agents will find very different (anomalous) outcomes than others. Not in all cases are those outcomes bad. What happens here?\n2. Similarly, what is there is diversity in the agent experience, and this leads to seemingly anomalous outcomes, which are then dominated out by the others that cluster together.\n\nIt seems that if the above considerations are true, then the federated RL agent will end up ignoring critical outliers or learning experiences. Is there a way the authors could evaluate against this? I did not see discussion about the exploration phase in the experiments. \n\nThe sample complexity guarantees look good, but again the thing that confuses me with those guarantees is what is the role of exploration policy? Obviously a bad exploration policy will destroy the guarantees. Are these upper bounds? I would have liked to see some more insights into what the theoretical results mean.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors do not seem to discuss societal impacts. Although the paper is theoretical and restricted to benchmark, it is true that federated RL will probably be used in a server node setting with many agents. Some of whom will be diverse and behave differently. It is important to know whether the idea of variance based clustering and rejecting of Byzantine agents based on that will hold in this case. Although I do not think that this is a major issue for this paper as is since its not focused on applications  currently.", "review_text": "", "extra_scores": {"ethical_concerns": "No major concerns", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "bOh3knx4VaV", "reviewer": "Reviewer_Ap1M", "summary": "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. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "It’s nice to see a fault-tolerant algorithm for FRL that is based on a theoretical guarantee. The algorithm can support up to (less than) 50% of agents being malicious which should be sufficient for real-world use cases. The empirical demonstrates the sample complexity does not degrade too much even some agents are malicious. \n\nAlthough this seems to be working well. I question whether the problem setting is realistic in the real world. All the agents are assumed to have identical MDP and transition probability, which seems to be very similar to a distributed RL training setting. If the environments are all the same among all the agents, why do we need to do federated learning, we can just train everything in a centralized fashion. Federated RL often contains some kind of data heterogeneity, where either the transition probability is different or the MDP differs slightly. Would the algorithm still work well if the agents are heterogeneous (e.g. have different transition functions)? Maybe, in this case, some of the good gradients would be quite different gradients from other agents. Can you provide more insights here?\n\nIn the experiment section, you selected three attack methods: random noise, random action, flip gradient. Although these methods seem to be valid, more sophisticated attacks should be considered to support the effectiveness of the algorithm. Some examples are: [1][2]. These attack may not requires large weight variance but be able to find specific values that would degrade the performance of the RL policy. This would even worst if the malicious agent collude when optimizing for their adversarial weights.\n\nThe aggregation method seems to require a pairwise computation among the weights of all the agents which may result in O(n^2) compared to O(n) in FedAVG. This may limits the scalability of the system. Is this true? Or is there ways to mitigate this?\n\n[1] Fang, Minghong, et al. “Local Model Poisoning Attacks to Byzantine-Robust Federated Learning”\n[2] Bhagoji, Arjun Nitin, et al. \"Analyzing federated learning through an adversarial lens\" \n[3] Bagdasaryan, Eugene, et al. \"How to backdoor federated learning\"\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See the main review for the suggestion for limitations.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "CZjSq6UifRB", "reviewer": "Reviewer_CftT", "summary": "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.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, the presentation of this work is clear and easy to read.\n\nMy main concern is regarding novelty. Without the fault-tolerance aspects, the algorithm and analysis would be very similar to that of [Xu et al 2020]. So the incorporation of fault-tolerance in terms of Algorithm 1.1 (ScsPG-Aggregate) is the only aspect that makes it \"Federated\". Other aspects of FL, such as heterogeneity of agents are not covered here.\n\nAlgorithm 1.1, however, seems quite similar to the works by Alistarh et al and Khanduri et al. I wonder whether the author can elaborate on the novelty introduced in this work? Perhaps there are additional challenges involved in integrating these works that I missed?\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "Af3OZfJITV", "reviewer": "Reviewer_pSwe", "summary": "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper proposes the first FRL method with formal convergence and robustness guarantees, which I think is a significant contribution to the community. The theoretical analysis seems to be correct, and the experiment results do support the theory. This paper is in generally well-written and easy to follow. I am not very familar with the related work, so it is hard to justify the novelty of the proposed idea. But this paper provides explanations about technical challenges that can distinguish this paper from prior works.\n\nMy main concern is that, although the analysis makes intuitive sense, is mainly built on some assumptions which might not be realistic. For example, assumption 2 is important to the algorithm and the guarantees, and the variance bound $\\sigma$ is also used as a hyperparameter in Algorithm 1.1. How can we know the value of $\\sigma$ in practice? How possible is that $\\sigma$ exists and is not too large? If I am understanding it correctly, the gradient estimator lives in a high-dimensional space, and this assumption should hold for any trajectory generated from the environment given a certain policy, so $\\sigma$ can be very large, which also makes the sample complexity high.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The experiment environments used in this paper is relatively simple, so it is not clear how the proposed algorithm scales to large environments and a large number of agents.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers in general agree that the paper considers an interesting new setting and this is one of the very first works that consider federated RL with theoretical guarantees, which make the reviewers in general lean towards an acceptance. But reviewers still have some concerns on the novelty of the proposed approach and whether or not the assumptions are realistic. 
Decision: Accept (Poster)