§ INTRODUCTION

Many real-world reinforcement learning (RL) systems consist of a group of agents (e.g. a fleet of autonomous vehicles), in which all agents aim to learn the same task, each in its local environment. Since RL models often suffer from poor sample complexity, collaboration is highly desirable. However, as in the autonomous driving example, trajectories of environment interactions may be made up of large amounts of video and sensor data (too large to transfer between agents), and possibly also with privacy restrictions. This motivates the need for distributed algorithms that can leverage the power of collaboration without sharing raw trajectories. In the broader machine learning context, this setting has been widely studied under the name Federated Learning (FL) [Kairouz et al., 2021, Li et al., 2020], and has inspired Federated Reinforcement Learning (FRL) [Qi et al., 2021, Zhuo et al., 2019, Fan et al., 2021, Fan et al., 2023] as an analogous concept in RL.

Policy gradient methods are among the most popular algorithms in model-free RL. Existing work studies how to generalize such approaches to FRL in a fully trusted setting [Jiang et al., 2022]. In many practical situations, however, there may not be any guarantee on the trustworthiness of information provided by the participating agents, be it due to e.g. communication failure, or malicious attempts at trying to prevent the system from learning. Methods that tolerate the presence of some fraction of Byzantine agents have previously been proposed and demonstrated to defend against some attacks in practice [Fan et al., 2021]. As we are going to discuss in related work, so far, FRL algorithms need additional non-standard assumptions regarding gradient estimation noise.

Moreover, a crucial limitation of previous methods for achieving Byzantine fault-tolerance is the need for one trusted party responsible for aggregating updates, filtering out potentially malicious inputs, and broadcasting results back to all participants. Introducing such a single point of failure seems like a high price to pay for achieving Byzantine resilience—and is going against the very idea of a trustless and robust design. Hence we are aiming for a decentralized system, i.e., a system in which Byzantine behavior of any participant can be tolerated, as long as only a reasonable number of such bad actors occur simultaneously. Algorithms achieving both Byzantine fault-tolerance and decentralization have previously been proposed for general non-convex optimization [El-Mhamdi et al., 2021] but analyzed only w.r.t. infinite-time asymptotic behavior. We propose a novel method and give finite-time sample complexity guarantees for decentralized federated PG with Byzantine fault-tolerance.

More concretely, our contributions can be summarized as follows:

* As a starting point, we provide a new centralized Byzantine fault-tolerant federated PG algorithm ByzPG, and prove competitive sample complexity guarantees under assumptions that are standard in non-fault-tolerant PG literature. In particular, unlike previous approaches, we do not rely on deterministic bounds on gradient estimation noise.

* For our main contribution, we extend the above (centralized) approach to the significantly more challenging decentralized setting: With DecByzPG, we propose a decentralized Byzantine fault-tolerant PG method. To the best of our knowledge, this is the first decentralized Byzantine fault-tolerant algorithm for non-convex optimization with sample complexity guarantee.

* Technically, we leverage the favorable interplay of fault-tolerant aggregation and agreement mechanisms that so far have only been studied in separation. Key to our analysis is a novel lemma on the concentration of random parameter vectors that helps control the bias incurred from agreement.

* To corroborate our theoretical results regarding both ByzPG and DecByzPG experimentally, we demonstrate speed-up as more agents join a federation, as well as tolerance against different Byzantine attack scenarios.

The rest of this paper is organized as follows: In Section <ref>, we provide the necessary background on RL while covering related work on FRL and fault-tolerance. Section <ref> introduces our setup regarding communication, the Byzantine failure model, and technical assumptions needed for the sample complexity analysis. As a warm-up, in Section <ref>, we introduce our centralized algorithm ByzPG which in Section <ref> is generalized to the decentralized DecByzPG. Finally, our experiments are described and evaluated in Section <ref>.

§ BACKGROUND & RELATED WORK

Reinforcement learning (RL) and policy gradient (PG). The RL setup is commonly modeled as a Markov Decision Process (MDP, see also [Sutton and Barto, 2018]) $\mathcal M:= \{\mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \gamma, \rho\}$ with state space $\mathcal{S}$, action space $\mathcal{A}$, transition dynamics $\mathcal{P}(s^\prime \mid s, a)$, and reward $\mathcal{R}: \mathcal{S} \times \mathcal{A} \mapsto[0, R]$ where $R > 0$, $\gamma \in (0,1)$ is the discount factor, and $\rho$ is the initial state distribution.
Let $\pi$ denote the policy controlling an agent's behavior, i.e., $\pi(a \mid s)$ is the probability that the agent chooses action $a$ at state $s$.
A trajectory $\tau:= \{s_0, a_0, \ldots, s_{H-1}, a_{H-1}\}$ is a sequence of state-action pairs followed by an agent according to a stationary policy $\pi$, where $s_0 \sim \rho$. We define $\mathcal{R}(\tau) :=\sum_{t=0}^{H-1} \gamma^{t} \mathcal{R}\left(s_{t}, a_{t}\right)$ as the cumulative discounted reward for a trajectory $\tau$. Note that here we study episodic MDPs with fixed trajectory horizon $H$.

PG methods are popular in model-free RL [Schulman et al., 2015, Schulman et al., 2017].
Compared to deterministic value-function-based methods, PG is more effective when applied to tasks with high-dimensional or infinite action spaces. Let $\pi_{\theta}$ denote the policy parameterized by $\theta \in \mathbb{R}^d$, and $p(\tau \mid \pi_{\theta})$ the trajectory distribution induced by policy $\pi_{\theta}$. The expected discounted future reward when following $\pi_\theta$ is given by $J(\theta) := \E_{\tau \sim p(\cdot \mid \theta)}\left[\mathcal{R}(\tau) \mid \mathcal M \right]$ whose gradient w.r.t. $\theta$ is

\begin{align*}
\nabla_{\theta} J(\theta)&=\int_{\tau} \mathcal{R}(\tau) \nabla_{\theta} p(\tau \mid \theta) \,d\tau \\
&=\mathbb{E}_{\tau \sim p(\cdot \mid \theta)}\left[\nabla_{\theta} \log p(\tau \mid \theta) \mathcal{R}(\tau) \mid \mathcal M\right].
\stepcounter{equation}\tag{\theequation}\label{def-full-gradient}
\end{align*}

Hence we can use gradient ascent in order to optimize $J(\theta)$ over $\theta \in \R^d$.
Since (<ref>) involves computing an integral over all possible trajectories, we typically use stochastic gradient ascent. In each iteration, a batch of trajectories $\{\tau_i\}_{i=1}^M$ is sampled at the current policy $\theta$. Then, the policy is updated by $\theta \leftarrow \theta + \eta \widehat{\nabla}_{M} J\left(\theta\right)$, where $\eta$ is the step size and $\widehat{\nabla}_{M} J(\theta)$ is an estimate of (<ref>) based on the sampled trajectories $\{\tau_i\}_{i=1}^M$: $\widehat{\nabla}_{M} J(\theta)=\frac{1}{M} \sum_{i=1}^{M} \nabla_{\theta} \log p\left(\tau_{i} \mid \theta \right) \mathcal{R}\left(\tau_{i}\right)$.
Commonly used policy gradient estimators, e.g. REINFORCE [Williams, 1992] and GPOMDP [Baxter and Bartlett, 2001], can be written as

\begin{align*}
\widehat{\nabla}_{M} J(\theta)=\frac{1}{M} \sum_{i=1}^{M} g(\tau_i \mid \theta)
\end{align*}

where $\tau_{i}=\{s_0^i, a_0^i, \ldots, s_{H-1}^{i}, a_{H-1}^{i}\}$ and $g(\tau_i \mid \theta)$ is an unbiased estimate of $\nabla_{\theta} \log p(\tau_{i} \mid  \theta) \mathcal{R}(\tau_{i})$. For more details on gradient estimation and sampling, we refer to Appendix <ref>.

Non-convex optimization. Despite PG's additional challenges of non-stationarity and the non-finite-sum structure, improvements in convergence results in non-convex optimization have generally led to similar progress for optimizing the non-concave $J(\theta)$ in PG. The $\mathcal O( \varepsilon^{-4})$ sample complexity for reaching an $\varepsilon$-stationary point, i.e., $\theta$ such that $\mathbb{E}[\|\nabla J(\theta)\|^2] \leq \epsilon^2$, of SGD [Reddi et al., 2016] and vanilla PG [Papini, 2021] has been lowered to $\mathcal O( \varepsilon^{-10/3})$ by SVRG, and SVRPG [Xu et al., 2020] respectively. These methods rely on an inner loop that reuses old gradient estimates for reduced variance which in the case of SVRPG is implemented via importance sampling. The recently proposed PAGE estimator [Li et al., 2021], and its PG adaptation PAGE-PG [Gargiani et al., 2022], replace the inner loop by a probabilistic switch, lowering the sample complexity to $\mathcal O( \varepsilon^{-3})$.

Fault-tolerance. Byzantine fault-tolerance [Lamport et al., 1982] has long been established as the strongest notion of resilience against arbitrary failure or deliberate manipulation of distributed systems. Regarding previous work in the federated optimization literature, we distinguish between the rather common centralized, and the far less studied decentralized, sometimes called collaborative, setting.

(a) Centralized: In the presence of a trusted coordinator, Byzantine fault-tolerant non-convex optimization has been widely studied—with approaches differing mostly in terms of filtering techniques and problem assumptions [Blanchard et al., 2017, Alistarh et al., 2018, Allen-Zhu et al., 2020]. We refer to [Farhadkhani et al., 2022] for an overview of such commonly used Byzantine-resilient methods for aggregating potentially malicious updates at a central server. Regarding Byzantine-tolerant PG, [Fan et al., 2021] shows promising empirical results. However, theoretical guarantees are proven only under deterministic noise bounds which makes results difficult to appreciate in comparison with non-fault-tolerant methods that do not rely on such assumptions. Recently, [Gorbunov et al., 2023] has proposed a non-convex optimization algorithm leveraging the favorable interplay of certain robust aggregators and the above-mentioned variance-reduced PAGE estimator. Our centralized ByzPG extends their ideas into the PG setting, with a modified algorithm and tightened analysis.

(b) Decentralized: In the PG context, there is no previous work studying decentralized Byzantine-tolerant methods. More generally, [El-Mhamdi et al., 2021] proposes a fault-tolerant algorithm for decentralized non-convex optimization. While convergence is only proven in an infinite-time asymptotic sense, their notion of averaging agreement is shown to be of crucial importance for decentralized learning. Indeed, the notion of $\epsilon$-approximate Byzantine agreement on $d$-dimensional inputs had previously been proposed [Mendes and Herlihy, 2013, Mendes et al., 2015]. However, unlike averaging agreement, such methods show poor applicability in our setting since the fraction of tolerable Byzantines goes to zero as $d$ increases.

§ SETUP AND ASSUMPTIONS

§.§ Distributed Computing Setup

Communication is assumed to happen in a round-based, synchronous, all-to-all manner among $K$ agents, and the exchange of raw trajectories is prohibited. In particular, our algorithms will only involve sending current values of local policy parameters and respective gradients.

In order to model both system failure as well as malicious agent behavior, we tolerate a fraction of Byzantine agents, in particular:
[Byzantine agents]

Let $\alpha_{\max}=1/2$ in the centralized setting, and $\alpha_{\max}=1/4$ in the decentralized setting, respectively. Denote by $\mathcal H_t \subset [K]$ the set of honest (i.e. non-Byzantine) agents in iteration $t$ of an algorithm. Then there exist $\alpha,\bar\epsilon>0$ such that $\bar\alpha:=\alpha + \bar\epsilon < \alpha_{\max}$ and for all $t$, $\mathcal |\mathcal H_t| \geq (1-\alpha)K$.

We point out that $\mathcal H_t$ may be different for each iteration $t$, hence it is of no use for any agent to remember past communication in order to infer who might be Byzantine.

Instead of sending updates as prescribed by our algorithms, Byzantine agents may send arbitrary values. In particular, these values may be chosen by an omniscient entity with access to all information (e.g. agents' local state, messages that have been sent, the definition of the algorithm, who is Byzantine, etc.) and controlling all Byzantine agents. This means Byzantine agents may collude or base their behavior on any other non-public information. However, Byzantine agents are not omnipotent, e.g. they cannot interfere in communication between honest agents by changing or delaying messages. Moreover, we assume that Byzantines cannot alter local state, not even their own state. In the centralized case, this assumption does not change anything, since our algorithm ByzPG only maintains cross-iteration state at the trusted central agent. In the decentralized case, however, corrupted local state may otherwise be passed on from a Byzantine agent to an honest agent across iterations.
Note also that in particular, any agent not sending messages in the required format or omitting updates, potentially due to failure of the communication network, can be modeled as Byzantine.

§.§ Reinforcement Learning Assumptions

Our theoretical analysis aims to bound the required number of sampled trajectories required per agent in order to reach an $\epsilon$-stationary solution. In the centralized case, this refers to the central agent finding $\theta \in \R^d$ such that $\|\nabla J ( \theta ) \| \leq \epsilon$ which can then be broadcast to all participants. A generalized solution concept for the decentralized setting is presented in Section <ref>.

In the following, we state the set of assumptions our analysis is based on, which is standard in the study of PG, see e.g. [Papini et al., 2018, Xu et al., 2020, Yuan et al., 2020, Gargiani et al., 2022]. In particular, we do not require a more restrictive version of Assumption <ref> made in [Fan et al., 2021]. Hence, our sample complexity results are amenable to comparison with non-fault tolerant counterparts.

Note that we are assuming homogeneity of all agents' local environments, and all agents hence share the same objective $J(\cdot)$.
[Log-policy gradient norm]
For any $a \in \mathcal{A}$ and $s \in \mathcal{S}$, there exists a constant $G>0$ such that for any $\theta \in \mathbb{R}^d$ we have $\left\|\nabla_\theta \log \pi_\theta(a \mid s)\right\| \leq G$.

[Log-policy smoothness]
For any $\theta \in \mathbb{R}^d$, $\pi_\theta$ is twice differentiable, and for any $a \in \mathcal{A}$ and $s \in \mathcal{S}$, there exists a constant $M>0$ such that $\left\|\nabla_\theta^2 \log \pi_\theta(a \mid s)\right\| \leq M$.

[Gradient estimator variance]
There exists a constant $\sigma>0$ such that for any $\theta \in \mathbb{R}^d$, we have $\operatorname{Var}\left[g(\tau \mid \theta)\right] = \mathbb{E}\|g(\tau\mid\theta) - \nabla J(\theta)\|^2 \leq \sigma^2$.

[Importance weight variance]
For any policy pair $\theta_a, \theta_b \in \mathbb{R}^d$ and $\tau \sim p\left(\cdot \mid \theta_b\right)$, the importance weight $\omega\left(\tau \mid \theta_b, \theta_a\right)=\frac{p\left(\tau \mid \theta_a\right)}{p\left(\tau \mid \theta_b\right)}$ is well-defined. In addition, there exists a constant $W>0$ such that $\operatorname{Var}\left[\omega\left(\tau \mid \theta_b, \theta_a\right)\right] \leq W \| \theta_a-\theta_b \|^2$.

For completeness, we restate the following commonly used proposition from [Xu et al., 2020].

Under the above assumptions <ref>, <ref>, <ref>, and <ref>, with $g(\tau\mid\theta)$ denoting the REINFORCE or GPOMDP gradient estimator, we have for all $\theta,\theta_1,\theta_2 \in \R^d$:

* $\left\| g_k(\tau \mid \theta) \right\| \leq C_g$ with $C_g=HG(R+|C_b|)/(1-\gamma)$ and $C_b$ is the baseline reward,

* $\left\| g(\tau\mid\theta_1)-g(\tau\mid\theta_2) \right\| \leq L_g \left\| \theta_1-\theta_2 \right\|$ with $L_g=HM(R+|C_b|)/(1-\gamma)$, and

* $J(\theta)$ is $L$-smooth with $L=HR(M+ HG^2)/(1-\gamma)$.

§ CENTRALIZED BYZANTINE-TOLERANT FEDERATED PG

In this section, we describe ByzPG, given by Algorithm <ref>, our centralized method for Byzantine fault-tolerant PG. This also serves as a warm-up for introducing parts of our method that are going to reappear in Section <ref>. Note that in Algorithm <ref>, $\operatorname{Be} \left( p \right)$ denotes a Bernoulli distribution with success probability $p$ and $\mathcal U(S)$ denotes a uniform distribution over a finite set $S$.

ByzPG at server agent

[1]
input: $\theta_0 \in \mathbb R^d$, large batch size $N$, small batch size $B$, step size $\eta$, probability $p \in (0,1]$
$t=0$ to $T-1$
$c_t \leftarrow \operatorname{\textbf{Sample}} \left( \operatorname{Be} \left( p \right) \right)$
$c_t=1$ or $t=0$
worker agent $k \in [K]$ in parallel
sample trajectories $\{\tau_{t,i}^{(k)}\}_{i=1}^{N}$ from $p(\cdot \mid \theta_{t})$
$\widetilde{v}_t^{(k)}=\frac{1}{N}\sum_{i=1}^N g(\tau_{t,i}^{(k)} \mid \theta_t)$
$v_t \leftarrow \operatorname{\textbf{Aggregate}}\left( \langle \widetilde{v}_t^{(k)} \rangle_{k=1}^{K} \right)$
$\widetilde{v}_t^{(k)}$ received from worker agent $k$, $\forall k \in [K]$
sample trajectories $\{\tau_{t,i}\}_{i=1}^{B}$ from $p(\cdot \mid \theta_{t})$
$v_t=\frac{1}{B}\sum_{i=1}^B g(\tau_{t,i} \mid \theta_t )+v_{t-1}-\frac{1}{B}\sum_{i=1}^B g^{\omega_{\theta_t}}\left( \tau_{t,i} \mid \theta_{t-1} \right)$
$\theta_{t+1}=\theta_t+\eta v_t$
broadcast $\theta_{t+1}$ to worker agents
output: $\theta_{\widehat{T}}$ with $\widehat{T} \sim \mathcal U \left([T]\right)$

§.§ Method

Instead of the usual inner loop seen in variance-reduced methods such as SVRPG [Papini et al., 2018], we probabilistically switch between update types, as in PAGE-PG [Gargiani et al., 2022]. Concretely, in each iteration, we either (a) sample a large batch of $N$ trajectories at $\theta_t$ for gradient estimation, or (b) sample a small batch of $B$ trajectories and use a variance-reduced estimator incorporating the previous iteration's gradient estimate, and employ importance sampling to correct for non-stationarity. For details on gradient estimation, importance sampling, and the definition of $g^{\omega_{\theta_t}}\left( \tau_{t,i} \mid \theta_{t-1} \right)$ we refer to Appendix <ref>. Note that with probability $p$ we use (a), and (b) otherwise—except for the first iteration, in which only (a) is well-defined. Furthermore, (a) is performed at all worker agents in parallel which have previously received the current parameters $\theta_t$ from the server agent. Then, the individual estimates $\widetilde{v}_t^k$ are aggregated at the server via the Aggregate subroutine described below. In the case of (b), we sample and estimate the gradient only at the server, hence there is no need for aggregation.

We point out that loopless variance-reduction has previously been used in conjunction with Byzantine fault-tolerant aggregation in [Gorbunov et al., 2023]'s Byz-VR-Marina. However, ByzPG distinguishes itself in two ways:

* ByzPG only samples at workers in case (a) while Byz-VR-Marina does so in either case. Our analysis suggests that unlike in case (a), in (b), the bias introduced by Byzantine filtering outweighs the benefits from the reduced variance of the aggregated sample. In our PG setting, this modification is key to achieving sample complexity competitive with non-fault-tolerant methods.

* Byz-VR-Marina is designed for general non-convex finite-sum optimization. ByzPG handles the additional challenges of non-stationarity and not having access to the full gradient by relying on importance sampling and switching between a large and small batch size.

The following notion of robust aggregation specifying our requirements on the Aggregate subroutine is adopted from [Gorbunov et al., 2023] and has first appeared in a similar form in [Karimireddy et al., 2021].

Let $C_{ra} > 0$ and $\alpha \in [0,1/2)$. A function $\operatorname{\textbf{Aggregate}}:(\mathbb R^d)^K \to \mathbb R^d$ is an $(\alpha,C_{ra})$-robust aggregator if for any tuple of inputs $\langle \theta^{(k)} \rangle_{k \in [K]}$ with $\theta^{(k)} \in \mathbb R^d$, and for any $\mathcal H \subseteq K$ with $|\mathcal H| \geq (1-\alpha)K$, denoting $\hat{\theta} := \operatorname{\textbf{Aggregate}}(\theta^{(1)},\dots,\theta^{(K)})$, it holds that

\begin{align*}
\mathbb E \left[ \| \hat{\theta}-\bar{\theta} \|^2 \right] \leq \frac{C_{ra} \alpha}{|\mathcal H|(|\mathcal H|-1)} \sum_{i,l \in \mathcal H} \mathbb E \left[ \| \theta^{(i)}-\theta^{(l)} \|^2 \right]
\end{align*}

where $\bar{\theta}:=\frac{1}{|\mathcal H|}\sum_{i \in \mathcal H} \theta^{(i)}$. Expectations are taken over the randomness of the input.

Known implementations satisfying Definition <ref> are discussed in Appendix <ref>. In particular, there exist $(\alpha,C_{ra})$-robust aggregators for constant $C_{ra}$ and any $\alpha \in [0,1/2)$.

§.§ Convergence Analysis and Sample Complexity

Next, we present the convergence guarantees for ByzPG, with proofs deferred to Appendix <ref>.

Let Assumptions <ref>, <ref>, <ref>, and <ref> hold.
Suppose Aggregate is an $(\alpha,C_{ra})$-robust aggregator with constant $C_{ra} > 0$ and $\alpha$ satisfying Assumption <ref>. Then the following holds for the output of ByzPG, i.e., Algorithm <ref>: For $\eta = \Theta(\min\{ \sqrt{pK},1/L\})$, there exists a constant $C>0$, such that for any $T \geq 1$,

\begin{align*}
\E \left[\| \nabla J \left( \theta_{\widehat{T}} \right) \|^2 \right] \leq \frac{2 \E \left[ \Phi_0 \right]}{\eta T} + \frac{C \sigma^2}{N} \left( \alpha+\frac{1}{K} \right)
\end{align*}

with $\Phi_0 := J^{*} - J \left( \theta_0 \right) + \frac{\eta}{p} \left\| v_0 - \nabla J \left( \theta_0 \right) \right\|^2$ and $J^{*}:=\max_{\theta \in \R^d} J(\theta)$.

In the setting of Theorem <ref>, by choosing $p=1/N$, the expected number of trajectories that need to be sampled per agent to achieve $\E[ \| \nabla J \left( \theta_{\widehat{T}} \right) \|^2] \leq \epsilon^2$ is

\begin{align*}
\mathcal O \left( \frac{\alpha^{1/2}}{K^{1/2}\epsilon^3}+\frac{1}{K \epsilon^3} \right).
\end{align*}

Observe that in particular, if $\alpha=0$, we need $\mathcal O(K^{-1} \epsilon^{-3})$ trajectories in expectation, and for constant $\alpha > 0$, we need $\mathcal O(K^{-1/2}\epsilon^{-3})$ trajectories in expectation. We hence recover the SOTA sample complexity of PAGE-PG [Gargiani et al., 2022] (which is proven under assumptions equivalent to ours) for $K=1$, and asymptotically improve for larger $K$, despite the presence of Byzantines.

§ DECENTRALIZED BYZANTINE-TOLERANT FEDERATED PG

DecByzPG at the $k$-th agent

[1]
input: $\theta_0 \in \mathbb R^d$, large batch size $N$, small batch size $B$, step size $\eta$, probability $p \in (0,1]$
initialize $\theta_0^{(k)}=\theta_{0}$
$t=0$ to $T-1$
$c_t \leftarrow \operatorname{\textbf{Common-Sample}} \left( \operatorname{Be} \left( p \right) \right)$
sample trajectories $\{\tau_{t,i}^{(k)}\}_{i=1}^{M}$ from $p(\cdot \mid \theta_{t}^{(k)})$ where $M = \begin{cases}N &\text{ if $c_t=1$ or $t=0$}\\B & \text{ else}\end{cases}$

\frac{1}{N} \sum_{i=1}^N g(\tau_{t,i}^{(k)} \mid \theta_t^{(k)}) \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\;\;\text{if $c_t=1$ or $t=0$}  \\[4pt]
\frac{1}{B} \sum_{i=1}^B g(\tau_{t,i}^{(k)} \mid \theta_t^{(k)})+\frac{1}{\eta}(\theta_{t}^{(k)}-\theta_{t-1}^{(k)})-\frac{1}{B} \sum_{i=1}^B g^{\omega_{\theta_t^{(k)}}}( \tau_{t,i}^{(k)} \mid \theta^{(k)}_{t-1}) \quad\text { else}
\end{cases}$

$v_t^{(k)} \leftarrow \operatorname{\textbf{Aggregate}}\left( \langle \widetilde{v}_t^{(k')} \rangle_{k'=1}^{K} \right)$
$\widetilde{\theta}^{(k)}_{t+1}=\theta_t^{(k)}+\eta v_t^{(k)}$

$\theta_{t+1}^{(k)} \leftarrow \textbf{Avg-Agree}_{\kappa}\left( \langle \widetilde{\theta}_{t+1}^{(k')} \rangle_{k'=1}^K \right)$

output: $\theta_{\widehat{T}}^{(k)}$ with $\widehat{T} \sim \textbf{Common-Sample}\left( \mathcal U \left( [T] \right) \right)$

§.§ Method

In the decentralized setting, instead of having a centrally maintained $\theta_t \in \R^d$, the state at each iteration $t$ is given by a tuple $\langle \theta^{(k)}_t \rangle_{k \in [K]}$ of each agent's local parameters with $\theta^{(k)}_t \in \R^d$. We are interested in the following solution concept.

For $\epsilon>0$, we call $\langle \theta^{(k)} \rangle_{k \in [K]}$ with $\theta^{(k)} \in \R^d$ a $K$-agent $\alpha$-tolerant $\epsilon$-stationary point if $\exists \mathcal G \subset [K]$ such that $|\mathcal G| \geq (1-\alpha)K$ and $\forall k \in \mathcal G$, we have $\|\nabla J ( \theta^{(k)} ) \| \leq \epsilon$. We say a decentralized algorithm achieves a $K$-agent $\alpha$-tolerant $\epsilon$-approximate solution in $T$ rounds if $\exists \mathcal G_T \subset [K]$ such that $|\mathcal G_T| \geq (1-\alpha)K$ and $\forall k \in \mathcal G_T$, we have $\mathbb{E} [ \|\nabla J ( \theta_T^{(k)} ) \|^2 ] \leq \epsilon^2$, where $\theta_T^{(k)}$ is the output of agent $k$ after $T$ rounds and the expectation is taken w.r.t. all randomness of the algorithm.

As a first step towards decentralizing ByzPG, suppose all agents simultaneously execute ByzPG, each with itself in the role of the server, and denote the $k$-th agent's resulting local parameters in iteration $t$ by $\tilde{\theta}^{(k)}_t$. Since Byzantines may send inconsistent gradient estimates to different agents, already after the first iteration, we may have $\widetilde{\theta}_1^{(k)}\not=\widetilde{\theta}_1^{(k')}$ for $k \not= k'$. Such disagreement on parameters across agents may be detrimental to convergence at each agent.
As a remedy, we adopt the notion of averaging agreement that has been proposed by [El-Mhamdi et al., 2021] in the context of Byzantine fault-tolerant collaborative learning.

Let Avg-Agree$_{\kappa}$ be a decentralized algorithm that as input receives $\langle \theta^{(k)} \rangle_{k \in [K]}$ where $\theta^{(k)} \in \mathbb R^d$ is known only to agent $k$. Under Assumption <ref>, let $\mathcal G_t \subseteq \mathcal H_t$ be such that $|\mathcal G_t| \geq (1-\bar\alpha)K$. Suppose after $\kappa$ rounds of communication, where $\kappa \in \mathbb N$ is a parameter of the algorithm, Avg-Agree$_{\kappa}$ terminates with output $\langle \hat{\theta}^{(k)} \rangle_{k \in \mathcal G_t}$ in the form of $\hat{\theta}^{(k)} \in \mathbb R^d$ being known to agent $k$. Then, we say Avg-Agree$_{\kappa}$ achieves $C_{avg}$-averaging agreement for some $C_{avg}>0$, if for any input it is guaranteed that

\begin{align*}
\max_{i,l \in \mathcal G_t} \| \hat{\theta}^{(i)}-\hat{\theta}^{(l)} \| &\leq \frac{\max_{i,l \in \mathcal G_t} \| \theta^{(i)}-\theta^{(l)} \|}{2^\kappa} \quad\text{ and} \\
\| \bar{\hat{\theta}} - \bar{\theta} \| &\leq C_{avg} \cdot \max_{i,l \in \mathcal G_t} \| \theta^{(i)}-\theta^{(l)} \|
\end{align*}

where $\bar{\theta}=\frac{1}{|\mathcal G_t|}\sum_{k \in \mathcal G_t} \theta^{(k)}$ and $\bar{\hat{\theta}}=\frac{1}{\left| \mathcal G_t \right|}\sum_{k \in \mathcal G_t} \hat{\theta}^{(k)}$.

Known implementations satisfying the above definition are stated and discussed in Appendix <ref>. Our algorithm DecByzPG, as described by Algorithm <ref>, employs an Avg-Agree$_\kappa$ subroutine at the end of each iteration to ensure averaging agreement on agents' local parameters.

We point out that while [El-Mhamdi et al., 2021] makes use of averaging agreement in a similar context, their analysis does not yield sample complexity results. Our improved results rely upon the following insights:

* Careful analysis of bias and variance of the realized gradient estimates, which we define as $\hat{v}^{(k)}_t:=\frac{1}{\eta} \left( \theta_{t+1}^{(k)}-\theta_t^{(k)} \right)$, reveal that variance-reduced methods combined with the notion of robust aggregation from Definition <ref> show favorable interplay with averaging agreement. In particular, the low variance of intermediate estimates $\widetilde{v}^{(k)}_t$ and $v^{(k)}_t$ keep the bias introduced by Avg-Agree$_\kappa$ small.

* Controlling this bias introduced by Avg-Agree$_\kappa$ further requires a bound on the expected diameter of agents' parameters before agreement, i.e., the $\tilde{\theta}^{(k)}_{t+1}$'s. We leverage the fact that only the diameter of some large subset of parameters needs to be bounded, allowing us to apply strong concentration bounds instead of a weak union bound.

In place of Sample in Line <ref> of Algorithm <ref>, DecByzPG requires a distributed Byzantine fault-tolerant sampling procedure. While such implementations have been studied in theory [Cachin and Shoup, 2000], in practice, we may simply use a pseudorandom generator with a seed derived from the common initialization $\theta_0$.

§.§ Convergence Analysis and Sample Complexity

We next present sample complexity guarantees for DecByzPG, and provide a proof sketch outlining key ideas required for the analysis.

Let Assumptions <ref>, <ref>, <ref>, and <ref> hold.
Suppose Aggregate is an $(\alpha,C_{ra})$-robust aggregator for constant $C_{ra} > 0$ and $\alpha$ as in Assumption <ref>. Let further Avg-Agree$_\kappa$ achieve $C_{avg}$-averaging agreement for constant $C_{avg}>0$. For $A=\Theta \left( \frac{\alpha}{p^2}+\frac{1}{pK} \right)$, choose $\eta = \frac{1}{2}\min \left\{ \frac{1}{\sqrt{A}}, \frac{1}{L} \right\}$, and $\kappa=\Theta \left( \log\frac{NK}{p^2} \right)$. Then the following holds for the output of DecByzPG, i.e., Algorithm <ref>: There exists a constant $C>0$ such that for any $T \geq 1$, $\exists \mathcal G_{\widehat{T}} \subset [K]$ with $|\mathcal G_{\widehat{T}}| \geq (1-\bar\alpha)K$ and $\forall k \in \mathcal G_{\widehat{T}}$,

\begin{align*}
\E \left[ \left\| \nabla J \left( \theta^{(k)}_{\widehat{T}} \right) \right\|^2 \right] \leq \frac{4 \E \left[ \Phi_0 \right]}{\eta T} + \frac{C\sigma^2}{N} \left( \alpha+\frac{1}{K} \right)+\mathcal O \left( 2^{-\kappa} \right)
\end{align*}

where we define $\Phi_0:=J^{*} - J \left(\theta_0\right)+\frac{2\eta}{p} \left\| \frac{1}{K}\sum_{k \in [K]}\hat{v}_0^{(k)}-\nabla J \left( \theta_0 \right) \right\|^2$ with $J^{*}:=\max_{\theta \in \R^d} J(\theta)$.

In the setting of Theorem <ref>, by choosing $p=1/N$ and $\kappa=\Theta \left( \max \left\{ \log \left( NK \right),\log \left( \epsilon^{-1} \right) \right\} \right)$, the expected number of trajectories that need to be sampled per agent, to achieve a $K$-agent $\bar\alpha$-tolerant $\epsilon$-approximate solution as in Definition <ref>, is

\begin{align*}
\mathcal O \left( \frac{\alpha^{3/2}}{\epsilon^4}+\frac{\alpha^{1/2}}{K\epsilon^4}+\frac{\alpha^{1/2}}{K^{1/2}\epsilon^3}+\frac{1}{K\epsilon^3} \right).
\end{align*}

In particular, if $\alpha=0$, we need $\mathcal O (K^{-1}\epsilon^{-3})$ trajectories in expectation which matches with our respective result from Corollary <ref>. The same sample complexity has been obtained in [Jiang et al., 2022] for a momentum-based decentralized PG method that, however, lacks fault-tolerance. For constant $\alpha > 0$, we need $\mathcal O(\epsilon^{-4})$ trajectories in expectation which in our setting matches for example the complexity of single-agent vanilla PG [Papini, 2021]. If, e.g., a constant number of agents are Byzantine, i.e., $\alpha=\Theta(K^{-1})$, we get a complexity of $\mathcal O(K^{-3/2}\epsilon^{-4}+K^{-1}\epsilon^{-3})$. Hence asymptotic speed-up w.r.t. the number of agents is possible despite the presence of Byzantine agents.

Besides sample complexity, we prefer algorithms with low communication complexity. Due to Avg-Agree$_{\kappa}$, each of the $T$ iterations of DecByzPG involves $\kappa=\Theta( \max \{ \log (NK),\log (\epsilon^{-1})\})$ rounds of all-to-all communication, each consisting of $\mathcal O(K^2)$ messages containing a vector in $\R^d$. We point out that the logarithmic number of rounds is crucial for the practicality of our decentralized algorithm, as otherwise the cost of communication may outweigh the benefits of the lower sample complexity gained from collaboration.

Due to space constraints, the full proofs of Theorem <ref> and Corollary <ref>, as well as all required lemmas are deferred to Appendix <ref>. Here, we want to focus on one key argument of the proof responsible for controlling the diameter of agents' local parameters. Before stating and proving the two respective lemmas, we introduce additional notation: Recall that $\mathcal H_t \subset [K]$ is the set of honest, i.e., non-Byzantine agents as in Assumption <ref> with $|\mathcal H_t|\geq (1-\alpha) K$. In addition, with $\bar\alpha=\alpha+\bar\epsilon < \alpha_{\max} = 1/4$, denote the diameter of a tuple of vectors by $\Delta_2 \left( \cdot \right)^2$, e.g., for some $S \subseteq [K]$, let

\begin{align*}
\Delta_2 \left( \langle \theta_t^{(i)} \rangle_{i \in S} \right) := \max_{i,j \in S} \| \theta_t^{(i)}-\theta_t^{(j)} \|
\end{align*}

and consider the set

\begin{align*}
\mathcal G_t := \argmin_{S \subset \mathcal H_t, |S| \geq (1-\bar\alpha)K} \Delta_2 \left( \langle \tilde{\theta}_t^{(i)} \rangle_{i \in S} \right) \subset \mathcal H_t
\end{align*}

which we will call the set of good agents. As we will show below, the diameter of good agents' parameters exhibits good concentration in the sense that we obtain stronger bounds as would hold for the expected diameter of all honest agents' parameters. The diameter of good agents' parameters after agreement will frequently occur as an error term which we denote by

\begin{align}
\label{eqn:diam-bound}
\mathcal E^{\Delta}_t:=\Delta_2 \left( \langle \theta_t^{(i)} \rangle_{i \in \mathcal G_t} \right)^2.
\end{align}

Finally, we abbreviate

\begin{align*}
\widetilde{\mathcal T}_{1,t} &:= \frac{1}{|\mathcal G_t|(|\mathcal G_t|-1)} \sum_{i,l \in \mathcal G_t} \E \left[ \| \tilde{v}_t^{(i)}-\tilde{v}_t^{(l)} \|^2 \mid c_t=1 \right], \\
\widetilde{\mathcal T}_{0,t} &:= \frac{1}{|\mathcal G_t|(|\mathcal G_t|-1)} \sum_{i,l \in \mathcal G_t} \E \left[ \| \tilde{v}_t^{(i)}-\tilde{v}_t^{(l)} \|^2 \mid c_t=0 \right].
\end{align*}

The following lemma bounds the diameter of good agents' parameters after aggregation and before agreement in iteration $t$, distinguishing between the two cases given by the probabilistic switch.

For any $\bar{\epsilon}>0$, it holds that

\begin{align*}
\E \left[ \Delta_2 \left( \langle \tilde{\theta}_{t+1}^{(i)} \rangle_{i \in \mathcal G_t} \right)^2 \mid c_t=1 \right] &\leq 2 \E[\mathcal E^\Delta_t] + \frac{10 \eta^2C_{ra}\alpha\widetilde{\mathcal T}_{1,t}}{\bar{\epsilon}},\\
\E \left[ \Delta_2 \left( \langle \tilde{\theta}_{t+1}^{(i)} \rangle_{i \in \mathcal G_t} \right)^2 \mid c_t=0 \right] &\leq 2 \E[\mathcal E^\Delta_t] + \frac{10 \eta^2C_{ra}\alpha\widetilde{\mathcal T}_{0,t}}{\bar{\epsilon}}.
\end{align*}

First, we define

\begin{align*}
S_t := \argmin_{S \subset \mathcal G_t, |S| \geq (1-(\alpha+\bar{\epsilon}))K} \Delta_2 \left( \langle v^{(i)}_t \rangle_{i \in S_t} \right) \subset \mathcal H_t \subset [K]
\end{align*}

and aim to bound $\E\left[ \Delta_2(\langle v^{(i)}_t \rangle_{i \in S_t})^2 \right]$. Observe that we have

\begin{align*}
\Delta_2 \left( \langle v^{(i)}_t \rangle_{i \in S_t} \right)^2 \leq \max_{i \in S_t} \| \bar{\tilde{v}}_t-v^{(i)}_t \|^2.
\end{align*}

For $i \in \mathcal H_t$, let $\overline{\mathcal T}_i$ be such that $\E[ \| \bar{\tilde{v}}_t-v^{(i)}_t \|^2] \leq \overline{\mathcal T}_i$ (we will plug in the right bound $\overline{\mathcal T}_i$ later) where $\bar{\tilde{v}}_t:= \frac{1}{|\mathcal G_t|} \sum_{i \in \mathcal G_t} \tilde{v}^{(i)}_t$, and let $X_i$ be indicator random variables for the events

\begin{align*}
\| \bar{\tilde{v}}_t-v^{(i)}_t \|^2 \geq \frac{2}{\bar\epsilon} \cdot \overline{\mathcal T}_i.
\end{align*}

Let $X=\sum_{i \in \mathcal H_t} X_i$. Our goal is to upper bound $\E X_i=\Pr \left[ X_i=1 \right]$ in order to use Chernoff concentration bounds on $X$.

By Lemma <ref> (see Appendix <ref>), we get

\begin{align*}
\pr \left[ X_i=1 \right] &= \pr \left[ \| \bar{\tilde{v}}_t-v^{(i)}_t \|^2 \geq \frac{2}{\bar \epsilon} \cdot \overline{\mathcal T}_i \right] \\
&\leq \pr \left[ \| \bar{\tilde{v}}_t-v^{(i)}_t \|^2 \geq \frac{2}{\bar \epsilon} \cdot \E \left[ \| \bar{\tilde{v}}_t-v^{(i)}_t \|^2 \right] \right] \\
&= \pr \left[ \| \bar{\tilde{v}}_t-v^{(i)}_t \| \geq \sqrt{\frac{2}{\bar \epsilon}} \cdot \sqrt{\E \left[ \| \bar{\tilde{v}}_t-v^{(i)}_t \|^2 \right]} \right] \\
&\leq \frac{\E \left[ \| \bar{\tilde{v}}_t-v^{(i)}_t \|^2 \right]}{\frac{2}{\bar \epsilon} \E \left[ \| \bar{\tilde{v}}_t-v^{(i)}_t \|^2 \right]} \\
&= \frac{\bar \epsilon}{2}.
\end{align*}

Let $E$ be the “bad case”, i.e., the event that we have $X \geq (\bar{\epsilon}+\alpha)K$. By Lemma <ref> (see Appendix <ref>), with $\delta=1+\frac{2\alpha}{\bar \epsilon}$ and $\hat{p}$ as bounded above, we get

\begin{align*}
\pr[E] = \pr \left[ X \geq (\bar{\epsilon}+\alpha)K \right] &= \pr \left[ X \geq \left( 1+\delta \right) \frac{\bar{\epsilon}K}{2} \right] \\
&\leq \exp \left( -\frac{\delta^2 \bar \epsilon K}{4+2\delta} \right) \\
&= \exp \left( -\frac{K(2\alpha+\bar\epsilon)^2}{4\alpha+6\bar\epsilon} \right) \\
&\leq \exp \left( -\frac{\bar\epsilon K}{6} \right).
\end{align*}

With $\overline{\mathcal T}:=\max_{i \in \mathcal H_t} \overline{\mathcal T}_i$, by the law of total expectation, we then have

\begin{align*}
\E \left[ \Delta_2 \left( \langle v^{(i)}_t \rangle_{i \in S_t} \right)^2 \right] &\leq \E \left[ \Delta_2 \left( \langle v^{(i)}_t \rangle_{i \in S_t} \right)^2 \mid \bar{E} \right] \cdot \underbrace{\pr \left[ \bar{E} \right]}_{\leq 1} \\
&\quad\quad+ \E \left[ \Delta_2 \left( \langle v^{(i)}_t \rangle_{i \in S_t} \right)^2 \mid E \right] \cdot \pr \left[ E \right] \\
&\leq \frac{2}{\bar{\epsilon}} \overline{\mathcal T} + K \overline{\mathcal T} \cdot \exp \left( -\frac{\bar{\epsilon}K}{6} \right) \\
&\leq \frac{5}{\bar{\epsilon}} \overline{\mathcal T}
\end{align*}

where in the first step, for the expectation conditioned on $E$ we union-bound the $\max$ by introducing a factor $K$, and in the second step we use the fact that the function $f(x)=xe^{-\beta x}$ has a global maximum with value $\frac{1}{\beta e}$.

Remains to use this bound on $\E[ \Delta_2(\langle v^{(i)}_t \rangle_{i \in S_t})^2]$ in order to obtain the desired bound on $\E[ \Delta_2(\langle \tilde{\theta}^{(i)}_{t+1} \rangle_{i \in \mathcal G_t})^2]$ which follows straightforwardly since

\begin{align*}
&\E \left[ \Delta_2 \left( \langle \tilde{\theta}^{(i)}_{t+1} \rangle_{i \in \mathcal G_t} \right)^2 \right] \\
= \;&\E \left[ \max_{i,l \in \mathcal G_t} \| \tilde{\theta}_{t+1}^{(i)}-\tilde{\theta}_{t+1}^{(l)} \|^2 \right]\\
\leq \;&2 \E \left[ \max_{i,l \in \mathcal G_t} \| \theta_{t}^{(i)}-\theta_{t}^{(l)} \|^2 \right]+2\eta^2 \E \left[ \max_{i,l \in \mathcal G_t} \| v_t^{(i)}-v_t^{(l)}\|^2 \right] \\
\leq \;&2 \E[\mathcal E^\Delta_t] + 2 \eta^2 \E \left[ \Delta_2 \left( \langle v^{(i)}_t \rangle_{i \in S_t} \right)^2 \right] \\
\leq \;&2 \E[\mathcal E^\Delta_t] + \frac{10\eta^2}{\bar{\epsilon}}  \overline{\mathcal T}.
\end{align*}

What can we plug in for $\overline{\mathcal T}$? Observe that $v_t^{(i)}$ is the result of aggregation of inputs with average $\bar{\tilde{v}}_t:= \frac{1}{|\mathcal G_t|} \sum_{i \in \mathcal G_t} \tilde{v}^{(i)}_t$. Therefore, by Definition <ref>, for any $i \in \mathcal G_t$, we have

\begin{align*}
\E \left[ \| v_t^{(i)}-\bar{\tilde{v}}_t \|^2 \right]
&\leq \frac{C_{ra} \alpha}{|\mathcal G_t|(|\mathcal G_t|-1)} \sum_{i,l \in \mathcal G_t} \E \left[ \| \tilde{v}_t^{(i)}-\tilde{v}_t^{(l)} \|^2 \right].
\end{align*}

Thus, we can distinguish between conditioning our expectation on $c_t=0$ and $c_t=1$ and using the respective bounds $C_{ra}\alpha \widetilde{\mathcal T}_{0,t}$ and $C_{ra}\alpha \widetilde{\mathcal T}_{1,t}$, the result follows.

With this bound on the diameter of intermediate local parameters $\tilde\theta_t^{(i)}$ at hand, we can now derive the desired bound on parameters after agreement that only depends on the averaging agreement parameter $\kappa$.

For all iterations $t \leq T$, there exists $\overline{\mathcal E}^{\Delta,\kappa}$ such that $\E [\mathcal E^{\Delta}_t] \leq \overline{\mathcal E}^{\Delta,\kappa}$ and

\begin{align*}
\overline{\mathcal E}^{\Delta,\kappa} \leq \mathcal O \left( 2^{-\kappa} \right).
\end{align*}

We proceed by induction on $t$. For $t=0$, $\mathcal E_t^{\Delta}=0$ due to the common initialization $\theta^{(k)}=\theta_0$ for all $k \in [K]$. Suppose for some $t<T-1$, $\E[\mathcal E_t^{\Delta}] \leq \overline{\mathcal E}^{\Delta,\kappa} \leq \mathcal O \left( 2^{-\kappa} \right)$. In iteration $t$, applying Lemma <ref> and the bounds on $\widetilde{\mathcal T}_{0,t}$ and $\widetilde{\mathcal T}_{0,t}$ from Lemma <ref> (see Appendix <ref>), one can observe that in both cases $c_{t-1}=1$ and $c_{t-1}=0$, the expected diameter of $\tilde{\theta}_t^{(i)}$'s for good agents $i \in \mathcal G_t$ is (loosely) bounded by $\mathcal O(1)$. Hence by the definition of averaging agreement, see Definition <ref>, we have $\E \left[ \mathcal E_t^{\Delta} \right] \leq \overline{\mathcal E}^{\Delta,\kappa}$ with

\begin{align*}
\overline{\mathcal E}^{\Delta,\kappa} \leq \frac{\E \left[ \Delta_2 \left( \langle \tilde{\theta}_t^{(i)} \rangle_{i \in \mathcal G_t} \right) \right]}{2^{\kappa}} \leq \mathcal O \left( 2^{-\kappa} \right).
\end{align*}

§ EXPERIMENTS

In order to corroborate our theoretical findings, we empirically study the performance of the proposed methods w.r.t. the properties suggested by Corollary <ref>, i.e., (a) speed-up when increasing the number of agents $K$, and (b) resilience against various Byzantine attacks. We focus on our main contribution regarding the more challenging decentralized setting here (i.e. DecByzPG), and defer experiments for ByzPG to Appendix <ref>.

Environments and Setup. We consider two common RL benchmarks, CartPole [Barto et al., 1983] and LunarLander. For all experiments, we report average returns of honest agents (y-axis) in terms of the trajectories that have been sampled per agent (x-axis). To visualize potential variance in our experiments, all plots show the respective mean and standard deviation across 10 independent runs. Further details, including hyperparameters, can be found in Appendix <ref>.

§.§ DecByzPG without Byzantine Agents

Performance of DecByzPG for different federation sizes when all agents behave honestly (i.e. $\alpha=0$).

Performance of DecByzPG for different federation sizes when all agents behave honestly (i.e. $\alpha=0$).

In Figure <ref>, we consider DecByzPG in the case $\alpha=0$, with $K=1$ (which is equivalent to PAGE-PG [Gargiani et al., 2022]), $K=5$, and $K=13$. Speed-up with increasing number of agents is observable in both environments, as suggested by Corollary <ref>. Such faster convergence provides empirical evidence motivating agents to join a decentralized federation.

§.§ DecByzPG under Attack

Performance & resilience of DecByzPG for CartPole w.r.t. our three attack types.

Performance & resilience of DecByzPG for CartPole w.r.t. our three attack types.

Performance & resilience of DecByzPG for LunarLander w.r.t. our three attack types.

Performance & resilience of DecByzPG for LunarLander w.r.t. our three attack types.

Choice of attacks. In previous work [Fan et al., 2021], Byzantine attacks are constructed by making random modifications to an agent's interaction with its environment, by e.g. choosing an action u.a.r. instead of following the current policy (here denoted RandomAction), adding noise to the reward, or randomly flipping the reward's sign. We find that in our setting, for simple environments such as CartPole, robustness to such attacks is often already given for naively collaborating agents. This behavior is exemplified by our experiments under the RandomAction attack. Thus, even though DecByzPG is also resilient to such attacks, a stronger adversary is needed to demonstrate DecByzPG's advantage over naive methods. LargeNoise lets Byzantine agents directly send noise instead of gradients obtained from noisy interactions. Even though introducing noise may generally also have beneficial effects on convergence speed (e.g. due to improved exploration), by choosing the variance large enough, such benefits are outweighed. The third attack, AvgZero leverages the power of Byzantine knowledge and collaboration. Gradients sent by Byzantines are chosen such that when averaged with gradients sent by honest agents, the result will be close to zero.

In Figure <ref> and <ref>, we compare DecByzPG under above attacks to (a) PAGE-PG [Gargiani et al., 2022], the SOTA single-agent PG method that DecByzPG reduces to when $K=1$, and (b) Dec-PAGE-PG, a naive decentralized (but not fault-tolerant) version of PAGE-PG where aggregation of gradients is done by averaging, and no agreement mechanism is used. Note that for experiments involving Byzantine agents, we choose their quantity to be the largest for which Assumption <ref>, and hence the guarantees of Theorem <ref>, still hold (i.e. 3 out of 13 agents are Byzantine).

For both environments and all attacks, we can observe that DecByzPG performs nearly on par with the unattacked Dec-PAGE-PG. This empirically supports the Byzantine fault-tolerance of DecByzPG. Furthermore, for CartPole, as expected, LargeNoise and AvgZero are highly effective against the non-fault-tolerant method, while as previously remarked, RandomAction barely shows any effect. For the more difficult task of LunarLander, already RandomAction breaks Dec-PAGE-PG. Lastly, we point out that in all cases DecByzPG with $K=13$ and $\alpha > 0$ outperforms PAGE-PG with $K=1$ (and $\alpha=0$), meaning that in our experiments, despite the presence of Byzantines, joining the federation is empirical beneficial for faster convergence.

§ CONCLUSION

We described and analyzed a federated decentralized Byzantine fault-tolerant PG algorithm. As a warm-up, we combined variance-reduced PG methods with results from Byzantine-tolerant non-convex optimization to obtain a new centralized algorithm under standard assumptions. We then use ideas from Byzantine robust aggregation and agreement to generalize our approach to the significantly more challenging decentralized setting. As a result, we obtained the first sample complexity guarantees for Byzantine fault-tolerant decentralized federated non-convex optimization. We thus believe that our technical contributions are more generally applicable and may therefore open up directions for future research. Moreover, the provided empirical results for standard RL benchmark tasks support our theory and promise practical relevance of our method.

[Kairouz et al., 2021]
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi
Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham
Cormode, Rachel Cummings, et al.
Advances and open problems in federated learning.
Foundations and Trends® in Machine Learning,
140 (1–2):0 1–210, 2021.

[Li et al., 2020]
Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith.
Federated learning: Challenges, methods, and future directions.
IEEE signal processing magazine, 370 (3):0
50–60, 2020.

[Qi et al., 2021]
Jiaju Qi, Qihao Zhou, Lei Lei, and Kan Zheng.
Federated reinforcement learning: Techniques, applications, and open
arXiv preprint arXiv:2108.11887, 2021.

[Zhuo et al., 2019]
Hankz Hankui Zhuo, Wenfeng Feng, Yufeng Lin, Qian Xu, and Qiang Yang.
Federated deep reinforcement learning.
arXiv preprint arXiv:1901.08277, 2019.

[Fan et al., 2021]
Xiaofeng Fan, Yining Ma, Zhongxiang Dai, Wei Jing, Cheston Tan, and Bryan
Kian Hsiang Low.
Fault-tolerant federated reinforcement learning with theoretical
In Advances in Neural Information Processing Systems,
volume 34, pages 1007–1021, 2021.

[Fan et al., 2023]
Flint Xiaofeng Fan, Yining Ma, Zhongxiang Dai, Cheston Tan, Bryan Kian Hsiang
Low, and Roger Wattenhofer.
Fedhql: Federated heterogeneous q-learning.
arXiv:2301.11135, 2023.

[Jiang et al., 2022]
Zhanhong Jiang, Xian Yeow Lee, Sin Yong Tan, Kai Liang Tan, Aditya Balu,
Young M Lee, Chinmay Hegde, and Soumik Sarkar.
Mdpgt: momentum-based decentralized policy gradient tracking.
In Proceedings of the AAAI Conference on Artificial
Intelligence, volume 36, pages 9377–9385, 2022.

[El-Mhamdi et al., 2021]
El Mahdi El-Mhamdi, Sadegh Farhadkhani, Rachid Guerraoui, Arsany Guirguis,
Lê-Nguyên Hoang, and Sébastien Rouault.
Collaborative learning in the jungle (decentralized, byzantine,
heterogeneous, asynchronous and nonconvex learning).
Advances in Neural Information Processing Systems,
34:0 25044–25057, 2021.

[Sutton and Barto, 2018]
Richard S Sutton and Andrew G Barto.
Reinforcement learning: An introduction.
MIT press, 2018.

[Schulman et al., 2015]
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp
Trust region policy optimization.
In International conference on machine learning, pages
1889–1897, 2015.

[Schulman et al., 2017]
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov.
Proximal policy optimization algorithms.
arXiv:1707.06347, 2017.

[Williams, 1992]
Ronald J Williams.
Simple statistical gradient-following algorithms for connectionist
reinforcement learning.
Machine learning, 80 (3-4):0 229–256, 1992.

[Baxter and Bartlett, 2001]
Jonathan Baxter and Peter L Bartlett.
Infinite-horizon policy-gradient estimation.
Journal of Artificial Intelligence Research, 15:0
319–350, 2001.

[Reddi et al., 2016]
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.

[Papini, 2021]
Matteo Papini.
Safe policy optimization.

[Xu et al., 2020]
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.

[Li et al., 2021]
Zhize Li, Hongyan Bao, Xiangliang Zhang, and Peter Richtárik.
Page: A simple and optimal probabilistic gradient estimator for
nonconvex optimization.
In International conference on machine learning, pages
6286–6295, 2021.

[Gargiani et al., 2022]
Matilde Gargiani, Andrea Zanelli, Andrea Martinelli, Tyler Summers, and John
Page-pg: A simple and loopless variance-reduced policy gradient
method with probabilistic gradient estimation.
In International Conference on Machine Learning, pages
7223–7240, 2022.

[Lamport et al., 1982]
Leslie Lamport, Robert Shostak, and Marshall Pease.
The byzantine generals problem.
ACM Trans. Program. Lang. Syst., 40 (3), 1982.

[Blanchard et al., 2017]
Peva Blanchard, El Mahdi El Mhamdi, Rachid Guerraoui, and Julien Stainer.
Machine learning with adversaries: Byzantine tolerant gradient
In Proceedings of the 31st International Conference on Neural
Information Processing Systems, pages 118–128, 2017a.

[Alistarh et al., 2018]
Dan Alistarh, Zeyuan Allen-Zhu, and Jerry Li.
Byzantine stochastic gradient descent.
Advances in Neural Information Processing Systems, 31, 2018.

[Allen-Zhu et al., 2020]
Zeyuan Allen-Zhu, Faeze Ebrahimian, Jerry Li, and Dan Alistarh.
Byzantine-resilient non-convex stochastic gradient descent.
arXiv:2012.14368, 2020.

[Farhadkhani et al., 2022]
Sadegh Farhadkhani, Rachid Guerraoui, Nirupam Gupta, Rafael Pinot, and John
Byzantine machine learning made easy by resilient averaging of
In International Conference on Machine Learning, pages
6246–6283, 2022.

[Gorbunov et al., 2023]
Eduard Gorbunov, Samuel Horváth, Peter Richtárik, and Gauthier Gidel.
Variance reduction is an antidote to byzantines: Better rates, weaker
assumptions and communication compression as a cherry on the top.
In The Eleventh International Conference on Learning
Representations, 2023.

[Mendes and Herlihy, 2013]
Hammurabi Mendes and Maurice Herlihy.
Multidimensional approximate agreement in byzantine asynchronous
In Proceedings of the forty-fifth annual ACM symposium on
Theory of computing, pages 391–400, 2013.

[Mendes et al., 2015]
Hammurabi Mendes, Maurice Herlihy, Nitin Vaidya, and Vijay K Garg.
Multidimensional agreement in byzantine systems.
Distributed Computing, 280 (6):0 423–441,

[Papini et al., 2018]
Matteo Papini, Damiano Binaghi, Giuseppe Canonaco, Matteo Pirotta, and Marcello
Stochastic variance-reduced policy gradient.
In International conference on machine learning, pages
4026–4035, 2018.

[Yuan et al., 2020]
Huizhuo Yuan, Xiangru Lian, Ji Liu, and Yuren Zhou.
Stochastic recursive momentum for policy gradient methods.
arXiv preprint arXiv:2003.04302, 2020.

[Karimireddy et al., 2021]
Sai Praneeth Karimireddy, Lie He, and Martin Jaggi.
Learning from history for byzantine robust optimization.
In International Conference on Machine Learning, pages
5311–5319, 2021.

[Cachin and Shoup, 2000]
C Cachin and V Shoup.
Random oracles in constantinople: Practical asynchronous byzantine
agreement using.
In Proceedings of the 19th ACM Symposium on Principles of
Distributed Computing, no, pages 1–26, 2000.

[Barto et al., 1983]
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, pages
834–846, 1983.

[Johnson and Zhang, 2013]
Rie Johnson and Tong Zhang.
Accelerating stochastic gradient descent using predictive variance
Advances in neural information processing systems, 26, 2013.

[Karimireddy et al., 2022]
Sai Praneeth Karimireddy, Lie He, and Martin Jaggi.
Byzantine-robust learning on heterogeneous datasets via bucketing.
In International Conference on Learning Representations, 2022.

[Blanchard et al., 2017]
Peva Blanchard, El Mahdi El Mhamdi, Rachid Guerraoui, and Julien Stainer.
Machine learning with adversaries: Byzantine tolerant gradient
Advances in neural information processing systems, 30,

[Pillutla et al., 2022]
Krishna Pillutla, Sham M Kakade, and Zaid Harchaoui.
Robust aggregation for federated learning.
IEEE Transactions on Signal Processing, 70:0
1142–1154, 2022.

[Weiszfeld, 1937]
Endre Weiszfeld.
Sur le point pour lequel la somme des distances de n points
donnés est minimum.
Tohoku Mathematical Journal, First Series, 43:0
355–386, 1937.

[Kingma and Ba, 2014]
Diederik P Kingma and Jimmy Ba.
Adam: A method for stochastic optimization.
arXiv:1412.6980, 2014.

§ APPENDIX

§ BACKGROUND IN RL & DETAILS ON ROBUST AGGREGATION AND AGREEMENT

§.§ Details on Gradient Estimation and Importance Sampling in PG Methods

Throughout the paper, we have used $g\left( \tau \mid \theta \right)$ to denote an unbiased estimator of $\nabla J (\theta)$. It is known, see e.g. [Fan et al., 2021], that in our setting of episodic MDP with trajectory horizon $H$, $g\left( \tau \mid \theta \right)$ can for example be implemented as REINFORCE [Williams, 1992],

\begin{align*}
g\left(\tau \mid \theta\right)=\left(\sum_{h=0}^{H-1} \nabla_{\theta} \log \pi_{\theta}\left(a_h \mid s_h\right)\right)\left(\sum_{h=0}^{H-1} \gamma^h \mathcal{R}\left(s_h, a_h\right)-C_b\right),
\end{align*}

or GPOMDP [Baxter and Bartlett, 2001],

\begin{align*}
g\left(\tau \mid \theta\right)=\sum_{h=0}^{H-1}\left(\sum_{t=0}^h \nabla_{\theta} \log \pi_{\theta}\left(a_t \mid s_t\right)\right)\left(\gamma^h r\left(s_h, a_h\right)-C_{b_h}\right).
\end{align*}

with $C_b$ and $C_{b_h}$ denoting the corresponding baselines. Under Assumption <ref>, Proposition <ref> is known to hold for both REINFORCE and GPOMDP [Xu et al., 2020]. For the experiments, our implementation will be based on GPOMDP, as it has generally been reported to have lower variance and thus yields better performance than REINFORCE [Papini et al., 2018, Xu et al., 2020].

Variance-reduced stochastic gradient descent methods such as SVRG [Johnson and Zhang, 2013] and PAGE [Li et al., 2021] rely on the ability to sample gradients at points that are not the current iterate. In PG however, the underlying sample distribution depends on the current parameters $\theta_t$. To overcome this challenge of non-stationarity, we employ the commonly used importance sampling technique and follow [Gargiani et al., 2022] in defining, for any $\theta_t,\theta_{t-1} \in \R^d$, and any trajectory $\tau$,

\begin{align*}
g^{\omega_{\theta_t}} \left( \tau \mid \theta_{t-1} \right) := \omega \left( \tau \mid \theta_t,\theta_{t-1} \right) g \left( \tau \mid \theta_{t-1} \right)
\end{align*}

with importance weight $\omega \left( \tau \mid \theta_t,\theta_{t-1} \right):=\frac{p \left( \tau \mid \theta_{t-1} \right)}{p \left( \tau \mid \theta_t \right)}$. It can be shown [Papini et al., 2018] that this yields an unbiased estimate of $\nabla J \left( \theta_{t-1} \right)$ despite trajectory $\tau$ being sampled from the current policy based on $\theta_t$, i.e.,

\begin{align*}
\E_{\tau \sim p \left(\cdot\mid\theta_t\right)} \left[ g^{\omega_{\theta_t}} \left( \tau \mid \theta_{t-1} \right) \right] = \nabla J \left( \theta_{t-1} \right).
\end{align*}

At this point, we also introduce the following additional notation that will be used throughout the proofs of Theorem <ref> and <ref>: For any $\theta_t, \theta_{t-1} \in \R^d$, and $M \in \mathbb N$, let

\begin{align*}
\hat{\Delta}^M \left( \theta_t,\theta_{t-1} \right) &:= \frac{1}{M} \sum_{j=1}^M g\left(\tau_{t,j} \mid \theta_t\right)-\frac{1}{M} \sum_{j=1}^M g^{\omega_{\theta_t}}\left( \tau_{t,j} \mid \theta_{t-1} \right)
\end{align*}

\begin{align*}
\Delta \left( \theta_t,\theta_{t-1} \right) &:= \nabla J \left( \theta_t \right) - \nabla J \left( \theta_{t-1} \right)
\end{align*}

where $\tau_{t,j} \sim p \left( \cdot \mid \theta_t \right)$ for $j=1,\dots,M$.

§.§ Implementation of Robust Aggregation

The notion of $(\alpha,C_{ra})$-robust aggregation, see Definition <ref>, is adopted from [Gorbunov et al., 2023], and has originally appeared in a similar form in [Karimireddy et al., 2022]. Known implementations satisfying our requirement of $C_{ra}=\mathcal O \left( 1 \right)$ include Krum [Blanchard et al., 2017] and Robust Federated Averaging (RFA) [Pillutla et al., 2022], where both must be used in conjunction with bucketing [Karimireddy et al., 2022].

Krum. Denoting by $S_i$ the $\lceil (1-\alpha)K \rceil$ closest neighbors to $\theta^{(i)}$ among $\theta^{(1)},\dots,\theta^{(K)}$ in Euclidean norm, we let

\begin{align*}
\texttt{Krum} \left( \theta^{(1)},\dots,\theta^{(K)} \right) := \argmin_{\theta^{(i)} \,\text{s.t.}\, i \in [K]} \sum_{j \in S_i} \left\| \theta^{(j)}-\theta^{(i)} \right\|^2.
\end{align*}

Note that due to the computation of pairwise distances, Krum has runtime complexity $\mathcal O \left( K^2 \right)$.
RFA. We define

\begin{align*}
\texttt{RFA} \left( \theta^{(1)},\dots,\theta^{(K)} \right) := \argmin_{\theta \in \R^d} \sum_{i \in [K]} \left\| \theta-\theta^{(i)} \right\|^2
\end{align*}

which corresponds to finding the geometric median—a problem that does not have a closed form solution. However, efficient iterative approximation methods, such as the smoothed Weiszfeld algorithm [Weiszfeld, 1937, Pillutla et al., 2022], exist.
Bucketing. Instead of directly aggregating the inputs vectors, [Karimireddy et al., 2022] proposes to apply existing aggregators to the means of buckets of size $\lfloor \alpha_{\max}/\alpha \rfloor$, where inputs are randomly assigned to buckets (see Algorithm 1 in [Karimireddy et al., 2022] for the detailed procedure). It has been shown that this can turn aggregation methods not satisfying Definition <ref> into robust aggregators.

For completeness, we restate the relevant parts summarized by Theorem D.1 of [Gorbunov et al., 2023] in the following lemma.

For $0<\alpha<\alpha_{\max}$, $C_{ra}=\mathcal O \left( 1 \right)$, and bucket size $\lfloor \alpha_{\max}/\alpha \rfloor$, it holds that

* bucketing with Krum is an $\left( \alpha,C_{ra} \right)$-robust aggregator for $\alpha_{\max}=1/4$, and

* bucketing with RFA is an  $\left( \alpha,C_{ra} \right)$-robust aggregator for $\alpha_{\max}=1/2$.

Note that this means, in order to achieve the values $\alpha_{\max}$ stated in Assumption <ref>, i.e., $1/2$ in the centralized, and $1/4$ in the decentralized case, we may use RFA for ByzPG, and either RFA or Krum for DecByzPG.

§.§ Implementation of Averaging Agreement

Averaging agreement, as in Definition <ref>, has been introduced by [El-Mhamdi et al., 2021], together with two possible implementations. One of them, Minimum Diameter Averaging (MDA) also satisfies our stronger requirement of $C_{avg}=\mathcal O \left( 1 \right)$.

MDA. For each $k \in [K]$, let

\begin{align*}
\textsc{Byz}^{(k)} \left( \langle \theta^{(k')} \rangle_{k' \in [K]} \right)=\langle \textsc{Byz}^{(k,i)} \left( \langle \theta^{(k')} \rangle_{k' \in [K]} \right) \rangle_{i \in [K]}
\end{align*}

be the set of vectors received by agent $k$ (from agent $i$) after one round of all-to-all parameter broadcast of $\langle \theta^{(k')} \rangle_{k' \in [K]}$, subject to some Byzantine attack, under Assumption <ref>. Furthermore, let

\begin{align*}
\texttt{MDA} \left( \langle \theta^{(k)} \rangle_{k \in [K]} \right) := \langle \theta^{(k)} \rangle_{k \in S^{*}} \quad\text{where}\quad S^{*} = \argmin_{S \subset [K], |S| \geq (1-\bar\alpha)K} \Delta_2 \left( \langle \theta^{(k)} \rangle_{k \in S} \right).
\end{align*}

The MDA averaging agreement mechanism is then defined by running Algorithm <ref> at all agents $k \in [K]$ concurrently, for $\kappa$ iterations.

MDA at $k$-th agent
[1]
input: $\theta^{(k)}$
$\kappa$ iterations
broadcast $\theta^{(k)}$ to all other agents and receive $\mathcal B:=\textsc{Byz}^{(k)} \left( \langle \theta^{(k')} \rangle_{k' \in [K]} \right)$
let $\mathcal M \leftarrow \texttt{MDA} \left( \mathcal B \right)$
$\theta^{(k)} \leftarrow \frac{1}{|\mathcal M|} \sum_{\theta \in \mathcal M} \theta$
output: $\theta^{(k)}$

The following is a special case of [El-Mhamdi et al., 2021]'s Theorem 4 for our synchronous setting, restated here for convenience.

Under Assumption <ref>, i.e., with $\alpha_{\max}=1/4$, and assuming synchronous communication, MDA as in Algorithm <ref> achieves $C_{avg}$-averaging agreement for $C_{avg}=\mathcal O(1)$.

However, it needs to be pointed out that for any constant $\bar\alpha>0$, finding the subset that minimizes the diameter in Line <ref> of Algorithm <ref> has computational complexity exponential in $K$, and for larger $K$ is therefore not suitable in practice. As proposed by [El-Mhamdi et al., 2021], a computationally efficient alternative exists, which we call Greedy Diameter Averaging (GDA). We define

\begin{align*}
\texttt{GDA}_k \left( \langle \theta^{(k)} \rangle_{k \in [K]} \right) := \langle \theta^{(k)} \rangle_{k \in S^{*}} \quad\text{where}\quad S^{*} = \argmin_{S \subset [K], |S| \geq (1-\bar\alpha)K} \sum_{i \in S} \left\| \theta^{(i)}-\theta^{(k)} \right\|^2.
\end{align*}

Note that unlike for MDA, in the case of GDA, the set $S^{*}$ can be found in time $\mathcal O(K)$ by choosing the $\lceil (1-\bar\alpha)K \rceil$ parameter vectors closest to $\theta^{(k)}$. As mentioned in [El-Mhamdi et al., 2021], replacing  with $_k$ in Algorithm <ref> still achieves $C_{avg}$-averaging agreement with $C_{avg}=\mathcal O(1)$ but comes at a slight cost in the fraction of tolerable Byzantines, namely requiring $\alpha_{\max}=1/5$ instead of $1/4$ in Assumption <ref>.

§.§ Useful Facts

In this section, we collect some simple relations and lemmas that will be helpful throughout our proofs. First, we recall some basic facts.

For any $x,y,a_1,\dots,a_n \in \R^d$, $p \in (0,1]$, and $\beta > 0$, it holds that

\begin{align}
\langle x,y \rangle &= \frac{\left\| x \right\|^2}{2} + \frac{\left\| x \right\|^2}{2} - \frac{\left\| y-x \right\|^2}{2} \label{eqn:scalar-prod} \\
\left\| \sum_{i=1}^n a_i \right\|^2 &\leq n \sum_{i=1}^n \left\| a_i \right\|^2 \label{eqn:norm-of-sum} \\
\left\| x+y \right\|^2 &\leq \left( 1+\beta \right) \left\| x \right\|^2 + \left( 1+\beta^{-1} \right) \left\| y \right\|^2 \label{eqn:beta-norm-sum} \\
\left( 1-p \right) \left( 1+\frac{p}{2} \right) &\leq 1-\frac{p}{2} \label{eqn:p-prod-1} \\
1.1p \left( 1-p \right) + \left( 1-p \right)^2 \left( 1+\frac{p}{4} \right) &\leq 1 - \frac{p}{2} \label{eqn:p-prod-2}
\end{align}

Next, we show a simple bound on the distance to a mean vector in terms of average pairwise distances.

Let $\theta^{(1)},\dots,\theta^{(K)} \in \R^d$, and $\bar{\theta}=\frac{1}{K} \sum_{j \in [K]} \theta^{(j)}$. Then, for any $i \in [K]$,

\begin{align*}
\left\| \bar{\theta}-\theta^{(i)} \right\|^2 \leq \frac{1}{K} \sum_{j \in [K]} \left\| \theta^{(j)}-\theta^{(i)} \right\|^2
\end{align*}

Observe that,

\begin{align*}
\left\| \bar{\theta}-\theta^{(i)} \right\|^2 &= \Bigg\| \frac{1}{K} \sum_{j \in [K]} \theta^{(j)}-\theta^{(i)} \Bigg\|^2 = \frac{1}{K^2} \Bigg\| \sum_{j \in [K]} \theta^{(j)}-\theta^{(i)} \Bigg\|^2
\end{align*}

from which the result follows using Lemma <ref>, (<ref>).

The following lemma shows how repeated, independent sampling reduces the variance of gradient estimates.

Let Assumption <ref> hold. Then, for any $M \in \N$, $\theta_t^{(i)} \in \R^d$, and $\tau_{t,j}^{(i)} \sim p \left( \cdot \mid \theta_t^{(i)} \right)$ for $j=1,\dots,M$,

\begin{align*}
\E \Bigg[ \Bigg\| \frac{1}{M}\sum_{j=1}^M g \left( \tau_{t,j}^{(i)} \mid \theta_t^{(i)} \right) - \nabla J \left( \theta_t^{(i)} \right) \Bigg\|^2 \Bigg] \leq \frac{\sigma^2}{M}.
\end{align*}

Using independence of the gradient estimates in the first step, we get

\begin{align*}
\E \Bigg[ \Bigg\| \frac{1}{M}\sum_{j=1}^M g \left( \tau_{t,j}^{(i)} \mid \theta_t^{(i)} \right) - \nabla J \left( \theta_t^{(i)} \right) \Bigg\|^2 \Bigg] = \frac{1}{M^2}\sum_{j=1}^M \underbrace{\E \left[ \left\| g \left( \tau_{t,j}^{(i)} \mid \theta_t^{(i)} \right) - \nabla J \left( \theta_t^{(i)} \right) \right\|^2 \right]}_{\leq \;\sigma^2} \leq \frac{\sigma^2}{M}
\end{align*}

where the inequality in the last step is by Assumption <ref>.

Finally, we give two lemmas that are slight variations of classical concentration bounds. The former is Markov's inequality, stated in terms of the random variable's second moment. The latter is a Chernoff bound for the case in which only an upper bound on the expectation is known.

Let $X$ be a non-negative random variable and $a>0$. Then

\begin{align*}
\Pr[X \geq a] \leq \frac{\E [X^2]}{a^2}.
\end{align*}

By Markov's inequality,

\begin{align*}
\Pr[X \geq a] = \Pr[X^2 \geq a^2] \leq \frac{\E [X^2]}{a^2}.
\end{align*}

For $i \in [n]$, let $Y_i \stackrel{i.i.d.}{\sim}\text{Ber}(p_i)$ where $p_i \leq \hat{p} \in [0,1]$ for all $i \in [n]$. With $Y:=\sum_{i=1}^n Y_i$, we have $\E \left[ Y \right] \leq n\hat{p}$, and for any $\delta \geq 0$,

\begin{align*}
\Pr \left[ Y \geq (1+\delta) n\hat{p} \right] \leq \exp \left( \frac{-\delta^2 n \hat{p}}{2+\delta} \right).
\end{align*}

For $i \in [n]$, let $X_i \stackrel{i.i.d.}{\sim}\text{Ber}(\hat{p})$. We then have

\begin{align*}
\Pr \left[ Y \geq (1+\delta) n\hat{p} \right] &\stackrel{(a)}{\leq} \Pr \left[ X \geq (1+\delta) n\hat{p} \right] \\
&\stackrel{(b)}{\leq} \exp \left( \frac{-\delta^2 n \hat{p}}{2+\delta} \right)
\end{align*}

where (a) is because by definition, $\Pr[X_i=1] \geq \Pr[Y_i=1]$ for all $i \in [n]$, and (b) is the standard Chernoff bound applied to $X_1,\dots,X_n$.

§ PROOFS FOR SECTION <REF>

In this section, we prove Theorem <ref> and Corollary <ref>. We start with the main results, and then proceed with the required technical lemmas.

§.§ Main Result

Following the strategy of [Gorbunov et al., 2023] applied to our policy gradient setting, we let

\begin{align*}
\Phi_t:=J^{*} - J \left( \theta_t \right)+\frac{\eta}{p} \left\| v_t-\nabla J \left( \theta_t \right) \right\|^2.
\end{align*}

Then, applying first Lemma <ref>, followed by Lemma <ref>, we derive

\begin{align*}
\E \left[ \Phi_{t+1} \right] &\leq \E \bigg[ J^{*}-J \left( \theta_t \right)-\frac{\eta}{2} \left\| \nabla J \left( \theta_t \right) \right\|^2 - \left( \frac{1}{2\eta}-\frac{L}{2} \right) \left\| \theta_{t+1}-\theta_t \right\|^2 + \frac{\eta}{2} \left\| v_t-\nabla J \left( \theta_t \right) \right\|^2 \\
&\quad+ \frac{\eta}{p} \left\| v_{t+1}-\nabla J \left( \theta_{t+1} \right) \right\|^2 \bigg]\\
&\leq \E \left[ J^{*}-J \left( \theta_t \right) - \left( \frac{1}{2\eta}-\frac{L}{2} \right) \left\| \theta_{t+1}-\theta_t \right\|^2 + \frac{\eta}{2} \left\| v_t-\nabla J \left( \theta_t \right) \right\|^2 \right] -\frac{\eta}{2} \E\left\| \nabla J \left( \theta_t \right) \right\|^2\\
&\quad+ \left( \frac{\eta}{p}-\frac{\eta}{2} \right) \E \left[ \left\| v_t-\nabla J \left( \theta_t \right) \right\|^2 \right] + \frac{\eta A}{2} \E \left[ \left\| \theta_{t+1}-\theta_t \right\|^2 \right] + \frac{\eta C \sigma^2}{2N} \left( \alpha+\frac{1}{K} \right)\\
&\leq \E \left[ \Phi_t \right] - \frac{\eta}{2} \E \left[ \left\| \nabla J \left( \theta_t \right) \right\|^2 \right] + \frac{\eta C \sigma^2}{2N} \left( \alpha+\frac{1}{K} \right)-\frac{1}{2\eta} \left( 1-L\eta-A\eta^2 \right) \E \left[ \left\| \theta_{t+1}-\theta_t \right\|^2 \right] \\
&\leq \E \left[ \Phi_t \right] - \frac{\eta}{2} \E \left[ \left\| \nabla J \left( \theta_t \right) \right\|^2 \right] + \frac{\eta C \sigma^2}{2N} \left( \alpha+\frac{1}{K} \right)
\end{align*}

where in the last step we use Lemma C.1 from [Gorbunov et al., 2023], our choice of $\eta$, and the fact that $A=\Theta \left( p^{-1}K^{-1} \right)$, see Lemma <ref>. Summing over $t$, we obtain

\begin{align*}
\frac{1}{T} \sum_{t=0}^{T-1} \E \left[ \left\| \nabla J \left( \theta_t \right) \right\|^2 \right] &\leq \frac{2}{\eta T} \sum_{t=0}^{T-1} \left( \E \left[
\Phi_t \right] - \left[ \Phi_{t+1} \right] \right) + \frac{C \sigma^2}{N} \left( \alpha+\frac{1}{K} \right) \\
&\leq \frac{2 \E \left[ \Phi_0 \right]}{\eta T} + \frac{C \sigma^2}{N} \left( \alpha+\frac{1}{K} \right)
\end{align*}

where in the second step we simplify the telescoping sum and use the fact that $\Phi_T \geq 0$. Note that the LHS is exactly $\E \left[ \left\| \nabla J \left( \theta_{\widehat{T}} \right) \right\|^2 \right]$ with $\widehat{T}$ chosen uniformly at random from $[T]$.

In order to achieve

\begin{align*}
\underbrace{\frac{2 \E \left[ \Phi_0 \right]}{\eta T}}_{(a)} + \underbrace{\frac{C \sigma^2}{N} \left( \alpha+\frac{1}{K} \right)}_{(b)} \leq \epsilon^2,
\end{align*}

we set

\begin{align*}
B=\Theta(1), \quad T=\Theta \left( \frac{1}{\epsilon^2 \sqrt{pK}} \right), \quad\text{and}\quad
N=\Theta \left( \epsilon^{-2} \left( \alpha+\frac{1}{K} \right) \right).
\end{align*}

Since $\eta=\Theta \left( \min \left\{ \sqrt{pK},1/L \right\} \right)$, above choice of $T$ ensures that term (a) is bounded by $\epsilon^2/2$. We treat $\sigma^2$ as constant, hence our choice of $N$ also ensures a $\epsilon^2/2$-bound for term (b).

To conclude the proof, we want to count the number of trajectories sampled at an agent: Per iteration, with probability $p$ we sample $N$ times, and with probability $1-p$ we sample $B$ times. Hence over all $T$ iterations, choosing $p=\frac{1}{N}=\frac{\epsilon^2}{\alpha+1/K}$, the expected number of sampled trajectories is given by

\begin{align*}
T \left( pN+(1-p)B \right) \,\leq\, \mathcal O(TpN) \stackrel{p=\frac{1}{N}}= \mathcal O \left( \epsilon^{-2}\frac{1}{\sqrt{pK}} \right) &= \mathcal O \left( \epsilon^{-2} \sqrt{\frac{\alpha+1/K}{K\epsilon^2}} \right) \\
&\leq \mathcal O \left( \frac{\alpha^{1/2}}{K^{1/2}\epsilon^3}+\frac{1}{K \epsilon^3} \right).
\end{align*}

§.§ Technical Lemmas

Here, we give proofs of the technical lemmas used in above proofs. The first is a standard application of smoothness, also seen in a similar form e.g. in [Gargiani et al., 2022, Li et al., 2021].

Let Assumptions <ref>, <ref>, <ref>, and <ref> hold. Then, for $\theta_{t+1}=\theta_t+\eta v_t$,

\begin{align*}
J \left( \theta_{t+1} \right) \geq J \left( \theta_t \right) + \frac{\eta}{2} \left\| \nabla J \left( \theta_t \right) \right\|^2 + \left( \frac{1}{2\eta}-\frac{L}{2} \right)\left\| \theta_{t+1}-\theta_t \right\|^2 - \frac{\eta}{2} \left\| v_t-\nabla J \left( \theta_t \right) \right\|^2.
\end{align*}

By smoothness of $J$, i.e., Proposition <ref>,

\begin{align*}
J \left( \theta_{t+1} \right) &\geq J \left( \theta_t \right) + \langle \nabla J \left( \theta_t \right), \theta_{t+1}-\theta_t \rangle - \frac{L}{2} \left\| \theta_{t+1}-\theta_t \right\|^2\\
&= J \left( \theta_t \right) + \eta \langle \nabla J \left( \theta_t \right), v_t \rangle - \frac{\eta^2 L}{2} \left\| v_t \right\|^2\\
&\stackrel{(a)}{=} J \left( \theta_t \right) + \frac{\eta}{2} \left\| \nabla J \left( \theta_t \right) \right\|^2 + \frac{\eta}{2} \left\| v_t \right\|^2 - \frac{\eta}{2} \left\| v_t-\nabla J \left( \theta_t \right) \right\|^2 - \frac{\eta^2L}{2} \left\| v_t \right\|^2\\
&= J \left( \theta_t \right) + \frac{\eta}{2} \left\| \nabla J \left( \theta_t \right) \right\|^2 + \left( \frac{1}{2\eta}-\frac{L}{2} \right)\left\| \theta_{t+1}-\theta_t \right\|^2 - \frac{\eta}{2} \left\| v_t-\nabla J \left( \theta_t \right) \right\|^2
\end{align*}

where (a) is due to Lemma <ref>, (<ref>).

As a next preparatory step, we want to show that the gradient estimates $\tilde{v}_t^{(i)}$ do not vary too much across different agents. In particular, we bound the average of pairwise variances, denoted by $\widetilde{\mathcal T}$. Note that we slightly abuse notation and omit adding an index $t$ to $\widetilde{\mathcal T}$ since the bound below does not depend on $t$.

Let Assumption <ref> and <ref> hold, i.e., $\mathcal H_t \subset K$ is the set of honest agents in iteration $t$. Then,

\begin{align*}
\widetilde{\mathcal T} &:= \frac{1}{|\mathcal H_t|(|\mathcal H_t|-1)} \sum_{i,l \in \mathcal H_t} \E \left[ \left\| \tilde{v}_t^{(i)}-\tilde{v}_t^{(l)} \right\|^2 \mid c_t=1 \right] \leq \frac{4\sigma^2}{N}
\end{align*}

and we will use $\widetilde{\mathcal T}$ also in subsequent lemmas to refer to this term.

By plugging in the definition of $\tilde{v}_t^{(i)}$ as in Algorithm <ref>, and using basic fact (<ref>) from Lemma <ref>, we get

\begin{align*}
\widetilde{\mathcal T} &= \frac{1}{|\mathcal H_t|(|\mathcal H_t|-1)} \sum_{i,l \in \mathcal H_t} \E \left[ \left\| \tilde{v}_t^{(i)}-\tilde{v}_t^{(l)} \right\|^2 \mid c_t=1 \right] \\
&= \frac{1}{|\mathcal H_t|(|\mathcal H_t|-1)} \sum_{i,l \in \mathcal H_t} \E \left[ \left\| \frac{1}{N} \sum_{j=1}^N g \left( \tau_{t,j}^{(i)} \mid \theta_t \right) - \frac{1}{N} \sum_{j=1}^N g \left( \tau_{t,j}^{(l)} \mid \theta_t \right) \right\|^2 \right] \\
&\leq \frac{1}{|\mathcal H_t|(|\mathcal H_t|-1)} \sum_{i,l \in \mathcal H_t} \E \left[ 2\left\| \frac{1}{N} \sum_{j=1}^N g \left( \tau_{t,j}^{(i)} \mid \theta_t \right) - \nabla J \left( \theta_t \right) \right\|^2 + 2\left\| \frac{1}{N} \sum_{j=1}^N g \left( \tau_{t,j}^{(l)} \mid \theta_t \right) - \nabla J \left( \theta_t \right) \right\|^2 \right] \\
&= \frac{4}{|\mathcal H_t|} \sum_{i \in \mathcal H_t} \underbrace{\E \left[ \left\| \frac{1}{N}\sum_{j=1}^N g \left( \tau_{t,j}^{(i)} \mid \theta_t \right) - \nabla J \left( \theta_t \right) \right\|^2 \right]}_{\stackrel{(a)}{\leq} \;\frac{\sigma^2}{N}} \\
&\leq \frac{4\sigma^2}{N}
\end{align*}

where (a) is by Lemma <ref>.

Next, we want to bound the deviation of our potentially aggregated gradient estimate $v_t$ from $\nabla J \left( \theta_t \right)$ which is what we aim to estimate. Note that in case $c_t=1$, this involves bounding both the bias introduced by aggregation, as well as the variance due to sampling.

In the setting of Theorem <ref>, the following bounds hold:

\begin{align*}
\mathcal T_{1,t}^{(1)} &:= \E \left[ \left\| v_t-\bar{\tilde{v}}_t \right\|^2 \mid c_t=1 \right] \leq C_{ra}\alpha \widetilde{\mathcal T}, \\
\mathcal T_{1,t}^{(2)} &:= \E \left[ \left\| \bar{\tilde{v}}_t-\nabla J \left( \theta_t \right) \right\|^2 \mid c_t=1 \right] \leq \frac{2\sigma^2}{KN}, \text{ and} \\
\mathcal T_{0,t}^{(1)} &:= \E \left[ \left\| v_t-\nabla J \left( \theta_t \right) \right\|^2 \mid c_t=0 \right] \leq \E \left[ \left\| v_{t-1}-\nabla J \left( \theta_{t-1} \right) \right\|^2 \right] + \left( \frac{C_p}{BK} + \frac{L^2}{K} \right) \E \left[ \left\| \theta_t - \theta_{t-1} \right\|^2 \right],
\end{align*}

where $\mathcal T_{1,t}^{(1)}$, $\mathcal T_{1,t}^{(2)}$ are the errors w.r.t. aggregation and sampling, respectively, in case $c_t=1$, and $\mathcal T_{0,t}^{(1)}$ is the error due to sampling in case $c_t=0$ (no aggregation done in this case). We will use this notation also to refer to the respective terms in subsequent lemmas.

We proceed by showing each of the claimed bounds separately, as follows:

* First, by applying Definition <ref>,

\begin{align*}
\mathcal T_{1,t}^{(1)}
&= \E \left[ \left\| \bar{v}_t-\bar{\tilde{v}}_t \right\|^2 \mid c_t=1 \right] \\
&\leq \frac{C_{ra} \alpha}{|\mathcal H_t|(|\mathcal H_t|-1)} \sum_{i,l \in \mathcal H_t} \E \left[ \left\| \tilde{v}_t^{(i)}-\tilde{v}_t^{(l)} \right\|^2 \mid c_t=1 \right] \\
&\leq C_{ra}\alpha \widetilde{\mathcal T}
\end{align*}

where the second step is the result of Lemma <ref>.

* Next, by plugging in the definition of $\bar{\tilde{v}}_t$ and then applying Lemma <ref>, we get

\begin{align*}
\mathcal T_{1,t}^{(2)} &= \E \left[ \left\| \bar{\tilde{v}}_t-\nabla J \left( \theta_t \right) \right\|^2 \mid c_t=1 \right] \\
&\leq \E \left[ \left\| \frac{1}{|\mathcal H_t|N} \sum_{i \in \mathcal H_t} \sum_{j=1}^N g \left( \tau_{t,j}^{(i)} \mid \theta_t \right)-\nabla J \left( \theta_t \right) \right\|^2 \right] \\
&\leq \frac{\sigma^2}{|\mathcal H_t|N} \\
&\leq \frac{2\sigma^2}{KN}
\end{align*}

where in the final step we use the fact that according to Assumption <ref>, we have $\alpha_{\max} \leq 1/2$ and therefore $|\mathcal H_t| \geq (1-\alpha)K \geq (1-\alpha_{\max})K \geq K/2$.

* We have

\begin{align*}
\mathcal T_{0,t}^{(1)}&=\E \left[ \left\| v_t - \nabla J \left( \theta_t \right) \right\|^2 \mid c_t=0 \right] \\
&=\E \left[ \left\| \hat{\Delta}^B \left( \theta_t,\theta_{t-1} \right) + v_{t-1} - \nabla J \left( \theta_t \right) \right\|^2 \right] \\
&=\E \left[ \left\| \hat{\Delta}^B \left( \theta_t,\theta_{t-1} \right) + v_{t-1} + \nabla J \left( \theta_{t-1} \right) - \nabla J \left( \theta_{t-1} \right) - \nabla J \left( \theta_t \right) \right\|^2 \right] \\
&=\E \Bigg[ \Big\| \underbrace{\left( v_{t-1}- \nabla J \left( \theta_{t-1} \right) \right)}_{=: X_1} + \underbrace{\left( \hat{\Delta}^B \left( \theta_t,\theta_{t-1} \right) - \Delta \left( \theta_t,\theta_{t-1} \right) \right)}_{=:X_2} \Big\|^2 \Bigg] \\
&\stackrel{(a)}{=} \E \left[ \left\| v_{t-1}- \nabla J \left( \theta_{t-1} \right) \right\|^2 \right] + \E \left[ \left\| \hat{\Delta}^B \left( \theta_t,\theta_{t-1} \right) - \Delta \left( \theta_t,\theta_{t-1} \right) \right\|^2 \right] \\
&\stackrel{(b)}{\leq} \E \left[ \left\| v_{t-1}-\nabla J \left( \theta_{t-1} \right) \right\|^2 \right] + \left( \frac{C_p}{BK} + \frac{L^2}{K} \right) \E \left[ \left\| \theta_t - \theta_{t-1} \right\|^2 \right]
\end{align*}

Steps (a) and (b) require further justification but appear again equivalently in the last part of the proof of Lemma <ref> where we explain the details.

Finally, we combine the individual bounds of Lemma <ref> into an overall distortion bound, as follows.

In the setting of Lemma <ref>, we have

\begin{align*}
\E \left\| v_t-\nabla J \left( \theta_t \right) \right\|^2 &\leq \left( 1-p \right) \E \left[ \left\| v_{t-1}-\nabla J \left( \theta_{t-1} \right) \right\|^2 \right] + \frac{Ap}{2} \E \left[ \left\| \theta_t - \theta_{t-1} \right\|^2 \right] + \frac{C p \sigma^2}{2N} \left( \alpha+\frac{1}{K} \right)
\end{align*}

where $C>0$ is a constant, and $A = \Theta \left( \frac{1}{pK} \right)$.

By the law of total expectation and using Lemma <ref>, (<ref>) in the first step, we have

\begin{align*}
\E \left[ \left\| v_t-\nabla J \left( \theta_t \right) \right\|^2 \right] &\leq \left( 1-p \right) \mathcal T_{0,t}^{(1)} + p \left( 2\mathcal T_{1,t}^{(1)}+2\mathcal T_{1,t}^{(2)} \right) \\
&\leq \left( 1-p \right) \left( \E \left[ \left\| v_{t-1}-\nabla J \left( \theta_{t-1} \right) \right\|^2 \right] + \left( \frac{2 C_p}{BK} + \frac{2L^2}{K} \right) \E \left[ \left\| \theta_t - \theta_{t-1} \right\|^2 \right] \right) \\
&\quad+\frac{8pC_{ra}\alpha\sigma^2}{N} + \frac{4p\sigma^2}{KN}.
\end{align*}

where in the second step we have plugged in the results of Lemma <ref>.
Since $1-p \leq 1, B \geq 1$, and treating $C_p,L,$ and $C_{ra}$ as constant, the result follows.

§ PROOFS FOR SECTION <REF>

First, we define (or recall from previous definitions), that for any $k \in [K]$:

\begin{align*}
\hat{v}^{(k)}_t &:= \frac{1}{\eta} \left( \theta_{t+1}^{(k)}-\theta_t^{(k)} \right), \\
\bar{\hat{v}}_t &:= \frac{1}{|\mathcal G_t|} \sum_{i \in \mathcal G_t} \hat{v}^{(i)}_t, \quad\quad \bar{\tilde{v}}_t := \frac{1}{|\mathcal G_t|} \sum_{i \in \mathcal G_t} \tilde{v}^{(i)}_t \\
\bar\theta_t &:= \frac{1}{|\mathcal G_t|} \sum_{i \in \mathcal G_t} \theta^{(i)}_t, \quad\quad \bar{\tilde{\theta}}_t := \frac{1}{|\mathcal G_t|} \sum_{i \in \mathcal G_t} \tilde{\theta}^{(i)}_t.
\end{align*}

In the remainder of this section, we prove Theorem <ref> and Corollary <ref>. As in Section <ref>, we first show the main results, and then provide proofs of the required technical lemmas.

§.§ Main Result

Following the proof strategy from [Gorbunov et al., 2023] applied to our decentralized policy gradient setting, we let

\begin{align*}
\Phi_t:=J^{*} - J \left( \bar{\theta}_t \right)+\frac{2\eta}{p} \Bigg\| \bar{\hat{v}}_t-\frac{1}{|\mathcal G_t|}\sum_{i \in \mathcal G_t}\nabla J \left( \theta_t^{(i)} \right) \Bigg\|^2.
\end{align*}

Then, applying first Lemma <ref> and then Lemma <ref>, we derive

\begin{align*}
\E \left[ \Phi_{t+1} \right] &\leq \E \Biggl[ J^{*}-J \left( \bar{\theta}_t \right)-\frac{\eta}{2} \left\| \nabla J \left( \bar{\theta}_t \right) \right\|^2 - \left( \frac{1}{2\eta}-\frac{L}{2} \right) \left\| \bar{\theta}_{t+1}-\bar{\theta}_t \right\|^2 + \eta \biggl\| \bar{\hat{v}}_t-\frac{1}{|\mathcal G_t|}\sum_{i \in \mathcal G_t}\nabla J \left( \theta_t^{(i)} \right) \biggr\|^2 \\
&\quad+ \eta \mathcal E^{\Delta}_t L^2 + \frac{2\eta}{p} \biggl\| \bar{\hat{v}}_{t+1}-\frac{1}{|\mathcal G_t|}\sum_{i \in \mathcal G_t}\nabla J \left( \theta_{t+1}^{(i)} \right) \biggr\|^2 \Biggr]\\
&\leq \E \left[ J^{*}-J \left( \bar{\theta}_t \right) - \left( \frac{1}{2\eta}-\frac{L}{2} \right) \Big\| \bar{\theta}_{t+1}-\bar{\theta}_t \Big\|^2 + \eta \Bigg\| \bar{\hat{v}}_t-\frac{1}{|\mathcal G_t|}\sum_{i \in \mathcal G_t}\nabla J \left( \theta_t^{(i)} \right) \Bigg\|^2 \right] + \eta L^2 \E[\mathcal E^{\Delta}_t] \\
&\quad- \frac{\eta}{2} \E \left[ \left\| \nabla J \left( \bar{\theta}_t \right) \right\|^2 \right] + \frac{2\eta}{p} \left( 1-\frac{p}{2} \right) \E \left[ \Bigg\| \bar{\hat{v}}_t-\frac{1}{|\mathcal G_t|}\sum_{i \in \mathcal G_t}\nabla J \left( \theta_t^{(i)} \right) \Bigg\|^2 \right] + \frac{2\eta Ap}{4p} \E \left[ \left\| \bar{\theta}_{t+1}-\bar{\theta}_t \right\|^2 \right] \\
&\quad+ \frac{2\eta C_1\sigma^2p\alpha}{4Np} + \frac{2\eta C_2\sigma^2p}{4KNp} \\
&\leq \E \left[ \Phi_t \right] - \frac{\eta}{2} \E \left[ \left\| \nabla J \left( \bar{\theta}_t \right) \right\|^2 \right] + \frac{\eta C_1\sigma^2\alpha}{2N} + \frac{\eta C_2\sigma^2}{2KN}-\frac{1}{2\eta} \left( 1-L\eta-A\eta^2 \right) \E \left[ \left\| \bar{\theta}_{t+1}-\bar{\theta}_t \right\|^2 \right] + \mathcal O \left( \eta 2^{-\kappa} \right)\\
&\leq \E \left[ \Phi_t \right] - \frac{\eta}{2} \E \left[ \left\| \nabla J \left( \bar{\theta}_t \right) \right\|^2 \right] + \frac{\eta C_1\sigma^2\alpha}{2N} + \frac{\eta C_2\sigma^2}{2KN} + \mathcal O \left( \eta 2^{-\kappa} \right)
\end{align*}

where in the second to last step we use Lemma <ref> and in last step we use Lemma C.1 from [Gorbunov et al., 2023] and our choice of $\eta$. We now sum over $t$ to obtain

\begin{align*}
\frac{1}{T} \sum_{t=0}^{T-1} \E \left[ \left\| \nabla J \left( \bar{\theta}_t \right) \right\|^2 \right] &\leq \frac{2}{\eta T} \sum_{t=0}^{T-1} \left( \E \left[
\Phi_t \right] - \left[ \Phi_{t+1} \right] \right) + \frac{C_1\sigma^2\alpha}{N} + \frac{C_2\sigma^2}{KN}+\mathcal O \left( 2^{-\kappa} \right)\\
&\leq \frac{2 \E \left[ \Phi_0 \right]}{\eta T} + \frac{C\sigma^2}{2N} \left( \alpha+\frac{1}{K} \right)+\mathcal O \left( 2^{-\kappa} \right)
\end{align*}

where $C:= \frac{1}{2}\max \left( C_1,C_2 \right)$. In the second step, we simplify the telescoping sum and use the fact that $\Phi_T \geq 0$. Note that the LHS is exactly $\E \left[ \left\| \nabla J \left( \bar{\theta}_{\widehat{T}} \right) \right\|^2 \right]$ with $\widehat{T}$ chosen u.a.r. from $[T]$. To finish the proof, notice that for any $k \in \mathcal G_t$,

\begin{align*}
\E \left[ \left\| \nabla J \left( \theta^{(k)}_{\widehat{T}} \right) \right\|^2 \right]
&\stackrel{(a)}{\leq} 2\E \left[ \left\| \nabla J \left( \bar{\theta}_{\widehat{T}} \right) \right\|^2 \right] + 2\E \left[ \left\| \nabla J \left( \theta^{(k)}_{\widehat{T}} \right)-\nabla J \left( \bar{\theta}_{\widehat{T}} \right) \right\|^2 \right] \\
&\stackrel{(b)}{\leq} 2\E \left[ \left\| \nabla J \left( \bar{\theta}_{\widehat{T}} \right) \right\|^2 \right] + 2L^2\E \left[ \mathcal E^\Delta_{\widehat{T}} \right] \\
&\stackrel{(c)}{\leq} \frac{4 \E \left[ \Phi_0 \right]}{\eta T} + \frac{C\sigma^2}{N} \left( \alpha+\frac{1}{K} \right)+\mathcal O \left( 2^{-\kappa} \right)
\end{align*}

where (a) is by Lemma <ref>, (<ref>), (b) easily follows from $L$-smoothness of $J(\cdot)$ (i.e. Proposition <ref>) and (<ref>), and (c) is by Lemma <ref>.

In order to achieve

\begin{align*}
\underbrace{\frac{4 \E \left[ \Phi_0 \right]}{\eta T}}_{(a)} + \underbrace{\frac{C\sigma^2}{N} \left( \alpha+\frac{1}{K} \right)}_{(b)} + \underbrace{\mathcal O \left( 2^{-\kappa} \right)}_{(c)} \leq \epsilon^2,
\end{align*}

we set

\begin{align*}
B=\Theta(1), \quad T=\Theta \left( \epsilon^{-2} \cdot \max \left\{ \frac{\sqrt{\alpha}}{p}, \frac{1}{\sqrt{pK}} \right\} \right), \quad\text{and}\quad
N=\Theta \left( \epsilon^{-2} \left( \alpha+\frac{1}{K} \right) \right).
\end{align*}

Since, in the statement of Theorem <ref>, we require

\begin{align*}
\eta \leq \mathcal O \left( \frac{1}{\sqrt{A}} \right) = \mathcal O \left( \min \left\{ \frac{p}{\sqrt{\alpha}},\sqrt{pK} \right\} \right),
\end{align*}

above choice of $T$ can ensure that term (a) is at most $\epsilon^2/3$. We treat $C_{ra},C_1,C_2,\sigma^2$ as constants, hence our choice of $N$ also ensures a $\epsilon^2/3$-bound for term (b), and the same holds for (c) due to our choice of $\kappa \leq \Theta \left( \log \epsilon^{-1} \right)$.

To conclude the proof, we want to count the number of trajectories sampled at an agent: Per iteration, with probability $p$ we sample $N$ times, and with probability $1-p$ we sample $B$ times. Hence over all $T$ iterations, choosing $p=\frac{1}{N}=\frac{\epsilon^2}{\alpha+1/K}$, the expected number of sampled trajectories is given by

\begin{align*}
T \left( pN+(1-p)B \right) &\leq \mathcal O(TpN)\\
&\stackrel{p=\frac{1}{N}}= \mathcal O \left( \epsilon^{-2} \cdot \max \left\{ \frac{\sqrt{\alpha}}{p}, \frac{1}{\sqrt{pK}} \right\} \right)\\
&\leq \mathcal O \left( \epsilon^{-2} \left( \frac{\alpha^{1/2} \left( \alpha+1/K \right)}{\epsilon^2} + \frac{\sqrt{\alpha+1/K}}{K^{1/2}\epsilon} \right) \right)\\
&\leq \mathcal O \left( \frac{\alpha^{3/2}}{\epsilon^4}+\frac{\alpha^{1/2}}{K\epsilon^4}+\frac{\alpha^{1/2}}{K^{1/2}\epsilon^3}+\frac{1}{K\epsilon^3} \right).
\end{align*}

§.§ Technical Lemmas

Similar to Lemma <ref> in the centralized case, we start with a standard result following from smoothness, now adjusted to the decentralized setting.

Under Assumptions <ref>, <ref>, <ref>, and <ref>, and for $\bar{\hat{v}}_t := \frac{1}{\eta} \left( \bar{\theta}_{t+1}-\bar{\theta}_t \right)$, we have

\begin{align*}
J \left( \bar{\theta}_{t+1} \right) \geq J \left( \bar{\theta}_t \right) + \frac{\eta}{2} \left\| \nabla J \left( \bar{\theta}_t \right) \right\|^2 + \left( \frac{1}{2\eta}-\frac{L}{2} \right)\left\| \bar{\theta}_{t+1}-\bar{\theta}_t \right\|^2 - \eta \left\| \bar{\hat{v}}_t-\frac{1}{|\mathcal G_t|}\sum_{i \in \mathcal G_t}\nabla J \left( \theta_t^{(i)} \right) \right\|^2 + \eta L^2 \mathcal E^{\Delta}_t.
\end{align*}

By smoothness of $J$, i.e., Proposition <ref>,

\begin{align*}
J \left( \bar{\theta}_{t+1} \right) &\geq J \left( \bar{\theta}_t \right) + \langle \nabla J \left( \bar{\theta}_t \right), \bar{\theta}_{t+1}-\bar{\theta}_t \rangle - \frac{L}{2} \left\| \bar{\theta}_{t+1}-\bar{\theta}_t \right\|^2\\
&= J \left( \bar{\theta}_t \right) + \eta \langle \nabla J \left( \bar{\theta}_t \right), \bar{\hat{v}}_t \rangle - \frac{\eta^2 L}{2} \left\| \bar{\hat{v}}_t \right\|^2\\
&\stackrel{(a)}{=} J \left( \bar{\theta}_t \right) + \frac{\eta}{2} \left\| \nabla J \left( \bar{\theta}_t \right) \right\|^2 + \frac{\eta}{2} \left\| \bar{\hat{v}}_t \right\|^2 - \frac{\eta}{2} \left\| \bar{\hat{v}}_t-\nabla J \left( \bar{\theta}_t \right) \right\|^2 - \frac{\eta^2L}{2} \left\| \bar{\hat{v}}_t \right\|^2\\
&= J \left( \bar{\theta}_t \right) + \frac{\eta}{2} \left\| \nabla J \left( \bar{\theta}_t \right) \right\|^2 + \left( \frac{1}{2\eta}-\frac{L}{2} \right)\left\| \bar{\theta}_{t+1}-\bar{\theta}_t \right\|^2 - \frac{\eta}{2} \left\| \bar{\hat{v}}_t-\nabla J \left( \bar{\theta}_t \right) \right\|^2 \\
&\stackrel{(b)}{=} J \left( \bar{\theta}_t \right) + \frac{\eta}{2} \left\| \nabla J \left( \bar{\theta}_t \right) \right\|^2 + \left( \frac{1}{2\eta}-\frac{L}{2} \right)\left\| \bar{\theta}_{t+1}-\bar{\theta}_t \right\|^2 - \eta \left\| \bar{\hat{v}}_t-\frac{1}{|\mathcal G_t|}\sum_{i \in \mathcal G_t}\nabla J \left( \theta_t^{(i)} \right) \right\|^2 \\
&\quad+ \eta \left\| \nabla J \left( \bar{\theta}_t \right)- \frac{1}{|\mathcal G_t|}\sum_{i \in \mathcal G_t}\nabla J \left( \theta_t^{(i)} \right) \right\|^2 \\
&\stackrel{(c)}{=} J \left( \bar{\theta}_t \right) + \frac{\eta}{2} \left\| \nabla J \left( \bar{\theta}_t \right) \right\|^2 + \left( \frac{1}{2\eta}-\frac{L}{2} \right)\left\| \bar{\theta}_{t+1}-\bar{\theta}_t \right\|^2 - \eta \left\| \bar{\hat{v}}_t-\frac{1}{|\mathcal G_t|}\sum_{i \in \mathcal G_t}\nabla J \left( \theta_t^{(i)} \right) \right\|^2 + \eta L^2 \mathcal E^{\Delta}_t
\end{align*}

where (a) is due to Lemma <ref>,(<ref>), (b) is by Lemma <ref>, (<ref>), and (c) easily follows from $L$-smoothness of $J$, i.e., Proposition <ref>, and the error bound (<ref>).

As a next preparatory step, we want to show that the overall gradient estimates $\tilde{v}_t^{(i)}$ do not vary too much across different agents. In particular, we bound the average of pairwise variances as follows.

Let Assumption <ref> and <ref> hold. Then, there exists a constant $C_p>0$ such that

\begin{align*}
\widetilde{\mathcal T}_{1,t} &:= \frac{1}{|\mathcal G_t|(|\mathcal G_t|-1)} \sum_{i,l \in \mathcal G_t} \E \left[ \left\| \tilde{v}_t^{(i)}-\tilde{v}_t^{(l)} \right\|^2 \mid c_t=1 \right] \leq 8 \left( \frac{\sigma^2}{N} + L^2\E[\mathcal E^{\Delta}_t] \right) \\
\widetilde{\mathcal T}_{0,t} &:= \frac{1}{|\mathcal G_t|(|\mathcal G_t|-1)} \sum_{i,l \in \mathcal G_t} \E \left[ \left\| \tilde{v}_t^{(i)}-\tilde{v}_t^{(l)} \right\|^2 \mid c_t=0 \right] \leq \frac{12\overline{\mathcal E}^{\Delta,\kappa}}{\eta^2} + \frac{36 C_p \E\left[\mathcal E^{\Delta}_t\right]}{B} + \frac{18 C_p}{B} \E \left[ \left\| \bar{\theta}_t-\bar{\theta}_{t-1} \right\|^2 \right]
\end{align*}

and we will use $\widetilde{\mathcal T}_{1,t},\widetilde{\mathcal T}_{0,t}$ also in subsequent lemmas to refer to these terms.

For the first bound, we plug in the definition of $\tilde{v}_t^{(i)}$ as in Algorithm <ref>, and use basic fact (<ref>) from Lemma <ref>, to get

\begin{align*}
\widetilde{\mathcal T}_{1,t} &= \frac{1}{|\mathcal G_t|(|\mathcal G_t|-1)} \sum_{i,l \in \mathcal G_t} \E \left[ \left\| \tilde{v}_t^{(i)}-\tilde{v}_t^{(l)} \right\|^2 \mid c_t=1 \right] \\
&= \frac{1}{|\mathcal G_t|(|\mathcal G_t|-1)} \sum_{i,l \in \mathcal G_t} \E \left[ \left\| \frac{1}{N} \sum_{j=1}^N g \left( \tau_{t,j}^{(i)} \mid \theta^{(i)}_t \right) - \frac{1}{N} \sum_{j=1}^N g \left( \tau_{t,j}^{(l)} \mid \theta^{(l)}_t \right) \right\|^2 \right] \\
&\leq \frac{1}{|\mathcal G_t|(|\mathcal G_t|-1)} \sum_{i,l \in \mathcal G_t} \E \left[ 2\left\| \frac{1}{N} \sum_{j=1}^N g \left( \tau_{t,j}^{(i)} \mid \theta^{(i)}_t \right) - \nabla J \left( \bar\theta_t \right) \right\|^2 + 2\left\| \frac{1}{N} \sum_{j=1}^N g \left( \tau_{t,j}^{(l)} \mid \theta^{(l)}_t \right) - \nabla J \left( \bar\theta_t \right) \right\|^2 \right] \\
&= \frac{4}{|\mathcal G_t|} \sum_{i \in \mathcal G_t} \E \left[ \left\| \frac{1}{N} \sum_{j=1}^N g \left( \tau_{t,j}^{(i)} \mid \theta^{(i)}_t \right) - \nabla J \left( \bar\theta_t \right) \right\|^2 \right] \\
&\leq \frac{4}{|\mathcal G_t|} \sum_{i \in \mathcal G_t} 2\underbrace{\E \left[ \left\| \frac{1}{N}\sum_{j=1}^N g \left( \tau_{t,j}^{(i)} \mid \theta_t^{(i)} \right) - \nabla J \left( \theta_t^{(i)} \right) \right\|^2 \right]}_{\stackrel{(a)}{\leq} \;\frac{\sigma^2}{N}} + 2\underbrace{\E \left[\left\|  \nabla J \left( \theta_t^{(i)} \right) - \nabla J \left( \bar{\theta}_t \right) \right\|^2 \right]}_{\stackrel{(b)}{\leq} \;L^2 \E\left[\mathcal E^{\Delta}_t\right]} \\
&\leq 8 \left( \frac{\sigma^2}{N} + L^2 \E\left[\mathcal E^{\Delta}_t\right] \right)
\end{align*}

where (a) is by Lemma <ref> and (b) easily follows from $L$-smoothness of $J$, i.e., Proposition <ref>, and error bound (<ref>).

Then, the second bound follows from

\begin{align*}
\widetilde{\mathcal T}_{0,t} &= \frac{1}{|\mathcal G_t|(|\mathcal G_t|-1)} \sum_{i,l \in \mathcal G_t} \E \left[ \left\| \tilde{v}_t^{(i)}-\tilde{v}_t^{(l)} \right\|^2 \mid c_t=0 \right] \\
&= \frac{1}{|\mathcal G_t|(|\mathcal G_t|-1)} \sum_{i,l \in \mathcal G_t} \E \left[ \left\| \left( \hat{\Delta}^B \left( \theta_t^{(i)},\theta_{t-1}^{(i)} \right) + \hat{v}_{t-1}^{(i)} \right) - \left( \hat{\Delta}^B \left( \theta_t^{(l)},\theta_{t-1}^{(l)} \right) + \hat{v}_{t-1}^{(l)} \right) \right\|^2 \right] \\
&\leq \frac{1}{|\mathcal G_t|(|\mathcal G_t|-1)} \sum_{i,l \in \mathcal G_t} 3\,\E \left[ \left\| \hat{\Delta}^B \left( \theta_t^{(i)},\theta_{t-1}^{(i)} \right) \right\|^2 \right] + 3\,\E \left[ \left\| \hat{\Delta}^B \left( \theta_t^{(l)},\theta_{t-1}^{(l)} \right) \right\|^2 \right] + 3\,\E \left[ \left\| \hat{v}_{t-1}^{(i)} -  \hat{v}_{t-1}^{(l)} \right\|^2 \right] \\
&\stackrel{(a)}{\leq} \frac{12\overline{\mathcal E}^{\Delta,\kappa}}{\eta^2} + \frac{1}{|\mathcal G_t|(|\mathcal G_t|-1)} \sum_{i,l \in \mathcal G_t} \frac{3C_p}{B} \E \left[ \left\| \theta_t^{(i)}-\theta_{t-1}^{(i)} \right\|^2 \right] + \frac{3C_p}{B} \E \left[ \left\| \theta_t^{(l)}-\theta_{t-1}^{(l)} \right\|^2 \right] \\
&\leq \frac{12\overline{\mathcal E}^{\Delta,\kappa}}{\eta^2} + \frac{6C_p}{B|\mathcal G_t|}\sum_{i \in \mathcal G_t} \E \left[ \left\| \theta_t^{(i)}-\theta_{t-1}^{(i)} \right\|^2 \right] \\
&\leq \frac{12 \overline{\mathcal E}^{\Delta,\kappa}}{\eta^2} + \frac{6C_p}{B|\mathcal G_t|}\sum_{i \in \mathcal G_t} \E \left[ 3 \left\| \theta_t^{(i)}-\bar{\theta}_t \right\|^2 + 3 \left\| \bar{\theta}_t-\bar{\theta}_{t-1} \right\|^2 + 3 \left\| \bar{\theta}_{t-1}-\theta_{t-1}^{(i)} \right\|^2 \right] \\
&\stackrel{(b)}{\leq} \frac{12\overline{\mathcal E}^{\Delta,\kappa}}{\eta^2} + \frac{36 C_p \E \left[ \mathcal E^\Delta_t \right]}{B} + \frac{18 C_p}{B} \E \left[ \left\| \bar{\theta}_t-\bar{\theta}_{t-1} \right\|^2 \right].
\end{align*}

Step (a) is due to

\begin{align*}
\frac{1}{|\mathcal G_t| \left( |\mathcal G_t|-1 \right)} \sum _{i,l \in \mathcal G_t} \E \left[ \left\| \hat{v}_{t-1}^{(i)} -  \hat{v}_{t-1}^{(l)} \right\|^2 \right] &\leq \frac{1}{|\mathcal G_t| \left( |\mathcal G_t|-1 \right)} \sum _{i,l \in \mathcal G_t} \E \left[ \left\| \frac{1}{\eta} \left[ \left( \theta_t^{(i)}-\theta_t^{(l)} \right) + \left( \theta_{t-1}^{(i)}-\theta_{t-1}^{(l)} \right) \right] \right\|^2 \right] \\
&\leq \frac{2 \E \left[ \mathcal E^\Delta_t \right] + 2 \E \left[ \mathcal E^\Delta_{t-1} \right]}{\eta^2} \\
&\leq \frac{4 \overline{\mathcal E}^{\Delta,\kappa}}{\eta^2}
\end{align*}

where in the last step we use our bound $\overline{\mathcal E}^{\Delta,\kappa}$ from Lemma <ref> that is independent of $t$. The second fact used in (a) is that there exists constant $C_p>0$ such that

\begin{align*}
\E \left[ \left\| \hat{\Delta}^B \left( \theta_t^{(i)},\theta_{t-1}^{(i)} \right) \right\|^2 \right] \leq \frac{C_p}{B} \E \left[ \left\| \theta_t^{(i)}-\theta_{t-1}^{(i)} \right\|^2 \right]
\end{align*}

which follows similarly as Lemma B.1 in [Gargiani et al., 2022].
Step (b) is because, using Lemma <ref> in the first step, we have

\begin{align*}
\frac{1}{|\mathcal G_t|} \sum _{i \in \mathcal G_t} \left\| \theta_t^{(i)}-\bar{\theta}_t \right\|^2 \leq \frac{1}{|\mathcal G_t| \left( |\mathcal G_t|-1 \right)} \sum _{i,l \in \mathcal G_t} \left\| \theta_t^{(i)}-\theta^{(l)}_t \right\|^2 \leq \mathcal E^{\Delta}_t.
\end{align*}

Next, we want to see how good our realized average gradient estimates $\bar{\hat{v}}_t$ are, i.e., how much they deviate from $\nabla J \left( \bar{\theta}_t \right)$ which is what we aim to estimate. Note that this is a key component since both the aggregation and averaging steps introduce bias that we need to control here.

In the setting of Theorem <ref>, the following bounds hold:

\begin{align*}
\mathcal T_{x1,t}^{(1)} &:= \E \left[ \left\| \bar{\hat{v}}_t-\bar{v}_t \right\|^2 \mid c_{t-1}=1 \right] \leq \frac{C_{avg}^2}{\eta^2}\, \left[ 2 \E[\mathcal E^\Delta_t] + \frac{10 \eta^2C_{ra}\alpha}{\bar{\epsilon}}\widetilde{\mathcal T}_{1,t} \right], \\
\mathcal T_{x0,t}^{(1)} &:= \E \left[ \left\| \bar{\hat{v}}_t-\bar{v}_t \right\|^2 \mid c_{t-1}=0 \right] \leq \frac{C_{avg}^2}{\eta^2}\, \left[ 2 \E[\mathcal E^\Delta_t] + \frac{10 \eta^2 C_{ra}\alpha}{\bar{\epsilon}} \widetilde{\mathcal T}_{0,t} \right], \\
\mathcal T_{1x,t}^{(2)} &:= \E \left[ \left\| \bar{v}_t-\bar{\tilde{v}}_t \right\|^2 \mid c_t=1 \right] \leq C_{ra}\alpha \widetilde{\mathcal T}_{1,t}, \\
\mathcal T_{0x,t}^{(2)} &:= \E \left[ \left\| \bar{v}_t-\bar{\tilde{v}}_t \right\|^2 \mid c_t=0 \right] \leq C_{ra}\alpha \widetilde{\mathcal T}_{0,t}, \\
\mathcal T_{1x,t}^{(3)} &:= \E \left[ \left\| \bar{\tilde{v}}_t-\frac{1}{|\mathcal G_t|} \sum_{i \in \mathcal G_t}  \nabla J \left( \theta_t^{(i)} \right) \right\|^2 \mid c_t=1 \right] \leq \frac{4\sigma^2}{KN}, \quad\text{and}, \\
\mathcal T_{0x,t}^{(3)} &:= \E \left[ \left\| \bar{\tilde{v}}_t - \frac{1}{|\mathcal G_t|} \sum_{i \in \mathcal G_t}  \nabla J \left( \theta_t^{(i)} \right) \right\|^2 \mid c_t=0 \right] \\ &\leq \E \left[ \left\| \bar{\hat{v}}_{t-1}-\frac{1}{|\mathcal G_t|} \sum_{i \in \mathcal G_t}  \nabla J \left( \theta_{t-1}^{(i)} \right) \right\|^2 \right] + \left( \frac{8 C_p}{BK} + \frac{8L^2}{K} \right) \E \left[ \left\| \bar{\theta}_t - \bar{\theta}_{t-1} \right\|^2 \right]
\end{align*}

where $\mathcal T_{ab,t}^{(i)}$ denotes the error in iteration $t$ with $c_t=a, c_{t-1}=b$, and due to averaging agreement for $i=1$, due to aggregation for $i=2$, and due to the randomness of sampling for $i=3$.

We proceed by showing each of the claimed bounds separately, as follows:

* We have

\begin{align*}
\mathcal T_{x1,t}^{(1)}
&= \E \left[ \left\| \bar{\hat{v}}_t-\bar{v}_t \right\|^2 \mid c_{t-1}=1 \right] \\
&= \E \left[ \left\| \frac{1}{\eta} \left( \bar{\theta}_{t+1}-\bar{\theta}_{t} \right) - \frac{1}{\eta} \left( \bar{\tilde{\theta}}_{t+1}-\bar{\theta}_{t} \right) \right\|^2 \mid c_{t-1}=1 \right] \\
&= \frac{1}{\eta^2} \E \left[ \left\| \bar{\theta}_{t+1}-\bar{\tilde{\theta}}_{t+1} \right\|^2 \mid c_{t-1}=1 \right] \\
&\stackrel{(a)}{\leq} \frac{C_{avg}^2}{\eta^2}\, \E \left[ \Delta_2 \left( \langle \tilde{\theta}_t^{(i)} \rangle_{i \in \mathcal G_t} \right)^2 \mid c_{t-1}=1 \right] \\
&\stackrel{(b)}{\leq} \frac{C_{avg}^2}{\eta^2}\, \left[ 2 \E[\mathcal E^\Delta_t] + \frac{10 \eta^2}{\bar{\epsilon}} \widetilde{\mathcal T}_{1,t} \right]
\end{align*}

where (a) is by the definition of averaging agreement, i.e., Definition <ref>, and (b) follows from Lemma <ref>.

* This follows equivalently to 1. — conditioning the expectation on $c_{t-1}=0$ instead of $c_{t-1}=1$ replaces $\widetilde{\mathcal T}_{1,t} $ by $\widetilde{\mathcal T}_{0,t}$ in the result.

* First, by applying Lemma <ref> and Definition <ref>,

\begin{align*}
\mathcal T_{1x,t}^{(2)} = \E \left[ \left\| \bar{v}_t-\bar{\tilde{v}}_t \right\|^2 \mid c_t=1 \right]
&\leq \frac{1}{|\mathcal G_t|} \sum_{j \in \mathcal G_t} \E \left[ \left\| v^{(j)}_t-\bar{\tilde{v}}_t \right\|^2 \mid c_t=1 \right] \\
&\leq \frac{1}{|\mathcal G_t|} \sum_{j \in \mathcal G_t} \frac{C_{ra} \alpha}{|\mathcal G_t|(|\mathcal G_t|-1)} \sum_{i,l \in \mathcal G_t} \E \left[ \left\| \tilde{v}_t^{(i)}-\tilde{v}_t^{(l)} \right\|^2 \mid c_t=1 \right] \\
&= \frac{C_{ra} \alpha}{|\mathcal G_t|(|\mathcal G_t|-1)} \sum_{i,l \in \mathcal G_t} \E \left[ \left\| \tilde{v}_t^{(i)}-\tilde{v}_t^{(l)} \right\|^2 \mid c_t=1 \right] \\
&\leq C_{ra}\alpha \widetilde{\mathcal T}_{1,t}
\end{align*}

where the final step is the result of Lemma <ref>.

* Again, this is equivalent to 3. — conditioning the expectation on $c_{t}=0$ instead of $c_{t}=1$ replaces $\widetilde{\mathcal T}_{1,t} $ by $\widetilde{\mathcal T}_{0,t}$ in the result.

* By plugging in the definition of $\bar{\tilde{v}}_t$, we get

\begin{align*}
\mathcal T_{1x,t}^{(3)} &= \E \left[ \left\| \bar{\tilde{v}}_t- \frac{1}{|\mathcal G_t|} \sum_{i \in \mathcal G_t} \nabla J \left( \theta^{(i)}_t \right) \right\|^2 \mid c_t=1 \right] \\
&\leq \E \left[ \left\| \frac{1}{|\mathcal G_t|} \sum_{i \in \mathcal G_t} \frac{1}{N} \sum_{j=1}^N g \left( \tau_{t,j}^{(i)} \mid \theta_t^{(i)} \right) - \frac{1}{|\mathcal G_t|} \sum_{i \in \mathcal G_t} \nabla J \left( \theta^{(i)}_t \right) \right\|^2 \right] \\
&= \E \left[ \left\| \frac{1}{|\mathcal G_t|N} \sum_{i \in \mathcal G_t} \sum_{j=1}^N g \left( \tau_{t,j}^{(i)} \mid \theta_t^{(i)} \right) - \nabla J \left( \theta^{(i)}_t \right) \right\|^2 \right] \\
&\leq \frac{\sigma^2}{|\mathcal G_t|N} \\
&\leq \frac{4\sigma^2}{KN}
\end{align*}

where the second to last step follows by an argument similar to Lemma <ref>. The last step then is due to $|\mathcal G_t| \geq (1-\bar\alpha)K \geq (1-\alpha_{\max})K \geq K/4$.

* First, observe that $\hat{\Delta}^M \left( \theta_t^{(k)},\theta_{t-1}^{(k)} \right)$ is an unbiased estimate of $\Delta \left( \theta_t^{(k)},\theta_{t-1}^{(k)} \right)$.

\begin{align*}
\mathcal T_{0x,t}^{(3)} &= \E \left[ \left\| \bar{\tilde{v}}_t - \frac{1}{|\mathcal G_t|} \sum_{i \in \mathcal G_t}  \nabla J \left( \theta_t^{(i)} \right) \right\|^2 \mid c_t=0 \right] \\
&= \E \left[ \left\| \frac{1}{|\mathcal G_t|} \sum_{i \in \mathcal G_t} \hat{\Delta}_i^B \left( \theta_t^{(i)},\theta_{t-1}^{(i)} \right) + \hat{v}_{t-1}^{(i)} - \nabla J \left( \theta_t^{(i)} \right) \right\|^2 \right] \\
&= \E \left[ \left\| \frac{1}{|\mathcal G_t|} \sum_{i \in \mathcal G_t} \hat{\Delta}_i^B \left( \theta_t^{(i)},\theta_{t-1}^{(i)} \right) + \hat{v}_{t-1}^{(i)} + \nabla J \left( \theta_{t-1}^{(i)} \right) - \nabla J \left( \theta_{t-1}^{(i)} \right) - \nabla J \left( \theta_t^{(i)} \right) \right\|^2 \right] \\
&= \E \Biggr[ \Biggr\| \underbrace{\Bigg( \bar{\hat{v}}_{t-1}- \frac{1}{|\mathcal G_t|} \sum_{i \in \mathcal G_t} \nabla J \left( \theta^{(i)}_{t-1} \right) \Bigg)}_{=: X_1} + \underbrace{\Bigg( \frac{1}{|\mathcal G_t|} \sum_{i \in \mathcal G_t} \hat{\Delta}_i^B \left( \theta_t^{(i)},\theta_{t-1}^{(i)} \right) - \Delta_i \left( \theta_t^{(i)},\theta_{t-1}^{(i)} \right) \Bigg)}_{=:X_2} \Biggr\|^2 \Biggr] \\
&\stackrel{(a)}{=} \E \left[ \left\| \bar{\hat{v}}_{t-1}- \frac{1}{|\mathcal G_t|} \sum_{i \in \mathcal G_t} \nabla J \left( \theta^{(i)}_{t-1} \right) \right\|^2 \right] + \E \left[ \left\| \frac{1}{|\mathcal G_t|} \sum_{i \in \mathcal G_t} \hat{\Delta}_i^B \left( \theta_t^{(i)},\theta_{t-1}^{(i)} \right) - \Delta_i \left( \theta_t^{(i)},\theta_{t-1}^{(i)} \right) \right\|^2 \right] \\
&\stackrel{(b)}{\leq} \E \left[ \left\| \bar{\hat{v}}_{t-1}- \frac{1}{|\mathcal G_t|} \sum_{i \in \mathcal G_t} \nabla J \left( \theta^{(i)}_{t-1} \right) \right\|^2 \right] + \frac{4}{K^2} \sum_{i \in \mathcal G_t} \E \left[ \left\| \hat{\Delta}_i^B \left( \theta_t^{(i)},\theta_{t-1}^{(i)} \right) - \Delta_i \left( \theta_t^{(i)},\theta_{t-1}^{(i)} \right) \right\|^2 \right] \\
&\stackrel{(c)}{\leq} \E \left[ \left\| \bar{\hat{v}}_{t-1}- \frac{1}{|\mathcal G_t|} \sum_{i \in \mathcal G_t} \nabla J \left( \theta^{(i)}_{t-1} \right) \right\|^2 \right] + \left( \frac{8 C_p}{BK} + \frac{8L^2}{K} \right) \E \left[ \left\| \bar{\theta}_t - \bar{\theta}_{t-1} \right\|^2 \right]
\end{align*}

Step (a) requires further justification: Note that $X_1$ does not depend on any randomness at step $t$, and also $\E \left[ X_2 \right]=0$. Hence, denoting by $\E_t$ the expectation over the randomness in step $t$, we can use the tower rule to get

\begin{align*}
\E \left[ \left\| X_1+X_2 \right\|^2 \right] &= \E \left[ \E_t \left[ \left\| X_1+X_2 \right\|^2 \right] \right] \\
&= \E \Bigg[ \left\| X_1 \right\|^2 + 2 \langle X_1, \underbrace{\E_t \left[ X_2 \right]}_{=0} \rangle + \E_t \left[ \left\| X_2 \right\|^2 \right] \Bigg] \\[4pt]
&= \E \left[ \left\| X_1 \right\|^2 \right]  + \E \left[ \left\| X_2 \right\|^2 \right]
\end{align*}

which then justifies (a). Step (b) follows from a similar argument on a sum of $|\mathcal G_t|$ random variables, the fact that $\E \left[ \hat{\Delta}^M \left( \theta_t^{(k)},\theta_{t-1}^{(k)} \right) \right] = \Delta \left( \theta_t^{(k)},\theta_{t-1}^{(k)} \right)$, and $|\mathcal G_t| \geq K/4$ as noted above. Step (c) then follows from the same argument used in the second part of the proof of Lemma <ref>.

In the setting of Lemma <ref>, let $\mathcal T_t:=\left\| \bar{\hat{v}}_{t}-\frac{1}{|\mathcal G_t|} \sum_{i \in \mathcal G_t} \nabla J \left( \theta^{(i)}_t \right) \right\|^2$. Then, we have

\begin{align*}
\E \left[ \left\| \mathcal T_t \right\|^2 \right] &\leq \left( 1-\frac{p}{2} \right) \E \left[ \left\| \mathcal T_{t-1} \right\|^2 \right] + \frac{Ap}{4} \E \left[ \left\| \bar{\theta}_t - \bar{\theta}_{t-1} \right\|^2 \right] + \frac{C_1\sigma^2p\alpha}{4N} + \frac{C_2\sigma^2p}{4KN}
\end{align*}

where $C_1,C_2>0$ are constants, and $A = \Theta \left( \frac{\alpha}{p^2B} + \frac{1}{pK} \right)$.

By the law of total expectation,

\begin{align*}
\E \left[ \mathcal T_t \right] &= p \E \left[ \mathcal T_t \mid c_t=1 \right]+ (1-p)\E \left[ \mathcal T_t \mid c_t=0 \right] \\
&= p\E \left[ \mathcal T_t \mid c_t=1 \right] + (1-p)\Big( p\E \left[ \mathcal T_t \mid c_t=0 \land c_{t-1}=1 \right] + (1-p) \E \left[ \mathcal T_t \mid c_t=0 \land c_{t-1}=0 \right] \Big).
\end{align*}

By applying (<ref>) and (<ref>) of Lemma <ref>, we further choose the following way of bounding:

\begin{align*}
\E \left[ \mathcal T_t \mid c_t=1 \right] &\leq 3 \left( p \mathcal T_{x1,t}^{(1)} + (1-p) \mathcal T_{x0,t}^{(1)} \right) + 3 \mathcal T_{1x,t}^{(2)} + 3 \mathcal T_{1x,t}^{(3)}, \\
\E \left[ \mathcal T_t \mid c_t=0 \land c_{t-1}=1 \ \right] &\leq 22 \mathcal T_{x1,t}^{(1)} + 22 \mathcal T_{0x,t}^{(2)} + 1.1 \mathcal T_{0x,t}^{(3)}, \quad\text{and} \\
\E \left[ \mathcal T_t \mid c_t=0 \land c_{t-1}=0 \right] &\leq \left( 2+\frac{8}{p} \right) \mathcal T_{x0,t}^{(1)} + \left( 2+\frac{8}{p} \right) \mathcal T_{0x,t}^{(2)} + \left( 1+\frac{p}{4} \right) \mathcal T_{0x,t}^{(3)}.
\end{align*}

Putting everything together, we get

\begin{align*}
\E \left[ \mathcal T_t \right] &\leq \left( 3p^2+22p \left( 1-p \right) \right) \mathcal T_{x1,t}^{(1)} + \left( 3p \left( 1-p \right) + \left( 1-p \right)^2 \left( 2+\frac{8}{p} \right) \right) \mathcal T_{x0,t}^{(1)} + 3p \mathcal T_{1x,t}^{(2)} \\
&\;+ \left( 22p \left( 1-p \right) + \left( 1-p \right)^2 \left( 2+\frac{8}{p} \right) \right) \mathcal T_{0x,t}^{(2)} + 3p \mathcal T_{1x,t}^{(3)} \\&+ \left( 1.1p \left( 1-p \right) + \left( 1-p \right)^2 \left( 1+\frac{p}{4} \right) \right) \mathcal T_{0x,t}^{(3)} \\
&\leq 22p \mathcal T_{x1,t}^{(1)} + \frac{8}{p} \mathcal T_{x0,t}^{(1)} + 3p \mathcal T_{1x,t}^{(2)} + \frac{22}{p} \mathcal T_{0x,t}^{(2)} + 3p \mathcal T_{1x,t}^{(3)} + \left( 1-\frac{p}{2} \right) \mathcal T_{0x,t}^{(3)}
\end{align*}

where the last step follows from Lemma <ref>, (<ref>).

After plugging in the results of Lemma <ref>, rearranging, and choosing large enough constants $C_1,C_2>0$, we get

\begin{align*}
&\E \left[ \mathcal T_t \right] \\[4pt]
\leq &\;\widetilde{\mathcal T}_{1,t} \left[ \frac{220p c \alpha C_{avg}^2}{\bar{\epsilon}}+3pC_{ra}\alpha \right] + \widetilde{\mathcal T}_{0,t} \left[ \frac{80C_{ra}\alpha C_{avg}^2}{p \bar{\epsilon}}+\frac{22C_{ra}\alpha}{p} \right] + \frac{4C_{avg}^2\overline{\mathcal E}^{\Delta,\kappa}}{\eta^2}\left( 11p+\frac{4}{p} \right) \\
&\quad+ \frac{12p\sigma^2}{KN} + \left( 1-\frac{p}{2} \right) \mathcal T_{0x,t}^{(3)}\\[6pt]
= &\;\overline{\mathcal E}^{\Delta,\kappa} \cdot \underbrace{\left[ \frac{4C_{avg}^2}{\eta^2}\left( 11p+\frac{4}{p} \right)+8L^2 \left( \frac{220p c \alpha C_{avg}^2}{\bar{\epsilon}}+3pC_{ra}\alpha \right) + \left( \frac{12}{\eta^2} + \frac{36 C_p}{B} \right) \left( \frac{80C_{ra}\alpha C_{avg}^2}{p \bar{\epsilon}}+\frac{22C_{ra}\alpha}{p} \right) \right]}_{=: \mathcal Z}\\
&\quad + \frac{8\sigma^2}{N} \left( \frac{220p c \alpha C_{avg}^2}{\bar{\epsilon}}+3pC_{ra}\alpha + \frac{3p}{2K} \right) + \frac{18 C_p}{B} \E\left\| \bar{\theta}_t - \bar{\theta}_{t-1} \right\|^2 \left( \frac{80C_{ra}\alpha C_{avg}^2}{p \bar{\epsilon}}+\frac{22C_{ra}\alpha}{p} \right)\\
&\quad+ \left( 1-\frac{p}{2} \right) \left[ \E \left[ \mathcal T_{t-1} \right] + \left( \frac{8 C_p}{BK} + \frac{8L^2}{K} \right) \E \left[ \left\| \bar{\theta}_t - \bar{\theta}_{t-1} \right\|^2 \right] \right] \\
\stackrel{(a)}{\leq} &\;\frac{\sigma^2}{4N} \left( C_1 p \alpha + \frac{C_2 p}{K} \right) + \mathcal O \left( \frac{\alpha}{p} \right) \E\left\| \bar{\theta}_t - \bar{\theta}_{t-1} \right\|^2 + \left( 1-\frac{p}{2} \right) \left[ \E \left[ \mathcal T_{t-1} \right] + \mathcal O \left( \frac{1}{K} \right) \E \left[ \left\| \bar{\theta}_t - \bar{\theta}_{t-1} \right\|^2 \right] \right].
\end{align*}

In step (a) we switch to asymptotic analysis, treating $\sigma,C_{avg},\eta,\bar{\epsilon},L,C_{ra}$ and $C_p$ as constants, and using $\alpha,p \leq 1$, and $B \geq 1$. Moreover, because of Lemma <ref>, we know $\overline{\mathcal E}^{\Delta,\kappa} \leq \mathcal O \left( 2^{-\kappa} \right)$, and further, one can see that $\mathcal Z = \Theta \left( 1/p \right)$. Therefore, with our choice of $\kappa=\Theta \left( \log\frac{KN}{p^2} \right)$, we have $\overline{\mathcal E}^{\Delta,\kappa} \cdot \mathcal Z \leq \mathcal O \left( \frac{p}{KN} \right)$ and this term hence gets swallowed by the constant $C_2$. From the last line above, it becomes clear that for

\begin{align*}
A = \Theta \left( \frac{\alpha}{p^2B} + \frac{1}{pK} \right)
\end{align*}

the result of the lemma follows.

§ EXPERIMENTAL SETUP

§.§ Hyperparameters

Throughout all experiments, policies are parameterized as neural networks, and we use the Adam [Kingma and Ba, 2014] optimizer during training. We summarize the chosen hyperparameters, some of which are adopted from [Fan et al., 2021] and [Gargiani et al., 2022], in Table <ref>, and refer to the repository provided as supplementary material for instructions on how to run the script that specifies the seeds and reproduces the experiments contained in this paper.

§.§ Compute Requirements

Our experiments have been conducted on a 4-core Intel(R) Xeon(R) CPU E3-1284L v4 clocked at 2.90GHz and equipped with 8Gbs of memory. Since no GPUs have been used, all experiments are fully reproducible using the specified seeds. Moreover, each individual experiment can terminate within less than 5 hours for CartPole tasks, and less than 15 hours for LunarLander tasks, on the specified hardware.

Hyperparameters     CartPole     LunarLander
NN policy     Categorical MLP     Categorical MLP

NN hidden weights     16,16     64,64

NN activation     ReLU     Tanh

NN output activation     Tanh     Tanh

Step size (Adam) $\eta$     5e-3     1e-3

Discount factor $\gamma$     0.999     0.999

Task horizon $H$     500     1000

Small batch size $B$     4     32

Large batch size $N$     50     96

Switching probability $p$     0.2     0.2

Hyperparameters used in our experiments.

§ ADDITIONAL EXPERIMENTS

§.§ Experiments for ByzPG

Performance of ByzPG for different federation sizes when all agents behave honestly (i.e. $\alpha=0$).
Performance of ByzPG for different federation sizes when all agents behave honestly (i.e. $\alpha=0$).

In Figure <ref>, we consider ByzPG in the case $\alpha=0$, with $K=1$ (which is equivalent to PAGE-PG [Gargiani et al., 2022]), $K=5$, and $K=13$. Speed-up with increasing number of agents is observable in both environments, as suggested by Corollary <ref>. Such faster convergence provides empirical evidence motivating agents to join a (centralized) federation.

In Figure <ref> and <ref>, we compare ByzPG under the same attacks as described in Section <ref> to (a) PAGE-PG [Gargiani et al., 2022], the SOTA single-agent PG method that ByzPG reduces to when $K=1$, and (b) Fed-PAGE-PG, a naive centralized federated (but not fault-tolerant) version of PAGE-PG where aggregation of gradients is done by averaging.

Performance & resilience of ByzPG for CartPole w.r.t. our three attack types.

Performance & resilience of ByzPG for CartPole w.r.t. our three attack types.

Performance & resilience of ByzPG for LunarLander w.r.t. our three attack types.

Performance & resilience of ByzPG for LunarLander w.r.t. our three attack types.

We observe that for both environments and all attacks, ByzPG performs nearly on par with the unattacked PAGE-PG. This empirically supports the Byzantine fault-tolerance of ByzPG. Furthermore, for CartPole, as expected, LargeNoise and AvgZero are highly effective against the non-fault-tolerant method, while RandomAction barely shows any effect, similar to our observation for the decentralized case in Section <ref>. For the more difficult task of LunarLander, already RandomAction breaks PAGE-PG. Finally, we conclude by pointing out that in all cases ByzPG with $K=13$ and $\alpha > 0$ outperforms PAGE-PG with $K=1$ (and $\alpha=0$), meaning that in our experiments, despite the presence of Byzantines, joining the (centralized) federation is empirical beneficial for faster convergence.

get arXiv to do 4 passes: Label(s) may have changed. Rerun