Safe Exploration Incurs Nearly No Additional Sample Complexity for Reward-Free RL
Authors: Ruiquan Huang
Jing Yang
Yingbin Liang
Venue: ICLR 2023 poster (2023)
Keywords: Reward-free RL
Safety constraint
Sample complexity
Pure exploration

Abstract: Reward-free reinforcement learning (RF-RL), a recently introduced RL paradigm, relies on random action-taking to explore the unknown environment without any reward feedback information. While the primary goal of the exploration phase in RF-RL is to reduce the uncertainty in the estimated model with minimum number of trajectories, in practice, the agent often needs to abide by certain safety constraint at the same time. It remains unclear how such safe exploration requirement would affect the corresponding sample complexity in order to achieve the desired optimality of the obtained policy in planning. In this work, we make a first attempt to answer this question. In particular, we consider the scenario where a safe baseline policy is known beforehand, and propose a unified Safe reWard-frEe ExploraTion (SWEET) framework. We then particularize the SWEET framework to the tabular and the low-rank MDP settings, and develop algorithms coined Tabular-SWEET and Low-rank-SWEET, respectively. Both algorithms leverage the concavity and continuity of the newly introduced truncated value functions, and are guaranteed to achieve zero constraint violation during exploration with high probability. Furthermore, both algorithms can provably find a near-optimal policy subject to any constraint in the planning phase. Remarkably, the sample complexities under both algorithms match or even outperform the state of the art in their constraint-free counterparts up to some constant factors, proving that safety constraint hardly increases the sample complexity for RF-RL.

Published as a conference paper at ICLR 2023
SAFE EXPLORATION INCURS NEARLY No ADDITIONAL SAMPLE COMPLEXITY FOR REWARD-FREE RL
Ruiquan Huang
Jing Yang
The Pennsylvania State University rzh551 @psu..ue.. edu
The Pennsylvania State University yang ng@psu edu
Yingbin Liang
The Ohio State University 1 liang. 8990osu. edu
ABSTRACT
Reward-free reinforcement learning (RF-RI), a recently introduced RI, paradigm, relies on random action-taking to explore the unknown environment without any reward feedback information. While the primary goal of the exploration phase in RF-RL to reduce the uncertainty in the estimated model with minimum number of trajectories, in practice, the agent often needs to abide by certain safety constraint at the same time. It remains unclear how such safe exploration requirement would affect the corresponding sample complexity in order to achieve the desired optimality of the obtained policy in planning. this work, we make a first attempt to answer this question. In particular, consider the scenario where safe baseline policy is known beforehand, and propose a unified Safe re wardd frEe ExploraTion (SWEET) framework. We then particularize the SWEET framework to the tabular and the low-rank MDP settings, and develop algorithms coined Tabular-SWEET and Low-rank-SWEET, respectively. Both algorithms leverage the concavity and continuity of the newly introduced truncated value functions, and are guaranteed achieve zero constraint violation during exploration with high probability. Furthermore, both algorithms can provably find near- vettmoltimal policy subject any constraint in the planning phase. Remarkably, the sample complexities under both algorithms match or even outperform the state of the art in their constraint-free counterparts up to some constant factors, proving that safety constraint hardly increases the sample complexity for RF-RI.
INTRODUCTION
Reward-free reinforcement learning (RF-RL) is RL paradigm under which learning agent first explores an unknown environment without any reward signal in the exploration phase, and then utilizes the gathered information to obtain near-optimal policy for any reward function during the planning phase. Since formally introduced in Din et al. (2020b), RF-RL has attracted increased attention in the research community (Kaufmann et al. 2021 ZZhan et al.) 2020 2021 Wang et al.. 2020, Modi et al. 202T). It is particularly attractive for applications where many reward functions may be of interest, such multi-objective RL (Miryoosefi & Jin 2021). or the reward function not specified by the environment but handcrafted in order to incentivize some desired behavior of the RL agent (Jin et al. 2020b).
The ability of RF-RL to identify near-optimal policy in response to arbitrary reward function relies on the fact that the agent is allowed explore any action during exploration. However, in practice, unrestricted exploration is often unrealistic or even harmful. In order to build safe, responsible and reliable artificial intelligence (AI), the RL. agent often has abide by certain application-dependen constraints, even during the exploration phase. Two motivating applications are provided as follows.
Autonomous driving, In order to learn a npar-optimal driving strategy, an RL agent needs to try various actions different states through exploration. While RF-LL is appealing approach as the reward function is difficult to specify, it is of critical importance for the RL agent to take safe actions (even during exploration) in order avoid catastrophic consequences.

---

