# Constrained Reinforcement Learning Under Model Mismatch

Zhongchang Sun  Sihong He  Fei Miao  Shaofeng Zou

###### Abstract

Existing studies on constrained reinforcement learning (RL) may obtain a well-
performing policy in the training environment. However, when deployed in a
real environment, it may easily violate constraints that were originally
satisfied during training because there might be model mismatch between the
training and real environments. To address the above challenge, we formulate
the problem as constrained RL under model uncertainty, where the goal is to
learn a good policy that optimizes the reward and at the same time satisfy the
constraint under model mismatch. We develop a Robust Constrained Policy
Optimization (RCPO) algorithm, which is the first algorithm that applies to
large/continuous state space and has theoretical guarantees on worst-case
reward improvement and constraint violation at each iteration during the
training. We demonstrate the effectiveness of our algorithm on a set of RL
tasks with constraints.

Machine Learning, ICML

##  1 Introduction

In reinforcement learning (RL), the agent aims to learn a policy that
maximizes the expected cumulative reward by interacting with an environment
(Sutton & Barto, 2018). However, in real-life applications, e.g., robotics
(Levine et al., 2016; Ono et al., 2015), health care (Yu et al., 2019a),
autonomous driving (Kiran et al., 2020; Fisac et al., 2018) and industry
automation (Gasparik et al., 2018), where it is crucial to meet various
constraints while maximizing reward, application of RL still remains limited.
For example, an unmanned aerial vehicle (UAV) performing post-disaster search
and rescue needs to return and charge before running out of battery, and
communication system needs to maximize throughput while adhering to power
consumption and latency constraints.

The framework of constrained Markov Decision Process (CMDP) was developed
(Altman, 1999) to tackle the above challenge and the goal is to search for one
policy that maximizes the overall reward among the policies that satisfy the
constraint, and an optimal policy for CMDP can be found via linear
programming.

When a well-performing policy trained using a simulator is deployed in a real
environment, it may easily violate constraints that were originally satisfied
during training because there might be model mismatch between the training and
real environments. This could be due to environment non-stationarity, sim-to-
real gap and adversarial attacks. Despite its practical importance, studies on
the problem of robust RL under constraints are rather limited in the
literature. Several attempts were made in (Russel et al., 2020; Mankowitz et
al., 2020), where two heuristic approaches were proposed. Their basic idea is
to first evaluate the worst-case performance of the policy over the
uncertainty set, and then use that together with classical policy improvement
methods, e.g., policy gradient, to update the policy. However, there is no
guarantee to obtain an improved robust policy by doing so. A robust primal-
dual approach was developed in (Wang et al., 2022), which however cannot
guarantee monotonic robust reward improvement or constraint satisfaction
during the training. Also, the results in (Wang et al., 2022) are limited to
the tabular case with finite state and action spaces.

In this paper, we study the problem of constrained RL under model mismatch.
Specifically, we consider an uncertainty set of transition kernels that
characterizes the potential model mismatch (see (Siddique et al., 2019) for an
example of uncertainty set construction). The goal is to guarantee that for
any MDP in the uncertainty set, the constraint is always satisfied. Among
these policies, we aim to identify one that maximizes the worst-case
accumulated reward over the uncertainty set. Solution to the above problem is
robust in that for any MDP in the uncertainty set, the constraint is always
satisfied, and at the same time, the overall reward of the obtained policy is
also robust to model mismatch.

We develop a robust constrained policy optimization (RCPO) algorithm, and
theoretically bound the constraint violation for any transition kernel in the
uncertainty set , and the worst-case reward improvement over the uncertainty
set for every policy during training. One thing to highlight is that our
algorithm applies to Markov Decision Processes (MDPs) with continuous state
space, which allows applications to large scale practical problems.

One essential theoretical result that drives our RCPO algorithm development is
a generalization of the performance difference lemma (Kakade & Langford, 2002;
Achiam et al., 2017) to robust MDPs. Specifically, we consider the robust
value function, which measures the worst-case performance of a policy over the
uncertainty set. We bound the difference between robust value functions for
two different policies using the difference between the two policies.

Our algorithm consists of two steps for each update: (i) robust policy
improvement step and (ii) projection.

Step (i) uses our robust performance difference lemma to develop a local
approximation of the robust value function, and design a robust policy
improvement step that searches in the neighborhood of the current policy. This
step generalizes the trust region method (Schulman et al., 2015a) to the
robust setting and guarantees robust reward improvement. Unlike the non-robust
setting where there is only one transition kernel which stays the same
throughout the training, under model uncertainty the worst-case transition
kernel changes with the policy and is different for reward and utility (see
Section 3.2). One challenge is that the local approximation implicitly depends
on the policy to be optimized, which is in the neighborhood of the current
policy, through its worst-case transition kernel, making the optimization
intractable. We develop a novel approximation using the current policy as a
surrogate, and prove that such an approximation still provides guaranteed
robust reward improvement (and later in step (ii) robust constraint
satisfaction).

The obtained policy guarantees the reward improvement, but may violate the
constraint due to bad initialization and stochastic noise. This leads to a
potential problem of the constrained policy optimization (CPO) approach in
(Achiam et al., 2017) that there may not exist any feasible solution during
the updates (as pointed out in (Yang et al., 2019)). To address this
challenge, in step (ii) we further project the obtained policy so that it
satisfies the constraint for any transition kernel in the uncertainty set.

One of the key challenges in the analysis lies in that the worst-case
transition kernel changes when the policy updates. We address this challenge
by leveraging our robust performance difference lemma and a novel integration
of the Lipchitz property of robust value function and the change of measure
technique.

##  2 Related Work

Constrained RL. The CMDPs (Altman, 1999) have been an active field of
research. The primal-dual method is one of the most commonly used method
(Altman, 1999; Auer et al., 2008; Liang et al., 2018; Paternain et al., 2019;
Tessler et al., 2018; Yu et al., 2019b; Stooke et al., 2020; Efroni et al.,
2020; Zheng & Ratliff, 2020; Zhang et al., 2020), which converts the
constrained optimization problem to an unconstrained Lagrangian formulation
and alternatively updates the primal and dual variables. Thanks to the strong
duality of the non-robust CMDPs (Paternain et al., 2019), the problem can be
solved exactly in the dual domain and the primal-dual method is guaranteed to
converge to the optimal solution (Ding et al., 2020, 2021; Li et al., 2021;
Liu et al., 2021; Ying et al., 2021; Wei et al., 2022). Another widely studied
method is the primal method (Chow et al., 2018; Dalal et al., 2018; Liu et
al., 2020; Xu et al., 2021; Bura et al., 2022), which takes all the updates in
the primal domain without formulating the Lagrangian function. The trust
region-based methods have also been proposed to solve the non-robust CMDPs
(Achiam et al., 2017; Yang et al., 2019; Kim et al., 2023), which guarantee
the reward improvement and constraint satisfaction during the training. Under
model mismatch, the worst-case transition kernel is different as the policy
updates, and therefore these approaches may not be applied, and the obtained
policy may easily violate the constraint when there is a model mismatch.

Robust RL. Robust RL was firstly introduced in (Iyengar, 2005; Nilim & El
Ghaoui, 2004) where the goal is to optimize the worst-case performance over
the uncertainty set of transition kernels. Algorithms with convergence
guarantee have been proposed for both the model-based robust RL with known
uncertainty set (Iyengar, 2005; Nilim & El Ghaoui, 2004; Xu & Mannor, 2010;
Lim & Autef, 2019; Wang et al., 2023a, b) and the model-free robust RL with
unknown uncertainty set (Roy et al., 2017; Zhou et al., 2021; Panaganti &
Kalathil, 2021; Yang et al., 2021; Wang & Zou, 2022; Wang et al., 2023c; Wang
& Zou, 2021; Wang et al., 2022). Compared with the unconstrained robust RL,
the robust constrained RL is more challenging since we also need to guarantee
the constraint is satisfied for any transition kernel in the uncertainty set.
Directly applying algorithms designed for unconstrained robust RL to robust
constrained RL will lead to constraint-violating policies.

Constrained RL under Model Uncertainty. Unlike the non-robust CMDPs, there are
rather limited works on constrained RL under model uncertainty. In (Russel et
al., 2020), a heuristic approach is proposed. The basic idea is that they
first estimate the robust value function, and then update the policy using the
non-robust policy gradient (Sutton et al., 1999). Since the worst-case
transition kernel is also a function of the policy, the non-robust policy
gradient may not update the policy along the direction of the real gradient.
Therefore, it cannot guarantee the performance improvement for each update,
and thus the convergence of this heuristic approach may not hold. In
(Mankowitz et al., 2020), the robust value function estimate is first
performed and a non-robust continuous control algorithm is applied to update
the policy. Similar to (Russel et al., 2020), the non-robust policy
improvement cannot guarantee the convergence of the algorithm. In (Wang et
al., 2022), a robust primal-dual algorithm (RPD) is proposed where the primal
and dual variables are updated alternatively, and the robust policy gradient
is employed to update the policy. However, the strong duality may not hold
when there is model mismatch. Secondly, the constraint may be violated during
the training, which is attributed to the nature of the primal-dual approach.
In contrast, the update of our algorithm is performed in the primal domain,
and we provide performance guarantee on the robust reward improvement and
robust constraint violation for each update. Our RCPO ensures constraint
satisfaction throughout the training, which is critical for many practical
applications.

##  3 Preliminaries and Problem Formulation

###  3.1 Constrained MDP

A constrained Markov Decision Process (CMDP) (Altman, 1999) is defined by a
tuple $(\mathcal{S},\mathcal{A},p,r,c)$, where $\mathcal{S}$ is the state
space, $\mathcal{A}$ is the action space,
$p=\\{p^{a}_{s}\in\Delta(\mathcal{S}),s\in\mathcal{S},a\in\mathcal{A}\\}$111$\Delta(\mathcal{S})$
denotes the probability simplex defined on $\mathcal{S}$. is the transition
kernel of the CMDP, $r:\mathcal{S}\times\mathcal{A}\rightarrow[0,1]$ is the
reward function, and $c:\mathcal{S}\times\mathcal{A}\rightarrow[0,1]$ is the
utility function. A stationary policy
$\pi:\mathcal{S}\rightarrow\Delta(\mathcal{A})$ is defined as the probability
distribution of choosing actions in $\mathcal{A}$ at the current state $s$.
After choosing action $a$ at state $s$, the system transits to the next state
$s^{\prime}$ based on the transition kernel $p^{a}_{s}$. At the same time, the
agent receives a reward $r(s,a)$ and a utility $c(s,a)$. For the sake of
simplicity in presentation, we consider the case with one constraint, and the
results in this paper can be extended to the case with multiple constraints.

Starting from an initial state $s$, the reward value function of a policy
$\pi$ is defined as

$\displaystyle
V_{r,p}^{\pi}(s)\triangleq\mathbb{E}_{p}\left[\sum_{t=0}^{\infty}\gamma^{t}r(s_{t},a_{t})|s_{0}=s,\pi\right],$

where $\mathbb{E}_{p}$ denotes the expectation with respect to the transition
kernel $p$ and $\gamma$ is the discount factor. The reward action value
function is defined as

$\displaystyle
Q_{r,p}^{\pi}(s,a)\triangleq\mathbb{E}_{p}\left[\sum_{t=0}^{\infty}\gamma^{t}r(s_{t},a_{t})|s_{0}=s,a_{0}=a,\pi\right].$

Similarly, the utility value function and the utility action value function
are defined as

$\displaystyle
V_{c,p}^{\pi}(s)\triangleq\mathbb{E}_{p}\left[\sum_{t=0}^{\infty}\gamma^{t}c(s_{t},a_{t})|s_{0}=s,\pi\right]$
$\displaystyle
Q_{c,p}^{\pi}(s,a)\triangleq\mathbb{E}_{p}\left[\sum_{t=0}^{\infty}\gamma^{t}c(s_{t},a_{t})|s_{0}=s,a_{0}=a,\pi\right].$

