# Federated Reinforcement Learning with Constraint Heterogeneity

Hao Jin
<EMAIL_ADDRESS>
Peking University
&Liangyu Zhang
<EMAIL_ADDRESS>
Peking University
&Zhihua Zhang
<EMAIL_ADDRESS>
Peking University

###### Abstract

We study a Federated Reinforcement Learning (FedRL) problem with constraint
heterogeneity. In our setting, we aim to solve a reinforcement learning
problem with multiple constraints while $N$ training agents are located in $N$
different environments with limited access to the constraint signals and they
are expected to collaboratively learn a policy satisfying all constraint
signals. Such learning problems are prevalent in scenarios of Large Language
Model (LLM) fine-tuning and healthcare applications. To solve the problem, we
propose federated primal-dual policy optimization methods based on traditional
policy gradient methods. Specifically, we introduce $N$ local Lagrange
functions for agents to perform local policy updates, and these agents are
then scheduled to periodically communicate on their local policies. Taking
natural policy gradient (NPG) and proximal policy optimization (PPO) as policy
optimization methods, we mainly focus on two instances of our algorithms,
i.e., FedNPG and FedPPO. We show that FedNPG achieves global convergence with
an $\tilde{O}(1/\sqrt{T})$ rate, and FedPPO efficiently solves complicated
learning tasks with the use of deep neural networks.

##  1 Introduction

Recent years have witnessed the growing popularity of reinforcement learning
(RL) (Sutton et al., 1998) in solving challenging problems, such as playing
the games of Go (Hessel et al., 2018; Silver et al., 2016, 2017) and driving
automobiles (Kiran et al., 2021; Fayjie et al., 2018; Chen et al., 2019). In
classical settings of RL, the agent continually interacts with a fixed
environment, and utilizes such collected experience to learn a policy
maximizing specified reward signals. However, real-life applications have
raised many new practical settings for policy learning (Qin et al., 2021; Jin
et al., 2022; Junges et al., 2016; Chow et al., 2017; Liu et al., 2019). As
one of these emerging settings, federated reinforcement learning (FedRL)
focuses on how to coordinate agents located separately to learn a well-
performing policy without privacy violations on individually collected
experience (Liu et al., 2019; Zhuo et al., 2019; Wang et al., 2020; Nadiger et
al., 2019; Jin et al., 2022). In the setting of FedRL, major challenges of
policy learning come from the misalignment of involved agents, which is
typically known as heterogeneity (Jin et al., 2022; Nadiger et al., 2019).

In this paper, we mainly consider the constraint heterogeneity, which is
prevalent due to the trend of distributed data collection and the necessity of
privacy preservation. Suppose there is a reinforcement learning problem with
multiple constraints, and the monitoring on a constraint signal is sometimes
costly. During the training process, it is impossible for any single agent to
collect the whole set of constraint signals. With the introduction of a
federated platform, any single participated agent only has to focus on a
certain constraint signal while it is finally guaranteed with a well-behaved
model satisfying all constraints. Constraint heterogeneity naturally arises in
the training process, where different agents have access to different
constraint signals. Take the fine-tuning of Large Language Models as an
example (LLM). There is a common science that LLM trained on raw Internet-
based data suffers from problems known as "social bias" Gallegos et al.
(2023), and introducing constraints on fairness of generated text is believed
to address the problem. Accompanied with the increasing trend of federated
optimization in training LLMs Ro et al. (2022); Chen et al. (2023), it is hard
to guarantee an alignment of constraint signals received in different devices
corresponding to different groups of users. To learn the LLM satisfying
constraints of all participated devices, it is natural to consider constraint
heterogeneity in federated reinforcement learning. In fact, constraint
heterogeneity is also prevalent in applications where training data is
distributed among different agents and the labelling on constraint signals is
costly, such as derivation of dynamic treatment regime (DTR) for patients in
different physical conditions (Liu et al., 2016; Zhang et al., 2019).

We formulate FedRL with constraint heterogeneity as a seven-tuple of
$\langle{\mathcal{S}},{\mathcal{A}},r,\\{(c_{i},d_{i})\\}_{i=1}^{N},\gamma,{\mathcal{P}},\\{\Gamma_{i}\\}_{i=1}^{N}\rangle$.
In our setting, $N$ agents share the same state space ${\mathcal{S}}$, action
space ${\mathcal{A}}$, reward function $r$, discounted factor $\gamma$, and
transition dynamic ${\mathcal{P}}$; the $i$-th constraint is modeled with its
associated cost functions $c_{i}$ and corresponding threshold
$d_{i}$;$\\{\Gamma_{i}\\}_{i=1}^{N}$ is the source of constraint
heterogeneity, and $\Gamma_{i}$ indexes the constraints accessible for the
$i$-th agent. Without loss of generality, we assume in our discussion that the
$i$-th agent can only access the $i$-th constraint $(c_{i},d_{i})$ in addition
to the reward function $r$, i.e., $~{}\Gamma_{i}=\\{i\\}$. In this way, none
of the $N$ agents has full access to all of $N$ constraints, which prevents
any agent from locally adopting existing methods of constrained reinforcement
learning (Chow et al., 2017; Liang et al., 2018; Tessler et al., 2018; Bohez
et al., 2019; Xu et al., 2021; Liu et al., 2022) to solve the problem.

We propose a class of federated primal-dual policy optimization methods to
solve FedRL problems with constraint heterogeneity. Suppose that we
parameterize a policy $\pi$ with $\theta\in\Theta$, and denote its cumulative
performance w.r.t. reward functions $r$ and cost functions
$\\{c_{i}\\}_{i=1}^{N}$ as functions of $\theta$, i.e., $~{}J_{r}(\theta)$ and
$\\{J_{c_{i}}(\theta)\\}_{i=1}^{N}$. The policy learning is then transformed
into the following constrained optimization problem w.r.t. $\theta$:

$\displaystyle\max_{\theta}~{}~{}$ $\displaystyle J_{r}(\theta),$
$\displaystyle\texttt{s.t.}~{}~{}J_{c_{i}}(\theta)$ $\displaystyle\leq
d_{i},~{}i\in[N]:=\\{1,2,\dots,N\\}.$

When there is no constraint heterogeneity, primal-dual methods considers the
following Lagrange function:

$L_{0}(\lambda,\theta)=J_{r}(\theta)+\sum_{i=1}^{N}\lambda_{k}(d_{i}-J_{c_{i}}(\theta)),$

where $\lambda=(\lambda_{1},\dots,\lambda_{N})^{T}\in\mathbb{R}_{+}^{N}$
serves as the vector of Lagrange multipliers associated with the $N$
constraint functions. In this way, these methods turn to solve the min-max
optimization based on $L_{0}(\lambda,\theta)$ through gradient-descent-ascent,
which solves original problem when strong duality holds (Oh et al., 2017;
Paternain et al., 2019; Ding et al., 2020). However, the existence of
constraint heterogeneity prohibits us from using $L_{0}(\lambda,\theta)$ to
update local policies. To address the issue, we decompose
$L_{0}(\lambda,\theta)$ into $N$ local Lagrange functions
$\\{L_{i}(\lambda_{i},\theta)\\}_{i=1}^{N}$. Specifically, the $i$-th local
Lagrange function does not require additional knowledge other than $r$ and
$(c_{i},d_{i})$ and the $i$-th agent is able to conduct primal-dual updates
accordingly. Furthermore, our methods require $N$ agents to periodically
communicate their local policies in order to find a policy satisfying all the
constraints. Finally, we instantiate different different federated algorithms
with different policy optimization methods. Specifically, in FedRL problems
with tabular environments, we devise the FedNPG algorithm based on natural
policy gradient. We show that FedNPG achieves an $\widetilde{O}(1/\sqrt{T})$
global convergence rate, and also conduct empirical analysis. To solve
complicated FedRL tasks on real data, we resort to the deep neural networks,
devise the FedPPO algorithm by utilizing proximal policy optimization, and
empirically validate its performance in CartPole, Acrobot and Inverted-
Pendulum.

In summary, our paper mainly offers the following contributions:

  * •

We are the first to consider federated reinforcement learning (FedRL) with
constraint heterogeneity, in which different agents have access to different
constraints and the learning goal is to find an optimal policy satisfying all
constraints.

  * •

We propose a class of federated primal-dual policy optimization methods to
solve FedRL problems with constraint heterogeneity, which involves the
introduction of local Lagrange functions and periodic aggregation of locally
updated policies.

  * •

We analyze theoretical performance of our method when adopting NPG as the
policy optimizer, and prove that FedNPG achieves global convergence at an
$\tilde{O}(1/\sqrt{T})$ rate. Moreover, we evaluate empirical performance of
FedPPO in complicated tasks of FedRL with the use of deep neural networks.

##  2 Constrained Reinforcement Learning

Before formulating our concerned FedRL with constraint heterogeneity, we first
discuss the constrained reinforcement learning (constrained RL) problem
including constrained Markov decision processes and primal-dual policy
optimization methods.

###  2.1 Constrained Markov decision processes

Constrained reinforcement learning problems are usually modeled with
constrained Markov decision processes (CMDPs), which is formulated as the
tuple
$\langle{\mathcal{S}},{\mathcal{A}},r,\\{(c_{i},d_{i})\\}_{i=1}^{N},\gamma,{\mathcal{P}}\rangle$.
Given any policy $\pi$, the cumulative reward and cumulative cost functions
are defined as follows:

$\displaystyle J_{r}(\pi)$
$\displaystyle={\mathbb{E}}_{s_{0}\sim\rho}\left[\sum_{t=0}^{\infty}\gamma^{t}r(s_{t},a_{t})\mathrel{\bigg{|}}a_{t}\sim\pi(\cdot|s_{t})\right],$
$\displaystyle J_{c_{i}}(\pi)$
$\displaystyle={\mathbb{E}}_{s_{0}\sim\rho}\left[\sum_{t=0}^{\infty}\gamma^{t}c_{i}(s_{t},a_{t})\mathrel{\bigg{|}},a_{t}\sim\pi(\cdot|s_{t})\right],$

where $\rho$ indicates the distribution of initial states, and the
expectations are taken over the randomness of both the policy $\pi$ and the
environment ${\mathcal{P}}$. In this way, the learning goal can be formulated
as the following optimization problem:

$\max_{\pi}J_{r}(\pi),~{}~{}\texttt{s.t.}J_{c_{i}}(\pi)\leq d_{i},~{}i\in[N].$
(1)

We will always assume the problem above is feasible and denote the optimal
policy as $\pi^{*}$.

###  2.2 Primal-dual policy optimization methods

Policy optimization methods are prevalent in solving reinforcement learning
problems with large state spaces. Suppose the policy $\pi$ is parameterized by
$\theta\in\Theta\subset{\mathbb{R}}^{d}$ (denoted $~{}\pi_{\theta}$). These
methods transform Problem 1 as the following constrained optimization problem
w.r.t. $\theta$:

$\max_{\theta\in\Theta}J_{r}(\theta),~{}~{}\texttt{s.t.}J_{c_{i}}(\theta)\leq
d_{i},~{}i\in[N],$ (2)

where $J_{r}(\theta)$ and $J_{c_{i}}(\theta)$ represent $J_{r}(\pi_{\theta})$
and $J_{c_{i}}(\pi_{\theta})$. To solve Problem 2, primal-dual methods augment
the objective as follows:

$L_{0}(\lambda,\theta)=J_{r}(\theta)+\sum_{i=1}^{N}\lambda_{i}(d_{i}-J_{c_{i}}(\theta)),$
(3)

where $\lambda_{i}\geq 0$ serves as the Lagrange multiplier of the $i$-th
constraint and $\lambda=(\lambda_{1},\dots,\lambda_{N})^{T}$ represents the
vector of these $N$ multipliers. When strong duality holds in constrained RL
problems Oh et al. (2017), Problem 2 is equivalent to the following min-max
policy optimization problem:

$\min_{\lambda\succcurlyeq 0}\max_{\theta\in\Theta}L_{0}(\lambda,\theta).$ (4)

Now these primal-dual methods solve Problem 4 with classical projected
gradient descent-ascent algorithms. Specifically, denoting the policy
parameters and Lagrange multipliers at the $t$-th step by $\theta^{(t)}$ and
$\lambda^{(t)}$, we compute $(\theta^{(t+1)},\lambda^{(t+1)})$ by

$\displaystyle\theta^{(t+1)}$
$\displaystyle=\texttt{Proj}_{\Theta}(\theta^{(t)}+\eta_{\theta}w^{(t)}),~{}$
$\displaystyle\lambda^{(t+1)}$
$\displaystyle=\texttt{Proj}_{\Lambda}(\lambda^{(t)}-\eta_{\lambda}l^{(t)}).$

Here $\Theta$ is the space of policy parameters, $\Lambda$ is the set
containing valid Lagrange multipliers, $\eta_{\theta},~{}\eta_{\lambda}$
respectively represent the learning rates of policy parameters and Lagrange
multipliers, and $(l^{(t)},w^{(t)})$ denote the gradient directions w.r.t
$(\lambda,\theta)$ obtained from certain policy optimization methods. Tessler
et al. (2018) directly took
$(\nabla_{\lambda}L_{0}(\lambda^{(t)},\theta^{(t)}),\nabla_{\theta}L_{0}(\lambda^{(t)},\theta^{(t)}))$
as $(l^{(t)},w^{(t)})$, while Ding et al. (2020) set $w^{(t)}$ as the natural
policy gradient of $\theta$ and set $l_{(t)}$ as the clipped gradient of
$\lambda$. Tessler et al. (2018) stated that such gradient descent-ascent
algorithms converge to

$(\lambda^{*},\theta^{*})=\arg\min_{\lambda\succcurlyeq
0}\max_{\theta\in\Theta}L_{0}(\lambda,\theta),$

where $\theta^{*}$ solves Problem 2 and $\pi_{\theta^{*}}$ represents the
optimal policy when strong duality holds.

##  3 Federated Reinforcement Learning with constraint heterogeneity

We formulate FedRL with constraint heterogeneity as the tuple
$\langle{\mathcal{S}},{\mathcal{A}},r,\\{(c_{i},d_{i})\\}_{i=1}^{N},\gamma,{\mathcal{P}},\\{\Gamma_{i}\\}_{i=1}^{N}\rangle$.
The learning goal of the problem is the same with that of CMDPs shown in
Problem 1, i.e., finding the policy maximizing the cumulative reward function
while satisfying all $N$ constraints. Despite such similarity, FedRL with
constraint heterogeneity has a totally different interpretation of
$\\{(c_{i},d_{i})\\}_{i=1}^{N}$ due to the heterogeneity introduced by
$\\{\Gamma_{i}\\}_{i=1}^{N}$: $N$ agents are separately located in $N$
environments, and the $i$-th agent only has access to constraint functions
$\\{(c_{j},d_{j})\\}_{j\in\Gamma_{i}}$ in addition to the reward function $r$.
The introduction of $\\{\Gamma_{i}\\}_{i=1}^{N}$ discriminates these $N$
agents from the omniscient agent with full access to
$\\{(c_{i},d_{i})\\}_{i=1}^{N}$ in CMDPs. Without loss of generality, we view
constraint functions accessible to the $i$-th constraint function as a whole
one and set $\Gamma_{i}$ to be $\\{i\\}$ in the following discussion.

###  3.1 Local Lagrange functions from $L_{0}(\lambda,\theta)$

Given the similar learning goal with CMDPs, it is natural for us to expect
that primal-dual methods would work in solving FedRL problems with multiple
constraints. However, constraint heterogeneity makes it impossible for the
$i$-th agent to evaluate $L_{0}(\lambda,\theta)$ from its own experience,
because the $i$-th agent cannot collect any information about constraint
functions of other agents. To address the issue, we decompose
$L_{0}(\lambda,\theta)$ into $N$ local Lagrange functions
$\\{L_{i}(\lambda_{i},\theta)\\}_{i=1}^{N}$ as follows:

$\displaystyle L_{0}(\lambda,\theta)$
$\displaystyle=\sum_{i=1}^{N}L_{i}(\lambda_{i},\theta),$ $\displaystyle
L_{i}(\lambda,\theta)$
$\displaystyle=\frac{1}{N}J_{r}(\theta)+\lambda_{i}(d_{i}-J_{c_{i}}(\theta)),~{}\forall
i\in[N]$

where $L_{i}(\lambda,\theta)$ is composed of reward function $r$ and the
$i$-th constraint function $(c_{i},d_{i})$, which are both observable for the
$i$-th agent. Moreover, $L_{i}(\lambda_{i},\theta)$ shares a similar
formulation with $L_{0}(\lambda,\theta)$, where the constraint function is
multiplied by a non-negative multiplier $\lambda_{i}$ and then added to a
function related to $r$. We denote Lagrange multipliers $\lambda$ and policy
parameters $\theta$ of the $i$-th agent at the $t$-th iteration by
$\lambda_{i}^{(t)}$ and $\theta_{i}^{(t)}$. Based on the $i$-th local Lagrange
function $L_{i}(\lambda_{i},\theta)$ of $L_{0}(\lambda,\theta)$, the $i$-th
agent is able to apply gradient descent-ascent in updating
$(\lambda_{i}^{(t)},\theta_{i}^{(t)})$ to
$(\lambda_{i}^{(t+1)},\theta_{i}^{(t+1)})$. In this way, agents manage to use
primal-dual methods in updating their local policies and Lagrange multipliers
based on local Lagrange functions rather than the original Lagrange function.

Algorithm 1 Federated primal-dual policy optimization

Initialize: Initial parameters $\theta^{(0)}$ and multipliers $\lambda^{(0)}$;
Learning rate $\eta_{\theta}$ and $\eta_{\lambda}$; Projection set $\Lambda$
and $\Theta$.

Set $t=0,~{}\lambda_{i}^{t}=\lambda^{(0)},~{}\forall i\in\\{1,\dots,N\\}$.

while $t<T$ do

Set $\theta_{i}^{(t)}=\theta^{(t)}$, $~{}i\in\\{1,2,\dots,N\\}$.

for $e=1$ to $E$ do

for $i=1$ to $N$ do

Collect experience $\mathcal{T}_{i}^{(t)}$ based on $\pi_{\theta_{i}^{(t)}}$.

Policy evaluation based on local experience ${\mathcal{T}}_{i}^{(t)}$:
$\hat{J}_{c_{i}}(\theta_{i}^{(t)})\approx
J_{c_{i}}(\theta_{i}^{(t)}),~{}\hat{J}_{r}(\theta_{i}^{(t)})\approx
J_{r}(\theta_{i}^{(t)})$.

Take one-step policy optimization towards maximizing
${L}_{i}(\lambda_{i}^{(t)},\theta_{i}^{(t)})$ as
$\texttt{Proj}_{\Theta}(\theta_{i}^{(t)}+\eta_{\theta}\hat{w}_{i}^{(t)})\rightarrow\theta_{i}^{(t+1)}$,
where $\hat{w}_{i}^{(t)}$ is obtained based on ${\mathcal{T}}_{i}$.

Update multipliers as
$\texttt{Proj}_{\Lambda}(\lambda_{i}^{(t)}-\eta_{\lambda}\hat{l}_{i}^{(t)})\rightarrow\lambda_{i}^{(t+1)}$,
where $\hat{l}_{i}^{(t)}=\hat{J}_{c_{i}}(\theta_{i}^{(t)})-d_{i}$

end for

$t=t+1$

end for

$N$ agents communicate $\\{\theta_{i}^{(t)}\\}_{i=1}^{N}$ and
$\\{\lambda_{i}^{(t)}\\}_{i=1}^{N}$.

Set
$\theta^{(t)}=\texttt{Aggregate}_{\theta}(\\{\lambda_{i}^{(t)}\\}_{i=1}^{N},\\{\theta_{i}^{(t)}\\}_{i=1}^{N})$.

Set $\lambda_{i}^{(t+1)}=\lambda_{i}^{(t)},~{}i\in\\{1,2,\dots,N\\}$.

end while

###  3.2 Periodic communication of local policies

Periodic communication is necessary for policy learning in the federated
setting. However, any exchange of constraint-related experience violates
agents’ privacy in our case. Instead, our proposed algorithms organise the
periodic communication among these $N$ agents at a policy level. Assume $E$ to
be the number of time steps between adjacent communication rounds. After the
$N$ agents update their local policies for $E$ steps, they communicate their
policy parameters and one takes a global aggregation as follows:

$\displaystyle\theta^{(t)}=\texttt{Aggregate}_{\theta}$
$\displaystyle(\\{\lambda_{i}^{(t)}\\}_{i=1}^{N},\\{\theta_{i}^{(t)}\\}_{i=1}^{N}),$

where $\texttt{Aggregate}_{\theta}$ stands for any feasible aggregation
method, such as averaging in parameter space with uniform weights, i.e.,
$~{}\theta^{(t)}=\frac{1}{N}\sum_{i=1}^{N}\theta_{i}^{(t)}$. Due to our
assumption on constraint heterogeneity, the algorithm does not update Lagrange
multipliers in rounds of communication.

We are ready to give a full implementation of these federated primal-dual
policy optimization methods in Alg. 1. Different policy optimization methods
lead to different instances of our algorithms. For detailed theoretical
analysis and empirical evaluation, we focus on the following two algorithms:
for tabular environments FedNPG applies natural policy gradient (NPG) for
policy updates of local agents; for non-tabular environments FedPPO conducts
proximal policy optimization (PPO) on policies parameterized by deep networks.
Details of implementation are left in Appendix A.

##  4 Theoretical Analysis

In this section, we present a theoretical analysis of FedNPG on its
convergence performance. In summary, we show FedNPG achieves an
$\widetilde{O}(1/\sqrt{T})$ convergence rate. Here $\widetilde{O}$ means we
discard any terms of $\operatorname{poly}(\log(\cdot))$ orders.

###  4.1 The FedNPG algorithm

We first give a brief description of how FedNPG works. Ideally, we would like
to use natural policy gradients to update the local policies, i.e.,

$\hat{w}_{i}^{(t)}=\frac{1}{N}F(\theta_{i}^{(t)})^{\dagger}\nabla_{\theta}J_{r}(\theta_{i}^{(t)})-\lambda_{i}^{(t)}F(\theta_{i}^{(t)})^{\dagger}\nabla_{\theta}J_{c_{i}}(\theta_{i}^{(t)}),$

where $(\cdot)^{\dagger}$ denotes the matrix pseudoinverse,

$\displaystyle F(\theta):=$ $\displaystyle{\mathbb{E}}_{s\sim
d^{\pi_{\theta}},a|s\sim\pi_{\theta}}[\nabla_{\theta}\pi_{\theta}(a|s)\nabla_{\theta}\pi_{\theta}(a|s)^{\top}],$
$\displaystyle d^{\pi_{\theta}}(s):=$
$\displaystyle(1-\gamma)\sum_{t=0}^{\infty}\gamma^{t}{\mathbb{P}}_{s_{0}\sim\rho,\pi}(s_{t}=s).$

However, in practical applications it is computationally expensive to evaluate
$F(\theta)$, and
$\nabla_{\theta}J_{r}(\theta),\nabla_{\theta}J_{c_{i}}(\theta)$ are usually
unknown. Therefore, we instead use sample-based NPG Agarwal et al. (2021) to
update the local policies. That is,

$\displaystyle\hat{w}_{i}^{(t)}$
$\displaystyle=\frac{1}{N}\hat{w}_{r}^{(t)}(i)-\lambda_{i}^{(t)}\hat{w}_{c_{i}}^{(t)}.$

And $\hat{w}_{r}^{(t)}(i)$, $\hat{w}_{c_{i}}^{(t)}$ are obtained by solving
the following optimization problems with SGD, respectively:

$\displaystyle\hat{w}_{r}^{(t)}(i)$
$\displaystyle\approx\arg\min_{w}E^{\nu^{(t)}_{i}}(r,\theta_{i}^{(t)},w),$
$\displaystyle\hat{w}_{c_{i}}^{(t)}$
$\displaystyle\approx\arg\min_{w}E^{\nu^{(t)}_{i}}(c_{i},\theta_{i}^{(t)},w).$

Here the $E^{\nu}(\diamond,\theta,w)$ are called the transferred compatible
function approximation errors, which are defined as:

$E^{\nu}(\diamond,\theta,w):={\mathbb{E}}_{(s,a)\sim\nu}(A^{\pi_{\theta}}_{\diamond}(s,a)-w^{\top}\nabla_{\theta}\log\pi_{\theta}(a|s))^{2},$

where
$\nu^{(t)}_{i}(s,a):=\pi_{\theta_{i}^{(t)}}(a|s)d^{\pi_{\theta_{i}^{(t)}}}(s)$
is the state-action occupancy measure induced by $\pi_{\theta_{i}^{(t)}}$. In
terms of the policy aggregation, we consider the averaging in parameter space
with uniform weights in the following discussion.

###  4.2 Technical assumptions

Before presenting our main result, we firstly state our technical assumptions.
Note that the following assumptions are standard in the literature of policy
optimization Agarwal et al. (2021); Ding et al. (2020).

######  Assumption 4.1 (Differentiable policy class).

We consider a parametrized policy class
$\Pi_{\theta}=\\{\pi_{\theta}|\theta\in\Theta\\}$, such that for all
$s\in{\mathcal{S}}$, $a\in{\mathcal{A}}$, $\log\pi_{\theta}(s|a)$ is a
differentiable function of $\theta$.

######  Assumption 4.2 (Lipschitz policy class).

For all $s\in{\mathcal{S}}$, $a\in{\mathcal{A}}$, $\log\pi_{\theta}(s|a)$ is a
$L_{\pi}$-Lipschitz function of $\theta$, i.e.,

$\|\nabla_{\theta}\log\pi_{\theta}(s|a)\|_{2}\leq L_{\pi},\forall
s\in{\mathcal{S}},a\in{\mathcal{A}},\theta\in{\mathbb{R}}^{d}.$

######  Assumption 4.3 (Smooth policy class).

For all $s\in{\mathcal{S}}$, $a\in{\mathcal{A}}$, $\log\pi_{\theta}(s|a)$ is a
$\beta$-smooth function of $\theta$, i.e., $\forall
s\in{\mathcal{S}},a\in{\mathcal{A}},~{}\theta,\theta^{\prime}\in{\mathbb{R}}^{d}$,

$\|\nabla_{\theta}\log\pi_{\theta}(s|a)-\nabla_{\theta}\log\pi_{\theta^{\prime}}(s|a)\|_{2}\leq\beta\|\theta-\theta^{\prime}\|_{2}.$

######  Assumption 4.4 (Positive definite Fisher information).

$F(\theta)\preccurlyeq G^{2}I_{d}\;\text{ for any
}\;\theta\in{\mathbb{R}}^{\mathrm{d}}\text{. }$

######  Assumption 4.5 (Bounded estimation error).

For any $t\in\\{1,...,T\\}$, for each $i\in\\{1,...,N\\}$,

$\displaystyle\left\|\underset{w}{\mathrm{argmin}}E^{\nu_{i}^{(t)}}(r,\theta_{i}^{(t)},w)\right\|_{2}^{2}\leq
W^{2},~{}~{}$
$\displaystyle\left\|\underset{w}{\mathrm{argmin}}E^{\nu_{i}^{(t)}}(c_{i},\theta_{i}^{(t)},w)\right\|_{2}^{2}\leq
W^{2}.$

Also,

${\mathbb{E}}\|\hat{w}_{r}^{(t)}(i)\|_{2}^{2}\leq
W^{2},~{}~{}{\mathbb{E}}\|\hat{w}_{c_{i}}^{(t)}\|_{2}^{2}\leq W^{2}.$

In addition, we assume the parametrization $\pi_{\theta}$ realizes good
function approximation in terms of transferred compatible function
approximation errors, which can be close to zero as long as the policy class
is rich Wang et al. (2019) or the underlying MDP has low-rank structure Jiang
et al. (2017).

######  Assumption 4.6 (Bounded function approximation error).

The transferred compatible function approximation errors satisfies that
$\forall t\in\\{1,...,T\\},~{}\forall i\in\\{1,...,N\\}$,

$\displaystyle\min_{w}E^{\nu_{i}^{(t)}}(r,\theta_{i}^{(t)},w)\leq\epsilon_{\text{bias}},$
$\displaystyle\min_{w}E^{\nu_{i}^{(t)}}(c_{i},\theta_{i}^{(t)},w)\leq\epsilon_{\text{bias}}.$

We also make the following two assumptions to ensure strong duality and
boundedness of dual variables.

######  Assumption 4.7.

Assume
${\mathcal{P}}({\mathcal{S}})^{{\mathcal{A}}}\subset\bar{\Pi}_{\theta}$. Here
we use $\bar{\Pi}_{\theta}$ to denote the closure of set ${\Pi}_{\theta}$.

######  Assumption 4.8 (Slater’s condition).

There exist $\xi>0$ and $\tilde{\pi}\in\Pi$ such that
$J_{c_{i}}(\tilde{\pi})+\xi\leq d_{i}$, $\forall i\in\\{1,...,N\\}$.

######  Lemma 4.1 (Strong duality and boundedness of dual variables).

If Assumption 4.7 and Assumption 4.8 are true, we have:

  1. (a)

$J_{r}(\pi^{*})=\sup_{\theta}\inf_{\lambda}L_{0}(\theta,\lambda)$;

  2. (b)

$\sum_{i=1}^{N}\lambda^{*}_{i}\leq\frac{J_{r}(\pi^{*})-J_{r}(\tilde{\pi})}{\xi}\leq\frac{1}{(1-\gamma)\xi}$.

The proof is in Appendix E. Assumption 4.7 may seem stringent. However, it is
necessary for the strong duality to hold (Paternain et al., 2019), which is of
vital importance for the theoretical analysis of primal-dual type methods. One
may notice that Ding et al. (2020) gave the convergence rate of the NPG-
PrimalDual algorithm in the case that the strong duality does not hold (see
Theorem 3 in Ding et al. (2020)). However, their theoretical analysis relies
on the assumption that $\\{\lambda^{(t)};t=1,...,T\\}$ is a bounded sequence
(see Assumption 4 in Ding et al. (2020)), which is unlikely to be true as long
as the strong duality does not hold. Also, Assumption 4.7 does not implies
$\epsilon_{bias}\equiv 0$, please see Appendix LABEL:Appendix_example for an
example.

###  4.3 Main results and discussions

Now we present our main result. The proof is in Appendix E.

######  Theorem 4.1.

Suppose Assumptions 4.1\- 4.8 are true. $\\{\theta^{(t)};t=1,...,T\\}$ and
$\\{\lambda^{(t)};t=1,...,T\\}$ are generated by the Fed-NPG algorithm with
$\eta_{\theta}=O(1/N\sqrt{T}),\eta_{\lambda}=O(1/\sqrt{T})$. Then for the
policy $\hat{\pi}$ returned by the FedNPG algorithm,

$\displaystyle{\mathbb{E}}(J_{r}(\pi^{*})-J_{r}(\hat{\pi}))={\mathbb{E}}\left[\frac{1}{T}\sum_{t=0}^{T-1}(J_{r}(\pi^{*})-J_{r}(\pi_{\theta^{(t)}}))\right]$
$\displaystyle=\widetilde{O}\left(\frac{|{\mathcal{A}}|EN}{\sqrt{T}(1-\gamma)^{3}}\right)+\widetilde{O}\left(\frac{\sqrt{\epsilon_{bias}+d/K}}{(1-\gamma)^{3.5}}\right),$
$\displaystyle{\mathbb{E}}(J_{c_{i}}(\hat{\pi})-d_{i})=\sum_{i=1}^{N}{\mathbb{E}}\left[\frac{1}{T}\sum_{t=0}^{T-1}J_{c_{i}}(\pi_{\theta^{(t)}})-d_{i}\right]_{+}$
$\displaystyle=\widetilde{O}\left(\frac{|{\mathcal{A}}|EN}{\sqrt{T}(1-\gamma)^{3}}\right)+\widetilde{O}\left(\frac{\sqrt{\epsilon_{bias}+d/K}}{(1-\gamma)^{2.5}}\right).$

$K$ is a hyper-parameter controlling the number of data points we collect at
each iteration. And the definition of $K$ can be found in Algorithm 2 in
Appendix A.

Remark 1: Even if we are allowed to perform an infinitely large number of
iterations i.e. $T=\infty$, the error bound in Theorem 4.1 still remains non-
zero. There are two reasons for this phenomenon:

  * •

our parameterization introduces inherent biases, which are measured by the
transferred compatible function approximation errors;

  * •

the natural policy gradient we use is not obtained with an oracle but
estimated from a limited number of data points.

The meaning of the $\widetilde{O}(1/\sqrt{T})$ convergence rate of the FedNPG
algorithm is that the excess risk would converge to $0$ with an
$\widetilde{O}(1/\sqrt{T})$ rate if our parameterized policy class admits no
transferred compatible function approximation errors and an oracle for exact
natural policy gradients is available. Such dependence on $T$ matches error
bounds of single-agent algorithm for constrained reinforcement learning Ding
et al. (2020), as well as results of federated reinforcement learning
algorithms in non-constrained cases Jin et al. (2022).

Remark 2: Unlike many existing works on federated learning, our finite-sample
bounds contain a $O(N)$ factor, meaning that when the number of agent $N$
increases our algorithm would take more time to converge. Traditional
federated settingi considers the average of $N$ _averaged_ heterogeneous
objectives, while our setting focuses on $N$ distinct heterogeneous
constraints in addition to a homogeneous objective without averaging on these
constraint signals. Moreover, it is worthy to note that even in the setting of
constrained RL with an omniscient agent having information of both reward
functions and $N$ cost functions, the finite-sample convergence rate will
still scale up with $N$ Liu et al. (2021); Li et al. (2021); Zeng et al.
(2022).

##  5 Empirical Study

In this section, we evaluate the training performance of FedNPG and FedPPO, in
which the policy gradient optimizers used in local updates are respectively
natural policy gradient (NPG) and proximal policy optimization (PPO) 111See
https://github.com/grandpahao/FedCMDP.git.

###  5.1 The Set-up

Environments. We construct a collection of FedRL tasks with multiple
constraints represented by different cost functions in both tabular and non-
tabular environments. We consider two types of tabular environments: RandomMDP
with randomly generated matrices as different cost functions; WindyCliff (Paul
et al., 2019) with a sequence of hazard spaces to which the entrance induces a
cost. In terms of non-tabular environments, we modify several classical
learning problems in Gym (Brockman et al., 2016) as follows: learning agents
of CartPole and Inverted-Pendulum are penalized when their horizontal
positions fall into certain regions, and certain actions of agents in Acrobot
are prohibited at a certain range of states.

Policy Parameterization. We apply two ways of policy parameterization in
instantiating our methods according to the type of environment. In tabular
environments, we use softmax parameterization. In terms of the policy
aggregation $\texttt{Aggregate}_{\theta}$, we apply an averaging strategy on
the level of policy as follows:

$\displaystyle\bar{\pi}_{t}(a|s)=\frac{1}{N}\sum_{i=1}^{N}\pi_{\theta_{i}^{(t)}}(a|s),$
$\displaystyle{\theta}^{(t)}(a|s)=\log\bar{\pi}_{t}(a|s)+C_{s},$

where $C_{s}$ is taken as $\sum_{a\in{\mathcal{S}}}\log\bar{\pi}_{t}(a|s)$ in
our methods. In non-tabular environments, the policy $\pi_{\theta}$ is
parameterized with deep neural networks. In terms of the policy aggregation,
the averaging policy is conducted on the level of deep models, i.e.,
$~{}{\theta}^{(t)}=\frac{1}{N}\sum_{i=1}^{N}\theta_{i}^{(t)}$.

Baselines. For each environment, our methods are compared with two types of
baselines: firstly, RL agents trained on locally collected experience without
communication, which we refer to as NPGk (PPOk) in the $k$-th environment;
secondly, an omniscient agent trained on trajectories with information of both
reward functions and $N$ cost functions, which we refer to as NPGo (PPOo).
Comparison with the first-type baselines is to show that no local agent is
able to independently solve the learning problem with multiple constraints,
while the second-type baseline gives us a perspective on how well our methods
perform in solving the constrained learning problem.

Comparison Metric. In most of involved FedRL tasks, we directly display
averaged training performances of different algorithms in terms of both reward
function and cost functions, and compare them with constraint thresholds.
However, such comparison is infeasible in randomly generated RandomMDP
environments, because reward functions and cost functions vary among different
instances. Instead, we introduce three auxiliary ratios which unify such
misalignment in different RandomMDP environments, i.e., Reward Ratio (RR),
maximum Violation Ratio (mVR) and maximum Relative Violation Ratio (mRVR),
which are defined as follows:

$\displaystyle\textit{RR}(\pi)$ $\displaystyle=J_{r}(\pi)/J_{r}(\pi_{o}),$
$\displaystyle\textit{mVR}(\pi)$
$\displaystyle=\max_{i\in[N]}J_{c_{i}}(\pi)/d_{i},$
$\displaystyle\textit{mRVR}(\pi)$
$\displaystyle=\max_{i\in[N]}J_{c_{i}}(\pi)/J_{c_{i}}(\pi_{o}),$

where $\pi$ represents any convergent policy to be evaluated and $\pi_{o}$
represents the convergent policy of the corresponding second-type baseline
with full access to the $N$ constraints.

Other Details. In terms of other experiment settings on environment
construction and hyperparameter selection, we leave a detailed description in
Appendix B.

Figure 1: Comparison between baselines and FedPPO in CartPole (first row),
Acrobot (second row) and Inverted-Pendulum (third row): we depict the mean as
line, standard error as shadow, and constraint thresholds as red lines.

###  5.2 Performance of FedNPG

To justify the convergence of FedNPG, we evaluate its performance in FedRL
tasks with tabular environments, i.e., RandomMDP and WindyCliff. The first row
of Figure LABEL:fig:tabular_exp reveals that FedNPG and NPGo achieve similar
performance in terms of both reward performance and cost violation, while NPGk
fails at satisfying all constraints. In WindyCliff, the second row of Figure
LABEL:fig:tabular_exp tells us that FedNPG is comparable with NPGo in terms of
reward performance and satisfies all the constraints with a smaller variance.

###  5.3 Performance of FedPPO

FedPPO utilizes deep neural networks to approximate policy functions and value
functions, and we evaluate its performance on FedRL tasks in CartPole, Acrobot
and Inverted-Pendulum. Different environments justify the efficiency of FedPPO
from different perspectives: CartPole focuses on the discrete control with
state-based constraints; Acrobot additionally considers state-action-based
constraints; Inverted-Pendulum focuses on agents with continuous action space.
In CartPole and Inverted-Pendulum, Figure 1 reveals that all the methods
achieve maximum reward and only convergent performances of PPOo and FedPPO
satisfy constraints specified by red lines. It is worth noting that PPOk
indeed satisfies the $k$-th constraint but fails in the other constraint. Such
phenomenon is more obviously observed in Inverted-Pendulum. In Acrobot, FedPPO
achieves comparable reward performance with PPOo and satisfies all the
constraints, while PPOk obviously violates the unobservable constraint.

##  6 Conclusion

We have imposed constraint heterogeneity into FedRL problems, where agents
have access to different constraints and the learned policy is expected to
satisfy all constraints. Through constructing local Lagrange functions, agents
are able to conduct local updates without knowledge of others’ experience.
Together with periodical communication of policies, we have proposed federated
primal-dual policy optimization methods to solve FedRL problems with
constraint heterogeneity. Moreover, we have furthermore analyzed two instances
of our methods: FedNPG and FedPPO. FedNPG is proved to achieve an
$\tilde{O}(1/\sqrt{T})$ convergence rate, enjoy reasonable sample complexity
compared with existing works on constrained reinforcement learning, and
achieve performance comparable with an omniscient agent having access to all
constraint signals in tabular FedRL tasks. FedPPO is evaluated on complicated
tasks with neural networks as function approximators, and manages to find
optimal policies simultaneously satisfying constraints distributed in
different agents.

## References

  * Sutton et al. [1998] Richard S Sutton, Andrew G Barto, et al.  _Introduction to reinforcement learning_ , volume 135.  MIT press Cambridge, 1998.
  * Hessel et al. [2018] Matteo Hessel, Joseph Modayil, Hado Van Hasselt, Tom Schaul, Georg Ostrovski, Will Dabney, Dan Horgan, Bilal Piot, Mohammad Azar, and David Silver.  Rainbow: Combining improvements in deep reinforcement learning.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 32, 2018.
  * Silver et al. [2016] David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al.  Mastering the game of Go with deep neural networks and tree search.  _Nature_ , 529(7587):484–489, 2016.
  * Silver et al. [2017] David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al.  Mastering the game of Go without human knowledge.  _Nature_ , 550(7676):354–359, 2017.
  * Kiran et al. [2021] 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.  _IEEE Transactions on Intelligent Transportation Systems_ , 2021.
  * Fayjie et al. [2018] Abdur R Fayjie, Sabir Hossain, Doukhi Oualid, and Deok-Jin Lee.  Driverless car: Autonomous driving using deep reinforcement learning in urban environment.  In _2018 15th international conference on ubiquitous robots (ur)_ , pages 896–901. IEEE, 2018.
  * Chen et al. [2019] Jianyu Chen, Bodi Yuan, and Masayoshi Tomizuka.  Model-free deep reinforcement learning for urban autonomous driving.  In _2019 IEEE intelligent transportation systems conference (ITSC)_ , pages 2765–2771. IEEE, 2019.
  * Qin et al. [2021] Zengyi Qin, Yuxiao Chen, and Chuchu Fan.  Density constrained reinforcement learning.  In _International Conference on Machine Learning_ , pages 8682–8692. PMLR, 2021.
  * Jin et al. [2022] Hao Jin, Yang Peng, Wenhao Yang, Shusen Wang, and Zhihua Zhang.  Federated reinforcement learning with environment heterogeneity.  In _International Conference on Artificial Intelligence and Statistics_ , pages 18–37. PMLR, 2022.
  * Junges et al. [2016] Sebastian Junges, Nils Jansen, Christian Dehnert, Ufuk Topcu, and Joost-Pieter Katoen.  Safety-constrained reinforcement learning for mdps.  In _International conference on tools and algorithms for the construction and analysis of systems_ , pages 130–146. Springer, 2016.
  * Chow et al. [2017] Yinlam Chow, Mohammad Ghavamzadeh, Lucas Janson, and Marco Pavone.  Risk-constrained reinforcement learning with percentile risk criteria.  _The Journal of Machine Learning Research_ , 18(1):6070–6120, 2017.
  * Liu et al. [2019] Boyi Liu, Lujia Wang, Ming Liu, and Chengzhong Xu.  Lifelong federated reinforcement learning: A learning architecture for navigation in cloud robotic systems.  _arXiv preprint arXiv:1901.06455_ , 2019.
  * Zhuo et al. [2019] Hankz Hankui Zhuo, Wenfeng Feng, Qian Xu, Qiang Yang, and Yufeng Lin.  Federated reinforcement learning.  _arXiv preprint arXiv:1901.08277_ , 2019.
  * Wang et al. [2020] Xiaofei Wang, Chenyang Wang, Xiuhua Li, Victor CM Leung, and Tarik Taleb.  Federated deep reinforcement learning for internet of things with decentralized cooperative edge caching.  _IEEE Internet of Things Journal_ , 7(10):9441–9455, 2020.
  * Nadiger et al. [2019] Chetan Nadiger, Anil Kumar, and Sherine Abdelhak.  Federated reinforcement learning for fast personalization.  In _2019 IEEE Second International Conference on Artificial Intelligence and Knowledge Engineering (AIKE)_ , pages 123–127. IEEE, 2019.
  * Gallegos et al. [2023] Isabel O Gallegos, Ryan A Rossi, Joe Barrow, Md Mehrab Tanjim, Sungchul Kim, Franck Dernoncourt, Tong Yu, Ruiyi Zhang, and Nesreen K Ahmed.  Bias and fairness in large language models: A survey.  _arXiv preprint arXiv:2309.00770_ , 2023.
  * Ro et al. [2022] Jae Hun Ro, Theresa Breiner, Lara McConnaughey, Mingqing Chen, Ananda Theertha Suresh, Shankar Kumar, and Rajiv Mathews.  Scaling language model size in cross-device federated learning.  _arXiv preprint arXiv:2204.09715_ , 2022.
  * Chen et al. [2023] Chaochao Chen, Xiaohua Feng, Jun Zhou, Jianwei Yin, and Xiaolin Zheng.  Federated large language model: A position paper.  _arXiv preprint arXiv:2307.08925_ , 2023.
  * Liu et al. [2016] Ying Liu, Yuanjia Wang, Michael R Kosorok, Yingqi Zhao, and Donglin Zeng.  Robust hybrid learning for estimating personalized dynamic treatment regimens.  _arXiv preprint arXiv:1611.02314_ , 2016.
  * Zhang et al. [2019] Zhongheng Zhang et al.  Reinforcement learning in clinical medicine: a method to optimize dynamic treatment regime over time.  _Annals of translational medicine_ , 7(14), 2019.
  * Liang et al. [2018] Qingkai Liang, Fanyu Que, and Eytan Modiano.  Accelerated primal-dual policy optimization for safe reinforcement learning.  _arXiv preprint arXiv:1802.06480_ , 2018.
  * Tessler et al. [2018] Chen Tessler, Daniel J Mankowitz, and Shie Mannor.  Reward constrained policy optimization.  _arXiv preprint arXiv:1805.11074_ , 2018.
  * Bohez et al. [2019] Steven Bohez, Abbas Abdolmaleki, Michael Neunert, Jonas Buchli, Nicolas Heess, and Raia Hadsell.  Value constrained model-free continuous control.  _arXiv preprint arXiv:1902.04623_ , 2019.
  * Xu et al. [2021] Tengyu Xu, Yingbin Liang, and Guanghui Lan.  Crpo: A new approach for safe reinforcement learning with convergence guarantee.  In _International Conference on Machine Learning_ , pages 11480–11491. PMLR, 2021.
  * Liu et al. [2022] Zuxin Liu, Zhepeng Cen, Vladislav Isenbaev, Wei Liu, Steven Wu, Bo Li, and Ding Zhao.  Constrained variational policy optimization for safe reinforcement learning.  In _International Conference on Machine Learning_ , pages 13644–13668. PMLR, 2022.
  * Oh et al. [2017] Junhyuk Oh, Satinder Singh, Honglak Lee, and Pushmeet Kohli.  Zero-shot task generalization with multi-task deep reinforcement learning.  In _International Conference on Machine Learning_ , pages 2661–2670. PMLR, 2017.
  * Paternain et al. [2019] Santiago Paternain, Luiz Chamon, Miguel Calvo-Fullana, and Alejandro Ribeiro.  Constrained reinforcement learning has zero duality gap.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Ding et al. [2020] Dongsheng Ding, Kaiqing Zhang, Tamer Basar, and Mihailo Jovanovic.  Natural policy gradient primal-dual method for constrained markov decision processes.  _Advances in Neural Information Processing Systems_ , 33:8378–8390, 2020.
  * Agarwal et al. [2021] Alekh Agarwal, Sham M. Kakade, Jason D. Lee, and Gaurav Mahajan.  On the theory of policy gradient methods: Optimality, approximation, and distribution shift.  _Journal of Machine Learning Research_ , 22(98):1–76, 2021.  URL http://jmlr.org/papers/v22/19-736.html.
  * Wang et al. [2019] Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang.  Neural policy gradient methods: Global optimality and rates of convergence.  _arXiv preprint arXiv:1909.01150_ , 2019.
  * Jiang et al. [2017] Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire.  Contextual decision processes with low bellman rank are pac-learnable.  In _International Conference on Machine Learning_ , pages 1704–1713. PMLR, 2017.
  * Liu et al. [2021] Tao Liu, Ruida Zhou, Dileep Kalathil, PR Kumar, and Chao Tian.  Policy optimization for constrained mdps with provable fast global convergence.  _arXiv preprint arXiv:2111.00552_ , 2021.
  * Li et al. [2021] Tianjiao Li, Ziwei Guan, Shaofeng Zou, Tengyu Xu, Yingbin Liang, and Guanghui Lan.  Faster algorithm and sharper analysis for constrained markov decision process.  _arXiv preprint arXiv:2110.10351_ , 2021.
  * Zeng et al. [2022] Sihan Zeng, Thinh T Doan, and Justin Romberg.  Finite-time complexity of online primal-dual natural actor-critic algorithm for constrained markov decision processes.  In _2022 IEEE 61st Conference on Decision and Control (CDC)_ , pages 4028–4033. IEEE, 2022.
  * Paul et al. [2019] Supratik Paul, Michael A Osborne, and Shimon Whiteson.  Fingerprint policy optimisation for robust reinforcement learning.  In _International Conference on Machine Learning_ , pages 5082–5091. PMLR, 2019.
  * Brockman et al. [2016] Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba.  Openai gym, 2016.
  * Agarwal et al. [2019] Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan.  On the theory of policy gradient methods: Optimality, approximation, and distribution shift.  _arXiv preprint arXiv:1908.00261_ , 2019.
  * Kakade and Langford [2002] Sham Kakade and John Langford.  Approximately optimal approximate reinforcement learning.  In _Proceedings of the Nineteenth International Conference on Machine Learning_ , ICML ’02, page 267–274, San Francisco, CA, USA, 2002. Morgan Kaufmann Publishers Inc.  ISBN 1558608737.
  * Bach and Moulines [2013] Francis Bach and Eric Moulines.  Non-strongly-convex smooth stochastic approximation with convergence rate o (1/n).  _Advances in neural information processing systems_ , 26, 2013.

##  Appendix A Implementations for FedNPG and FedPPO

Here we display detailed implementations for federated primal-dual natural
policy gradient FedNPG and federated primal-dual proximal policy optimization
FedPPO.

###  A.1 Federated primal-dual natural policy gradient (FedNPG)

In FedNPG, we apply sampling procedure in Algorithm 3 of Agarwal et al. [2019]
to estimate value functions and leave choices of
$\texttt{Aggregate}_{\theta}(\cdot)$ unspecified for different ways of
parameterization. In addition, we use $\pi_{i}^{(t)}$ in short of
$\pi_{\theta_{i}^{(t)}}$.

Algorithm 2 Federated primal-dual Natural Policy Gradient (FedNPG)

Initialization: Initial parameters $\theta^{(0)}$ and multipliers
$\lambda^{(0)}$; Learning rates $\eta_{\theta}$, $\eta_{\lambda}$, $\alpha$;
Number of sampled trajectories $K$; Projection sets $\Lambda$ and $\Theta$.

Set $t=0$.

Set $\lambda_{i}^{(t)}=\lambda^{(t)},~{}i\in\\{1,\dots,N\\}$.

while $t<T$ do

Set $\theta_{i}^{(t)}=\theta^{(t)},~{}i\in\\{1,\dots,N\\}$.

for $e=1$ to $E$ do

for $i=1$ to $N$ do

Set $\widehat{V}^{(t)}_{c_{i}}(\rho)=0$.

for $k=0$ to $K-1$ do

Draw $(s,a)\sim\nu^{(t)}_{i}$, with
$\nu^{(t)}_{i}(s,a)=d^{\pi^{(t)}_{i}}(s)\pi^{(t)}_{i}(a|s)$.

Draw $L\sim\text{Geometry}(1-\gamma)$ and execute policy $\pi^{(t)}_{i}$ from
$(s,a)$ for $L$ steps, then construct estimators as
$\widehat{Q}^{(t)}_{r}(s,a)=\sum^{L}_{l=0}r(s_{l},a_{l}),\
\widehat{Q}^{(t)}_{c_{i}}(s,a)=\sum^{L}_{l=0}c_{i}(s_{l},a_{l}),\text{where
}(s_{0},a_{0})=(s,a).$

Draw $L\sim\text{Geometry}(1-\gamma)$ and execute policy $\pi^{(t)}_{i}$ from
$s$ for $L$ steps, then construct estimators as
$\widehat{V}^{(t)}_{r}(s)=\sum^{L}_{l=0}r(s_{k},a_{k}),\
\widehat{V}^{(t)}_{c_{i}}(s)=\sum^{L}_{l=0}c_{i}(s_{l},a_{l}),\text{where
}s_{0}=s.$

Set
$\widehat{A}_{r}^{(t)}(s,a)=\widehat{Q}^{(t)}_{r}(s,a)-\widehat{V}_{r}^{(t)}(s)$
and
$\widehat{A}_{c_{i}}^{(t)}(s,a)=\widehat{Q}^{(t)}_{c_{i}}(s,a)-\widehat{V}_{c_{i}}^{(t)}(s)$.

Update $w_{r}^{(k+1)}(i)=w_{r}^{(k)}(i)-\alpha G_{r}^{(k)}(i)$,
$w_{c_{i}}^{(k+1)}=w_{c_{i}}^{(k)}-\alpha G_{c_{i}}^{(k)}$ with
$\displaystyle G_{r}^{(k)}(i)$
$\displaystyle=2({w_{r}^{(k)}(i)}^{\top}\nabla_{\theta}\log\pi^{(t)}_{i}(a|s)-\widehat{A}_{r}^{(t)}(s,a))\nabla_{\theta}\log\pi^{(t)}_{i}(a|s),$
$\displaystyle G_{c_{i}}^{(k)}$
$\displaystyle=2({w_{c_{i}}^{(k)}}^{\top}\nabla_{\theta}\log\pi_{i}^{(t)}(a|s)-\widehat{A}_{c_{i}}^{(t)}(s,a))\nabla_{\theta}\log\pi^{(t)}_{i}(a|s)$

Draw $s\sim\rho$, $L\sim\text{Geometry}(1-\gamma)$ and execute policy
$\pi_{i}^{(t)}$ from $s$ for $L$ steps, then update
$\widehat{V}_{c_{i}}(\rho)$ as
$\widehat{V}^{(t)}_{c_{i}}(\rho)=\widehat{V}^{(t)}_{c_{i}}(\rho)+\frac{1}{K}\sum_{l=0}^{L-1}c_{i}(s_{l},a_{l}),\
\text{where\ }s_{0}=s.$

end for

Set $\hat{w}_{r}^{(t)}(i)=\frac{1}{K}\sum_{k=1}^{K}w_{r}^{(k)}(i)$,
$\hat{w}_{c_{i}}^{(t)}=\frac{1}{K}\sum_{k=1}^{K}w_{c_{i}}^{(k)}$,
$\hat{w}^{(t)}(i)=\hat{w}_{r}^{(t)}(i)/N-\lambda_{i}^{(t)}\hat{w}_{c_{i}}^{(t)}$.

Update parameters and multipliers as
$\theta^{(t+1)}_{i}=\operatorname{Proj}_{\Theta}(\theta^{(t)}_{i}+\eta_{\theta}\hat{w}^{(t)}(i)),\
\lambda_{i}^{(t+1)}=\operatorname{Proj}_{\Lambda}(\lambda_{i}^{(t)}-\eta_{\lambda}(d_{i}-\widehat{V}_{c_{i}}^{(t)}(\rho))).$

end for

Set $t=t+1$.

end for

$N$ agents communicate $\\{\theta_{i}^{(t)}\\}_{i=1}^{N}$ and
$\\{\lambda_{i}^{(t)}\\}_{i=1}^{N}$.

Set
$\theta^{(t)}=\texttt{Aggregate}_{\theta}(\\{\lambda_{i}^{(t)}\\}_{i=1}^{N},\\{\theta_{i}^{(t)}\\}_{i=1}^{N})$.

end while

RETURN $\hat{\pi}=\pi_{\hat{\theta}}$, where
$\hat{\theta}\sim\operatorname{Unif}(\\{\theta^{(1)},...,\theta^{(T)}\\})$.

###  A.2 Federated primal-dual proximal policy optimization (FedPPO)

FedPPO is implemented for complicated tasks with large state space or
continuous action space. In these cases, an policy $\pi$ is usually
parameterized with a deep neural network $\theta$. In addition to the policy
network, FedPPO also utilizes deep neural networks $\phi,\psi$ to estimate
value functions for both reward signals, i.e.$~{}V_{\phi}$, and cost signals,
i.e.$~{}V_{\psi}$. It is noteworthy that $V_{\psi}$ contains private
information of constraint signals and is prohibited from any communication.
Value networks $V_{\phi}$ of reward functions is communicated along with
policy networks $\pi_{\theta}$ and $\texttt{Aggregate}_{\phi}$ has the same
formulation with $\texttt{Aggregate}_{\theta}$.

Algorithm 3 Federated primal-dual Proximal Policy Optimization

Initialization: Initial policy parameters $\theta^{(0)}$, critic parameters
$(\phi^{(0)}$,$~{}\psi^{(0)})$, multipliers $\lambda^{(0)}$; Learning rates
$\eta_{\theta}$, $\eta_{\lambda}$, $\eta_{\phi}$; Length of sampled trajectory
$K$; Number of inner iterations $K_{in}$; Projection sets $\Lambda$ and
$\Theta$.

Set $t=0$.

Set
$\lambda_{i}^{(t)}=\lambda^{(t)},~{}\psi_{i}^{(0)}=\psi^{(0)},~{}i\in\\{1,\dots,N\\}$.

while $t<T$ do

Set
$\theta_{i}^{(t)}=\theta^{(t)},\phi_{i}^{(t)}=\phi^{(t)},~{}i\in\\{1,\dots,N\\}$.

for $e=1$ to $E$ do

for $i=1$ to $N$ do

Collect a trajectory of length
${\mathcal{T}}_{k}^{t}=\\{(s^{l},a^{l},r^{l},c^{l}_{i},d^{l})\\}_{l=0}^{K-1}$
following $\pi_{\theta_{i}^{(t)}}$.

Compute reward-to-go $\\{R^{l}\\}_{l=0}^{K-1}$ and cost-to-go
$\\{C^{l}_{i}\\}_{l=0}^{K-1}$.

Compute averaged cost of one episode:
$\hat{J}_{C_{i}}=(\sum_{l=0}^{K-1}C_{i}^{l}\mathds{1}_{d^{l}=1})/(\sum_{l=0}^{K-1}\mathds{1}_{d^{l}=1})$.

Take one-step gradient descent w.r.t. $\lambda$:
$\lambda_{i}^{(t+1)}=\operatorname{Proj}_{\Lambda}(\lambda_{i}^{(t)}-\eta_{\lambda}(d_{i}-\hat{J}_{C_{i}}))$.

Compute squared errors of $V_{\phi_{j-1}}$ and $V_{\psi_{j-1}}$:
$Error_{R}(\phi)=\frac{1}{K}\sum_{l=0}^{K-1}(R^{l}-V_{\phi}(s^{l}))^{2},~{}Error_{C_{i}}(\psi)=\frac{1}{K}\sum_{l=0}^{K-1}(C_{i}^{l}-V_{\psi}(s^{l}))^{2}.$

Compute advantages of both reward and cost functions with local critic
networks $V_{\phi_{i}^{t}}$ and $V_{\psi_{i}^{t}}$:
$A_{r}^{l}=R^{l}-V_{\phi_{i}^{(t)}}(s^{l}),~{}A_{c_{i}}^{l}=C^{l}_{i}-V_{\psi_{i}^{(t)}}(s^{l}),~{}\forall
l\in\\{0,\dots,K-1\\}.$

Take one-step gradient descent w.r.t. $\phi$:
$\phi_{i}^{(t+1)}=\phi_{i}^{(t)}-\eta_{\phi}\frac{\partial_{\phi}Error_{R}(\phi)}{\partial_{\phi}}\big{|}_{\phi=\phi_{i}^{(t)}}$.

Take one-step gradient descent w.r.t. $\psi$:
$\psi_{i}^{(t+1)}=\psi_{i}^{(t)}-\eta_{\psi}\frac{\partial_{\psi}Error_{C_{i}}(\psi)}{\partial_{\psi}}\big{|}_{\psi=\psi_{i}^{(t)}}$.

Compute advantages of local Lagrange function
$A_{L}^{l}=A_{r}^{l}/N-\lambda_{i}^{(t)}A_{c_{i}}^{l},~{}\forall
l\in\\{0,\dots,K-1\\}$.

Set $\theta_{0}=\theta_{i}^{(t)}$.

for $j=1$ to $K_{in}$ do

Construct the PPO-clip objective:
$Clip(\theta)=\sum_{l=0}^{K-1}\min\left(\frac{\pi_{\theta}(a_{l}|s_{l})}{\pi_{\theta_{i}^{(t)}}(a_{l}|s_{l})}A_{L}^{l},\max\left((1-\epsilon)A_{L}^{l},~{}(1+\epsilon)A_{L}^{l}\right)~{}\right).$

Take one-step gradient ascent w.r.t. policy parameters:
$\theta_{j}=\operatorname{Proj}_{\Theta}\left(\theta_{j-1}+\eta_{\theta}\frac{\partial_{\theta}Clip(\theta)}{\partial_{\theta}}\big{|}_{\theta=\theta_{j-1}}\right)$.

end for

Set $\theta_{i}^{(t+1)}=\theta_{K_{in}}$.

end for

$t=t+1$

end for

$N$ agents communicate $\\{(\theta_{i}^{(t)},\phi_{i}^{(t)})\\}_{i=1}^{N}$ and
$\\{\lambda_{i}^{(t)}\\}_{i=1}^{N}$.

Set
$\theta^{(t)}=\texttt{Aggregate}_{\theta}(\\{\lambda_{i}^{(t)}\\}_{i=1}^{N},\\{\theta_{i}^{(t)}\\}_{i=1}^{N})$
and
$\phi^{(t)}=\texttt{Aggregate}_{\phi}(\\{\lambda_{i}^{(t)}\\}_{i=1}^{N},\\{\phi_{i}^{(t)}\\}_{i=1}^{N})$.

end while

##  Appendix B Detailed Experiment Settings

###  B.1 Environment Construction

#### RandomMDP

An instance of RandomMDP is composed of a randomly generated transition
dynamic, a randomly generated reward function and $N$ randomly generated cost
functions. The constraint threshold is determined with a randomly generated
anchor policy: its performances w.r.t. $N$ cost functions multiplied by a
hardness factor $\nu<1$ are set to be threshold values of the $N$ constraints.
In our case, we set $|{\mathcal{S}}|=3$, $|{\mathcal{A}}|=5$, $N=4$ and
$\nu=0.7$.

#### WindyCliff

WindyCliff is a modified version of a classical example in Sutton et al.
[1998]: Cliff Walking. In WindyCliff, the agent is expected to walk from the
left-bottom grid to the right-bottom with hazard regions known as the cliff
zone, and there is a blowing wind in the environment with probability
$\theta\leq 1$ of forcing the agent to move regardless of its action. In our
case, the gridworld size is set to be $4\times 10$, the agent can move to any
adjacent grid in four directions (stay unmoved at the move beyond boundaries),
there are three hazard zones notated as $Z_{1},Z_{2},Z_{3}$ and there is a
wind blowing to the bottom of our gridworld.

Figure 2: The gridworld in WindyCliff with size of $4\times 10$.

In terms of the reward function, we reward the agent with 20 at reaching $E$,
while it receives a negative reward of $-1$ at reaching the other grids. In
terms of constraints, we introduce three cost functions corresponding to three
hazard zones: the $k$-th cost function generates a cost of $10$ at reaching
the grid in $Z_{k}$, and the threshold of these cost functions is uniformly
set to be $1.5$. In other words, the agent satisfying these three cost
functions are prohibited from reaching any grid in hazard zones. Moreover, the
wind intensity is set to be $\theta=0.4$ in our instance.

#### CartPole

In the original setting of CartPole Brockman et al. [2016], the block is
horizontally restricted in a range of $[-4.8,4.8]$ and the agent is rewarded
when the pole is kept upright. Keeping the reward function unchanged, we
introduce two hazard zones for the horizontal position of the block:

$\displaystyle Z_{1}$
$\displaystyle=[-2.4,-2.3]\cup[-1.3,-1.2]\cup[-0.1,0.0]\cup[1.1,1.2]\cup[2.2,2.3],$
$\displaystyle Z_{2}$
$\displaystyle=[-2.3,-2.2]\cup[-1.2,-1.1]\cup[0.0,0.1]\cup[1.2,1.3]\cup[2.3,2.4].$

In terms of constraints, the $k$-th cost function generates a cost of $1$ when
the horizontal position of the block falls in $Z_{k}$ and constraint budgets
are both set to be $20$.

#### Acrobot

In our setting, the agent is rewarded with $1.0$ when the free end achieves
the target height $H$, and it is otherwise rewarded with $0.001(s_{h}-H)$ when
the height of free end is $s_{h}$. In terms of constraints, we introduce two
cost functions as follows:

$C_{1}(s,a)=\mathds{1}_{\\{s_{\theta_{1}}\in[-\pi/2,0.0],a=\text{push}\\}},~{}C_{2}(s,a)=\mathds{1}_{\\{s_{\theta_{1}}\in[-\pi/2,0.0],a=\text{pull}\\}},$

where $s_{\theta_{1}}$ represents the angle of the first joint. Budgets of
these constraints are set to be $40$. In other words, agents satisfying these
two actions are not expected to take any action, i.e.$~{}a=\text{null}$, when
the first joint falls in the leftbottom region.

#### InvertedPendulum

In the original setting of InvertedPendulum Brockman et al. [2016], the agent
is rewarded when the pole is kept upright and there is no limit on the
horizontal range of the block. Keeping the reward function unchanged, we
firstly restrict the horizontal range of the block within $[-2.4,2.4]$ and
then introduce two hazard zones:

$\displaystyle Z_{1}$
$\displaystyle=[-2.4,-2.0]\cup[-1.3,-0.8]\cup[-0.2,0.2]\cup[0.8,1.3]\cup[2.0,2.4],$
$\displaystyle Z_{2}$
$\displaystyle=[-1.9,-1.3]\cup[-0.5,-0.2]\cup[0.2,0.5]\cup[1.3,1.9].$

In terms of constraints, the $k$-th cost function generates a cost of $1$ when
the horizontal position of the block falls in $Z_{k}$ and constraint budgets
are both set to be $20$.

###  B.2 Hyperparameter Selection

#### Network structure

In tasks of CartPole, Acrobot and InvertedPendulum, we approximate policy
functions and value functions with deep neural networks. In CartPole and
Acrobot, both policy functions and value functions utilize neural networks
with two hidden layers of size $(64,64)$. In InvertedPendulum, both policy
functions and value functions utilize neural networks with two hidden layers
of size $(256,256)$.

#### Learning rates

In RandomMDP, $(\eta_{\theta},\eta_{\lambda})$ are set to be $(1e-3,1e-3)$. In
WindyCliff, $(\eta_{\theta},\eta_{\lambda})$ are set to be $(3e-4,3e-4)$. In
CartPole, Acrobot and InvertedPendulum,
$(\eta_{\theta},\eta_{\psi},\eta_{\phi},\eta_{\lambda})$ are set to be
$(1e-4,1e-4,1e-4,1e-3)$.

#### Projection set $\Lambda$

In RandomMDP and WindyCliff, we set $\Lambda=[0,10]$. In CartPole and
InvertedPendulum, we set $\Lambda=[0,1]$. In Acrobot, we set $\Lambda=[0,2]$.

#### Other hyperparameters

In RandomMDP and WindyCliff, we set $E=5$ and $K=10$. In the other tasks, we
set $E=1$ and $K=10000$, which indicates that any agent performs at least $10$
local updates between every two communication rounds.

##  Appendix C Notations in the Proofs

In this section, we introduce some useful notations that do not appear in the
main paper. For a CMDP
$\langle{\mathcal{S}},{\mathcal{A}},r,\\{(c_{i},d_{i})\\}_{i=1}^{N},\gamma,{\mathcal{P}}\rangle$,
we define the value function, state-action value function and advantage
function w.r.t the reward $r$ as follows:

$\displaystyle V_{r}^{\pi}(s)$
$\displaystyle={\mathbb{E}}\left[\sum_{t=0}^{\infty}\gamma^{t}r(s_{t},a_{t})\mathrel{\bigg{|}}s_{0}=s,a_{t}\sim\pi(\cdot|s_{t})\right],$
$\displaystyle Q_{r}^{\pi}(s,a)$
$\displaystyle={\mathbb{E}}\left[\sum_{t=0}^{\infty}\gamma^{t}r(s_{t},a_{t})\mathrel{\bigg{|}}s_{0}=s,a_{0}=a,a_{t}\sim\pi(\cdot|s_{t})\
\text{for}\ {t\geq 1}\right],$ $\displaystyle A^{\pi}_{r}(s,a)$
$\displaystyle=Q^{\pi}_{r}(s,a)-V^{\pi}_{r}(s).$

Given an initial distribution $\rho$, we also define
$V_{r}^{\pi}(\rho)={\mathbb{E}}_{s\sim\rho}V_{r}^{\pi}(s)$. We define the
value function, state-action value function and advantage function w.r.t the
$i$th cost function $c_{i}$ as $V_{c_{i}}^{\pi}(s)$, $Q_{c_{i}}^{\pi}(s,a)$
and $A^{\pi}_{c_{i}}(s,a)$ in a similar manner. Given an initial distribution
$\rho$, we also define
$V_{c_{i}}^{\pi}(\rho)={\mathbb{E}}_{s\sim\rho}V_{c_{i}}^{\pi}(s)$. For
simplicity of notations, we use $\pi^{(t)}$ in short for $\pi_{\theta^{(t)}}$,
$\pi_{i}^{(t)}$ in short for $\pi_{\theta_{i}^{(t)}}$ and $\pi^{[t]}$ in short
of $\pi_{\bar{\theta}^{(t)}}$. We also use $V_{\diamond}^{(t)}$,
$V_{\diamond}^{(t)_{i}}$, $V_{\diamond}^{[t]}$ and $V_{\diamond}^{*}$ in short
for $V_{\diamond}^{\pi^{(t)}}$, $V_{\diamond}^{\pi_{i}^{(t)}}$,
$V_{\diamond}^{\pi^{[t]}}$ and $V_{\diamond}^{\pi^{*}}$ respectively. Here
$\diamond$ represents either the reward $r$ or the $i$th cost function
$c_{i}$. $Q_{\diamond}^{(t)}$, $Q_{\diamond}^{(t)_{i}}$, $Q_{\diamond}^{[t]}$,
$Q_{\diamond}^{*}$, $A_{\diamond}^{(t)}$, $A_{\diamond}^{(t)_{i}}$,
$A_{\diamond}^{[t]}$ and $A_{\diamond}^{*}$ are defined similarly.

##  Appendix D Auxiliary Lemmas

######  Lemma D.1 (Performance difference lemma).

For any state $s\in{\mathcal{S}}$, any stationary policy $\pi,\pi^{\prime}$,
we have

$V^{\pi}_{\diamond}\left(s_{0}\right)-V^{\pi^{\prime}}_{\diamond}\left(s_{0}\right)=\frac{1}{1-\gamma}\mathbb{E}_{s\sim
d_{s_{0}}^{\pi}}\left[\mathbb{E}_{a\sim\pi(\cdot\mid
s)}A_{\diamond}^{\pi^{\prime}}(s,a)\right].$

###### Proof.

See Kakade and Langford [2002]. ∎

######  Lemma D.2 (Lipschitz values).

Let Assumption 4.2 hold true. For any $s_{0}\in{\mathcal{S}}$,

$|V_{\diamond}^{\pi_{\theta}}(s)-V_{\diamond}^{\pi_{\theta^{\prime}}}(s)|\leq\frac{|{\mathcal{A}}|L_{\pi}\|\theta-\theta^{\prime}\|_{2}}{(1-\gamma)^{2}}.$

###### Proof.

By Lemma D.1 we have

$\displaystyle
V_{\diamond}^{\pi_{\theta}}(s_{0})-V_{\diamond}^{\pi_{\theta^{\prime}}}(s_{0})$
$\displaystyle=\frac{1}{1-\gamma}{\mathbb{E}}_{s\sim
d^{\pi_{\theta}}}\left[{\mathbb{E}}_{a\sim\pi_{\theta}(\cdot|s)}A_{\diamond}^{\pi_{\theta^{\prime}}}(s,a)\right]$
$\displaystyle=\frac{1}{1-\gamma}{\mathbb{E}}_{s\sim
d^{\pi_{\theta}}}\left[(\pi_{\theta}(\cdot|s)-\pi_{\theta^{\prime}}(\cdot|s))^{\top}Q_{\diamond}^{\pi_{\theta^{\prime}}}(s,a)\right]$
$\displaystyle\leq\frac{1}{1-\gamma}{\mathbb{E}}_{s\sim
d^{\pi_{\theta}}}\left[\|\pi_{\theta}(\cdot|s)-\pi_{\theta^{\prime}}(\cdot|s)\|_{\infty}\|Q_{\diamond}^{\pi_{\theta^{\prime}}}(s,a)\|_{1}\right]$
$\displaystyle\leq\frac{|{\mathcal{A}}|}{(1-\gamma)^{2}}\max_{s\in{\mathcal{S}},a\in{\mathcal{A}}}|\pi_{\theta}(a|s)-\pi_{\theta^{\prime}}(a|s)|.$

Now we may apply Assumption 4.2 to get for any
$s\in{\mathcal{S}},a\in{\mathcal{A}}$,

$\|\nabla_{\theta}\pi_{\theta}(s|a)\|_{2}\leq\|\nabla_{\theta}\log\pi_{\theta}(s|a)\|_{2}\leq
L_{\pi}.$

Therefore, for any $s\in{\mathcal{S}},a\in{\mathcal{A}}$

$|\pi_{\theta}(a|s)-\pi_{\theta^{\prime}}(a|s)|\leq
L_{\pi}\|\theta-\theta^{\prime}\|_{2}$

and

$\displaystyle
V_{\diamond}^{\pi_{\theta}}(s_{0})-V_{\diamond}^{\pi_{\theta^{\prime}}}(s_{0})$
$\displaystyle\leq\frac{|{\mathcal{A}}|}{(1-\gamma)^{2}}\max_{s\in{\mathcal{S}},a\in{\mathcal{A}}}|\pi_{\theta}(a|s)-\pi_{\theta^{\prime}}(a|s)|$
$\displaystyle\leq\frac{|{\mathcal{A}}|L_{\pi}\|\theta-\theta^{\prime}\|_{2}}{(1-\gamma)^{2}}$

∎

######  Lemma D.3 (Strong duality and bounded dual variables).

If Assumption 4.7 and Assumption 4.8 are true, we have:

$\displaystyle\text{(a):\
}J_{r}(\pi^{*})=\sup_{\theta^{*}}\inf_{\lambda}L_{0}(\theta,\lambda);$
$\displaystyle\text{(b):\
}\sum_{i=1}^{N}\lambda^{*}_{i}\leq\frac{J_{r}(\pi^{*})-J_{r}(\tilde{\pi})}{\xi}\leq\frac{1}{(1-\gamma)\xi}.$

###### Proof.

The proof of part (a) can be found in Paternain et al. [2019]. To prove part
(b), we consider a sublevel set $\Lambda_{a}$:

$\Lambda_{a}:=\\{\lambda\in[0,\infty)^{N}\mid\sup_{\theta}L_{0}(\theta,\lambda)\leq
a\\}.$

For any $\lambda\in\Lambda_{a}$, we have

$J_{r}(\tilde{\pi})+\xi\sum_{i=1}^{N}\lambda_{i}\leq
J_{r}(\tilde{\pi})+\sum_{i=1}^{N}\lambda_{i}(d_{i}-J_{c_{i}}(\tilde{\pi}))\leq
a,$

where $\tilde{\pi}$ is defined as in Assumption 4.8. Thus we have
$\sum_{i=1}^{N}\lambda_{i}\leq\frac{a-J_{r}(\tilde{\pi})}{\xi}$. The result
follows by setting $a=J_{r}(\pi^{*})$. ∎

######  Lemma D.4 (Constraint violation).

Let Assumption 4.7, Assumption 4.8 hold true. If there exists a policy
$\bar{\pi}\in\Pi$, a positive scalar $C>2\lambda^{*}_{i},\forall
i\in\\{1,...,N\\}$, and another positive scalar $\delta$ such that:

$J_{r}(\pi^{*})-J_{r}(\bar{\pi})+C\sum_{i=1}^{N}(J_{c_{i}}(\bar{\pi})-d_{i})_{+}\leq\delta,$

then we have

$\sum_{i=1}^{N}(J_{c_{i}}(\bar{\pi})-d_{i})_{+}\leq\frac{2\delta}{C}.$

###### Proof.

For any $\tau\in\mathbb{R}^{N}$, define the perturbation function associated
to Problem 1 as:

$\displaystyle P(\tau)=\max_{\pi}$ $\displaystyle J_{r}(\pi)$ $\displaystyle
s.t.$ $\displaystyle J_{c_{i}}(\pi)\leq d_{i}-\tau_{i},\ i=1,...,N.$

First, according to Lemma D.3 we have $\forall\pi$,

$J_{r}(\pi)+\sum_{i=1}^{N}\lambda^{*}_{i}(d_{i}-J_{c_{i}}(\pi))\leq
J_{r}(\pi^{*})=P(0).$

For any $\pi\in\Pi$ such that $J_{c_{i}}(\pi)\leq d_{i}-\tau_{i}$, we have

$\displaystyle P(0)-\sum_{i=1}^{N}\tau_{i}\lambda_{i}^{*}$ $\displaystyle\geq
J_{r}(\pi)+\sum_{i=1}^{N}\lambda^{*}_{i}(d_{i}-J_{c_{i}}(\pi))-\sum_{i=1}^{N}\tau_{i}\lambda_{i}^{*}$
$\displaystyle=J_{r}(\pi)+\sum_{i=1}^{N}\lambda^{*}_{i}(d_{i}-J_{c_{i}}(\pi)-\tau_{i})$
$\displaystyle\geq J_{r}(\pi).$

If we take $\tau_{i}=-(J_{c_{i}}(\bar{\pi})-d_{i})_{+}$, then because
$J_{c_{i}}(\bar{\pi})\leq d_{i}+(J_{c_{i}}(\bar{\pi})-d_{i})_{+}$ we can get

$\displaystyle J_{r}(\bar{\pi})\leq
P(0)-\sum_{i=1}^{N}\tau_{i}\lambda_{i}^{*}=J_{r}(\pi^{*})-\sum_{i=1}^{N}\tau_{i}\lambda_{i}^{*}.$

Noting that

$\frac{C}{2}\sum_{i=1}^{N}(-\tau_{i})\leq\sum_{i=1}^{N}(C-\lambda^{*}_{i})(-\tau_{i})\leq
C\sum_{i=1}^{N}(-\tau_{i})+J_{r}(\pi^{*})-J_{r}(\bar{\pi})\leq\delta,$

we complete the proof. ∎

##  Appendix E Omitted Proofs

###### Proof of Lemma 4.1 .

See the proof of Lemma D.3. ∎

######  Lemma E.1.

We have

$\displaystyle{\mathbb{E}}\left[\frac{1}{TN}\sum_{t=0}^{T-1}\sum_{i=1}^{N}(V_{r}^{*}(\rho)-V_{r}^{(t)_{i}}(\rho))\right]$
$\displaystyle\leq\frac{\log|{\mathcal{A}}|}{T(1-\gamma)\eta_{\theta}}+{\mathbb{E}}\left[\frac{1}{TN}\sum_{t=0}^{T-1}\sum_{i=1}^{N}\frac{\beta}{1-\gamma}\left\|\bar{\theta}^{(t)}-\theta_{i}^{(t)}\right\|_{2}\left\|\hat{w}_{i}^{(t)}\right\|_{2}\right]+{\mathbb{E}}\left[\frac{1}{T}\sum_{t=0}^{T-1}\sum_{i=1}^{N}\lambda_{i}^{(t)}(V_{c_{i}}^{*}(\rho)-V_{c_{i}}^{(t)_{i}}(\rho))\right]$
$\displaystyle\quad+{\mathbb{E}}\left[\frac{1}{TN(1-\gamma)}\sum_{t=0}^{T-1}\sum_{i=1}^{N}\sqrt{E^{\nu^{*}}\left(r,\theta^{(t)},\hat{w}^{(t)}_{r}(i)\right)}+\frac{1}{T(1-\gamma)}\sum_{t=0}^{T-1}\sum_{i=1}^{N}\lambda_{i}^{(t)}\sqrt{E^{\nu^{*}}\left(c_{i},\theta^{(t)},\hat{w}^{(t)}_{c_{i}}\right)}\right]$
$\displaystyle\quad+\beta\eta_{\theta}V^{2}(N+1)\left(\frac{N}{2(1-\gamma)^{3}\xi^{2}}+\frac{1}{2(1-\gamma)}\right)$

###### Proof.

Recall that the virtual sequence $\\{\bar{\theta}^{(t)}\\}$ is defined as:

$\bar{\theta}^{(t)}=\frac{1}{N}\sum_{i=1}^{N}{\theta_{i}^{(t)}}.$

And we always have

$\displaystyle\bar{\theta}^{(t+1)}$
$\displaystyle=\frac{1}{N}\sum_{i=1}^{N}\theta_{i}^{(t+1)}$
$\displaystyle=\frac{1}{N}\sum_{i=1}^{N}\left[\theta_{i}^{(t)}+\eta_{\theta}\hat{w}_{i}^{(t)}\right]$
$\displaystyle=\frac{1}{N}\sum_{i=1}^{N}\left[\theta_{i}^{(t)}+\eta_{\theta}\left(\hat{w}_{r}^{(t)}(i)-N\lambda_{i}^{(t)}\hat{w}_{c_{i}}^{(t)}\right)\right]$
$\displaystyle=\bar{\theta}^{(t)}+\eta_{\theta}\left(\frac{1}{N}\sum_{i=1}^{N}\hat{w}_{r}^{(t)}(i)-\sum_{i=1}^{N}\lambda_{i}^{(t)}\hat{w}_{c_{i}}^{(t)}\right)$
$\displaystyle:=\bar{\theta}^{(t)}+\eta_{\theta}\hat{w}^{(t)}$

We have $\bar{\theta}^{(t)}=\theta^{(t)}$ when $E\mid t$. Now we have

$\displaystyle{\mathbb{E}}_{s\sim
d^{\pi^{*}}}(D_{\operatorname{KL}}(\pi^{*}(\cdot|s)\|\pi^{[t]}(\cdot|s))-D_{\operatorname{KL}}(\pi^{*}(\cdot|s)\|\pi^{[t+1]}(\cdot|s)))$
$\displaystyle=-{\mathbb{E}}_{(s,a)\sim\nu^{*}}\log\frac{\pi^{[t]}(a|s)}{\pi^{[t+1]}(a|s)}$
$\displaystyle\geq\eta_{\theta}{\mathbb{E}}_{(s,a)\sim\nu^{*}}[\nabla_{\theta}\log\pi^{[t]}(a|s)^{\top}\hat{w}^{(t)}]-\frac{\beta\eta_{\theta}^{2}}{2}\|\hat{w}^{(t)}\|^{2}_{2}$
$\displaystyle=\frac{1}{N}\sum_{i=1}^{N}\eta_{\theta}{\mathbb{E}}_{(s,a)\sim\nu^{*}}\left[\nabla_{\theta}\log\pi^{[t]}(a|s)^{\top}\hat{w}_{i}^{(t)}\right]-\frac{\beta\eta_{\theta}^{2}}{2}\|\hat{w}^{(t)}\|^{2}_{2}$
$\displaystyle=\frac{1}{N}\sum_{i=1}^{N}\eta_{\theta}{\mathbb{E}}_{(s,a)\sim\nu^{*}}\left[\left(\nabla_{\theta}\log\pi^{[t]}(a|s)-\nabla_{\theta}\log\pi^{(t)}_{i}(a|s)\right)^{\top}\hat{w}_{i}^{(t)}\right]+\frac{1}{N}\sum_{i=1}^{N}\eta_{\theta}{\mathbb{E}}_{(s,a)\sim\nu^{*}}\left[\nabla_{\theta}\log\pi^{(t)}_{i}(a|s)^{\top}\hat{w}_{i}^{(t)}\right]$
$\displaystyle\quad-\frac{\beta\eta_{\theta}^{2}}{2}\|\hat{w}^{(t)}\|^{2}_{2}$
$\displaystyle\geq-\frac{1}{N}\sum_{i=1}^{N}\eta_{\theta}{\mathbb{E}}_{(s,a)\sim\nu^{*}}\left[\left\|\nabla_{\theta}\log\pi^{[t]}(a|s)-\nabla_{\theta}\log\pi^{(t)}_{i}(a|s)\right\|_{2}\left\|\hat{w}_{i}^{(t)}\right\|_{2}\right]+\frac{1}{N}\sum_{i=1}^{N}\eta_{\theta}{\mathbb{E}}_{(s,a)\sim\nu^{*}}\left[\nabla_{\theta}\log\pi^{(t)}_{i}(a|s)^{\top}\hat{w}_{i}^{(t)}\right]$
$\displaystyle\quad-\frac{\beta\eta_{\theta}^{2}}{2}\|\hat{w}^{(t)}\|^{2}_{2}$
$\displaystyle=-\frac{1}{N}\sum_{i=1}^{N}\eta_{\theta}\beta\left\|\bar{\theta}^{(t)}-\theta_{i}^{(t)}\right\|_{2}\left\|\hat{w}_{i}^{(t)}\right\|_{2}+\frac{1}{N}\sum_{i=1}^{N}\eta_{\theta}{\mathbb{E}}_{(s,a)\sim\nu^{*}}\left[\nabla_{\theta}\log\pi^{(t)}_{i}(a|s)^{\top}\hat{w}_{i}^{(t)}\right]-\frac{\beta\eta_{\theta}^{2}}{2}\|\hat{w}^{(t)}\|^{2}_{2}$
$\displaystyle=-\frac{1}{N}\sum_{i=1}^{N}\eta_{\theta}\beta\left\|\bar{\theta}^{(t)}-\theta_{i}^{(t)}\right\|_{2}\left\|\hat{w}_{i}^{(t)}\right\|_{2}+\frac{1}{N}\sum_{i=1}^{N}\eta_{\theta}{\mathbb{E}}_{(s,a)\sim\nu^{*}}A_{r}^{(t)_{i}}(s,a)-\sum_{i=1}^{N}\eta_{\theta}{\mathbb{E}}_{(s,a)\sim\nu^{*}}\left[\lambda_{i}^{(t)}A_{c_{i}}^{(t)_{i}}(s,a)\right]$
$\displaystyle\quad+\frac{1}{N}\sum_{i=1}^{N}\eta_{\theta}{\mathbb{E}}_{(s,a)\sim\nu^{*}}\left[\nabla_{\theta}\log\pi^{(t)}_{i}(a|s)^{\top}\hat{w}_{i}^{(t)}-\left(A_{r}^{(t)_{i}}(s,a)-N\lambda_{i}^{(t)}A_{c_{i}}^{(t)_{i}}(s,a)\right)\right]-\frac{\beta\eta_{\theta}^{2}}{2}\|\hat{w}^{(t)}\|^{2}_{2}$
$\displaystyle=-\frac{1}{N}\sum_{i=1}^{N}\eta_{\theta}\beta\left\|\bar{\theta}^{(t)}-\theta_{i}^{(t)}\right\|_{2}\left\|\hat{w}_{i}^{(t)}\right\|_{2}+\frac{1}{N}\sum_{i=1}^{N}\eta_{\theta}{\mathbb{E}}_{(s,a)\sim\nu^{*}}A_{r}^{(t)_{i}}(s,a)-\sum_{i=1}^{N}\eta_{\theta}{\mathbb{E}}_{(s,a)\sim\nu^{*}}\left[\lambda_{i}^{(t)}A_{c_{i}}^{(t)_{i}}(s,a)\right]$
$\displaystyle\quad+\frac{1}{N}\sum_{i=1}^{N}\eta_{\theta}{\mathbb{E}}_{(s,a)\sim\nu^{*}}\left[\nabla_{\theta}\log\pi^{(t)}_{i}(a|s)^{\top}\hat{w}_{i}^{(t)}-\left(A_{r}^{(t)_{i}}(s,a)-N\lambda_{i}^{(t)}A_{c_{i}}^{(t)_{i}}(s,a)\right)\right]-\frac{\beta\eta_{\theta}^{2}}{2}\|\hat{w}^{(t)}\|^{2}_{2}$
$\displaystyle=-\frac{1}{N}\sum_{i=1}^{N}\eta_{\theta}\beta\left\|\bar{\theta}^{(t)}-\theta_{i}^{(t)}\right\|_{2}\left\|\hat{w}_{i}^{(t)}\right\|_{2}+\frac{1}{N}\sum_{i=1}^{N}\eta_{\theta}{\mathbb{E}}_{(s,a)\sim\nu^{*}}A_{r}^{(t)_{i}}(s,a)-\sum_{i=1}^{N}\eta_{\theta}{\mathbb{E}}_{(s,a)\sim\nu^{*}}\left[\lambda_{i}^{(t)}A_{c_{i}}^{(t)}(s,a)\right]-\frac{\beta\eta_{\theta}^{2}}{2}\|\hat{w}^{(t)}\|^{2}_{2}$
$\displaystyle\quad+\frac{1}{N}\sum_{i=1}^{N}\eta_{\theta}{\mathbb{E}}_{(s,a)\sim\nu^{*}}\left[\nabla_{\theta}\log\pi^{(t)_{i}}(a|s)^{\top}\hat{w}_{r}^{(t)}(i)-A_{r}^{(t)_{i}}(s,a)\right]-\sum_{i=1}^{N}\eta_{\theta}\lambda_{i}^{(t)}{\mathbb{E}}_{(s,a)\sim\nu^{*}}\left[\nabla_{\theta}\log\pi^{(t)_{i}}(a|s)^{\top}\hat{w}_{c_{i}}^{(t)}(t)-A_{c_{i}}^{(t)_{i}}(s,a)\right].$

Now we apply the performance difference lemma and Jensen’s inequality:

$\displaystyle-\frac{1}{N}\sum_{i=1}^{N}\eta_{\theta}\beta\left\|\bar{\theta}^{(t)}-\theta_{i}^{(t)}\right\|_{2}\left\|\hat{w}_{i}^{(t)}\right\|_{2}+\frac{1}{N}\sum_{i=1}^{N}\eta_{\theta}{\mathbb{E}}_{(s,a)\sim\nu^{*}}A_{r}^{(t)_{i}}(s,a)-\sum_{i=1}^{N}\eta_{\theta}{\mathbb{E}}_{(s,a)\sim\nu^{*}}\left[\lambda_{i}^{(t)}A_{c_{i}}^{(t)}(s,a)\right]-\frac{\beta\eta_{\theta}^{2}}{2}\|\hat{w}^{(t)}\|^{2}_{2}$
$\displaystyle\quad+\frac{1}{N}\sum_{i=1}^{N}\eta_{\theta}{\mathbb{E}}_{(s,a)\sim\nu^{*}}\left[\nabla_{\theta}\log\pi^{(t)_{i}}(a|s)^{\top}\hat{w}_{r}^{(t)}(i)-A_{r}^{(t)_{i}}(s,a)\right]-\sum_{i=1}^{N}\eta_{\theta}\lambda_{i}^{(t)}{\mathbb{E}}_{(s,a)\sim\nu^{*}}\left[\nabla_{\theta}\log\pi^{(t)_{i}}(a|s)^{\top}\hat{w}_{c_{i}}^{(t)}(t)-A_{c_{i}}^{(t)_{i}}(s,a)\right]$
$\displaystyle\geq-\frac{1}{N}\sum_{i=1}^{N}\eta_{\theta}\beta\left\|\bar{\theta}^{(t)}-\theta_{i}^{(t)}\right\|_{2}\left\|\hat{w}_{i}^{(t)}\right\|_{2}+\frac{1}{N}\sum_{i=1}^{N}(1-\gamma)\eta_{\theta}(V_{r}^{*}(\rho)-V_{r}^{(t)_{i}}(\rho))-\sum_{i=1}^{N}(1-\gamma)\eta_{\theta}\lambda_{i}^{(t)}(V_{c_{i}}^{*}(\rho)-V_{c_{i}}^{(t)_{i}}(\rho))$
$\displaystyle\quad-\frac{\eta_{\theta}}{N}\sum_{i=1}^{N}\sqrt{E^{\nu^{*}}\left(r,\theta_{i}^{(t)},\hat{w}^{(t)}_{r}(i)\right)}-\eta_{\theta}\sum_{i=1}^{N}\lambda_{i}^{(t)}\sqrt{E^{\nu^{*}}\left(c_{i},\theta_{i}^{(t)},\hat{w}^{(t)}_{c_{i}}\right)}-\frac{\beta\eta_{\theta}^{2}}{2}\|\hat{w}^{(t)}\|^{2}_{2}.$

Rearranging terms yields

$\displaystyle\frac{1}{N}\sum_{i=1}^{N}(V_{r}^{*}(\rho)-V_{r}^{(t)_{i}}(\rho))$
$\displaystyle\leq\frac{1}{(1-\gamma)\eta_{\theta}}{\mathbb{E}}_{s\sim
d^{\pi^{*}}}(D_{\operatorname{KL}}(\pi^{*}(\cdot|s)\|\pi^{[t]}(\cdot|s))-D_{\operatorname{KL}}(\pi^{*}(\cdot|s)\|\pi^{[t+1]}(\cdot|s)))+\frac{1}{N}\sum_{i=1}^{N}\frac{\beta}{1-\gamma}\left\|\bar{\theta}^{(t)}-\theta_{i}^{(t)}\right\|_{2}\left\|\hat{w}_{i}^{(t)}\right\|_{2}$
$\displaystyle\quad+\sum_{i=1}^{N}\lambda_{i}^{(t)}(V_{c_{i}}^{*}(\rho)-V_{c_{i}}^{(t)_{i}}(\rho))+\frac{1}{N(1-\gamma)}\sum_{i=1}^{N}\sqrt{E^{\nu^{*}}\left(r,\theta_{i}^{(t)},\hat{w}^{(t)}_{r}(i)\right)}+\frac{1}{1-\gamma}\sum_{i=1}^{N}\lambda_{i}^{(t)}\sqrt{E^{\nu^{*}}\left(c_{i},\theta_{i}^{(t)},\hat{w}^{(t)}_{c_{i}}\right)}$
$\displaystyle\quad+\frac{\beta\eta_{\theta}}{2(1-\gamma)}\|\hat{w}^{(t)}\|^{2}_{2}.$

Therefore,

$\displaystyle\frac{1}{TN}\sum_{t=0}^{T-1}\sum_{i=1}^{N}(V_{r}^{*}(\rho)-V_{r}^{(t)_{i}}(\rho))$
$\displaystyle\leq\frac{1}{T(1-\gamma)\eta_{\theta}}{\mathbb{E}}_{s\sim
d^{\pi^{*}}}(D_{\operatorname{KL}}(\pi^{*}(\cdot|s)\|\pi^{[0]}(\cdot|s))-D_{\operatorname{KL}}(\pi^{*}(\cdot|s)\|\pi^{[T]}(\cdot|s)))+\frac{1}{TN}\sum_{t=0}^{T-1}\sum_{i=1}^{N}\frac{\beta}{1-\gamma}\left\|\bar{\theta}^{(t)}-\theta_{i}^{(t)}\right\|_{2}\left\|\hat{w}_{i}^{(t)}\right\|_{2}$
$\displaystyle\quad+\frac{1}{TN(1-\gamma)}\sum_{t=0}^{T-1}\sum_{i=1}^{N}\sqrt{E^{\nu^{*}}\left(r,\theta^{(t)},\hat{w}^{(t)}_{r}(i)\right)}+\frac{1}{T(1-\gamma)}\sum_{t=0}^{T-1}\sum_{i=1}^{N}\lambda_{i}^{(t)}\sqrt{E^{\nu^{*}}\left(c_{i},\theta^{(t)},\hat{w}^{(t)}_{c_{i}}\right)}$
$\displaystyle\quad+\frac{1}{T}\sum_{t=0}^{T-1}\sum_{i=1}^{N}\lambda_{i}^{(t)}(V_{c_{i}}^{*}(\rho)-V_{c_{i}}^{(t)_{i}}(\rho))+\frac{\beta\eta_{\theta}}{2T(1-\gamma)}\sum_{t=0}^{T-1}\|\hat{w}^{(t)}\|^{2}_{2}$
$\displaystyle\leq\frac{\log|{\mathcal{A}}|}{T(1-\gamma)\eta_{\theta}}+\frac{1}{TN}\sum_{t=0}^{T-1}\sum_{i=1}^{N}\frac{\beta}{1-\gamma}\left\|\bar{\theta}^{(t)}-\theta_{i}^{(t)}\right\|_{2}\left\|\hat{w}_{i}^{(t)}\right\|_{2}+\frac{1}{T}\sum_{t=0}^{T-1}\sum_{i=1}^{N}\lambda_{i}^{(t)}(V_{c_{i}}^{*}(\rho)-V_{c_{i}}^{(t)_{i}}(\rho))+\frac{\beta\eta_{\theta}}{2T(1-\gamma)}\sum_{t=0}^{T-1}\|\hat{w}^{(t)}\|^{2}_{2}$
$\displaystyle\quad+\frac{1}{TN(1-\gamma)}\sum_{t=0}^{T-1}\sum_{i=1}^{N}\sqrt{E^{\nu^{*}}\left(r,\theta^{(t)},\hat{w}^{(t)}_{r}(i)\right)}+\frac{1}{T(1-\gamma)}\sum_{t=0}^{T-1}\sum_{i=1}^{N}\lambda_{i}^{(t)}\sqrt{E^{\nu^{*}}\left(c_{i},\theta^{(t)},\hat{w}^{(t)}_{c_{i}}\right)}.$

Now we take expectation to both sides and use
$\lambda_{i}^{(t)}\in[0,\frac{2}{(1-\gamma)\xi}]$:

$\displaystyle{\mathbb{E}}\left[\frac{1}{TN}\sum_{t=0}^{T-1}\sum_{i=1}^{N}(V_{r}^{*}(\rho)-V_{r}^{(t)_{i}}(\rho))\right]$
$\displaystyle\leq\frac{\log|{\mathcal{A}}|}{T(1-\gamma)\eta_{\theta}}+{\mathbb{E}}\left[\frac{1}{TN}\sum_{t=0}^{T-1}\sum_{i=1}^{N}\frac{\beta}{1-\gamma}\left\|\bar{\theta}^{(t)}-\theta_{i}^{(t)}\right\|_{2}\left\|\hat{w}_{i}^{(t)}\right\|_{2}\right]+{\mathbb{E}}\left[\frac{1}{T}\sum_{t=0}^{T-1}\sum_{i=1}^{N}\lambda_{i}^{(t)}(V_{c_{i}}^{*}(\rho)-V_{c_{i}}^{(t)_{i}}(\rho))\right]$
$\displaystyle\quad+{\mathbb{E}}\left[\frac{1}{TN(1-\gamma)}\sum_{t=0}^{T-1}\sum_{i=1}^{N}\sqrt{E^{\nu^{*}}\left(r,\theta^{(t)},\hat{w}^{(t)}_{r}(i)\right)}+\frac{1}{T(1-\gamma)}\sum_{t=0}^{T-1}\sum_{i=1}^{N}\lambda_{i}^{(t)}\sqrt{E^{\nu^{*}}\left(c_{i},\theta^{(t)},\hat{w}^{(t)}_{c_{i}}\right)}\right]$
$\displaystyle\quad+{\mathbb{E}}\left[\frac{\beta\eta_{\theta}}{2T(1-\gamma)}\sum_{t=0}^{T-1}\|\hat{w}^{(t)}\|^{2}_{2}\right]$
$\displaystyle\leq\frac{\log|{\mathcal{A}}|}{T(1-\gamma)\eta_{\theta}}+{\mathbb{E}}\left[\frac{1}{TN}\sum_{t=0}^{T-1}\sum_{i=1}^{N}\frac{\beta}{1-\gamma}\left\|\bar{\theta}^{(t)}-\theta_{i}^{(t)}\right\|_{2}\left\|\hat{w}_{i}^{(t)}\right\|_{2}\right]+{\mathbb{E}}\left[\frac{1}{T}\sum_{t=0}^{T-1}\sum_{i=1}^{N}\lambda_{i}^{(t)}(V_{c_{i}}^{*}(\rho)-V_{c_{i}}^{(t)_{i}}(\rho))\right]$
$\displaystyle\quad+{\mathbb{E}}\left[\frac{1}{TN(1-\gamma)}\sum_{t=0}^{T-1}\sum_{i=1}^{N}\sqrt{E^{\nu^{*}}\left(r,\theta^{(t)},\hat{w}^{(t)}_{r}(i)\right)}+\frac{1}{T(1-\gamma)}\sum_{t=0}^{T-1}\sum_{i=1}^{N}\lambda_{i}^{(t)}\sqrt{E^{\nu^{*}}\left(c_{i},\theta^{(t)},\hat{w}^{(t)}_{c_{i}}\right)}\right]$
$\displaystyle\quad+\beta\eta_{\theta}V^{2}(N+1)\left(\frac{N}{2(1-\gamma)^{3}\xi^{2}}+\frac{1}{2(1-\gamma)}\right).$

We complete the proof. ∎

######  Lemma E.2.

For any $i\in\\{1,...,N\\}$, $t\in\\{0,...,T-1\\}$,

$\displaystyle{\mathbb{E}}\|\bar{\theta}^{(t)}-\theta_{i}^{(t)}\|_{2}^{2}$
$\displaystyle\leq
4(E-1)^{2}\eta_{\theta}^{2}V^{2}(N+1)\left(\frac{N}{(1-\gamma)^{2}\xi^{2}}+1\right)$
$\displaystyle{\mathbb{E}}\|\theta^{(t)}-\theta_{i}^{(t)}\|_{2}$
$\displaystyle\leq(E-1)\eta_{\theta}V\left(\frac{N}{(1-\gamma)\xi}+1\right)$

###### Proof.

By the definition of $\bar{\theta}^{(t)}$, we may always find $t-E<t_{0}\leq
t$ such that $\bar{\theta}_{i}^{(t_{0})}=\theta_{i}^{(t_{0})}$, $\forall
i\in\\{1,...,N\\}$. If $t_{0}=t$, then the conclusion holds trivially. Else we
have

$\displaystyle{\mathbb{E}}\|\bar{\theta}^{(t)}-\theta_{i}^{(t)}\|_{2}^{2}$
$\displaystyle\leq
2{\mathbb{E}}\|\bar{\theta}^{(t)}-\bar{\theta}^{(t_{0})}\|_{2}^{2}+2{\mathbb{E}}\|\theta_{i}^{(t)}-\theta_{i}^{(t_{0})}\|_{2}^{2}$
$\displaystyle=2{\mathbb{E}}\left[\left\|\sum_{t^{\prime}=t_{0}}^{t-1}\eta_{\theta}\hat{w}^{(t^{\prime})}\right\|_{2}^{2}\right]+2{\mathbb{E}}\left[\left\|\sum_{t^{\prime}=t_{0}}^{t-1}\eta_{\theta}\hat{w}_{i}^{(t^{\prime})}\right\|_{2}^{2}\right]$
$\displaystyle\leq
2(t-1-t_{0})\sum_{t^{\prime}=t_{0}}^{t-1}{\mathbb{E}}\left[\left\|\eta_{\theta}\hat{w}^{(t^{\prime})}\right\|_{2}^{2}\right]+2(t-1-t_{0})\sum_{t^{\prime}=t_{0}}^{t-1}{\mathbb{E}}\left[\left\|\eta_{\theta}\hat{w}_{i}^{(t^{\prime})}\right\|_{2}^{2}\right]$
$\displaystyle\leq
2(E-1)\sum_{t^{\prime}=t_{0}}^{t_{0}+E-2}{\mathbb{E}}\left[\left\|\eta_{\theta}\hat{w}^{(t^{\prime})}\right\|_{2}^{2}\right]+2(E-1)\sum_{t^{\prime}=t_{0}}^{t_{0}+E-2}{\mathbb{E}}\left[\left\|\eta_{\theta}\hat{w}_{i}^{(t^{\prime})}\right\|_{2}^{2}\right]$
$\displaystyle\leq
4(E-1)^{2}\eta_{\theta}^{2}V^{2}(N+1)\left(\frac{N}{(1-\gamma)^{2}\xi^{2}}+1\right)$

Similarly, there always exists $t-E<t_{0}\leq t$ such that
$\theta^{(t)}=\theta^{(t_{0})}=\theta_{i}^{(t_{0})}$, $\forall
i\in\\{1,...,N\\}$. If $t_{0}=t$, then the conclusion holds trivially. Else we
have

$\displaystyle{\mathbb{E}}\|\theta^{(t)}-\theta_{i}^{(t)}\|_{2}$
$\displaystyle={\mathbb{E}}\|\theta_{i}^{(t)}-\theta_{i}^{(t_{0})}\|_{2}$
$\displaystyle={\mathbb{E}}\left[\left\|\sum_{t^{\prime}=t_{0}}^{t-1}\eta_{\theta}\hat{w}_{i}^{(t^{\prime})}\right\|_{2}\right]$
$\displaystyle\leq\sum_{t^{\prime}=t_{0}}^{t-1}{\mathbb{E}}\left[\left\|\eta_{\theta}\hat{w}_{i}^{(t^{\prime})}\right\|_{2}\right]$
$\displaystyle\leq\sum_{t^{\prime}=t_{0}}^{t_{0}+E-2}{\mathbb{E}}\left[\left\|\eta_{\theta}\hat{w}_{i}^{(t^{\prime})}\right\|_{2}\right]$
$\displaystyle\leq(E-1)\eta_{\theta}V\left(\frac{N}{(1-\gamma)\xi}+1\right)$

We complete the proof. ∎

######  Lemma E.3.

For any $i\in\\{1,...,N\\}$, we have

$\displaystyle{\mathbb{E}}E^{\nu^{*}}(c_{i},\theta^{(t)},\hat{w}_{c_{i}}^{(t)})$
$\displaystyle\leq\frac{1}{1-\gamma}\left\|\frac{\nu^{*}}{\nu_{0}}\right\|_{\infty}\left(\epsilon_{bias}+\frac{2\left(2\sqrt{d}WL_{\pi}+\frac{2\sqrt{d}}{1-\gamma}+WL_{\pi}\right)^{2}}{K}\right),$
$\displaystyle{\mathbb{E}}E^{\nu^{*}}(r,\theta^{(t)},\hat{w}_{r}^{(t)}(i))$
$\displaystyle\leq\frac{1}{1-\gamma}\left\|\frac{\nu^{*}}{\nu_{0}}\right\|_{\infty}\left(\epsilon_{bias}+\frac{2\left(2\sqrt{d}WL_{\pi}+\frac{2\sqrt{d}}{1-\gamma}+WL_{\pi}\right)^{2}}{K}\right),$

where $\nu_{0}$ is the uniform distribution on
${\mathcal{S}}\times{\mathcal{A}}$.

###### Proof.

Here we show

${\mathbb{E}}E^{\nu^{*}}(c_{1},\theta^{(t)},\hat{w}_{c_{1}}^{(t)})\leq\frac{1}{1-\gamma}\left\|\frac{\nu^{*}}{\nu_{0}}\right\|_{\infty}\left(\epsilon_{bias}+\frac{2\left(2\sqrt{d}WL_{\pi}+\frac{2\sqrt{d}}{1-\gamma}+WL_{\pi}\right)^{2}}{K}\right),$

and the full conclusion can be obtained via similar arguments. First we have:

$\displaystyle{\mathbb{E}}\left[E^{\nu^{*}}(c_{1},\theta^{(t)},\hat{w}_{c_{1}}^{(t)})\right]$
$\displaystyle={\mathbb{E}}\left[E^{\nu^{*}}(c_{1},\theta^{(t)},\hat{w}_{c_{1}}^{(t)})\right]$
$\displaystyle\leq{\mathbb{E}}\left[\left\|\frac{\nu^{*}}{\nu^{(t)}}\right\|_{\infty}E^{\nu^{(t)}}(c_{1},\theta^{(t)},\hat{w}_{c_{1}}^{(t)})\right]$
$\displaystyle\leq\frac{1}{1-\gamma}{\mathbb{E}}\left[\left\|\frac{\nu^{*}}{\nu_{0}}\right\|_{\infty}E^{\nu^{(t)}}(c_{1},\theta^{(t)},\hat{w}_{c_{1}}^{(t)})\right]$
$\displaystyle=\frac{1}{1-\gamma}\left\|\frac{\nu^{*}}{\nu_{0}}\right\|_{\infty}\left({\mathbb{E}}\min_{w}E^{\nu^{(t)}}(c_{1},\theta^{(t)},w)+{\mathbb{E}}\left[E^{\nu^{(t)}}\left(c_{1},\theta^{(t)},\hat{w}^{(t)}_{c_{1}}\right)-\min_{w}E^{\nu^{(t)}}(c_{1},\theta^{(t)},w)\right]\right)$
$\displaystyle\leq\frac{1}{1-\gamma}\left\|\frac{\nu^{*}}{\nu_{0}}\right\|_{\infty}\left(\epsilon_{bias}+{\mathbb{E}}\left[E^{\nu^{(t)}}\left(c_{1},\theta^{(t)},\hat{w}^{(t)}_{c_{1}}\right)-\min_{w}E^{\nu^{(t)}}(c_{1},\theta^{(t)},w)\right]\right).$

Set $\alpha=\frac{1}{4L_{\pi}^{2}}$, by Theorem 1 in Bach and Moulines [2013]
we may get:

${\mathbb{E}}\left[E^{\nu^{(t)}}\left(c_{1},\theta^{(t)},\hat{w}^{(t)}_{c_{1}}\right)-\min_{w}E^{\nu^{(t)}}(c_{1},\theta^{(t)},w)\right]\leq\frac{2(\sigma\sqrt{d}+L_{\pi}W)^{2}}{K}.$

$\sigma$ is defined as:

${\mathbb{E}}_{(s,a)\sim\nu^{(t)}}\left[G_{c_{1}}^{(t)}\left(G_{c_{1}}^{(t)}\right)^{\top}\right]\preceq\sigma^{2}F(\theta^{(t)}),$

where
$G_{c_{1}}^{(t)}:=2\left(\left(w_{c_{1}}^{*}\right)^{\top}\nabla_{\theta}\log\pi^{(t)}(a\mid
s)-\widehat{A}_{c_{1}}^{(t)}(s,a)\right)\nabla_{\theta}\log\pi^{(t)}(a\mid s)$
and
$w_{c_{1}}^{*}:=\underset{w}{\mathrm{argmin}}E^{\nu^{(t)}}(c_{i},\theta^{(t)},w).$
We have $\sigma\leq 2WL_{\pi}+\frac{2}{1-\gamma}$. The proof is completed. ∎

######  Lemma E.4.

For $\forall i\in\\{1,...,N\\}$,

${\mathbb{E}}\left[\sum_{t=0}^{T-1}\left(d_{i}-\widehat{V}_{c_{i}}^{(t)_{i}}(\rho)\right)^{2}\right]\leq\frac{3T}{(1-\gamma)^{2}}.$

###### Proof.

Note that:

$\displaystyle{\mathbb{E}}\left[\sum_{t=0}^{T-1}\left(d_{i}-\widehat{V}_{c_{i}}^{(t)_{i}}(\rho)\right)^{2}\right]$
$\displaystyle=\sum_{t=0}^{T-1}d_{i}^{2}-2\sum_{t=0}^{T-1}d_{i}{\mathbb{E}}\widehat{V}_{c_{i}}^{(t)_{i}}(\rho)+\sum_{t=0}^{T-1}{\mathbb{E}}\left[\widehat{V}_{c_{i}}^{(t)_{i}}(\rho)\right]^{2}$
$\displaystyle\leq\frac{T}{(1-\gamma)^{2}}+\sum_{t=0}^{T-1}{\mathbb{E}}\left[\widehat{V}_{c_{i}}^{(t)_{i}}(\rho)\right]^{2}.$

Then it suffices to bound
${\mathbb{E}}\left[\widehat{V}_{c_{i}}^{(t)_{i}}(\rho)\right]^{2}$. Since

$\displaystyle{\mathbb{E}}\left[\widehat{V}_{c_{i}}^{(t)_{i}}(\rho)\right]^{2}$
$\displaystyle=\operatorname{Var}\left[\widehat{V}_{c_{i}}^{(t)_{i}}(\rho)\right]+\left[{\mathbb{E}}\widehat{V}_{c_{i}}^{(t)_{i}}(\rho)\right]^{2}$
$\displaystyle=\frac{1}{K}\operatorname{Var}\left[\widehat{V}_{c_{i}}^{(t)_{i}}(s)\right]+\left[{\mathbb{E}}\widehat{V}_{c_{i}}^{(t)_{i}}(\rho)\right]^{2}$
$\displaystyle=\frac{1}{K}{\mathbb{E}}\left[\widehat{V}_{c_{i}}^{(t)_{i}}(s)-{V}_{c_{i}}^{(t)_{i}}(s)\right]^{2}+\left[{\mathbb{E}}\widehat{V}_{c_{i}}^{(t)_{i}}(\rho)\right]^{2}$
$\displaystyle=\frac{1}{K}{\mathbb{E}}_{K^{\prime}}{\mathbb{E}}\left[\left(\sum_{k=1}^{K^{\prime}}c_{i}(s_{k},a_{k})-{V}_{c_{i}}^{(t)_{i}}(s)\right)^{2}\Bigg{|}K^{\prime}\right]+\left[{\mathbb{E}}\widehat{V}_{c_{i}}^{(t)_{i}}(\rho)\right]^{2}$
$\displaystyle\leq\frac{1}{K}{\mathbb{E}}[K^{\prime}]^{2}+\left[{\mathbb{E}}\widehat{V}_{c_{i}}^{(t)_{i}}(\rho)\right]^{2}$
$\displaystyle\leq\frac{1+K}{K(1-\gamma)^{2}}$
$\displaystyle\leq\frac{2}{(1-\gamma)^{2}}$

we complete the proof. ∎

######  Lemma E.5.

We have

${\mathbb{E}}\left[\frac{1}{T}\sum_{t=0}^{T-1}\sum_{i=1}^{N}\lambda_{i}^{(t)}\left(V_{c_{i}}^{*}(\rho)-V_{c_{i}}^{(t)_{i}}(\rho)\right)\right]\leq\frac{2N\eta_{\lambda}}{(1-\gamma)^{2}}.$

###### Proof.

Note that $\forall i\in\\{1,...,N\\}$,

$\displaystyle\left(\lambda_{i}^{(T)}\right)^{2}$
$\displaystyle=\sum_{t=0}^{T-1}\left[\left(\lambda_{i}^{(t+1)}\right)^{2}-\left(\lambda_{i}^{(t)}\right)^{2}\right]$
$\displaystyle=\sum_{t=0}^{T-1}\left[\left(\operatorname{Proj}_{\Lambda}\left(\lambda_{i}^{(t)}-\eta_{\lambda}\left(d_{i}-\widehat{V}_{c_{i}}^{(t)_{i}}(\rho)\right)\right)\right)^{2}-\left(\lambda_{i}^{(t)}\right)^{2}\right]$
$\displaystyle\leq\sum_{t=0}^{T-1}\left[\left(\lambda_{i}^{(t)}-\eta_{\lambda}\left(d_{i}-\widehat{V}_{c_{i}}^{(t)_{i}}(\rho)\right)\right)^{2}-\left(\lambda_{i}^{(t)}\right)^{2}\right]$
$\displaystyle=\sum_{t=0}^{T-1}\eta_{\lambda}^{2}\left(d_{i}-\widehat{V}_{c_{i}}^{(t)_{i}}(\rho)\right)^{2}+2\sum_{t=0}^{T-1}\eta_{\lambda}\lambda_{i}^{(t)}\left(\widehat{V}_{c_{i}}^{(t)_{i}}(\rho)-d_{i}\right)$
$\displaystyle=\sum_{t=0}^{T-1}\eta_{\lambda}^{2}\left(d_{i}-\widehat{V}_{c_{i}}^{(t)_{i}}(\rho)\right)^{2}+2\sum_{t=0}^{T-1}\eta_{\lambda}\lambda_{i}^{(t)}\left(\widehat{V}_{c_{i}}^{(t)_{i}}(\rho)-{V}_{c_{i}}^{(t)_{i}}(\rho)\right)+2\sum_{t=0}^{T-1}\eta_{\lambda}\lambda_{i}^{(t)}\left({V}_{c_{i}}^{(t)_{i}}(\rho)-d_{i}\right)$
$\displaystyle\leq\sum_{t=0}^{T-1}\eta_{\lambda}^{2}\left(d_{i}-\widehat{V}_{c_{i}}^{(t)_{i}}(\rho)\right)^{2}+2\sum_{t=0}^{T-1}\eta_{\lambda}\lambda_{i}^{(t)}\left(\widehat{V}_{c_{i}}^{(t)_{i}}(\rho)-{V}_{c_{i}}^{(t)_{i}}(\rho)\right)+2\sum_{t=0}^{T-1}\eta_{\lambda}\lambda_{i}^{(t)}\left({V}_{c_{i}}^{(t)_{i}}(\rho)-V^{*}_{c_{i}}(\rho)\right).$

The last inequality holds because of the feasibility of the optimal policy
$\pi^{*}$. We take expectations of both sides and rearrange terms:

${\mathbb{E}}\left[\sum_{t=0}^{T-1}\eta_{\lambda}\lambda_{i}^{(t)}\left(V^{*}_{c_{i}}(\rho)-{V}_{c_{i}}^{(t)_{i}}(\rho)\right)\right]\leq\frac{1}{2}{\mathbb{E}}\left[\sum_{t=0}^{T-1}\eta_{\lambda}^{2}\left(d_{i}-\widehat{V}_{c_{i}}^{(t)_{i}}(\rho)\right)^{2}\right]+{\mathbb{E}}\left[\sum_{t=0}^{T-1}\eta_{\lambda}\lambda_{i}^{(t)}\left(\widehat{V}_{c_{i}}^{(t)_{i}}(\rho)-{V}_{c_{i}}^{(t)_{i}}(\rho)\right)\right].$

First, we have
${\mathbb{E}}\left[\sum_{t=0}^{T-1}\eta_{\lambda}\lambda_{i}^{(t)}\left(\widehat{V}_{c_{i}}^{(t)_{i}}(\rho)-{V}_{c_{i}}^{(t)_{i}}(\rho)\right)\right]=0$
due to the conditional unbiasedness of $\widehat{V}_{c_{i}}^{(t)_{i}}(\rho)$.
Using Lemma E.4, we also have

${\mathbb{E}}\left[\sum_{t=0}^{T-1}\eta_{\lambda}^{2}\left(d_{i}-\widehat{V}_{c_{i}}^{(t)_{i}}(\rho)\right)^{2}\right]\leq\frac{3T\eta_{\lambda}^{2}}{(1-\gamma)^{2}}.$

Thus

$\displaystyle{\mathbb{E}}\left[\frac{1}{T}\sum_{t=0}^{T-1}\sum_{i=1}^{N}\lambda_{i}^{(t)}\left(V_{c_{i}}^{*}(\rho)-V_{c_{i}}^{(t)_{i}}(\rho)\right)\right]$
$\displaystyle\leq\frac{1}{2}{\mathbb{E}}\left[\frac{1}{T}\sum_{t=0}^{T-1}\sum_{i=1}^{N}\eta_{\lambda}\left(d_{i}-\widehat{V}_{c_{i}}^{(t)_{i}}(\rho)\right)^{2}\right]$
$\displaystyle\leq\frac{2N\eta_{\lambda}}{(1-\gamma)^{2}}.$

We complete the proof. ∎

######  Lemma E.6.

We have

$\displaystyle{\mathbb{E}}\left[\frac{1}{T}\sum_{t=0}^{T-1}(V_{r}^{*}(\rho)-V_{r}^{(t)}(\rho))\right]$
$\displaystyle\leq\frac{\log|{\mathcal{A}}|}{T(1-\gamma)\eta_{\theta}}+\frac{(2(E-1)+1/2)\beta\eta_{\theta}V^{2}(N+1)}{1-\gamma}\left(\frac{N}{(1-\gamma)^{2}\xi^{2}}+1\right)+|{\mathcal{A}}|L_{\pi}(E-1)\eta_{\theta}V\left(\frac{N}{(1-\gamma)^{3}\xi}+\frac{1}{(1-\gamma)^{2}}\right)$
$\displaystyle\quad+\left(\frac{1}{1-\gamma}+\frac{2}{(1-\gamma)^{2}\xi}\right)\sqrt{\frac{1}{1-\gamma}\left\|\frac{\nu^{*}}{\nu_{0}}\right\|_{\infty}\left(\epsilon_{bias}+\frac{2\left(2\sqrt{d}VL_{\pi}+\frac{2\sqrt{d}}{1-\gamma}+VL_{\pi}\right)^{2}}{K}\right)}.$

###### Proof.

$\displaystyle{\mathbb{E}}\left[\frac{1}{TN}\sum_{t=0}^{T-1}\sum_{i=1}^{N}(V_{r}^{*}(\rho)-V_{r}^{(t)_{i}}(\rho))\right]$
$\displaystyle\leq\frac{\log|{\mathcal{A}}|}{T(1-\gamma)\eta_{\theta}}+{\mathbb{E}}\left[\frac{1}{TN}\sum_{t=0}^{T-1}\sum_{i=1}^{N}\frac{\beta}{1-\gamma}\left\|\bar{\theta}^{(t)}-\theta_{i}^{(t)}\right\|_{2}\left\|\hat{w}_{i}^{(t)}\right\|_{2}\right]+{\mathbb{E}}\left[\frac{1}{T}\sum_{t=0}^{T-1}\sum_{i=1}^{N}\lambda_{i}^{(t)}(V_{c_{i}}^{*}(\rho)-V_{c_{i}}^{(t)_{i}}(\rho))\right]$
$\displaystyle\quad+{\mathbb{E}}\left[\frac{1}{TN(1-\gamma)}\sum_{t=0}^{T-1}\sum_{i=1}^{N}\sqrt{E^{\nu^{*}}\left(r,\theta^{(t)},\hat{w}^{(t)}_{r}(i)\right)}+\frac{1}{T(1-\gamma)}\sum_{t=0}^{T-1}\sum_{i=1}^{N}\lambda_{i}^{(t)}\sqrt{E^{\nu^{*}}\left(c_{i},\theta^{(t)},\hat{w}^{(t)}_{c_{i}}\right)}\right]$
$\displaystyle\quad+\beta\eta_{\theta}V^{2}(N+1)\left(\frac{N}{2(1-\gamma)^{3}\xi^{2}}+\frac{1}{2(1-\gamma)}\right)$
$\displaystyle\leq\frac{\log|{\mathcal{A}}|}{T(1-\gamma)\eta_{\theta}}+{\mathbb{E}}\left[\frac{1}{TN}\sum_{t=0}^{T-1}\sum_{i=1}^{N}\frac{\beta}{1-\gamma}\left\|\bar{\theta}^{(t)}-\theta_{i}^{(t)}\right\|_{2}\left\|\hat{w}_{i}^{(t)}\right\|_{2}\right]+\frac{2N\eta_{\lambda}}{(1-\gamma)^{2}}$
$\displaystyle\quad+\left(\frac{1}{1-\gamma}+\frac{2}{(1-\gamma)^{2}\xi}\right)\sqrt{\frac{1}{1-\gamma}\left\|\frac{\nu^{*}}{\nu_{0}}\right\|_{\infty}\left(\epsilon_{bias}+\frac{2\left(2\sqrt{d}VL_{\pi}+\frac{2\sqrt{d}}{1-\gamma}+VL_{\pi}\right)^{2}}{K}\right)}$
$\displaystyle\quad+\beta\eta_{\theta}V^{2}(N+1)\left(\frac{N}{2(1-\gamma)^{3}\xi^{2}}+\frac{1}{2(1-\gamma)}\right)$

The first inequality is true due to Lemma E.1 and the second inequality is
true due to Lemma E.3 and Lemma E.5. By Cauchy’s inequality and Lemma E.2 we
may get

$\displaystyle{\mathbb{E}}\left[\frac{1}{TN}\sum_{t=0}^{T-1}\sum_{i=1}^{N}\frac{\beta}{1-\gamma}\left\|\bar{\theta}^{(t)}-\theta_{i}^{(t)}\right\|_{2}\left\|\hat{w}_{i}^{(t)}\right\|_{2}\right]$
$\displaystyle\leq\frac{1}{TN}\sum_{t=0}^{T-1}\sum_{i=1}^{N}\frac{\beta}{1-\gamma}\sqrt{{\mathbb{E}}\left\|\bar{\theta}^{(t)}-\theta_{i}^{(t)}\right\|_{2}^{2}}\sqrt{{\mathbb{E}}\left\|\hat{w}_{i}^{(t)}\right\|_{2}^{2}}$
$\displaystyle\leq\frac{1}{TN}\sum_{t=0}^{T-1}\sum_{i=1}^{N}\frac{\beta}{1-\gamma}\left(2(E-1)\eta_{\theta}V^{2}(N+1)\left(\frac{N}{(1-\gamma)^{2}\xi^{2}}+1\right)\right)$
$\displaystyle=\frac{2(E-1)\beta\eta_{\theta}V^{2}(N+1)}{1-\gamma}\left(\frac{N}{(1-\gamma)^{2}\xi^{2}}+1\right)$

Thus we have

$\displaystyle{\mathbb{E}}\left[\frac{1}{TN}\sum_{t=0}^{T-1}\sum_{i=1}^{N}(V_{r}^{*}(\rho)-V_{r}^{(t)_{i}}(\rho))\right]$
$\displaystyle\leq\frac{\log|{\mathcal{A}}|}{T(1-\gamma)\eta_{\theta}}+\frac{(2(E-1)+1/2)\beta\eta_{\theta}V^{2}(N+1)}{1-\gamma}\left(\frac{N}{(1-\gamma)^{2}\xi^{2}}+1\right)$
$\displaystyle\quad+\left(\frac{1}{1-\gamma}+\frac{2}{(1-\gamma)^{2}\xi}\right)\sqrt{\frac{1}{1-\gamma}\left\|\frac{\nu^{*}}{\nu_{0}}\right\|_{\infty}\left(\epsilon_{bias}+\frac{2\left(2\sqrt{d}VL_{\pi}+\frac{2\sqrt{d}}{1-\gamma}+VL_{\pi}\right)^{2}}{K}\right)}.$

Finally, we may complete the proof by noting that by Lemma D.2 and Lemma E.2,
$\forall t\in\\{0,...,T-1\\}$, $\forall i\in\\{1,...,N\\}$

$\displaystyle{\mathbb{E}}|V_{r}^{(t)_{i}}-V_{r}^{(t)}|$
$\displaystyle\leq\frac{|{\mathcal{A}}|L_{\pi}{\mathbb{E}}\|\theta^{(t)}-\theta_{i}^{(t)}\|_{2}}{(1-\gamma)^{2}}$
$\displaystyle\leq|{\mathcal{A}}|L_{\pi}(E-1)\eta_{\theta}V\left(\frac{N}{(1-\gamma)^{3}\xi}+\frac{1}{(1-\gamma)^{2}}\right).$

Therefore,

$\displaystyle{\mathbb{E}}\left[\frac{1}{T}\sum_{t=0}^{T-1}(V_{r}^{*}(\rho)-V_{r}^{(t)}(\rho))\right]$
$\displaystyle\leq{\mathbb{E}}\left[\frac{1}{TN}\sum_{t=0}^{T-1}\sum_{i=1}^{N}(V_{r}^{*}(\rho)-V_{r}^{(t)_{i}}(\rho))\right]+{\mathbb{E}}\left[\frac{1}{T}\sum_{t=0}^{T-1}|V_{r}^{(t)}(\rho)-V_{r}^{(t)_{i}}(\rho)|\right]$
$\displaystyle\leq\frac{\log|{\mathcal{A}}|}{T(1-\gamma)\eta_{\theta}}+\frac{(2(E-1)+1/2)\beta\eta_{\theta}V^{2}(N+1)}{1-\gamma}\left(\frac{N}{(1-\gamma)^{2}\xi^{2}}+1\right)+|{\mathcal{A}}|L_{\pi}(E-1)\eta_{\theta}V\left(\frac{N}{(1-\gamma)^{3}\xi}+\frac{1}{(1-\gamma)^{2}}\right)$
$\displaystyle\quad+\left(\frac{1}{1-\gamma}+\frac{2}{(1-\gamma)^{2}\xi}\right)\sqrt{\frac{1}{1-\gamma}\left\|\frac{\nu^{*}}{\nu_{0}}\right\|_{\infty}\left(\epsilon_{bias}+\frac{2\left(2\sqrt{d}VL_{\pi}+\frac{2\sqrt{d}}{1-\gamma}+VL_{\pi}\right)^{2}}{K}\right)}.$

∎

######  Lemma E.7.

$\displaystyle\sum_{i=1}^{N}{\mathbb{E}}\left[\frac{1}{T}\sum_{t=0}^{T-1}V_{c_{i}}^{(t)}(\rho)-d_{i}\right]_{+}$
$\displaystyle\leq(1-\gamma)\xi\Bigg{\\{}\frac{\log|{\mathcal{A}}|}{T(1-\gamma)\eta_{\theta}}+\frac{(2(E-1)+1/2)\beta\eta_{\theta}V^{2}(N+1)}{1-\gamma}\left(\frac{N}{(1-\gamma)^{2}\xi^{2}}+1\right)+\frac{2N}{T\eta_{\lambda}(1-\gamma)^{2}\xi^{2}}+\frac{2N\eta_{\lambda}}{(1-\gamma)^{2}}$
$\displaystyle\quad+\left(\frac{1}{1-\gamma}+\frac{2}{(1-\gamma)^{2}\xi}\right)\sqrt{\frac{1}{1-\gamma}\left\|\frac{\nu^{*}}{\nu_{0}}\right\|_{\infty}\left(\epsilon_{bias}+\frac{2\left(2\sqrt{d}VL_{\pi}+\frac{2\sqrt{d}}{1-\gamma}+VL_{\pi}\right)^{2}}{K}\right)}$
$\displaystyle\quad+\frac{|{\mathcal{A}}|L_{\pi}(E-1)\eta_{\theta}V}{(1-\gamma)^{2}}\left(\frac{N}{(1-\gamma)\xi}+1\right)^{2}\Bigg{\\}}.$

###### Proof.

For any $\lambda=(\lambda_{1},...,\lambda_{N})\in\Lambda^{N}$,

$\displaystyle{\mathbb{E}}\left[\frac{1}{TN}\sum_{t=0}^{T-1}\sum_{i=1}^{N}(V_{r}^{*}(\rho)-V_{r}^{(t)_{i}}(\rho))\right]+{\mathbb{E}}\left[\frac{1}{T}\sum_{t=0}^{T-1}\sum_{i=1}^{N}\lambda_{i}(V_{c_{i}}^{(t)_{i}}(\rho)-d_{i})\right]$
$\displaystyle\leq\frac{\log|{\mathcal{A}}|}{T(1-\gamma)\eta_{\theta}}+\frac{(2(E-1)+1/2)\beta\eta_{\theta}V^{2}(N+1)}{1-\gamma}\left(\frac{N}{(1-\gamma)^{2}\xi^{2}}+1\right)+\frac{\sum_{i=1}^{N}\lambda_{i}^{2}}{2T\eta_{\lambda}}+\frac{2N\eta_{\lambda}}{(1-\gamma)^{2}}$
$\displaystyle\quad+\left(\frac{1}{1-\gamma}+\frac{2}{(1-\gamma)^{2}\xi}\right)\sqrt{\frac{1}{1-\gamma}\left\|\frac{\nu^{*}}{\nu_{0}}\right\|_{\infty}\left(\epsilon_{bias}+\frac{2\left(2\sqrt{d}VL_{\pi}+\frac{2\sqrt{d}}{1-\gamma}+VL_{\pi}\right)^{2}}{K}\right)}.$

By Lemma D.2 and Lemma E.2, we have

$\displaystyle{\mathbb{E}}|V_{\diamond}^{(t)_{i}}-V_{\diamond}^{(t)}|$
$\displaystyle\leq\frac{|{\mathcal{A}}|L_{\pi}{\mathbb{E}}\|\theta^{(t)}-\theta_{i}^{(t)}\|_{2}}{(1-\gamma)^{2}}$
$\displaystyle\leq|{\mathcal{A}}|L_{\pi}(E-1)\eta_{\theta}V\left(\frac{N}{(1-\gamma)^{3}\xi}+\frac{1}{(1-\gamma)^{2}}\right).$

Thus

$\displaystyle{\mathbb{E}}\left[\frac{1}{T}\sum_{t=0}^{T-1}(V_{r}^{*}(\rho)-V_{r}^{(t)}(\rho))\right]+{\mathbb{E}}\left[\frac{1}{T}\sum_{t=0}^{T-1}\sum_{i=1}^{N}\lambda_{i}(V_{c_{i}}^{(t)}(\rho)-d_{i})\right]$
$\displaystyle\leq{\mathbb{E}}\left[\frac{1}{TN}\sum_{t=0}^{T-1}\sum_{i=1}^{N}(V_{r}^{*}(\rho)-V_{r}^{(t)_{i}}(\rho))\right]+{\mathbb{E}}\left[\frac{1}{TN}\sum_{t=0}^{T-1}\sum_{i=1}^{N}|V_{r}^{(t)}(\rho)-V_{r}^{(t)_{i}}(\rho)|\right]$
$\displaystyle\quad+{\mathbb{E}}\left[\frac{1}{T}\sum_{t=0}^{T-1}\sum_{i=1}^{N}\lambda_{i}(V_{c_{i}}^{(t)_{i}}(\rho)-d_{i})\right]+{\mathbb{E}}\left[\frac{1}{T}\sum_{t=0}^{T-1}\sum_{i=1}^{N}\lambda_{i}|V_{c_{i}}^{(t)_{i}}(\rho)-V_{c_{i}}^{(t)}(\rho)|\right]$
$\displaystyle\leq\frac{\log|{\mathcal{A}}|}{T(1-\gamma)\eta_{\theta}}+\frac{(2(E-1)+1/2)\beta\eta_{\theta}V^{2}(N+1)}{1-\gamma}\left(\frac{N}{(1-\gamma)^{2}\xi^{2}}+1\right)+\frac{\sum_{i=1}^{N}\lambda_{i}^{2}}{2T\eta_{\lambda}}+\frac{2N\eta_{\lambda}}{(1-\gamma)^{2}}$
$\displaystyle\quad+\left(\frac{1}{1-\gamma}+\frac{2}{(1-\gamma)^{2}\xi}\right)\sqrt{\frac{1}{1-\gamma}\left\|\frac{\nu^{*}}{\nu_{0}}\right\|_{\infty}\left(\epsilon_{bias}+\frac{2\left(2\sqrt{d}VL_{\pi}+\frac{2\sqrt{d}}{1-\gamma}+VL_{\pi}\right)^{2}}{K}\right)}$
$\displaystyle\quad+\left(1+\sum_{i=1}^{N}\lambda_{i}\right)|{\mathcal{A}}|L_{\pi}(E-1)\eta_{\theta}V\left(\frac{N}{(1-\gamma)^{3}\xi}+\frac{1}{(1-\gamma)^{2}}\right).$

We take $\lambda_{i}=0$ if
$\frac{1}{T}\sum_{t=0}^{T-1}V_{c_{i}}^{(t)_{i}}(\rho)\leq d_{i}$ and
$\lambda_{i}=\frac{2}{(1-\gamma)\xi}$ otherwise. Then we obtain

$\displaystyle{\mathbb{E}}\left[\frac{1}{T}\sum_{t=0}^{T-1}(V_{r}^{*}(\rho)-V_{r}^{(t)}(\rho))\right]+\frac{2}{(1-\gamma)\xi}\sum_{i=1}^{N}{\mathbb{E}}\left[\frac{1}{T}\sum_{t=0}^{T-1}V_{c_{i}}^{(t)}(\rho)-d_{i}\right]_{+}$
$\displaystyle\leq\frac{\log|{\mathcal{A}}|}{T(1-\gamma)\eta_{\theta}}+\frac{(2(E-1)+1/2)\beta\eta_{\theta}V^{2}(N+1)}{1-\gamma}\left(\frac{N}{(1-\gamma)^{2}\xi^{2}}+1\right)+\frac{2N}{T\eta_{\lambda}(1-\gamma)^{2}\xi^{2}}+\frac{2N\eta_{\lambda}}{(1-\gamma)^{2}}$
$\displaystyle\quad+\left(\frac{1}{1-\gamma}+\frac{2}{(1-\gamma)^{2}\xi}\right)\sqrt{\frac{1}{1-\gamma}\left\|\frac{\nu^{*}}{\nu_{0}}\right\|_{\infty}\left(\epsilon_{bias}+\frac{2\left(2\sqrt{d}VL_{\pi}+\frac{2\sqrt{d}}{1-\gamma}+VL_{\pi}\right)^{2}}{K}\right)}$
$\displaystyle\quad+\frac{|{\mathcal{A}}|L_{\pi}(E-1)\eta_{\theta}V}{(1-\gamma)^{2}}\left(\frac{N}{(1-\gamma)\xi}+1\right)^{2}.$

Noting that there always exits a policy $\pi^{\prime}$ such that
$V_{\diamond}^{\pi^{\prime}}(\rho)=\frac{1}{T}\sum_{t=0}^{T-1}V_{\diamond}^{(t)}(\rho)$:

$\displaystyle{\mathbb{E}}\left[(V_{r}^{*}(\rho)-V_{r}^{\pi^{\prime}}(\rho))\right]+\frac{2}{(1-\gamma)\xi}\sum_{i=1}^{N}{\mathbb{E}}\left[V_{c_{i}}^{\pi^{\prime}}(\rho)-d_{i}\right]_{+}$
$\displaystyle\leq\frac{\log|{\mathcal{A}}|}{T(1-\gamma)\eta_{\theta}}+\frac{(2(E-1)+1/2)\beta\eta_{\theta}V^{2}(N+1)}{1-\gamma}\left(\frac{N}{(1-\gamma)^{2}\xi^{2}}+1\right)+\frac{2N}{T\eta_{\lambda}(1-\gamma)^{2}\xi^{2}}+\frac{2N\eta_{\lambda}}{(1-\gamma)^{2}}$
$\displaystyle\quad+\left(\frac{1}{1-\gamma}+\frac{2}{(1-\gamma)^{2}\xi}\right)\sqrt{\frac{1}{1-\gamma}\left\|\frac{\nu^{*}}{\nu_{0}}\right\|_{\infty}\left(\epsilon_{bias}+\frac{2\left(2\sqrt{d}VL_{\pi}+\frac{2\sqrt{d}}{1-\gamma}+VL_{\pi}\right)^{2}}{K}\right)}$
$\displaystyle\quad+\frac{|{\mathcal{A}}|L_{\pi}(E-1)\eta_{\theta}V}{(1-\gamma)^{2}}\left(\frac{N}{(1-\gamma)\xi}+1\right)^{2}.$

Now we apply Lemma D.4 to get the conclusion:

$\displaystyle\sum_{i=1}^{N}{\mathbb{E}}\left[\frac{1}{T}\sum_{t=0}^{T-1}V_{c_{i}}^{(t)}(\rho)-d_{i}\right]_{+}=\sum_{i=1}^{N}{\mathbb{E}}\left[V_{c_{i}}^{\pi^{\prime}}(\rho)-d_{i}\right]_{+}$
$\displaystyle\leq(1-\gamma)\xi\Bigg{\\{}\frac{\log|{\mathcal{A}}|}{T(1-\gamma)\eta_{\theta}}+\frac{(2(E-1)+1/2)\beta\eta_{\theta}V^{2}(N+1)}{1-\gamma}\left(\frac{N}{(1-\gamma)^{2}\xi^{2}}+1\right)+\frac{2N}{T\eta_{\lambda}(1-\gamma)^{2}\xi^{2}}+\frac{2N\eta_{\lambda}}{(1-\gamma)^{2}}$
$\displaystyle\quad+\left(\frac{1}{1-\gamma}+\frac{2}{(1-\gamma)^{2}\xi}\right)\sqrt{\frac{1}{1-\gamma}\left\|\frac{\nu^{*}}{\nu_{0}}\right\|_{\infty}\left(\epsilon_{bias}+\frac{2\left(2\sqrt{d}VL_{\pi}+\frac{2\sqrt{d}}{1-\gamma}+VL_{\pi}\right)^{2}}{K}\right)}$
$\displaystyle\quad+\frac{|{\mathcal{A}}|L_{\pi}(E-1)\eta_{\theta}V}{(1-\gamma)^{2}}\left(\frac{N}{(1-\gamma)\xi}+1\right)^{2}\Bigg{\\}}.$

∎

###### Proof of Theorem 4.1.

Theorem 4.1 is a direct consequence of the combination of Lemma E.6 and Lemma
E.7. ∎