Global Convergence Guarantees for Federated Policy Gradient Methods with Adversaries
Authors: Swetha Ganesh
Jiayu Chen
Gugan Thoppe
Vaneet Aggarwal
Venue: Accepted by TMLR ()

Abstract: Federated Reinforcement Learning (FRL) allows multiple agents to collaboratively build a decision making policy without sharing raw trajectories. However, if a small fraction of these agents are adversarial, it can lead to catastrophic results. We propose a policy gradient based approach that is robust to adversarial agents which can send arbitrary values to the server. Under this setting, our results form the first global convergence guarantees with general parametrization. These results demonstrate resilience with adversaries, while achieving optimal sample complexity of order $\tilde{\mathcal{O}}\left( \frac{1}{N\epsilon^2} \left( 1+ \frac{f^2}{N}\right)\right)$, where $N$ is the total number of agents and $f < N/2$ is the number of adversarial agents.

Published in Transactions on Machine Learning Research (11/2024)
Global Convergence Guarantees for Federated Policy Gradi- ent Methods with Adversaries
Swetha Ganesh
swethaganesh @visc....
Indian Institute of Science (IISe), Bengaluru 560012, India Purdue Universily, West Lafayelte, IN, 47907, USA
Jiayu Chen
jiayuc2 cmaa edu
Carnegie Mellon University (CMU), Pillsburgh, PA, 15289, USA
Gugan Thoppe
gthoppeWissc.oo
Indian Institute of Science (1ISe), Bengakuru 560012, India
Vancet Aggarwal
vaneet&yyrruee.. edu
Purdue University, West Lafayelte, IN, 47907, USA
Reviewed on OpenReview: https: openreview. net/ forum? id- EaOLrPOR
Abstract
Federated Reinforcement Learning (FRL) allows multiple agents to collaboratively build decision making policy without sharing raw trajectories. However, if small fraction of these agents are adversarial, it can load to catastrophic results. We propose policy gradient based approach that robust to adversarial agents which can send arbitrary values the server. Under this setting, our results form the first global convergence guarantees with general paramotrization. These results demonstrate resilience with adversarics, while achieving optimal sample complexity of order ① N2
where N is the total number of agents and f < N/2 is the number of adversarial agents.
1 Introduction
Reinforccment Learning (RL) encompasses a category of challenges in which an agent iteratively selects ac- tions and acquires rewards within an unfamiliar environment, all while striving to maximize the cumulative rewards. The Policy Gradient (PG) based approaches serve as an effective means of addressing RT. prob- diverse range of complex domains, such as game playing lems, demonstrating its successful application transportation (Kiran et al. 2021 Al-Abbasi al. 2019).
(Schrittwieser et al. 2020 Bonjour al. 2022).
robotics (Abeyruwan el al. 2023 Chen et al. 2023b). telesurgery GGonalee et al. 2023), network scheduling
(Geg et al. 2020 Chen et al. 2023a) and healthcare (Yu et al. 2021
RL applications often demand extensive training data to attain the desired accuracy level. Parallelizing train- ing can significantly expedite this process, with one approach being Federated Reinforcement Learning (FRL) (Jin et al. 2022]. : In FRI, workers exchange locally trained models instcad of raw data, ensuring efficient communication and data privacy. While Federated Learning (FL) is typically associaled with supervised learning (Hosseinalipour al.) 2020), recent developments have extended its application to FRL, enabling multiple agents to collaboratively construct decision-making policios without sharing raw trajectories.
Distributed systems, including FRL, face vulnerabilities such as random failures or adversarial allacks. These issues may arise from agents' arbitrary behavior due to hardware glitches, inaccurate training data, or deliberate malicious attacks. the case of attacks, the possibility cxists that attackers possess extensive knowledge and can collaborate with others maximize disruption. These scenarios fall under the Byzantine failure model, the most rigorous fault framework in distributed computing, where minority of agents

---