Let $V_{r,p}^{\pi}(\rho)=\mathbb{E}_{s\sim\rho}[V_{r,p}^{\pi}(s)]$ and
$V_{c,p}^{\pi}(\rho)=\mathbb{E}_{s\sim\rho}[V_{c,p}^{\pi}(s)]$ be the
discounted accumulative reward function and the discounted accumulative
utility function, respectively, when the initial state $s$ follows
distribution $\rho$. Let $d^{\pi}_{p}(s)$ denote the state occupancy measure
when the initial state $s$ follows distribution $\rho$:

$\displaystyle
d^{\pi}_{p}(s)=(1-\gamma)\sum_{t=0}^{\infty}\gamma^{t}\mathbb{P}(s_{t}=s|s_{0}\sim\rho,\pi,p).$

The goal of the CMDP is to learn a policy $\pi$ that maximizes the cumulative
discounted reward $V_{r,p}^{\pi}(\rho)$ subject to the constraint on the
cumulative discounted utility $V_{c,p}^{\pi}(\rho)$, i.e.,

$\displaystyle\max_{\pi}V_{r,p}^{\pi}(\rho)\ \text{s.t.}\
V_{c,p}^{\pi}(\rho)\geq d,$

where $d$ is some positive threshold for the constraint.

###  3.2 Robust MDP

The robust MDP is defined as $(\mathcal{S},\mathcal{A},\mathcal{P},r)$, where
$\mathcal{P}$ is the uncertainty set of transition kernels that measures the
model uncertainty. In this paper, we consider the uncertainty set with
$(s,a)$-rectangularity (Nilim & El Ghaoui, 2004; Iyengar, 2005). Specifically,
the uncertainty set is defined as
$\mathcal{P}=\bigotimes_{s,a}\mathcal{P}_{s}^{a}$, where
$\mathcal{P}_{s}^{a}\subseteq\Delta(\mathcal{S})$ are independent over
different state-action pairs. The robust value function is defined as

$\displaystyle
V_{r}^{\pi}(s)\triangleq\min_{p\in\mathcal{P}}\mathbb{E}_{p}\Big{[}\sum_{t=0}^{\infty}\gamma^{t}r(s_{t},a_{t})|s_{0}=s,\pi\Big{]}.$
(1)

Similarly, the robust action value function is defined as

$\displaystyle
Q_{r}^{\pi}(s,a)\triangleq\min_{p\in\mathcal{P}}\mathbb{E}_{p}\Big{[}\sum_{t=0}^{\infty}\gamma^{t}r(s_{t},a_{t})|s_{0}=s,a_{0}=a,\pi\Big{]}.$
(2)

The transition kernel that achieves the min in (1) and (2) is referred to as
the worst-case transition kernel. Denote by $V_{r}^{\pi}(\rho)$ the robust
discounted accumulative reward function when the initial state $s$ follows the
distribution $\rho$. For robust RL, the goal is to find an optimal robust
policy $\pi^{*}$ that optimizes the worst-case performance over the
uncertainty set of transition kernels, i.e.

$\displaystyle\pi^{*}=\operatorname*{arg\,max}_{\pi}V_{r}^{\pi}(\rho).$ (3)

###  3.3 Problem Formulation

Define the constrained MDP problem under model mismatch as a tuple
$(\mathcal{S},\mathcal{A},\mathcal{P},r,c)$, where $\mathcal{P}$ is an
uncertainty set of transition kernels as defined in Section 3.2 to
characterize the potential model mismatch (see (Siddique et al., 2019) for an
example of uncertainty set construction). To guarantee that the constraint is
always satisfied even under model mismatch, we define the robust utility value
function which measures the worst-case accumulated utility over the
uncertainty set:

$\displaystyle
V_{c}^{\pi}(s)\triangleq\min_{p\in\mathcal{P}}\mathbb{E}_{p}\Big{[}\sum_{t=0}^{\infty}\gamma^{t}c(s_{t},a_{t})|s_{0}=s,\pi\Big{]}.$
(4)

We are interested in policies that for any transition kernel in the
uncertainty set, i.e., under model mismatch, the accumulative utility is still
above a prescribed threshold. Furthermore, among those policies, we would like
to find one that achieves a good accumulative reward for any transition kernel
in the uncertainty set. Formally, we aim to find a policy that maximizes the
worst-case cumulative discounted reward subject to the constraint on the
worst-case cumulative discounted utility, i.e.,

$\displaystyle\max_{\pi}V_{r}^{\pi}(\rho),\ \text{s.t.}\ V_{c}^{\pi}(\rho)\geq
d.$ (5)

The problem in (5) is referred to as robust constrained RL in this paper.

##  4 Robust Constrained Policy Optimization

In this section, we present our algorithm, the robust constrained policy
optimization (RCPO), to solve the problem in (5), and theoretically prove that
the obtained policy has an improved robust reward value function and also has
guarantees for constraint satisfaction at each iteration. Our RCPO algorithm
can be applied to large scale problems with a continuous state space. We also
generalize the performance difference lemma in (Achiam et al., 2017) to the
robust setting, and show the robust value functions of two policies can be
bounded using the divergence between them.

In this section, we first present our algorithm and its theoretical
performance analyses. In Section 5, we will provide a practical implementation
for an efficiently computation.

###  4.1 Algorithm Design

In the following, we will develop our RCPO algorithm. The basic idea is to
first find a policy to maximize the robust reward advantage function in a
neighborhood of the current policy, which generalizes the trust region policy
optimization (Schulman et al., 2015a) to the robust constrained RL problem,
and then to project the obtained policy to meet the robust constraint.

To obtain a local approximation of the robust value function, we first present
the robust performance difference lemma. Specifically, we need a bound for the
performance difference of the robust value functions between two policies. Let
$p_{\pi}^{r}$ denote the worst-case transition kernel of $\pi$ for reward such
that
$V_{r,p_{\pi}^{r}}^{\pi}(\rho)=\min_{p\in\mathcal{P}}V_{r,p}^{\pi}(\rho)$. Let
$D_{KL}(f_{0}\|f_{1})$ denote the Kullback-Leibler (KL) divergence between two
distributions $f_{0}$ and $f_{1}$. The following robust performance difference
lemma generalizes the bound for standard non-robust value functions in (27)
(Achiam et al., 2017) to the robust value functions.

######  Lemma 4.1 (Robust performance difference lemma).

For any two policies $\pi,\pi^{\prime}$, let

$\epsilon^{\pi^{\prime}}_{r,p_{\pi^{\prime}}^{r}}=\max_{s}|\mathbb{E}_{a\sim\pi^{\prime}}[A^{\pi}_{r,p_{\pi^{\prime}}^{r}}(s,a)]|.$

We have the following bound:

$\displaystyle V_{r}^{\pi^{\prime}}(\rho)-V_{r}^{\pi}(\rho)\geq$ (6)
$\displaystyle\frac{1}{1-\gamma}\mathbb{E}_{\begin{subarray}{c}s\sim
d^{\pi}_{p_{\pi^{\prime}}^{r}}\\\
a\sim\pi^{\prime}\end{subarray}}\left[A^{\pi}_{r,{p_{\pi^{\prime}}^{r}}}(s,a)-\frac{2\gamma\epsilon^{\pi^{\prime}}_{r,p_{\pi^{\prime}}^{r}}}{1-\gamma}\sqrt{\frac{1}{2}D_{KL}(\pi^{\prime}\|\pi)(s)}\right].$

It can be easily verified that the bound in (6) holds with equality when
$\pi=\pi^{\prime}$.

A first idea is to optimize the lower bound in (6) over $\pi^{\prime}$ in the
neighborhood of $\pi$, and to obtain policy $\pi^{\prime}$ with an improved
performance. However, it’s difficult to implement since the lower bound in (6)
involves the advantage function and visitation distribution under
$p_{\pi^{\prime}}^{r}$ which implicitly depends on $\pi^{\prime}$. To address
this unique challenge to the robust setting, we propose to approximate
$A^{\pi}_{r,{p_{\pi^{\prime}}^{r}}}(s,a)$ and $d^{\pi}_{p_{\pi^{\prime}}^{r}}$
by $A^{\pi}_{r,{p_{\pi}^{r}}}(s,a)$ and $d^{\pi}_{p_{\pi}^{r}}$ respectively
in the neighborhood of $\pi$. The motivation of such an approximation is that
$\pi^{\prime}$ is in the neighborhood of $\pi$, and the robust value function
is Lipschitz in the policy (as shown in (Wang et al., 2023a)). We then use

$\displaystyle\frac{1}{1-\gamma}\mathbb{E}_{\begin{subarray}{c}s\sim
d^{\pi}_{p_{\pi}^{r}}\\\
a\sim\pi^{\prime}\end{subarray}}\left[A^{\pi}_{r,{p_{\pi}^{r}}}(s,a)-\frac{2\gamma\epsilon^{\pi^{\prime}}_{r,p_{\pi^{\prime}}^{r}}}{1-\gamma}\sqrt{\frac{1}{2}D_{KL}(\pi^{\prime}\|\pi)(s)}\right]$
(7)

as an approximation of the robust performance difference
$V_{r}^{\pi^{\prime}}(\rho)-V_{r}^{\pi}(\rho)$ and further design our RCPO
algorithm based on this approximation.

As will be shown below, though (7) may not necessarily be a lower bound of
$V_{r}^{\pi^{\prime}}(\rho)-V_{r}^{\pi}(\rho)$ due to the use of the
approximation, we are still able to guarantee both the reward improvement and
the constraint violation. This actually corresponds to the additional
challenge than the non-robust standard CMDP, where there is only one
transition kernel for both policies. Here, we are interested in the robust
value function, which is essentially the value function under the worst-case
transition kernel, and two different policies induce two different worst-case
transition kernels.

Let $p_{k}^{r}$ denote the worst-case transition kernel of $\pi_{k}$ for
reward and $p_{k}^{c}$ denote the worst-case transition kernel of $\pi_{k}$
for utility. A direct generalization of the CPO algorithm in (Achiam et al.,
2017) is to optimize the policy iteratively using the following update:

$\displaystyle\pi_{k+1}$
$\displaystyle=\operatorname*{arg\,max}_{\pi}\mathbb{E}_{\begin{subarray}{c}s\sim
d^{\pi_{k}}_{p_{k}^{r}}\\\
a\sim\pi\end{subarray}}\Big{[}A^{\pi_{k}}_{r,p_{k}^{r}}(s,a)\Big{]}$ s.t.
$\displaystyle\
V_{c,p_{k}^{c}}^{\pi_{k}}(\rho)+\frac{1}{1-\gamma}\mathbb{E}_{\begin{subarray}{c}s\sim
d^{\pi_{k}}_{p_{k}^{c}}\\\
a\sim\pi\end{subarray}}\Big{[}A^{\pi_{k}}_{c,p_{k}^{c}}(s,a)\Big{]}\geq d,$
$\displaystyle\mathbb{E}_{s\sim
d^{\pi_{k}}_{p_{k}^{r}}}[D_{KL}(\pi\|\pi_{k})(s)]\leq\delta.$ (8)

Here, the first constraint in (4.1) guarantees the new policy satisfies the
robust constraint, and the second constraint in (4.1) limits the search to be
in the neighborhood of $\pi_{k}$. However, this has an issue that there may be
no feasible solution to (4.1) if the current policy $\pi_{k}$ violates the
constraint.

To address the above challenge, we design a two-step approach which performs
policy improvement followed by a projection step (Yang et al., 2019). Below,
we introduce our RCPO algorithm in details, and the pseudocode is provided in
Algorithm 1. To handle large-scale MDPs, we consider a parameterized policy
class $\Pi_{\boldsymbol{\theta}}$ with parameter $\boldsymbol{\theta}$.

Step 1: Robust Policy Improvement. At the robust policy improvement step, we
first estimate the worst-case transition kernel $p_{k}^{r}$ for the current
policy $\pi_{k}$. This can be done by a gradient-based method (Wang et al.,
2023a). We iteratively update $p_{k}^{r,t}$ using the projected gradient
descent as follows,

$\displaystyle
p_{k}^{r,t+1}=\text{Proj}_{\mathcal{P}}\big{(}p_{k}^{r,t}-\beta_{t}\nabla_{p}V_{r,p_{k}^{r,t}}^{\pi_{k}}(\rho)\big{)},$
(9)

where $\beta_{t}$ is the step size and $\text{Proj}_{\mathcal{P}}$ is the
projection operator onto set $\mathcal{P}$:
$\text{Proj}_{\mathcal{P}}(p_{s}^{a})=\arg\min_{q\in\mathcal{P}_{s}^{a}}D(p_{s}^{a},q),$
where $D$ is some distance measure between two distributions.

Consider the tabular case for an example, an accurate $p_{k}^{r}$ can be
obtained such that

$\displaystyle
V_{r,p_{k}^{r}}^{\pi_{k}}(\rho)=\min_{p\in\mathcal{P}}V_{r,p}^{\pi_{k}}(\rho),$
(10)

as shown in Theorem 4.4 in (Wang et al., 2023a). For the large/continuous
state space, to estimate the worst-case transition kernel, we parameterize the
transition kernel and perform gradient descent to learn the worst-case
transition kernel estimate. Consider the case with a large discrete state
space as an example, the transition kernel can be parameterized as follows:

$\displaystyle
p_{s,a}^{\boldsymbol{\xi}}(s^{\prime})=\frac{p^{0}_{s,a}(s^{\prime})\cdot\exp(\frac{\boldsymbol{\eta}^{\top}\boldsymbol{\phi}(s^{\prime})}{\lambda_{s,a}})}{\sum_{x}p^{0}_{s,a}(x)\exp(\frac{\boldsymbol{\eta}^{\top}\boldsymbol{\phi}(x)}{\lambda_{s,a}})},$
(11)

where $p^{0}$ is the nominal transition kernel of the uncertainty set
$\mathcal{P}$, $\boldsymbol{\phi}:\mathcal{S}\rightarrow\mathbb{R}^{m}$ is a
$m$-dimensional feature vector,
$\boldsymbol{\xi}=(\boldsymbol{\eta},\boldsymbol{\lambda})$,
$\boldsymbol{\lambda}=\\{\lambda_{s,a}>0,\forall(s,a)\in\mathcal{S}\times\mathcal{A}\\}$
and $\boldsymbol{\eta}\in\mathbb{R}^{m}$ are parameters. We then present
another example for the case with a continuous state space, where the
transition kernel can be parameterized using the Gaussian mixture model:

$\displaystyle
p_{s,a}^{\boldsymbol{\xi}}(s^{\prime})=\sum_{i=1}^{m}\phi_{i}\mathcal{N}({\mu}_{i},{\sigma}_{i}^{2}),$
(12)

where $\phi_{i}:\mathcal{S}\rightarrow[0,1]$ and $\sum_{i=1}^{m}\phi_{i}=1$,
$\mathcal{N}$ denotes the Gaussian distribution and
$\boldsymbol{\mu}=(\mu_{1},\cdots,\mu_{m}):\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}^{m},\boldsymbol{\sigma}=(\sigma_{1},\cdots,\sigma_{m}):\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}^{m}$
are the parameters. In this case, let
$\boldsymbol{\xi}=(\boldsymbol{\mu},\boldsymbol{\sigma})$.

We then evaluate the advantage function $A_{r,p^{r}_{k}}^{\pi_{k}}$ and the
visitation distribution $d^{\pi_{k}}_{p^{r}_{k}}$ by performing policy
$\pi_{k}$ under the transition kernel $p_{k}^{r}$. The intermediate policy
$\pi_{k+\frac{1}{2}}$ is updated by solving the following optimization
problem:

$\displaystyle\max_{\pi\in\Pi_{\boldsymbol{\theta}}}\quad$
$\displaystyle\mathbb{E}_{\begin{subarray}{c}s\sim d^{\pi_{k}}_{p^{r}_{k}}\\\
a\sim\pi\end{subarray}}[A_{r,p^{r}_{k}}^{\pi_{k}}(s,a)],$ s.t.
$\displaystyle\mathbb{E}_{s\sim
d^{\pi_{k}}_{p^{r}_{k}}}[D_{KL}(\pi||\pi_{k})(s)]\leq\delta.$ (13)

Note that in (4.1), $A_{r,p^{r}_{k}}^{\pi_{k}}$ and $d^{\pi_{k}}_{p^{r}_{k}}$
are estimated using the sample trajectories from the current policy $\pi_{k}$
under the transition kernel $p^{r}_{k}$, which can be easily obtained. We
optimize the advantage function over a neighborhood of the current policy
$\pi_{k}$. Therefore, the advantage function and visitation distribution under
policy $\pi_{k}$ are good local approximations for all policies in this
neighborhood. For the tabular case, in the policy improvement step, we only
need to find a policy $\pi$ that maximizes the expected value of
$A_{r,p^{r}_{k}}^{\pi_{k}}(s,a)$ with $a\sim\pi$, which is linear in $\pi$,
and satisfies the constraint on the expected $D_{KL}(\pi||\pi_{k})(s)$ under
the distribution $d^{\pi_{k}}_{p^{r}_{k}}$, which is convex in $\pi$.
Therefore, (4.1) is a convex optimization problem and can be solved
efficiently.

Step 2: Projection. By solving (4.1), we obtain a policy $\pi_{k+\frac{1}{2}}$
that maximizes the advantage function in the neighborhood of current policy
$\pi_{k}$. However, $\pi_{k+\frac{1}{2}}$ does not necessarily satisfy the
constraint. In the projection step, we project the policy
$\pi_{k+\frac{1}{2}}$ to the constraint set to obtain a constraint-satisfying
policy $\pi_{k+1}$. We first estimate the worst-case transition kernel
$p_{k}^{c}$ for the utility value function under the current policy $\pi_{k}$
using the projected gradient descent method:

$\displaystyle
p_{k}^{c,t+1}=\text{Proj}_{\mathcal{P}}\big{(}p_{k}^{c,t}-\beta_{t}\nabla_{p}V_{c,p_{k}^{c,t}}^{\pi_{k}}(\rho)\big{)}.$
(14)

For the tabular case, $p_{k}^{c}$ can be obtained such that

$\displaystyle
V_{c,p_{k}^{c}}^{\pi_{k}}(\rho)=\min_{p\in\mathcal{P}}V_{c,p}^{\pi_{k}}(\rho).$
(15)

For the large/continuous state space, we parameterize the transition kernel as
introduced in Step 1.

We then estimate $A_{c,p^{c}_{k}}^{\pi_{k}},d^{\pi_{k}}_{p_{k}^{c}}$ using
sample trajectories from $p_{k}^{c}$. The projection step is achieved by
solving

$\displaystyle\min_{\pi\in\Pi_{\boldsymbol{\theta}}}$
$\displaystyle\quad\mathbb{E}_{s\sim
d^{\pi_{k}}_{p^{r}_{k}}}[D_{KL}(\pi||\pi_{k+\frac{1}{2}})(s)]$ s.t.
$\displaystyle
V_{c,p^{c}_{k}}^{\pi_{k}}(\rho)+\mathbb{E}_{\begin{subarray}{c}s\sim
d^{\pi_{k}}_{p_{k}^{c}}\\\
a\sim\pi\end{subarray}}[A_{c,p^{c}_{k}}^{\pi_{k}}(s,a)]\geq d.$ (16)

In (4.1), the constraint $V_{c,p^{c}_{k}}^{\pi_{k}}(\rho)+\mathbb{E}_{s\sim
d^{\pi_{k}}_{p_{k}^{c}},a\sim\pi}[A_{c,p^{c}_{k}}^{\pi_{k}}(s,a)]$ is a local
approximation for $V_{c}^{\pi}(\rho)$. For the tabular case, problem in (4.1)
is a convex optimization since the advantage function and the visitation
distribution are obtained from the current policy $\pi_{k}$, and therefore,
can be solved efficiently.

Unlike solving (4.1), which might be infeasible when the current policy
$\pi_{k}$ doesn’t satisfy the constraint, our update rule consists of two
convex optimization problems (4.1) and (4.1), the feasible set of which are
much larger than (4.1).

Algorithm 1 Robust Constrained Policy Optimization

Input: step size $\delta,\\{\beta_{t}\\}_{t\geq 0}$, iteration time $K,T$,
initial policy $\pi_{0}$

for $k=0,1,\cdots,K-1$ do

Initialize $p_{k}^{r,0},p_{k}^{c,0}$

for $t=0,1,\cdots,T-1$ do

$p_{k}^{r,t+1}\leftarrow\text{Proj}_{\mathcal{P}}\big{(}p_{k}^{r,t}-\beta_{t}\nabla_{p}V_{r,p_{k}^{r,t}}^{\pi_{k}}(\rho)\big{)}$

$p_{k}^{c,t+1}\leftarrow\text{Proj}_{\mathcal{P}}\big{(}p_{k}^{c,t}-\beta_{t}\nabla_{p}V_{c,p_{k}^{c,t}}^{\pi_{k}}(\rho)\big{)}$

end for

$p_{k}^{r}\leftarrow p_{k}^{r,T}$, $p_{k}^{c}\leftarrow p_{k}^{c,T}$

Compute $A^{\pi_{k}}_{r,p^{r}_{k}}$, $A^{\pi_{k}}_{c,p^{c}_{k}}$,
$d^{\pi_{k}}_{p^{r}_{k}}$, $d^{\pi_{k}}_{p^{c}_{k}}$

Update $\pi_{k+\frac{1}{2}}$ according to (4.1)

Update $\pi_{k+1}$ according to (4.1)

end for

Output: $\pi_{K}$

###  4.2 Theoretical Results

We first make the following assumption on the worst-case transition kernel.

######  Assumption 4.2.

We are able to find transition kernels
$p_{k}^{r,\boldsymbol{\xi}},p_{k}^{c,\boldsymbol{\xi}}$ such that

$\displaystyle\big{|}V_{r,p_{k}^{r,\boldsymbol{\xi}}}^{\pi_{k}}(\rho)-V_{r,p_{k}^{r}}^{\pi_{k}}(\rho)\big{|}\leq\epsilon,$
$\displaystyle\big{|}V_{c,p_{k}^{c,\boldsymbol{\xi}}}^{\pi_{k}}(\rho)-V_{c,p_{k}^{c}}^{\pi_{k}}(\rho)\big{|}\leq\epsilon.$
(17)

This assumption can be satisfied under the tabular case using a direct
parameterization of the transition kernel or under the case with a continuous
state space if a large enough neural network is used to parameterize the
transition kernel.

In the following theorem, we provide a lower bound on the worst-case reward
improvement and an upper bound on the worst-case constraint violation for each
iteration of our RCPO algorithm in Algorithm 1.

######  Theorem 4.3.

Let
$\epsilon_{r,p_{k+1}^{r}}^{\pi_{k+1}}=\max_{s}|\mathbb{E}_{a\sim\pi_{k+1}}A^{\pi_{k}}_{r,p_{k+1}^{r}}(s,a)|$
and
$\epsilon_{c,p_{k+1}^{c}}^{\pi_{k+1}}=\max_{s}|\mathbb{E}_{a\sim\pi_{k+1}}A^{\pi_{k}}_{c,p_{k+1}^{c}}(s,a)|$.
Under 4.2, when the current policy $\pi_{k}$ satisfies the constraint in (5),
we have:

Worst-case reward improvement: $\displaystyle
V_{r}^{\pi_{k+1}}(\rho)-V_{r}^{\pi_{k}}(\rho)\geq-\frac{1}{1-\gamma}M\Big{(}2L_{\pi}+\frac{2\gamma\epsilon_{r,p_{k+1}^{r}}^{\pi_{k+1}}}{1-\gamma}\Big{)}\sqrt{\frac{\delta}{2}};$
Constraint violation: $\displaystyle V_{c}^{\pi_{k+1}}(\rho)\geq
d-\epsilon-\frac{1}{1-\gamma}M\Big{(}3L_{\pi}+\frac{2\gamma\epsilon_{c,p_{k+1}^{c}}^{\pi_{k+1}}}{1-\gamma}\Big{)}\sqrt{\frac{\delta}{2}},$

where
$M=\sup_{p,p^{\prime}\in\mathcal{P}}\|d^{\pi_{k}}_{p}/d^{\pi_{k}}_{p^{\prime}}\|_{\infty}$
is finite whenever $supp(\rho)=\mathcal{S}$ and
$L_{\pi}=\frac{\sqrt{|\mathcal{A}|}}{(1-\gamma)^{2}}$.

Theorem 4.3 shows that we could adjust $\delta$ towards improved robust reward
value function and smaller constraint violation. Moreover, for the
large/continuous state space, our RCPO only incurs an additional degradation
$\epsilon$ on constraint violation due to the worst-case transition kernel
mismatch. For the tabular case, $\epsilon$ can be arbitrarily close to zero.
On the other hand, throughout the training, the policy $\pi_{k}$ may violate
the constraint due to the random initialization or estimation errors.
Therefore, in the following, we also characterize the performance of our
algorithm when the current policy $\pi_{k}$ violates the constraint.

Let $b=d-V_{c}^{\pi_{k}}(\rho)$. The following theorem provides a lower bound
on the worst-case reward improvement and an upper bound on the worst-case
constraint violation.

######  Theorem 4.4.

Under 4.2, when the current policy $\pi_{k}$ violates the constraint in (4.1),
we have:
Worst-case reward improvement:

$\displaystyle V_{r}^{\pi_{k+1}}(\rho)-V_{r}^{\pi_{k}}(\rho)$
$\displaystyle\geq-\frac{1}{1-\gamma}M\Big{(}2L_{\pi}+\frac{2\gamma\epsilon_{r,p_{k+1}^{r}}^{\pi_{k+1}}}{1-\gamma}\Big{)}\sqrt{\frac{\delta+b^{2}\alpha_{KL}}{2}};$
(18)

Constraint violation:

$\displaystyle V_{c}^{\pi_{k+1}}(\rho)\geq
d-\epsilon-\frac{1}{1-\gamma}M\Big{(}3L_{\pi}+\frac{2\gamma\epsilon_{c,p_{k+1}^{c}}^{\pi_{k+1}}}{1-\gamma}\Big{)}$
$\displaystyle\times\sqrt{\frac{\delta+b^{2}\alpha_{KL}+bM^{\prime}\sqrt{\frac{\alpha_{KL}}{2}}}{2}},$
(19)

where
$\alpha_{KL}=\frac{1}{2\boldsymbol{h}^{\top}\boldsymbol{H}^{-1}\boldsymbol{h}}$,
$\boldsymbol{h}$ and $\boldsymbol{H}$ are defined in (5) and (21),
$M^{\prime}<\infty$ is some constant.

Theorem 4.4 characterizes the performance of our algorithm when the current
policy $\pi_{k}$ is infeasible. A small $b$, i.e., the current policy
$\pi_{k}$ only violates the constraint slightly, leads to a better robust
reward improvement and a smaller constraint violation. If the current policy
$\pi_{k}$ satisfies the constraint, i.e., $b=0$, Theorem 4.4 reduces to
Theorem 4.3. The misspecified worst-case transition kernel only incurs an
additional performance degradation $\epsilon$ on the constraint violation for
large/continuous state space. For the tabular case, $\epsilon$ can be
arbitrarily close to zero.

##  5 Practical Implementation

In this section, we provide a practical implementation of Algorithm 1 to
tackle the computational challenge.

To update the policy efficiently, for a small step size $\delta$, we
approximate the objective functions and constraints in the optimization
problems (4.1) and (4.1) using their Taylor expansions. Let

$\displaystyle\boldsymbol{g}$
$\displaystyle=\nabla_{\boldsymbol{\theta}}\mathbb{E}_{s\sim
d^{\pi_{k}}_{p^{r}_{k,\boldsymbol{\xi}}},a\sim\pi}[A_{r,p^{r}_{k,\boldsymbol{\xi}}}^{\pi_{k}}(s,a)],$
$\displaystyle\boldsymbol{h}$
$\displaystyle=\nabla_{\boldsymbol{\theta}}\mathbb{E}_{s\sim
d^{\pi_{k}}_{p^{c}_{k,\boldsymbol{\xi}}},a\sim\pi}[A_{c,p^{c}_{k,\boldsymbol{\xi}}}^{\pi_{k}}(s,a)]$
(20)

be the gradient of the reward advantage function and the gradient of the
utility advantage function, respectively. Moreover, let

$\displaystyle\boldsymbol{H}=\nabla^{2}_{\boldsymbol{\theta}}{\mathbb{E}_{s\sim
d^{\pi_{k}}_{p^{r}_{k,\boldsymbol{\xi}}}}\big{[}D_{KL}(\pi||\pi_{k})(s)\big{]}}$
(21)

be the Hessian matrix of the KL divergence. We then develop the following
practical implementation for our RCPO algorithm.

Step 1: Robust Policy Improvement. We first estimate the worst-case transition
kernel $p_{k}^{r}$ for the current policy $\pi_{k}$. We iteratively update the
parameterized transition kernel $p_{k,\boldsymbol{\xi}}^{r,t}$ using the
following projected gradient descent method:

$\displaystyle
p_{k,\boldsymbol{\xi}}^{r,t+1}=\text{Proj}_{\mathcal{P}}\left(p_{k,\boldsymbol{\xi}}^{r,t}-\beta_{t}\nabla_{p}V_{r,p_{k,\boldsymbol{\xi}}^{r,t}}^{\pi_{k}}(\rho)\right).$
(22)

We then use the first-order approximation for the objective function and the
second-order approximation for the KL divergence constraint at the current
policy $\pi_{k}$ in (4.1). Let $\boldsymbol{\theta}_{k}$ denote the parameter
of policy $\pi_{k}$. The parameter of the intermediate policy
$\pi_{k+\frac{1}{2}}$ is updated by solving the following practical
formulation for (4.1):

$\displaystyle\max_{\boldsymbol{\theta}}\boldsymbol{g}^{\top}(\boldsymbol{\theta}-\boldsymbol{\theta}_{k}),\
\text{s.t.}\
\frac{1}{2}(\boldsymbol{\theta}-\boldsymbol{\theta}_{k})^{\top}\boldsymbol{H}(\boldsymbol{\theta}-\boldsymbol{\theta}_{k})\leq\delta.$
(23)

The objective function of (23) is linear in $\boldsymbol{\theta}$ and the
constraint is quadratic in $\boldsymbol{\theta}$. Therefore, problem (23) can
be easily solved.

Step 2: Projection. For the projection step, we first estimate the worst-case
transition kernel $p_{k}^{c}$ for utility. Similarly, we iteratively update
the parameterized transition kernel $p_{k,\boldsymbol{\xi}}^{c,t}$ using the
following projected gradient descent method:

$\displaystyle
p_{k,\boldsymbol{\xi}}^{c,t+1}=\text{Proj}_{\mathcal{P}}\big{(}p_{k,\boldsymbol{\xi}}^{c,t}-\beta_{t}\nabla_{p}V_{c,p_{k,\boldsymbol{\xi}}^{c,t}}^{\pi_{k}}(\rho)\big{)}.$
(24)

We then approximate the objective function in (4.1) by its second order
expansion and approximate the constraint in (4.1) by its first order
expansion. The parameter of the policy $\pi_{k+1}$ is then updated by solving
the following problem:

$\displaystyle\min_{\boldsymbol{\theta}}$
$\displaystyle\frac{1}{2}(\boldsymbol{\theta}-\boldsymbol{\theta_{k+\frac{1}{2}}})^{\top}\boldsymbol{H}(\boldsymbol{\theta}-\boldsymbol{\theta_{k+\frac{1}{2}}})$
s.t.
$\displaystyle\boldsymbol{h}^{\top}(\boldsymbol{\theta}-\boldsymbol{\theta}_{k})+b\leq
0.$ (25)

The problems in (23) and (5) can be solved by convex programming (Yang et al.,
2019). We have the following update rule for each policy update.

$\displaystyle\boldsymbol{\theta}_{k+1}$
$\displaystyle=\boldsymbol{\theta}_{k}+\sqrt{\frac{2\delta}{\boldsymbol{g}^{\top}\boldsymbol{H}^{-1}\boldsymbol{g}}}\boldsymbol{H}^{-1}\boldsymbol{g}$
$\displaystyle-\max\Bigg{(}\frac{\sqrt{\frac{2\delta}{\boldsymbol{g}^{\top}\boldsymbol{H}^{-1}\boldsymbol{g}}}\boldsymbol{h}\boldsymbol{H}^{-1}\boldsymbol{g}+b}{\boldsymbol{h}^{\top}\boldsymbol{H}^{-1}\boldsymbol{h}},0\Bigg{)}\boldsymbol{H}^{-1}\boldsymbol{h}.$
(26)

In this way, our RCPO algorithm can be implemented efficiently using the above
described approximation for large-scale problems.

##  6 Experiments

To validate the proposed algorithm, we compare it with several baseline
algorithms (PCPO (Yang et al., 2020), RVI (Iyengar, 2005), and CPO (Achiam et
al., 2017)) in the setting of tabular and deep cases, while using different
environments such as the gambler problem (Sutton & Barto, 2018; Zhou et al.,
2021; Shi & Chi, 2022), the $N$-chain problem (Wang et al., 2022), the Frozen-
Lake problem (Brockman et al., 2016) and the Point Gather in Mujoco (Achiam et
al., 2017; Yang et al., 2020).

###  6.1 Tabular Case

In the setting of tabular cases, we evaluate the performance of our algorithm
in the environment of gambler problem, N-chain problem and Frozen-Lake
problem, where both state and action spaces are finite. We compare our
algorithm with two baselines: the PCPO (Yang et al., 2020) and the model-based
robust value iteration (RVI) (Iyengar, 2005). The PCPO learns an optimal
policy subjecting to the constraints under the nominal transition kernels
without considering the model mismatch. The model-based RVI directly optimizes
the unconstrained robust reward objective, which serves as an upper bound of
the reward value function for the robust constrained problem. We consider the
KL divergence uncertainty set. For each problem, we run the algorithms for $5$
independent times and plot the mean of the reward and utility along with their
standard deviation as a function of the number of iterations. The detailed
environments descriptions can be found in Appendix E.

For the gambler problem, the threshold for the constraint is $2.5$. It can be
seen from Fig. 1 that our RCPO always satisfies the constraint during the
training while both the PCPO and RVI violate the constraints. Moreover, the
reward of our RCPO in Fig. 1 is close to the reward of RVI, which is the best
achievable reward for the unconstrained robust RL. Therefore, our algorithm
learns a policy that satisfies the worst-case constraint on the utility and
achieves optimal reward objective.

Figure 1: Gambler Problem

For the $N$-chain problem, the threshold is set to be $6$. From Fig. 2, it can
be seen that all three algorithms satisfy the constraint, indicating that the
constraint is easy to satisfy for this problem. However, in Fig. 2, PCPO
converges to a sub-optimal policy while our RCPO has a similar convergence
rate as the unconstrained RVI.

Figure 2: $N$-chain Problem

For the Frozen-Lake problem, the threshold is set to be $0.7$. From Fig. 3, it
can be seen that only RCPO satisfies the constraint. Both PCPO and RVI violate
the constraint during training. Moreover, in Fig. 3, it can be seen that our
RCPO obtain more reward than PCPO, which demonstrates the effectiveness and
robustness of our algorithm.

Figure 3: Frozen-Lake Problem

###  6.2 Deep Case

In the setting of the deep case, we incorporate our algorithm into deep neural
networks for tackling high-dimensional spaces (e.g. continuous state spaces).
We compare the proposed RCPO with CPO (Achiam et al., 2017) and PCPO (Yang et
al., 2020). We use the same neural network policies with two hidden layers of
size (64, 32) in all three algorithms. We adopt a Mujoco-based environment,
Point Gather task with safety constraints (Achiam et al., 2017), which is a
well-recognized constrained MDP environment. We use the following hyper-
parameters for training RCPO: discounted factor $=0.995$, learning step size
$=0.001$, batch size $=50,000$, and utility-constrained threshold $=0.1$. To
provide fair comparisons, we use the same hyper-parameters for training
baseline algorithms. The experiments are implemented in rllab (Duan et al.,
2016), a tool for developing and evaluating RL algorithms. To introduce model
uncertainties into the environment, we use Gaussian noise to perturb the
environment and evaluate the performance of three algorithms under the
perturbed environment. It can be seen from Fig. 4 that the rewards of RCPO are
much higher than these two non-robust algorithms under model uncertainty,
which demonstrates the robustness of our algorithm to model uncertainty when
incorporating deep neural networks. Meanwhile, the well-trained RCPO policy
satisfies the utility constraint. In summary, RCPO is able to provide
efficient, robust, and constraint-satisfied policies in environments with
continuous spaces by incorporating deep neural networks.

Figure 4: Point Gather

##  7 Conclusion

In this paper, we study the problem of constrained reinforcement learning
under model mismatch. The goal is to maximize the worst-case reward over the
uncertainty set subject to a constraint that the utility function for all
transition kernels in the uncertainty set shall be above a prescribed
threshold. We propose a robust constrained policy optimization (RCPO)
algorithm, which consists of several novel technical developments than the CPO
algorithm (Achiam et al., 2017) for the non-robust standard CMDP problem. One
result that may of independent interest is a robust performance difference
lemma that bound the different between the robust value functions of two
policies. Our algorithm is applicable to large scale MDPs, and has theoretical
guarantees on worst-case reward improvement and constraint violation at each
iteration during the training. We further provide an efficient approximation
for the purpose of practical implementation of our algorithm. Numerical
experiments on demonstrate the effectiveness and robustness of our algorithm
under model mismatch.

##  8 Impact Statements

This paper presents work whose goal is to advance the field of Reinforcement
Learning. There are many potential societal consequences of our work, none
which we feel must be specifically highlighted here.

## References

  * Achiam et al. (2017) Achiam, J., Held, D., Tamar, A., and Abbeel, P.  Constrained policy optimization.  In _Proc. International Conference on Machine Learning (ICML)_ , pp. 22–31. PMLR, 2017.
  * Altman (1999) Altman, E.  _Constrained Markov decision processes: stochastic modeling_.  Routledge, 1999.
  * Auer et al. (2008) Auer, P., Jaksch, T., and Ortner, R.  Near-optimal regret bounds for reinforcement learning.  In _Proc. Advances in Neural Information Processing Systems (NIPS)_ , volume 21, 2008.
  * Brockman et al. (2016) Brockman, G., Cheung, V., Pettersson, L., Schneider, J., Schulman, J., Tang, J., and Zaremba, W.  OpenAI Gym.  _arXiv preprint arXiv:1606.01540_ , 2016.
  * Bura et al. (2022) Bura, A., HasanzadeZonuzy, A., Kalathil, D., Shakkottai, S., and Chamberland, J.-F.  Dope: Doubly optimistic and pessimistic exploration for safe reinforcement learning.  _Advances in Neural Information Processing Systems_ , 35:1047–1059, 2022.
  * Chow et al. (2018) Chow, Y., Nachum, O., Duenez-Guzman, E., and Ghavamzadeh, M.  A lyapunov-based approach to safe reinforcement learning.  In _Proc. Advances in Neural Information Processing Systems (NeurIPS)_ , volume 31, 2018.
  * Csiszár & Körner (2011) Csiszár, I. and Körner, J.  _Information theory: coding theorems for discrete memoryless systems_.  Cambridge University Press, 2011.
  * Dalal et al. (2018) Dalal, G., Dvijotham, K., Vecerik, M., Hester, T., Paduraru, C., and Tassa, Y.  Safe exploration in continuous action spaces.  _arXiv preprint arXiv:1801.08757_ , 2018.
  * Ding et al. (2020) Ding, D., Zhang, K., Basar, T., and Jovanovic, M.  Natural policy gradient primal-dual method for constrained Markov decision processes.  In _Proc. Advances in Neural Information Processing Systems (NeurIPS)_ , volume 33, pp. 8378–8390, 2020.
  * Ding et al. (2021) Ding, D., Wei, X., Yang, Z., Wang, Z., and Jovanovic, M.  Provably efficient safe exploration via primal-dual policy optimization.  In _Proc. International Conference on Artifical Intelligence and Statistics (AISTATS)_ , pp. 3304–3312. PMLR, 2021.
  * Duan et al. (2016) Duan, Y., Chen, X., Houthooft, R., Schulman, J., and Abbeel, P.  Benchmarking deep reinforcement learning for continuous control.  In _International conference on machine learning_ , pp. 1329–1338. PMLR, 2016.
  * Efroni et al. (2020) Efroni, Y., Mannor, S., and Pirotta, M.  Exploration-exploitation in constrained MDPs.  _arXiv preprint arXiv:2003.02189_ , 2020.
  * Fisac et al. (2018) Fisac, J. F., Akametalu, A. K., Zeilinger, M. N., Kaynama, S., Gillula, J., and Tomlin, C. J.  A general safety framework for learning-based control in uncertain robotic systems.  _IEEE Transactions on Automatic Control_ , 64(7):2737–2752, 2018.
  * Gasparik et al. (2018) Gasparik, A., Gamble, C., and Gao, J.  Safety-first AI for autonomous data centre cooling and industrial control.  _DeepMind blog_ , 2018.
  * Iyengar (2005) Iyengar, G. N.  Robust dynamic programming.  _Mathematics of Operations Research_ , 30(2):257–280, 2005.
  * Kakade & Langford (2002) Kakade, S. and Langford, J.  Approximately optimal approximate reinforcement learning.  In _ICML_ , volume 2, pp. 267–274, 2002.
  * Kim et al. (2023) Kim, D., Lee, K., and Oh, S.  Trust region-based safe distributional reinforcement learning for multiple constraints.  In _Thirty-seventh Conference on Neural Information Processing Systems_ , 2023.
  * Kiran et al. (2020) Kiran, B. R., Sobh, I., Talpaert, V., Mannion, P., Al Sallab, A. A., Yogamani, S., and Pérez, P.  Deep reinforcement learning for autonomous driving: A survey.  _arXiv preprint arXiv:2002.00444_ , 2020.
  * Levine et al. (2016) Levine, S., Finn, C., Darrell, T., and Abbeel, P.  End-to-end training of deep visuomotor policies.  _The Journal of Machine Learning Research_ , 17(1):1334–1373, 2016.
  * Li et al. (2021) Li, T., Guan, Z., Zou, S., Xu, T., Liang, Y., and Lan, G.  Faster algorithm and sharper analysis for constrained Markov decision process.  _arXiv preprint arXiv:2110.10351_ , 2021.
  * Liang et al. (2018) Liang, Q., Que, F., and Modiano, E.  Accelerated primal-dual policy optimization for safe reinforcement learning.  _arXiv preprint arXiv:1802.06480_ , 2018.
  * Lim & Autef (2019) Lim, S. H. and Autef, A.  Kernel-based reinforcement learning in robust Markov decision processes.  In _Proc. International Conference on Machine Learning (ICML)_ , pp. 3973–3981. PMLR, 2019.
  * Liu et al. (2021) Liu, T., Zhou, R., Kalathil, D., Kumar, P., and Tian, C.  Fast global convergence of policy optimization for constrained MDPs.  _arXiv preprint arXiv:2111.00552_ , 2021.
  * Liu et al. (2020) Liu, Y., Ding, J., and Liu, X.  Ipo: Interior-point policy optimization under constraints.  In _Proc. Conference on Artificial Intelligence (AAAI)_ , volume 34, pp. 4940–4947, 2020.
  * Mankowitz et al. (2020) Mankowitz, D. J., Calian, D. A., Jeong, R., Paduraru, C., Heess, N., Dathathri, S., Riedmiller, M., and Mann, T.  Robust constrained reinforcement learning for continuous control with model misspecification.  _arXiv preprint arXiv:2010.10644_ , 2020.
  * Nilim & El Ghaoui (2004) Nilim, A. and El Ghaoui, L.  Robustness in Markov decision problems with uncertain transition matrices.  In _Proc. Advances in Neural Information Processing Systems (NIPS)_ , pp. 839–846, 2004.
  * Ono et al. (2015) Ono, M., Pavone, M., Kuwata, Y., and Balaram, J.  Chance-constrained dynamic programming with application to risk-aware robotic space exploration.  _Autonomous Robots_ , 39(4):555–571, 2015.
  * Panaganti & Kalathil (2021) Panaganti, K. and Kalathil, D.  Sample complexity of robust reinforcement learning with a generative model.  _arXiv preprint arXiv:2112.01506_ , 2021.
  * Paternain et al. (2019) Paternain, S., Chamon, L., Calvo-Fullana, M., and Ribeiro, A.  Constrained reinforcement learning has zero duality gap.  In _Proc. Advances in Neural Information Processing Systems (NeurIPS)_ , volume 32, 2019.
  * Roy et al. (2017) Roy, A., Xu, H., and Pokutta, S.  Reinforcement learning under model mismatch.  In _Proc. Advances in Neural Information Processing Systems (NIPS)_ , pp. 3046–3055, 2017.
  * Russel et al. (2020) Russel, R. H., Benosman, M., and Van Baar, J.  Robust constrained-MDPs: Soft-constrained robust policy optimization under model uncertainty.  _arXiv preprint arXiv:2010.04870_ , 2020.
  * Schulman et al. (2015a) Schulman, J., Levine, S., Abbeel, P., Jordan, M., and Moritz, P.  Trust region policy optimization.  In _Proc. International Conference on Machine Learning (ICML)_ , pp. 1889–1897. PMLR, 2015a.
  * Schulman et al. (2015b) Schulman, J., Moritz, P., Levine, S., Jordan, M., and Abbeel, P.  High-dimensional continuous control using generalized advantage estimation.  _arXiv preprint arXiv:1506.02438_ , 2015b.
  * Shi & Chi (2022) Shi, L. and Chi, Y.  Distributionally robust model-based offline reinforcement learning with near-optimal sample complexity.  _arXiv preprint arXiv:2208.05767_ , 2022.
  * Siddique et al. (2019) Siddique, T., Hau, J. L., Atallah, S., and Petrik, M.  Robust pest management using reinforcement learning.  _The Multi-disciplinary Conference on Reinforcement Learning and Decision Making_ , 2019.
  * Stooke et al. (2020) Stooke, A., Achiam, J., and Abbeel, P.  Responsive safety in reinforcement learning by pid lagrangian methods.  In _Proc. International Conference on Machine Learning (ICML)_ , pp. 9133–9143. PMLR, 2020.
  * Sutton & Barto (2018) Sutton, R. S. and Barto, A. G.  _Reinforcement learning: An introduction_.  MIT press, 2018.
  * Sutton et al. (1999) Sutton, R. S., McAllester, D. A., Singh, S. P., Mansour, Y., et al.  Policy gradient methods for reinforcement learning with function approximation.  In _Proc. Advances in Neural Information Processing Systems (NIPS)_ , volume 99, pp. 1057–1063. Citeseer, 1999.
  * Tessler et al. (2018) Tessler, C., Mankowitz, D. J., and Mannor, S.  Reward constrained policy optimization.  _arXiv preprint arXiv:1805.11074_ , 2018.
  * Wang et al. (2023a) Wang, Q., Ho, C. P., and Petrik, M.  Policy gradient in robust mdps with global convergence guarantee, 2023a.
  * Wang & Zou (2021) Wang, Y. and Zou, S.  Online robust reinforcement learning with model uncertainty.  In _Proc. Advances in Neural Information Processing Systems (NeurIPS)_ , volume 34, pp. 7193–7206, 2021.
  * Wang & Zou (2022) Wang, Y. and Zou, S.  Policy gradient method for robust reinforcement learning.  In _Proc. International Conference on Machine Learning (ICML)_ , volume 162, pp. 23484–23526. PMLR, 2022.
  * Wang et al. (2022) Wang, Y., Miao, F., and Zou, S.  Robust constrained reinforcement learning.  _arXiv preprint arXiv:2209.06866_ , 2022.
  * Wang et al. (2023b) Wang, Y., Velasquez, A., Atia, G., Prater-Bennette, A., and Zou, S.  Robust average-reward markov decision processes.  In _Proc. Conference on Artificial Intelligence (AAAI)_ , 2023b.
  * Wang et al. (2023c) Wang, Y., Velasquez, A., Atia, G. K., Prater-Bennette, A., and Zou, S.  Model-free robust average-reward reinforcement learning.  In _International Conference on Machine Learning_ , pp. 36431–36469. PMLR, 2023c.
  * Wei et al. (2022) Wei, H., Liu, X., and Ying, L.  Triple-q: A model-free algorithm for constrained reinforcement learning with sublinear regret and zero constraint violation.  In Camps-Valls, G., Ruiz, F. J. R., and Valera, I. (eds.), _Proceedings of The 25th International Conference on Artificial Intelligence and Statistics_ , volume 151 of _Proceedings of Machine Learning Research_ , pp. 3274–3307. PMLR, 28–30 Mar 2022.
  * Xu & Mannor (2010) Xu, H. and Mannor, S.  Distributionally robust Markov decision processes.  In _Proc. Advances in Neural Information Processing Systems (NIPS)_ , pp. 2505–2513, 2010.
  * Xu et al. (2021) Xu, T., Liang, Y., and Lan, G.  Crpo: A new approach for safe reinforcement learning with convergence guarantee.  In _Proc. International Conference on Machine Learning (ICML)_ , pp. 11480–11491. PMLR, 2021.
  * Yang et al. (2019) Yang, T.-Y., Rosca, J., Narasimhan, K., and Ramadge, P. J.  Projection-based constrained policy optimization.  In _International Conference on Learning Representations_ , 2019.
  * Yang et al. (2020) Yang, T.-Y., Rosca, J., Narasimhan, K., and Ramadge, P. J.  Projection-based constrained policy optimization.  _arXiv preprint arXiv:2010.03152_ , 2020.
  * Yang et al. (2021) Yang, W., Zhang, L., and Zhang, Z.  Towards theoretical understandings of robust Markov decision processes: Sample complexity and asymptotics.  _arXiv preprint arXiv:2105.03863_ , 2021.
  * Ying et al. (2021) Ying, D., Ding, Y., and Lavaei, J.  A dual approach to constrained Markov decision processes with entropy regularization.  _arXiv preprint arXiv:2110.08923_ , 2021.
  * Yu et al. (2019a) Yu, C., Liu, J., and Nemati, S.  Reinforcement learning in healthcare: A survey.  _arXiv preprint arXiv:1908.08796_ , 2019a.
  * Yu et al. (2019b) Yu, M., Yang, Z., Kolar, M., and Wang, Z.  Convergent policy optimization for safe reinforcement learning.  In _Proc. Advances in Neural Information Processing Systems (NeurIPS)_ , volume 32, 2019b.
  * Zhang et al. (2020) Zhang, Y., Vuong, Q., and Ross, K.  First order constrained optimization in policy space.  _Advances in Neural Information Processing Systems_ , 33:15338–15349, 2020.
  * Zheng & Ratliff (2020) Zheng, L. and Ratliff, L.  Constrained upper confidence reinforcement learning.  In _Learning for Dynamics and Control_ , pp. 620–629. PMLR, 2020.
  * Zhou et al. (2021) Zhou, Z., Bai, Q., Zhou, Z., Qiu, L., Blanchet, J., and Glynn, P.  Finite-sample regret bound for distributionally robust offline tabular reinforcement learning.  In _Proc. International Conference on Artifical Intelligence and Statistics (AISTATS)_ , pp. 3331–3339. PMLR, 2021.

##  Appendix A Review of Constrained Policy Optimization

In this section, we provide an overview of the CPO method developed in (Achiam
et al., 2017). Recall that in the standard (non-robust) RL setting, the value
function difference between two policies $\pi,\pi^{\prime}$ can be written as
(Kakade & Langford, 2002):

$\displaystyle
V_{r,p}^{\pi\prime}(\rho)-V_{r,p}^{\pi}(\rho)=\frac{1}{1-\gamma}\mathbb{E}_{\begin{subarray}{c}s\sim
d^{\pi^{\prime}}_{p}\\\ a\sim\pi^{\prime}\end{subarray}}[A^{\pi}_{r,p}(s,a)],$
(27)

where $A^{\pi}_{r,p}(s,a)=Q^{\pi}_{r,p}(s,a)-V^{\pi}_{r,p}(s)$ is the reward
advantage function. In (Achiam et al., 2017), the above result was further
extended to the following one:

$\displaystyle V_{r,p}^{\pi^{\prime}}(\rho)-V_{r,p}^{\pi}(\rho)$ (28)
$\displaystyle\geq\frac{1}{1-\gamma}\mathbb{E}_{\begin{subarray}{c}s\sim
d^{\pi}_{p}\\\
a\sim\pi^{\prime}\end{subarray}}\left[A^{\pi}_{r,p}(s,a)-\frac{2\gamma\epsilon^{\pi^{\prime}}_{r}}{1-\gamma}\sqrt{\frac{1}{2}D_{KL}(\pi^{\prime}\|\pi)(s)}\right],$

where
$\epsilon^{\pi^{\prime}}_{r}=\max_{s}|\mathbb{E}_{a\sim\pi^{\prime}}[A^{\pi}_{r,p}(s,a)]|$.

Equation 28 connects the performance difference between two policies to an
average divergence between them. Compared with (27), the expectation is taken
with respect to $d^{\pi}_{p}$ in (28) instead of $d^{\pi^{\prime}}_{p}$. When
$\pi^{\prime}$ is close to $\pi$, $D_{KL}(\pi^{\prime}\|\pi)(s)$ is small and
$d^{\pi^{\prime}}_{p}$ is close to $d^{\pi}_{p}$. Therefore, the right hand
side of (28) is a good local approximation for the performance difference
$V_{r,p}^{\pi^{\prime}}-V_{r,p}^{\pi}$. The trust region method for
unconstrained RL was proposed (Schulman et al., 2015a, b) based on this
approximation and provides monotonic improvement for the reward value
function.

For the utility value function, we have the following equivalent expression:

$\displaystyle V_{c,p}^{\pi^{\prime}}(\rho)-V_{c,p}^{\pi}(\rho)$ (29)
$\displaystyle\geq\frac{1}{1-\gamma}\mathbb{E}_{\begin{subarray}{c}s\sim
d^{\pi}_{p}\\\
a\sim\pi^{\prime}\end{subarray}}\left[A^{\pi}_{c,p}(s,a)-\frac{2\gamma\epsilon^{\pi^{\prime}}_{c}}{1-\gamma}\sqrt{\frac{1}{2}D_{KL}(\pi^{\prime}\|\pi)(s)}\right],$

where
$\epsilon^{\pi^{\prime}}_{c}=\max_{s}|\mathbb{E}_{a\sim\pi^{\prime}}[A^{\pi}_{c,p}(s,a)]|$
and $A^{\pi}_{c,p}(s,a)=Q^{\pi}_{c,p}(s,a)-V^{\pi}_{c,p}(s)$ is the utility
advantage function. The right hand side of (29) can be used as an
approximation for $V_{c,p}^{\pi^{\prime}}(\rho)-V_{c,p}^{\pi}(\rho)$. By
applying the trust region methods to CMDPs, the constrained policy
optimization (CPO) was proposed in (Achiam et al., 2017), where the policy is
updated by solving the following optimization problem.

$\displaystyle\pi_{k+1}$
$\displaystyle=\operatorname*{arg\,max}_{\pi}\mathbb{E}_{\begin{subarray}{c}s\sim
d^{\pi_{k}}_{p}\\\
a\sim\pi\end{subarray}}\Big{[}A^{\pi_{k}}_{r,p}(s,a)\Big{]}$ s.t.
$\displaystyle\
V_{c,p}^{\pi_{k}}(\rho)+\frac{1}{1-\gamma}\mathbb{E}_{\begin{subarray}{c}s\sim
d^{\pi_{k}}_{p}\\\
a\sim\pi\end{subarray}}\Big{[}A^{\pi_{k}}_{c,p}(s,a)\Big{]}\geq d,$
$\displaystyle\mathbb{E}_{s\sim
d^{\pi_{k}}_{p}}[D_{KL}(\pi\|\pi_{k})(s)]\leq\delta.$ (30)

When the current policy $\pi_{k}$ satisfies the constraint, this update rule
leads to a policy that has performance improvement and approximate
satisfaction of constraints (Achiam et al., 2017). Note that the expectation
in the optimization problem (A) is taken with respect to $d^{\pi_{k}}_{p}$.
The optimization problem (A) depends on $\pi$ only through the distribution of
the current action $a$, which can thus be optimized efficiently.

##  Appendix B Proof of Lemma 4.1

For any policies $\pi,\pi^{\prime}$, we have that

$\displaystyle V_{r}^{\pi^{\prime}}(\rho)-V_{r}^{\pi}(\rho)$
$\displaystyle=V_{r,p_{\pi^{\prime}}^{r}}^{\pi^{\prime}}(\rho)-V_{r,p_{\pi}^{r}}^{\pi}(\rho)$
$\displaystyle\geq
V_{r,p_{\pi^{\prime}}^{r}}^{\pi^{\prime}}(\rho)-V_{r,p_{\pi^{\prime}}^{r}}^{\pi}(\rho)$
$\displaystyle\geq\frac{1}{1-\gamma}\mathbb{E}_{\begin{subarray}{c}s\sim
d^{\pi}_{p_{\pi^{\prime}}^{r}}\\\
a\sim\pi^{\prime}\end{subarray}}\Big{[}A^{\pi}_{r,{p_{\pi^{\prime}}^{r}}}(s,a)-\frac{2\gamma\epsilon^{\pi^{\prime}}_{r,p_{\pi^{\prime}}^{r}}}{1-\gamma}\sqrt{\frac{1}{2}D_{KL}(\pi^{\prime}\|\pi)(s)}\Big{]},$
(31)

where the first inequality is because
$V_{r,p_{\pi}^{r}}^{\pi}(\rho)=\min_{p\in\mathcal{P}}V_{r,p}^{\pi}(\rho)$ and
the second inequality follows from Theorem 1 in (Achiam et al., 2017).

##  Appendix C Proof of Theorem 4.3

We first prove the follow Lemma.

######  Lemma C.1.

If the current policy $\pi_{k}$ satisfies the constraint and the constraint
set is closed and convex under the policy parameterization, then under the KL
divergence projection, we have that

$\displaystyle\mathbb{E}_{s\sim
d^{\pi_{k}}_{p^{r,\boldsymbol{\xi}}_{k}}}[D_{KL}(\pi_{k+1}||\pi_{k})(s)]\leq\delta.$
(32)

