DOPE: Doubly Optimistic and Pessimistic Exploration for Safe Reinforcement Learning
Authors: Archana Bura
Aria Hasanzadezonuzy
Dileep Kalathil
Srinivas Shakkottai
Jean-Francois Chamberland
Venue: NeurIPS 2022 Accept (2022)
Keywords: Constrained MDP
Safe Exploration
Constrained Reinforcement Learning

Abstract: Safe reinforcement learning is extremely challenging--not only must the agent explore an unknown environment, it must do so while ensuring no safety constraint violations. We formulate this safe  reinforcement learning (RL) problem using the framework of a finite-horizon Constrained Markov Decision Process (CMDP) with an unknown transition probability function, where we model the safety requirements as constraints on the expected cumulative costs that must be satisfied during all episodes of learning.  We propose a model-based safe RL algorithm that we call Doubly Optimistic and Pessimistic Exploration (DOPE), and show that it achieves an objective regret $\tilde{O}(|\mathcal{S}|\sqrt{|\mathcal{A}| K})$ without violating the safety constraints during learning, where  $|\mathcal{S}|$ is the number of states, $|\mathcal{A}|$ is the number of actions, and $K$ is the number of learning episodes.  Our key idea is to combine a reward bonus for exploration (optimism) with a conservative constraint (pessimism), in addition to the standard optimistic model-based exploration.  DOPE is not only able to improve the objective regret bound, but also shows a significant empirical performance improvement as compared to earlier optimism-pessimism approaches. 

