# Learning Policies with Zero or Bounded Constraint Violation for Constrained
MDPs

Tao Liu
Texas A&M University
<EMAIL_ADDRESS>
&Ruida Zhou∗
Texas A&M University
<EMAIL_ADDRESS>
&Dileep Kalathil
Texas A&M University
<EMAIL_ADDRESS>
&P. R. Kumar
Texas A&M University
<EMAIL_ADDRESS>
&Chao Tian
Texas A&M University
<EMAIL_ADDRESS>
The first two authors contributed equally.

###### Abstract

We address the issue of safety in reinforcement learning. We pose the problem
in an episodic framework of a constrained Markov decision process. Existing
results have shown that it is possible to achieve a reward regret of
$\tilde{\mathcal{O}}(\sqrt{K})$ while allowing an
$\tilde{\mathcal{O}}(\sqrt{K})$ constraint violation in $K$ episodes. A
critical question that arises is whether it is possible to keep the constraint
violation even smaller. We show that when a strictly safe policy is known,
then one can confine the system to zero constraint violation with arbitrarily
high probability while keeping the reward regret of order
$\tilde{\mathcal{O}}(\sqrt{K})$. The algorithm which does so employs the
principle of optimistic pessimism in the face of uncertainty to achieve safe
exploration. When no strictly safe policy is known, though one is known to
exist, then it is possible to restrict the system to bounded constraint
violation with arbitrarily high probability. This is shown to be realized by a
primal-dual algorithm with an optimistic primal estimate and a pessimistic
dual update.

##  1 Introduction

Reinforcement learning (RL) addresses the problem of learning an optimal
control policy that maximizes the expected cumulative reward while interacting
with an unknown environment [29]. Standard RL algorithms typically focus only
on maximizing a single objective. However, in many real-world applications,
the control policy learned by an RL algorithm has to additionally satisfy
stringent safety constraints [10, 4]. For example, an autonomous vehicle may
need to reach its destination in the minimum possible time without violating
safety constraints such as crossing the middle of the road. The Constrained
Markov Decision Process (CMDP) [2, 14] formalism, where one seeks to maximize
a reward while satisfying safety constraints, is a standard approach for
modeling the necessary safety criteria of a control problem via constraints on
cumulative costs.

Several policy-gradient-based algorithms have been proposed to solve CMDPs.
Lagrangian-based methods [30, 28, 25, 20] formulate the CMDP problem as a
saddle-point problem and optimize it via primal-dual methods, while
Constrained Policy Optimization [1, 33] (inspired by the trust region policy
optimization [27]) computes new dual variables from scratch at each update to
maintain constraints during learning. Although these algorithms provide ways
to learn an optimal policy, performance guarantees about reward regret, safety
violation or sample complexity are rare.

One class of RL algorithms for which performance guarantees are available
follow the principle of Optimism in the Face of Uncertainty (OFU) [9, 11, 26],
and provide an $\tilde{\mathcal{O}}(\sqrt{K})$ guarantee for the reward
regret, where $K$ is the number of episodes. However, these algorithms also
have $\tilde{\mathcal{O}}(\sqrt{K})$ safety violations. Such significant
violation of the safety constraints during learning may be unacceptable in
many safety-critical real-world applications such as the control of autonomous
vehicles or power systems. These applications demand a class of safe RL
algorithms that can provably guarantee safety during learning. With this goal
in mind, we aim to answer the following open theoretical question in this
paper:

Can we design safe RL algorithms that can achieve an
$\tilde{\mathcal{O}}(\sqrt{K})$ regret with respect to the performance
objective, while guaranteeing zero or bounded safety constraint violation with
arbitrarily high probability?

Table 1: Regret and constraint violation comparisons for algorithms on episodic CMDPs Algorithm | Regret111This table is presented for $K\geq\text{poly}(|\mathcal{S}|,|\mathcal{A}|,H)$, with polynomial terms independent of $K$ omitted. | Constraint violation 1
---|---|---
OPDOP [9] | $\tilde{\mathcal{O}}(H^{3}\sqrt{|\mathcal{S}|^{2}|\mathcal{A}|K})$ | $\tilde{\mathcal{O}}(H^{3}\sqrt{|\mathcal{S}|^{2}|\mathcal{A}|K})$
OptCMDP [11] 222Efroni et al. [11] use $\mathcal{N}$, the maximum number of non-zero transition probabilities across the entire state-action space, in their regret and constraint violation analysis. For consistency, we use $|\mathcal{S}|^{2}|\mathcal{A}|$ to bound $\mathcal{N}$. | $\tilde{\mathcal{O}}(H^{2}\sqrt{|\mathcal{S}|^{3}|\mathcal{A}|K})$ | $\tilde{\mathcal{O}}(H^{2}\sqrt{|\mathcal{S}|^{3}|\mathcal{A}|K})$
OptCMDP-bonus [11] 2 | $\tilde{\mathcal{O}}(H^{2}\sqrt{|\mathcal{S}|^{3}|\mathcal{A}|K})$ | $\tilde{\mathcal{O}}(H^{2}\sqrt{|\mathcal{S}|^{3}|\mathcal{A}|K})$
OptDual-CMDP [11] 2 | $\tilde{\mathcal{O}}(H^{2}\sqrt{|\mathcal{S}|^{3}|\mathcal{A}|K})$ | $\tilde{\mathcal{O}}(H^{2}\sqrt{|\mathcal{S}|^{3}|\mathcal{A}|K})$
OptPrimalDual-CMDP [11] 2 | $\tilde{\mathcal{O}}(H^{2}\sqrt{|\mathcal{S}|^{3}|\mathcal{A}|K})$ | $\tilde{\mathcal{O}}(H^{2}\sqrt{|\mathcal{S}|^{3}|\mathcal{A}|K})$
C-UCRL [34] 333Zheng et al. [34] assumes a known transition kernel and analyzes regret in the long-term average setting. | $\tilde{\mathcal{O}}(T^{\frac{3}{4}})$ | $0$
OptPess-LP | $\tilde{\mathcal{O}}(\frac{H^{3}}{\tau-c^{0}}\sqrt{|\mathcal{S}|^{3}|\mathcal{A}|K})$ | $0$
OptPess-PrimalDual | $\tilde{\mathcal{O}}(\frac{H^{3}}{\tau-c^{0}}\sqrt{|\mathcal{S}|^{3}|\mathcal{A}|K})$ |  $\mathcal{O}(1)$ 444The detailed constraint violation is $\mathcal{O}\left(C^{\prime\prime}H+H^{2}\sqrt{|\mathcal{S}|^{3}|\mathcal{A}|C^{\prime\prime}\log(C^{\prime\prime}/\delta^{\prime})}\right)$, which is independent of $K$. Here, $\delta^{\prime}=\delta/(16|\mathcal{S}|^{2}|\mathcal{A}|H)$ and  $C^{\prime\prime}=\mathcal{O}(\frac{H^{4}|\mathcal{S}|^{3}|\mathcal{A}|}{(\tau-c^{0})^{2}}\log\frac{H^{4}|\mathcal{S}|^{3}|\mathcal{A}|}{(\tau-c^{0})^{2}\delta^{\prime}})$.

We answer the above question affirmatively by proposing two algorithms and
establishing their stringent safety performance during learning. Our focus is
on the tabular episodic constrained RL setting (unknown transition
probabilities, rewards, and costs). The key idea behind both algorithms is a
concept used earlier for safe exploration in constrained bandits [24, 21],
which we call “Optimistic Pessimism in the Face of Uncertainty (OPFU)” here.
The optimistic aspect incentivizes the algorithm for using exploration
policies that can visit new state-action pairs, while the pessimistic aspect
disincentivizes the algorithm from using exploration policies that can violate
safety constraints. By carefully balancing optimism and pessimism, the
proposed algorithms guarantee zero or bounded safety constraint violation
during learning while achieving an $\tilde{\mathcal{O}}(\sqrt{K})$ regret with
respect to the reward objective.

The two algorithms address two different classes of the safe learning problem:
whether a strictly safe policy is known a priori or not. The resulting
exploration strategies are very different in the two cases.

  1. 1.

OptPess-LP Algorithm: This algorithm assumes the prior knowledge of a strictly
safe policy. It ensures zero safety constraint violation during learning with
high probability and utilizes the linear programming (LP) approach for solving
a CMDP problem. The algorithm achieves a reward regret of
$\tilde{\mathcal{O}}(\frac{H^{3}}{\tau-c^{0}}\sqrt{|\mathcal{S}|^{3}|\mathcal{A}|K})$
with respect to the performance objective, where $H$ is the number of steps
per episode, $\tau$ is the given constraint on safety violation, $c^{0}$ is
the known safety constraint value of a strictly safe policy $\pi^{0}$, and
$|\mathcal{S}|$ and $|\mathcal{A}|$ are the number of states and actions
respectively.

  2. 2.

OptPess-PrimalDual Algorithm: This algorithm addresses the case where no
strictly safe policy, but a feasible strictly safe cost is known. By allowing
a bounded (in $K$) safety cost, it opens up space for exploration. The
OptPess-PrimalDual algorithm avoids linear programming and its attendant
complexity and exploits the primal-dual approach for solving a CMDP problem.
The proposed approach improves the computational tractability, while ensuring
a bounded safety constraint violation during learning and a reward regret of
$\tilde{\mathcal{O}}(\frac{H^{3}}{\tau-c^{0}}\sqrt{|\mathcal{S}|^{3}|\mathcal{A}|K})$
with respect to the objective.

Compared with the other methods listed in Table 1, though the proposed
algorithms have an additional $H/(\tau-c^{0})$ or
$\sqrt{|\mathcal{S}|}/(\tau-c^{0})$ factor in the regret bounds, they are able
to reduce the constraint violation to zero or constant with high probability.
This improvement in safety can be extremely important for many mission-
critical applications.

###  1.1 Related work

The problem of learning an optimal control policy that satisfies safety
constraints has been studied both in the RL setting and the multi-armed
bandits setting.

#### Constrained RL:

Several policy-gradient algorithms have seen success in practice [30, 28, 25,
20, 1, 33]. Also of interest are works which utilize Gaussian processes to
model the transition probabilities and value functions [5, 31, 19, 7].

Several algorithms with provable guarantees are closely related to our work.
Zheng et al. [34] considered the constrained RL problem in an infinite horizon
setting with unknown reward and cost functions. The approach is similar to the
UCRL2 algorithm [16] and achieves a sub-linear reward regret
$\tilde{\mathcal{O}}(T^{\frac{3}{4}})$ while satisfying constraints with high
probability during learning. In contrast to this work, we consider the setting
of unknown transition probabilities. Efroni et al [11] focused on the episodic
setting of unknown non-stationary transitions over a finite horizon, attaining
both a reward regret and a constraint violation of
$\tilde{\mathcal{O}}(H^{2}\sqrt{|\mathcal{S}|^{3}|\mathcal{A}|K})$. Ding et
al. [9] studied an episodic setting with linear function approximation
(suitable for large state space cases), and proposed algorithms that can
achieve $\tilde{\mathcal{O}}(dH^{3}\sqrt{K})$ for both the regret and the
constraint violation (where $d$ is the dimension of the feature mapping). The
regret analysis in [9] can be easily extended to the tabular case, yielding
$\tilde{\mathcal{O}}(H^{3}\sqrt{|\mathcal{S}|^{2}|\mathcal{A}|K})$.

#### Constrained Multi-Armed Bandits:

Multi-armed bandit problems are special cases of MDPs, with both the number of
states as well as the episode length being one. Linear bandits with
constraints (satisfied with high probability) have been investigated in
different settings. One setting, referred to as conservative bandits [32, 18,
13], requires the cumulative reward to remain above a fixed percentage of the
cumulative reward of a given baseline policy. Another setting is where each
arm is associated with two unknown distributions (similar to our setting),
generating reward and cost signals respectively [3, 24, 21, 22].

##  2 Problem formulation

A finite-horizon constrained non-stationary MDP model is defined as a tuple
$M=(\mathcal{S},\mathcal{A},H,P,r,c,\tau,\mu)$, where $\mathcal{S}$ is the
state space, $\mathcal{A}$ is the action space, $H$ is the number of steps in
each episode, $r:\mathcal{S}\times\mathcal{A}\rightarrow[0,1]$ is the unknown
reward function of interest, $c:\mathcal{S}\times\mathcal{A}\rightarrow[0,1]$
is the unknown safety cost function used to model the constraint violation,
$\tau\in(0,H]$ is the given constant used to define the safety constraint, and
$\mu$ is the known initial distribution of the state.
$P_{\cdot}(\cdot|s,a)\in\Delta_{\mathcal{S}}^{H},\forall
s\in\mathcal{S},\forall a\in\mathcal{A}$, where $\Delta_{\mathcal{S}}$ is the
$|\mathcal{S}|$-dimensional probability simplex, and $P_{h}(s^{\prime}|s,a)$
is the unknown transition probability that the next state is $s^{\prime}$ when
action $a$ is taken for state $s$ at step $h$.

Some further notation is necessary to define the problem. A (randomized
Markov) policy is defined by a map
$\pi:\mathcal{S}\times[H]\rightarrow\Delta_{\mathcal{A}}$, with $\pi_{h}(a|s)$
being the probability of taking action $a$ in state $s$ at time step $h$. With
$S_{t}$ and $A_{t}$ representing the state and the action at time $t$
respectively, let

$\displaystyle
V^{\pi}_{h}(s;g,P):=\mathbb{E}_{P,\pi}\left[\sum_{t=h}^{H}g(S_{t},A_{t})|S_{h}=s\right],\quad\forall
s\in\mathcal{S}$

denote the expected cumulative value with respect to a function
$g:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}_{+}$ under $P$ for a
policy $\pi$ over a time interval $[h,h+1,\ldots,H]$. With slightly abuse of
notation, we use $V^{\pi}_{1}(\mu;g,P)$ to denote
$\mathbb{E}_{S_{1}\sim\mu}[V^{\pi}_{1}(S_{1};g,P)]$.

In the formulation below there are a total of $K$ episodes with $H$ steps
each. Each episode $k\in[K]$ begins with an initial probability distribution
$\mu$ for $\mathcal{S}_{1}$. Then, the agent determines a randomized Markov
policy $\pi^{k}$ for that episode based on the information gathered from the
previous episodes, and executes it. At time step $h$ during the execution of
the $k$-th episode, after taking action $A_{h}^{k}$ at state $S_{h}^{k}$, the
agent receives a noisy reward and cost of
$R_{h}^{k}(S_{h}^{k},A_{h}^{k})=r_{h}(S_{h}^{k},A_{h}^{k})+\xi^{k}_{h}(S_{h}^{k},A_{h}^{k};r)$
and
$C_{h}^{k}(S_{h}^{k},A_{h}^{k})=c_{h}(S_{h}^{k},A_{h}^{k})+\xi^{k}_{h}(S_{h}^{k},A_{h}^{k};c)$,
respectively.

######  Assumption 2.1 (Sub-Gaussian noise).

For all $h\in[H],k\in[K]$, the reward and cost noise random variables are
conditionally independent zero-mean 1/2-sub-Gaussian, i.e.,
$\mathbb{E}[\xi_{h}^{k}|\mathcal{F}_{k-1}]=0$,
$\mathbb{E}[\exp(\lambda\xi^{k}_{h})|\mathcal{F}_{k-1}]\leq\exp(\lambda^{2}/4)$,
$\forall\lambda\in\mathbb{R}$. Here $\mathcal{F}_{k}$ is the $\sigma$-algebra
generated by the random variables up to episode $k$.

Let $\pi^{*}$ denote the optimal policy of the following CMDP model:

$\displaystyle\max_{\pi}$ $\displaystyle\quad
V_{1}^{\pi}(\mu;r,P)\quad\quad\text{s.t.}\quad V_{1}^{\pi}(\mu;c,P)\leq\tau.$
(1)

A policy $\pi$ is said to be _strictly safe_ if $V_{1}^{\pi}(\mu;c,P)<\tau$.

######  Assumption 2.2.

There exists a strictly safe policy $\pi^{0}$ with
$V^{\pi^{0}}_{1}(\mu;c,P)=c^{0}<\tau$.

There are two important cases of the safe learning problem.

Zero constraint violation case: The agent has prior knowledge of a strictly
safe policy $\pi^{0}$ and its safety cost value
$c^{0}:=V_{1}^{\pi^{0}}(\mu;c,P)$. The agent wishes to attain a sublinear (in
$K$) _cumulative regret_ ,

$\displaystyle
Reg(K;r):=\sum_{k=1}^{K}\left(V_{1}^{\pi^{*}}(\mu;r,P)-V^{\pi^{k}}_{1}(\mu;r,P)\right),$
(2)

while incurring zero constraint violation with at least a specified high
probability $(1-\delta)$, i.e.,

$\displaystyle\mathbb{P}\left(V^{\pi^{k}}_{1}(\mu;c,P)\leq\tau,\forall
k\in[K]\right)\geq 1-\delta.$

Bounded constraint violation case: The agent knows that there exists a
strictly safe policy with a known safety cost value $c^{0}$, but does not know
any strictly safe policy. It aims to achieve a cumulative regret (2) that
grows sublinearly with $K$, while ensuring that the _regret of constraint
violation_ ,

$\displaystyle
Reg(K;c):=\left(\sum_{k=1}^{K}\left(V^{\pi^{k}}_{1}(\mu;c,P)-\tau\right)\right)_{+}\mbox{
(where $(a)_{+}:=\max\\{a,0\\}$) },$

satisfies $\sup_{K}Reg(K;c)<+\infty$ with at least a specified high
probability $(1-\delta)$.

Remarks. For the zero constraint violation case, the assumption of knowing
$c^{0}$ can be relaxed, as shown in Appendix E.

##  3 Zero constraint violation case

We start by considering the zero constraint violation case. On one hand, to
balance the exploration-exploitation trade-off, we employ an optimistic
estimate of the reward function, as embodied in the OFU principle. On the
other hand, to maintain absolute safety with high probability during the
exploration, we employ a pessimistic estimate of the safety cost. Such an OPFU
principle was previously discussed in constrained bandits [3] and we adapt it
to the unknown CMDP setting.

At each episode $k$, we begin by forming empirical estimates of the transition
probabilities, the reward function, and the cost function from step $h$ of all
previous episodes:

$\displaystyle\hat{P}_{h}^{k}(s^{\prime}|s,a)$
$\displaystyle:=\frac{\sum_{k^{\prime}=1}^{k-1}\mathbbm{1}(S_{h}^{k^{\prime}}=s,A_{h}^{k^{\prime}}=a,S_{h+1}^{k^{\prime}}=s^{\prime})}{N^{k}_{h}(s,a)\vee
1},$ (3) $\displaystyle\hat{g}_{h}^{k}(s,a)$
$\displaystyle:=\frac{\sum_{k^{\prime}=1}^{k-1}\mathbbm{1}(S_{h}^{k^{\prime}}=s,A_{h}^{k^{\prime}}=a)(g_{h}(s,a)+\xi_{h}^{k}(s,a;g))}{N^{k}_{h}(s,a)\vee
1},\quad\mbox{ for }g=r,c,$ (4)

where $a\vee b:=\max\\{a,b\\}$, and

$\displaystyle N^{k}_{h}(s,a):=\mbox{\\# of visits to state-action pair
$(s,a)$ at step $h$ in episodes $[1,2,\ldots,k-1]$.}$ (5)

Next we fix some $\delta\in(0,1)$ and form a common (for notational
simplicity) confidence radius $\beta^{k}_{h}(s,a)$ for the transition
probabilities, the rewards, and the costs,

$\displaystyle\beta^{k}_{h}(s,a)$
$\displaystyle:=\sqrt{\frac{1}{N^{k}_{h}(s,a)\vee 1}Z},\quad\text{where
$Z:=\log(16|\mathcal{S}|^{2}|\mathcal{A}|HK/\delta)$.}$

At each episode $k$, we define the _optimistically biased reward estimate_ as

$\displaystyle\bar{r}^{k}_{h}(s,a)$
$\displaystyle:=\hat{r}^{k}_{h}(s,a)+\alpha_{r}\beta^{k}_{h}(s,a),\quad\forall(s,a,h)\in\mathcal{S}\times\mathcal{A}\times[H],$
(6)

where the scaling factor is

$\displaystyle\alpha_{r}:=1+|\mathcal{S}|H+\frac{4H(1+|\mathcal{S}|H)}{\tau-c^{0}}.$
(7)

To guarantee safe exploration, define the _pessimistically biased safety cost
estimate_ at episode $k$ as

$\displaystyle\underline{c}{}_{h}^{k}(s,a)$
$\displaystyle:=\hat{c}_{h}^{k}(s,a)+(1+H|\mathcal{S}|)\beta^{k}_{h}(s,a),\quad\forall(s,a,h)\in\mathcal{S}\times\mathcal{A}\times[H].$
(8)

The policy we execute at episode $k$ is chosen from a “pessimistically safe"
policy set $\Pi^{k}$, defined as

$\Pi^{k}:=\begin{cases}\\{\pi^{0}\\}&\text{if
}V_{1}^{\pi^{0}}(\mu;\underline{c}^{k},\hat{P}^{k})\geq(\tau+c^{0})/2,\\\
\\{\pi:V_{1}^{\pi}(\mu;\underline{c}^{k},\hat{P}^{k})\leq\tau\\}&\text{otherwise.}\end{cases}$
(9)

We simply use the strictly safe policy $\pi^{0}$ until
$V_{1}^{\pi^{0}}(\mu;\underline{c}^{k},\hat{P}^{k})<(\tau+c^{0})/2$, which is
a sufficient condition to guarantee that the set
$\\{\pi:V_{1}^{\pi}(\mu;\underline{c}^{k},\hat{P}^{k})\leq\tau\\}$ is non-
empty. Within this set, we choose the optimistically best reward earning
policy $\pi^{k}$, which can be solved by linear programming with
$\Theta(|\mathcal{S}||\mathcal{A}|H)$ decision variables and constraints [11].
The resulting Optimistic Pessimism-based Linear Programming (OptPess-LP)
algorithm is presented below:

Input: $K,\delta,\pi^{0},c^{0},\tau$;

Initialization: $N_{h}^{1}(s,a)=0,\
\forall(s,a,h)\in\mathcal{S}\times\mathcal{A}\times[H]$;

for  _$k=1,2,\ldots,K$_ do

Update empirical model (i.e., $\hat{P}^{k},\hat{r}^{k},\hat{c}^{k}$) as in
Equations (3)-(5);

Update $\bar{r}^{k},\underline{c}^{k}$, and $\Pi^{k}$ as in Equations (6)-(9);

Calculate
$\pi^{k}\in\arg\max_{\pi\in\Pi^{k}}V^{\pi}_{1}(\mu;\bar{r}^{k},\hat{P}^{k})$;

Execute $\pi^{k}$ and collect a trajectory
$(S_{h}^{k},A_{h}^{k},R_{h}^{k},C_{h}^{k}),\ \forall h\in[H]$;

Update counters $N_{h}^{k+1}(S_{h}^{k},A_{h}^{k}),\ \forall h\in[H]$;

end for

Algorithm 1 OptPess-LP

######  Theorem 3.1 (Regret and constraint violation bounds for OptPess-LP).

Fix any $\delta\in(0,1)$. With probability at least ($1-\delta$), OptPess-LP
has zero constraint violation with

$\displaystyle
Reg^{\textbf{OPLP}}(K;r)=\tilde{\mathcal{O}}\left(\frac{H^{3}}{\tau-c^{0}}\sqrt{|\mathcal{S}|^{3}|\mathcal{A}|K}+\frac{H^{5}|\mathcal{S}|^{3}|\mathcal{A}|}{(\tau-c^{0})^{2}\land(\tau-c^{0})}\right),\mbox{
where $a\land b:=\min\\{a,b\\}$.}$

Theorem 3.1 shows that it is possible to achieve sublinear regret in $K$,
while simultaneously incurring no constraint violation with arbitrarily high
probability. The proof is sketched in Section 5.1, with detailed proofs
presented in Appendix B.

##  4 Bounded constraint violation case

Without prior knowledge of a strictly safe policy $\pi^{0}$, we may not be
able to guarantee zero constraint violation with high probability. However, by
relaxing the requirement to bounded (in $K$) safety constraint violation, we
can incorporate more exploration and design a more efficient algorithm by a
primal-dual approach. It is inspired by the design of the pessimistic term in
constrained bandits [21].

Different from traditional optimistic dual analysis methods in [11], we
introduce an additive pessimistic term $\epsilon_{k}$ at each episode $k$ in
the original optimization problem (1), i.e.,

$\displaystyle\max_{\pi}$ $\displaystyle\quad
V_{1}^{\pi}(\mu;r,P)\quad\quad\text{s.t.}\quad
V_{1}^{\pi}(\mu;c,P)+\epsilon_{k}\leq\tau.$ (10)

The pessimistic term restrains the constraint violation and will be
progressively decreased as learning proceeds.

The CMDP problem in (10) may however not have any feasible solution. To
overcome this, we consider the Lagrangian,

$\displaystyle
L^{k}(\pi,\lambda):=V^{\pi}_{1}(\mu;r,P)+\lambda\left(\tau-\epsilon_{k}-V_{1}^{\pi}(\mu;c,P)\right),$

for which, given any Lagrange multiplier $\lambda$, we can always solve for
the optimizer $\max_{\pi}L^{k}(\pi,\lambda)$ by dynamic programming.

With the introduction of the additive term $\epsilon_{k}$, the dual variable
(denoted by $\lambda^{k}$) governed by the subgradient algorithm grows faster,
which enhances safety constraints in the next episode.

In order to guarantee sufficient optimism of rewards and costs, we integrate
the uncertainty of transitions into rewards and costs, i.e.,

$\displaystyle\tilde{r}_{h}^{k}(s,a)$
$\displaystyle:=\hat{r}_{h}^{k}(s,a)+\beta(n_{k}(s,a,h))+H|\mathcal{S}|\beta(n_{k}(s,a,h)),\quad\forall(s,a,h)\in\mathcal{S}\times\mathcal{A}\times[H],$
$\displaystyle\tilde{c}_{h}^{k}(s,a)$
$\displaystyle:=\hat{c}_{h}^{k}(s,a)-\beta(n_{k}(s,a,h))-H|\mathcal{S}|\beta(n_{k}(s,a,h)),\quad\forall(s,a,h)\in\mathcal{S}\times\mathcal{A}\times[H].$
(11)

Note that in contrast to the zero constraint violation case, we
_optimistically_ estimate the safety cost function, with the pessimism only
governed by $\epsilon_{k}$.

We employ truncated value functions due to the additional uncertainties from
transitions, i.e.,

$\displaystyle\hat{V}_{1}^{\pi}(\mu;\tilde{r}^{k},\hat{P}^{k}):=\min\\{H,V_{1}^{\pi}(\mu;\tilde{r}^{k},\hat{P}^{k})\\},~{}~{}\hat{V}_{1}^{\pi}(\mu;\tilde{c}^{k},\hat{P}^{k}):=\max\\{0,V_{1}^{\pi}(\mu;\tilde{c}^{k},\hat{P}^{k})\\}.$
(12)

For the policy update of the primal variable (denoted by $\pi^{k}$), we can
apply standard dynamic programming by viewing
$\tilde{r}_{h}^{k}(s,a)-\frac{\lambda^{k}}{\eta^{k}}(\tilde{c}_{h}^{k}(s,a)-\tau)$
as the reward function. Specifically, we apply backward induction to solve for
the optimal policy:

$\displaystyle
Q_{h}^{k}(s,a)=\tilde{r}_{h}^{k}(s,a)-\frac{\lambda^{k}}{\eta^{k}}(\tilde{c}_{h}^{k}(s,a)-\tau)+\sum_{s^{\prime}\in\mathcal{S}}\hat{P}_{h}^{k}(s^{\prime}|s,a)\max_{a^{\prime}}Q_{h+1}^{k}(s^{\prime},a^{\prime}),\quad\forall
h\in[H]$

with $Q_{H+1}^{k}(s,a)=0,\forall(s,a)\in\mathcal{S}\times\mathcal{A}$. Then,
$\pi_{h}^{k}\in\arg\max_{a}Q_{h}^{k}(s,a)$, which is computationally efficient
(as efficient as policy-gradient-based algorithms in the tabular case).

The resulting Optimistic Pessimism-based Primal-Dual (OptPess-PrimalDual)
algorithm is shown in Algorithm 2. It chooses
$\epsilon_{k}:=5H^{2}\sqrt{|\mathcal{S}|^{3}|\mathcal{A}|}(\log\frac{k}{\delta^{\prime}}+1)/\sqrt{k\log\frac{k}{\delta^{\prime}}}$,
$\delta^{\prime}=\delta/(16|\mathcal{S}|^{2}|\mathcal{A}|H)$, the scaling
parameter $\eta^{k}:=(\tau-c^{0})H\sqrt{k}$ in the primal policy update, and,
for convenience, a step size of 1 for the dual update.

Input: $K,\delta,c^{0},\tau$;

Initialization: $N_{h}^{1}(s,a)=0,\
\forall(s,a,h)\in\mathcal{S}\times\mathcal{A}\times[H]$, $\lambda^{1}=0$;

for  _$k=1,2,\ldots,K$_ do

Set
$\epsilon_{k}=5H^{2}\sqrt{|\mathcal{S}|^{3}|\mathcal{A}|}(\log\frac{k}{\delta^{\prime}}+1)/\sqrt{k\log\frac{k}{\delta^{\prime}}}$,
$\delta^{\prime}=\delta/(16|\mathcal{S}|^{2}|\mathcal{A}|H)$,
$\eta^{k}=(\tau-c^{0})H\sqrt{k}$;

Update empirical model (i.e., $\hat{P}^{k},\hat{r}^{k},\hat{c}^{k}$) as in
Equations (3)-(5);

Update $\tilde{r}^{k}$, $\tilde{c}^{k}$ as in Equation (4);

_(Policy Update)_
$\pi^{k}\in\arg\max_{\pi\in\Pi}\hat{V}_{1}^{\pi}(\mu;\tilde{r}^{k},\hat{P}^{k})-\frac{\lambda^{k}}{\eta^{k}}\left(\hat{V}_{1}^{\pi}(\mu;\tilde{c}^{k},\hat{P}^{k})-\tau\right)$;

_(Dual Update)_
$\lambda^{k+1}=\left(\lambda^{k}+\hat{V}_{1}^{\pi^{k}}(\mu;\tilde{c}^{k},\hat{P}^{k})+\epsilon_{k}-\tau\right)_{+}$;

Execute $\pi^{k}$ and collect a trajectory
$(S_{h}^{k},A_{h}^{k},R_{h}^{k},C_{h}^{k}),\ \forall h\in[H]$;

Update counters $N_{h}^{k+1}(S_{h}^{k},A_{h}^{k}),\ \forall h\in[H]$;

end for

Algorithm 2 OptPess-PrimalDual

######  Theorem 4.1 (Regret and constraint violation bounds for OptPess-
PrimalDual).

Fix any $\delta\in(0,1)$. Then,

$\displaystyle Reg^{\textbf{OPPD}}(K;r)$
$\displaystyle=\tilde{\mathcal{O}}\left(\frac{H^{3}}{\tau-c^{0}}\sqrt{|\mathcal{S}|^{3}|\mathcal{A}|K}+\frac{H^{5}|\mathcal{S}|^{3}|\mathcal{A}|}{(\tau-c^{0})^{2}}\right),$
$\displaystyle Reg^{\textbf{OPPD}}(K;c)$
$\displaystyle=\mathcal{O}\left(C^{\prime\prime}(H-\tau)+H^{2}\sqrt{|\mathcal{S}|^{3}|\mathcal{A}|C^{\prime\prime}}\right)=\mathcal{O}(1),$

where
$C^{\prime\prime}=\mathcal{O}(\frac{H^{4}|\mathcal{S}|^{3}|\mathcal{A}|}{(\tau-c^{0})^{2}}\log\frac{H^{4}|\mathcal{S}|^{3}|\mathcal{A}|}{(\tau-c^{0})^{2}\delta^{\prime}})$
is a coefficient independent of $K$.

Theorem 4.1 shows that it is possible to achieve an
$\tilde{\mathcal{O}}(\sqrt{K})$ reward regret, while only allowing bounded
constraint violation with arbitrarily high probability. Detailed proofs are
presented in Section 5.2 and Appendix C.

##  5 Regret and constraint violation analysis

We sketch the key steps in the proofs of Theorems 3.1 and 4.1. Full details
are relegated to Appendices B and C, respectively. Note that our analysis and
results are conditioned on the same high probability event (specifically
defined in Appendix A), which occurs with probability at least $(1-\delta)$.

###  5.1 Analysis of OptPess-LP (Algorithm 1)

#### Constraint violation analysis

The zero constraint violation of OptPess-LP follows from the following
property of the pessimistic policy set $\Pi^{k}$:

######  Lemma 5.1.

With probability at least $(1-\delta)$, for any $k\in[K]$ and policy
$\pi\in\Pi^{k}$, $V^{\pi}_{1}(\mu;c,P)\leq\tau$.

#### Regret of reward analysis

When the parameters $c,P$ are not well estimated, there may not exist any
policy $\pi$ such that
$V^{\pi}_{1}(\mu;\underline{c}^{k},\hat{P}^{k})\leq\tau$. Hence, as defined in
(9), $\Pi^{k}$ is a singleton set $\\{\pi^{0}\\}$, and accordingly $\pi^{0}$
is executed, even though $\pi^{0}$ is not safe for
$(\underline{c}^{k},\hat{P}^{k})$. It subsequently takes several episodes of
exploration using $\pi^{0}$ until it becomes strictly safe for
$(\underline{c}^{k},\hat{P}^{k})$. At that time, policies close enough to
$\pi^{0}$, of which there are infinitely many, are also safe for
$(\underline{c}^{k},\hat{P}^{k})$, and so $|\Pi^{k}|=+\infty$. At this point
the learning algorithm can proceed to enhance reward while maintaining safety
with respect to $(\underline{c}^{k},\hat{P}^{k})$.

To analyze the algorithm, we decompose the reward regret as follows:

$\displaystyle Reg^{\textbf{OPLP}}(K;r)=$
$\displaystyle\sum_{k=1}^{K}\mathbbm{1}(|\Pi^{k}|=1)\left(V^{\pi^{*}}_{1}(\mu;r,P)-V^{\pi^{0}}_{1}(\mu;r,P)\right)$
$\displaystyle+$
$\displaystyle\sum_{k=1}^{K}\mathbbm{1}(|\Pi^{k}|>1)\left(V^{\pi^{*}}_{1}(\mu;r,P)-V^{\pi^{k}}_{1}(\mu;\bar{r}^{k},\hat{P}^{k})\right)$
$\displaystyle+$
$\displaystyle\sum_{k=1}^{K}\mathbbm{1}(|\Pi^{k}|>1)\left(V^{\pi^{k}}_{1}(\mu;\bar{r}^{k},\hat{P}^{k})-V^{\pi^{k}}_{1}(\mu;r,P)\right).$
(13)

To bound the first term on the right-hand side (RHS) of (13), we have the
following lemma which gives an upper bound on the number of episodes for
exploration by policy $\pi^{0}$:

######  Lemma 5.2.

With probability at least $(1-\delta)$,
$\sum_{k=1}^{K}\mathbbm{1}(|\Pi^{k}|=1)\leq C^{\prime}$, where
$C^{\prime}=\tilde{\mathcal{O}}(H^{4}|\mathcal{S}|^{3}|\mathcal{A}|/((\tau-c^{0})^{2}\land(\tau-c^{0})))$.

Turning to the second term on the RHS of (13), we first note that $\pi^{*}$
may not be in $\Pi^{k}$. To ensure that the term
$V^{\pi^{*}}_{1}(\mu;r,P)-V^{\pi^{k}}_{1}(\mu;\bar{r}^{k},\hat{P}^{k})$ is
nevertheless non-positive even when $\pi^{*}\not\in\Pi^{k}$, we set
$\alpha_{r}$ to the large value shown in (7). This increases $\bar{r}^{k}$,
and hence also $V^{\pi^{k}}_{1}(\mu;\bar{r}^{k},\hat{P}^{k})$. In addition, we
show that there is a policy $\hat{\pi}^{k}$ that attains the same reward as
the (non-Markov) probabilistic mixed policy,
$\tilde{\pi}^{k}:=B_{\gamma_{k}}\pi^{*}+(1-B_{\gamma_{k}})\pi^{0}$, where
$B_{\gamma_{k}}$ is a Bernoulli distributed random variable with mean
$\gamma_{k}$ for $\gamma_{k}\in[0,1]$. $\gamma_{k}$ will be chosen as the
largest coefficient such that
$V_{1}^{\tilde{\pi}^{k}}(\mu;\underline{c}^{k},\hat{P}^{k})\leq\tau$. This
latter policy in turn has a larger reward than $\pi^{0}$ since it is a mixture
with $\pi^{*}$, yielding the following:

######  Lemma 5.3.

With probability at least $(1-\delta)$,

$\displaystyle\sum_{k=1}^{K}\mathbbm{1}(|\Pi^{k}|>1)\left(V^{\pi^{*}}_{1}(\mu;r,P)-V^{\pi^{k}}_{1}(\mu;\bar{r}^{k},\hat{P}^{k})\right)\leq
0.$

Finally, concerning the third term on the RHS of (13), akin to the closed-loop
identifiability property [6, 23], while $\hat{P}^{k}$ may not converge to $P$,
the difference in the rewards
$V^{\pi^{k}}_{1}(\mu;\bar{r}^{k},\hat{P}^{k})-V^{\pi^{k}}_{1}(\mu;r,P)$ grows
sublinearly in $k$ since the same policy $\pi^{k}$ is used in both values:

######  Lemma 5.4.

With probability at least $(1-\delta)$,

$\displaystyle\sum_{k=1}^{K}\mathbbm{1}(|\Pi^{k}|>1)\left(V^{\pi^{k}}_{1}(\mu;\bar{r}^{k},\hat{P}^{k})-V^{\pi^{k}}_{1}(\mu;r,P)\right)=\tilde{\mathcal{O}}\left(\frac{H^{3}}{\tau-c^{0}}\sqrt{|\mathcal{S}|^{3}|\mathcal{A}|K}+\frac{H^{5}|\mathcal{S}|^{3}|\mathcal{A}|}{\tau-c^{0}}\right).$

Combining Lemmas 5.2, 5.3, and 5.4 yields Theorem 3.1.

###  5.2 Analysis of OptPess-PrimalDual (Algorithm 2)

In this section, we outline the steps in the proof of Theorem 4.1 by analyzing
regret and constraint violation of OptPess-PrimalDual respectively.

Recall
$\epsilon_{k}=5H^{2}\sqrt{|\mathcal{S}|^{3}|\mathcal{A}|}(\log\frac{k}{\delta^{\prime}}+1)/\sqrt{k\log\frac{k}{\delta^{\prime}}}$,
where $\delta^{\prime}=\delta/(16|\mathcal{S}|^{2}|\mathcal{A}|H)$. The
existence of a feasible solution to (10) can be guaranteed if
$\epsilon_{k}\leq\tau-c^{0}$. Let $C^{\prime\prime}$ be the smallest value
such that $\forall k\geq C^{\prime\prime}$, $\epsilon_{k}\leq(\tau-c^{0})/2$.
Then the perturbed optimization problem (10) has at least one feasible
solution for any $k\geq C^{\prime\prime}$. By simple calculation, one can
verify that
$C^{\prime\prime}=\mathcal{O}(\frac{H^{4}|\mathcal{S}|^{3}|\mathcal{A}|}{(\tau-c^{0})^{2}}\log\frac{H^{4}|\mathcal{S}|^{3}|\mathcal{A}|}{(\tau-c^{0})^{2}\delta^{\prime}})$.
Notice that $\epsilon_{k}$ is a function not depending on $K$, and so is the
coefficient $C^{\prime\prime}$.

#### Constraint violation analysis

The bounded constraint violation of OptPess-PrimalDual is established as
follows. We first decompose the constraint violation as

$\displaystyle Reg^{\textbf{OPPD}}(K;c)$
$\displaystyle=\left(\sum_{k=1}^{K}\left(V_{1}^{\pi^{k}}(\mu;c,P)-\hat{V}_{1}^{\pi^{k}}(\mu;\tilde{c}^{k},\hat{P}^{k})\right)+\sum_{k=1}^{K}\left(\hat{V}_{1}^{\pi^{k}}(\mu;\tilde{c}^{k},\hat{P}^{k})-\tau\right)\right)_{+}$
$\displaystyle\leq\left(\sum_{k=1}^{K}\left(V_{1}^{\pi^{k}}(\mu;c,P)-\hat{V}_{1}^{\pi^{k}}(\mu;\tilde{c}^{k},\hat{P}^{k})\right)+\lambda^{K+1}-\sum_{k=1}^{K}\epsilon_{k}\right)_{+}.$
(14)

The first summation term and $\lambda^{K+1}$ in (14) can be bounded as
follows:

######  Lemma 5.5.

Recall $\delta^{\prime}=\delta/(16|\mathcal{S}|^{2}|\mathcal{A}|H)$, with
probability at least $(1-\delta)$,

$\displaystyle\sum_{k=1}^{K}\left(V_{1}^{\pi^{k}}(\mu;c,P)-\hat{V}_{1}^{\pi^{k}}(\mu;\tilde{c}^{k},\hat{P}^{k})\right)\leq
8H^{2}\sqrt{|\mathcal{S}|^{3}|\mathcal{A}|K\log\frac{K}{\delta^{\prime}}}+\mathcal{O}(PolyLog(K)).$

######  Lemma 5.6.

For any $k\geq C^{\prime\prime}$, with probability at least $(1-\delta)$,

$\displaystyle\lambda^{k}\leq\frac{1}{\zeta}\ln\frac{11\nu_{\max}^{2}}{3\rho^{2}}+C^{\prime\prime}(H-\tau)+\sum_{u=1}^{C^{\prime\prime}}\epsilon_{u}+H+\frac{4(H^{2}+\epsilon_{k}^{2}+\eta^{k}H)}{\tau-c^{0}},$

where $\rho=(\tau-c^{0})/4$, $\nu_{\max}=H$,
$\zeta=\rho/(\nu_{\max}^{2}+\nu_{\max}\rho/3)$.

To guarantee bounded violation, we ensure that $\sum_{k=1}^{K}\epsilon_{k}$ in
(14) can cancel the dominant terms in the two lemmas above. According to
Lemmas 5.5 and 5.6, with probability at least $(1-\delta)$, the violation is
bounded as

$\displaystyle
Reg^{\textbf{OPPD}}(K;c)=\mathcal{O}\left(C^{\prime\prime}H+H^{2}\sqrt{|\mathcal{S}|^{3}|\mathcal{A}|C^{\prime\prime}\log{(C^{\prime\prime}/\delta^{\prime})}}\right).$

#### Regret of reward analysis

For episode $k$ with $k\geq C^{\prime\prime}$, let $\pi^{\epsilon_{k},*}$ be
the optimal policy for (10), which is well-defined by the definition of
$C^{\prime\prime}$. We decompose the reward regret as

$\displaystyle Reg^{\textbf{OPPD}}$
$\displaystyle(K;r)=\sum_{k=1}^{C^{\prime\prime}}\left(V_{1}^{\pi^{*}}(\mu;r,P)-V_{1}^{\pi^{k}}(\mu;r,P)\right)$
(15) $\displaystyle+$
$\displaystyle\sum_{k=C^{\prime\prime}}^{K}\left(V_{1}^{\pi^{*}}(\mu;r,P)-V_{1}^{\pi^{\epsilon_{k},*}}(\mu;r,P)\right)+\sum_{k=C^{\prime\prime}}^{K}\left(V_{1}^{\pi^{\epsilon_{k},*}}(\mu;r,P)-\hat{V}_{1}^{\pi^{\epsilon_{k},*}}(\mu;\tilde{r}^{k},\hat{P}^{k})\right)$
$\displaystyle+$
$\displaystyle\sum_{k=C^{\prime\prime}}^{K}\left(\hat{V}_{1}^{\pi^{\epsilon_{k},*}}(\mu;\tilde{r}^{k},\hat{P}^{k})-\hat{V}_{1}^{\pi^{k}}(\mu;\tilde{r}^{k},\hat{P}^{k})\right)+\sum_{k=C^{\prime\prime}}^{K}\left(\hat{V}_{1}^{\pi^{k}}(\mu;\tilde{r}^{k},\hat{P}^{k})-V_{1}^{\pi^{k}}(\mu;r,P)\right).$

We upper bound each term on the RHS of (20). Since
$V_{1}^{\pi}(\mu;r,P)\in[0,H]$ for any policy $\pi$, the first term is upper
bounded by $HC^{\prime\prime}$. The second and third terms can be bounded by
the following two lemmas:

######  Lemma 5.7.

With probability at least $(1-\delta)$,

$\displaystyle\sum_{k=C^{\prime\prime}}^{K}\left(V_{1}^{\pi^{*}}(\mu;r,P)-V_{1}^{\pi^{\epsilon_{k},*}}(\mu;r,P)\right)\leq\sum_{k=C^{\prime\prime}}^{K}\frac{\epsilon_{k}H}{\tau-c^{0}}=\tilde{\mathcal{O}}\left(\frac{H^{3}}{\tau-c^{0}}\sqrt{|\mathcal{S}|^{3}|\mathcal{A}|K}\right).$

######  Lemma 5.8.

With probability at least $(1-\delta)$,
$\sum_{k=C^{\prime\prime}}^{K}\left(V_{1}^{\pi^{\epsilon_{k},*}}(\mu;r,P)-\hat{V}_{1}^{\pi^{\epsilon_{k},*}}(\mu;\tilde{r}^{k},\hat{P}^{k})\right)\leq
0$.

The pivotal step is to leverage optimism of $\pi^{k}$ to further decompose the
fourth term on the RHS of (20), and utilize the projected dual update to
transfer it into the form of $\lambda^{k}(\lambda^{k}-\lambda^{k+1})$. The
following lemmas provide high probability bounds for the remaining two terms
on the RHS of (20):

######  Lemma 5.9.

With probability at least $(1-\delta)$,

$\displaystyle\sum_{k=C^{\prime\prime}}^{K}\left(\hat{V}_{1}^{\pi^{\epsilon_{k},*}}(\mu;\tilde{r}^{k},\hat{P}^{k})-\hat{V}_{1}^{\pi^{k}}(\mu;\tilde{r}^{k},\hat{P}^{k})\right)=\tilde{\mathcal{O}}\left(\frac{H}{\tau-c^{0}}\sqrt{K}\right).$

######  Lemma 5.10.

With probability at least $(1-\delta)$,

$\displaystyle\sum_{k=C^{\prime\prime}}^{K}\left(\hat{V}_{1}^{\pi^{k}}(\mu;\tilde{r}^{k},\hat{P}^{k})-V_{1}^{\pi^{k}}(\mu;r,P)\right)=\tilde{\mathcal{O}}\left(H^{2}\sqrt{|\mathcal{S}|^{3}|\mathcal{A}|K}+H^{4}|\mathcal{S}|^{3}|\mathcal{A}|\right).$

Applying Lemmas 5.7, 5.8, 5.9, and 5.10 yields Theorem 4.1.

##  6 Concluding remarks

We present two optimistic pessimism-based algorithms that maintain stringent
safety constraints (either zero or bounded safety constraint violation) for
unknown CMDPs with high probability, while still attaining an
$\tilde{\mathcal{O}}(\sqrt{K})$ regret of reward. The algorithms employ,
respectively, a pessimistically safe policy set $\Pi^{k}$ or an additional
pessimistic term $\epsilon_{k}$ into the safety constraint. The first
algorithm, OptPess-LP, guarantees zero violation with high probability by
solving a linear programming with $\Theta(|\mathcal{S}||\mathcal{A}|H)$
decision variables, while the second algorithm, OptPess-PrimalDual, is as
efficient as policy-gradient-based algorithms in the tabular case, but
violates constraints during initial episodes. A possible future direction for
exploration is the application of the above OPFU principle in model-free
algorithms.

## Acknowledgement

P. R. Kumar’s work is partially supported by US National Science Foundation
under CMMI-2038625, HDR Tripods CCF-1934904; US Office of Naval Research under
N00014-21-1-2385; US ARO under W911NF1810331, W911NF2120064; and U.S.
Department of Energy’s Office of Energy Efficiency and Renewable Energy (EERE)
under the Solar Energy Technologies Office Award Number DE-EE0009031. The
views expressed herein and conclusions contained in this document are those of
the authors and should not be interpreted as representing the views or
official policies, either expressed or implied, of the U.S. NSF, ONR, ARO,
Department of Energy or the United States Government. The U.S. Government is
authorized to reproduce and distribute reprints for Government purposes
notwithstanding any copyright notation herein.

Dileep Kalathil gratefully acknowledges funding from the U.S. National Science
Foundation (NSF) grants NSF-CRII- CPS-1850206 and NSF-CAREER-EPCN-2045783.

## References

  * [1] J. Achiam, D. Held, A. Tamar, and P. Abbeel.  Constrained policy optimization.  In International Conference on Machine Learning, pages 22–31. PMLR, 2017.
  * [2] E. Altman.  Constrained Markov decision processes, volume 7.  CRC Press, 1999.
  * [3] S. Amani.  Linear stochastic bandits under safety constraints.  NeurIPS 2019, 2019.
  * [4] D. Amodei, C. Olah, J. Steinhardt, P. Christiano, J. Schulman, and D. Mané.  Concrete problems in ai safety.  arXiv preprint arXiv:1606.06565, 2016.
  * [5] F. Berkenkamp, M. Turchetta, A. P. Schoellig, and A. Krause.  Safe model-based reinforcement learning with stability guarantees.  In Proceedings of the 31st International Conference on Neural Information Processing Systems, pages 908–919, 2017.
  * [6] V. Borkar and P. Varaiya.  Adaptive control of Markov chains, I: Finite parameter set.  IEEE Transactions on Automatic Control, 24(6):953–957, 1979.
  * [7] R. Cheng, G. Orosz, R. M. Murray, and J. W. Burdick.  End-to-end safe reinforcement learning through barrier functions for safety-critical continuous control tasks.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 3387–3395, 2019.
  * [8] C. Dann, T. Lattimore, and E. Brunskill.  Unifying pac and regret: uniform pac bounds for episodic reinforcement learning.  In Proceedings of the 31st International Conference on Neural Information Processing Systems, pages 5717–5727, 2017.
  * [9] D. Ding, X. Wei, Z. Yang, Z. Wang, and M. Jovanovic.  Provably efficient safe exploration via primal-dual policy optimization.  In International Conference on Artificial Intelligence and Statistics, pages 3304–3312. PMLR, 2021.
  * [10] G. Dulac-Arnold, D. Mankowitz, and T. Hester.  Challenges of real-world reinforcement learning.  arXiv preprint arXiv:1904.12901, 2019.
  * [11] Y. Efroni, S. Mannor, and M. Pirotta.  Exploration-exploitation in constrained mdps.  arXiv preprint arXiv:2003.02189, 2020.
  * [12] Y. Efroni, N. Merlis, M. Ghavamzadeh, and S. Mannor.  Tight regret bounds for model-based reinforcement learning with greedy policies.  Advances in Neural Information Processing Systems, 32:12224–12234, 2019.
  * [13] E. Garcelon, M. Ghavamzadeh, A. Lazaric, and M. Pirotta.  Improved algorithms for conservative exploration in bandits.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 3962–3969, 2020.
  * [14] J. Garcıa and F. Fernández.  A comprehensive survey on safe reinforcement learning.  Journal of Machine Learning Research, 16(1):1437–1480, 2015.
  * [15] W. Hoeffding.  Probability inequalities for sums of bounded random variables.  In The Collected Works of Wassily Hoeffding, pages 409–426. Springer, 1994.
  * [16] T. Jaksch, R. Ortner, and P. Auer.  Near-optimal regret bounds for reinforcement learning.  Journal of Machine Learning Research, 11(4), 2010.
  * [17] C. Jin, T. Jin, H. Luo, S. Sra, and T. Yu.  Learning adversarial markov decision processes with bandit feedback and unknown transition.  In International Conference on Machine Learning, pages 4860–4869. PMLR, 2020.
  * [18] A. Kazerouni, M. Ghavamzadeh, Y. Abbasi-Yadkori, and B. Van Roy.  Conservative contextual linear bandits.  In Proceedings of the 31st International Conference on Neural Information Processing Systems, pages 3913–3922, 2017.
  * [19] T. Koller, F. Berkenkamp, M. Turchetta, and A. Krause.  Learning-based model predictive control for safe exploration.  In 2018 IEEE Conference on Decision and Control (CDC), pages 6059–6066. IEEE, 2018.
  * [20] Q. Liang, F. Que, and E. Modiano.  Accelerated primal-dual policy optimization for safe reinforcement learning.  arXiv preprint arXiv:1802.06480, 2018.
  * [21] X. Liu, B. Li, P. Shi, and L. Ying.  An efficient pessimistic-optimistic algorithm for constrained linear bandits.  arXiv preprint arXiv:2102.05295, 2021.
  * [22] A. Moradipari, S. Amani, M. Alizadeh, and C. Thrampoulidis.  Safe linear thompson sampling with side information.  arXiv preprint arXiv:1911.02156, 2019.
  * [23] P. R. Kumar and A. Becker.  A new family of optimal adaptive controllers for Markov chains.  IEEE Transactions on Automatic Control, 27(1):137–146, 1982.
  * [24] A. Pacchiano, M. Ghavamzadeh, P. Bartlett, and H. Jiang.  Stochastic bandits with linear constraints.  In International Conference on Artificial Intelligence and Statistics, pages 2827–2835. PMLR, 2021.
  * [25] S. Paternain, M. Calvo-Fullana, L. F. Chamon, and A. Ribeiro.  Safe policies for reinforcement learning via primal-dual methods.  arXiv preprint arXiv:1911.09101, 2019.
  * [26] S. Qiu, X. Wei, Z. Yang, J. Ye, and Z. Wang.  Upper confidence primal-dual reinforcement learning for cmdp with adversarial loss.  arXiv e-prints, pages arXiv–2003, 2020.
  * [27] J. Schulman, S. Levine, P. Abbeel, M. Jordan, and P. Moritz.  Trust region policy optimization.  In International conference on machine learning, pages 1889–1897. PMLR, 2015.
  * [28] A. Stooke, J. Achiam, and P. Abbeel.  Responsive safety in reinforcement learning by pid lagrangian methods.  In International Conference on Machine Learning, pages 9133–9143. PMLR, 2020.
  * [29] R. S. Sutton and A. G. Barto.  Reinforcement learning: An introduction.  MIT press, 2018.
  * [30] C. Tessler, D. J. Mankowitz, and S. Mannor.  Reward constrained policy optimization.  In International Conference on Learning Representations, 2018.
  * [31] A. Wachi, Y. Sui, Y. Yue, and M. Ono.  Safe exploration and optimization of constrained mdps using gaussian processes.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
  * [32] Y. Wu, R. Shariff, T. Lattimore, and C. Szepesvári.  Conservative bandits.  In International Conference on Machine Learning, pages 1254–1262. PMLR, 2016.
  * [33] T.-Y. Yang, J. Rosca, K. Narasimhan, and P. J. Ramadge.  Projection-based constrained policy optimization.  In International Conference on Learning Representations, 2019.
  * [34] L. Zheng and L. Ratliff.  Constrained upper confidence reinforcement learning.  In Learning for Dynamics and Control, pages 620–629. PMLR, 2020\.

Appendix

The theorems and lemmas presented in the paper are provided with full details
in this appendix.

First, let’s recall some notations. Fix some $0<\delta<1$ as the input of
algorithms. We say $g=\tilde{\mathcal{O}}(f)$ if there exists a universal
constant $C$ such that $g\leq C\left(f\log\frac{1}{\delta}+f\log f\right)$ for
any $f$ and $\delta$. The filtration $\\{\mathcal{F}_{k}\\}_{k\geq 0}$ is
defined as follows: $\mathcal{F}_{0}$ is the trivial sigma algebra, and for
each $k\in[K]$,
$\mathcal{F}_{k}=\sigma\left((S_{h}^{k^{\prime}},A_{h}^{k^{\prime}},R_{h}^{k^{\prime}},C_{h}^{k^{\prime}})_{h\in[H],k^{\prime}\in[k]}\right)$.
The policy process, i.e., the sequence of deployed policies
$\\{\pi^{k}\\}_{k\in[K]}$, is a predictable process with respect to the
filtration $\\{\mathcal{F}_{k}\\}_{k\geq 0}$. According to the definition of
$N^{k}_{h}$, we know $N^{k}_{h}(s,a)\in\mathcal{F}_{k-1}$.

Additionally, we define expectation operator
$\mathbb{E}_{\mu^{\prime},P^{\prime},\pi^{\prime}}[\cdot]$ as the expectation
with respect to a stochastic trajectory $(S_{h},A_{h})_{h\in[H]}$ generated
according to the Markov chain induced by
$(\mu^{\prime},P^{\prime},\pi^{\prime})$. When
$\mu^{\prime},P^{\prime},\pi^{\prime}$ are random elements,
$\mathbb{E}_{\mu^{\prime},P^{\prime},\pi^{\prime}}[\cdot]$ will be a
$\sigma(\mu^{\prime},P^{\prime},\pi^{\prime})$-measurable random variable.

##  Appendix A High probability good event $\mathcal{E}$

We aim to give performance guarantees of the algorithms with high probability.
To this end, we first consider a high probability “good event" $\mathcal{E}$
that all the subsequent analysis is conditioned on.

First, for any predictable event sequence $\mathcal{G}_{1:K}$, i.e.,
$\mathcal{G}_{k}\in\mathcal{F}_{k-1},~{}\forall k\in[K]$, define the event

$\displaystyle\mathcal{E}_{\mathcal{G}}(\delta):={\Bigg{\\{}}\forall
K^{\prime}\in[K],~{}\sum_{k=1}^{K^{\prime}}\sum_{h=1}^{H}\sum_{s,a}\frac{\mathbbm{1}(\mathcal{G}_{k})q^{\pi^{k}}(s,a,h)}{N^{k}_{h}(s,a)\lor
1}\leq 4H|\mathcal{S}||\mathcal{A}|+2H|\mathcal{S}||\mathcal{A}|\ln
K^{\prime}_{\mathcal{G}}+4\ln\frac{2HK}{\delta},$
$\displaystyle\sum_{k=1}^{K^{\prime}}\sum_{h=1}^{H}\sum_{s,a}\frac{\mathbbm{1}(\mathcal{G}_{k})q^{\pi^{k}}(s,a,h)}{\sqrt{N^{k}_{h}(s,a)\lor
1}}\leq
6H|\mathcal{S}||\mathcal{A}|+2H\sqrt{|\mathcal{S}||\mathcal{A}|K^{\prime}_{\mathcal{G}}}+2H|\mathcal{S}||\mathcal{A}|\ln
K^{\prime}_{\mathcal{G}}+5\ln\frac{2HK}{\delta}{\Bigg{\\}}},$

