Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper studies inverse decision theory---the problem of identifying the loss function of given optimal (under a given hypothesis class) state-action (covariates-label) pairs in a binary classification setting. The contributions of the paper are two-fold: the authors provide (1) a nice formulation of inverse learning problems where one can analytically study suboptimal behaviors and what makes inverse learning easier/harder; (2) identifiability and sample complexity results for identifying the loss function when the hypothesis class is either realizable or unrealizable. 
main_review: Though most inverse learning paper focuses on sequential decision-making settings (e.g., inverse reinforcement learning), it is great to see an inverse supervised learning paper that has a more distilled analysis of inverse learning using suboptimal behavior. By considering cases where suboptimality comes into play due to the unrealizable hypothesis class, the authors provide an interesting way of defining suboptimality in inverse learning settings (which I believe is novel). Here are some questions/comments:

(1) Is the assumption on P(q_H(X) \in (c, c+ \rho)) \geq p_c \rho and  P(q_H(X) \in (c-\epsilon, c)) \geq p_c \epsilon necessary? Some experimental results on how the estimator performs under cases when such assumptions don't hold would help the readers understand this assumption better. 
(2) Will this intuition that identification is easier when the problem is more uncertain extends to cases where the loss functions are not 0/1 loss but some surrogate losses (e.g., logistic loss)?
(3) As supervised learning can be viewed as an RL instance, could the results in this paper suggest some lower bound on identifiability of IRL under suboptimal behaviors?
limitations_and_societal_impact: The authors have adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors analyze learning preferences from human decisions in one-shot decision problems. They make 4 main contributions: 1) characterize sample complexity in this setting for the goal of identifying the cost function parameter (as opposed to doing prediction) 2) show that sample complexity improves when the decisions are uncertain 3) repeat contributions 1 & 2 when the human is suboptimal and can therefore only choose from a limited set of policies 4) show under what conditions, when the set of policies is unknown, one can still recover the cost function. 

main_review: In my view, the most important contribution is under what conditions preferences can be identified without knowing how the human makes decisions. This is a thorny and major open problem that limits the prospects for learning human preferences. In this paper, each model of human decision-making is described by a limited hypothesis class that the human can choose from. Identifying the true class is possible with a smoothness assumption on the set of hypothesis classes. However, the authors could better clarify the strength of this assumption.

The findings are not only interesting - it is easy to see they it could be used to develop better preference learning techniques.

The paper has some clarity issues. If they are resolved I may increase my score. For example the introduction talks about human uncertainty but this concept is never defined and doesn’t appear to be used. Instead the theoretical analysis requires uncertainty in the sense that the _agent’s_ posteriors haven’t concentrated (for every decision). Or at least that is my reading of the text. Figure 1 doesn’t help improve this confusion. Please see Houlsby et al (https://arxiv.org/abs/1112.5745) for discussion of these different uncertainties. More details below.

The first contribution, that uncertainty helps with identifying preferences, seems novel in this setting but a similar contribution is made in Mindermann et al. (https://arxiv.org/abs/1809.03060) which points out that cost function parameters can be better identified by excluding the optimal choice from the set of choices for the human. This paper and Biyik et al (https://arxiv.org/abs/1910.04365) also suggest that human uncertainty can hurt preference learning; the contrast to your result should be discussed. Furthermore, many papers have pointed out that decisions only convey information when they are uncertain _under the agent’s current posterior_. 


___Detailed comments___

Well-written abstract and introduction

Thm 4.2: how do you account for the fact that the posterior changes after each new sample? 

Please explain MD-smoothness and how plausible it is. This is important if you want theorem 4.10 to be a main contribution.

Some definitions are lacking. 
- Please define the human policy
- Please define partial observability. What is not observed. You seem to be using it in a non-standard way. It usually means that the state x is hidden but this is not the case here. Indeed I think you might be looking for a different term.
- Please define uncertainty (see above). Uncertainty in what?
- Please define the posterior probability, conditioned on some data. And the distribution over posterior probabilities

The paper has somewhat disparate contributions ranging from decisions under uncertainty to suboptimal decisions. Perhaps these could be separated into two papers.

Typo: “between between”

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors study the problem of learning the preferences of a human decision-maker from past decisions. The setting is that feature–decision pairs (X, Y) are drawn from a known distribution $\mathcal{D}$. Initially the authors assume the Bayes-optimal case, where the decision-maker perfectly knows P(Y | X), and the objective is to identify the decision boundary separating positive labels from negative labels in terms of P(Y | X) conditional belief. The authors take a PAC approach, give bounds on the number of samples required to identify the boundary with probability $1 - \delta$. They later relax the Bayes-optimal rationality assumption, considering the case of a limited hypothesis class and the case of a family of hypothesis classes.

 
main_review: I found this to be a clear, useful paper that tackles a natural problem that builds on the literature. The main line of analysis is fairly straightforward, but the author's approach is quite thorough and goes quite a bit beyond the "minimum" needed to make the main point. This "additional" content is rather useful and really helps to explain their approach and how it could be used (e.g., the counterexample showing the lack of MD-smoothness, the characterization of MD-smoothness for the "ignoring some features" hypothesis class, lower bounds for the problems of interest, and the fairness example). There are several directions of interest that build off the approach taken by the paper.

The risks of the paper that would push me towards rejection are:
- Significant math errors—I couldn't find any, but I did not check thoroughly.
- The ideas and techniques are well known enough that there could have been another paper to do this in the last decade. To the best of my knowledge, no such paper exists, but the risk is larger than normal.

Minor comments: I did not find the introduction clear—the cat vs. pandemic example did not work for me. The authors say that the pandemic quarantine decision is subjective and thus, they seem to imply that the cat decision is objective. I don't think that argument works—if the cat decision is objective, there is nothing to learn about the decision-maker at all. A suggestion would be to use a case where there is a hypothetically perfectly accurate COVID test instead of the cat example. Both decisions are then subjective, but there is no uncertainty in the perfect test case, and there is thus very little we can learn about the preferences of the decision-maker.

Post-response: I am maintaining my score. The authors proposed changes will increase clarity.
limitations_and_societal_impact: The authors have a paragraph devoted to limitations that satisfied my concerns. In my opinion, the largest limitation is the restriction to expected utility as a metric. A natural successor of this paper considers risk sensitivity and constraints that the decision must satisfy.

I do not consider negative societal impact to be an issue with this paper.
review_title: null

Meta-review: This paper analyzes the inverse decision theory task of recovering the loss function of a decision maker making (observational) decisions under uncertainty. The paper's surprising insight is that uncertainty of the decision maker can enable better loss function recovery. This is supported with sample complexity bounds. There were some initial concerns among the reviewers about clarity in distinguishing "clear" vs. "uncertain" decisions and the positioning of the work among some other papers, but the author(s) was/were able to alleviate those concerns and the reviewers are satisfied with the intended direction of the final version of the paper. The reviewers discussed the lack of experiments in the paper, concluding that experiments demonstrating the analyzed benefits---particularly with suboptimal decision makers---would enhance the paper, but that the paper was a significant contribution without additional experiments and worthy of acceptance.
Decision: Accept (Spotlight)