DOPE: Doubly Optimistic and Pessimistic Exploration for Safe Reinforcement Learning
Archana Bura, Aria HasanzadeZonuzz, Dileep Kalathil, Srinivas Shakkottai, lean-Francois Chamberland Department of Electrical and Computer Engineering, Texas A&M University carchanabura, azonuzy, dileep.
dillep..alathhl kalathil, sshakkot, chmbrlnd)@tamd edu
Abstract
Safe reinforcement learning is extremely challenging-nol not only must the agent explore unknown environment, it must do while ensuring safety constraint violations. We formulate this safe reinforcement learning (RL) problem using the framework of Enite-horizon Constrained Markov Decision Process (CMDP) with an unknown transition probability function, where we model the safety require- ments constraints on the expected cumulative costs that must be satisfied during all episodes of learning. We propose a model-based safe RL algorithm that we call Doubly Optimistic and Pessimistic Exploration (DOPE), and show that it achieves objective regret Ö [S] [SSV (A( without violating the safety constraints during learning, where |S] is the number of states, |A| is the number of actions, and K is the number of learning episodes. Our key idea is to combine a reward bonus for exploration (optimism) with a conservative constraint (pessimism). in addition to the standard optimistic model-based exploration. DOPE not only able improve the objective regret bound, but also shows significant empirical performance improvement as compared to earlier aptimism-pessiming approaches.
Introduction
Constrained Markov Decision Processes (CMDPs) impose restrictions that pertain resource or safety constraints of the system. For example, the average radiated power in wireless communication system must be restricted due to user health and battery lifetime considerations or the frequency of braking or accelerating in an autonomous vehicle must be kept bounded to ensure passenger comfort. Since these systems have complex dynamics, a constrained reinforcement learning (CRL) approach is attractive for determining an optimal control policy. But how do we ensure that safety or resource availability constraints are not violated while learning such an optimal control policy?
Our goal is to develop a framework for safe exploration without constraint violation (with high probability) for solving CMDP problems where the model unknown. While there has been much work on RL for both the MDP and the CMDP setting, ensuring safe exploration in the CRL setting has received less attention. The problem is challenging, since do not allow constraint violation either during learning or deployment, while ensuring a low regret in terms of the optimal objective. Our aim to explore model-based approach in an episodic setting under which the model (the transition kernel of the CMDP) is empirically determined as samples from the system are gathered.
There has been much recent interest in model-based RL approaches solving a constrained MDP, the most relevant of which we have summarized in Table The setup is of a finite horizon episodic CMDP, with state space of size |S), an action space of size [A] and horizon of length H. Regret is measured over the first K episodes of the algorithm. Both the attained objective and constraint satisfaction computed in an expected sense for given policy. Allowing constraint violations during learning means that the algorithm suffers both an objective regret and a constraint regret.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Table 1: Comparison of safe RL algorithms for CMDPs. The algorithms are: OptCMDP, OpICMDP. Bonus (18), AlwaysSafe (36) and OptPessLP (28). This table is presented for K 2 poly([S), |A], H), with polynomial terms independent of K omitted. Expected regret results are in high probabilityy.
ALGORITHM
MODEL
REWARD
CONSTRAINT PESSIMISM
OBJECTIVE REGRET
CONSTRAINT
EMPIRICAL
OFTIMISM
OPTIMISM
REGRET
PERF
OPTCMDP OPTCMDP-I B ALNAYSSARE
X
(AHKK) Ó(S V (AHRR
OISSI (A V(SMAR
X
HEURISTIC
UNKNOWN
X
OPTPESS-LP
K
V
DOPE
V Ō
H3 U-G
(SIVAR
0
Examples of algorithms following this method are OpICMDP, OpICMDP-Bonus [18] The algorithms use different ways of incentivizing exploration to obtain samples to build up an empirical system model. OptCMDP uses the idea of optimism in the face of uncertainty from the model perspective and solves an extended linear program to find the best model (highest reward) under the samples gathered thus far. OpICMDP- Bonus uses different approach of adding bonus to the reward term to incentivize exploration of acatenaction pairs that have fewer samples, which we consider as a form of optimism from the reward perspective. While the objective regret of both these algorithms is Ō(vK), the constraint regret too is of the same order, since constraints may be violated during learning.
An algorithm that begins with no knowledge of the model will have exploration steps during learning that might violate constraints in expectation. Hence, safe RI. approaches assume the availability of an inexpert baseline policy that does not violate the constraints, but is insufficient to explore the entire state action space. So it cannot be simply applied until high-accuracy model is obtained. A heuristic approach entitled AlwaysSafe (36) assumes a factored CMDP that allows the easy generation of a safe baseline policy. It then combines the optimism with respect to the model of OpiCMDP with heuristically chosen hardening of constraints. This guarantees no constraint violations, but does not have regret guarantee with respect to the objective. Its empirical performance is variable and its use is limited to factored CMDP problems.
The OptPessL. P algorithm (28) formalizes the idea of coupling optimism and pessimism by starting with OpICMDPBonus that has an optimistic reward, and systematically applying decreasing levels of pessimism with respect to the constraint violations. The approach is successful in ensuring the twin goals of ((VK) objective regret, while ensuring constraint violations. However, the authors do not present any empirical performance evaluation results. When we implemented OptPessLP, we found that the performance is singularly bad in that linear regret persists for a large number of samples, and the tapering off to Ō(VK) regret behavior does not appear to happen quickly. The problem with this algorithm is that is so pessimistic with regard to constraints that it heavily disincentivizes exploration and ends up choosing the base policy for long sequences.
The issue upon which algorithm performance depends is the choice of how to combine optimism and pessimism to obtain both order optimal and empirically good objective regret performance, while ensuring no constraint violations happen. Our insight that optimism with respect to the model is key enabler of exploration, and can be coupled with the addition of optimism with respect to the reward. This double dose of optimism- with respect to model and reward- could-ooldd ensure that pessimistic hardening of constraints does not excessively retard exploration. Following this insight, we develop DOPE, a doubly optimistic and pessimistic exploration approach. We are able to show that DOPE not only attains Ö(vK) objective regret behavior with zero constraint regret with high probability, it also reduces the objective regret bound over OptPessLP by a factor of VJST. We conduct performance analysis simulations under representative CMDP problems and show that DOPE easily outperforms all the earlier approaches. Thus, the idea of double optimism is not only valuable from the order optimal algorithm design perspective, it also shows good empirical regret performance, indicating the feasibility of utilizing the methodology in real-world systems. The code for the experiments in this paper is located at: https://githun wwom/archaaaabug
Related Work: Constrained RL: Constrained Markov Decision Processes (CMDP) has been an ac-
tive area of research (2), with applications in domains such as power systems [39 25 communication
networks 3 38 and robotics [17 In [9, the author proposed an actor-critic RL algorithm for

---

learning the asymptotically optimal policy for an infinite horizon average cost CMDP when the model unknown. This approach is also utilized in function approximation settings with asymptotic local
convergence guarantees [8] 12 40] Policy gradient algorithms for CMDPs have also been developed 27
However, none these works address the problem of safe exploration to provide guarantees on the constraint violations during learning.
47 35
16
Safe Multi-Armed Bandits: The problem of safe exploration in linear bandits with stage-wise safety constraint is studied in 4 [ B3 Linear bandits with more general constraints have also been studied [34] 29). These works do not consider the more challenging RL setting which involves an underlying dynamical system with unknown model.
Safe Online Convex Optimization: Online convex optimization 20 has been studied with stochas-
tic constraints 45 10] and adversarial constraints [32 46 26]. These allow constraint violation
during learning and characterize the cumulative amount of violation. A safe Frank-Wolf algorithm for
convex optimization with unknown linear stochastic constraints has been studied in [4 However, these too do not consider the RL setting with an unknown model.
Exploration in Constrained RL: There has been much work in this area with constraint violations during learning, including the work discussed in the introduction [8]. These include [37 19] 23]
which derive bounds either on the objective and constraint regret or on the sample complexity of learning an e-optimal policy. Other works safe RL include 43J 12 where model-free approach is considered, and [S], that pertains to offline RL. These are complementary to our model-based approach. The problem of learning the optimal policy of a CMDP without violating the constraints was also studied in [48] However, they assume that the model is known and only the cost functions unknown, whereas we address more difficult problem with unknown model and cost functions.
Notations:
For any integer M. [M] denotes the set {L...., M.. For any two real numbers a, b. V b= == ma bj. For any given set X. A(X) denotes the probability simplex over the set X,, and | denotes the cardinality of the set X.
2 Preliminaries and Problem Formulation
2.1 Constrained Markov Decision Process
We address the safe exploration problem using the framework of episodic Constrained Markov Decision Process (CMDP) (2). We consider CMDP, denoted as M AS, A, r, c, P. H, C) with
r r= (r()) c (cx) H 1. P = (P)) 1, where S is the state space, A is the action space, H is the episode length, Th : S x A R. is the objective cost function at time step h E [H) ch S x A RR is the constraint cost function at time step h E [H], Pr. is the transition probability function with (s (s.a) a) representing the probability of transitioning to state s' when action is taken at state s at time h. In the RL context, the transition matrix P is also called the model of the CMDP. Finally, C' is scalar that specifies the safety constraint terms of the maximum permissible value for the expected cumulative constraint cost. We consider the setting where |S] and |.A| are finite. Also, without loss of generality, we assume that costs r and e are bounded in [0. 1].
A non-stationary randomized policy π = (mT)) TA S + A(A) specifies the control action to be taken each time step h E [H]. In particular, TA a) denotes the probability of taking action a when the state is at time step h. For an arbitrary cost function 1 [H] x S x A + R, the value function of a policy æ corresponding to time step h E [H] given a state s E S is defined as
Vr. (s: P) = E Σ
4 (sr. ass = s].
(1)
T=h
where a, IT, (S), Sr+1 (-1s ).). Since we are mainly interested in the value of a policy starting from h = 1, we simply denote V (s; P) as V Ps: For the rest of the paper, we will assume that the initial state is $1 is fixed. So, we will simply denote (TT : P) as (P). when it is clear from the context. This standard assumption
[& 15 can be made without loss of generality.
The CMDP (planning) problem with a known model P can then be stated as follows: min VT(P) s.t.
C.
We say that policy æ a safe policy if V. (P'(P) S SCC, ie., if the expected cumulative constraint cost corresponding the policy is less than the maximum permissible value C. The set of safe policies.
3

---

denoted as Sate. is defined as Sa = { (P) I Cj. Without loss of generality, we assume that the CMDP problem ( is feasible, ie.. Iaee non-empty. Let 'T" be the optimal safe policy, which is the solution of
The CMDP (planning) problem is significantly different from the standard Markov Decision Process (MDP) (planning) problem [2]. Firstly, there may not exist an optimal deterministic policy for CMDP, whereas the existence of deterministic optimal policy is well known for a standard MDP. Secondly, there does not exist Bellman optimality principle or Bellman equation for CMDP. So, the standard dynamic programming solution approaches which rely on the Bellman equation cannot be directly applied to solve the CMDP problem.
There two standard upproaches for solving the CMDP problem, namely the Lagrangian approach and the linear programming (LP) approach. Both approaches exploit the zero duality gap property of the CMDP problem [2] to find the optimal policy. In this work, we will use the I.P approach, consistent with model optimism. Details of solving 2 using the LP approach are in Appendix A
2.2 Reinforcement Learning with Safe Exploration
The goal of the reinforcement learning with safe exploration is to solve 2 but without the knowledge of the model P priori. Hence, the learning algorithm has perform exploration by employing different policies to learn P. However, we also want the exploration for learning to have a safety guarantee, i.e, the policies employed during learning should belong to the set of safe policies safe Since Mafe itself is defined based on the unknown P. the learning algorithm will not know Iafe a priori. This makes the safe exploration problem extremely challenging.
We consider a model-based RL algorithm that interacts with the environment in an episodic manner. Let Ty& = (fA,,)) be the policy employed by the algorithm in episode k. At each time step h [H] in an episode k. the algorithm observes state $j,k, selects action Æy.* ~ Th. ( :), and incurs the costs r' (s (b.,)) and Cy (S,,A; (n,x). The next state 81++1, is realized according to the probability vector p( dg.k). - As stated before, for simplicity, we assume that the initial state is fixed for each episode k E [K]
{1,..., K). i.e., $1,1 81. We also assume that the maximum permissible cost C for any exploration policy is known and it is specified as part of the learning problem.
The performance of the RL algorithm is measured using the metric of safe objective regret. The safe objective regret is defined exactly as the standard regret of an RL algorithm for exploration in MDPs [4 6), but with an additional constraint that the exploration polices should belong to the safe set Mafe. Formally, the safe objective regret R K)) after K learning episodes is defined as
K
R(K) = Σ (V V. (P)), E Iaae Vk E [K].
(3)
k=1
Since Iaaee is unknown, clearly it is not possible to employ a safe policy without making any additional assumptions. We overcome this obvious limitation by assuming that the algorithm has access to safe baseline policy Ta such that T. E I We formalize this assumption as follows.
Assumption (Safe baseline policy). The algorithm knows a safe baseline policy na such that V.*(P) = C.. where C. < C. The value Co is also known to the algorithm.
Remark 2. Knowing a safe policy my is necessary for solving the safe RL problem because we require the constraint to always be satisfied. A similar assumption has been used in the case of safe
exploration in linear bandits 4 24 33 as well in earlier work on safe RI. [36 28
3 Algorithm and Performance Guarantee
DOPE builds on the optimism in the face of uncertainty (OFU) style exploration algorithms for RL [4 using such optimism, both in terms of the model, as well as to provide a reward bonus for under-explored state-actions. However, a naive OFU-style algorithm may lead to selecting exploration policies that are not in the safe set Is So we modify the selection of exploratory policy by incorporating pessimism in the face of uncertainty (PFU) on the constraints, making DOPÉ doubly optimistic and pessimistic in exploration.
DOPE operates in episodes, each of length H. Define the filtration Fs as the sigma algebra generated by the observations until the end of episode k E [K], i.c., Fx (Sh, an, h E [H), k [k]). Let

---

m,,b(s,a) = EK w= 1f = s,a = a be the number of times the pair (s, was observed time step h until the beginning of episode k. Similarly, define ni, s') Σx 1
8. On.k" a, S = =s'). At the beginning of each episode k, DOPE estimates the model as (s ks, a, (.msaaa))))...ss....
1). Similar to OFU-style algorithms, we construct confidence set Pk around Px as Pk= = (ea))Ssx a), where
Pa(5, a) (P' P (8, a) (s S ah, vh 1111 E ES}.
(4)
4Var (n
14L
(s - (8, V1 (()),(s,,a
(5)
where T. log( 2SAHK), and Var( (s a)) (s's a) Pr, a)). Using the empirical Bernstein inequality, we can show that the true model P is an element of Pk for any k E [K] with probability at least 1 1- 26 (see Appendix C).
Similarly, at the beginning of each episode k; DOPE estimates the unknown objective and constraint costs as (8, a) = Ees (s
(s, Ets (s,
In keeping with OFU, construct confidence sets R2 and Cs around fx and é respectively,
R₂ {f: (F)(s, (8, S ( a). vh, E [M] x 8 A
Cx {ē: a) Cn a)l S (s, a), s. H S A},
(6)
(s. = / (n (v).
where = 2lgg /),, and F = (Fn) 2 (cn) Using Hoeffding inequality, we can
show that the true costs belong R2 and Cj for any & E [ with probability at least 1 8 (see Appendix C). We define M₁ = Pk n Rx n C2 to be the total confidence ball.
It is tempting to use the standard OFU approach for selecting the exploration polices since this approach is known to provide sharp regret guarantees for exploration problems in RL. The standard OFU approach will find the optimistic model La and optimistic policy I&. where
( Pk)
arg min st ('.(P"r''.'""
V (P'), s.t. V (P') S.
The OFU problem (7) is feasible since the true model M is an element of Mr (with high probability). In particular, (ma. P) and (TT", P) are feasible solutions of (7). Moreover, (7) can be solved efficiently using an extended linear programming approach, as described in Appendix The policy H ensures exploration while satisfying the constraint V. (Px)
(Px) S C. However, this naive OFU approach overlooks the important issue that T may not be safe policy with respect to the true model P. More
precisely, it is possible to have Ve (P) > Ć even though Vo (P,) S C. So, the standard OFU
approach alone will not give safe exploration strategy.
In order to ensure that the exploration policy employed at any episode is safe, we add pessimistic penalty to the empirical constraint cost get the pessimistic constraint cost function C₁ (s, (s, a) + B/,, (s, + H (s,
(8) where (s, = =Eves (s, a'). Since ( a) is D(1///n.d a)), (s, a) pairs that are less observed have a higher penalty, disincentivizing their exploration. However. such pessimistic penalty may prevent the exploration that is necessary learn the optimal policy. To overcome this issue, we also modify the empirical objective cost function by subtracting a term to incentivize exploration, to obtain optimistic objective cost function
3H
2² C-C,"
(s, a) a) C C- (h,
B C- (s,
Since ( a) is /01/V/m, mn (s, (s, a) pairs that are less observed will have lowered cost to incentivize their exploration.
We select the policy n for episode by solving the Doubly Optimistic-Pessinee (DOP) problem: (TT: Pb) = arg min V (P') s.t. V (P') < C. x x',P
(10)
Notice that DOPE doubly optimistic by considering both the optimistic objective cost function in and the optimistic model Ps from the confidence set P; in (10), while being pessimistic on the
5

---

constraint in (T). Later, in Lemma 18 the appendix, we prove that (TT Pt)) is indeed an optimistic
solution. This is in contrast with [28]. where the optimism solely limited to the objective cost. We
will show that our approach carefully balances double optimism and pessimism, yielding a regret minimizing learning algorithm with episodic safe exploration guarantees.
We note that the DOP problem (10) may not be feasible, especially in the first few episodes of learning. This is because, BR,,, (s, a) and (5,, may be large during the initial phase of learning
so that there may not be policy T' and model P" Pp that can satisfy the constraint V (P*) S Ć. We overcome this issue by employing a safe baseline policy nh (as defined in Assumption I in the first K, episodes, a value provided by Proposition | Since T6 is safe by definition, DOPE ensures safety during the first Ko episodes. We will later show that the DOP problem (TO) will have a feasible solution after the first K. episodes (see Proposition 4). For any episode k Ko, DOPE employs
policy Tg. which is the solution of (TO). We will also show that Ti from (TO) (once it becomes feasible) will indeed be safe policy (see Proposition 5). We present DOPE formally in Algorithm T
Algorithm 1 Doubly Optimistic and Pessimistic Exploration (DOPE)
1: Input: d E (0, 1) C, Th, Cb, C, K,
2: Initialization: n,,,,s,, (s, a) mn,,kss a, 5') = 0 Vs S,a E A, ( [H].
3: for episodes A = .,..., KK do
4: Compute the estimates Pk. fR. én and the confidence set Mr according (4) ()) and (6).
5: i < Ko then
6: Select the exploration policy TH Thh
7: else
8:
Select the exploration policy गą according to (TOp
9:
end if'
for h ..,,...,fHi H. do
11:
Observe state kt.k, select action ah,k ( :), incur the cost (s ar.k) and Ch (Sh,k, k,,,), and observe next state S1+1,6 ~ Pn (-(-/sh, ah.x)
12:
Update the counts: nA (S ap + (S (b.A) ) + 1, ns, ( On, SM41,) & T (8 &n 1,8) +
13:
end for
14:
end for
We now present our main result, which shows that the DOPE algorithm achieves Ō(VK) regret without violating the safety constraints during learning, with high probability.
Theorem 3. Fix any 8 (0,1). 1). Consider the DOPE algorithm with Ko as specified in Proposition
4 Let (T k E [K] be the sequence of policies generated by the DOPE algorithm. Then, with probability at least 1 56, TT& E IIsate for all is E [K]. Moreover, with probability at least 1 58, the regret of the DOPE algoritium satisfies
SH3
R(K) S 0
(C-C,) VAK).
4 Analysis
We now provide the technical analysis of DOPE, concluding with the proof outline of Theorem 3
4.1 Preliminaries
For an arbitrary policy n' and transition probability function P', define ox (P') and nh (P') as
H
H
&x (P')
HE Σ (s..
(P' F'
E
an. Pr,F Fa-il.
(1I)
Then, is straightforward to show that (see
23
in the Appendix) (P' = (P) 24
Tho (P) + (P"), Fg (Pr) = V (P") C- the (P')
:- ot' (P"). The analysis utilizes this decomposition of V (P') and V (P"), and the properties of c (P") and De (P'). Under the good
event G defined in Lemma 12 can show, V. (P') (P')-m²
nr (P') S V. (('(") Vg (P') (P").

---

4.2 Feasibility of the OP Problem
Even though (Tb, P) feasible solution to the original CMDP problem 22, may not be a feasible for the DOP problem (10) in the initial phase of learning. To see this, note that V (P) =
V.ah (P) = Cb. we will have Va ( 2f (P) E (P) 'Tk (P) under the good event, and solution for (10) if 2m (P) + (P)
(P) + Mi (P) + & (P), and since Ve (P) 2 V
(P) (c).)). So, (To, P) is a feasible Cp). This sufficient condition may not be satisfied for initial episodes. However, since & (P) and nig (P) are decreasing in h: if (mb. P) becomes feasible solution for (TO) at episode K, then it will remain feasible for all episodes k: 2 W. Also, since A. and Bh,, decrease with k; one can expect that (TO) becomes feasible after some number of episodes. We use these intuitions, along with some technical lemmas to show the following result.
Proposition& 4. Under the DOPE algoritlum, with a probability greater that 1 1 56, (To, P) is feasible solution for the DOP problem (TO) for all k 2 Ko, where K,, Ö 52 AI 4.3 Safety Exploration Guarantee
(C-C,))
We show that the DOPE algorithm provides a safe exploration guarantee, i.e., T E saaee for all k e [K] with high probability, where TT the exploration policy employed by DOPE in episode k. This is achieved by the carefully designed pessimistic constraint of the DOP problem (TO.
For any k S Kor since Te
Tu, and it is safe by Assumption For k > Ko,
10) is feasible
according to Proposition 4 Since (TT, Pk) is the solution of (10), we have V (Px)
V2. (Pt) +
ME m (Px) + & (Px) S C. This implies that ViTh (Px) + 7% (Px)
E 2t (Px). We have that
V. (Px) < V (Px) + me (Ps) under the good event, and hence, the above equation implies that v. (Px) < C- -pp) ie., Ty. satisfies tighter constraint with respect to the model Ps. However, is not obvious that the policy Te will be safe with respect to the true model P because ViT* (P)( may be larger than V (Px) due to the change from Pe to P.
We, however, show that V. (P) cannot be larger than V.T* (Pk) by more than 6 2 (Pt), i.e., VTL(() V.TH (Px) S T (Px). This will then yield that V=*((P) S (P&) + cx (Px) S C, which is the true safety constraint. The key idea is in the design of the pessimistic cost function (..-.) such that
its pessimistic effect will balance the change in the value function (from V (P&) to V. (P) due to the optimistic selection of the model Px. We formally state the safety guarantee of DOPE below.
Proposition 5. Let {Tk. K E [K]] be the sequence of policies generated by the DOPE algorithm. Then TT is safe vk E [K], i.e. V.T (P) S for all l E [K), with probability greater than 1 - 56.
4.4 Regret Analysis
The regret analysis for most OFU style RL algorithms follows the standard approach of decomposing the regret into two terms as R₂ = V V." (P) = (V.** (P) V (Px)) + (V.** (Ps)
V."" (P)), where R2 denotes the regret in episode k. The first term is the difference between value functions of the selected policy Ta with respect to the true model P and optimistic model Ps. Bounding this term is the key technical analysis part of most of the OFU algorithms for the unconstrained MDP 21 [3) and also the CMDP [18.. In the standard OFU style analysis for the unconstrained problem, since P E Py for all k. it can be easily observed that (TT", P)) is feasible solution for the OFU problem 7 for all t [K]. Moreover, since (Tk Pk) is the optimal solution in tth episode, we get V.T (Px) S V. (P). So, the second term will be non- non-positive, and hence can be dropped from the regret analysis. However, in our setting, the second term can be positive since (Tr", P)) may not be a feasible solution of the DOP problem (TPp due the pessimistic constraint. This necessitates a different approach for bounding the regret. Existing work (28) only considers optimism in the objective cost, and hence their proof closely follows that of OptCMDP- Bonus algorithm in [18] with pessimistic constraints. In analyzing the regret of DOPF, we need to handle the optimism in objective cost as well as the model regret terms, along with the pessimistic constraints. This make the analysis particularly challenging. The full proof is detailed in the appendix.
5 Experiments
We now evaluate DOPE via experiments. We have two relevant metries, namely, (i) objective regret, defined in (3) that measures the optimality gap of the algorithm, and (ii) constraint regret, defined
7

---

as Zk= max c (P) C}. where is the output of the algorithm in question at episode A. This measures the safety gap of the algorithm. Our candidate algorithms are (i) OptCMDP, (ii) A AlwaysSafe, (iii) OptPessI.P and (iv) DOPE, all described in the introduction. OptCMDP is expected to show constraint violations, while the other three should show zero constraint regret. We consider two environments here, with a third environment presented in the appendix. AlwaysSafe can directly be used only with a factored CMDP, and only applies to the first environment presented. We simulate both variants of this algorithm, referred to AlwaysSafe тт and AlwaysSafe Ta, respectively (36).
We first consider a CMDP where the safety relavant features of the model can be separated, as shown in [36]. This CMDP has states {1. 2, 3} arranged in circle, and 2 actions {1.2] in each state, to move right or stay put, respectively. The transitions move the agent to its right state with probability 1, if action 1 is taken. If action 2 is taken, it remains in the same state with probability 1. Action 1 does not incur any objective cost or constraint cost. Action incurs an objective cost equals to the state number, and constraint cost of 1. We choose episode length H = 6, and constraint as C = 3. The structure of this CMDP allows AlwaysSafe to extract a safe baseline policy from it.
Factored CMDP:
Media Streaming CMDP: Our second environment represents media streaming to a device from a wireless base station, which provides high and low service rates at different costs. These service rates have independent Bernoulli distributions, with parameters μl 0.9, and μll 0.1, where μl corresponds to the fast service. Packets received at the device are stored in a media buffer and played out according to a Bernoulli process with parameter y. We denote the number of incoming packets into the buffer as An, and the number of packets leaving the buffer Bū. The media buffer length is the state and evolves as 8 = min max((, 8h + A B,); N). where N 20 the maximum buffer length. The action space is 21, where action corresponds to using the fast service. The objective cost is r(s, a) = 1ss = =O}, while the constraint cost is c(s, a) = Iaa = 1), i... we desire to minimize the outage cost, while limiting the usage of fast service. We consider episode length H H 10, and constraint C' c= 2
Experiment Setup: OptCMDP and OptPessLP algorithms have not been implemented earlier. For accurate comparison, we simulate all the algorithms true to their original formulations of cost functions and confidence intervals. Our experiments are carried out for 20 random runs, and averaged to obtain the regret plots. For DOPE, we choose Kg to be as specified in Proposition [4] Full details on the algorithm parameters and experiment settings are provided in Appendix E
Both OptPessLLP and DOPE require baseline policies. We select the baseline policies as the optimal solutions of the given CMDP with a constraint C. = 0.2C. We choose the same baseline policies for both the algorithms. This choice is to showcase the efficacy of DOPE, despite starting with a conservative baseline policy.
Baseline Policies:
Results for Factored CMDP: Fig. I(a) shows the objective regret of the algorithms in this environ- ment. OptCMDP has a good objective regret performance as expected, but shows constraint violations. AlwasySafe fails to achieve Ó O(VK) regret in the episodes shown for both variants, although the T, variant has smaller regret as compared to the Ty variant. OptPessLLP takes a long time to attain VK behavior, which means that is chooses the baseline policy for extended period, and shows high empirical regret. This suggests that reward optimism of OptPessI. _P is insufficient to balance the pessimism in the constraint. DOPE not only achieves the desired Ö( regret, but also does so in fewer episodes compared to the other two algorithms. Furthermore, it has low empirical regret. Fig. shows that the constraint violation regret is zero for all the episodes of learning for all the safe algorithms, while OptCMDP shows a large constraint violation regret.
Results for Media Streaming CMDP: Fig 2(a) compares the objective regret across algorithms. The value of DOPE over OptPessLP is more apparent here. After linear growth phase, the objective regret of DOPE changes to a square-root scaling. OptPessLP has not explored sufficiently at this point, and hence suffers high linear regret. Finally, OpICMDP also has square-root regret scaling, but is fastest, since it is not constrained by safe exploration. violation for these algorithms. As expected, DOPE and OptPessL. do not violate the constraint, while the OptCMDP algorithm significantly violates the constraints during learning.
comppars the regret in constraint
We compare the objective regret of DOPE under different baseline policies in Fig and 2 We see that less conservative (but safe) baselines result in lower regret, but the difference is not excessive, implying that the exact baseline policy chosen is not crucial.
Effect of Baseline Policy:
8

---

104
DetPhi P
1.3
Objoctive Regrez
AbroyySafe
D0Re Amantates OptONe
3.01
Donsrrant
0.5
Episode
le5
Episode
Episode
(a) Objective Regret
(b) Constraint Regret
(c) DOPE Objective Regret, vary-
ing C.
Figure 1: Illustrating the Objective Regret and Constraint Regret for a Factored CMDP environment.
Rogres
DDrE
OptPnes-L
Constrantt Ragner
Objective Reprat
1.0
7.0
Done Optihe--1P
0.5
0.5
0.6 Episode
Episode
Episode
(a) Objective Regret
(b) Constraint Regret
(c) DOPE Objective Regret, vary-
ing C.
Figure 2: Illustrating the Objective Regret and Constraint Regret for the Media Streaming Environ- ment.
Summary: DOPE has two valuable properties: (i) Faster rate of shift to v K behavior, since the linear regret phase where it applies the baseline policy is relatively short, and (it) Õ(VK) K) regret with respect to optimal, which together mean that the empirical regret lower than other approaches.
Our goal is to find an RL algorithm with no constraint violation with high probability in the tabular setting. Since safe exploration is basic problem, follow the usual approach in the
Limitations:
literature first establishing the fundamental theory results for the tabular setting [21] 14 6 We
also note that most of the existing work exploration in safe RL is in the tabular setting 18 37 28
In our future work, we plan to employ the DOPE approach in a function approximation setting.
Conclusion
considered the safe exploration problem reinforcement learning, wherein safety constraint must be satisfied during learning and evaluation. Earlier approaches to constrained RL have proposed optimism on the model, optimism on reward, and pessimism on constraints as means modulating exploration, but none have shown order optimal regret, no safety violation, and good empirical performance simultancously. We started with the conjecture that double optimism combined with pessimism is the key attaining the ideal balance for fast and safe exploration, and design DOPE that carefully combines these elements. We showed that DOPE not only attains order-optimal Ö(V K) regret without violating safety constraints, but also reduces the best known regret bound by factor of S.. Furthermore, it has significantly better empirical performance than existing approaches. We thus make for adoption of the approach for real world use cases and extension large scale RL problems using function approximation.
7 Acknowledgement
This work was supported in part by the grants NSF-CAREER- 2045783, NSF ECCS 2038963, and ARO W91 19-1-961- Any opinions, findings, and conclusions or recommendations ex- pressed in this material are those of the authors and do not necessarily reflect the views of the sponsoring agencies.

---

References
[1] Joshua Achiam, David Held, Aviv Tamar, and Picter Abbeel. Constrained Policy Optimization.
In International Conference Machine Learning, pages 22 22-31. PMLR, 2017.
[2] Eitan Altman. Constrained Markov decision processes, volume 7. CRC Press, 1999.
[3] Eitan Altman. Applications of Markov decision processes communication networks. In Handbook of Markov decision processes, pages 489-536. Springer, 2002.
[4] Sanae Amani, Mahnoosh Alizadeh, and Christos Thrampoulidis, Linear stochastic bandits under safety constraints. Advances in Neural Information Processing Systems, 32:9256-9266, 2019.
[5] Sanae Amani and Lin F. Yang. Doubly pessimistic algorithms for strictly safe off-policy optimization. In 2022 56th Annual Conference on Information Sciences and Systems (CISS), pages 113-118, 2022.
[6] Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforcement learning. In International Conference Machine Learning, pages 263-272.
PMLR, 2017.
[7] Dimitri P Bertsekas et al. Dynamic programming and optimal control: Vol. 1. Athena scientific Belmont, 2000.
[8] Shalabh Bhatnagar and Lakshmanan. An online actor-critic algorithm with function ap- proximation for constrained Markov decision processes. Journal of Optimization Theory and Applications, 153())6688770) 2012.
[9] Vivek S Borkar. An actor-critic algorithm for constrained Markov decision processes. Systems control letters, 54(3):207-233, 2005.
[10] Sapana Chaudhary and Dileep Kalathil. Safe online convex optimization with unknown linear safety constraints. In Proceedings of the AAAI Conference Artificial Intelligence, volume 36, pages 6175-6182, 2022.
[11] Yin-Lam Chow, Marco Pavone, Brian M Sadler, and Stefano Carpin. Trading safety versus performance: Rapid deployment of robotic swarms with robust performance constraints. Journal of Dynamic Systems, Measurement, and Control, 137(3):03 1005, 2015.
[12] Yinlam Chow, Mohammad Ghavamzadeh, Lucas Janson, and Marco Pavone. Risk-constrained reinforcement learning with percentile risk criteria. The Journal of Machine Learning Research, 18(1):6070-61 6120, 2017.
[13] Christoph Dann and Emma Brunskill. Sample complexity of episodic fixed-horizon reinforce- ment learning. Advances in Neural Information Processing Systems, 28:2816 8 28-2266, 2015.
[14] Christoph Dann, Tor Lattimore, and Emma Brunskill. Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning. arXiv preprint arXiv 077110 2017.
[15] Dongsheng Ding, Xiaohan Wei, Zhuoran Yang, Zhaoran Wang, and Mihailo Jovanovic. Provably efficient safe exploration via primal-dual policy optimization. International Conference on Artificial Intelligence and Statistics, pages 3304-3312. PMLR, 2021.
[16] Dongsheng Ding, Kaiqing Zhang, Tamer Basar, and Mihailo Jovanovic. Natural policy gradient primal-dual method for constrained Markov decision processes, Advances in Neural Information Processing Systems, 33:8378 8390, 2020.
[17] Xu Chu Ding, Alessandro Pinto, and Amit Surana. Strategic planning under uncertainties via constrained Markov decision processes. In 2013 IEEE International Conference on Robotics and Automation, pages 4568-4575. IEEE, 2013.
[18] Yonathan Efroni, Shie Mannor, and Matteo Pirotta. Exploration-exploitation in constrained MDPs. arXiv preprint axX1v:2003.02189, 2020.
10

---

[19] Aria HasanzadeZonuzz, Archana Bura, Dileep Kalathil, and Srinivas Shakkottai. Learning with safety constraints: Sample complexity of reinforcement learning for constrained MDPs. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 7667-7674, 2021.
[20] Elad Hazan. Introduction to online convex optimization. Foundations and Trends in Optimiza- fion, 2(3-4):157-325, 2016.
[21] Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(4), 2010.
[22] Chi Jin, Tiancheng Jin, Haipeng Luo, Suvrit Sra, and Tiancheng Yu. Learning adversarial Markov decision processes with bandit feedback and unknown transition. In Proceedings of the 37th International Conference Machine Learning, volume 119, pages 4860-4869, PMLR. 13-18 Jul 2020.
[23] Krishna C Kalagarla, Rahul Jain, and Pierluigi Nuzzo. A sample-efficient algorithm for episodic finite-horizon MDP with constraints. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 1030-8037, 2021.
[24] Kia Khezeli and Eilyan Bitar. Safe linear stochastic bandits. In Proceedings of the AAAI Conference Artificial Intelligence, volume 34, pages 10209, 2020.
[25] Hepeng Li, Zhiqiang Wan, and Haibo He. Constrained EV charging scheduling based on safe deep reinforcement learning. IEEE Transactions Smart Grid, 11(3):2427-2433 2019.
[26] Nikolaos
Liakopoulos, Apostolos Destounis, Georgios Paschos, Thrasyvoulos Spyropoulos, and Panayotis Mertikopoulos. Cautious regret minimization: Online optimization with long- term budget constraints. In International Conference on Machine Learning, pages 3944-3952. PMLR, 2019.
[27] Tao Liu, Ruida Zhou, Dileep Kalathil, PR Kumar, and Chao Tian. Fast global convergence of policy optimization for constrained mdps. arXiv preprint arXiv:2111.00552, 2021.
[28] Tao Liu, Ruida Zhou, Dileep Kalathil, PR Kumar, and Chao Tian. Learning Policies with Zero Bounded Constraint Violation for Constrained MDPs. In Thirty-fifth Conference on Neural Information Processing Systems, 2021.
[29] Xin Liu, Bin Li, Pengyi Shi, and Lei Ying. An efficient pessimistic-optimissicaall algorithm for stochastic linear bandits with general constraints. arXiv preprint arXiv:2102.05295, 2021.
[30] Andreas Maurer and Massimiliano Pontil. Empirical Bernstein bounds and sample-variance penalization. In COLT 2009 The 22nd Conference on Learning Theory, Montreal, Quebec, Canada, June 18-21, 2009, 2009.
[31] Ahmadreza Moradipari, Christos Thrampoulidis, and Mahnoosh Alizadeh. Stage-wits wise conser- vative linear bandits. Advances Neural Information Processing Systems, 33. 2020.
[32] Michael J Neely and Hao Yu. Online convex optimization with time-varying constraints. arXiv preprint 17Xiv:1702.0488.. 2017.
[33] Aldo Pacchiano, Mohammad Ghavamzadeh, Peter Bartlett, and Heinrich Jiang. Stochastic bandits with linear constraints. In International Conference on Artificial Intelligence and Statistics, pages 2827-2835. PMLR, 2021.
[34] Advait Parulekar, Soumya Basu, Aditya Gopalan, Karthikeyan Shanmugam, and Sanjay Shakkottai. Stochastic linear bandits with protected subspace. arXiv preprint 20Xix:0011.00011 2020.
[35] Santiago Paternain, Luiz Chamon, Miguel Calvo-Fullana, and Alejandro Ribeiro. Constrained reinforcement learning has zero duality gap. Advances Neural Information Processing Systems, 32:7555-7565, 2019.

---

[36] Thiago D Simão, Nils Jansen, and Matthijs TJ Spaan. Alwayssafe: Reinforeement learning without safety constraint violations during training. In Proceedings the 20th International Conference on Autonomous Agents and MultiAgent Systems. International Foundation for Autonomous Agents and Multiagent Systems, 2021.
[37] Rahul Singh, Abhishek Gupta, and Ness B Shroff. Learning in Markov decision processes under constraints. arXiv preprint 2rXfv:2002.12433. 2020.
[38] Rahul Singh and PR Kumar. Throughput optimal decentralized scheduling of multihop networks with end-to-end deadline constraints: Unreliable links. IEEE Transactions on Automatic Control, 64(1))127-142, 2018.
[39] Rahul Singh, PR Kumar, and Le Xie. Decentralized control via dynamic stochastic prices: The independent system operator problem. IEEE Transactions on Automatic Control, 63(10))3206 3220, 2018.
[40] Chen Tessler, Daniel Mankowitz, and Shie Mannor. Reward constrained policy optimization. In International Conference Learning Representations, 2018
[41] Ilnura Usmanova, Andreas Krause, and Maryam Kamgarpour. Safe convex learning under uncertain constraints. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 2106-2114 14. PMLR, 2019.
[42] Honghao Wei, Xin Liu, and Lei Ying. A provably-efficien model-free algorithm for infinite- horizon average-reward constrained Markov decision processes. In AAAI Conference on Artificial Intelligence, 2022.
[43] Honghao Wei, Xin Liu, and Lei Ying. Triple-q: model-free algorithm for constrained reinforcement learning with sublinear regret and zero constraint violation. In International Conference on Artificial Intelligence and Statistics, pages 3274-3307. PMIR, 2022.
[44] Tsung- Yen Yang. Justinian Rosca, Karthik Narasimhan, and Peter J Ramadge. Projection-based constrained policy optimization. In International Conference Learning Representations, 2019.
[45] Hao Yu, Michael J Neely, and Xiaohan Wei. Online convex optimization with stochastic con- straints. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pages 1427-1437, 2017.
[46] Jianjun Yuan and Andrew Lamperski. Online convex optimization for cumulative constraints. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 6140 6149, 2018.
[47] Yiming Zhang, Quan Vuong, and Keith Ross. First order constrained optimization in policy space. Advances in Neural Information Processing Systems, 33, 2020.
[48] Liyuan Zheng and Lillian Ratliff. Constrained upper confidence reinforcement learning. In Learning for Dynamics and Control, pages 620-629. PMLR, 2020.
[49] Ruida Zhou, Tao Liu, Dileep Kalathil, PR Kumar, and Chao Tian. Anchor-changing reg- ularized natural policy gradient for multi-objective reinforcement learning. arXiv preprini arXiv:2206.05337, 2022.
[50] Alexander Zimin and Gergely Neu. Online learning in episodic Markovian decision processes by relative entropy policy search. In Neural Information Processing Systems 26, 2013.
12

---

Societal Impact and Ethics Statement
Reinforcement learning has much potential for application variety of cyber-physical systems. such as the power grid, robotics and other systems where guarantees on the operating region of the system must met. Our work provides a theoretical basis for the design of controllers that can be applied in such scenarios. The approaches presented in the paper were tested on simulated environments, and did not involve any human interaction. We do not see any ethical concerns with our research approach.
note of caution with approach is that the policy generated is only good the training environment, and many examples exist wherein the policy generated is optimal according to its training, but violates basic truths known human operators and could fail quite badly. Indeed, our approach does not provide sample-path guarantees, and the system could well move into deleterious states for small fraction of the time, which might be completely unacceptable and trigger hard fail safes, such as breakers in a power system. Understanding the right application environments with excellent domain knowledge is hence needed before any practical success can be claimed.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes] In Theorem 3 and Section 5
(b) Did you describe the limitations of your work? [Yes] In Section 5
(c) Did you discuss any potential negative societal impacts of your work? [Yes] Societal Impact and Ethics Statement.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes] Described in Societal Impact and Ethics Statement.
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] Assumption and assumptions in statement of Theorem 3
(b) Did you include complete proofs of all theoretical results? [Yes] Appendix.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results? [Yes] Supplemental material
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [Yes] Section and Appendix E
(c) Did you report error bars (c.g., with respect the random seed after running experi- ments multiple times)? [Yes] Figures contain error hars.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] Appendix
4. If you using existing assets (e.g., code, data, models) curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either the supplemental material as URL? [Yes] Code is released as supplemtental material.
(d) Did you discuss whether and how consent was obtained from people whose data you're
using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects... [N/A]
13


Reviews:
[{"review_id": "QJ7CMsF8kOC", "reviewer": "Reviewer_UkP1", "summary": "This paper proposes an RL algorithm to learn a policy in a constrained setting without violating the safety constraints.\nIt relies on an initial baseline policy to collect data for the first episodes.\nEventually, it switches to a policy optimistic with respect to the transition function and reward.\nTo ensure the new policy is safe the paper proposes to penalize the cost function inversely to the number of times, being pessimistic with respect to the cost function.\n\nThe paper provides regret bounds for the main objective tighter than the bounds from previous algorithms that also do not violate the safety constraints (OptPess-LP).", "questions": "\n1. The current definition of regret is related to a weak measure as described in [17], which allows for \"error cancellations\". Considering Proposition 5, which states the policy applied in each episode is safe with high-probability, can we conclude the bound on the safety regret of DOPE is a strong measure?\n\n2. How DOPE behaves in the Factored CMDP given a baseline with cost bound $\\bar{C}_b = 0$?\n\n3. Empirically, it seems the effect of the baseline policy in the regret seems to be contradictory to what would be expected from the regret bounds. That is, lower values of $\\bar{C}_b$ would lead to lower regrets. Could you comment on this phenomenon?\n\n### references\n\n[17] Yonathan Efroni, Shie Mannor, and Matteo Pirotta. Exploration-exploitation in constrained MDPs. arXiv preprint arXiv:2003.02189, 2020.", "limitations": "\nYes, the paper makes clear statements regarding the assumptions required for the proposed algorithm, namely, access to a safe initial baseline policy.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\n### strengths\n\n- The main novelty of the proposed algorithm compared to the previous OptPess-LP is to be optimistic with respect to the transition function in addition to optimism with respect to the reward. To compensate for the double optimism the paper also proposes a new penalty for the cost function, increasing the pessimism with respect to the cost.\n- The significance of the paper seems limited to showing that the algorithm proposed has smaller regret compared to the OptPess-LP algorithm.\n\n### weaknesses\n\n- The empirical results could be improved considerably. Although the paper describes the AlwaysSafe-$\\pi_\\alpha$ algorithm, it tests the AlwaysSafe-$\\pi_T$ algorithm. In [34], it is already shown that the $\\pi_T$ variant can be overly conservative, it may even fail to converge to the optimal policy. An appropriate comparison should use the $\\pi_\\alpha$ algorithm, which can converge to the optimal policy.\n- The clarity of the paper could be improved, for instance, by clarifying the connections between the different theoretical claims in Section 4.\n\n### minor comments\n\n- line 100: peratins -> pertains\n- line 210: something is strange with \"less observed less\"\n\n\n### references\n\n[34] Thiago D Simão, Nils Jansen, and Matthijs TJ Spaan. AlwaysSafe: Reinforcement learning without safety constraint violations during training. 2021.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "DDWxmSpjamn", "reviewer": "Reviewer_ucst", "summary": "Existing safe reinforcement learning (RL) algorithms are basically optimistic w.r.t. reward (via exploration bonus) and pessimistic w.r.t. constraints. Such algorithms are excessively pessimistic; thus, empirical performance is bad due to a long learning process. The authors present Doubly Optimistic and Pessimistic\nExploration (DOPE) algorithm for safe RL, which is doubly optimistic w.r.t. reward and model while being pessimistic w.r.t safety. The authors theoretically analyze the objective regret and constraint violation, which is better than OptPessLP algorithm. Finally, they empirically show that DOPE performs better than baselines in multiple benchmark tasks.", "questions": "[Q1] Can the authors provide me with an intuitive explanation of which of the innovations in this paper led to the reduction of objective regret? I think I understand the DOPE algorithm and followed the proof, but I do not fully understand why the DOPE algorithm can achieve smaller regret.", "limitations": "Limitations and potential negative societal impact have been fully addressed in lines 351-355 and lines 487-500, respectively.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I think this paper is a solid paper, which will potentially contribute to the future safe RL researches.\n\n[Strength]\n- This paper is well-organized and easy to follow.\n- Theoretical results are good. Especially, it is an important result that objective regret is less than OptPess-LP while constraint regret is zero.\n- Empirical experiments. I deeply appreciate that the authors conducted experiments in three tasks. As the authors argue, many safe RL algorithms do not perform well in empirical experiments in spite of its beautiful theoretical properties. I personally think that DOPE algorithm is impressive in that it is backed by theory and practice.\n\n[Weakness]\n- (Note that I think this is a minor weakness) Benchmark tasks are still easy and simple.\n- Source code is messy. I would like the authors to refactor it before open-sourcing it. \n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "AznZRV8f6fj", "reviewer": "Reviewer_sxzS", "summary": "The authors propose a safe exploration algorithm that relies on the idea of both optimism and pessimism under uncertainty. The problem is formulated as a constrained MDP that is solved using a Linear Programming approach which iteratively approximates the transition model and the optimal policy, the cost, and constraints for each state-action pair.\nIn order to ensure that the policy is safe through this approximation, an additional term is added to the constraint objectives (pessimism) and the cost objective is relaxed with additional terms (optimism) which ensures the exploration of under-explored states. These terms are O(1/n(s,a)) and can cause the initial problem to be infeasible. Therefore,\nthe algorithm relies on an initial safe exploration policy that ensures that constraints are not violated. The authors demonstrate that under certain conditions, constraints are satisfied with high probability in the original problem i.e. under the true transition model. The result is an algorithm that has 0 constraint regret and that, compared to SOTA, reduces the objective regret\nby a factor of O^{\\tilde}(\\sqrt(|S|)) where |S| is the size of the state space.", "questions": "Line 179: Shouldn't there be a summation over the timestep h? or it should be the number of times the pair (s,a) has been observed at timestep h before the beginning of episode k\nLine 188: The summation should be until k-1 and r_{h} should be replaced by r_{h, k^{\\prime}} I suppose\nLine 189: What is r^{\\tilde} in terms of (r^{\\tilde}_{h})", "limitations": "The algorithm is limited to tabular settings but this is something that the authors have already pointed out.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nAn algorithm that combines both advantages of pessimism and optimism approaches to safety yielding 0 constraints regret and a reduced objective regret by a factor of O^{\\tilde}(\\sqrt(|S|))\nAn analysis of the algorithm which clarifies the motivation behind the algorithm\nEmpirical results that demonstrate the superiority of the algorithm over SOTA\nWeaknesses:\n\nThe algorithm relies on the assumption that we have an initial safe exploration policy which ensures that the constraints are always satisfied.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept