Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process

Tianjiao Li⋆ Ziwei Guan† Shaofeng Zou‡ Tengyu Xu† Yingbin Liang† Guanghui Lan⋆

⋆Georgia Institute of Technology †The Ohio State University ‡University at
Buffalo, The State University of New York

###### Abstract

The problem of constrained Markov decision process (CMDP) is investigated,
where an agent aims to maximize the expected accumulated discounted reward
subject to multiple constraints on its utilities/costs. A new primal-dual
approach is proposed with a novel integration of three ingredients: entropy
regularized policy optimizer, dual variable regularizer, and Nesterov’s
accelerated gradient descent dual optimizer, all of which are critical to
achieve a faster convergence. The finite-time error bound of the proposed
approach is characterized. Despite the challenge of the nonconcave objective
subject to nonconcave constraints, the proposed approach is shown to converge
to the global optimum with a complexity of $\tilde{\mathcal{O}}(1/\epsilon)$
in terms of the optimality gap and the constraint violation, which improves
the complexity of the existing primal-dual approach by a factor of
$\mathcal{O}(1/\epsilon)$ (Ding et al. ,, 2020a; Paternain et al. ,, 2019a).
This is the first demonstration that nonconcave CMDP problems can attain the
complexity lower bound of $\mathcal{O}(1/\epsilon)$ for convex optimization
subject to convex constraints. Our primal-dual approach and non-asymptotic
analysis are agnostic to the RL optimizer used, and thus are more flexible for
practical applications. More generally, our approach also serves as the first
algorithm that provably accelerates constrained nonconvex optimization with
zero duality gap by exploiting the geometries such as the gradient dominance
condition, for which the existing acceleration methods for constrained convex
optimization are not applicable.

##  1 Introduction

In reinforcement learning (RL), an agent interacts with a stochastic
environment over time in order to maximize its expected accumulated reward
(Sutton & Barto,, 2018). In many practical applications such as autonomous
driving (Fisac et al. ,, 2018) and robotics (Ono et al. ,, 2015), it is also
critical for an agent to meet certain safety constraints, for example, an
accumulated utility should be kept above a given threshold (or equivalently an
accumulated cost should be kept below a given threshold). Such safe RL
problems (Garcıa & Fernández,, 2015) are commonly formulated as constrained
Markov decision processes (CMDPs) (Altman,, 1999). One method used widely in
practice is the primal-dual approach, which constructs a Lagrangian function
and then solves a minimax optimization problem respectively over dual
variables and the policy.

Various algorithms have been proposed based on the primal-dual approach
(Tessler et al. ,, 2018; Ding et al. ,, 2020b; Stooke et al. ,, 2020; Yu et
al. ,, 2019; Achiam et al. ,, 2017; Yang et al. ,, 2019; Altman,, 1999).
Theoretically, two recent studies (Paternain et al. ,, 2019a) and (Ding et al.
,, 2020a) showed that algorithms with alternating updates between policy
optimization over the policy and gradient descent over dual variables achieve
the computational complexity of $\mathcal{O}(1/\epsilon^{2})$ to attain an
$\epsilon$-accurate solution (in terms of duality gap in (Paternain et al. ,,
2019a), and both the optimality gap and constraint violation in (Ding et al.
,, 2020a)). Such a complexity result appears natural, because the CMDP problem
has a nonconcave optimization objective with nonconcave constraints. However,
recent understanding about (C)MDPs does suggest a promise for a better rate.
Several recent studies (Mei et al. ,, 2020b; Agarwal et al. ,, 2020; Bhandari
& Russo,, 2020; Cen et al. ,, 2020) on policy gradient (PG) approaches showed
that they can attain global optimum with as fast as linear convergence rate,
which suggest that MDP objective has better geometry in nature beyond
nonconcavity. These optimistic insights thus motivate us to aim at a more
ambitious goal of achieving the lower bound $\mathcal{O}(1/\epsilon)$ on the
computational complexity given by (Ouyang & Xu,, 2019; Nemirovsky,, 1992) for
convex optimization with convex constraints. Therefore, the following
challenging but fundamental question is asked.

  * Despite the nonconcave objective function and nonconcave constraints, can we develop an approach for CMDP to achieve the complexity lower bound of $\mathcal{O}(1/\epsilon)$ for convex optimization with convex constraints?

We provide an affirmative answer to the above question. Specifically, we
develop a novel primal-dual approach for CMDP problems, and establish its non-
asymptotic global convergence guarantee with the desired complexity of
$\tilde{\mathcal{O}}(1/\epsilon)$, where the notation
$\tilde{\mathcal{O}}(\cdot)$ omits the dependence on logarithm terms.

Our approach can be naturally extended more broadly to the following nonconvex
functional constrained optimization problem, which includes the above CMDP
problem as a special case:

$\displaystyle\min_{x\in X}\;f_{0}(x),\quad\text{s.t.}\;\;f_{i}(x)\leq
0,\quad\text{for }i=1,\ldots,m,$ (1)

where $X\subseteq\mathbb{R}^{n}$ is a nonempty closed convex set and
$f_{i}(x),i=0,\ldots,m$ are nonconvex functions with $|f_{i}(x)|\leq
G,~{}\forall x\in X$. Existing literature on such a nonconvex constrained
problem is rather limited Boob et al. , (2019); Facchinei et al. , (2021);
Wang et al. , (2017), and all these studies provide only the guarantee to
stationary points. We generalize our approach to exploit geometric properties
that nonconvex constrained optimization may have such as the gradient
dominance condition, and show that our approach achieves a fast convergence
rate of $\tilde{\mathcal{O}}\left({1}/{\sqrt{\epsilon}}\right)$ with
guaranteed convergence to the global optimum.

###  1.1 Main Contributions

Our main contributions in this paper can be summarized as follows.

We propose a novel primal-dual approach, called Accelerated and Regularized
Constrained Policy Optimization (AR-CPO), for solving constrained MDPs. Our
AR-CPO approach includes a novel blend of three ingredients: (a) entropy
regularized policy optimizer, (b) dual variable regularizer, and (c)
Nesterov’s accelerated gradient descent dual optimizer, each of which is
necessary and indispensable for attaining the improved complexity.

We show that AR-CPO attains an $\epsilon$-accurate optimal policy with
$\epsilon$-level constraint violation with a computational complexity of
$\tilde{\mathcal{O}}(1/\epsilon)$, which improves the best known complexity of
$\mathcal{O}(1/\epsilon^{2})$ for the primal-dual approaches in Ding et al. ,
(2020a); Paternain et al. , (2019a) by a factor of $\mathcal{O}(1/\epsilon)$.
Interestingly, our result achieves the complexity lower bound for convex
optimization with convex constraints up to a logarithmic dependence on
$\epsilon$, although CMDP has nonconcave objective and nonconcave constraints.

Our technical analysis includes the following new developments. (a) To prove
that the entropy-regularized dual function is smooth, our analysis involves a
novel application of Mitrophanov’s perturbation bound (Mitrophanov,, 2005) for
showing that the visitation measure is Lipschitz with respect to (w.r.t.) the
policy and further technical arguments that the optimal policy for the
entropy-regularized MDP is Lipschitz w.r.t. its reward function and hence the
dual variable. (b) Our analysis of Nesterov’s accelerated gradient descent
dual optimizer is non-trivial and is significantly different from the
Nesterov’s analysis for minimization problems. (c) We exploit the first-order
optimality condition of the dual variable update, and establish an upper bound
on the optimality gap and constraint violation using dual variable updates.

We further extend our approach to accelerate a class of nonconvex functional
constrained optimization problems with zero duality gap (see eq. 1). By
exploiting the geometric properties such as the gradient dominance condition,
our approach achieves the $\mathcal{O}\left({1}/{\sqrt{\epsilon}}\right)$ rate
of convergence to the global optimum, which also matches the lower bound of
smooth convex optimization up to some logarithmic factor. This is the first
global convergence guarantee for nonconvex constrained optimization in the
literature.

###  1.2 Related Works

Primal-dual approach to CMDP. The primal-dual approach is a popular method to
solve the CMDP problem. Based on such an approach, various algorithms have
been proposed (Tessler et al. ,, 2018; Ding et al. ,, 2020b; Stooke et al. ,,
2020; Yu et al. ,, 2019; Achiam et al. ,, 2017; Yang et al. ,, 2019; Altman,,
1999). On the theory side, (Tessler et al. ,, 2018) provided an asymptotic
convergence analysis for primal-dual method and established a local
convergence guarantee under certain stability assumptions. (Paternain et al.
,, 2019a) showed that the primal-dual method achieves zero duality gap. (Ding
et al. ,, 2020b) proposed a primal-dual type proximal policy optimization
(PPO) and established the regret bound for linear CMDP. More recently, (Ding
et al. ,, 2020a) provided a finite-time analysis for an alternating updating
algorithm between natural policy gradient and project gradient descent. Both
(Paternain et al. ,, 2019a) and (Ding et al. ,, 2020a) showed that the
existing common primal-dual framework achieves the complexity order of
$\mathcal{O}(1/\epsilon^{2})$. This paper proposes a new primal-dual approach,
which enhances such a complexity order by a factor of
$\mathcal{O}(1/\epsilon)$.

Other approaches to CMDP. In addition to the primal-dual approaches, other
methods have also been proposed to solve the CMDP problem. Notably, (Liu et
al. ,, 2019b) developed an interior point method, which applies logarithmic
barrier functions for CMDP. (Chow et al. ,, 2018, 2019) leveraged Lyapunov
functions to handle constraints. (Dalal et al. ,, 2018) introduced a safety
layer to the policy network to enforce constraints. None of these methods is
provably convergent to an optimal feasible policy. Recently, (Xu et al. ,,
2020b) proposed a new primal approach which alternatively updates between
policy maximization and constraint descent (if violated). Such an algorithm
has been shown to converge to the optimal policy.

Global optimality of policy optimization. In the unconstrained setting, recent
studies have established the global convergence of policy optimization
algorithms despite the nonconvexity of the objective. For general MDPs, it has
been shown that both policy gradient and natural policy gradient converge to
the global optimal policy in the tabular or function approximation setting
Agarwal et al. , (2019); Wang et al. , (2019); Liu et al. , (2019a); Xu et al.
, (2020a). For regularized MDP, entropy regularizer has been widely used for
designing RL algorithms (Williams & Peng,, 1991; Peters et al. ,, 2010; Mnih
et al. ,, 2016; Duan et al. ,, 2016; Haarnoja et al. ,, 2018; Hazan et al. ,,
2019; Xiao et al. ,, 2019). The theoretical performance of such designed
algorithms have recently been characterized. The regularized MDP problem has
been studied in Nachum et al. , (2017), in which the authors revealed the
connection between the optimal value function and optimal policy, see also
Shani et al. , (2020); Agarwal et al. , (2020); Mei et al. , (2020a); Cen et
al. , (2020). Linear convergence of policy gradient methods for both
regularized and general MDP problems has been recently established in Lan,
(2021).

Nonconvex constrained optimization. The studies that deal with the nonconvex
functional constraints in eq. 1 appear to be scarce and only recently. In
Facchinei et al. , (2021); Wang et al. , (2017), the authors treat such a
problem using penalty methods with first order oracles, where the convergence
established is to stationary points. In Boob et al. , (2019) the problem is
decomposed into a series of strongly convex constrained optimization
subproblems by adding sequentially designed strongly convex regularizers.
Convergence to stationary points was shown under certain conditions. Our study
exploits the geometries that nonconvex functions can have to design an
algorithm that achieves the global optimum. Note that existing analysis on
convex constrained optimization cannot be applicable for establishing such a
result (see Section 2 of Boob et al. , (2019) and references therein).

##  2 Preliminaries

###  2.1 Markov Decision Process

A Markov decision process (MDP) is determined by a five-tuple
$(\mathcal{S},\mathcal{A},\mathsf{P},r,\gamma)$, where $\mathcal{S}$ is the
state space, $\mathcal{A}$ is the action space, $\mathsf{P}$ is the transition
kernel, $r$ is the reward function and $\gamma\in(0,1)$ is the discount
factor. Assume that $\mathcal{S}$ and $\mathcal{A}$ are finite with
cardinality $|\mathcal{S}|$ and $|\mathcal{A}|$, respectively. At any time
$t\in\mathbb{N}_{+}$, an agent takes an action $a_{t}\in\mathcal{A}$ at state
$s_{t}\in\mathcal{S}$, and then the environment transits to the next state
$s_{t+1}$ according to the distribution $\mathsf{P}(s_{t}|s_{t-1},a_{t-1})$.
At the same time, the agent receives a reward of $r(s_{t},a_{t})$. We assume
that the initial state $s_{0}$ follows a distribution $\rho$. The goal is to
maximize the expected accumulated discounted reward:
$\mathbb{E}[\sum_{t=0}^{\infty}\gamma^{t}r(s_{t},a_{t})]$. A stationary policy
maps a state $s\in\mathcal{S}$ to a distribution $\pi(\cdot|s)$ over
$\mathcal{A}$, which does not depend on time $t$.

For a given policy $\pi$, we define its value function for any initial state
$s\in\mathcal{S}$ as
$V_{r}^{\pi}(s)\coloneqq\mathbb{E}[\sum_{t=0}^{\infty}\gamma^{t}r(s_{t},a_{t})|s_{0}=s,a_{t}\sim\pi(a_{t}|s_{t}),s_{t+1}\sim\mathsf{P}(\cdot|s_{t},a_{t})].$
We further take the expectation with respect to the distribution of the
initial state, and define the expected reward by following policy $\pi$ as
$V_{r}^{\pi}(\rho)\coloneqq\mathbb{E}_{s_{0}\sim\rho}[V_{r}^{\pi}(s_{0})]$. We
define the discounted state-action visitation distribution $\nu_{\rho}^{\pi}$
as follows:
$\nu_{\rho}^{\pi}(s,a)\coloneqq(1-\gamma)\sum_{t=0}^{\infty}\gamma^{t}\mathrm{Pr}\big{\\{}s_{t}=s,a_{t}=a\big{|}s_{0}\sim\rho,a_{t}\sim\pi(\cdot|s_{t}),s_{t+1}\sim\mathsf{P}(\cdot|s_{t},a_{t})\big{\\}},$
for any $s\in\mathcal{S}$, $a\in\mathcal{A}$. The value function thus can be
equivalently written as

$\displaystyle
V_{r}^{\pi}(\rho)=\frac{\sum_{s\in\mathcal{S},a\in\mathcal{A}}\nu_{\rho}^{\pi}(s,a)r(s,a)}{1-\gamma}=\frac{\langle\nu_{\rho}^{\pi},r\rangle_{\mathcal{S}\times\mathcal{A}}}{1-\gamma},$

where $\langle\cdot,\cdot\rangle_{\mathcal{S}\times\mathcal{A}}$ denotes the
inner product over the space $\mathcal{S}\times\mathcal{A}$ by reshaping
$\nu_{\rho}^{\pi}$ and $r$ as $|\mathcal{S}|\times|\mathcal{A}|$-dimensional
vectors, and we omit the subscripts and use $\langle\cdot,\cdot\rangle$ when
there is no confusion.

###  2.2 Constrained MDP

The CMDP has exactly the same dynamic as the general MDP except the reward is
an $(m+1)$-dimensional vector. Specifically, taking action $a\in\mathcal{A}$
at state $s\in\mathcal{S}$, the agent receives a vector of rewards,
${r}(s,a)=[r_{0}(s,a),r_{1}(s,a),\ldots,r_{m}(s,a)]^{\top}$. For each reward
function $r_{i}$, $i=0,1,\ldots,m$, we assume that it is positive and finite.
We let
$r_{i,\max}\coloneqq\max_{s\in\mathcal{S},a\in\mathcal{A}}\\{r_{i}(s,a)\\}$,
for $i=0,1,...,m$, and let
$R_{\max}\coloneqq\sqrt{\sum_{i=1}^{m}r_{i,\max}^{2}}$. We define the value
function with respect to the $i$-th component of the reward vector ${r}$ as
follows
$V_{i}^{\pi}(s)\coloneqq\mathbb{E}[\sum_{t=0}^{\infty}\gamma^{t}r_{i}(s_{t},a_{t})|s_{0}=s,a_{t}\sim\pi(a_{t}|s_{t}),s_{t+1}\sim\mathsf{P}(\cdot|s_{t},a_{t})],$
for $i=0,1,...,m$. Similarly, we define
$V^{\pi}_{i}(\rho)=\mathbb{E}_{s_{0}\sim\rho}[V_{i}^{\pi}(s_{0})]$. The
objective of the constrained MDP is to solve the following constrained
optimization problem:

$\displaystyle\max_{\pi\in\Pi}\quad$ $\displaystyle V_{0}^{\pi}(\rho)$
$\displaystyle s.t.\quad$ $\displaystyle V^{\pi}_{i}(\rho)\geq c_{i},\quad
i=1,\ldots,m,$ (2)

where
$\Pi=\big{\\{}\pi\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}|}:\sum_{a\in\mathcal{A}}\pi(a|s)=1,\pi(a|s)\geq
0,$ $\forall(s,a)\in\mathcal{S}\times\mathcal{A}\big{\\}}$ is the set of all
stationary policies. In this paper, we focus on the case with direct
parameterization of the policy. Let $\pi^{*}$ denote the policy that attains
the optimum of the problem in eq. 2. We note that both the objective and
constraint functions are nonconcave in $\pi$ (Bhandari & Russo,, 2019; Agarwal
et al. ,, 2020), which makes the problem challenging.

Our goal is to solve the CMDP problem in eq. 2 and find an $\epsilon$-optimal
policy defined as follows.

###### Definition 1

A policy $\tilde{\pi}$ is said to be $\epsilon$-optimal if its corresponding
optimality gap and the constraint violation satisfy

$\displaystyle V_{0}^{*}(\rho)-V^{\tilde{\pi}}_{0}(\rho)\leq\epsilon;\text{and
}\|({c}-{V}^{\tilde{\pi}}(\rho))_{+}\|_{1}\leq\epsilon,$ (3)

where $V_{0}^{*}(\rho)$ is the optimal value of eq. (2),
${V}^{\tilde{\pi}}(\rho):=[{V}_{1}^{\tilde{\pi}}(\rho),...,{V}_{m}^{\tilde{\pi}}(\rho)]^{\top}$
and ${c}:=[c_{1},...,c_{m}]^{\top}$.

We note that this is a stronger performance guarantee than the metric of the
duality gap in (Paternain et al. ,, 2019a).

###  2.3 Notations

Given a vector ${x}\in\mathbb{R}^{m}$, denote its $i$-th entry by ${x}_{i}$.
Let $\|{x}\|_{1}\coloneqq\sum_{i=1}^{m}|{x}_{i}|$,
$\|{x}\|_{2}\coloneqq\sqrt{\sum_{i=1}^{m}{x}_{i}^{2}}$ and
$\|x\|_{\infty}:=\max_{i}|x_{i}|$ denote the $\ell_{1}$, $\ell_{2}$ and
$\ell_{\infty}$ norms respectively. Let $(\cdot)_{+}$ be the entry-wise
rectified linear function, i.e., given ${x}$, the $i$-th entry of $({x})_{+}$
is $\max\\{0,{x}_{i}\\}$. Given two vectors $x$ and $y$, we use $\langle
x,y\rangle$ or $x^{\top}y$ to denote the inner product. We say $x\succeq y$,
if and only if $x_{i}\geq y_{i}$, for all $i=1,\ldots,m$. Let $\mathbf{1}$ be
the $m$-dimensional all-one vector. Given two functions $f(x)$ and $g(x)$,
$f(x)=\mathcal{O}(g(x))$ if there exists some constant $a>0$, such
that$f(x)\leq ag(x)$ for all $x$; and $f(x)=\tilde{\mathcal{O}}(g(x))$ if
there exists some constant $a>0$ and $n\in\mathbb{N}$, such that $f(x)\leq
ag(x)\log^{n}(g(x))$ for all $x$. Let $[T]$ denote the set $\\{1,2,...,T\\}$.

##  3 A Novel Primal-Dual Approach to CMDP

###  3.1 Existing Primal-Dual Approach

Algorithm 1 Existing Primal-Dual Approach

1:Input: $\eta$.

2:Initialize: $\lambda_{0}=0$, $\pi_{0}=0$.

3:for $t=0,1,...,T$ do

4: Compute $\pi_{t+1}$ based on $\mathcal{L}(\pi,\lambda_{t})$ and $\pi_{t}$
via a policy optimization method.

5: Compute the dual ascent step
$\lambda_{k+1}=(\lambda_{k}-\eta(V^{\pi_{t+1}}(\rho)-c))_{+}$.

6:end for

A popular method to solve the CMDP problem in eq. 2 is the primal-dual
approach. The idea is to solve the following minimax problem over a
constructed Lagrangian function given by

$\displaystyle\min_{\lambda\in\mathbb{R}^{m}_{+}}\max_{\pi\in\Pi}\mathcal{L}(\pi,\lambda)$
$\displaystyle:=V_{0}^{\pi}(\rho)+\sum_{i=1}^{m}\lambda_{i}(V^{\pi}_{i}(\rho)-c_{i})$
$\displaystyle~{}=V_{0}^{\pi}(\rho)+\langle\lambda,V^{\pi}(\rho)-c\rangle,$
(4)

where $\lambda=[\lambda_{1},...,\lambda_{m}]^{\top}$ denotes the dual variable
vector, $V^{\pi}(\rho)=[V^{\pi}_{1}(\rho),\ldots,V^{\pi}_{m}(\rho)]^{\top}$
denotes the vector of constraints and $c=[c_{1},\ldots,c_{m}]^{\top}$ denotes
the vector of constraint thresholds.

The problem in eq. 4 is commonly solved via a general algorithmic framework
summarized in Algorithm 1, which alternatively updates the policy via a policy
optimization RL algorithm and the dual variable $\lambda$ via a projected
gradient descent. Under such a framework, existing primal-dual algorithms can
have various designs. For example, in (Ding et al. ,, 2020a), a natural policy
gradient is adopted for the policy update, and in (Paternain et al. ,, 2019a),
the RL algorithm for updating the policy is not specified, but each update
needs to find an approximate solution to
$\max_{\pi\in\Pi}\mathcal{L}(\pi,\lambda_{t})$.

Recent theoretical studies have shown that the primal-dual approach in
Algorithm 1 achieves the convergence rate of $\mathcal{O}(1/\sqrt{T})$, which
corresponds to the computational complexity of
$\mathcal{O}({1}/{\epsilon^{2}})$ to either attain an $\epsilon$-accurate
duality gap with a RL policy optimizer (Paternain et al. ,, 2019a), or to
attain an $\epsilon$-accurate optimality gap and $\epsilon$-level constraint
violation with a natural policy gradient algorithm (Ding et al. ,, 2020a).

###  3.2 AR-CPO: A New Primal-Dual Approach

Algorithm 2 AR-CPO: A New Primal-Dual Approach

1:Input: $T$, stepsizes $\eta$, $\alpha$ and $q$, regularization parameters
$\tau$ and $\mu$, accuracy $\delta$, and projection radius $B$

2:Initialize: $\lambda_{0}=0$, $\bar{\lambda}_{0}=0$

3:for $t=1,...,T$ do

4: $\underline{\lambda}_{t}\leftarrow(1-q)\bar{\lambda}_{t-1}+q\lambda_{t-1}$

5: $\pi_{t}\leftarrow\mathrm{RegPO}(\delta,\underline{\lambda}_{t},\tau)$

6:
$\widehat{\nabla}d_{\tau,\mu}(\underline{\lambda}_{t})\leftarrow{V}^{\pi_{t}}(\rho)-c+\mu\underline{\lambda}_{t}$

7:
$\lambda_{t}\leftarrow\operatorname*{arg\,min}_{\lambda\in\Lambda}\big{\\{}\eta[\langle\widehat{\nabla}d_{\tau,\mu}(\underline{\lambda}_{t}),\lambda\rangle+\frac{\mu}{2}\|\lambda-\underline{\lambda}_{t}\|_{2}^{2}]+\frac{1}{2}\|\lambda-\lambda_{t-1}\|^{2}_{2}\big{\\}}$,
$\qquad\textrm{where }\Lambda=\\{\lambda\in\mathbb{R}_{+}^{m}:\lambda_{i}\leq
2B,i=1,\dots,m\\}$

8:
$\bar{\lambda}_{t}\leftarrow(1-\alpha)\bar{\lambda}_{t-1}+\alpha\lambda_{t}$

9:end for

10:Output: $\tilde{\pi}$, where for any given $a\in\mathcal{A}$ and
$s\in\mathcal{S}$ $\tilde{\pi}$ is defined as
$\displaystyle\tilde{\pi}(a|s)=\tfrac{(1-\alpha)^{T-1}\nu_{\rho}^{\pi_{1}}(s,a)+\sum\nolimits_{t=2}^{T}\alpha(1-\alpha)^{T-t}\nu_{\rho}^{\pi_{t}}(s,a)}{(1-\alpha)^{T-1}\chi^{\pi_{1}}_{\rho}(s)+\sum\nolimits_{t=2}^{T}\alpha(1-\alpha)^{T-t}\chi_{\rho}^{\pi_{t}}(s)},$
where
$\chi_{\rho}^{\pi}(s)=\textstyle{\sum}_{a^{\prime}\in\mathcal{A}}\nu_{\rho}^{\pi}(s,a^{\prime})$.

One prominent drawback of the existing primal-dual approach in Algorithm 1 is
that the overall complexity is dominated by the minimization over the dual
function, namely
$\min_{\lambda}d(\lambda):=\max_{\pi\in\Pi}\mathcal{L}(\pi,\lambda).$ Since
$d(\lambda)$ is nonsmooth due to the maximization over $\pi$, the (projected)
gradient descent over $\lambda$ decays only at the rate of
$\mathcal{O}(1/\sqrt{T})$, although the RL policy optimizer typically achieves
a much faster rate of $\mathcal{O}(1/T)$. Hence, the overall complexity is
only $\mathcal{O}({1}/{\epsilon^{2}})$.

In this paper, we propose a novel primal-dual approach, which we call as
Accelerated and Regularized Constrained Policy Optimizer (AR-CPO), and is
summarized in Algorithm 2. The central idea is to solve the minimax problem
over the $(\tau,\mu)$-regularized Lagrangian via an accelerated dual descent:

$\displaystyle\min_{\lambda\in\mathbb{R}^{m}_{+}}\max_{\pi\in\Pi}\mathcal{L}_{\tau,\mu}(\pi,\lambda)\coloneqq\mathcal{L}(\pi,\lambda)+\tau\mathcal{H}(\pi)+\frac{\mu}{2}\|\lambda\|_{2}^{2},$
(5)

where
$\mathcal{H}(\pi)=-\mathbb{E}\big{[}\sum_{t=0}^{\infty}\gamma^{t}\log(\pi(a_{t}|s_{t}))\big{|}s_{0}=s,a_{t}\sim\pi(a_{t}|s_{t}),s_{t+1}\sim\mathsf{P}(\cdot|s_{t},a_{t})\big{]}$
is the discounted entropy of the policy $\pi$, and $\tau,\mu\geq 0$ are
regularization constants.

Compared to the existing primal-dual approach in Algorithm 1, AR-CPO consists
of three new components, which collectively yield the improved complexity of
$\mathcal{O}({1}/{\epsilon})$.

(a) Entropy-regularized policy optimizer. The entropy regularizer
$\tau\mathcal{H}(\pi)$ in eq. 5 plays a critical role to smooth the dual
function defined as
$d_{\tau,\mu}(\lambda):=\max_{\pi\in\Pi}\mathcal{L}_{\tau,\mu}(\pi,\lambda)$,
which is shown in 1 in Appendix C. Thus, the dual problem
$\min_{\lambda\in\mathbb{R}^{m}_{+}}d_{\tau,\mu}(\lambda)$ becomes
minimization over a smooth objective, which (together with items (b) and (c)
to be introduced) can enjoy a better convergence rate and an enhanced
complexity order.

To obtain the dual function, i.e., to solve
$\max_{\pi\in\Pi}\mathcal{L}_{\tau,\mu}(\pi,\lambda)$ for any given $\lambda$,
it can be observed that such a problem is equivalent to the maximization of an
entropy-regularized value function corresponding to a reward function
$r_{\lambda}\coloneqq r_{0}+\sum_{i=1}^{m}\lambda_{i}r_{i}$, which is a linear
combination of the rewards. Therefore, many entropy-regularized policy
optimizers can be applied here, and in Algorithm 2,
$\text{RegPO}(\delta,\lambda,\tau)$ represents such a generic optimizer that
learns an optimal policy for the entropy-regularized MDP with reward
$r_{\lambda}$ up to $\delta$-accuracy. We give two example RegPOs in Appendix
A: RegPO-NPG based on natural policy gradient method and RegPO-SoftQ based on
soft Q-learning.

In this paper, we focus on the deterministic case and assume that RegPO has
the access to an MDP oracle that provides the expected value for an update,
such as exact policy gradient in RegPO-NPG or soft Bellman operator in RegPO-
SoftQ. Thus, the computational complexity is measured by the number of queries
of such an oracle. Due to the regularization of MDP, each call of the
optimizer RegPO $(\delta,\lambda,\tau)$ requires
$\mathcal{O}(\log(1/(\delta\tau)))=\mathcal{O}(\log({1}/{\epsilon}))$ queries
of the MDP oracle (see Appendix A for more details).

(b) $\ell_{2}$ regularization on $\lambda$. We further introduce an
$\ell_{2}$-regularizer $\frac{\mu}{2}\|\lambda\|_{2}^{2}$ on the dual variable
$\lambda$ in eq. 5 so that the dual function $d_{\tau,\mu}(\lambda)$ becomes a
strongly convex function with respect to $\lambda$. This design, together with
the following Nesterov’s accelerated gradient method for updating $\lambda$,
will yield the enhanced complexity order.

(c) Nesterov’s accelerated gradient descent dual optimizer. We further adopt a
variant of Nesterov’s accelerated gradient descent method, which is discussed
in (Lan,, 2020, Section 3.3), for the update of the dual variable $\lambda$.
In contrast to the gradient descent method, such an acceleration method builds
up a lower approximation $d_{\tau,\mu}(\underline{\lambda}_{t})+\langle\nabla
d_{\tau,\mu}(\underline{\lambda}_{t}),\lambda-\underline{\lambda}_{t}\rangle+\tfrac{\mu}{2}\|\underline{\lambda}_{t}-\lambda\|_{2}^{2}$
of the objective function at the search point ${\underline{\lambda}_{t}}$,
which is a weighted average of iterates $\\{\lambda_{t}\\}$. This approach
will improve the dependence on the condition number so that the convergence
rate is $\left(1-\sqrt{\mu/L_{d}}\right)^{T}$, where $L_{d}$ is the smoothness
parameter of the dual function (will be formally defined later in 1). As will
be shown in Section 4, if we choose the regularization constant as
$\mu,\tau=\mathcal{O}(\epsilon)$ so that $L_{d}=\mathcal{O}({1}/{\epsilon})$,
then $T=\tilde{\mathcal{O}}({1}/{\epsilon})$ iterations yield an
$\epsilon$-accurate optimality gap and $\epsilon$-level violation. Thus, we
achieve an overall complexity of $\tilde{\mathcal{O}}({1}/{\epsilon})$, which
improves the existing primal-dual approach by a factor of
$\tilde{\mathcal{O}}({1}/{\epsilon})$. Note that without the acceleration, the
vanilla gradient decent update for $\lambda$ does not yield the improved
complexity order.

##  4 Convergence Rate and Optimality

In this section, we present the global convergence and complexity of Algorithm
2.

###  4.1 Main Results

We first state our technical assumptions that are commonly used in the
literature of optimization and reinforcement learning theory.

######  Assumption 1 (Slater Condition)

There exists a constant $\xi\in\mathbb{R}_{+}$, and at least one policy
$\pi_{\xi}\in\Pi$, such that for all $i=1,\ldots,m,$ $V_{i}^{\pi_{\xi}}\geq
c_{i}+\xi$.

The Slater condition is easy to satisfy in practice, as we usually has one
policy that is strictly feasible, i.e., all the constraints are satisfied
strictly.

######  Assumption 2 (Uniform Ergodicity)

For any $\lambda\in\Lambda$, the Markov chain induced by the policy
$\pi^{*}_{\tau,\lambda}$ and the Markov transition kernel is uniformly
ergodic, i.e., there exist constants $C_{M}>0$ and $0<\beta<1$ such that for
all $t\geq 0$,

$\sup_{s\in\mathcal{S}}\textrm{d}_{TV}\left(\mathbb{P}(s_{t}\in\cdot|s_{0}=s),\chi_{\pi^{*}_{\tau,\lambda}}\right)\leq
C_{M}\beta^{t},$

where $\pi^{*}_{\tau,\lambda}$ is the solution to
$\max_{\pi\in\Pi}\mathcal{L}_{\tau,\mu}(\pi,\lambda)$,
$\chi_{\pi^{*}_{\tau,\lambda}}$ is the stationary distribution of the MDP
induced by policy $\pi^{*}_{\tau,\lambda}$, and
$\textrm{d}_{TV}\left(\cdot,\cdot\right)$ is the total variation distance.

Note that a Markov chain is uniformly ergodic if it is irreducible (i.e.,
possibly gets to any state from any state) and aperiodic (Levin & Peres,,
2017). As for any $\lambda$, $\pi^{*}_{\tau,\lambda}$ is the optimal policy
for the entropy-regularized MDP with the reward $r_{\lambda}$, and is
therefore a softmax policy (Nachum et al. ,, 2017), which takes any action
with non-zero probability. Therefore, Assumption 2 can be easily satisfied in
practice.

The following theorem characterizes the global convergence of Algorithm 2 in
terms of the optimality gap $V_{0}^{*}(\rho)-V_{0}^{\tilde{\pi}}(\rho)$ and
the constraint violation $({c}-{V}^{\tilde{\pi}}(\rho))_{+}$. The complete
proof is provided in Appendix C.

###### Theorem 1

Consider AR-CPO in Algorithm 2. Suppose Assumptions 1 and 2 hold and we choose

$\displaystyle\alpha=\sqrt{\tfrac{\mu}{2L_{d}}},~{}q=\tfrac{2\alpha-\mu/L_{d}}{2-\mu/L_{d}},~{}\text{and}~{}\eta=\tfrac{\alpha}{\mu(1-\alpha)},$
(6)

where $L_{d}:=\frac{2R_{\max}^{2}L_{\nu}}{(1-\gamma)^{2}\tau}+\mu$ is the
smoothness parameter of the dual function, and
$L_{\nu}\coloneqq\lceil\log_{\beta}(C_{M}^{-1})\rceil+(1-\beta)^{-1}+1$. Then
we have the following convergence guarantee of the optimality gap and the
constraint violation:

$\displaystyle\quad V_{0}^{*}(\rho)-V^{\tilde{\pi}}_{0}(\rho)$
$\displaystyle\leq\zeta_{T}\left(\tfrac{2R_{\max}}{1-\gamma}+\tfrac{2\sqrt{m}B}{\eta}\right)+\sqrt{\tfrac{2L_{d}}{\mu}}\max_{t\in[T]}|\Delta_{t}|$
$\displaystyle\quad+\tfrac{\tau\log|\mathcal{A}|}{1-\gamma}+6\mu mB^{2},$
(optimality gap) $\displaystyle\quad\|({c}-{V}^{\tilde{\pi}}(\rho))_{+}\|_{1}$
$\displaystyle\leq\zeta_{T}\left(\tfrac{2R_{\max}}{(1-\gamma)B}+\tfrac{2\sqrt{m}}{\eta}\right)+\sqrt{\tfrac{2L_{d}}{\mu}}\tfrac{\max_{t\in[T]}|\Delta_{t}|}{B}$
$\displaystyle\quad+\tfrac{\tau\log|\mathcal{A}|}{(1-\gamma)B}+6\mu
mB+2\left(1-\sqrt{\tfrac{\mu}{2L_{d}}}\right)^{T-1}\tfrac{\sqrt{m}R_{\max}}{1-\gamma},$

where

$\displaystyle\zeta_{T}:$
$\displaystyle=2\left(1-\sqrt{\tfrac{\mu}{2L_{d}}}\right)^{\frac{T}{2}}\sqrt{\eta
K_{0}(\lambda^{*}_{\tau,\mu})}$
$\displaystyle\quad+\sqrt{8\eta\sqrt{m}B\max_{t\in[T]}\|\delta_{t}\|_{2}},$

$\lambda_{\tau,\mu}^{*}:=\operatorname*{arg\,min}_{\lambda\in\mathbb{R}^{m}_{+}}d_{\tau,\mu}(\lambda)$,
$\Delta_{t}:=V_{0}^{\pi^{*}_{\tau,\underline{\lambda}_{t}}}(\rho)+\underline{\lambda}_{t}^{\top}({V}^{\pi^{*}_{\tau,\underline{\lambda}_{t}}}(\rho)-c)-[V_{0}^{\pi_{t}}(\rho)+\underline{\lambda}_{t}^{\top}({V}^{\pi_{t}}(\rho)-c)]$,
$B=\tfrac{r_{0,\max}}{(1-\gamma)\xi}$, $K_{0}(\lambda)\coloneqq
d_{\tau,\mu}(\bar{\lambda}_{0})-d_{\tau,\mu}(\lambda)+\tfrac{\alpha}{2}(\mu+\tfrac{1}{\eta})\|\lambda_{0}-\lambda\|_{2}^{2}$,
and
$\delta_{t}\coloneqq\widehat{\nabla}d_{\tau,\mu}(\underline{\lambda}_{t})-\nabla
d_{\tau,\mu}(\underline{\lambda}_{t})$.

1 indicates that the optimality gap is bounded by an exponential decaying term
with the convergence rate $\left(1-\sqrt{{\mu}/({2L_{d}})}\right)^{T}$. This
is a faster convergence due to the acceleration of the dual variable than the
convergence of a simple gradient descent, whose convergence rate is
$\left(1-{\mu}/{L_{d}}\right)^{T}$. Furthermore, the parameter $L_{d}$ of the
dual function plays an important role here, because a smoother dual function
with a smaller $L_{d}$ yields a faster convergence. The bound also contains
other terms captured by the regularization parameters $\tau$ and $\mu$, and
the convergence errors $\max|\Delta_{t}|$ and $\max\|\delta_{t}\|_{2}$ of the
entropy-regularized policy optimizer RegPO. All these terms can be controlled
to be below any required accuracy $\epsilon$. The constraint violation is also
bounded via the terms that have the same nature.

In the above theorem, the optimality gap and constraint violation are bounded
in terms of the regularization parameters, the number of iterations $T$, the
convergence errors of RegPO, which can be jointly chosen properly to guarantee
the required $\epsilon$-accurate optimality gap and $\epsilon$-level
constraint violation. In the following corollary, we present the overall
complexity to converge to such an $\epsilon$-optimal policy. Its proof is
given in Section C.4.

###### Corollary 1

With a total computational complexity of
$\tilde{\mathcal{O}}({1}/[{(1-\gamma)^{3.5}\epsilon}])$, Algorithm 2 outputs
an $\epsilon$-optimal policy with respect to both the optimality gap and
constraint violation.

##  5 Generalization to Constrained Nonconvex Optimization with zero duality
gap

In this section, we extend our approach to accelerate a class of generic
constrained nonconvex optimization problems. Our approach is the first that
can accelerate convergence of constrained nonconvex optimization to global
optimum under certain geometries.

Recall the problem defined in eq. 1. Consider the dual function defined below:

$\displaystyle d(\lambda):=\min_{x\in
X}\mathcal{L}(x,\lambda),\quad\text{and}\quad
d^{*}:=\max_{\lambda\in\mathbb{R}_{+}^{m}}d(\lambda),$

where $\mathcal{L}(x,\lambda):=f_{0}(x)+\sum_{i=1}^{m}\lambda_{i}f_{i}(x)$ is
the Lagrangian. Let $\lambda:=[\lambda_{1},...,\lambda_{m}]^{\top}$ denote the
dual variable vector, and let $f(x):=[f_{1}(x),...,f_{m}(x)]^{\top}$ denote
the constraints.

As suggested in our AR-CPO algorithm, we further introduce an $\ell_{2}$
perturbation denoted by
$d_{\mu}(\lambda):=d(\lambda)-\tfrac{\mu}{2}\|\lambda\|^{2}$ and
$\lambda_{\mu}^{*}:=\operatorname*{arg\,max}_{\lambda\in\mathbb{R}_{+}^{m}}d_{\mu}(\lambda)$.
We consider a class of constrained nonconvex optimization problem satisfying
the following assumptions on the geometry.

######  Assumption 3 (Strong Duality)

Strong duality holds for eq. 1, i.e. $f_{0}^{*}=d^{*}$.

######  Assumption 4 (Dual Function Smoothness)

$d(\lambda)$ is $L$-smooth:
$~{}\forall\lambda,\lambda^{\prime}\in\mathbb{R}_{+}^{m},$

$\displaystyle\|\nabla d(\lambda)-\nabla
d(\lambda^{\prime})\|_{2}=\|f(x_{\lambda}^{*})-f(x_{\lambda^{\prime}}^{*})\|_{2}\leq
L\|\lambda-\lambda^{\prime}\|_{2},$

where $x_{\lambda}^{*}:=\operatorname*{arg\,min}_{x\in
X}\mathcal{L}(x,\lambda)$ and
$x_{\lambda^{\prime}}^{*}:=\operatorname*{arg\,min}_{x\in
X}\mathcal{L}(x,\lambda^{\prime})$. Consequently, $d_{\mu}(\lambda)$ is
$\tilde{L}$-smooth, where $\tilde{L}:=L+\mu$.

Assumption 4 requires that the Lagrangian has a unique solution in terms of
$x$ when $\lambda$ is fixed. For a general nonconvex problem, Assumption 4 can
be guaranteed if the Lagrangian satisfies the gradient dominance condition.

######  Assumption 5 (Slater’s Condition)

There exists a constant $\xi\in\mathbb{R}_{+}$, and at least one $x_{\xi}\in
X$, such that for all $i=1,\ldots,m,$ $f_{i}(x_{\xi})\leq-\xi$.

Given the assumptions above, we propose the Accelerated and Regularized
Constrained Optimizer (AR-CO), which is an extension of AR-CPO to general
constrained nonconvex optimization problems. The AR-CO shares the same
structure as the AR-CPO in Algorithm 2, and the difference lies in the update
of nonconvex variable $x$ and how to generate a final output when given
$x_{1},\ldots,x_{T}$. Specifically, the AR-CO algorithm replaces the steps
$5$, $6$ and $7$ in Algorithm 2 with the following steps $5^{\prime}$,
$6^{\prime}$ and $7^{\prime}$.

$\displaystyle x_{t}$
$\displaystyle\leftarrow\mathrm{LagOPT}(\delta,\underline{\lambda}_{t}),$
(step $5^{\prime}$)

where LagOPT denotes a nonconvex optimizer that can solve the Lagrangian to
any prescribed accuracy $\delta>0$ under parameter $\underline{\lambda}_{t}$,
which can be guaranteed if the Lagrangian satisfies the gradient dominance
condition.

$\displaystyle\widehat{\nabla}d(\underline{\lambda}_{t})\leftarrow
f(x_{t})-\mu\underline{\lambda}_{t}.$ (step $6^{\prime}$)

The step $7^{\prime}$ is the same as step $7$ except replacing
$\widehat{\nabla}d(\underline{\lambda}_{t})$ with
$-\widehat{\nabla}d(\underline{\lambda}_{t})$ instead, since the step is
ascent here. And also $B\coloneqq{G}/{\xi}$. For the output, we randomly pick
$\tilde{x}=x_{1}$ with probability $(1-\alpha)^{T-1}$ and $\tilde{x}=x_{i}$
with probability $\alpha(1-\alpha)^{T-i}$ for $i=2,\ldots,T$.

The following theorem characterizes the global convergence of AR-CO.

###### Theorem 2

Consider the AR-CO algorithm. Suppose Assumptions 4, 3 and 5 hold and we
choose $\alpha=\sqrt{\tfrac{\mu}{2\tilde{L}}}$,
$q=\tfrac{2\alpha-\mu/\tilde{L}}{2-\mu/\tilde{L}}$, and
$\eta=\tfrac{\alpha}{\mu(1-\alpha)}$. Then we have the following convergence
guarantee of the optimality gap and the constraint violation:

$\displaystyle\mathbb{E}[f_{0}(\tilde{x})]-f_{0}^{*}\leq~{}$
$\displaystyle\tilde{\zeta}_{T}\left(2\sqrt{m}G+\tfrac{2\sqrt{m}G}{\eta\xi}\right)$
$\displaystyle~{}+\sqrt{\tfrac{2\tilde{L}}{\mu}}\max_{t\in[T]}|\Delta_{t}|+\tfrac{6\mu
mG^{2}}{\xi^{2}},$ (optimality gap)
$\displaystyle\|\mathbb{E}[f(\tilde{x})]_{+}\|_{1}\leq$
$\displaystyle~{}\tilde{\zeta}_{T}\left(2\sqrt{m}\xi+\tfrac{2\sqrt{m}}{\eta}\right)+\sqrt{\tfrac{2\tilde{L}}{\mu}}\tfrac{\max_{t\in[T]}|\Delta_{t}|}{B}$
$\displaystyle~{}+\tfrac{6\mu
mG}{\xi}+2mG\left(1-\sqrt{\tfrac{\mu}{2\tilde{L}}}\right)^{T-1},$ (constraint
violation)

where

$\displaystyle\tilde{\zeta}_{T}:$
$\displaystyle=2\left(1-\sqrt{\tfrac{\mu}{2\tilde{L}}}\right)^{\frac{T}{2}}\sqrt{\eta
K_{0}(\lambda^{*}_{\mu})}$
$\displaystyle\quad+\sqrt{\tfrac{8\eta\sqrt{m}G}{\xi}\max_{t\in[T]}\|\delta_{t}\|_{2}},$

$\Delta_{t}:=d({\underline{\lambda}_{t}})-f_{0}(x_{t})-\langle\underline{\lambda}_{t},f(x_{t})\rangle$,
$K_{0}(\lambda)\coloneqq
d_{\mu}(\lambda)-d_{\mu}(\bar{\lambda}_{0})+\tfrac{\alpha}{2}(\mu+\tfrac{1}{\eta})\|\lambda_{0}-\lambda\|_{2}^{2}$,
and
$\delta_{t}\coloneqq\widehat{\nabla}d_{\mu}(\underline{\lambda}_{t})-\nabla
d_{\mu}(\underline{\lambda}_{t}).$

###### Corollary 2

With a computational complexity of
$\tilde{\mathcal{O}}({L}/{\sqrt{\epsilon}})$, Algorithm AR-CO outputs an
$\epsilon$-optimal policy with respect to both the optimality gap and
constraint violation.

The properties of the constrained MDP that enable the proof of 1 have already
been captured in Assumptions 3, 4 and 5. Thus, the proof of 2 and 2 follows by
replacing $V_{0}(\rho)$ and $V(\rho)-c$ with $-f_{0}(x)$ and $-f(x)$ in the
proof of 1 and applying Assumptions 3, 4 and 5 when needed.

##  6 Experiments

Our experiments are conducted on the environment Acrobot-v1, OpenAI Gym (Mei
et al. ,, 2020a). The Acrobot-v1 simulates the acrobot system where there
exist two joints and two links. The upper joint is fixed and the lower joint
is actuated by the agent. The goal is to swing the end of the lower link up to
a given height. Moreover, two safe penalties are implemented when (I) the
first link swings in a prohibited direction, or when (II) the second link
swings in a prohibited direction with respect to the first link.

We compare our AR-CPO algorithm with the state-of-the-art primal-dual
optimization (PDO) method for CMDP (Chow et al. ,, 2017). In order for a fair
comparison, the same neural softmax policy and the trust region policy
optimization (Schulman et al. ,, 2015) are used in both algorithms. In Figure
1, we show the performance of the two algorithms under their best tuned
parameters. The opaque lines provides the accumulated discounted reward (for
the objective and the constraints) averaged over $10$ random initialized seeds
and translucent error bands have the width of two standard deviations of the
$10$ random initializations, respectively. More details on the environment and
parameters setting can be found in Appendix B. The dashed lines in Figure 1
(b) and (c) are the constraint thresholds, i.e. $c_{1}$ and $c_{2}$.

(a) Objective

(b) Constraint I

(c) Constraint II

Figure 1: Comparison between AR-CPO and PDO

From Figure 1(a), we observe that, our AR-CPO has a much higher accumulated
reward in the objective function, and the standard deviations of both
algorithms are similar. Figures 1(b) and 1(c) show that the accumulated reward
in the constraints of AR-CPO decays slightly faster than that of PDO. After
the constraints are satisfied, the cumulative reward in the constraints of AR-
CPO is much closer to the threshold, which enables AR-CPO to explore a higher
reward in the objective function.

##  7 Conclusion

In this paper, we developed a novel AR-CPO approach for solving the CMDP
problem, and showed that AR-CPO achieves an improved complexity of
$\tilde{\mathcal{O}}(1/\epsilon)$, which improves the complexity results in
existing studies Ding et al. , (2020a); Paternain et al. , (2019a) by a factor
of $\mathcal{O}(1/\epsilon)$. Our AR-CPO approach involves a novel blend of
three ingredients: (a) entropy regularized policy optimization, (b) dual
variable regularizer, and (c) Nesterov’s accelerated gradient descent dual
optimizer. To the best of our knowledge, this is the first establishment that
CMDP, despite its nonconcave nature of the objective and constraint functions,
can achieve the same complexity as the convex optimization with convex
constraints. Furthermore, we extended our approach to accelerate a class of
nonconvex functional constrained optimization problems, and showed that by
exploiting geometric properties, e.g., the gradient dominance condition, our
approach achieves the $\mathcal{O}(1/\sqrt{\epsilon})$ rate of convergence to
the global optimum. The numerical simulations also confirm the advantage of
the proposed approach.

## References

  * Achiam et al. , (2017) Achiam, Joshua, Held, David, Tamar, Aviv, & Abbeel, Pieter. 2017.  Constrained policy optimization.  Pages 22–31 of: International Conference on Machine Learning (ICML).
  * Agarwal et al. , (2019) Agarwal, Alekh, Kakade, Sham M, Lee, Jason D, & Mahajan, Gaurav. 2019.  Optimality and approximation with policy gradient methods in Markov decision processes.  arXiv preprint arXiv:1908.00261.
  * Agarwal et al. , (2020) Agarwal, Alekh, Kakade, Sham M, Lee, Jason D, & Mahajan, Gaurav. 2020.  Optimality and Approximation with Policy Gradient Methods in Markov Decision Processes.  In: Proc. Annual Conference on Learning Theory (COLT).
  * Altman, (1999) Altman, Eitan. 1999.  Constrained Markov Decision Processes.  Vol. 7.  CRC Press.
  * Bhandari & Russo, (2019) Bhandari, Jalaj, & Russo, Daniel. 2019.  Global optimality guarantees for policy gradient methods.  arXiv preprint arXiv:1906.01786.
  * Bhandari & Russo, (2020) Bhandari, Jalaj, & Russo, Daniel. 2020.  A note on the linear convergence of policy gradient methods.  arXiv preprint arXiv:2007.11120.
  * Boob et al. , (2019) Boob, Digvijay, Deng, Qi, & Lan, Guanghui. 2019.  Stochastic first-order methods for convex and nonconvex functional constrained optimization.  arXiv preprint arXiv:1908.02734.
  * Cen et al. , (2020) Cen, Shicong, Cheng, Chen, Chen, Yuxin, Wei, Yuting, & Chi, Yuejie. 2020.  Fast global convergence of natural policy gradient methods with entropy regularization.  arXiv preprint arXiv:2007.06558.
  * Chow et al. , (2017) Chow, Yinlam, Ghavamzadeh, Mohammad, Janson, Lucas, & Pavone, Marco. 2017.  Risk-constrained reinforcement learning with percentile risk criteria.  The Journal of Machine Learning Research, 18(1), 6070–6120.
  * Chow et al. , (2018) Chow, Yinlam, Nachum, Ofir, Duenez-Guzman, Edgar, & Ghavamzadeh, Mohammad. 2018\.  A Lyapunov-based approach to safe reinforcement learning.  Pages 8092–8101 of: Proc. Advances in Neural Information Processing Systems (NIPS).
  * Chow et al. , (2019) Chow, Yinlam, Nachum, Ofir, Faust, Aleksandra, Duenez-Guzman, Edgar, & Ghavamzadeh, Mohammad. 2019.  Lyapunov-based safe policy optimization for continuous control.  arXiv preprint arXiv:1901.10031.
  * Dalal et al. , (2018) Dalal, Gal, Dvijotham, Krishnamurthy, Vecerik, Matej, Hester, Todd, Paduraru, Cosmin, & Tassa, Yuval. 2018.  Safe exploration in continuous action spaces.  arXiv preprint arXiv:1801.08757.
  * Ding et al. , (2020a) Ding, Dongsheng, Zhang, Kaiqing, Basar, Tamer, & Jovanovic, Mihailo. 2020a.  Natural Policy Gradient Primal-Dual Method for Constrained Markov Decision Processes.  In: Proc. Advances in Neural Information Processing Systems (NIPS), vol. 33.
  * Ding et al. , (2020b) Ding, Dongsheng, Wei, Xiaohan, Yang, Zhuoran, Wang, Zhaoran, & Jovanović, Mihailo R. 2020b.  Provably efficient safe exploration via primal-dual policy optimization.  arXiv preprint arXiv:2003.00534.
  * Duan et al. , (2016) Duan, Yan, Chen, Xi, Houthooft, Rein, Schulman, John, & Abbeel, Pieter. 2016.  Benchmarking deep reinforcement learning for continuous control.  Pages 1329–1338 of: International conference on machine learning.  PMLR.
  * Facchinei et al. , (2021) Facchinei, Francisco, Kungurtsev, Vyacheslav, Lampariello, Lorenzo, & Scutari, Gesualdo. 2021.  Ghost penalties in nonconvex constrained optimization: Diminishing stepsizes and iteration complexity.  Mathematics of Operations Research.
  * Fisac et al. , (2018) Fisac, Jaime F, Akametalu, Anayo K, Zeilinger, Melanie N, Kaynama, Shahab, Gillula, Jeremy, & Tomlin, Claire J. 2018.  A general safety framework for learning-based control in uncertain robotic systems.  IEEE Transactions on Automatic Control, 64(7), 2737–2752.
  * Garcıa & Fernández, (2015) Garcıa, Javier, & Fernández, Fernando. 2015.  A comprehensive survey on safe reinforcement learning.  Journal of Machine Learning Research, 16(1), 1437–1480.
  * Haarnoja et al. , (2018) Haarnoja, Tuomas, Zhou, Aurick, Abbeel, Pieter, & Levine, Sergey. 2018.  Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor.  Pages 1861–1870 of: International Conference on Machine Learning.  PMLR.
  * Hazan et al. , (2019) Hazan, Elad, Kakade, Sham, Singh, Karan, & Van Soest, Abby. 2019.  Provably efficient maximum entropy exploration.  Pages 2681–2691 of: International Conference on Machine Learning.  PMLR.
  * Kakade, (2001) Kakade, Sham M. 2001.  A natural policy gradient.  Advances in neural information processing systems, 14, 1531–1538.
  * Lan, (2021) Lan, G. 2021.  Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classes.  arXiv preprint arXiv:2102.00135.
  * Lan, (2020) Lan, Guanghui. 2020.  First-order and Stochastic Optimization Methods for Machine Learning.  Springer.
  * Levin & Peres, (2017) Levin, David A, & Peres, Yuval. 2017.  Markov Chains and Mixing Times.  Vol. 107.  American Mathematical Soc.
  * Liu et al. , (2019a) Liu, Boyi, Cai, Qi, Yang, Zhuoran, & Wang, Zhaoran. 2019a.  Neural proximal/trust region policy optimization attains globally optimal policy.  In: In Proc. Advances in Neural Information Processing Systems (NeurIPS), vol. 32.
  * Liu et al. , (2019b) Liu, Yongshuai, Ding, Jiaxin, & Liu, Xin. 2019b.  IPO: interior-point policy optimization under constraints.  arXiv preprint arXiv:1910.09615.
  * Mei et al. , (2020a) Mei, J., Xiao, C., Szepesvari, C., & Schuurmans, D. 2020a.  On the global convergence rates of softmax policy gradient methods.  arXiv preprint arXiv:2005.06392.
  * Mei et al. , (2020b) Mei, Jincheng, Xiao, Chenjun, Szepesvari, Csaba, & Schuurmans, Dale. 2020b.  On the Global Convergence Rates of Softmax Policy Gradient Methods.  arXiv preprint arXiv:2005.06392.
  * Mitrophanov, (2005) Mitrophanov, A. Y. 2005.  Sensitivity and convergence of uniformly ergodic Markov chains.  Journal of Applied Probability, 42(4), 1003–1014.
  * Mnih et al. , (2016) Mnih, Volodymyr, Badia, Adria Puigdomenech, Mirza, Mehdi, Graves, Alex, Lillicrap, Timothy, Harley, Tim, Silver, David, & Kavukcuoglu, Koray. 2016.  Asynchronous methods for deep reinforcement learning.  Pages 1928–1937 of: International conference on machine learning.  PMLR.
  * Nachum et al. , (2017) Nachum, Ofir, Norouzi, Mohammad, Xu, Kelvin, & Schuurmans, Dale. 2017.  Bridging the gap between value and policy based reinforcement learning.  In: Proc. Advances in Neural Information Processing Systems (NIPS).
  * Nemirovsky, (1992) Nemirovsky, Arkadi S. 1992.  Information-based complexity of linear operator equations.  Journal of Complexity, 8(2), 153–175.
  * Ono et al. , (2015) Ono, Masahiro, Pavone, Marco, Kuwata, Yoshiaki, & Balaram, J. 2015.  Chance-constrained dynamic programming with application to risk-aware robotic space exploration.  Autonomous Robots, 39(4), 555–571.
  * Ouyang & Xu, (2019) Ouyang, Yuyuan, & Xu, Yangyang. 2019.  Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems.  Mathematical Programming, 1–35.
  * Paternain et al. , (2019a) Paternain, Santiago, Chamon, Luiz FO, Calvo-Fullana, Miguel, & Ribeiro, Alejandro. 2019a.  Constrained reinforcement learning has zero duality gap.  In: Proc. Advances in Neural Information Processing Systems (NIPS).
  * Paternain et al. , (2019b) Paternain, Santiago, Calvo-Fullana, Miguel, Chamon, Luiz FO, & Ribeiro, Alejandro. 2019b.  Safe policies for reinforcement learning via primal-dual methods.  arXiv preprint arXiv:1911.09101.
  * Peters et al. , (2010) Peters, Jan, Mulling, Katharina, & Altun, Yasemin. 2010.  Relative entropy policy search.  In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 24.
  * Schulman et al. , (2015) Schulman, John, Levine, Sergey, Abbeel, Pieter, Jordan, Michael, & Moritz, Philipp. 2015.  Trust region policy optimization.  Pages 1889–1897 of: Proc. International Conference on Machine Learning (ICML).  PMLR.
  * Shani et al. , (2020) Shani, Lior, Efroni, Yonathan, & Mannor, Shie. 2020.  Adaptive trust region policy optimization: Global convergence and faster rates for regularized MDPs.  Proc. AAAI Conference on Artificial Intelligence (AAAI).
  * Stooke et al. , (2020) Stooke, Adam, Achiam, Joshua, & Abbeel, Pieter. 2020.  Responsive safety in reinforcement learning by PID Lagrangian methods.  In: In Proc. International Conference on Machine Learning (ICML).
  * Sutton & Barto, (2018) Sutton, Richard S., & Barto, Andrew G. 2018.  Reinforcement Learning: An Introduction, Second Edition.  The MIT Press, Cambridge, Massachusetts.
  * Szepesvári, (2020) Szepesvári, Csaba. 2020.  Constrained MDPs and the reward hypothesis.  http://readingsml.blogspot.com/2020/03/constrained-mdps-and-reward-hypothesis.html.  Accessed: 2021-01-27.
  * Tessler et al. , (2018) Tessler, Chen, Mankowitz, Daniel J, & Mannor, Shie. 2018.  Reward constrained policy optimization.  In: In Proc. International Conference on Learning Representations (ICLR).
  * Wang et al. , (2019) Wang, Lingxiao, Cai, Qi, Yang, Zhuoran, & Wang, Zhaoran. 2019.  Neural policy gradient methods: Global optimality and rates of convergence.  arXiv preprint arXiv:1909.01150.
  * Wang et al. , (2017) Wang, Xiao, Ma, Shiqian, & Yuan, Ya-xiang. 2017.  Penalty methods with stochastic approximation for stochastic nonlinear programming.  Mathematics of computation, 86(306), 1793–1820.
  * Williams & Peng, (1991) Williams, Ronald J, & Peng, Jing. 1991.  Function optimization using connectionist reinforcement learning algorithms.  Connection Science, 3(3), 241–268.
  * Xiao et al. , (2019) Xiao, Chenjun, Huang, Ruitong, Mei, Jincheng, Schuurmans, Dale, & Müller, Martin. 2019.  Maximum Entropy Monte-Carlo Planning.  In: Proc. Advances in Neural Information Processing Systems (NIPS).
  * Xu et al. , (2020a) Xu, Tengyu, Wang, Zhe, & Liang, Yingbin. 2020a.  Improving sample complexity bounds for actor-critic algorithms.  arXiv preprint arXiv:2004.12956.
  * Xu et al. , (2020b) Xu, Tengyu, Liang, Yingbin, & Lan, Guanghui. 2020b.  A Primal Approach to Constrained Policy Optimization: Global Optimality and Finite-Time Analysis.  arXiv preprint arXiv:2011.05869.
  * Yang et al. , (2019) Yang, Tsung-Yen, Rosca, Justinian, Narasimhan, Karthik, & Ramadge, Peter J. 2019\.  Projection-based constrained policy optimization.  In: In Proc. International Conference on Learning Representations (ICLR).
  * Yu et al. , (2019) Yu, Ming, Yang, Zhuoran, Kolar, Mladen, & Wang, Zhaoran. 2019.  Convergent policy optimization for safe reinforcement learning.  Pages 3127–3139 of: In Proc. Advances in Neural Information Processing Systems (NeurIPS).
  * Zou et al. , (2019) Zou, Shaofeng, Xu, Tengyu, & Liang, Yingbin. 2019.  Finite-sample analysis for SARSA with linear function approximation.  Pages 8665–8675 of: Proc. Advances in Neural Information Processing Systems (NeurIPS).

Supplementary Materials

##  Appendix A Example Entropy-Regularized Policy Optimizers (RegPOs)

In this section, we introduce two entropy-regularized policy optimizers
(RegPOs), which solves the maximization problem of an entropy-regularized
value function as

$\displaystyle\max_{\pi\in\Pi}V_{\tau,\lambda}^{\pi}(\rho):=V^{\pi}_{r_{\lambda}}(\rho)+\tau\mathcal{H}(\pi)$
(7)

where $V^{\pi}_{r_{\lambda}}$ is the value function corresponding to the
reward function $r_{\lambda}\coloneqq r_{0}+\sum_{i=1}^{m}\lambda_{i}r_{i}$.
Note that the above problem is equivalent to the entropy regularized
Lagrangian maximization problem
$\max_{\pi\in\Pi}\mathcal{L}_{\tau,\mu}(\pi,\lambda)$ for any
$\lambda\in\Lambda$. Define the Q-function under regularized MDP as, for all
$s\in\mathcal{S}$ and $a\in\mathcal{A}$,

$\displaystyle
Q_{\tau,\lambda}^{\pi}(s,a)=r_{\lambda}(s,a)+\gamma\mathbb{E}_{s^{\prime}\sim\mathsf{P}(\cdot|s,a)}\left[V^{\pi}_{\tau,\lambda}(s^{\prime})\right].$

And we use the short-hand notation $Q^{*}_{\tau,\lambda}$ to denote
$Q^{\pi^{*}_{\tau,\lambda}}_{\tau,\lambda}$ in the Appendix.

###  A.1 RegPO-NPG

Algorithm 3 RegPO-NPG $(\delta,\lambda,\tau)$ (Kakade,, 2001; Cen et al. ,,
2020)

1:Input: Output accuracy $\delta$, dual variable value $\lambda$,
regularization coefficient $\tau$, rewards $r$.

2:Initialize: $\theta_{0}=0$,
$K=\left\lceil\log\left(\frac{2(r_{0,\max}+BR_{\max})}{(1-\gamma)\delta\tau}\right)/\left(\log\left(\tfrac{1}{\gamma}\right)\right)\right\rceil$.

3:for $k=0,...,K$ do

4:
$\theta_{k+1}\leftarrow\theta_{k}+\frac{1-\gamma}{\tau}(\mathcal{F}_{\rho}^{\theta_{k}})^{\dagger}\nabla_{\theta}V_{\tau,\lambda}^{\pi_{\theta_{k}}}(\rho)$

5:end for

We summarize an NPG-based RegPO in Algorithm 3. Suppose a softmax
parameterization of the policy $\pi$ is used. Then, the natural policy
gradient (NPG) can be applied to solve the entropy-regularized MDP (Kakade,,
2001; Cen et al. ,, 2020). Specifically, the parameter update is given by

$\displaystyle\theta_{k+1}=\theta_{k}+\beta(\mathcal{F}_{\rho}^{\theta_{k}})^{\dagger}\nabla_{\theta}V_{\tau,\lambda}^{\pi_{\theta_{k}}}(\rho),$

where $\beta$ is the stepsize,
$\nabla_{\theta}V_{\tau,\lambda}^{\pi_{\theta_{k}}}(\rho)$ denotes the policy
gradient, and $\mathcal{F}_{\rho}^{\theta_{k}}$ denotes the Fisher information
matrix defined blow

$\displaystyle\mathcal{F}_{\rho}^{\theta_{k}}\coloneqq\mathbb{E}_{(s,a)\sim\nu_{\rho}^{\pi_{\theta_{k}}}}\bigg{[}(\nabla\log\pi_{\theta}(a|s))(\nabla\log\pi_{\theta}(a|s))^{\top}\bigg{]}.$

Let $\pi_{\tau,\lambda}^{*}$ denote the optimal policy for eq. 7. It has been
shown in (Cen et al. ,, 2020) that if we take the stepsize
$\beta=(1-\gamma)/\tau$, RegPO-NPG converges linearly as given by

$\displaystyle\|Q_{\tau,\lambda}^{*}-Q_{\tau,\lambda}^{\pi_{\theta_{K}}}\|_{\infty}\leq\|Q_{\tau,\lambda}^{*}-Q_{\tau,\lambda}^{\pi_{\theta_{0}}}\|_{\infty}\cdot\gamma^{K},$
$\displaystyle\|\pi_{K+1}-\pi_{\tau,\lambda}^{*}\|_{\infty}\leq\tfrac{2}{\tau}\|Q_{\tau,\lambda}^{*}-Q_{\tau,\lambda}^{\pi_{\theta_{K}}}\|_{\infty}.$

Therefore, choosing $\beta=(1-\gamma)/\tau$ and
$K=\left\lceil\log\left(\frac{2(r_{0,\max}+BR_{\max})}{(1-\gamma)\delta\tau}\right)/\left(\log\left(\tfrac{1}{\gamma}\right)\right)\right\rceil$
guarantees that $\|\pi_{K+1}-\pi_{\tau,\lambda}^{*}\|_{\infty}\leq\delta$.

###  A.2 RegPO-SoftQ

Algorithm 4 RegPO-SoftQ $(\delta,\lambda,\tau)$

1:Input: Output accuracy $\delta$, dual variable value $\lambda$,
regularization coefficient $\tau$.

2:Initialize: $Q_{0}=0$,
$K=\left\lceil\log\left(\frac{2(r_{0,\max}+BR_{\max})}{(1-\gamma)\delta\tau}\right)/\left(\log\left(\tfrac{1}{\gamma}\right)\right)\right\rceil$.

3:for $k=0,...,K-1$ do

4: $Q_{k+1}\leftarrow\mathcal{T}_{\tau,\lambda}(Q_{k})$

5:end for

6:$\pi_{K}(a|s)\leftarrow\exp(Q_{K}(s,a)/\tau)/\left(\sum_{a^{\prime}\in\mathcal{A}}\exp(Q_{K}(s,a^{\prime})/\tau)\right)$,
for all $s\in\mathcal{S}$ and $a\in\mathcal{A}$.

We propose a new soft Q-learning based RegPO, which is summarized in Algorithm
4. For the $\tau$-regularized MDP problem in eq. 7, we define the following
soft Bellman operator

$\displaystyle(\mathcal{T}_{\tau}(Q))_{s,a}=r_{\lambda}(s,a)+\gamma\mathbb{E}_{s^{\prime}\sim\mathsf{P}(\cdot|s,a)}\left[\tau\log\left(\textstyle\sum_{a^{\prime}\in\mathcal{A}}\exp\left(\frac{Q(s^{\prime},a^{\prime})}{\tau}\right)\right)\right],$

for every $s\in\mathcal{S}$ and $a\in\mathcal{A}$, where we adopt the soft
Q-learning update (Nachum et al. ,, 2017; Cen et al. ,, 2020) for the
Q-function rather than the “max" operator.

It can be shown that the Q-function converges linearly:

$\displaystyle\|Q_{K}-Q^{*}_{\tau,\lambda}\|_{\infty}\leq\|Q_{0}-Q^{*}_{\tau,\lambda}\|_{\infty}\cdot\gamma^{K}.$

Then the relationship $\pi_{K}(a|s)\propto\exp(Q_{K}(s,a)/\tau)$ further
implies that

$\displaystyle\|\pi_{K}-\pi^{*}_{\tau,\lambda}\|_{\infty}\leq\tfrac{2}{\tau}\|Q_{K}-Q^{*}_{\tau,\lambda}\|_{\infty},$

which yields $\|\pi_{K}-\pi_{\tau,\lambda}^{*}\|_{\infty}\leq\delta$ for
$K=\left\lceil\log\left(\frac{2(r_{0,\max}+BR_{\max})}{(1-\gamma)\delta\tau}\right)/\left(\log\left(\tfrac{1}{\gamma}\right)\right)\right\rceil$.

##  Appendix B Details of Numerical Simulations

###  B.1 Reward and Constraint Costs Setting

The interaction of the agent and virtual environment is divided into episodes
and the horizon of each episode is $500$. The agent receives a reward
$r_{0}=+1$ (reward for the objective), when the end of the lower link is at a
height of $0.5$. It is penalized with cost $r_{1}=+1$ (cost for constraint 1)
when the first link swings at a anticlockwise direction and the agent applies
a $+1$ torque to the actuating joint; it also receives a penalty of $r_{2}=+1$
(cost for constraint 2) when the second link swings at a anticlockwise
direction with respect to the first link and the agent applies a $+1$ torque
to the actuating joint. The cost thresholds for both $r_{1}$ and $r_{2}$ are
set to be $50$.

###  B.2 Parameters Setting

The details of PDO and TRPO are given in (Schulman et al. ,, 2015; Achiam et
al. ,, 2017). For the PDO algorithm, we tune the stepsize (for dual variable
update) from the set $\\{0.0001,0.0005,0.001,0.005,0.01,0.05\\}$, and the best
performance (given in Figure 1) corresponds to the choice of 0.0005. For our
AR-CPO method, we tune the following parameters.

  * •

$q$: parameter in the update of $\underline{\lambda}$,

$\underline{\lambda}_{t}=(1-q_{t})\bar{\lambda}_{t-1}+q_{t}\lambda_{t-1},$

where $t$ is the number of iterations.

  * •

$\alpha$: parameter in the update of $\bar{\lambda}$,

$\bar{\lambda}_{t}=(1-\alpha_{t})\bar{\lambda}_{t-1}+\alpha_{t}\lambda_{t}.$

In our experiment, we set $\alpha_{t}$ and $q_{t}$ to first diminish and then
remain constant as follows

$\alpha_{t}=q_{t}=\begin{cases}\frac{2s}{t+1},\qquad&1\leq t<H\\\
\frac{2s}{H},&\text{otherwise},\end{cases}$

where the parameters $H>0$ and $0<s<1$ completely determine $\alpha_{t}$ and
$q_{t}$.

  * •

inner_loop: the number of policy optimization steps in RegPO subroutine.

  * •

max_KL: the parameter that controls the RegPO updates.

  * •

$\eta$: the parameter in the update of $\lambda$, defined in Step 7 of
Algorithm 2 with $\mu=0$ and $\Lambda=[0,\infty)^{2}$.

We tune the above parameters over a range of choices as
$s\in\\{1,0.3,0.05\\}$, $H\in\\{15,45,85\\}$, inner_loop $\in\\{1,5\\}$,
max_KL $\in\\{0.001,0.003,0.01\\}$ and $\eta\in\\{0.0001,0.0003,0.001\\}$, and
do the grid search over all possible choices. The best performance (given in
Figure 1) corresponds to the choices of $s=1$, $H=45$, inner_loop=$1$,
max_KL$=0.01$ and $\eta=0.0003$.

##  Appendix C Proofs of 1 and 1

###  C.1 Main Proof of 1

Step 1. The first step establishes that the dual function
$d_{\tau,\mu}(\lambda)$ is an $L_{d}$-smooth function in 1, which is a
necessary property for the complexity order improvement. The entropy
regularizer plays an important role for such a property to hold, without which
1 does not hold anymore.

###### Proposition 1

Suppose Assumption 2 holds, then $d_{\tau,\mu}(\lambda)$ is $L_{d}$-smooth:

$\displaystyle\|\nabla d_{\tau,\mu}(\lambda)-\nabla
d_{\tau,\mu}(\lambda^{\prime})\|_{2}\leq
L_{d}\|\lambda-\lambda^{\prime}\|_{2},\quad\forall\lambda,\lambda^{\prime}\in\mathbb{R}_{+}^{m},$
(8)

where $L_{d}=\frac{2R_{\max}^{2}L_{\nu}}{(1-\gamma)^{2}\tau}+\mu$.

Step 2. This step contains three major novel components: (a) construction of a
weighted value function
$(1-\alpha)^{T-1}V_{0}^{\pi_{1}}(\rho)+\sum\nolimits_{t=2}^{T}\alpha(1-\alpha)^{T-t}V_{0}^{\pi_{t}}(\rho)$,
which will ultimately yield the convergence of the optimality gap in Step 4;
(b) construction of a weighted policy $\tilde{\pi}$ based on the updates of
the dual variable $\\{\underline{\lambda}_{t}\\}$ in Algorithm 2, whose value
function equals to the weighted value function constructed in (a) as shown in
2; and (c) establishment of the connection between the optimality gap, the
constraint violation and the updates of the dual variable $\\{\lambda_{t}\\}$
as presented in 3.

###### Proposition 2

Define the policy $\tilde{\pi}$, such that, for all $s\in\mathcal{S}$ and
$a\in\mathcal{A}$,

$\displaystyle\tilde{\pi}(a|s)=\frac{(1-\alpha)^{T-1}\nu_{\rho}^{\pi_{1}}(s,a)+\sum\nolimits_{t=2}^{T}\alpha(1-\alpha)^{T-t}\nu_{\rho}^{\pi_{t}}(s,a)}{(1-\alpha)^{T-1}\chi^{\pi_{1}}_{\rho}(s)+\sum\nolimits_{t=2}^{T}\alpha(1-\alpha)^{T-t}\chi_{\rho}^{\pi_{t}}(s)},$
(9)

where
$\chi_{\rho}^{\pi}(s)=\sum_{a^{\prime}\in\mathcal{A}}\nu_{\rho}^{\pi}(s,a^{\prime})$.
Then for $i=0,...,m,$

$\displaystyle
V_{i}^{\tilde{\pi}}(\rho)=(1-\alpha)^{T-1}V_{i}^{\pi_{1}}(\rho)+\sum_{t=2}^{T}\alpha(1-\alpha)^{T-t}V_{i}^{\pi_{t}}(\rho).$
(10)

###### Proposition 3

Consider Algorithm 2. Then the summation of the optimality gap and the
constraint violation is bounded by the dual variable increments as follows.
For any $\lambda\in\Lambda$,

$\displaystyle
V_{0}^{*}(\rho)-\left[(1-\alpha)^{T-1}V_{0}^{\pi_{1}}(\rho)+\sum\nolimits_{t=2}^{T}\alpha(1-\alpha)^{T-t}(V_{0}^{\pi_{t}}(\rho)+\lambda^{\top}(c-{V}^{\pi_{t}}(\rho)))\right]$
$\displaystyle\leq$
$\displaystyle\left(\sum\nolimits_{t=1}^{T}\alpha(1-\alpha)^{T-t}\|\lambda_{t}-\lambda_{t-1}\|_{2}^{2}\right)^{\frac{1}{2}}\left(\tfrac{q}{\alpha}\tfrac{R_{\max}}{1-\gamma}+\tfrac{R_{\max}}{1-\gamma}+\tfrac{2\sqrt{m}B}{\eta}\right)$
$\displaystyle+\sum\nolimits_{t=1}^{T}(1-\alpha)^{T-t}\Delta_{t}+\tfrac{\tau}{1-\gamma}\log|\mathcal{A}|+6\mu
mB^{2}.$ (11)

The analysis indicates that the convergence rate of the distance between two
consecutive iterates $\|\lambda_{t}-\lambda_{t-1}\|_{2}^{2}$ plays a central
role in the overall convergence and complexity of the optimality gap and
constraint violation of policy $\tilde{\pi}$, which we will bound in Step 3.

Step 3. This step provides the convergence bound for the dual variable
$\lambda$, which is updated via Nesterov’s accelerated gradient descent.
However, our analysis here is significantly different from the Nesterov’s
analysis. The reason is that the Nesterov’s analysis would provide only the
convergence in terms of the dual function gap for our problem, whereas for the
constrained MDP problem, our goal is the convergence guarantee in terms of the
optimality gap and the constraint violation (see Definition 1), which requires
to bound the distance between two consecutive iterates of the dual variable
due to 3. To this end, in this step we develop the following proposition.

###### Proposition 4

Let $(\underline{\lambda}_{t},\lambda_{t},\bar{\lambda}_{t})\in\Lambda$ be
generated by Algorithm 2 and the parameters be chosen in (6). Then for any
$\lambda\in\Lambda$,

$\displaystyle\sum_{t=1}^{T}\tfrac{\alpha(1-\alpha)^{T-t}}{4\eta}\|\lambda_{t}-\lambda_{t-1}\|_{2}^{2}\leq(1-\alpha)^{T}K_{0}(\lambda)-K_{T}(\lambda)+\sum_{t=1}^{T}\alpha(1-\alpha)^{T-t}\langle\delta_{t},\lambda-\lambda_{t}\rangle,$
(12)

where $K_{t}(\lambda)\coloneqq
d_{\tau,\mu}(\bar{\lambda}_{t})-d_{\tau,\mu}(\lambda)+\tfrac{\alpha}{2}(\mu+\tfrac{1}{\eta})\|\lambda_{t}-\lambda\|_{2}^{2}$,
and
$\delta_{t}\coloneqq\widehat{\nabla}d_{\tau,\mu}(\underline{\lambda}_{t})-\nabla
d_{\tau,\mu}(\underline{\lambda}_{t})$ .

4 indicates that by introducing the $\ell_{2}$ regularization for the dual
variable, the distance term
$\sum\nolimits_{t=1}^{T}\alpha(1-\alpha)^{T-t}\|\lambda_{t}-\lambda_{t-1}\|_{2}^{2}$
converges linearly in terms of the error $K_{0}(\lambda^{*}_{\tau,\mu})$
introduced by the selection of the initial point $\lambda_{0}$. The gradient
error $\delta_{t}$ can be made as small as possible via sufficient RegPO
updates.

Step 4. This step characterizes the ultimate convergence in terms of the
optimality gap and the constraint violation. Substituting the bound in eq. 12
into 3 yields that

$\displaystyle
V_{0}^{*}(\rho)-\left[(1-\alpha)^{T-1}V_{0}^{\pi_{1}}(\rho)+\sum\nolimits_{t=2}^{T}\alpha(1-\alpha)^{T-t}(V_{0}^{\pi_{t}}(\rho)+\lambda^{\top}(c-{V}^{\pi_{t}}(\rho)))\right]$
$\displaystyle\leq$
$\displaystyle\left(4\eta(1-\alpha)^{T}K_{0}(\lambda^{*}_{\tau,\mu})+\sum\nolimits_{t=1}^{T}4\eta\alpha(1-\alpha)^{T-t}\langle\delta_{t},\lambda^{*}_{\tau,\mu}-\lambda_{t}\rangle\right)^{\frac{1}{2}}\left(\tfrac{q}{\alpha}\tfrac{R_{\max}}{1-\gamma}+\tfrac{R_{\max}}{1-\gamma}+\tfrac{2\sqrt{m}B}{\eta}\right)$
$\displaystyle+\sum\nolimits_{t=1}^{T}(1-\alpha)^{T-t}\Delta_{t}+\tfrac{\tau}{1-\gamma}\log|\mathcal{A}|+6\mu
mB^{2}$ $\displaystyle\leq$
$\displaystyle\left(2(1-\alpha)^{\frac{T}{2}}\sqrt{\eta
K_{0}(\lambda^{*}_{\tau,\mu})}+\sqrt{8\eta\sqrt{m}B\max_{t=1,\ldots
T}\|\delta_{t}\|_{2}}\right)\left(\tfrac{2R_{\max}}{1-\gamma}+\tfrac{2\sqrt{m}B}{\eta}\right)$
$\displaystyle+\tfrac{\max_{t=1,\ldots
T}|\Delta_{t}|}{\alpha}+\tfrac{\tau}{1-\gamma}\log|\mathcal{A}|+6\mu mB^{2}.$
(13)

The result of optimality gap follows directly by taking $\lambda=0$ in eq. 13.

To further derive the bound on the constraint violation, we first add
$(1-\alpha)^{T-1}\lambda^{\top}({c}-{V}^{\pi_{1}}(\rho))$ on both sides of eq.
13. By taking $\lambda_{i}=2B$ if $({c}-{V}^{\tilde{\pi}}(\rho))_{i}>0$, and
taking $\lambda_{i}=0$ otherwise, we have

$\displaystyle V_{0}^{*}(\rho)-$ $\displaystyle
V^{\tilde{\pi}}_{0}(\rho)+2B\mathbf{1}^{\top}({c}-{V}^{\tilde{\pi}}(\rho))_{+}$
$\displaystyle\leq$ $\displaystyle\left(2(1-\alpha)^{\frac{T}{2}}\sqrt{\eta
K_{0}(\lambda^{*}_{\tau,\mu})}+\sqrt{8\eta\sqrt{m}B\max_{t=1,\ldots
T}\|\delta_{t}\|_{2}}\right)\left(\tfrac{2R_{\max}}{1-\gamma}+\tfrac{2\sqrt{m}B}{\eta}\right)$
$\displaystyle+\tfrac{\max_{t=1,\ldots
T}|\Delta_{t}|}{\alpha}+\tfrac{\tau}{1-\gamma}\log|\mathcal{A}|+6\mu
mB^{2}+2(1-\alpha)^{T-1}\sqrt{m}B\tfrac{R_{\max}}{1-\gamma}.$ (14)

Then we utilize the following proposition to bound the constraint violation.

###### Proposition 5

Given a policy $\tilde{\pi}$, suppose
$V^{*}_{0}(\rho)-V^{\tilde{\pi}}_{0}(\rho)+\langle\lambda,({c}-V^{\tilde{\pi}})_{+}\rangle\leq\sigma,$
where $\lambda\in\mathbb{R}^{m}_{+}$ satisfying
$\lambda\succeq\lambda^{*}+B\mathbf{1}$. Then, we have
$\|({c}-V^{\tilde{\pi}})_{+}\|_{1}\leq\frac{\sigma}{B}$.

Together with 5, eq. 14 implies the bound on the constraint violation.

$\displaystyle\|({c}-{V}^{\tilde{\pi}}(\rho))_{+}\|_{1}\leq$
$\displaystyle\left(2\left(1-\sqrt{\tfrac{\mu}{2L_{d}}}\right)^{\frac{T}{2}}\sqrt{\eta
K_{0}(\lambda^{*}_{\tau,\mu})}+\sqrt{8\eta\sqrt{m}B\max_{t=1,\ldots
T}\|\delta_{t}\|_{2}}\right)\left(\tfrac{2R_{\max}}{(1-\gamma)B}+\tfrac{2\sqrt{m}}{\eta}\right)$
$\displaystyle+\sqrt{\tfrac{2L_{d}}{\mu}}\tfrac{\max_{t=1,\ldots
T}|\Delta_{t}|}{B}+\tfrac{\tau\log|\mathcal{A}|}{(1-\gamma)B}+6\mu
mB+2\left(1-\sqrt{\tfrac{\mu}{2L_{d}}}\right)^{T-1}\tfrac{\sqrt{m}R_{\max}}{1-\gamma}.$

The complete proof of Propositions 1, 2, 3, 4 and 5 are provided in Section
C.3.

###  C.2 Supporting Lemmas

We first introduce three useful lemmas. They are quite explicit and thus we
omit the proof.

###### Lemma 1

Given $x,y\in(0,1)$, we have $|x-y|\leq|\log(x)-\log(y)|$.

###### Lemma 2

For any two vectors $x,y\in\mathbb{R}^{m}$,
$\left|\log\left(\|\exp(x)\|_{1}\right)-\log\left(\|\exp(y)\|_{1}\right)\right|\leq\|x-y\|_{\infty}.$

###### Lemma 3

Suppose we have two functions $f$ and $g$: $\mathcal{X}\rightarrow\mathbb{R}$,
where $\mathcal{X}$ could be a finite set or a subset of $\mathbb{R}^{m}$ for
some $m\in\mathbb{N}$. Then, we have

$\left|\sup_{x\in\mathcal{X}}\\{f(x)\\}-\sup_{x\in\mathcal{X}}\\{g(x)\\}\right|\leq\sup_{x\in\mathcal{X}}\left\\{|f(x)-g(x)|\right\\}.$

The following lemma (Lan,, 2020, Lemma 3.5), often referred to as the “three-
point lemma", characterizes the property of one step update in Line 7 of
Algorithm 2.

###### Lemma 4

Let $(\underline{\lambda}_{t},\lambda_{t},\bar{\lambda}_{t})\in\Lambda$ be
generated by Algorithm 2, then for any $\lambda\in\Lambda$, we have

$\displaystyle\eta\langle\widehat{\nabla}d_{\tau,\mu}(\underline{\lambda}_{t}),\lambda_{t}-\lambda\rangle+\tfrac{\eta\mu}{2}\|\lambda_{t}-\underline{\lambda}_{t}\|_{2}^{2}+\tfrac{1}{2}\|\lambda_{t}-\lambda_{t-1}\|_{2}^{2}\leq\tfrac{\eta\mu}{2}\|\lambda-\underline{\lambda}_{t}\|_{2}^{2}+\tfrac{1}{2}\|\lambda-\lambda_{t-1}\|_{2}^{2}.$
(15)

###### Lemma 5

Suppose Assumption 1 holds. Let $\lambda^{*}$ be the minimizer of the dual
function. Then

$\|\lambda^{*}\|_{1}\leq B\coloneqq\tfrac{r_{0,\max}}{(1-\gamma)\xi}.$

##### Proof

By the definition of $d(\lambda)$, we have that

$\displaystyle d(\lambda)\geq
V_{0}^{\pi_{\xi}}(\rho)+\langle\lambda,V^{\pi_{\xi}}(\rho)-c\rangle\overset{(i)}{\geq}\xi\|\lambda\|_{1},$
(16)

where $(i)$ follows from the fact that $V_{0}^{\pi_{\xi}}\geq 0$ and
Assumption 1. Moreover, constrained reinforcement learning has no duality gap
(Paternain et al. ,, 2019a). Combining this with the fact that the optimal
function value is bounded, we conclude that the optimal dual variable exists
in $\mathbb{R}_{+}^{m}$. Taking $\lambda=\lambda^{*}$ in eq. 16 and using the
fact that
$d(\lambda^{*})=V_{0}^{\pi^{*}}(\rho)\leq\tfrac{r_{0,\max}}{1-\gamma}$, we
complete the proof. $\square$

###### Lemma 6

Under Assumption 2, for any $\lambda,\lambda^{\prime}\in\mathbb{R}_{+}^{m}$,
and the corresponding optimal policy $\pi^{*}_{\tau,\lambda}$ and
$\pi^{*}_{\tau,\lambda^{\prime}}$, we have

$\left\|\nu^{\pi^{*}_{\tau,\lambda}}_{\rho}-\nu^{\pi^{*}_{\tau,\lambda^{\prime}}}_{\rho}\right\|_{1}=2\textrm{d}_{TV}\left(\nu^{\pi^{*}_{\tau,\lambda}}_{\rho},\nu^{\pi^{*}_{\tau,\lambda^{\prime}}}_{\rho}\right)\leq
L_{\nu}\max_{s\in\mathcal{S}}\left\|\pi^{*}_{\tau,\lambda}(\cdot|s)-\pi^{*}_{\tau,\lambda^{\prime}}(\cdot|s)\right\|_{1},$

where $L_{\nu}\coloneqq\lceil\log_{\beta}(C_{M}^{-1})\rceil+(1-\beta)^{-1}+1$.

##### Proof

Our proof here is inspired by Zou et al. , (2019); Xu et al. , (2020a).
Readers may find more bounds on the difference of visitation measures in their
papers. Denote $\tilde{P}(s^{\prime}|s,a):=\gamma
P(s^{\prime}|s,a)+(1-\gamma)\rho(s^{\prime})$, $\forall
s,s^{\prime}\in\mathcal{S},~{}a\in\mathcal{A}.$ Denote $\tilde{P}^{\pi}$ as a
transition kernel, where
$\tilde{P}^{\pi}_{s,s^{\prime}}:=\gamma\textstyle{\sum}_{a\in\mathcal{A}}\pi(a|s)\mathsf{P}(s^{\prime}|s,a)+(1-\gamma)\rho(s^{\prime})$.
Moreover, recall that
$\chi^{\pi}_{\rho}(s)=\sum_{a\in\mathcal{A}}\nu_{\rho}^{\pi}(s,a)=(1-\gamma)\textstyle{\sum}_{t=0}^{\infty}\gamma^{t}\mathsf{P}(s_{t}=s|s_{0}\sim\rho,a_{t}\sim\pi(\cdot|s_{t}),s_{t+1}\sim\mathsf{P}(\cdot|s_{t},a_{t}))$.
Then we have

$\displaystyle\left(\left(\chi_{\rho}^{\pi}\right)^{\top}\tilde{P}^{\pi}\right)_{s^{\prime}}$
$\displaystyle=\gamma\textstyle{\sum}_{s\in\mathcal{S}}(1-\gamma)\big{(}\textstyle{\sum}_{t=0}^{\infty}\gamma^{t}\mathsf{P}(s_{t}=s|s_{0}\sim\rho,a_{t}\sim\pi(\cdot|s_{t}),s_{t+1}\sim\mathsf{P}(\cdot|s_{t},a_{t}))\big{)}\cdot\big{(}\textstyle{\sum}_{a\in\mathcal{A}}\pi(a|s)\mathsf{P}(s^{\prime}|s,a)\big{)}$
$\displaystyle\quad+(1-\gamma)\rho(s^{\prime})\big{(}\textstyle{\sum}_{s\in
S}\chi_{\rho}^{\pi}(s)\big{)}$
$\displaystyle=(1-\gamma)\textstyle{\sum}_{t=1}^{\infty}\gamma^{t}\mathsf{P}(s_{t}=s^{\prime}|s_{0}\sim\rho,a_{t}\sim\pi(\cdot|s_{t}),s_{t+1}\sim\mathsf{P}(\cdot|s_{t},a_{t}))+(1-\gamma)\rho(s^{\prime})\big{(}\textstyle{\sum}_{s\in
S}\chi_{\rho}^{\pi}(s)\big{)}$
$\displaystyle=(1-\gamma)\left(\rho(s^{\prime})+\textstyle{\sum}_{t=1}^{\infty}\gamma^{t}\mathsf{P}(s_{t}=s^{\prime}|s_{0}\sim\rho,a_{t}\sim\pi(\cdot|s_{t}),s_{t+1}\sim\mathsf{P}(\cdot|s_{t},a_{t}))\right)$
$\displaystyle=\chi_{\rho}^{\pi}(s^{\prime}).$

The above equality implies that
$\left(\chi_{\rho}^{\pi}\right)^{\top}\tilde{P}^{\pi}=\left(\chi_{\rho}^{\pi}\right)^{\top}$.
Therefore, $\chi_{\rho}^{\pi}$ is the stationary distribution with respect to
kernel $\tilde{P}^{\pi}$. Invoking Theorem 3.1 of Mitrophanov, (2005) gives us

$\displaystyle\left\|\chi_{\rho}^{\pi^{*}_{\tau,\lambda}}-\chi_{\rho}^{\pi^{*}_{\tau,\lambda^{\prime}}}\right\|_{1}\leq\left(\lceil\log_{\beta}(C_{M}^{-1})\rceil+(1-\beta)^{-1}\right)\|\tilde{P}^{\pi^{*}_{\tau,\lambda}}-\tilde{P}^{\pi^{*}_{\tau,\lambda^{\prime}}}\|,$
(17)

where
$\|\tilde{P}^{\pi^{*}_{\tau,\lambda}}-\tilde{P}^{\pi^{*}_{\tau,\lambda^{\prime}}}\|:=\sup_{\|q\|_{1}=1}\textstyle{\sum}_{s^{\prime}\in\mathcal{S}}\big{|}\textstyle{\sum}_{s\in\mathcal{S}}q(s)(\tilde{P}^{\pi^{*}_{\tau,\lambda}}_{s,s^{\prime}}-\tilde{P}^{\pi^{*}_{\tau,\lambda^{\prime}}}_{s,s^{\prime}})\big{|}$.
We upper-bound
$\|\tilde{P}^{\pi^{*}_{\tau,\lambda}}-\tilde{P}^{\pi^{*}_{\tau,\lambda^{\prime}}}\|$
in the next steps.

$\displaystyle\|\tilde{P}^{\pi^{*}_{\tau,\lambda}}-\tilde{P}^{\pi^{*}_{\tau,\lambda^{\prime}}}\|$
$\displaystyle\leq\sup_{\|q\|_{1}=1}\textstyle{\sum}_{s^{\prime}\in\mathcal{S}}\textstyle{\sum}_{s\in\mathcal{S}}|q(s)|\big{|}(\tilde{P}^{\pi^{*}_{\tau,\lambda}}_{s,s^{\prime}}-\tilde{P}^{\pi^{*}_{\tau,\lambda^{\prime}}}_{s,s^{\prime}})\big{|}$
$\displaystyle\leq\gamma\sup_{\|q\|_{1}=1}\textstyle{\sum}_{s\in\mathcal{S}}|q(s)|\textstyle{\sum}_{a\in\mathcal{A}}\big{|}\pi^{*}_{\tau,\lambda}(a|s)-\pi^{*}_{\tau,\lambda^{\prime}}(a|s)\big{|}\big{(}\textstyle{\sum}_{s^{\prime}\in\mathcal{S}}\mathsf{P}(s^{\prime}|s,a)\big{)}$
$\displaystyle\leq\sup_{\|q\|_{1}=1}\big{(}\textstyle{\sum}_{s\in
S}|q(s)|\big{)}\cdot\max_{s\in\mathcal{S}}\|\pi^{*}_{\tau,\lambda}(\cdot|s)-\pi^{*}_{\tau,\lambda^{\prime}}(\cdot|s)\|_{1}$
$\displaystyle=\max_{s\in\mathcal{S}}\|\pi^{*}_{\tau,\lambda}(\cdot|s)-\pi^{*}_{\tau,\lambda^{\prime}}(\cdot|s)\|_{1}.$

Substituting the above inequality in to eq. 17 yields

$\displaystyle\left\|\chi_{\rho}^{\pi^{*}_{\tau,\lambda}}-\chi_{\rho}^{\pi^{*}_{\tau,\lambda^{\prime}}}\right\|_{1}\leq\left(\lceil\log_{\beta}(C_{M}^{-1})\rceil+(1-\beta)^{-1}\right)\max_{s\in\mathcal{S}}\|\pi^{*}_{\tau,\lambda}(\cdot|s)-\pi^{*}_{\tau,\lambda^{\prime}}(\cdot|s)\|_{1}.$
(18)

Moreover, we have

$\displaystyle\left\|\nu_{\rho}^{\pi^{*}_{\tau,\lambda}}-\nu_{\rho}^{\pi^{*}_{\tau,\lambda^{\prime}}}\right\|_{1}$
$\displaystyle=\sum_{s\in\mathcal{S},a\in\mathcal{S}}\left|\nu_{\rho}^{\pi^{*}_{\tau,\lambda}}(s,a)-\nu_{\rho}^{\pi^{*}_{\tau,\lambda^{\prime}}}(s,a)\right|$
$\displaystyle=\sum_{s\in\mathcal{S},a\in\mathcal{S}}\left|\chi_{\rho}^{\pi^{*}_{\tau,\lambda}}(s){\pi^{*}_{\tau,\lambda}}(a|s)-\chi_{\rho}^{\pi^{*}_{\tau,\lambda^{\prime}}}(s){\pi^{*}_{\tau,\lambda^{\prime}}}(a|s)\right|$
$\displaystyle=\sum_{s\in\mathcal{S},a\in\mathcal{S}}\left|\chi_{\rho}^{\pi^{*}_{\tau,\lambda}}(s){\pi^{*}_{\tau,\lambda}}(a|s)-\chi_{\rho}^{\pi^{*}_{\tau,\lambda^{\prime}}}(s){\pi^{*}_{\tau,\lambda}}(a|s)+\chi_{\rho}^{\pi^{*}_{\tau,\lambda^{\prime}}}(s){\pi^{*}_{\tau,\lambda}}(a|s)-\chi_{\rho}^{\pi^{*}_{\tau,\lambda^{\prime}}}(s){\pi^{*}_{\tau,\lambda^{\prime}}}(a|s)\right|$
$\displaystyle\leq\sum_{s\in\mathcal{S},a\in\mathcal{S}}\left|\chi_{\rho}^{\pi^{*}_{\tau,\lambda}}(s)-\chi_{\rho}^{\pi^{*}_{\tau,\lambda^{\prime}}}(s)\right|{\pi^{*}_{\tau,\lambda}}(a|s)+\sum_{s\in\mathcal{S},a\in\mathcal{S}}\chi_{\rho}^{\pi^{*}_{\tau,\lambda^{\prime}}}(s)\left|{\pi^{*}_{\tau,\lambda}}(a|s)-{\pi^{*}_{\tau,\lambda^{\prime}}}(a|s)\right|$
$\displaystyle=\sum_{s\in\mathcal{S}}\left|\chi_{\rho}^{\pi^{*}_{\tau,\lambda}}(s)-\chi_{\rho}^{\pi^{*}_{\tau,\lambda^{\prime}}}(s)\right|+\sum_{s\in\mathcal{S}}\chi_{\rho}^{\pi^{*}_{\tau,\lambda^{\prime}}}(s)\left\|{\pi^{*}_{\tau,\lambda}}(\cdot|s)-{\pi^{*}_{\tau,\lambda^{\prime}}}(\cdot|s)\right\|_{1}$
$\displaystyle\overset{(i)}{\leq}\left(\lceil\log_{\beta}(C_{M}^{-1})\rceil+(1-\beta)^{-1}+1\right)\max_{s\in\mathcal{S}}\|\pi^{*}_{\tau,\lambda}(\cdot|s)-\pi^{*}_{\tau,\lambda^{\prime}}(\cdot|s)\|_{1},$

where $(i)$ follows from eq. 18. $\square$

###### Lemma 7

The optimal policy $\pi^{*}_{\tau,\lambda}$ for the regularized MDP is smooth
with respect to $\lambda$, i.e., for all
$\lambda,\lambda^{\prime}\in\mathbb{R}^{m}_{+}$, we have

$\max_{s\in\mathcal{S}}\|\pi^{*}_{\tau,\lambda}(\cdot|s)-\pi^{*}_{\tau,\lambda^{\prime}}(\cdot|s)\|_{1}\leq\tfrac{2R_{\max}}{(1-\gamma)\tau}\|\lambda-\lambda^{\prime}\|_{2}.$

##### Proof

We first rewrite the Lagrangian as follows

$\displaystyle\mathcal{L}_{\tau,\mu}(\pi,\lambda)$
$\displaystyle=V_{\tau,\lambda}^{\pi}(\rho)-\langle\lambda,c\rangle+\tfrac{\mu}{2}\|\lambda\|^{2}_{2}.$
(19)

The optimal policy that maximizes eq. (19) is the optimal policy for the same
MDP but with entropy regularizer and a different reward function
$r_{\lambda}$, i.e. $\pi^{*}_{\tau,\lambda}$. In Nachum et al. , (2017) it was
shown that $\pi^{*}_{\tau,\lambda}$ is as follows

$\displaystyle\pi_{\tau,\lambda}^{*}(a|s)=\tfrac{\exp(Q_{\tau,\lambda}^{*}(s,a)/\tau)}{\sum_{a^{\prime}\in\mathcal{A}}\exp(Q_{\tau,\lambda}^{*}(s,a^{\prime})/\tau)},\quad\forall
s\in\mathcal{S},a\in\mathcal{A}.$

Thus, for any $s\in\mathcal{S}$ and $a\in\mathcal{A}$, we have that

$\displaystyle|\log\left(\pi^{*}_{\tau,\lambda}(s,a)\right)-\log\left(\pi^{*}_{\tau,\lambda^{\prime}}(s,a)\right)|$
$\displaystyle=\left|\tfrac{1}{\tau}(Q_{\tau,\lambda}^{*}(s,a)-Q_{\tau,\lambda^{\prime}}^{*}(s,a))-\left(\log\left(\sum_{a^{\prime}\in\mathcal{A}}\exp\left(\tfrac{Q_{\tau,\lambda}^{*}(s,a^{\prime})}{\tau}\right)\right)-\log\left(\sum_{a^{\prime}\in\mathcal{A}}\exp\left(\tfrac{Q_{\tau,\lambda^{\prime}}^{*}(s,a^{\prime})}{\tau}\right)\right)\right)\right|$
$\displaystyle\overset{(i)}{\leq}\tfrac{1}{\tau}|Q_{\tau,\lambda}^{*}(s,a)-Q_{\tau,\lambda^{\prime}}^{*}(s,a)|+\tfrac{1}{\tau}\|Q_{\tau,\lambda}^{*}(s,\cdot)-Q_{\tau,\lambda^{\prime}}^{*}(s,\cdot)\|_{\infty}$
$\displaystyle\leq\tfrac{2}{\tau}\|Q_{\tau,\lambda}^{*}-Q_{\tau,\lambda^{\prime}}^{*}\|_{\infty},$

where $(i)$ follows from the fact that $|x+y|\leq|x|+|y|$ and 2. Further
applying 1, we have that

$\displaystyle|\pi^{*}_{\tau,\lambda}(s,a)-\pi^{*}_{\tau,\lambda^{\prime}}(s,a)|$
$\displaystyle\leq\tfrac{2}{\tau}\|Q_{\tau,\lambda}^{*}-Q_{\tau,\lambda^{\prime}}^{*}\|_{\infty}$
$\displaystyle=\tfrac{2}{\tau}\max_{s\in\mathcal{S},a\in\mathcal{A}}|Q_{\tau,\lambda}^{*}(s,a)-Q_{\tau,\lambda^{\prime}}^{*}(s,a)|$
$\displaystyle\overset{(i)}{\leq}\tfrac{2}{\tau}\max_{s\in\mathcal{S},a\in\mathcal{A}}\max_{\pi\in\Pi}|Q_{\tau,\lambda}^{\pi}(s,a)-Q_{\tau,\lambda^{\prime}}^{\pi}(s,a)|$
$\displaystyle\overset{(ii)}{\leq}\tfrac{2R_{\max}}{(1-\gamma)\tau}\|\lambda-\lambda^{\prime}\|_{2},$
(20)

where $(i)$ follows from 3, and $(ii)$ follows from the uniform upper bound
developed below,

$\displaystyle|Q_{\tau,\lambda}^{\pi}(s,a)-Q_{\tau,\lambda^{\prime}}^{\pi}(s,a)|$
$\displaystyle\quad=\left|r_{\lambda}(s,a)+\gamma\mathbb{E}_{s^{\prime}\sim\mathsf{P}(\cdot|s,a)}\left[V^{\pi}_{\tau,\lambda}(s^{\prime})\right]-r_{\lambda^{\prime}}(s,a)-\gamma\mathbb{E}_{s^{\prime}\sim\mathsf{P}(\cdot|s,a)}\left[V^{\pi}_{\tau,\lambda^{\prime}}(s^{\prime})\right]\right|$
$\displaystyle\quad\leq|r_{\lambda}(s,a)-r_{\lambda^{\prime}}(s,a)|+\gamma\mathbb{E}_{s^{\prime}\sim\mathsf{P}(\cdot|s,a)}\left[\left|V^{\pi}_{\tau,\lambda}(s^{\prime})-V^{\pi}_{\tau,\lambda^{\prime}}(s^{\prime})\right|\right]$
$\displaystyle\quad\leq\tfrac{R_{\max}}{1-\gamma}\|\lambda-\lambda^{\prime}\|_{2}.$

Taking maximum on the left-hand-side of eq. 20 concludes the proof. $\square$

###  C.3 Proof of the Propositions

####  C.3.1 Proof of 1

We first note that $\Pi$ is a compact set. Moreover,
$\mathcal{L}_{\tau,\mu}(\pi,\lambda)$ is continuous in both $\pi$ and
$\lambda$, and is convex in $\lambda$ for any given $\pi$. The maximum of
$\mathcal{L}_{\tau,\mu}(\pi,\lambda)$ is attained uniquely at
$\pi^{*}_{\tau,\lambda}$. Thus, by Danskin’s theorem, we obtain that

$\nabla
d_{\tau,\mu}(\lambda)=\tfrac{\partial}{\partial\lambda}\mathcal{L}_{\tau,\mu}(\pi,\lambda)|_{\pi=\pi^{*}_{\tau,\lambda}}=V^{\pi^{*}_{\tau,\lambda}}(\rho)-c+\mu\lambda.$

Moreover, it can be shown that

$\displaystyle\|\nabla d_{\tau,\mu}(\lambda)-\nabla
d_{\tau,\mu}(\lambda^{\prime})\|_{2}$
$\displaystyle=\|V^{\pi^{*}_{\tau,\lambda}}(\rho)-c+\mu\lambda-(V^{\pi^{*}_{\tau,\lambda^{\prime}}}(\rho)-c+\mu\lambda^{\prime})\|_{2}$
$\displaystyle\leq\|V^{\pi^{*}_{\tau,\lambda}}(\rho)-V^{\pi^{*}_{\tau,\lambda^{\prime}}}(\rho)\|_{2}+\mu\|\lambda-\lambda^{\prime}\|_{2}$
$\displaystyle=\tfrac{1}{1-\gamma}\bigg{(}\sum_{i=1}^{m}(\langle\nu_{\rho}^{\pi^{*}_{\tau,\lambda}}-\nu_{\rho}^{\pi^{*}_{\tau,\lambda^{\prime}}},r_{i}\rangle)^{2}\bigg{)}^{1/2}+\mu\|\lambda-\lambda^{\prime}\|_{2}$
$\displaystyle\leq\tfrac{R_{\max}}{1-\gamma}\|\nu_{\rho}^{\pi^{*}_{\tau,\lambda}}-\nu_{\rho}^{\pi^{*}_{\tau,\lambda^{\prime}}}\|_{1}+\mu\|\lambda-\lambda^{\prime}\|_{2}$
$\displaystyle\overset{(i)}{\leq}\tfrac{R_{\max}L_{\nu}}{1-\gamma}\max_{s\in\mathcal{S}}\|\pi^{*}_{\tau,\lambda}(\cdot|s)-\pi^{*}_{\tau,\lambda^{\prime}}(\cdot|s)\|_{1}+\mu\|\lambda-\lambda^{\prime}\|_{2}$
$\displaystyle\overset{(ii)}{\leq}\left(\tfrac{2R^{2}_{\max}L_{\nu}}{(1-\gamma)^{2}\tau}+\mu\right)\|\lambda-\lambda^{\prime}\|_{2},$

where $(i)$ follows from 6 and $(ii)$ follows from 7. Then setting
$L_{d}=\tfrac{2R_{\max}^{2}L_{\nu}}{(1-\gamma)^{2}\tau}+\mu$ completes the
proof.

####  C.3.2 Proof of 2

First, we construct an auxiliary non-stationary policy $\pi_{N}$ as follows.
Let $N$ be a random index variable with $\mathrm{Pr}(N=1)=(1-\alpha)^{T-1}$,
and $\mathrm{Pr}(N=i)=\alpha(1-\alpha)^{T-i}$ for $i=2,\dots,T$. To execute
the algorithm, an agent first randomly generates a value for $N$, and then
applies the policy $\pi_{N}(\cdot|s_{t})$ throughout the process. By
construction, we have

$\displaystyle\nu_{\rho}^{\pi_{N}}(s,a)=(1-\alpha)^{T-1}\nu_{\rho}^{\pi_{1}}(s,a)+\sum\nolimits_{t=2}^{T}\alpha(1-\alpha)^{T-t}\nu_{\rho}^{\pi_{t}}(s,a),$
(21)
$\displaystyle\chi_{\rho}^{\pi_{N}}(s)=(1-\alpha)^{T-1}\chi_{\rho}^{\pi_{1}}(s)+\sum\nolimits_{t=2}^{T}\alpha(1-\alpha)^{T-t}\chi_{\rho}^{\pi_{t}}(s).$
(22)

Then by the definition of $\tilde{\pi}$, we have

$\displaystyle\nu_{\rho}^{\pi_{N}}(s,a)=\chi_{\rho}^{\pi_{N}}(s)\tilde{\pi}(a|s).$
(23)

Furthermore, applying $\tilde{\pi}$ as a stationary policy, we obtain

$\displaystyle\nu_{\rho}^{\tilde{\pi}}(s,a)=\chi_{\rho}^{\tilde{\pi}}(s)\tilde{\pi}(a|s).$
(24)

Then it suffices to show that
$\chi_{\rho}^{\pi_{N}}(s)=\chi_{\rho}^{\tilde{\pi}}(s)$, because eq. 23 and
eq. 24 together imply

$\nu_{\rho}^{\tilde{\pi}}(s,a)=\nu_{\rho}^{\pi_{N}}(s,a)=(1-\alpha)^{T-1}\nu_{\rho}^{\pi_{1}}(s,a)+\sum\nolimits_{t=2}^{T}\alpha(1-\alpha)^{T-t}\nu_{\rho}^{\pi_{t}}(s,a),$

which further yields that
$V_{i}^{\tilde{\pi}}(\rho)=(1-\alpha)^{T-1}V_{i}^{\pi_{1}}(\rho)+\sum\nolimits_{t=2}^{T}\alpha(1-\alpha)^{T-t}V_{i}^{\pi_{t}}(\rho)$
holds for all $i=0,\ldots,m$ due to the fact that
$V_{i}^{\pi}(\rho)=\left\langle r_{i},\nu_{\rho}^{\pi}\right\rangle$.

To show that $\chi_{\rho}^{\pi_{N}}(s)=\chi_{\rho}^{\tilde{\pi}}(s)$, we will
prove that they are both equal to the unique fixed point of a Bellman
operator. The following proof is the one in Szepesvári, (2020) and we include
them here for completeness. To this end, for a policy $\pi$ and a measure
$\nu$ over the state space $\mathcal{S}$, we define a Bellman operator
$\mathcal{B}_{\rho}^{\pi}$ as: for all $s\in\mathcal{S}$,

$\displaystyle(\mathcal{B}_{\rho}^{\pi}(\chi))_{s}\coloneqq(1-\gamma)\rho(s)+\gamma\sum_{s^{\prime},a^{\prime}}\mathsf{P}(s|s^{\prime},a^{\prime})\pi(a^{\prime}|s^{\prime})\chi(s^{\prime}).$

It is easy to verify that $\mathcal{B}_{\rho}^{\pi}$ satisfies the
$\gamma$-contraction property with respect to $\ell_{\infty}$ norm, i.e., for
any $\chi,\chi^{\prime}\in\mathbb{R}^{|\mathcal{S}|}$, we have

$\|\mathcal{B}_{\rho}^{\pi}(\chi)-\mathcal{B}_{\rho}^{\pi}(\chi^{\prime})\|_{\infty}\leq\gamma\|\chi-\chi^{\prime}\|_{\infty}.$

Thus, by the Banach–Caccioppoli fixed-point theorem, on the compact bounded
set (the probability simplex over $\mathcal{S}$), $\mathcal{B}_{\rho}^{\pi}$
has a unique fixed point. We first show that $\chi_{\rho}^{\pi}$ is a fixed
point of $\mathcal{B}_{\rho}^{\pi}$ for any $\pi$ as follows.

$\displaystyle\chi_{\rho}^{\pi}(s)$
$\displaystyle=(1-\gamma)\sum_{t=0}^{\infty}\gamma^{t}\mathrm{Pr}\\{s_{t}=s|s_{0}\sim\rho,\pi\\}$
$\displaystyle=(1-\gamma)\rho(s)+(1-\gamma)\sum_{t=1}^{\infty}\gamma^{t}\mathrm{Pr}(s_{t}=s|s_{0}\sim\rho,\pi)$
$\displaystyle\overset{(i)}{=}(1-\gamma)\rho(s)+(1-\gamma)\sum_{t=1}^{\infty}\gamma^{t}\sum_{s^{\prime},a^{\prime}}\big{(}\mathrm{Pr}(s_{t}=s|s_{t-1}=s^{\prime},a_{t-1}=a^{\prime})$
$\displaystyle\qquad\quad\quad\qquad\quad\quad\cdot\mathrm{Pr}(s_{t-1}=s^{\prime},a_{t-1}=a^{\prime}|s_{0}\sim\rho,\pi)\big{)}$
$\displaystyle=(1-\gamma)\rho(s)+\gamma\sum_{s^{\prime},a^{\prime}}\mathrm{Pr}(s_{t}=s|s_{t-1}=s^{\prime},a_{t-1}=a^{\prime})\pi(a^{\prime}|s^{\prime})$
$\displaystyle\qquad\quad\quad\qquad\quad\quad\cdot(1-\gamma)\big{(}\sum_{t=1}^{\infty}\gamma^{t-1}\mathrm{Pr}(s_{t-1}=s^{\prime}|s_{0}\sim\rho,\pi)\big{)}$
$\displaystyle=(1-\gamma)\rho(s)+\gamma\sum_{s^{\prime},a^{\prime}}\mathsf{P}(s|s^{\prime},a^{\prime}){\pi}(a^{\prime}|s^{\prime})\chi_{\rho}^{\pi}(s^{\prime})$
$\displaystyle=(\mathcal{B}^{\pi}_{\rho}(\chi^{\pi}_{\rho}))_{s},$

where $(i)$ follows from the property of Markov chain. Thus,
$\chi_{\rho}^{\tilde{\pi}}$ is a fixed point of
$\mathcal{B}_{\rho}^{\tilde{\pi}}$.

Then, it is sufficient to show that $\chi_{\rho}^{\pi_{N}}$ is also a fixed
point of $\mathcal{B}^{\tilde{\pi}}_{\rho}$, which is given as follows:

$\displaystyle\chi_{\rho}^{\pi_{N}}(s)$
$\displaystyle=(1-\gamma)\rho(s)+(1-\gamma)\sum_{t=1}^{\infty}\gamma^{t}\mathrm{Pr}(s_{t}=s|s_{0}\sim\rho,\pi_{N})$
$\displaystyle=(1-\gamma)\rho(s)+(1-\gamma)\sum_{t=1}^{\infty}\gamma^{t}\sum_{s^{\prime},a^{\prime}}\bigg{(}\mathrm{Pr}(s_{t-1}=s^{\prime},a_{t-1}=a^{\prime}|s_{0}\sim\rho,\pi_{N})$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\cdot\mathrm{Pr}(s_{t}=s|s_{t-1}=s^{\prime},a_{t-1}=a^{\prime})\bigg{)}$
$\displaystyle\overset{(i)}{=}(1-\gamma)\rho(s)+\gamma\sum_{s^{\prime},a^{\prime}}\mathsf{P}(s|s^{\prime},a^{\prime})\nu_{\rho}^{\pi_{N}}(s^{\prime},a^{\prime})$
$\displaystyle\overset{(ii)}{=}(1-\gamma)\rho(s)+\gamma\sum_{s^{\prime},a^{\prime}}\mathsf{P}(s|s^{\prime},a^{\prime})\tilde{\pi}(a^{\prime}|s^{\prime})\xi_{\rho}^{\pi_{N}}(s^{\prime},a^{\prime})$
$\displaystyle=(\mathcal{B}^{\tilde{\pi}}_{\rho}(\chi^{\pi_{N}}_{\rho}))_{s},$

where $(i)$ follows by rearranging the summation and $(ii)$ follows from the
definitions of $\nu^{\pi_{N}}_{\rho}(s,a)$ and $\chi_{\rho}^{\pi_{N}}(s)$.
Thus, $\chi_{\rho}^{\pi_{N}}(s)=\chi_{\rho}^{\tilde{\pi}}(s)$ because they
both equal the unique fixed point of $\mathcal{B}^{\tilde{\pi}}_{\rho}$. This
yields the desired result as we argue above, and concludes the proof.

####  C.3.3 Proof of 3

For convenience of the proof, define following notations

$\displaystyle\mathcal{L}_{\tau}(\pi,\lambda)=\mathcal{L}(\pi,\lambda)+\tau\mathcal{H}(\pi),$

and

$\displaystyle
d_{\tau}(\lambda)=\max_{\pi\in\Pi}\left\\{\mathcal{L}_{\tau}(\pi,\lambda)\right\\}.$

First, we build the recursive relationship for
$\\{d_{\tau}(\underline{\lambda}_{t})\\}$. By the definition of
$d_{\tau}(\cdot)$, for $t=1,...,T-1$, we have

$\displaystyle d_{\tau}(\underline{\lambda}_{t+1})$
$\displaystyle=V_{0}^{\pi^{*}_{\tau,\underline{\lambda}_{t+1}}}(\rho)+\underline{\lambda}_{t+1}^{\top}({V}^{\pi^{*}_{\tau,\underline{\lambda}_{t+1}}}(\rho)-c)$
$\displaystyle=V_{0}^{\pi_{t+1}}(\rho)+\underline{\lambda}_{t+1}^{\top}({V}^{\pi_{t+1}}(\rho)-c)+\Delta_{t+1}$
$\displaystyle\overset{(i)}{=}(1-\alpha)[V_{0}^{\pi_{t+1}}(\rho)+\underline{\lambda}_{t}^{\top}({V}^{\pi_{t+1}}(\rho)-c)]$
$\displaystyle\quad+[(1-q)\alpha+q][V_{0}^{\pi_{t+1}}(\rho)+\lambda_{t}^{\top}({V}^{\pi_{t+1}}(\rho)-c)]$
$\displaystyle\quad-q(1-\alpha)[V_{0}^{\pi_{t+1}}(\rho)+\lambda_{t-1}^{\top}({V}^{\pi_{t+1}}(\rho)-c)]+\Delta_{t+1}$
$\displaystyle\overset{(ii)}{\leq}(1-\alpha)d_{\tau}(\underline{\lambda}_{t})+[(1-q)\alpha+q][V_{0}^{\pi_{t+1}}(\rho)+\lambda_{t}^{\top}({V}^{\pi_{t+1}}(\rho)-c)]$
$\displaystyle\quad-q(1-\alpha)[V_{0}^{\pi_{t+1}}(\rho)+\lambda_{t-1}^{\top}({V}^{\pi_{t+1}}(\rho)-c)]+\Delta_{t+1},$

where $(i)$ follows from the update rule of the algorithm, and $(ii)$ follows
from the definition of $d_{\tau}(\cdot)$. Multiplying $(1-\alpha)^{T-1-t}$ on
both sides of the above inequality and summing up from $t=1$ to $T-1$, we
obtain that

$\displaystyle d_{\tau}(\underline{\lambda}_{T})$
$\displaystyle\leq(1-\alpha)^{T-1}d_{\tau}(\underline{\lambda}_{1})+\sum\nolimits_{t=2}^{T}(1-\alpha)^{T-t}[(1-q)\alpha+q][V_{0}^{\pi_{t}}(\rho)+\lambda_{t-1}^{\top}({V}^{\pi_{t}}(\rho)-c)]$
$\displaystyle\quad-\sum\nolimits_{t=2}^{T}(1-\alpha)^{T-t}q(1-\alpha)[V_{0}^{\pi_{t}}(\rho)+\lambda_{t-2}^{\top}({V}^{\pi_{t}}(\rho)-c)]+\sum\nolimits_{t=2}^{T}(1-\alpha)^{T-t}\Delta_{t}$
$\displaystyle\overset{(i)}{\leq}(1-\alpha)^{T-1}V_{0}^{\pi_{1}}(\rho)+\sum\nolimits_{t=2}^{T}(1-\alpha)^{T-t}[(1-q)\alpha+q][V_{0}^{\pi_{t}}(\rho)+\lambda_{t-1}^{\top}({V}^{\pi_{t}}(\rho)-c)]$
$\displaystyle\quad-\sum\nolimits_{t=2}^{T}(1-\alpha)^{T-t}q(1-\alpha)[V_{0}^{\pi_{t}}(\rho)+\lambda_{t-2}^{\top}({V}^{\pi_{t}}(\rho)-c)]+\sum\nolimits_{t=1}^{T}(1-\alpha)^{T-t}\Delta_{t}$
$\displaystyle\leq(1-\alpha)^{T-1}V_{0}^{\pi_{1}}(\rho)+\sum\nolimits_{t=2}^{T}\alpha(1-\alpha)^{T-t}(V_{0}^{\pi_{t}}(\rho)+\lambda_{t-1}^{\top}({V}^{\pi_{t}}(\rho)-c))$
$\displaystyle\quad+\sum\nolimits_{t=2}^{T}(1-\alpha)^{T-t+1}q(\lambda_{t-1}-\lambda_{t-2})^{\top}({V}^{\pi_{t}}(\rho)-c)+\sum\nolimits_{t=1}^{T}(1-\alpha)^{T-t}\Delta_{t},$
(25)

where $(i)$ follows from $\underline{\lambda}_{1}=\lambda_{0}=0$.

Next, we build the connection between $d_{\tau}(\underline{\lambda}_{T})$ and
the optimal primal function value $V_{0}^{*}(\rho)$. From the above inequality
and the definition of $d_{\tau}(\cdot)$ and $d_{\tau,\mu}(\cdot)$, it follows
that

$\displaystyle d_{\tau}(\underline{\lambda}_{T})$
$\displaystyle=d_{\tau,\mu}(\underline{\lambda}_{T})-\tfrac{\mu}{2}\|\underline{\lambda}_{T}\|_{2}^{2}$
$\displaystyle\geq
d_{\tau,\mu}(\lambda_{\tau,\mu}^{*})-\tfrac{\mu}{2}\|\underline{\lambda}_{T}\|_{2}^{2}$
$\displaystyle=d_{\tau}(\lambda_{\tau,\mu}^{*})+\tfrac{\mu}{2}(\|\lambda_{\tau,\mu}^{*}\|_{2}^{2}-\|\underline{\lambda}_{T}\|_{2}^{2})$
$\displaystyle\overset{(i)}{\geq}V_{0}^{*}(\rho)-\tfrac{\tau}{1-\gamma}\log\left(|\mathcal{A}|\right)+\tfrac{\mu}{2}(\|\lambda_{\tau,\mu}^{*}\|_{2}^{2}-\|\underline{\lambda}_{T}\|_{2}^{2}),$
(26)

where $(i)$ follows from the inductions below

$\displaystyle d_{\tau}(\lambda_{\tau,\mu}^{*})$
$\displaystyle\geq\min_{\lambda\in\mathbb{R}_{+}^{m}}d_{\tau}(\lambda)$
$\displaystyle\overset{(i)}{=}\max_{\pi\in\Pi}\\{V_{0}^{\pi}(\rho)+\tau\mathcal{H}(\pi):V_{i}^{\pi}(\rho)\geq
c_{i}\\}$
$\displaystyle\overset{(ii)}{\geq}\max_{\pi\in\Pi}\\{V_{0}^{\pi}(\rho):V_{i}^{\pi}(\rho)\geq
c_{i}\\}-\tfrac{\tau}{1-\gamma}\log(|\mathcal{A}|)$
$\displaystyle=V_{0}^{*}(\rho)-\tfrac{\tau}{1-\gamma}\log(|\mathcal{A}|),$

where $(i)$ follows from the zero duality gap of constrained reinforcement
learning (Paternain et al. ,, 2019a), and $(ii)$ follows from 3 and
$|\mathcal{H}(\pi)|\leq\log(|\mathcal{A}|)$ for all $\pi$.

Combining eqs. 25 and 26, it follows that

