Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies reward-free RL with safe exploration. The authors consider the scenario where a
safe 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.

strength_and_weaknesses: **Strengths:**

1 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. 

**Weaknesses:**

1 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.  

For example,  
[1] Kazerouni, Abbas, et al. "Conservative contextual linear bandits." Advances in Neural Information Processing Systems 30 (2017).  
[2] Yang, Yunchang, et al. "A unified framework for conservative exploration." arXiv preprint arXiv:2106.11692 (2021).  
[3] Amani, Sanae, Christos Thrampoulidis, and Lin Yang. "Safe reinforcement learning with linear function approximation." International Conference on Machine Learning. PMLR, 2021.  

It 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.

The 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.

2 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?

clarity,_quality,_novelty_and_reproducibility: This paper is clearly written and well executed. In my opinion, the idea behind the safe exploration is not novel. The theoretical results in this paper are supported by complete proofs.
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.

If 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.

====After reading the authors' rebuttal====

Thank the authors for their response.

I 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$.

For the novelty, I am not sure if the reward-free-exploration safe RL brings significant unique challenges than existing safe/conservative RL. 
In 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. 
However, 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). 
Therefore, 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.

For 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.

====After reading the authors' additional explanations and discussions=====

The 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.

I 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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
strength_and_weaknesses: ### Strength:

- Defining the convexity in uncertainty quantification is interesting.

### Weakness:

- 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$. 
- 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$
- 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?

clarity,_quality,_novelty_and_reproducibility: - This paper is well-written and easy to follow. studying safety in reward-free exploration is interesting and useful
- There are some concerns I mentioned in the weakness where the author needs to further clarify
- In Definition 6, I would suggest the author to includes $\pi'$ in the notation $\pi^\gamma$, since $\pi^\gamma = \gamma \pi + (1 - \gamma) \pi'$, informally speaking.
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.


***
I'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
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
strength_and_weaknesses: Strengths:

- 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. 
- The algorithmic design principle (Alg. 1) is applicable to both tabular and linear MDPs.

Weaknesses:

- I have concerns about the paper's soundness (details in below).
- 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.

clarity,_quality,_novelty_and_reproducibility: I couldn’t verify the correctness of Theorem 1. If I understand correctly, there are at least some unstated assumptions regarding the safety constraint $(c^*, \tau^*)$:

- In the paragraph after Eq. (16) (page 16), $\gamma$ is defined by $(\Delta_{c^*}-3\mathfrak{U})/\Delta_{c^*}$. But to make $\pi^\gamma$ well-defined, $\gamma$ must belongs to $[0,1]$. It’s unclear to me how to establish such a relationship. In particular, could the authors elaborate why $\Delta_{c^*}>0$ and $\Delta_{c^*}\ge 3\mathfrak{U}$? It seems to me that the choice of $c^\star$ and $\tau^\star$ is arbitrary.
- Fundamentally, I don’t think Theorem 1 can be true without any assumptions on $(c^\star,\tau^\star)$. Imagine that $\tau^\star=\min_\pi V^\pi_{P^\star,c^\star}$. Then finding an $(c^\star,\tau^\star)$-safe policy is equivalent to finding the exact optimal policy under the utility $c^\star$, which is impossible under finite samples.

Some informal statements in this paper are not well-supported:  

- In related work section, this paper claims “Chen et al. (2022) studies RF-RL with more general function approximation, but their results cannot recover the upper bound we have for the low-rank MDPs” with no further discussions. Could the author elaborate?
- In the introduction, this paper claims “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 no additional sample complexity for RF-RL.” While the first part of this statement is supported by Theorem 1, I don’t see how the second part is supported --- the safety constraint always introduces an extra multiplicative factor $1/\Delta_{min}$ to the sample complexity, which is exactly the additional cost of having a safety constraint.


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.

===== after rebuttal ====

The authors addressed my concerns regarding the correctness of the theorems. Therefore I'll raise my score accordingly.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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.
strength_and_weaknesses: *Strengths*
- (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;
- (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;
- (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.

*Weaknesses*
- (Computational complexity) The paper does not discuss the computational tractability of the Algorithm 1;
- (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;
- (Strength of the assumptions) The paper assumes to have access to a safe baseline policy and the presence of a positive safety margin.

*Questions*

(Complexity) Can the authors discuss the computational complexity of Algorithm 1? Especially, the optimization problem in line 6 can be solved efficiently?

(Technical novelty) Can the authors describe the main technical innovations of their analysis?

(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)?
clarity,_quality,_novelty_and_reproducibility: To the best of my knowledge, the paper is novel and the provided results are of great value. However, some aspects of the framework could have been explained with more details (see comments above). Since I did not carefully checked the analysis, it is hard for me to judge its reproducibility.
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.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: Summary:
This paper proposes a framework called SWEET for reward-free RL with safety constraint. In the setting, a safe baseline policy is given beforehand, and the MDP is low-rank. 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 the safety requirement does not increase the sample complexity of reward-free RL.

Strength:
- 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.
- Technical assumes appears interesting.
- The algorithm do not need the knowledge of the safety margin.
- Paper clearly written.

Weakness:
-(Computational complexity) The paper does not discuss the computational tractability of the Algorithm 1;
- (Strength of the assumptions) The paper assumes to have access to a safe baseline policy and the presence of a positive safety margin.

justification_for_why_not_higher_score: The paper has some issues regarding the assumptions, parameter selection, and knowledge about the safety margin and did not discusses issues like computational complexity. The technical novelty is also limited.
justification_for_why_not_lower_score: The paper stands out for the relevance of the main take:  when we have access to a safe baseline policy, reward-free RL exploration under safety constraints is not harder than unconstrained reward-free RL. The methodology is new and  the result is complete.
Decision: Accept: poster