Published as a conference paper at ICLR 2023
Cellular network optimization. The operation of cellular network needs to take diverse corpus of key performance indicators into consideration, which makes RF-RL a plausible solution. Mean- while, the exploration also needs to meet certain system requirements, such as power consumption.
While meeting these constraints throughout the learning process is pressing need for the broad adoption of RL in real-world applications, it is mission impossible to accomplish if no other information provided, as the learner has little knowledge of the underlying MDP at the beginning of the learning process and will inevitably take undesirable actions (in hindsight) and violate the constraints. On the other hand, various engineering applications, there often exist either rule-based (e.g., autonomous driving) or human expert guided (e.g., cellular network optimization) solutions to ensure safe operation of the system. One natural question is, is it possible to leverage such existing safe solutions to ensure safety throughout the learning process? If so, how would the safe exploration requirement affect the corresponding RF-RL performances in terms of the sample complexity of exploration and the optimality and safety guarantees of the obtained policy in planning?
To answer these questions, in this work, we introduce a new safe RF-RL framework. In the proposed safe RF-RL framework, the agent does not receive any reward information in the exploration phase, but is aware of a cost function associated with actions at a given state. We require that the cumulative cost in each episode is below a given threshold during exploration, with the aid of a pre-existing safe baseline policy π". The ultimate learning goal of safe RF-RL is to find a safe and near-optimal policy for any given reward and cost functions after exploration.
Main contributions. We summarize our main contributions as follows.
First, we introduce a novel safe RF-RL framework that imposes safety constraints during both exploration and planning RF-RL, which may have implications in various applications.
Second, we propose unified safe exploration strategy coined SWEET to leverage the prior knowledge of safe baseline policy nO. SWEET admits general model estimation and safe exploration policy construction modules, thus can accommodate various MDP structures and different algorithmic designs. Under the assumption that the approximation error function is concave and continuous in the policy space, SWEET is guaranteed to achieve zero constraint violation during exploration, and output a near-optimal safe policy for any given reward function and safety constraint under some assumptions in planning. both with high probability.
Third, in order to facilitate the specific design of the approximation error function to ensure its concavity, we introduce a novel definition of truncated value functions. It relies on new clipping method to avoid underestimation of the approximation error captured by the corresponding value function, and ensures the concavity of the resulted value function.
Finally, we particularize the SWEET algorithm for both tabular and low-rank MDPs, and propose Sabular-SWEET and Low-rank-SWEET, respectively. Both algorithms inherit the optimality guarantee during planning, and the safety guarantees in both exploration and planning. Remarkably, the sample complexities under both algorithms match or even outperform the state of the art of their constraint- free counterparts up to some constant factors, proving that safety constraint incurs nearly additional sample complexity for RF-RL.
2
PRELIMINARIES AND PROBLEM FORMULATION
2.1 EPISODIC MARKOV DECISION PROCESSES
We consider episodic Markov decision processes (MDPs) in the form of M (1, where S is the state space and A is the finite action space, H is the number of time steps in each episode, P (Pr) H
collection of transition kernels, and Pa 8/, oz) denotes the transition probability from the state-action pair (81, at step h to state 8h+1 in the next step. Without loss of generality, we assume that each episode of the MDP, the initial state is fixed at 81- In addition, an MDP may be equipped with certain specified utility functions u = {un ) where we assume Un : x A + [0, 1] is a deterministic function for case of exposition.
A Markov policy is a set of mappings {TAA : S ( where (AA) is the set of all possible distributions over the action space A. In particular, Fy (als) s)ss denotes the probability of selecting action in state at time step h. We denote the set of all Markov policies by X. For agent adopting policy π in an MDP M, at each step h E [H] where [H] == {1...., H). she observes state s, E S, and takes action d4 A according to æ, after which the environment transits to the next state 8
2

---

Published as a conference paper at ICLR 2023
with probability Pr(sh+1 18h, az.). The episode ends after H steps, and virtual state 5 to denote the terminal state at step H + 1. We use R.,, to denote the expectation of the distribution induced by the transition kernel P and policy x.
Let P,u. ah) and (s.)) be the corresponding action- value function and value func- tion at step h, respectively, for a given collection of utility functions u. Then, VI..P..(M)) == Ep, -h (sw, aw)) [s.]. and Qi, an) == EP En uy aw) 8h, an). We also use the shorthand V. to denote (s1) due to the fixed initial state, and Pr an) = (---)r [sx+1)] for any function f S - I. We further assume that the utility functions are normalized such that for any trajectory generated under a policy, the cumulative value over one episode is bounded by 1, i.e., Σx=1 Up (Sn, 4x)= S 1.
2.2 SAFE REWARD- FREE REINFORCEMENT LEARNING
The safe policy considered in this work is formally defined as follows.
Definition 1. Given an MDP M (8, A, Pt, H, 81), a set of cost functions c. {ch 1 T E (0, 1), a policy π is (c, -safe Vp p. ST
h= and
Based on this definition of (c, T) -safe policies, we now elaborate the proposed safe RF-RL framework, which contains two phases. In the first phase of "exploration", the agent is required to efficiently explore the unknown environment without reward signals, and simultaneously not to violate a predefined safety constraint (c, r) in each episode during this exploration phase. Let T(7) be the policy implemented in the n-th episode of the exploration. Then the agent's exploration should satisfy the safety constraint in every episode with high probability, namely,
P
[V TT Vn
[N] 2 1
where 5 E (0, 1) and N is the total number of episodes in the exploration phase. Note that the agent only given set of cost functions e but not the reward in this phase. This reasonable for many RL applications, where the purpose of exploration is not to maximize certain reward but to learn the environment, while the safety constraint need to be satisfied throughout the learning process.
In the second phase of "planning". the agent is given an arbitrary set of reward functions r" and new set of safety constraint (c",T*) 7*). Without further exploration, she is required to learn an e-optimal policy & with respect to the given reward r", and subject to the safety constraint (c",7").
Definition 2. Given an MDP M (S, A, P", s1). reward functions r", cost functions e* and r" E (0, 1]. 7 is an c-optimal (c", 7 -sae policy if
V - Vpr,.- S and V p-, ST¹ where e E (0, 1), and n² is the policy satisfying x = arg max, VT-..- S.t. Vj-..= ST
The design goal of safe RF-RI algorithms is three-fold: 1) to collect as few sample trajectories as possible, 2) to satisfy the safety constraint (c, in the exploration phase, and 3) to obtain an e-optimal (c", --aae policy for any given reward r" and constraint (c", in the planning phase.
We note that is impossible to ensure zero constraint violation with high probability during explo- ration if an agent starts with no information about the system. Therefore, we make the assumption that a safe baseline policy is available to the learning agent during exploration. Besides, we also assume the constrained MDP always has enough feasible solutions, either during exploration or planning.
Assumption 1 (Feasibilityy. The agent has knowledge of a baseline policy TO and E (0, such that VT= margin, defined as A(c, r) := T min, V/-..c is bounded away from zero, i.e. A 7) 2 A Amin >
0 < T K. Besides, for any given constraint (c, r) in exploration or planning phases, the safety
We remark that assuming the existence of a safe baseline policy is reasonable in practice. Many engineering applications already have existing solutions deployed and verified to be safe, although their reward performances may not necessarily be near-optimal. Such solutions can naturally serve as the baseline for safe RF-RL. Additionally, there are practical ways construct safe baseline policies, e.g., via imitation learning using expert demonstrations, or via policy gradient algorithms to reduce the cost value function to be below the required safety threshold. This assumption is also widely adopted in the safe RL literature (see Section for more discussions).
3

---

Published as a conference paper at ICLR 2023
3 THE SWEET FRAMEWORK
Compared with constraint- free RF-RL, the additional safety requirements during both exploration and planning bring two main challenges in the design of safe RF-RL algorithms. First, in order to obtain an e-optimal policy for any given reward during planning. it requires all actions to be sufficiently covered in the exploration phase. In particular, uniform action selection is one of the enablers for reward-free exploration when the state space is undesirably large (Agarwal et al. 2020 [ehara et al. 2021: Modi et al. 2021). ). On the other hand, the predefined safety constraint (c, T) may preclude the agent from taking certain actions in exploration, which may affect the estimation accuracy of the environment and degrade the optimality of the output policy in planning. This dilemma requires novel design to balance safety and state- acte-nction space coverage during exploration. Second, there may exist safety constraint mismatch between exploration and planning. Intuitively, the information obtained under a given set of constraint (c. r) during exploration may not provide enough coverage for the optimal policy under another set of constraint (c", TT) during planning. How to design the safe exploration algorithm to handle such constraint mismatch is non-trivial.
In this section, we introduce unified framework for safe reward-free exploration, termed as SWEET. We will show that the general framework achieves the second and third design objectives, i.e., safe exploration, and e-optimality and (c",T*) -*)-safety for the output policy in planning. The first design objective, i.e., low sample complexity for exploration, is dependent on the underlying MDP structure and will be investigated in Section and Section 5 for tabular MDPs and low-rank MDPs, respectively.
3.1 ALGORITHM DESIGN
The SWEET framework relies on several key design components, namely, the (Co. t)- f)-greedy policy, the approximation error function, and the empirical safe policy set, as elaborated below.
Definition 3 ((eg. -)-gredyy policy). Given eD E (0, 1) and t E {0, 1, H). x' is an (co, t) --rredy version of π if there exists H. C [H] with [H]] = such that TH, = Ty for all h & H. and
(als)) = (1 ET) (als) + eo/\ |A wh E H. E S, A.
Essentially, under (co, tg-geedd version of given policy æ, the agent follows policy я except for t out of H steps, at which with probability 6o, she takes actions uniformly at random from the state space A. One critical property of the (so, .ggreedy policy is that, the difference between the value functions under the (Co. t) -l-greedy policy and its original policy is bounded by eot for any normalized utility function (See Lemma [ Appendix[A)
(
The approximation error function U(P, T) measures the uncertainty in the model estimate P under a policy и. Specifically, for given MDP M u(P, v) upper bounds the value function difference under P and P", i.e. U(P x) 2 max, IV P.u. - VV..ul .ll where u is a normalized utility function.
The empirical safe policy set, which is critical for constructing safe exploration policies, is defined as
(,²), if V + U(P,x 9)) 2 Eat- R.
Cp.u(R, ED.
(3)
T: (T: + -((, S - -eot)
otherwise,
where R, en and / are constants satisfying the condition that cgl - R
The intuition behind the construction of the empirical safe policy can be explained as follows (Liu et al. 2021): : if V + U(P,T') 2 r cot - R, it indicates that P is not sufficiently accurate. Thus, the empirical safe policy set only contains the safe baseline policy TO. On the other hand, VE" + U(P, ) < r - enl - R, which happens when U(P, x0) is sufficiently small, it indicates that P is sufficiently accurate on 0 Then, we relax the constraint on V + +((P,)) P.c
.) from 7 -cot -ot--o R to T -- eet include T and other policies in the empirical safe policy set. Since V + U(P T) is an upper bound of the true value VB-,c for any ग, it ensures that Vp-,c < - egl for all π included in Cp.u- Moreover, all (Eo, t)) -greedy versions of such policies satisfy the safety constraint (c, T).
With those salient components, SWEET proceeds as follows. At the beginning of each episode, the agent executes set of behavior policies, which are (co, !)-greddy versions of reference policy
4

---

Published as a conference paper at ICLR 2023
TT obtained in the previous episode. For the first episode, the reference policy would be x The general construction of T, will be elaborated below. By collecting trajectories generated under the behavior policies, the agent updates the estimated model P and the corresponding approximation emrrr function .),,)).
The agent then seeks a reference policy 7, that maximizes the approximation error U(P, π) within the constructed empirical safe policy set. Intuitively, U(P, π) is upper bound of certain distance of distributions trajectories induced by under P and P Therefore, म, induces distribution that captures the most uncertainty in P. Choosing सy thus reduces the uncertainty in P in a greedy fashion. If U(P, mT) is less than a termination threshold defined in SWEET, indicates that estimated model is sufficiently accurate for the planning task. The exploration phase then terminates. Otherwise, the agent continues to the next episode with the new ,..
After termination, SWEET enters the planning phase and receives arbitrary reward functions r" and a safety constraint (c"; T*). The agent utilizes P to compute a policy म, which maximizes p.y- subject to an empirical safety constraint V + UUP, T) T
Algorithm has the detail of SWEET.
Algorithm SWEET (Safe ReWard FrEE ExploraTion)
1: Input: Reference policy n. uncertainty function U, Eo, 4, R and T.
2: // Exploration:
3: while TRUE do
4: Construct a set of (co, t)-gredyy policies of T. (see Definition 3 and use them to collect data;
5: Model estimation: Update P using collected data;
6: Obtain म. arg (f. U(P, T) where Cr, co. t) is defined in Equation
7: if V
P.c + +U(P, TD) S eut R and U(P, TT) I then
8: Output P: break;
9: end if
10: end while
11: // Planning:
12: Receive reward function r* and a safety constraint T²),
13: Output: म = arg max, V.,-- s.t. Vp.c. + U(P S
3.2
THEORETICAL ANALYSIS
Before we present the theoretical guarantee for SWEET, we first introduce the notion of mixture policies and equivalent policies and characterize the concavity over Markov policy space.
Definition 4. Given two Markov policies n' E X, we use 7 + (1 - () to denote the mixture policy that uses π with probability 7 and uses T' with probability Definition 5. Given an MDP M, two policies, including mixture policies, are equivalent if they induce the same marginal distribution over any state-action pair (a, s) in any step [H]].
during an episode.
By Theorem 6.1 in Altman 1999), for any mixture policy yæ @ (1 (1-7) there exists an equivalent Markov policy > (T, T') E For ease of presentation, in the following, we simply use n² to denote it when the definition is clear from the context. Therefore, the Markov policy space X' is equipped with an abstract convexity by mapping all mixture policies to their equivalent Markov policies in X' With this convexity,
define concave functions X' follows.
Definition 6. A function f X + j0, 1] is concave and continuous on the Markov policy space X' if for any ग. x' E X and ? [o, 1), f(T") 2 (f())
(='), and continuous y [0. 1).
With Definition 6 we have the following result of SWEET.
Theorem (e-optimality and safety guarantee SWEET). Given an MDP M and model estimate P. assume U(P, πT) is concave and continuous over the Markov policy space X and V -V $ U(P,m x) for any normalized utility u and policy and Assumption holds. Let cu, and R be T-e ((A(c.))cot--R) and
constants that satisfy egl + R < k. Let 11 min Amtn
eAmin
((Ae.)))
5

---

Published as a conference paper at ICLR 2023
T I (A(c,T) eat))// be the termination condition of SWEET. If SWEET terminates in finite episodes, then, the following statements hold:
(i) The exploration phase is safe.
(ii) The output 7 of SWEET in the planning phase is an c-optimal (c", > policy.
The detailed proof of Theorem
deferred to Appendix A We highlight the main idea behind the analysis follows. While the construction of Cppp( 60, () ensures safe exploration, the ability for SWEET to find an c-optimal (c", >=")ae policy in planning relies on the concavity and continuity of U( ()...) Note that when SWEET terminates, it only guaranteed that the approximation error U(P, T)) is upper bounded by T for the policies within Cpp co, t). Due to possibly different constraint in planning, it is desirable to have u(P,*) x) sufficiently small under any H, so that the agent is able to achieve the learning goal in planning with the estimated model P. Let स arg max, U(P, x), xT' be the equivalent Markov policy of y @ (1 - >) f()) U(P, i and g(7) p Then, is
T-fof 2.
r(v)
2000- DO0
20
700-700
Figure 1: proof.
Illustration of the
The definition of (,, (.. ensures that F(0) S T -egt K, and F()) Tot if M lies in Cp.y-
concave and is linear in by Theorem 6.1 in Altman (1999). Let f()+
suffices to consider the case when F(1) > Epl, under which we can show that both g and F(*)-P10)
increase with 7. Then, the concavity of and linearity of g ensure that f(x)-f(0)
f(1)-(()) 2 F(1 -(1) as illustrated in Figure [ Let 70 be the policy under which F(70) T Egt. Then, (11))=((0))
Combining with the fact that [11 - F(0) < 2, we have f(1) S f(0) + (f(ro) f(0) S 2T/R,
which provides an upper bound on U(P, π7) for any x.
3.3 TRUNCATED VALUE FUNCTION
Theorem I highliight the importance of the concave and continuous approximation error function on the Markov policy space. In the following, introduce prototype function, coined truncated value function, which is concave and continuous on the Markov policy space and can be used for the construction of the approximation error functions for both tabular and low-rank MDPs.
Definition 7 (Truncated value function). Given an MDP M, > 0, and set of (un-normalized) utility functions u, the truncated value function p.
V. V.P,, (s1) X + RR defined as follows:
Qu.P, (sh, aN) = u(sh, an) + aPP Va.
P, (sk, an),
vas (s)) min {
1, O (sn, an)
where VM-F1, P, (SH+4) = and we omit the upper index a for simplicity when a
is worth noting that the clipping technique is applied to the value function as opposed to the action-value function, where the latter is more conventional in the existing literature. This new method is critical for achieving the superior sample complexity in safe RF-RL, as will be elaborated later. Meanwhile, it preserves the desired concavity and continuity (see Lemma 3 in Appendix Ap. which ensures the safety guarantee for both exploration and planning.
THE TABULAR-S RRULAR-SWEET ALGORITHM
4.1 ALGORITHM DESIGN
Under tabular MDPs, state space S and action space AA are both finite (with sizes S and A, respec- tively). We instantiate the modules of model estimation and exploration policy construction of the SWEET framework, and specify the approximation error function and parameter selection as follows. The details of the Tabular-SWEET algorithm is shown in Algorithm 2 in Appendix B
Model estimation. At each episode n, the agent uses (x-1), which is the reference policy derived
from the last episode 1, collect trajectory {o( (n) ,
(n) (n) For that, set eg and
88 81 a

---

Published as a conference paper at ICLR 2023
t as 0, i.e., it is essentially a (0, O)-greedy version of policy x(==1), We note that although ((--1) is greedy policy, the uncertainty captured by the approximation error function U (P, will guide the agent to explore the uncertain state-action pairs and obtain sufficient coverage for the entire space.
(") (n) M to maintained dataset data triples {8h ah 1.4t1/==1
The agent then adds D. Let Nob (sh, an) Em=1 118h) (m) = Sh, On (m) on, sh+1 Sb+1} be the visitation counters. The agent estimates
Em=1 1/5 (n)
Sh: an = an} and " ahs sh+1)
(m)
No (on. an+41) if N/ (sh, a4) > and as otherwise.
h (8h+1 18h, an) as
N (s))aa)
Approximation error function. Inspired by Ménard al. (02T). we adopt an uncertainty-driven to guide the exploration, where 3o is a fixed (ss.0n)
virtual reward function b/²" (sh, aA)
B.H
parameter. Let ar = + H/H. Then, the approximation error function is specified as ( (T) :=
3 ((m)(z) (x) is concave and continuous in æ. Besides, as shown in Lemma in Appendix B we have V - p.. S u(")(T)
Vagg pin) Bln) According Lemma
(T) for any normalized utility u, i.e., uln) (T) is valid upper bound on the estimate error for the corresponding value function. The required properties of U in Theorem Tare thus satisfied.
Exploration policy. To guarantee that the exploration is safe, we set k = nz/2, and construct an empirical safety set ((n) == Cpc. ppt)) 2, O, 0) (Equation (3)) Hence, the algorithm finds a policy (00) used for the next episode, which is in the safe set Cta) and maximizes the truncated value function To
((w) _6o)* The exploration phase stops at episode n. when (1(2)) S T. The algorithm
will utilize the model learned in episode to design an c-optimal policy with respect to arbitrary given reward r" and safety constraint (c", (c",
4.2 THEORETICAL ANALYSIS
The theoretical guarantee of Sibular-SWEET is characterized in the theorem below, whose proof can be found in Appendix B
Theorem 2 (Sample complexity of Taaular-SWEEET. Given c, 5 (0, 1), and safety constraint (c,
5mm 7 16 and T = A(c, T)2/ be the termination condition of "abular-SEEET. Then, with probability at least - 8. Y'abllarSWFEF" achieves the learning objective of safe reward-free exploration (Equations
under Assumption 1, let 1l min { 2 2n sAmin
and ) and the number of trajectories collected in the exploration phase is at most Ô HS
HSA(S+)0e(1/B)) K2
A
We discuss several possible scenarios and the corresponding selections of 1l as follows.
Constraint-free RF-RL. For this case ((c, T) = Amin = 1, and = 0. Thus. 11 = O(e) and the sample complexity is Ô S2 A/c?), which matches the state of the art (Ménard et al. 2021) Constraint planning. If only safe exploration is required, set 1l (min x)), and the sample complexity scales in Ô Ae..r ) The blow-up factor A[c,7]² depends on the safety margin, and the impact baseline policy only appears in the e-independent term.
Constraint mismatch between exploration and planning. For this case, we set 1( = (rrAmin). and
the sample complexity is at most Ô
HSa
(2 min?
)
Ale,7)
THE LOW-RANK-SE -WWRRANK-WEEET SWEET ALGORITHM
5.1 LOW-RANK MDP
In this section, we present another SWEET variant for low-rank MDPs.
Definition 8 (Low-rank MDP (Jiang et al. 2017 Agarwal et al. 2020 Uehara et al. 202 ). An MDP M is a low-rank MDP with dimension d E N if for each E [H. the transition kernel PA admits d-dimensional decomposition, i.e., there exist two features Φn S x A + Rd and pa : - Rd such that PA (s 1h+1lss. an) = (01(s,, on), Ar (*h++))) Vsh, 8h+1 E S, an E Let @ = (on and μ
{nA he be the features for P. Then, (1,% as)a) I 1, |l (s))s S Vd. ((s,a) S A, Vg S [0, 1).
7

---

Published as a conference paper at ICLR 2023
Differently from linear MDPs Waan et al. 2020 in et al. 2020b), low-rank MDP does not assume that the features Φ are known a prior. The lack of knowledge on features in fact invokes a nonlinear structure, which makes it impossible to learn model in polynomial time if there is assumption features Φ and jr. We hence adopt the following conventional assumption (Jiang et al. 2017 Agarwal
et al. 2020 [ehara al., (202)) from the recent studies low-rank MDPs.
Assumption 2 (Realizability). A learning agent can access a finite model class { }) that contains the true model, i.e., (#" 1 E + x V, where (sh, an), (aa)))/"(8))) (8h++1)) P% (8h++1 [8h, as).
We note that finite model class assumption can be relaxed to the infinite case with bounded statistical complexity (Sun et al. 2019 Agarwal et al., 2020). Then, we present the following standard oracle computational abstraction, which is commonly adopted in the literature (Agarwal et al. 2020
Uchara et al., 202T).
Definition 9 (MLE oracle). Given the model class (Φ, v) and dataset 'D of (Sh; 0b; 8h++),, the MLE oracle MLE(D) takes D as the input and returns the following estimators as the output:
(0h, (n)) MLE(D) = arg max EN
Σ
log(on(sn) un); P (8((8+1)))
5.2 ALGORITIM DESIGN
The instantiated SWEET algorithm, termed as Low-rank-SWEET, can be found in Algorithm in Appendix [C) It proceeds as follows. In each iteration n during the exploration phase, the agent samples H trajectories, indexed by ((), h= During the (n, h--th episode, the agent executes an (co. 2)-gredy version of the reference policy 7 T(m-1), where co x/6 and the co-greedy action selection only takes place at time steps h and h 1. Denote the trajectory collected in episode (n, h) (m.h)
as {s] (s(n.h) d1
8H aH (n.h)) The agent maintains a dataset D,, for each time step h, which (n.h)
(n,b)
(n.h) (m,b), is updated through D(_)) + D U (s(m.A) .a, ,8111 J. Note that both s) affected by the -n-gredy action selection.
(n.A)
(n.h) and a
Model estimation. Then, the agent obtains the model estimate p(x) through the MLE oracle:
(ot (1)) MLE(D,), and p(a) (S141|8h an) = (0) (sh, an), P% (8)+1)).
(5)
[(m)
Approximation error function. The algorithm will also use the estimated representation o) to update the empirical covariance matrix (n)) as
a (g()) = >" 2mm. (6m) (5 (m,,+1) (mm.h+))) (6th" (s/
(m,,h11)
ah (mm.tt)))) + And.
is worth noting that only a," (mm,.+1) is affected by the en-greedy action selection, which different from the dataset augmentation step. Next, the agent uses both a(n)) and (n)) to derive exploration- driven virtual reward function as (((²) (s. = allø%
(()) (s, a))l a))o( where ||æ||A == vx Ar and
a pre-determined parameter. As shown in Lemma 14 in Appendix C the approximation error can be bounded by the truncated value function with factor = 1 up to constant additive term, i.e.
IV7... V....
V pin),8tm) + V AA//n== = ufz² (T), where "I"" stands for "Low-rank".
Exploration policy. Based on SWEET, we choose ñ r/3 such that ñ + eat < K. Then, the algorithm defines the empirical safe policy set as c(1) = C Coo (1/33, n/6, 2). It then finds reference policy (") in c(.)) that maximizes (TT,, which is used for exploration at the next iteration.
5.3 THFORETICAL ANALYSIS
We summarize the results of Now-rank-SWER. in Theorem and defer the proof Appendix C Theorem 3 (Sample complexity of Low-rank-SWEET, Given e, E (0, 1), and safety constraint and T = A(c, T/1/3 be the termination condition of Sow-rank-SWERR Then, under Assumption 1,2, with probability at least 8, Low-rank-
(c, let il min { Amin =mmiu
8 24
achieves the learning objective of safe reward-free exploration (Equeations ① and (2)) and the number
of trajectories collected in the exploration phuse is at most ò d (og(1/)) H² A? log(1/6)
16
8

---

Published as a conference paper at ICLR 2023
For the constraint- frre scenario, set A 7) Amm =K=1, and to be zero. Then, the sample complexity scales as Ô (H /22), which outperforms the best known
Remark 1.
sample complexity of RF-RL (Agarwal et al., 2020 Modi et al.) 2021) and even reward-known RL
with computational feasibility (Uchara et
2021 all for low-rank MDPs.
RELATED WORKS
Reward-free reinforcement learning. Reward-free exploration is formally introduced by Jin
2020a for tabular MDP, where an algorithm called RF-RL-Explore is proposed, which et al.
A/e²) sample complexity The result is then improved to Ô (f by achieves O H S²
Kaufmann al. 2021..
By leveraging an empirical Bernstein inequality, RF-Express (Ménard al. 2021) 1 achieves O (HS2A/e) sample complexity, which matches the minimax lower bound in H (Domingues et al., 2020). Zhang et al. (2020) considers the stationary case, and achieves Ô (5 A/E²) sample complexity, which is nearly minimax optimal. When structured MDPs are considered, Wang et al. (2020) studies linear MDPs and obtains Ô (d3 (d=H+/e²)) sample complexity, where d is the dimension of feature vectors. Zhang et al. (2021) investigates linear mixture MDPs and achieves Ô (11+dd/=²)) sample complexity. Zanette et al. (2020b) considers a class of MDPs with low inherent Bellman error introduced by Zanette et al. (2020a). Agarwal et al. (2020) studies low-rank MDPs and proposes FLAMBE, whose learning objective can be translated to a reward- free learning goal with sample complexity Ô (HH22d Aaddd//////// A9) Subsequently, Modi et al. 2021) proposes a model-free algorithm MOFFLE for low-nonnegative-rank MDPs, for which the sample complexity
scales Ó
H² A² ). where div denotes the non-negative rank of the transition kernel. Recently,
22n
Chen et al.
(022) studies RF-RL with more general function approximation, but their result scales in
d A/e*) when specializes to low-rank MDPs, and cannot recover our upper bound.
Safe reinforcement learning. Safe RL is often cast in the Constrained MDP (CMDP) framework (Alt
man
1999) under which the learning agent must satisfy set of constraints (Elroni et al., 2020
Turchetta et al. 2020 Zheng & Ratlifi 2020 Qiu et al. 2020; Ding et al. 2020 Kalagarla et al. 2020
et 2021 Wei et al.] 2022] Ghosh al. (022). However, most of the constraints considered
in the existing works require the cumulative expected cost over a horizon falling below a certain
threshold, which is less stringent than the episodic-wise constraint imposed in this work. Other forms of constraints such as minimizing the variance (Tamar et al. (012) or more generally maximizing some utility function (Ding et al.) 202I). have also been investigated. [Amani et al. (2021) studies safe RL with linear function approximation, where the constraint is defined using an (unknown) linear cost function of each state and action pair. In particular, Miryoosefi Jin (202T) utilizes a reward-free oracle to solve CMDP which, however, does not have any safety guarantee for the exploration phase.
By assuming availability of safe baseline policy, Zheng & Ratliff (2020) considers a known MDP with unknown rewards and cost functions and presents C-UCRL, that achieves regret ((N3/4) and zero constraint violation, where N is the number of episodes. [Lu et al. (2021) improves the result by proposing OptPess-LP, and achieves a regret of Ô HS3
where is is the cost value gap between the baseline policy and the constraint boundary. Safe baseline policy has been widely utilized in conservative RL as well, which is special case of safe RL, as the constraint is defined in terms of the total expected reward being above a threshold (Garcelon et al. 2020 Yang et al. 202T).
7 CONCLUSION
We proposed a novel safe RF-RL framework where safety constraints are imposed during the exploration and planning phases of RF-RL. A unified algorithmic framework called SWEET was developed, which leverages an existing baseline policy to guide safe exploration. Leveraging a concave approximation error function, SWEET can achieve zero constraint violation in exploration and provably produce a near-optimal safe policy for any given reward function and safety constraint he feasible assumption in planning. We also instantiated SWEET to both tabular and low-rank MDPs, resulting in Tabular-SWi SWEET and Low-rank-SWEER match or outperform the state of the art in their constraint free counterparts, proving that the safety constraint does not fundamentally impact the sample complexity of RF-RL.
The sample complexities of both algorithms
'The bound is adapted from the original result by normalizing the reward function.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
The work of R. Huang and J. Yang was supported by the U.S. National Science Foundation under the grant CNS-2003131. The work of Y. Liang was supported in part by the U.S. National Science Foundation under the grant RINGS- -1GS-22
REFERENCES
Alekh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun. FLAMBE: Structural com- plexity and representation learning of low rank MDPs. In H. Larochelle, M. Ranzato, R. Hadsell, Balcan, and H. Lin (eds.), Advances Neural Information Processing Systems, volume 33, pp. 20095-20107. Curran Associates, Inc., 2020.
E. Altman. Constrained Markov Decision Processes. Chapman and Hall, 1999.
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.
Jinglin Chen, Aditya Modi, Akshay Krishnamurthy, Nan Jiang, and Alekh Agarwal. On the statistical efficiency of reward-free exploration in non-linear rl. arXiv preprint 7xXi:2206.10770 2022.
Dongsheng Ding, Kaiging Zhang, Tamer Basar, and Mihailo Jovanovic. Natural policy gradient primal-dual method for constrained Markov decision processes. Advances in Neural Information Processing Systems, 33, 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, pp. 3304-3312. PMLR, 2021.
Omar Darwiche Domingues, Pierre Ménard, Emilie Kaufmann, and Michal Valko. Episodic rein- forcement learning in finite mdps: Minimax lower bounds revisited. 2020.
Yonathan Efroni, Shie Mannor, and Matteo Pirotta. Exploration-exploitatoo in constrained MDPs.
arXiv preprint arXiv:2003.02/15 2020.
Evrard Garcelon, Mohammad Ghavamzadeh, Alessandro Lazaric, and Matteo Pirotta. Conservative exploration in reinforcement learning. Proceedings of the Twenty Third International Conference on Artificial Inielligence and Statistics, pp. 1431-1441, 26-28 Aug 2020.
Arnob Ghosh, Xingyu Zhou, and Ness Shroff. Provably efficient model-free constrained rl with linear function approximation. arXiv preprint drXiv:2206.//889) 2022.
Jiafan He, Dongruo Zhou, and Quanquan Gu. Logarithmic regret for reinforcement learning with linear function approximation. In International Conference Machine Learning, pp. 4171-4180. PMLR, 2021.
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E. Schapire. Contex- tual decision processes with low bellman rank are pac-learnable. International Conference on Machine Learning, pp. 1704-1713, PMLR, 2017.
Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu. Reward-free exploration for reinforcement learning. Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning mlr
Research, pp. 4870-4879. PMLR, 13-18 Jul 2020a. URL bttps::/proceedai (tesss/v19//iin000
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pp. 2137-2143. PMLR, 2020b.
Krishna C Kalagarla, Rahul Jain, and Pierluigi Nuzzo. A sample-efficient algorithm for episodic finite-horizon MDP with constraints. arXiv preprint arXiv:2009. //448, 2020.
10

---

Published as a conference paper at ICLR 2023
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.
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, 2021.
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. A simple reward- free approach to constrained reinforcement learning, 2021.
Aditya Modi, Jinglin Chen, Akshay Krishnamurthy, Nan Jiang, and Alekh Agarwal. Model-free representation learning and exploration in low-rank mdps. arXiv preprint arXiv:2102.0703: 2021.
Shuang Qiu, Xiaohan Wei, Zhuoran Yang, Jieping Ye, and Zhaoran Wang. Upper confidence primal- dual optimization: Stochastically constrained Markov decision processes with adversarial losses and unknown transitions. arXiv preprint arXiv:2003.0000 2020.
Wen Sun, Nan Jiang, Akshay Krishnamurthy. Alekh Agarwal, and John Langford. Model-based rl in contextual decision processes: Pac bounds and exponential improvements over model-free approaches. In Conference on learning theory, pp.
PMLR, 2019.
Aviv Tamar, Dotan Di Castro, and Shie Mannor. Policy gradients with variance related risk criteria. In Proceedings of the 29th International Conference on Machine Learning, ICML' pp. 1651-1658, Madison, WI, USA, 2012. Omnipress. ISBN 9781450312851.
Matteo Turchetta, Andrey Kolobov, Shital Shah, Andreas Krause, and Alekh Agarwal. Safe rein- forcement learning via curriculum induction. arXiv preprint Sttiv:2006./13336 2020.
Masatoshi Uehara, Xuezhou Zhang, and Wen Sun. Representation learning for online and offline RL in low-rank MDPs. arXiv preprint arXiv:21 2021.
Ruosong Wang, Simon S Du, Lin F Yang, and Ruslan Salakhutdinov. On reward-free reinforcement learning with linear function approximation. arXiv preprint arXiv:2006. /274, 2020.
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 Artificial Intelligence and Statistics, pp. 3274-3307. PMLR, 2022.
Yunchang Yang, Tianhao Wu, Han Zhong, Evrard Garcelon, Matteo Pirotta, Alessandro Lazaric, Liwei Wang, and Simon S Du. A unified framework for conservative exploration. arXiv preprini 21Xiv:2106.11692, 2021.
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learning near optimal policies with low inherent bellman error. International Conference on Machine Leurning, pp. 10978-10989, PMLR, 2020a.
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Provably efficient reward-agnostic navigation with linear value iteration. arXiv preprint arXiv:2008.07737, 2020b.
Weitong Zhang, Dongruo Zhou, and Quanquan Gu. Reward-free model-based reinforcement learning with linear function approximation. Advances Neural Information Processing Systems, 34, 2021.
Zihan Zhang, Simon S Du, and Xiangyang Nearly minimax optimal reward-free reinforcement learning. arXiv preprint arXiv:2010.05901, 2020.
Liyuan Zheng and Lillian J Ratliff. Constrained upper confidence reinforcement learning. arXiv preprint arXiv:2001.09377 2020.
11

---

Published as a conference paper at ICLR 2023
Supplementary Material
A ANALYSIS OF THE SWEET FRAMEWORK AND THE TRUNCATED VALUE FUNCTION
In this section, we first prove two supporting lemmas in Appendix A.1 which are useful for the proof of Theorem]] [
Then, we provide the proof for Theorem I in Appendix [A.2] and the proof for an important concavity property of the truncated value function Appendix AA.3 AA.3 which are essential for instantiating Theorem I for Tabular-SWEET and Low-rank-SWEER
A.1 SUPPORTING LEMMAS
We first show that the value function under an (co, g)-greddy policy deviates from that under the original policy by at most Ent.
Lemma 1. Let x' be an (co.t)-gun grgredy version of policy n. Then, for an MDP with transition kernel P and normalized utility function must have
VT
VTTmm S Ent.
Proof. First, we prove the statement for the case when = 1.
Assume policy n' deviates from policy ग at step h, and denote P (5%) the marginal distribution induced by under the transition kernel P. Let n2 (TI, Th- 1, Th+1," ; where 2/ the uniform policy over the action space, i.e., (())((()))))))))))))))))()) = A//
Consider the equivalent Markov policy of c @ (1 ET) denoted by noo By Lemma 16 we have
(anls))
cu
(1 co) (aN (sh)
[A|
CoPR" (sn) ) (an (sh. + (1 - (s) copT (sn) + (1 - pT)
x (s))))):
where the second equality follows from the fact that pi (sn) - 0% (St). since the first h 1 policies of æ and n¹¹ are the same.
For any 2 h + 1, we have
x (sw) = cupt" ( (anrlsn)) + co)p% ( (an (sw))
EOP% (sw) + (1 60) 60)p% (sw.
= TM (sw)
= Thy )s
where the last equality is due to the definition of n.. Therefore, = n0= which further yields that
penn @(1-co)= = cn V P.u
P.u + (1- Vo
P.u
Since the value function is upper bounded by with normalized utility function immediately obtain that
P.u.
P.u
S En-
For the general case where x' differs from at steps in H c. [H] with |7| = < H, consider sequence of subsets {H, such that Hi C. H441, HH,+1l - HH 1, and H., = H. Then, we can define a sequence of policies (- - such that n' the (eg, i)- I-gredyy policy of that deviates from at steps in H4. Then, by the definition of (Co. t)-greedy policy in Definition n 1+1 is an (Co, grrgedy version of policy ny. Thus, by induction, we conclude that
VF - VT S
V
VF"
I cat,
1=1
12

---

Published as a conference paper at ICLR 2023
where we denote n' as r' and T².
The following lemma is critical for handling constraint mismatch not only between the exploration phase and the planning phase, but also between the constraint adopted for the construction of the empirical safe policy set used in exploration and the true constraint V p-,.. S. T.
Lemma 2. Consider set X in which the convex combination is defined through z @ (1-r)y E X, where T, E X and ? [0, 1]. Let f.g X + [0, 1] be two functions on X such that f is concave and is convex, iee. J(y @ (1-7)y) 2 ( + (1-7)f() and g(rr @ (1 - 7)4) S
1g(x) + (1 - -y)(y), We further assume that both f.g are continuous w.r.t. yf E [0, 1]. Define an optimization problem (P) as follows:
(P) max f(z) s.t. g(z) + S( FE FE (0.1).
Assume there exists a strictly feasible solution To E X such that g(ro) + (1ro S 7 - R where E (0,7), and denote x² as an optimal solution to (P).
If the optimal value of (P) is strictly less than R, i.e. f(x*) < R, then
max (x) < 2z (x²)) zEX
Proof. Let Ø1 = arg maX f(r), and x, = 1 + (1 7)20 E X, which is the convex combina- tion of Fi and 21-
vi satisfies the constraint in (P), the result is trivial. Therefore, it suffices to consider the case when g(ar)) + [(x) 7.
We first show that g(r)) 2 g(xo) through contradiction.
Assume 9(x1) < g(zo). Then, have
f(x1) > 3 g(x1) = - k -g(x1) +
g(5o) + f(x)) - -g(z1) +
R
where (i) follows because wo a strictly feasible solution, and (ii) follows from the assumption that
((0) E [0, 1] and g(z0) >> g(x1). Note that f(xo) < R, and f(r,) is continuous function with respect to E [0, 1]. Thus, we can choose 711 E (0, 1) such that
f(I,,) = R E [f(x)), f(x))]-
In addition, by the convexity of and the assumption that g(x,) < g(Ho), we have g ) S (1((21) (1 7)9(00) g(æu).
(8)
Combining Equations and 8) we have
f(x,,) + g(
S g(00) + R < g(ze) + f(xo) + k
x 7,
which implies that Iny is a feasible solution of the optimization problem (P).
Thus, by the optimality o", we have R > f(x") 2 ((m) R, which is contradiction. Therefore, g(æo) & g(21).
Then, let no be the solution the following equation.
To (g(x1) + f(x1)) + (1 - (0) (g(2o) + +f = F.
(9)
Since g( + ((x0) S - ñ and f.g- E |0, 1], we have:
< 270
13

---

Published as a conference paper at ICLR 2023
which implies "ro R/2.
Since f is concave and continuous w.r. 7, there exists y S Yo such that
[(xr) = (x)) + (1 70 (xo)-
(10)
On the other hand, due to the convexity of Ø. have
g(x,,) S ( (1 {0()))))))))))
n S (0) ) + (1 7o)g(ro);
(11)
where (i) follows from the fact that y S To and g( g(zo).
Combining Equations 10 and [11 we have
g(xr-) + f(x,,) (z) (1 (0) + 70 + (1 (x0) =
which indicates that xg is a feasible solution the optimization problem (P). Thus, by the optimality of x=, Equation [0). and Nu 2 R/2, conclude that
max f(x (=)(
Yo
(0)( ) + +11 - (0))
70
[(xn))
2ff(x")/R.
A.2 PROOF OF THROREM
1
We first formally restate Theorem Dellow and then provide the proof for this theorem.
Theorem 4 (Restatement of Theorem 1/. Given an MDP M and model estimate P, assume U(P, x) is concave and continuous over the Markov policy space X and IVT_,. VP I U(P, π) for any normalized utility and policy т. Let co, and i be constants that satisfy cat + < k. Let = min
cot)il/2 be the termination condition of SWEET. If SWEET terminates in finite episodes, then, the following statements hold:
$. Amin edmin I-eat b(A(ccr)=eglét) j. aand S
- ((D(e.7)-cot)
(i) The exploration phase is safe (See Equation IT)
(ii The output ă of SWEET in the planning phase is an c-optimal (c", (""saee policy (See Equa- tion (2).
Proof. The proof consists of three steps: Step I shows that the exploration phase of SWEET is safe; Step 2 shows that SWEET can find an e-optimal policy in the planning phase for any given reward and without the constraint requirement; and Step 3 shows that SWEET find copptimll policy in the planning phase for any given reward and under any constraint (c",7*) requirement. We next provide details for each step.
Step 1. This step shows that the exploration phase of SWEET is safe.
Note that the exploration policy, denoted by Te is (co, f)-greddy version of the reference policy Ty, where n, is a solution to the following optimization problem:
U(P, T),
max TECp.(R,co.t)
where
[o9), vg +U(,, r - -ot- R,
Cp Cp.p(R, co. t)
VB. VT +u(P S - -cot] otherwise.
14

---

Published as a conference paper at ICLR 2023
If क, nT, then by Lemma I we have
pe S VV cot 1 + cot <
where the last inequality is due the condition Egt + < k.
nr # T then V + U(P, TT) T Ept. By Lemma have
Vp S Vp p +
eat
1r u(P, m,) + Got P.c
cot + eg! =, T,
where (i) follows from the definition of ((P, r). Therefore, the exploration phase is safe.
Step 2: This step shows that SWEET can find an e-optimal policy in the planning phase for any given reward p* in the constraint-free setting (T* oo), i.e., the planning phase does not have constraint requirement.
Consider the Markov policy space X' with the convex combination defined by the mixture policy YT @ (1 - 7'' and g p.c'
Let n, be the reference policy when the termination condition is satisfied. Then, by the property of U(P, x) and the termination condition in SWEET, the following statements hold:
g()) TT) is convex (linear) and U(T) is concave on X. Morcover, they are both continuous.
The baseline policy T X and ((=0) + U(P, 7 S eot
arg max, U(P.mt π²) s.t. g(x)) + U(P: T) S egt. Moreover, U(P,T,) ST < R.
Applying Lemma 2 with the baseline policy x0, we have
2 max max)(() - U R.
2T
21.
(12)
Let x min = arg min, Vp.co .. By the definition of U and Assumption
we have
g( min) + U(r min) I Vp min
20(T min)
min 4T pa.e
T - Egl - T
min Vp-.c
4T
(13)
R
We again apply Lemma 2
with the feasible solution fixed as policy π min to conclude that
2T
(8)
2T
max
A(c,T) eot - 4T/R = 22
cut Vp-.e 4T/R
where (i) follows from Equation
13 and (ii) follows from the definition of ( T).
Continuing this process, we get sequence { with recursive formula
Fnt1 2T/ r) cat 2rn),
and
max inf f2
Denote A(c, ent by Á. Then, T A.//
A(A. which implies that
Â
Φ1 <
4
2
15

---

Published as a conference paper at ICLR 2023
Then, based on Lemma 20 { converges to
A
16T
4
Therefore, we conclude that
Â.
16T
A
max U(
S
11.
(14)
4
A
A 16T
Let arg max, V..,.. By the definition of U(T), we can compute the suboptimality gap of π as follows.
Vp.
Vp.
Ve Verr. pe V Vp..r
U(#) U(
< 2 max U())
- 21l c,
where (1) follows from the optimality of न. i.e. V frrr S <V
Step 3: This step shows that SWEET can find e-optimal policy in the planning phase for any given reward r" and under any constraint (c", T*)
Let g)( Ve... Recall that
π = arg max VT.,,- s.t. Vp- ST¹ s.t. 90( + U(T) ST
म arg max V Pr.
If (00[=*)+U(m)) S r", by the optimality of n, we immediately have
Vi
(f() U(T*) > r", then by the definition of and Equation 14 we have
(o(=T) + U(T*) < V7. .c + 20(
<T + 211
(15)
Let min, Vp.
By Equation 14 have
go i ((T)
20(
V p 20 < T
(16)
Let ? be the Markov policy equivalent to the mixture policy 7x @ (1 - 7) under the estimated
model P. Let A A(c", T") 7" Vp-..- and 7 (A 351) / By the linearity of go
and Equation (14). we have
go(m?) + U(#?)
I (T") (1 - 7)) +11
(4)
S 77 -21 (1 (VF 211) + 11
= = + 331 VP..."
= A. + v =
where (i) follows from Equations 15 and 16). This implies that T is a feasible solution of the optimization problem solved in the planning phase. By the optimality of म and the lincarity of V
P p.r.
we have
Vp.. Vir..
16

---

Published as a conference paper at ICLR 2023
P. P.r
311
VT""
V
P,r
A.
P.y
311
V
(17)
p.r
Amin
where (i) follows because 7 tion condition and Assumption 1
-A.-- / and the last inequality follows from the normaliza-
Recall 11 < Amins Therefore, the suboptimality gap under ग can be computed as follows.
5
Vp
Vp
VT
U(TT)
per..- U(T)
Pe.
31
A Amin + 211
where (i) follows from Equation 17
A.3 PROOF OF CONCAVITY OF THE TRUNCATED VALUE FUNCTION
In this subsection, we show that the truncated value function defined Equation 4 concave and continuous on the Markov policy space X. These crucial properties to be used for instantiating our theorem to Sabular-SWEET and
Lemma 3 (Concavity of the truncated value function). Let n² be the equivalent markov policy of @ (1 - 7)) under a transition model P. Then,
P.u. 2 VV (1-
In addition, VT. is continuous w.r.f. ? [0. Moreover, if the utility function u. satisfies the normalization condition, then the equality holds, i.e.,
VÆ" = >VP + (1 (1-7) (1-7)VPu.
Proof. Recall that the truncated value function defined recursively as follows:
Th,pan (sh, an.) a(s,a) + aPp)") V 1+1, (sh, on)
v Vi,pon min
1, @ n MCw), (s, (s.
with V0 1,,,, (1 =
The continuity of the truncated value function is straightforward, since it is a composition of H continuous functions. Therefore, we focus the concavity part in the following analysis.
By Lemma 16 the following equality holds for any utility function u and time step h. Ep [un(sn, am)] =Ep, [un(s),a)) + (1 P, [un(sn an)]
(18)
We then prove the claim by induction.
First, note that when h H +
V (i + +(1 (1-7)
Vi p.
E
E P.
= =0 5 min {
E
p.
17

---

Published as a conference paper at ICLR 2023
Assume it holds for step h + i.e,
Vh (itie) + (1- B Par
E P.x
S min { 1, P.
[ (oitaelonnntannilll
Then, for step h, by Jensen's 's inequality, we have
Vil (sn) + +11
7 Par
E P,r
S Smin
1,7 E
(sh + +(1 (1--) Par
E
Pir
min
1.7 E P.
(u(sh: +(1 (1) E p,
[u(sh: an)
V (otti) ( (1- P.r [ [Vineealaati)]
+o7
E
P.
min
1, [u(on, an)]
E +
P,
P,
PT (sh an)
{nd]]
min
J P.57
where (1) follows from Equation
18 and the induction hypothesis.
Therefore, at step = 1, we have
VE +1 (1-2) Vp S min {1. EE #3
@ [ (1
P.a.
If satisfies the normalization condition, then P,, an) 1 holds for any a and h. By the definition of the truncated value function, we have QT.p... an) (T. an) and V... (sx) VT.. (sk), which implies that the truncated value function and the true value function are identical.
By Lemma 16 n introduces the same marginal probability over any state-action pair the mixture policy 7Tt 3 >'''. Therefore, when is normalized,
VV + (1 -V
VV + (1 ->)VV'' VP V
which completes the proof.
B ANALYSIS OF TABULAR-SWEET
In this section. we first elaborate the Tabular-SWEET algorithm in Appendix B.I To provide the analysis for this algorithm, we first provide several supporting lemmas in Appendix B.2 and then prove Theorem in Appendix B.3
B. THE TABULAR-SWERS ALGORITHM
We first specify the parameters in Tabular-SWEET. The detail of Tabular-SWEET is shown in Algorithm
18

---

Published as a conference paper at ICLR 2023
Let min 2: -
I 8. and (c,, 7//2 be the termination condition of Tabular-
I 16
SWEET. Let the maximum iteration number N be the solution of the following equation:
22 (2-3033HSAA 3HSA log(N + 1) + 2 3HSA log(N + +1)
(19)
(c,, 121 where 3 = (25(22AHH)) + Slog(e(1 + N)).
x²
Recall that the estimated model is computed by
N (vn.a..34+1)
(o( if N " (sn, 1,
p (9h+11sh:: ah)
p( No (sp.0a))
(20)
(sht118 an. S otherwise,
where N/ (sh; an) and No(1) (sh, an 18+1) denote the numbers of visits of (sh. on) and (sh, 4h, 8h+1) up n-th episode, respectively.
Then, the exploration-drivee virtual reward is defined as
6(m) (sh;ah)
an)
H N (en. (s)
(21)
where 3p 83.
The approximation error bound concave function of the truncated value function, defined as u(n) (T) =4/
\ pins jens"
V/
Since co and k.2, the safety set ((r) is given by
(x²), if ir + 2T
2T
Cp.p(R, co, =
(22)
T: VP + ( (T)
otherwise.
Algorithm 2 Tabular-SWEET
1: Input: Baseline policy n7, dataset = 0, constants T, K, aR = H+1
T Alc, T)4/2.
H
2: // Exploration:
3: for = 1,..., do
4: Use (1= to collect (s(") "..,,, ); - DU (s
.....,,,)))
(5) .a
(m)
(m) 1f 1
5: Estimate p(n) update (() u()) and the empirical safe policy set c(r) (Equations (0
(22):
6: Solve n (n) = arg rec(s) (IT(
7: if c(m) > 1 and (x((() < T then
8: ney pe (8 n, p(n), B(m)). break;
9: end if
10: end for
11: // Planning:
Receive reward function fd and safety constraint (ct,T") yann < T"
13: Output: म = max, Vp s.t. V + +AV
B.2 SUPPORTING LEMMAS
First, denote Varp, 141.P' (Sh. an) as the variance of value function V follows the distribution Pr (r(-)sh, an), i.e.,
PPP,P (sh+1). where sh++
Varp, V 1, (8h, an) Ep, (V PAVE PA (5 18n, an (23)
Then, have the following lemma.
19

---

Published as a conference paper at ICLR 2023
1). Let Pi,h (Sh, an) be the marginal probability over state-action pair (sh; a+) induced by policy under the true environment P Suppose the utility function u satisfees the normalization condition. Denote
Lemma 4 (Lemma 3 in Ménard et al. (0211).
Eo-
Yn, h, 8h, an, (PL(P (P( an)ll (1
3
(sh (sh, an)
n-1
E1
Yn, h, S/, an, (sh. (sh. 2
Σ
Pa.h (sh+ and - B1
2 m=U
Vn, h Sh, ahi (P/ Ph)) VT (snns an)
82 =
2 Varps (Va+1,P* (shs anh)
333
Ni (sh. an.)
No (sn, an)
where B = 1og(35AH/o) + *S Slog(8e() (1 + N)), === =lo0(3AAH//) and 82 = log(35AH/6) -
(1 (1 N)). Note that B Z 92 2 Br. Let 38 n2 Then, we have
P [ 1 8.
The following lemma shows the relationship between the visitation counters (sn. ax) and the pseudo-counter Σm= p (sh, an), where (s,, un) is the marginal distribution on (sn, an) induced by policy æ under true model p*
Lemma (Lemma we have
Kaufmann et al. 2021) Lemma in Ménard (202)) ). On the event
B (sn, an)
4,
min
.1
<
(n) No.
max
Em=o
P (sh, an).
(m))
In addition, we generalize Lemma Ménard et (2021) from deterministic policies randomized
policies. This is important for safe RL, as the optimal policy in constrained RL is possibly randomized.
Lemma (Law of total variance with randomized policy). Given model P. policy n, and normalized utility function u, define another utillty function on (Sh, ax) as
(1h an)) Varp, V 1. (Sh, (k))
Then, for any Markov policy w and h E [H], the following bound holds:
2 En (oheeu(onan Σ "usss aaw)
8h, an
2 (oh
(24)
In particular, when h L, we have
( (P,,((1,))))
2
1> E
Σ u(sh, an)
81
2 E (s,,
Σ Σ Mish an) ak)
Σ
Σ (h an) Varry
h21 8h.0s
where PT, (S), an) is the marginal distribution over state-action pair (sh, ox) induced by policy π under model P.
Proof. First, note that the statement is trivial for h H + since all Q-value functions O.
20

---

Published as a conference paper at ICLR 2023
Then, prove the result through induction. Assume that at time step h + 1,
Err @h 1h+1)
Σ
u(sw: awx)
sh+1 asti
2 ( ah+1).
M24+1
Then, time step the LHS of Equation 24 be computed follows.
(oieulonnn -
Σ u(Sur, (ne)
E
8/, ah
12
Ex
Ph PaVitz
Σ
u(sws,aw) + (9tt1, - Q (hh1,P 1hh an
124+1
Ex
Qh+LPa(0hht (1+11,
Σ
u(sw, (w))
8/1 an
#2h41
(QT+I.Pa(SH411 PLVV (Sh, (8h,
Shi an
E u(sw,aw) (w)) k2h+1
( (oinnrnashht ax+1) Ph V ( an) Shi ap
2E,
The term within the expectation in the third term equals 0 if we further condition it on $h+1, Ch+1+ indicating that the third term is O. Therefore, from the assumption, have
@h, (h an) - Σ
u(s'', an))
8h: Oh
12b
2 E
QNtI.P.005411 (1+)1, sh. ab
(QNtLLLLOOnni - Pr. VTT+ (7,, an)
+ E
8h+1
Sho ah
( (VitLLea(ont))) - PA P (
Pn. (1 By
8hs ah
(n on) + P.
= QT. an),
where (1) follows from Jensen's inequality.
Thus, Equation (44 holds for all step h, and the proof is completed.
The following lemma is the key ensure that Tabular-SWEET satisfies the termination condition.
Lemma 7. On the event E, the summation of Van,at (n) ool W), i.e.
fmm_6ln over any subset N c [N] seales in the order
Σ REN
(() pin) p(n) S 64c (4e23HS) + [W]).
21

---

Published as a conference paper at ICLR 2023
Proof. First, similar to the truncated value function, we extend the definitions of value function to incorporate the additional factor aи- Specifically, wh E [H],
QN.P. u(sh, an) + az Pn V 1+1,PM
Von.a E [h.rr.
and V Vag. Po.
We then examine the difference between the truncated Q-value function defined with respect model p(n) and the Q-value function defined with respect model P
Qap Bim) (sh: an)
Po.pp- p- (sh, ap)))
= -o P(n) ponn
141,Pt0),ise (8hs (h.) on PR Vo h41,P- S.,,,-,,ee jila (8h: as)
O. ((()) - Ph))
Vann
1+1, Boo) (8h, 0n) + az Ph (Dagi
1+ (8h. an).
1011,
By Lemma 10 in Ménard et al. 2021), we bound the first term as follows.
Ph
vauga P.Pr Brn) (sh, an)
B
28
min
VoHST Var h41,ptm) 80m) (sh, an)
+
No (sh, an)
3,1 (sh,
Varp: Vanio
bt1, Boo) (sh, an)
min (2+ H/2)B
H
3,((( (sh: an)
(i) h h+1, Aom,, Brw) (Sh, an)
+ min (
(sh, an)
where (i) follows from 22B < A/H + BH/2, and (ii) is due to the truncated value function is at most and Var(X) < B[X] if X [0, 1].
Therefore, by combining the above two inequalities and taking expectation, we have,
pan. ((m))
(sh) S E
@ann P.P M(n) (sh, an))ss) 8p
min (()12) (sn, an). sh + +an an min (( (sh, an)/8,
$ Ex
+ E,
(ax - aH > vann
ho1, Jimn (sh, an)
H
< Ex
3 2 min (ith (sn, and. 1 + 1 H
Pr vani
1+1,Pos Bony (0h, and
Telescoping the above inequality from min (8) (sh,
to H and defining (sn, an)
(sh, an). we get
T p(n) (in) I /113//H, 2c Bln) 2b(m)
Therefore, ph,h (sh, un) the marginal distribution over state-action pairs induced by exploration policy n (n) under the true model p*, we have
Σ BEN
(i p(n) 860) 5 Σ
nEN
22

---

Published as a conference paper at ICLR 2023
$ 2
Σ
E
min
8HB
((()
Nim) (8h. ah))
NEN /==1
2
H
Pa. (sh, an) min
(1)
8H3
N(n) (s), ah
nEN h=1 Sh.
(8)
8HB
26
E
Pi, (8h: an.)
max 1, Lm
Pa.h (s and
Tim
Shaap nEW
11
Phh (5h, anh)
(m)
< 16e HB
Σ
ΣEΣ
1=1 8b, nEN max 11 I,, P (sh, an)
(#i)
64e HB Σ Σ log 1+ Σ
(sh an)
Sh 4h
nEN
(1i1)
x 64e 3H5A + WW),
where (i) is due to Lemma
5
(1i) follows from Lemma 18 and (iti) follows the fact that
Pa, (sh, an) I 1. Therefore.
a(m)
Σ
vag,al)) 8(o) S AHS (W1).
nEN
B.3 PROOF OF THEBREM 2
Theorem 5 (Complete version of Theorem Given c, E (0, 1), and safety constraint (c,T), let I }. and T (e,, 1)/2 be the termination condition of Tabular- achieves the learning objective of
11 = min
2) - 2-
Amin cAmin
SWEET, Then, with probability least safe reward-free exploration (Equations and (b). and the number of trajectories collected in the exploration phase at most
3HSA BHSA.) ( 2)2
R2
where log
SHSA AI
BHSA
and B = (0 + Slog(e( + N)).
Proof. The proof of Theorem mainly instantiates Theorem by verifying that (a) v(")(T) = /ann B(x) valid approximation error bound for Vo and (b) Tabular-SWEET satisfies the termination condition within N episodes. The proof consists of three steps with the first two steps verifying the above two conditions and the last step characterizes the sample complexity.
Step 1: This step establishes the following lemma, which shows that u(") (TT) 4 valid approximation error bound.
Von pin 860) is
any Lemma 8. With aи 1 + 1/H defined in "aabllarSWEETT (Algorithm) 2 the event for any policy v. and any utility normalized function u,
Va p(n)
VP-
< 4
p(n)_ B(a)"
Proof. Recall that
(m)
3 H
b/
N
(5h ah)
23

---

Published as a conference paper at ICLR 2023
where Bu 8p.
Define utility function u² as (sh: an)
83
1
Var p(n) V
1-1, (shs an) min
N
())
(sh+ an) H
Following Step of Lemma in Ménard et al. (001)
we get
V Po0,u
5 Pin) [o0)"
(25)
p-
Next, we aim to show that
van.z POO
S c
V Vani pou p00,860 86m)
(26)
For that, let 1M' (sh: an) be the marginal distribution p(m) and policy æT. Note that the truncated value function is a lower bound of the corresponding value function. Thus, we can expand vaus as follows:
state-action pair (8h, un) induced by model
H Σ E shith
Tag. pio), ,
aH h-1 (s an) an) an)
83
1
pa (shnsaa)) Var Var
V
1+1, (sh, an) min
N
(sh. an)
H
Pu 94 A.
(88)
ΣΣ (sh an) p(n)) V
1111, (sh, and
Σ
Σ Sh,0n
i an min
83
1
N/ (sh an)
H
where (1) follows from the fact that (1 + 1/H)" S and (ii) follows from Cauchy- inequality.
Note that in contrast to the optimistic policy, क could be a randomized policy in general. By Lemma we have
H
Σ
(8h,
Var p(nn V
P(m (Sh, an) S 1.
1=1 9h.9a
Meanwhile, if we define u (sh, an)
min
which is obviously a normalized
Ni (sh on)
H
utility function, then, we have
H
83
1
Σ
Σ (Th, and min
V pini,e S
Vou.m plai itn)
(m) (sh an)
H
1=1 MA.
where the last inequality follows from the facts that ut (sh, an) S ((/)) an) and an 1. Thus. we have Equation (26) established.
Combining Equations
255 and (26), we conclude that
Ve Poo),
Vp- S V
+ VoOHH on pCw), (80) (1+
p(n), S 4
where (i) is due to the fact that the truncated value function is at most 1.
Step 2: This step establishes the following lemma, which shows that TabET will terminate within N episodes.
24

---

Published as a conference paper at ICLR 2023
Lemma 9. On the event E. there exists ne E [N] such that (((m.) > and Van, (mn))
((ie)) bine) S 12//16,
where N is defined in Equation 19 and T is defined in Tabular-WEEET (Algorithm 2
Proof. Denote No {n [N] =(() x"). We first prove No is finite. Note that for all n E No.
Vg p + 4 Tan pin) _i(m) 2 T - k/2.
By Lemmas| and
we have
Σ
Va0
pin),e + 1 / Veg (in) Vp.
neNo
Σ 8 neW,
p pin), ((n)
I 64
No N):
where the last inequality due 2 BHSA (++ x²
Cauchy-Schwarz inequality. Therefore, [
(a(m)) Then, we prove Lemma by contradiction. Assume pin),i(m) to Lemma 7 have
> T2/16, Vn E [N] According
(N (ol))22/16
Σ
(a pini_ ((m))
ME(M//NO I 64c BHSA log Wool + 1),
which implies that
2 N n e So 1
BHSSOooO + +1)
T
R²
This contradicts with the condition that N 2 by noting that ((()) (T) = /V Von, non Bin),,tk) there exists n. E [N] such that the exploration phase under
3 N+g) Therefore,
7
Tabular-SWEET terminates.
Step 3: This step analyzes the sample complexity as follows.
On the event E, since
(c,, 2 by Lemma 9 the sample complexity is at most
N 2 + +1 21 BHS Alog(N (N
A(c,T)21
R²2
Note that n co log(cin) implies 2c, log(coe1). Thus,
N 0 ( BHSAL
BHSA + R²
A A(c, 2211
where
3HSA
3HSA R²
1 == log Alc, 2)
Therefore, Tabular-SWEET terminates in finite episodes.
Besides, U(T) 4 B On the event &, by Lemma Lemma and the concavity of /or U(z)
fe
an approximation error function under P and is concave and continuous X.
We further note that x/2(A(e.r)=//2) .s due the condition A(c, r) 2 k. which indicates that 43(cT)
T = A(c, T 11/2 satisfies the requirement Theorem
Therefore, by Theorem 4 conclude that with probability at least 8, the exploration phase of Tabular-SWEET is safe and मे is an e-optimal policy subject to the safety constraint (c", r*).
25

---

Published as a conference paper at ICLR 2023
C ANALYSIS OF LOW-RANK-SWEET
In this section, we first elaborate the Low-rank -WEET algorithm in Appendix C.1 To provide the analysis for this algorithm, first provide several supporting lemmas in Appendix C.2 and then prove Theorem in Appendix C.3
C.I THE LOW-RANK-S WEET ALGORITHM
We first specify the parameters adopted in Low-rank-SWEET, which is presented in Algorithm 3
Amin <mmin 8: f. and T = (cc, T)4/3 be the termination condition of Low- rank-SWEET. Recall that we set 60 = K/6, = 2, and i = k/3.
Let 1t = min
2
We define the maximum number of iterations N 2 3g d 2 2 3 d
N
(27)
R²T2
k4
where ( = log (2 V N 1 and 33 is defined in Lemma
10
Besides, we set Ā A/eg and = 5/ 335(A d²).
For ease of exposition, we introduce the following notation for an (eo, ()-greddy version of policy m denoted as G as follows:
if E H. if h $ H. where |H| Intuitively, G follows time step h H with probability eg and takes uniformly action selection with the probability Ep.
A + (anll))) T(a,, ax),
(aa((ans))
(28)
We also define
II Unif nr (m)) 10-1
(29)
where Unif (2t) a mixture policy that uniformly chooses one policy from the policy set No C X. We use G to denote the (Eo. |greddy version of IIn.
C.2 SUPPORTING LEMMAS
We first characterize the following high probability event. Lemma 10. Denote
f/ (sh, an) = (-1sh an) -(( (-1sh, (-Isn, (1sh
(31)
E "A *M-(P ma) "A -g~o,f0 11
[o(sn, an)oss))) + AAI,
(32)
where X = 33d ((//))1))))))))) and BB = O(1.
Define events Eo and E as
Eo
[H], sh E E an E A, Vn IME [N],
fl (s)s,,an)) s }//n)
m o Ba)
a
Vn E [N], E S, E,,
5 0h (s, a) ( < ( (0.0 (10 53 (3,0) log - }
1 g())
where Ç log /
Denote = Eo & Then, [P 2 -
26

---

Published as a conference paper at ICLR 2023
Algorithm 3 Low-rank-SWEET
1: Input: Constants k/6, Å = A/eo, and termination condition T.
2: EEExloraaiio
3: for 1, .,..,, N do
4: for h = 1, H do
5: Execute policy Gh-1,1 = (n-1) and collect data sf s/mah), (m.h) ...., 8y
(n.h) (n.h)
6: Di D U {8A oh 15/+1
(m.h) (n.h) (n.h)
7:
end for
Learn (0))) 1// (1)) M) and update p(n) according to Equation 5
8:
9: Update empirical covariance matrix U/(h) according to Equation (6)
Define exploration-driven reward function ().)) (:, min à @ (s (10))1
11: Define (
Vi((n) pint (80) + +v AC//n
if V + (xm) 2T - -2k/3,
(nn)
(30)
T: Vp,c + ( ST x/3) ST-k/3]
otherwise.
12: Solve π (") arg max rect.)) Un() (T), where cl-) is defined in Equation (30).
13: if (n)
and (xx((x(()) T then
nei Pc, + (n, p(m), 8(m)) break
15: end if
end for
17: // Pllannnng:
18: Receive reward function r" and constraint (c", T*),
s.t. V pr + Va pe,bo + / Assm. ST¹
19: Output: म = arg max, Va Pe.
6/2. Further, by Lemma 39 in Zanette et al. (2020a) for the version of fixed o and Lemma 11 in Uchara et al. (2021). we have P 8/2. Therefore, IP[8] > 8.
Proof. By Corollary in Appendix D have P[E,]
Based on Lemma 10 we can bound the exploration-driven virtual reward in Low-rank-SWEET as follows.
Corollary 1. Given that the event & occurs, the following inequality holds for any E [N], e [M] sn S, an A:
à 5
(3 (sh,
leogng 1:1 < (sh. an) 30 10/0)) (shr (sk. (sx
min
where â 5v Bos(A d2).
Proof. Recall ((m) (sh, an) = min a
((m) (1m (s, (1))
13 Applying Lemma 10 we can
immediately obtain the result.
The following lemma summarizes Lemmas 12 and 13 in Uehara et al. (2021) and generalizes them to eo-greedy policies. We provide the proof for completeness.
Lemma 11. Let Pa-1 = (chh-1. be low-rank MDP model, and IT be an arbitrary and possibly mixture policy. Define an expected Gram matrix as follows:
MA-1 -
O 0h-1(Sh-11 ap-1) (0h-1(Sh-1.) ah-1))
*h-1~(P1 SPP
27

---

Published as a conference paper at ICLR 2023
Further, let f1-1($h- 04-1) be the total variation distance between P and Ph-1 time step
h - 1. Suppose 9 E S x A + R is bounded by B E (0), Le., || S B. Then, for h 2 2, any
policy The
E [g(s,, an (1)
1n-Ph-1 mmk
nÂ "b (I) a
(P(sn,an) + AdB² +B
[hn 1 (sh-
ab ah-1)
PP m
Proof. We first derive the following bound:
E
[Ø(s), as 18))ssh1,0n
ah-1)) ph- 1 (sh))dsh
/
Σ / glon, an (ann)aannnnnnnnn11 (
$ | (58-1 (2
on
M
where the inequality follows from Cauchy-Schwarz inequality. We further expand the second term in the RHS of the above inequality as follows.
| Σ g(sn, (aa dsn 0%
Mh-1.
-
27
(1)
oat (0 an 1)d8h
AdB²
pe m 10
An
1)
27
g(sh, an) 8h 8h an-1 an )
E
+ Ad
2i (P=
"n Panthe - ug ma
(0)
2n
E
E ANo SH
g(s an)
8h- ah-1
+ AdB²
4h 1
op
Illl
+ 2nB2
E
1 11
o a
(116) S
nA
E 4k
g(on, ap)
>d + nB²
E p
(8h-1,
where (1) follows from the assumption that ||g]l & B, (ii) follows from Jensen's inequality, and that (1--1 is the total variation distance between P;-1 and P 1 at time step h 1. For
(iét), note that G II (sx) 2 co = 1/4, which implies that TA (-18)) S 1 < AG II[ (ss).. This
finishes the proof.
Based on Lemma we summarize three useful inequalities in the following lemma, which bridges the total variation f( and the exploration-driver reward ((n)
Lemma 12. Define
(n(n) = h.s
E *A Mp ..,)
(n)(s, AI,
(33)
28

---

Published as a conference paper at ICLR 2023
where À = any iteration n. When h 2 2,
Civen that the event & occurs, the following inequalities hold for
f (sh, an)
8h-1. 0h-1
I a
- (9h-1.
2(m)
logi --1--
(34)
(s), an)
8/-1, ap-1
I a 1 ah-1) (0
--)
(35)
to Por h-1 spoun
II Pe mm1 uq
( (sh, an)
84-1, an-1
S - 18h-1, an 1w h-1
(36)
where
BoC(A + +d)),
== 4 +
When h
(o)
s / AA//n,
E
(1) S 15a%
dÅ
(37)
61
apoi
Proof.
We start by showing Equation 34) as follows. Given that the event & occurs, we have
(km) (rr) an) (naaan)a---0 16-1. an-1
E
(shs
((m) h (sh-1, on-
(w(m))
a 1.11))-11 x
nd
[f((1)
(sh, an) 11 Ad n
E
((n) (sh-1 (sh-1,
*n mimp - [Tn)
" hh T.))
(0h-1) 1000 U1
(0))
(((m) [
(8h-1,
x
(1)0)) (
nd
(1( (Sh, an + Ad n.
.h (8h-2,
(n)
ti mip --, 1nn
" 1m(p Gh Und (ax- 1o fn
og Gg G
(61)
h1-1
(n)
(8h-1, ah
(v(() )-1 V2ÇA BBçd2
(n)
<
0h
(8h- ah-1)
where (i) follows from Lemma and the fact that f(()) (8h, ag
1, (Mi) follows from importance
sampling at time step h 2, and (vi)) follows from Lemma 10
Equation 35) follows from the arguments similar the above.
To obtain Equation (36, we first apply Lemma and obtain
(m) (sn, an) 8h-1, ah-1
E PP anm=(())
<110%- (5h-1, < an--),
)-
nd
E Ph ppp... mn 10.0
(sh,))1))))))))1 + Ad,
29

---

Published as a conference paper at ICLR 2023
where the fact that 8 (sh, an)
1.
We further bound the term
n E Eap-(pe n.) un
[(8] (sh, an))?] follows:
(8%)) (sh: an)) )
E c Mal op w m0
S
á
((0)
( (shr an) an)) 1|
((0) 9a²
(Shr (skr an 11 (100)))
Y1
"A
up. 1 IIn
-r
E
260 (sn, (sn, (s):
EE
On (8hx (h))
(5h, an) + XI
"h "k-(P* PP=(PP. Hnd on ah-0p
"K-(PP (P- Bnd on of.0
S 96 tr²(t(()= = 9d²d.
where (i) follows from Lemma 10 and we use tr(A) to denote the trace of any matrix A. Thus,
((m) (sh, an)
< (90--(9h-11. (w(()) 1- V9Aa²d Ad
E
8h ax-1
I 10 1 ab --)
In addition, for 1, we have
f (())
(s1,
(1)
A
E
(s s Ac/nn
V
(1)
and
(1))
5 à
Ā
E
(1)
(0(0g)
(1
a1 II
< 3d
Ā
E
(1)(
(0
ar
Ad
S 3/
15 Āc/n.
where both (i) and (ii) follow from Jensen's inequality and importance sampling.
The following lemma is key to ensure that Low-Rank-SWEET terminates in finite episodes.
Lemma 13. Given that the event & occurs, the summation of the truncated value functions (a(()
pln) Blo)
under exploration policies { JAEN is sublinear with respect to | any N C [N], L.e the following bound holds:
Σ penn) gins VAc/n 32 ABB
BEN
30

---

Published as a conference paper at ICLR 2023
Proof. Note that v
I holds for any policy and h E [H]. We first have
B(o))
Verla) Pin) Piis,,60
Valln
p(m)
2, 2,Prn), BBoo (s1. a1) Pi 30m (51, (51, a1)
(n)
E
mpn)
((x) Pi)
2,A(0,,B ($1, a1) + PP (gr par
Va
Bim)) (01,
E
st(n)
(m) ($1, a1) + PP
Va(()) 2,b()),Bl (bl))
E
p. (pp,8))))
m(m)
H
Σ
= -Volin (s2. and
E p (t(m)
V which implies pln) [jo))
S V=(())
+ Voll) (n)
pe (0,0
pinfins
Applying the Equation (36) and Equation 33 we obtain the following bound on the value function
Vin
p- _00)
N
V ((o)
E
Bn an)
* A on (n)
h=1
H
( 110 200) _ + 15al
E
an
h=2 (P=-(("
(nve(t)
H
Y (1 aw)llmgg. )
dA
E P (n)
+ 15a V
Similarly, we obtain
V Pt (w))
E "Naeee (m1)
in bunss
(n)
ÇA
a 1 (8p-1, an-1)) )-1 )-1 +
E
2= ( ((t)))
n
2 ( (n)
ÇÂ
E (((( (n)
a [1]oū Mogg
+V
n
Then, taking the summation of T p- +ta; over N, we have
Vinn pe, (86)) + Ac/n
REN
dÀ +2
AÇ
Σ 15ag NEN
In 100 (wlll
n
nEA h=1l
(n)
+ ΣΣ
aa (1 an (esseee
E
nEN
A=1 mn()(()
31

---

Published as a conference paper at ICLR 2023
(
H
- I7ay
(d
+
Σ
W
Σ nEW " (a((Pt,e "A (m)
E
[ an awllle
H
+ a
AMA
Σ E
(1o (ilosnnaWlleeoo ------
nEA a " x(m)) 50 (1x)
h=1
17C ( + H 45
+ HV BoC(A+ + B) dAIiIs
- 32CHL / BBA(T + A)IN
$ 32 (/BHHA
where (i) follows from Kauchy-Schward inequality and importance sampling, and (ii) follows from
Lemma 19 Hence, the statement of Lemma 13 is verified.
C.3 PROOF OF THEOREM 3
Theorem 6 (Restatement of Theorem
3 Given e, E (0, 1), and safety constraint T), let
min { 2 Ami =Ammn
and T (e,, 7///3 the termination condition of Low-rank- SWEET. Then, with probability at least
x 6 24
8. Low-rank-SWEET achieves the learning objective of safe reward-free exploration (Equations and (2) and the number of trajectories collected in the exploration phase most
Hdd
A2 R²
A2 2012
where log² (
H2d (AA(C)))) (~
| 1T|
11/8
Proof. The proof of Theorem 3 mainly instantiates Theorem by verifying that (a) U(")(T)
V joo + v Āc/n is valid approximation error bound for V pin) aa and (b) Low-rank-SWDI. satisfies the termination condition within iterations. The proof consists of three steps with the first
two steps verifying the above two conditions and the last step characterizes the sample complexity.
This step establishes that g(m)(T) Vica 860 + v Ac/n is valid approximation error bound Low-rank-SWEET.
Step 1:
Lemma 14. For all E [N], policy and the normalized utility function u, given that the event E occurs, we have
VP-.u
Vittnt
S Poo., + v Aç/n.
Proof. We first show that VV...
V pin),u
V pimd_pto>>
Recall the definition of the truncated value functions V Vi, (st) and Qn, (sh, an):
QT P(o) a (sh, an) = u(( a) + p(() V V (sh, ax),
vx h, pin Ptw (8a) min { 1, 2 p(n) (sh, an)
We develop the proof by induction.
For the base case h H + 1, we have
V"
#+1,Pt), (8H+1)= - VB+ ( (8H41)
= = V Blo, (8H+1)-
32

---

Published as a conference paper at ICLR 2023
Assume that V 1+1,PMM) ,u ($1+1) VIt,, (sn+z) ,a & V Aen, (sh+1) holds for any 8h+1.
Then, from Bellman equation, we have,
@h 07 (sh, an) - @p- (sh,n()))
((m) V N.B(W) (sh. and -P P- (P
p(u) (V (VitI.PIm,," - Viiti.p-,a (1) (sh, an) + (ph)) - Pi) Vh (on,
(
(sh, an) (/(m)) V
Vi Vi++1pm (sh,ah)
(60
$
p(() (s ax) + p( h+1, pin),
P(m), p(o) (sn. ax)
2% pin) ptn) (sh:
(38)
where (i) follows from | (p()) (-1kk, an) (- an)ll 1 = 1/ (sh,az) and the assumption that normalized, and (ti) follows from the induction hypothesis.
Then, by the definition of V (,,) (sh), we have
V Na (8t) Vi(
min 1 hr "h.p",a(sh)) (sn), (h, (sh, and) - Q ((h }
min
1,
Q Pro) (sh, and Qh, ((hh
E, @T pin, (6), (oh and
min
where (i) follows because QU pems (sh, an) - QT.pT p-,,,, (sh, an) -1, and (ii) follows from Equa-
tion 38
Therefore, by induction, we have
VT-... Veen S Vitn Flo
Then, we show that V ( S poo) joo + VAG..
By Equation (34) and the fact that the total variation distance is upper bounded by 1, with probability at least 1 - 8/2, we have
(vln)) m --1 :1) wh 2.
((m (sn, an) 8h-1
E fl J
I E
min
(39)
Similarly, when = 1,
(s1, <
Ā
E
(1rT) (s1n)))) < AGn.
(40)
ai
a n.
Based Corollary 1
Equation
39 and 5 we have
1)
(m) h
(Sh
an)
84
>
E
min |
(m)
1 .11
> E
s(i) (Sh+1, an+1)
p())
(41)
33

---

Published as a conference paper at ICLR 2023
For the base case h H, we have
E p(n)
v Hib,n,, p(a) (SH) 8H-1
IE p(n),a
pla)
5H aHl 9H-1
b (z)
(8H 1, aH -1)s-
11
< min 1,
Q (0-
s11-1
Va pin) Blr) (511-1).
Assume that Ep(n), Jensen's ' inequality, we obtain
v pto, fow (sh+1) 8h
V b,P()) Bin) Bin) (82) holds for step + 1. Then, by
V pon (SN) 84-1
E p
min
1, E p(
an) + -p()) vm
Pin), Pim), f(n) (8h. and 8h-1
(n) 1, On (5h- (15=-1.0-11) + E plni,
V Pow, sins (Sn+1) sh
min
sn-1
p(n),
(1)
min
L. bb ($ an-
vn hip jam) (Sh) sh-1
p(o)
@ h- 1, bin) (sh-1, (sh-1, an-1
min
E,
ar h (ic)), (6.)) (sh-1),
where (i) follows from Equation 41 and (ii) is due to the induction hypothesis. By induction, conclude that
VT pin) = E
[1 (s1,
+ E pln)a
Vi.pin p(n) (82)
v Ac/n + Vi Vpen),
Combining Step 1 and Step 2, conclude that
VĀ-.a.
V VT Viini, S /Ac/n++
Vi Blo)"
Step 2: This step shows that Low-rank-SWEET terminates in finite episodes.
Th Lemma 15. On the event E, there exists n. E [N] such that pime), Blnes + Ac/m S T, where N
defined in Equation 27
34

---

Published as a conference paper at ICLR 2023
Let No = {
{n: n:: (c),) = }
We first show that No is finite set.
Note that, E No implies that V we have,
pen, + + A 1 and m(7) x². Then,
pin),
|olkx/3 < Σ
+ V p(n) jins + v AGa - V
Pin),
neNo
Σ
2V
p(n),8r0) + +2VAN A5n
BENO
64CH BgW,
where (i) due to Lemma and the (ii) follows from Lemma 13
Therefore, we have
W 2 3 Ball2d
x²
Next, we prove the existence of ne via contradiction. Assume V By Lemma
pin), + V AGn > T, Vn E [N]/No.
13
we have
(N WWolT < Σ vall) Pin) jiin) + AGn
nEN
$ 32 Av Bg
which implies
2 d A2 N Wol
2 33ll' 3 d²3
T
T
R²
This contradicts with the fact that N =
Step 3:
This step analyzes the sample complexity of Www-rank-SWERB as follows.
Given that the event & occurs, since T = A)c, and À = A/co = 6A/k. by Lemma number of iterations most
15 the
N 21231 Bg HMH
2113132 A2
K4
Note that n co logo (cin) implies S 4co (og(()))))) Thus,
H2dd A2 A2
=
R2A(C,T) 2
x²
where
H²d A²
H² c | H/8
1. == log²
()
Since there H episodes in each iteration, the sample complexity is most
H3
A22
x2A(C,,))3PP
Thus, Low-rank-SWEEr terminates in finite episodes.
& + V VĀc/ne. Given that the event & occurs, by Lemma and Lemma 14
Note that U(T) = V U(T) is approximation error function under Pe and is concave and continuous X.
35

---

Published as a conference paper at ICLR 2023
( 2x/3] 2 24 and -(c,T)-x//3 2A(c,T)/8 We further note that 4(A(e,7)- xx/))
r)/3 due the condition (c, 2 K, which implies that T = (e,, T 11/3 satisfies the requirement Theorem
Therefore, using Theorem 4 we conclude that with probability least 1 - 8, the exploration phase of Low-rank-SWEEY is safe and an e-optimal policy subject to the constraint (c",
D AUXILIARY LEMMAS
We first provide the following property of a mixture policy and its equivalent Markov policy for completeness.
Lemma 16 (Theorem 6.1 in Altman 1999)). Given model P, any Markov policies n' E X, and
Y E [0. 1), there exists x²? E that is Markov and equivalent the mixture policy "yn @ (1 y)) Let P7 (sk) and Ph (5h, an) be the marginal distributions over the state and the state-action pairs induced by π under P, respectively. Then, the following statements hold:
ph (sh) (s), + +(1 -p0p% (sk).
(
(Shs an) 70% an) (1 (1-77) 70% (sh: an).
(Tnn((s)) - -h (sh, an)/ (sn).
VE - >Vp, + V holds for any utility function u.
Next, we present the estimation error of MLE in the re-th iteration at step h, given state and action in terms of the total variation distance, i.e. ((n) (s, a) = p(() (-Is, a) P- a) By Theorem
21 in Agarwal et al. (2020), we are able to guarantee that under all exploration policies, the estimation error can be bounded with high probability.
Lemma 17. (MLE guarantee). Given E (0, we have the following inequality holds for any [N], [H] with probability least 1 - -//2:
n-1
Σ
fh (sh, Sc
where Ç == log (2 V NH/6)
( G. ((m)) m==
mo m(m)
Dividing both sides of the inequality Lemma 17 by n, we have the following corollary hold, which intensively used in the analysis.
Corollary 2. Given E (0, 1), the following inequality holds for any h 2 with probability at least 1 8/22
[s an) < C/n,
"A
(pi.c B.)
where 1I, and Go lI, are defined in Equation
29 and Equation
28
respectively.
Then, present two critical lemmas which ensure the summation of the approximation errors grows sublinearly in Tabular-SWEET and Low-rank-SWErS
Lemma 18 (Lemma 9 in Ménard al. (2021)). Suppose {an 100 is a sequence with 0n [0. 1).
Vn. Let S, = max Em=o am J- Then, the Jollowing inequality holds:
an < 4loggSN +
Lemma 19 (Elliptical potential lemma: Lemma B.3 in He et 1021h). Consider sequence of d x d positive semidefinite matrices XI...., XN with tr (X.) S for all n E [N). Define Mo = Ao1 and M,, Mn-1 Xn. Then, VN [N].
tr(X, tr(X, & log 1+ (1+ W
Σ WEN
dAn
36

---

Published as a conference paper at ICLR 2023
Finally, the following lemma is used in Theorem Lemma 20. Given a, b >> O, define positive sequence {ra recursively by
En+1
then, fun) converges to a-va--46 If a² : 4b and 21 [0= e+va²=45
Proof. Step 1. We first show that in pa-vai_10, a+v02-10)
This is true for n 1, as
[0- - 1b a+va2-10)
Assume that Fn-1 E [a=vat-a 4h at 4h
Then, with simple algebra, we can show that
a²
4b a a+
va² 4b
Fn In-1
2
Step 2. We show that {x,} } is non-increasing sequence. Indeed, from Step 1, we have
aa 2x S V a2 4b
a² 4ax, + 4x a² 46
a.d x 2b b b
In Fn
Tn41.
Therefore, Tn+1 S vn, holds for all n 2 Combining Steps and 2, we conclude that there exists limit of the sequence (r,], denoted by x².
By the recursive formula, x² must be a solution to the following equation
a x
Since x² I 01 < atvaa=au 2
by solving the above equation, we conclude that
lim In = a Va² 46
n n
37


Reviews:
[{"review_id": "jGKLSUdxcVW", "reviewer": "Reviewer_5h43", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the reward-free reinforcement learning setting with additional safety constraint. Assuming the access to a safe baseline policy, the SWEET algorithm proposed in this paper meets the safety requirement throughout the learning process with high probability. After the reward-free exploration phase, the algorithm can output a near-optimal policy for any  reward function and (new) safety constraint. The SWEET algorithm achieves tight sample complexity guarantees on both tabular and linear MDPs.", "summary_of_the_review": "My main concerns are the correctness/clarify of this paper. As a result, I recommend a rejection for now, but I will be happy to raise my score if my concerns are addressed.\n\n===== after rebuttal ====\n\nThe authors addressed my concerns regarding the correctness of the theorems. Therefore I'll raise my score accordingly.", "strength_and_weaknesses": "Strengths:\n\n- This paper proves tight sample complexity bounds for the safe RF-RL setting. This bound matches RF-RL without safety guarantees up to some constant factors. \n- The algorithmic design principle (Alg. 1) is applicable to both tabular and linear MDPs.\n\nWeaknesses:\n\n- I have concerns about the paper's soundness (details in below).\n- I don’t think the autonomous driving example mentioned in the introduction is a good way to motivate this paper. In the exploration phase of the SWEET algorithm, the safe policy set is essentially a mixture between the safe baseline policy and some rather random policy, so that the average constraint is smaller than the threshold.  In the autonomous driving example, this policy could be crashing the car with some probability and using the policy baseline otherwise, which doesn’t sound the right type of guarantees.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "YR73n3sdW_", "reviewer": "Reviewer_gkGM", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper addresses the problem of reward-free reinforcement learning under (possibly mismatching) cost constraints in both the exploration phase and the planning phase. Crucially, the paper shows how to exploit the knowledge of a safe baseline policy to achieve zero constraints violations while matching the sample complexity of unconstrained methods in both tabular and low-rank MDPs. The proposed method, called SWEET, is based on three novel components: A notion of (eps,t)-greedy policy that allows for some exploration over actions without deviating too much from a reference policy, an approximate error function that accounts for the uncertainty on the estimated model, and an empirical safe policy set built upon the approximation error function.", "summary_of_the_review": "This looks like a great work to me. Especially, it stands out for the relevance of the main take, i.e., that reward-free RL exploration under safety constraints is not harder than unconstrained reward-free RL (at least when we have access to a baseline policy), for the originality of the methodology and (supposedly) the analysis, and for the completeness of the results, which include both tabular and low-rank MDPs. Thus, I am currently providing a fully positive evaluation. However, I could not check the analysis with such a short reviewing window, and I reserve to update my evaluation when I will have the chance to look into the technical details.", "strength_and_weaknesses": "*Strengths*\n- (Relevance and value of the contribution) The main result of this paper, i.e., that reward-free RL under safe constraints is not statistically harder than the unconstrained version is really interesting;\n- (Originality of the method) The proposed method is based on several original components, and, to the best of my knowledge, is not an incremental extension of previous approaches;\n- (Thorough analysis) The paper provides sample complexity results that match the best-known rates for unconstrained reward-free RL in both tabular MDPs and low-rank MDPs.\n\n*Weaknesses*\n- (Computational complexity) The paper does not discuss the computational tractability of the Algorithm 1;\n- (Technical novelty) The technical novelty of the analysis is not clearly discussed in the main paper, although the originality of the algorithm suggests that uncommon techniques have been used;\n- (Strength of the assumptions) The paper assumes to have access to a safe baseline policy and the presence of a positive safety margin.\n\n*Questions*\n\n(Complexity) Can the authors discuss the computational complexity of Algorithm 1? Especially, the optimization problem in line 6 can be solved efficiently?\n\n(Technical novelty) Can the authors describe the main technical innovations of their analysis?\n\n(Assumptions) Although the assumptions of knowing a safe baseline policy and the positive safety gap are mostly reasonable, it would be great to have a discussion on whether they can be overcome and to what extent. E.g., do the authors believe that the baseline policy assumption can be avoided through a weaker notion of zero constraint violations (such as constraints violations decrease at a fast rate)?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Bo6HZziyghC", "reviewer": "Reviewer_3Lc4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the reward-free RL in general MDP settings with safety constrain. The author then extend their analysis to tabular MDP and low-rank MDP for a detailed result.", "summary_of_the_review": "This paper provides some new thoughts on reward-free RL, especially on safety concerns. The methodology proposed by the authors is quite interesting. However, It has some issues regarding the Assumptions, parameter selection, and knowledge about the safety margin. Therefore I would suggest a marginal rejection but would like to change my score after the discussion if the authors well clarify my concerns.\n\n\n***\nI've carefully read the author's response and other reviews. The authors' response addressed some of my concerns thus I would raise my score to 6", "strength_and_weaknesses": "### Strength:\n\n- Defining the convexity in uncertainty quantification is interesting.\n\n### Weakness:\n\n- I'm not sure if Assumption 1 will hold for **any given constraint $(c, \\tau)$. For example, if $\\tau = \\min_{\\pi} V_{P^\\*, c}^\\pi$, then $\\Delta(c, \\tau) = 0$. \n- Following the previous question, does the author want to express that $\\tau$ is a selected parameter in the exploration phase, then it's not clear how to select the $\\tau$\n- In the stopping condition we need $T \\ge \\Delta(c, \\tau)$. Does that mean we need some prior knowledge of the magnitude of the safety margin?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "2aYH5WT1_L-", "reviewer": "Reviewer_kzdP", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies reward-free RL with safe exploration. The authors consider the scenario where a\nsafe baseline policy is given beforehand, propose a unified algorithmic framework called SWEET, and instantiate the SWEET framework to the tabular and low-rank MDP settings. Their algorithms utilize the concavity and continuity of the truncated value functions to achieve zero constraint violation with high probability. The sample complexities of their algorithms match or outperform their constraint-free counterparts, which shows that safety constraint hardly increases the sample complexity for reward-free RL.\n", "summary_of_the_review": "This paper is well executed and gives results for both tabular and low-rank MDP settings. My concern mainly falls on the novelty of the used techniques, e.g., approximation error function and estimated safe policy set, and the reliance on the prior knowledge of safety margin $\\kappa$. In my opinion, the finding of “safe exploration incurs nearly no additional sample complexity for reward-free RL” is not surprising and similar conclusion has been obtained in the regret minimization bandit/RL. Due to the above reasons, I give borderline rejection.\n\nIf the authors can address my concerns on technical novelty (what techniques/findings are novel and unique for reward-free RL compared to existing literature of bandit/RL with safe exploration), I am ready to raise my score.\n\n====After reading the authors' rebuttal====\n\nThank the authors for their response.\n\nI appreciate that the authors provide a new method which does not need prior knowledge on the safety margin $\\kappa$, which relieves my concern on prior knowledge of $\\kappa$.\n\nFor the novelty, I am not sure if the reward-free-exploration safe RL brings significant unique challenges than existing safe/conservative RL. \nIn the rebuttal, the authors explained that, the reward-free-exploration safe RL needs to both ensure safety for a given constraint during exploration and find a near-optimal policy *for arbitrary reward and constraint* during planning. \nHowever, since the algorithm can first estimate a sufficiently accurate transition model during exploration and then do planning, I am not sure if finding a near-optimal policy *for arbitrary reward and constraint* will pose significant unique challenges (at least for the tabular setting). \nTherefore, I think the finding that \"safe exploration incurs nearly no additional sample complexity for reward-free RL\" is not surprising, since we already know that safe exploration incurs nearly no additional sample complexity for standard RL.\n\nFor the proposed technique, while the authors explained that the truncated value function is critical to their analysis, I did not get the significance and novelty of this technique very much. In my understanding, I think that SWEET does clipping on the value function (instead of the Q-value function) with the universal reward upper bound $1$, while RepUCB does not do clipping on value functions, and thus, SWEET improves the dependency of $H$. This technique does not look very significant and novel to me. The authors may consider to highlight more on how this truncated value function preserves concavity and continuity and brings large advantages in analysis compared to the conventional clipping technique in their revision.\n\n====After reading the authors' additional explanations and discussions=====\n\nThe authors' additional explanations relieve my concerns on the unique challenges of reward-free safe RL. In addition, I appreciate the authors' efforts in designing a new algorithmic strategy which does not require the prior knowledge of $\\kappa$. So I raised my score from 5 to 6.\n\nI suggest the authors to discuss the unique challenges of reward-free safe RL in a deeper analysis level (instead of just mentioning the differences of problem settings), and elaborate how the concavity of the truncated value function helps to handle these challenges more specifically in their revision. For the current version, it is not easy for readers (at least, to me) to quickly understand the challenges of reward-free safe RL and the novelty of the truncated value function compared to conventional clipping technique.\n", "strength_and_weaknesses": "**Strengths:**\n\n1 The proposed algorithmic framework SWEET is general, and can be applied to the tabular and the low-rank MDP settings to obtain start-of-the-art sample complexity guarantees. \n\n**Weaknesses:**\n\n1 The ideas of safe exploration based on known baseline policy, approximation error function and estimated safe policy set are not novel. There have been several works that study bandit/RL with safe/conservative exploration.  \n\nFor example,  \n[1] Kazerouni, Abbas, et al. \"Conservative contextual linear bandits.\" Advances in Neural Information Processing Systems 30 (2017).  \n[2] Yang, Yunchang, et al. \"A unified framework for conservative exploration.\" arXiv preprint arXiv:2106.11692 (2021).  \n[3] Amani, Sanae, Christos Thrampoulidis, and Lin Yang. \"Safe reinforcement learning with linear function approximation.\" International Conference on Machine Learning. PMLR, 2021.  \n\nIt is well known that in the regret minimization setting, the requirement of safe exploration will only incur an additional $O(1)$ regret (independent of the number of timesteps $T$ played in the RL game). Hence, it is also not surprising that safe exploration will not incur additional sample complexity for reward-free RL.\n\nThe technical novelties of the proposed techniques, e.g., approximation error function and estimated safe policy set, are unclear to me. In addition, the results of this paper reply on known baseline policy $\\pi_0$ and safety margin $\\kappa$. While a known baseline policy is widely used in the safe bandit/RL literature, the algorithm design and results in this paper heavily depend on the prior knowledge of safety margin $\\kappa$, and are expected.\n\n2 For the low-rank MDP setting, the authors obtain a better sample complexity result under the safe exploration constraint than all existing constraint-free algorithms (without proposing new techniques for low-rank MDP). This result is surprising. Can the authors discuss what techniques used in their algorithm design/analysis enable them to achieve a tighter sample complexity?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster