Provably Safe Reinforcement Learning with Step-wise Violation Constraints
Authors: Nuoya Xiong
Yihan Du
Longbo Huang
Venue: NeurIPS 2023 poster (2023)
Keywords: safe reinforcement learning
step-wise violation
reinforcement learning theory
TL;DR: This paper study the safe reinforcement learning and reward-free exploration with step-wise violation constraints

Abstract: We investigate a novel safe reinforcement learning problem with step-wise violation constraints. Our problem differs from existing works in that we focus on stricter step-wise violation constraints and do not assume the existence of safe actions, making our formulation more suitable for safety-critical applications that need to ensure safety in all decision steps but may not always possess safe actions, e.g., robot control and autonomous driving.
We propose an efficient algorithm SUCBVI, which guarantees $\widetilde{\mathcal{O}}(\sqrt{ST})$ or gap-dependent $\widetilde{\mathcal{O}}(S/\mathcal{C}_{\mathrm{gap}} + S^2AH^2)$ step-wise violation and $\widetilde{\mathcal{O}}(\sqrt{H^3SAT})$ regret. Lower bounds are provided to validate the optimality in both violation and  regret performance with respect to the number of states $S$ and the total number of steps $T$. 
Moreover, we further study an innovative safe reward-free exploration problem with step-wise violation constraints. For this problem, we design algorithm SRF-UCRL to find a near-optimal safe policy, which achieves nearly state-of-the-art  sample complexity $\widetilde{\mathcal{O}}((\frac{S^2AH^2}{\varepsilon}+\frac{H^4SA}{\varepsilon^2})(\log(\frac{1}{\delta})+S))$, and guarantees $\widetilde{\mathcal{O}}(\sqrt{ST})$ violation during exploration.  Experimental results demonstrate the  superiority of our algorithms in safety performance and corroborate our theoretical results.

