# Communication Efficient Parallel Reinforcement Learning

Mridul Agarwal, Bhargav Ganguly, and Vaneet Aggarwal
<EMAIL_ADDRESS>
Purdue University, West Lafayette IN 47907

###### Abstract

We consider the problem where $M$ agents interact with $M$ identical and
independent environments with $S$ states and $A$ actions using reinforcement
learning for $T$ rounds. The agents share their data with a central server to
minimize their regret. We aim to find an algorithm that allows the agents to
minimize the regret with infrequent communication rounds. We provide dist-UCRL
which runs at each agent and prove that the total cumulative regret of $M$
agents is upper bounded as $\tilde{O}(DS\sqrt{MAT})$ for a Markov Decision
Process with diameter $D$, number of states $S$, and number of actions $A$.
The agents synchronize after their visitations to any state-action pair
exceeds a certain threshold. Using this, we obtain a bound of
$O\left(MSA\log(MT)\right)$ on the total number of communications rounds.
Finally, we evaluate the algorithm against multiple environments and
demonstrate that the proposed algorithm performs at par with an always
communication version of the UCRL2 algorithm, while with significantly lower
communication.

##  I Introduction

Reinforcement Learning (RL) is being increasingly deployed and trained with
parallel agents. In many cases, each agent interacts with identical and
independent environments. For example, in autonomous cars, the agents do not
share the environment as they are located possibly far away [Kiran et al.,
2020]. Similarly, in ride/freight sharing services, different RL agents
(vehicles) make decisions in parallel to minimize their costs and maximize the
profits [Al-Abbasi et al., 2019, Manchella et al., 2021]. Further, consider an
example of an e-commerce company using RL agents in servers for recommending
products to customer. Based on the location of the customer, each customer’s
query may potentially be routed to a particular server (or agent)
[Sankararaman et al., 2019]. Finally in the field of robotics, parallel robots
are often deployed in practice [Hu et al., 2020, Sartoretti et al., 2019].
From these examples, we note that every agent would gain by sharing their data
collected, otherwise they would be wasting the knowledge accumulated by the
remaining agents. Such parallel policy learning with limited amount of
communication is the focus of this paper.

Sharing of data across agents poses a new set of problems which comes from
communicating the samples. If the agents communicate the observation tuple
(state, action, reward, next state) at every time step, their communication
complexity will increase. For various power constrained devices such as small
robots, this luxury might not always be available [Sankararaman et al., 2019].
In this paper, we aim to work on the problem to reduce the number of
communication steps while obtaining the same regret bounds as that of an
strategy in which the agents always communicate.

For a system with $M$ parallel agents, the parallel agents generate $M$ times
more data. From the lens of regret analysis, this setup loosely translates to
a setup where a single agent works for time horizon of $MT$. For the setup
where a single agent runs for $MT$ steps, the regret is lower bounded by
$O(\sqrt{DSMAT}$ and upper bounded by $\tilde{O}(DS\sqrt{MAT})$ [Jaksch et
al., 2010, Agrawal and Jia, 2017]. We show that, if the agents take their
actions sequentially and communicate after every interaction with their
respective environments, then the agents can collectively obtain a regret
bound of $\tilde{O}(DS\sqrt{MAT})$. This results in a faster convergence rate
of $O(1/\sqrt{MT})$ to the optimal policy as compared to the convergence rate
of $O(1/\sqrt{T})$ when using one RL agent. Note that in practice, a
sequential decision making for parallel independent agents cannot be
guaranteed. Thus, this result acts as a lower bound to parallel reinforcement
learning. In this paper, we further provide an algorithm, in which agents work
in parallel, that achieves these bounds with limited communication.

We consider a setup where $M$ reinforcement learning agents interact with $M$
identical environments or Markov Decision Processes (MDPs) [Sutton and Barto,
2018, Puterman, 1994]. Similar to the examples considered above, the $M$
environments are independent. We assume that there also exists a central
coordinator (server), although we suggest a method to relax this assumption.
All the agents report their experiences to the central coordinator which then
computes and shares a policy with the agents. We consider that the central
coordinator uses a model based algorithm to compute the policy and each agent
stores the number of visitations made to any particular (state, action, next
state) tuple. The central coordinator also shares the total visitations to
each state-action pair back to all the agents.

Based on this setup, we provide a novel communication efficient dist-UCRL
algorithm. In dist-UCRL algorithm, the agents communicate with the central
coordinator whenever any agent visits any state action pair $s,a$ in the
current epoch (since last synchronization) a fraction ($1/M$) of the total
visitation counts in $s,a$ till last synchronization, instead of every $N\geq
1$ time step. Using this synchronization strategy, for an MDP with diameter
$D$, number of states $S$, and number of actions $A$, using dist-UCRL
algorithm, we bound the cumulative regret of $M$ agents for $T$ time horizon
scales as $O(DS\sqrt{MAT})$ using only $O(MAS\log_{2}(MT))$ synchronization
steps111We use the term communication round and synchronization step
interchangeably.. Note that dist-UCRL not only achieves the lower bound regret
scaling ($\tilde{O}(\sqrt{MT})$) but also with limited communication.

To obtain our results, we also derive a concentration bound on $M$ independent
Martingale sequences which can be of independent interest. To the best of our
knowledge, this is the first work in the direction of obtaining the
performance guarantees using regret analysis for a setup where $M$ agents
interact and collaborate.

We also evaluate our algorithms empirically. We run the proposed dist-UCRL
algorithm in multiple environments. We compare the dist-UCRL algorithm against
the modified UCRL algorithm, following which the agents communicates after
every time step. We show that dist-UCRL algorithm obtain similar regret bound
with reduced communication.

The rest of the paper is organized as follows. Section II summarizes the key
related works. Section III describes the complete system model. Section IV
describes the dist-UCRL algorithm, and the regret guarantees of the algorithm
are provided in Section V. Section VI describes a modification of UCRL2, mod-
UCRL2, and its regret guarantees. Section VII tests the proposed algorithms in
multiple environments, and Section VIII concludes the paper with some possible
directions for future works.

##  II Related Works

Optimal planning using Markov Decision Processes has seen numerous significant
contributions in history. Many algorithms have been proposed to find the
optimal policies. The major algorithms include Q-learning, and policy
iteration to find optimal policies [Howard, 1960, Puterman, 1994, Bertsekas,
1995, Sutton and Barto, 2018]. Fundamentally, the algorithms work by
calculating the utility of taking certain actions in states that maximizes the
utility of the state. These algorithms provide optimal policy when the
transition probabilities of the Markov Decision Process is known or an
$\epsilon$-optimal policy if using iterative algorithms [Puterman, 1994].

A large body of work is also done in the setup where the transition
probabilities are not known. The model-based algorithms work by reducing the
number samples required to obtain a close estimate of transition probabilities
[Bartlett and Tewari, 2009, Jaksch et al., 2010]. The model-free algorithms
work by directly estimating the utilities obtained by taking an action in a
state [Jin et al., 2018]. These algorithms apply optimism in the face of
uncertainty principle to find a model near the empirical estimates that
provides the highest reward. There are also algorithms that sample the
transition probabilities using posterior sampling and obtain regret bound [Ian
et al., 2013, Agrawal and Jia, 2017]. The algorithms suggest that using
parallel agents interacting independent and identical environments will
provide tighter concentration inequalities and hence will help in reducing the
regret.

In the domain of multiple agents using RL, most of the work is done where the
agents interact with a dependent environment and the decision of one agent
impacts all the other agents. This area is known as Multi-Agent Reinforcement
Learning (MARL) [Gupta et al., 2017, Zhang et al., 2018]. The agents may
cooperate with each other, for example, in the case of autonomous vehicles
yielding on a busy road. Or the agents may also compete with each other, for
example, in the case of car racing where only one car may win. Although, we do
have multiple agents in our setup, the environments are independent. Hence, we
will refrain from using MARL terminology in this paper.

With the introduction of deep learning to the field of reinforcement learning,
many “Deep RL” algorithms have been provided to minimize the sample complexity
to find the optimal policies [Mnih et al., 2013, Schulman et al., 2015, Mnih
et al., 2016, Schulman et al., 2017, Haarnoja et al., 2018]. Recently, various
algorithms are using parallel actors to learn better policies using deep
reinforcement learning [Nair et al., 2015, Clemente et al., 2017, Horgan et
al., 2018, Espeholt et al., 2018, Assran et al., 2019]. These algorithms
consist of parallel agents that share the entire sequence of (state, action,
reward, next state) tuples after every $n$ epochs, and update a common neural
network with the gradients computed from possibly parallel learners. Compared
to these works, we consider a model based setup to obtain regret guarantees
with only $O(MAS\log_{2}(MT))$ number of synchronization rounds with a common
controller learning the policy.

Recently, in the area of Bandits [Lattimore and Szepesvári, 2020], there has
been a thrust on distributed bandits with reduced number of communication
rounds. Various algorithms have been proposed to minimize the regret for
setups where the agents synchronize a central coordinator [Kanade et al.,
2012, Hillel et al., 2013, Wang et al., 2019, Dubey and Pentland, 2020].
Recently, Wang et al. [2019] showed that it is possible to obtain optimal
regret guarantees with number of rounds that are independent of $T$ in
stochastic Multi-Armed Bandits and Linear Bandits. Further, Dubey and Pentland
[2020] considered a linear bandit setup and aimed to protect the privacy of
the agents collaborating along with minimizing the number of communications
rounds. Moreover, [Chawla et al., 2020, Sankararaman et al., 2019] considered
a gossiping setup to communicate only the index of the best arm, thus reducing
not only the number of communication rounds, but also the number of bits in
each communication round. Similar to the bandit setup, we also attempt to find
rigorous regret guarantees of the dist-UCRL algorithm and a bound on the
number of communication rounds.

##  III System Model

Let $[K]$ be the set of $K$ elements, or $[K]=\\{1,2,\cdots,K\\}$. We consider
an MDP $\mathcal{M}=(\mathcal{S},\mathcal{A},P,\bar{r})$, where
$\mathcal{S}=[S]$ is the set of finite states and $\mathcal{A}=[A]$ is the set
of finite actions. $P$ denotes the transition probabilities, i.e., on taking
action $a\in\mathcal{A}$ in state $s\in\mathcal{S}$, the next state
$s^{\prime}\in\mathcal{S}$ follows distribution $P(\cdot|s,a)$. Also, on
taking action $a\in\mathcal{A}$ in state $s\in\mathcal{S}$, an agent receives
a stochastic reward $r$ drawn from a distribution over $[0,1]$ with mean
$\bar{r}(s,a)$.

We consider $M$ agents in the system, each interacting with $M$ identical
environments. Let $i\in[M]$ be the indexing for agents and their corresponding
environment. For an agent $i$, at time step $t$, let $s_{i,t}$ denote the
state of the agent, $a_{i,t}$ be the action taken by the agent, and $r_{i,t}$
denote the reward obtained by the agent on taking action $a_{i,t}$ in state
$s_{i,t}$. We assume that the $M$ environments are independent.
Mathematically, $\forall\leavevmode\nobreak\ i\in[M]\text{ and
}\forall\leavevmode\nobreak\ t\geq 1$, we have,

$\displaystyle\mathbb{P}(s_{i,t+1}|s_{1,t},a_{1,t},\cdots,s_{M,t},a_{M,t},)=\mathbb{P}(s_{i,t+1}|s_{i,t},a_{i,t}),$

and we take a similar assumption over the rewards $r_{i,t}$ as well. This
means, the distribution of the next state $s_{i,t+1}$ and the rewards
$r_{i,t}$ of agent $i\in[M]$ are conditioned only on the knowledge of the
current state and action $(s_{i,t},a_{i,t})$ of the agent $i$ and is
independent of the other states and actions of the remaining agents.

Let policy $\pi:\mathcal{S}\to\mathcal{A}$ be a function to determine which
action to select in state $s\in\mathcal{S}$. Note that each policy induces a
Markov Chain on the states $\mathcal{S}$ with transition probabilities
$P_{s,s}=P(\cdot|s,\pi(s))$. After defining a policy, we can now define the
diameter of the MDP $\mathcal{M}$ as:

######  Definition 1 (Diameter).

Consider the Markov Chain induced by the policy $\pi$ on the MDP
$\mathcal{M}$. Let $T(s^{\prime}|\mathcal{M},\pi,s)$ be a random variable that
denotes the first time step when this Markov Chain enters state $s^{\prime}$
starting from state $s$. Then, the diameter of the MDP $\mathcal{M}$ is
defined as:

$\displaystyle D(\mathcal{M})=\max_{s^{\prime}\neq
s}\min_{\pi}\mathbb{E}\left[T(s^{\prime}|\mathcal{M},\pi,s)\right]$ (1)

We assume that the MDP $\mathcal{M}$ has a finite diameter which means that
there is a policy, such that following that policy all $s\in\mathcal{S}$
communicate with each other.

Any agent $i\in[M]$ starting from an initial random state $s_{i,1}=s$ follows
an algorithm $\mathscr{A}$ till $T$ time steps to collect a cumulative reward
of $R_{i}$. Also, let $\rho_{i}$ denote the average reward of the agent
following algorithm $\mathscr{A}$. Or,

$\displaystyle R_{i}(\mathcal{M},\mathscr{A},s,T)$
$\displaystyle=\sum\nolimits_{t=0}^{T}r_{i,t}$ (2)
$\displaystyle\rho_{i}(\mathcal{M},\mathscr{A},s)$
$\displaystyle=\lim_{T\to\infty}\frac{1}{T}\sum\nolimits_{t=0}^{T}\mathbb{E}\left[r_{i,t}\right]$
(3)

Let there be an algorithm $\mathscr{A}$ which always selects action according
to a stationary policy $\pi:\mathcal{S}\to\mathcal{A}$. Then, we denote
$\rho(\mathcal{M},\mathscr{A},s)=\rho(\mathcal{M},\pi,s)$. The optimal average
reward does not depend on the state [Puterman, 1994, Section 8.3.3], and hence
for the optimal policy $\pi^{*}$ which maximizes the average reward
$\rho(\mathcal{M},\pi,s)$ we have,

$\displaystyle\rho^{*}(\mathcal{M})\coloneqq\rho^{*}(\mathcal{M},s)\coloneqq\max\nolimits_{\pi}\rho(\mathcal{M},s).$
(4)

Further, the optimal average reward satisfies [Puterman, 1994, Theorem 8.4.7],

$\displaystyle\rho^{*}+v(s)=\bar{r}(s,a^{*})+\sum\nolimits_{s^{\prime}}P(s^{\prime}|s,a^{*})v(s^{\prime})\leavevmode\nobreak\
\forall s\in\mathcal{S}$ (5)

where $a^{*}=\pi^{*}(s)$, and $v(s)$ is called the bias of the state $s$ and
it denotes the extra reward obtained from starting in the state $s$. Note that
$v(s)$ is not unique since if $v(s)\leavevmode\nobreak\
\forall\leavevmode\nobreak\ s$ satisfy Equation (5), then so does $v(s)+c$ for
all $c\in\mathbb{R}$ and hence, the bias is translation invariant.

We aim to maximize the cumulative reward collected by all the agents. Hence,
we want to develop an algorithm that, starting from no knowledge about the
system, learns a policy that minimizes the regret. The regret of an algorithm
$\mathscr{A}$, for starting state $s$, and running for time $T$, is defined
as:

$\displaystyle\Delta(\mathcal{M},\mathscr{A},s,T):=\rho^{*}MT-\sum\nolimits_{i\in[M]}R_{i}(\mathcal{M},\mathscr{A},s,T)$

We will now present our algorithm dist-UCRL that uses upper confidence bounds
to bound the regret $\Delta(\mathcal{M},\textsc{dist-UCRL},s,T)$ with high
probability with only $O(MAS\log_{2}(MT))$ communication rounds.

##  IV dist-UCRL Algorithm

We consider that each agent runs an instance of the dist-UCRL algorithm. The
dist-UCRL algorithm running at agent $i$ is described in Algorithm 1. The
algorithm proceeds in epochs indexed as $k=1,2,\cdots$. The start of every
epoch also coincides with the synchronization step where every agent
communicates with the central node to share data and update policies. This
also implies that the number of synchronization rounds requires by the
algorithm are the same as the number of epochs for the algorithm runs.

Algorithm 1 dist-UCRL at agent $i$

1: Input: $S,A,M$

2: Set parameters
$P_{i}(s,a,s^{\prime})=0\forall(s,a,s^{\prime})\in\mathcal{S}\times\mathcal{A}\times\mathcal{S}$
and $\hat{r}_{i}(s,a)=0\forall(s,a)\in\mathcal{S}\times\mathcal{A}$.

3: for Epochs: $k=1,2,\cdots$ do

4: Set $\nu_{i,k}(s,a)=0\forall(s,a)\in\mathcal{S}\times\mathcal{A}$.

5: $\pi_{k},N_{k}=$ synchronize$(P_{i},\hat{r}_{i},t)$

6: while $\nu_{i,k}(s,a)<\max(1,N_{k}(s,a))/M\forall(s,a)$ and Synchronization
not requested do

7: Play action $a_{i,t}=\pi_{k}(s_{i,t})$, observe reward $r_{t}$ and next
state $s_{i,t+1}$.

8: Set $\nu_{i,k}(s_{i,t},a_{i,t})=\nu_{i,k}(s_{i,t},a_{i,t})+1$,
$P_{i}(s_{i,{i,t}},a_{i,t},s_{t+1})=P_{i}(s_{i,t},a_{i,t},s_{i,t+1})+1$,
$\hat{r}_{i}(s_{i,t},a_{i,t})=\hat{r}_{i}(s_{i,t},a_{i,t})+r_{t}$.

9: Set $t=t+1$.

10: end while

11: Request synchronization

12: end for

Algorithm 1 running at agent $i$, maintains two counters, $\nu_{i,k}(s,a)$ and
$P_{i}(s,a,s^{\prime})$. $\nu_{i,k}(s,a)$ counts the number of visitations to
state action pair $(s,a)$ in epoch $k$, and $P_{i}(s,a,s^{\prime})$ counts the
instances when the agent moves to state $s^{\prime}$ on taking action $a$ in
state $s$. The agent also stores $\hat{r}_{i}(s,a)$ as the cumulative reward
obtained in $(s,a)$.

Algorithm 2 synchronize at central node

1: Input: $P_{i},\hat{r}_{i}$ from all agents $i\in[M]$, $t$.

2: for $(s,a)\in\mathcal{S}\times\mathcal{A}$ do

3: Set $N(s,a)=\sum_{i}\sum_{s^{\prime}}P_{i}(s,a,s^{\prime})$.

4: Set
$\hat{p}(s,a,s^{\prime})=\frac{\sum_{i}P_{i}(s,a,s^{\prime})}{\max\\{1,N(s,a)\\}}$

5: Set
$\hat{\bar{r}}(s,a)=\frac{\sum_{i}\hat{r}_{i}(s,a)}{\max\\{1,N(s,a)\\}}$

6: Set
$\tilde{r}(s,a)=\hat{\bar{r}}(s,a)+\sqrt{\frac{7\log(2MSAt)}{2\max\\{1,N(s,a)\\}}}$

7: Set $d(s,a)=\sqrt{\frac{14S\log(2MAt)}{\max\\{1,N(s,a)\\}}}$

8: end for

9: Set $\pi$ = Extended Value
Iteration($\hat{p},d,\tilde{r},\frac{1}{\sqrt{Mt}}$)

10: Return $\pi,N$

Let $N_{k}(s,a)=\sum_{i=1}^{M}\sum_{k^{\prime}=1}^{k-1}\nu_{i,k}(s,a)$ be the
total number of visitations till the start of epoch $k$ for all agents. And
hence, $N_{k}(s,a)=0$ at $k=1$ for all $s,a\in\mathcal{S}\times\mathcal{A}$.
At the start of every epoch $k\geq 1$, the agents obtains the policy for epoch
$k$ and total visitations to any state action pair $N_{k}(s,a)$. We will
denote the time step at which epoch $k$ start and agents synchronize of the
$k^{th}$ time with $t_{k}$. At $t=1$, the algorithm synchronizes all the
agents for the very first time, or $t_{1}=1$. Later, a new epoch is triggered
whenever any of the agent requests for synchronization222The synchronization
request can be sent to server, which will in turn pause and synchronize the
entire system.. An agent $i$ requests synchronization whenever
$\nu_{i,k}(s,a)$ becomes at least $1/M$ of $N_{k}(s,a)$ for any state action
pair. We assume that every agent is able to receive the synchronization signal
instantly and stop further processing of the current epoch. The algorithm
calls synchronize algorithm every time after a new epoch starts and updates
the policy $\pi_{k}$ and $N_{k}(s,a)$ values. Every agent now selects actions
according to the policy $\pi_{k}$ in the epoch $k$.

The synchronize algorithm is described in Algorithm 2. This algorithm
calculates the estimates of the transition probability $\hat{p}(\cdot|s,a)$
and the mean rewards $\hat{\bar{r}}(s,a)$ using the samples from all the $M$
agents. We now consider a set of all plausible MDPs $\mathscr{M}(t)$ that
exist in the neighborhood of the estimated MDP
$\widehat{\mathcal{M}}=(\mathcal{S},\mathcal{A},\hat{p},\hat{\bar{r}})$. The
mean rewards $r^{\prime}(s,a)$ and the transition probabilities
$p^{\prime}(s,a)$ for all the MDPs in the set $\mathscr{M}(t)$ satisfies:

$\displaystyle|\hat{\bar{r}}(s,a)-r^{\prime}(s,a)|$
$\displaystyle\leq\sqrt{\frac{7\log(2MSAt)}{2\max\\{1,N(s,a)\\}}}$ (6)
$\displaystyle\|\hat{p}(\cdot|s,a)-p^{\prime}(\cdot|s,a)\|_{1}$
$\displaystyle\leq\sqrt{\frac{14S\log(2MAt)}{\max\\{1,N(s,a)\\}}}$ (7)

After obtaining $\mathscr{M}(t)$, Algorithm 2 calls the Extended Value
Iteration algorithm which then computes the optimal policy for the optimistic
MDP $\tilde{\mathcal{M}}_{t}$ in the set $\mathscr{M}(t)$. The optimistic MDP
satisfies
$\rho^{*}(\tilde{\mathcal{M}})=\sup_{\mathrm{M}\in\mathscr{M}(t)}\rho^{*}(\mathrm{M})$.
As described in [Jaksch et al., 2010], it is not trivial to directly find the
optimistic MDP in $\mathscr{M}(t)$. Hence, we consider an extended MDP
$\mathcal{M}_{t}^{+}$ which is constructed with the same state space and a
continuous action space
$(a,q(\cdot|\cdot,a))\in\mathcal{A}\times\mathscr{P}_{t}$, where
$\mathscr{P}_{t}$ is the set of transition probabilities for action
$a\in\mathcal{A}$ that satisfies Equation (7). When $\mathscr{M}(t)$ contains
the true MDP $\mathcal{M}$, the diameter of the extended MDP
$\mathcal{M}_{t}^{+}$ is bounded by $D$ as the policy for which all states
communicate with each other for MDP $\mathcal{M}$ also ensures that all states
communicate in the extended MDP $\mathcal{M}_{t}^{+}$ as well.

Algorithm 3 Extended Value Iteration

1: Input: $\hat{p},d,\tilde{r},\epsilon$.

2: Set $u_{0}(s,a)=0,u_{1}(s)=\max_{a}\tilde{r}(s,a),i=1$.

3: Set $\pi(s)=\arg\max_{a}\tilde{r}(s,a)$

4: while
$\max_{s}\\{u_{i}(s)-u_{i-1}(s)\\}-\min_{s}\\{u_{i}(s)-u_{i-1}(s)\\}\geq\epsilon$
do

5: Sort $s_{1}^{\prime},\cdots,s_{S}^{\prime}$ such that
$u_{i}(s_{1}^{\prime})\geq\cdots\geq u_{i}(s_{S}^{\prime})$.

6: Set $p(s_{1})=\min\\{1,\hat{p}(s^{\prime}|s_{1},a)+d(s_{1},a)/2\\}$

7: Set $p(s_{n})=\hat{p}(s^{\prime}|s_{n},a),n=2,3,\cdots,S$.

8: Set $l=1$

9: while $\sum_{s}p(s)>1$ do

10: Set $p(s_{l})=\max\\{0,1-\sum_{s_{n}\neq s_{l}}p(s_{n})\\}$

11: Set $l=l-1$

12: end while

13: $i=i+1$

14:
$u_{i}(s)=\max_{a}\left\\{\tilde{r}(s,a)+\sum_{s^{\prime}}p(s^{\prime})u_{i-1}(s^{\prime})\right\\}$

15:
$\pi(s)=\arg\max_{a}\left\\{\tilde{r}(s,a)+\sum_{s^{\prime}}p(s^{\prime})u_{i-1}(s^{\prime})\right\\}$

16: end while

17: Return $\pi$

The Extended Value Iteration algorithm (Algorithm 3) follows the design of the
Extended Value Iteration of UCRL2 algorithm by Jaksch et al. [2010]. As
described by Jaksch et al. [2010], Extended Value Iteration (EVI) obtains a
policy $\pi$ that is $\epsilon$-optimal for the extended MDP
$\mathcal{M}_{t}^{+}$ and in turn the optimistic MDP $\tilde{\mathcal{M}}$.
Algorithm 3 calculates the values of the states of the extended MDP
$\mathcal{M}_{t}^{+}$. The extended value iteration calculates the utilities
of the states and the actions that achieve this utility. Note that unlike the
extended value iteration in UCRL2 algorithm, we consider Algorithm 3 to be
converged when we have
$\max_{s}(u_{i+1}-u_{i}(s))-\min_{s}(u_{i+1}-u_{i}(s))\leq\epsilon=1/\sqrt{Mt}$.
This is because we now have $M$ times more samples till any time step $t$ as
compared to the UCRL algorithm. The EVI, at start of epoch $k$, returns a
policy $\pi_{k}$ that satisfies
$\rho(\tilde{\mathcal{M}},\pi_{k})\geq\rho^{*}(\tilde{\mathcal{M}}_{t_{k}})-1/\sqrt{Mt_{k}}$.

We also note that the central controller is not necessariliy required if the
agents are in a completely connected network, they can share there data with
each other and run the algorithms for the central controller by themselves.
Further, the completely connected assumption can also be relaxed by
considering a setup where all agents forward the messages they get. This
allows the broadcast of the information. Hence, the proposed algorithm can be
generalized to any network structure as long as all the agents are connected
via some path.

##  V Results for dist-UCRL

After describing the algorithm, we now bound the regret of the dist-UCRL
algorithm. We show that the regret bound holds with high probability. We bound
the regret incurred by the dist-UCRL algorithm in the form of following
theorem.

######  Theorem 1.

For a MDP $\mathcal{M}=([S],[A],P,r)$ with diameter $D$, for any starting
state $s$, the regret of the dist-UCRL algorithm, running on $M$ agents for
$T$ time steps, is upper bounded with probability at least
$1-\frac{1}{(MT)^{5/4}}$ as:

$\displaystyle\Delta(\mathcal{M},\textsc{dist-
UCRL},s,T)\leq\tilde{O}(DS\sqrt{MAT})$ (8)

where $\tilde{O}$ hides the poly-log terms in $M,S,A,$ and $T$.

We let $m$ be the total number synchronizations done by agents running dist-
UCRL algorithm till time $T$. Then, we bound $m$ deterministically in the
following theorem.

######  Theorem 2.

The total number of communication rounds $m$ for dist-UCRL2 up to step $T\geq
SA/M$ is upper bounded as

$\displaystyle m\leq 1+2MAS+MAS\log_{2}\left(MT\right)$ (9)

###### Proof.

We use the fact that when $\nu_{i,k}(s,a)\geq N_{k}(s,a)/M$ for some state
action pair $(s,a)$ and for some agent $i$, the total visitation count
$N_{k+1}(s,a)$ is at least
$N_{k}(s,a)+\nu_{i,k}(s,a)=N_{k}(s,a)(1+\frac{1}{M})$. This gives an
exponential growth for the total visitation count of any state action pair.
Also, since the total visitation count for all state action pairs is upper
bounded by $MT$, using Jensen’s inequality we bound the number of epochs in
logarithmic order of $MT$. A complete proof is provided in Appendix D. ∎

We now state the lemmas required for the proof of the Theorem 1. The first
three lemmas are used to handle the stochastic nature of the algorithm and
environment. The first lemma provides concentration bounds on the
$\ell_{1}$-deviation of the transition probabilities $\hat{p}(\cdot|s,a)$ for
any $(s,a)$.

######  Lemma 1.

The $\ell_{1}$-deviation of the true distribution and the empirical
distribution using $n$ samples, over the next states given the current state
$s$ and action $a$ is bounded by

$\displaystyle\mathbb{P}\left(\|\hat{p}(\cdot|s,a)-P(\cdot|s,a)\|_{1}\geq\epsilon\right)\leq
2^{S}\exp{(-\frac{n\epsilon^{2}}{2})}$ (10)

###### Proof.

The proof follows on the lines of [Weissman et al., 2003, Theorem 2.1], using
the distribution as transition probabilities. ∎

######  Lemma 2 (Hoeffding’s Inequality, [Hoeffding, 1994]).

Let $\\{X_{t}\\}_{t=1}^{T}$ be i.i.d. random variables in [0,1]. Then, we
have,

$\displaystyle
P(\sum_{t=1}^{T}X_{i,t}\geq\epsilon)\leq\exp{\left(-\frac{2\epsilon^{2}}{T}\right)}$
(11)

The next lemma provides concentration bounds on the sum of $M$ independent
Martingale sequences for length $T$.

######  Lemma 3.

Let $\\{X_{i,t}\\}_{t=1}^{T}$ be a zero-mean Martingale sequence for
$i=1,\cdots,M$ adapted to filtration $\\{\mathcal{F}_{t}\\}_{t=0}^{T}$. Then,
if $\\{X_{i,t}\\}_{t=1}^{T}$ and $\\{X_{j,t}\\}_{t=1}^{T}$ are independent for
all $i\neq j$ and $|X_{i,t}|X_{i,t-1}|\leq c$ for all $i,t$, we have,

$\displaystyle
P\left(\sum_{t=1}^{T}\sum_{i=1}^{M}X_{i,t}\geq\epsilon\right)\leq\exp{\left(-\frac{2\epsilon^{2}}{MTc^{2}}\right)}$
(12)

###### Proof Sketch.

We prove this lemma similar to the proof of Azuma-Hoeffding’s Inquality
[Hoeffding, 1994]. A detailed proof is provided in Appendix A. ∎

We now bound the growth rate of the total number of visitations to state
action pair $(s,a)$, $\sum_{i=1}^{M}\nu_{i,k}(s,a)$, in any epoch $k$. If the
total visitations are large, then the agents will incur large regret from a
possibly sub-optimal policy. Hence, we have the following lemma:

######  Lemma 4.

For any epoch $k$, we have,

$\displaystyle\sum\nolimits_{i=1}^{M}\nu_{i,k}(s,a)\leq N_{k}(s,a)+M-1$ (13)

###### Proof.

Note that agent $i$ requests for synchronization, and triggers a new epoch,
whenever $\nu_{i,k}(s,a)=\lceil N_{k}(s,a)/M\rceil\leq N_{k}(s,a)/M+(M-1)/M$.
Summing over all the agents $i$ gives the bound. ∎

######  Lemma 5 (Lemma 19 [Jaksch et al., 2010]).

For any sequence of number $z_{1}\leq z_{2}\leq\cdots\leq z_{n}$ with
$z_{k}\leq\sum_{k^{\prime}=1}^{k-1}z_{k^{\prime}}\eqqcolon Z_{k}$, we have,

$\displaystyle\sum_{k=1}^{n}\frac{z_{k}}{Z_{k}}\leq(\sqrt{2}+1)Z_{n}$ (14)

The last lemma states that the span of the bias of the optimal policy defined
as $\max_{s}v(s)-\min_{s}v(s)$ is bounded by the diameter $D$.

######  Lemma 6 (Remark 8 from Jaksch et al. [2010]).

The span of the bias $v:\mathcal{S}\to\mathbb{R}$ of the optimal policy $\pi$
for any MDP $\mathcal{M}$ is upper bounded by its diameter $D(\mathcal{M})$,
or,

$\displaystyle sp(v)=\max_{s}v(s)-\min_{s}v(s)\leq D(\mathcal{M})$ (15)

After stating all the necessary lemmas, we are now ready to prove the regret
bound of the dist-UCRL algorithm or $\Delta(\mathcal{M},\textsc{dist-
UCRL},s,T)$. We provide a detailed sketch here and provide the complete proof
in Appendix C.

###### Proof Sketch of Theorem 1.

We break the regret expression, into $4$ different sources of regrets as:

1\. Regret from deviating from expected reward: Note that regret compares the
expected optimal gain $\rho^{*}$ with the observed rewards $r_{i,t}$. Since,
$r_{i,t}$ is a random variable between $[0,1]$, the agents suffer a regret if
the observed rewards are lower as compared to the mean. Hence, we use
Hoeffding’s inequality [Hoeffding, 1994] to bound the regret generated by the
randomness of the observed rewards. This gives us regret bounded by
$\tilde{O}(\sqrt{MT})$.

2\. Regret from deviating from the expected next state: The algorithm, when
transitioning to the next state, expects a bias given the current state.
However, the bias of the realized state may be different and even lower from
the expected bias. Hence, we bound the deviation from the expected bias as the
algorithm moves to states. Starting from state $s$, the deviation process is
modelled as a zero-mean Martingale sequence of the states visited by an agent
$i$. Also, we have $M$ independent agents interacting with $M$ independent
environment. We use Lemma 3 to bound the total deviation of the realized bias
and the expected bias. This gives us regret bounded by
$\tilde{O}(D\sqrt{MT})$.

3\. Regret from not optimizing for the true MDP: For epoch $k$, we run an
$\frac{1}{\sqrt{Mt_{k}}}$-optimal policy for an optimistic MDP from the set of
MDPs $\mathscr{M}(t_{k})$ for $\sum_{i\in[M]}\sum_{s,a}\nu_{i,k}(s,a)$. The
transition probabilities and the mean rewards of MDPs in $\mathscr{M}(t_{k})$
satisfy Equation (7) and Equation (6). When the true MDP $\mathcal{M}$ lies in
$\mathscr{M}(t_{k})$, we bound the regret because of the incorrect MDPs by the
product of the diameter of the set $\mathscr{P}_{t_{k}}$, the diameter $D$ of
the MDP $\mathcal{M}$, and the number of visitations to any state action pair
$s,a$ in epoch $k$ using Lemma 6. All we need to do now is to bound the sum of
the product for all epochs. We do so by using Lemma 4 and Lemma 5. This gives
us regret bounded by $\tilde{O}(DS\sqrt{MAT})$.

4\. Regret when the estimated MDP is far from the true MDP $\mathcal{M}$: We
use Lemma 1 to bound the $\ell_{1}$ distances of the estimated transition
probability and the true transition probability given any state action pair.
Further, we also use Hoeffding’s inequality (Lemma 2) to bound the distance of
the true mean rewards and the estimated rewards. Taking union bounds over all
time steps till $T$, we obtain the bound for all possible values of $N(s,a)$.
Further, taking union bounds over all state and actions provide the desired
concentration bounds for all states and actions. Finally, we take the union
bounds for all values of $t\geq(MT)^{1/4}$. This gives the total bound on
probability that the true MDP $\mathcal{M}$ lies in $\mathscr{M}(t_{k})$ as:

$\displaystyle\mathbb{P}\left(\mathcal{M}\notin\mathscr{M}(t)\right)\leq\frac{1}{(MT)^{5/4}}\forall\leavevmode\nobreak\
t\geq(MT)^{5/4}.$ (16)

Now summing over all the regret sources, we get the regret bound of the dist-
UCRL algorithm. ∎

The proof of the Theorem 1 and Theorem 2 suggests that the analysis could
potentially be extended to various other algorithms that follow the epoch
completion condition from the UCRL-2 Algorithm of [Jaksch et al., 2010].

##  VI Naive Approach: mod-UCRL2 for multiple agents

The proposed dist-UCRL algorithm does not require the agents to work
sequentially, and hence the $M$ agents can truly work in parallel. For
comparison of the proposed algorithm and completeness, we also consider an
extension of UCRL2 algorithm by Jaksch et al. [2010] for $M$ parallel agents
which we call mod-UCRL2. In the mod-UCRL2 algorithm, we assume that all the
agents communicate to a centralized server at each time step $t$, and the
server decides the actions for the agents at each time $t$. Thus, the
communication rounds for mod-UCRL2 algorithm is $O(T)$, while the regret
analysis is not apriori clear, and is the focus of this section. We also note
that even though this algorithm is an easy extension of UCRL2, the analysis of
regret is not straightforward, and uses the approach that was used to prove
the regret guarantees of dist-UCRL because of the presence of $M$ agents.

At every time step $t$, every agent $i\in[M]$ observes its state $s_{i,t}$ and
sends it to the server. The server after receiving all the states, process the
requests sequentially in the order $s_{1,t},s_{2,t},\cdots,s_{M,t}$. The
central server runs an instance of the UCRL2 algorithm with state sequence
$s_{1,1},s_{2,1},\cdots,s_{M,1},s_{1,2},\cdots,$ and the corresponding action
sequence $a_{1,1},a_{2,1},\cdots,a_{M,1},a_{1,2},\cdots$. The UCRL2 algorithm,
running at the server, proceeds in epoch with epoch $1$ starting with
$(i,t)=(1,1)$. We consider an epoch $k$ contains observations for
$\\{(\underline{i}_{k},\underline{t}_{k}),(\underline{i}_{k},\underline{t}_{k})+1,\cdots,(\bar{i}_{k},\bar{t}_{k})\\}$
for some $\underline{i}_{k},\underline{t}_{k},\bar{i}_{k},\bar{t}_{k}$. The
server maintains counters $\nu_{k}(s,a)$ denoting the number of times a state
action pair $s,a$ is visited in the epoch $k$, and counter $N_{k}(s,a)$
denoting the number of times a state action pair $s,a$ is visited before the
start of the epoch $k$ as:

$\displaystyle\nu_{k}(s,a)$
$\displaystyle=\sum\nolimits_{(i,t)=(\underline{i}_{k},\underline{t}_{k})}^{(\bar{i}_{k},\bar{t}_{k})}\bm{1}{\\{s_{i,t}=s,a_{i,t}=a\\}}$
(17) $\displaystyle N_{k}(s,a)$
$\displaystyle=\sum\nolimits_{k^{\prime}=1}^{k-1}\nu_{k^{\prime}}(s,a)$ (18)

The server updates an epoch $k$ whenever $\nu_{k}(s,a)=\max\\{1,N_{k}(s,a)\\}$
for some $s,a$. Following the UCRL2 algorithm, the server updates the policy
at the beginning of every epoch using the observations collected till the
beginning of the epoch. The complete algorithm is provided in Appendix E.

Note that in the mod-UCRL2 algorithm, the agents only behaves as interfaces to
the $M$ independent environments, and is essentially not practical because of
the sequential interface. In the following result, we formally state the
result that the regret is upper bounded by $\tilde{O}(DS\sqrt{MAT})$.

######  Theorem 3.

For a MDP $\mathcal{M}=([S],[A],P,r)$ with diameter $D$, for any starting
state $s$, the regret of the mod-UCRL2 algorithm, running on $M$ agents for
$T$ time steps, is upper bounded with probability at least
$1-\frac{1}{(MT)^{5/4}}$ as:

$\displaystyle\Delta(\mathcal{M},\textsc{mod-
UCRL2},s,T)\leq\tilde{O}(DS\sqrt{MAT})$

where $\tilde{O}$ hides the poly-log terms in $M,S,A,$ and $T$.

###### Proof Outline.

Similar to the proof of Theorem 1, we again consider the four sources of
regret. Then, breaking the regret into episodes when the mod-UCRL2 algorithm
updates policy, we obtain the required bound. The complete proof is provided
in Appendix F. ∎

##  VII Evaluations

In this section, we analyze the performance of the proposed dist-UCRL
algorithm empirically. We test the dist-UCRL algorithm in multiple
environments and also vary the number of agents in all the cases to study the
regret growth with respect to $M$. Further, we also evaluate the average
number of communication steps used by the dist-UCRL algorithm till time step
$T$.

(a) RiverSwim environment

(b) RiverSwim-12 environment

(c) Gridworld environment

Figure 1: Average cumulative regret per agent under various communication
strategies. The empirical regret of the dist-UCRL algorithm and mod-UCRL2
algorithm are almost identical which is expected from the regret analysis of
the two algorithms.

We first run the dist-UCRL algorithm for the riverswim environment, which is a
standard benchmark for model-based RL algorithm [Ian et al., 2013, Tossou et
al., 2019] with $6$ states and $2$ actions. Next, we construct an extended
riverswim environment with $12$ states and $2$ actions. Finally, we use a
Grid-World environment [Sutton and Barto, 2018] for a $7\times 7$ grid which
amounts to $20$ states and $4$ actions.

We compare the dist-UCRL algorithm against the mod-UCRL2 algorithm. We also
compare with the standard UCRL2 algorithm for $M=1$. Note that for the case of
$M=1$, both, dist-UCRL algorithm and the mod-UCRL2 algorithm reduces to the
UCRL2 algorithm.

(a) RiverSwim environment

(b) RiverSwim-12 environment

(c) Gridworld environment

Figure 2: Total number of communication rounds required for the dist-UCRL
algorithm for multiple number agents across various environments.

We run $50$ independent iterations of the algorithm. We plot the average per-
agent regret, $\Delta(\mathcal{M},\textsc{dist-UCRL},s,T)/M$, over the $50$
iterations and the error bars for both dist-UCRL and mod-UCRL2 algorithm in
Figure 1. We vary the number of agents $M$ as $1,4$, and $16$ to reduce
clutter in figures. From Figure 1(a) and Figure 1(c), we note that the per-
agent regret decreases approximately by a factor of $2$ for every $4$-fold
increase in the number of agents. This is expected and was indeed the goal.

Note that in Figure 1(b), the per-agent regret falls from being linear in
UCRL2 ($M=1$) to significantly sublinear as the number of agents were
increased to $M=4$ and $M=16$. For the extended RiverSwim environment with
$12$ states, the diameter is approximately $5\times 10^{4}$. Hence, the
available time horizon of $T=10^{5}$ was not sufficient for UCRL2. However,
distributed RL algorithms still observed a sub-linear regret by collating
their knowledge. This further demonstrates the advantage of deploying multiple
parallel agents in complex environments to enhance exploration.

We also empirically evaluate the number of communication rounds required by
the dist-UCRL algorithm. Note that the number of communications for mod-UCRL2
algorithm is same as the total length for which the algorithm runs. Hence, we
only plot the number of communications rounds required for the dist-UCRL
algorithm. We vary the number of agents $M$ in multiples for $2$ and starting
from $M=2$ agents. We again run the experiment for $50$ independent iterations
and plot the average number of synchronization rounds till time step $t$.

We plot the number of communication rounds of the dist-UCRL algorithm in
Figure 2. We observe that the number of the synchronization rounds increase
very slowly with $t$. Further, as suggested from Theorem 2, the number of
synchronization rounds are increasing in $M$. However, we note that for large
values of $t$, the increase in the number of communication rounds is sub-
linear. This is because for the bound on the number of communication rounds,
we take pessimistic estimates on the increase on the visitation counts
$N_{k}(s,a)$ where only one agent $i$ updates total $N_{k}(s,a)$ by a factor
of $(1+1/M)$ only when the agent $i$ triggers the synchronization round for
$s,a$. However, in practice, $N_{k}(s,a)$ grows faster than $(1+1/M)$, as the
synchronization rounds triggered for other state action pairs and other agents
also contribute towards $N_{k}(s,a)$.

##  VIII Conclusion

In this work, we considered the problem of simultaneously reducing the
cumulative regret and the number of communication rounds between $M$ agents.
The $M$ agents interact with $M$ independent and identical Markov Decision
Processes and share their data to learn the optimal policy faster. To this
end, we proposed dist-UCRL, an epoch-based algorithm, following which the
agents communicate in the beginning of every epoch. The data collected from
the $M$ agents allows obtaining tighter deviation bounds and hence a smaller
confidence set. Further, the agents trigger an epoch only after collecting
sufficient samples in every epoch. This allows us to bound the regret of the
dist-UCRL algorithm as $\tilde{O}(DS\sqrt{MAT})$ and the number of
communication rounds as $O(MAS\log_{2}(MT))$. To analyze our algorithm, we
also provide a concentration inequality for $M$ independent Martingale
sequence of equal length which may be of an independent interest. We also
evaluate the algorithm empirically and found that the average per-agent regret
decreases as $O(1/\sqrt{M})$.

For comparison, we consider an extension of the UCRL2 algorithm for $M$
parallel agents working in round-robin sequence, and denote this algorithm as
mod-UCRL2. We show that this algorithm also achieves the same regret bound as
dist-UCRL algorithm, while with $O(T)$ communication rounds. The regret
guarantee required the techniques developed for dist-UCRL. The evaluation
results demonstrate the effectiveness of the proposed dist-UCRL algorithm in
achieving the same regret bound as mod-UCRL2, while with lower communication.
Thus, the proposed dist-UCRL algorithm can be utilized in training multiple
parallel power starved devices using reinforcement learning.

Possible future works for the proposed works include analysing parallel RL and
dist-UCRL algorithm with differential privacy, where agents may send data with
additional noise to protect privacy.

## References

  * Agrawal and Jia [2017] Shipra Agrawal and Randy Jia.  Optimistic posterior sampling for reinforcement learning: worst-case regret bounds.  In _Proceedings of the 31st International Conference on Neural Information Processing Systems_ , pages 1184–1194, 2017.
  * Al-Abbasi et al. [2019] Abubakr O Al-Abbasi, Arnob Ghosh, and Vaneet Aggarwal.  Deeppool: Distributed model-free algorithm for ride-sharing using deep reinforcement learning.  _IEEE Transactions on Intelligent Transportation Systems_ , 20(12):4714–4727, 2019.
  * Assran et al. [2019] Mahmoud Assran, Joshua Romoff, Nicolas Ballas, Joelle Pineau, and Michael Rabbat.  Gossip-based actor-learner architectures for deep reinforcement learning.  In _Advances in Neural Information Processing Systems_ , volume 32, 2019.
  * Bartlett and Tewari [2009] Peter L Bartlett and Ambuj Tewari.  Regal: a regularization based algorithm for reinforcement learning in weakly communicating mdps.  In _Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence_ , pages 35–42, 2009.
  * Bertsekas [1995] Dimitri P Bertsekas.  _Dynamic programming and optimal control_ , volume 1.  1995\.
  * Chawla et al. [2020] Ronshee Chawla, Abishek Sankararaman, Ayalvadi Ganesh, and Sanjay Shakkottai.  The gossiping insert-eliminate algorithm for multi-agent bandits.  In _International Conference on Artificial Intelligence and Statistics_ , pages 3471–3481. PMLR, 2020.
  * Clemente et al. [2017] Alfredo V Clemente, Humberto N Castejón, and Arjun Chandra.  Efficient parallel methods for deep reinforcement learning.  _arXiv preprint arXiv:1705.04862_ , 2017.
  * Dubey and Pentland [2020] Abhimanyu Dubey and AlexSandy’ Pentland.  Differentially-private federated linear bandits.  _Advances in Neural Information Processing Systems_ , 33, 2020.
  * Espeholt et al. [2018] 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.
  * Gupta et al. [2017] Jayesh K Gupta, Maxim Egorov, and Mykel Kochenderfer.  Cooperative multi-agent control using deep reinforcement learning.  In _International Conference on Autonomous Agents and Multiagent Systems_ , pages 66–83. Springer, 2017.
  * Haarnoja et al. [2018] Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine.  Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor.  In _International Conference on Machine Learning_ , pages 1861–1870. PMLR, 2018.
  * Hillel et al. [2013] Eshcar Hillel, Zohar Karnin, Tomer Koren, Ronny Lempel, and Oren Somekh.  Distributed exploration in multi-armed bandits.  In _Proceedings of the 26th International Conference on Neural Information Processing Systems-Volume 1_ , pages 854–862, 2013.
  * Hoeffding [1994] Wassily Hoeffding.  Probability inequalities for sums of bounded random variables.  In _The Collected Works of Wassily Hoeffding_ , pages 409–426. Springer, 1994.
  * Horgan et al. [2018] Dan Horgan, John Quan, David Budden, Gabriel Barth-Maron, Matteo Hessel, Hado van Hasselt, and David Silver.  Distributed prioritized experience replay.  In _International Conference on Learning Representations_ , 2018.
  * Howard [1960] Ronald A Howard.  Dynamic programming and markov processes.  1960\.
  * Hu et al. [2020] Junyan Hu, Hanlin Niu, Joaquin Carrasco, Barry Lennox, and Farshad Arvin.  Voronoi-based multi-robot autonomous exploration in unknown environments via deep reinforcement learning.  _IEEE Transactions on Vehicular Technology_ , 2020.
  * Ian et al. [2013] Osband Ian, Van Roy Benjamin, and Russo Daniel.  (more) efficient reinforcement learning via posterior sampling.  In _Proceedings of the 26th International Conference on Neural Information Processing Systems-Volume 2_ , pages 3003–3011, 2013.
  * Jaksch et al. [2010] Thomas Jaksch, Ronald Ortner, and Peter Auer.  Near-optimal regret bounds for reinforcement learning.  _Journal of Machine Learning Research_ , 11(4), 2010.
  * Jin et al. [2018] Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan.  Is q-learning provably efficient?  In _Proceedings of the 32nd International Conference on Neural Information Processing Systems_ , pages 4868–4878, 2018.
  * Kanade et al. [2012] Varun Kanade, Zhenming Liu, and Božidar Radunović.  Distributed non-stochastic experts.  In _Proceedings of the 25th International Conference on Neural Information Processing Systems-Volume 1_ , pages 260–268, 2012.
  * Kiran et al. [2020] B Ravi Kiran, Ibrahim Sobh, Victor Talpaert, Patrick Mannion, Ahmad A Al Sallab, Senthil Yogamani, and Patrick Pérez.  Deep reinforcement learning for autonomous driving: A survey.  _arXiv preprint arXiv:2002.00444_ , 2020.
  * Lattimore and Szepesvári [2020] Tor Lattimore and Csaba Szepesvári.  _Bandit algorithms_.  Cambridge University Press, 2020.
  * Manchella et al. [2021] Kaushik Manchella, Abhishek K Umrawal, and Vaneet Aggarwal.  Flexpool: A distributed model-free deep reinforcement learning algorithm for joint passengers and goods transportation.  _IEEE Transactions on Intelligent Transportation Systems_ , 2021.
  * Mnih et al. [2013] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller.  Playing atari with deep reinforcement learning.  _arXiv preprint arXiv:1312.5602_ , 2013.
  * Mnih et al. [2016] Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu.  Asynchronous methods for deep reinforcement learning.  In _International conference on machine learning_ , pages 1928–1937. PMLR, 2016.
  * Nair et al. [2015] Arun Nair, Praveen Srinivasan, Sam Blackwell, Cagdas Alcicek, Rory Fearon, Alessandro De Maria, Vedavyas Panneershelvam, Mustafa Suleyman, Charles Beattie, Stig Petersen, et al.  Massively parallel methods for deep reinforcement learning.  _arXiv preprint arXiv:1507.04296_ , 2015.
  * Puterman [1994] Martin L. Puterman.  _Markov Decision Processes: Discrete Stochastic Dynamic Programming_.  John Wiley & Sons, Inc., New York, NY, USA, 1st edition, 1994.  ISBN 0471619779.
  * Sankararaman et al. [2019] Abishek Sankararaman, Ayalvadi Ganesh, and Sanjay Shakkottai.  Social learning in multi agent multi armed bandits.  _Proceedings of the ACM on Measurement and Analysis of Computing Systems_ , 3(3):1–35, 2019.
  * Sartoretti et al. [2019] Guillaume Sartoretti, Yue Wu, William Paivine, TK Satish Kumar, Sven Koenig, and Howie Choset.  Distributed reinforcement learning for multi-robot decentralized collective construction.  In _Distributed autonomous robotic systems_ , pages 35–49. Springer, 2019.
  * Schulman et al. [2015] John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz.  Trust region policy optimization.  In _International conference on machine learning_ , pages 1889–1897. PMLR, 2015.
  * Schulman et al. [2017] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov.  Proximal policy optimization algorithms.  _arXiv preprint arXiv:1707.06347_ , 2017.
  * Sutton and Barto [2018] Richard S Sutton and Andrew G Barto.  _Reinforcement learning: An introduction_.  MIT press, 2018.
  * Tossou et al. [2019] Aristide C. Y. Tossou, Debabrota Basu, and Christos Dimitrakakis.  Near-optimal optimistic reinforcement learning using empirical bernstein inequalities.  _CoRR_ , abs/1905.12425, 2019.
  * Wang et al. [2019] Yuanhao Wang, Jiachen Hu, Xiaoyu Chen, and Liwei Wang.  Distributed bandit learning: Near-optimal regret with efficient communication.  In _International Conference on Learning Representations_ , 2019.
  * Weissman et al. [2003] Tsachy Weissman, Erik Ordentlich, Gadiel Seroussi, Sergio Verdu, and Marcelo J Weinberger.  Inequalities for the l1 deviation of the empirical distribution.  2003\.
  * Zhang et al. [2018] Kaiqing Zhang, Zhuoran Yang, Han Liu, Tong Zhang, and Tamer Basar.  Fully decentralized multi-agent reinforcement learning with networked agents.  In _International Conference on Machine Learning_ , pages 5872–5881. PMLR, 2018.

##  Appendix A Proof of the concentration bound of sum of independent
Martingales

######  Lemma 7.

Let $\\{X_{i,t}\\}_{t=1}^{T}$ be a zero-mean Martingale sequence for
$i=1,\cdots,M$ adapted to filtration $\\{\mathcal{F}_{t}\\}_{t=0}^{T}$. Then,
if $\\{X_{i,t}\\}_{t=1}^{T}$ and $\\{X_{j,t}\\}_{t=1}^{T}$ are independent for
all $i\neq j$ and $|X_{i,t}|X_{i,t-1}|\leq c$ for all $i,t$, we have,

$\displaystyle
P(\sum_{t=1}^{T}\sum_{i=1}^{M}X_{i,t}\geq\epsilon)\leq\exp{\left(-\frac{2\epsilon^{2}}{MTc^{2}}\right)}$
(19)

###### Proof.

For any $s>0$, we can write

$\displaystyle P\left(\sum_{t=1}^{T}\sum_{i=1}^{M}X_{i,t}\geq\epsilon\right)$
(20)
$\displaystyle=P\left((\exp{\left(s\left(\sum_{i=1}^{M}\sum_{t=1}^{T}X_{i,t}\right)\right)}\geq\exp{(s\epsilon)}\right)$
(21)
$\displaystyle\leq\frac{\mathbb{E}\left[\exp{\left(s\left(\sum_{i=1}^{M}\sum_{t=1}^{T}X_{i,t}\right)\right)}\right]}{\exp{(s\epsilon)}}$
(22)
$\displaystyle=\frac{\mathbb{E}\left[\prod_{i=1}^{M}\exp{\left(s\left(\sum_{t=1}^{T}X_{i,t}\right)\right)}\right]}{\exp{(s\epsilon)}}$
(23)
$\displaystyle=\frac{\prod_{i=1}^{M}\mathbb{E}\left[\exp{\left(s\left(\sum_{t=1}^{T}X_{i,t}\right)\right)}\right]}{\exp{(s\epsilon)}}$
(24)
$\displaystyle=\frac{\prod_{i=1}^{M}\mathbb{E}\left[\exp{\left(s\sum_{t=1}^{T-1}X_{i,t}\right)\mathbb{E}\left[\exp{\left(sX_{i,T}\right)}|X_{i,T-1}\right]}\right]}{\exp{(s\epsilon)}}$
$\displaystyle\leq\frac{\prod_{i=1}^{M}\mathbb{E}\left[\exp{\left(s\left(\sum_{t=1}^{T-1}X_{i,t}\right)\right)}\exp{(s^{2}c^{2}/8)}\right]}{\exp{(s\epsilon)}}$
(25)
$\displaystyle\leq\frac{\prod_{i=1}^{M}\prod_{t=1}^{T}\exp{\left(s^{2}c^{2}/8\right)}}{\exp{(s\epsilon)}}$
(26)
$\displaystyle=\frac{\exp{\left(MTs^{2}c^{2}/8\right)}}{\exp{(s\epsilon)}}$
(27)
$\displaystyle\leq\sup_{s}\frac{\exp{\left(MTs^{2}c^{2}/8\right)}}{\exp{(s\epsilon)}}=\exp{\left(-\frac{2\epsilon^{2}}{MTc^{2}}\right)}$
(28)

Equation (24) follows from independence of sequences from each other. Equation
(25) follows from Hoeffding’s lemma [Hoeffding, 1994] on the last random
variable of sequence, and Equation (26) follows from applying Hoeffding’s
lemma iteratively. Choosing $s$ that minimizes the expression in Equation (27)
we get the required result. ∎

##  Appendix B Bounds on Probability of Event
$\mathcal{M}\notin\mathscr{M}(t)$

######  Lemma 8.

The probability of the event that the set $\mathscr{M}(t)$ does not contain
the true MDP $\mathcal{M}$ is bounded as:

$\displaystyle\mathbb{P}\left(\mathcal{M}\notin\mathscr{M}(t)\right)\leq\frac{1}{15(Mt)^{6}}$
(29)

###### Proof.

From Lemma 1, the $\ell_{1}$ distance of a probability distribution over $S$
events with $n$ samples is bounded as:

$\displaystyle\mathbb{P}\left(\|P(\cdot|s,a)-\hat{P}(\cdot|s,a)\|_{1}\geq\epsilon\right)\leq(2^{S}-2)\exp{\left(-\frac{n\epsilon^{2}}{2}\right)}\leq(2^{S})\exp{\left(-\frac{n\epsilon^{2}}{2}\right)}$
(30)

This, for some given number of visits $n(s,a)$ to state action pair $(s,a)$
and
$\epsilon=\sqrt{\frac{2}{n(s,a)}\log(2^{S}20SA(Mt)^{7})}\leq\sqrt{\frac{14S}{n(s,a)}\log(2A(Mt))}$
gives,

$\displaystyle\mathbb{P}\left(\|P(\cdot|s,a)-\hat{P}(\cdot|s,a)\|_{1}\geq\sqrt{\frac{14S}{n(s,a)}\log(2A(Mt))}\right)$
$\displaystyle\leq(2^{S})\exp{\left(-\frac{n(s,a)}{2}\frac{2}{n(s,a)}\log(2^{S}20SA(Mt)^{7})\right)}$
(31) $\displaystyle=2^{S}\frac{1}{2^{S}20SA(Mt)^{7}}=\frac{1}{20AS(Mt)^{7}}$
(32)

We sum over the all the possible values of $n(s,a)$ till $t$ time-step to
bound the probability that the event $\mathcal{E}_{t}$ does not occur as:

$\displaystyle\sum_{n(s,a)=1}^{t}\frac{1}{20SA(Mt)^{7}}\leq\frac{1}{20SA(Mt)^{6}}$
(33)

Also, the rewards $r_{t}$, conditioned on $(s_{t},a_{t})=(s,a)$, are
independent and identically distributed over $[0,1]$ with mean $\bar{r}(s,a)$.
Hence, using Hoeffding’s concentration bounds, we have the $\ell_{1}$ distance
of reward estimates $\hat{r}(s,a)$ of $\bar{r}(s,a)$ with $n$ samples is
bounded as:

$\displaystyle\mathbb{P}\left(|\hat{r}(s,a)-\bar{r}(s,a)|\geq\epsilon\right)\leq
2\exp{\left(-2n\epsilon^{2}\right)}$ (34)

This, for
$\epsilon=\sqrt{\frac{1}{2n(s,a)}\log(120SA(Mt)^{7})}\leq\sqrt{\frac{7}{2n(s,a)}\log(2SA(Mt))}$
gives,

$\displaystyle\mathbb{P}\left(|\hat{r}(s,a)-\bar{r}(s,a)|\geq\epsilon\right)$
$\displaystyle\leq 2\exp{\left(-2n\frac{\log(120SA(Mt)^{7})}{2n(s,a)}\right)}$
(35) $\displaystyle\leq 2\frac{1}{120SA(Mt)^{7}}=\frac{1}{60SA(Mt)^{7}}$ (36)

We sum over the all the possible values of $n(s,a)$ till $t$ time-step to
bound the probability that $\mathcal{M}\notin\mathcal{M}(t)$ does not occur
as:

$\displaystyle\mathbb{P}\left(\|P(\cdot|s,a)-\hat{P}(\cdot|s,a)\|_{1}\geq\sqrt{\frac{14S}{N(s,a)}\log(2A(Mt))}\right)\leq\sum_{n(s,a)=1}^{t}\frac{1}{20SA(Mt)^{7}}\leq\frac{1}{20SA(Mt)^{6}}$
(37)
$\displaystyle\mathbb{P}\left(|\hat{r}(s,a)-\bar{r}(s,a)|\geq\sqrt{\frac{7}{2N(s,a)}\log(2SA(Mt))}\right)\leq\sum_{n(s,a)=1}^{t}\frac{1}{60SA(Mt)^{7}}\leq\frac{1}{60SA(Mt)^{6}}$
(38)

where $N(s,a)$ denotes the number of visitations to $s,a$ till $t$.

Finally, summing over all the $s,a$, we get,

$\displaystyle\mathbb{P}\left(\mathcal{M}\notin\mathscr{M}(t)\right)\leq\frac{1}{15(Mt)^{6}}$
(39)

∎

##  Appendix C Proof of the Regret Bound

###### Proof.

We want to bound $\Delta(\mathcal{M},\textsc{dist-UCRL},s,T)$. The dist-UCRL
algorithm proceeds in epoch and generates a new policy for each epoch $k$
using an optimistic MDP from set $\mathscr{M}(t_{k})$. For that, we construct
two cases as enumerated:

  1. (a)

Case where the true MDP $\mathcal{M}$ lies in the set $\mathscr{M}(t_{k})$ for
all $k$:. In this case, we will bound the regret with the terms corresponding
to parts 1, 2, and 3, of the four sources of regret as mentioned in the main
text, and analyze each of them.

From the definition of regret, we have:

$\displaystyle\Delta(\mathcal{M},\textsc{dist-UCRL},s,T)$
$\displaystyle=\sum_{i=1}^{M}\sum_{t=1}^{T}\rho^{*}-\sum_{i=1}^{M}\sum_{t=1}^{T}r_{i,t}$
$\displaystyle=\sum_{i=1}^{M}\sum_{t=1}^{T}(\rho^{*}-\mathbb{E}[r_{i,t}])+\sum_{i=1}^{M}\sum_{t=1}^{T}\left(\mathbb{E}[r_{i,t}]-r_{i,t}\right)$
$\displaystyle=\sum_{i=1}^{M}\sum_{k=1}^{m}\sum_{s,a}\nu_{i,k}(s,a)\left(\rho^{*}-\bar{r}(s,a)\right)+\sum_{i=1}^{M}\sum_{t=1}^{T}\left(\mathbb{E}[r_{i,t}]-r_{i,t}\right)$
(40)
$\displaystyle\leq\sum_{i=1}^{M}\sum_{k=1}^{m}\sum_{s,a}\nu_{i,k}(s,a)\left(\tilde{\rho}_{t_{k}}+\frac{1}{\sqrt{Mt_{k}}}-\bar{r}(s,a)\right)+\sum_{i=1}^{M}\sum_{t=1}^{T}\left(\mathbb{E}[r_{i,t}]-r_{i,t}\right)$
(41)

Equation (40) follows from the fact that at time $t$ playing action $a$ in
state $s$, the expected reward $\mathbb{E}[r_{i,t}]=\bar{r}(s,a)$ for any
agent $i\in[M]$. Equation (41) follows from the fact that the Extended Value
Iteration algorithm returns an $1/\sqrt{Mt_{k}}$-optimal policy for the
optimistic MDP $\tilde{\mathcal{M}_{t}}\in\mathscr{M}(t)$ at time $t_{k}$ and
hence the gain $\tilde{\rho}_{t_{k}}$ of the policy $\pi_{k}$ for
$\tilde{\mathcal{M}}$ satisfies
$\tilde{\rho}_{t_{k}}\geq\rho^{*}(\tilde{\mathcal{M}})-\frac{1}{\sqrt{Mt_{k}}}\geq\rho^{*}(\mathcal{M})-\frac{1}{\sqrt{Mt_{k}}}=\rho^{*}-\frac{1}{\sqrt{Mt_{k}}}$.
Further, the algorithm runs the policy $\pi_{k}$ for entire epoch $k$. We will
now separate the terms in Equation (41) to different parts as explained below.

1\. Regret from deviating from expected reward: This denotes the second
summation in Equation (41). Since the reward $r_{i,t}\in[0,1]$, we use
Hoeffding’s Inequality (Lemma 2) to bound the deviation of observed rewards
from expected rewards with high probability:

$\displaystyle\mathbb{P}\left(\sum_{i=1}^{M}\sum_{t=1}^{T}\left(\mathbb{E}[r_{i,t}]-r_{i,t}\right)\leq\sqrt{\frac{5}{8}MT\log(8MT)}\right)$
$\displaystyle\leq\exp{\left(-\frac{2}{MT}\frac{5}{8}MT\log(8MT)\right)}$ (42)
$\displaystyle\leq\left(\frac{1}{4MT}\right)^{5/4}<\frac{1}{12(MT)^{5/4}}$
(43)

This completes part 1.

We now want to bound the first term in Equation (41). Recall that $t_{k}$ was
defined as the time step whenever the epoch $k$ starts. Let
$\tilde{\mathcal{M}}_{k}=(\mathcal{S},\mathcal{A},\tilde{P}_{k},,\tilde{r}_{k})$
be the optimistic MDP in $\mathscr{M}(t)$. Then, we overload the notation and
let $\tilde{P}_{k}(s^{\prime}|s)=\tilde{P}(s^{\prime}|s,\pi_{k}(s))$ denote
the transition probability matrix for the Markov Chain induced by the policy
$\pi_{k}$ on MDP $\tilde{\mathcal{M}}$. Also, let $\tilde{v}_{k}$ denote the
bias vector of the policy $\pi_{k}$ for MDP $\tilde{\mathcal{M}}$. Then
$\tilde{P}_{k}\tilde{v}_{k}$ is a vector and $\tilde{P}_{k}\tilde{v}_{k}(s)$
denote its $s^{th}$ element. Similarly, we overload the true transition
probability $P$ into a matrix $P_{k}$ and obtain a corresponding vector
$P_{k}v_{k}$. Further, both $\bar{r}$, and $\tilde{r}_{k}$ satisfy Equation
(6) for mean estimated mean $\hat{\bar{r}}$. Hence, for all $s,a$, we have:

$\displaystyle|\tilde{r}_{k}(s,a)-\bar{r}(s,a)|$
$\displaystyle\leq|\tilde{r}_{k}(s,a)-\hat{\bar{r}}_{k}(s,a)|+|\hat{\bar{r}}_{k}(s,a)-\bar{r}(s,a)|$
(44) $\displaystyle\leq
2\sqrt{\frac{7\log(2MSAt_{k})}{\max\\{1,N_{k}(s,a)\\}}}\eqqcolon d_{k}(s,a)$
(45)

We now consider the gain-bias relationship from [Puterman, 1994] as:

$\displaystyle\sum_{i\in[M]}\sum_{k=1}^{m}\sum_{s,a}\nu_{i,k}(s,a)\left(\tilde{\rho}_{t_{k}}+\frac{1}{\sqrt{Mt_{k}}}-\bar{r}(s,a)\right)$
$\displaystyle=\sum_{i\in[M]}\sum_{k=1}^{m}\sum_{s,a}\nu_{i,k}(s,a)\left(\tilde{\rho}_{t_{k}}-\tilde{r}_{k}(s,a)+\left(\tilde{r}_{k}(s,a)-\bar{r}(s,a)\right)+\frac{1}{\sqrt{Mt_{k}}}\right)$
$\displaystyle=\sum_{i\in[M]}\sum_{k=1}^{m}\sum_{s,a}\nu_{i,k}(s,a)\left(\tilde{P}_{k}\tilde{v}_{k}(s)-\tilde{v}_{k}(s)+\left(\tilde{r}_{k}(s,a)-\bar{r}(s,a)\right)+\frac{1}{\sqrt{Mt_{k}}}\right)$
(46)
$\displaystyle=\sum_{i\in[M]}\sum_{k=1}^{m}\sum_{s,a}\nu_{i,k}(s,a)(P_{k}\tilde{v}_{k}(s)-\tilde{v}_{k}(s))$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
+\sum_{i\in[M]}\sum_{k=1}^{m}\sum_{s,a}\nu_{i,k}(s,a)\left((\tilde{P}_{k}\tilde{v}_{k}(s)-P_{k}\tilde{v}_{k}(s))+\left(\tilde{r}_{k}(s,a)-\bar{r}(s,a)\right)+\frac{1}{\sqrt{Mt_{k}}}\right)$
(47)

where Equation (46) follows from Equation (5). Note that the first term in
Equation (47) denotes part 2, or the regret from deviating from the expected
next state. The second term in Equation (47) denotes part 3, or the regret
when algorithm is not accurately optimizing for the true MDP.

2\. Regret from deviating from the expected next state: Note that $t_{k+1}-1$
is the last time step of the epoch. Using this, we can upper bound the first
term of the Equation (47) as:

$\displaystyle\sum_{i\in[M]}\sum_{k=1}^{m}\sum_{s,a}\nu_{i,k}(s,a)(P\tilde{v}_{k}(s)-\tilde{v}_{k}(s))$
$\displaystyle=\sum_{i\in[M]}\sum_{k=1}^{m}\sum_{t=t_{k}}^{t_{k+1}-1}(P\tilde{v}_{k}(s_{i,t})-\tilde{v}_{k}(s_{i,t}))$
(48)
$\displaystyle=\sum_{i\in[M]}\sum_{k=1}^{m}\sum_{t=t_{k}}^{t_{k+1}-1}(P\tilde{v}_{k}(s_{i,t})-\tilde{v}_{k}(s_{i,t+1}))$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\
+\sum_{i\in[M]}\sum_{k=1}^{m}(\tilde{v}_{k}(s_{i,t_{k+1}})-\tilde{v}_{k}(s_{i,t_{k}}))$
(49)
$\displaystyle=\sum_{i\in[M]}\sum_{k=1}^{m}\sum_{t=t_{k}}^{t_{k+1}-1}(P\tilde{v}_{k}(s_{i,t})-\tilde{v}_{k}(s_{i,t+1}))+MmD$
(50)
$\displaystyle=\sum_{i\in[M]}\sum_{k=1}^{m}\sum_{t=t_{k}}^{t_{k+1}-1}(X_{i,t})+MmD$
(51) $\displaystyle=\sum_{i\in[M]}\sum_{t=1}^{T}(X_{i,t})+MmD$ (52)

where Equation (48) follows from the fact that
$\sum_{a}\nu_{i,k}(s,a)=\sum_{t=t_{k}}^{t_{k+1}-1}\bm{1}\\{s_{t}=s\\}$.
Equation (50) follows from Lemma 6. Now, note that $X_{i,t}$ is a Martingale
difference sequence for each $i\in[M]$. Further, the processes are independent
as the environments of each agent are independent. Hence, the first term in
Equation 52 is sum of $M$ independent Martingale sequences of length $T$ such
that $0\leq\tilde{v}_{k}(s_{i,t})\leq D$. Hence, using the Lemma 3 for $c=2D$,
with probability at least $1-1/(12(MT)^{5/4})$, we get:

$\displaystyle\sum_{i=1}^{M}\sum_{k=1}^{m}\sum_{s,a}\nu_{i,k}(s,a)(P\tilde{v}_{k}(s)-\tilde{v}_{k}(s))$
$\displaystyle\leq D\sqrt{2MT\frac{5}{4}\log(8MT)}+MmD$ (53)

This completes part 2\.

3\. Regret from not optimizing for the true MDP: We now attempt to bound the
second term in Equation (47) which denotes the distance of the estimated
transition probability and the true transition probabilities:

$\displaystyle\sum_{i=1}^{M}\sum_{k=1}^{m}\sum_{s,a}\nu_{i,k}(s,a)((\tilde{P}_{k}\tilde{v}_{k}(s)-P\tilde{v}_{k}(s))+({\tilde{r}}_{k}(s,a)-\bar{r}(s,a))+\frac{1}{\sqrt{Mt_{k}}})$
$\displaystyle\leq\sum_{s,a}\sum_{k=1}^{m}\sum_{i=1}^{M}\nu_{i,k}(s,a)((\tilde{P}_{k}\tilde{v}_{k}(s)-P\tilde{v}_{k}(s))+d_{k}(s,a)+\frac{1}{\sqrt{Mt_{k}}})$
(54)
$\displaystyle\leq\sum_{s,a}\sum_{k=1}^{m}\sum_{i=1}^{M}\nu_{i,k}(s,a)\left(\|\tilde{P}_{k}-P\|_{1}\|\tilde{v}_{k}(s)\|_{\infty}+d_{k}(s,a)+\frac{1}{\sqrt{Mt_{k}}}\right)$
(55)
$\displaystyle\leq\sum_{s,a}\sum_{k=1}^{m}\sum_{i=1}^{M}\nu_{i,k}(s,a)\left(D\|\tilde{P}_{k}-P\|_{1}+d_{k}(s,a)+\frac{1}{\sqrt{Mt_{k}}}\right)$
(56)
$\displaystyle\leq\sum_{s,a}\sum_{k=1}^{m}\sum_{i=1}^{M}\nu_{i,k}(s,a)\left(D\|\tilde{P}_{k}-P\|_{1}\right)+d_{k}(s,a)+\sum_{s,a}\sum_{k=1}^{m}\sum_{i=1}^{M}\nu_{i,k}(s,a)\left(\frac{1}{\sqrt{Mt_{k}}}\right)$
(57)

where Equation (54) holds from using Equation (45). Equation (55) follows from
Hölder’s inequality. Equation (56) follows from Lemma 6 and noting that
$\tilde{v}$ is translation invariant, and hence we can choose
$\min_{s}\tilde{v}(s)\geq 0$. Now, note that $\tilde{P}_{k},P_{k}$, both
satisfy Equation (7). Hence, $\|\tilde{P}_{k}-P_{k}\|_{1}$ is upper bounded by
the diameter of the set $\mathscr{P}_{t_{k}}$. Further,
$N_{k}(s,a)\leq\sum_{s,a}N_{k}(s,a)=Mt_{k}$. This gives us:

$\displaystyle\leq\sum_{s,a}\sum_{k=1}^{m}\sum_{i=1}^{M}\nu_{i,k}(s,a)\frac{2\sqrt{7\log(2MSAt_{k})}+2D\sqrt{14S\log(2MAt_{k})}+1}{\sqrt{N_{k}(s,a)}}$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
+\sum_{s,a}\sum_{k=1}^{m}\sum_{i=1}^{M}\nu_{i,k}(s,a)\frac{1}{\sqrt{N_{k}(s,a)}}$
(58) $\displaystyle\leq
2\left(\sqrt{7\log(2MSAT)+1}+D\sqrt{14S\log(2MAT)}\right)$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\times\left(\sum_{s,a}\sum_{k=1}^{m}\frac{\sum_{i=1}^{M}\nu_{i,k}(s,a)}{\sqrt{N_{k}(s,a)}}+\sum_{s,a}\sum_{k=1}^{m}\frac{\sum_{i=1}^{M}\nu_{i,k}(s,a)}{\sqrt{N_{k}(s,a)}}\right)$
$\displaystyle\leq(\sqrt{2}+1)2\left(\sqrt{7\log(2MSAT)+1}+D\sqrt{14S\log(2MAT)}\right)\sum\nolimits_{s,a}\left(\sqrt{N(s,a)}+\sum_{k=1}^{m}\frac{M-1}{\sqrt{N_{k}(s,a)}}\right)$
(59)
$\displaystyle\leq(\sqrt{2}+1)2\left(\sqrt{7\log(2MSAT)+1}+D\sqrt{14S\log(2MAT)}\right)\sum\nolimits_{s,a}\left(\sqrt{N(s,a)}+\sum_{k=1}^{m}(M-1)\right)$
(60)
$\displaystyle\leq(\sqrt{2}+1)2\left(\sqrt{7\log(2MSAT)+1}+D\sqrt{14S\log(2MAT)}\right)$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\times\left(\sqrt{\left(\sum\nolimits_{s,a}1\right)\left(\sum\nolimits_{s,a}N(s,a)\right)}+m(M-1)SA\right)$
(61)
$\displaystyle\leq(\sqrt{2}+1)2\left(\sqrt{7\log(2MSAT)+1}+D\sqrt{14S\log(2MAT)}\right)\left(\sqrt{SAMT}+m(M-1)SA\right)$
(62)

Equation (59) follows from Lemma 5 and Lemma 4. Further, we note that if
$N(s,a)=0$, then $N_{k}(s,a)=0$ for all $k$, and $\nu_{i,k}=0$ for all $k,i$.
Hence, $N_{k}(s,a)\geq 1$ for all $k$ in Equation (59) and this gives Equation
(60). Equation (61) follows from the Cauchy Schwarz inequality.

This completes part 3.

  2. (b)

Case where the true MDP $\mathcal{\notin}\mathscr{M}(t_{k})$ for some $k$: For
this case, we use a trivial bound of $1$ for each agent $i$ at each time step
$t$. This is because the reward $r_{i,t}$ lie in $[0,1]$ for all $i\in[M]$ and
for all $t=1,2,\cdots,T$. Using this, we show that the regret remains bounded
by $\sqrt{MT}$ with high probability . We bound the regret incurred for this
case in part 4..

4\. Regret when the estimated MDP is far from the true MDP $\mathcal{M}$: In
the following, we bound the probability of the event when the
$\ell_{1}$-deviation bounds in Equation (7) and the bounds in Equation (6)
fail to hold. Note that the regret of any time step is upper bound by $1$ as
$r_{t}\in[0,1]$. Hence,

$\displaystyle\sum_{i=1}^{M}\sum_{k=1}^{m}\nu_{i,k}(s,a)\bm{1}_{\\{\mathcal{M}\notin\mathscr{M}(t_{k})\\}}$
$\displaystyle=\sum_{k=1}^{m}\sum_{i=1}^{M}\nu_{i,k}(s,a)\bm{1}_{\\{\mathcal{M}\notin\mathscr{M}(t_{k})\\}}$
(63)
$\displaystyle\leq\sum_{k=1}^{m}N_{k}(s,a)\bm{1}_{\\{\mathcal{M}\notin\mathscr{M}(t_{k})\\}}$
(64)
$\displaystyle\leq\sum_{k=1}^{m}Mt_{k}\bm{1}_{\\{\mathcal{M}\notin\mathscr{M}(t_{k})\\}}$
(65)
$\displaystyle\leq\sum_{t=1}^{T}Mt\bm{1}_{\\{\mathcal{M}\notin\mathscr{M}(t)\\}}$
(66) $\displaystyle\leq
M\sum\nolimits_{t=1}^{(T/M)^{1/4}}t+\sum\nolimits_{t=(T/M)^{1/4}+1}^{T}t\bm{1}_{\\{\mathcal{M}\notin\mathscr{M}(t)\\}}$
$\displaystyle\leq\sqrt{MT}+\sum\nolimits_{t=(T/M)^{1/4}+1}^{T}t\bm{1}_{\\{\mathcal{M}\notin\mathscr{M}(t)\\}}$
(67)

where (64) follows from Lemma 4. Now, we bound the probability of the event
$\\{\mathcal{M}\notin\mathscr{M}(t)\\}$ with $1/(15(Mt)^{6})$ for all $t$
using Lemma 8 (which uses Lemma 1, refer Appendix B for a detailed proof).
Taking union bounds over
$\\{\mathcal{M}\notin\mathscr{M}(t_{k})\\},t\geq(T/M)^{1/4}+1$, we get

$\displaystyle\sum_{t=(T/M)^{1/4}+1}^{T}\mathbb{P}(\bm{1}_{\\{\mathcal{M}\notin\mathscr{M}(t)\\}})$
$\displaystyle\leq\sum_{t=(T/M)^{1/4}+1}^{\infty}\mathbb{P}(\bm{1}_{\\{\mathcal{M}\notin\mathscr{M}(t)\\}})$
$\displaystyle\leq\int_{t=(T/M)^{1/4}}^{\infty}\mathbb{P}(\bm{1}_{\\{\mathcal{M}\notin\mathscr{M}(t)\\}})$
$\displaystyle\leq\int_{t=(T/M)^{1/4}}^{\infty}\frac{1}{(Mt)^{6}}\leq\frac{M^{5/4}}{12M^{6}T^{5/4}}\leq\frac{1}{12(MT)^{5/4}}$

This complete part 4 of the regret sources and all the cases pertaining to the
true MDP $\mathcal{M}$.

Summing over all the possible sources of regret, we obtain the required bound
on the regret. Further, using union bound on all the event when the
concentration bounds fails to hold, we establish that the regret bound in
Equation (8) holds with high probability. ∎

##  Appendix D Bound on number of communication rounds

###### Proof.

Let $N(s,a)$ be the total number of visits to the state action pair $(s,a)$
across all agents when algorithm dist-UCRL terminates. Let $K(s,a)$ denote the
synchronization rounds requested when $\nu_{i,k}\geq N_{k}(s,a)/M$ for any
agent $i\in[M]$. Now, assuming that agent $i$ triggers the communication round
because $\nu_{i,k}(s,a)\geq N_{k}(s,a)/M$ for some $(s,a)$ and $N_{k}(s,a)>0$.
Then for this $(s,a)$ we have, $N_{k+1}(s,a)\geq N_{k}(s,a)+\nu_{i,k}(s,a)\geq
N_{k}(s,a)(1+1/M)$. Then, for $K(s,a)\geq 1$, we have:

$\displaystyle N(s,a)$
$\displaystyle=\sum_{k=1}^{m}\sum_{i=1}^{M}\nu_{i,k}(s,a)$ (68)
$\displaystyle\geq\left(\frac{1}{M}+\sum_{k:\nu_{i,k}(s,a)\geq
N_{k}(s,a)/M\text{ for any }i}\frac{N_{k}(s,a)}{M}\right)$
$\displaystyle\geq\frac{1}{M}\left(1+\sum_{j}N_{j}(s,a)\right)$ (69)
$\displaystyle\geq\frac{1}{M}\left(1+\sum_{j=1}^{K(s,a)}\left(1+\frac{1}{M}\right)^{j-1}\right)$
(70) $\displaystyle\geq\left(1+\frac{1}{M}\right)^{K(s,a)}$ (71)

where Equation (69) follows for $j\in\\{k:\nu_{i,k}(s,a)\geq
N_{k}(s,a)/M\text{ for any }i\\}$. Equation (70) follows from using $K(s,a)$
lowest $j\in\\{k:\nu_{i,k}(s,a)\geq N_{k}(s,a)/M\text{ for any }i\\}\cup[m]$
and lower bounding the sequence $N_{j}(s,1)$ with $N_{j}(s,a)=1$ for $j=1$.

Now, we note (71) holds when $N(s,a)\geq 1$. Further, we note that whenever
$N(s,a)=0$ or $N(s,a)=1$, we have $K(s,a)=0$. So, to include the case of
$N(s,a)=0$, we have

$\displaystyle N(s,a)\geq(1+\frac{1}{M})^{K(s,a)}-1$ (72)

Also, note that the total visitations $N(s,a)$ for all state action pairs is
the total interactions of $M$ agents with their correspoinding environments
which is $MT$, hence we have

$\displaystyle MT$ $\displaystyle=\sum_{s,a}N(s,a)$ (73)
$\displaystyle\geq\sum_{s,a}\left[\left(1+\frac{1}{M}\right)^{K(s,a)}-1\right]$
(74) $\displaystyle\geq AS\left(1+\frac{1}{M}\right)^{\sum_{s,a}K(s,a)/AS}-SA$
(75) $\displaystyle\implies\sum_{s,a}K(s,a)$
$\displaystyle\leq\frac{AS}{\log_{2}\left(1+\frac{1}{M}\right)}\log_{2}\left(\frac{MT}{SA}+1\right)$
(76) $\displaystyle\leq MAS\log_{2}\left(\frac{MT}{SA}+1\right)$ (77)

where Equation (75) follows from Jensen’s inequality. Equation (77) follows
from the fact that $\frac{1}{M}\leq\log_{2}(1+\frac{1}{M})\forall M\geq 1$.
Now, a new epoch is triggered when
$\nu_{i,k}(s,a)\geq\max\\{1,N_{k}(s,a)\\}/M$. This means that a new epoch will
be triggered whenever $N_{k}(s,a)=0$ and any agent visits $(s,a)$ for the very
first time. Hence, the algorithm can trigger $SA$ epochs even when $K(s,a)=0$
for all $(s,a)$. Also, there is epoch $1$ trivially starts when the algorithm
starts. This gives:

$\displaystyle m$ $\displaystyle\leq 1+AS+\sum\nolimits_{s,a}K(s,a)$ (78)
$\displaystyle\leq 1+2MAS+MAS\log_{2}\left(\frac{MT}{SA}\right),$ (79)

for $T\geq SA/M$. This completes the proof. ∎

##  Appendix E mod-UCRL2 algorithm description

Algorithm 4 Modified UCRL 2 at central server

1: Input: $S,A,M$

2: Set parameters
$P(s,a,s^{\prime})=0\forall(s,a,s^{\prime})\in\mathcal{S}\times\mathcal{A}\times\mathcal{S}$
and $\hat{r}(s,a)=0,N(s,a)=0\leavevmode\nobreak\ \leavevmode\nobreak\
\forall\leavevmode\nobreak\ (s,a)\in\mathcal{S}\times\mathcal{A}$.

3: for Epochs: $k=1,2,\cdots$ do

4: Set $\nu_{k}(s,a)=0\forall(s,a)\in\mathcal{S}\times\mathcal{A}$.

5: for $(s,a)\in\mathcal{S}\times\mathcal{A}$ do

6: Set $N(s,a)=\sum_{s^{\prime}}P(s,a,s^{\prime})$.

7: Set $\hat{p}(s,a,s^{\prime})=\frac{P(s,a,s^{\prime})}{\max\\{1,N(s,a)\\}}$

8: Set $\hat{\bar{r}}(s,a)=\frac{\hat{r}(s,a)}{\max\\{1,N(s,a)\\}}$

9: Set
$\tilde{r}(s,a)=\hat{\bar{r}}(s,a)+\sqrt{\frac{7\log(2MSAt)}{2\max\\{1,N(s,a)\\}}}$

10: Set $d(s,a)=\sqrt{\frac{14S\log(2MAt)}{\max\\{1,N(s,a)\\}}}$

11: end for

12: Set $\pi$ = Extended Value
Iteration($\hat{p},d,\tilde{r},\frac{1}{\sqrt{Mt}}$)

13: while $\nu_{i,k}(s,a)<\max\\{1,N_{k}(s,a)\\}\forall(s,a)$ do

14: Receive state $s_{i,t}$ from agent $i$

15: Send action $a_{i,t}=\pi_{k}(s_{i,t})$ to agent $i$ and receive back
reward $r_{t}$ and next state $s_{i,t+1}$.

16: Set  $\nu_{k}(s_{i,t},a_{i,t})=\nu_{k}(s_{i,t},a_{i,t})+1$
$P(s_{i,{i,t}},a_{i,t},s_{t+1})=P_{i}(s_{i,t},a_{i,t},s_{i,t+1})+1$
$\hat{r}(s_{i,t},a_{i,t})=\hat{r}(s_{i,t},a_{i,t})+r_{t}$

17: Set $i=i+1$.

18: if $i>M$ then

19: $i=1$

20: $t=t+1$

21: end if

22: end while

23: end for

##  Appendix F Proof of the Regret Bound for the Modified UCRL2 Algorithm

###### Proof.

We want to bound $\Delta(\mathcal{M},\textsc{mod-UCRL2},s,T)$. For this, we
reuse most of the proof of Theorem 1.

First note that the number of epochs of the mod-UCRL2 algorithm, $m^{\prime}$,
is upper bounded by $1+AS+AS\log_{2}(MT/SA)$. The proof mostly follows from
Section D. However, the server now performs the update whenever
$\nu_{k}(s,a)=N_{k}(s,a)$. This results in growth factor of $2$ instead of
$(1+1/M)$ in Equation (71).

We again use the fact that the EVI algorithm finds an $\epsilon$-optimal
policy of the optimistic MDP in the neighborhood of the true MDP
$\mathcal{M}$. Recall that, we define server time $t^{\prime}$ to be a pair
$(i,t)$. Let server time $t_{k}^{\prime}$ to be the pair
$\underline{i}_{i},\underline{t}_{k}$ when the epoch $k$ starts. Then, all the
definitions from the analysis of Theorem 1 will translate here with subscripts
changed from $t$ to $t^{\prime}$ and $t_{k}$ to $t_{k}^{\prime}$. Further, we
define $|t^{\prime}|=|(i,t)|=M(t-1)+i$, as the total number of interactions
the agent collectively did with their environments till the server time
$t^{\prime}$. We also define $t^{\prime}+1$, and $t^{\prime}-1$ as:

$\displaystyle t_{i}^{\prime}+1=\begin{cases}(i,t+1)\text{ for
}t_{i}^{\prime}=(i,t),i=K,\\\ (i+1,t)\text{ for
}t_{i}^{\prime}=(i,t),i<K.\end{cases}$ (80) $\displaystyle
t_{i}^{\prime}-1=\begin{cases}(i-1,t)\text{ for }t_{i}^{\prime}=(i,t),i>1,\\\
(K,t-1)\text{ for }t_{i}^{\prime}=(i,t),i=1.\end{cases}$ (81)

The mod-UCRL2 algorithm proceeds in epoch and generates a new policy for each
epoch $k$ using an optimistic MDP from set $\mathscr{M}(t_{k}^{\prime})$. Now,
similar to the proof of Theorem 1, we construct two cases as enumerated:

  1. (a)

Case where the true MDP $\mathcal{M}$ lies in the set
$\mathscr{M}(t_{k}^{\prime})$ for all $k$: In this case, we will bound the
regret with the terms corresponding to parts 1, 2, and 3, of the four sources
of regret as mentioned in the main text for Theorem 1, and analyze each of
them.

Again, from the definition of regret, we have:

$\displaystyle\Delta(\mathcal{M},\textsc{mod-UCRL2},s,T)$
$\displaystyle=\sum_{t^{\prime}=1}^{(M,T)}\rho^{*}-\sum_{t^{\prime}=1}^{(M,T)}r_{t^{\prime}}$
$\displaystyle=\sum_{t^{\prime}=1}^{(M,T)}(\rho^{*}-\mathbb{E}[r_{t^{\prime}}])+\sum_{t^{\prime}=1}^{(M,T)}\left(\mathbb{E}[r_{t^{\prime}}]-r_{t^{\prime}}\right)$
$\displaystyle=\sum_{k=1}^{m}\sum_{s,a}\nu_{k}(s,a)\left(\rho^{*}-\bar{r}(s,a)\right)+\sum_{t^{\prime}=1}^{(M,T)}\left(\mathbb{E}[r_{t^{\prime}}]-r_{t^{\prime}}\right)$
(82)
$\displaystyle\leq\sum_{k=1}^{m}\sum_{s,a}\nu_{k}(s,a)\left(\tilde{\rho}_{t_{k}}+\frac{1}{\sqrt{|t_{k}^{\prime}|}}-\bar{r}(s,a)\right)+\sum_{t^{\prime}=1}^{(M,T)}\left(\mathbb{E}[r_{t^{\prime}}]-r_{t^{\prime}}\right)$
(83)

Equation (82) follows from the fact that at step $t^{\prime}$ playing action
$a$ in state $s$, the expected reward
$\mathbb{E}[r_{t^{\prime}}]=\bar{r}(s,a)$ for any agent $i\in[M]$. Equation
(83) follows from the fact that the Extended Value Iteration algorithm returns
an $1/\sqrt{|t_{k}^{\prime}|}$-optimal policy for the optimistic MDP
$\tilde{\mathcal{M}_{t^{\prime}}}\in\mathscr{M}(t)$ at server time $t_{k}$ and
hence the gain $\tilde{\rho}_{t_{k}^{\prime}}$ of the policy $\pi_{k}$ for
$\tilde{\mathcal{M}}$ satisfies
$\tilde{\rho}_{t_{k}^{\prime}}\geq\rho^{*}(\tilde{\mathcal{M}})-\frac{1}{\sqrt{|t_{k}^{\prime}|}}\geq\rho^{*}(\mathcal{M})-\frac{1}{\sqrt{|t_{k}^{\prime}|}}=\rho^{*}-\frac{1}{\sqrt{|t_{k}^{\prime}|}}$.
Further, the algorithm runs the policy $\pi_{k}$ for entire epoch $k$.

Separating terms in Equation (83), similar to that in the proof of Theorem 1,
we reduce the problem into sum of the three parts as explained below.

1\. Regret from deviating from expected reward: Since the reward
$r_{t^{\prime}}\in[0,1]$, we first bound the second summation in Equation (83)
with high probability using Hoeffding’s inequality (Lemma 2):

$\displaystyle\mathbb{P}\left(\sum_{t^{\prime}=1}^{(M,T)}\left(\mathbb{E}[r_{t^{\prime}}]-r_{t^{\prime}}\right)\leq\sqrt{\frac{5}{8}MT\log(8MT)}\right)$
$\displaystyle=\mathbb{P}\left(\sum_{i=1}^{M}\sum_{t=1}^{T}\left(\mathbb{E}[r_{i,t}]-r_{i,t}\right)\leq\sqrt{\frac{5}{8}MT\log(8MT)}\right)$
(84) $\displaystyle\leq\exp{\left(-\frac{2}{MT}\frac{5}{8}MT\log(8MT)\right)}$
(85)
$\displaystyle\leq\left(\frac{1}{4MT}\right)^{5/4}<\frac{1}{12(MT)^{5/4}}$
(86)

This completes part 1.

We now want to bound the first term in Equation (83). Based on the assumption,
the true MDP $\mathcal{M}$ lies in the set $\mathscr{M}(t_{k}^{\prime})$. Let
$\tilde{\mathcal{M}}_{k}=(\mathcal{S},\mathcal{A},\tilde{P}_{k},,\tilde{r})$
be the optimistic MDP in $\mathscr{M}(t^{\prime})$. Then, we overload the
notation and let
$\tilde{P}_{k}(s^{\prime}|s)=\tilde{P}(s^{\prime}|s,\pi_{k}(s))$ denote the
transition probability matrix for the Markov Chain induced by the policy
$\pi_{k}$ on MDP $\tilde{\mathcal{M}}$. Also, let $\tilde{v}_{k}$ denote the
bias vector of the policy $\pi_{k}$ for MDP $\tilde{\mathcal{M}}$. Then
$\tilde{P}_{k}\tilde{v}_{k}$ is a vector and $\tilde{P}_{k}\tilde{v}_{k}(s)$
denote its $s^{th}$ element. Similarly, we overload the true transition
probability $P$ into a matrix $P_{k}$ and obtain a corresponding vector
$P_{k}v_{k}$. Also, similar to the proof of Theorem 1, we have

$\displaystyle|\tilde{r}-\bar{r}(s,a)|$ $\displaystyle\leq
2d_{k}(s,a):=\sqrt{\frac{7\log(2AS|t_{k}^{\prime}|}{2\max\\{1,N_{k}(s,a)\\}}}$
(87)

We now consider the gain-bias relationship from [Puterman, 1994] as:

$\displaystyle\sum_{k=1}^{m}\sum_{s,a}\nu_{k}(s,a)\left(\tilde{\rho}_{t_{k}^{\prime}}+\frac{1}{\sqrt{|t_{k}^{\prime}|}}-\bar{r}(s,a)\right)$
(88)
$\displaystyle=\sum_{k=1}^{m}\sum_{s,a}\nu_{k}(s,a)\left(\tilde{\rho}_{t_{k}^{\prime}}-\tilde{r}_{k}(s,a)+\left(\tilde{r}_{k}(s,a)-\bar{r}(s,a)\right)+\frac{1}{\sqrt{|t_{k}^{\prime}|}}\right)$
$\displaystyle=\sum_{k=1}^{m}\sum_{s,a}\nu_{k}(s,a)\left(\tilde{P}_{k}\tilde{v}_{k}(s)-\tilde{v}_{k}(s)+\left(\tilde{r}_{k}(s,a)-\bar{r}(s,a)\right)+\frac{1}{\sqrt{|t_{k}^{\prime}|}}\right)$
(89)
$\displaystyle=\sum_{k=1}^{m}\sum_{s,a}\nu_{k}(s,a)(P_{k}\tilde{v}_{k}(s)-\tilde{v}_{k}(s))$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\
+\sum_{k=1}^{m}\sum_{s,a}\nu_{k}(s,a)\left((\tilde{P}_{k}\tilde{v}_{k}(s)-P_{k}\tilde{v}_{k}(s))+\left(\tilde{r}_{k}(s,a)-\bar{r}(s,a)\right)+\frac{1}{\sqrt{|t_{k}^{\prime}|}}\right)$
(90)

where Equation (89) follows from Equation (5). Again, the first term in
Equation (90) denotes part 2, or the regret from deviating from the expected
next state. The second term in Equation (90) denotes part 3, or the regret
when algorithm is not accurately optimizing for the true MDP.

2\. Regret from deviating from the expected next state: Let
$t_{k+1}^{\prime}-1=(\bar{i}_{i},\bar{t}_{k})$ be the last server time step of
the epoch. Using this, we can upper bound the first term of the Equation (90)
as:

$\displaystyle\sum_{k=1}^{m}\sum_{s,a}\nu_{k}(s,a)(P\tilde{v}_{k}(s)-\tilde{v}_{k}(s))$
$\displaystyle=\sum_{k=1}^{m}\sum_{t^{\prime}=t_{k}^{\prime}}^{t_{k+1}^{\prime}-1}(P\tilde{v}_{k}(s_{t^{\prime}})-\tilde{v}_{k}(s_{t^{\prime}}))$
(91)
$\displaystyle=\sum_{k=1}^{m}\sum_{t^{\prime}=t_{k}^{\prime}}^{t_{k+1}^{\prime}-1}(P\tilde{v}_{k}(s_{t^{\prime}})-\tilde{v}_{k}(s_{t^{\prime}+1}))+\sum_{k=1}^{m}(\tilde{v}_{k}(s_{t_{k+1}})-\tilde{v}_{k}(s_{t_{k}}))$
(92)
$\displaystyle=\sum_{k=1}^{m}\sum_{t^{\prime}=t_{k}^{\prime}}^{t_{k+1}^{\prime}-1}(P\tilde{v}_{k}(s_{t^{\prime}})-\tilde{v}_{k}(s_{t^{\prime}+1}))+\sum_{k=1}^{m}(\tilde{v}_{k}(s_{(\bar{i}_{k+1},\bar{t}_{k+1})})-\tilde{v}_{k}(s_{(\underline{i}_{k},\underline{t}_{k})}))$
(93)
$\displaystyle\leq\sum_{k=1}^{m}\sum_{t^{\prime}=t_{k}^{\prime}}^{t_{k+1}^{\prime}-1}(P\tilde{v}_{k}(s_{t^{\prime}})-\tilde{v}_{k}(s_{t^{\prime}+1}))+mD$
(94)
$\displaystyle\leq\sum_{k=1}^{m}\sum_{t^{\prime}=(\underline{i}_{k},\underline{t}_{k})}^{\bar{i}_{k},\bar{t}_{k}}(P\tilde{v}_{k}(s_{t^{\prime}})-\tilde{v}_{k}(s_{t^{\prime}+1}))+mD$
(95)
$\displaystyle\leq\sum_{i=1}^{M}\sum_{k=1}^{m}\sum_{t=\underline{t}_{k}}^{\bar{t}_{k}}(P\tilde{v}_{k}(s_{i,t})-\tilde{v}_{k}(s_{i,t+1}))+mD$
(96)
$\displaystyle\leq\sum_{i=1}^{M}\sum_{k=1}^{m}\sum_{t=\underline{t}_{k}}^{\bar{t}_{k}}X_{i,t}+mD$
(97) $\displaystyle\leq\sum_{i=1}^{M}\sum_{t=1}^{T}X_{i,t}+mD$ (98)

where Equation (91) follows from the fact that
$\sum_{a}\nu_{k}(s,a)=\sum_{t^{\prime}=t_{k}^{\prime}}^{t_{k+1}^{\prime}-1}\bm{1}\\{s_{t^{\prime}}=s\\}$.
Equation (94) follows from Lemma 6 and from the fact that although states
$s_{(\bar{i}_{k+1},\bar{t}_{k+1})}$ and
$s_{(\underline{}{i}_{k},\underline{}{t}_{k})}$ may belong to two different
processes, the processes are identical. Now, we note that the first term in
Equation (98) is sum of $M$ independent Martingale sequences of length $T$
such that $0\leq\tilde{v}_{k}(s_{(i,t)})\leq D$. Hence, using the Lemma 3 for
$c=2D$, with probability at least $1-1/(12(MT)^{5/4})$, we get:

$\displaystyle\sum_{k=1}^{m}\sum_{s,a}\nu_{k}(s,a)(P\tilde{v}_{k}(s)-\tilde{v}_{k}(s))$
$\displaystyle\leq D\sqrt{2MT\frac{5}{4}\log(8MT)}+MmD$ (99)

This completes part 2.

3\. Regret from not optimizing for the true MDP: We now attempt to bound the
second term in Equation (90) which denotes the distance of the estimated
transition probability and the true transition probabilities:

$\displaystyle\sum_{k=1}^{m}\sum_{s,a}\nu_{k}(s,a)((\tilde{P}_{k}\tilde{v}_{k}(s)-P\tilde{v}_{k}(s))+\left(\tilde{r}_{k}(s,a)-\bar{r}(s,a)\right)+\frac{1}{\sqrt{|t_{k}^{\prime}|}})$
$\displaystyle\leq\sum_{s,a}\sum_{k=1}^{m}\nu_{k}(s,a)((\tilde{P}_{k}\tilde{v}_{k}(s)-P\tilde{v}_{k}(s))+d_{k}(s,a)\frac{1}{\sqrt{|t_{k}^{\prime}|}})$
$\displaystyle\leq\sum_{k=1}^{m}\nu_{k}(s,a)\left(\|\tilde{P}_{k}-P\|_{1}\|\tilde{v}_{k}(s)\|_{\infty}+d_{k}(s,a)+\frac{1}{\sqrt{|t_{k}^{\prime}|}}\right)$
(100)
$\displaystyle\leq\sum_{s,a}\sum_{k=1}^{m}\nu_{k}(s,a)\left(D\|\tilde{P}_{k}-P\|_{1}+d_{k}(s,a)+\frac{1}{\sqrt{|t_{k}^{\prime}|}}\right)$
(101)
$\displaystyle\leq\sum_{s,a}\sum_{k=1}^{m}\nu_{k}(s,a)\left(D\|\tilde{P}_{k}-P\|_{1}+d_{k}(s,a)\right)+\sum_{s,a}\sum_{k=1}^{m}\nu_{k}(s,a)\left(\frac{1}{\sqrt{|t_{k}^{\prime}|}}\right)$
(102)

where Equation (100) follows from Hölder’s inequality. Equation (101) follows
from Lemma 6 and noting that $\tilde{v}$ is translation invariant, and hence
we can choose $\min_{s}\tilde{v}(s)\geq 0$. Now, note that
$\tilde{P}_{k},P_{k}$, both satisfy Equation (7). Hence,
$\|\tilde{P}_{k}-P_{k}\|_{1}$ is upper bounded by the diameter of the set
$\mathscr{P}_{t_{k}^{\prime}}$. Further,
$N_{k}(s,a)\leq\sum_{s,a}N_{k}(s,a)=|t_{k}|$. This gives us:

$\displaystyle\leq\sum_{s,a}\sum_{k=1}^{m}\nu_{k}(s,a)\frac{2D\sqrt{14S\log(2A|t_{k}^{\prime}|)}+2\sqrt{7\log(2SA|t_{k}^{\prime}|)}+1}{\sqrt{N_{k}(s,a)}}$
(103) $\displaystyle\leq
2\left(D\sqrt{14S\log(2MAT)}+\sqrt{7\log(2MSAT)+1}\right)\sum_{s,a}\sum_{k=1}^{m}\frac{\nu_{k}(s,a)}{\sqrt{N_{k}(s,a)}}$
$\displaystyle\leq(\sqrt{2}+1)\left(2D\sqrt{14S\log(2MAT)}+\sqrt{7\log(2MSAT)+1}\right)\sum\nolimits_{s,a}\left(\sqrt{N(s,a)}\right)$
(104)
$\displaystyle\leq(\sqrt{2}+1)\left(2D\sqrt{14S\log(2MAT)}+\sqrt{7\log(2MSAT)+1}\right)\sum\nolimits_{s,a}\left(\sqrt{N(s,a)}\right)$
(105)
$\displaystyle\leq(\sqrt{2}+1)\left(2D\sqrt{14S\log(2MAT)}+\sqrt{7\log(2MSAT)+1}\right)\left(\sqrt{\left(\sum\nolimits_{s,a}1\right)\left(\sum\nolimits_{s,a}N(s,a)\right)}\right)$
(106)
$\displaystyle\leq(\sqrt{2}+1)\left(2D\sqrt{14S\log(2MAT)}+\sqrt{7\log(2MSAT)+1}\right)\left(\sqrt{SAMT}\right)$
(107)

Equation (104) follows from Lemma 5. Further, we note that if $N(s,a)=0$, then
$N_{k}(s,a)=0$ for all $k$, and $\nu_{k}=0$ for all $k,i$. Hence,
$N_{k}(s,a)\geq 1$ for all $k$ in Equation (104) and this gives Equation
(105). Equation (106) follows from the Cauchy Schwarz inequality. This
completes part 3.

  2. (b)

Case where the true MDP $\mathcal{\notin}\mathscr{M}(t_{k}^{\prime})$ for some
$k$: For this case, we use a trivial bound of $1$ at each server time step
$t^{\prime}$. This is because the reward $r_{(i,t)}$ lie in $[0,1]$ for all
$i\in[M]$ and for all $t=1,2,\cdots,T$. Using this, we show that the regret
remains bounded by $\sqrt{MT}$ with high probability . We bound the regret
incurred for this case in part 4.

4\. Regret when the estimated MDP is far from the true MDP $\mathcal{M}$: We
bound the probability of $\mathcal{M}\notin\mathscr{M}(t_{k}^{\prime})$ for
some $k$, as follows:

$\displaystyle\sum_{k=1}^{m}\nu_{k}(s,a)\bm{1}_{\\{\mathcal{M}\notin\mathscr{M}(t_{k}^{\prime})\\}}$
$\displaystyle=\sum_{k=1}^{m}\nu_{k}(s,a)\bm{1}_{\\{\mathcal{M}\notin\mathscr{M}(t_{k}^{\prime})\\}}$
(108)
$\displaystyle\leq\sum_{k=1}^{m}N_{k}(s,a)\bm{1}_{\\{\mathcal{M}\notin\mathscr{M}(t_{k}^{\prime})\\}}$
(109)
$\displaystyle\leq\sum_{k=1}^{m}|t_{k}^{\prime}|\bm{1}_{\\{\mathcal{M}\notin\mathscr{M}(t_{k}^{\prime})\\}}$
(110)
$\displaystyle\leq\sum_{|t^{\prime}|=1}^{MT}|t^{\prime}|\bm{1}_{\\{\mathcal{M}\notin\mathscr{M}(t^{\prime})\\}}$
(111)
$\displaystyle\leq\sum\nolimits_{t=1}^{(MT)^{1/4}}|t^{\prime}|+\sum\nolimits_{t=(MT)^{1/4}+1}^{MT}|t^{\prime}|\bm{1}_{\\{\mathcal{M}\notin\mathscr{M}(t^{\prime})\\}}$
$\displaystyle\leq\sqrt{MT}+\sum\nolimits_{|t^{\prime}|=(MT)^{1/4}+1}^{MT}|t^{\prime}|\bm{1}_{\\{\mathcal{M}\notin\mathscr{M}(t^{\prime})\\}}$
(112)

where (109) follows from Lemma 4. Now, we bound the probability of the event
$\\{\mathcal{M}\notin\mathscr{M}(t^{\prime})\\}$ with
$1/(15(|t^{\prime}|)^{6})$ for all $t^{\prime}$ using Lemma 8 (which uses
Lemma 1, refer Appendix B for a detailed proof). Taking union bounds over
$\\{\mathcal{M}\notin\mathscr{M}(t_{k}^{\prime})\\},|t^{\prime}|\geq(MT)^{1/4}+1$,
we get

$\displaystyle\sum_{|t^{\prime}|=(MT)^{1/4}+1}^{T}\mathbb{P}(\bm{1}_{\\{\mathcal{M}\notin\mathscr{M}(t^{\prime})\\}})$
$\displaystyle\leq\sum_{|t^{\prime}|=(MT)^{1/4}+1}^{\infty}\mathbb{P}(\bm{1}_{\\{\mathcal{M}\notin\mathscr{M}(t^{\prime})\\}})$
$\displaystyle\leq\int_{|t^{\prime}|=(MT)^{1/4}}^{\infty}\mathbb{P}(\bm{1}_{\\{\mathcal{M}\notin\mathscr{M}(t^{\prime})\\}})$
$\displaystyle\leq\int_{|t^{\prime}|=(MT)^{1/4}}^{\infty}\frac{1}{(|t^{\prime}|)^{6}}\leq\frac{1}{12(MT)^{5/4}}$

This complete part 4 of the regret sources and all the cases pertaining to the
true MDP $\mathcal{M}$.

Summing over all the possible sources of regret, we obtain the required bound
on the regret. Further, using union bound on all the event when the
concentration bounds fails to hold, we establish that the regret bound in
Equation (8) holds with high probability. ∎