Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPs
Year: 2022

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 Õ( √ K) while allowing an Õ( √ 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 Õ( √ 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.

text: √ K) while
allowing an Õ( √ 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 Õ( √ 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.

heading: 1 Introduction
text: Reinforcement learning (RL) addresses the problem of learning an optimal control policy that maximizes the expected cumulative reward while interacting with an unknown environment [25]. 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 [9, 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, 12] 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 [26, 24, 21, 16] formulate the CMDP problem as a saddle-point problem and optimize it via primal-dual methods, while Constrained Policy Optimization [1, 29] (inspired by the trust region policy optimization [23]) 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) [8, 10, 22], and provide an Õ( √ K) guarantee
∗The first two authors contributed equally.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
for the reward regret, where K is the number of episodes. However, these algorithms also have Õ( √ 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 Õ( √ K) regret with respect to the performance objective, while guaranteeing zero or bounded safety constraint violation with arbitrarily high probability?
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 [20, 17], 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 Õ( √ 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. 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 Õ( H 3 τ−c0 √ |S|3|A|K) with respect to the performance objective,
where H is the number of steps per episode, τ is the given constraint on safety violation, c0 is the known safety constraint value of a strictly safe policy π0, and |S| and |A| are the number of states and actions respectively.
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
2This table is presented for K ≥ poly(|S|, |A|, H), with polynomial terms independent of K omitted. 3Efroni et al. [10] use 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 |S|2|A| to boundN . 4Zheng et al. [30] assumes a known transition kernel and analyzes regret in the long-term average setting. 5The detailed constraint violation is O ( C′′H +H2 √ |S|3|A|C′′ log(C′′/δ′) ) , which is independent of
K. Here, δ′ = δ/(16|S|2|A|H) and C′′ = O(H 4|S|3|A| (τ−c0)2 log H4|S|3|A| (τ−c0)2δ′ ).
ensuring a bounded safety constraint violation during learning and a reward regret of Õ( H 3 τ−c0 √ |S|3|A|K) with respect to the objective.
Compared with the other methods listed in Table 1, though the proposed algorithms have an additional H/(τ − c0) or √ |S|/(τ − c0) 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.

heading: 1.1 Related work
text: 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 [26, 24, 21, 16, 1, 29]. Also of interest are works which utilize Gaussian processes to model the transition probabilities and value functions [5, 27, 15, 7].
Several algorithms with provable guarantees are closely related to our work. Zheng et al. [30] considered the constrained RL problem in an infinite horizon setting with unknown reward and cost functions. The approach is similar to the UCRL2 algorithm [13] and achieves a sub-linear reward regret Õ(T 34 ) while satisfying constraints with high probability during learning. In contrast to this work, we consider the setting of unknown transition probabilities. Efroni et al [10] focused on the episodic setting of unknown non-stationary transitions over a finite horizon, attaining both a reward regret and a constraint violation of Õ(H2 √ |S|3|A|K). Ding et al. [8] studied an episodic setting with linear function approximation (suitable for large state space cases), and proposed algorithms that can achieve Õ(dH3 √ K) for both the regret and the constraint violation (where d is the dimension of the feature mapping). The regret analysis in [8] can be easily extended to the tabular case, yielding Õ(H3 √ |S|2|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 [28, 14, 11], 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, 20, 17, 18].

heading: 2 Problem formulation
text: A finite-horizon constrained non-stationary MDP model is defined as a tuple M = (S,A, H, P, r, c, τ, µ), where S is the state space, A is the action space, H is the number of steps in each episode, r : S ×A → [0, 1] is the unknown reward function of interest, c : S ×A → [0, 1] is the unknown safety cost function used to model the constraint violation, τ ∈ (0, H] is the given constant used to define the safety constraint, and µ is the known initial distribution of the state. P·(·|s, a) ∈ ∆HS ,∀s ∈ S,∀a ∈ A, where ∆S is the |S|-dimensional probability simplex, and Ph(s
′|s, a) is the unknown transition probability that the next state is s′ 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 π : S × [H]→ ∆A, with πh(a|s) being the probability of taking action a in state s at time step h. With St and At representing the state and the action at time t respectively, let
V πh (s; g, P ) := EP,π [ H∑ t=h g(St, At)|Sh = s ] , ∀s ∈ S
denote the expected cumulative value with respect to a function g : S × A → R+ under P for a policy π over a time interval [h, h+ 1, . . . ,H]. With slightly abuse of notation, we use V π1 (µ; g, P ) to denote ES1∼µ[V π1 (S1; g, P )].
In the formulation below there are a total of K episodes with H steps each. Each episode k ∈ [K] begins with an initial probability distribution µ for S1. Then, the agent determines a randomized Markov policy π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 Akh at state Skh , the agent receives a noisy reward and cost of R k h(S k h, A k h) = rh(S k h, A k h) + ξ k h(S k h, A k h; r) and Ckh(S k h, A k h) = ch(S k h, A k h) + ξ k h(S k h, A k h; c), respectively. Assumption 2.1 (Sub-Gaussian noise). For all h ∈ [H], k ∈ [K], the reward and cost noise random variables are conditionally independent zero-mean 1/2-sub-Gaussian, i.e., E[ξkh|Fk−1] = 0, E[exp(λξkh)|Fk−1] ≤ exp(λ2/4), ∀λ ∈ R. Here Fk is the σ-algebra generated by the random variables up to episode k.
Let π∗ denote the optimal policy of the following CMDP model:
max π
V π1 (µ; r, P ) s.t. V π 1 (µ; c, P ) ≤ τ. (1)
A policy π is said to be strictly safe if V π1 (µ; c, P ) < τ .
Assumption 2.2. There exists a strictly safe policy π0 with V π 0
1 (µ; c, P ) = c 0 < τ .
There are two important cases of the safe learning problem.
Zero constraint violation case: The agent has prior knowledge of a strictly safe policy π0 and its safety cost value c0 := V π 0
1 (µ; c, P ). The agent wishes to attain a sublinear (in K) cumulative regret,
Reg(K; r) := K∑ k=1 ( V π ∗ 1 (µ; r, P )− V π k 1 (µ; r, P ) ) , (2)
while incurring zero constraint violation with at least a specified high probability (1− δ), i.e., P ( V π k 1 (µ; c, P ) ≤ τ,∀k ∈ [K] ) ≥ 1− δ.
Bounded constraint violation case: The agent knows that there exists a strictly safe policy with a known safety cost value c0, 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,
Reg(K; c) := ( K∑ k=1 ( V π k 1 (µ; c, P )− τ ))
+
(where (a)+ := max{a, 0}) ,
satisfies supK Reg(K; c) < +∞ with at least a specified high probability (1− δ). Remarks. For the zero constraint violation case, the assumption of knowing c0 can be relaxed, as shown in Appendix E.

heading: 3 Zero constraint violation case
text: We start by considering the zero constraint violation case. On one hand, to balance the explorationexploitation 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:
P̂ kh (s ′|s, a) :=
∑k−1 k′=1 1(S k′ h = s,A k′ h = a, S k′ h+1 = s ′)
Nkh (s, a) ∨ 1 , (3)
ĝkh(s, a) :=
∑k−1 k′=1 1(S k′ h = s,A k′ h = a)(gh(s, a) + ξ k h(s, a; g))
Nkh (s, a) ∨ 1 , for g = r, c, (4)
where a ∨ b := max{a, b}, and
Nkh (s, a) := # of visits to state-action pair (s, a) at step h in episodes [1, 2, . . . , k − 1]. (5)
Next we fix some δ ∈ (0, 1) and form a common (for notational simplicity) confidence radius βkh(s, a) for the transition probabilities, the rewards, and the costs,
βkh(s, a) :=
√ 1
Nkh (s, a) ∨ 1 Z, where Z := log(16|S|2|A|HK/δ).
At each episode k, we define the optimistically biased reward estimate as
r̄kh(s, a) := r̂ k h(s, a) + αrβ k h(s, a), ∀(s, a, h) ∈ S ×A× [H], (6)
where the scaling factor is
αr := 1 + |S|H + 4H(1 + |S|H)
τ − c0 . (7)
To guarantee safe exploration, define the pessimistically biased safety cost estimate at episode k as
ckh(s, a) := ĉ k h(s, a) + (1 +H|S|)βkh(s, a), ∀(s, a, h) ∈ S ×A× [H]. (8)
The policy we execute at episode k is chosen from a “pessimistically safe" policy set Πk, defined as
Πk := { {π0} if V π01 (µ; ck, P̂ k) ≥ (τ + c0)/2, {π : V π1 (µ; ck, P̂ k) ≤ τ} otherwise.
(9)
We simply use the strictly safe policy π0 until V π 0
1 (µ; c k, P̂ k) < (τ + c0)/2, which is a sufficient
condition to guarantee that the set {π : V π1 (µ; ck, P̂ k) ≤ τ} is non-empty. Within this set, we choose the optimistically best reward earning policy πk, which can be solved by linear programming with Θ(|S||A|H) decision variables and constraints [10]. The resulting Optimistic Pessimism-based Linear Programming (OptPess-LP) algorithm is presented below:
Algorithm 1: OptPess-LP Input: K, δ, π0, c0, τ ; Initialization: N1h(s, a) = 0, ∀(s, a, h) ∈ S ×A× [H]; for k = 1, 2, . . . ,K do
Update empirical model (i.e., P̂ k, r̂k, ĉk) as in Equations (3)-(5); Update r̄k, ck, and Πk as in Equations (6)-(9); Calculate πk ∈ arg maxπ∈Πk V π1 (µ; r̄k, P̂ k); Execute πk and collect a trajectory (Skh, A k h, R k h, C k h), ∀h ∈ [H]; Update counters Nk+1h (S k h, A k h), ∀h ∈ [H];
end
Theorem 3.1 (Regret and constraint violation bounds for OptPess-LP). Fix any δ ∈ (0, 1). With probability at least (1− δ), OptPess-LP has zero constraint violation with
RegOPLP(K; r) = Õ ( H3 τ − c0 √ |S|3|A|K + H 5|S|3|A| (τ − c0)2 ∧ (τ − c0) ) , where a ∧ 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.

heading: 4 Bounded constraint violation case
text: Without prior knowledge of a strictly safe policy π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 [17].
Different from traditional optimistic dual analysis methods in [10], we introduce an additive pessimistic term k at each episode k in the original optimization problem (1), i.e.,
max π
V π1 (µ; r, P ) s.t. V π 1 (µ; c, P ) + k ≤ τ. (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,
Lk(π, λ) := V π1 (µ; r, P ) + λ (τ − k − V π1 (µ; c, P )) , for which, given any Lagrange multiplier λ, we can always solve for the optimizer maxπ Lk(π, λ) by dynamic programming.
With the introduction of the additive term k, the dual variable (denoted by λ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., r̃kh(s, a) := r̂ k h(s, a) + β(nk(s, a, h)) +H|S|β(nk(s, a, h)), ∀(s, a, h) ∈ S ×A× [H],
c̃kh(s, a) := ĉ k h(s, a)− β(nk(s, a, h))−H|S|β(nk(s, a, h)), ∀(s, a, h) ∈ S ×A× [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 k.
We employ truncated value functions due to the additional uncertainties from transitions, i.e., V̂ π1 (µ; r̃ k, P̂ k) := min{H,V π1 (µ; r̃k, P̂ k)}, V̂ π1 (µ; c̃k, P̂ k) := max{0, V π1 (µ; c̃k, P̂ k)}. (12)
For the policy update of the primal variable (denoted by πk), we can apply standard dynamic programming by viewing r̃kh(s, a)− λ k ηk (c̃kh(s, a)− τ) as the reward function. Specifically, we apply backward induction to solve for the optimal policy:
Qkh(s, a) = r̃ k h(s, a)−
λk ηk (c̃kh(s, a)− τ) + ∑ s′∈S P̂ kh (s ′|s, a) max a′ Qkh+1(s ′, a′), ∀h ∈ [H]
with QkH+1(s, a) = 0,∀(s, a) ∈ S × A. Then, πkh ∈ arg maxaQkh(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 k := 5H2 √ |S|3|A|(log kδ′ + 1)/ √ k log kδ′ , δ
′ = δ/(16|S|2|A|H), the scaling parameter ηk := (τ − c0)H √ k in the primal policy update, and, for convenience, a step size of 1 for the dual update. Theorem 4.1 (Regret and constraint violation bounds for OptPess-PrimalDual). Fix any δ ∈ (0, 1). Then,
RegOPPD(K; r) = Õ ( H3 τ − c0 √ |S|3|A|K + H 5|S|3|A| (τ − c0)2 ) ,
RegOPPD(K; c) = O ( C ′′(H − τ) +H2 √ |S|3|A|C ′′ ) = O(1),
where C ′′ = O(H 4|S|3|A| (τ−c0)2 log H4|S|3|A| (τ−c0)2δ′ ) is a coefficient independent of K. Theorem 4.1 shows that it is possible to achieve an Õ( √ K) reward regret, while only allowing bounded constraint violation with arbitrarily high probability. Detailed proofs are presented in Section 5.2 and Appendix C.
Algorithm 2: OptPess-PrimalDual Input: K, δ, c0, τ ; Initialization: N1h(s, a) = 0, ∀(s, a, h) ∈ S ×A× [H], λ1 = 0; for k = 1, 2, . . . ,K do
Set k = 5H2 √ |S|3|A|(log kδ′ + 1)/ √ k log kδ′ , δ
′ = δ/(16|S|2|A|H), ηk = (τ − c0)H √ k;
Update empirical model (i.e., P̂ k, r̂k, ĉk) as in Equations (3)-(5); Update r̃k, c̃k as in Equation (11); (Policy Update) πk ∈ arg maxπ∈Π V̂ π1 (µ; r̃k, P̂ k)− λ k
ηk
( V̂ π1 (µ; c̃ k, P̂ k)− τ ) ;
(Dual Update) λk+1 = ( λk + V̂ π k
1 (µ; c̃ k, P̂ k) + k − τ ) + ;
Execute πk and collect a trajectory (Skh, A k h, R k h, C k h), ∀h ∈ [H]; Update counters Nk+1h (S k h, A k h), ∀h ∈ [H];
end

heading: 5 Regret and constraint violation analysis
text: 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− δ).

heading: 5.1 Analysis of OptPess-LP (Algorithm 1)
text: Constraint violation analysis The zero constraint violation of OptPess-LP follows from the following property of the pessimistic policy set Πk: Lemma 5.1. With probability at least (1− δ), for any k ∈ [K] and policy π ∈ Πk, V π1 (µ; c, P ) ≤ τ .
Regret of reward analysis When the parameters c, P are not well estimated, there may not exist any policy π such that V π1 (µ; c
k, P̂ k) ≤ τ . Hence, as defined in (9), Πk is a singleton set {π0}, and accordingly π0 is executed, even though π0 is not safe for (ck, P̂ k). It subsequently takes several episodes of exploration using π0 until it becomes strictly safe for (ck, P̂ k). At that time, policies close enough to π0, of which there are infinitely many, are also safe for (ck, P̂ k), and so |Πk| = +∞. At this point the learning algorithm can proceed to enhance reward while maintaining safety with respect to (ck, P̂ k).
To analyze the algorithm, we decompose the reward regret as follows:
RegOPLP(K; r) = K∑ k=1 1(|Πk| = 1) ( V π ∗ 1 (µ; r, P )− V π 0 1 (µ; r, P ) )
+ K∑ k=1 1(|Πk| > 1) ( V π ∗ 1 (µ; r, P )− V π k 1 (µ; r̄ k, P̂ k) ) +
K∑ k=1 1(|Πk| > 1) ( V π k 1 (µ; r̄ k, P̂ k)− V π k 1 (µ; r, P ) ) . (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 π0:
Lemma 5.2. With probability at least (1 − δ), ∑K k=1 1(|Πk| = 1) ≤ C ′, where C ′ = Õ(H4|S|3|A|/((τ − c0)2 ∧ (τ − c0))).
Turning to the second term on the RHS of (13), we first note that π∗ may not be in Πk. To ensure that the term V π ∗
1 (µ; r, P )− V π k 1 (µ; r̄ k, P̂ k) is nevertheless non-positive even when π∗ 6∈ Πk, we set αr
to the large value shown in (7). This increases r̄k, and hence also V π k
1 (µ; r̄ k, P̂ k). In addition, we
show that there is a policy π̂k that attains the same reward as the (non-Markov) probabilistic mixed policy, π̃k := Bγkπ
∗+(1−Bγk)π0, whereBγk is a Bernoulli distributed random variable with mean γk for γk ∈ [0, 1]. γk will be chosen as the largest coefficient such that V π̃ k 1 (µ; c k, P̂ k) ≤ τ . This latter policy in turn has a larger reward than π0 since it is a mixture with π∗, yielding the following: Lemma 5.3. With probability at least (1− δ),
K∑ k=1 1(|Πk| > 1) ( V π ∗ 1 (µ; r, P )− V π k 1 (µ; r̄ k, P̂ k) ) ≤ 0.
Finally, concerning the third term on the RHS of (13), akin to the closed-loop identifiability property [6, 19], while P̂ k may not converge to P , the difference in the rewards V π k
1 (µ; r̄ k, P̂ k)−V πk1 (µ; r, P )
grows sublinearly in k since the same policy πk is used in both values: Lemma 5.4. With probability at least (1− δ), K∑ k=1 1(|Πk| > 1) ( V π k 1 (µ; r̄ k, P̂ k)− V π k 1 (µ; r, P ) ) = Õ ( H3 τ − c0 √ |S|3|A|K + H 5|S|3|A| τ − c0 ) .
Combining Lemmas 5.2, 5.3, and 5.4 yields Theorem 3.1.

heading: 5.2 Analysis of OptPess-PrimalDual (Algorithm 2)
text: 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 k = 5H2 √ |S|3|A|(log kδ′ + 1)/ √ k log kδ′ , where δ
′ = δ/(16|S|2|A|H). The existence of a feasible solution to (10) can be guaranteed if k ≤ τ−c0. LetC ′′ be the smallest value such that ∀k ≥ C ′′, k ≤ (τ − c0)/2. Then the perturbed optimization problem (10) has at least one feasible solution for any k ≥ C ′′. By simple calculation, one can verify that C ′′ = O(H
4|S|3|A| (τ−c0)2 log H4|S|3|A| (τ−c0)2δ′ ).
Notice that k is a function not depending on K, and so is the coefficient C ′′.
Constraint violation analysis The bounded constraint violation of OptPess-PrimalDual is established as follows. We first decompose the constraint violation as
RegOPPD(K; c) = ( K∑ k=1 ( V π k 1 (µ; c, P )− V̂ π k 1 (µ; c̃ k, P̂ k) ) + K∑ k=1 ( V̂ π k 1 (µ; c̃ k, P̂ k)− τ )) +
≤ ( K∑ k=1 ( V π k 1 (µ; c, P )− V̂ π k 1 (µ; c̃ k, P̂ k) ) + λK+1 − K∑ k=1 k ) + . (14)
The first summation term and λK+1 in (14) can be bounded as follows: Lemma 5.5. Recall δ′ = δ/(16|S|2|A|H), with probability at least (1− δ),
K∑ k=1 ( V π k 1 (µ; c, P )− V̂ π k 1 (µ; c̃ k, P̂ k) ) ≤ 8H2 √ |S|3|A|K log K δ′ +O(PolyLog(K)).
Lemma 5.6. For any k ≥ C ′′, with probability at least (1− δ),
λk ≤ 1 ζ ln 11ν2max 3ρ2 + C ′′(H − τ) + C′′∑ u=1 u +H + 4(H2 + 2k + η kH) τ − c0 ,
where ρ = (τ − c0)/4, νmax = H , ζ = ρ/(ν2max + νmaxρ/3).
To guarantee bounded violation, we ensure that ∑K k=1 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− δ), the violation is bounded as
RegOPPD(K; c) = O ( C ′′H +H2 √ |S|3|A|C ′′ log (C ′′/δ′) ) .
Regret of reward analysis For episode k with k ≥ C ′′, let π k,∗ be the optimal policy for (10), which is well-defined by the definition of C ′′. We decompose the reward regret as
RegOPPD(K; r) = C′′∑ k=1 ( V π ∗ 1 (µ; r, P )− V π k 1 (µ; r, P ) )
(15)
+ K∑ k=C′′ ( V π ∗ 1 (µ; r, P )− V π k,∗ 1 (µ; r, P ) ) + K∑ k=C′′ ( V π k,∗ 1 (µ; r, P )− V̂ π k,∗ 1 (µ; r̃ k, P̂ k) ) +
K∑ k=C′′ ( V̂ π k,∗ 1 (µ; r̃ k, P̂ k)− V̂ π k 1 (µ; r̃ k, P̂ k) ) + K∑ k=C′′ ( V̂ π k 1 (µ; r̃ k, P̂ k)− V π k 1 (µ; r, P ) ) .
We upper bound each term on the RHS of (15). Since V π1 (µ; r, P ) ∈ [0, H] for any policy π, the first term is upper bounded by HC ′′. The second and third terms can be bounded by the following two lemmas: Lemma 5.7. With probability at least (1− δ),
K∑ k=C′′ ( V π ∗ 1 (µ; r, P )− V π k,∗ 1 (µ; r, P ) ) ≤ K∑ k=C′′ kH τ − c0 = Õ ( H3 τ − c0 √ |S|3|A|K ) .
Lemma 5.8. With probability at least (1− δ), ∑K k=C′′ ( V π k,∗ 1 (µ; r, P )− V̂ π k,∗ 1 (µ; r̃ k, P̂ k) ) ≤ 0.
The pivotal step is to leverage optimism of πk to further decompose the fourth term on the RHS of (15), and utilize the projected dual update to transfer it into the form of λk(λk − λk+1). The following lemmas provide high probability bounds for the remaining two terms on the RHS of (15): Lemma 5.9. With probability at least (1− δ),
K∑ k=C′′ ( V̂ π k,∗ 1 (µ; r̃ k, P̂ k)− V̂ π k 1 (µ; r̃ k, P̂ k) ) = Õ ( H τ − c0 √ K ) .
Lemma 5.10. With probability at least (1− δ), K∑
k=C′′
( V̂ π k
1 (µ; r̃ k, P̂ k)− V π
k 1 (µ; r, P ) ) = Õ ( H2 √ |S|3|A|K +H4|S|3|A| ) .
Applying Lemmas 5.7, 5.8, 5.9, and 5.10 yields Theorem 4.1.

heading: 6 Concluding remarks
text: 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 Õ( √ K) regret of reward. The algorithms employ, respectively, a pessimistically safe policy set Πk or an additional pessimistic term k into the safety constraint. The first algorithm, OptPess-LP, guarantees zero violation with high probability by solving a linear programming with Θ(|S||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.

heading: Acknowledgement
text: 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 DEEE0009031. 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.

Review summaries:
This paper presents two novel reinforcement learning algorithms for CMDPS, one which has no constraint violations with high probability, but requires a known safe policy, and another which bounds the probability of constraint regret, but only requires the existence of a safe policy. The first algorithm picks pessimistically safe policies if they obtain a high enough value, but chooses a best reward policy otherwise. The second algorithm iteratively chooses the highest value policy subject to a dynamically tightening constraint. Both algorithms have a higher regret than previous approaches, but are provably safe  in the respective metrics

The paper studies the problem of safety in learning, within the framework of tabular episodic Constrained MDPs (unknown transition, rewards and costs). The authors propose a method based on the principle of optimistic pessimism in face of uncertainty that achieves a regret of $\mathcal{O}(\sqrt{K})$ for the rewards ($K$ being the number of episodes) that is comparable to the existing methods. The main advantage of the proposed approach is that it achieves a smaller constraint violation: particularly zero constraint violation when an initial safe policy is given, and bounded constraint violation when no safe policy is known (but it is known that one such policy exists). The known policy case is based on the LP formulation of solving the pessimistic CMDP, and the unknown policy case uses a  primal-dual approach.

This paper studies safety in reinforcement learning. It guarantees a zero constraint violation happens with high probability when strictly safe policy is known. The algorithm employs optimism in the face of uncertainty and achieves a regret of O(\sqrt{K}). For the case with no known strictly safe policy, it is proven that  the constraint violation is bounded.