where
$K^{\prime}_{\mathcal{G}}:=\sum_{k=1}^{K^{\prime}}\mathbbm{1}(\mathcal{G}_{k})$
and $q^{\pi^{k}}$ is the occupancy measure of policy $\pi^{k}$, i.e.,
$q^{\pi^{k}}(s,a,h)=\mathbb{E}_{\mu,P,\pi^{k}}[\mathbbm{1}(S_{h}^{k}=s,A_{h}^{k}=a)|\mathcal{F}_{k-1}]$.

A trivial predictable event sequence is $\mathcal{G}_{1:k}$ with
$\mathcal{G}_{k}=\Omega,\forall k\in[K]$, where $\Omega$ is the sample space.
Let $\mathcal{E}_{\Omega}(\delta)$ be the event defined by this trivial event
sequence.

Consider another event sequence
$\mathcal{G}^{\prime}_{1:K}=\\{V^{\pi^{0}}_{1}(\mu;\underline{c}^{k},\hat{P}^{k})\geq\frac{\tau+c^{0}}{2}\\}_{k\in[K]}$,
which is predictable with respect to $\\{\mathcal{F}_{k}\\}_{k\geq 0}$. Let
$\mathcal{E}_{0}(\delta)$ be the event
$\mathcal{E}_{\mathcal{G}^{\prime}}(\delta)$ defined by this event sequence
$\mathcal{G}^{\prime}_{1:K}$. Notice that all notations (including
$\hat{r},\hat{c},\hat{P},$ and $\underline{c}^{k}$) are defined in the same
manner in the two algorithms, so this event sequence
$\mathcal{G}^{\prime}_{1:K}$ is also well-defined in Algorithm 2.

#### Good event $\mathcal{E}$.

Define a “good event" $\mathcal{E}$ as

$\displaystyle\mathcal{E}$ $\displaystyle:={\Big{\\{}}\forall k\in[K],\forall
h\in[H],\forall s\in\mathcal{S},\forall a\in\mathcal{A},$
$\displaystyle\quad\quad\left.~{}|r_{h}(s,a)-\hat{r}^{k}_{h}(s,a)|\leq\beta^{k}_{h}(s,a),~{}|c_{h}(s,a)-\hat{c}^{k}_{h}(s,a)|\leq\beta^{k}_{h}(s,a),\right.$
$\displaystyle\quad\quad\left.~{}|\hat{P}^{k}_{h}(s^{\prime}|s,a)-P_{h}(s^{\prime}|s,a)|\leq\beta^{k}_{h}(s,a),\forall
s^{\prime}\in\mathcal{S}\right.$
$\displaystyle\quad\quad\left.~{}|\hat{P}^{k}_{h}(s^{\prime}|s,a)-P_{h}(s^{\prime}|s,a)|\leq\tilde{\beta}^{k}_{h}(s^{\prime}|s,a),\forall
s^{\prime}\in\mathcal{S}\right\\}\cap\mathcal{E}_{\Omega}(\delta/4)\cap\mathcal{E}_{0}(\delta/4),$
(16)

where
$\tilde{\beta}^{k}_{h}(s^{\prime}|s,a):=\sqrt{\frac{2P(s^{\prime}|s,a)}{N^{k}_{h}(s,a)\lor
1}Z}+\frac{Z}{3N^{k}_{h}(s,a)\lor 1}$ and
$Z:=\log(16|\mathcal{S}|^{2}|\mathcal{A}|HK/\delta)$.

######  Lemma A.1.

Fix any $\delta\in(0,1)$ as the confidence parameter in the inputs of the
proposed algorithms. The good event $\mathcal{E}$ occurs with probability at
least $1-\delta$.

###### Proof of Lemma A.1.

For each $(s,a,h)\in\mathcal{S}\times\mathcal{A}\times[H]$, we take $K$
mutually independent samples of the reward, cost, and next state with the
probability distribution specified by the generative model $M$:

$\displaystyle\\{R^{n}(s,a,h),C^{n}(s,a,h),S^{n}(s,a,h)\\}_{n=1}^{K},$

Let $(\hat{r}^{n}(s,a,h),\hat{c}^{n}(s,a,h),\hat{P}^{n}(\cdot|s,a,h))$ be the
corresponding (running) empirical means, respectively, for the samples

$\displaystyle\\{R^{i}(s,a,h),C^{i}(s,a,h),S^{i}(s,a,h)\\}_{i=1}^{n}.$

Define the following failure events:

$\displaystyle F_{n}^{r}$ $\displaystyle:=\\{\exists
s,a,h:|\hat{r}^{n}(s,a,h)-r_{h}(s,a)|\geq\beta(n)\\},$ $\displaystyle
F_{n}^{c}$ $\displaystyle:=\\{\exists
s,a,h:|\hat{c}^{n}(s,a,h)-c_{h}(s,a)|\geq\beta(n)\\},$ $\displaystyle
F_{n}^{P}$ $\displaystyle:=\\{\exists
s,a,s^{\prime},h:|P_{h}(s^{\prime}|s,a)-\hat{P}^{n}(s^{\prime}|s,a,h)|\geq\beta(n)\\},$
$\displaystyle\tilde{F}_{n}^{P}$ $\displaystyle:=\\{\exists
s,a,s^{\prime},h:|P_{h}(s^{\prime}|s,a)-\hat{P}^{n}(s^{\prime}|s,a,h)|\geq\tilde{\beta}(n,P_{h}(s^{\prime}|s,a))\\},$

where $\beta(n):=\sqrt{\frac{1}{n\lor 1}Z}$ and
$\tilde{\beta}(n,p):=\sqrt{\frac{2P(s^{\prime}|s,a)}{n\lor
1}Z}+\frac{Z}{3n\lor 1}$.

Define the event $\mathcal{E}^{gen}$

$\mathcal{E}^{gen}:=\left((\bigcup_{n=1}^{K}F_{n}^{r}\cup F_{n}^{c}\cup
F_{n}^{P}\cup\tilde{F}_{n}^{P})^{C}\cap\mathcal{E}_{\Omega}(\delta/4)\cap\mathcal{E}_{0}(\delta/4)\right).$

By the definition of $\mathcal{E}_{\Omega}(\delta/4)$ and
$\mathcal{E}_{0}(\delta/4)$ and Lemma D.5, event
$\mathcal{E}_{\Omega}(\delta/4)\cap\mathcal{E}(\delta/4)$ occurs with
probability at least $1-\delta/2$. Therefore, to show that
$\mathbb{P}(\mathcal{E}^{gen})\geq 1-\delta$, it is sufficient to show that
$\mathbb{P}(\bigcup_{n=1}^{K}F_{n}^{r}\cup F_{n}^{c}\cup
F_{n}^{P}\cup\tilde{F}_{n}^{P})\leq\delta/2$. Note that
$\delta/16\leq\delta|\mathcal{S}|/4(1+|\mathcal{S}|)=:\delta^{\prime}$. Now,
it is straightforward to show the following:

(i) Using Hoeffding’s inequality,
$\mathbb{P}(\bigcup_{n=1}^{K}F_{n}^{r})\leq|\mathcal{S}||\mathcal{A}|HK\frac{\delta}{16|\mathcal{S}|^{2}|\mathcal{A}|HK}\leq\frac{\delta^{\prime}}{|\mathcal{S}|}$.

(ii) Using Hoeffding’s inequality,
$\mathbb{P}(\bigcup_{n=1}^{K}F_{n}^{c})\leq|\mathcal{S}||\mathcal{A}|HK\frac{\delta}{16|\mathcal{S}|^{2}|\mathcal{A}|HK}\leq\frac{\delta^{\prime}}{|\mathcal{S}|}$.

(iii) Using Hoeffding’s inequality,
$\mathbb{P}(\bigcup_{n=1}^{K}F_{n}^{P})\leq|\mathcal{S}|^{2}|\mathcal{A}|HK\frac{\delta}{16|\mathcal{S}|^{2}|\mathcal{A}|HK}\leq\delta^{\prime}$.

(iv) Using Bernstein’s inequality,
$\mathbb{P}(\bigcup_{n=1}^{K}\tilde{F}_{n}^{P})\leq|\mathcal{S}|^{2}|\mathcal{A}|HK\frac{\delta}{16|\mathcal{S}|^{2}|\mathcal{A}|HK}\leq\delta^{\prime}$.

Using union bound, $\mathbb{P}(\bigcup_{n=1}^{K}F_{n}^{r}\cup F_{n}^{c}\cup
F_{n}^{P}\cup\tilde{F}_{n}^{P})\leq\mathbb{P}(\bigcup_{n=1}^{K}F_{n}^{r})+\mathbb{P}(\bigcup_{n=1}^{K}F_{n}^{c})+\mathbb{P}(\bigcup_{n=1}^{K}F_{n}^{P})+\mathbb{P}(\bigcup_{n=1}^{K}\tilde{F}_{n}^{P})\leq(2+2/|\mathcal{S}|)\delta^{\prime}=\delta/2$.

The episodic CMDP problem studied here can be simulated as follows: at episode
$k$, taking action $a$ at state $s$ and step $h$ returns

$\displaystyle\left(R^{n_{k}(s,a,h)}(s,a,h),C^{n_{k}(s,a,h)}(s,a,h),S^{n_{k}(s,a,h)}(s,a,h)\right).$

Then all the samples drawn in the episodic CMDP problem are contained in

$\displaystyle\\{R^{n}(s,a,h),C^{n}(s,a,h),S^{n}(s,a,h)\\}_{n=1}^{K}.$

The sample averages calculated by the algorithm are

$\displaystyle\left(\hat{r}^{k}_{h}(s,a),\hat{c}^{k}_{h}(s,a),\hat{P}^{k}_{h}(\cdot|s,a)\right)=\left(\hat{r}^{n_{k}(s,a,h)}(s,a,h),\hat{c}^{n_{k}(s,a,h)}(s,a,h),\hat{P}^{n_{k}(s,a,h)}(\cdot|s,a,h)\right).$

Since $\mathcal{E}^{gen}$ implies $\mathcal{E}$, $\mathcal{E}$ holds with
probability at least $1-\delta$. ∎

Remark. _The analysis in the rest of this appendix is conditioned on the good
event $\mathcal{E}$. That is, if $(\Omega,{\cal{F}},P)$ is the underlying
probability space, then we suppose throughout the rest of the appendix that
the sample point $\omega\in\mathcal{E}$._

##  Appendix B Details of analysis for the zero constraint violation case

###  B.1 Constraint violation analysis

We will provide a proof of a slightly stronger result. Specifically, we will
suppose that we know a policy $\pi^{0}$ and a constant $c^{0}<\tau$ such that
the safety cost $V_{1}^{\pi^{0}}(\mu;c,P)\leq c^{0}$. The strengthening lies
in the relaxed requirement of knowing only an _upper bound_ on the safety cost
of $\pi^{0}$, rather than its _exact_ value.

The zero constraint violation of OptPess-LP is guaranteed by the pessimistic
policy set $\Pi^{k}$, as stated in the following lemma. Recall

$\Pi^{k}:=\begin{cases}\\{\pi^{0}\\}&\text{if
}V_{1}^{\pi^{0}}(\mu;\underline{c}^{k},\hat{P}^{k})\geq(\tau+c^{0})/2,\\\
\\{\pi:V_{1}^{\pi}(\mu;\underline{c}^{k},\hat{P}^{k})\leq\tau\\}&\text{otherwise.}\end{cases}$

######  Lemma B.1 (Restatement of Lemma 5.1).

On the good event $\mathcal{E}$, for any $k\in[K]$ and policy $\pi\in\Pi^{k}$,
$V^{\pi}_{1}(\mu;c,P)\leq\tau$.

###### Proof of Lemma 5.1.

Fix $\omega\in\mathcal{E}$ throughput. Then, for any $k,s,a,h$, we have

$\displaystyle(\underline{c}_{h}^{k}-c_{h})(s,a)$
$\displaystyle=\underline{c}_{h}^{k}(s,a)-\hat{c}_{h}^{k}(s,a)+\hat{c}^{k}_{h}(s,a)-c_{h}(s,a)$
$\displaystyle=(1+|\mathcal{S}|H)\beta^{k}_{h}(s,a)+\hat{c}^{k}_{h}(s,a)-c_{h}(s,a)$
$\displaystyle\geq(1+|\mathcal{S}|H)\beta^{k}_{h}(s,a)-\beta^{k}_{h}(s,a)=|\mathcal{S}|H\beta^{k}_{h}(s,a),$

and

$\displaystyle\sum_{s^{\prime}}(\hat{P}^{k}_{h}-P_{h})(s^{\prime}|s,a)V^{\pi}_{h+1}(s^{\prime};c,P)\geq-H\sum_{s^{\prime}}\beta^{k}_{h}(s,a)=-|\mathcal{S}|H\beta^{k}_{h}(s,a).$

Thus, by Lemma D.2, for any policy $\pi$, we have

$\displaystyle
V^{\pi}_{1}(\mu;\underline{c}^{k},\hat{P}^{k})-V^{\pi}_{1}(\mu;c,P)$
$\displaystyle=$
$\displaystyle\mathbb{E}_{\mu,\hat{P}^{k},\pi}\left[\sum_{h=1}^{H}\left((\underline{c}_{h}^{k}-c_{h})(S_{h},A_{h})+\sum_{s^{\prime}}(\hat{P}^{k}_{h}-P_{h})(s^{\prime}|S_{h},A_{h})V^{\pi}_{h+1}(s^{\prime};c,P)\right)~{}{\Big{|}}~{}\mathcal{F}_{k-1}\right]$
$\displaystyle\geq$
$\displaystyle\mathbb{E}_{\mu,\hat{P}^{k},\pi}\left[\sum_{h=1}^{H}|\mathcal{S}|H\beta^{k}_{h}(S_{h},A_{h})-|\mathcal{S}|H\beta^{k}_{h}(S_{h},A_{h})~{}{\Big{|}}~{}\mathcal{F}_{k-1}\right]\geq
0.$ (17)

Consider any $\pi\in\Pi^{k}$. If $\pi=\pi^{0}$, then
$V^{\pi^{0}}_{1}(\mu;c,P)=c^{0}<\tau$. Otherwise,

$\displaystyle V_{1}^{\pi}(\mu;c,P)\leq
V_{1}^{\pi}(\mu;\underline{c}^{k},\hat{P}^{k})\leq\tau.$

∎

###  B.2 Regret of reward analysis

When the parameters $c,P$ are not well estimated, there may not exist any
policy $\pi$ such that
$V^{\pi}_{1}(\mu;\underline{c}^{k},\hat{P}^{k})\leq\tau$. Hence, as defined in
(B.1), $\Pi^{k}$ is a singleton set $\\{\pi^{0}\\}$, and accordingly $\pi^{0}$
is executed, even though $\pi^{0}$ is not safe for
$(\underline{c}^{k},\hat{P}^{k})$. It subsequently takes several episodes of
exploration using $\pi^{0}$ until it becomes strictly safe for
$(\underline{c}^{k},\hat{P}^{k})$, which means that $\pi^{k}=\pi^{0}$ and
$V_{1}^{\pi^{k}}(\mu;\underline{c}^{k},\hat{P}^{k})\geq(\tau+c^{0})/2$ when
$|\Pi^{k}|=1$. At that time, policies close enough to $\pi^{0}$, of which
there are infinitely many, are also safe for
$(\underline{c}^{k},\hat{P}^{k})$, and so $|\Pi^{k}|=+\infty$. At this point
the learning algorithm can proceed to enhance reward while maintaining safety
with respect to $(\underline{c}^{k},\hat{P}^{k})$.

To analyze the algorithm, we decompose the reward regret as follows:

$\displaystyle Reg(K;r)=$
$\displaystyle\underbrace{\sum_{k=1}^{K}\mathbbm{1}(|\Pi^{k}|=1)\left(V^{\pi^{*}}_{1}(\mu;r,P)-V^{\pi^{0}}_{1}(\mu;r,P)\right)}_{\textnormal{(I)}}$
$\displaystyle+$
$\displaystyle\underbrace{\sum_{k=1}^{K}\mathbbm{1}(|\Pi^{k}|>1)\left(V^{\pi^{*}}_{1}(\mu;r,P)-V^{\pi^{k}}_{1}(\mu;\tilde{r}^{k},\hat{P}^{k})\right)}_{\textnormal{(II)}}$
$\displaystyle+$
$\displaystyle\underbrace{\sum_{k=1}^{K}\mathbbm{1}(|\Pi^{k}|>1)\left(V^{\pi^{k}}_{1}(\mu;\tilde{r}^{k},\hat{P}^{k})-V^{\pi^{k}}_{1}(\mu;r,P)\right)}_{\textnormal{(III)}}.$

We analyze these three terms, and the results are summarized in the following
lemmas, respectively.

The following lemma gives an upper bound on the number of episodes for
exploration by policy $\pi^{0}$. It thereby bounds the first term on the
right-hand side (RHS) of (13).

######  Lemma B.2 (Restatement of Lemma 5.2).

On the good event $\mathcal{E}$, $\sum_{k=1}^{K}\mathbbm{1}(|\Pi^{k}|=1)\leq
C^{\prime}$, where
$C^{\prime}=\tilde{\mathcal{O}}(H^{4}|\mathcal{S}|^{3}|\mathcal{A}|/((\tau-c^{0})^{2}\land(\tau-c^{0})))$.

###### Proof of Lemma 5.2.

With $K^{\prime}:=\sum_{k=1}^{K}\mathbbm{1}(|\Pi^{k}|=1)$, we then have

$\displaystyle\frac{(\tau-c^{0})K^{\prime}}{2}$
$\displaystyle=\sum_{k=1}^{K}\mathbbm{1}(|\Pi^{k}|=1)\frac{(\tau-c^{0})}{2}$
$\displaystyle=\sum_{k=1}^{K}\mathbbm{1}(|\Pi^{k}|=1)\left(\frac{\tau+c^{0}}{2}-c^{0}\right)$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\sum_{k=1}^{K}\mathbbm{1}(V^{\pi^{k}}_{1}(\mu;\underline{c}^{k},\hat{P}^{k})\geq\frac{\tau+c^{0}}{2})\left(V^{\pi^{k}}_{1}(\mu;\underline{c}^{k},\hat{P}^{k})-V^{\pi^{k}}_{1}(\mu;c,P)\right)$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}\tilde{\mathcal{O}}\left(H^{4}|\mathcal{S}|^{3}|\mathcal{A}|+H^{2}\sqrt{|\mathcal{S}|^{3}|\mathcal{A}|K^{\prime}}\right).$

(a) holds since $\pi^{k}=\pi^{0}$,
$V_{1}^{\pi^{k}}(\mu;\underline{c}^{k},\hat{P}^{k})\geq(\tau+c^{0})/2$, and
$V^{\pi^{k}}_{1}(\mu;c,P)\leq c^{0}$ when $|\Pi^{k}|=1$. The equality (b)
follows from Lemma D.4 with
$|\underline{c}_{h}^{k}-c_{h}|=|\hat{c}_{h}^{k}-c_{h}+(1+H|\mathcal{S}|)\beta_{h}^{k}|\leq(2+|\mathcal{S}|H)\beta_{h}^{k}$.
Applying Lemma D.6 for $K^{\prime}$, there exists some parameter $C^{\prime}$
that

$\displaystyle K^{\prime}\leq
C^{\prime}=\tilde{\mathcal{O}}\left(\frac{H^{4}|\mathcal{S}|^{3}|\mathcal{A}|}{(\tau-c^{0})\left(1\land(\tau-c^{0})\right)}\right).$

∎

The following lemma gives the resulting high probability bound for Term (II).

######  Lemma B.3 (Restatement of Lemma 5.3).

Recall $\alpha_{r}=1+|\mathcal{S}|H+4H(1+|\mathcal{S}|H)/(\tau-c^{0})$. On the
good event $\mathcal{E}$,

$\displaystyle\sum_{k=1}^{K}\mathbbm{1}(|\Pi^{k}|>1)\left(V^{\pi^{*}}_{1}(\mu;r,P)-V^{\pi^{k}}_{1}(\mu;\bar{r}^{k},\hat{P}^{k})\right)\leq
0.$

###### Proof of Lemma 5.3.

Consider any $k\in[K]$ with
$V^{\pi^{0}}_{1}(\mu;\underline{c}^{k},\hat{P}^{k})<(\tau+c^{0})/2$. Then
$|\Pi^{k}|>1$. When $\pi^{*}\in\Pi^{k}$, it is straightforward to verify that
Term (II) is less or equal to zero by optimism. When $\pi^{*}\not\in\Pi^{k}$,
define a probabilistic mixed policy

$\displaystyle\tilde{\pi}^{k}=B_{\gamma_{k}}\pi^{*}+(1-B_{\gamma_{k}})\pi^{0},$

where $B_{\gamma_{k}}$ is an independent Bernoulli distributed random variable
with mean $\gamma_{k}$. Let $\gamma_{k}\in[0,1]$ be the largest coefficient
such that

$\displaystyle
V^{\tilde{\pi}^{k}}_{1}(\mu;\underline{c}^{k},\hat{P}^{k})\leq\tau.$ (18)

If $V^{\pi^{*}}_{1}(\mu;\underline{c}^{k},\hat{P}^{k})<\tau$, then
$\gamma_{k}=1$. Otherwise, at $\gamma_{k}$, equality holds in (18). Then we
have

$\displaystyle\tau$
$\displaystyle=\gamma_{k}V^{\pi^{*}}_{1}(\mu;\underline{c}^{k},\hat{P}^{k})+(1-\gamma_{k})V^{\pi^{0}}_{1}(\mu;\underline{c}^{k},\hat{P}^{k})$
$\displaystyle\leq\gamma_{k}V^{\pi^{*}}_{1}(\mu;\underline{c}^{k},\hat{P}^{k})+(1-\gamma_{k})\frac{\tau+c^{0}}{2}$
$\displaystyle=\gamma_{k}(V_{1}^{\pi^{*}}(\mu;\underline{c}^{k},\hat{P}^{k})-V_{1}^{\pi^{*}}(\mu;c,P))+\gamma_{k}V_{1}^{\pi^{*}}(\mu;c,P)+(1-\gamma_{k})\frac{\tau+c^{0}}{2}$
$\displaystyle\leq\gamma_{k}\left(V_{1}^{\pi^{*}}(\mu;\underline{c}^{k},\hat{P}^{k})-V_{1}^{\pi^{*}}(\mu;c,P)\right)+\gamma_{k}\tau+\frac{\tau+c^{0}}{2}-\gamma_{k}\frac{\tau+c^{0}}{2}$
$\displaystyle=\gamma_{k}\left(V_{1}^{\pi^{*}}(\mu;\underline{c}^{k},\hat{P}^{k})-V_{1}^{\pi^{*}}(\mu;c,P)+\frac{\tau-c^{0}}{2}\right)+\frac{\tau+c^{0}}{2}.$

From (17),
$V_{1}^{\pi^{*}}(\mu;\underline{c}^{k},\hat{P}^{k})-V_{1}^{\pi^{*}}(\mu;c,P)+(\tau-c^{0})/2>0$,
from which it follows that

$\displaystyle\gamma_{k}\geq\frac{\tau-c^{0}}{\tau-c^{0}+2\left(V^{\pi^{*}}_{1}(\mu;\underline{c}^{k},\hat{P}^{k})-V^{\pi^{*}}_{1}(\mu;c,P)\right)}.$

By Lemma D.2, for any policy $\pi$,

$\displaystyle
V^{\pi}_{1}(\mu;\underline{c}^{k},\hat{P}^{k})-V^{\pi}_{1}(\mu;c,P)$
$\displaystyle=\mathbb{E}_{\mu,\hat{P}^{k},\pi}\left[\sum_{h=1}^{H}(\underline{c}^{k}_{h}-c_{h})(S_{h},A_{h})~{}{\Big{|}}~{}\mathcal{F}_{k-1}\right]$
$\displaystyle+\mathbb{E}_{\mu,\hat{P}^{k},\pi}\left[\sum_{h=1}^{H}\langle(\hat{P}^{k}_{h}-P_{h})(\cdot|S_{h},A_{h}),V^{\pi}_{h+1}(\cdot;c,P)\rangle~{}{\Big{|}}~{}\mathcal{F}_{k-1}\right]$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\mathbb{E}_{\mu,\hat{P}^{k},\pi}\left[\sum_{h=1}^{H}2(1+|\mathcal{S}|H)\beta_{h}^{k}(S_{h},A_{h}))~{}{\Big{|}}~{}\mathcal{F}_{k-1}\right]$
$\displaystyle=2(1+|\mathcal{S}|H)V^{\pi}_{1}(\mu;\beta^{k},\hat{P}^{k}),$

where (a) holds since for any $k,s,a,h$, we have

$\displaystyle(\underline{c}_{h}^{k}-c_{h})(s,a)$
$\displaystyle=\underline{c}_{h}^{k}(s,a)-\hat{c}_{h}^{k}(s,a)+\hat{c}_{h}^{k}(s,a)-c_{h}(s,a)$
$\displaystyle\leq(1+|\mathcal{S}|H)\beta_{h}^{k}(s,a)+\beta_{h}^{k}(s,a)$
$\displaystyle=(2+|\mathcal{S}|H)\beta_{h}^{k}(s,a),$

and

$\displaystyle\sum_{s^{\prime}}(\hat{P}^{k}_{h}-P_{h})(s^{\prime}|s,a)V^{\pi}_{h+1}(s^{\prime};c,P)\leq
H\sum_{s^{\prime}}\beta^{k}_{h}(s,a)=|\mathcal{S}|H\beta^{k}_{h}(s,a).$

Though policy $\tilde{\pi}^{k}$ is not a (randomized or non-randomized) Markov
policy, we can find a randomized Markov policy $\hat{\pi}^{k}$ such that the
occupation distributions of the state-action pair at any time of
$\hat{\pi}^{k}$ coincides with $\tilde{\pi}^{k}$ under the transition
probabilities $\hat{P}^{k}$. Therefore, as stated in by Lemma D.3,
$V^{\hat{\pi}^{k}}_{1}(\mu;g,\hat{P}^{k})=V^{\tilde{\pi}^{k}}_{1}(\mu;g,\hat{P}^{k})$
for any $g$.

Since $\hat{\pi}^{k}\in\Pi^{k}$, by the definition of $\pi^{k}$, we then have

$\displaystyle V^{\pi^{k}}_{1}(\mu;\bar{r}^{k},\hat{P}^{k})$
$\displaystyle\geq
V^{\hat{\pi}^{k}}_{1}(\mu;\bar{r}^{k},\hat{P}^{k})=V^{\tilde{\pi}^{k}}_{1}(\mu;\bar{r}^{k},\hat{P}^{k})$
$\displaystyle=\gamma_{k}V^{\pi^{*}}_{1}(\mu;\bar{r}^{k},\hat{P}^{k})+(1-\gamma_{k})V^{\pi^{0}}_{1}(\mu;\bar{r}^{k},\hat{P}^{k})$
$\displaystyle\geq\gamma_{k}V^{\pi^{*}}_{1}(\mu;\bar{r}^{k},\hat{P}^{k})$
$\displaystyle=\frac{\tau-c^{0}}{\tau-c^{0}+2\left(V^{\pi^{*}}_{1}(\mu;\underline{c}^{k},\hat{P}^{k})-V^{\pi^{*}}_{1}(\mu;c,P)\right)}V^{\pi^{*}}_{1}(\mu;\bar{r}^{k},\hat{P}^{k})$
$\displaystyle\geq\frac{\tau-c^{0}}{\tau-c^{0}+4(1+|\mathcal{S}|H)V^{\pi^{*}}_{1}(\mu;\beta^{k},\hat{P}^{k})}V^{\pi^{*}}_{1}(\mu;\bar{r}^{k},\hat{P}^{k}).$

To make $V^{\pi^{k}}_{1}(\mu;\bar{r}^{k},\hat{P}^{k})\geq
V^{\pi^{*}}_{1}(\mu;r,P)$, it suffices that

$\displaystyle\frac{\tau-c^{0}}{\tau-c^{0}+4(1+|\mathcal{S}|H)V^{\pi^{*}}_{1}(\mu;\beta^{k},\hat{P}^{k})}V^{\pi^{*}}_{1}(\mu;\bar{r}^{k},\hat{P}^{k})\geq
V^{\pi^{*}}_{1}(\mu;r,P),$

which follows since

$\displaystyle(\tau-c^{0})(V_{1}^{\pi^{*}}(\mu;\bar{r}^{k},\hat{P}^{k})-V_{1}^{\pi^{*}}(\mu;r,P))\geq
4(1+|\mathcal{S}|H)V_{1}^{\pi^{*}}(\mu;\beta^{k},\hat{P}^{k})V^{\pi^{*}}_{1}(\mu;r,P).$

Now notice that from Lemma D.2,

$\displaystyle
V_{1}^{\pi^{*}}(\mu;\bar{r}^{k},\hat{P}^{k})-V_{1}^{\pi^{*}}(\mu;r,P)$
$\displaystyle=$
$\displaystyle\mathbb{E}_{\mu,\hat{P}^{k},\pi^{*}}\left[\sum_{h=1}^{H}\left((\bar{r}^{k}_{h}-r_{h})(S_{h},A_{h})+\sum_{s^{\prime}}(\hat{P}^{k}_{h}-P_{h})(s^{\prime}|S_{h},A_{h})V^{\pi^{*}}_{h+1}(s^{\prime};r,P)\right)~{}{\Big{|}}~{}\mathcal{F}_{k-1}\right]$
$\displaystyle\geq$
$\displaystyle\mathbb{E}_{\mu,\hat{P}^{k},\pi^{*}}\left[\sum_{h=1}^{H}(\alpha_{r}-1-H|\mathcal{S}|)\beta_{h}^{k}(S_{h},A_{h})~{}{\Big{|}}~{}\mathcal{F}_{k-1}\right]$
$\displaystyle=$
$\displaystyle(\alpha_{r}-1-H|\mathcal{S}|)V^{\pi^{*}}_{1}(\mu;\beta^{k},\hat{P}^{k}).$

Thus, the choice of
$\alpha_{r}=4H(1+|\mathcal{S}|H)/(\tau-c^{0})+1+|\mathcal{S}|H$ suffices to
guarantee that $V^{\pi^{k}}_{1}(\mu;\bar{r}^{k},\hat{P}^{k})\geq
V^{\pi^{*}}_{1}(\mu;r,P)$ for any $k$ with $|\Pi^{k}|>1$. ∎

Finally, Term (III) is bounded as follows by employing the value of
$\alpha_{r}$.

######  Lemma B.4 (Restatement of Lemma 5.4).

On the good event $\mathcal{E}$,

$\displaystyle\sum_{k=1}^{K}\mathbbm{1}(|\Pi^{k}|>1)\left(V^{\pi^{k}}_{1}(\mu;\bar{r}^{k},\hat{P}^{k})-V^{\pi^{k}}_{1}(\mu;r,P)\right)=\tilde{\mathcal{O}}\left(\frac{H^{3}}{\tau-c^{0}}\sqrt{|\mathcal{S}|^{3}|\mathcal{A}|K}+\frac{H^{5}|\mathcal{S}|^{3}|\mathcal{A}|}{\tau-c^{0}}\right).$

###### Proof of Lemma 5.4.

Since
$|\bar{r}_{h}^{k}-r_{h}|=|\hat{r}_{h}^{k}-r_{h}+\alpha_{r}\beta_{h}^{k}|\leq(1+\alpha_{r})\beta_{h}^{k}$,
by Lemma D.4, we have

$\displaystyle\sum_{k=1}^{K}\mathbbm{1}(|\Pi^{k}|>1)\left(V^{\pi^{k}}_{1}(\mu;\bar{r}^{k},\hat{P}^{k})-V^{\pi^{k}}_{1}(\mu;r,P)\right)$
$\displaystyle\leq$
$\displaystyle\sum_{k=1}^{K}{\Big{|}}V^{\pi^{k}}_{1}(\mu;\bar{r}^{k},\hat{P}^{k})-V^{\pi^{k}}_{1}(\mu;r,P){\Big{|}}$
$\displaystyle=$
$\displaystyle\tilde{\mathcal{O}}\left((\alpha_{r}+H\sqrt{|\mathcal{S}|})H\sqrt{|\mathcal{S}||\mathcal{A}|K}+H^{3}|\mathcal{S}|^{2}|\mathcal{A}|(\alpha_{r}+|\mathcal{S}|)\right)$
$\displaystyle=$
$\displaystyle\tilde{\mathcal{O}}\left(\frac{H^{3}}{\tau-c^{0}}\sqrt{|\mathcal{S}|^{3}|\mathcal{A}|K}+\frac{H^{5}|\mathcal{S}|^{3}|\mathcal{A}|}{\tau-c^{0}}\right).$

∎

###  B.3 Proof of Theorem 3.1

######  Theorem B.5 (Regret and constraint violation bounds for OptPess-LP
(Restatement of Theorem 3.1)).

On the good event $\mathcal{E}$, OptPess-LP has zero constraint violation with

$\displaystyle
Reg^{\textbf{OPLP}}(K;r)=\tilde{\mathcal{O}}\left(\frac{H^{3}}{\tau-c^{0}}\sqrt{|\mathcal{S}|^{3}|\mathcal{A}|K}+\frac{H^{5}|\mathcal{S}|^{3}|\mathcal{A}|}{(\tau-c^{0})^{2}\land(\tau-c^{0})}\right),\mbox{
where $a\land b:=\min\\{a,b\\}$.}$

###### Proof of Theorem 3.1.

The zero constraint violation of OptPess-LP is guaranteed by Lemma 5.1.
Combining Lemmas 5.2, 5.3, and 5.4, which give upper bounds to Terms (I)-(III)
respectively, we have

$\displaystyle\sum_{k=1}^{K}\left(V^{\pi^{*}}_{1}(\mu;r,P)-V^{\pi^{k}}_{1}(\mu;r,P)\right)=\tilde{\mathcal{O}}\left(\frac{H^{3}}{\tau-c^{0}}\sqrt{|\mathcal{S}|^{3}|\mathcal{A}|K}+\frac{H^{5}|\mathcal{S}|^{3}|\mathcal{A}|}{(\tau-c^{0})\land(\tau-c^{0})^{2}}\right).$

∎

##  Appendix C Details of analysis for bounded constraint violation case

Recall
$\epsilon_{k}=5H^{2}\sqrt{|\mathcal{S}|^{3}|\mathcal{A}|}(\log\frac{k}{\delta^{\prime}}+1)/\sqrt{k\log\frac{k}{\delta^{\prime}}}$,
where $\delta^{\prime}=\delta/(16|\mathcal{S}|^{2}|\mathcal{A}|H)$. The
existence of a feasible solution to (10) can be guaranteed if
$\epsilon_{k}\leq\tau-c^{0}$. Let $C^{\prime\prime}$ be the smallest value
such that $\forall k\geq C^{\prime\prime}$, $\epsilon_{k}\leq(\tau-c^{0})/2$.
Then the perturbed optimization problem (10) has at least one feasible
solution for any $k\geq C^{\prime\prime}$. By simple calculation, one can
verify that
$C^{\prime\prime}=\mathcal{O}(\frac{H^{4}|\mathcal{S}|^{3}|\mathcal{A}|}{(\tau-c^{0})^{2}}\log\frac{H^{4}|\mathcal{S}|^{3}|\mathcal{A}|}{(\tau-c^{0})^{2}\delta^{\prime}})$.
Notice that since $\epsilon_{k}$ is a function not depending on $K$, so is the
coefficient $C^{\prime\prime}$.

######  Lemma C.1 (Optimistic of cost value).

On the good event $\mathcal{E}$, for any $C^{\prime\prime}\leq k\leq K$ and
any policy $\pi$,

$\displaystyle\hat{V}^{\pi}_{1}(\mu;\tilde{c}^{k},\hat{P}^{k})\leq
V^{\pi}_{1}(\mu;c,P).$

###### Proof of Lemma C.1.

If
$\hat{V}_{1}^{\pi}(\mu;\tilde{c}^{k},\hat{P}^{k})=V_{1}^{\pi}(\mu;\tilde{c}^{k},\hat{P}^{k})$,
then

$\displaystyle\sum_{k=C^{\prime\prime}}^{K}\left(\hat{V}^{\pi}_{1}(\mu;\tilde{c}^{k},\hat{P}^{k})-V^{\pi}_{1}(\mu;c,P)\right)$
$\displaystyle=$
$\displaystyle\sum_{k=C^{\prime\prime}}^{K}\mathbb{E}_{\mu,\hat{P}^{k},\pi}\left[\sum_{h=1}^{H}\left(\tilde{c}_{h}^{k}(S_{h},A_{h})-c_{h}(S_{h},A_{h})\right)+\langle(\hat{P}_{h}^{k}-P_{h})(\cdot|S_{h},A_{h}),V^{\pi}_{h+1}(\cdot;c,P)\rangle~{}{\Big{|}}~{}\mathcal{F}_{k-1}\right]$
$\displaystyle\leq$
$\displaystyle\sum_{k=C^{\prime\prime}}^{K}\mathbb{E}_{\mu,\hat{P}^{k},\pi}\left[\sum_{h=1}^{H}(\hat{c}_{h}^{k}(S_{h},A_{h})-c_{h}(S_{h},A_{h}))-\beta_{h}^{k}-H|\mathcal{S}|\beta_{h}^{k}+H|\mathcal{S}|\beta_{h}^{k}~{}{\Big{|}}~{}\mathcal{F}_{k-1}\right]\leq
0.$

Otherwise, $\hat{V}_{1}^{\pi}(\mu;\tilde{c}^{k},\hat{P}^{k})=0\leq
V^{\pi}_{1}(\mu;c,P)$. ∎

###  C.1 Constraint violation analysis

######  Lemma C.2 (Restatement of Lemma 5.5).

Recall $\delta^{\prime}=\delta/(16|\mathcal{S}|^{2}|\mathcal{A}|H)$. On the
good event $\mathcal{E}$,

$\displaystyle\sum_{k=1}^{K}\left(V_{1}^{\pi^{k}}(\mu;c,P)-\hat{V}_{1}^{\pi^{k}}(\mu;\tilde{c}^{k},\hat{P}^{k})\right)\leq
8H^{2}\sqrt{|\mathcal{S}|^{3}|\mathcal{A}|K\log\frac{K}{\delta^{\prime}}}+\tilde{\mathcal{O}}\left(H^{4}|\mathcal{S}|^{3}|\mathcal{A}|\right),$

where $\tilde{\mathcal{O}}(H^{4}|\mathcal{S}|^{3}|\mathcal{A}|)$ contains
factors poly-logarithmic in $K$.

###### Proof of Lemma 5.5.

For any $k,s,a,h$, we have

$\displaystyle|(\tilde{c}_{h}^{k}-c_{h})(s,a)|$
$\displaystyle=|\tilde{c}_{h}^{k}(s,a)-\hat{c}_{h}^{k}(s,a)+\hat{c}^{k}_{h}(s,a)-c_{h}(s,a)|$
$\displaystyle\leq(1+|\mathcal{S}|H)\beta^{k}_{h}(s,a)+|\hat{c}^{k}_{h}(s,a)-c_{h}(s,a)|$
$\displaystyle\leq(1+|\mathcal{S}|H)\beta^{k}_{h}(s,a)+\beta^{k}_{h}(s,a)=(2+|\mathcal{S}|H)\beta^{k}_{h}(s,a).$

By Lemma D.4, we have

$\displaystyle\sum_{k=1}^{K}\left(V_{1}^{\pi^{k}}(\mu;c,P)-\hat{V}_{1}^{\pi^{k}}(\mu;\tilde{c}^{k},\hat{P}^{k})\right)$
$\displaystyle\leq$
$\displaystyle(3(2+|\mathcal{S}|H)+3\sqrt{2}H\sqrt{|\mathcal{S}|})H\sqrt{|\mathcal{S}||\mathcal{A}|KZ}+\tilde{\mathcal{O}}\left(H^{4}|\mathcal{S}|^{3}|\mathcal{A}|\right)$
$\displaystyle=$
$\displaystyle(6+3|\mathcal{S}|H+3H\sqrt{2|\mathcal{S}|})H\sqrt{|\mathcal{S}||\mathcal{A}|KZ}+\tilde{\mathcal{O}}\left(H^{4}|\mathcal{S}|^{3}|\mathcal{A}|\right)$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}$ $\displaystyle
8H^{2}|\mathcal{S}|\sqrt{|\mathcal{S}||\mathcal{A}|KZ}+\tilde{\mathcal{O}}\left(H^{4}|\mathcal{S}|^{3}|\mathcal{A}|\right),$

where $\tilde{\mathcal{O}}(H^{4}|\mathcal{S}|^{3}|\mathcal{A}|)$ contains
factors poly-logarithmic in $K$. (a) holds since we assume that
$|\mathcal{S}|\geq 2$ and $H\geq 2$. ∎

######  Lemma C.3 (Restatement of Lemma 5.6).

On the good event $\mathcal{E}$, for any $k\geq C^{\prime\prime}$,

$\displaystyle\lambda^{k}\leq\frac{1}{\zeta}\ln\frac{11\nu_{\max}^{2}}{3\rho^{2}}+C^{\prime\prime}(H-\tau)+\sum_{u=1}^{C^{\prime\prime}}\epsilon_{u}+H+\frac{4(H^{2}+\epsilon_{k}^{2}+\eta^{k}H)}{\tau-c^{0}},$

where $\rho:=(\tau-c^{0})/4$, $\nu_{\max}:=H$,
$\zeta:=\rho/(\nu_{\max}^{2}+\nu_{\max}\rho/3)$.

###### Proof of Lemma 5.6.

We will first verify conditions (i) and (ii) of Lemma D.7 for $k\geq
C^{\prime\prime}$ by defining $\Phi(k)=\lambda^{k}$. Suppose
$\Phi(k)=\lambda^{k}\geq\varphi_{k}:=4(H^{2}+\epsilon_{k}^{2}+\eta^{k}H)/(\tau-c^{0})$.
It is straightforward to verify that
$\lambda^{k}+\hat{V}_{1}^{\pi^{k}}(\mu;\tilde{c}^{k},\hat{P}^{k})+\epsilon_{k}-\tau$
is positive, which implies

$\displaystyle\lambda^{k+1}=\lambda^{k}+\hat{V}_{1}^{\pi^{k}}(\mu;\tilde{c}^{k},\hat{P}^{k})+\epsilon_{k}-\tau.$

Let $L(k)=(\lambda^{k})^{2}/2$, we have

$\displaystyle L(k+1)-L(k)$
$\displaystyle=\frac{1}{2}(\lambda^{k+1})^{2}-\frac{1}{2}(\lambda^{k})^{2}$
$\displaystyle=\lambda^{k}(\lambda^{k+1}-\lambda^{k})+\frac{1}{2}(\lambda^{k+1}-\lambda^{k})^{2}$
$\displaystyle=\lambda^{k}\left(\hat{V}_{1}^{\pi^{k}}(\mu;\tilde{c}^{k},\hat{P}^{k})+\epsilon_{k}-\tau\right)+\frac{1}{2}(\hat{V}_{1}^{\pi^{k}}(\mu;\tilde{c}^{k},\hat{P}^{k})+\epsilon_{k}-\tau)^{2}$
$\displaystyle=\left(\lambda^{k}\left(\hat{V}_{1}^{\pi^{k}}(\mu;\tilde{c}^{k},\hat{P}^{k})+\epsilon_{k}-\tau\right)-\eta^{k}\hat{V}_{1}^{\pi^{k}}(\mu;\tilde{r}^{k},\hat{P}^{k})\right)$
$\displaystyle+\eta^{k}\hat{V}_{1}^{\pi^{k}}(\mu;\tilde{r}^{k},\hat{P}^{k})+\frac{1}{2}(\hat{V}_{1}^{\pi^{k}}(\mu;\tilde{c}^{k},\hat{P}^{k})+\epsilon_{k}-\tau)^{2}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\left(\lambda^{k}\left(\hat{V}_{1}^{\pi^{0}}(\mu;\tilde{c}^{k},\hat{P}^{k})+\epsilon_{k}-\tau\right)-\eta^{k}\hat{V}_{1}^{\pi^{0}}(\mu;\tilde{r},\hat{P}^{k})\right)$
$\displaystyle+\eta^{k}\hat{V}_{1}^{\pi^{k}}(\mu;\tilde{r}^{k},\hat{P}^{k})+(\hat{V}_{1}^{\pi^{k}}(\mu;\tilde{c}^{k},\hat{P}^{k})-\tau)^{2}+\epsilon_{k}^{2}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\lambda^{k}\left(V_{1}^{\pi^{0}}(\mu;c,P)+\epsilon_{k}-\tau\right)+\eta^{k}H+H^{2}+\epsilon_{k}^{2}$
$\displaystyle\leq-\frac{\tau-c^{0}}{2}\lambda^{k}+H^{2}+\epsilon_{k}^{2}+\eta^{k}H.$

(a) is by the optimality of $\pi^{k}$ and $(a+b)^{2}/2\leq(a^{2}+b^{2})$. (b)
holds since $\hat{V}_{1}^{\pi^{0}}(\mu;\tilde{c}^{k},\hat{P}^{k})\leq
V_{1}^{\pi^{0}}(\mu;c,P)$ according to Lemma C.1.

It then follows that $L(k+1)<L(k)$ and

$\displaystyle\lambda^{k+1}-\lambda^{k}$
$\displaystyle=\frac{(\lambda^{k+1})^{2}-(\lambda^{k})^{2}}{\lambda^{k+1}+\lambda^{k}}$
$\displaystyle\leq\frac{(\lambda^{k+1})^{2}-(\lambda^{k})^{2}}{2\lambda^{k}}$
$\displaystyle\leq-\frac{\tau-c^{0}}{2}+\frac{H^{2}+\epsilon_{k}^{2}+\eta^{k}H}{\varphi_{k}}=-\frac{\tau-c^{0}}{4}=:-\rho.$

In addition, since $\forall k\geq C^{\prime\prime}$,
$\epsilon_{k}\leq(\tau-c^{0})/2$,

$\displaystyle|\lambda^{k+1}-\lambda^{k}|\leq|\hat{V}_{1}^{\pi^{k}}(\mu;\tilde{c}^{k},\hat{P}^{k})+\epsilon_{k}-\tau|\leq
H=:\nu_{\max}.$

With the definitions of $\varphi_{k},\rho,\nu_{\max}$, we apply Lemma D.7
starting from $C^{\prime\prime}$, which gives

$\displaystyle\lambda^{k}$
$\displaystyle\leq\frac{1}{\zeta}\ln\left(e^{\zeta\lambda^{C^{\prime\prime}}}+\frac{2e^{\zeta(v_{\max}+\varphi_{k})}}{\zeta\rho}\right)$
$\displaystyle\leq\frac{1}{\zeta}\ln\left(\frac{11v_{\max}^{2}e^{\zeta(\lambda^{C^{\prime\prime}}+v_{\max}+\varphi_{k})}}{3\rho^{2}}\right)$
$\displaystyle=\frac{1}{\zeta}\ln\frac{11\nu_{\max}^{2}}{3\rho^{2}}+\lambda^{C^{\prime\prime}}+v_{\max}+\varphi_{k}$
$\displaystyle\leq\frac{1}{\zeta}\ln\frac{11\nu_{\max}^{2}}{3\rho^{2}}+C^{\prime\prime}(H-\tau)+\sum_{u=1}^{C^{\prime\prime}}\epsilon_{u}+H+\frac{4(H^{2}+\epsilon_{k}^{2}+\eta^{k}H)}{\tau-c^{0}},$

where $\zeta=\rho/(\nu_{\max}^{2}+\nu_{\max}\rho/3)\geq
3(\tau-c^{0})/(13H^{2})$, and the last inequality is by

$\displaystyle\lambda^{C^{\prime\prime}}$
$\displaystyle\leq\lambda^{1}+\sum_{k=1}^{C^{\prime\prime}-1}(\hat{V}_{1}^{\pi^{k}}(\mu;\tilde{c}^{k},\hat{P}^{k})+\epsilon_{k}-\tau)_{+}$
$\displaystyle\leq\sum_{k=1}^{C^{\prime\prime}}\epsilon_{k}+C^{\prime\prime}(H-\tau).$
(19)

∎

The bounded constraint violation of OptPess-PrimalDual is established as
follows. Notice that

$\displaystyle\lambda^{K+1}$
$\displaystyle=\left(\lambda^{K}+\hat{V}_{1}^{\pi^{K}}(\mu;\tilde{c}^{K},\hat{P}^{K})+\epsilon_{K}-\tau\right)_{+}$
$\displaystyle\geq\epsilon_{K}+\hat{V}_{1}^{\pi^{K}}(\mu;\tilde{c}^{K},\hat{P}^{K})-\tau+\lambda^{K}$
$\displaystyle\geq\epsilon_{K}+\epsilon_{K-1}+\hat{V}_{1}^{\pi^{K}}(\mu;\tilde{c}^{K},\hat{P}^{K})-\tau+\hat{V}_{1}^{\pi^{K-1}}(\mu;\tilde{c}^{K-1},\hat{P}^{K-1})-\tau+\lambda^{K-1}$
$\displaystyle\geq\cdots$
$\displaystyle\geq\sum_{k=1}^{K}\epsilon_{k}+\sum_{k=1}^{K}\left(\hat{V}_{1}^{\pi^{k}}(\mu;\tilde{c}^{k},\hat{P}^{k})-\tau\right)+\lambda^{1}.$

Since $\lambda^{1}=0$ according to the initial condition of Algorithm 2, we
can decompose the constraint violation:

$\displaystyle Reg^{\textbf{OPPD}}(K;c)$
$\displaystyle=\left(\sum_{k=1}^{K}\left(V_{1}^{\pi^{k}}(\mu;c,P)-\hat{V}_{1}^{\pi^{k}}(\mu;\tilde{c}^{k},\hat{P}^{k})\right)+\sum_{k=1}^{K}\left(\hat{V}_{1}^{\pi^{k}}(\mu;\tilde{c}^{k},\hat{P}^{k})-\tau\right)\right)_{+}$
$\displaystyle\leq\left(\sum_{k=1}^{K}\left(V_{1}^{\pi^{k}}(\mu;c,P)-\hat{V}_{1}^{\pi^{k}}(\mu;\tilde{c}^{k},\hat{P}^{k})\right)+\lambda^{K+1}-\sum_{k=1}^{K}\epsilon_{k}\right)_{+}.$

The first summation term can be bounded by Lemma 5.5. The second
$\lambda^{K+1}$ term can be bounded by Lemma 5.6. Finally, recall
$\epsilon_{k}=5H^{2}\sqrt{|\mathcal{S}|^{3}|\mathcal{A}|}(\log\frac{k}{\delta^{\prime}}+1)/\sqrt{k\log\frac{k}{\delta^{\prime}}}$,
we have

$\displaystyle\sum_{k=1}^{K}\epsilon_{k}$
$\displaystyle\geq\int_{1}^{K+1}\epsilon_{u}\mathrm{d}u$ $\displaystyle\geq
10H^{2}\sqrt{|\mathcal{S}|^{3}|\mathcal{A}|K\log\frac{K}{\delta^{\prime}}}-10H^{2}\sqrt{|\mathcal{S}|^{3}|\mathcal{A}|\log\frac{1}{\delta^{\prime}}}.$

The negative $\sum_{k=1}^{K}\epsilon_{k}$ term can cancel the dominant terms.
Thus, with probability at least ($1-\delta$), the violation is bounded as

$\displaystyle
Reg^{\textbf{OPPD}}(K;c)=\mathcal{O}\left(C^{\prime\prime}H+H^{2}\sqrt{|\mathcal{S}|^{3}|\mathcal{A}|C^{\prime\prime}\log{(C^{\prime\prime}/\delta^{\prime})}}\right).$

###  C.2 Regret of reward analysis

For episode $k$ with $k\geq C^{\prime\prime}$, let $\pi^{\epsilon_{k},*}$ be
the optimal policy for (10), which is well-defined by the definition of
$C^{\prime\prime}$. We decompose the reward regret as

$\displaystyle Reg^{\textbf{OPPD}}$
$\displaystyle(K;r)=\sum_{k=1}^{C^{\prime\prime}}\left(V_{1}^{\pi^{*}}(\mu;r,P)-V_{1}^{\pi^{k}}(\mu;r,P)\right)$
$\displaystyle+$
$\displaystyle\sum_{k=C^{\prime\prime}}^{K}\left(V_{1}^{\pi^{*}}(\mu;r,P)-V_{1}^{\pi^{\epsilon_{k},*}}(\mu;r,P)\right)+\sum_{k=C^{\prime\prime}}^{K}\left(V_{1}^{\pi^{\epsilon_{k},*}}(\mu;r,P)-\hat{V}_{1}^{\pi^{\epsilon_{k},*}}(\mu;\tilde{r}^{k},\hat{P}^{k})\right)$
$\displaystyle+$
$\displaystyle\sum_{k=C^{\prime\prime}}^{K}\left(\hat{V}_{1}^{\pi^{\epsilon_{k},*}}(\mu;\tilde{r}^{k},\hat{P}^{k})-\hat{V}_{1}^{\pi^{k}}(\mu;\tilde{r}^{k},\hat{P}^{k})\right)+\sum_{k=C^{\prime\prime}}^{K}\left(\hat{V}_{1}^{\pi^{k}}(\mu;\tilde{r}^{k},\hat{P}^{k})-V_{1}^{\pi^{k}}(\mu;r,P)\right).$
(20)

We upper bound each term in the RHS of (20). Since
$V_{1}^{\pi}(\mu;r,P)\in[0,H]$ for any policy $\pi$, the first term is upper
bounded by $HC^{\prime\prime}$. The second and third terms can be bounded by
the following two lemmas.

######  Lemma C.4 (Restatement of Lemma 5.7).

On the good event $\mathcal{E}$,

$\displaystyle\sum_{k=C^{\prime\prime}}^{K}\left(V_{1}^{\pi^{*}}(\mu;r,P)-V_{1}^{\pi^{\epsilon_{k},*}}(\mu;r,P)\right)\leq\sum_{k=C^{\prime\prime}}^{K}\frac{\epsilon_{k}H}{\tau-c^{0}}=\tilde{\mathcal{O}}\left(\frac{H^{3}}{\tau-c^{0}}\sqrt{|\mathcal{S}|^{3}|\mathcal{A}|K}\right).$

###### Proof of Lemma 5.7.

Define a probabilistic mixed policy

$\displaystyle\pi^{\epsilon_{k}}=(1-B_{k})\pi^{*}+B_{k}\pi^{0},\quad\forall
k\geq C^{\prime\prime},$

where $B_{k}$ is a Bernoulli distributed random variable with mean
$\epsilon_{k}/(\tau-c^{0})$.

We have that

$\displaystyle V_{1}^{\pi^{\epsilon_{k}}}(\mu;c,P)$
$\displaystyle=(1-\frac{\epsilon_{k}}{\tau-c^{0}})V_{1}^{\pi^{*}}(\mu;c,P)+\frac{\epsilon_{k}}{\tau-c^{0}}V_{1}^{\pi^{0}}(\mu;c,P)$
$\displaystyle\leq(1-\frac{\epsilon_{k}}{\tau-c^{0}})\tau+\frac{\epsilon_{k}}{\tau-c^{0}}c^{0}=\tau-\epsilon_{k}.$

Though $\pi^{\epsilon_{k}}$ is not a Markov policy, by Lemma D.3, there exists
a Markov policy $\hat{\pi}^{\epsilon_{k}}$, which has the same performance as
$\pi^{\epsilon_{k}}$ under transition probabilities $P$.
$\hat{\pi}^{\epsilon_{k}}$ is a feasible solution to the following problem

$\displaystyle\max_{\pi}$ $\displaystyle\quad V_{1}^{\pi}(\mu;r,P)$ s.t.
$\displaystyle\quad V_{1}^{\pi}(\mu;c,P)+\epsilon_{k}\leq\tau.$

We then have

$\displaystyle\sum_{k=C^{\prime\prime}}^{K}V_{1}^{\pi^{*}}(\mu;r,P)-V_{1}^{\pi^{\epsilon_{k},*}}(\mu;r,P)$
$\displaystyle\leq\sum_{k=C^{\prime\prime}}^{K}V_{1}^{\pi^{*}}(\mu;r,P)-V_{1}^{\hat{\pi}^{\epsilon_{k}}}(\mu;r,P)$
$\displaystyle=\sum_{k=C^{\prime\prime}}^{K}V_{1}^{\pi^{*}}(\mu;r,P)-V_{1}^{\pi^{\epsilon_{k}}}(\mu;r,P)$
$\displaystyle\leq\sum_{k=C^{\prime\prime}}^{K}\frac{\epsilon_{k}}{\tau-c^{0}}\left(V_{1}^{\pi^{*}}(\mu;r,P)-V_{1}^{\pi^{0}}(\mu;r,P)\right)$
$\displaystyle\leq\sum_{k=C^{\prime\prime}}^{K}\frac{\epsilon_{k}H}{\tau-c^{0}}.$

∎

######  Lemma C.5 (Restatement of Lemma 5.8).

On the good event $\mathcal{E}$,
$\sum_{k=C^{\prime\prime}}^{K}\left(V_{1}^{\pi^{\epsilon_{k},*}}(\mu;r,P)-\hat{V}_{1}^{\pi^{\epsilon_{k},*}}(\mu;\tilde{r}^{k},\hat{P}^{k})\right)\leq
0$.

###### Proof of Lemma 5.8.

For any $k\in[C^{\prime\prime},K]$, $\pi^{\epsilon_{k},*}$ is well-defined. If
$\hat{V}_{1}^{\pi^{\epsilon_{k},*}}(\mu;\tilde{r}^{k},\hat{P}^{k})=V_{1}^{\pi^{\epsilon_{k},*}}(\mu;\tilde{r}^{k},\hat{P}^{k})$,
then by the value difference lemma (Lemma D.2), we know

$\displaystyle
V_{1}^{\pi^{\epsilon_{k},*}}(\mu;r,P)-\hat{V}_{1}^{\pi^{\epsilon_{k},*}}(\mu;\tilde{r}^{k},\hat{P}^{k})$
$\displaystyle=$
$\displaystyle\mathbb{E}_{\mu,\hat{P}^{k},\hat{\pi}^{\epsilon_{k},*}}\left[\sum_{h=1}^{H}\left(r_{h}(S_{h},A_{h})-\tilde{r}_{h}^{k}(S_{h},A_{h})+\sum_{s^{\prime}}(P_{h}-\hat{P}^{k}_{h})(s^{\prime}|S_{h},A_{h})V^{\pi}_{h+1}(s^{\prime};r,P)\right)~{}{\Big{|}}~{}\mathcal{F}_{k-1}\right]$
$\displaystyle\leq$
$\displaystyle\sum_{k=C^{\prime\prime}}^{K}\mathbb{E}_{\mu,\hat{P}^{k},\hat{\pi}^{\epsilon_{k},*}}\left[\sum_{h=1}^{H}(r_{h}(S_{h},A_{h})-\hat{r}_{h}^{k}(S_{h},A_{h}))-\beta_{h}^{k}-H|\mathcal{S}|\beta_{h}^{k}+H|\mathcal{S}|\beta_{h}^{k}~{}{\Big{|}}~{}\mathcal{F}_{k-1}\right]\leq
0.$

Otherwise,
$\hat{V}_{1}^{\pi^{\epsilon_{k},*}}(\mu;\tilde{r}^{k},\hat{P}^{k})=H\geq
V_{1}^{\pi^{\epsilon_{k},*}}(\mu;r,P)$. Thus
$\hat{V}_{1}^{\pi^{\epsilon_{k},*}}(\mu;\tilde{r}^{k},\hat{P}^{k})\geq
V_{1}^{\pi^{\epsilon_{k},*}}(\mu;r,P)$, for any $k\in[C^{\prime\prime},K]$,
and the lemma is proved. ∎

The pivotal step is to leverage optimism of $\pi^{k}$ to further decompose the
fourth term on the RHS of (20) and utilize the projected dual update to
transfer it into the form of $\lambda^{k}(\lambda^{k}-\lambda^{k+1})$. The
following lemmas provide high probability bounds for the remaining two terms
in the RHS of (20):

######  Lemma C.6 (Restatement of Lemma 5.9).

On the good event $\mathcal{E}$,

$\displaystyle\sum_{k=C^{\prime\prime}}^{K}\left(\hat{V}_{1}^{\pi^{\epsilon_{k},*}}(\mu;\tilde{r}^{k},\hat{P}^{k})-\hat{V}_{1}^{\pi^{k}}(\mu;\tilde{r}^{k},\hat{P}^{k})\right)=\tilde{\mathcal{O}}\left(\frac{H}{\tau-c^{0}}\sqrt{K}\right).$

###### Proof of Lemma 5.9.

Taking advantage of the optimism of $\pi^{k}$ and the definition of the dual
update, we have the following decomposition:

$\displaystyle\sum_{k=C^{\prime\prime}}^{K}\left(\hat{V}_{1}^{\pi^{\epsilon_{k},*}}(\mu;\tilde{r}^{k},\hat{P}^{k})-\hat{V}_{1}^{\pi^{k}}(\mu;\tilde{r}^{k},\hat{P}^{k})\right)=\underbrace{\sum_{k=C^{\prime\prime}}^{K}\left(\frac{\lambda^{k}}{\eta^{k}}(\hat{V}_{1}^{\pi^{\epsilon_{k},*}}(\mu;\tilde{c}^{k},\hat{P}^{k})-\hat{V}_{1}^{\pi^{k}}(\mu;\tilde{c}^{k},\hat{P}^{k}))\right)}_{\textnormal{(I)}}$
$\displaystyle+$
$\displaystyle\underbrace{\sum_{k=C^{\prime\prime}}^{K}\left(\hat{V}_{1}^{\pi^{\epsilon_{k},*}}(\mu;\tilde{r}^{k},\hat{P}^{k})-\frac{\lambda^{k}}{\eta^{k}}\hat{V}_{1}^{\pi^{\epsilon_{k},*}}(\mu;\tilde{c}^{k},\hat{P}^{k})\right)-\left(\hat{V}_{1}^{\pi^{k}}(\mu;\tilde{r}^{k},\hat{P}^{k})-\frac{\lambda^{k}}{\eta^{k}}\hat{V}_{1}^{\pi^{k}}(\mu;\tilde{c}^{k},\hat{P}^{k})\right)}_{\textnormal{(II)}}$

Owing to the optimism of $\pi^{k}$, we know (II) $\leq 0$. Term (I) can then
be upper bounded as follows:

$\displaystyle(\textnormal{I})$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\sum_{k=C^{\prime\prime}}^{K}\frac{\lambda^{k}}{\eta^{k}}\left(\tau-\epsilon_{k}-\hat{V}_{1}^{\pi^{k}}(\mu;\tilde{c}^{k},\hat{P}^{k})\right)$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\sum_{k=C^{\prime\prime}}^{K}\frac{1}{\eta^{k}}\left(\lambda^{k}(\lambda^{k}-\lambda^{k+1})+\tau^{2}\right)$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{=}}\sum_{k=C^{\prime\prime}}^{K}\frac{1}{\eta^{k}}(\frac{1}{2}(\lambda^{k})^{2}-\frac{1}{2}(\lambda^{k+1})^{2})+\sum_{k=C^{\prime\prime}}^{K}\frac{1}{2\eta^{k}}(\lambda^{k+1}-\lambda^{k})^{2}+\sum_{k=C^{\prime\prime}}^{K}\frac{1}{\eta^{k}}\tau^{2}$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{\leq}}\frac{(\lambda^{C^{\prime\prime}})^{2}}{2\eta^{C^{\prime\prime}}}+\sum_{k=C^{\prime\prime}}^{K}\frac{H^{2}}{2\eta^{k}}+\tau^{2}\sum_{k=C^{\prime\prime}}^{K}\frac{1}{\eta^{k}}$
$\displaystyle\stackrel{{\scriptstyle(e)}}{{\leq}}\frac{(\sum_{k=1}^{C^{\prime\prime}}\epsilon_{k}+C^{\prime\prime}(H-\tau))^{2}}{2\eta^{C^{\prime\prime}}}+\sum_{k=C^{\prime\prime}}^{K}\frac{H^{2}}{2\eta^{k}}+\tau^{2}\sum_{k=C^{\prime\prime}}^{K}\frac{1}{\eta^{k}}.$

(a) holds by applying Lemma C.1 for $\pi=\pi^{\epsilon_{k},*}$ and
$\hat{V}_{1}^{\pi^{\epsilon_{k},*}}(\mu;c,P)\leq\tau-\epsilon_{k}$.

(b) holds as follows: if $\lambda^{k+1}>0$, we know

$\displaystyle\tau-\epsilon_{k}-\hat{V}_{1}^{\pi^{k}}(\mu;\tilde{c}^{k},\hat{P}^{k})=\lambda^{k}-\lambda^{k+1}.$

If $\lambda^{k+1}=0$, we have

$\displaystyle\lambda^{k}\leq\tau-\epsilon_{k}-\hat{V}_{1}^{\pi^{k}}(\mu;\tilde{c}^{k},\tilde{P}^{k})<\tau,$

which indicates that
$\lambda^{k}(\tau-\epsilon_{k}-\hat{V}_{1}^{\pi^{k}}(\mu;\tilde{c}^{k},\hat{P}^{k}))\leq\tau^{2}$.
Thus,

$\displaystyle\lambda^{k}(\tau-\epsilon_{k}-\hat{V}_{1}^{\pi^{k}}(\mu;\tilde{c}^{k},\hat{P}^{k}))\leq\lambda^{k}(\lambda^{k}-\lambda^{k+1})+\tau^{2}.$

Then, (c) holds since
$-\epsilon\Delta=\frac{1}{2}\epsilon^{2}-\frac{1}{2}(\epsilon+\Delta)^{2}+\frac{1}{2}\Delta^{2}$,
where $\epsilon=\lambda^{k},\Delta=\lambda^{k+1}-\lambda^{k}$, (d) holds since
$\eta^{k}$ is monotonically increasing and
$(\lambda^{k}-\lambda^{k+1})^{2}\leq(\hat{V}_{1}^{\pi^{k}}(\mu;\tilde{c}^{k},\hat{P}^{k})+\epsilon_{k}-\tau)^{2}\leq
H^{2}$, and (e) holds according to (19). ∎

######  Lemma C.7 (Restatement of Lemma 5.10).

On the good event $\mathcal{E}$,

$\displaystyle\sum_{k=C^{\prime\prime}}^{K}\left(\hat{V}_{1}^{\pi^{k}}(\mu;\tilde{r}^{k},\hat{P}^{k})-V_{1}^{\pi^{k}}(\mu;r,P)\right)=\tilde{\mathcal{O}}(H^{2}\sqrt{|\mathcal{S}|^{3}|\mathcal{A}|K}+H^{4}|\mathcal{S}|^{3}|\mathcal{A}|).$

###### Proof of Lemma 5.10.

For any $k,s,a,h$, we have

$\displaystyle|(\tilde{r}_{h}^{k}-r_{h})(s,a)|$
$\displaystyle=|\tilde{r}_{h}^{k}(s,a)-\hat{r}_{h}^{k}(s,a)+\hat{r}^{k}_{h}(s,a)-r_{h}(s,a)|$
$\displaystyle\leq(1+|\mathcal{S}|H)\beta^{k}_{h}(s,a)+|\hat{r}^{k}_{h}(s,a)-r_{h}(s,a)|$
$\displaystyle\leq(1+|\mathcal{S}|H)\beta^{k}_{h}(s,a)+\beta^{k}_{h}(s,a)=(2+|\mathcal{S}|H)\beta^{k}_{h}(s,a).$

By Lemma D.4, we have

$\displaystyle\sum_{k=C^{\prime\prime}}^{K}\left(\hat{V}^{\pi^{k}}_{1}(\mu;\tilde{r}^{k},\hat{P}^{k})-V^{\pi^{k}}_{1}(\mu;r,P)\right)\leq\tilde{\mathcal{O}}(H^{2}\sqrt{|\mathcal{S}|^{3}|\mathcal{A}|K}+H^{4}|\mathcal{S}|^{3}|\mathcal{A}|).$

∎

###  C.3 Proof of Theorem 4.1

######  Theorem C.8 (Regret and constraint violation bounds for OptPess-
PrimalDual (Restatement of Theorem 4.1)).

On the good event $\mathcal{E}$,

$\displaystyle Reg^{\textbf{OPPD}}(K;r)$
$\displaystyle=\tilde{\mathcal{O}}\left(\frac{H^{3}}{\tau-c^{0}}\sqrt{|\mathcal{S}|^{3}|\mathcal{A}|K}+\frac{H^{5}|\mathcal{S}|^{3}|\mathcal{A}|}{(\tau-c^{0})^{2}}\right),$
$\displaystyle Reg^{\textbf{OPPD}}(K;c)$
$\displaystyle=\mathcal{O}\left(C^{\prime\prime}(H-\tau)+H^{2}\sqrt{|\mathcal{S}|^{3}|\mathcal{A}|C^{\prime\prime}}\right)=\mathcal{O}(1),$

where
$C^{\prime\prime}=\mathcal{O}(\frac{H^{4}|\mathcal{S}|^{3}|\mathcal{A}|}{(\tau-c^{0})^{2}}\log\frac{H^{4}|\mathcal{S}|^{3}|\mathcal{A}|}{(\tau-c^{0})^{2}\delta^{\prime}})$
is a coefficient independent of $K$.

###### Proof of Theorem 4.1.

The bounded constraint analysis has been provided in the previous subsection.
Applying Lemmas 5.7, 5.8, 5.9, and 5.10 yields the regret bound in Theorem
4.1. ∎

##  Appendix D Other supporting lemmas

######  Lemma D.1 (Hoeffding’s inequality [15]).

For independent zero-mean $1/2$-sub-Gaussian random variables
$X_{1},X_{2},\ldots,X_{n}$,

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

######  Lemma D.2 (Value difference lemma, [8, Lemma E.15]).

$\displaystyle V_{1}^{\pi}(\mu;g^{\prime},P^{\prime})-V_{1}^{\pi}(\mu;g,P)$
$\displaystyle=$
$\displaystyle\mathbb{E}_{\mu,P,\pi}\left[\sum_{h=1}^{H}\left(g^{\prime}(S_{h},A_{h})-g(S_{h},A_{h})+\sum_{s^{\prime}}(P^{\prime}_{h}-P_{h})(s^{\prime}|S_{h},A_{h})V^{\pi}_{h+1}(s^{\prime};g^{\prime},P^{\prime})\right)~{}{\Big{|}}~{}\mathcal{F}_{k-1}\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}_{\mu,P^{\prime},\pi}\left[\sum_{h=1}^{H}\left(g^{\prime}(S_{h},A_{h})-g(S_{h},A_{h})+\sum_{s^{\prime}}(P^{\prime}_{h}-P_{h})(s^{\prime}|S_{h},A_{h})V^{\pi}_{h+1}(s^{\prime};g,P)\right)~{}{\Big{|}}~{}\mathcal{F}_{k-1}\right],$

where $g=g^{\prime}=r,c$.

######  Lemma D.3 ([2, Theorem 6.1(i)]).

Suppose the transition function is $P$. For any mixed policy
$\tilde{\pi}=B_{\gamma}\pi^{1}+(1-B_{\gamma})\pi^{2}$, where $B_{\gamma}$ is a
Bernoulli distributed random variable with mean $\gamma$. Then there exists a
Markov policy $\hat{\pi}$ that

$\displaystyle
V^{\hat{\pi}}_{h}(s;r,P)=V^{\tilde{\pi}}_{h}(s;r,P),\quad\forall r,s,h.$

######  Lemma D.4.

Let $\mathcal{G}_{1:K}$ be a sequence of events such that
$\mathcal{G}_{k}\in\mathcal{F}_{k-1}$ for each $k\in[K]$. Suppose
$|\tilde{g}^{k}-g|\leq\alpha\beta^{k}$, $\alpha\geq 1$. On the good event
$\mathcal{E}$, for any $K^{\prime}\leq K$,

$\displaystyle\sum_{k=1}^{K^{\prime}}\mathbbm{1}(\mathcal{G}_{k})|V^{\pi^{k}}_{1}(\mu;\tilde{g}^{k},\hat{P}^{k})-V^{\pi^{k}}_{1}(\mu;g,P)|$
$\displaystyle\leq(3\alpha+3\sqrt{2}H\sqrt{|\mathcal{S}|})H\sqrt{|\mathcal{S}||\mathcal{A}|K^{\prime}_{\mathcal{G}}Z}$
$\displaystyle+\tilde{\mathcal{O}}\left(\alpha
H^{3}|\mathcal{S}|^{2}|\mathcal{A}|)\right),$

where $\mathcal{G}_{1:K}=(\Omega)_{1:K}$ or
$\mathcal{G}_{1:k}=\\{V^{\pi^{0}}_{1}(\mu;\underline{c}^{k},\hat{P}^{k})\geq\frac{\tau+c^{0}}{2}\\}_{k\in[K]}$,
and
$K^{\prime}_{\mathcal{G}}=\sum_{k=1}^{K^{\prime}}\mathbbm{1}(\mathcal{G}_{k})$.

###### Proof of Lemma D.4.

It can be proved following steps similar to those in the proof of Lemma 32 in
[11], but utilizing Lemma D.5 for taking account of the predictable event
sequence $\mathcal{G}_{1:K}$, and Lemma D.6 for bounding the leading order
explicitly. For completeness, we include the detailed proof here.

$\displaystyle\sum_{k=1}^{K^{\prime}}\mathbbm{1}(\mathcal{G}_{k})\left|V^{\pi^{k}}_{1}(\mu;\tilde{g}^{k},\hat{P}^{k})-V^{\pi^{k}}_{1}(\mu;g,P)\right|$
$\displaystyle=$
$\displaystyle\sum_{k=1}^{K^{\prime}}\sum_{h=1}^{H}\sum_{s,a}\mathbbm{1}(\mathcal{G}_{k})q^{\pi_{k}}(s,a,h)\left|\tilde{g}_{h}^{k}(s,a)-g_{h}(s,a)+\sum_{s^{\prime}}(\hat{P}_{h}^{k}-P_{h})(s^{\prime}|s,a)V_{h+1}^{\pi_{k}}(s^{\prime};\tilde{g}^{k},\hat{P}^{k})\right|$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}$
$\displaystyle\sum_{k=1}^{K^{\prime}}\sum_{h=1}^{H}\sum_{s,a}\mathbbm{1}(\mathcal{G}_{k})q^{\pi_{k}}(s,a,h)\left[\alpha\beta_{h}^{k}(s,a)+\sqrt{\sum_{s^{\prime}}2P(s^{\prime}|s,a)(\beta_{h}^{k}(s,a))^{2}}\sqrt{|\mathcal{S}|H^{2}}+\frac{ZH|\mathcal{S}|}{N_{h}^{k}(s,a)\vee
1}\right]$ $\displaystyle+$
$\displaystyle\sum_{k=1}^{K^{\prime}}\sum_{h=1}^{H}\sum_{s,a}\mathbbm{1}(\mathcal{G}_{k})q^{\pi_{k}}(s,a,h)\left|\sum_{s^{\prime}}(\hat{P}_{h}^{k}-P_{h})(s^{\prime}|s,a)\left(V_{h+1}^{\pi_{k}}(s^{\prime};\tilde{g}^{k},\hat{P}^{k})-V_{h+1}^{\pi_{k}}(s^{\prime};g,P)\right)\right|$
$\displaystyle=$
$\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}\sum_{s,a}\mathbbm{1}(\mathcal{G}_{k})q^{\pi_{k}}(s,a,h)\left[(\alpha+\sqrt{2|\mathcal{S}|}H)\sqrt{\frac{Z}{N_{h}^{k}(s,a)\vee
1}}+\frac{ZH|\mathcal{S}|}{N_{h}^{k}(s,a)\vee 1}\right]$ $\displaystyle+$
$\displaystyle\sum_{k=1}^{K^{\prime}}\sum_{h=1}^{H}\sum_{s,a}\mathbbm{1}(\mathcal{G}_{k})q^{\pi_{k}}(s,a,h)\left|\sum_{s^{\prime}}(\hat{P}_{h}^{k}-P_{h})(s^{\prime}|s,a)\left(V_{h+1}^{\pi_{k}}(s^{\prime};\tilde{g}^{k},\hat{P}^{k})-V_{h+1}^{\pi_{k}}(s^{\prime};g,P)\right)\right|.$

Since

$\displaystyle\sum_{k=1}^{K^{\prime}}\sum_{h=1}^{H}\sum_{s,a}\mathbbm{1}(\mathcal{G}_{k})q^{\pi_{k}}(s,a,h)\left|\sum_{s^{\prime}}(\hat{P}_{h}^{k}-P_{h})(s^{\prime}|s,a)\left(V_{h+1}^{\pi_{k}}(s^{\prime};\tilde{g}^{k},\hat{P}^{k})-V_{h+1}^{\pi_{k}}(s^{\prime};g,P)\right)\right|$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}$
$\displaystyle\sum_{k=1}^{K^{\prime}}\sum_{h=1}^{H}\sum_{s,a}\mathbbm{1}(\mathcal{G}_{k})q^{\pi_{k}}(s,a,h)\sum_{s^{\prime}}\frac{\sqrt{2P_{h}(s^{\prime}|s,a)Z}}{\sqrt{N_{h}^{k}(s,a)\vee
1}}\left|V_{h+1}^{\pi_{k}}(s^{\prime};\tilde{g}^{k},\hat{P}^{k})-V_{h+1}^{\pi_{k}}(s^{\prime};g,P)\right|$
$\displaystyle+$
$\displaystyle\sum_{k=1}^{K^{\prime}}\sum_{h=1}^{H}\sum_{s,a}\mathbbm{1}(\mathcal{G}_{k})q^{\pi_{k}}(s,a,h)\frac{(1+\alpha)|\mathcal{S}|HZ}{N_{h}^{k}(s,a)\vee
1}$ $\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}$
$\displaystyle\tilde{\mathcal{O}}(\alpha
H^{2}|\mathcal{S}|^{2}|\mathcal{A}|)+|\mathcal{S}|\sqrt{\alpha|\mathcal{A}|H^{3}}\sqrt{\sum_{k=1}^{K^{\prime}}\mathbbm{1}(\mathcal{G}_{k})\left|V_{1}^{\pi^{k}}(\mu;\tilde{g}^{k},\hat{P}^{k})-V_{1}^{\pi^{k}}(\mu;g,P)\right|}+|\mathcal{S}|\sqrt{\alpha|\mathcal{A}|H^{3}}$
$\displaystyle\times$
$\displaystyle\sqrt{\sum_{k=1}^{K^{\prime}}\sum_{h=1}^{H}\sum_{s,a}\mathbbm{1}(\mathcal{G}_{k})q^{\pi_{k}}(s,a,h)\left|\sum_{s^{\prime}}(\hat{P}_{h}^{k}-P_{h})(s^{\prime}|s,a)\left(V_{h+1}^{\pi_{k}}(s^{\prime};\tilde{g}^{k},\hat{P}^{k})-V_{h+1}^{\pi_{k}}(s^{\prime};g,P)\right)\right|}$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{\leq}}$
$\displaystyle\tilde{\mathcal{O}}(\alpha
H^{3}|\mathcal{S}|^{2}|\mathcal{A}|)+\frac{3}{2}|\mathcal{S}|H\sqrt{\alpha|\mathcal{A}|H}\sqrt{\sum_{k=1}^{K^{\prime}}\mathbbm{1}(\mathcal{G}_{k})\left|V_{1}^{\pi^{k}}(\mu;\tilde{g}^{k},\hat{P}^{k})-V_{1}^{\pi^{k}}(\mu;g,P)\right|},$

we have

$\displaystyle\sum_{k=1}^{K^{\prime}}\mathbbm{1}(\mathcal{G}_{k})\left|V_{1}^{\pi^{k}}(\mu;\tilde{g}^{k},\hat{P}^{k})-V_{1}^{\pi^{k}}(\mu;g,P)\right|$
$\displaystyle\stackrel{{\scriptstyle(e)}}{{\leq}}$
$\displaystyle(2\alpha+2\sqrt{2}H\sqrt{|\mathcal{S}|})H\sqrt{|\mathcal{S}||\mathcal{A}|K^{\prime}_{\mathcal{G}}Z}+\tilde{\mathcal{O}}\left(H|\mathcal{S}||\mathcal{A}|(\alpha+|\mathcal{S}|H)\right)+\tilde{\mathcal{O}}(\alpha
H^{3}|\mathcal{S}|^{2}|\mathcal{A}|)$ $\displaystyle+$
$\displaystyle\frac{3}{2}|\mathcal{S}|H\sqrt{\alpha|\mathcal{A}|H}\sqrt{\sum_{k=1}^{K^{\prime}}\mathbbm{1}(\mathcal{G}_{k})\left|V_{1}^{\pi^{k}}(\mu;\tilde{g}^{k},\hat{P}^{k})-V_{1}^{\pi^{k}}(\mu;g,P)\right|}$
$\displaystyle\stackrel{{\scriptstyle(f)}}{{\leq}}$
$\displaystyle(3\alpha+3\sqrt{2}H\sqrt{|\mathcal{S}|})H\sqrt{|\mathcal{S}||\mathcal{A}|K^{\prime}_{\mathcal{G}}Z}+\tilde{\mathcal{O}}\left(\alpha
H^{3}|\mathcal{S}|^{2}|\mathcal{A}|\right).$

(a) and (b) hold due to the triangle inequality, the Cauchy-Schawarz
inequality, and since
$|V_{1}^{\pi^{k}}(\mu;\tilde{g}^{k},\hat{P}^{k})-V_{1}^{\pi^{k}}(\mu;g,P)|\leq|V_{1}^{\pi^{k}}(\mu;\tilde{g}^{k},\hat{P}^{k})-V_{1}^{\pi^{k}}(\mu;g,\hat{P}^{k})|+|V_{1}^{\pi^{k}}(\mu;g,\hat{P}^{k})-V_{1}^{\pi^{k}}(\mu;g,P)|\leq(\alpha+1)H$.
(c) follows by steps similar to those in Lemma 32 in [12]. (d) and (f) hold
due to Lemma D.6. (e) holds due to Lemma D.5. ∎

######  Lemma D.5 ([17, Lemma 10] with a predictable events sequence).

Given a sequence of events $\mathcal{G}_{1:K}$ that
$\mathcal{G}_{k}\in\mathcal{F}_{k-1}$ for each $k\in[K]$. With probability at
least $1-\delta$, for any $K^{\prime}\leq K$

$\displaystyle\sum_{k=1}^{K^{\prime}}\sum_{h=1}^{H}\sum_{s,a}\frac{\mathbbm{1}(\mathcal{G}_{k})q^{\pi^{k}}(s,a,h)}{N^{k}_{h}(s,a)\lor
1}$ $\displaystyle\leq
4H|\mathcal{S}||\mathcal{A}|+2H|\mathcal{S}||\mathcal{A}|\ln
K^{\prime}_{\mathcal{G}}+4\ln\frac{2HK}{\delta},$
$\displaystyle\sum_{k=1}^{K^{\prime}}\sum_{h=1}^{H}\sum_{s,a}\frac{\mathbbm{1}(\mathcal{G}_{k})q^{\pi^{k}}(s,a,h)}{\sqrt{N^{k}_{h}(s,a)\lor
1}}$ $\displaystyle\leq
6H|\mathcal{S}||\mathcal{A}|+2H\sqrt{|\mathcal{S}||\mathcal{A}|K^{\prime}_{\mathcal{G}}}+2H|\mathcal{S}||\mathcal{A}|\ln
K^{\prime}_{\mathcal{G}}+5\ln\frac{2HK}{\delta},$

where
$K^{\prime}_{\mathcal{G}}=\sum_{k=1}^{K^{\prime}}\mathbbm{1}(\mathcal{G}_{k})$
and $q^{\pi^{k}}$ is the occupancy measure of policy $\pi^{k}$, i.e.,
$q^{\pi^{k}}(s,a,h)=\mathbb{E}_{\mu,P,\pi^{k}}[\mathbbm{1}(S_{h}^{k}=s,A_{h}^{k}=a)|\mathcal{F}_{k-1}]$.

###### Proof of Lemma D.5.

This lemma can be proved following steps similar to those in the proof of
Lemma 10 in [17]. For completeness, we include the detailed proof here.

Let $\mathbbm{1}_{k}(s,a,h)$ be the indicator of whether the pair $(s,a)$ is
visited at step $h$ in episode $k$, so that
$\mathbb{E}_{k}[\mathbbm{1}_{k}(s,a,h)]=q^{\pi^{k}}(s,a,h)$. We decompose the
first quantity as

$\displaystyle\sum_{k=1}^{K^{\prime}}\sum_{h=1}^{H}\sum_{s,a}\frac{\mathbbm{1}(\mathcal{G}_{k})q^{\pi^{k}}(s,a,h)}{N^{k}_{h}(s,a)\lor
1}$
$\displaystyle=\sum_{k=1}^{K^{\prime}}\sum_{h=1}^{H}\sum_{s,a}\frac{\mathbbm{1}(\mathcal{G}_{k})\mathbbm{1}_{k}(s,a,h)}{N^{k}_{h}(s,a)\lor
1}$
$\displaystyle+\sum_{k=1}^{K^{\prime}}\sum_{h=1}^{H}\sum_{s,a}\frac{\mathbbm{1}(\mathcal{G}_{k})(q^{\pi^{k}}(s,a,h)-\mathbbm{1}_{k}(s,a,h))}{N^{k}_{h}(s,a)\lor
1}.$

The first term can be bounded as

$\displaystyle\sum_{k=1}^{K^{\prime}}\sum_{h=1}^{H}\sum_{s,a}\frac{\mathbbm{1}(\mathcal{G}_{k})\mathbbm{1}_{k}(s,a,h)}{N^{k}_{h}(s,a)\lor
1}\leq 2H|\mathcal{S}||\mathcal{A}|+H|\mathcal{S}||\mathcal{A}|\ln
K^{\prime}_{\mathcal{G}}.$

To bound the second term, we apply Lemma 9 in [17] with
$Y_{k}=\sum_{h=1}^{H}\sum_{s,a}\frac{\mathbbm{1}(\mathcal{G}_{k})(q^{\pi^{k}}(s,a,h)-\mathbbm{1}_{k}(s,a,h))}{N^{k}_{h}(s,a)\lor
1},\lambda=1/2$, and the fact

$\displaystyle\mathbb{E}_{k}[Y_{k}^{2}]$
$\displaystyle\leq\mathbb{E}_{k}\left[\left(\sum_{h=1}^{H}\sum_{s,a}\frac{\mathbbm{1}(\mathcal{G}_{k})\mathbbm{1}_{k}(s,a,h)}{N^{k}_{h}(s,a)\lor
1}\right)^{2}\right]$
$\displaystyle=\mathbb{E}_{k}\left[\sum_{h=1}^{H}\sum_{s,a}\frac{\mathbbm{1}(\mathcal{G}_{k})\mathbbm{1}_{k}(s,a,h)}{(N^{k}_{h}(s,a))^{2}\lor
1}\right]$
$\displaystyle\leq\sum_{h=1}^{H}\sum_{s,a}\frac{\mathbbm{1}(\mathcal{G}_{k})q^{\pi^{k}}(s,a,h)}{N^{k}_{h}(s,a)\lor
1},$

which show that with probability at least $1-\delta/(2HK)$,

$\displaystyle\sum_{k=1}^{K^{\prime}}\sum_{h=1}^{H}\sum_{s,a}\frac{\mathbbm{1}(\mathcal{G}_{k})(q^{\pi^{k}}(s,a,h)-\mathbbm{1}_{k}(s,a,h))}{N^{k}_{h}(s,a)\lor
1}\leq\frac{1}{2}\sum_{k=1}^{K^{\prime}}\sum_{h=1}^{H}\sum_{s,a}\frac{\mathbbm{1}(\mathcal{G}_{k})q^{\pi^{k}}(s,a,h)}{N^{k}_{h}(s,a)\lor
1}+2\ln\frac{2HK}{\delta}.$

Combining these two bounds, rearranging, and applying a union bound over $k$
proves the first part of the lemma.

Similarly, we decompose the second quantity as

$\displaystyle\sum_{k=1}^{K^{\prime}}\sum_{h=1}^{H}\sum_{s,a}\frac{\mathbbm{1}(\mathcal{G}_{k})q^{\pi^{k}}(s,a,h)}{\sqrt{N^{k}_{h}(s,a)\lor
1}}$
$\displaystyle=\sum_{k=1}^{K^{\prime}}\sum_{h=1}^{H}\sum_{s,a}\frac{\mathbbm{1}(\mathcal{G}_{k})\mathbbm{1}_{k}(s,a,h)}{\sqrt{N^{k}_{h}(s,a)\lor
1}}$
$\displaystyle+\sum_{k=1}^{K^{\prime}}\sum_{h=1}^{H}\sum_{s,a}\frac{\mathbbm{1}(\mathcal{G}_{k})(q^{\pi^{k}}(s,a,h)-\mathbbm{1}_{k}(s,a,h))}{\sqrt{N^{k}_{h}(s,a)\lor
1}}.$

The first term is bounded as

$\displaystyle\sum_{k=1}^{K^{\prime}}\sum_{h=1}^{H}\sum_{s,a}\frac{\mathbbm{1}(\mathcal{G}_{k})\mathbbm{1}_{k}(s,a,h)}{\sqrt{N^{k}_{h}(s,a)\lor
1}}\leq
2H|\mathcal{S}||\mathcal{A}|+2H\sqrt{|\mathcal{S}||\mathcal{A}|K^{\prime}_{\mathcal{G}}}.$

To bound the second term, we again apply Lemma 9 in [17] with
$Y_{k}=\sum_{h=1}^{H}\sum_{s,a}\frac{\mathbbm{1}(\mathcal{G}_{k})(q^{\pi^{k}}(s,a,h)-\mathbbm{1}_{k}(s,a,h))}{\sqrt{N^{k}_{h}(s,a)\lor
1}}\leq 1,\lambda=1$, and the fact

$\displaystyle\mathbb{E}_{k}[Y_{k}^{2}]\leq\mathbb{E}_{k}\left[\left(\sum_{h=1}^{H}\sum_{s,a}\frac{\mathbbm{1}(\mathcal{G}_{k})\mathbbm{1}_{k}(s,a,h)}{\sqrt{N^{k}_{h}(s,a)\lor
1}}\right)^{2}\right]=\sum_{h=1}^{H}\sum_{s,a}\frac{\mathbbm{1}(\mathcal{G}_{k})q^{\pi^{k}}(s,a,h)}{N^{k}_{h}(s,a)\lor
1},$

which shows that with probability at least $1-\delta/(2HK)$,

$\displaystyle\sum_{k=1}^{K^{\prime}}\sum_{h=1}^{H}\sum_{s,a}\frac{\mathbbm{1}(\mathcal{G}_{k})(q^{\pi^{k}}(s,a,h)-\mathbbm{1}_{k}(s,a,h))}{\sqrt{N^{k}_{h}(s,a)\lor
1}}$
$\displaystyle\leq\sum_{k=1}^{K^{\prime}}\sum_{h=1}^{H}\sum_{s,a}\frac{\mathbbm{1}(\mathcal{G}_{k})q^{\pi^{k}}(s,a,h)}{N^{k}_{h}(s,a)\lor
1}+\ln\frac{2HK}{\delta}.$

Combining the first part of the lemma and employing a union bound proves the
second part of the lemma. ∎

######  Lemma D.6.

Suppose $0\leq x\leq a+b\sqrt{x}$, for some $a,b>0$,

$\displaystyle x\leq\frac{3}{2}a+\frac{3}{2}b^{2}.$

###### Proof of Lemma D.6.

By solving the equation of $x_{0}=a+b\sqrt{x_{0}}$, we know

$\displaystyle x$ $\displaystyle\leq
x_{0}=\frac{1}{2}(\sqrt{4ab^{2}+b^{4}}+2a+b^{2})$
$\displaystyle\leq\sqrt{ab^{2}}+\frac{b^{2}}{2}+a+\frac{b^{2}}{2}$
$\displaystyle\leq\frac{3}{2}a+\frac{3}{2}b^{2}.$

∎

######  Lemma D.7 ([21, Lemma 11]).

Let $S(k)$ be a random process, $\Phi(k)$ be its Lyapunov function with
$\Phi(0)=\Phi_{0}$ and $\Delta(k)=\Phi(k+1)-\Phi(k)$ be the Lyapunov drift.
Given an increasing sequence $\left\\{\varphi_{t}\right\\},\rho$ and
$\nu_{\max}$ with $0<\rho\leq\nu_{\max}$, if the expected drift
$\mathbb{E}[\Delta(k)|S(k)=s]$ satisfies the following conditions:
(i) There exists constants $\rho>0$ and $\varphi_{t}>0$ s.t.
$\Delta(k)\leq-\rho$ when $\Phi(k)\geq\varphi_{k}$, and
(ii) $|\Phi(k+1)-\Phi(k)|\leq\nu_{\max}$ holds with probability one;
then we have

$\displaystyle e^{\zeta\Phi(k)}\leq
e^{\zeta\Phi_{0}}+\frac{2e^{\zeta\left(\nu_{\max}+\varphi_{k}\right)}}{\zeta\rho},$

where $\zeta=\rho/(\nu_{\max}^{2}+\nu_{\max}\rho/3)$.

##  Appendix E Extensions (unknown $c^{0}$ with prior knowledge of $\pi^{0}$)

It may be noticed that the OptPess-LP algorithm can guarantee zero violation
with high probability if a coefficient $c^{0^{\prime}}$ with
$V^{\pi^{0}}_{1}(\mu;c,P)\leq c^{0^{\prime}}<\tau$ is used to replace $c^{0}$
in the inputs. Thus when the value $V^{\pi^{0}}_{1}(\mu;c,P)$ is not known,
one may first estimate an appropriate upper bound of
$V^{\pi^{0}}_{1}(\mu;c,P)$, and call OptPess-LP using this upper bound. The
details of choosing the upper bound are as follows.

We can execute policy $\pi^{0}$ sequentially until an estimate of $c^{0}$ with
enough precision is obtained. Denote $\hat{c}^{0}(k)$ as the mean estimate
after executing policy $\pi^{0}$ $k$ times. We stop the estimation process
after $K^{\prime\prime}$ executions, where

$\displaystyle K^{\prime\prime}:=\min\left\\{k\geq 1:\tau-\hat{c}^{0}(k)\geq
3\sqrt{\frac{1}{kH}\log\frac{2K}{\delta^{\prime\prime}}}\right\\}\land K.$

By Hoeffding’s inequality, with probability at least
$1-\delta^{\prime\prime}$,

$\displaystyle|\hat{c}^{0}(k)-c^{0}|\leq\sqrt{\frac{1}{kH}\log\frac{2K}{\delta^{\prime\prime}}}.$

Thus with probability at least $1-\delta^{\prime\prime}$, for
$k=K^{\prime\prime}-1$,

$\displaystyle\tau-4\sqrt{\frac{1}{kH}\log\frac{2K}{\delta^{\prime\prime}}}<\hat{c}^{0}(k)-\sqrt{\frac{1}{kH}\log\frac{2K}{\delta^{\prime\prime}}}\leq
c^{0},$

which implies

$\displaystyle K^{\prime\prime}=k+1\leq
1+\frac{16\log(2K/\delta^{\prime\prime})}{H(\tau-c^{0})^{2}}.$

Then $K^{\prime\prime}<K$ can then be guaranteed if
$\frac{16\log(2K/\delta^{\prime\prime})}{H(\tau-c^{0})^{2}}<K-1$. After
$K^{\prime\prime}$ executions, with probability at least
$1-\delta^{\prime\prime}$,

$\displaystyle c^{0^{\prime}}=$
$\displaystyle\hat{c}^{0}(K^{\prime\prime})+\sqrt{\frac{1}{K^{\prime\prime}H}\log\frac{2K}{\delta^{\prime\prime}}}$
$\displaystyle=$
$\displaystyle\frac{1}{2}\left(\hat{c}^{0}(K^{\prime\prime})-\sqrt{\frac{1}{K^{\prime\prime}H}\log\frac{2K}{\delta^{\prime\prime}}}\right)+\frac{1}{2}\left(\hat{c}^{0}(K^{\prime\prime})+3\sqrt{\frac{1}{K^{\prime\prime}H}\log\frac{2K}{\delta^{\prime\prime}}}\right)$
$\displaystyle\leq$
$\displaystyle\frac{1}{2}c^{0}+\frac{1}{2}\tau=\frac{1}{2}(c^{0}+\tau).$

We can apply the OptPess-LP algorithm with a pessimistic estimate
$\left(\hat{c}^{0}(K^{\prime\prime})+\sqrt{\frac{1}{K^{\prime\prime}H}\log\frac{2K}{\delta^{\prime\prime}}}\right)$
of $c^{0}$. It also maintains zero constraint violation with the same order of
regret since $1/(\tau-c^{0^{\prime}})\leq
1/(\tau-\frac{1}{2}(c^{0}+\tau))=2/(\tau-c^{0})$.