Abstract

We consider a distributed reinforcement learning setting where multiple agents separately explore the environment and communicate their experiences through a central server. However, \(\alpha\)-fraction of agents are adversarial and can report arbitrary fake information. Critically, these adversarial agents can collude and their fake data can be of any sizes. We desire to robustly identify a near-optimal policy for the underlying Markov decision process in the presence of these adversarial agents. Our main technical contribution is Weighted-Clique, a novel algorithm for the robust mean estimation from batches problem, that can handle arbitrary batch sizes. Building upon this new estimator, in the offline setting, we design a Byzantine-robust distributed pessimistic value iteration algorithm; in the online setting, we design a Byzantine-robust distributed optimistic value iteration algorithm. Both algorithms obtain near-optimal sample complexities and achieve superior robustness guarantee than prior works.

1 Introduction↩︎

Distributed learning systems have been one of the main driving force to recent successes of deep learning [1]–[3]. Advances in designing efficient distributed optimization algorithms[4] and deep learning infrastructures [5] have enables training powerful models with hundreds of billions of parameters [6]. However, with the outsourcing of computation and data collection, new challenges emerges. In particular, distributed system has been found vulnerable to Byzantine failure [7], 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 [8]–[10], which raise security concern in real world applications such as chatbot [11] and autonomous vehicles [12], [13]. In addition, other desired properties are chased after, such as protecting data privacy of individual data contributors [14], [15] and and reducing communication cost[16]. 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 [17], power grids optimization [18], automatic traffic control [19]. 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:

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 [8], [20]–[22], our algorithm adapts to arbitrary batch sizes, which is desired in many applications of interests.
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 [23]–[25], and preserves data privacy of individual agents.
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 [26].

2.0.0.1 Reinforcement learning:

Reinforcement learning studies the optimal strategy in a Markov Decision Process (MDP) [27]. [28], [29] show that UCB style algorithm achieves minimax regret bound in tabular MDPs. Recent work extend the theoretical understanding to RL with function approximation [30], [31]. [32], [33] use pessimistic strategy to efficiently learn a nearly optimal policy in offline setting. Recently, [23]–[25] study low switching cost RL algorithm, meaning the learning agent has small budget for policy changes.

2.0.0.2 Distributed reinforcement learning:

Parallel RL deploys large-scale models in distributed system [34]. [4], [5] provide distributed architecture for deep reinforcement learning by parallelizing the data generating process. [16], [35], [36] provide the first sets of theoretical guarantee for performance and communication cost in parallel RL.

2.0.0.3 Robust statistics:

Robust statistics has a long history [37], [38], which studies learning with corrupted dataset. In modern machine learning, models are high dimensional. Recent work provide sample and computationally efficient algorithms for robust mean and covariance estimation in high dimension [39], [40]. Shortly after, those robust mean estimators are applied to robust supervised learning [41], [42] and RL [26], [43].

2.0.0.4 Robust learning from batches:

Another line of work studies robust learning from batches [8], [20]–[22]. A collection of data is generated from data sources while a fraction of the data sources are corrupted. By exploiting the batch structure of the data, these algorithms achieve significantly high accuracy than non-batch setting [39]. To our best knowledge, all of these work study batches with equal size. Our paper is the first that generalizes to the setting where the batch size varies. Similarly, these works all assume the same batch sizes from each agent, which may not be true in many crowd-sourcing applications.

2.0.0.5 Byzantine-robust distributed learning:

Byzantine-Robust learning algorithm studies learning under Byzantine failure [7]. [44] provides a Byzantine gradient descent via geometric median of mean estimation for the gradients. [8] provides robust distributed gradient descent algorithms with optimal statistics rates.

2.0.0.6 Corruption robust RL and Byzantine-robust RL:

There is a line of work studying adversarial attack against reinforcement learning [9], [10], [45], and corruption robust reinforcement RL for online [43], [46] and offline [26] settings. [47] studies Byzantine-Robust linear bandits in federated setting. Unlike our setting, they allow different agents to be subject to Byzantine attack in different episodes. Our algorithm enjoys a better regret bound and communication cost. [48] provides a Byzantine-robust policy gradient algorithm that is guaranteed to converge to an approximate stationary point while we focus the regret of the algorithm. [49] studies Byzantine-Robust multi-armed bandit, where the corruption can only come from a fixed distribution. We study a more difficult MDP setting and allow the corruption to be arbitrary.

3 Robust Mean Estimation from Untruthful Batches↩︎

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 1 (Robust mean estimation from batches). There are \(m\) data providers indexed by: \(\{1, 2, \ldots, m\} =: [m]\). Among these providers, we denote the indexes of uncorrupted providers by \(\Gcal\) and the indexes of corrupted providers by \(\Bcal\), where \(\Bcal \cup \Gcal = [m]\), \(\Bcal \cap \Gcal = \emptyset\), \(\left|\Bcal\right| = \alpha m\). Any uncorrupted providers has access to a sub-Gaussian distribution \(\Dcal\) with mean \(\mu\) and variance proxy \(\sigma^2\) (i.e. \(\EE_{X\sim \mathcal{D}}[X] = \mu\) and \(\EE_{X \sim \mathcal{D}}\left[\exp\left(s \left(X - \mu\right)\right)\right] \le \exp\left({\sigma^2 s^2}/{2}\right)\), \(\forall s \in \RR.\)). For each \(j \in [m]\), a data batch \(\left\{x_j^i\right\}_{i=1}^{n_j}\) is sent to the learner, where \(n_j\) can be arbitrary. For \(j\in\Gcal\), \(\left\{x_j^i\right\}_{i=1}^{n_j}\) are i.i.d. samples drawn from \(\Dcal\); for \(j \in \Bcal\), \(\left\{x_j^i\right\}_{i=1}^{n_j}\) can be arbitrary.

considers a robust learning problem from batches where we allow arbitarily different batch sizes. In contrast, prior works [20]–[22] have only studied the setting with (roughly) equal batch sizes, which is much more restricted. For this problem, we propose the Weighted-Clique algorithm (). 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 () 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 . Next, a set confidence intervals for the true mean \(\mu\) is constructed in based on the data of each batch, where \(I_j = \RR\) 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 , finds a cluster of good data batches and drops extreme batches. We show that achieves the following guarantee.

Theorem 1. Under , if \(\ncut > 0\), \(\alpha < \frac{1}{2}\), with probability at least \(1-\delta\), \(\hat{x}\) returned by satisfies: \[\begin{align} \left|\hat{x} - \mu\right| \le & \frac{2}{\sqrt{\sum_{j \in [m]}\tilde{n}_j}} \sigma\sqrt{2\log\frac{2}{\delta}} + \frac{8\alpha m\sqrt{\ncut}}{\sum_{j \in [m]}\tilde{n}_j} \sigma\sqrt{2\log\frac{2m}{\delta}} \label{eq:err32bound} \end{align}\qquad{(1)}\] where \(\ncut\) and \(\tilde{n}_j\)’s are defined in and in .

A number of immediate remarks are in order.

Note that comparing to prior works [20]–[22], we allow arbitrary batch sizes. Even if some agents report \(n_j = 0\), as long as \(\ncut >0\), i.e. there are at least \(2\alpha m + 1\) agents reporting non-zero \(n_j\)’s, our estimator will have a well-behaved error bound. This means that the breakdown point (in the sense of fraction of bad agent) of our algorithm is \(\frac{1}{2}\), which is optimal.

When \(n_1 = \cdots = n_m=n\), the right hand side of becomes \(O\left(\frac{\sigma}{\sqrt{n}}\left(\frac{1}{\sqrt{m}} + \alpha\sqrt{\log m}\right)\right).\) This recovers the rate in [8], which is optimal (up to logarithmic factors).

In classical robust mean estimation setting [37], [50], the optimal error rate is \(O\left(\sigma\left(\alpha + \frac{1}{\sqrt{m}}\right)\right)\) given \(m\) total samples and \(\alpha\) faction corrupted samples. In contrast, due to having data source ID, i.e. the batch indices, the adversary are much restricted. To see this, notice that the equal batch setting can be viewed as robust mean estimation from \(m\) data points \(\hat{x}_j\)’s. When the batch size \(n\) becomes larger, \(\hat{x}_j\) has a smaller variance \(\frac{\sigma^2}{{n}}\) and thus the error of robust mean estimation becomes \(O\left(\frac{\sigma}{\sqrt{n}}\left(\alpha + \frac{1}{\sqrt{m}}\right)\right)\), which matches the above rate (up to logarithmic factors).

Our bound in does not depend on the largest \(2\alpha m\) \(n_j\)’s. This means even if some of the clean agents have infinite samples, the algorithm cannot get a very low error. This might look not ideal at first glance, but we show that this is inevitable information-theoretically. Interested readers are referred to .

When the good data batch is subject to point-wise perturbation of magnitude at most \(\epsilon\), a variant of ( Pert-Weighted-Clique, see ) suffers at most a \(2\epsilon\) term in the error upper bound in addition to . does not need the exact dataset as input, but only the empirical mean and batch sizes of each data batch. As we see later, this property is essential to achieve low communication cost and preserve data privacy.

4 Byzantine-Robust Learning in Parallel MDP↩︎

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 and .

In both online and offline settings, we consider a finite horizon episodic tabular Markov Decision Process (MDP) \(\Mcal = \left(\Scal, \Acal, \Pcal, \Rcal, H, \mu_1\right)\). Where \(\Scal\) is the finite state space with \(|\Scal|=S\); \(\Acal\) is the finite action space with \(|\Acal|=A\); \(\Pcal = \left\{P_h\right\}_{h=1}^H\) is the sequence of transition probability matrix, meaning \(\forall h \in [H]\), \(P_h: \Scal \times \Acal \mapsto \Delta(\Scal)\) 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\); \(\Rcal = \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 \(\Scal\) to action space \(\Acal\). The value function \(V_h^{\pi}: \Scal \mapsto [0, H-h+1]\), is the expected sum of future rewards by taking action according policy \(\pi\), i.e. \(V_h^{\pi}(s) := \EE\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}:\Scal\times\Acal \mapsto [0, H-1+1]\): \(Q_h^{\pi}(s,a):= \EE\left[R_h(s,a)\right] + \EE\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:\Scal \mapsto [0,H]\), We define the Bellman operator by: \(\left(\Bell_h f\right)(s,a) = \EE\left[R_h(s,a)\right] + \EE_{s' \sim P_h(\cdot | s,a)}[f(s')]\) Then the Bellman equation is given by: \[V_h^{\pi}(s) = Q_h^{\pi}(s,\pi_h(s)), \quad Q_h^{\pi}(s,a) = \left(\Bell_h V_{h+1}^{\pi}\right)(s,a), \quad V_{H+1}^{\pi}(s) = 0\] The Bellman optimality equation is given by: \[V_h^{*}(s) = \max_{a \in \Acal}Q_h^{*}(s,a), \quad Q_h^{*}(s,a) = \left(\Bell_h V_{h+1}^{*}\right)(s,a), \quad V_{H+1}^{*}(s) = 0\] 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.

5 Byzantine-Robust Online RL↩︎

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:

Definition 2 (Distributed online RL with Byzantine corruption). There are \(m\) agents consists of two types:

\((1-\alpha)m\) good agents, denoted by \(\Gcal\): Each of the good agents interacts with a copy of \(\Mcal\) and communicates its observations to the server following the interaction protocol;
\(\alpha m\) bad agents, denoted by \(\Bcal\): The bad agents is allowed to send arbitrary observations to the server at the end of each episode.

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: \[\operatorname{Regret}(K) = \sum_{k=1}^K \sum_{j\in\mathcal{G}} \left(V_1^*(s_1) - V_1^{\pi_k^j }(s_1)\right),\] 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 (). We highlight the following key features of Byzan-UCBVI:

Low-switching-cost style algorithm design: the server will check the synchronization criteria in when receiving requests from agents. Each good agent will request synchronization if and only if any of their own \((s,a,h)\) counts doubles (). 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 [47], ours is much lower. Unlike [16], our agents do not need to know other agents’ transition counts in order to decide whether to synchronize or not.
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. ).
Robust UCBVI updates: During synchronization, the central server performs policy update using a variant of the UCBVI algorithm [28]: for \(h = H, H-1, \ldots, 1\), compute: \[\begin{align} &\bar Q_h(\cdot, \cdot) = \left(\hat{\Bell}_h \hat{V}_{h+1}\right)(\cdot, \cdot) + \Gamma_h(\cdot,\cdot)\tag{1}, \quad \hat{Q}_h(\cdot, \cdot) = \min\left\{\bar Q_{h}(\cdot,\cdot), H-h+1\right\}^+\\ &\hat{\pi}_h(\cdot) = \argmax_{a} \hat{Q}_h(\cdot, a), \quad \hat{V}_h(\cdot) = \max_{a} \hat{Q}_h(\cdot, a) \tag{2} \end{align}\] We replace the empirical mean estimation with our Pert-Weighted-Clique (PWC) algorithm () 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 .

Figure 2: \mathrm{\small Byzan-UCBVI}\left(K, \delta,\alpha\right) — Figure 2: \(\mathrm{\small Byzan-UCBVI}\left(K, \delta,\alpha\right)\)

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

Theorem 2 (Regret bound). Under , if \(\alpha \le \frac{1}{3}\left(1-\frac{1}{m}\right)\), for all \(\delta < \frac{1}{4}\), with probability at least \(1-3\delta\), the total regret of is at most \[\sum_{k=1}^K \sum_{j \in \mathcal{G}}\left(V_1^*(s_1) - V_1^{\hat{\pi}_k^j}(s_1)\right) = \tilde{O}\left( (1 + \alpha \sqrt{m})H^2S\sqrt{AmK\log (1/\delta)} \right)\]

In , the good agents are using the same policy and thus for all \(j \in \Gcal\), \(\hat{\pi}_k^j = \hat{\pi}_k\), where \(\hat{\pi}_k\) is the policy calculated by the server in \(k\)-th episode. By utilizing the batch structure, achieves a regret sublinear in \(K\), even under Byzantine attacks. Our regret is only \(O(\sqrt{mK}+\alpha {m}\sqrt{K}))\) compared to the \(O(m\sqrt{K} + m\alpha^{1/4}K^{3/4})\) regret in [47]. When \(\alpha\leq 1/\sqrt{m}\), the dominating term \(\sqrt{mK}\) is optimal even in the clean setting [28].

Because each agent runs \(K\) episodes in total, count of each of the \((s,a,h)\) tuples doubles at most \(\lfloor\log_2 K\rfloor\) times during training. Thus each good agent will send at most \(SAH\lfloor\log_2 K\rfloor\) sync requests. The bad agents can only send logarithmic number of effective request because of the checking step in . As a result, there will be at most \(mSAH\lfloor\log_2 K\rfloor\) synchronization episodes in total. The communication inside one synchronization episode includes the following: at least one agent sends a sync request; inside the value iteration, the server will send estimated value functions at \(H\) steps to each agents; each of the good agents will send the estimated Bellman operator for each \((s,a)\) pairs at \(H\) steps and the counts to server. Importantly, the agents only need to send summary statistics, instead of the raw dataset to server, this preserves the data privacy of individual agents [14], [15].

Switching cost measures the number of policy changes. Algorithms with low switching cost is favorable in real world applications [23]–[25]. only performs policy updates in the synchronization episodes, its switching cost is thus at most \(mSAH\lfloor\log_2 K\rfloor\).

6 Byzantine-Robust Offline RL↩︎

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:

Definition 3 (Distributed offline RL with Byzantine corruption). The server has access to an offline data set with \(m\) data batches \(\bigcup_{j \in [m]}D_j\), including \((1-\alpha) m\) good batches \(\Gcal\) and \(\alpha m\) bad batches \(\Bcal\), where \(D_j := \bigcup_{h \in [H]}D_j^h := \bigcup_{h \in [H]} \left\{\left(s_h^{j,k}, a_h^{j,k}, r_h^{j,k},{s_h^{\prime}}^{j, k}\right)\right\}_{k=1}^{K_j}\). We make an assumption on the data generating process similar to [51]. Precisely, for all \(j\in\Gcal\), \(D_j\) is drawn from an unknown distribution \(\left\{\nu^j_h\right\}_{h=1}^H\), where for each \(h \in [H]\), \(\nu_h^j \in \Delta\left(\Scal \times \Acal\right)\). For all \(h,j,k\), \(\left(s_h^{j,k}, a_h^{j,k}\right) \sim \nu_h^j\), \({s_h^{\prime}}^{j,k} \sim P_h(\cdot |s_h^{j,k}, a_h^{j,k})\) and \(r_h^{j,k}\) is an instantiation of \(R_h\left(s_h^{j,k}, a_h^{j,k}\right)\). For any \(j \in \Bcal\) (i.e. bad batches), \(D_j\) can be arbitrary.

The performance is measured by the suboptimality w.r.t. a deterministic comparator policy \(\tilde{\pi}\) (not necessarily an optimal policy): \[\label{eq:sub-opt} \subopt\left(\pi, \tilde{\pi}\right) := V_1^{\tilde{\pi}}(s_1) - V_1^{\pi}(s_1).\tag{3}\] 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 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: \[N_h^j(s,a) := \sum_{k \in [K_j]}\one\left\{(s_h^{j,k}, a_h^{j,k}) = (s, a)\right\}, \quad \forall j \in [m].\] When calling , the large data batches might be clipped in . By definition, the clipping threshold is bounded between: \(N_h^{\Gcal, \cut_1}(s,a)\), the \((\alpha m+1)\)-th largest of \(\left\{N_h^j(s,a)\right\}_{j\in\Gcal}\) and \(N_h^{\Gcal, \cut_2}(s,a)\), the \((2\alpha m+1)\)-th largest of \(\left\{N_h^j(s,a)\right\}_{j\in\Gcal}\). We define three quantities \(p^{\Gcal,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:

Definition 4 (Measure of insufficient coverage). We define \(p^{\Gcal,0}\) as the probability of \(\tilde{\pi}\) visiting an \((s,h,a)\) tuple that is insufficiently covered by the logged data, namely \[p^{\Gcal,0} := \sum_{h=1}^H \EE_{d_h^{\tilde{\pi}}} \left[\one\left\{ N_h^{\Gcal, \cut_2}(s,\tilde{\pi}(s)) =0 \right\}\right]\]

Recall that requires there are at least \((2\alpha m + 1)\) non-empty data batches to make an informed decision. \(p^{\Gcal,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 [26], [33]. We only focus on the \((s,a,h)\) tuples excluded by \(p^{\Gcal,0}\) in :

Definition 5 (density ratio). We use \(\left\{\Ccal_h\right\}_{h=1}^H\) to denote the state space (in the support of \(\left\{d_h^{\tilde{\pi}}\right\}_{h=1}^H\)) that have proper clean agents coverage: \[\Ccal_h = \left\{s | N_h^{\Gcal, \cut_2}(s,\tilde{\pi}(s)) >0\right\}\]

We use \(\kappa\) to denote the density ratio between the state distribution of policy \(\tilde{\pi}\) and the empirical distribution over the uncorrupted offline dataset: \[\kappa := \max_{h\in[H]}\max_{s\in\Ccal_h} \frac{d_h^{\tilde{\pi}}(s)}{\sum_{j \in \Gcal} N_h^j(s, \tilde{\pi}_h(s)) / \sum_{j\in\Gcal}K_j}\]

As we can see in , the accuracy of 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. ). We define the following quantity to measure the information loss in the clipping step ( in ):

Definition 6 (Unevenness of good agents coverage). \[\kappa_{\text{even}} := \max_{h\in[H]}\max_{s\in\Ccal_h} \frac{{\sum_{j \in \Gcal}N_h^j(s, \tilde{\pi}_h(s))}}{\sum_{j\in\Gcal} \tilde{N}_h^{j,\cut_2}(s, \tilde{\pi}_h(s))} \frac{m(1-\alpha) N_h^{\Gcal, \cut_1}(s,\tilde{\pi}_h(s))}{\sum_{j\in\Gcal} \tilde{N}_h^{j,\cut_2}(s, \tilde{\pi}_h(s))}\] where \(\tilde{N}_h^{j,\cut_2}(s, \tilde{\pi}_h(s)) = \max\left(N_h^{\Gcal, \cut_2}(s,\tilde{\pi}_h(s)), N_h^j(s, \tilde{\pi}_h(s))\right)\)

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^{\Gcal, \cut_1}(s,\tilde{\pi}_h(s))\) and \(N_h^{\Gcal, \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 \(L m\) for some \(L > 1\) while the others have size \(1\), then \(N_h^{\Gcal, \cut_1}(s,a) = N_h^{\Gcal, \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 [32]. 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 () runs pessimistic value iteration (-) and calls Weighted-Clique as a subroutine to robustly estimate the Bellman operator using offline dataset \(D\): \[\begin{align} &\bar Q_h(\cdot, \cdot) = \left(\hat{\Bell}_h \hat{V}_{h+1}\right)(\cdot, \cdot) - \Gamma_h(\cdot,\cdot)\tag{4} , \quad \hat{Q}_h(\cdot, \cdot) = \min\left\{\bar Q_{h}(\cdot,\cdot), H-h+1\right\}^+\\ &\hat{\pi}_h(\cdot) = \argmax_{a} \hat{Q}_h(\cdot, a), \quad \hat{V}_h(\cdot) = \max_{a} \hat{Q}_h(\cdot, a) \tag{5} \end{align}\]

Theorem 3. Given any deterministic comparator policy \(\tilde{\pi}\), under , , and : for any \(\delta\), \(\alpha < \frac{1}{3}\), with probability at least \(1-\delta\), outputs a policy \(\hat{\pi}\) with: \[\begin{align} \subopt\left(\hat{\pi}, \tilde{\pi}\right) \le& 2H p^{\Gcal,0} + O\left(\sqrt{\kappa\kappa_{\text{even}}}H^2\sqrt{|\Scal|} \frac{1+\sqrt{m}\alpha}{\sqrt{\sum_{j\in\Gcal}K_j}} \sqrt{\log\frac{H|\Scal||\Acal|m}{\delta}} \right). \end{align}\]

Compared to [26], there is no non-diminishing term in the bound. Meaning the suboptimality gap vanishes as the good agents collect more data. To the best of our knowledge, this is the first result for Byzantine-robust offline RL.

Our offline RL results are more involved and notation heavy due to the nature of the problem. In the offline RL setting, learner has no control over the data generating process, and each data source can be arbitrarily different. The agent can only passively rely on the robust mean estimator we designed and the pessimism principle to learn as well as the data permits. In contrast, in the online setting, the learner has complete control over the clean agents’ data collection process. Our algorithm Byzan-UCBVI enables the server to realize its full potential and obtain a tighter and cleaner sample complexity guarantee.

7 Conclusion↩︎

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?

8 More discussion on :Weighted-Clique ↩︎

8.1 Impossible result↩︎

Theorem 4 (impossibility result). There exists a distribution \(\Dcal\), s.t. given \(m\) data batches \(\left\{\left\{x_j^i\right\}_{i=1}^{n_j}\right\}_{j\in[m]}\) generated under , every robust mean estimation algorithm \(\mathscr{A}\) suffers an error at least \[\Omega\left(\frac{1}{\sqrt{N}}\right)\] even \(\mathscr{A}\) knows some of the batches are clean, where \(N\) is the sum of sizes of the smallest \((1-2\alpha)m\) good batches.

Proof of . Let \(\Dcal\) be Bernoulli distribution with parameter \(\frac{1}{2}\). W.l.o.g., assume \(\Gcal = [(1-\alpha)m]\), \(n_1\le \cdots \le n_{(1-\alpha)m}\) and \(\Bcal = \left\{(1-\alpha)m+1, \ldots, m\right\}\). We assume algorithm \(\mathscr{A}\) knows \([(1-2\alpha)m]\) is a subset of the good batches.

Let \(\eta = \frac{1}{2\sqrt{N}} = \frac{1}{2\sqrt{\sum_{j=1}^{(1-2\alpha)m}n_j}}\). Let the bad batches \(\Bcal\) be i.i.d. samples from \(\Dcal'\), a Bernoulli distribution with parameter \(\frac{1}{2} + \eta\). By Theorem 4 of [52], [53], no algorithm can distinguish if the batches \(\left\{x_1^i\right\}_{i=1}^{n_1},\ldots, \left\{x_{(1-2\alpha)m}^i\right\}_{i=1}^{n_{(1-2\alpha)m}}\) are sampled from \(\Dcal\) or \(\Dcal'\). I.e. no algorithm can distinguish if \(\left\{(1-2\alpha)m+1, \ldots, (1-\alpha)m\right\}\) are good batches or \(\Bcal\) are good batches. This means, given \(m\) data batches \(\left\{\left\{x_j^i\right\}_{i=1}^{n_j}\right\}_{j\in[m]}\), every robust mean estimation algorithm suffers an error at least \(\Omega\left(\frac{1}{\sqrt{N}}\right)\). ◻

8.2 Adaption to good batch perturbation and distributed learning↩︎

Compared to , enlarges the confidence interval by \(\epsilon\) on both endpoints due to the perturbation and only requires some sufficient statistics from the batches, instead of the whole dataset. When \(\ncut >0\), meaning there are at least \(2\alpha m + 1\) non-empty batches, runs a modified Weighted-Clique algorithm to calculate the mean estimation and the error upper bound (with an additional \(\epsilon\) as an adjustment for \(\epsilon\)-cover argument in the proof of ). When \(\ncut =0\), returns \(0\) and a trivial error upper bound.

9 Proof of↩︎

To prove , we show holds under some concentration event while the event happens with high probability. We consider a slight more general setting where there could be perturbations to even good batches:

Definition 7 (Robust mean estimation from batches). There are \(m\) data providers indexed by: \(\{1, 2, \ldots, m\} =: [m]\). Among these providers, we denote the indexes of uncorrupted providers by \(\Gcal\) and the indexes of corrupted providers by \(\Bcal\), where \(\Bcal \cup \Gcal = [m]\), \(\Bcal \cap \Gcal = \emptyset\), \(\left|\Bcal\right| = \alpha m\). Any uncorrupted providers has access to perturbed samples from a sub-Gaussian distribution \(\Dcal\) with mean \(\mu\) and variance proxy \(\sigma^2\) (i.e. \(\EE_{X\sim \mathcal{D}}[X] = \mu\) and \(\EE_{X \sim \mathcal{D}}\left[\exp\left(s \left(X - \mu\right)\right)\right] \le \exp\left({\sigma^2 s^2}/{2}\right)\), \(\forall s \in \RR.\)). For each \(j \in \Gcal\), a data batch \(\left\{\tilde{x}_j^i\right\}_{i=1}^{n_j}\) is drawn from \(\Dcal\), while a perturbed version \(\left\{ x_j^i\right\}_{i=1}^{n_j}\) is sent to the learner, where \(n_j\) can be arbitrary and \(\left|\hat{x}_j^i - \tilde{x}_j^i\right| \le \epsilon\) for some \(\epsilon \ge 0\). For \(j \in \Bcal\), \(\left\{x_j^i\right\}_{i=1}^{n_j}\) can be arbitrary.

One can easily recover by letting \(\epsilon = 0\). We prove the We first define the concentration event as following:

Definition 8 (Concentration event). For all \(j \in \Gcal\), define the event that the empirical mean of clean batches is close to the population mean as: \[\Ecal_j := \left\{\left|\hat{x}_j - \mu\right| \le \frac{\sigma}{\sqrt{\tilde{n}_j}}\sqrt{2\log \frac{2m}{\delta}} + \epsilon \right\}\] Define the event that the weighted average of empirical means of clean batches is close to the population mean as: \[\Ecal_{{wa}} := \left\{ \left|\frac{1}{\sum_{j \in \Gcal}\tilde{n}_j}\sum_{j \in \Gcal}\tilde{n}_j \hat{x}_j - \mu\right| \le \frac{\sigma}{\sqrt{\sum_{j \in \Gcal}\tilde{n}_{j}}}\sqrt{2\log\frac{2}{\delta}} + \epsilon \right\}\] Let \(\Ecal_{{conc}}\) be the event that events above happens together: \[\Ecal_{{conc}} := \Ecal_{wa} \cap \bigcap_{j\in\Gcal}\Ecal_j\]

We can show \(\Ecal_{{conc}}\) happens with high probability using Hoeffding’s inequality:

Lemma 1. \(\PP\left(\Ecal_{conc}\right) \ge 1- 2\delta\).

Proof. See proof in . ◻

Under event \(\Ecal_{conc}\), we can give an upper bound on the estimation error:

Lemma 2. Under event \(\Ecal_{conc}\), if \(n^\cut > 0\), outputs a \(\hat{x}\) with \[\label{eq:pert32bd325eps} \left| \hat{x}- \mu \right| \le \frac{2}{\sqrt{\sum_{j \in [m]}\tilde{n}_j}} \sigma\sqrt{2\log\frac{2}{\delta}} + \frac{8\alpha m\sqrt{\ncut}}{\sum_{j \in [m]}\tilde{n}_j} \sigma\sqrt{2\log\frac{2m}{\delta}} + 5\epsilon\qquad{(2)}\]

Proof. See proof in . ◻

Proof of . Consider \(\epsilon = 0\), i.e. no perturbation involved. By and , with probability at least \(1-2\delta\), \[\left| \hat{x}- \mu \right| \le \frac{2}{\sqrt{\sum_{j \in [m]}\tilde{n}_j}} \sigma\sqrt{2\log\frac{2}{\delta}} + \frac{8\alpha m\sqrt{\ncut}}{\sum_{j \in [m]}\tilde{n}_j} \sigma\sqrt{2\log\frac{2m}{\delta}}\] ◻

9.1 Proof of↩︎

To prove ,

we first show that the perturbation changes the empirical mean of batches by at most \(\epsilon\);
we can show the concentration bound of empirical means and weighted means for the unperturbed samples;
we can conclude by using the two results above and triangular inequality.

9.1.0.1 the probability of event \(\bigcap_{j\in{\Gcal}}\Ecal_{j}\):

For all \(j \in \Gcal\), let \(\bar x_j\) be the empirical mean of unperturbed samples in batch \(j\): \[\bar x_j := \frac{1}{n_j}\sum_{i=1}^{n_j} \tilde{x}_j^i\] By triangular inequality: \[\begin{align} \label{eq:pert32mean} \left|\bar x_j - \hat{x}_j\right| = \left|\frac{1}{n_j}\sum_{i=1}^{n_j} (x_j^i - \tilde{x}_j^i)\right| \le \frac{1}{n_j}\sum_{i=1}^{n_j}\epsilon = \epsilon \end{align}\tag{6}\]

Since \(\mathcal{D}\) is sub-Gaussian distribution, we can show the concentration of unperturbed samples \(\bar x_j\): for all good batch \(j \in \Gcal\), \[\PP\left(\left|\bar x_j - \mu\right| > t\right) \le 2\exp\left(-\frac{n_j t^2}{2\sigma^2}\right) \le 2\exp\left(-\frac{\tilde{n}_j t^2}{2\sigma^2}\right)\] By union bound, with probability at least \(1-\delta\), \(\forall j \in \Gcal\), \[\left|\bar x_j - \mu\right| \le \frac{\sigma}{\sqrt{\tilde{n}_j}}\sqrt{2\log\frac{2\left|\Gcal\right|}{\delta}} \le \frac{\sigma}{\sqrt{\tilde{n}_j}}\sqrt{2\log\frac{2m}{\delta}}\] By triangular inequality, with probability at least \(1-\delta\), \(\forall j \in \Gcal\), \[\left|\hat{x}_j - \mu\right| \le \left|\hat{x}_j - \bar x_j\right| + \left|\bar x_j - \mu\right| \le \frac{\sigma}{\sqrt{\tilde{n}_j}}\sqrt{2\log\frac{2m}{\delta}} + \epsilon\] I.e. \(\PP\left(\bigcap_{j\in\Gcal}\Ecal_{j}\right) \ge 1-\delta\).

9.1.0.2 the probability of event \(\Ecal_{wa}\):

We first show the weighted average of empirical mean of the unperturbed sample i.e., \(\frac{1}{\sum_{j' \in \Gcal}\tilde{n}_{j'}}\sum_{j \in \Gcal}\tilde{n}_{j} \bar x_j\) is a sub-Gaussian random variable: firstly, note that the mean of the weighted average is \(\mu\), i.e. \(\EE\left[\frac{1}{\sum_{j' \in \Gcal}\tilde{n}_{j'}}\sum_{j \in \Gcal}\tilde{n}_{j} \bar x_j\right] = \mu\). By definition, we know for good batch \(j \in \Gcal\), \(\tilde{x}_j^1, \ldots, \tilde{x}_j^{n_j}\) are i.i.d. sub-Gaussian random variable with mean \(\mu\) and variance proxy \(\sigma^2\), i.e. \[\EE\left[\exp\left(s \left(\tilde{x}_j^i - \mu\right)\right)\right] \le \exp\left(\frac{\sigma^2 s^2}{2}\right) \quad \forall s \in \RR.\] Since \(\bar x_j = \frac{1}{n_j}\sum_{i=1}^{n_j}\tilde{x}_j^i\): for all \(s \in \RR\), \[\begin{align} &\EE\left[\exp\left(s \left(\frac{1}{\sum_{j' \in \Gcal}\tilde{n}_{j'}}\sum_{j \in \Gcal}\tilde{n}_j \bar x_j - \mu\right)\right)\right] = \prod_{j \in \Gcal} \EE\left[\exp\left(s \left(\frac{1}{\sum_{j' \in \Gcal}\tilde{n}_{j'}}\tilde{n}_j (\bar x_j - \mu)\right)\right)\right] \\ = & \prod_{j \in \Gcal} \prod_{i \in [n_j]} \EE\left[\exp\left(\frac{s}{\sum_{j' \in \Gcal}\tilde{n}_{j'}}\frac{\tilde{n}_j}{n_j} (\tilde{x}_j^i - \mu)\right)\right] \le \prod_{j \in \Gcal} \prod_{i \in [n_j]} \exp\left(\frac{\sigma^2}{2}\left(\frac{s}{\sum_{j' \in \Gcal}\tilde{n}_{j'}}\frac{\tilde{n}_j}{n_j} \right)^2\right) \\ \le & \prod_{i \in \Gcal} \prod_{i \in [n_j]} \exp\left(\frac{\sigma^2}{2}\left(\frac{s}{\sum_{j' \in \Gcal}\tilde{n}_{j'}} \right)^2\right) = \exp\left(\frac{s^2}{2}\left(\frac{\sigma}{\sqrt{\sum_{j' \in \Gcal}\tilde{n}_{j'}}}\right)^2 \right) \end{align}\] This means \(\frac{1}{\sum_{j' \in \Gcal}\tilde{n}_{j'}}\sum_{j' \in \Gcal}\tilde{n}_{j'} \bar x_j\) is a sub-Gaussian random variable with variance proxy \(\frac{\sigma^2}{\sum_{j' \in \Gcal}\tilde{n}_{j'}}\). Thus \(\forall t > 0\), \[\PP\left(\left|\frac{1}{\sum_{j' \in \Gcal}\tilde{n}_{j'}}\sum_{j \in \Gcal}\tilde{n}_{j} \bar x_j - \mu\right| > t \right) \le 2\exp\left(-\frac{\sum_{j' \in \Gcal}\tilde{n}_{j'}t^2}{2\sigma^2}\right)\] Thus with probability at least \(1-\delta\): \[\left|\frac{1}{\sum_{j' \in \Gcal}\tilde{n}_{j'}}\sum_{j \in \Gcal}\tilde{n}_{j} \bar x_j - \mu\right| \le \frac{\sigma}{\sqrt{\sum_{j' \in \Gcal}\tilde{n}_{j'}}}\sqrt{2\log\frac{2}{\delta}}\] This means: \[\begin{align} \label{eq:clean95bound32purt} &\left|\frac{1}{\sum_{j' \in \Gcal}\tilde{n}_{j'}}\sum_{j \in \Gcal}\tilde{n}_{j} \hat{x}_j - \mu\right|\\ \le & \left|\frac{1}{\sum_{j' \in \Gcal}\tilde{n}_{j'}}\sum_{j \in \Gcal}\tilde{n}_{j} \bar x_j - \mu\right| + \left|\frac{1}{\sum_{j' \in \Gcal}\tilde{n}_{j'}}\sum_{j \in \Gcal}\tilde{n}_{j} \bar x_j - \frac{1}{\sum_{j' \in \Gcal}\tilde{n}_{j'}}\sum_{j \in \Gcal}\tilde{n}_{j} \hat{x}_j\right|\\ \le &\frac{\sigma}{\sqrt{\sum_{j' \in \Gcal}\tilde{n}_{j'}}}\sqrt{2\log\frac{2}{\delta}} + \epsilon \end{align}\tag{7}\] I.e. \(\PP\left(\Ecal_{wa}\right) \ge 1-\delta\).

By union bound \(\PP\left(\Ecal_{conc}\right) = \PP\left(\Ecal_{wa} \cap \bigcap_{j\in\Gcal}\Ecal_j\right)\ge 1- 2\delta\).

9.2 Proof of↩︎

By , we know the weighted average of empirical mean of good batches is a proper estimation for the population mean. Compared to \(\Gcal\), the \(U^*\) returned in in may remove some good batches and include some bad batches. Even though, as long as we can show:

will not remove too many good batches and will not include too many bad batches;
the bad batches included in \(U^*\) will not be significant

then we can show that the \(\hat{x}\) returned in is a reasonable estimation for \(\mu\).

9.2.0.1 The structure of \(U^*\):

\(U^*\) is the largest subset of batches with confidence interval intersection. The confidence intervals of all the good batches intersect under event \(\bigcap_{j\in\Gcal}\Ecal_{j}\), thus \(U^*\) should at least as large as \(\Gcal\), thus it is not possible to remove too many good batches. Furthermore, we can also show that we will not lose too much information, meaning significantly reduce the total number of samples and thus later on, we can show that the statistical rate will not be affected by too much. We make these ideas precise below.

Under event \(\bigcap_{j\in\Gcal}\Ecal_{j}\), \[\mu \in \bigcap_{j\in\Gcal}I_j,\] where \(I_j\) is the confidence interval defined in . Thus \(\bigcap_{j\in\Gcal}I_j \neq \emptyset\).

Because \(U^*\) maximizes \[\max_{Us.t.\emptyset\neq\bigcap_{j \in U}I_j }|U|,\] we know \(|U^*| \ge |\Gcal| = (1-\alpha)m\). Furthermore, \(U^*\) can include at most \(\alpha m\) batches, this means \(U^*\) includes at least \((1-2\alpha m)\) good batches. Formally: \[|U^* \cap \Gcal| = |U^* \setminus\Bcal| \ge |U^*| - |\Bcal| \ge (1-2\alpha )m.\]

Now we show \(U^*\) is not losing too much information, i.e. \(\sum_{j\in U^*} \tilde{n}_j \ge \frac{1}{2}\sum_{j \in [m]} \tilde{n}_j\). By definition of \(\ncut\), there are at least \(2 \alpha m + 1\) batches in \([m]\) such that \(\tilde{n}_j = \ncut\). Because \(U^*\) removes at more \(\alpha m\) batches, there are at least \(\alpha m + 1\) batches in \(U^*\) such that \(\tilde{n}_j = \ncut\). I.e. \[\begin{align} \left|\left\{j \in U^* :\tilde{n}_j = \ncut\right\}\right| = &\left|\left\{j \in [m] :\tilde{n}_j = \ncut\right\}\right| - \left|\left\{j \in [m]\setminus U^* :\tilde{n}_j = \ncut\right\}\right|\\ \ge & \left|\left\{j \in [m] :\tilde{n}_j = \ncut\right\}\right| - \left|[m]\setminus U^*\right| \\ \ge & 2\alpha m + 1 - \alpha m = \alpha m + 1 \label{eq:ncut32in32U32star} \end{align}\tag{8}\] This means the information loss \(\sum_{j \in [m]\setminus \Gcal} \tilde{n}_j\) can be bounded by \(\sum_{j \in U^*} \tilde{n}_j\), formally: \[\begin{align} 2\sum_{j\in U^*} \tilde{n}_j - \sum_{j \in [m] } \tilde{n}_j= & \sum_{j \in U^*}\tilde{n}_j + \sum_{j \in U^* }\tilde{n}_j - \sum_{j \in [m]\cap U^*}\tilde{n}_j - \sum_{j \in [m]\setminus U^*}\tilde{n}_j \\ = & \sum_{j \in U^*}\tilde{n}_j - \sum_{j \in [m]\setminus U^*}\tilde{n}_j \ge (\alpha m +1)\ncut - \alpha m \ncut \ge 0 \end{align}\] Thus we have: \[\label{eq:sm32info32loss} \sum_{j\in U^*} \tilde{n}_j \ge \frac{1}{2}\sum_{j \in [m]} \tilde{n}_j.\tag{9}\]

9.2.0.2 Bad batches in \(U^*\):

In order for a bad batch \(i\) to survive in \(U^*\), its confidence interval \(I_i\) must intersect with each good batches’ confidence interval in \(U^*\). In particular, \(I_i\) must intersect with the good batch in \(U^*\) with largest \(\tilde{n}_j\). By definition, there are at least \(\alpha m + 1\) good batches with \(\tilde{n}_j = \ncut\). Because \(U^*\) excludes at most \(\alpha m\) good batches, there are at least one good batch (denote by \(j^*\)), s.t. \(\tilde{n}_{j^*} = \ncut\).

Thus \(\forall j \in U^* \cap \Bcal\), \(I_i \cap I_{j^*} \neq \emptyset\). Which means, there exists some point \(x\), s.t. \(x \in I_i \cap I_{j^*}\), thus \[\begin{align} &\left|\hat{x}_i - \hat{x}_{j^*}\right| \le \left|\hat{x}_i - x\right| + \left|x-\hat{x}_{j^*}\right|\\ \le & \frac{\sigma}{\sqrt{\tilde{n}_i}}\sqrt{2\log \frac{2m}{\delta}} + \epsilon + \frac{\sigma}{\sqrt{\tilde{n}_{j^*}}}\sqrt{2\log \frac{2m}{\delta}} + \epsilon\\ =& \left(\frac{1}{\sqrt{\tilde{n}_i}} + \frac{1}{\sqrt{\ncut}}\right) \sigma \sqrt{2\log \frac{2m}{\delta}} + 2\epsilon. \end{align}\] Furthermore, under event \(\bigcap_{j\in\Gcal}\Ecal_{j}\), \[\left|\hat{x}_{j^*}-\mu\right| \le \frac{\sigma}{\sqrt{\ncut}}\sqrt{2\log \frac{2m}{\delta}} + \epsilon\] By triangular inequality, \(\hat{x}_i\) we not bee too far away from \(\mu\): \[\label{eq:bd32bc32bd} \left|\hat{x}_i - \mu\right| \le \left|\hat{x}_i - \hat{x}_{j^*}\right| + \left|\hat{x}_{j^*} - \mu\right| = \left(\frac{1}{\sqrt{\tilde{n}_i}} + \frac{2}{\sqrt{\ncut}}\right) \sigma \sqrt{2\log \frac{2m}{\delta}} + 3\epsilon\tag{10}\]

9.2.0.3 Error decomposition:

As mentioned earlier, we can decompose the estimation of \(\hat{x}\) returned by by: statistical error (with potential information loss), term \(\mathscr{A}_1\) in ; error coming from including bad batches, term \(\mathscr{A}_2\) in ; error coming from removing good batches, term \(\mathscr{A}_3\) in . Specifically: \[\begin{align} &\left|\hat{x} - \mu\right| = \frac{1}{\sum_{j \in U^*}\tilde{n}_j}\left|\sum_{j \in U^*} \tilde{n}_j (\hat{x}_j - \mu)\right|\\ = &\frac{1}{\sum_{j \in U^*}\tilde{n}_j}\left|\left(\sum_{j \in \Gcal} + \sum_{j \in U^*\cap \mathcal{B}} - \sum_{j \in \Gcal\setminus U^*}\right) \tilde{n}_j (\hat{x}_j - \mu)\right| \\ \le & \frac{1}{\sum_{j \in U^*}\tilde{n}_j} \left(\left|\sum_{j \in \Gcal} \tilde{n}_j (\hat{x}_j - \mu)\right| + \left|\sum_{j \in U^*\cap \mathcal{B}} \tilde{n}_j (\hat{x}_j - \mu)\right| + \left|\sum_{j \in \Gcal\setminus U^*} \tilde{n}_j (\hat{x}_j - \mu)\right|\right) \\ &(this is by triangular inequality)\\ =: & \mathscr{A}_1 + \mathscr{A}_2 + \mathscr{A}_3 \label{eq:est32err32decom} \end{align}\tag{11}\] We can bound the first term \(\mathscr{A}_1\) by under event \(\Ecal_{wa}\): \[\begin{align} \mathscr{A}_1 = & \frac{1}{\sum_{j \in U^*}\tilde{n}_j} \left|\sum_{j \in \Gcal} \tilde{n}_j (\hat{x}_j - \mu)\right| = \frac{\sum_{j \in \Gcal}\tilde{n}_j}{\sum_{j \in U^*}\tilde{n}_j} \left|\frac{1}{\sum_{j \in \Gcal}\tilde{n}_j}\sum_{j \in \Gcal} \tilde{n}_j (\hat{x}_j - \mu)\right| \\ = &\frac{\sum_{j \in \Gcal}\tilde{n}_j}{\sum_{j \in U^*}\tilde{n}_j} \left|\frac{1}{\sum_{j \in \Gcal}\tilde{n}_j}\sum_{j \in \Gcal} \tilde{n}_j \hat{x}_j - \mu\right|\\ \le& \frac{\sum_{j \in \Gcal}\tilde{n}_j}{\sum_{j \in U^*}\tilde{n}_j} \left(\frac{\sigma}{\sqrt{\sum_{j \in \Gcal}\tilde{n}_{j}}}\sqrt{2\log\frac{2}{\delta}} + \epsilon \right) \quad \left(By event \Ecal_{wa}\right) \\ =& \frac{\sqrt{\sum_{j \in \Gcal}\tilde{n}_j}}{\sum_{j \in U^*}\tilde{n}_j} {\sigma}\sqrt{2\log\frac{2}{\delta}} + \frac{\sum_{j \in \Gcal}\tilde{n}_j}{\sum_{j \in U^*}\tilde{n}_j}\epsilon \\ \le& 2\frac{\sqrt{\sum_{j \in \Gcal}\tilde{n}_j}}{\sum_{j \in [m]}\tilde{n}_j} {\sigma}\sqrt{2\log\frac{2}{\delta}} + \frac{\sum_{j \in \Gcal}\tilde{n}_j}{\sum_{j \in U^*}\tilde{n}_j}\epsilon \quad \left(By \pref{eq:sm32info32loss}\right) \\ \le& 2\frac{\sqrt{\sum_{j \in [m]}\tilde{n}_j}}{\sum_{j \in [m]}\tilde{n}_j} {\sigma}\sqrt{2\log\frac{2}{\delta}} + \frac{\sum_{j \in \Gcal}\tilde{n}_j}{\sum_{j \in U^*}\tilde{n}_j}\epsilon \quad \left(By \Gcal \subseteq [m]\right) \\ = & \frac{2}{\sqrt{\sum_{j \in [m]}\tilde{n}_j}} {\sigma}\sqrt{2\log\frac{2}{\delta}} + \frac{\sum_{j \in \Gcal}\tilde{n}_j}{\sum_{j \in U^*}\tilde{n}_j}\epsilon \end{align}\] By , we can bound the second term \(\mathscr{A}_2\) by: \[\begin{align} \mathscr{A}_2 & = \frac{1}{\sum_{j \in U^*}\tilde{n}_j} \left|\sum_{j \in U^*\cap \mathcal{B}} \tilde{n}_j (\hat{x}_j - \mu)\right| \le \frac{1}{\sum_{j \in U^*}\tilde{n}_j} \sum_{j \in U^*\cap \mathcal{B}} \tilde{n}_j\left| \hat{x}_j - \mu\right| \quad \left(By triangular ineq\right)\\ \le &\frac{1}{\sum_{j \in U^*}\tilde{n}_j} \sum_{j \in U^*\cap \mathcal{B}} \tilde{n}_j \left(\left(\frac{1}{\sqrt{\tilde{n}_j}} + \frac{2}{\sqrt{\ncut}}\right) \sigma \sqrt{2\log \frac{2m}{\delta}} + 3\epsilon\right) \quad \left(By \pref{eq:bd32bc32bd}\right)\\ \le &\frac{1}{\sum_{j \in U^*}\tilde{n}_j} \sum_{j \in U^*\cap \mathcal{B}} \left({\sqrt{\tilde{n}_j}} + \frac{2\tilde{n}_j}{\sqrt{\ncut}}\right) \sigma \sqrt{2\log \frac{2m}{\delta}} + \frac{\sum_{j \in U^*\cap \mathcal{B}} \tilde{n}_j}{\sum_{j \in U^*}\tilde{n}_j} 3\epsilon \\ \le &\frac{1}{\sum_{j \in U^*}\tilde{n}_j} \sum_{j \in U^*\cap \mathcal{B}} 3{\sqrt{\ncut}} \sigma \sqrt{2\log \frac{2m}{\delta}} + \frac{\sum_{j \in U^*\cap \mathcal{B}} \tilde{n}_j}{\sum_{j \in U^*}\tilde{n}_j} 3\epsilon \quad \left(By \tilde{n}_j \le \ncut\right)\\ \le &\frac{3\alpha m{\sqrt{\ncut}}}{\sum_{j \in U^*}\tilde{n}_j} \sigma \sqrt{2\log \frac{2m}{\delta}} + \frac{\sum_{j \in U^*\cap \mathcal{B}} \tilde{n}_j}{\sum_{j \in U^*}\tilde{n}_j} 3\epsilon \quad \left(U^* includes at most \alpha m bad batches\right) \end{align}\]

We can bound the third term \(\mathscr{A}_3\) by: \[\begin{align} \mathscr{A}_3 = & \frac{1}{\sum_{j \in U^*}\tilde{n}_j} \left|\sum_{j \in \Gcal\setminus U^*} \tilde{n}_j (\hat{x}_j - \mu)\right| \le \frac{1}{\sum_{j \in U^*}\tilde{n}_j} \sum_{j \in \Gcal\setminus U^*} \tilde{n}_j\left|\hat{x}_j - \mu\right| \quad \left(By triangular ineq\right)\\ \le & \frac{1}{\sum_{j \in U^*}\tilde{n}_j} \sum_{j \in \Gcal\setminus U^*} \tilde{n}_j \left(\frac{\sigma}{\sqrt{\tilde{n}_j}}\sqrt{2\log \frac{2m}{\delta}} + \epsilon\right) \quad \left(By event \bigcap_{j\in\Gcal}\Ecal_j\right)\\ = & \frac{1}{\sum_{j \in U^*}\tilde{n}_j} \sum_{j \in \Gcal\setminus U^*} {\sigma}{\sqrt{\tilde{n}_j}}\sqrt{2\log \frac{2m}{\delta}} + \frac{\sum_{j \in \Gcal\setminus U^*}\tilde{n}_j}{\sum_{j \in U^*}\tilde{n}_j} \epsilon \\ \le & \frac{\alpha m {\sqrt{\ncut}}}{\sum_{j \in U^*}\tilde{n}_j} {\sigma}\sqrt{2\log \frac{2m}{\delta}} + \frac{\sum_{j \in \Gcal\setminus U^*}\tilde{n}_j}{\sum_{j \in U^*}\tilde{n}_j} \epsilon\\ & \left(Because U^* excludes at most \alpha m good batches and \tilde{n}_j \le \ncut\right) \end{align}\] Note that the above upper bounds for \(\mathscr{A}_2\) and \(\mathscr{A}_3\) are still valid even if some of the \(\tilde{n}_j\)’s are zero.

In conclusion, we can bound the estimation error by: \[\begin{align} \left|\hat{x} - \mu\right| \le & \mathscr{A}_1 + \mathscr{A}_2 + \mathscr{A}_3 \\ \le & \left(\frac{2}{\sqrt{\sum_{j \in [m]}\tilde{n}_j}} {\sigma}\sqrt{2\log\frac{2}{\delta}} + \frac{\sum_{j \in \Gcal}\tilde{n}_j}{\sum_{j \in U^*}\tilde{n}_j}\epsilon\right) \\ &+ \left(\frac{3\alpha m{\sqrt{\ncut}}}{\sum_{j \in U^*}\tilde{n}_j} \sigma \sqrt{2\log \frac{2m}{\delta}} + \frac{\sum_{j \in U^*\cap \mathcal{B}} \tilde{n}_j}{\sum_{j \in U^*}\tilde{n}_j} 3\epsilon \right)\\ &+ \left(\frac{\alpha m {\sqrt{\ncut}}}{\sum_{j \in U^*}\tilde{n}_j} {\sigma}\sqrt{2\log \frac{2m}{\delta}} + \frac{\sum_{j \in \Gcal\setminus U^*}\tilde{n}_j}{\sum_{j \in U^*}\tilde{n}_j} \epsilon\right)\\ = & \frac{2}{\sqrt{\sum_{j \in [m]}\tilde{n}_j}} {\sigma}\sqrt{2\log\frac{2}{\delta}} + \frac{4\alpha m{\sqrt{\ncut}}}{\sum_{j \in U^*}\tilde{n}_j} \sigma \sqrt{2\log \frac{2m}{\delta}} \\ & + \frac{\left(\sum_{j \in \Gcal}+\sum_{j \in U^*\cap \Bcal}\right)\tilde{n}_j}{\sum_{j \in U^*}\tilde{n}_j}\epsilon + \frac{\sum_{j \in U^*\cap \mathcal{B}} \tilde{n}_j}{\sum_{j \in U^*}\tilde{n}_j} 2\epsilon + \frac{\sum_{j \in \Gcal\setminus U^*}\tilde{n}_j}{\sum_{j \in U^*}\tilde{n}_j} \epsilon\\ \le & \frac{2}{\sqrt{\sum_{j \in [m]}\tilde{n}_j}} {\sigma}\sqrt{2\log\frac{2}{\delta}} + \frac{4\alpha m{\sqrt{\ncut}}}{\sum_{j \in U^*}\tilde{n}_j} \sigma \sqrt{2\log \frac{2m}{\delta}} \\ & + \frac{\sum_{j \in [m]}\tilde{n}_j}{\sum_{j \in U^*}\tilde{n}_j}\epsilon + \frac{\alpha m \ncut}{\sum_{j \in U^*}\tilde{n}_j} 2\epsilon + \frac{\alpha m \ncut}{\sum_{j \in U^*}\tilde{n}_j} \epsilon \\ &\left(By \Gcal \cup \left(U^*\cap\Bcal\right) \subseteq [m], |U^*\cap \Bcal|\le \alpha m, |\Gcal \setminus U^*|\le \alpha m\right)\\ \le & \frac{2}{\sqrt{\sum_{j \in [m]}\tilde{n}_j}} {\sigma}\sqrt{2\log\frac{2}{\delta}} + \frac{8\alpha m{\sqrt{\ncut}}}{\sum_{j \in [m]}\tilde{n}_j} \sigma \sqrt{2\log \frac{2m}{\delta}} + 5\epsilon \\ & \left(By \pref{eq:ncut32in32U32star} and \pref{eq:sm32info32loss}\right) \end{align}\]

10 Proof of↩︎

By following standard regret decomposition for UCB type of algorithm (see [30]), under the event that the estimation error of Bellman operator is bounded by bonus terms, we can decompose the regret by:

the cumulative bonus term occurred in the trajectories of each good agent
a term that can be easier bounded by Azuma-Hoeffding’s inequalities.

By and replacing with a variant for martingale, we can show the event mentioned above happens with high probability. Unlike standard regret bound for tabular setting, we cannot directly use the telescope series to estimate the cumulative bonuses. Instead, we first need to show that because each good agent is using the same policy in every episode, their trajectories have a lot of overlaps, meaning the \((s,a,h)\) counts of all good agents do not differ by too much. Given that, we can simply the bound in and use the telescope series.

We start by restating :

Theorem 5 (Regret bound, ). If \(\alpha \le \frac{1}{3}\left(1-\frac{1}{m}\right)\), for all \(\delta<\frac{1}{4}\), with probability at least \(1-3\delta\): \[\sum_{k=1}^K \sum_{j \in \mathcal{G}}\left(V_1^*(s_1) - V_1^{\hat{\pi}^k}(s_1)\right) = \tilde{O}\left( (1 + \alpha \sqrt{m})SH^2\sqrt{AKm\log \frac{1}{\delta}} \right)\]

We first give the high level idea of our proof:

We give an analysis under the intersection of three “good events”:
- event \(\mathcal{E}\): the estimation error of Bellman operator is upper-bounded by bonus (See , );
- event \(\mathcal{E}_{even}\): if the total count \(\sum_{j\in\mathcal{G}}N_h^{j,k}(s,a,h)\) on some \((s,a,h)\) is large, then the counts of each agent differ by at most \(2\) times (See , );
- event \(\mathcal{E}_{Azmua}\): an error term in the regret decomposition is bounded by Azmua-Hoeffding bound.
Under event \(\mathcal{E}\), we can decompose the regret into two terms (see , ):
- a martingale with bounded difference which is controlled by Hoeffding bound under event \(\mathcal{E}_{Azmua}\);
- the cumulative bonus term, which can be bounded by telescoping series under event \(\mathcal{E}_{even}\).

We use \(\bar Q_h^k\), \(\hat{Q}_h^k\), \(\hat{\pi}_h^k\), \(\hat{V}_h^k\), \(\hat{\Bell}_h^k\), \(\Gamma_h^k\) to denote the variables used in the \(k\)-th episode. When a synchronization happens in episode \(k\), those variables are the updated ones after the synchronization; when there is no synchronization in episode \(k\), those variables remain the same as last episode. Let \(N_h^{j,k}(s,a)\) be the counts on \((s,a,h)\) tuples in episode \(k\) after the counts update. Formally, We start by restating the data collection process and counts on \((s,a,h)\) tuples of each good agent \(j \in \mathcal{G}\): during the data collection process, we allow all of the agents collect data together. In the \(k\)-th episode, agent \(j\) collects a multi-set of transition tuples using policy \(d^{\hat{\pi}^k}\): \(\left\{\left(s_{h}^{j,k}, a_{h}^{j,k}, r_{h}^{j,k}, s_{h+1}^{j,k}\right)\right\}_{h \in [H]}\). \[D_{j,k} := \bigcup_{h \in [H]}D_{j,k}^h :=\bigcup_{h \in [H]}\bigcup_{k' \le k}\left\{\left(s_{h}^{j,k'}, a_{h}^{j,k'}, r_{h}^{j,k'}, s_{h+1}^{j,k'}\right)\right\}\] \(N_h^{j,k}(s,a)\) is given by: \[N_h^{j,k}(s,a) = \sum_{h = 1}^H\sum_{(\tilde{s}, \tilde{a}, \tilde{r},\tilde{s}') \in D_{j,k}^h} \mathbf{1}\left\{(s,a) = (\tilde{s}, \tilde{a})\right\}\] We give the formal definition of good events below:

Definition 9. \[\begin{align} \mathcal{E}_{Azmua} := & \left\{\sum_{k=1}^K \sum_{j \in \mathcal{G}}\sum_{h=1}^H\left(\EE_{s'\sim P_h(\cdot \mid s_h^{j,k},a_h^{j,k})}\left[\hat{V}_{h+1}^k (s') - V_{h+1}^{\hat{\pi}^k}(s')\right] \right.\right.\\ & \left.\left. - \left(\hat{V}_{h+1}^k (s_{h+1}^{j,k}) - V_{h+1}^{\hat{\pi}^k}(s_{h+1}^{j,k})\right)\right) \le \sqrt{8mKH^3\log\frac{2}{\delta}} \right\} \end{align}\] \[\mathcal{E} := \left\{ \bigcap_{(s,a,h,k,f) \in \mathcal{S} \times \mathcal{A} \times H \times K \times [0,1]^{\mathcal{S}}} \left\{\left| \left(\hat{\Bell}_h^k f\right)(s,a) - \left(\Bell_h f\right)(s,a) \right| \le \Gamma_h^k(s,a)\right\} \right\}\] For any \((s,a,h,k) \in \mathcal{S}\times\mathcal{A}\times [H] \times [K]\), we define the follow event: \[\mathcal{E}_{even}(s,a, h, k) := \left\{if \sum_{j\in \mathcal{G}} N_h^{j,k}(s,a) \ge 400 m\log \frac{2 mKSAH}{\delta} , then \max_{i,j \in \mathcal{G}}\frac{N_h^{j,k}(s,a)}{N_h^{i,k}(s,a)} \le 2\right\}\] And define \[\mathcal{E}_{even} := \bigcap_{s,a,h,K} \mathcal{E}_{even}(s,a, h, k).\]

Proof of . By Azuma-Hoeffding inequality: \[\begin{align} &\PP\left(\overline{\mathcal{E}_{Azmua}}\right) \le \delta \end{align}\] Then by union bound: and together implies for all \(0 < \delta < \frac{1}{4}\): \[\begin{align} \PP\left(\overline{\mathcal{E}} \cup \overline{\mathcal{E}_{even}} \cup \overline{\mathcal{E}_{Azmua}}\right) \le \PP\left(\overline{\mathcal{E}}\right) + \PP\left(\overline{\mathcal{E}_{even}}\right) + \PP\left(\overline{\mathcal{E}_{Azmua}}\right) \le 3\delta \end{align}\] which means \(\mathcal{E} \cap \mathcal{E}_{even} \cap \mathcal{E}_{Azmua}\) happens with probability at least \(1- 3\delta\).

We now upper bound the regret under event \(\mathcal{E} \cap \mathcal{E}_{even}\cap \mathcal{E}_{Azmua}\). By we can decompose the regret by: \[\begin{align} &\sum_{k=1}^K \sum_{j \in \mathcal{G}}\left(V_1^*(s_1) - V_1^{\hat{\pi}^k}(s_1)\right) \\ \le & 2\sum_{k=1}^K \sum_{j \in \mathcal{G}}\sum_{h=1}^H\Gamma_h^k(s_h^{j,k},a_h^{j,k}) \\ &+ \sum_{k=1}^K \sum_{j \in \mathcal{G}}\sum_{h=1}^H\left(\EE_{s'\sim P_h(\cdot \mid s_h^k,a_h^k)}\left[\hat{V}_{h+1}^k (s') - V_{h+1}^{\hat{\pi}^k}(s')\right] - \left(\hat{V}_{h+1}^k (s_{h+1}^{j,k}) - V_{h+1}^{\hat{\pi}^k}(s_{h+1}^{j,k})\right)\right) \\ & \left(Under event \mathcal{E}\right)\\ \le & 2\sum_{k=1}^K \sum_{j \in \mathcal{G}}\sum_{h=1}^H\Gamma_h^k(s_h^{j,k},a_h^{j,k}) + \sqrt{8mKH^3\log\frac{2}{\delta}} \\ & \left(Under event \mathcal{E}_{Azmua}\right) \end{align}\] We only need to upper bound the cumulative bonus. Suppose the policy is updated at the beginning of \(k_0+1, k_1+1, k_2+1, \ldots, k_l+1\)-th episodes, with the data collected in the first \(k_0, k_1, k_2, \ldots, k_l\)-th episodes, with \(k_1 =1\). To simplify the notation, we define \(k_{0} = 0\), \(k_{l+1} = K\).

For convenience, in the following, we use \(N_h^k(s,a)\) to denote the total count on \((s,a,h)\) tuples up to episode \(k\) over all good agents: \[N_h^k(s,a) := \sum_{j \in \mathcal{G}}N_h^{j,k}(s,a),\] where \(N_h^0(s,a) = 0\). We can rearrange the cumulative bonus by summing over \((s,a)\) pairs: \[\begin{align} \label{eq:bonus32sum} \sum_{k=1}^K \sum_{j \in \mathcal{G}} \sum_{h=1}^H\Gamma_h^k(s_h^{j,k},a_h^{j,k}) = \sum_{h=1}^H\sum_{(s,a) \in \mathcal{S} \times \mathcal{A}} \sum_{t = 1}^{l+1}\Gamma_h^{k_{t-1}+1}(s, a) \left( N_h^{k_t}(s,a) - N_h^{k_{t-1}}(s,a) \right) \end{align}\tag{12}\] When there are less than \((2\alpha m+1)\) agents have coverage on some \((s,a,h)\) tuple, the bonus term \(\Gamma_h^k(s,a)\) is trivially set to be \(H-h+1\). In the following, we show that under event \(\mathcal{E}_{even}\), in , for each \((s,a,h)\) tuple, there are at most \(2N_0\) bonus term such that \(\Gamma_h(s,a) = H-h+1\), where \[N_0 := 400m\log \frac{2 mKSAH}{\delta}.\] For any \((s,a,h)\), let \(l_0(s,a,h)\) be such that: \[N_h^{k_{l_0(s,a,h)-1}}(s,a) < N_0 \le N_h^{k_{l_0(s,a,h)}}(s,a).\] This means when running the policy update at episode \(k_{l_0(s,a,h)} + 1\), the total counts for \((s,a,h)\), i.e. \(N_h^{k_{l_0(s,a,h)}}(s,a)\), is larger than \(N_0\). For any \(k \ge k_{l_0(s,a,h)}\), we have \[\sum_{j\in\mathcal{G}}N_h^{j,k}(s,a) = N_h^{k}(s,a) \ge N_h^{k_{l_0(s,a,h)}}(s,a) \ge N_0.\] By definition of \(\mathcal{E}_{even}\), for any \(k \ge k_{l_0(s,a,h)}\) \[\max_{i,j \in \mathcal{G}}\frac{N_h^{j,k}(s,a)}{N_h^{i,k}(s,a)} \le 2\] this means for any \(k \ge k_{l_0(s,a,h)}\), \(N_h^{j,k}(s,a) > 0, \forall j \in \mathcal{\mathcal{G}}\), meaning all of the good agents have coverage on \((s,a,h)\), this means there are at least \((1-\alpha)m \ge 2\alpha m +1\) agents have coverage, and thus:

Trivial bonus can only happens at \(k \le k_{l_0(s,a,h)}\), i.e. \[\label{eq:bad32bonus} \Gamma_h^k(s,a) = H-h+1only ifk \le k_{l_0(s,a,h)}.\tag{13}\] Furthermore, because in the algorithm, the agents synchronize and update their policy when or before any \((s,a,h)\) counts for a good agent doubles. I.e.: for all \((s,a,h,j,i) \in \mathcal{S} \times \mathcal{A} \times [H] \times \mathcal{G} \times [l]\): \[\label{eq:at32most32double} N_h^{k_{t}}(s,a) \le 2N_h^{k_{t-1}}(s,a)\tag{14}\] This means \[\label{eq:at32most322N0} N_h^{k_{l_0(s,a,h)}}(s,a) \le 2N_h^{k_{l_0(s,a,h)-1}}(s,a) < 2N_0.\tag{15}\] Thus for each \((s,a,h)\) tuple, there are at most \(2N_0\) bonus term such that \(\Gamma_h(s,a) = H-h+1\).
for any \(k \ge k_{l_0(s,a,h)}+1\) \[\begin{align} \Gamma_h^k(s,a) = & \frac{6}{SAHKm}+ \frac{2(H-h+1)}{\sqrt{\sum_{j \in [m]}\tilde{N}_h^{j,k-1}(s,a)}} \sqrt{2\log\frac{2(SAHKm)^{3S}}{\delta}} \\ &+ \frac{8\alpha m\sqrt{N_h^{\operatorname{cut},k-1}(s,a)}}{\sum_{j \in [m]}\tilde{N}_h^{j,k-1}(s,a)} (H-h+1)\sqrt{2\log\frac{2m(SAHKm)^{3S}}{\delta}} \end{align}\] Where \(N_h^{\operatorname{cut},k-1}(s,a)\) is the \((2\alpha m +1)\)-largest among \(\left\{N_{h}^{j,k-1}(s,a)\right\}\) and \[\tilde{N}_h^{j,k-1}(s,a) = \max\left(N_h^{\operatorname{cut},k-1}(s,a), N_h^{j,k-1}(s,a)\right);\] For any \(k -1\ge k_{l_0(s,a,h)}\), \(\max_{i,j \in \mathcal{G}}\frac{N_h^{j,k-1}(s,a)}{N_h^{i,k-1}(s,a)} \le 2\) implies \(\forall j\), \(\tilde{N}_h^{j,k-1}(s,a) \ge \frac{1}{2}N_h^{j,k-1}(s,a)\) and \(\tilde{N}_h^{j,k-1}(s,a) \ge \frac{1}{2}N_h^{\operatorname{cut},k-1}(s,a)\).

This means for any \(k \ge k_{l_0(s,a,h)}+1\) \[\frac{1}{\sqrt{\sum_{j \in [m]}\tilde{N}_h^{j,k-1}(s,a)}} \le \frac{\sqrt{2}}{\sqrt{\sum_{j \in [m]}N_h^{j,k-1}(s,a)}} = \frac{\sqrt{2}}{\sqrt{N_h^{k-1}(s,a)}}\] \[\begin{align} \frac{m\sqrt{N_h^{\operatorname{cut},k-1}(s,a)}}{\sum_{j \in [m]}\tilde{N}_h^{j,k-1}(s,a)} = & \frac{\sqrt{m}\sqrt{\sum_{j\in[m]}N_h^{\operatorname{cut},k-1}(s,a)}}{\sum_{j \in [m]}\tilde{N}_h^{j,k-1}(s,a)}\\ \le& \frac{\sqrt{m}\sqrt{2\sum_{j\in[m]}\tilde{N}_h^{j,k-1}(s,a)}}{\sum_{j \in [m]}\tilde{N}_h^{j,k-1}(s,a)} \le \frac{2\sqrt{m}}{\sqrt{N_h^{k-1}(s,a)}} \end{align}\] Thus \[\begin{align} \label{eq:bd32bn} \Gamma_h^k(s,a) \le & \frac{4 + 16\sqrt{2} \alpha \sqrt{m}}{\sqrt{N_h^{k-1}(s,a)}} H\sqrt{\log\frac{2m(SAHKm)^{3S}}{\delta}} + \frac{6}{SAHKm} \end{align}\tag{16}\]

We are know ready to bound the cumulative bonus: \[\begin{align} &\sum_{k=1}^K \sum_{j \in \mathcal{G}} \sum_{h=1}^H\Gamma_h^k(s_h^{j,k},a_h^{j,k}) = \sum_{h=1}^H\sum_{(s,a) \in \mathcal{S} \times \mathcal{A}} \sum_{t = 1}^{l+1}\Gamma_h^{k_{t-1}+1}(s, a) \left( N_h^{k_t}(s,a) - N_h^{k_{t-1}}(s,a) \right) \\ = & \sum_{h=1}^H\sum_{(s,a) \in \mathcal{S} \times \mathcal{A}} \left( \sum_{t = 1}^{l_0(s,a,h)}\Gamma_h^{k_{t-1}+1}(s, a) \left( N_h^{k_t}(s,a) - N_h^{k_{t-1}}(s,a) \right) \right.\\ & \left.+ \sum_{t = l_0(s,a,h)+1}^{l+1}\Gamma_h^{k_{t-1}+1}(s, a) \left( N_h^{k_t}(s,a) - N_h^{k_{t-1}}(s,a) \right) \right) \\ \le & \sum_{h=1}^H\sum_{(s,a) \in \mathcal{S} \times \mathcal{A}} \left( \sum_{t = 1}^{l_0(s,a,h)}\Gamma_h^{k_{t-1}+1}(s, a) \left( N_h^{k_t}(s,a) - N_h^{k_{t-1}}(s,a) \right) \right.\\ & +\sum_{t = l_0(s,a,h)+1}^{l+1}\frac{4 + 16\sqrt{2} \alpha \sqrt{m}}{\sqrt{N_h^{k-1}(s,a)}} H\sqrt{\log\frac{2m(SAHKm)^{3S}}{\delta}} \left( N_h^{k_t}(s,a) - N_h^{k_{t-1}}(s,a) \right)\\ &\left.+ \sum_{t = l_0(s,a,h)+1}^{l+1}\frac{6}{SAHKm} \left( N_h^{k_t}(s,a) - N_h^{k_{t-1}}(s,a) \right) \right) \\ &\left(By \pref{eq:bd32bn}\right)\\ =:& \mathscr{A}_1 + \mathscr{A}_2 + \mathscr{A}_3. \end{align}\] By and , \[\mathscr{A}_1 \le SAH^2N_h^{k_{l_0(s,a,h)}}(s,a)\le 2SAH^2N_0.\] Because \(k_{l+1} = K\), \[\begin{align} \mathscr{A}_3 \le & \frac{6}{SAHKm}\sum_{h=1}^H \sum_{(s,a)\in\Scal\x\Acal} N_h^{K}(s,a) = \frac{6}{SA} \end{align}\] By , \[\begin{align} &\sum_{t = l_0(s,a,h)+1}^{l+1}\frac{N_h^{k_t}(s,a) - N_h^{k_{t-1}}(s,a)}{\sqrt{N_h^{k_{t-1}}(s,a)}} \le (\sqrt{2}+1)\sum_{t = l_0(s,a,h)+1}^{l+1}\frac{N_h^{k_t}(s,a) - N_h^{k_{t-1}}(s,a)}{\sqrt{N_h^{k_t}(s,a)} + \sqrt{N_h^{k_{t-1}}(s,a)}}\\ =& (\sqrt{2}+1)\sum_{t = l_0(s,a,h)+1}^{l+1}\left({\sqrt{N_h^{k_t}(s,a)} - \sqrt{N_h^{k_{t-1}}(s,a)}}\right) \le (\sqrt{2}+1)\sqrt{N_h^{K}(s,a)} \end{align}\] By Cauchy–Schwarz inequality, \[\begin{align} \sum_{(s,a) \in \mathcal{S} \times \mathcal{A}} \sqrt{N_h^{K}(s,a)} \le \sqrt{\sum_{(s,a) \in \mathcal{S} \times \mathcal{A}} 1\sum_{(s,a) \in \mathcal{S} \times \mathcal{A}} {N_h^{K}(s,a)}} =\sqrt{SAKm} \end{align}\] Thus \[\begin{align} \mathscr{A}_2 \le & (\sqrt{2}+1)(4+16\sqrt{2}\alpha \sqrt{m})H^2\sqrt{SAKm} \sqrt{\log\frac{2m(SAHKm)^{3S}}{\delta}} \\ =&O\left((1+\alpha\sqrt{m})H^2S\sqrt{AKm}\sqrt{\log\frac{SAHKm}{\delta}} \right) \end{align}\] Thus \[\begin{align} \mathscr{A}_1 + \mathscr{A}_2 + \mathscr{A}_3 \le & O\left((1+\alpha\sqrt{m})H^2S\sqrt{AKm}\sqrt{\log\frac{SAHKm}{\delta}} \right)\\ &+ O\left(SAH^2 m\log \frac{2 mKSAH}{\delta}\right) \end{align}\]

In conclusion: \[\begin{align} \sum_{k=1}^K \sum_{j \in \mathcal{G}}\left(V_1^*(s_1) - V_1^{\hat{\pi}^k}(s_1)\right) \le & 2\sum_{k=1}^K \sum_{j \in \mathcal{G}}\sum_{h=1}^H\Gamma_h^k(s_h^{j,k},a_h^{j,k}) + \sqrt{8mKH^3\log\frac{2}{\delta}}\\ =&\tilde{O}\left( (1 + \alpha \sqrt{m})SH^2\sqrt{AKm\log \frac{1}{\delta}} \right) \end{align}\] ◻

10.1 the good event \(\mathcal{E}\) ↩︎

We first show that our bonus is a valid upper confidence bound for the estimated Bellman operator. Recall that our bonus term used in \(k\)-th episode is calculated based on the data collected in the first \(k-1\)-episodes. The bonus is given by:

If \(|j \in [m]: N_h^{j,k-1}(s,a) > 0| < 2\alpha m + 1\) \[\Gamma_h^k(s,a) = H - h + 1;\]
If \(|j \in [m]: N_h^{j,k-1}(s,a) > 0| \ge 2\alpha m + 1\) \[\begin{align} \Gamma_h^k(s,a) := & \frac{6}{SAHKm}+ \;\frac{2{(H-h+1)}}{\sqrt{\sum_{j \in [m]}\tilde{N}_h^{j,k-1}(s,a)}} \sqrt{2\log\frac{2(SAHKm)^{3S}}{\delta}} \\ &+ \frac{8\alpha m\sqrt{N_h^{\operatorname{cut},k-1}(s,a)}}{\sum_{j \in [m]}\tilde{N}_h^{j,k-1}(s,a)} {(H-h+1)}\sqrt{2\log\frac{2m(SAHKm)^{3S}}{\delta}} \end{align}\] Where \(N_h^{\operatorname{cut},k-1}(s,a)\) is the \((2\alpha m +1)\)-largest among \(\left\{N_{h}^{j,k-1}(s,a)\right\}\) and \[\tilde{N}_h^{j,k-1}(s,a) = \max\left(N_h^{\operatorname{cut},k-1}(s,a), N_h^{j,k-1}(s,a)\right).\]

To be precise:

Lemma 3 (Valid bonus). Let \(\mathcal{E}\) be the following event: \[\mathcal{E} = \left\{ \bigcap_{(s,a,h,k,f) \in \mathcal{S} \times \mathcal{A} \times H \times K \times [0,1]^{\mathcal{S}}} \left\{\left| \left(\hat{\Bell}_h^k f\right)(s,a) - \left(\Bell_h f\right)(s,a) \right| \le \Gamma_h^k(s,a)\right\} \right\}\] Then, we have \[\PP\left(\mathcal{E}\right) \ge 1 - \delta\]

To show that \(\Ecal\) is a high probability event, we seek to utilize the result of . Since there are two obstacles, we need to make some modifications:

Because the transition tuples are collected sequentially, they are no longer i.i.d., which means does not hold trivially. To resolve this, we use the concentration of martingale (see );
Event \(\Ecal\) shows the concentration property of \(\hat{\Bell}\) holds uniformly for infinitely many \(f\)’s. Thus a direct union bound does not apply. Instead we need to use a cover number argument for all possible \(f\)’s, which is standard (see [30]).

Proof of . Let \(\mathcal{E}'\) be the following event: \[\label{eq:eve32cover} \mathcal{E}' = \left\{N_h^{\operatorname{cut},k-1}(s,a) > 0\right\}.\tag{17}\] In the following, we decompose \(\mathcal{E}\) by: \[\mathcal{E} = \left(\mathcal{E} \cap \overline{\mathcal{E}'}\right) \cup \left(\mathcal{E} \cap \mathcal{E}'\right)\] and bound \(\PP\left(\mathcal{E}\right)\) by law of total probability.

If \(N_h^{\operatorname{cut},k-1}(s,a)=0\), because \(\left(\hat{\Bell}_h^k f\right)(s,a) = 0\) and \(\left(\Bell_h f\right)(s,a) \le H - h + 1\), with probability \(1\), \(\forall (s,a,h,k,f) \in \mathcal{S} \times \mathcal{A} \times H \times K \times [0,1]^{\mathcal{S}}\), \[\left| \left(\hat{\Bell}_h^k f\right)(s,a) - \left(\Bell_h f\right)(s,a) \right| \le \Gamma_h^k(s,a)\] This means \[\PP\left(\mathcal{E} \cap \overline{\mathcal{E}'}\right) = \PP\left(\mathcal{E} | \overline{\mathcal{E}'}\right) \PP\left(\overline{\mathcal{E}'}\right) = \PP\left(\overline{\mathcal{E}'}\right)\]

If \(N_h^{\operatorname{cut},k-1}(s,a) > 0\), we use a covering number argument and union bound to bound the probability of event \(\mathcal{E}\).

Consider \(\mathcal{V}_{\epsilon} := \left\{ \frac{1}{\lceil 1/ \epsilon \rceil}, \frac{2}{\lceil 1/ \epsilon \rceil}, \ldots, \frac{H\lceil 1/ \epsilon \rceil}{\lceil 1/ \epsilon \rceil} \right\}^{\mathcal{S}}\), an \(\epsilon\) cover of \([0,H]^{\mathcal{S}}\), in the sense of \(\infty\)-norm. We can bound the cover number by \(\left|\mathcal{V}_{\epsilon}\right| \le \left(H\left(\frac{1}{\epsilon} + 1\right)\right)^{S}\). This means \(\forall f \in [0,H]^{\mathcal{S}}\), we can find an \(V_f \in \mathcal{V}_\epsilon\), s.t. \(\|f - V_f\|_\infty := \max_{x\in\mathcal{S}}|f(x) - V_f(x)| \le \epsilon\). In another word, \[[0,H]^{\mathcal{S}} = \bigcup_{f_\epsilon \in \mathcal{V}_\epsilon} \left\{f : \|f - f_\epsilon\|_\infty \le \epsilon\right\}.\]

Importantly, unlike model based method without bad agents, our \(\hat{\Bell}\) is not an linear operator, meaning we cannot trivially upper bound \(\left| \left(\hat{\Bell}_h^k f\right)(s,a) - \left(\hat{\Bell}_h^k V_f\right)(s,a) \right|\) in the cover number argument. Instead, we need to use the continuity of error bound of our robust mean estimation , meaning as long as each data point collected by each agent is not perturbed too much, then the estimation error bound does not increase too much.

Recall that in , at episode \(k\), if the agents decide to synchronize, then at each step \(h\), given any function \(f\), the clean agents will calculate empirical mean for \[\label{eq:pert32bell32set} \left\{r + f (s'): (s,a,r,s') \in D_h^{j,k}\right\}.\tag{18}\] Let \(f_\epsilon\) be an element in \(\mathcal{V}_{\epsilon}\), s.t. \(\|f_\epsilon- f\|_\infty \le \epsilon\), this means set is a perturbed version (by at most \(\epsilon\)) of \[\left\{r + f_\epsilon (s'): (s,a,r,s') \in D_h^{j,k}\right\}.\] This means given an \(f_\epsilon \in \mathcal{V}_\epsilon\), for any \(f\), s.t. \(\|f - f_\epsilon\|_\infty \le \epsilon\), can be used to robustly estimate \(\left(\Bell_h f_\epsilon\right)(s,a)\), given set . Furthermore, choosing \(\epsilon = \frac{1}{SAHKm}\), by , and , given any \(s,a,h,k, f_\epsilon\), and any \(f\), s.t. \(\|f - f_\epsilon\|_\infty \le \epsilon\), with probability at least \(1-\frac{\delta}{(SAHKm)^{3S}/(2mK)}\), \[\left| \left(\hat{\Bell}_h^k f\right)(s,a) - \left( \Bell_h f_\epsilon\right)(s,a) \right| \le \Gamma_h^k(s,a) - \frac{1}{SAHKm}.\]

We can bound the \(\left| \left(\hat{\Bell}_h^k f\right)(s,a) - \left(\Bell_h f\right)(s,a) \right|\) by: \[\begin{align} \left| \left(\hat{\Bell}_h^k f\right)(s,a) - \left(\Bell_h f\right)(s,a) \right| \le &\left| \left(\hat{\Bell}_h^k f\right)(s,a) - \left(\Bell_h f_\epsilon\right)(s,a) \right|+ \left| \left(\Bell_h f_\epsilon\right)(s,a) - \left(\Bell_h f\right)(s,a) \right| \\ \le & \left| \left(\hat{\Bell}_h^k f\right)(s,a) - \left(\Bell_h f_\epsilon\right)(s,a) \right| + \frac{1}{SAHKm} \end{align}\]

Then \[\begin{align} &\PP\left(\bigcup_{s,a,h,k,f} \left\{\left| \left(\hat{\Bell}_h^k f\right)(s,a) - \left(\Bell_h f\right)(s,a) \right| > \Gamma_h^k(s,a)\right\} \right) \\ \le & \sum_{s,a,h,k} \PP\left(\bigcup_{f\in[0,H]^{\mathcal{S}}} \left\{\left| \left(\hat{\Bell}_h^k f\right)(s,a) - \left(\Bell_h f\right)(s,a) \right| > \Gamma_h^k(s,a)\right\} \right) \\ \le & \sum_{s,a,h,k} \PP\left(\bigcup_{f_\epsilon \in \mathcal{V}_\epsilon}\bigcup_{f: \|f - f_\epsilon\|_\infty \le \epsilon} \left\{\left| \left(\hat{\Bell}_h^k f\right)(s,a) - \left(\Bell_h f_\epsilon\right)(s,a) \right| + \frac{1}{SAHKm} > \Gamma_h^k(s,a)\right\} \right)\\ \le & \sum_{s,a,h,k}\sum_{f_\epsilon \in \mathcal{V}_\epsilon} \PP\left(\bigcup_{f: \|f - f_\epsilon\|_\infty \le \epsilon} \left\{\left| \left(\hat{\Bell}_h^k f\right)(s,a) - \left(\Bell_h f_\epsilon\right)(s,a) \right| + \frac{1}{SAHKm} > \Gamma_h^k(s,a)\right\} \right)\\ \le &SAHK (H(1+HSAKm))^{S} \frac{\delta}{(SAHKm)^{3S}/(2mK)} \le \delta \end{align}\] This means \[\PP\left(\mathcal{E} \cap {\mathcal{E}'}\right) = \PP\left(\mathcal{E} | {\mathcal{E}'}\right) \PP\left({\mathcal{E}'}\right) \ge \left(1 - \delta\right)\PP\left({\mathcal{E}'}\right) \ge \PP\left({\mathcal{E}'}\right) - \delta\] In conclusion, \[\PP\left(\mathcal{E}\right) = \PP\left(\mathcal{E} \cap {\mathcal{E}'}\right) + \PP\left(\mathcal{E} \cap \overline{\mathcal{E}'}\right) \ge \PP\left({\mathcal{E}}\right) + \PP\left({\mathcal{E}'}\right) - \delta = 1 - \delta.\] ◻

10.1.1 Concentration of estimation from good agents↩︎

Lemma 4. Let: \[\left(\hat{\Bell}_h^{j,k} f \right)(s,a) := \frac{1}{N_{h}^{j,k}(s,a)}\sum_{(s,a,r,s') \in D_h^{j,k}}r+f(s'),\] where we define \(\frac{0}{0}=0\). For any \(f:\Scal \mapsto [H]\), and for any \((s,a,h,k)\in\Scal \x \Acal \x [H] \x [K]\) with probability at least \(1-\delta/2\), \(\Ecal_{conc-seq}(s,a,h,k)\) happens, where \[\Ecal_{conc-seq}(s,a,h,k) = \bigcap_{j\in\Gcal}\Ecal_{c-seq}(s,a,h,j,k),\] and \[\begin{align} \Ecal_{c-seq}(s,a,h,j,k) := \left\{ \left|\left(\hat{\Bell}_h^{j,k} f \right)(s,a) - \left(\Bell_h f \right)(s,a) \right| \le \frac{H-h+1}{\sqrt{\tilde{N}_{h}^{j,k}(s,a)}} \sqrt{2\log \frac{4Km}{\delta}} \right\} \end{align}\]

Proof of . We use the martingale stopping time argument in Lemma 4.3 of [54].

For each fixed \((s,a,h,j) \in \Scal \x \Acal \x [H] \x \Gcal\): for all \(t \in [K]\), define \[\Fcal_t := \sigma\left(\bigcup_{t'\le t}\bigcup_{j \in [m]}\left\{\left(s_{h}^{j,t'},a_{h}^{j,t'},r_{h}^{j,t'},s_{h+1}^{j,t'}\right)\right\}_{h=1}^H\right).\] Let \[X_t = \sum_{(s,a,r,s') \in D_h^{j,t}} \left( r+f(s') - \left(\Bell_h f \right)(s,a) \right)\] Then \(\left\{\left(\Fcal_t, X_t\right)\right\}_{t=1}^K\) is a martingale. One observation is \(X_{t_1} = X_{t_2}\) if agent \(j\) did not visit \((s,a,h)\) in \(t_1+1, t_1 + 2, \dots, t_2\)-th episodes. Thus we can use the stopping time idea to shorten the martingale sequence.

Define the following sequence of \(t_i\)’s: \(t_0:=0\), \[t_i := \min\left(\left\{t' \in [K]: t' \ge t_{i-1}and(s_h^{j,t'}, a_h^{j,t'}) = (s,a)\right\}\cup \left\{K+1\right\}\right).\] Intuitively, \(t_i\) is the episode when \((s,a, h)\) is visited by agent \(j\) for the \(i\)-th time. If agent \(j\) visit \((s,a,h)\) for less than \(i\) times, then \(t_i = K+1\). By definition, \(t_i\) is a stopping time w.r.t. \(\left\{\Fcal_t\right\}_{t=1}^K\).

By optional sampling theorem, \(\left\{\left(\Fcal_{t_i}, X_{t_i}\right)\right\}_{i=1}^K\) is a martingale.

By Azuma-Hoeffding’s inequality: for any \(\tau \le K\) \[\PP\left(\left|X_{t_\tau}\right| \ge \beta\right) \le 2\exp\left(-\frac{2\beta^2}{4\tau (H-h+1)^2}\right)\] Let \(\frac{\delta}{2mK} = 2\exp\left(-\frac{2\beta^2}{4\tau (H-h+1)^2}\right)\), we get: for any \((s,a,h,j)\), for any \(\tau \le K\), with probability at least \(1-\frac{\delta}{2mK}\): \[\left|\sum_{(s,a,r,s') \in D_h^{j,t_{\tau}}} \left( r+f(s') - \left(\Bell_h f \right)(s,a) \right) \right| < \sqrt{\tau}(H-h+1)\sqrt{2\log\frac{4mK}{\delta}}.\] By union bound, for any \((s,a,h,j)\), with probability at least \(1-\frac{\delta}{mK}\), for any \(\tau \le K\): \[\left|\sum_{(s,a,r,s') \in D_h^{j,t_{\tau}}} \left( r+f(s') - \left(\Bell_h f \right)(s,a) \right) \right| < \sqrt{\tau}(H-h+1)\sqrt{2\log\frac{4mK}{\delta}}.\] This means for any \((s,a,h,j,k)\) and any \(\tau \le k\) \[\begin{align} &\PP\left(\left.\overline{\Ecal_{c-seq}(s,a,h,j,k)}\right| N_{h}^{j,k}(s,a)=\tau\right)\\ \le & \PP\left( \left. \left|\left(\hat{\Bell}_h^{j,k} f \right)(s,a) - \left(\Bell_h f \right)(s,a) \right| \ge \frac{H-h+1}{\sqrt{N_{h}^{j,k}(s,a)}} \sqrt{2\log \frac{4Km}{\delta}} \right| N_{h}^{j,k}(s,a) = \tau \right) \\ \le & \frac{\delta}{mK} \end{align}\] Thus \[\begin{align} \PP\left(\overline{\Ecal_{c-seq}(s,a,h,j,k)}\right) =&\sum_{\tau = 0}^{k} \PP\left(\left.\overline{\Ecal_{c-seq}(s,a,h,j,k)}\right| N_{h}^{j,k}(s,a)=\tau\right) \PP\left(N_{h}^{j,k}(s,a)=\tau\right) \\ \le & \frac{\delta}{2mK} \end{align}\] By union bound \[\PP\left({\Ecal_{conc-seq}(s,a,h,k)}\right) \ge 1- \frac{\delta}{2} .\] ◻

Lemma 5. Let: \[\left(\hat{\Bell}_h^{j,k} f \right)(s,a) := \frac{1}{N_{h}^{j,k}(s,a)}\sum_{(s,a,r,s') \in D_h^{j,k}}r+f(s'),\] \[\left(\hat{\Bell}_h^{\Gcal,k} f \right)(s,a) :=\frac{1}{\sum_{j\in\Gcal}\tilde{N}_h^{j,k}(s,a)} \sum_{j\in\Gcal}\tilde{N}_h^{j,k}(s,a)\left(\hat{\Bell}_h^{j,k} f \right)(s,a),\] where we define \(\frac{0}{0}=0\). For any \(f:\Scal \mapsto [H]\), with probability at least \(1-\delta/2\), \(\Ecal_{ct}(s,a,h,k)\) happens, where \[\begin{align} \Ecal_{ct}(s,a,h,k):= \left\{ \left|\left(\hat{\Bell}_h^{\Gcal,k} f \right)(s,a) - \left(\Bell_h f \right)(s,a) \right| \le \frac{H-h+1}{\sqrt{\sum_{j\in\Gcal}\tilde{N}_{h}^{j,k}(s,a)}} \sqrt{2\log \frac{4mK}{\delta}} \right\} \end{align}\]

Proof . During the data collecting process, the agents are allowed to collect data simultaneously. For analysis purpose, we artificially order the data in the following sequence: \[\label{eq:E32seq} E^{1,1}, E^{2,1}, \ldots, E^{m,1}, E^{1,2}, \ldots, E^{m,2}, \ldots, E^{1,K}, \ldots, E^{m,K}\tag{19}\] where \(E^{j,k} := \left\{\left(s_{h}^{j,k},a_{h}^{j,k},r_{h}^{j,k},s_{h+1}^{j,k}\right)\right\}_{h=1}^H\). Let \[\Fcal_t = \sigma\left(\bigcup_{j,ks.t. m(k-1) + j \le t}E^{j,k}\right).\] Then \(\left\{\Fcal_t\right\}_{t=0}^{mK}\) forms a valid filtration. Let \(\left\{\left\{\gamma_{j,k}\right\}_{j\in[m]}\right\}_{k\in[K]}\) be a fixed set of scalar, s.t. \(0\le \gamma_{j,k}\le 1\), for all \(j,k\).

For each fixed \((s,a,h) \in \Scal \x \Acal \x [H]\): for all \(t \in [mK]\), Let \[X_t = \sum_{(s,a,r,s') \in \bigcup_{(j,k) \in \Gcal \x [K]s.t. m(k-1) + j \le t}E^{j,k}} \gamma_{j,k} \left( r+f(s') - \left(\Bell_h f \right)(s,a) \right)\] Then \(\left\{\left(\Fcal_t, X_t\right)\right\}_{t=1}^{mK}\) is a martingale. As we can see, if good agent \(j\) did not visit \((s,a,h)\) in episode \(k\), then \(X_{m(k-1) + j} = X_{m(k-1) + j-1}\) a.s. Thus we can use the stopping time idea to shorten the martingale sequence.

Define the following functions to map from sequence index to agent index and episode index: \[\begin{align} \mathcal{J}(t) := t - m\left(\lceil t/m \rceil - 1\right), \quad \mathcal{K}(t) := \lceil t/m \rceil \end{align}\] For any \(n_1, \ldots, n_m\), define the following sequence of \(t_i\)’s: \(t_0:=0\), \[\begin{align} t_i := &\min\left(\left\{t' \in [mK]: t' \ge t_{i-1}and(s_h^{\Jcal(t'), \Kcal(t')}, a_h^{\Jcal(t'), \Kcal(t')}) = (s,a) \right.\right.\\ &\left. \left. and for all j\le \Jcal(t'), N_h^{j,\Kcal(t')} \le n_j;j> \Jcal(t'), N_h^{j,\Kcal(t')-1} \le n_j \right\}\cup \left\{K+1\right\}\right). \end{align}\] Intuitively, \(t_i\) is the episode when \((s,a, h)\) is visited in sequence for the \(i\)-th time. And for all \(j\), agent \(j\) have not collected \(n_j\) \((s,a,h)\) tuples. If \((s,a,h)\) is visited for less than \(i\) times or there exists agent \(j\) visiting \((s,a,h)\) more than \(n_j\) times, then \(t_i = K+1\). By definition, \(t_i\) is a stopping time w.r.t. \(\left\{\Fcal_t\right\}_{t=1}^{mK}\).

In particular, let \(n_\cut\) be the \((2\alpha m +1)\)th-largest of all \(n_j\)’s and \(\tilde{n}_j = \min(n_\cut, n_j)\). We choose \(\gamma_{j,k}:= \frac{\tilde{n}_j}{n_j}\le1\).

By optional sampling theorem, \(\left\{\left(\Fcal_{t_i}, X_{t_i}\right)\right\}_{i=1}^{mK}\) is a martingale.

By Azuma-Hoeffding’s inequality: for any \(\tau := \sum_{j\in[m]}n_j \le mK\) \[\PP\left(\left|X_{t_\tau}\right| \ge \beta\right) \le 2\exp\left(-\frac{2\beta^2}{4(H-h+1)^2\sum_{t=1}^{\tau}\gamma_{\Jcal(t), \Kcal(t)}^2}\right)\] Let \(\frac{\delta}{2mK} = 2\exp\left(-\frac{2\beta^2}{4(H-h+1)^2\sum_{t=1}^{\tau}\gamma_{\Jcal(t), \Kcal(t)}^2}\right)\), we get: for any \((s,a,h)\), for any \(\tau \le mK\), with probability at least \(1-\frac{\delta}{2mK}\): \[\left|X_{t_\tau}\right| < \sqrt{\sum_{t=1}^{\tau}\gamma_{\Jcal(t), \Kcal(t)}^2}(H-h+1)\sqrt{2\log\frac{4mK}{\delta}}.\] By union bound, for any \((s,a,h)\), with probability at least \(1-\frac{\delta}{2}\), for any \(\tau \le mK\): \[\left|X_{t_\tau}\right| < \sqrt{\sum_{t=1}^{\tau}\gamma_{\Jcal(t), \Kcal(t)}^2}(H-h+1)\sqrt{2\log\frac{4mK}{\delta}}.\] This means for any \((s,a,h,k)\in\Scal \x \Acal \x [H] \x [ K]\) and any \(\tau \le mk\) \[\begin{align} &\PP\left(\left.\overline{\Ecal_{ct}(s,a,h,k)}\right| N_{h}^{j,k}(s,a)=n_{j}, \forall j\right)\\ \le & \PP\left( \left|\left(\hat{\Bell}_h^{\Gcal,k} f \right)(s,a) - \left(\Bell_h f \right)(s,a) \right| \ge \frac{(H-h+1)\sqrt{\sum_{t=1}^{\tau}\frac{\tilde{N}_h^{\Jcal(t), \Kcal(t)}(s,a)}{N_h^{\Jcal(t), \Kcal(t)}(s,a)}}}{{\sum_{j\in\Gcal}\tilde{N}_{h}^{j,k}(s,a)}}\right.\\ &\left.\left.\cdot\sqrt{2\log \frac{4SAHmK^2}{\delta}} \right| N_{h}^{j,k}(s,a)=n_{j}, \forall j \right) \\ \le & \PP\left( \left|\left(\hat{\Bell}_h^{\Gcal,k} f \right)(s,a) - \left(\Bell_h f \right)(s,a) \right| \ge \frac{(H-h+1)\sqrt{\sum_{t=1}^{\tau}\left(\frac{\tilde{N}_h^{\Jcal(t), \Kcal(t)}(s,a)}{N_h^{\Jcal(t), \Kcal(t)}(s,a)}\right)^2}}{{\sum_{j\in\Gcal}\tilde{N}_{h}^{j,k}(s,a)}}\right.\\ &\left.\left.\cdot\sqrt{2\log \frac{4SAHmK^2}{\delta}} \right| N_{h}^{j,k}(s,a)=n_{j}, \forall j \right) \\ \le & \frac{\delta}{2} \quad \left(By \gamma_{j,k} = \frac{\tilde{N}_h^{j,k}(s,a)}{N_h^{j,k}(s,a)}\right) \end{align}\] Thus \[\begin{align} \PP\left(\overline{\Ecal_{ct}(s,a,h,k)}\right) =&\sum_{(n_1, \ldots, n_m) \in [K]^m} \PP\left(\left.\overline{\Ecal_{ct}(s,a,h,k)}\right| N_{h}^{j,k}(s,a)=n_{j}, \forall j\right) \\ &\PP\left(N_{h}^{j,k}(s,a)=n_{j}, \forall j\right) \\ \le & \frac{\delta}{2} \end{align}\] ◻

10.2 The regret decomposition for UCB style algorithm↩︎

We follow the regret decomposition strategy in [30] under event \(\mathcal{E}\), i.e. the estimation error for the Bellman operator is bounded by the bonus term.

The estimated Bellman operator can be used to approximate the Q function:

Lemma 6. Under event \(\mathcal{E}\), for any \((s,a,h,k) \in \mathcal{S} \times \mathcal{A} \times H \times K\), and any policy \(\pi'\) \[\begin{align} \left|\left(\hat{\Bell}_h^k \hat{V}_{h+1}^k\right)(s,a) - Q_h^{\pi'}(s,a) - \EE_{s'\sim P_h(\cdot \mid s,a)}\left[\hat{V}_{h+1}^k (s') - V_{h+1}^{\pi'}(s')\right] \right| \le \Gamma_h^k(s,a) \end{align}\]

Proof of . \[\begin{align} &\left|\left(\hat{\Bell}_h^k \hat{V}_{h+1}^k\right)(s,a) - Q_h^{\pi'}(s,a) - \EE_{s'\sim P_h(\cdot \mid s,a)}\left[\hat{V}_{h+1}^k (s') - V_{h+1}^{\pi'}(s')\right] \right| \\ \le & \left|\left(\hat{\Bell}_h^k \hat{V}_{h+1}^k\right)(s,a) - \left(\Bell_h \hat{V}_{h+1}^k\right)(s,a)\right| \\ &+\left|\left(\Bell_h \hat{V}_{h+1}^k\right)(s,a) - \left( \Bell_h V_{h+1}^{\pi'}\right)(s,a) - \EE_{s'\sim P_h(\cdot \mid s,a)}\left[\hat{V}_{h+1}^k (s') - V_{h+1}^{\pi'}(s')\right] \right| \\ & \left(By triangular inequality and the fact that \left( \Bell_h V_{h+1}^{\pi'}\right)(s,a) = Q_h^{\pi'}(s,a).\right)\\ \le & \Gamma_h^k(s,a) \\ & \left(We can bound the first term by the definition of event \mathcal{E}, \right.\\ &\left.and the second term is zero by the definition of Bellman operator.\right) \end{align}\] ◻

Under event \(\mathcal{E}\) we can upper bound the value function and Q function of the optimal policy by the estimated value function and Q function of policy \(\hat{\pi}^k\):

Lemma 7 (Optimism). Under event \(\mathcal{E}\), \(\forall s,a,h,k\): \[\begin{align} \hat{Q}_h^k(s,a) \ge Q_h^*(s,a), \quad \hat{V}_h^k(s) \ge V_h^*(s) \label{eq:hat32Q32ge32Q} \end{align}\qquad{(3)}\]

Proof of . We prove this by induction on \(h\). Before that, note that, for any \(h,k,s\), if \[\hat{Q}_h^k(s,a) \ge Q_h^*(s,a), \quad \forall a\] then because \(\hat{\pi}^k\) is chosen by maximizing \(\hat{Q}_{h}^k(s,a)\), we know \[\hat{V}_h^k(s) = \max_a \hat{Q}_{h}^k(s,a) \ge \hat{Q}_{h}^k(s,\pi_h^*(a)) \ge Q_{h}^*(s,\pi_h^*(a)) =V_h^*(s)\] This means for any \(h,k,s\): \[\label{eq:Q32232V} \left\{\forall a,\hat{Q}_h^k(s,a) \ge Q_h^*(s,a)\right\} \implies \left\{\hat{V}_h^k(s) \ge V_h^*(s)\right\}\tag{20}\] We now begin our induction:

For the base case, our goal is to show for any \(s,a,k\), in the last step \(H\), \[\begin{align} \hat{Q}_H^k(s,a) \ge Q_H^*(s,a), \quad \hat{V}_H^k(s) \ge V_H^*(s) \end{align}\] First note that \(\hat{V}_{H+1} = V_{H+1}^*=0\). By and choose \(\pi' = \pi^*\), \[\begin{align} \left|\left(\hat{\Bell}_H^k \hat{V}_{H+1}^k\right)(s,a) - Q_h^{*}(s,a)\right| \le \Gamma_H^k(s,a) \end{align}\] By definition of \(\hat{Q}_H^k(s,a)\), and the fact that \(Q_h^{*}(s,a)\) only contains the reward at step \(H\), which is bounded by \(1\): \[\begin{align} \hat{Q}_H^k(s,a) = \min\left(\left(\hat{\Bell}_H^k \hat{V}_{H+1}^k\right)(s,a) + \Gamma_H^k(s,a),1 \right) \ge Q_H^{*}(s,a) \end{align}\] By , \(\hat{V}_H^k(s) \ge V_H^*(s), \forall s\).
Suppose for any \(s,a,k\), the statement holds for step \(h+1\), i.e. \[\begin{align} \label{eq:hat32Q32ge32Q32h431} \hat{Q}_{h+1}^k(s,a) \ge Q_{h+1}^*(s,a), \quad \hat{V}_{h+1}^k(s) \ge V_{h+1}^*(s) \end{align}\tag{21}\] our goal is to show \(\forall s,a,k\): \[\begin{align} \hat{Q}_h^k(s,a) \ge Q_h^*(s,a), \quad \hat{V}_h^k(s) \ge V_h^*(s) \end{align}\] \[\begin{align} & \left(\hat{\Bell}_h^k \hat{V}_{h+1}^k\right)(s,a) + \Gamma_h^k(s,a)\\ \ge&\left(\hat{\Bell}_h^k \hat{V}_{h+1}^k\right)(s,a) + \left|\left(\hat{\Bell}_h^k \hat{V}_{h+1}^k\right)(s,a) - Q_h^{*}(s,a) - \EE_{s'\sim P_h(\cdot \mid s,a)}\left[\hat{V}_{h+1}^k (s') - V_{h+1}^{*}(s')\right] \right| \\ & \left(By \prettyref{lem:q32error} and let \pi' = \pi^*\right) \\ \ge & Q_h^{*}(s,a) + \EE_{s'\sim P_h(\cdot \mid s,a)}\left[\hat{V}_{h+1}^k (s') - V_{h+1}^{*}(s')\right]\\ &\left(By triangular inequality\right)\\ \ge & Q_h^{*}(s,a) \\ &\left(\forall s,\hat{V}_{h+1}^k (s') \ge V_{h+1}^{*}(s') by \pref{eq:hat32Q32ge32Q32h431}\right) \end{align}\] By definition of Q function \(Q_h^{*}(s,a) \le H-h+1\). We concludes these two statements by: \[\begin{align} \hat{Q}_h^k(s,a) = \min\left(\left(\hat{\Bell}_h^k \hat{V}_{h+1}^k\right)(s,a) + \Gamma_h^k(s,a),H - h+1 \right) \ge Q_h^{*}(s,a) \end{align}\] By , \(\hat{V}_h^k(s) \ge V_h^*(s), \forall s\).

◻

We are know ready to prove the regret decomposition lemma:

Lemma 8. Under good event \(\mathcal{E}\): \[\begin{align} &\sum_{k=1}^K \sum_{j \in \mathcal{G}}\left(V_1^*(s_1) - V_1^{\hat{\pi}^k}(s_1)\right) \\ \le & 2\sum_{k=1}^K \sum_{j \in \mathcal{G}}\sum_{h=1}^H\Gamma_h^k(s_h^{j,k},a_h^{j,k}) \\ &+ \sum_{k=1}^K \sum_{j \in \mathcal{G}}\sum_{h=1}^H\left(\EE_{s'\sim P_h(\cdot \mid s_h^k,a_h^k)}\left[\hat{V}_{h+1}^k (s') - V_{h+1}^{\hat{\pi}^k}(s')\right] - \left(\hat{V}_{h+1}^k (s_{h+1}^{j,k}) - V_{h+1}^{\hat{\pi}^k}(s_{h+1}^{j,k})\right)\right) \end{align}\]

Proof of . We start by showing the decomposition of regret after step \(h\) in one episode of a single agent: by and , under event \(\mathcal{E}\), for any \(s,k,h\) \[\begin{align} &V_h^*(s) - V_h^{\hat{\pi}^k}(s)\le \hat{V}_h^{\hat{\pi}^k}(s) - V_h^{\hat{\pi}^k}(s) \quad \left(By \prettyref{lem:opt}\right) \\ = & \hat{Q}_h^{k}(s, \hat{\pi}_h^k(s)) - Q_h^{\hat{\pi}^k}(s, \hat{\pi}_h^k(s))\\ \le & \left(\hat{\Bell}_h^k \hat{V}_{h+1}^k\right)(s,a) + \Gamma_h^k(s,a) - Q_h^{\hat{\pi}^k}(s, \hat{\pi}_h^k(s)) \quad \left(By definition of \hat{Q}_h^k\right)\\ \le&\left|\left(\hat{\Bell}_h^k \hat{V}_{h+1}^k\right)(s,\hat{\pi}_h^k(s)) - Q_h^{\hat{\pi}^k}(s,\hat{\pi}_h^k(s)) - \EE_{s'\sim P_h(\cdot \mid s,\hat{\pi}_h^k(s))}\left[\hat{V}_{h+1}^k (s') - V_{h+1}^{\hat{\pi}^k}(s')\right] \right| \\ &+ \left|Q_h^{\hat{\pi}^k}(s,\hat{\pi}_h^k(s)) + \EE_{s'\sim P_h(\cdot \mid s,\hat{\pi}_h^k(s))}\left[\hat{V}_{h+1}^k (s') - V_{h+1}^{\hat{\pi}^k}(s')\right] \right| \\ & + \Gamma_h^k(s,a)- Q_h^{\hat{\pi}^k}(s, \hat{\pi}_h^k(s)) \\ &\left(By using triangular inequality on the first term\right)\\ \le& \Gamma_h^k(s,\hat{\pi}_h^k(s)) + Q_h^{\hat{\pi}^k}(s,\hat{\pi}_h^k(s)) + \EE_{s'\sim P_h(\cdot \mid s,\hat{\pi}_h^k(s))}\left[\hat{V}_{h+1}^k (s') - V_{h+1}^{\hat{\pi}^k}(s')\right] \\ &+ \Gamma_h^k(s,a)- Q_h^{\hat{\pi}^k}(s, \hat{\pi}_h^k(s))\\ & \left(The first term is by using \prettyref{lem:q32error} with \pi' = \hat{\pi}^k, \right.\\ &\left.the term inside the absolute in the second is non-negative by \prettyref{lem:opt}\right)\\ = & 2\Gamma_h^k(s,\hat{\pi}_h^k(s)) + \EE_{s'\sim P_h(\cdot \mid s,\hat{\pi}_h^k(s))}\left[\hat{V}_{h+1}^k (s') - V_{h+1}^{\hat{\pi}^k}(s')\right] \end{align}\]

This indeed gives a recursive formula: for any trajectory \(\left\{(s_{h}^k, a_{h}^k, r_{h}^k, s_{h+1}^k)\right\}_{h\in[H]}\) \[\begin{align} &\hat{V}_h^{\hat{\pi}^k}(s_h^k) - V_h^{\hat{\pi}^k}(s_h^k) \\ \le& 2\Gamma_h^k(s_h^k,\hat{\pi}_h^k(s_h^k)) + \EE_{s'\sim P_h(\cdot \mid s_h^k,\hat{\pi}_h^k(s_h^k))}\left[\hat{V}_{h+1}^k (s') - V_{h+1}^{\hat{\pi}^k}(s')\right] \\ = & \hat{V}_{h+1}^k (s_h^k) - V_{h+1}^{\hat{\pi}^k}(s_h^k) + 2\Gamma_h^k(s_h^k,\hat{\pi}_h^k(s_h^k)) \\ &+ \left( \EE_{s'\sim P_h(\cdot \mid s_h^k,\hat{\pi}_h^k(s_h^k))}\left[\hat{V}_{h+1}^k (s') - V_{h+1}^{\hat{\pi}^k}(s')\right] - \left(\hat{V}_{h+1}^k (s_h^k) - V_{h+1}^{\hat{\pi}^k}(s_h^k)\right)\right) \end{align}\]

Then, we can show the regret decomposition in one episode of a single agent by recursion:

for any trajectory \(\left\{(s_{h}^k, a_{h}^k, r_{h}^k, s_{h+1}^k)\right\}_{h\in[H]}\) collected by a clean agent under policy \(\hat{\pi}^k\): \[\begin{align} & V_1^*(s_1^k) - V_1^{\hat{\pi}^k}(s_1^k) \le \hat{V}_1^k(s_1^k) - V_1^{\hat{\pi}^k}(s_1^k) \\ \le & \left(\hat{V}_{2}^k (s_2^k) - V_{2}^{\hat{\pi}^k}(s_2^k)\right) + 2\Gamma_1^k(s_1^k,a_1^k) \\ &+ \left( \EE_{s'\sim P_1(\cdot \mid s_1^k,a_1^k)}\left[\hat{V}_{2}^k (s') - V_{2}^{\hat{\pi}^k}(s')\right] - \left(\hat{V}_{2}^k (s_2^k) - V_{2}^{\hat{\pi}^k}(s_2^k)\right)\right)\\ \le & \left(\hat{V}_{3}^k (s_3^k) - V_{3}^{\hat{\pi}^k}(s_3^k)\right) + \sum_{h=1}^2 2\Gamma_h^k(s_h^k,a_h^k) \\ &+ \sum_{h=1}^2\left(\EE_{s'\sim P_h(\cdot \mid s_h^k,a_h^k)}\left[\hat{V}_{h+1}^k (s') - V_{h+1}^{\hat{\pi}^k}(s')\right] - \left(\hat{V}_{h+1}^k (s_{h+1}^k) - V_{h+1}^{\hat{\pi}^k}(s_{h+1}^k)\right)\right)\\ \le& \cdots\\ \le & \sum_{h=1}^H 2\Gamma_h^k(s_h^k,a_h^k) \\ &+ \sum_{h=1}^H\left(\EE_{s'\sim P_h(\cdot \mid s_h^k,a_h^k)}\left[\hat{V}_{h+1}^k (s') - V_{h+1}^{\hat{\pi}^k}(s')\right] - \left(\hat{V}_{h+1}^k (s_{h+1}^k) - V_{h+1}^{\hat{\pi}^k}(s_{h+1}^k)\right)\right) \end{align}\] Now we are ready to show the total regret decomposition. For each episode, we can make the regret decomposition w.r.t. any trajectory collected by a clean agent following policy \(\hat{\pi}^k\). For convenience, we specialize the trajectories to be exactly the ones that are collected by the good agents and are used to calculate the bonus terms. The purpose is, in the future, when we bound the regret, we need to bound the cumulative bonus used in the trajectory. By decomposing the regret w.r.t. the trajectory collected in the algorithm, it is naturally guaranteed that the \((s,a,h)\) tuples that collected a lot by the good agents have lower bonus. This is because with more data collected, we can narrow down the confidence interval and design small but still valid bonus terms.

Because in our MDP definition, the MDP has a deterministic initial distribution, meaning the good agents always have the same starting state: \[\begin{align} &\sum_{k=1}^K \sum_{j \in \mathcal{G}}\left(V_1^*(s_1) - V_1^{\hat{\pi}^k}(s_1)\right) = \sum_{k=1}^K \sum_{j \in \mathcal{G}}\left(V_1^*(s_1^{j,k}) - V_1^{\hat{\pi}^k}(s_1^{j,k})\right) \\ \le & 2\sum_{k=1}^K \sum_{j \in \mathcal{G}}\sum_{h=1}^H\Gamma_h^k(s_h^{j,k},a_h^{j,k}) \\ &+ \sum_{k=1}^K \sum_{j \in \mathcal{G}}\sum_{h=1}^H\left(\EE_{s'\sim P_h(\cdot \mid s_h^{j,k},a_h^{j,k})}\left[\hat{V}_{h+1}^k (s') - V_{h+1}^{\hat{\pi}^k}(s')\right] - \left(\hat{V}_{h+1}^k (s_{h+1}^{j,k}) - V_{h+1}^{\hat{\pi}^k}(s_{h+1}^{j,k})\right)\right) \end{align}\] ◻

10.3 Evenness of clean agents↩︎

We need at least \((2\alpha m + 1)\)-agents to cover \((s,a,h)\) in order to learn the Bellman operator properly. In this section, we show that the agents have “even” coverage on the visited \((s,a,h)\) tuples in each (except a relatively small number) of the episodes. In the following we use \(\tilde{m} := (1-\alpha)m = |\mathcal{G}|\) to denote the number of good agents.

Formally, we have:

Lemma 9 (Even coverage of good agent). For any \((s,a,h,k) \in \mathcal{S}\times\mathcal{A}\times [H] \times [K]\), we define the follow event: \[\mathcal{E}_{even}(s,a, h, k) := \left\{if \sum_{j\in \mathcal{G}} N_h^{j,k}(s,a) \ge 400m\log \frac{2mKSAH}{\delta} , then \max_{i,j \in \mathcal{G}}\frac{N_h^{j,k}(s,a)}{N_h^{i,k}(s,a)} \le 2\right\}\] then, we have: for all \(0<\delta < \frac{1}{4}\) \[\PP\left(\bigcap_{(s,a,h,k) \in \mathcal{S}\times\mathcal{A}\times [H] \times [K]} \mathcal{E}_{even}(s,a, h, k)\right) \ge 1 - 2\delta\]

The event \(\mathcal{E}_{even}(s,a, h, k)\) characterizes that: if in any episode \(k\), a \((s,a,h)\) tuple gets enough coverage from the clean agents, then the coverage of each agent are very close.

See proof of in .

10.3.1 Proof of↩︎

Proof of depends on the concentration of \(N_h^{j,k}(s,a)\):

Lemma 10 (Concentration of counts around empirical mean). For all \(0<\delta < \frac{1}{4}\) \[\begin{align} &\PP\left(\bigcup_{s,a,h,k,j} \left\{ \left|N_h^{j,k}(s,a) - \frac{1}{|\Gcal|}\sum_{j \in \mathcal{G}}N_h^{j,k}(s,a)\right| \right.\right. \\ &> \left.\left. 18\log \frac{2SAHmK}{\delta} + 4\sqrt{\log\frac{2SAHmK}{\delta}} \sqrt{\frac{1}{|\Gcal|}\sum_{j\in\Gcal} N_h^{j,k}(s,a)} \right\}\right) < 2\delta \end{align}\]

Proof of . See . ◻

Proof of . Let \[N_0:= 400m\log \frac{2mKSAH}{\delta}\] For any \((s,a,h,k) \in \mathcal{S} \times \mathcal{A} \times [H] \times [K]\), define events: \[\begin{align} \mathcal{E}_1(s,a,h,k) := & \left\{\sum_{j\in\mathcal{G}} N_h^{j,k}(s,a)\ge N_0\right\} \\ \mathcal{E}_2(s,a,h,k) := & \left\{\max_{i,j \in \mathcal{G}}\frac{N_h^{j,k}(s,a)}{N_h^{i,k}(s,a)} \le 2\right\} \end{align}\] Recall: \[\mathcal{E}_{even}(s,a, h, k) := \left\{if \sum_{j\in \mathcal{G}} N_h^{j,k}(s,a) \ge 400m\log \frac{2mKSAH}{\delta} , then \max_{i,j \in \mathcal{G}}\frac{N_h^{j,k}(s,a)}{N_h^{i,k}(s,a)} \le 2\right\}\] Then we can rewrite even \(\mathcal{E}_{even}(s,a, h, k)\) as: \[\mathcal{E}_{even}(s,a, h, k) = \overline{\mathcal{E}_1(s,a,h,k)} \cup \mathcal{E}_2(s,a,h,k)\] We first show that of there are two \(N_h^{j,k}\)’s, whose ratio exceed \(2\), then there must be some \(N_h^{j,k}\) that deviates a lot from the empirical mean of \(N_h^{j,k}\)’s: \[\begin{align} &\overline{\mathcal{E}_2(s,a,h,k)} = \left\{\max_{i,j \in \mathcal{G}}\frac{N_h^{j,k}(s,a)}{N_h^{i,k}(s,a)} > 2\right\} \\ \subseteq &\bigcup_{i \in \mathcal{G}} \left\{N_h^{i,k}(s,a) > \frac{498}{400}\frac{1}{|\Gcal|}\sum_{j \in \mathcal{G}}N_h^{j,k}(s,a)\right\} \cup \bigcup_{i \in \mathcal{G}} \left\{N_h^{i,k}(s,a) < \frac{302}{400}\frac{1}{|\Gcal|}\sum_{j \in \mathcal{G}}N_h^{j,k}(s,a)\right\} \\ = &\bigcup_{i \in \mathcal{G}} \left\{N_h^{i,k}(s,a) - \frac{1}{|\Gcal|}\sum_{j \in \mathcal{G}}N_h^{j,k}(s,a)> \frac{98}{400}\frac{1}{|\Gcal|}\sum_{j \in \mathcal{G}}N_h^{j,k}(s,a)\right\} \\ &\cup \bigcup_{i \in \mathcal{G}} \left\{N_h^{i,k}(s,a) - \frac{1}{|\Gcal|}\sum_{j \in \mathcal{G}}N_h^{j,k}(s,a)< -\frac{98}{400}\frac{1}{|\Gcal|}\sum_{j \in \mathcal{G}}N_h^{j,k}(s,a)\right\} \\ =& \bigcup_{i \in \mathcal{G}} \left\{\left|N_h^{i,k}(s,a) - \frac{1}{|\Gcal|}\sum_{j \in \mathcal{G}}N_h^{j,k}(s,a)\right|> \frac{98}{400}\frac{1}{|\Gcal|}\sum_{j \in \mathcal{G}}N_h^{j,k}(s,a)\right\} \label{eq:deviate32from32mean} \end{align}\tag{22}\] To show that \(\mathcal{E}_{even}(s,a, h, k)\) happens w.h.p.: \[\begin{align} &\PP\left(\bigcup_{s,a,h,k}\overline{\mathcal{E}_{even}(s,a, h, k)}\right) = \PP\left(\bigcup_{s,a,h,k}\overline{\overline{\mathcal{E}_1(s,a,h,k)} \cup \mathcal{E}_2(s,a,h,k)}\right)\\ = & \PP\left(\bigcup_{s,a,h,k}{\mathcal{E}_1(s,a,h,k)} \cap \overline{\mathcal{E}_2(s,a,h,k)}\right)\\ \le & \PP\left(\exists s,a,h,k,\sum_{j\in\mathcal{G}} N_h^{j,k}(s,a)\ge N_0, \right.\\ &\left.\exists i \in \mathcal{G}, \left|N_h^{i,k}(s,a) - \frac{1}{|\Gcal|}\sum_{j\in\mathcal{G}} N_h^{j,k}(s,a)\right| > \frac{98}{400}\frac{1}{|\Gcal|}\sum_{j\in\mathcal{G}} N_h^{j,k}(s,a)\right) \\ & (By \prettyref{eq:deviate32from32mean}) \\ \le & \PP\left(\exists s,a,h,k,i\left|N_h^{i,k}(s,a) - \frac{1}{|\Gcal|}\sum_{j\in\mathcal{G}} N_h^{j,k}(s,a)\right| \right.\\ &\left.> \frac{18}{400}\frac{1}{|\Gcal|}N_0 + 4\sqrt{\frac{1}{400}\frac{1}{|\Gcal|}N_0}\sqrt{\frac{1}{|\Gcal|}\sum_{j\in\mathcal{G}} N_h^{j,k}(s,a)}\right) \\ = & \PP\left(\exists s,a,h,k,i\left|N_h^{i,k}(s,a) - \frac{1}{|\Gcal|}\sum_{j\in\mathcal{G}} N_h^{j,k}(s,a)\right| \right.\\ &\left.> 18\log \frac{2 mKSAH}{\delta} + 4\sqrt{\log \frac{2 mKSAH}{\delta}} \sqrt{\frac{1}{|\Gcal|}\sum_{j\in\mathcal{G}} N_h^{j,k}(s,a)} \right) \\ < &2\delta \quad (By \prettyref{lem:concen32of32cts}) \end{align}\] ◻

10.3.2 Proof of↩︎

The high level ideas are:

For each \(s,a,h\),
- for each \(j\in\mathcal{G}\), define centered \(N_h^{j,k}(s,a)\) as a martingale;
- define centered \(\sum_{j\in\mathcal{G}} N_h^{j,k}(s,a)\) as a martingale;
apply a modified Bernstein type of martingale concentration bound for both centered \(N_h^{j,k}(s,a)\)’s and centered \(\sum_{j\in\mathcal{G}} N_h^{j,k}(s,a)\) (see and );
because \(N_h^{j,k}(s,a)\) and \(\frac{1}{\tilde{m}}\sum_{j\in\mathcal{G}} N_h^{j,k}(s,a)\) have the same mean, we can use triangular inequality to show these two terms are close, and the distance is bounded by the variance term in Bernstein inequality.
Bernstein on \(\frac{1}{\tilde{m}}\sum_{j\in\mathcal{G}} N_h^{j,k}(s,a)\) also allow us to bound its variance in terms of itself.
We can get our result by combining and .

Lemma 11 (Concentration of each \(N_h^{j,k}(s,a)\)). For all \(0<\delta \le1/4\), with probability at least \(1-\delta\), for all \((s,a,h,j,k)\in\Scal\x\Acal\x[H]\x\Gcal\x[K]\): \[\label{eq:nj32conc} \left|N_h^{j,k}(s,a) - \sum_{t=1}^k d_h^{\hat{\pi}^{t}}(s,a)\right| < 3\log \frac{2SAHmK}{\delta} + \sqrt{2\sum_{t=1}^k d_h^{\hat{\pi}^{t}}(s,a)\log\frac{2SAHmK}{\delta}}\qquad{(4)}\]

Proof of . See ◻

Lemma 12 (Concentration of each \(\frac{1}{\tilde{m}}\sum_{j\in\mathcal{G}} N_h^{j,k}(s,a)\)). For all \(0<\delta \le1/4\), with probability at least \(1-\delta\), for all \((s,a,h,k) \in \Scal\x\Acal\x[H]\x[K]\): \[\label{eq:nj32ave32conc} \left| \sum_{j\in\Gcal} N_h^{j,k}(s,a)- |\Gcal|\sum_{t=1}^k d_h^{\hat{\pi}^t}(s,a) \right| < 3\log \frac{2SAHmK}{\delta} + \sqrt{2|\Gcal|\sum_{t=1}^k d_h^{\hat{\pi}^{t}}(s,a)\log\frac{2SAHmK}{\delta}}\qquad{(5)}\]

Proof of . See ◻

Proof of . Let \(\Ecal_{N}\) the intersection of the events in and . Then by and , \(\Ecal_{N}\) happens with probability at least \(1-2\delta\). By , \[\label{eq:sum32d32bd} \sqrt{\sum_{t=1}^k d_h^{\hat{\pi}^{t}}(s,a)} \le 4\sqrt{\log \frac{2SAHmK}{\delta} } + \sqrt{\frac{1}{|\Gcal|}\sum_{j\in\Gcal} N_h^{j,k}(s,a)}\tag{23}\] By and , for all \(s,a,h,j,k\) \[\begin{align} & \left| \frac{1}{|\Gcal|}\sum_{j'\in\Gcal} N_h^{j',k}(s,a)- N_h^{j,k}(s,a) \right| \\ \le & \left|N_h^{j,k}(s,a) - \sum_{t=1}^k d_h^{\hat{\pi}^{t}}(s,a)\right| + \left| \frac{1}{|\Gcal|}\sum_{j'\in\Gcal} N_h^{j',k}(s,a)- \sum_{t=1}^k d_h^{\hat{\pi}^t}(s,a) \right|\\ \le & 6\log \frac{2SAHmK}{\delta} + 2\sqrt{2\sum_{t=1}^k d_h^{\hat{\pi}^{t}}(s,a)\log\frac{2SAHmK}{\delta}}\\ \le & 6\log \frac{2SAHmK}{\delta} + 2\sqrt{2\log\frac{2SAHmK}{\delta}} \left(4\sqrt{\log \frac{2SAHmK}{\delta} } + \sqrt{\frac{1}{|\Gcal|}\sum_{j\in\Gcal} N_h^{j,k}(s,a)}\right)\\ \le & 18\log \frac{2SAHmK}{\delta} + 4\sqrt{\log\frac{2SAHmK}{\delta}} \sqrt{\frac{1}{|\Gcal|}\sum_{j\in\Gcal} N_h^{j,k}(s,a)} \end{align}\] ◻

10.3.3 Proof of↩︎

Proof of . For each fixed \((s,a,h,j) \in \Scal \x \Acal \x [H] \x \Gcal\): for all \(t \in [K]\), define \[\Fcal_k := \sigma\left(\bigcup_{t\le k}\bigcup_{j \in [m]}\left\{\left(s_{h}^{j,t},a_{h}^{j,t},r_{h}^{j,t},s_{h+1}^{j,t}\right)\right\}_{h=1}^H\right).\] Let \[\begin{align} S_h^{j,k}(s,a) = & N_h^{j,k}(s,a) - \sum_{t=1}^k d_h^{\hat{\pi}^{t}}(s,a)\\ T_h^{j,k}(s,a) = &\sum_{t=1}^k d_h^{\hat{\pi}^{t}}(s,a)\left(1-d_h^{\hat{\pi}^{t}}(s,a)\right) \end{align}\] Then \(\left\{\left(\Fcal_k, S_h^{j,k}(s,a)\right)\right\}_{t=k}^K\) is a martingale. Since \(d_h^{\hat{\pi}^{k}}(s,a)\) depends on \(\hat{\pi}^k\), which is calculated use data in the first \(k-1\) episodes, then \(d_h^{\hat{\pi}^{k}}(s,a) \in \Fcal_{k-1}\). By , \[\begin{align} &\PP\left(\bigcup_{k=1}^K\left\{|S_h^{j,k}(s,a)| \ge 3\log \frac{2SAHmK}{\delta} + \sqrt{2\sum_{t=1}^k d_h^{\hat{\pi}^{t}}(s,a)\log\frac{2SAHmK}{\delta}}\right\} \right)\\ \le & \PP\left(\bigcup_{k=1}^K\left\{|S_h^{j,k}(s,a)| \ge 3\log \frac{2SAHmK}{\delta} + \sqrt{2T_h^{j,k}(s,a)\log\frac{2SAHmK}{\delta}}\right\} \right) \le \frac{\delta}{SAHm} \end{align}\] By union bound, with probability at least \(1-\delta\), for all \((s,a,h,j,k)\in\Scal\x\Acal\x[H]\x\Gcal\x[K]\): \[|S_h^{j,k}(s,a)| < 3\log \frac{2SAHmK}{\delta} + \sqrt{2\sum_{t=1}^k d_h^{\hat{\pi}^{t}}(s,a)\log\frac{2SAHmK}{\delta}}\] ◻

10.3.4 Proof of↩︎

Proof of . During the data collecting process, the agents are allowed to collect data simultaneously. For analysis purpose, we artificially order the data in the following sequence: \[\label{eq:E32seq32Njs} E^{1,1}, E^{2,1}, \ldots, E^{m,1}, E^{1,2}, \ldots, E^{m,2}, \ldots, E^{1,K}, \ldots, E^{m,K}\tag{24}\] where \(E^{j,k} := \left\{\left(s_{h}^{j,k},a_{h}^{j,k},r_{h}^{j,k},s_{h+1}^{j,k}\right)\right\}_{h=1}^H\). Let \[\Fcal_t = \sigma\left(\bigcup_{j,ks.t. m(k-1) + j \le t}E^{j,k}\right).\] Then \(\left\{\Fcal_t\right\}_{t=0}^{mK}\) forms a valid filtration. Define the following functions to map from sequence index to agent index and episode index: \[\begin{align} \mathcal{J}(t) := t - m\left(\lceil t/m \rceil - 1\right), \quad \mathcal{K}(t) := \lceil t/m \rceil \end{align}\]

For each fixed \((s,a,h) \in \Scal \x \Acal \x [H]\), for all \(t \in [mK]\), we define \(S_h^{\Gcal,t}(s,a)\) as the (centered) total counts of \((s,a,h)\) collected by all good agents up to time \(t\). The \(t\)-th term in could be in the center of an episode, meaning some agents have not collected their trajectories yet. So we need to treat the agents differently: Let \[\begin{align} S_h^{\Gcal,t}(s,a) = & \sum_{j\in \Gcal, j \le \Jcal(t)} \left( N_h^{j,\Kcal(t)}(s,a) - \sum_{t=1}^{\Kcal(t)} d_h^{\hat{\pi}^{t}}(s,a) \right)\\ &+ \sum_{j\in \Gcal, j > \Jcal(t)} \left( N_h^{j,\Kcal(t)-1}(s,a) - \sum_{t=1}^{\Kcal(t)-1} d_h^{\hat{\pi}^{t}}(s,a) \right) \end{align}\] Then \(\left\{\left(\Fcal_t, S_h^{\Gcal,t}(s,a)\right)\right\}_{t=1}^{mK}\) is a martingale. Similar to , define \[\begin{align} T_h^{\Gcal,t}(s,a) = & \sum_{j\in \Gcal, j \le \Jcal(t)} \sum_{t=1}^{\Kcal(t)} d_h^{\hat{\pi}^{t}}(s,a)\left(1-d_h^{\hat{\pi}^{t}}(s,a)\right)\\ &+ \sum_{j\in \Gcal, j > \Jcal(t)} \sum_{t=1}^{\Kcal(t)-1} d_h^{\hat{\pi}^{t}}(s,a)\left(1-d_h^{\hat{\pi}^{t}}(s,a)\right) \end{align}\] Then by , \[\begin{align} &\PP\left(\bigcup_{k\in[K]} \left\{ \left| \sum_{j\in\Gcal} N_h^{j,k}(s,a)- |\Gcal|\sum_{t=1}^k d_h^{\hat{\pi}^t}(s,a) \right| \ge 3\log \frac{2SAHmK}{\delta} \right.\right.\\ & \left.\left.+ \sqrt{2|\Gcal|\sum_{t=1}^k d_h^{\hat{\pi}^{t}}(s,a)\log\frac{2SAHmK}{\delta}} \right\} \right) \\ \le &\PP\left(\bigcup_{k\in[K]} \left\{ \left| \sum_{j\in\Gcal} N_h^{j,k}(s,a)- |\Gcal|\sum_{t=1}^k d_h^{\hat{\pi}^t}(s,a) \right| \ge 3\log \frac{2SAHmK}{\delta} \right.\right.\\ & \left.\left.+ \sqrt{2|\Gcal|\sum_{t=1}^k d_h^{\hat{\pi}^{t}}(s,a)\left(1-d_h^{\hat{\pi}^{t}}(s,a)\right)\log\frac{2SAHmK}{\delta}} \right\} \right) \\ \le & \PP\left(\bigcup_{k=1}^{mK}\left\{|S_h^{\Gcal,k}(s,a)| \ge 3\log \frac{2SAHmK}{\delta} + \sqrt{2T_h^{\Gcal,k}(s,a)\log\frac{2SAHmK}{\delta}}\right\} \right) \\ \le & \frac{\delta}{SAH} \end{align}\] By union bound, with probability at least \(1-\delta\), for all \((s,a,h,k) \in \Scal\x\Acal\x[H]\x[K]\): \[\left| \sum_{j\in\Gcal} N_h^{j,k}(s,a)- |\Gcal|\sum_{t=1}^k d_h^{\hat{\pi}^t}(s,a) \right| < 3\log \frac{2SAHmK}{\delta} + \sqrt{2|\Gcal|\sum_{t=1}^k d_h^{\hat{\pi}^{t}}(s,a)\log\frac{2SAHmK}{\delta}}\] ◻

11 Proof of↩︎

By the following lemma, we can upper bound the suboptimality by the cumulative bonuses:

Lemma 13. [Suboptimality for Pessimistic Value Iteration, Lemma 3.2 in [26] and Theorem 4.2 in [32]] Under the event \(\mathcal{E}\) that the \(\Gamma_h(s,a)\) satisfies the required property of bounding the Bellman error, i.e. \(|\hat{Q}_h(s,a)-(\Bell\hat{V}_{h+1})(s,a)| \leq \Gamma_h(s,a), \forall h\in[H], (s,a) \in \mathcal{S} \times \mathcal{A}\) then against any comparator policy \(\tilde{\pi}\), it achieves \[\begin{align} \label{eq:pess95opt} \subopt(\hat{\pi},\tilde{\pi})\leq 2\sum_{h=1}^H\EE_{d^{\tilde{\pi}}}[\Gamma_h(s_h,a_h)] \end{align}\qquad{(6)}\]

Recall that for all \((s,a,h)\in\Scal\x\Acal\x[H]\), \[N_h^j(s,a) := \sum_{k \in [K_j]}\one\left\{(s_h^{j,k}, a_h^{j,k}) = (s, a)\right\}, \quad \forall j \in [m].\] and \(N_h^{\operatorname{cut}}(s,a)\) is the \((2\alpha m +1)\)-largest among \(\left\{N_h^j(s,a)\right\}_{j\in[m]}\). \(N_h^{\Gcal, \cut_1}(s,a)\) is the \((\alpha m+1)\)-th largest of \(\left\{N_h^j(s,a)\right\}_{j\in\Gcal}\) and \(N_h^{\Gcal, \cut_2}(s,a)\) is the \((2\alpha m+1)\)-th largest of \(\left\{N_h^j(s,a)\right\}_{j\in\Gcal}\). The bonuses are given by:

If \(N_h^{\operatorname{cut}}(s,a)=0\) \[\Gamma_h(s,a) = H - h + 1;\]
If \(N_h^{\operatorname{cut}}(s,a)>0\) \[\begin{align} \Gamma_h(s,a) := & \frac{2{(H-h+1)}}{\sqrt{\sum_{j \in [m]}\tilde{N}_h^{j}(s,a)}} \sqrt{2\log\frac{2SAH}{\delta}} \\ &+ \frac{8\alpha m\sqrt{N_h^{\operatorname{cut}}(s,a)}}{\sum_{j \in [m]}\tilde{N}_h^{j}(s,a)} {(H-h+1)}\sqrt{2\log\frac{2mSAH}{\delta}} \end{align}\] Where \[\tilde{N}_h^{j}(s,a) = \max\left(N_h^{\cut}(s,a), N_h^{j}(s,a)\right).\]

Proof of . We first show that with probability at least \(1-\delta\), \[\label{eq:pess32bd} |(\hat{\Bell}_h\hat{V}_{h+1})(s,a)-(\Bell_h\hat{V}_{h+1})(s,a)| \leq \Gamma_h(s,a), \quad \forall (s,a) \in \mathcal{S}\times \mathcal{A}, \forall h\in[H]\tag{25}\] where \(\Gamma_h(s,a)\) is defined in .

if \(N_h^{\cut}(s,a) = 0\), by definition, \((\hat{\Bell}_h\hat{V}_{h+1})(s,a) = 0\). By definition of \(\hat{V}_h\) and \(\Bell_h\), \((\Bell_h\hat{V}_{h+1})(s,a) \in [0, H-h+1]\), thus holds;
if \(N_h^{\cut}(s,a) > 0\), for any fixed \(h \in [H]\), \((s,a) \in \mathcal{S} \times \mathcal{A}\), \(f: \mathcal{S} \to [0,H]\). Because \((\hat{\Bell}_h f)(s,a)\) is bounded and thus sub-Gaussian, we can use to upper bound \(|(\hat{\Bell}_h f)(s,a)-(\Bell_h f)(s,a)|\): \[\begin{align} \PP\left( \left|(\hat{\Bell}_h f)(s,a)-(\Bell_h f)(s,a)\right| \ge \Gamma_h(s,a) \right) \le \frac{\delta}{HSA} \end{align}\]

Thus \[\begin{align} &\PP\left(|(\hat{\Bell}_h\hat{V}_{h+1})(s,a)-(\Bell_h\hat{V}_{h+1})(s,a)| \ge \Gamma_h(s,a)\right) \\ = & \int_{[0,H]^\Scal} \PP\left( \left.|(\hat{\Bell}_h\hat{V}_{h+1})(s,a)-(\Bell_h\hat{V}_{h+1})(s,a)| \ge \Gamma_h(s,a) \right| \hat{V}_{h+1}(\cdot)\right) d \PP(\hat{V}_{h+1}(\cdot)) \\ \le & \frac{\delta}{HSA} \end{align}\] By union bound, with probability at least \(1-\delta\), \[|(\hat{\Bell}_h\hat{V}_{h+1})(s,a)-(\Bell_h\hat{V}_{h+1})(s,a)| \leq \Gamma_h(s,a), \quad \forall (s,a) \in \mathcal{S}\times \mathcal{A}, \forall h\in[H]\]

Then, by , with probability at least \(1-\delta\), \[\begin{align} \label{eq:pess95opt32in32proof} &\subopt(\hat{\pi},\tilde{\pi})\leq 2\sum_{h=1}^H\EE_{d^{\tilde{\pi}}}[\Gamma_h(s_h,a_h)] \\ =& 2\sum_{h=1}^H\EE_{d^{\tilde{\pi}}}\left[\Gamma_h(s_h,a_h)\one{\left\{N_h^{\Gcal,\cut_2}(s_h,a_h) = 0\right\}}\right] \\ &+ 2\sum_{h=1}^H\EE_{d^{\tilde{\pi}}}\left[\Gamma_h(s_h,a_h)\one\left\{N_h^{\Gcal,\cut_2}(s_h,a_h) > 0\right\}\right] \\ =:&\mathscr{A}_1 + \mathscr{A}_2. \end{align}\tag{26}\] By definition of \(p^{\Gcal,0}\) in , \[\mathscr{A}_1 \le 2H p^{\Gcal,0}\] \[\begin{align} \mathscr{A}_2 = & 2\sum_{h=1}^H\EE_{d^{\tilde{\pi}}}\left[\Gamma_h(s_h,a_h)\one\left\{N_h^{\Gcal,\cut_2}(s_h,a_h) > 0\right\}\right] \\ \le & 2\sum_{h=1}^H\EE_{d^{\tilde{\pi}}}\left[\left(\frac{2{(H-h+1)}}{\sqrt{\sum_{j \in \Gcal}\tilde{N}_h^{j}(s,a)}} \sqrt{2\log\frac{2SAH}{\delta}}\right.\right. \\ &\left.\left.+ \frac{8\alpha m\sqrt{N_h^{\operatorname{cut}}(s,a)}}{\sum_{j \in \Gcal}\tilde{N}_h^{j}(s,a)} {(H-h+1)}\sqrt{2\log\frac{2mSAH}{\delta}} \right)\one\left\{N_h^{\Gcal,\cut_2}(s_h,a_h) > 0\right\}\right]. \end{align}\] By the definition of \(\kappa_{\text{even}}\) in : for \(a = \tilde{\pi}(s)\), \[\begin{align} \frac{1}{\sqrt{\sum_{j \in \Gcal}\tilde{N}_h^{j}(s,a)}} = & \frac{\sqrt{\sum_{j \in \Gcal}N_h^{j}(s,a)}}{\sqrt{\sum_{j \in \Gcal}\tilde{N}_h^{j}(s,a)}} \frac{1}{\sqrt{\sum_{j \in \Gcal}N_h^{j}(s,a)}} \\ \le & \frac{\sqrt{\sum_{j \in \Gcal}N_h^{j}(s,a)}}{\sqrt{\sum_{j \in \Gcal}\tilde{N}_h^{j,\cut_2}(s,a)}} \frac{1}{\sqrt{\sum_{j \in \Gcal}N_h^{j}(s,a)}}\\ \le &\frac{\sqrt{\kappa_{\text{even}}}}{\sqrt{\sum_{j \in \Gcal}N_h^{j}(s,a)}} \end{align}\] and \[\begin{align} \frac{ m\sqrt{N_h^{\operatorname{cut}}(s,a)}}{\sum_{j \in \Gcal}\tilde{N}_h^{j}(s,a)} &\le\frac{1}{\sqrt{1-\alpha}} \sqrt{ \frac{\sum_{j \in \Gcal}N_h^{j}(s,a)}{\sum_{j \in \Gcal}\tilde{N}_h^{j}(s,a)} \frac{ m(1-\alpha){N_h^{\operatorname{cut}}(s,a)}}{\sum_{j \in \Gcal}\tilde{N}_h^{j}(s,a)} } \frac{\sqrt{m}}{\sqrt{\sum_{j \in \Gcal}N_h^{j}(s,a)}}\\ &\le \sqrt{ \frac{\sum_{j \in \Gcal}N_h^{j}(s,a)}{\sum_{j \in \Gcal}\tilde{N}_h^{j,\cut_2}(s,a)} \frac{ m(1-\alpha){N_h^{\Gcal,\cut_1}(s,a)}}{\sum_{j \in \Gcal}\tilde{N}_h^{j,\cut_2}(s,a)} } \frac{\sqrt{2m}}{\sqrt{\sum_{j \in \Gcal}N_h^{j}(s,a)}} \\ \le & \frac{\sqrt{2\kappa_{\text{even}}m}}{\sqrt{\sum_{j \in \Gcal}N_h^{j}(s,a)}} \end{align}\] Thus \[\begin{align} \mathscr{A}_2 \le & 2\sum_{h=1}^H\EE_{d^{\tilde{\pi}}}\Bigg[\left(\frac{2}{\sqrt{\sum_{j \in \Gcal}\tilde{N}_h^{j}(s,a)}} + \frac{8\alpha m\sqrt{N_h^{\operatorname{cut}}(s,a)}}{\sum_{j \in \Gcal}\tilde{N}_h^{j}(s,a)} \right)H\sqrt{2\log\frac{2mSAH}{\delta}} \\ & \one\left\{N_h^{\Gcal,\cut_2}(s_h,a_h) > 0\right\}\Bigg] \\ \le & 2\sum_{h=1}^H\EE_{d^{\tilde{\pi}}} \left[ \frac{\left(2+8\alpha\sqrt{2m}\right)\sqrt{\kappa_{\text{even}}}}{\sqrt{\sum_{j \in \Gcal}N_h^{j}(s,a)}} H\sqrt{2\log\frac{2mSAH}{\delta}} \one\left\{N_h^{\Gcal,\cut_2}(s_h,a_h) > 0\right\} \right]\\ \le & 2\left(2+8\alpha\sqrt{2m}\right)\sqrt{\kappa_{\text{even}}} H\sqrt{2\log\frac{2mSAH}{\delta}} \sum_{h=1}^H\EE_{d^{\tilde{\pi}}} \left[ \frac{\one\left\{N_h^{\Gcal,\cut_2}(s_h,a_h) > 0\right\}}{\sqrt{\sum_{j \in \Gcal}N_h^{j}(s,a)}} \right] \end{align}\] Recall that \(\Ccal_h = \left\{s | N_h^{\Gcal, \cut_2}(s,\tilde{\pi}(s)) >0\right\}\). By Cauchy–Schwarz inequality and the definition of \(\kappa\) in , \[\begin{align} \EE_{d^{\tilde{\pi}}} \left[ \frac{\one\left\{N_h^{\Gcal,\cut_2}(s_h,a_h) > 0\right\}}{\sqrt{\sum_{j \in \Gcal}N_h^{j}(s,a)}} \right] \le & \sqrt{ \EE_{d^{\tilde{\pi}}} \left[ \frac{\one\left\{N_h^{\Gcal,\cut_2}(s_h,a_h) > 0\right\}}{{\sum_{j \in \Gcal}N_h^{j}(s,a)}} \right]} \\ = & \sqrt{ \sum_{s \in \Ccal_h} \frac{d_h^{\tilde{\pi}}(s)}{{\sum_{j \in \Gcal}N_h^{j}(s,a)}} }\\ = & \sqrt{ \sum_{s \in \Ccal_h} \frac{d_h^{\tilde{\pi}}(s)}{{\sum_{j \in \Gcal}N_h^{j}(s,a)}/\sum_{j\in\Gcal}K_j} \frac{1}{\sum_{j\in\Gcal}K_j} }\\ \le & \sqrt{ \sum_{s \in \Ccal_h} \frac{\kappa}{\sum_{j\in\Gcal}K_j} } \le \sqrt{ \frac{\kappa S}{\sum_{j\in\Gcal}K_j} } \end{align}\] In conclusion, \[\begin{align} \subopt(\hat{\pi}, \tilde{\pi}) \le & \mathscr{A}_1 + \mathscr{A}_2\\ \le & 2H p^{\Gcal,0} + 2\left(2+8\alpha\sqrt{2m}\right)\frac{\sqrt{\kappa\kappa_{\text{even}}S}}{\sqrt{\sum_{j\in\Gcal}K_j}} H^2\sqrt{2\log\frac{2mSAH}{\delta}} \\ = & 2H p^{\Gcal,0} + O\left( \sqrt{\kappa\kappa_{\text{even}}}H^2\sqrt{S} \frac{1+\alpha\sqrt{m}}{\sqrt{\sum_{j\in\Gcal}K_j}} \sqrt{\log\frac{mSAH}{\delta}} \right) \end{align}\] ◻

12 Useful inequalities↩︎

Theorem 6 (Bernstein type of bound for martingale, Theorem 1.6 of [55]). Let \((\Omega, \mathcal{F}, P)\) be a probability triple. Let \(\mathcal{F}_0\subset\mathcal{F}_1\subset \cdots\) be an increasing sequence of sub-\(\sigma\)-fields of \(\mathcal{F}\). Let \(X_1, X_2, \ldots\) be random variables on \((\Omega, \mathcal{F}, P)\), such that \(X_n\) is \(\mathcal{F}_n\) measurable. Let \(V_n = \VV\left[X_n | \mathcal{F}_{n-1}\right]\). Assume \(|X_n| \le 1\) and \(\EE[X_n | \mathcal{F}_{n-1}]\) = 0. Let \[\begin{align} &S_n = X_1 + \cdots + X_n\\ &T_n = V_1 + \cdots + V_n, \end{align}\] where \(S_0 = T_0 = 0\). Then, for any \(a>0\), \(b>0\), \[\PP\left(|S_n| \ge aandT_n \le bfor some n \right) \le 2\exp\left(-\frac{a^2}{2(a+b)}\right).\]

By union bound and partition, we can get a more useful version of .

We first present a result, which shows: given, \[\PP\left(X \ge t, Y\le t \right) \le \delta(t)\] We can bound \(\PP\left(X \ge Y \right)\) up to some error.

Lemma 14. Let \(\{A_n\}_{n=1}^N\) and \(\{B_n\}_{n=1}^N\) be two sequences of random variables. We don’t make any assumption about the independence. Assume

\(\forall n\), \(0 \le B_n \le n M\) almost surely;
\(\forall \delta > 0\), \(f_\delta : \RR_+ \mapsto \RR_+\), \(f_{\delta}(\cdot)\) monotonic increasing,

If for all \(t > 0\), \[\label{eq:prob32under32t} \P\left(\bigcup_{n=1}^N \left\{|A_n| \ge f_{\delta}(t), B_n \le t\right\}\right) \le \delta\qquad{(7)}\] Then for any \(\epsilon > 0\), \[\P\left(\bigcup_{n=1}^N \left\{|A_n| \ge f_{\delta}(B_n+ \epsilon) \right\}\right) \le NM\lceil 1/ \epsilon \rceil\delta\]

Proof. See proof in . ◻

Corollary 1. Under the assumption of , suppose \(X_n\) terminate at \(n = N\). Then, for all \(0 < \delta < {2}{\exp(-2)}\), \[\begin{align} & \PP\left(\bigcup_{n=1}^N\left\{|S_n| \ge 3\log \frac{2N}{\delta} + \sqrt{2T_n\log\frac{2N}{\delta}}\right\} \right) \le \delta \end{align}\]

Proof of . Let \(\frac{\delta}{N} = 2\exp\left(-\frac{a^2}{2(a+b)}\right)\) then \[a = \log \frac{2N}{\delta} + \sqrt{\log^2\frac{2N}{\delta} + 2b\log\frac{2N}{\delta}}\] by , For all \(b > 0\), \[\PP\left(|S_n| \ge \log \frac{2N}{\delta} + \sqrt{\log^2\frac{2N}{\delta} + 2b\log\frac{2N}{\delta}},andT_n \le bfor some n \right) \le \delta/N\] In , let:

\(A_n = S_n\), \(B_n = T_n\), \(M=1\)
\(\epsilon = \frac{1}{2}\log\frac{2N}{\delta}\)
\(f_\delta(x) = \log \frac{2N}{\delta} + \sqrt{\log^2\frac{2N}{\delta} + 2x\log\frac{2N}{\delta}}\)

Because \(0 < \delta < 2\exp(-2)\), \(\epsilon \ge 1\). then, we get: \[\begin{align} & \PP\left(\bigcup_{n=1}^N\left\{|S_n| \ge 3\log \frac{2N}{\delta} + \sqrt{2T_n\log\frac{2N}{\delta}}\right\} \right) \\ \le & \PP\left(\bigcup_{n=1}^N\left\{|S_n| \ge \log \frac{2N}{\delta} + \sqrt{2\log^2\frac{2N}{\delta} + 2T_n\log\frac{2N}{\delta}}\right\} \right) \\ \le & N\lceil 1/ \epsilon \rceil\frac{\delta}{N} \le \delta \end{align}\] ◻

12.1 Proof for↩︎

Proof of . For discrete random variable, we can just conditioning on each possible value of \(B_n\) and use a union bound. Here, because \(B_n\) can be continuous random variable, we divide the range of \(B_n\) into intervals. And upper bound the target by law of total probability.

For all \(n\), let: \[0 < \frac{1}{\lceil 1/ \epsilon \rceil} < \frac{2}{\lceil 1/ \epsilon \rceil} < \cdots < \frac{nM\lceil 1/ \epsilon \rceil}{\lceil 1/ \epsilon \rceil} = nM\] Be a partition of interval \([0, nM]\). Let \(I_i := \left[\frac{i-1}{\lceil 1/ \epsilon \rceil}, \frac{i}{\lceil 1/ \epsilon \rceil}\right],i = 1, \ldots, nM\lceil 1/ \epsilon \rceil\) be a set of intervals. Note that, \(\bigcup_{i = 1}^{nM\lceil 1/ \epsilon \rceil}I_i = [0,nM]\).

Then \[\begin{align} &\bigcup_{n=1}^N \left\{|A_n| \ge f_{\delta}(B_n + \epsilon)\right\} = \bigcup_{n=1}^N \bigcup_{i=1}^{nM\lceil 1/ \epsilon \rceil}\left\{|A_n| \ge f_{\delta}(B_n+ \epsilon) , B_n \in I_i\right\}\\ = & \bigcup_{n=1}^N \bigcup_{i=1}^{nM\lceil 1/ \epsilon \rceil}\left\{|A_n| \ge f_{\delta}(B_n+ \epsilon) , \frac{i-1}{\lceil 1/ \epsilon \rceil} \le B_n \le \frac{i}{\lceil 1/ \epsilon \rceil}\right\} \\ \subseteq & \bigcup_{n=1}^N \bigcup_{i=1}^{nM\lceil 1/ \epsilon \rceil}\left\{|A_n| \ge f_{\delta}(\frac{i}{\lceil 1/ \epsilon \rceil}) , B_n \le \frac{i}{\lceil 1/ \epsilon \rceil}\right\} \\ \subseteq & \bigcup_{n=1}^N \bigcup_{i=1}^{NM\lceil 1/ \epsilon \rceil}\left\{|A_n| \ge f_{\delta}(\frac{i}{\lceil 1/ \epsilon \rceil}) , B_n \le \frac{i}{\lceil 1/ \epsilon \rceil}\right\} \\ = & \bigcup_{i=1}^{NM\lceil 1/ \epsilon \rceil}\bigcup_{n=1}^N \left\{|A_n| \ge f_{\delta}(\frac{i}{\lceil 1/ \epsilon \rceil}) , B_n \le \frac{i}{\lceil 1/ \epsilon \rceil}\right\} \end{align}\] Thus \[\begin{align} \P\left(\bigcup_{n=1}^N \left\{|A_n| \ge f_{\delta}(B_n+ \epsilon) \right\}\right) \le &\sum_{i=1}^{NM\lceil 1/ \epsilon \rceil} \PP\left(\bigcup_{n=1}^N \left\{|A_n| \ge f_{\delta}(\frac{i}{\lceil 1/ \epsilon \rceil}) , B_n \le \frac{i}{\lceil 1/ \epsilon \rceil}\right\}\right)\\ \le& NM\lceil 1/ \epsilon \rceil\delta \quad \left(By \pref{eq:prob32under32t}\right) \end{align}\] ◻

References↩︎

[1]

Joost Verbraeken, Matthijs Wolting, Jonathan Katzy, Jeroen Kloppenburg, Tim Verbelen, and Jan S Rellermeyer. A survey on distributed machine learning. ACM Computing Surveys (CSUR), 53 (2): 1–33, 2020.

[2]

Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch sgd: Training imagenet in 1 hour. arXiv preprint arXiv:1706.02677, 2017.

[3]

Martı́n Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, et al. Tensorflow: Large-scale machine learning on heterogeneous distributed systems. arXiv preprint arXiv:1603.04467, 2016.

[4]

Dan Horgan, John Quan, David Budden, Gabriel Barth-Maron, Matteo Hessel, Hado Van Hasselt, and David Silver. Distributed prioritized experience replay. arXiv preprint arXiv:1803.00933, 2018.

[5]

Lasse Espeholt, Hubert Soyer, Remi Munos, Karen Simonyan, Vlad Mnih, Tom Ward, Yotam Doron, Vlad Firoiu, Tim Harley, Iain Dunning, et al. Impala: Scalable distributed deep-rl with importance weighted actor-learner architectures. In International Conference on Machine Learning, pages 1407–1416. PMLR, 2018.

[6]

Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33: 1877–1901, 2020.

[7]

LESLIE LAMPORT, ROBERT SHOSTAK, and MARSHALL PEASE. The byzantine generals problem. ACM Transactions on Programming Languages and Systems, 4 (3): 382–401, 1982.

[8]

Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett. Byzantine-robust distributed learning: Towards optimal statistical rates. In International Conference on Machine Learning, pages 5650–5659. PMLR, 2018.

[9]

Yuzhe Ma, Xuezhou Zhang, Wen Sun, and Jerry Zhu. Policy poisoning in batch reinforcement learning and control. Advances in Neural Information Processing Systems, 32, 2019.

[10]

Xuezhou Zhang, Yuzhe Ma, Adish Singla, and Xiaojin Zhu. Adaptive reward-poisoning attacks against reinforcement learning. In International Conference on Machine Learning, pages 11225–11234. PMLR, 2020.

[11]

Gina Neff and Peter Nagy. Automation, algorithms, and politics| talking to bots: Symbiotic agency and the case of tay. International Journal of Communication, 10: 17, 2016.

[12]

Kevin Eykholt, Ivan Evtimov, Earlence Fernandes, Bo Li, Amir Rahmati, Chaowei Xiao, Atul Prakash, Tadayoshi Kohno, and Dawn Song. Robust physical-world attacks on deep learning visual classification. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1625–1634, 2018.

[13]

Yuzhe Ma, J Sharp, Ruizhe Wang, Earlence Fernandes, and Xiaojin Zhu. Adversarial attacks on kalman filter-based forward collision warning systems. In The Thirty-Fifth AAAI Conference on Artificial Intelligence, 2021.

[14]

Jun Sakuma, Shigenobu Kobayashi, and Rebecca N Wright. Privacy-preserving reinforcement learning. In Proceedings of the 25th international conference on Machine learning, pages 864–871, 2008.

[15]

Ximeng Liu, Robert H Deng, Kim-Kwang Raymond Choo, and Yang Yang. Privacy-preserving reinforcement learning design for patient-centric dynamic treatment regimes. IEEE Transactions on Emerging Topics in Computing, 9 (1): 456–470, 2019.

[16]

Abhimanyu Dubey and Alex Pentland. Provably efficient cooperative multi-agent reinforcement learning with function approximation. arXiv preprint arXiv:2103.04972, 2021.

[17]

Guohui Ding, Joewie J Koh, Kelly Merckaert, Bram Vanderborght, Marco M Nicotra, Christoffer Heckman, Alessandro Roncone, and Lijun Chen. Distributed reinforcement learning for cooperative multi-robot object manipulation. arXiv preprint arXiv:2003.09540, 2020.

[18]

Tao Yu, HZ Wang, Bin Zhou, Ka Wing Chan, and J Tang. Multi-agent correlated equilibrium q (\(\lambda\)) learning for coordinated smart generation control of interconnected power grids. IEEE transactions on power systems, 30 (4): 1669–1679, 2014.

[19]

Ana LC Bazzan. Opportunities for multiagent systems and multiagent reinforcement learning in traffic control. Autonomous Agents and Multi-Agent Systems, 18 (3): 342–375, 2009.

[20]

Mingda Qiao and Gregory Valiant. Learning discrete distributions from untrusted batches. arXiv preprint arXiv:1711.08113, 2017.

[21]

Sitan Chen, Jerry Li, and Ankur Moitra. Efficiently learning structured distributions from untrusted batches. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 960–973, 2020.

[22]

Ayush Jain and Alon Orlitsky. Robust density estimation from batches: The best things in life are (nearly) free. In International Conference on Machine Learning, pages 4698–4708. PMLR, 2021.

[23]

Yu Bai, Tengyang Xie, Nan Jiang, and Yu-Xiang Wang. Provably efficient q-learning with low switching cost. Advances in Neural Information Processing Systems, 32, 2019.

[24]

Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Almost optimal model-free reinforcement learningvia reference-advantage decomposition. Advances in Neural Information Processing Systems, 33: 15198–15207, 2020.

[25]

Minbo Gao, Tianle Xie, Simon S Du, and Lin F Yang. A provably efficient algorithm for linear markov decision process with low switching cost. arXiv preprint arXiv:2101.00494, 2021.

[26]

Xuezhou Zhang, Yiding Chen, Jerry Zhu, and Wen Sun. Corruption-robust offline reinforcement learning. arXiv preprint arXiv:2106.06630, 2021.

[27]

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

[28]

Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforcement learning. In International Conference on Machine Learning, pages 263–272. PMLR, 2017.

[29]

Christoph Dann, Tor Lattimore, and Emma Brunskill. Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning. Advances in Neural Information Processing Systems, 30, 2017.

[30]

Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137–2143. PMLR, 2020.

[31]

Lin Yang and Mengdi Wang. Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound. In International Conference on Machine Learning, pages 10746–10756. PMLR, 2020.

[32]

Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline rl? In International Conference on Machine Learning, pages 5084–5096. PMLR, 2021.

[33]

Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell. Bridging offline reinforcement learning and imitation learning: A tale of pessimism. Advances in Neural Information Processing Systems, 34, 2021.

[34]

R Matthew Kretchmar. Parallel reinforcement learning. In The 6th World Conference on Systemics, Cybernetics, and Informatics. Citeseer, 2002.

[35]

Mridul Agarwal, Bhargav Ganguly, and Vaneet Aggarwal. Communication efficient parallel reinforcement learning. In Uncertainty in Artificial Intelligence, pages 247–256. PMLR, 2021.

[36]

Tianyi Chen, Kaiqing Zhang, Georgios B Giannakis, and Tamer Basar. Communication-efficient policy gradient methods for distributed reinforcement learning. IEEE Transactions on Control of Network Systems, 2021.

[37]

Peter J Huber. Robust estimation of a location parameter. In Breakthroughs in statistics, pages 492–518. Springer, 1992.

[38]

John W Tukey. A survey of sampling from contaminated distributions. Contributions to probability and statistics, pages 448–485, 1960.

[39]

Ilias Diakonikolas and Daniel M Kane. Recent advances in algorithmic high-dimensional robust statistics. arXiv preprint arXiv:1911.05911, 2019.

[40]

Kevin A Lai, Anup B Rao, and Santosh Vempala. Agnostic estimation of mean and covariance. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 665–674. IEEE, 2016.

[41]

Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Jacob Steinhardt, and Alistair Stewart. Sever: A robust meta-algorithm for stochastic optimization. In International Conference on Machine Learning, pages 1596–1606. PMLR, 2019.

[42]

Adarsh Prasad, Arun Sai Suggala, Sivaraman Balakrishnan, and Pradeep Ravikumar. Robust estimation via robust gradient estimation. arXiv preprint arXiv:1802.06485, 2018.

[43]

Xuezhou Zhang, Yiding Chen, Xiaojin Zhu, and Wen Sun. Robust policy gradient against strong data corruption. In International Conference on Machine Learning, pages 12391–12401. PMLR, 2021.

[44]

Yudong Chen, Lili Su, and Jiaming Xu. Distributed statistical machine learning in adversarial settings: Byzantine gradient descent. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 1 (2): 1–25, 2017.

[45]

Sandy Huang, Nicolas Papernot, Ian Goodfellow, Yan Duan, and Pieter Abbeel. Adversarial attacks on neural network policies. arXiv preprint arXiv:1702.02284, 2017.

[46]

Thodoris Lykouris, Max Simchowitz, Alex Slivkins, and Wen Sun. Corruption-robust exploration in episodic reinforcement learning. In Conference on Learning Theory, pages 3242–3245. PMLR, 2021.

[47]

Ali Jadbabaie, Haochuan Li, Jian Qian, and Yi Tian. Byzantine-robust federated linear bandits. arXiv preprint arXiv:2204.01155, 2022.

[48]

Xiaofeng Fan, Yining Ma, Zhongxiang Dai, Wei Jing, Cheston Tan, and Bryan Kian Hsiang Low. Fault-tolerant federated reinforcement learning with theoretical guarantee. Advances in Neural Information Processing Systems, 34, 2021.

[49]

Abhimanyu Dubey and Alex Pentland. Private and byzantine-proof cooperative decision-making. In AAMAS, pages 357–365, 2020.

[50]

Ilias Diakonikolas, Gautam Kamath, Daniel M Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Being robust (in high dimensions) can be practical. In International Conference on Machine Learning, pages 999–1008. PMLR, 2017.

[51]

Ruosong Wang, Dean P Foster, and Sham M Kakade. What are the statistical limits of offline rl with linear function approximation? arXiv preprint arXiv:2010.11895, 2020.

[52]

Liam Paninski. A coincidence-based test for uniformity given very sparsely sampled discrete data. IEEE Transactions on Information Theory, 54 (10): 4750–4755, 2008.

[53]

Siu-On Chan, Ilias Diakonikolas, Paul Valiant, and Gregory Valiant. Optimal algorithms for testing closeness of discrete distributions. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pages 1193–1203. SIAM, 2014.

[54]

Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan. Is q-learning provably efficient? Advances in neural information processing systems, 31, 2018.

[55]

David A Freedman. On tail probabilities for martingales. the Annals of Probability, pages 100–118, 1975.

Byzantine-Robust Online and Offline Distributed Reinforcement Learning

Abstract

1 Introduction↩︎

2.0.0.1 Reinforcement learning:

2.0.0.2 Distributed reinforcement learning:

2.0.0.3 Robust statistics:

2.0.0.4 Robust learning from batches:

2.0.0.5 Byzantine-robust distributed learning:

2.0.0.6 Corruption robust RL and Byzantine-robust RL:

3 Robust Mean Estimation from Untruthful Batches↩︎

4 Byzantine-Robust Learning in Parallel MDP↩︎

5 Byzantine-Robust Online RL↩︎

6 Byzantine-Robust Offline RL↩︎

7 Conclusion↩︎

8 More discussion on :Weighted-Clique ↩︎

8.1 Impossible result↩︎

8.2 Adaption to good batch perturbation and distributed learning↩︎

9 Proof of↩︎

9.1 Proof of↩︎

9.1.0.1 the probability of event \(\bigcap_{j\in{\Gcal}}\Ecal_{j}\):

9.1.0.2 the probability of event \(\Ecal_{wa}\):

9.2 Proof of↩︎

9.2.0.1 The structure of \(U^*\):

9.2.0.2 Bad batches in \(U^*\):

9.2.0.3 Error decomposition:

10 Proof of↩︎

10.1 the good event \(\mathcal{E}\) ↩︎

10.1.1 Concentration of estimation from good agents↩︎

10.2 The regret decomposition for UCB style algorithm↩︎

10.3 Evenness of clean agents↩︎

10.3.1 Proof of↩︎

10.3.2 Proof of↩︎

10.3.3 Proof of↩︎

10.3.4 Proof of↩︎

11 Proof of↩︎

12 Useful inequalities↩︎

12.1 Proof for↩︎

References↩︎

Subjects

Updated on Academus

Byzantine-Robust Online and Offline Distributed Reinforcement Learning

Abstract

1 Introduction↩︎

2 Related Work↩︎

2.0.0.1 Reinforcement learning:

2.0.0.2 Distributed reinforcement learning:

2.0.0.3 Robust statistics:

2.0.0.4 Robust learning from batches:

2.0.0.5 Byzantine-robust distributed learning:

2.0.0.6 Corruption robust RL and Byzantine-robust RL:

3 Robust Mean Estimation from Untruthful Batches↩︎

4 Byzantine-Robust Learning in Parallel MDP↩︎

5 Byzantine-Robust Online RL↩︎

6 Byzantine-Robust Offline RL↩︎

7 Conclusion↩︎

8 More discussion on :Weighted-Clique ↩︎

8.1 Impossible result↩︎

8.2 Adaption to good batch perturbation and distributed learning↩︎

9 Proof of↩︎

9.1 Proof of↩︎

9.1.0.1 the probability of event \(\bigcap_{j\in{\Gcal}}\Ecal_{j}\):

9.1.0.2 the probability of event \(\Ecal_{wa}\):

9.2 Proof of↩︎

9.2.0.1 The structure of \(U^*\):

9.2.0.2 Bad batches in \(U^*\):

9.2.0.3 Error decomposition:

10 Proof of↩︎

10.1 the good event \(\mathcal{E}\) ↩︎

10.1.1 Concentration of estimation from good agents↩︎

10.2 The regret decomposition for UCB style algorithm↩︎

10.3 Evenness of clean agents↩︎

10.3.1 Proof of↩︎

10.3.2 Proof of↩︎

10.3.3 Proof of↩︎

10.3.4 Proof of↩︎

11 Proof of↩︎

12 Useful inequalities↩︎

12.1 Proof for↩︎

References↩︎

Subjects

Updated on Academus