Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes SPO-LF, a safe learning algorithm for sequential decision making. The key idea is to predict a pessimistic safe space and an optimistic safe space based on the confidence intervals, and constrains the exploration in the safe space. The proposed algorithm is evaluated in the mini-grid and the safety-gym environments, compared with several baselines, and claimed to be able to handle large-scale problems, and behave more safely than the CMDP-based deep RL algorithms.
main_review: Safe exploration is critical to apply reinforcement learning in real-world systems, such as robotics and self-driving cars. This paper tries to address this important challenge by extending the dynamic programming approach to ensure zero unsafe actions during training while still learning near-optimal policies.

My major concern of this paper is its unsupported claims that "our algorithm is more applicable to large-scale problems" and "behaves more safely than existing advanced deep RL methods with constraints". It appears to me that SPO-LF only works for environments with discrete state and action spaces. Discretizing the state and the action space, as did in the safety-gym evaluation, is not scalable to large scale continuous control problems. For this reason, comparisons with CPO, PPO-Lagrangian or TRPO-Lagrangian are not fair because the baseline algorithms are solving a much more challenging continuous-space problem.

Here are a few clarification questions:
1) Equations below line 121. Why is it necessary to have \phi_{s_\tau} right before "=" on the left hand side of equations?
2) It would be great to give some intuitions of Assumption 2 "The link function satisfies ..." What's its physical meaning? How strong is this assumption?
3) I had some trouble understanding line 223-225. What is the physical meaning of C_t?
4) The ETSE seems to be a heuristic for exploration whose goal is to reduce uncertainty. I could misunderstand here, but ETSE can potentially make the entire algorithm unsafe because it needs to explore the states with large uncertainty. If this is the case, I am surprised to see that the number of unsafe actions is still zero for both the grid world and safety-gym evaluations. Did I miss anything here?
limitations_and_societal_impact: I did not find where the limitations are discussed. Are there any limitations of the proposed method? 
I did not find any potential negative societal impact of this work.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This work proposes a novel safe RL algorithm based on locally available far-sighted features based on GLM assumption.
main_review: The idea of shared representations for safety/reward is interesting.
The paper is well written.

Major concerns:
1) in line 155, Y_return(X,bar{X}) is defined by bar{X} \cup ---.  Is it obvious that from state in bar{X} to bar{X} is feasible?  is there any action choice that makes the agent stays in the same state?  also in line 159, is Y_epsilon(X) needed in the definition of Z? (removing this term does not seem to affect the set)


Minor concerns:
1) in line 89, the definition of psi should be psi:S -> 2^S ?
2) this work considers finite sets of state and action, and also assumes that the transition is known; therefore, saying that existing GP-based method is not scalable while the proposed work is scalable is a bit misleading; what if the work is extended to unknown transition?

-----------
Review updated after the initial response
limitations_and_societal_impact: The reviewer wanted to see the discussions on discretization accuracy vs the usefulness of local feature for continuous control problems.  It would be possible to discuss limitations more.

Social impact is discussed.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper studies the problem of safe exploration in reinforcement learning contexts. It develops a new algorithm which, by making several assumptions, can stay safe while exploring and achieves good sample efficiency. The proposed approach incorporates sensor measurements ("far-sighted observations") and estimates of safety based on those observations, as well as the idea of an optimistic and pessimistic safe set, to stay safe during exploration. It also introduces a novel way to ensure that the algorithm does not get stuck in a safe area by detecting this case and more aggressively expanding the set of considered exploration actions.
main_review: # Originality
The approach is novel. The paper draws on unexpected sources to develop new theoretical guarantees on the algorithm's performance. ESTE is a clever workaround to getting stuck during exploration.

# Significance
A number of techniques have tackled this problem in the past with varying degrees of success (Sui et al. 2018, Wachi and Sui 2020, Berkenkamp et al. 2016 are a few notable examples). This paper is significant in the field because it seems to provide a comprehensive framework for dealing with safe RL problems - as long as the problems satisfy this (fairly relaxed) set of assumptions, the technique should apply broadly - even if the safety function has discontinuities, which is common in real world scenarios.

# Quality
This paper builds up a new safe exploration technique with logical assumptions and clearly shows the approach's effectiveness. So much of the paper hinges on these assumptions, so it is good that they are stated clearly.

It's unclear why the approach was not compared directly to the algorithms used in prior work. Many of these works even have open-source code available, so the experiments could have been true head-to-head rather than "stepwise approaches as in [36]" (line 310) which implies a re-implementation, or a similar-but-not-identical algorithm.

From my reading of the paper, it seems that the ESTE version should perform not worse than the non-ESTE version in all cases. However, in Figure 2, the ESTE version of the algorithm did seem a bit slower than the non-ESTE version, and it's unclear why this would be the case. Perhaps the difference is random deviation, however, since the experiment is fully controlled, it should be possible to do a direct, deterministic, head-to-head comparison between ESTE and non-ESTE versions of the algorithm on identical problems. 

It is odd that Algorithm 1 gives the next state directly, rather than the action to be taken. This makes it difficult to see how it would extend to a situation with non-deterministic transition functions.

Is one of the baselines algorithmically equivalent to SPO-LF but with no sensor data? This would be an interesting comparison to make, to see how vital the sensor data is.

# Clarity
The paper is written and organized superbly.

Minor edits/questions:
- L160: Should $Z_\epsilon^n$ be just $Z^n$? or does $Z_\epsilon(X) = Z(X, \epsilon)$?
- L204: this follows from $g(s) = ◇(s) \geq h$? It would be nice for this to be made explicit
- L204: this only holds for $s \in S \setminus \Psi$, correct?
- L58: resprcively
limitations_and_societal_impact: The assumptions are clearly stated, and this gives some idea of the limitations of the algorithm. However, further limitations were not really discussed. Line 183 gives a worst-case scenario for sample efficiency. However, some other limitations are that this paper uses deterministic state transitions, and that it uses a discrete MDP.

Some relevant questions:
- Is there really no way for an agent to get "stuck" or accidentally visit an unsafe state as long as the assumptions hold?
- Are these assumptions valid for most robotics problems? Are there some situations that are more likely to invalidate the assumptions than others?
- How would the technique deal with limited sensor information (finite range, obstacles, a LIDAR that was not 360 degrees, etc.)?
review_title: null

Meta-review: All reviewers recommend acceptance, two strongly. The reviewers recognize the importance of the topic (safe exploration in reinforcement learning) and the significance of the submission within this specific area. Any concerns were addressed clearly by the authors, and so the AC recommends acceptance. 

Note: There appears to be some confusion surrounding a claim "our algorithm is more applicable to large-scale problems than previous safe RL methods with theoretical guarantees". The point of confusion appears to be what constitutes a previous safe RL method with theoretical guarantees. If CPO is included (it is safety-inspired and has some theoretical guarantees [though not strong guarantees of safety]) then this may not be true. However, when comparing to algorithms with very strong (high-confidence) safety guarantees, the author's claim is clearly true. The AC hopes that the authors do not dismiss the reviewers concerns about this line, but rather aim to clarify this line to ensure that other readers do not have the same misconception about the authors' intent with the statement.
Decision: Accept (Poster)