###### Proof.

Note that the constraint in (4.1) is linear in $\pi$. Therefore, the
constraint set is closed and convex. Since $\pi_{k}$ lies in the constraint
set and $\pi_{k+1}$ is the projection of $\pi_{k+\frac{1}{2}}$ onto the
constraint set, from the Bregmann divergence projection inequality, we have
that

$\displaystyle\mathbb{E}_{s\sim
d^{\pi_{k}}_{p^{r,\boldsymbol{\xi}}_{k}}}[D_{KL}(\pi_{k}||\pi_{k+\frac{1}{2}})(s)]\geq\mathbb{E}_{s\sim
d^{\pi_{k}}_{p^{r,\boldsymbol{\xi}}_{k}}}[D_{KL}(\pi_{k}||\pi_{k+1})(s)]+\mathbb{E}_{s\sim
d^{\pi_{k}}_{p^{r,\boldsymbol{\xi}}_{k}}}[D_{KL}(\pi_{k+1}||\pi_{k+\frac{1}{2}})(s)].$
(33)

Since the KL divergence is non-negative, we have that

$\displaystyle\mathbb{E}_{s\sim
d^{\pi_{k}}_{p^{r,\boldsymbol{\xi}}_{k}}}[D_{KL}(\pi_{k}||\pi_{k+\frac{1}{2}})(s)]\geq\mathbb{E}_{s\sim
d^{\pi_{k}}_{p^{r,\boldsymbol{\xi}}_{k}}}[D_{KL}(\pi_{k}||\pi_{k+1})(s)].$
(34)

When $\delta$ is small, the KL divergence is asymptotically symmetric.
Therefore, we have that

$\displaystyle\mathbb{E}_{s\sim
d^{\pi_{k}}_{p^{r,\boldsymbol{\xi}}_{k}}}[D_{KL}(\pi_{k+1}\|\pi_{k})(s)]\leq\mathbb{E}_{s\sim
d^{\pi_{k}}_{p^{r,\boldsymbol{\xi}}_{k}}}[D_{KL}(\pi_{k+\frac{1}{2}}\|\pi_{k})(s)]\leq\delta.$
(35)

∎

With Lemma C.1, we are ready to prove Theorem 4.3.

###### Proof.

From Lemma 4.1, we have that for the reward improvement,

$\displaystyle V_{r}^{\pi_{k+1}}(\rho)-V_{r}^{\pi_{k}}(\rho)$
$\displaystyle\geq\frac{1}{1-\gamma}\mathbb{E}_{\begin{subarray}{c}s\sim
d^{\pi_{k}}_{p_{{k+1}}^{r}}\\\
a\sim\pi_{k+1}\end{subarray}}\Big{[}A^{\pi_{k}}_{r,{p_{{k+1}}^{r}}}(s,a)-\frac{2\gamma\epsilon^{\pi_{k+1}}_{r,p_{k+1}^{r}}}{1-\gamma}\sqrt{\frac{1}{2}D_{KL}(\pi_{k+1}\|\pi_{k})(s)}\Big{]}.$
(36)

Note that
$A^{\pi_{k}}_{r,{p_{{k+1}}^{r}}}(s,a)=Q^{\pi_{k}}_{r,{p_{{k+1}}^{r}}}(s,a)-V^{\pi_{k}}_{r,{p_{{k+1}}^{r}}}(s)$
is Lipschitz in $\pi_{k}$ (Wang et al., 2023a). We have that there exists
$L_{\pi}$ such that

$\displaystyle|A^{\pi_{k}}_{r,{p_{{k+1}}^{r}}}(s,a)-A^{{k+1}}_{r,{p_{{k+1}}^{r}}}(s,a)|\leq
L_{\pi}\|\pi_{k+1}(s)-\pi_{k}(s)\|_{1}.$ (37)

We then have that

$\displaystyle\frac{1}{1-\gamma}\mathbb{E}_{\begin{subarray}{c}s\sim
d^{\pi_{k}}_{p_{{k+1}}^{r}}\\\
a\sim\pi_{k+1}\end{subarray}}\Big{[}A^{\pi_{k}}_{r,{p_{k+1}^{r}}}(s,a)-\frac{2\gamma\epsilon^{\pi_{k+1}}_{r,p_{k+1}^{r}}}{1-\gamma}\sqrt{\frac{1}{2}D_{KL}(\pi_{k+1}\|\pi_{k})(s)}\Big{]}$
$\displaystyle\geq\frac{1}{1-\gamma}\mathbb{E}_{\begin{subarray}{c}s\sim
d^{\pi_{k}}_{p_{{k+1}}^{r}}\\\
a\sim\pi_{k+1}\end{subarray}}\Big{[}A^{\pi_{k+1}}_{r,{p_{k+1}^{r}}}(s,a)-L_{\pi}\|\pi_{k+1}(s)-\pi_{k}(s)\|_{1}-\frac{2\gamma\epsilon^{\pi_{k+1}}_{r,p_{k+1}^{r}}}{1-\gamma}\sqrt{\frac{1}{2}D_{KL}(\pi_{k+1}\|\pi_{k})(s)}\Big{]}$
$\displaystyle=\frac{1}{1-\gamma}\mathbb{E}_{s\sim
d^{\pi_{k}}_{p_{k+1}^{r}}}\Big{[}-L_{\pi}\|\pi_{k+1}(s)-\pi_{k}(s)\|_{1}-\frac{2\gamma\epsilon^{\pi_{k+1}}_{r,p_{k+1}^{r}}}{1-\gamma}\sqrt{\frac{1}{2}D_{KL}(\pi_{k+1}\|\pi_{k})(s)}\Big{]},$
(38)

where the equality is due to the fact that
$\mathbb{E}_{a\sim\pi_{k+1}}\big{[}A^{\pi_{k+1}}_{r,{p_{k+1}^{r}}}(s,a)\big{]}=\mathbb{E}_{a\sim\pi_{k+1}}\big{[}Q^{\pi_{k+1}}_{r,{p_{k+1}^{r}}}(s,a)-V^{\pi_{k+1}}_{r,{p_{k+1}^{r}}}(s)\big{]}=0$.
Since
$\|\pi_{k+1}(s)-\pi_{k}(s)\|_{1}=2D_{TV}(\pi_{k+1}\|\pi_{k})(s)\leq\sqrt{2D_{KL}(\pi_{k+1}\|\pi_{k})(s)}$
(Csiszár & Körner, 2011), we have that

$\displaystyle\frac{1}{1-\gamma}\mathbb{E}_{s\sim
d^{\pi_{k}}_{p_{k+1}^{r}}}\Big{[}-L_{\pi}\|\pi_{k+1}(s)-\pi_{k}(s)\|_{1}-\frac{2\gamma\epsilon^{\pi_{k+1}}_{r,p_{k+1}^{r}}}{1-\gamma}\sqrt{\frac{1}{2}D_{KL}(\pi_{k+1}\|\pi_{k})(s)}\Big{]}$
$\displaystyle\geq\frac{1}{1-\gamma}\mathbb{E}_{s\sim
d^{\pi_{k}}_{p_{k+1}^{r}}}\Big{[}-\big{(}2L_{\pi}+\frac{2\gamma\epsilon^{\pi_{k+1}}_{r,p_{k+1}^{r}}}{1-\gamma}\big{)}\sqrt{\frac{1}{2}D_{KL}(\pi_{k+1}\|\pi_{k})(s)}\Big{]}$
$\displaystyle\overset{(a)}{\geq}\frac{1}{1-\gamma}\mathbb{E}_{s\sim
d^{\pi_{k}}_{p^{r,\boldsymbol{\xi}}_{k}}}\Big{[}-M\big{(}2L_{\pi}+\frac{2\gamma\epsilon^{\pi_{k+1}}_{r,p_{k+1}^{r}}}{1-\gamma}\big{)}\sqrt{\frac{1}{2}D_{KL}(\pi_{k+1}\|\pi_{k})(s)}\Big{]}$
$\displaystyle\overset{(b)}{\geq}-\frac{1}{1-\gamma}M\big{(}2L_{\pi}+\frac{2\gamma\epsilon^{\pi_{k+1}}_{r,p_{k+1}^{r}}}{1-\gamma}\big{)}\sqrt{\frac{\delta}{2}},$
(39)

where $(a)$ is due to the fact that
$M=\sup_{p,p^{\prime}\in\mathcal{P}}\|d^{\pi_{k}}_{p}/d^{\pi_{k}}_{p^{\prime}}\|_{\infty}$
is finite and $(b)$ is from Lemma C.1 and Jensen’s inequality.

To characterize the constraint violation, we first have that

$\displaystyle
V_{c,p^{c,\boldsymbol{\xi}}_{k}}^{\pi_{k}}(\rho)+\mathbb{E}_{\begin{subarray}{c}s\sim
d^{\pi_{k}}_{p_{k}^{c,\boldsymbol{\xi}}}\\\
a\sim\pi_{k+1}\end{subarray}}[A_{c,p^{c,\boldsymbol{\xi}}_{k}}^{\pi_{k}}(s,a)]\geq
d.$ (40)

and

$\displaystyle V_{c}^{\pi_{k+1}}(\rho)-V_{c}^{\pi_{k}}(\rho)$
$\displaystyle=V_{c,p_{k+1}^{c}}^{\pi_{k+1}}(\rho)-V_{c,p_{\pi_{k}}^{c}}^{\pi_{k}}(\rho)$
$\displaystyle\geq
V_{c,p_{k+1}^{c}}^{\pi_{k+1}}(\rho)-V_{c,p_{k+1}^{c}}^{\pi_{k}}(\rho)$
$\displaystyle\geq\frac{1}{1-\gamma}\mathbb{E}_{\begin{subarray}{c}s\sim
d^{\pi_{k}}_{p_{k+1}^{c}}\\\
a\sim\pi_{k+1}\end{subarray}}\Big{[}A^{\pi_{k}}_{c,{p_{k+1}^{c}}}(s,a)-\frac{2\gamma\epsilon^{\pi_{k+1}}_{c,p_{k+1}^{c}}}{1-\gamma}\sqrt{\frac{1}{2}D_{KL}(\pi_{k+1}\|\pi_{k})(s)}\Big{]}.$
(41)

Following the proof of (C), we have that

