Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 8: Accept
review_content: In this work, a novel inverse constraint learning method is proposed, where the goal is to find out the constraints over state-action pairs for given demonstration and MDP **including a reward function** (so different from inverse cost learning). The novelty of this work comes from introducing maximum entropy inverse reinforcement learning (MaxEntIRL) framework to previous works [1, 2], and this work mainly focused on the tabular setting. The objective of this work is to solve the optimization in (8), which tries to find out the constraint that maximizes the probability of trajectories that cannot be generated if that constraint is applied. (Such an objective minimizes the normalization constant in (5) and results in maximization of the demonstration likelihood under the constraint.) To solve this objective, the proposed algorithm first computes the feature occupancy (Algorithm 1), and then use those feature occupancy with greedy iterative constraint inference (Algorithm 2 that motivated by maximum coverage problem) to get constraints. Two experiments in the GridWorld show that the proposed method effectively works. 

I think this work is quite fundamental, impactful to be accepted at the conference and is possibly extended to practical scenarios (like explainable and safety RL and imitation learning) in the future. One thing I’d like to point out is to enhance the readability by reordering contents and adding some additional explanations to clarify their arguments. There are a few comments and questions I have:

- The exact definition and usage of nominal environments and rewards are still unclear to me. For example in Figure 2 (b), how did you define and get nominal MDP?
- Since Figure 1 is related to the second experiment, I recommend moving it to the experiment section. 
- At 3.2.1., “Because constraints are sets of state-action pairs, imposing a
constraint within an MDP means restricting the set of actions that can be taken from certain states.” -> Need clarification
- At 3.2.1., “For MDPs with deterministic transitions, it is clear that any agent respecting these constraints will not visit an empty state.” -> Why?
- At (8), $\{\}$ to $\emptyset$
- In Figure 3, I was a bit confused about the relationship between the threshold and the false positive rate at first glance. What I understood is that a small threshold leads to lots of iteration for constraint selection, which increases the false positive. I want authors to add some comments on that.

 Reference
[1] Chou, Bereson, Ozay, “Learning Constraints from Demonstrations,” arXiv 2019
[2] Chou, Bereson, Ozay, “Learning Parametric Constraints in High Dimensions from Demonstrations,” CoRL 2019
review_title: Official Blind Review #4

final_score: rating: 6: Weak Accept
review_content: The paper aims to address a new method for inverse reinforcement learning based on maximum likelihood constrained inference. In general, I find the problem very interesting and the motivation of the work is quite reasonable. However, I have two major comments:

(i) Does the constraint semantically similar to the domain of the MDP? In my intuition, one can create a convex hull over the state and action representations to  actually estimate the constraint.

(ii) Suppose, the reward function is unknown, how your method will fare in this case?
review_title: Official Blind Review #2

final_score: rating: 3: Weak Reject
review_content: The paper considers learning of constraints in MDPs in an IRL setting with the goal of maximizing the likelihood of demonstrations (in the constrained MDP). The constraints come in the form of avoiding certain states, actions or features. The authors propose an algorithm for learning the constraints and evaluate their approach in synthetic and a real-world experiment.

The paper is mainly well written and considers a relevant problem. However, at a conceptual level, I am missing a more precise problem formulation and an extended discussion of the possible failure cases/limitations of the approach. Also more real-world experiments would be welcome (the presented real-world problem is relatively easy, expert's trajectories are likely to agree and not make any "mistakes").

In more detail, I think the paper can be improved by spelling out the problem formulation more precisely (Section 3.1) -- in its current form I think it somewhat fuzzy. What I mean by this is that there is a nominal MDP (which is at least as "large" as the true MDP) and there are demonstrations. The goal seems to be to identify constraints from the demonstrations and the MDP such that if added to the nominal MDP it "shrinks" to the true MDP. Is that the actual underlying problem? (I understand the current formulation in the terms of the likelihood of demonstrations). In this formulation, I think the definition of over-fitting arises naturally. In the current formulation though, over-fitting seems somewhat disconnected in the sense that even if we identify a solution which generalizes perfectly to new demonstrations, we would talk about over-fitting (the optimization of the likelihood maximization is not the problem that we actually want to solve). 

Further, as also mentioned by the authors, there is a problem with sub-optimal demonstrators. Considering the example of cars given in the paper, there might be drivers that do violate speed limits. In that case, the proposed approach will fail to identify some constraints. On the other hand, if all "optimal" demonstrations are to go fast, the approach would constraint the possibility to drive slowly. All this is fine, but I think it warrants a broader discussion which is not deferred to the Conclusion/Future Work section as it is very crucial regarding the applicability of the proposed approach.


review_title: Official Blind Review #1

final_score: rating: 6: Weak Accept
review_content: The submission considers estimating the constraints on the state, action and feature in the provided demonstrations, instead of learning rewards. The authors use the likelihood as MaxEnt IRL methods to evaluate the "correctness" of the constraints, and find the most likely constraints given the demonstrations. While the problem is challenging (NP-hard), suboptimality of the proposed algorithm is analyzed. Experiments are provided to demonstrate the performance of the proposed method. 

The problem considered is interesting, and the authors provide a straightforward but empirically effective method. However, the motivation is a little unclear to me. Specifically, what will be the practical cases, where the learning the constraints is important and necessary? Can authors further motivate this topic by providing more real-world applications? 


review_title: Official Blind Review #3

Meta-review: The paper introduces a novel way of doing IRL based on learning constraints. The topic of IRL is an important one in RL and the approach introduced is interesting and forms a fundamental contribution that could lead to relevant follow-up work.
Decision: Accept (Spotlight)