Foundation of Scalable Constraint Learning from Human Feedback

1. There is no clear representation of the motivation and contributions of the paper.
2. The theoretical analysis is limited, aspects such as convergence analysis and constraint violations related to constraint learning are not addressed.
3. The overall presentation of the paper might benefit from improvements, as it does not clearly convey its main claims and contains some expression errors.
4. The experimental results do not seem to adequately support the theoretical analysis. For example, Figure 3 shows significant constraint violations in CCPG w/PC.
5. The paper lacks additional necessary experiments, including comparison experiments, ablation studies, and hyperparameter analysis, etc.
6. The baselines and experimental environments in the paper are too few to illustrate the validity of the method.
7. There is no code or detailed implementation description provided to support the reproducibility of the results.

• The proof of proposition 1 leaves some questions open to me (see questions).
• I believe, a natural addition that many readers would appreciate in this context is if the analysis extended to preference-based feedback.
• In addition to the point above, it would be interesting to see an experimental confirmation of the contents of proposition 1 and 2 (i.e. the learnability of constraints from diffferen types of feedback).

Generally speaking, the paper is written in concise and clear language, however there are a number of typos and sentences/notation I would consider rephrasing:

• line 39, "comprehensive" is too strong in my view
• line 40, "fills"
• line 51, "a more general constraints"
• line 53, "empirical validated"
• line 57, I don't know the term "curly alphabets"
• line 65, "finte"
• line 79, the shorthand for the value function taking a probability distribution as an input should be mentioned
• line 110, "a constrained RL"

One major weakness of the paper is that it is not well-written; examples are given below and in the Questions section. As a consequence, I found it fairly difficult to follow the paper—I had to write my own document of notes and math to fill in several missing or confusing pieces. The clarify of the paper could have been improved tremendously, and I encourage the authors to do so.

The part of the proof of Proposition 4 that you omitted should not have been omitted, and this proof can be explained better. The claims on ine 816-820 are confusing. Particularly, it says "policy feedback does not provide no information on $c_1$". Firstly, it should say "policy feedback does not provide any information…". More importantly, I don't necessarily find this accurate. What the equation on line 818 implies is that for any policy feedback dataset will have the form $\{(\pi_k, 0)\}$, so there is no signal for identifying a safe policy. This property is directly a consequence of the stucture of $c_1$, though (i.e., there are certainly alternative cost functions that will not have this property here). Specifically, it is saying that the costs are sufficiently close to $0$ (or "symmetric" enough) that no policy is dangerous. This does give information about $c_1$. However, it does not prevent us from inferring that $\hat{c}_1\equiv 0$, so that the constraint function induced from policy feedback does not restrict the class of safe policies, which can result in the deployment of a C-CMDP-unsafe policy (by being a strict superset of the set on line 809). I think this example / narrative would be very helpful.

Again, Proposition 2 should have a more complete proof, and perhaps should be motivated more. What is the oracle here, and why should we assume access to one? I'm assuming what is really meant here is that with unbounded preferences, we can learn safe policies. I think there is a substantial amount missing in the proof here:

1. The policy feedback case is not immediately obvious to me. Maybe it's obvious to you as the authors that have been thinking a lot about this setting, but as a reader, I would like verification that my thought process is actually what you had in mind; at the very least, this would help me understand the claim of the proposition. Am I correct in my interpretation that, in the policy feedback case, you can theoretically enumerate policies, query the oracle until you get feedback $0$, and then this certifies a safe policy by definition (so you can return it)?
2. For the trajectory feedback case, is my interpretation correct that you again enumerate policies like in the policy feedback case, enumerate trajectories under each policy (given knowledge of $P_1, P$), and return a policy once you find one that the oracle only returns $1$ on at most $p|\mathcal{T}|$ trajectories? And why do you need knowledge of $r$?

Another issue with the paper is what I believe to be a lack of baselines with respect to the empirical analysis. Notably, the authors had no results for any baselines except for in the tabular domain. As such, given the prevalence of the SafetyGym domain, I am skeptical that no other method is able to solve the tasks attempted in this paper.

Minor Issues

On line 56, "We denote sets by curly alphabets" – I don't think "alphabets" is the right word, maybe "braces"?

In Definition 1, "finte" should be "finite".

The notation for the return in Definition 2 is not quite right. In particular, you're simultaneously defining the return as a function on $\mathcal{S}$ and on $\Delta(\mathcal{S})$.

The notation $v^\pi_1$ in Definition 3 is technically not defined. I'm assuming this implicitly represents $v^\pi_{r, h}$ where $r$ is the reward function in the MDP.

In theorem 1, you have defined $K := |\mathcal{D}|$, so you can (and should) replace the $\forall (d, K)\in\mathcal{H}\times\mathbb{N}$ with $\forall d\in\mathcal{H}$.

1. The notion of impossibility in learning is not explained. Does it imply you can never find a cost function that is safe?
2. There are other types of CMDPs that have not been referenced. Only expected cost constraint and value at risk cost constraint have been provided. There is hard constraint and Conditional Value at Risk constraint that have previously been introduced by Hao et al. [Reward Penalties on Augmented States for Solving Richly Constrained RL Effectively].
3. Why is learning of cost function important to safety? Can't systems be made safer without explicitly learning a cost function
4. How are the experimental domains decided? Only a few environments from Safety Gym are considered. Frozen lake is a simpler problem setting. Why were other environments not considered.
5. In the second paragraph of introduction, it is mentioned that CLHF has significant works. However, in the experiments there are not too many baselines provided. Can I please check why that is the case?
6. There needs to be more intuition provided before utilising formal description. Otherwise, it gets difficult to keep track of all the symbols.