Provably Safe Reinforcement Learning with Step-wise Violation Constraints
Nuoya Xiong' Yihan Du Longbo Huang 1+++
Institute for Interdisciplinary Information Sciences, Tsinghua University
University of Illinois at Urbana-Champaign
"muoyaxiong@gmail. yyhhandu@llinnoss. loongbhhanggdssinghaaa edu. .au..ch cn
Abstract
We investigate novel safe reinforcement learning problem with step-wise violation constraints. Our problem differs from existing works in that we focus stricter step-wise violation constraints and do not assume the existence of safe actions, making our formulation more suitable for safety-critical applications that need to ensure safety in all decision steps but may not always possess safe actions, e.g., robot control and autonomous driving. We propose an efficient algorithm SUCBVI, which guarantees an Ö(VST) or gap-dependent OSS/Cgup S AH))
step-wise violation and an Õ(v SAAT regret. Lower bounds are provided to validate the optimality in both violation and regret performance with respect the number of states S and the total number of steps T. Moreover, we further study an innovative safe reward-free exploration problem with step-wise violation constraints. For this problem, we design the algorithm SRF-UCRL. to find near- optimal safe policy, which achieves a nearly state-of-the-ie sample complexity =² Õ(( 55 + $*$$ (1og(3) + 5)), and guarantees an O (VVST) violation during exploration. Experimental results demonstrate the superiority of our algorithms safety performance and corroborate our theoretical results.
Introduction
In recent years, reinforcement learning (RL) (Sutton & Barto, 2018) has become powerful framework for decision-making and learning in unknown environments. Despite the ground-breaking success of RL in games (Lanctot al., 2019), recommendation systems (Afsar et al., 2022) and complex tasks in simulation environments (Zhao et al., 2020), most existing RL algorithms focus on optimizing the cumulative reward and do take into consideration the risk aspect, e.g., the agent runs into catastrophic situations during control. 'he lack of strong safety guarantees hinders the application of RI. to broader safety-critical scenarios such as autonomous driving, roboties and healthcare. For example, for robotic control in complex environments, it is crucial to prevent the robot from getting into dangerous situations, e.g., hitting walls or falling into water pools, at all times.
To handle the safety requirement, common approach is to formulate safety as a long-term expected violation constraint in each episode. This approach focuses on seeking policy whose cumulative expected violation in each episode is below a certain threshold. However, for applications where an agent needs to avoid disastrous situations throughout the decision process, e.g., robot needs avoid hitting obstacles at each step, merely reducing the long-term expected violation is not sufficient to guarantee safety.
"Corresponding author.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Motivated by this fact, we investigate safe reinforcement learning with a more fine- tin-igrined constraint, called step-wise violation constraint, which aggregates all nonnegative violations at each step (no offset between positive and negative violations permitted). We name this problem Safe-RI-SS.. Our step-wise violation constraint differs from prior expected violation constraint (Wachi & Sui, 2020; Efroni et al., 2020b; Kalagarla et al., 2021) in two aspects: (i) Minimizing the step-wise violation enables the agent to learn an optimal policy that avoids unsafe regions deterministically, while reducing the expected violation only guarantees to find policy with low expected violation, instead of per-step zero sero-violation policy, (ii) Reducing the aggregated nonnegative violation allows us to have risk control for each step, while small cumulative expected violation can still result in large cost at some individual step and cause danger, if other steps with smaller costs offset the huge cost.
Our problem faces two unique challenges. First, the step-wise violation requires us to guarantee a small violation at each step, which demands very different algorithm design and analysis from that for the expected violation (Wachi Sui, 2020; Efroni et al., 2020b; Kalagarla et al., 2021). Second, in safety-critice scenarios, the agent needs to identify not only unsafe states but also potentially unsafe states, which are states that may appear to be safe but will ultimately lead to unsafe regions with non-zero probability, For example, self-driving car needs to learn to slow down or change directions early, foreseeing the potential danger in advance in order to ensure safe driving (Thomas et al., 2021). Existing safe RL works focus mainly the expected violation (Wachi & Sui, 2020; Liu et al., 2021b; Wei et al., 2022), or requiring some other assumptions such as imposing the prior knowledge of safe action for each state (Amani et al., 2021). Moreover, many previous works also require strong assumptions that exclude discrete tabular MDP (Amani et al., 2021; Wachi et al., 2021; Wang al., 2023) which is considered in our paper. Hence, techniques in previous works cannot be applied to handle step-wise violations. More detailed comparisons are provided in Section 2.
To systematically handle these two challenges, we formulate safety each state without assuming safe actions, and consider minimizing the step-wise violation instead of the expected violation. We propose a general algorithmic framework called Safe UCBVI (SUCBVI), Specifically, in each episode, we first estimate the transition kernel and cost function in an optimistic manner, tending to regard a state safe at the beginning of learning. After that, we introduce novel dynamic programming to identify potentially unsafe states and determine safe actions, based on our estimated transition and costs. Finally, we employ the identified safe actions to conduct value iteration. This mechanism can adaptively update dangerous regions, and help the agent plan for the future, which keeps her away from all states that may lead to unsafe states. As our estimation becomes more accurate over time, the safety violation becomes smaller and eventually converges to zero. Note that without the assumption of safe actions, the agent knows nothing about the environment the beginning. Thus, it is impossible for her to achieve an absolute zero violation. Nevertheless, we show that SUCBVI can achieve a sub-linear ((VST) cumulative violation or an O(S/Cgup + 52 AF?2) gap-dependent violation that is independent of T. This violation implies that as the RL game proceeds, the agent eventually learns how avoid unsafe states. We also provide matching lower bound to demonstrate the optimality of SUCBVI in both violation and regret.
unknown cost function for
Furthermore, we apply our step-wise safe RL framework to the reward-free exploration (Jin et al., 2020) setting. In this novel safe reward-free exploration, the agent needs to guarantee small step-wise violations during exploration, and also output a near-optimal safe policy. Our algorithm achieves cumulative step-wise violation during exploration, and also identifies a e-optimal and safe policy. See the definition of e-optimal and s-safe policy in Section 6. 1. Another interesting application of our framework is safe zero-sum Markov games, which we discuss in Appendix B.
The main contributions of our paper are as follows.
We formulate the safe RL with step-wise violation constraint problem (Safe-RL-SW), which models safety as a cost function for states and aims to minimize the cumulative step-wise violation. Our formulation is particularly useful for safety-critica applications where avoiding disastrous situations at each decision step is desirable, e.g., autonomous driving and robotics.
We provide a general algorithmic framework SUCBVI, which is equipped with an innovative dynamic programming to identify potentially unsafe states and distinguish safe actions. We estab- lish an ((V regret and an (VVTT) or (S/Coap + 52 AH12) gap-dependent violation guarantees, which exhibits the capability of SUCBVI in attaining high rewards while maintaining small violation.

---

We further establish an (TVHSTT regret and an [ ((VST) violation lower bounds for Safe-RL-SW. The lower bounds demonstrate the optimality of algorithm SUCBVI in both regret minimization and safety guarantee, with respect to factors S and T'
We consider step-wise safety constraints in the reward free exploration setting, which is called the Safe-RFE-SW problem. In this setting, we design an efficient algorithm SRF-UCRL. which ensures ε step-wise violations during exploration and plans a s-optimal and E-safe policy for any reward functions with probability at least 1 - 8. We obtain O((
D((S"AH' AHH + H' (log( () + S)) sample complexity and an OT" violation guarantee for SRF-UCRL, which shows the efficiency of SRF-UCRL in sampling and danger avoidance even without reward signals. To the best of our knowledge, this work is the first to study the step-wise violation constraint in the RFE setting.
2 Related Work
Safe RL. Safety is an important topic in RL, which has been extensively studied. The constrained
Markov decision process (CMDP)-based approaches handle safety via cost functions, and aim to minimize the expected episode-wise violation, e.g., (Yu et al., 2019; Wachi & Sui, 2020; Qiu et al., 2020; Efroni et al., 2020b; Turchetta et al., 2020; Ding et al., 2020; Singh al., 2020; Kalagarla et al.,
2021; Simão et al., 2021; Ding et al., 2021), achieve zero episode-wise violation, e.g., (Liu et al.,
2021b; Bura et al., 2021; Wei et al., 2022: Sootla et al., 2022). Apart from CMDP- approaches, there are also other works that tackle safe RL by control-based approaches (Berkenkamp et al., 2017; Chow et al., 2018; Dalal et al., 2018; Wang et al., 2022), policy optimization (Uchibe & Doya, 2007;
Achiam et al., 2017; Tessler et al., 2018; Liu et al., 2020; Stooke et al., 2020) and safety shields (Alshickh et al., 2018).
In recent years, there are also some works studying step-wise violations with additional assumptions. Now we provide detailed comparisons between existing papers with instantaneous constraints. Turchetta et al. (2016); Wachi et al. (2018) propose a GP-based algorithm, which assumes that the transition deterministic and known, while modeling the reward and cost functions using Gaussian Processes. By using this particular structure, they can infer the safety cost by estimating the parameters. Wachi et al. (2021) assumes the reward and cost functions have a generalized linear structure. Their algorithm explores in safe space until time 1* when the agent explores sufficiently, However, the upper bound of the exploring time t* is not given in their paper. In fact, under the tabular MDP setting t' can be infinite.
Amani et al. (2021) further considers the reward and cost functions to have linear structure. makes two assumptions: (a) There exists a safe action in each state, which prevents the agent from going to a potentially unsafe state. (b) The feature set a star convex set, which helps them change actions continuously. However, this makes their works infeasible in tabular MDPs: The feature set in tabular MDPs consists of one-hot vectors and is not a star convex set. Hence, the work Amani et al. (2021) cannot solve our problem. Shi et al. (2023) considers safe RL in linear mixture MDPs. Their work also contains assumption (b), making it infeasible in tabular MDPs. Moreover, although they do not have assumption (a), it assumes the transition set A(s, a) is known, which is not needed in our paper. Thus our paper is more challenging since we need to estimate A(s, a) in our algorithm adaptively.
There are some other papers investigating the safety of RL problems. Alshickh et al. (2018) represents the safe state by the reactive system, and uses shielding to calculate and restrict the agent within a safe trajectory completely. The main difference between their work and our work is that we need to dynamically update the estimated safe state, while they require know the mechanism and state to calculate the shield. Dalal et al. (2018) considers restricting the safe action by projecting the action into the closest safe actions. They achieve this goal by solving a convex optimization problem on the continuous action set. However, in their paper, they do not consider the situation where a state can have no safe actions. To be more specific, they do not consider the situation when the convex optimization problem has solutions. Le et al. (2019) considers the decision-making making problem with a pre-collected dataset. Turchetta et al. (2020) and Sootla et al. (2022) both consider cumulative cost constraints rather than step-wise constraints. The former uses teacher for intervention to keep the agent away from the unsafe region, while the latter encourages safe exploration by augmenting a safety state to measure safety during training.
Reward-free Exploration with Safety. Motivated by sparse reward signals in realistic applica- tions, reward-free exploration (RFE) has been proposed in Jin et al. (2020), and further developed
3

---

in Kaufmann et al. 1) Ménard et al. (2021). In RFE, the agent explores the environment without reward signals. After enough exploration, the reward function given, and the agent needs to plan near-optimal policy based on his knowledge collected in exploration. Safety is also important in RFE: We need to not only guarantee that our outputted policy is safe, but also ensure small violations during exploration.
Recently, Miryoosefi & Jin (2022); Huang et al. (2022) also study RFE with safety constraints. Compared to our paper, Miryoosefi & Jin (2022) only considers the safety constraint after the exploration phase. Huang et al. (2022) differs from our work in the following aspects: (i) They allow different reward functions during exploration and after exploration, and the agent can directly know the true costs during training. In our work, the cost function the same during and after exploration. but the agent can only observe the noisy costs of a state when she arrives at that state. (ii) They require prior knowledge of safe baseline policies, while we do not need such an assumption. (iii) They consider the zero-expected violation during exploration, while we focus on keeping small step-wise violations.
3 The Safe MDP Model
Episodic MDP. In this paper, we consider the finite-horizon episodic Markov Decision Process (MDP), represented by a tuple (S, A, H, P. r). Here S is the state space, A is the action space, and H is the length of each episode. P = (T',, S x A As [ is the transition kernel, and Py (x a) gives the transition probability from (s, a) to s' at step h. the reward function, and r. rx, a) gives the reward of taking action in state at step h. A policy π = ( : S + A)EE(H] consists of H mappings from the state space to action space. In each episode k, the agent first chooses a policy n². At each step h E [H], the agent observes a state * takes an action a and then goes to a next state + with probability PA (s sx at). The algorithm executes T = HK steps. Moreover, the state value function V (s,, a) and state-action value function Q7, (s, a.) for a policy π can be defined as
[M]
{rr S x A + [0. 1E is
(s) = E.z
Σ
rhe (((s,,,T<(BB (8w.) 8h =
-=
H
QT( = E,
Σ
(sw TM (sw))
8h. = aq =
h'=h
Safety Constraint. To model unsafe regions in the environment, similar to Wachi Sui (2020); Yu
al. (2022), we define safety cost function e: S [0, 1]. Let [0, denote the safety threshold. A state is called safe if c(s) S r, and called unsafe if c(s) > т. Similar to Efroni et al. (2020b); Amani et al. (2021), when the agent arrives in state 8, she will receive a cost signal z(s) = c(s) - C.
where ( is an independent, zero-mean and I-sub-Gaussian noise. Denote (x)+ max 0}. The
violation in state s defined as (c(s) T)+, and the cumulative step-wise violation till episode K is
K H
C(K) =
(o(s)) M
-)+
Eg. (1) represents the accumulated step-wise violation during training. When the agent arrives in state sf. step f in episode k. she will suffer violation (c(sf) - 7)+ This violation setting is significantly different from the previous CMDP setting (Qiu et al., 2020; Ding et al., 2020; Efroni et al., 2020b; Ding et al., 2021; Wachi Sui, 2020; Liu et al., 2021a; Kalagarla et al., 2021). They study the
episode-wise expected violation C' (K) Ek=1
[Е |>>-_ o of) - -)) There are also some
papers (Efroni et al., 2020a; Simão et al., 2021) considering a stricter constraint named episode-
wise clipped expected violation: ("())) = ΣK= (H Σm c(s), at) - -)) .Compared to the
episode-wise violation (including expected violation and clipped expected violation), our step-wise violation has two main differences: (i) First, the episode- wise violation constraints allow the agent to get into unsafe states occasionally. Instead, the step-wise violation constraint forees the agent to stay in safe regions at all times. (ii) Second, in the episode-wise constraints, the average violation

---

Blc(sk, [[]]s,;;)]]=-)) H/ at step h is allowed to be positive or negative, and they can cancel out in one episode to achieve E| cs a[]] S μ.. Instead, consider nonnegative function (c(s) +)+ at each step our step-wise violation, which imposes stricter constraint.
Define 4 = {s E 8 c(s) > 7 as the set of all unsafe states. Let {81, ai, 8H, an}} denote a trajectory. Since feasible policy needs to satisfy the constraint at each step, we define the set of feasible policies II { Pr( 3 h E [H] S4 E E x) = 0). The feasible policy set II consists of all policies under which one never reaches any unsafe state in an episode.
Learning Objective, In this paper, we consider the regret minimization objective. Specifically, define π argmax TEll V/1", V* V= and Q = =Q". The regret till K episodes is then defined as
R(K) = - (vi(s)) VT (si)),
where x* is the policy taken in episode k. Our objective is to minimize R(K) to achieve a good performance, and minimize the violation C(K) to guarantee the safety the same time.
4 Safe RL with Step-wise Violation Constraints
4.1 Assumptions and Problem Features
Before introducing our algorithms, we first state the important assumptions and problem features for Safe-RL-SS.
Suppose и is feasible policy. Then, if we arrive at s step H needs select an action that guarantees
& U. Define the transition set (s, = {s' [' s,a) > 0} for any v(s,a, a, h) E S x A x [H] which represents the set of possible next states after taking action a in state at step h. Then, at the former step H 1, the state is potentially unsafe if it satisfies that AH-1(s, a) nu + ( for all A. (i.e., no matter taking what action, there positive probability of transitioning to an unsafe next state). Therefore, we can recursively define the set of potentially unsafe states at step h as
Un U (s VaE A, A,
+ 0),
(2)
where Un U. Intuitively, if we in state Sy. U4, at step h, action can be taken completely avoid reaching potentially unsafe states 84+1 E Uh+1 at step / + 1. Thus, in order to completely prevent from getting into unsafe states V/ throughout all steps, one needs avoid potentially unsafe states in Ub at step h. From the above argument, we have that 81 é 2h is equivalent to the existence of feasible policies. The detailed proof is provided in Appendix D. Thus, we make the following necessary assumption.
Assumption 4.1 (Existence of feasible policies). The initial state 81 satisfies 81 $ Uh. For any 8 E S and h E H 1], we define the set of safe actions for state at step h as
Ar (s)) {a E A (n(s,)) n1h+1 = 0),
and let Agafe(s) A. (s) stands for the set of all actions at step h which will not lead to potentially unsafe states +1+ Here, (24n (eee)e and { (s))n(t are defined by dynamic programming: we know sets of all possible next state (Ai(s, he(an] and unsafe state set Ug.
we can calculate all potentially unsafe state sets (U4, (eej) and safe action sets {A)afe(s) (s)] and choose feasible policies completely avoid unsafe states.
4.2 Algorithm SUCBVI
Now we present our main algorithm Safe UCBVI (SUCBVI), which is based on previous classic RL algorithm UCBVI (Azar et al., 2017), and equipped with novel dynamic programming to identify potentially unsafe states and safe actions. The pseudo-code is shown in Algorithm 1. First, we provide some intuitions about how SUCBVI works. At each episode, we first estimate all the unsafe states based on the historical data. Then, we perform dynamic programming procedure introduced
5

---

Algorithm SUCBVI
1: Initialize: ()
N (s, for a. A. s' S and h [H].
2: for k = 1,2,.... , do
3: Update the optimistic estimates of cost.
4: Update the empirical cost ē(s) and calculate ((s) = ((s) (s), for all & E S. b
5: Define U - {a c(s) > } and U U U Va E A, A (s, a) nu 1 A 0) for all
h E [H] recursively. Calculate (Att (eE)) by Eq. (3) with (4 he(m-
& Perform value iteration with previous estimates.
6: for h H, 1, do
7:
for 8 E S do
8:
for E A do
Compute (8' 8, a) (e.o,')
9:
(s.a)
10:
(s, Hi ( Eg (s s.a) + (s,))
end for
12:
if 8 & U then
13:
(s) = max EEA 1 (8) = arg max ae (x) (%(s,)).
else
15:
(s) = max (s. arg max (s.a)
end if
17:
end for end for
19:
for
1.2, do Take action a - (s and observe state s 8h+11
> Update the estimates of Ass, a).
A k++1 (s a (s a 11h Increase N (5 a No
N (sh ag st +1+)) (441)b by
22:
end for
23: end for
in Section 4.1 and calculate the safe action set (s) for each state Then, we perform value iteration in the estimated safe action set. As the estimation becomes more accurate, SUCBVI will eventually avoid potentially unsafe states and achieve both sublinear regrets and violations.
Now begin introduce algorithm. In the beginning, initialize (n(s, 0 for all (h, s, a) E [H] x A. implies that the agent considers all actions to be safe at first, because no action will lead unsafe states from the agent's perspective. In each episode, we first estimate the empirical cost č(s) based on historical cost feedback z(8), and regard state as safe if e(s) ē(s) 3 т for some bonus term 3, which aims to guarantee c(s) S c(s) (Line 4). Then, calculate the estimated unsafe state set 24, which is a subset of the true unsafe state set U UH with high probability by optimism. With Ut and A (s,a), we can estimate potentially unsafe state sets UK for all h E [H] by Eq. (2) recursively.
Then, we perform value iteration to compute the optimistically estimated optimal policy. Specifically, for any hypothesized safe state & Ug, we update the greedy policy on the estimated safe actions, i... (s) = an (s) Q (s, a) (Line 13). On the other hand, for any hypothesized unsafe state 8) E Uh. since there is action that can completely avoid unsafe states, we ignore safety costs and simply update the policy by (s) = max Q(s, a) (Line 15). After that, we calculate the estimated optimal policy Te for episode k, and the agent follows nh and collects a trajectory. Then, we update 1 a) by incorporating the observed state 1 into the set (s af)). Under this updating rule, it holds that (s,ss a) S An(s, a) for all (s, a) E S x A. The performance of Algorithm 1 is summarized below in Theorem 4.2.
Theorem 4.2. Let a(n 8) = 7H
(8) and 3(n, 8) = V (og(SK/)). With probability least 8, the regret and step-wise violation of Algorithm 1 are bounded by
R(K) = O(HHSSAT)
C(K) ÖVVST 52

---

Moreover, if Cgap minggu(c(s)) - + > O, we have C(K) = ÖSS/Cgap S AH²).
Theorem 4.2 shows that SUCBVI achieves both sublinear regret and violation. Moreover, when all the unsafe states have a large cost compared to the safety threshold T, i.c., Ggap = min.ggt ( is constant, we can distinguish the unsafe states easily and get constant violation. In particular, when r = 1, Safe- RL-SW degenerates to the unconstrained MDP and Theorem 4.2 maintains the same regret (AT) as UCBVI-CH (Azar et al., 2017), while CMDP algorithms (Efroni et al., 2020b; Liu et al., a02 suffer a larger ( regret.
We provide the analysis idea of Theorem 4.2 here. First, by the updating rule of (s,, a), we show that U4 and A (s) have the following crucial properties: U C Un. Ah. A C (s). Based on this property, can prove that Q7 a) I (f, a) and V
(s) for all (s, a).
and then apply the regret decomposition techniques to derive the regret bound.
Recall that x is a feasible policy with respect to the estimated unsafe state set U and transition set { [ (s, a) hejz)- If the agent takes policy T² and the transition follows (8, a), i.e., sh+1 E (s, a). the agent never arrive any estimated unsafe state Uh in this episode. Hence the agent will suffer at most an Ö(VST) step-wise violation an O(S/Cgap + S² (HHAH gap-dependent bounded violation. Yet, the situation S/+1 (s, a) does always hold for all [H]. In the
case when & $ (s, a)) we add the newly observed state & into A * (s%. af) (Line 21).
We can show that this case appears at most S A times, and thus incurs (H2)) additional violation. Combining the above cases, the total violation can be upper bounded.
5 Lower Bounds for Safe-RL-SW
In this section, we provide a matching lower bound for Safe-RL-SW Section 4. The lower bound shows that if an algorithm always achieves sublinear regret in Safe-RL-SS, it must incur an 2(VST) violation. This result matches our upper bound in Theorem 4.2, showing that SUCBVI achieves the optimal violation performance.
Theorem 5.1. If an algorithm has an expected regret E, [m(R(()) < HK for all MDP instances, there 24
exists an MDP instance in which the algorithm suffers expected violation [x,[C(K]] ((vST).
Now we validate the optimality terms of regret. Note that if we do not consider safety constraints, the lower bound for classic RL (Osband & Van Roy, 2016) can be applied to our setting. Thus, we also have an R(VT) regret lower bound. To understand the essential hardness brought by safety constraints, further investigate whether safety constraints will lead to an Ω (TV)) regret, given that can achieve an o(VT) regret some good instances without the safety constraints.
......,,Me, Mn satisfying Theorem 5.2. For any a E (0, 1), there exists a parameter n and n MDPs Mi...,, that:
If we do not consider any constraint, there is an algorithm that achieves an H(r(1-a)/2 regret compared to the unconstrained optimal policy on all MDPs.
2. If we consider the safety constraint, any algorithum with O(Tl-0) expected violation will achieve an ((VHST)) regret compared the constrained optimal policy on one of MDPs.
Intuitively, Theorem 5.2 shows that if one achieves sublinear violation, she must suffer least an Q(VT) regret even if she can achieve an of (T) regret without considering constraints. This theorem demonstrates the hardness particularly brought by the step-wise constraint, and corroborates the optimality of our results. Combining with Theorem 5.1, the two lower bounds show an essential trade-off between the violation and performance.
7

---

6 Safe Reward-Free Exploration with Step-wise Violation Constraints
6.1 Formulation of Safe-RFE-SW
In this section, consider Safe RL in the reward-free exploration (RFE) setting (Jin al., 2020; Kaufmann et al., 2021; Ménard et al., 2021) called Safe-RFE-SW, to show the generality of our proposed framework. In the RFE setting, the agent does not have access reward signals and only receives random safety cost feedback z(s) = c(s) + Ç. To impose safety requirements, Safe-RFE-SV requests the agent to keep small safety violations during exploration, and outputs a near-optimal safe policy after receiving the reward function.
Definition 6.1 ((e, 8) opptimll safe algorithm for Safe-RFE-SW) An algorithm is (s, 8)-ptimall safe for Safe-RFF-SW if outputs the triple (IP, (s,, a), UH) such that for any reward function r, with probability least 1 d,
ES Σ (c(s)) - [ VT ET
(S VP (81r)) Se,
Se,
where 4* is the optimal feasible policy with respect (P,, A(s, a), II is the set of feasible policies with respect to (A (s. a). Un). and ((s;)) is the value function under reward function r. We say that a policy is E-optimal if it satisfies the left inequality in Eq. (4) and E-safe if it satisfies the right inequality in Eq. (4). We measure the performance by the number of episodes used before the algorithm terminates, i.e., sample complexity. Moreover, the cumulative step-wise violation till episode is defined as C(K) Σ ((=r(())) +)+- In Safe-RFE-SW our goal is to design an (s, oopttmal safe algorithm, and minimize both sample complexity and violation.
6.2 Algorithm SRF-UCRI.
The Safe-RFE-SW problem requires us consider extra safety constraints for both the exploration phase and final output policy, which needs new algorithm design and techniques compared to previous RFE algorithms. Also, the techniques for Safe-RL-SW in Section 4.2 are not sufficient for guaranteeing the safety of output policy, because SUCBVI only guarantees a step-wise violation during exploration.
We design an efficient algorithm Safe RE-UCRL (SRF-UCRL), which builds upon previous RFE algorithm RF-UCRL (Kaufmann et al., 2021). SRF-UCRL distinguishes potentially unsafe states and safe actions by backward iteration, and establishes a new uncertainty function to guarantee the safety of output policy. Algorithm 2 illustrates the procedure of SRF-UCRL. Specifically, in each episode k we first execute a policy म computed from previous episodes, and then update the estimated next state set {A (s, h)E and unsafe state set U4 by optimistic estimation. Then, we use Eq. (2) to calculate the unsafe state set Un. for steps h E [H] After that, we update the uncertainty function - defined in Eq. (5) below and compute the policy x++1 that maximizes the uncertainty to encourage more exploration in the next episode.
Now we provide the definition of the uncertainty function, which measures the estimation error between the empirical MDP and true MDP. For any safe state-action pair & Un, a E A sk. we define
(h, = min { H. H,N((,((, Σ Pl (,
Wh Wh+i(s'.b) ().
max
(5)
BE A Fina
(6)
where M ( = -2H (oa)..) (g(a.a)
+ (N.(N) and (n, 8) is logarithmic term ()(aa))
that is formally defined in Theorem 6.2. For other state-action pairs (s, a), we relax the restriction of b E AR.safe (s') to AA in the max function. Our algorithm stops when W (s), x (s1)) shrinks to within e/2. Compared to previous RFE works (Kaufmann et al. (2021); Ménard al. (2021)), our uncertainty function has two distinctions. First, for any safe state-action pair (s,a) a) E (S \ Ub. Att f Eq. (5) considers only safe actions A At.safe(s), (s). which guarantees that the agent focuses on safe policies. Second, Eq. (5) incorporates another term (SH (N a), 8)/N)) N (s, a)) to control the expected violation for feasible policies. Now present result for AFf--RFE-SW.
8

---

Algorithm 2 SRI-UCRL
1: Initialize: k= 1, W (3) = H, ())s) ai all S, E A and h [H].
2: while WA 15 (s1)) S s/2 do
3: for h = 1....., do
4:
Observe state si Take action of = =x (f%) and observe s
> Update the optimistic estimate of cost.
5:
Calculate empirical cost ē(s) and 2(s) 0(s) - (s)* 8) for all s E S.
> Update the estimates of An(s, a) and Un.
6:
Update ( a = - "s a (sh+1) and { JoEm by Eq. (2).
7:
Calculate A 1f. (s) for all end for
by Eq. (3).
8:
9:
Update (s, a, s'),,,,,)),,,, N (s, a) and PK for all S,a E A, e and h [M].
Compute W according to Eq. (5).
10:
> Calculate the greedy policy.
11:
for l E [H], S do
if A s. (s) + then
13:
"
k+1 (8) arg max
S aa Wx
14:
else
15:
k+1 (s) = arg mA W as)
16:
end if
17:
end for
18:
Set k: = k: 1.
19:
end while
20:
return the tpple (iP--11 ())
[og(e((++n/(G Theorem 6.2. Let 7n, 8) = 2(log + (S - log(ee1 + n/(S - 1))), Algorithm 2 is (E,8 algorithum with sample complexity most?
K k=ō((
(55((AA))
82 S
H'SAY 22
J + (+)))
log
The step-wise violation of Algorithm 2 during exploration C(K) O(S AH2 + VT)..
Compared to previous work (Kaufmann et al., 2021) with an (((H/5A/==))l complexity, result has additional term ((S2 AH2 (e)oo((11)1 + S)). This term is due to the additional safety requirement for the final output policy, which was not considered in previous RFE algorithms (Kaufmann al., 2021; Ménard al., 2021). When and are sufficiently small, the leading term is ((H*SA/EE) log(1/o)), which implies that our algorithm satisfies the safety constraint without suffering additional regret.
+)) sample
6.3 Analysis for Algorithm SRF-UCRL
For the analysis of step-wise violation (Eq. (1)), similar to algorithm SUCBVI, algorithm SRF-UCRL
estimates the next state set Au (s, a) and potentially unsafe state set Uh. which guarantees a Õ step-wise violation. Now we give a proof sketch for the E-safe property of output policy (Eq. (4)).
First, if is feasible policy for (T& As,s, a), (44) (NEEH) and 8h+1 E A (sh, an) for all [H), the agent who follows policy æ will only visit the estimated safe states. Since each estimated safe state
HHere Ó() ignores all log S, log A, log H1, (/e( and log(log(1/8)) terms.
'Ménard et al. (2021) improve the result by factor H and replace 1og(1/6) S by log(1/0) via the Bernstein-type inequality. While they do not consider safety constraints, we believe that similar improvement can also be applied to our framework, without significant changes in our analysis. However, since our paper mainly focuses on tackling the safety constraint for reward-fre exploration, we use the Hoeffding stppiiinn--peeeaee inequality keep the succinctness of our statements.

---

Jursage bepard Safe RW
Step peep--tteeeeee Vitueter Sttte-l
Average Reaand Sww.-Brtteeeeee
Eepected Vilietor Safe arc-ow
Aucragg homur
3900
FORL hed
122
1.50
Consprinnd gp saltaard
1930
Solo cp--nal rowas
500
R Wr-.OliRassmmm el
Oiramo bie v1
Uncrritaned uptinal ronar)
13:99 2003
Us 26
599
Morbber Epiandas
Eo6odes
The Nurbbr ppitadeen
Figure 1: Experimental results for Safe-RL-SW and Safe-RFE-SW. The left two figures show the average rewards and step-wise violations of algorithms SUCBVI, UCBVI (Azar et al., 2017), OpICMDP-bonus (Efroni al., 2020b), Triple-Q (Wei et al., 2022) and Optpess (Liu al., 2021a). The right two figures show the reward and expected violation of the policies outputted by algorithms SRF-UCRL and RF-UCRL (Kaufmann et al., 2021).
only suffers a O(1/ (N(Ss, Th (5x))) violation, the violation led by this situation is bounded by (i Ti (s1)). Next, we bound the probability that sh+1 $ A (sh: aa) for some step h E [M]. For any state-action pair (s, a), if there is a probability IPs' s, a) (log( (S/))/N (s, a)) that the agent transitions to next state s' from (s, a) at step h, the state s' is put into A (s, a) with probability at least - 8/S. Then, we can expect that all such states are put into our estimated next state set K A (s, a). Thus, the probability that sh+1 & A (sh, aq)) is no larger than Ö(S log(S/))/N) (s, a))
by a union bound over all possible next states s'. Based on this argument, W A (8h, (n)) is an upper bound for the total probability that 81+1 & A (sh: an.) for some step h. This will lead additional
K w ($1, TT (s1)) expected violation. Hence the expected violation of output policy is upper bounded
by 2W 1 (81, of (81)) S.. e. The complete proof is provided in Appendix A.
7
Experiments
In this section, we provide experiments for Safe-RL-SW and Safe-RFE-SW to validate our theoret- ical results. For Safe-RL-SW, we compare our algorithm SUCBVI with a classical RL algorithm UCBVI (Azar et al., 2017) and three state-of-the-att art CMDP algorithms OpCCMDP-bonus (Efroni et al., 2020b), Optpess (Liu et al., 2021a) and Triple-Q (Wei et al., 2022). For Safe-RFE-SW, we report the average reward in each episode and cumulative step-wise violation. For Safe-RFE-SW. we compare our algorithm SRF-UCRL with a satte-of-the-aad RFE algorithm RF-UCRL (Kaufmann et al., 2021). We do not plot the regret because unconstrained MDP CMDP algorithms do not guarantee step-wise violation. Applying them to the step-wise constrained setting can lead to negative or large regret and large violations, making the results meaningless. Detailed experiment setup is in Appendix E.
As shown in Figure 1, the rewards of SUCBVI and SRF-UCRL converge to the optimal rewards under safety constraints (denoted by "safe optimal reward"). contrast, the rewards of UCBVI and UCRL converge to the optimal rewards without safety constraints (denoted by "unconstrained optimal reward"), and those of CMDP algorithms converge to a policy with low expected violation (denoted by "constrained optimal reward"). For Safe-RFE-SW, the expected violation of output policy of SRF-UCRL converges to zero while that of RF-UCRL does not. This corroborates the ability of SRF-UCRL in finding policies that simultancously achieve safety and high rewards.
8 Conclusion
In this paper, we investigate a novel safe reinforcement learning problem with step-wise safety constraints. We first provide algorithmic framework SUCBVI to achieve both an Ó O(VH3$AA regret and an ((VST) step-wise or an O(S/Coap + S AH2)) gap-dependent bounded violation that is independent of T: Then, we provide two lower bounds to validate the optimality of SUCBVI in both violation and regret in terms of S and T. Further, we extend our framework to the safe RFE with step-wiss wise violation and provide an algorithm SRF-UCRL that identifies a near-optimal safe policy given any reward function and guarantees ((vST) violation during exploration.
10

---

Acknowledgements
This work is supported by the Technology and Innovation Major Project of the Ministry of Science and Technology of China under Grant 2020AAA0108400 and 2020AAA0108403 and the Tsinghua Precision Medicine Foundation 10001020109.
References
Joshua Achiam, David Held, Aviv Tamar, and Picter Abbeel. Constrained policy optimization. In International conference on machine learning, pp. 22-31. PMLR, 2017.
M Mehdi Afsar, Trafford Crump, and Behrouz Far. Reinforcement learning based recommender systems: A survey. ACM Computing Surveys, 55(7):1 2022.
Mohammed Alshiekh, Roderick Bloem, Rüdiger Ehlers, Bettina Könighofer, Scott Niekum, and Ufuk Topcu. Safe reinforcement learning via shielding. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
Sanae Amani, Christos Thrampoulidis, and Lin Yang. Safe reinforcement learning with linear function approximation. In International Conference on Machine Learning, pp. 243-253, PMLR, 2021.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for rein- forcement learning. In International Conference Machine Learning, pp. 263-272. PMLR, 2017.
Felix Berkenkamp, Matteo Turchetta, Angela Schoellig, and Andreas Krause. Safe model-based reinforcement learning with stability guarantees. Advances in neural information processing systems, 30, 2017.
Archana Bura, Aria HasanzadeZonuzz, Dileep Kalathil, Srinivas Shakkottai, and Jean- -ran-Francois Chamberland. Safe exploration for constrained reinforcement learning with provable guarantees. arXiv preprint 1rXiv:21/2.00888: 2021.
Yinlam Chow, Ofir Nachum, Edgar Gureez,Guzman, and Mohammad Ghavamzadeh. A lyapunov- based approach to safe reinforcement learning. Advances in neural information processing systems, 31, 2018.
Gal Dalal, Krishnamurthy Dvijotham, Matej Vecerik, Todd Hester, Cosmin Paduraru, and Yuval Tassa. Safe exploration in continuous action spaces. arXiv preprint
08757,, 2018.
Dongsheng Ding, Kaiging Zhang, Tamer Basar, and Mihailo Jovanovie. Natural policy gradient primal-dual method for constrained markov decision processes. Advances in Neural Information Processing Systems, 33:8378 0888378-3390 2020.
Dongsheng Ding, Xiaohan Wei, Zhuoran Yang. Zhaoran Wang, and Mihailo Jovanovic. Provably efficient safe exploration via primal-dual policy optimization. In International Conference on Artificial Intelligence and Statistics, 3304-3312. PMLR, 2021.
Yonathan Efroni, Shie Mannor, and Matteo Pirotta. Exploration-exploottaion in constrained mdps. arXiv preprint 0221v22003.02189, 2020a.
Yonathan Efroni, Shie Mannor, and Matteo Pirotta. Exploration-explootaaion in constrained mdps. arXiv preprint arXiv:2003.02/88, 2020h.
Ruiquan Huang, Jing Yang, and Yingbin Liang. Safe exploration incurs nearly additional sample
complexity for reward -free arXiv preprint (rXii:2206.14057 2022.
Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu. Reward-free exploration for reinforcement learning. International Conference on Machine Learning, pp. 4870 PMIR, 2020.
11

---

Krishna C Kalagarla, Rahul Jain, and Pierluigi Nuzzo. A sample-effciien algorithm for episodic finite- horizon mdp with constraints. In Proceedings of the AAAI Conference on Artificial Intelligence. volume 35, pp. 8030-8037, 2021.
Emilie Kaufmann, Pierre Ménard, Omar Darwiche Domingues, Anders Jonsson, Edouard Leurent, and Michal Valko. Adaptive reward-free exploration. In Algorithmic Learning Theory, pp. 865-891.
PMLR. 2021.
Marc Lanctot, Edward Lockhart, rean-Baptiste Lespiau, Vinicius Zambaldi, Satyaki Upadhyay, Julien Pérolat, Sriram Srinivasan, Finbarr Timbers, Karl Tuyls. Shayegan Omidshafiei, et al. Openspiel: A framework for reinforcement learning games. arXiv preprint arXiv: www.:/908.0945,, 2019.
Hoang Le, Cameron Voloshin, and Yisong Yue. Batch policy learning under constraints. In Interna- tional Conference on Machine Learning, pp. 3703-3712. PMLR, 2019.
Tao Liu, Ruida Zhou, Dileep Kalathil, Panganamala Kumar, and Chao Tian. Learning policies with zero or bounded constraint violation for constrained mdps. Advances in Neural Information Processing Systems, 34:17183-1719 2021a.
Tao Liu, Ruida Zhou, Dileep Kalathil, Panganamala Kumar, and Chao Tian. Learning policies with zero or bounded constraint violation for constrained mdps. Advances in Neural Information Processing Systems, 14:173331,799,, 2021b.
Yongshuai Liu, Jiaxin Ding, and Xin Liu. Ipo: Interior-point policy optimization under constraints. In Proceedings of the AAAI conference artificial intelligence, volume 34, pp. 4940-4947, 4947, 2020.
Pierre Ménard, Omar Darwiche Domingues, Anders Jonsson, Emilie Kaufmann, Edouard Leurent, and Michal Valko. Fast active learning for pure exploration in reinforcement learning. In Interna- tional Conference on Machine Learning, pp. 7599-7608. PMLR, 2021.
Sobhan Miryoosefi and Chi Jin. simple reward-free approach to constrained reinforcement learning. In International Conference on Machine Learning, pp. 15666-15698. PMLR, 2022.
Ian Osband and Benjamin Van Roy. On lower bounds for regret in reinforcement learning. arXiv preprint arXiv: 2016.
Shuang Qiu, Xiaohan Wei, Zhuoran Yang, Jieping Ye, and Zhaoran Wang. Upper confidence primal- dual reinforcement learning for emdp with adversarial loss. Advances in Neural Information Processing Systems, 33:15277-15287, 2020.
Ming Shi, Yingbin Liang, and Ness Shroff. A near-optimal algorithm for safe reinforcement learning under instantaneous hard constraints. arXiv preprint arXiv:2302.04335, 2023.
Thiago D Simão, Nils Jansen, and Matthijs TJ Spaan. Alwayssafe: Reinforcement learning without safety constraint violations during training. 2021.
Rahul Singh, Abhishek Gupta, and Ness B Shroff. Learning markov decision processes under constraints. arXiv preprint arXiv:2002.12435, 2020.
Aivar Sootla, Alexander Cowen-Rivers, Jun Wang, and Haitham Bou Ammar. Enhancing safe exploration using safety state augmentation. Advances in Neural Information Processing Systems, 35:34464-3443 34477, 2022.
Adam Stooke, Joshua Achiam, and Pieter Abbeel. Responsive safety in reinforcement learning by pid lagrangian methods. In International Conference on Machine Learning, pp. 9133-9143, PMLR, 2020.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Chen Tessler, Daniel J Mankowitz, and Shie Mannor. Reward constrained policy optimization. arXiv preprint arXiv:1805.11077 2018
Garrett Thomas, Yuping Luo, and Tengyu Ma. Safe reinforcement learning by imagining the near future. Advances in Neural Information Processing Systems, 34:13859-13866 2021.
12

---

Matteo Turchetta, Felix Berkenkamp, and Andreas Krause. Safe exploration in finite markov decision processes with gaussian processes. Advances in neural information processing systems, 29, 2016.
Matteo Turchetta, Andrey Kolobov, Shital Shah, Andreas Krause, and Alekh Agarwal. Safe rein- forcement learning via curriculum induction. Advances in Neural Information Processing Systems, 33:12151-12162, 2020.
Eiji Uchibe and Kenji Doya. Constrained reinforcement learning from intrinsic and extrinsic rewards. In 2007 IEEE 6th International Conference on Development and Learning, pp. 163-168. IEEE, 2007.
Akifumi Wachi and Yanan Sui. Safe reinforvement learning in constrained markov decision processes. In International Conference on Machine Learning, pp. 9797-9806. PMLR, 2020.
Akifumi Wachi, Yanan Sui, Yisong Yue, and Masahiro Ono. Safe exploration and optimization of constrained mdps using gaussian processes. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
Akifumi Wachi, Yunyue Wei, and Yanan Sui. Safe policy optimization with local generalized linear function approximations. Advances in Neural Information Processing Systems, 34:20759-20771 2021.
Yixuan Wang, Simon Sinong Zhan, Ruochen Jiao, Zhilu Wang, Wanxin Jin, Zhuoran Yang, Zhaoran Wang, Chao Huang, and Qi Zhu. Enforcing hard constraints with soft barriers: Safe reinforcement learning in unknown stochastic environments. arXiv preprint arXiv:2209. 15090, 2022.
Yixuan Wang, Simon Sinong Zhan, Ruochen Jiao, Zhilu Wang. Wanxin Jin, Zhuoran Yang. Zhaoran Wang, Chao Huang, and Qi Zhu. Enforeing hard constraints with soft barriers: Safe reinforcement learning in unknown stochastic environments. In International Conference on Machine Learning, pp. 36593-36604. PMIR, 2023.
Honghao Wei, Xin Liu, and Lei Ying. Triple-q: A model-free algorithm for constrained reinforcement learning with sublinear regret and zero constraint violation. In International Conference Artificial Intelligence and Statistics. pp. 3274-3307 PMLR, 2022.
Dongjie Yu, Haitong Ma, Shengbo Li, and Jianyu Chen. Reachability constrained reinforcement learning. International Conference Machine Learning, pp. 25636-25655. PMLR, 2022.
Ming Yu, Zhuoran Yang. Mladen Kolar, and Zhaoran Wang. Convergent policy optimization for safe reinforcement learning. Advances in Neural Information Processing Systems, 32, 2019.
Wenshuai Zhao, Jorge Peña Queralta, and Tomi Westerlund. Sim-to-real transfer in deep rein- forcement learning for roboties: a survey. In 2020 IEEE Symposium Series on Computational Intelligence (SSCI), pp. 737-744. IEEF, 2020.
13


Reviews:
[{"review_id": "ZkoGOQeYQK", "reviewer": "Reviewer_RuZi", "summary": "The paper studies an episodic constrained reinforcement learning problem with step-wise constraints on states. The authors first extend the classical UCB-VI to step-wise constraints and prove the sub-linear optimality gap and step-wise constraint violation. A lower bound is also provided to show optimal dependence on the state space size and the number of episodes. Second, the authors present a reward-free algorithm that takes nearly optimal sample complexity and subliner step-wise constraint violation during exploration. Some numerical experiments are provided to show the effectiveness of the proposed algorithms. ", "questions": "Some questions are stated in Strengths and Questions.\n\nHere are some other questions.\n\n- How the confidence bonus in Algorithm 1 is constructed? \n\n- Is there a lower bound for Algorithm 2 that shows the hardness of step-wise constraints?  \n\n- To see how the proposed algorithms deal with step-wise constraints, can the authors plot the instantaneous constraint violation? ", "limitations": "Yes. ", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "**originality**\n\n- The problem formulation follows the existing tabular constrained MDP with instantaneous constraints. The safety constraint used in this work is an inequality of a function of state. The learning objective is to minimize regret and step-wise violation. The instantaneous constraint is also studied in other papers, e.g., Safe Policy Optimization with Local Generalized Linear Function Approximations and Provable Safe Reinforcement Learning with Binary Feedback. \n\n-  The only problem assumption is the existence of an initial state that is not in the unsafe set. This assumption seems to be the weakest in the literature. Since the feasible policy has to satisfy the constraint at every step, transition dynamics can't guarantee the feasibility of the next state no matter the actions taken. So, it might not be intuitive that the feasibility has nothing to do with transition dynamics. \n\n- In the first algorithm, the authors extend the existing UCBVI by incorporating the estimation of safe and unsafe sets, and prove sublinear regret and step-wise violation. It is useful if the authors could discuss how this work differs from previous applications of UCBVI to constrained MDPs, e.g., (Amani et al., 2021), which studies linear function approximation and offers zero violation. \n\n- In the second algorithm, the authors generalize the existing reward-free algorithm to step-wise constraints, and prove nearly-optimal sample complexity.  \n\n**quality**\n\n- Most statements are clarified by remarks or proofs.\n\n- It is useful if the authors can make a more technical comparison with existing works since this paper is more theoretical. \n\n- In experiments, it might be not very fair to compare other methods that study value-based constraints. \n\n- It is less discussed about the weaknesses of the proposed method. It is useful to discuss if the proposed methods handle function approximation and provide zero constraint violation.\n\n\n**clarity**\n\n- The main results are delivered clearly, and the paper is organized well. \n\n**significance**\n\n- It is important to develop RL algorithms that can learn step-wise constraints. The authors have extended two known unconstrained RL algorithms to tabular constrained MDPs with step-wise constraints. However, step-wise constraints have been tackled in several other works, which warrant detailed comparison to show the significance of this paper. \n\n- The provided theoretical analysis and guarantees are more expected. It is less discussed new challenges of extending the existing unconstrained analysis.\n\n- The provided experiments do not seem to reflect the performance of the proposed algorithms. There is no variance in learning curves. Since all algorithms directly converge, exploration does seem to be an issue for convergence, which does not explains the adaptivity of online RL algorithms. ", "weaknesses": "- It is useful to make a more detailed comparison with existing works on constrained MDP with instantaneous constraints, especially problem assumptions. Discussing some related applications is also useful. \n\n- The technical contributions can be better explained by comparing the constrained and unconstrained ones. It is useful to highlight the main technical challenges.  \n\n- It is useful to discuss extending to large problems using function approximation and providing better violation guarantees.\n\n- For experiments, it is important to make a fair comparison with existing works on constrained MDPs with instantaneous constraints. It is also important to experiment algorithmms in a correct way by showing convergence and exploration randomness. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your time and effort in reviewing our paper!  We will be happy to answer any further questions you may have.\n\n**1. Comparison with existing works and applications**\n\nWe provide a brief summary of existing papers with instantaneous constraints and list their assumptions.\n\n**(1). Gaussian Process (GP) Structure**\n\n[1,2] propose a GP-based algorithm, which assumes that (a) the transition is known, and (b) the reward and cost functions are modeled by GPs. Based on the GP structure, they can infer the safety cost by estimating the parameters. \n\n**(2). Unbounded exploration time** \n\n[3] assumes the reward and cost have a generalized linear structure. Their algorithm explores in a safe space until a time $t^*$ when the agent explores sufficiently. However, their is no upper bound of the exploration time $t^*$ in [3]. For tabular MDP, $t^*$ can be infinite since the linear feature vectors consist of one-hot vectors.\n\n**(3). Safe action, convex feature set and known transition set**\n\n[4] considers the reward and cost functions to have a linear structure. It makes two assumptions: (a) There exists a safe action in each state, which avoids the agent go to a potentially unsafe state. (b) The feature set is a star convex set, which helps them change actions continuously. However, this makes their works infeasible in tabular MDPs: The feature set in tabular MDPs consists of one-hot vectors and is not a star convex set. Hence, the work [4] cannot solve our problem. [6] considers safe RL in linear mixture MDPs. It also contains the assumption (b), making it infeasible in tabular MDPs. Moreover, although it does not require assumption (a), it assumes the transition set $\\Delta(s,a)$ is known, which is not needed in our paper. Thus our problem is more challenging since we need to estimate $\\Delta(s,a)$ adaptively.\n\n**(4). Safety feedback oracle**\n\n[5] considers safe RL with binary safety feedback. They also assume that there is a safe action in each state. Moreover, they can receive safety feedback of $(s,a)$ by calling an oracle without taking action $a$ in state $s$. \n\nThere are other works that do not provide regret analysis [7,8]. Compared to the above works, our paper does not require any of their assumptions. \n\n**Applications**\n\nFor robotic control in complex environments, it is crucial to prevent the robot from hitting walls or falling into pools at all time. Our algorithm can be applied to train the robot and ensure that it stays safe at each step.\n\n**2. Technical comparison with existing works and challenges/novelty**\n\n(i) All previous works require strong assumptions (a) to help the agent infer the safety cost without going to an unsafe state or taking an unsafe action, and (b) to prevent the agent from getting stuck in a state. We do not require these assumptions. Instead, we estimate the cost and transition set $\\Delta(s,a)$, and update the estimated set of potentially unsafe states by a novel dynamic program adaptively. We also consider the uncertainty of inaccurate unsafe states in regret analysis.\n\n(ii) We consider the safe RFE setting. Compared to unconstrained RFE, the safety constraints make it harder for the agent to explore the environment.  We propose a new uncertainty function to bound the step-wise violation during exploration and the expected violation for the output policy  (Line 261).\n\n(iii) We establish lower bounds to demonstrate that Theorem 4.2 is minimax-optimal.  To the best of our knowledge, this is the first lower bound that shows the tradeoff between regret and violation for safe RL.\n\n**3. Function approximation and zero constraint violation**\n\nFor the function approximation, the large state space makes the estimation of $\\Delta(s,a)$ infeasible. [6] overcomes this difficulty by assuming $\\Delta(s,a)$ is known. One direction is to study whether partial information about $\\Delta(s,a)$ is sufficient. For the zero constraint violation, it is infeasible without additional assumptions since we can only receive the safety feedback by going to that state. Hence it is unavoidable to get in an unsafe state. \n\n**4. Experiments for instantaneous constraints and variance curves**\n\nSince all works for instantaneous constraints either require strong assumptions or are infeasible in discontinuous tasks, these works and ours cannot be directly compared. \n   \nAs for the variance curve, see Figure 1 in the global response. In Figure 1, We plot the first 2000 episodes since the variance is evident and most of the algorithms converge (except Triple-Q, which requires a large $T$ in theoretical results). \n\n**5. The confidence bonus in Algorithm 1**\n\nWe provide the definitions of confidence bonuses in Theorem 4.2 (Line 202). \n\n**6. Lower bound for Algorithm 2**\n\nA lower bound for Algorithm 2 (RFE) remains open. This is a very interesting direction, and we plan to study it in future work.  \n\n**7. Plot the instantaneous constraint violation** \n\nWe provide the curve of instantaneous violation in the second figure of Figure 1 in our paper.\n\nReferences:\n\n[1]. Turchetta et al. Safe exploration in finite Markov decision processes with gaussian processes. 2016\n\n[2]. Wachi et al. Safe exploration and optimization of constrained MDPs using Gaussian processes. 2018.\n\n[3]. Wachi et al. Safe policy optimization with local generalized linear function approximations. 2021.\n\n[4]. Amani et al. Safe reinforcement learning with linear function approximation, 2021.\n\n[5].Bennett et al. Provable Safe Reinforcement Learning with Binary Feedback, 2023.\n\n[6]. Shi et al. A Near-Optimal Algorithm for Safe Reinforcement Learning Under Instantaneous Hard Constraints, 2023.\n\n[7]. Wang et al. Enforcing hard constraints with soft barriers: Safe reinforcement learning in unknown stochastic environments, 2023. \n\n[8]. Thomas et al. Safe reinforcement learning by imagining the near future, 2021."}, {"review_id": "iQ1AgVA0PV", "reviewer": "Reviewer_83sH", "summary": "This paper considers online RL problem for an MDP with stage-wise constraints. The stage-wise constraints basically specify the set of unsafe states which must be avoided at all times. While there is a lot of recent work on CMDPs, this formulation, which is actually more relevant is less studied. The authors propose a variant of UCBVI algorithm, and show that it achieves O(\\sqrt{SATH^3}) regret which is order optimal except in H. It also achieves sublinear constraint violation, which is independent of T when it is gap-dependent. They also present a reward-free exploration algorithms with sublinear regret and constraint violation.\n\n ", "questions": "Could you use some of the recent work of Lei Ying and Dileep Kalathil to design algorithms that achieve even sharper results. I believe it is possible without too much extra work. ", "limitations": "N/A.", "rating": 5, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "This seems one of the few results on Online RL for MDP with stage-wise constraints. Attempt at numerical evaluation is commendable.", "weaknesses": "Unfortunately, the results are weaker than what have been achieved recently for CMDP problems: some of the formulations only consider clipped violation functions, and still achieve bounded constraint violation. The results for reward-free learning are actually much weaker as it only achieves sublinear constraint violation. Furthermore, novelty in the algorithm is limited based as it is on UCBVI, a well-trodden path. Recent work on online learning for CMDPs has several interesting algorithmic ideas which the authors could potentially use to propose algorithms for sharper results.  ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your time and effort in reviewing our paper!  Please find our responses to your comments  below. We will be happy to answer any further questions you may have. \n\n**1. Unfortunately, the results are weaker than what has been achieved recently for CMDP problems: some of the formulations only consider clipped violation functions and still achieve bounded constraint violation.**\n\nTo the best of our knowledge, [1,5] are the most related papers that consider the clipped violation $C''(K)=\\sum_{k=1}^K (\\mathbb{E}[\\sum_{h=1}^H c(s_h^k,a_h^k)]-\\mu)_+$ for a safety threshold $\\mu$. However, our results are not weaker than theirs. In particular, our step-wise constraint induces a stricter requirement as it requires the agent to stay safe **at each step with certainty** rather than in expectation over each episode.  \n\nWe will be happy to explain the differences if the reviewer has concerns about any other references. \n\n**2. The results for reward-free learning are actually much weaker as it only achieves sublinear constraint violation.**\n\nFirst of all, note that similar to the regret minimization setting, we can derive a constant constraint violation if the safety gap $\\mathcal{C}_\\mathrm{gap}>0$.\n   \nTo our best knowledge, there is only one work [4] considering safety problems in RFE. They consider RFE in the CMDP setting with expected constraints, and achieve zero violation during exploration. Compared to them, we consider a stricter step-wise constraint that requires the agent to stay safe **at each step with certainty**, and provide bounded violation guarantees. \n\n**3. Novelty in the algorithm is limited based as it is on UCBVI, a well-trodden path.**\n\nAlthough our algorithm is motivated by UCBVI, our algorithm design and analysis are novel. Compared to unconstrained RL,  we use a novel dynamic program to estimate the set of potentially unsafe states and plan for the future in each episode, avoiding going to an unsafe state in the future inevitably. In addition, since the potentially unsafe states are changing in each episode, we need to further consider the uncertainty brought by the inaccurately estimated unsafe states in regret analysis. \n\nMoreover, we consider safety problems in the RFE setting, which is an important and challenging problem in RL. Compared to unconstrained RFE problems, the agent needs to both stay safe during the exploration phase and output a nearly safe policy afterward.  Previous work for RFE in CMDP [4] cannot be directly applied to solve this problem, since they only consider expected violations during the exploration phase, and thus cannot guarantee safety for each step with certainty. We tackle this challenge by proposing a new uncertainty function defined in Eqs. (8) and (9) to upper bound both the violation during exploration and the expected violation for the output policy.\n\n**4. Recent work of Lei Ying and Dileep Kalathil**\n\nWe find two related works by these two authors. [2] designs model-free algorithms for non-stationary CMDPs, where the main framework builds upon the Triple-Q algorithm.  [3] considers doubly optimistic and pessimistic exploration to achieve zero violation when there is a safe baseline policy. These two papers are interesting but they both focus on the expected violation $C'(K)=\\sum_{k=1}^K (\\mathbb{E}[\\sum_{h=1}^H c(s_h^k,a_h^k)]-\\mu)$. Thus, their results cannot solve our step-wise constraint problems. In addition, we extend our algorithmic framework to solve the safety problem in RFE for the exploration phase and the final output policy, which is not considered in their papers.\n\n[1]. Efroni Y, Mannor S, Pirotta M. Exploration-exploitation in constrained mdps. preprint, 2020.\n\n[2]. Wei H, Ghosh A, Shroff N, et al. Provably Efficient Model-Free Algorithms for Non-stationary CMDPs, AISTATS 2023.\n\n[3]. Bura A, HasanzadeZonuzy A, Kalathil D, et al. DOPE: Doubly optimistic and pessimistic exploration for safe reinforcement learning, NIPS 2022.\n\n[4]. Huang R, Yang J, Liang Y. Safe exploration incurs nearly no additional sample complexity for reward-free rl, preprint 2022.\n\n[5]. Simao et al. AlwaysSafe: Reinforcement learning without safety constraint violations during training,2021"}, {"review_id": "OVVtmTiwID", "reviewer": "Reviewer_ryzU", "summary": "The authors propose a new formulation for the safe RL problem Safe-RL-SW, whose violation constraints are step-wise, different from the existing work. A model-based general algorithmic framework SUCBVI is proposed and the theoretical guarantees on the upper bound and lower bound of its regret are provided. The authors also propose a similar reward-free safe RL problem with step-wise violation constraints (Safe-RFE-SW) along with an algorithm SRF-UCRL, the theoretical upper bound on whose regret is provided. It is claimed to be the first result on step-wise violation constraints in the RFE setting. Experiments are provided in support of the theoretical results.", "questions": "I hope the authors can provide clarification for a few questions:\n\n1. What is the role of $n$ in Theorem 5.2? Why considers $M_1, \\cdots, M_n$ in this theorem instead of just focusing on the one MDP that establishes the lower bound?\n\n2. Do all CMDP works define violation with $C'(K)$ in Line 136? Is there any CMDP work that do not use $C'(K)$ and have a violation definition that is more comparable to the step-wise violation in this work? \n\n3. In the plot of \"Step-wise Violation in Safe-RL-SW\" of Figure 1, the cumulative step-wise violation curve for SUCBVI seems to grow much more slowly than $\\sqrt{T}$. However, shouldn't we expect something $\\Omega(\\sqrt{ST})$, especially given your lower bounds in Section 5?", "limitations": "The limitation is currently discussed in Appendix A. I encourage the authors to move part of it in the conclusion so that it is more conspicuous.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The authors propose new problem formulations for safe RL as well as algorithms under these formulations. Theoretical results are provided for the proposed algorithms. Overall, the new problem formulations seem original and the results seem significant.", "weaknesses": "How the results in this work compare with the existing work is somewhat unclear, despite some discussion in the Related Work Section. In Section 2, the authors mention two closely-related work Amani et al. (2021) and Shi et al. (2023) that also consider step-wise violation and state that more detailed comparisons can be found in Appendix B, but I did not find any comparison with these two works in Appendix B. I strongly suggest that the authors compare with all related works and clearly state how this work differentiates from them in the revision. For example, do all CMDP works define violation with $C'(K)$ in Line 136? Can you compare with the CMDP works that do not use expected violation like $C'(K)$, if there is any? As for Amani et al. (2021) and Shi et al. (2023), please explain whether there is any difference in your formulations and how your results compare with theirs, if your setting is comparable with theirs. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your time and effort in reviewing our paper.  We will be happy to answer any further questions you may have. \n\n**1. Comparison with existing works**\n\n We provide a brief summary of existing papers with instantaneous constraints and list the assumptions.\n\n**(1). Gaussian Process (GP) Structure**\n\n[1,2] propose a GP-based algorithm, which assumes that (a) the transition is deterministic and known, and (b) the reward and cost functions are modeled by GPs. By using this particular structure, they can infer the safety cost by estimating the parameters. \n\n**(2). Unbounded exploring time**\n\n[3] assumes the reward and cost functions have a generalized linear structure. Their algorithm explores in a safe space until a time $t^*$ when the agent explores sufficiently. However, the upper bound of the exploring time $t^*$ is not given in their paper. Under the tabular MDP setting, $t^*$ can be infinite since the linear feature vectors consist of one-hot vectors.\n\n**(3). Safe action, convex feature set and known transition set**\n\n[4] considers the reward and cost functions to have a linear structure. It makes two assumptions: (a) There exists a safe action in each state, which avoids the agent go to a potentially unsafe state. (b) The feature set is a star convex set, which helps them change actions continuously. However, this makes their works infeasible in tabular MDPs: The feature set in tabular MDPs consists of one-hot vectors and is not a star convex set. Hence, the work [4] cannot solve our problem. [6] considers safe RL in linear mixture MDPs. It also contains assumption (b), making it infeasible in tabular MDPs. Moreover, although they do not have assumption (a), it assumes the transition set $\\Delta(s,a)$ is known, which is not needed in our paper. Thus our paper is more challenging since we need to estimate $\\Delta(s,a)$ in our algorithm adaptively.\n\n**(4). Safety feedback oracle**\n\n[5] considers safe RL problems with binary safety feedback. They also assume there is a safe action in each state. Moreover, they can receive safety feedback of $(s,a)$ by calling an oracle without taking action $a$ at state $s$. \n\nThere are also other related works that do not provide regret or sample complexity analysis [7,9], so we do not provide a technical comparison. In contrast, our paper does not require any of these assumptions. \n\n\n**2. Other CMDP formulation**\n\nMost CMDP works focus on the **expected violation**, i.e., $C'(K) = \\sum_{k=1}^K (E[\\sum_{h=1}^H c(s_h^k,a_h^k)]-\\mu)$ \nto define their constraints. [10,11] consider the **clipped expected violation** \n$C''(K)=\\sum_{k=1}^K (E[\\sum_{h=1}^H c(s_h^k,a_h^k)]-\\mu)_+$, which is a slightly stricter constraint than the expected violation. \n \nDifferent from previous works, we consider the step-wise violation $$C(K)=\\sum_{k=1}^K \\sum_{h=1}^H (c(s_h^k)-\\tau)_+,$$ \n\nwhich enforces the safety at each step. The clipped expected violation $C''(K)$ in [10,11] cannot guarantee the safety at each step with certainty, since in the definition of $C''(K)$, the average violation at each step $c(s_h^k,a_h^k)-\\mu/H$ can be positive or negative, and they can cancel out to get $E[\\sum_{h=1}^H c(s_h^k,a_h^k)]\\le \\mu$. \n\n**3. Comparison for [4,6].**\n\nAs we mentioned in Reply 1, [4,6] cannot work for tabular MDPs. Moreover, [4] requires an assumption that there exists a safe action in each state, while [6] needs known $\\Delta(s,a)$. In our work, we do not require these assumptions. Hence, their works and ours cannot be directly compared.\n\n**4. Why consider n MDPs instead of focusing on one MDP for the lower bound?**\n\nIf we just focus on one MDP M, it is impossible to derive a lower bound for M: If the algorithm guesses the optimal policy $\\pi^*$ for a MDP correctly and takes $\\pi^*$ all the time, it can achieve zero regret and violation on M. Therefore, to construct the lower bound, we must consider multiple MDPs, so that no algorithm can always take the optimal policies for all MDPs because the optimal policies are different.  Then, one can prove that the algorithm does not work well in one of them. This construction idea has been used in many prior works for different problems, e.g., [8,12]. \n\n**5. The cumulative violation curve grows more slowly than $\\sqrt{T}$.**\n\nTheorem 4.2 shows that if the safety gap $C_\\text{gap}>0$, we can get a bounded $\\tilde{O}(S/C_\\text{gap}+ S^2AH^2)$ violation. In our experiment, the safety gap is large, and our curve matches this result. \nHowever,  the lower bound Theorem 5.1 is constructed by the worst instance with safety gap $C_{\\text{gap}}= O(\\sqrt{S/T})$ in the construction. This safety gap is small and changes for different numbers of episodes $T$, which is not the setting of our experiment.\n\n**References:**\n\n[1]. Turchetta et al. Safe exploration in finite Markov decision processes with gaussian processes. 2016.\n\n[2]. Wachi et al. Safe exploration and optimization of constrained MDPs using Gaussian processes. 2018.\n\n[3]. Wachi et al. Safe policy optimization with local generalized linear function approximations. 2021.\n\n[4]. Amani et al. Safe reinforcement learning with linear function approximation, 2021.\n\n[5].Bennett et al. Provable Safe Reinforcement Learning with Binary Feedback, 2023.\n\n[6]. Shi et al. A Near-Optimal Algorithm for Safe Reinforcement Learning Under Instantaneous Hard Constraints, 2023.\n\n[7]. Wang et al. Enforcing hard constraints with soft barriers: Safe reinforcement learning in unknown stochastic environments, 2023. \n\n[8]. Simchowitz et al. Non-asymptotic gap-dependent regret bounds for tabular mdps, 2019.\n\n[9]. Thomas et al. Safe reinforcement learning by imagining the near future, 2021.\n\n[10]. Efroni et al. Exploration and exploitation in CMDP, 2020.\n\n[11]. Simao et al. AlwaysSafe: Reinforcement learning without safety constraint violations during training, 2021.\n\n[12] Domingues et al. Episodic reinforcement learning in finite mdps: Minimax lower bounds revisited, ALT 2021."}, {"review_id": "tWbiPFcGvw", "reviewer": "Reviewer_ZGMh", "summary": "This paper formulates and studies a strict step-wise violation constraint reinforcement learning problem, where a non-negative state-dependent cost is cumulated at each step. They show lower bounds for regret and safety violations. A model-based algorithm that matches the lower bound is provided, while another O(1) gap-dependent violation is provided too. They also study the reward-free problem and provide an algorithm that has a sample complexity with a leading term matching the SOTA of a no-constraint case.", "questions": "See weakness.", "limitations": "Part of the limitations are shown. The authors don't discuss the limitations of state-dependent cost as well as the weird reward-free setting.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "The step-wise violation constraint problem is meaningful. This paper is technically sound. The proofs are correct as far as I can tell. The empirical result looks good.", "weaknesses": "1. The idea of the unsafe set can only apply to state-dependent safety problems. I doubt this technique can apply to a (state, action)-dependent safety problem. Additionally, it is weird that the reward is (state, action)-dependent, but the cost is state-dependent only.\n2. It is weird that the reward-free can give cost feedback.\n3. Definition 6.1 is confusing. I guess from your proof that \\pi in (4) means all feasible policies defined by \\Delta and U?\n4. line 545, '<' should be '>'?\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your time and effort in reviewing our paper!  Please find our responses to your comments below. We will be happy to answer any further questions you may have. \n\n\n**1. Can the cost be (state, action)-dependent?**\n\nThe reason why we choose the state-dependent cost is to follow the setting in previous works [1,2,3] for step-wise constraints. \n    \n   Extending our framework to (state, action)-dependent cost is not difficult. Intuitively, we can define a state $s$ is unsafe when $\\max_{a \\in \\mathcal{A}}c(s,a) \\le \\tau$. Then, in each state $s$, we can also use the uniform exploration to choose the action and estimate $c(s,a)$. It only leads to an extra $A$ factor in regret and violation. \n   \n\n**2. It is weird that the reward-free can give cost feedback.**\n\n   The motivation of RFE is that, since the reward functions are often engineered and changed in practice, we need an algorithm to explore the environment and work well for different rewards [4]. In many real-world scenarios such as robot control, the cost function depends on the environment, which does not change frequently. Hence, it is natural that we can receive the cost feedback without the reward signal. This setting is also considered in previous works for safe RFE, e.g., [5]. \n\n**3. Definition 6.1 is confusing**\n\nThanks for pointing out this confusion. $\\pi$ in Eq.(4) denotes any feasible policies in $\\Pi$ with respect to true $\\Delta(s,a)$ and $\\mathcal{U}$. Note that $\\Pi^K$ is feasible with respect to $\\hat{\\Delta}^K(s,a)$ and $\\mathcal{U}^k_H$, thus $\\Pi^K\\subseteq \\Pi$ by  optimism. We will improve the explanation in our revision. \n\n**4. Typo**\n\n   The equation under Line 545 is $\\ge$. We will fix this typo in our revision.\n\n**References:**\n\n[1]. Wachi, A., Sui, Y., Yue, Y., and Ono, M. Safe exploration and optimization of constrained\nMDPs using Gaussian processes. AAAI 2018.\n\n[2]. Wachi A, Wei Y, Sui Y. Safe policy optimization with local generalized linear function approximations[J]. Advances in Neural Information Processing Systems, 2021\n\n[3]. Wang Y, Zhan S S, Jiao R, et al. Enforcing hard constraints with soft barriers: Safe reinforcement learning in unknown stochastic environments, ICML 2023. \n\n[4]. Jin C, Krishnamurthy A, Simchowitz M, et al. Reward-free exploration for reinforcement learning, ICML 2020.\n\n[5]. Huang R, Yang J, Liang Y. Safe exploration incurs nearly no additional sample complexity for reward-free rl, 2022."}, {"review_id": "M59JikXSyz", "reviewer": "Reviewer_31rE", "summary": "This paper studies safe RL with step-wise violation constraints, different from the popular CMDP with\nan additive expectation cost constraint. The step-wise violation constraint is more suitable for safety-critical\nsystems. The authors propose an algorithm that provides violation and regret bound. They then further\ndevelops an algorithm to learn a near-optimal safe policy and show its effectiveness in the experiments.\n\n", "questions": "I am using a Windows laptop and I cannot open the full_paper file (format) in the supplementary folder, so I cannot see the limitations of the approach.", "limitations": "I would like to authors to clarify the limitations of their formulation and approach in the response. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1) This paper studies an important problem. The paper is well-written and easy to follow. \nThe RL with step-wise violation constraint, as a formulation, is novel and more general than the popular CMDP with an additive expectation constraint. \n2) The proposed approach looks correct and sound to me although I didn't check every proof. \n3) The authors provide theoretical analyses of violation and regret bound. \n4) The proposed safe RL algorithm achieves better performance than the existing baselines.", "weaknesses": "1. This paper may miss some reference for safe RL with step-wise violations such as\n\na) Wang, Y., Zhan, S. S., Jiao, R., Wang, Z., Jin, W., Yang, Z., ... & Zhu, Q. (2022). \nEnforcing Hard Constraints with Soft Barriers: Safe Reinforcement Learning in Unknown Stochastic Environments. \narXiv preprint arXiv:2209.15090.\n\nThe authors have to at least discuss this paper in this work as the timepoint-level \"hard chance constraint\" looks very similar to the step-wise violations proposed by the authors. \n\n2. In the MDP model, it is not clear to me whether the paper solves safe RL with continuous/discrete deterministic/stochastic\nsystems or environments. The transition set \\Delta_h(s, a) could be an infinite set when considering continuous state space. \n\n3. Essentially, my understanding of this paper is that they are dealing with discrete action and state space, and because of this,\nthe RL agent can infer which state and/or future state is unsafe to visit by building the A_safe set via dynamical programming. \nwhich is the core of the proposed algorithms. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your time and effort in reviewing our paper! We really appreciate your positive comments about our work. Please find our responses to your comments below. We will be happy to answer any further questions you may have. \n\n\n**1. Discuss with [3].**\n\n[3] considers the same step-wise constraint as ours. They solve step-wise constraints via  learning a generative-model-based soft barrier function. To be more specific, they use a soft barrier function to encode the constraint of the surrogate model provided by the generative model. They learn the generative model as a discrete-time SDE. \n\n   There are two major differences between [3] and our work: (a) They can only solve the continuous dynamics (stated in Assumption 3.1 in [3]), while we consider discontinuous tabular MDPs. (b) They focus on the empirical side and do not obtain any theoretical guarantees, while we focus on the theoretical side and provide rigorous regret analysis and lower bounds. \n\n\n**2. Continuous space**\n    \n\n        \n   We agree that it is interesting and challenging to extend our framework to continuous state space since $\\Delta(s,a)$ is infinite there. [2] avoids this problem by assuming $\\Delta(s,a)$ is known. An important future direction is to study whether partial information of $\\Delta(s,a)$ is sufficient, instead of the entire $\\Delta(s,a)$. Moreover, we want to emphasize that previous works [1,2] cannot solve the safety problem on tabular MDPs: They assume the linear feature set is star and convex (Assumption 5 in [1] and Assumption 2 in [2]), which does not hold in tabular MDPs since the feature set in tabular MDP consists of one-hot vectors. \n   \n   We emphasize that our problem is challenging and novel. In fact,  [3] states that discontinuous  MDP  still remains challenging, even if the setting of continuous state space is solved. Thus, our results for tabular and discontinuous MDPs are significant.\n\n\n\n**3. Cannot open the full paper file**\n\n   The \"full$\\\\_$paper\" file can be opened by adding a \".pdf\" suffix. Thanks for pointing out this issue. We will fix it in our revision.\n\n   **Here we describe the limitation of our paper.** \n   First, Algorithm 1 will suffer a non-zero step-wise violation in the beginning. This non-zero violation is unavoidable, because the agent has no information about unsafe states to begin with. Second, in some real-world environments, the number of states and actions can be large and even infinite. Thus, the complexity of our algorithm can be high. To overcome this challenge, one interesting direction is to extend our work to the function approximation setting, such as linear MDP [4].\n\n   \n**References:**\n\n[1]. Amani S, Thrampoulidis C, Yang L. Safe reinforcement learning with linear function approximation, ICML, 2021.\n\n\n[2]. Shi M, Liang Y, Shroff N. A Near-Optimal Algorithm for Safe Reinforcement Learning Under Instantaneous Hard Constraints, arXiv preprint, 2023.\n\n[3]. Wang Y, Zhan S S, Jiao R, et al. Enforcing hard constraints with soft barriers: Safe reinforcement learning in unknown stochastic environments, ICML 2023.\n\n[4]. Jin C, Yang Z, Wang Z, et al. Provably efficient reinforcement learning with linear function approximation, COLT 2020."}]

Author rebuttal:
Thanks for the responses of all the reviewers! The experiment curve with variance is attached in the PDF. We only plot the first few
episodes to show the variance of each algorithm more clearly.

Meta-review: The paper explores reinforcement learning with rigorous step-wise violation constraints, wherein a state-dependent, non-negative cost accumulates at each decision-making step. It establishes lower bounds for both regret and safety violations and presents a model-based algorithm that meets these lower bounds. An additional algorithm with a constant gap-dependent violation is also offered. The authors further examine the reward-free case, introducing an algorithm with a leading-term sample complexity that matches the state-of-the-art for cases without constraints. The paper also provides experiments to justify the theory.

**Reasons to Accept:**
The paper studies an important problem and the proposed stepwise violation constraint setting is novel. The theoretical results are reasonable and experiments are also adequate.  However, reviewers do find that the theoretical contributions are limited and can be improved to, e.g., zero constraint violation.
Decision: Accept (poster)