Byzantine-Robust Online and Offline Distributed Reinforcement Learning

Distributed learning systems have been one of the main driving force to recent successes of deep learning [Verbraeken et al., 2020, Goyal et al., 2017, Abadi et al., 2016]. Advances in designing efficient distributed optimization algorithms[Horgan et al., 2018] and deep learning infrastructures [Espeholt et al., 2018] have enables training powerful models with hundreds of billions of parameters [Brown et al., 2020]. However, with the outsourcing of computation and data collection, new challenges emerges. In particular, distributed system has been found vulnerable to Byzantine failure [LAMPORT et al., 1982], meaning there could be agents with failure that may send arbitrary information to the central server. Even a small number of Byzantine machines who send out moderate value can lead to a significant loss in performance [Yin et al., 2018, Ma et al., 2019, Zhang et al., 2020a], which raise security concern in real world applications such as chatbot [Neff and Nagy, 2016] and autonomous vehicles [Eykholt et al., 2018, Ma et al., 2021]. In addition, other desired properties are chased after, such as protecting data privacy of individual data contributors [Sakuma et al., 2008, Liu et al., 2019] and and reducing communication cost[Dubey and Pentland, 2021]. These challenges requires new algorithmic design on the server side, which is the main focus of this paper.

When it comes to reinforcement learning (RL), distributed learning has been prevalent to many large scale decision making problems even before the deep learning era, such as cooperative learning in robotics systems [Ding et al., 2020], power grids optimization [Yu et al., 2014], automatic traffic control [Bazzan, 2009]. Different from supervised learning where the data distribution of interest is often fixed a prior, reinforcement learning requires active exploration on the agent’s side to discover the optimal policy for the current task, thus creating new challenges in achieving the above desiderata while exploring in an unknown environment.

This paper studies this precise problem:

Can we design a distributed RL algorithm that is sample efficient and robust to Byzantine agents, while having small communication costs and promote data privacy?

We study Byzantine-robust RL in both online and offline reinforcement learning settings: in the online setting, a central server is designed to outsource the exploration task to $m$ agents, and the agents collect experiences and send back to the server, and the server use the data to update its policy; in the offline setting, a central server collects logged data from $m$ agents and use the data to identify a good policy, without the additional interaction to the environment. Importantly, among the $m$ agents, $\alpha$ fraction are Byzantine, meaning they are allowed to send out arbitrary data in both the online and offline setting. We summarize our contributions as following:

1. 1.

   We design Weighted-Clique, a robust mean estimation algorithm for learning from batches. By utilizing the batch structure, the estimation error of our algorithm vanishes with more data. Compared to prior works [Qiao and Valiant, 2017, Chen et al., 2020, Jain and Orlitsky, 2021, Yin et al., 2018], our algorithm adapts to arbitrary batch sizes, which is desired in many applications of interests.

2. 2.

   We design Byzan-UCBVI, a Byzantine-Robust variant of optimistic value iteration for online RL by calling Weighted-Clique as a subroutine. We show that Byzan-UCBVI achieves near-optimal regret with $\alpha$-fraction Byzantine agents. Meanwhile, Byzan-UCBVI also enjoys a logarithmic communication cost and switching cost [Bai et al., 2019, Zhang et al., 2020b, Gao et al., 2021], and preserves data privacy of individual agents.

3. 3.

   We design Byzan-PEVI, a Byzantine-Robust variant of pessimistic value iteration for offline RL again utilizing Weighted-Clique as a subroutine. Despite of the presence of Byzantine agents, we show that Byzan-PEVI can learn a near-optimal policy with polynomial name of samples, when certain good coverage properties are satisfied [Zhang et al., 2021a].

We first present our novel algorithm, Weighted-Clique, for the robust mean estimation from batches problem, which we define below. Weighted-Clique will be the main workhorse later in our algorithms for both offline and online Byzantine-robust RL problems.

Definition 3.1 considers a robust learning problem from batches where we allow arbitarily different batch sizes. In contrast, prior works [Qiao and Valiant, 2017, Chen et al., 2020, Jain and Orlitsky, 2021] have only studied the setting with (roughly) equal batch sizes, which is much more restricted. For this problem, we propose the Weighted-Clique algorithm (Algorithm 1). Given the batch datasets $\left\{x_{1}^{i}\right\}_{i=1}^{n_{1}},\left\{x_{2}^{i}\right\}_{i=1}^{n_{2}},\ldots,\left\{x_{m}^{i}\right\}_{i=1}^{n_{m}}$, parameter $\sigma$ of the sub-Gaussian distribution, corruption level $\alpha$, and confidence level $\delta$, Weighted-Clique first performs a clipping step (Line 4) to clip the sizes of the largest $2\alpha m$ batches to the size of the $(2\alpha+1)m$-th largest batch. This is to reduce the impact of corrupted batch on the weighted average in Line 7. Next, a set confidence intervals for the true mean $\mu$ is constructed in Line 5 based on the data of each batch, where $I_{j}=\mathbb{R}$ if $n_{j}=0$. In order to remove the outliers, the algorithm find the largest set of batches whose confidence intervals all intersect. This can be formulated as a maximum-clique problem, and thus the name Weighted-Clique. The largest clique can be found efficiently by sorting and scanning endpoints of all $I_{j}$’s. This algorithm returns the weighted average of empirical means of the maximum clique, where the weights are given by clipped sample size, $\tilde{n}_{j}$.

Intuitively, by choosing the maximum clique in Line 6, Algorithm 1 finds a cluster of good data batches and drops extreme batches. We show that Algorithm 1 achieves the following guarantee.

A number of immediate remarks are in order.

We study the problem of Byzantine-robust reinforcement learning in the parallel Markov Decision Processes (MDPs) setting with one central server and $m$ agents, $\alpha$ fraction of which may suffer Byzantine failure. We postpone the precise interaction protocols between the server and agents to Section 5 and Section 6.

In both online and offline settings, we consider a finite horizon episodic tabular Markov Decision Process (MDP) $\mathcal{M}=\left({\mathcal{S}},\mathcal{A},\mathcal{P},\mathcal{R},H,\mu_{1}\right)$. Where ${\mathcal{S}}$ is the finite state space with $|{\mathcal{S}}|=S$; $\mathcal{A}$ is the finite action space with $|\mathcal{A}|=A$; $\mathcal{P}=\left\{P_{h}\right\}_{h=1}^{H}$ is the sequence of transition probability matrix, meaning $\forall h\in[H]$, $P_{h}:{\mathcal{S}}\times\mathcal{A}\mapsto\Delta({\mathcal{S}})$ and $P_{h}(\cdot|s,a)$ specifies the state distribution in step $h+1$ if action $a$ is taken from state $s$ at step $h$; $\mathcal{R}=\left\{R_{h}\right\}_{h=1}^{H}$ is the sequence of bounded stochastic reward function, meaning $\forall h\in[H]$, $R_{h}(s,a)$ is the stochastic reward bounded in $[0,1]$ associated with taking action $a$ in state $s$ at step $h$; $H$ is the time horizon; $\mu_{1}$ is the initial state distribution. For simplicity, we assume $\mu_{1}$ is deterministic, and has probability mass $1$ on state $s_{1}$.

Within each episode, the MDP starts at state $s_{1}$. At each step $h$, the agent observes current state $s_{h}$ and take an action $a_{h}$ and receives a stochastic reward $R_{h}(s_{h},a_{h})$. After that, the MDP transits to a next state $s_{h+1}$, which is drawn from $P_{h}(\cdot|s,a)$. The episode terminates after the agent takes action $a_{H}$ in state $s_{H}$ and receives reward $R_{H}(s_{H},a_{H})$ at step $H$.

A policy $\pi$ is a sequence of functions $\left\{\pi_{1},\ldots,\pi_{H}\right\}$, each maps from state space ${\mathcal{S}}$ to action space $\mathcal{A}$. The value function $V_{h}^{\pi}:{\mathcal{S}}\mapsto[0,H-h+1]$, is the expected sum of future rewards by taking action according policy $\pi$, i.e. $V_{h}^{\pi}(s):=\mathbb{E}\left[\left.\sum_{t=h}^{H}R_{t}(s_{t},\pi_{t}(s_{t}))\right|s_{h}=s\right],$ where the expectation is w.r.t. to the stochasticity of state transition and reward in the MDP. Similarly, we define the state-action value function $Q_{h}^{\pi}:{\mathcal{S}}\times\mathcal{A}\mapsto[0,H-1+1]$: $Q_{h}^{\pi}(s,a):=\mathbb{E}\left[R_{h}(s,a)\right]+\mathbb{E}\left[\left.\sum_{t=h+1}^{H}R_{t}(s_{t},\pi_{t}(s_{t}))\right|s_{h}=s,a_{h}=a\right]$ Let $\pi^{*}=\left\{\pi^{h}\right\}$ be an optimal policy and let $V_{h}^{*}(s):=V_{h}^{\pi^{*}}(s,a)$, $Q_{h}^{*}(s):=Q_{h}^{\pi^{*}}(s,a)$, $\forall h,s,a$.

For any $f:{\mathcal{S}}\mapsto[0,H]$, We define the Bellman operator by: $\left(\mathbb{B}_{h}f\right)(s,a)=\mathbb{E}\left[R_{h}(s,a)\right]+\mathbb{E}_{s^{\prime}\sim P_{h}(\cdot|s,a)}[f(s^{\prime})]$ Then the Bellman equation is given by:

The Bellman optimality equation is given by:

We define the state distribution at step $h$ by following policy $\pi$ as $d_{h}^{\pi}(s):=P_{h}^{\pi}(s_{h}=s)$, and the state trajectory distribution of $\pi$ as: $d^{\pi}:=\left\{d_{h}^{\pi}\right\}_{h=1}^{H}$. The goal is to find a policy that maximizes the reward, i.e. find a $\hat{\pi}$, s.t. $V_{1}^{\hat{\pi}}(s_{1})=V_{1}^{*}(s_{1})=\max_{\pi}V_{1}^{\pi}(s_{1})$. To measure the performance of our RL algorithms, we use suboptimality as our performance metric for offline setting and use regret as our performance metric for online setting. We formalize these two measures in their corresponding sections below.

In the online setting, we assume that a central server and $m$ agents aim to collaboratively minimizing their total regrets. The agents and server collaborate by following a communication protocol to decide when to synchronize and what information to communicate. Unlike standard distributed RL setting, we assume $\alpha$ fraction of the agents are Byzantine:

Because the server has no control over the bad agents, we only seek to minimize the error incurred by the good agents. Formally, we use regret as our performance measure for the online RL algorithm:

where $\pi_{k}^{j}$ is the policy used by agent $j$ in episode $k$. At the same time , because of the distributed nature of our problem, we want to synchronize between the servers and agents only if it is necessary to reduce the communication cost.

Based on these considerations, we propose the Byzan-UCBVI algorithm (Algorithm 2). We highlight the following key features of Byzan-UCBVI:

1. 1.

   Low-switching-cost style algorithm design: the server will check the synchronization criteria in Line 6 when receiving requests from agents. Each good agent will request synchronization if and only if any of their own $(s,a,h)$ counts doubles (Line 21). Importantly, our agents do not need to know other agents’ $(s,a,h)$ counts to decide if synchronization is necessary. This design choice reduces the number of policy switches, synchronization rounds and communication cost all from $O(T)$ to $O(\log T)$. Compared to the $O(\sqrt{T})$ communication steps in [Jadbabaie et al., 2022], ours is much lower. Unlike [Dubey and Pentland, 2021], our agents do not need to know other agents’ transition counts in order to decide whether to synchronize or not.

2. 2.

   Homogeneous policy execution: In any episode $k$, our algorithm ensures that all good agents are running the same policy $\pi_{k}$. This ensures that the robust mean estimation achieves the smallest estimation error. Recall that the samples in the large batches are wasted if the batch sizes are severely imbalanced (cf. Section 3).

3. 3.

   Robust UCBVI updates: During synchronization, the central server performs policy update using a variant of the UCBVI algorithm [Azar et al., 2017]: for $h=H,H-1,\ldots,1$, compute:

   	$\displaystyle\bar{Q}_{h}(\cdot,\cdot)=\left(\hat{\mathbb{B}}_{h}\hat{V}_{h+1}\right)(\cdot,\cdot)+\Gamma_{h}(\cdot,\cdot),\quad\hat{Q}_{h}(\cdot,\cdot)=\min\left\{\bar{Q}_{h}(\cdot,\cdot),H-h+1\right\}^{+}$		(5)
   	$\displaystyle\hat{\pi}_{h}(\cdot)=\mathop{\mathrm{argmax}}_{a}\hat{Q}_{h}(\cdot,a),\quad\hat{V}_{h}(\cdot)=\max_{a}\hat{Q}_{h}(\cdot,a)$		(6)

   We replace the empirical mean estimation with our Pert-Weighted-Clique (PWC) algorithm (Algorithm 4) and design a new confidence bonus accordingly. Instead of estimating the transition matrix and reward function, we directly estimate the Bellman operator given an estimated value function $\hat{V}_{h+1}$. The server gathers the sufficient statistics from agents in Line 13.

We are now ready to present the following regret bound for Byzan-UCBVI.

In the offline setting, we assume the server has access to a set of data batches while some data batches are corrupted. The goal of the server is to find a nearly optimal policy without further interaction with the environment. Specifically:

The performance is measured by the suboptimality w.r.t. a deterministic comparator policy $\tilde{\pi}$ (not necessarily an optimal policy):

In the offline setting, the server cannot interact with the MDP. So our result relies heavily on the quality of the dataset. As we will see in the analysis, the suboptimality gap (8) can be upper bounded by the estimation error of Bellman operator along the trajectory of $\tilde{\pi}$. As a result, we do not need full coverage over the whole state-action space. Instead, we only need the offline dataset to have proper coverage over $\{d_{h}^{\tilde{\pi}}\}_{h=1}^{H}$, the state distribution of policy $\tilde{\pi}$ at each step $h$. To characterize the data coverage, for any $s,a,h$, we define the counts on $(s,a,h)$ tuples by:

When calling Algorithm 1, the large data batches might be clipped in Line 4. By definition, the clipping threshold is bounded between: $N_{h}^{\mathcal{G},{\operatorname{cut}}_{1}}(s,a)$, the $(\alpha m+1)$-th largest of $\left\{N_{h}^{j}(s,a)\right\}_{j\in\mathcal{G}}$ and $N_{h}^{\mathcal{G},{\operatorname{cut}}_{2}}(s,a)$, the $(2\alpha m+1)$-th largest of $\left\{N_{h}^{j}(s,a)\right\}_{j\in\mathcal{G}}$. We define three quantities $p^{\mathcal{G},0},\kappa,\kappa_{\text{even}}$ to characterize the quality of the offline dataset. The first quantity describes the density of $\tilde{\pi}$ trajectory that are not properly covered by the offline dataset:

Recall that Algorithm 1 requires there are at least $(2\alpha m+1)$ non-empty data batches to make an informed decision. $p^{\mathcal{G},0}$ measures an upper bound on the total probability under $d^{\tilde{\pi}}$ to encounter an $(s,h,a)$ on which Weighted-Clique cannot return a good mean estimator.

We now introduce $\kappa$, the density ratio between the $d^{\tilde{\pi}}$ and the empirical distribution of the uncorrupted offline dataset. $\kappa$ quantifies the portion of useful data in the whole dataset and is commonly used in the offline RL literature [Rashidinejad et al., 2021, Zhang et al., 2021a]. We only focus on the $(s,a,h)$ tuples excluded by $p^{\mathcal{G},0}$ in Definition 6.2:

As we can see in Theorem 3.2, the accuracy of Algorithm 1 heavily depend on the evenness of the batches. Even if there are some good batches with a large amount of data, those extra data are not useful (cf. Remark 3.6). We define the following quantity to measure the information loss in the clipping step (Line 4 in Algorithm 1):

Intuitively, $\kappa_{\text{even}}$ describes the evenness of good agent coverage. It measures both how many data in large batches are cut off by the clip step and the unevenness of the batches after clipping. We includes $N_{h}^{\mathcal{G},{\operatorname{cut}}_{1}}(s,\tilde{\pi}_{h}(s))$ and $N_{h}^{\mathcal{G},{\operatorname{cut}}_{2}}(s,\tilde{\pi}_{h}(s))$, instead of the true clipping threshold, meaning $\kappa_{\text{even}}$ serves as an upper bound of the actual unevenness resulting from running the algorithm. For example, suppose $\alpha m>1$: if for any $s,a,h,j$, $N_{h}^{j}(s,a)=n$, then $\kappa_{\text{even}}=1$; if for any $s,a,h$, there is one good data batch with size $Lm$ for some $L>1$ while the others have size $1$, then $N_{h}^{\mathcal{G},{\operatorname{cut}}_{1}}(s,a)=N_{h}^{\mathcal{G},{\operatorname{cut}}_{2}}(s,a)=1$ and $\kappa_{\text{even}}=\frac{Lm+(1-\alpha)m-1}{(1-\alpha)m}\frac{(1-\alpha)m}{(1-\alpha)m}\approx L+1$, meaning $\kappa_{\text{even}}$ increases as the batches become less even.

Remarkably, all three quantities defined above only depend on the $(s,a,h)$ counts of the good data batches.

Given the above setup, we now present our second algorithm, Byzan-PEVI, a Byzantine-Robust variant of pessimistic value iteration [Jin et al., 2021]. Similar to the online setting, we use our Weighted-Clique (without perturbation) algorithm to approximate the Bellman operator and use the estimation error to design PESSIMISTIC bonus for the value iteration. Byzan-PEVI (Algorithm 3) runs pessimistic value iteration ((14)-(15)) and calls Weighted-Clique as a subroutine to robustly estimate the Bellman operator using offline dataset $D$:

To summarize, in this work, we first present Weighted-Clique, a robust mean estimation algorithm for learning from uneven batches that can be of independent interest. Building upon Weighted-Clique, we propose byzantine-robust online (Byzan-UCBVI) and the first byzantine-robust offline (Byzan-PEVI) reinforcement learning algorithms in distributed setting. Several questions remain open: (1) Can we provide a complete characterization of the information-theoretical lower bound for robust mean estimation from uneven batches? (2) Can we extend our RL algorithms to the function approximation setting?