Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPs
Authors: Tao Liu
Ruida Zhou
Dileep Kalathil
Panganamala Kumar
Chao Tian
Venue: NeurIPS 2021 Poster (2021)
Keywords: Safe Reinforcement Learning
Constrained Markov Decision Process

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.

Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPs
Tao Liu" Texas A&M University tliu@tamu. edu
Ruida Zhou" Texas A&M University ruida@tamu, edu
Dileep Kalathil Texas A&M University dileep kalathil@tamm edu
P. Kumar
Chao Tian
Texas A&M University prkStamu.edi edu
Texas A&M University
chao. thaoo.ian@tae tian@tamu, edu
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 achieve a reward regret of Ō(VK) while allowing an Ō(VK) constraint violation K episodes. A critical question that arises whether it is possible keep the constraint violation even smaller. We show that when 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 Ō(VK). The algorithm which does employs the principle of optimistic pessimism in the face uncertainty to achieve safe exploration. When strictly safe policy is known, though one is known to exist, then is possible restrict the system to bounded constraint violation with arbitrarily high probability. This shown to be realized by primal-dual algorithm with optimistic primal estimate and a pessimistic dual update.
Introduction
Reinforcement learning (RL) addresses the problem of learning optimal control policy that maximizes the expected cumulative reward while interacting with an unknown environment [25). Standard RL algorithms typically focus only maximizing single objective. However, in many real-world applications, the control policy learned by an RL algorithm has to additionally satisfy stringent safety constraints
99 4 For example, autonomous vehicle may need 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) 12) formalism, where seeks to maximize a reward while satisfying safety constraints, is a standard approach for modeling the necessary safety criteria of control problem via constraints on cumulative costs.
Several Dolicy-gradient based algorithms have been proposed to solve CMDPs. Lagrangian-bar based methods 26 24 21 16] formulate the CMDP problem as saddle-poing problem and optimize via primal-dual methods, while Constrained Policy Optimization [1] 29] (inspired by the trust region policy optimization (23] computes new dual variables from scratch each update maintain constraints during learning. Although these algorithms provide ways to learn an optimal policy, performance guarantees about reward regret, safety violation sample complexity are rare.
One class of RI. algorithms for which performance guarantees are available follow the principle of Optimism in the Face of Uncertainty (OFU) 10 and provide an Ó ((vK) K) guarantee
TTe first two authors contributed equally.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Table 1: Regret and constraint violation comparisons for algorithms on episodic CMDPs
Algorithm
Regre
Constraint violation
OPDOP
Õ( S
Ó(H² S
A
OpICMDP
O (
Ō(1² S| A
OpICMDP-bone
10 2
(SHAAA)))
Ō(H² VIS [
OpiDual-CMMP
0(H² (
Ó(H² VSS A
OpIPrimalDual-CMD
10
Ó(H² (UH'VSAAAIK Ö(T+)
Ó(H² V A
C-UCRL
30
0
OptPess-LP
/SPAAK 0 H
OptPess-Prinee PrimalDual
SMATK) O(1)
for the reward regret, where is the number of episodes. However, these algorithms also have (VKK) safety violations. Such significant violation of the safety constraints during learning may be unacceptable in many safety-critical real-world applications such the control of autonomous vehicles or power systems. These applications demand a class of safe RI. algorithss that can provably guarantee safety during learning. With this goal in mind, aim answer the following open theoretical question in this paper:
Can we design safe RL algorithms that can achieve an Ō(vK) regret with respect to the performance objective, while guaranteeing zero 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 [7]. 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 ((v 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 safety constraint violation during learning with high probability and utilizes the linear programming (LP) approach for solving a CMDP problem. The algorithm achieves reward regret of Ö م v Is (AA with respect to the performance objective, where H is the number of steps per episode, T is the given constraint on safety violation, c is the known safety constraint value of strictly safe policy n and |S] and [A|] are the number of states and actions respectively.
Ha
2. OptPess-P OptPess-PrimalDuu 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 EppiPess-PrimalDuuse programming and its attendant complexity and exploits the primal-dual approach for solving a CMDP problem. The proposed approach improves the computational tractability, while
algorithm avoids linear
TThis table presented for K 2 (oly H), with polynomial terms independent of K omitted. Effooi 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 | to bound M.
"Zheng al. (30) assumes known transition kernel and analyzes regret in the long- term average setting.
'The detailed constraint violation is O (C" + VVS log(C" f8)). which is independent of
K. Here, 8' ((A)) and C" O
8 (5-20)0
log *1AS

---

ensuring a bounded safety constraint violation during learning and reward regret of Ō H V ( with respect the objective.
Compared with the other methods listed Table though the proposed algorithms have an additional H/(T - d or VISl/(T= cd) factor in the regret bounds, they are able to reduce the constraint violation to zero 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 optimal control policy that satisfies safety constraints has been studied both in the RL. setting and the multi-armed bandits setring.
Constrained RL: Several policy-gradient algorithms have seen success in practice 26
16 I 29]. Also of interest are works which utilize Gaussian processes to model the transition probabilities and value functions 27
Several algorithms with provable guarantees are closely related to our work. Zheng et al. 30 considered the constrained RL problem in infinite horizon setting with unknown reward and cost functions. The approach is similar to the UCRL2 algorithm [33 and achieves a sub-linear reward regret Ö 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 finite horizon, attaining both a reward regret and a constraint violation of Ó V A). Ding et al. [8] studied an episodic setting with linear function approximation (suitable for large state space cases), and proposed algorithms that can achieve OdH VK) K) for both the regret and the constraint violation (where d is the dimension of the feature mapping). The regret analysis in g can be easily extended to the tabular case, yielding Ó(H3 ()
Constrained Multi-Armed Bandits: Multi-armed bandit problems are special cases of MDPs, with both the number of states 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 conservative bandits 228 14 I1, requires the eumulative 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 B 20
[8].
2 Problem formulation
finite-horizon constrained non-stationary MDP model defined as tuple (S.A, H, C,,,,,TTPp) where S is the state space. A is the action space, H is the number of steps in each episode, S x A + [0, 1] is the unknown reward function of interest, e 8:5 x A + [o. 1] is the unknown safety cost function used to model the constraint violation, constant used to define the safety constraint, and μ is the known initial distribution of the state. P.(.(s..) a) E Ag Vs E S, Va A, where As is the [i)-dimenso probability simplex, and (s (islss,, a) is the unknown transition probability that the next state when action a is taken for state s step h.
(0, H) is the given
Some further notation necessary to define the problem. A (randomized Markov) policy is defined by a map S x [H] + A with ny (a|s) being the probability of taking action in state at time step h. With S, and A, representing the state and the action at time ł respectively, let
H Σ 9SS, AD]S, = VsE
V (s: P) = EP
denote the expected cumulative value with respect to function S x A + R, under P for policy и over a time interval [h, h 1,..., H.. With slightly abuse of notation, we use (" P) to denote (V" P)].
3

---

In the formulation below there are total of K episodes with H steps each. Each episode & [K] begins with an initial probability distribution μ for Sy. Then, the agent determines randomized Markov policy x² 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 at state Sk. the agent receives a noisy reward and cost of (5) (2, A = rS(,) A + (S), Af: and
(S A ca A + (S Af; c), respectively.
Assumption 2.1 Gub-Gaassiann noise). For all h [H] k
[K], the reward and cost noise iee, F 0,
random variables are conditionally independent zero-mean ( I exp(X2/4), AA E R. Here Fk is the a-algebra generated by the random variables up to episode
Let x² denote the optimal policy of the following CMDP model:
max VT (H
s.t. P)
(1)
policy ı is said be strictly safe if (T
Assumption 2.2. There exists a strictly safe policy x² with VP (u;c, P) d <T.
There are two important cases of the safe learning problem.
Zero constraint violation case: The agent has prior knowledge of a strictly safe policy x² and its safety cost value e² := Vi² (pc: P). The agent wishes to attain a sublinear (in K) cumulative regret,
Reg( K;r) = Σ (VT (Jrr, - VT" (IST,P)).
E(V
(2)
k=1
while incurring zero constraint violation with at least specified high probability (1 6), i.e.,
P (vT" (p.c, T, Vk (K]) 2 1 1-1
The agent knows that there exists a strictly safe policy with known safety cost value c., 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,
Bounded constraint violation case:
Reg(K;c)= = Σ (w:c,))))
(where (a)+ = max(a, 0})
satisfies supk
< +o0 with at least a specified high probability (1 - 5).
Remarks. For the zero constraint violation case, the assumption of knowing cº can be relaxed, as shown in Appendix E.
Zero constraint violation case
We start by considering the constraint violation case. On one hand, 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 we begin by forming empirical estimates of the transition probabilities, the reward function, and the cost function from step of all previous episodes:
(8(18,,) = EN 1(SK 8, A a, Sk =s)
(3)
(s, v1
(s = Ei 1(S = 8, A = (s, a) (h,
for r,C,
(4)

---

where a V := max(a, b), and
(s, 88 a) = # of visits to state-action pair (s, a) at step episodes [1,2...., 1). (5)
Next we fix some E (0, 1) and form a common (for notational simplicity) confidence radius 3% (s, a) for the transition probabilities, the rewards, and the costs,
a)) == V as Z, where == (og[
At each episode k. we define the optimistically biased reward estimate as a)) a) = ( a) a, Vlx.a.)))
(6)
where the scaling factor is
4H + HHH 0r = 1+11+1884+
c-
To guarantee safe exploration, define the pessimistically biased safety cost estimate episode k as
(s, a) == (1+ (1+)))))))) V(s,a,h) Ex
(8)
The policy we execute at episode k is chosen from "pessimistically safe" policy set II, defined as if VT (u:c², ph) 2 (T c
{TT} VT pi)
I
(9)
otherwise.
We simply use the strictly safe policy T" until VIT² (4;c*, PR) < (T c))2, which is sufficient condition to guarantee that the set { (TT & Pk) S r is non-empty. Within this set, we choose the optimistically best reward earning policy Th which can be solved by linear programming with @ (H] decision variables and constraints 10 The resulting Optimistic Pessimism-based Linear Programming (OptPess-I.P)) algorithm is presented below:
Algorithm 1: OptPess-LP
Input: K, 5, x0 co T; Initialization: (s. = 0, v(s,ahh) E x [H]:
for k = 1,2, K do
Update empirical model (i.e., pk ph et) as in Equations 53-5)
Update ph c and IIl as in Equations (6)
Calculate n* E arg max V (μ: Fk P*);
Execute = and collect trajectory (Sk, A R Ch), wh E [M];
Update counters N (S), A)), vh [H];
end
Theorem 3.1 (Regret and constraint violation bounds for OptPess-LP). any 8 E (0, 1). With probability at least (1 - 8), OptPess-LP has constraint violation with
3
H HS1SPLAA
) where bb: min(a,b) b).
Reg
orL (K;r) Ô r o
8 BBAKK
(--
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 proof' presented in Appendix B.
5

---

Bounded constraint violation case
Without prior knowledge of a strictly safe policy x9, may not be able guarantec constraint violation with high probability. However, by relaxing the requirement to bounded (in K) safety constraint violation, primal-dual approach. is inspired by the design the pessimistic term in constrained bandits [17]
incorporate more exploration and design more efficient algorithm by
Different from traditional optimistic dual analysis methods in [10], we introduce an additive pes-
simistic term ex at each episode & in the original optimization problem ( i.e.
max
VT P) s.t. Ví (4G C, EN S.
(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,
(=)
e (us P)),
for which, given any Lagrange multiplier A. we can always solve for the optimizer max, ( A) by dynamic programming.
With the introduction of the additive term és. the dual variable (denoted by X²) 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.
(s. a) := (s, a) ((nx(s, a, h)) (m,, V(s,a,h) S Ax [H], (s. = c| (s. ((mx(s, a, h)) (m, V(s,a,h) E x Ax [H.. (1I)
Note that contrast to the zero constraint violation case, we optimistically estimate the safety cost function, with the pessimism only governed by cg-
We employ truncated value functions due to the additional uncertainties from transitions, i.e., VIT (1; ph) == min VT" (,; ph)), (1; phh) max VT (n; 2h, ph)). (12)
For the policy update of the primal variable (denoted by Th), we can apply standard dynamic programming by viewing (s, a) backward induction to solve for the optimal policy:
x (eh (s, a) 7) as the reward function. Specifically, apply
(x) = (s, a)
(c) -) + Σ
Pe (6'1s,)) max (b, 4h [
e'ES
with (s. 0, ((s S A. Then, T/ E arg max. (s,s),, which is computationally efficient (as efficient as -ercie-traientt-ooo based algorithms in the tabular case).
The resulting Optimistic Pessimism-based Puilal-Dual (OptPess-PrimalDDnn PrimalDual) algorithm is shown 5 + 1)/ l log $. 8' = 5/ the scaling parameter 1/* -T VT in the primal policy update, and, for convenience, a step size of for the dual update.
in Algorithm 2 It chooses c : 5H2 /
Theorem 4.1 (Regret and constraint violation bounds for OptPess-PrimalDual), Fix any & E (0, 1). Then,
OPPD Reg OPD (K;r) (P:)(K:))))))) (K;r)= (0 - SS H2 OPPD (Kic) c) O Hf
H3
+ H11S|$AA|
(T 20)2
Reg OPD
O(1)
where C" O
HO''' 2 log
H' H'ISPAA (7-69)88))
is a coefficient independent of K.
Theorem 4.1 shows that it is possible to achieve an Ō(VK) 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, c², . (s.
Initialization: (,, a) = 0, v(s,a,h) E x x [M], X 0; for k = 1,2..... K do
Set c = 5
& + +1/ l log $.. = 5/ (/16
11t (T
Update empirical model (i.c., pk, fk e as in Equations 3
Update i* ah as in Equation 11:
(Policy Update) Th E arg max (w; Fh ph #/ (w; - -T):
(Dual Update) X (* + V/ (u; (e,,PP)) + Ex - -T)
Execute x* and collect trajectory (Sh Al. Ri, ch., wh [H]:
Update counters N (S). A vh [H];
end
5 Regret and constraint violation analysis
We sketch the key steps the proofs of Theorems a.d Full details are relegated 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 - 6).
5.1 Analysis of OptPess-LP (Algorithm I
Constraint violation analysis The zero constraint violation of OptPess-LPP follows from the fol- lowing property of the pessimistic policy set I
Lemma 5.1. With probability at least (1 for any l E [K] and policy π E II, (p c) ST.
Regret of reward analysis When the parameters P are not well estimated, there may exist any policy such that V (":g", pbk < т. Hence, defined in (9). II is singleton set (="), and accordingly o is executed, even though nO is not safe for (c* P*). It subsequently takes several episodes of exploration using T0 until it becomes strictly safe for (ch pp)). At that time, policies close enough to T", of which there are infinitely many, are also safe for (c* P*), and so |11*| = +o0. At this point the learning algorithm can proceed enhance reward while maintaining safety with respect (c* ph))
To analyze the algorithm, we decompose the reward regret as follows:
Reg OPLP (K;r)
1(IT") 1) (VT (ngr, P) - (1,,,
(1rr, P))
K 1(1141 > 1) (vi (por, - Vi (m: 5h phi)
K I(111>> 1) (VT* (1; pKy- Vi* (Isr,
(13)
k=1
To bound the first term the right-hand side (RHS) of (33, have the following lemma which gives an upper bound on the number episodes for exploration by policy z0:
Lemma 5.2. With probability at least (1 - 6). Σk 1(I1=) = 1) < C', where C" = ((ALSS 2 A (T-
Turning to the second term on the RHS of 13 we first note that n" may not be in 1 To ensure that the term Vi"" (u P) ViT (k fk) is nevertheless non-positive even when T" 11th we set a,
7

---

to the large value shown in This increases f* and hence also Vi" (e: In addition, show that there is policy n that attains the same reward as the (non-Markov) probabilistic mixed policy, 7* By ग. + (1-B,, )=², where Byy a Bermoulli distributed random variable with mean The for Y [0, 1]. will be chosen as the largest coefficient such that V (ur pk) < т. This latter policy in turn has larger reward than x since it is mixture with σ², yielding the following:
B,,,
Lemma 5.3. With probability at least (1 8).
K
1(111M > (vT (1sT, VI" (c; (M, ph)) S O.
Finally, concerning the third term on the RHS of 13 akin to the closed-loop identifiability property
19 while fh may not converge to P. the difference in the rewards V/=" (4; Fh pP) - Vi" (u;r, P)
grows sublinearly in since the same policy x² is used in both values:
Lemma 5.4. With probability at least (1 - 8).
- H
( > 1) (VT* (n; Ph. - v (u:r, P)) = T- d VIS
7
Combining Lemmas 5.2 5.3 and 5.4 yields Theorem 3.1
5.2 Analysis of OptPess- PrinaalDalll (Algorithm
2
In this section, we outline the steps in the proof of Theorem 4.1 by analyzing regret and constraint violation of OptPess- Pess--Prialluall respectively.
Recall 6 = 5 / |S|| (log &
x + +1// log & where 8' = [((]]S(((A))) The existence of a
feasible solution to (10) can guaranteed if if --
co Let C" the smallest value such that vk 2
C" Ek < (T e 2. Then the perturbed optimization problem (0) has at least one feasible solution
for any k 2 C". By simple calculation, one can verify that C" = O [*1SSLAA log H "AA),
(7-
(r-c"y8
Notice that Eg is function not depending K, and is the coefficient C".
Constraint violation analysis The bounded constraint violation of OptPess-PrimalDDus PrimalDual is estab- lished as follows. We first decompose the constraint violation as
Reg
OPPD (K:c)
VF" (u:c, Du= (H; Ju:ce,Phy + Σ
(iT (1: (mt
K
(VT' (u:c, VT (w; ph) + X K+1
(14)
k=
The first summation term and K+1 in 14p can be bounded as follows:
Lemma 5.5. Recall 8' = 5/ A H), with probability at least (1 -),
K
(cc (vT' (m.e, V p!)) s 8H² V SSSAIK log & + ((PolyLog((K))
Lemma 5.6. For any k 2 C", with probubility least (1 -8),
e"
2
Eu + H 4(H² + + + (H)
* < In
max
+ CH
Σ
3p2
==1
where p (T - -c0) Vmax
H, Ç = p/(2 + MmaxP/3).
8

---

To guarantee bounded violation, we ensure that Σ
in 14 can cancel the dominant terms in the
two lemmas above. According to Lemmas 5.5 and 5.6 is bounded as
with probability least (1 6). the violation
Reg OPPD = ( H 1S/ A C" log (8")8))
Regret of reward analysis For episode l with k 2 C", let क be the optimal policy for (10) which is well-defined by the definition of C", We decompose the reward regret as
OPPD (K;r) = Σ VT (NST,)) VT (y:r,P) P))
Reg
(15)
K
K
+
VT" () -Vr''
(M,T, + Σ
(v (1 ()
km C"
1m
(y7ih (uapk,Pt) ViF' (1r ph))
Σ (VT" (u: phy Vp" (usr, R=
We upper bound each term on the RHS of 15 Since V (w: r, P) E [0, for any policy x, the first term is upper bounded by HC", The second and third tenms can be bounded by the following two lemmas:
Lemma 5.7. With probability at least - -6),
K
K
E
H
VT (uGr, P) VT (ugr, PI) S Σ
=
( V
C=
k=C"
Lemma 5.8. With probability least (1- Ek=
(VT'
(p5r, P)
ViTiiin (c3 pk, p.))
The pivotal step is to leverage optimism of αb to further decompose the fourth term the RHS of (15), and utilize the projected dual update to transfer into the form of >* *+1)). The following lemmas provide high probability bounds for the remaining two terms on the RHS of
Lemma 5.9. With probability at least (1 - 8).
Σ (VT"' (u; pkky ViT (urt,,pt) =ō e
H
C
Lemma 5.10. With probability at least (1 -0),
K
(VT' (15 pok) VT (HiT, Ô (11² / B 11
k=
Applying Lemmas 5.7
5.8
5.9 and 5.10 yields Theorem 4.1
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 Ó / K) regret of reward. The algorithms employ, respectively, a pessimistically safe policy set R or an additional pessimistic term 6g into the safety constraint. The first algorithm, OptPess-LP,, guarantees zero violation with high probability by solving linear programming with ((S]|AA) H)) decision variables, while the second algorithm, OptPess-PrimalDuus selicy-gradient-ee algorithms in the tabular case, but violates constraints during initial episodes. A possible future direction for exploration the application the above OPFU principle model-free algorithms.
is as efficient as

---

Acknowledgement
R. Kumar's work is partially supported by US National Science Foundation under CMMII-208625,, HDR Tripods CCF-1934904 US Office of Naval Research under N00014-21-1-23855 US ARO under W91 I911NF212006;; and U.S. Department of Energy's '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 the authors and should not be interpreted representing the views 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- 1850266 and NSF-CARREE-DPCN-225555
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. NeurlPS 2019, 2019.
[4] D. Amodei, C. Olah, J. Steinhardt, P. Christiano, J. Schulman, and D. Mané. Concrete problems in ai safety. arXiv preprint arXiv: 06566666660666. 2016.
[5] Berkenkamp, M. Turchetta, A. Schoellig, and A. Krause. Safe model-based reinforcement learning with stability guarantees. In Proceedings of the 3 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, Orosz, 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] 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.
[9] G. Dulac-Arnold, D. Mankowitz, and T. Hester. Challenges of real-world reinforcement learning. arXiv preprint
2019.
[10] Y. Efroni, S. Mannor, and M. Pirotta. Exploration-exploitatio in constrained mdps. arXiv preprint arXiv:2003.02 021899 2020.
[11] E. Garcelon, M. Ghavamzadeh, A. Lazaric, and M. Pirotta. Improved algorithms for conservative exploration in bandits. Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 3962-3969, 2020.
[12] J. Garcia and F. Fernández. A comprehensive survey on safe reinforcement learning. Journal of Machine Learning Research, 16(1):1437-1480, 2015.
[13] T. Jaksch, R. Ortner, and P. Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(4), 2010.
[14] A. Kazerouni, M. Ghavamzadeh, Y. Abbasi- Abbasi-Yadkori, and B. Van Roy. Conservative contextual linear bandits. In Proceedings of the 31 International Conference on Neural Information Processing Systems, pages 3913-3922, 2017.
10

---

[15] 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. IEFE, 2018.
[16] Q. Liang, F. Que, and E. Modiano. Accelerated primal-dual policy optimization for safe reinforcement learning. arXiv preprint arXiv: 2018.
[17] X. Liu, B. Li, Shi, and L.. Ying. An efficient pessimisticooptimmssic algorithm for constrained linear bandits. arXiv preprint arXiv:2102.052:: 2021.
[18] A. Moradipari, Amani, M. Alizadeh, and Thrampoulidis. Safe linear thompson sampling with side information. arXiv preprint arXiv:1911.02155 2019.
[19] P. R. Kumar and A. Becker. A new family of optimal adaptive controllers for Markov chains. IFFE Transactions on Automatic Control, 27(1):137-146, 1982.
[20] A. Pacchiano, M. Ghavamzadeh, P. Bartlett, and H. Jiang. Stochastic bandits with linear constraints. In International Conference Artificial Intelligence and Statistics, pages 2827- 2835. PMLR, 2021.
[21] S. Paternain, M. Calvo- Calvo-Fullana, L. F. Chamon, and A. Ribeiro. Safe policies for reinforcement learning via primal-dual methods. arXiv preprint arXiv:1911.09100 2019.
[22] S. Qiu, X. Wei, Z. Yang, Ye, and Z. Wang. Upper confidence primal-dual reinforcement learning for emdp with adversarial loss, arXiv e-prints, pages arXiv-2003, 2020.
[23] 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.
[24] A. Stooke, Achiam, and Abbeel. Responsive safety in reinforcement learning by pid lagrangian methods. In International Conference Machine Learning, pages 9133-9143. PMLR, 2020.
[25] R. S. Sutton and A. G. Barto. Reinforcement learning: An introduction. MIT press, 2018.
[26] C. Tessler, D. J. Mankowitz, and S. Mannor. Reward constrained policy optimization. In International Conference on Learning Representations, 2018.
[27] A. Wachi, 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
[28] Y. Wu, R. Shariff, T. Lattimore, and C. Szepesvári. Conservative bandits. In International Conference Machine Learning, pages 1264-1262. PMLR, 2016.
[29] T.-Y. Yang, J. Rosca, K. Narasimhan, and P. J. Ramadge. Projection-based constrained policy optimization. In International Conference on Learning Representations, 2019.
[30] L. Zheng and L. Ratifff. Constrained upper confidence reinforcement learning. In Learning for Dynamics and Control, pages PMLR, 2020.


Reviews:
[{"review_id": "xfzMFtBHCQ9", "reviewer": "Reviewer_cdW5", "summary": "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", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\nBroadly speaking the paper is well written.\n\nThe knowledge of safe policies are reasonable assumptions, and the two distinct cases seem natural. The relevance and novelty is clear.\n\nThe description of both procedures are clear and reproducible.\n\nThe theoretical aspects of the paper are thorough. \n\n\nWeaknesses:\nThe paper consistently refers to notation before it is introduced, making it difficult to read. While it is hard to summarise the work in the introduction without a formal problem definition, some of the more important terms, like regret, should be explained informally.\n\nThe problem formulation needs to more clearly state what parts of the CMDP are known vs unknown to the agent at start.\n\nThe two approaches lack intuition. With the appendix, it's clear why certain bounds were chosen, but motivation that ties to the problem would help the reader's understanding.\n\nFinally, whilst I appreciate the focus of this paper is theory, it is presenting two algorithms, so I think an empirical evaluation would greatly strengthen the contribution. This could be done by moving some of the results in Section 5 to the appendix.\n\n\nSpecific comments/questions\n\n* Is assumption 2.1 common? Further intuition on its need, and how strong it is, should be given\n\n* In line 129, I don't follow the use of sup. Shouldn't it be lim k->infty?\n\n* point (iii) in line 132 feels a bit irrelevant in the context of this paper\n\n===UPDATE===\nAfter reading the other reviews and the authors' thorough responses, I think the paper should probably be accepted, assuming some of the insights and clarifications provided in the responses are added to the paper.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No discussion on societal impact. Some limitations are mentioned.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "PjFB9G1d1BR", "reviewer": "Reviewer_uBAh", "summary": "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Originality:\n\nThe proposed methods are inspired by safe exploration in constrained bandits but the extension and application to the constrained RL problem are novel and valuable. The authors do a good job of citing the related literature and differentiating their approach from the others. \n\n### Quality: \n\nThe submission is technically sound with all the claims being supported sufficiently. All the assumptions and limitations are stated clearly. \n\n### Clarity:\n\nThe paper is clear and easy to follow. Although I believe some aspects of the paper can be improved wrt clarity, particularly:\n-  All the analysis depends on how the high probability good event is defined (Appendix A). I think the authors can do a better job in explaining the details in this section. For instance, when the author’s define $\\mathcal{E}^{gen}$ the Hoeffding’s, Berstein and Union bound are all applied in a single step and it is not obvious how the $\\frac{1}{4(1+|S|)}$ term shows up in the denominator for $\\delta’$. I think it will be useful for the readers if the intermediate steps are also provided.\n- The results depend heavily on Lemma D.5, the proof for which is referred to another related work. However, the referenced work uses different notation and setting that makes it difficult to draw the connections. I think it will be useful if the proofs for Lemma D.5 (and even D.4) can be presented in the work itself for the sake of completeness.\n- Another point that can be highlighted a bit further is how the threshold for the first condition in Eq 9 ($\\frac{\\tau+c^0}{2}$) is derived. Some discussion on that will add to the clarity of the approach. \n\n\n\n### Significance:\n\nThe paper is technically sound and novel with strong results which I believe will be useful for developing further safe/bounded-constraint algorithms in this setting. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "2fh6wo3E4Mv", "reviewer": "Reviewer_5BQY", "summary": "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well-written and the problem formulation and the contributions are clearly stated. However, numerical experiments that corroborate the theoretical guarantees of the paper are missing in the current version and I highly recommend to add some in the revision.\n\nQuestions:\n\n1. My first question is whether the authors can extend their analysis to the case with focus on deterministic policy? \n2. My second question is whether either of the regret bounds and the constraint violation bound are tight in terms of c^0? \n3. Could the authors comment  on an example of safety-critical system where it is reasonable to assume the knowledge of a safe policy?\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I believe this work does not have any potential negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the problem of learning episodic CMDPs, which provides improved theoretical results comparing to previous works. This work is technically sound and novel with strong results. All the reviewers have reached a consensus on the acceptance of this work. We suggest that the authors further polish their paper to prepare a camera-ready version based on the reviewers’ comments.
Decision: Accept (Poster)