$\displaystyle
V_{0}^{*}(\rho)-\left((1-\alpha)^{T-1}V_{0}^{\pi_{1}}(\rho)+\sum\nolimits_{t=2}^{T}\alpha(1-\alpha)^{T-t}V_{0}^{\pi_{t}}(\rho)\right)$
$\displaystyle\leq$
$\displaystyle\sum\nolimits_{t=2}^{T}\alpha(1-\alpha)^{T-t}\lambda_{t-1}^{\top}({V}^{\pi_{t}}(\rho)-c)+\sum\nolimits_{t=2}^{T}(1-\alpha)^{T-t+1}q(\lambda_{t-1}-\lambda_{t-2})^{\top}({V}^{\pi_{t}}(\rho)-c)$
$\displaystyle+\sum\nolimits_{t=1}^{T}(1-\alpha)^{T-t}\Delta_{t}+\tfrac{\tau}{1-\gamma}\log\left(|\mathcal{A}|\right)+\tfrac{\mu}{2}(\|\underline{\lambda}_{T}\|_{2}^{2}-\|\lambda_{\tau,\mu}^{*}\|_{2}^{2})$
$\displaystyle\leq$
$\displaystyle\sum\nolimits_{t=2}^{T}\alpha(1-\alpha)^{T-t}\lambda_{t}^{\top}({V}^{\pi_{t}}(\rho)-c)+\sum\nolimits_{t=2}^{T}(1-\alpha)^{T-t+1}q(\lambda_{t-1}-\lambda_{t-2})^{\top}({V}^{\pi_{t}}(\rho)-c)$
$\displaystyle+\sum\nolimits_{t=2}^{T}\alpha(1-\alpha)^{T-t}(\lambda_{t-1}-\lambda_{t})^{\top}({V}^{\pi_{t}(\rho)}-c)+\sum\nolimits_{t=1}^{T}(1-\alpha)^{T-t}\Delta_{t}+\tfrac{\tau}{1-\gamma}\log\left(|\mathcal{A}|\right)$
$\displaystyle+\tfrac{\mu}{2}(\|\underline{\lambda}_{T}\|_{2}^{2}-\|\lambda_{\tau,\mu}^{*}\|_{2}^{2})$
$\displaystyle\leq$
$\displaystyle\sum\nolimits_{t=2}^{T}\alpha(1-\alpha)^{T-t}\lambda_{t}^{\top}({V}^{\pi_{t}}(\rho)-c)+\left(\sum\nolimits_{t=2}^{T}\alpha(1-\alpha)^{T-t+1}\|\lambda_{t-1}-\lambda_{t-2}\|_{2}\right)\tfrac{q}{\alpha}\tfrac{R_{\max}}{1-\gamma}$
$\displaystyle+\left(\sum\nolimits_{t=2}^{T}\alpha(1-\alpha)^{T-t}\|\lambda_{t}-\lambda_{t-1}\|_{2}\right)\tfrac{R_{\max}}{1-\gamma}+\sum\nolimits_{t=1}^{T}(1-\alpha)^{T-t}\Delta_{t}+\tfrac{\tau}{1-\gamma}\log|\mathcal{A}|+2\mu
mB^{2}.$ (27)

In order to analyze the first term of the right hand side of (27), we exploit
the first order optimality condition of step 7 in Algorithm 2 to upper bound
the term $(\lambda-\lambda_{t})^{\top}(c-{V}^{\pi_{t}}(\rho))$. The first-
order optimality condition implies that for $t=1,...,T$,
$\forall\lambda\in\Lambda$,

$\displaystyle 0$
$\displaystyle\leq\langle\eta({V}^{\pi_{t}}(\rho)-c+\mu\underline{\lambda}_{t})+\eta\mu(\lambda_{t}-\underline{\lambda}_{t})+(\lambda_{t}-\lambda_{t-1}),\lambda-\lambda_{t}\rangle$
$\displaystyle=\langle\eta({V}^{\pi_{t}}(\rho)-c)+(\eta\mu+1)\lambda_{t}-\lambda_{t-1},\lambda-\lambda_{t}\rangle$
$\displaystyle=\langle(\eta\mu+1)\lambda_{t}-\lambda_{t-1},\lambda-\lambda_{t}\rangle+\eta(\lambda-\lambda_{t})^{\top}({V}^{\pi_{t}}(\rho)-c)$
$\displaystyle\leq\|\lambda_{t-1}-(\eta\mu+1)\lambda_{t}\|_{2}\|\lambda-\lambda_{t}\|_{2}+\eta(\lambda-\lambda_{t})^{\top}({V}^{\pi_{t}}(\rho)-c)$
$\displaystyle\leq 2\|\lambda_{t}-\lambda_{t-1}\|_{2}\sqrt{m}B+4\eta\mu
mB^{2}+\eta(\lambda-\lambda_{t})^{\top}({V}^{\pi_{t}}(\rho)-c).$ (28)

Adding both sides of eqs. 27 and 28, we have that

$\displaystyle
V_{0}^{*}(\rho)-\left((1-\alpha)^{T-1}V_{0}^{\pi_{1}}(\rho)+\sum\nolimits_{t=2}^{T}\alpha(1-\alpha)^{T-t}(V_{0}^{\pi_{t}}(\rho)+\lambda^{\top}(c-{V}^{\pi_{t}}(\rho)))\right)$
$\displaystyle\leq$
$\displaystyle\left(\sum\nolimits_{t=1}^{T}\alpha(1-\alpha)^{T-t}\|\lambda_{t}-\lambda_{t-1}\|_{2}\right)\left(\tfrac{q}{\alpha}\tfrac{R_{\max}}{1-\gamma}+\tfrac{R_{\max}}{1-\gamma}+\tfrac{2\sqrt{m}B}{\eta}\right)$
$\displaystyle+\sum\nolimits_{t=1}^{T}(1-\alpha)^{T-t}\Delta_{t}+\tfrac{\tau}{1-\gamma}\log|\mathcal{A}|+6\mu
mB^{2}$ $\displaystyle\overset{(i)}{\leq}$
$\displaystyle\left(\sum\nolimits_{t=1}^{T}\alpha(1-\alpha)^{T-t}\right)^{\tfrac{1}{2}}\left(\sum\nolimits_{t=1}^{T}\alpha(1-\alpha)^{T-t}\|\lambda_{t}-\lambda_{t-1}\|_{2}^{2}\right)^{\tfrac{1}{2}}\left(\tfrac{q}{\alpha}\tfrac{R_{\max}}{1-\gamma}+\tfrac{R_{\max}}{1-\gamma}+\tfrac{2\sqrt{m}B}{\eta}\right)$
$\displaystyle+\sum\nolimits_{t=1}^{T}(1-\alpha)^{T-t}\Delta_{t}+\tfrac{\tau}{1-\gamma}\log|\mathcal{A}|+6\mu
mB^{2}$ $\displaystyle\leq$
$\displaystyle\left(\sum\nolimits_{t=1}^{T}\alpha(1-\alpha)^{T-t}\|\lambda_{t}-\lambda_{t-1}\|_{2}^{2}\right)^{\tfrac{1}{2}}\left(\tfrac{q}{\alpha}\tfrac{R_{\max}}{1-\gamma}+\tfrac{R_{\max}}{1-\gamma}+\tfrac{2\sqrt{m}B}{\eta}\right)$
$\displaystyle+\sum\nolimits_{t=1}^{T}(1-\alpha)^{T-t}\Delta_{t}+\tfrac{\tau}{1-\gamma}\log|\mathcal{A}|+6\mu
mB^{2},$

where $(i)$ follows from Hölder’s inequality. This yields the desired result
as we argue above, and concludes the proof.

####  C.3.4 Proof of 4

Denote $g_{t}=\bar{\lambda}_{t}-\underline{\lambda}_{t}$. It follows from
lines 4, 7 and 8 of Algorithm 2 that

$\displaystyle g_{t}$
$\displaystyle=(q-\alpha)\bar{\lambda}_{t-1}+\alpha\lambda_{t}-q\lambda_{t-1}$
$\displaystyle=\alpha[\lambda_{t}-\tfrac{\alpha-q}{\alpha(1-q)}\underline{\lambda}_{t}-\tfrac{q(1-\alpha)}{\alpha(1-q)}\lambda_{t-1}].$
(29)

By the convexity of $d_{\tau,\mu}(\cdot)$, we have that

$\displaystyle d_{\tau,\mu}(\bar{\lambda}_{t})$ $\displaystyle\leq
d_{\tau,\mu}(\underline{\lambda}_{t})+\langle\nabla
d_{\tau,\mu}(\underline{\lambda}_{t}),\bar{\lambda}_{t}-\underline{\lambda}_{t}\rangle+\tfrac{L_{d}}{2}\|g_{t}\|_{2}^{2}$
$\displaystyle=(1-\alpha)[d_{\tau,\mu}(\underline{\lambda}_{t})+\langle\nabla
d_{\tau,\mu}(\underline{\lambda}_{t}),\bar{\lambda}_{t-1}-\underline{\lambda}_{t}\rangle]+\alpha[d_{\tau,\mu}(\underline{\lambda}_{t})+\langle\nabla
d_{\tau,\mu}(\underline{\lambda}_{t}),\lambda_{t}-\underline{\lambda}_{t}\rangle]$
$\displaystyle\quad+\tfrac{L_{d}}{2}\|g_{t}\|_{2}^{2}$
$\displaystyle\overset{(i)}{\leq}(1-\alpha)d_{\tau,\mu}(\bar{\lambda}_{t-1})+\alpha[d_{\tau,\mu}(\underline{\lambda}_{t})+\langle\nabla
d_{\tau,\mu}(\underline{\lambda}_{t}),\lambda_{t}-\underline{\lambda}_{t}\rangle+\tfrac{L_{d}(a-q)}{2(1-q)}\|\lambda_{t}-\underline{\lambda}_{t}\|_{2}^{2}$
$\displaystyle\quad+\tfrac{L_{d}q(1-\alpha)}{2(1-q)}\|\lambda_{t}-\lambda_{t-1}\|_{2}^{2}]$
$\displaystyle\overset{(ii)}{\leq}(1-\alpha)d_{\tau,\mu}(\bar{\lambda}_{t-1})+\alpha[d_{\tau,\mu}(\underline{\lambda}_{t})+\langle\nabla
d_{\tau,\mu}(\underline{\lambda}_{t}),\lambda_{t}-\underline{\lambda}_{t}\rangle+\tfrac{\mu}{2}\|\lambda_{t}-\underline{\lambda}_{t}\|_{2}^{2}$
$\displaystyle\quad+\tfrac{1}{4\eta}\|\lambda_{t}-\lambda_{t-1}\|_{2}^{2}],$

where $(i)$ follows from eq. 29, the convexity of $d_{\tau,\mu}(\cdot)$, the
convexity of $\|\cdot\|_{2}^{2}$ and the fact that $\alpha\geq q$, and $(ii)$
follows from the fact that $\tfrac{L_{d}(\alpha-q)}{1-q}\leq\mu$ and
$\tfrac{L_{d}q(1-\alpha)}{1-q}\leq\tfrac{1}{2\eta}$. Combining the above
inequality and eq. 15, we obtain that

$\displaystyle d_{\tau,\mu}(\bar{\lambda}_{t})$
$\displaystyle\leq(1-\alpha)d_{\tau,\mu}(\bar{\lambda}_{t-1})+\alpha[d_{\tau,\mu}(\underline{\lambda}_{t})+\langle\nabla
d_{\tau,\mu}(\underline{\lambda}_{t}),\lambda-\underline{\lambda}_{t}\rangle+\tfrac{\mu}{2}\|\lambda-\underline{\lambda}_{t}\|_{2}^{2}]$
$\displaystyle\quad+\tfrac{\alpha}{2\eta}\|\lambda-\lambda_{t-1}\|_{2}^{2}-\tfrac{\alpha}{2}(\mu+\tfrac{1}{\eta})\|\lambda-\lambda_{t}\|_{2}^{2}-\tfrac{\alpha}{4\eta}\|\lambda_{t}-\lambda_{t-1}\|_{2}^{2}+\alpha\langle\delta_{t},\lambda-\lambda_{t}\rangle$
$\displaystyle\leq(1-\alpha)d_{\tau,\mu}(\bar{\lambda}_{t-1})+\alpha
d_{\tau,\mu}(\lambda)+\tfrac{\alpha}{2\eta}\|\lambda-\lambda_{t-1}\|_{2}^{2}-\tfrac{\alpha}{2}(\mu+\tfrac{1}{\eta})\|\lambda-\lambda_{t}\|_{2}^{2}$
$\displaystyle\quad-\tfrac{\alpha}{4\eta}\|\lambda_{t}-\lambda_{t-1}\|_{2}^{2}+\alpha\langle\delta_{t},\lambda-\lambda_{t}\rangle.$

Subtracting $d_{\tau,\mu}(\lambda)$ on both sides of the above inequality and
rearranging the terms, we have

$\displaystyle
K_{t}(\lambda)+\tfrac{\alpha}{4\eta}\|\lambda_{t}-\lambda_{t-1}\|_{2}^{2}$
$\displaystyle\leq(1-\alpha)[d_{\tau,\mu}(\bar{\lambda}_{t-1})-d_{\tau,\mu}(\lambda)+\tfrac{\alpha}{2\eta(1-\alpha)}\|\lambda_{t-1}-\lambda\|_{2}^{2}]$
$\displaystyle\quad+\alpha\langle\delta_{t},\lambda-\lambda_{t}\rangle$
$\displaystyle\overset{(i)}{\leq}(1-\alpha)K_{t-1}(\lambda)+\alpha\langle\delta_{t},\lambda-\lambda_{t}\rangle,$

where $(i)$ follows from the fact that
$\tfrac{1}{\eta(1-\alpha)}\leq\mu+\tfrac{1}{\eta}$. The desired result follows
directly by multiplying $(1-\alpha)^{T-t}$ on both sides of the above
inequality and summing up from $t=1$ to $T$.

####  C.3.5 Proof of 5

We first define the perturbation function, given $\zeta\in\mathbb{R}^{m}$,
$f(\zeta)=\max\\{V_{0}^{\pi}(\rho)|V_{i}^{\pi}(\rho)\geq c_{i}+\zeta_{i}\\}$.
It was shown in (Paternain et al. ,, 2019b, Proposition 1) that $f(\zeta)$ is
concave in $\zeta$.

For a given $\zeta\in\mathbb{R}^{m}$ and any policy
$\pi\in\left\\{\pi\in\Pi|V_{i}^{\pi}(\rho)\geq c_{i}+\zeta_{i}\right\\}$, we
have that

$\displaystyle f(0)-\langle\zeta,\lambda^{*}\rangle$
$\displaystyle\overset{(i)}{=}\mathcal{L}(\pi^{*},\lambda^{*})-\langle\zeta,\lambda^{*}\rangle$
$\displaystyle\geq\mathcal{L}(\pi,\lambda^{*})-\langle\zeta,\lambda^{*}\rangle$
$\displaystyle=V_{0}^{\pi}(\rho)+\langle V^{\pi}(\rho)-c,\lambda^{*}\rangle$
$\displaystyle\geq V_{0}^{\pi}(\rho),$

where $(i)$ follows from the fact that
$f(0)=V_{0}^{*}(\rho)=\mathcal{L}(\pi^{*},\lambda^{*})$. The above inequality
implies that

$\displaystyle f(0)-\langle\zeta,\lambda^{*}\rangle\geq f(\zeta).$

Moreover, using above inequality, we have

$\displaystyle V_{0}^{\tilde{\pi}}(\rho)\leq
f(-(c-V^{\tilde{\pi}}(\rho))_{+})\leq
V_{0}^{\pi^{*}}+\langle(c-V^{\tilde{\pi}}(\rho))_{+},\lambda^{*}\rangle.$

Combing the above inequality and the bound given in the proposition, i.e.

$V_{0}^{*}(\rho)-V_{0}^{\tilde{\pi}}(\rho)+\langle\lambda,(c-V^{\tilde{\pi}}(\rho))_{+}\rangle\leq\sigma,$

we obtain

$\langle\lambda-\lambda^{*},(c-V^{\tilde{\pi}}(\rho))_{+}\rangle\leq\sigma.$

Using the condition that $\lambda\succeq\lambda^{*}+B\mathbf{1}$, we complete
the proof.

###  C.4 Proof of 1

We pick $\tau\leq{\epsilon}/{\log(|\mathcal{A}|)}$,
$\mu\leq{\epsilon}/{(6mB^{2})}$,

$\displaystyle\delta\leq\max\bigg{\\{}\epsilon^{2}/\big{(}8L_{\nu}R_{\max}(\tfrac{2R_{\max}}{1-\gamma}+\tfrac{2\sqrt{m}B}{\eta})^{2}\eta\sqrt{m}B\big{)},\tfrac{\epsilon}{L_{\nu}r_{0,\max}}\sqrt{\tfrac{\mu}{2L_{d}}}\bigg{\\}},$
(30)

and

$\displaystyle
T\geq\sqrt{\tfrac{2L_{d}}{\mu}}\max\bigg{\\{}2\log\bigg{(}2\sqrt{\eta
K_{0}(\lambda^{*}_{\tau,\mu})}\bigg{(}\tfrac{2R_{\max}}{1-\gamma}+\tfrac{2\sqrt{m}B}{\eta}\bigg{)}\tfrac{1}{\epsilon}\bigg{)},\log\bigg{(}\tfrac{2e\sqrt{m}BR_{\max}}{(1-\gamma)\epsilon}\bigg{)}\bigg{\\}}.$
(31)

By the design of RegPO (see Appendix A), we have that for all $t=1,\ldots T$,
$\|\delta_{t}\|_{2}\leq L_{\nu}R_{\max}\delta$ and $|\Delta_{t}|\leq
L_{\nu}r_{0,\max}\delta$, and thus, following from Theorem 1,
$V_{0}^{*}(\rho)-V^{\tilde{\pi}}_{0}(\rho)\leq 5\epsilon$ and
$\|({c}-{V}^{\tilde{\pi}}(\rho))_{+}\|_{1}\leq{6\epsilon}/{B}$.

To obtain the overall complexity, following our choices
$\tau=\mathcal{O}(\epsilon)$ and $\mu=\mathcal{O}(\epsilon)$, the Lipschitz
constant
$L_{d}=\tfrac{2R_{\max}^{2}L_{\nu}}{(1-\gamma)^{2}\tau}+\mu=\mathcal{O}({1}/{\epsilon})$
(see 1), and then $\delta=\mathcal{O}\left(\epsilon^{2}\right)$ due to eq. 30
and $T=\mathcal{O}({1}/{\epsilon}\log({1}/{\epsilon}))$ due to eq. 31. Hence,
RegPO $(\delta,\lambda,\tau)$ takes
$K=\mathcal{O}(\log(1/(\delta\tau)))=\mathcal{O}(\log({1}/{\epsilon}))$
iterations (see Appendix A). Therefore, the overall computational complexity
of Algorithm 2 is given by
$KT=\mathcal{O}({1}/{\epsilon}\log^{2}({1}/{\epsilon}))$.