Published in Transactions on Machine Learning Research (11/2024)
act arbitrarily and potentially maliciously with the aim of disrupting the system's convergence (Lamport et al. 1982j. In this paper, we investigate how adversaries affect the overall convergence of federated policy gradient methods.
Related Works:
1. Global Convergence of Policy Gradient Approaches: Recently, there has been an incrcasing re- search emphasis on exploring the global convergence of PG-based methods, going beyond the well-recognized convergence to first-order stationary policies. In (Agarwal et al.) 2021a), fairly comprehensive characteri- zation of global convergence for PG approaches is provided. Additionally, other significant studies on sample complexity for global convergence include (Wang et al., 2019 Xu al.) 2019 Liu et al.) 2020; Masiha et al.
2022 Fatkhullin et al. 2023 Mondal & Aggarwal 2024). We note that both (Fatkhullin el al., 2023) and
(Mondal & Aggarwal 2024) achieve near-optimal sample complexity of Ó(1e²). In the absence of adversarial
elements, we use the work in (Fatkhullin et al.
2023 as a foundational reference for this paper.
2. Federated Reinforcement Learning: Federated reinforcement learning has been explored in various setups, including tabular RL (Agarwal et al.
2021b Jin et al.) 2022 Khodadadian et al. 2022). control
tasks (Wang et al. 2023b). and value-function based algorithms (Wang et al.; 2023a Xic & Song 2023
showcasing linear speedup. In the case of policy-gradient based algorithms, it's evident that linear speedup is achievable, as each agent's 's collected trajectories can be parallelized (Lan et al. 2023 ). Nevertheless, achieving
speedup becomes challenging with increasing nodes when adversaries are introduced, and this paper focuses on addressing this key issue.
3. Byzantine Fault Tolerance in Federated Learning: A significant body of research has focused distributed Stochastic Gradient Descent (SGD) with adversaries, with various works such as (Chen et al.
2017 EI Mhamdi et al.)
2018 Yin et al.]
2018 Xie et al., 2018 Alistarh et al. 2018 Diakonikolas et al. 2019
Allen- Zhu et al. 2020
Prasad et al. 2020). Most studies typically employ an aggregator to merge gradient ostimates from workers while filtoring out unreliable ones (Xie et al., 2018 Chen ct al. 2017
Mhamdi
ett al. 2018 Yin et al.) 2018). However, many of these approaches make stringent assumptions regarding gradient noise, making it challenging to compare different aggregators. Notably, (Farhadkhani et al.) 2002))
introduces the concept of (f, A)resiiitt averaging, demonstrating that several well-known aggregators can be seen special instances of this idea. In our work, we explore (f, A)-averaging for combining policy gradient estimates from workers.
4. Byzantine Fault Tolerance in Distributed Reinforcement Learning: We note that [aan et al.
2021) introduces an SVRG-PG based algorithm with a local sample complexity bound of O N279g078 where N represents the number of workers and denotes the fraction of adversarial workers. However, they do not provide global convergence guarantees and require that the variance of importance sampling weights is upper bounded, which is unverifiable in practice. Moreover, their result is sub-optimal in N, which fails to provide linear speedup even when no adversaries are present. They additionally perform variance reduction with samples drawn from the central server, assuming its reliability. This is not generally allowed under lederated learning since this could lead to data leakage and privacy issues (Kairouz et al., 2021). In contrast, our study centers on the global convergence of federated RL while keeping the server process minimal, aggregating different gradients using (f, A)rresilient aggregator (Farhadkhani et al. 2022 without requiring additional samples at server.
1 + 2473
4/3
Distributed RL algorithms with adversaries have been studied for episodic tabular MDPs in (Chen et al. 2023c Another line of works focus on empirical evaluations of Federated RL with adversaries (Lin &
Ling 2022 Rjoub et al. 2022 Zhang et al. 2022 Xu et al. 2022) and do not provide sample complexity
guarantees.
Main Contributions: In this paper, we address the following fundamental question:
What is the influence of adversaries on the global convergence sample complerity of Federated Reinforcement Learning (FRI))
To lackle this question, we introduce Resilient Normalized Hessian Aided Recursive Policy Gradient (Res- NHARPG). NHARPG integrates resilient averaging with variance-reduced policy gradient. Resilient
2

---

Published in Transactions on Machine Learning Research (11/2024)
averaging combines gradient estimates in manner that minimizes the impact of adversaries the algo- rithm's performance, while variance reduction accelerates convergence. Our main result. is that the global sample complexities of Res-NHARPG with (f, averaging is O (1 log (+) ( + X² log(N))). Here, N de- notes the number of workers and f < N/2 denotes the number of faulty workers. The significance of our contributions can be summarized as follows.
This paper provides the first global convergence sample complexity findings for federated policy gradient-baser approaches with general parametrization in the presence of adversaries.
We derive the sample complexity for Res-NHARPG for a broad class of aggregators, called (f.
aggregators (Farhadkhani et al. 2022). This includes several popular methods such as Krum
Blan-
chard et al. 2017), Co-ordinate Wise Median (CWMed) and Co-ordinate Wise Trimmed Mean
(CWTM) (Yin et al. 2018 Minimum Diameter Averaging (MDA) (El Mhanni et al. 2018
Geo-
metric Median (Chen et al. 2017 and Mean around Medians (MeaMed) (Xie et al.) 2018
3. We observe that for certain choices of aggregators (MDA, CWTM, MeaMed), our proposed approach achieves the optimal sample complexity of δ N (1+ f)), where Ô ignores logarithmic factors (see Remark 4.7 In particular, this implies linear speedup when O(N)), where 8 S 0.5.
We also provide experimental results showing the effectiveness of our algorithm under popular adversarial attacks (random noise, random action and sign flipping) under different environments (Cartpole-vl from OpenAl Gym and unvertedPendulumm-e HalfCheetah, Hopper, Inverted Double Pendulum and Walker from MuJoCo).
We obtain a significant improvement over the original bounds for (J, A)rrssiitl averaging in the context of stochastic optimization (Farhadkhani et al. 2022). We achieve this by showing that our policy gradient update direction has certain desirable properties that allows us to utilize sharper concentration inequalities, instead of simple union-bound (sec Section 5
2 Problem Setup
We consider a discounted Markov decision process defined by the tuple (S,A, r. 7), where S denotes the state space, A denotes the action space, P(s'(s,a) a) is the probability of transitioning from state s to state s' after taking action a; 7 E (0,1) is the discount factor, and r S A - [-R, R] the reward function of and a. At each time i, the agent is the current state 8, S and takes action o, A based on a possibly stochastic policy π S + P(A), i.e., a T(-[s:). The agent then obtains reward ra r(st, at). The sequence of state-action pairs = (so, 0o, 81, 82, ".) is called trajectory.
We consider a parameler-serrer architecture with a trusted central server and N distributed workers or agents, labelled 1,2..... .N. We assume each agent is given an independent and identical copy of the MDP. Among these N agents, we assume that f are adversarial, with these agents providing any arbitrary information (such adversaries are also called Byzantine adversaries). The aim is for the agents to collaborate using& federated policy gradient based approach to come up with a policy æ that maximizes the value function, i.e.
max J(T) B Bxo-pparrss((())))eee- P(
r'r
(1)
where the initial state so is drawn from some distribution p. In practice the state and action spaces are typically very large and thus the policy is parameterized by some 0 E Rd. The problem in equation [ now becomes finding 0 using a collaborative approach among agents that maximizes J((z). However since this maximization problem is usually nonconvex, it is difficult to find the globally optimal policy.
Let J(Ø) denote J(mp) henceforth and let J' max, J(r). The optimization problem equation can be solved using the Policy Gradient (PG) approach at each agent, where the gradient VJ(()) is estimated through sampling trajectories at that agent and observing rewards collected and then used in gradient ascent.
3

---

Published in Transactions on Machine Learning Research (11/2024)
Using the current estimate of the parameter 8, we aim to find VJ(0) using the sampled trajectories at the agent. Let G C {1,2, ... ",,,,.,,NN ,N be the set of good workers of size N - For n É 9, let [n) (n) .a (n) ) ( be a trajectory sampled by agent n under policy va of length H 11111.
x(m) (000) d
(n) ( be the sample return. We denote the distribution of trajectory т and R(((1)) _ r
of length H induced by policy mo with initial state distribution p as Po (r(0), which can be expressed Pp (T(0) p(su) II== (a(an (n) P(s (sh, an). The gradient of the truncated expected return function (0) = Bermpaae (19
[R(T)] can then be written as
VJH(0) = J R(T)Vp) (+)0)dr J. R(T)
(T P (T|0) Pp (T(0)dr Vogg (T(0))
REINFORCE Williams 1992) and GPOMDP [axter & Bartlett,
2001 are commonly used estimators for the gradient (0)). In this work, we will be using the GPOMDP estimator given below:
.) ,(
Σ
Σ
Ve log log (o ((o( s/m)) ( 7 (((()/ (1) ).
(2)
h=0
1=0
The above expression is an unbiased stochastic estimate of (#) [axttrr & Bartlett, 2001
3 Proposed Algorithm
In Res-NHARPG (given in Algorithm D. each good agent n E G computes variance-reducel gradient estimator, d("), in a recursive manner as follows:
101= - -0111m))dd (d + B(A!")) ((0) 62-1)) + mo((T")) (x) (z),
(3)
where } denotes suitable choice of parameters, B(r, =
V² 0) with ("r(s,,,,)) log mo(a,, st), (x) P/ (.1m0)), f(() 1/d (-TT)()) and 0(r)) qi (m)
((T, 0) Em
0, +
(1-9) (1-g:") "l 0 where (( is sampled from 4((0, 1]).
The update in equation is inspired by the N- HARPG algorithm in (ratkhullin et al. 2023) since help
Algorithm 1 Resilient Normalized Hessian- Re- cursive Policy Gradient (Res-NHARPG)
its use of Hessian information was shown achieve sample complexity of order O (+), which is currently the state of the art. The algorithm draws inspiration from the STORM variance reduc-
1: Input: l, 0,, do. T, {mhh11 tnhe21
2: for t= 1,..., T-..,T-I. do
3: Server broadcasts O, to agents
4: Agent update
tion technique [Cutkosky & Orabona 2019), but in- stead relying on the difference between successive
5:
for each agent n E [N] do in parallel
6:
q ~ ~U([O 1])
(n)
stochastic gradients, it incorporates second-order in- formation (Tran& & Cutkosky 2022). This approach removes the dependency on Importance Sampling (IS) and circumvents the need for unverifiable as- sumptions to bound the IS weights (Fatkhullin et al.) 2023). In Step 10 of Algorithm [ the update di- rection d(") is computed by adding second-order correction, (1 - - (as defined in Step 9), to the momentum stochastic gradient (1 (1-n)d )dd + n=((T!")) (n) ,0,). The uniform sampling procedure in Steps 6-9 ensures that v²") is an unbiased estimator closcly resembling the term used in the original STORM method (Cutkosky &
0.0) %: 0. + qt )0))
(n)
T ~ p/" (:(TT))) ((n) ~ p( 1 (T
8:
(n) B(+(") ((")) 0-11)
9:
e d.m) = (1 - (d( + (m) + m
10:
11:
end for
12:
Server Update
d, = F(d!") (1) ... of (N)
13:
14:
o = 0g + Yt TTl.l
de
15: end for
16: return 0r
of (H.)-V.JJH
Orabona 2019
4

---

Published in Transactions on Machine Learning Research (11/2024)
In Step 9, we do not need to compute and store B but only term of form B(T, which can be easily computed via automatic differentiation of the scalar quantity (g(T,0), 0), u) (Fatkhullin et al. 2023 This allows us to exploit curvature information from the policy Hessian without compromising the per-iteration computation cost.
A gggeggation at the Server: At each iteration i, a good agent always sends its computed estimate back the server, while an adversarial agent may return any arbitrary vector. At the server, we aim mitigate the effect of adversaries is by using aggregator to combine estimates from all agents such that bad estimates are filtered out.
The server receives d!"), nt = 1,2, ... ,N and uses the following update
d, = F(d (1) d.
M) and
(4)
de
0% = 0% +
(5)
||d.l
where F is aggregator and 7 > 0 is the stepsize. For the robust aggregator F, consider (f, A)-avergging introduced in (Farhadkhani et al., 2022) as this family of aggregators encompasses several popularly used methods in Byzantine literalure. The aggregator function aims to make our algorithm resilient to adversaries. The last step of the algorithm (Step 14) uses the direction de with normalization to update the parameter l++1-
We now define A)r-esiill averaging as (Farhadkhani et al. 2022) below for ease of reference, where f N/2. We note that f N/2 is the optimal breakdown point as no aggregator can possibly tolerate J N/2 adversaries (Karimireddy et al. 2020).
Definition 3.1 ((f, A)-Resilient averaging). For f < N/2 and real value À 2 0, an aggregation rule F is called (J, A)-resilient averuging if for any collection of N vectors 21,...: 2N, and any set S (1...., N) of size N- f,
| [F........ .N.....,,NN............... IN) Fzll S À max | xyll
t.jg
where nig = 1 T0T Eieg Hi, and | is the cardinality of g.
Several well-known aggregators such as Krum, CWMed, CWTM, MDA, GM and MeaMed are known to be (f, A)-eesiieen. We note that for these aggregators, as function of f is summarized in Table [ where these values are from (Farhadkhani et al. 2022). As a result, our unified analysis provides guarantees for all the above mentioned methods. We define and discuss these aggregators Appendix B
4 Assumptions and Main Result
In this section, we first introduce few notations and list the assumptions used for our results. Let do e P(S) denote the state visitation measure induced by policy Ta and initial distribution p defined as
d (8) = B) spoup
P(s: = 8|80, me)
(6)
1=0
and
be the statc-action visitation measure induced by πe.
We assume that the policy parametrization zo is good function approximator, which is measured by the transferred compatible function approzimation error. This assumption is commonly used in obtaining global bounds with parametrization [Agarwal et al. 2021a Liu et al. 2020).
Assumption 4.1. For any E Rdd the transferred compatible function approcimation error, Ly (w 0), satisfies
Ly- (w:: 0) B(Ka)aur (AT - () T To logss < Ebias:
(7)
5

---

Published in Transactions on Machine Learning Research (11/2024)
Aggregator
Computational Complexity
À
Sample Complexity Res-NHARPG
Order
Optimal?
MDA
NP-Hard
N-1
2f
px
log (1)
N
+
log(N)
No
Yes
CWTM
((dN)
N-
0
pz
log (t)
+
[=a=llu(())
N2
Yes
MeaMed
((dN)
A
o
log (t)
1's"log(M)
Yes
N-J
N
N22
CWMed
(ddN)
2 2(N-n
o
log (c)
[ A²log([))
No
Krum
@(dN3)
1+
N-25
N-J
0
log (:)
N-27
N-f
log(())
No
GM
OddN (og"ee/)))) (1)
1+
NIN-211
(N-1)2
log (t)
N
+
N-27 log(N))
N
No
the above table, = min(vd, 2 2 f)- The computational complexity the aggregator, and the order optimality of sample complexity (in terms of f, _N, and c) are also mentioned in the Table. Remark 4.8 provides discussion on the sample complexity bounds. (1) We note that while GM is convex optimization with no closed-form solution, (1 --approxiiate solution be found in O(dN log" (NV/c) time (Cohen et al. 2016).
Table 1:
where A (s. is the advantage function of policy To (s. a), v*, a) = dz (s) x (als) is the stato-action distribution induced by an optimal policy x² that maximizes J(x), and we is the exact. Natural Policy Gradient update direction at
Ebias captures the parametrization capacity of ne. For wo using the softmax paramotrization, have Sbias = 0 (Agarwal et al., 2021a). When To is restricted parametrization, which may not contain all stochastic policies, we have Ehins
O. It is known that Ebas is very small when rich neural parametrizations
are used (Wang et al. 2019).
Assumption 4.2. For all 0 E Rdd the Fisher information matrix induced by policy me and initial state distribution p satisfics
Fp(0) = (sa)mo [Volog (o(as) log ] > pr Ia.
for some constant μP > 0.
Assumption 4.3. There exists o > such that g(t, 0) defined in equation satisfies () 0)]1 o², for all and 7 ~ p (-10). Assumption 4.4.
Vo (a))) < G1 for any 0 and (8, ESXA.
V log ne, (als) V lo (a|s)
G2|l0 02ll for any 0,, Og and (s, ESXA.
4.4 We would like to highlight that all the assumptions used in this work are commonly found in PG literature. We elaborate more on these assumptions below.
Comments on Assumptions 4.2 4.2.4.
Assumption requires that the eigenvalues the Fisher information matrix can be bounded from below.
This assumption is also known as the Fisher non-degenerate policy assumption and commonly used
obtaining global complexity bounds for PG based methods [Liu et al. 2020 Zhang al. 2021 Bai et al.
2022
Fatkhullin et al. 2023
Assumption
4.3 requires that the variance of the PG estimator must be bounded and 4.4 requires that the
score function is bounded and Lipschitz continuous. Both assumptions are widely used in the analysis of PG
based mothods [Liu et al. 2020 Agarwal et al. 2021a Papini et al. 2018 Xu et al. 2020 2019
Fatkhullin
et al.
2023
Assumptions 4.2 4.4 were shown to hold for various examples recently including Gaussian policies with
linearly parameterized means with clipping (Liu et al. 2020 Fatkhullin et al. 2023
We now state the main result which gives us the last iterate global convergence rate of Algorithm/
Theorem 4.5. Consider Algoritlm with "t = pr(t+2], 7)t & and H = (1 (1-7) 7) log(T + 1). Let Assumptions
6G,
4.1 4.2 and 4.7 hold. Then for every T 2 1 the output Or satisfies
J J'O)(( = VEblas +0
+0 1-
log T
log N + log
+ X
NT
T

---

Published in Transactions on Machine Learning Research (11/2024)
From Theorem 4.5 the number of trajectories required by Algorithm 1 ensure J -p-JJ J(OT) y Siin
is
I-7
o ( log
{){}) E
( (1) N + X2 Log(Av))
For case of exposition, we keep only dependence on c, N and À while providing a detailed expression in equation 38 We also note that the expression implicitly reflects the dependence on f. as the value of X depends on both f and the choice of the aggregator. The sample complexity for different aggregator functions are summarized in Table [ The value of in the table for each aggregator is from (Farhadkhani et al. 2022).
We now remark the lower bound for the sample complexity. In order to do that, we will first provide the lower bound for Stochastic Gradient Descent with Adversaries in (Alistarh et al. 2018).
Lemma 4.6 (Alistarh et al. (2018)). For any D, V, and <> 0, let there erists a linear function g [-D, D] + R (of Lipschitz contiruity G ==a = with a stochastic estimator ga such that Elg.] = g and (x) Vg(z)|l S V for all x in the domain. Then, given N machines, of which are adversaries, and T samples from the stochastic estimator per machine, algorithm
output x so that g(x) g(x²)
with probability 2 2/3 unless T=Sh Q Dav2 +fV322) where x² = arg min n.n) g(z).
Remark 4.7. Lemma 4.6 provides the lower bound for the sample complexity of SGD with adversarics such as: T= i 2 N + NZ We note that the lower bound function class in Lemma 4.6 may not satisfy the function class in this paper explicitly. However, we believe that since the lower bound holds for any class of functions that includes linear functions, the result should still hold with the assumptions in this paper. We also note that since 1/c² is lower bound for the centralized case (Mondal & Aggarwal 2024), it follows that the lower bound for the distributed selup is Ω (Nzz) even in the absence of adversaries, which is the same Q
(+) when f< VN.
Remark 4.8. From Remark 4.7 follows that MDA, CWTM and MeaMed achieve optimal sample com- plexity in terms of e, N and f (upto logarithmie factors). As result, these methods exhibit linear speedup when the number of adversarial agents is the order of O(VN). When the number of adversarial agents is O(N)), where 5 > 0.5, they achieve speedup of order (V)((1))). It's worth noting that while MDA poses computations ional challenges, CWTM and MeaMed are computationally inexpensive, on par with simple averaging used in vanilla federated policy gradient.
Remark 4.9. Works in Byzantine literature generally use strong assumptions on the noise. For example, there are line of works assuming vanishing variance (Blanchard et al. 2017 El Mhamdi et al. 2018 Xie et al., 2018), which does not hold even for the simplest policy parametrizations. Intuitively, when the assumptions on the noise is weakened, it becomes harder to distinguish adversarial and honest workers. In contrast, we provide these near-optimal bounds only using standard assumptions in Policy Gradient literature.
5 Proof Outline for Theorem 4.5
The main challenge in analyses with adversaries lies in bounding the difference of the update direction (in Algorithm 1, de) and the true gradient, (..)
Key step:
We bound Elid+ - (n.)))) as
d4 (JH((.)) El|d, dell + +Eld, (+))ll
where de = ~ Eneg d.th
We note that El|d,-d. del| can be bounded using the definition of (f, ag-ggggegtsors as follows (details given in Detailed Outline):
E d4 - d, < 2XE
max (|db
(8)
GEG
7

---

Published in Transactions on Machine Learning Research (11/2024)
In Farhadkhani et al. 2022), , E E[maxied ||de ( is bounded by
E
| JJH(0:))]] -N- D) (JH((.))l
E
where d!0) is an unbiased estimate of (O.) obtained from an honest agent j E G. This results in an extra factor of (N f). To illustrate the impact of this term, consider the scenario where À is of optimal order, specifically O
and f O(N5). Even with optimal and with 0 < 8 I 0.5, their sample complexity bounds do not achieve linear speedup. Furthermore, if the number of faulty workers 8 >> 0.5, the convergence rate deteriorates with an increase in the number of workers N. More specifically, if f = @(N6+1/2) their sample complexity bound is
222
holding true for all 8 > 0.
In contrast, we show that for our algorithm, this term can be reduced Ollo((N f)), from (N WW-F), f). This results in significant improvement in the sample complexity bound, enabling us to obtain linear speedup when 5 & 0.5 and sample complexity of order O [ 1) when 8 > 0.5, with certain choice of aggregators, showing speedup of order O(N2(1=))
22
We do this by showing that the update direction calculated by each worker i in Algorithm | de is a sum of bounded martingale differences. As result, we can then invoke numa--ooffdiin inequality obtain sharper bounds. This ensures that our algorithm guarantees speedup as long as f O(V"), where 6 < 1.
Detailed Outline: We split the proof into three steps given below:
1. Bounding Bl|de - -del:
From the definition of (f, Aggggreg,,,,,, we have I|d, d À max l1d - -dd Thus,
Eld dell max Tjy
|
a!"
I||
AE max (1a. VJH (|d (JH(0.)
2JEG
$ 2XE max
(n)
(9)
iEg
Let X; = | JJH (0.) and X = max:eg X,. We shall denote the indicator function of the event A by
14- Then for all > 0
B[ = [[1 (x24) + X1xxeal S E[1
(x2a [[X1 + + | (x27] +
- C.P. 2 2) + + > P(X, +2= C1 - f) P(I()) - JJH( 2 2) +
iEG
where C1 is an upper bound on X (sce Appendix
C.3 Thus, for all ビ> 0
E d: - 4,1l s 2C1A(N - f) P(Ia,) (..)ll)) 2 2) + 21E.
(10)
In order to bound P( (0,)ll 2 2), we make use of the following result. Lemma 5.1. Consider Algorithm For all E Eg and 2 1, we have
VJH((.)) = M0
where | < C1 and (
11 = 0.
The proof of the above lemma is given in Appendix C.3 obtain the following bound (proof in Appendix C.4
Using Vector Axuma-Hoeflding inequality, we
El|d, dell < 4e CeNNN De-1))+))/220 + 2XE.
(11)
8

---

Published in Transactions on Machine Learning Research (11/2024)
Let é / - -oN(N- Then, 1+1
4e Eldd dell 4e2C,A(N - -f) 227 t+1 + +20
2 llgg(N f)(++1
(12)
t
2. Bounding Eldd, (H:Hll))l::
We provide a bound for Fldd - (..)l below. The proof can be found Appendix C.2
Lemma 5.2. Consider Algorithm 7 For all 2 1, we have
Elid, Jnn(0.)1 = C2(1 + log!)
(13)
(N - f)t
where C2 is defined in Appendiz
C.2
From equation
12 and equation 13
we have
4E
2 logg(N - -s) + V
C2(1 + log!)
B - V (0.))l
++1 + 2012
(14)
t t+
(N f)t
3. Obtaining the final bound:
Using Lemma 7 (Fatkhullin et al. 2023 we have
J 1(0++1)
22
(J+ - J(0.)) + 7t 8 Bl [J,((.))
L
(15)
+ Yo D 7
3
2
where /
2 20
JEbise and py, I. are defined in Appendix C.1 p(1-7)
Substituting equation 14 in equation 15 and unrolingg the recursions gives us the following bound. The full
proof can be found in Appendix C.5 Lemma 5.3. Consider Algorithm
Then for all T
J J(Or) < Ebiia
+ J J(0p)
C3
+ T +1
(T'
#FVT+1 +1 (V
32G1
(V2(1 -
C2(1 log T)
+
f)( + +1)
where C3 is defined in Appendir
C.5
6 Evaluation
To show the effectiveness of our algorithm design (i.e., Res-NHARPG), we provide evaluation results on two commonly-used continuous control tasks: CartPole-vl from OpenAT Gym (Brockman et al., 2016) and InvertedPendulum-22 from MuJoCo TTodorov al., 2012). Additional experiments on more demanding MuJoCo lasks, including HalfCheetah, Hopper, Inverted Double Pendulum, and Walker are provided in Appendix A For each task CartPole-vl and InvertedPendulummvt there are ten workers to individually sample trajectories and compute gradients, and three of them are adversaries who would apply attacks to the learning process. Note that we do not know which worker is an adversary, so we cannot simply ignore certain gradient estimates to avoid the attacks. We simulate three types of attacks to the learning process: random noise, random action, and sign flipping.
In Figure D we present the learning process of the eight algorithms in two environments under three types of attacks. In each subfigure, the x-axis represents the number of sampled trajectories; the y-axis records the
9

---

Published in Transactions on Machine Learning Research (11/2024)
500
522
400
433
Sigortyn
300
GM
PG c0.5v
200
CNTTM
MDA
Meshted
Number trajectorics
Nammerr tnujedorics
(a) CartPole (Random Noise)
(b) CartPole (Random Action)
500
SM
440
300
800
Kram
MDA
200
Certed
Mea Med
(2
CM
100
200
1000
1900
1756
200
7B0
1000
1750
(c) CartPole (Sign Flipping)
InvertedPendullmm (Random Noise)
dggetten
1000
algorihmn
PG
SM
S14
CalModl
CIK TM
000
Rasu
000
400
MooWed
420
Meafted
200
200
500
752
1000
1200
1500
1750
500
1000
1500
2000
2000
2000
Numbber tralecooii
(e) InvertedPendullmm (Random Action)
InvertedPendullum (Sign Flipping)
Figure 1: Evaluation results of Res-NHARPG on CartPole and InvertedPendullm. We test Res-NHARPG with the six aggregators as shown in Table For baselines, we select Res-NHARPG with a simple mean (SM) function as the aggregator, which is equivalent to the original N-HARPG algorithm, and vanilla policy gradient method with the simple mean aggregator (PG-SM). For each environment, there are ten workers, of which three are adversaries, and simulate three types of attacks: random noise, random action, and sign flipping. It be observed that N-HARPG outperforms PG and Res- NHARPGG with those (f, aggregators can effectively handle multiple types of attacks during the learning process.
10

---

Published in Transactions on Machine Learning Research (11/2024)
acquired trajectory return of the learned policy during evaluation. Each algorithm is repeated five times with different random seeds. The average performance and 95% confidence interval are shown as the solid line and shadow area, respectively. Codes for our experiments have been submitted as supplementary material and will be made public.
Comparing the performance of N-HARPG (i.e., SM) and Vanilla PG (i.e., PG-SM), we can see that N- HARPG consistently outperforms, especially in Figure [[a] and [(b) of which the task and attacks are relatively easier to deal with. For the 'random action' attack (Figure [(b) and [ which does not directly
alter the gradient estimates, N-HARPG shows better resilience. However, in more challenging tasks (e.g.,
InvertedPendullm) and under stronger attacks (e.g., sign flipping), both N-HARPG and Vanilla PG would likely fail, which calls for effective aggregator functions.
For CartPole, the maximum trajectory return is set as 500. Res-NHARPG, implemented with each of the six aggregators, can reach that expert level within 1000 trajectory samples, with slight difference in the convergence rale. As for InvertedPendulum, not all aggregators achieve the expert level (i.e., a trajectory return of 1000), yet they all demonstrate superior performance compared to those employing only the simple mean aggregator. It's worth noting that Res-NHARPP with the MDA aggregator consistently converges to the expert level across all test cases, showing its robustness. Morcover, the 'random action' attack brings more challenges to the aggregators, as the influence of random actions during sampling on the gradient estimates is indirect while all aggregators filter abnormal estimates based on gradient values.
7 Summary
In this paper, investigate the impact of adversaries on the global convergence sample complexity of Federated Reinforcement Learning (FRL). We introduce Res-NHARPG, and show its sample complexity is of order Ô N- + 1²)) using (J, A-aggregatooos,,,, where N is the total number of workers and f is the number of faulty workers. Notably, when certain aggregators are used (MDA, CWTM and MeaMed), we show our approach achieves optimal sample complexity.
This work opens up multiple possible future directions in RL with adversaries, including delay in agent feedback and heterogeneous agents. We further note that parameter free version of the proposed algorithm is also important future direction.
Acknowledgment
Swetha Ganesh's research is supported by the Overseas Visiting Doctoral Fellowship (OVDF) and Prime Minister's Research Fellowship (PMRF). Gugan Thoppe's research is supported by the Indo-French Centre for the Promotion of Advanced Research CEFIPRA (7102-1), the Walmart Centre for Tech Excellence IISe (CSR Grant WMGT-23-0001), DST-SERB's Core Research Grant (CRG/2021/00833)) and the Pratiksha Trust. Young Investigator Award.
References
Saminda Wishwajith Abeyruwan, Laura Graesser, David B D' D'Ambrosio, Avi Singh, Anish Shankar, Alex Bewley, Deepali Jain, Krzysztof Marcin Choromanski, and Pannag R Sanketi. i-sim2real: Reinforcement learning of robotic policies in tight human-robot interaction loops. Conference on Robot Learning, pp. 212-224. PMLR, 2023.
Alekh Agarwal, Shamn M Kakade, Jason Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. The Journal of Machine Learning Research, 22(1):4431 4506, 2021a.
Mridul Agarwal, Bhargav Ganguly, and Vancet Aggarwal. Communication efficient parallel reinforcement learning. In Uncerlainly in Artificial Intelligence, 2021b.
11

---

Published in Transactions on Machine Learning Research (11/2024)
Abubakr O Al-Abbasi, Arnob Ghosh, and Vancet Aggarwal. Deeppool:
Distributed model-free algorithm for ride-sharing using deep reinforcement learning. TEEF Transactions on Intelligent. Transportation Systems, 20(12):4714 4727, 2019.
Dan Alistarh, Zeyuan Allen-Zhu, and Jerry Li. Byzantine stochastic gradient descent. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pp.
2018.
Zeyuan Allen-Zhu, Faeze Ebrahimianghaaaii, Jerry Li, and Dan Alistarh. Byzaniine-resiliet non-convex stochastic gradient descent. In International Conference on Learning Representations, 2020.
Qinbo Bai, Amrit Singh Bedi, Mridul Agarwal, Alec Koppel, and Vaneet Aggarwal. Achieving zero con- straint violation for constrained reinforcement learning via primal-dual approach. Proceedings of the AAAT Conference on Artificial Intelligence, 36:3682 3689, Jun. 2022. doi: 10.1609 10.1609/aaai.v3366 baai.v33i4..0288)
Jonathan Baxter and Peter L Bartlett. Infinite-
estimation. Journal of Artificial
Intelligence Research, 15:319-305 3500, 2001.
Peva Blanchard, El Mahdi El Mhamdi, Rachid Guerraoui, and Julien Stainer. Machine learning with adversaries: Byzantine tolerant gradient descent. In 1. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems 30, pp. 119 129. Curran Associates, Inc., 2017.
Trevor Bonjour, Marina Haliem, Aala Alsalem, Shilpa Thomas, Hongyu Li, Vaneet Aggarwal, Mayank Kejriwal, and Bharat Bhargava. Decision making in monopoly using a hybrid deep reinforcement learning approach. TEEE Transactions on Emerying Topics in Computational Intelligence, 6(6):1335-133 1344, 2022.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym. CoRR, abs/ hass/606.000 160/.016600, 2016.
Chang-Lin Chen, Bharat Bhargava, Vancet Aggarwal, Basavaraj Tonshal, and Amrit Gopal. A hybrid doep reinforcement learning approach for jointly optimizing ofloading and resource management in vehicular networks. IEFE Transactions on Vehiculor Technology, 2023a.
Jiayu Chen, Tian Lan, and Vaneet Aggarwal. Option-aware adversarial inverse reinforcement learning for robotic control. In 2023 IEEE International Conference on Robotics and Automation (ICRA), pp. 5902- 5908. IEEE, 2023b.
Yiding Chen, Xuezhou Zhang, Kaiqing Zhang, Mengdi Wang, and Xiaojin Zhu. Byzantine-robust online and offline distributed reinforcement learning, In Francisco Ruiz, Jennifer Dy, and Jan-Willem van de Meent (eds.). Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Reseavch, pp. 3230 -2669. PMLR, 2023c.
Yudong Chen, Lili Su, and Jiaming Xu. Distributed statistical machine learning in adversarial settings: Byzantine gradient descent. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 1(2):1-25, 2017.
Michael B. Cohen, Yin Tat Lee, Gary Miller, Jakub Pachocki, and Aaron Sidford. Geometric median in nearly linear time. In Proceedings of the Forty-Eights Annual ACM Symposium Theory of Computing, STOC '16, pp. 9-21. Association for Computing Machinery, 2016.
Ashok Cutkosky and Francesco Orabona. Momentunn-asee variance reduction in non-convex sgd. Advances in neural information processing systems, 32, 2019.
1has Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Jacob Steinhardt, and Alistair Stewart, Sever: A robust meta-algorin mega-tlgorithm for stochastic optimization. In International Conference on Machine Learning, pp. 1596-1606. PMLR, 2019.
Mahdi EI Mhamdi, Rachid Guerraoui, and Sébastien Rouault. The hidden vulnerability of distributed learning in Byzantium. In Jennifer Dy and Andreas Krause (eds.). Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Reseorch, pp. 3521-3530. PMLR, 10- 15 Jul 2018.
12

---

Published in Transactions on Machine Learning Research (11/2024)
Xiaofeng Fan, Yining Ma, Zhongxiang Dai, Wei Jing, Cheston Tan, and Bryan Kian Hsiang Low. Fault- tolerant. federated reinforcement learning with theoretical guarantee. Advances in Neural Information Processing Systems, 1111007-10211 2021.
Sadegh Farhadkhani, Rachid Guerraoui, Nirupam Gupta, Rafacl Pinot, and John Stephan. Byzantine machine learning made easy by resilient averaging of momentuns. In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 6246-6283. PMLR, 2022.
Nyas Fatkhullin, Anas Barakat, Anastasia Kireeva, and Niao Hc. Stochastic policy gradient methods: Im- proved sample complexity for Fisher-non-deggneeaate policies. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 9827 9869. PMLR, 23 29 Jul 2023.
Nan Geng, Tian Lan, Vancet Aggarwal, Yuan Yang, and Mingwei Xu. multi-agent reinforcement learning perspective on distributed traflic engineering. In 2020 IEEE 28th International Conference on Network Protocols (ICNP), pp. 1-11. IEEE, 2020.
Glebys Gonzalez, Mythra Balakuntala, Mridul Agarwal, Tomas Low, Bruce Knoth, Andrew W Kirkpatrick, Jessica McKee, Gregory Hager, Vaneet Aggarwal, Yexiang Xue, et al. Asap: A semi-autonomous precise system for telesurgery during communication delays. IEEE Transactions on Medicol Robolics and Bionics, 5(1):66 78, 2023.
Thomas P Hayes. A large-deviation inoquality for vector-valued martingales. Combinatorics, Probability and Compuling, 2005.
Seyyodali Hosscinalipour, Christopher G. Brinton, Vaneet Aggarwal, Huaiyu Dai, and Mung Chiang. From federated to fog learning: Distributed machine learning over heterogeneous wireless networks. 1EEE Commanications Magazine, 58(12):41-47, 2020. doi: 141109/MCOMO00 2000040....
Hao Jin, Yang Peng, Wenhao Yang, Shusen Wang, and Zhihua Zhang. Federated reinforcement learning with environment heterogeneity. In International Conference on Artificial Intelligence and Statistics, 2022.
Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, K. A. Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G.L. D'Oliveira, Salim Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaid Harchaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konečný, Aleksandra Korolova, Fari- Koushanfar, Sanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateek Mittal, Mehryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh, Mariana Raykova, Hang Qi, Daniel Ramage, Ramesh Raskar, Dawn Song, Weikang Song, Sebastian U, Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramer, Praneeth Vepakomma, Jianyu Wang, Li Xiong, Zheng Xu, Qiang Yang, Felix X. Yu, Han Yu, and Sen Zhao. Ad- vances and open problems federated learning. Foundations and trends in machine learning, 14(1 2): 1-210, 2021.
Sai Praneeth Karimireddy, Lie He, and Martin Jaggi. Byzantine-robust learning on heterogeneous datasets via bucketing. arXiv preprint arXiv:2006. 0005200000965 2020.
Sajad Khodadadian, Pranay Sharma, Gauri Joshi, and Siva Theja. Maguluri. Federated reinforcement learn- ing: Linear speedup under Markovian sampling. In International Conference on Machine Learning, 2022.
B Ravi Kiran, Tbrahim Sobh, Victor Talpaert, Patrick Mannion, Ahmad A Al Sallab, Senthil Yogamani, and Patrick Pérez. Deep reinforcement learning for autonomous driving: A survey. IEEE Transactions on Intelligent Transportation Systems, 23(6) 4926, 2021.
Leslic Lamport, Robert Shostak, and Marshall Pease. The byzantine generals problem. ACM Thans. Program Lang. Syst., 4(3):382 401, 1982.
13

---

Published in Transactions on Machine Learning Research (11/2024)
Guangehen Lan, Han Wang, James Anderson, Christopher Brinton, and Vancet Aggarwal. Improved commu- nication efficiency in lederated natural policy gradient via admm-based gradient updates. In Proceedings of the 37th International Conference on Newral Information Processing Systems, pp. 59873 59885, 2023.
Qifeng Lin and Qing Ling. Byzantine-robust federated deep deterministic policy gradient. In ICASSP 2022-2022 IEEE International Conference Acoustics, Speech and Signal Processing (ICASSP), pp. 4013-4017 IEEE, 2022.
Yanli Liu, Kaiqing Zhang, Tamer Basar, and Wotao Yin. An improved analysis of (variance-reduced) policy gradient and natural policy gradient methods. Advances Neural Information Processing Systems, 33: 7624 7636, 2020.
Saeed Masiha, Saber Salehkaleybar, Niao He, Negar Kiyavash, and Patrick Thiran. Stochastic second-ordes methods improve best-known sample complexity of SGD for gradient-dominaaeed functions. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Newral Information Processing Systems, 2022.
Washim U Mondal and Vaneet Aggarwal. Improved sample complexity analysis of natural policy gradient algorithm with general parameterization for infinite horizon discounted reward markov decision processes. In International Conference on Artificial Intelligence and Statistics, pp. 3097 3105. PMLR, 2024.
Matteo Papini, Damiano Binaghi, Giuseppe Canonaco, Matteo Pirotta, and Marcello Restelli. Stochas- tic variance-reduced policy gradient. In Proceedings of the 35th International Conference on Machine Learnäng, pp. 4026-4035, 2018.
Adarsh Prasad, Arun Sai Suggala, Sivaraman Balakrishnan, and Pradeep Ravikumar. Robust estimation via robust gradient estimation. Journal of the Royal Statistical Society: Series B (Statistical Methodology). 82(3):601 127, 2020.
Gaith Rjoub, Jamal Bentahar, and Omar Abdel Wahab. Explainable ai-based federated deep reinforcement learning for trusted autonomous driving. In 2022 International Wireless Communications and Mobile Computing (IWCMC), pp. 318-323. IEEE, 2022.
Peter J Roussceuw. Multivariate estimation with high breakdown point. Mathematical statistics and appli- cations, 8(37):283-297) 1985.
Julian Schrittwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, al. Mastering atari, go, chess and shogi by planning with learned model. Nature, 588(7839):604 609, 2020.
Zebang Shen, Alejandro Ribeiro, Hamed Hassani, Hui Qian, and Chao Mi. Hessian aided policy gradient. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 5729-5738. PMLR, 09-15 Jun 2019.
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In IEEE/RSJ International Conference on Intelligent Robols and Systems, pp. 5026 5033. IEEE, 2012.
Hoang Tran and Ashok Cutkosky. Better sgd using second-order momentum. Advances in Neural Information Processing Systems, 35:3530-355 3541, 2022.
Han Wang, Aritra Mitra, Hamed Hassani, George J Pappas, and James Anderson. Federated temporal difference learning with linear function approximation under environmental heterogeneity. arXiv preprint Stfi:230000211.. 2023a.
Han Wang, Leonardo F Toso, Aritra Mitra, and James Anderson. Model-free learning with heterogencous dynamical systems: A federated LQR approach. arXiv preprint 3rXim:2308.117/3. 2023b.
Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural policy gradient methods: Global opti- mality and rates of convergence. In International Conference on Learning Representations, 2019.
14

---

Published in Transactions on Machine Learning Research (11/2024)
Jiayi Weng, Huayu Chen, Dong Yan, Kaichao You, Alexis Dubureq, Minghao Zhang, Yi Su, Hang Su, and Jun Zhu. Tianshou: A highly modularized deep reinforcement learning library. Journal of Machine Learning Research, 23(267):1 6, 2022. URL
Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine Learning, 8(3-4):229-25 256, 1992.
Cong Xie, Oluwasanmi Koyejo, and Indranil Gupta. Generalized byzantine-toleran sgd. orXiv preprint arXiv: 10116, 2018.
Zhijie Xie and Shenghui Song. FedKL: Tackling data heterogeneity in federated reinforcement learning by penalizing KL divergence. IEEE Journal on Selected Areas in Communications, 41(4):1227-12 1242, 2023.
Jian Xu, Shao-Lun Huang, Linqi Song, and Tian Lan. Byzantino-robust federated learning through collabo- ralive malicious gradient filtering. In 2022 IEEE 42nd International Conference on Distribuled Compuling Systems (ICDCS), pp. 1223 1235. IEEE, 2022.
Pan Xu, Felicia Gao, and Quanquan Gu. Sample efficient policy gradient methods with recursive variance reduction. In International Conference Learning Representations, 2019.
Pan Xu, Felicia Gao, and Quanquan Gu. An improved convergence analysis of stochastic variance-reduced
policy gradient. In Uncerlainly in Artificial Intellignce, pp. 541 551. PMLR, 2020.
Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett. Byzantinc-robust distributed learning:
Towards optimal statistical rates. In International Conference on Machine Learning, pp. 3650-5633 PMLR, 2018
Chao Yu, Jiming Liu, Shamim Nemati, and Guosheng Yin. Reinforcement learning in healthcare: A survey. ACM Computing Surveys (CSUR), 55(1):1-36, 2021.
Rui Yuan, Robert M. Gower, and Alessandro Lazaric. A general sample complexity analysis of vanilla policy gradient. In Proceedings of The 25th International Conference Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pp. 2332-3380 PMLR, 28-30 Mar 2022.
Junyu Zhang, Chengzhuo Ni, Zheng Yu, Csaba Szepesvari, and Mengdi Wang. On the convergence and sample efficiency of variance-reduced policy gradient method. In A. Beygelzimer, Y. Dauphin, Liang, and J. Wortman Vaughan (eds.), Advances in Newral Information Processing Systems, 2021.
Mingyue Zhang, Zhi Jin, Jian Hou, and Renwei Tuo. Resilient mechanism against byzantine failure for dis- tributed deep reinforcement learning. In 2022 IEEE 33rd International Symposium on Software Reliability Engineering (ISSRE), pp. 378 389. IEEE, 2022.
15

---

Published in Transactions on Machine Learning Research (11/2024)
A Additional experiments
1000
2000
aigerithm
algorithm
PG-SM
8C0
FG.SM
1500
Sphtin
600
1000
400
200
250
500
750
1000
1250
1500
1750
730
1200
1756
Numberr trajectories
(a) HalfCheotah
(b) Hopper
5000
1000
4000
algorttm
algorithim
PG 3M 5M
000
PC SM
SM
3000
Pelim
600
2000
300
200
1000
1750
Number Trajectories
Number trajectories
(c) Inverted Double Pendulum
(d) Walker
Figure 2: Ros-NHARPG with the MDA aggregator consistently outperform the basclines: N-HARPG (i.c.) SM) and Vanilla PG (i.e., PG-SM), series of MuJoCo tasks.
Previous evaluation results have shown the superiority of NHARPG with (f, aggregators. To further demonstrate its applicability, we consider Res-NHARPG with MDA and compare with the baselines: N- HARPG (i.e., SM) and Vanilla PG (i.e,, PG-SM), on series of more challenging MuJoCo tasks: HalfCheetah, Hopper, Inverted Double Pendulum, Walker, of which the result is shown Figure 2 Our algorithm consistently outperforms the baselines when adversaries (specifically, random noise) exist, and relatively, N-HARPG performs better than Vanilla PG. Note that our purpose is not to reach SOTA performance but to testify the effectiveness of aggregators, so the three algorithms in each subfigure share the same set of hyperparameters (without heavy fine-tuning). maximum number sampled trajectories (6000 for the Inverted Double Pendulum and 1800 for other tasks), for each algorithm by plotting their episodic returns. The advantage of Res-NHARPG is more significant when considering the peak model performance. For instance, the highest evaluation score achieved by Res- NHARPG on Inverted Double Pendulum can exceed 9000, ie., the SOTA performance noted in (Weng et al. 2022), while the baselines' scores are under 500. We also evaluate the Fed-ADMM algorithm proposed in (Lan et al.) 2023) in Fig. 3 As expected, even with a higher number of samples, Fed-ADMM yields significantly lower returns compared to NeARN with the MDA aggregator (see, for instance, Fed- ADMM performs poorly in HallCheetah, achieves a return of 350 Hopper compared to consistently above 400 for our algorithm; 90 Inverted Double Pendulum to above 4000 for our algorithm; less than 300 Walker to around 1000 for our algorithm).
Figure 2 we illustrate the training progress, up to a
Details regarding attacks considered: By 'random noise' or 'sign flipping', the real estimated policy gradients are altered by adding random noises or multiplying by a negative factor, respectively. While, for 'random action', adversarial workers would select random actions at each step, regardless of the state, when sampling trajectories for gradient estimations. Unlike the other attacks, 'random action' does not directly change the gradients, making it more challenging detect. Also, 'random action' is different from the widely-adopted e-greedy exploration method, since the action choice is fully random and the randomness does not decay with the learning process.
16

---

Published in Transactions on Machine Learning Research (11/2024)
-200
-225
300
-250
250
Return
Return
200
330
925
100
-390
-375
0
Number trajertories
Number trajectories
(a) HalfCheetah
(b) Hopper
90
80
150
100
50
4/4
2000
4000
6000
8000
10000
2000
4000
8000
8000 1000C
Number trajectories
Number of trajectorias
(c) Inverted Double Pendulum
(d) Walker
Figure 3: Evaluation of Fed-ADMM Lan et al. 2023 on MuJoCo tasks with random noise. The solid lines
represent the mean performance, while the shaded areas indicate the 95% confidence intervals from repeated experiments. We used the official implementation from (Lan 2023
B Details of aggregator functions
Let [r]* denote the k-th coordinate of x E Rd. Given a set of n vectors X {æ1...., 2nF as input, the outputs of different aggregator functions are given below.
Minimum Diameter Averaging (MDA) (originally proposed in (Rousseeww) 1985) and reused in EEl Mhamdi al. 2018) selects set 9 of cardinality N with the smallest diameter, i.e.,
G E arg min GC(L.... N} N=
max ||,, - -251 (ijeg
and outputs N- Eieg Zt.
Co-ordinate wise Trimmed Mean (CWTM) Yin et al. 2018): Consider co-ordinate k 1,2,...,4 .d Let Gb C X be such that ge consists only of elements in X with the f largest or f smallest values of [z].. Then, CWTM outputs
(CWTM(E)....... D.) - 25 DEg:
Σ [z]x.
Co-ordinate wise Median (CWMed) Yin et al. 2018): The output of CWMed is given by
[CWMed ",, Median ([r1)s.... [z,]k).
Mean around Median (MeaMed) (Xie et al. 2018 ; MeaMed computes the average of the N N-f closest elements to the median in each dimension. Specifically, for each [d]. m [n], let inck be
17

---

Published in Transactions on Machine Learning Research (11/2024)
the index of the imput vector with k-th coordinate that is m-th closest to Mledian((11le.. [xx]k)) Let Ck be the set of N indices defined as
C2 (11,0).... iN --
Then we have
Σ [aale iECk
Krum (Blanchard et al. 2017): Multi-Krumi outputs an average of the vectors that are the closest to their neighbors upon discarding farthest vectors. Specifically, for cach i E [n] and h [n 1]. let in E [n] (i) be the index of the k-th closest input vector from 24; i.e., we have 1|0;-1;, S S ||. - |l with ties broken arbitrarily. Let C₁ be the set of N - closest vectors to It, i.e.,
C (l....., iN-S-1)-
Then, for each i E [n], we define score(i) Ejec; || - xz average of q input vectors with the smallest scores, i.e.,
Finally, Multi-Krum; oulputs the
Multi-Krum;, (Z1, Fnd = Σ
Fi. 9 SE
where S(g) is the set of q vectors with the smallest scores. Multi-Krum, for q =1
We call Krum" the special case of
Geometric Median (GM) (Chen et al. 2017 For input vectors 21,..., na, their geometric median, denoted by GM(z), Tn); ) is defined be vector that minimizes the sum of the distances to these vectors. Specifically, we have
GM Fn) arg min sERd
|| 2ell-
Comments:
We observe that MDA, CWTM and MeaMed achieve optimal bounds, while CWMed, Krum and GM do not. This explained in (Farhadkhani al. 2022) by noting that Krum, CWMed, and GM operate solely on median- based aggregation, while MDA, CWTM, and MeaMed perform an averaging step after filtering out suspicious estimates. This averaging step results in variance reduction, similar to simple averaging in vanilla distributed SGD.
It's worth mentioning that CWMed and GM do not require any knowledge of f to be implemented. On the other hand, while MDA, CWTM, MeaMed, and Krum do rely on some knowledge of f, they can still be implemented by substituting an upper bound for instead. In this case, our guarantees would scale based on this upper bound, instead of f.
C Proof details
C.1 Notations
Before proceeding further, we begin with the following lemma where we also introduce a few notations.
Lemma C.1. For all 6 E Rd and trajectories т of length H sampled by policy no, we have
R(G
I. J is L-smooth with L = (1-7)²
18

---

Published in Transactions on Machine Learning Research (11/2024)
2. g(T, 0) is unbiased estimate of (0) and
G.R
11 0)11 <
(1 - 7)2 = Gg.
(16)
3. B(T, 0) is unbiased estimate of Jz) and
G2G + LRR
[B(r, 0)1 <
GH-
(17)
(1-
4. Por some < < S G we have
E B( B|B((T))-VVJ((00
$ o
(18)
The first two statements are given in Lemma 4.2 and 4.4, Yuan et al. 2022 and the third and fourth statements are given in Lemma 4.1 in (Shen et al. 2019). Since the algorithm makes use of the truncated gradient and hessian estimates VJH (0) and (² instead of () and (²)(0), we must bound the error terms VJ((0) (#) and V².((0) (0). It known that these error terms vanish geometrically fast with H and stated below:
Lemma C.2 (Lemma 3, (Masiha et al.
2022
Let Assumption 4-4 be satisfied, then for all Re and
every H 1, we have
(O) VJ(O)) < D,T " (V))(0)--J3)) ( DAT",
where D, G.Rt
1 + and D = R(G++09) 1-7
1 + H
1-7 1-7
1-7
C.2 Proof of Lemma 5.2
The proof follows similarly as in Fatkhhullin et al. 2023 Here, we take into account the affect of estimates of (N (N-f) f) agents versus one agent. Since each of the d."" m) are updated as
aeth n1) B(F(") (0, 0c-1)) + mg((T")) (n) o(()),
(19)
we notice that d. N- Eneg d! can be expressed as
d. = (1 (1-1 B(Q.) 0.-1)) + m
(20)
where B(0.)= = N- N-y Eneg B(+(") 3(#(").0(") 0(()) and g(0.) N-z Eneg "(T("),0) 0.).
It follows that
de (J.( = (1 - B()) 1,-1)) + m)((.)) (..(0,)) = (1 - (d (J.((..1) + ((Q)) - 0.-1) + (Jn((0--1) VJn((.)))
()(())) (O.)
= (1-m) - JHH (0..))) + - -m): + m n.
(21)
where W, =
VJ and D := 5(0.) (Jn( We then have the following 0, - VJ (0.
lemma
Lemma C.3. For all 2 1, the following statements hold
(1) B[W] = 0
(i) E(P.]
19

---

Published in Transactions on Machine Learning Research (11/2024)
o² (tt) 3 - N-j
(tv) B|||W||
12 N-j ((21² + to + D3, ) -2 + ).
Proof of Lemma
The first two statements are casy to see since E[V; N- Eneg E and 1
for all from Lemma
C.1
Similar arguments show that E[W] 0.
Notice that
o² N - f 11 s
B11 (N f)2
(1)
(22)
neg
where the last incquality follows from Assumption 4.3 Similarly,
B|| (N ƒ)
Σ
EllW (0) 13)
(23)
ngg
We have for all n E g
= -J)(())))))))))))) B(+,")
B( 0fth)
0c-1)11
< 6E 6E (n,(0) () 6E (J (o)(1
+ GEI 0(t)) (0) 0--1)1 63 63 J2) -=J(0.)(0.- 0.-1)11?
+ (())) - -1,-1)12
2(61" + B3 01-111 12 + 2 01-111
S 2(612 ) 12 1 21 + ,
2H .7
12((212 + t + 2 2H d. + D3 7 2H
where the last inequality follows from the fact that 100 - 0,-1l = 11 |ل d, = =
Using Lemma C.3 we obtain
1 I (oH(11 < (1 nh: 1E] d (0,-)11)
1
(24)
N (202n) 12((2122 + D2 2H) 72 2H
Let 1/2 = x==~~220" 1202 + 12((212 + +o + D3 - 2H 72 + D2 >
2H
Unrolling the above, we obtain
Eldd JJH (1:)11
(1 - nn)..
-=1 1=f+1
For 7) 4. it follows that IP
1o (1 m// لييه and
1 - Σ
Eldee vJn(0))1
igh.
1=1
20

---

Published in Transactions on Machine Learning Research (11/2024)
601 Note that for 7i 2:2 71 (z((+2)
and H
l)) (1-7) we have ing 3,3 in3 -
6G ppz
and by2" 1 1 Thus,
1 20 El d VJH((,))12 S (N -f)
6G1
24D
12((21,
0i D2 221)
i
20 + 12(21.2 + + + D 7 2H 6G1
2AD2) 3)
1
'NN- - f)t
HF
1 20 + 12(212 + + + D 2H
6G1
+ 2AD?)
(
(25)
M
μF
C2(1 + logt)
(26)
(N - f)t
where C2 0==20 202 + 12(212 + o + D 7 211)
6G1 uF
+ 24D
C.3 Proof of Lemma 5.1
Similar to equation 21 we have
[H:( = (1- - md - VJn(((-1))) + + + - +11-m) W
where 2,(0) = g(T( 0.) (mn(O)) and W0!0 = - + ,.)((, - Let M. =
1 + 1-m) W! Then,
(O,( (1 (11)) vJzr(0-1))) + (
Unrolling the above recursion gives
de VJH(())
Σ Ti
II (1 ma) MS" k=j+1
j=1
where we use the convention I 0g 1 if b < a.
Let n7 = J. With this choice of m, it follows that I (1 - -mk)= = _o-1
=Jot and
a (H,
Σ j M Σ M
Now we show that _ is bounded and forms a martingale difference sequence. We have |D] || s G, (from Lemma C.1 and
||! || < [[VJH (1) 0,)( - 6,-1)1l
< [[ - (.,(l + (1)( (,)() -.-1)ll < LIJ0, - 0. 0.- + ( 0011110 0--1l1 S + (L+Gr)
Thus
|| | || = 15000 + (1-1)) 1/e
m1(0)
S GG + " + GH) S SGg +
6G
[I + GH) = Ct.
(27)
1/:
Note that this implies that
11 1 (JH(l)))l - Σ | Cr.
21

---

Published in Transactions on Machine Learning Research (11/2024)
Define sequence {M (0) 120 such that M700) and M c. Σラー
for k
Then for all k 2 0
| - M | /C 1
/Cill
and
k-1 Σ
EMM
R+1 | [ = E
M
(T((
R
M
+ C
C 1=0
C
=E E
M + G7
_M
M *
M
1 E
M
( (x
c
Note that
x( c c00. 00.0000.99 0f (6) (0)
(1)
0k) = =
We get
E M
(8) x E
E (0)
|
Observe that
ElM
k
(1)
| k-
= E
(1)
-1-mh
w
F
1/
= E (x
121 k-
(1-
m
+
E
O.
Thus, for all k 2 0
E EIM (6) k+1
[ = NM
(28)
C.4 Proof of Equation equation 11
Lemma C.4 (Vector Azuma-Hoeffdinn Inequality, HHayes 2005 ). Let M = (Mo,... ................................ Mn) taking values in Rd be such that
Mo = 0 B[Ma Mn-1] = M and MM - Mn- S 1.
Then, for every 8 0,
P (I 2 8) < 2 82/
(29)
The sequence {M Juzo satisfies all properties in Lemma C.4 which gives us
P( ( E) s 2 202e-81122
(30)
It follows that
(1
-V))) 26) =P
Σ
M
(1)
Ne E
PP
C1
Σ
(M
(M
(C))
26
[+1 1=
i+1
P
Ci
26
P
(1774)
> (1+1)e/C))
+
2c - (1+1)2//20)
(31)
Plugging the above bound into equation 10 gives
El|de dell CexCN - (241)) + 2Xe'.
(32)
22

---

Published in Transactions on Machine Learning Research (11/2024)
C.5
Proof of Lemma 5.3
From equation
15 we have
J J (0c+1)
<(1 1 <(1-1+2 1+2 (J' ((0)+ + +3 Dg 78 + 87 Blldd - ( +
2
L +
e'
(33)
3
3
We use the following auxillary lemma to bound the above recursion
Lemma C.5 (Lemma 12, (Fatkhullin et al. 2023 ) Let T be a positive integer and {ribizu be a sequence of non-negalive numberrs such that
T+41 S (1 - at)r: + Bt.
where {asle20 and (B:)20 are non-negative sequences and a₁ S 1 for all t. Then for all to, T 2 1,
TT 1)9r,
T-1 Belt + T)2 2i
(T + - 1)2
Using Lemma C.5 on equation
33 yields
J" J(Oo) J J' S
0 Bell + 2) (T T+D 112
+
(34)
(T + 1)2
where
Be =
3 N1 Dg 7"
4
H
+
Blldd #
87
VJH (0))ll
L1
E'
3
2
3
4
Dg H 160
2 logg N - f) 1)
64c"
< 3 7/4
3
t+1
3(++1)
87 C2(1+ ((g+)
L c'7c
(N-S))
3
(g Dg 7 + Lx2
64e
16CiA7
llg((N (1)
+
2
+1++1)
3
t+1
8%
C2(1 + log t)
+ c'
(N f)t
Note that
ΣT EL 7, +
e' EL 6G
3(T + 1)2
34F (T + 1)2
6G1E' Σl (t + 2)
3pF (T+ 1)2
6G1e' 2 TT -1
3pF 2(T 1)²
G15' /Shins (1-7)*
μF
Also, note that since H Ing(T++)
7th < T+I and it
6G1
1-7
pr(++2]
T
4
Dg
H
L
64e2C1A7x)
T
16G,Dg
18G
950C
+
(t (t+2)² <
+
+
3
2
3(t 3(++1)
PF
PF
t=0
16G,Dg
18G /
950C1G1
(T +1)
PF
PF
23

---

Published in Transactions on Machine Learning Research (11/2024)
It follows that
1
4 Dyn"
L
(t 2)2
(T
1)²
3
2
3(t+1) +1++1)
1=
16G
186
950
Pr
HF
T+I
Finally,
2 log f)(t + +1)
8%
C2(1 + logt)
3
t+1 1
3
(N -ftt
1661
2log(N - ff)
C2(1 + logt)
CLA
1y +2)
1+1
V
(N - f)L
16G
C2(1 + log
(GAA/2log(A +1) +
1y 2)VE
(N - f)
Note that
T (1+2)2
Σ
1
Σ t+2
(T + 1)²
(t+ 222V
(T + 1)2
Vi
T
Σ 22)
$ (T+ 1)2
t=0
7 +
2
S
(T 112
+ 1)1/2"
Combining all of the above, we get
Vbbia
J - J((o).
+ (
18G P5
950C
Jr J(Or)
+
(1 7)
(T + +12
PF
HF
T+1
(1 C2(1 (og+log7] T)
32G1
+ +GA 2ogg(N - -f)
(35)
#FVT+I
(N-
From the above expression, we have
J J- - 1-7 ( Gi
Ebias +0
( C2log T ( (N-
+ SiAVlog((N f)(T + 1))
(36)
where Ci = Gy + 6G: (L+ GH) and C2 = 20 12(212 + o + 2) 6G, + +442 The Lipschitz constant pF
L, variance bounds x² and o and the remaining terms Gg, GH, D₁ and D, in turn, be bounded in terms of 7/ pr, the bound on the reward function R and the Lipschitz and smoothness constants of the score function G1, G2 (see Lemma C.1 and C.2 Substituting these bounds, we obtain
J ---](OT)
Ebias
+0
G1
C. PF
R8G33 + [I-9)*
R4GH++)) (I-7)5
log T
1-7
#F
(N-
(37)
RRG2G
R2 (29 + G2)
+
(1-
Av Avlo(((N - f)(T + 1))
(1 71-7)a
24

---

Published in Transactions on Machine Learning Research (11/2024)
With the above bound, obtain J - J(Or)= <
Sibus I-7
for
T o 2
log (1)
R.G.
+
(N f) G2G
1pp(1 7)
p3 ( + G9G
(38)
X2 log(AV f)
1 7)
1 - (1)8
D
Compute Resources
Experiments were conducted using the Oracle Cloud infrastructure, where each computation instance equipped with 8 Intel Xeon Platinum CPU cores and 128 GB of memory. In Figure 1, each subfigure contains comparisons among eight algorithms each of which is repeated five times with different random seeds. The single running time for an algorithm is approximately two hours. Thus, to reproduce Figure 1, it requires approximately 480 CPU hours. Similarly, for Figure 2, the time would be about 120 CPU hours.
25


Reviews:
[{"review_id": "FjOsMHoPW0", "reviewer": "Reviewer_HHRA", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper studies an interesting (although very specific) setting and provides the first sample complexity result for it.\nTo ensure optimality, some care in the technical analysis was needed. The proof technique is well explained in the paper.\n\nThe contribution relies heavily on previous work from two well-established lines:\n- Policy gradient with global convergence, in particular (Fatkhullin et al., 2023), which provides the standard assumptions on the policy class, the policy gradient estimates (for the agents) based on second order information and the analysis that leads to the optimal $\\epsilon^{-2}$ rate\n- Federated learning, providing the robust aggregation techniques that allow a linear speedup w.r.t. the number of agents even when adversaries are present\n\nThe main effort of this paper is thus combining these results into a single federated-PG algorithm for the new setting. On one hand, this means that no truly original ideas are introduced. On the other hand, as mentioned above, this combination does require some care from a purely technical standpoint. The relationship with previous works and the key technical challenges are well documented in the paper.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors study policy-based federated RL with adversaries: N agents or nodes contribute to the optimization of a parametric policy for the same MDP. They do so by collecting trajectories with the same policy in independent copies of the MDP and sending policy gradient estimates to a trusted central server that updates the policy parameters by (normalized) gradient ascent and broadcasts the updated parameters to all agents (no trajectory data are shared). Among the N agents hide f adversaries that can send arbitrary values to the server. \n\nAn algorithm with optimal sample complexity (to find a globally optimal policy) is provided under standard assumptions. This is the first such result for this specific setting. Its optimality is guaranteed by a lower bound for stochastic gradient descent with adversaries.\n\nExperiments on Mujoco tasks with 3 adversaries out of 10 nodes show the advantages compared to policy gradient algorithms that do not take into account the possible presence of adversarial agents.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The only adjustment that I deem critical has to do with the lower bound (Lemma 4.6 and Remark 4.8). Intuitively, the lower bound does hold for your setting. However, I think that a more formal reduction argument is needed. Is it possible for the \"hard\" linear function by (Alistarh et al., 2018) to appear as the performance function (expected return) of a reasonable policy class in some MDP? By reasonable policy class, ideally, I mean one that satisfies your assumptions 4.1-4.4. If this is not possible, at least a discussion about this and possible mismatches between the upper and the lower bound is required. Another aspect that should be clarified is the dependence on the task horizon, that can only result from an ad-hoc lower bound for MDPs. \n\nRegarding the experiments, the approach is not compared with federated RL algorithms from the literature. It would make sense to compare at least with (Lan et al. 2023) that is policy-based.\n\nMinor issues:\n- Assumption 4.4 does *not* hold for Gaussian policies, unless some sort of clipping is used. cf Assumption 4.1 by Yuan et al. 2022 and the related discussion\n- \"late-iterate\" -> last iterate", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "HsjrKBgRIF", "reviewer": "Reviewer_BVJf", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n1. This work provides the first global convergence sample complexity for federated reinforcement learning under adversarial attacks. Their algorithm and its analysis is compatible with any $(f,\\lambda)-$resilient aggregator, hence they can provide sample complexity results for a bunch of popular algorithms.\n2. This work considers parameterized policy and the result includes a parametrization error characterizes the representational capacity of the policy class.\n3. The assumptions are well listed and discussed.\n4. Besides the theoretical guarantees, they conducted experiments which showed the advantage of the proposed algorithm.\n\n### Weaknesses\n1. In Theorem 4.5, to simplify the expression, they keep only dependence on $\\epsilon, N, \\lambda$. Why is $f$ omitted which I think is an important factor for this problem?\n2. The discussion on the lower bound (i.e., Remark 4.6) is not clear. As one of the contributions listed is to claim the optimal sample complexity under some aggregators, I think the remark on the lower bound should be more comprehensive.\n3. The theory shows for some aggregators, an optimal sample complexity is achieved while for other aggregators, it is not. This finding is not reflected obviously in the experiments. For example, in (a), CWMed (not optimal from theory) has faster convergence rate than MeaMed (optimal from theory).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies federated reinforcement learning under Byzantine attacks. They propose an algorithm for this problem along with a global convergence sample complexity. The algorithm is based on a variance-reduced gradient estimator utilizing Hessian information and is compatible with any $(f,\\lambda)-$Resilient aggregator. They achieve a sample complexity $O\\left(\\frac{1}{\\epsilon^2}\\log(\\frac{1}{\\epsilon})(\\frac{1}{N}+\\lambda^2\\log(N))\\right)$. And they show for some specific aggregator (i.e., some specific $\\lambda$), the sample complexity is of optimal order. They also conduct experiments on continuous tasks to show the advantage of the proposed algorithm.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Refer to the weaknesses I listed. Besides, there are some minor problems. For example, a quantify should be explained if it first appears in the manuscript ($A^{\\pi_\\theta}(s,a)$ in (7)). Some missing brackets ($\\nabla J_H\\theta_t$ in (9)).", "broader_impact_concerns": "There is no concerns on the ethical implications of this work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Qc6plSAsG2", "reviewer": "Reviewer_U4B5", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n- The paper studies an interesting and important problem. \n- The assumptions are clearly listed and the theoretical results are clean. \n- Empirical studies are used to demonstrate the effectiveness of the algorithm. \n\n**Weaknesses:**\n- The main message isn't consistent throughout the paper. From the title, abstract and conclusion, the most important contribution seems to be the algorithm's resilience to adversaries. However, this is not discussed in the \"main contributions\" paragraph of introduction, in section 3 (when discussing the algorithm design) and section 4 (when explaining the theoretical result). \nI believe the algorithm is resilient to adversaries because the information is aggregated by $(f,\\lambda)$-resilient averaging. Currently the readers can only confirm this when reading the proof sketch.\n- Some messages are not accurate. For example, in the abstract, the authors claim achieving optimal sample complexity. However, from Table 1, the optimal sample complexity is achieved only when the MDA aggregator is used. The optimality is not universal across all aggregators, and the only optimal aggregator is NP-hard to compute. Another example is the sample complexity $\\tilde{\\mathcal{O}}(\\frac{1}{\\epsilon^2}\\log(\\frac{1}{\\epsilon}(\\frac{1}{N}+\\lambda^2\\log(N))))$ (in introduction and after theorem 4.5). The dependence of $f$ (or $N-f$) is omitted. I understand that this is neglectable when $f<N/2$. But it's very confusing if parameter $f$ is not in the result, since the aggregator is $(f,\\lambda)$-resilient.\n- Some background information is missing. I understand that many components of the algorithm are from existing result. But it would greatly help if the authors could talk more about the intuitions, or definitions, behind them. Examples include equation (3), line 6-10 of algorithm 1 (i.e. approximation of equation (3)), the word \"Byzantine adversaries\" at the beginning of section 5. \n- To achieve the theoretical result, we need to set $\\gamma_t$ using parameter $\\mu_F$ and $G_1$. However, they may not be accessible in practice. The authors should discuss how to tackle this challenge. \n- Some small mistakes. (i). \"R->r\" in the five-tuple of the first line at the beginning of section2. (ii). A in equation 7 is not defined. (iii). i is not defined on the RHS of the equation right below equation (8). (iv) \"$J_H\\theta_t)$->$J_H(\\theta_t)$\" in equation (9).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper designs an algorithm for FRL with adversarial agents and general policy parameterization by combining the $(f,\\lambda)$-resilient averaging and the N-HARPG from previous literature. Global convergence guarantee is provided, showing resilience of the algorithm to adversaries. Empirical evaluations are also provided.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "According to the weaknesses, the following points, which are critical for acceptance, should be addressed.\n- Make the main message consistent. The authors may talk more about \"resilience to adversaries\" in the \"main contribution\" paragraph, in section 3 (on which parts of the algorithm design enable this resilience), and in section 4 (on how the theorem implies resilience and how it compares to previous literature). \n- The authors may modify the sentences and equations that are inaccurate.\n- The authors may talk more about the missing background definitions and intuitions. \n\nThe following concerns should also be address:\n- The authors should discuss how to set $\\gamma_t$ in practice if we don't know the required parameters, or how to estimate the required parameters.\n- Correct the mistakes.", "broader_impact_concerns": "Nnone of those are considered as necessary to be specifically highlighted here.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies a special but practically relevant setting within reinforcement learning. Multiple decentralized agents are given independent copies of the same MDP. Each of them computes a policy gradient estimate, sends it to a central server that runs a policy gradient algorithm, and then receives the updated parameter from the central server. It is further assumed that among the agents some of them are adversarial, and the goal is to ensure global convergence while being resilient to the adversaries. 

All reviewers found the setting interesting and praised the technical quality of the paper. The proposed algorithm and its analysis combine a few known components from the literature (policy gradient methods and federated learning), but materializing it requires special technical care, which the paper does very well. The reviewers are also satisfied with the writing of the paper, and found the post-rebuttal revision helpful. 

On the flip side, the reviewers found the novelty as a weakness, as the central technical components are somewhat standard. But this does not affect the decision of the paper due to TMLR's emphasis on relevance and correctness. 

Overall, I recommend the paper to be accepted as is.
Decision: Accept (poster)