$\displaystyle V_{c}^{\pi_{k+1}}(\rho)$ $\displaystyle\geq
d-(V_{c,p^{c,\boldsymbol{\xi}}_{k}}^{\pi_{k}}(\rho)-V_{c}^{\pi_{k}}(\rho))-\mathbb{E}_{\begin{subarray}{c}s\sim
d^{\pi_{k}}_{p_{k}^{c,\boldsymbol{\xi}}}\\\
a\sim\pi_{k+1}\end{subarray}}[A_{c,p^{c,\boldsymbol{\xi}}_{k}}^{\pi_{k}}(s,a)]$
$\displaystyle\quad+\frac{1}{1-\gamma}\mathbb{E}_{\begin{subarray}{c}s\sim
d^{\pi_{k}}_{p_{k+1}^{c}}\\\
a\sim\pi_{k+1}\end{subarray}}\Big{[}A^{\pi_{k}}_{c,{p_{k+1}^{c}}}(s,a)-\frac{2\gamma\epsilon^{\pi_{k+1}}_{c,p_{k+1}^{c}}}{1-\gamma}\sqrt{\frac{1}{2}D_{KL}(\pi_{k+1}\|\pi_{k})(s)}\Big{]}$
$\displaystyle\geq d-\epsilon-\mathbb{E}_{\begin{subarray}{c}s\sim
d^{\pi_{k}}_{p_{k}^{c,\boldsymbol{\xi}}}\\\
a\sim\pi_{k+1}\end{subarray}}\big{[}A_{c,p^{c}_{k}}^{\pi_{k+1}}(s,a)+L_{\pi}\|\pi_{k+1}(s)-\pi_{k}(s)\|_{1}\big{]}$
$\displaystyle\quad+\frac{1}{1-\gamma}\mathbb{E}_{\begin{subarray}{c}s\sim
d^{\pi_{k}}_{p_{k+1}^{c}}\\\
a\sim\pi_{k+1}\end{subarray}}\Big{[}A^{\pi_{k+1}}_{c,{p_{k+1}^{c}}}(s,a)-L_{\pi}\|\pi_{k+1}(s)-\pi_{k}(s)\|_{1}-\frac{2\gamma\epsilon^{\pi_{k+1}}_{c,p_{k+1}^{c}}}{1-\gamma}\sqrt{\frac{1}{2}D_{KL}(\pi_{k+1}\|\pi_{k})(s)}\Big{]}$
$\displaystyle=d-\epsilon-\mathbb{E}_{s\sim
d^{\pi_{k}}_{p_{k}^{c,\boldsymbol{\xi}}}}[L_{\pi}\|\pi_{k+1}(s)-\pi_{k}(s)\|_{1}]$
$\displaystyle\quad+\frac{1}{1-\gamma}\mathbb{E}_{s\sim
d^{\pi_{k}}_{p_{k+1}^{c}}}\Big{[}-L_{\pi}\|\pi_{k+1}(s)-\pi_{k}(s)\|_{1}-\frac{2\gamma\epsilon^{\pi_{k+1}}_{c,p_{k+1}^{c}}}{1-\gamma}\sqrt{\frac{1}{2}D_{KL}(\pi_{k+1}\|\pi_{k})(s)}\Big{]}$
$\displaystyle\geq d-\epsilon+\frac{1}{1-\gamma}\mathbb{E}_{s\sim
d^{\pi_{k}}_{p_{k}^{c,\boldsymbol{\xi}}}}\Big{[}-M\big{(}3L_{\pi}+\frac{2\gamma\epsilon^{\pi_{k+1}}_{c,p_{k+1}^{c}}}{1-\gamma}\big{)}\sqrt{\frac{1}{2}D_{KL}(\pi_{k+1}\|\pi_{k})(s)}\Big{]}$
$\displaystyle\geq
d-\epsilon-\frac{1}{1-\gamma}M\big{(}3L_{\pi}+\frac{2\gamma\epsilon^{\pi_{k+1}}_{c,p_{k+1}^{c}}}{1-\gamma}\big{)}\sqrt{\frac{\delta}{2}}.$
(42)

This completes the proof. ∎

##  Appendix D Proof of Theorem 4.4

We first provide an upper bound on the KL divergence between $\pi_{k}$ and
$\pi_{k+1}$ in the following lemma. We then follow the proof of Theorem 4.3 to
prove Theorem 4.4.

######  Lemma D.1.

If the current policy $\pi_{k}$ violates the constraint and the constraint set
is convex and closed under the policy parameterization, let
$b=V_{c}^{\pi}(\rho)-d$, then under the KL divergence projection, we have that

$\displaystyle\mathbb{E}_{s\sim
d^{\pi_{k}}_{p^{r,\boldsymbol{\xi}}_{k}}}[D_{KL}(\pi_{k+1}||\pi_{k})(s)]\leq\delta+b^{2}\alpha_{KL}+bM^{\prime}\sqrt{\frac{\alpha_{KL}}{2}},$
(43)

where
$\alpha_{KL}=\frac{1}{2\boldsymbol{h}^{\top}\boldsymbol{H}^{-1}\boldsymbol{h}}$,
$\boldsymbol{h}$ is the gradient of the utility advantage function,
$\boldsymbol{H}$ is the Hessian matrix of the KL divergence constraint,
$M^{\prime}\leq\infty$ is some constant.

###### Proof.

Define the following set:

$\displaystyle
Z_{\pi_{k}}=\big{\\{}\pi\big{|}V_{c,{p^{c,\boldsymbol{\xi}}_{k}}}^{\pi_{k}}(\rho)+\mathbb{E}_{s\sim
d^{\pi_{k}}_{p^{c,\boldsymbol{\xi}}_{k}},a\sim\pi}[A_{c,{p^{c,\boldsymbol{\xi}}_{k}}}^{\pi_{k}}(s,a)]\geq
V_{c,{p^{c,\boldsymbol{\xi}}_{k}}}^{\pi_{k}}(\rho)\big{\\}}.$ (44)

Note that the current policy $\pi_{k}$ lies in $Z_{\pi_{k}}$. Define the
policy $\pi_{k+1}^{l}$ as the projection of $\pi_{k+\frac{1}{2}}$ onto
$Z_{\pi_{k}}$. We have that

$\displaystyle
D_{KL}(\pi_{k+1}\|\pi_{k})(s)=D_{KL}(\pi_{k+1}^{l}\|\pi_{k})(s)+D_{KL}(\pi_{k+1}\|\pi_{k+1}^{l})(s)+\big{(}\pi_{k+1}(s)-\pi_{k+1}^{l}(s)\big{)}^{\top}\log\frac{\pi_{k+1}^{l}(s)}{\pi_{k}(s)}.$
(45)

From C.1, we have that $\mathbb{E}_{s\sim
d^{\pi_{k}}_{p^{r,\boldsymbol{\xi}}_{k}}}[D_{KL}(\pi_{k+1}^{l}\|\pi_{k})(s)]\leq\delta$.
For small $b$, $\mathbb{E}_{s\sim
d^{\pi_{k}}_{p^{r,\boldsymbol{\xi}}_{k}}}[D_{KL}(\pi_{k+1}\|\pi_{k+1}^{l})(s)]$
can be approximated by the second order expansion. We have that

$\displaystyle\mathbb{E}_{s\sim
d^{\pi_{k}}_{p^{r,\boldsymbol{\xi}}_{k}}}[D_{KL}(\pi_{k+1}\|\pi_{k+1}^{l})(s)]$
$\displaystyle\approx\frac{1}{2}(\boldsymbol{\theta}_{k+1}-\boldsymbol{\theta}^{l}_{k+1})^{\top}\boldsymbol{H}(\boldsymbol{\theta}_{k+1}-\boldsymbol{\theta}^{l}_{k+1})$
$\displaystyle=\frac{1}{2}\Big{(}\frac{b}{\boldsymbol{h}^{\top}\boldsymbol{H}^{-1}\boldsymbol{h}}\boldsymbol{H}^{-1}\boldsymbol{h}\Big{)}^{\top}\boldsymbol{H}\Big{(}\frac{b}{\boldsymbol{h}^{\top}\boldsymbol{H}^{-1}\boldsymbol{h}}\boldsymbol{H}^{-1}\boldsymbol{h}\Big{)}$
$\displaystyle=\frac{b^{2}}{2\boldsymbol{h}^{\top}\boldsymbol{H}^{-1}\boldsymbol{h}}$
$\displaystyle=b^{2}\alpha_{KL},$ (46)

where
$\alpha_{KL}=\frac{1}{2\boldsymbol{h}^{\top}\boldsymbol{H}^{-1}\boldsymbol{h}}$
and the first equality is from the update rule in (5). For
$\big{(}\pi_{k+1}(s)-\pi_{k+1}^{l}(s)\big{)}^{\top}\log\frac{\pi_{k+1}^{l}(s)}{\pi_{k}(s)}$,
we have that

$\displaystyle\big{(}\pi_{k+1}(s)-\pi_{k+1}^{l}(s)\big{)}^{\top}\log\frac{\pi_{k+1}^{l}(s)}{\pi_{k}(s)}\leq\|\pi_{k+1}(s)-\pi_{k+1}^{l}(s)\|_{1}\big{\|}\log\frac{\pi_{k+1}^{l}(s)}{\pi_{k}(s)}\big{\|}_{\infty}.$
(47)

Since $\mathbb{E}_{s\sim
d^{\pi_{k}}_{p^{r,\boldsymbol{\xi}}_{k}}}[D_{KL}(\pi_{k+1}^{l}\|\pi_{k})(s)]\leq\delta$,
there exists $M^{\prime}$ such that $\mathbb{E}_{s\sim
d^{\pi_{k}}_{p^{r,\boldsymbol{\xi}}_{k}}}\Big{[}\big{\|}\log\frac{\pi_{k+1}^{l}(s)}{\pi_{k}(s)}\big{\|}_{\infty}\Big{]}\leq
M^{\prime}.$ Moreover, we have that
$\|\pi_{k+1}(s)-\pi_{k+1}^{l}(s)\|_{1}\leq\sqrt{2D_{KL}(\pi_{k+1}\|\pi_{k+1}^{l})(s)}$.
We then have that

$\displaystyle\mathbb{E}_{s\sim
d^{\pi_{k}}_{p^{r,\boldsymbol{\xi}}_{k}}}\Big{[}\big{(}\pi_{k+1}(s)-\pi_{k+1}^{l}(s)\big{)}^{\top}\log\frac{\pi_{k+1}^{l}(s)}{\pi_{k}(s)}\Big{]}$
$\displaystyle\leq\mathbb{E}_{s\sim
d^{\pi_{k}}_{p^{r,\boldsymbol{\xi}}_{k}}}\Big{[}M^{\prime}\sqrt{\frac{1}{2}D_{KL}(\pi_{k+1}\|\pi_{k+1}^{l})(s)}\Big{]}$
$\displaystyle\overset{(a)}{\leq}M^{\prime}\sqrt{\mathbb{E}_{s\sim
d^{\pi_{k}}_{p^{r,\boldsymbol{\xi}}_{k}}}\Big{[}\frac{1}{2}D_{KL}(\pi_{k+1}\|\pi_{k+1}^{l})(s)\Big{]}}$
$\displaystyle\overset{(b)}{\approx}bM^{\prime}\sqrt{\frac{\alpha_{KL}}{2}},$
(48)

where $(a)$ is from Jensen’s inequality and $(b)$ is from (D).

By combining (45), (D) and (D), we have that

$\displaystyle\mathbb{E}_{s\sim
d^{\pi_{k}}_{p^{r,\boldsymbol{\xi}}_{k}}}[D_{KL}(\pi_{k+1}||\pi_{k})(s)]\leq\delta+b^{2}\alpha_{KL}+bM^{\prime}\sqrt{\frac{\alpha_{KL}}{2}}.$
(49)

∎

With Lemma D.1, Theorem 4.4 can be proved similarly as Theorem 4.3.

##  Appendix E Experiments

The detailed environments descriptions are in the following:

Gambler Problem in a game in which a gambler bets on a sequence of coin
tosses, wining the stake when the outcome is head and losing when it’s tail.
Starting from an initial balance, the game ends once the gambler’s balance
reaches $16$ or $0$. For different state-action pairs, the gambler receives
different utilities. The reward is $10$ when the balance reaches $16$ and $0$
otherwise. The probability of head for each coin toss is $p=0.6$. The radius
of the uncertainty set is $0.1$.

$N$-chain problem involves a chain with $N$ nodes. At each node, the agent can
choose to move to its left or its right. Upon moving to its left, it receives
a reward-utility signal of $(1,0)$, while moving to its right yields a reward-
utility signal of $(0,2)$. When reaching the $N$-th node, the agent receives a
bonus reward of $10$. With probability $0.1$, the agent may slip to the
different direction of its action. We let $N=40$ and the radius of the
uncertainty set be $0.15$.

Frozen-Lake problem is about training an agent to cross a $4\times 4$ frozen
lake from the starting point to the end point without falling into any holes.
Upon falling into the holes, the agent will get trapped and receive zero
reward and utility. Reaching the end point yields a reward of $r=200$,
otherwise $r=0$. At some states, the agent will receive a utility of $c=1$.
The agent may slip to the different direction of its action. The radius of the
uncertainty set is $0.1$.

Point Gather is a benchmark Mujoco task for constrained MDP, in which an agent
is rewarded for gathering green apples but is constrained to collect a limited
number of red fruit (Achiam et al., 2017).