Uncertain Decisions Facilitate Better Preference Learning
Authors: Cassidy Laidlaw
Stuart Russell
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: preference learning
reward learning
inverse reinforcement learning
IRL
statistical learning
statistical learning theory
PAC learning
inverse decision theory
IDT
preference elicitation
decision theory

Abstract: Existing observational approaches for learning human preferences, such as inverse reinforcement learning, usually make strong assumptions about the observability of the human's environment. However, in reality, people make many important decisions under uncertainty. To better understand preference learning in these cases, we study the setting of inverse decision theory (IDT), a previously proposed framework where a human is observed making non-sequential binary decisions under uncertainty. In IDT, the human's preferences are conveyed through their loss function, which expresses a tradeoff between different types of mistakes. We give the first statistical analysis of IDT, providing conditions necessary to identify these preferences and characterizing the sample complexity—the number of decisions that must be observed to learn the tradeoff the human is making to a desired precision. Interestingly, we show that it is actually easier to identify preferences when the decision problem is more uncertain. Furthermore, uncertain decision problems allow us to relax the unrealistic assumption that the human is an optimal decision maker but still identify their exact preferences; we give sample complexities in this suboptimal case as well. Our analysis contradicts the intuition that partial observability should make preference learning more difficult. It also provides a first step towards understanding and improving preference learning methods for uncertain and suboptimal humans.

Uncertain Decisions Facilitate Better Preference Learning
Cassidy Laidlaw University of California, Berkeley berkeley edu www.woccsbbeeeeey...e..
Stuart Russell University of California, Berkeley russell0cs. berkeley. messell@cs.berkeeyy edu
Abstract
Existing observational approaches for learning human preferences, such inverse reinforcement learning, usually make strong assumptions about the observability of the human's 's environment. However, in reality, people make many important decisions under uncertainty. To better understand preference learning these cases, we study the setting of inverse decision theory (IDT), previously proposed framework where a human is observed making non-sequential binary decisions under uncertainty. In IDT, the human's preferences are conveyed through their loss function, which expresses a tradeoff between different types of mistakes. We give the first statistical analysis of IDT, providing conditions necessary identify these preferences and characterizing the sample complexity the number of decisions that must observed to learn the tradeoff the human making a desired precision. Interestingly, we show that it is actually easier to identify preferences when the decision problem is more uncertain. Furthermore, uncertain decision problems allow us to relax the unrealistic assumption that the human is an optimal decision maker but still identify their exact preferences; we give sample complexities in this suboptimal case well. Our analysis contradicts the intuition that partial observability should make preference learning more difficult. also provides first step towards understanding and improving preference learning methods for uncertain and suboptimal humans.
Introduction
The problem of inferring human preferences has been studied for decades in fields such as inverse reinforcement learning (IRL), preference elicitation, and active learning. However, there still several shortcomings in existing methods for preference learning. Active learning methods require query access human; this infeasible in many purely observational settings and may lead to inaccuracies due to the description-experienee gap [1] IRL is an alternative preference learning tool which requires only observations of human behavior. However, IRL suffers from underspecification. i... preferences are not precisely identifiable from observed behavior 2 Furthermore, nearly all IRL methods require that the observed human is optimal or noisily optimal at optimizing for their preferences. However, humans are often systematically suboptimal decision makers [3). and accounting for this makes IRL even more underspecified, since it hard tell suboptimal behavior for one set of preferences apart from optimal behavior for another set of preferences 4
IRL and preference learning from observational data generally applied in situations where human acting under no uncertainty. Given the underspecification challenge, one might expect that adding in the possibility of uncertainty in decision making (known as partial observability) would only make preference learning more challenging. Indeed, Choi and Kim [5] and Chinaei and Chaib-Draa (6) who worked to apply IRL to partially observable Markov decision processes (POMDPs, where agents
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Decisions without uncertainty
Decisions under uncertainty
(a) Should quarantine a traveler with a 100% accurate negative test for dangerous dis- ease?
Should quarantine a traveler with some symptoms of a dangerous discase but no test results?
(b) Should person with irrefutable evidence of and confession to a crime be convicted?
Should a person with circumstantial evi- dence of a crime be convicted?
Figure 1: One of our key findings that decisions made under uncertainty can reveal more preferences than clear decisions. Here we give examples of decisions made with and without uncertainty. (a) In the case without uncertainty, nobody would choose to quaramtine the traveler, so we cannot distinguish between different people's preferences. However, in the case with uncertainty, people might decide differently whether to quarantine the traveler depending on their preferences on the tradeoff between individual freedom and public health. This allows us to identify those preferences by observing decisions. (b) Similarly, observing decisions on whether to convict a person under uncertainty reveals preferences about the tradeoff' between convicting innocent people and allowing criminals to go freee
act under uncertainty), remarked that the underspecificatioon of IRL combined with the intractability of POMDPs made for a very difficult task.
In this work, we find that, surprisingly. observing humans making decisions under uncertainty actually makes preference learning easier (see Figure To show this, we analyze a simple setting, where a human decision maker observes some information and must make a binary choice. This is somewhat analogous to supervised learning, where a decision rule is chosen to minimize some loss function over a data distribution. In our formulation, the goal is to learn the human decision maker's s loss function by observing their decisions. Often, in supervised learning, the loss function is simply the 0-1 loss. However, humans may incorporate many other factors into their implicit "loss functions"; they may weight different types of mistakes unequally or incorporate fairness constraints, for instance. One might call this setting "inverse supervised learning." " but it is better described as inverse decision theory (IDT) 77,, since the objective is to reverse- reverse-engineer only the human's 's decision rule and not any learning process used to arrive at it. IDT can be shown to be a special case of partially observable IRL (see Appendix B but its restricted assumptions allow more analysis than would be possible for IRL in arbitrary POMDPs. However, be applicable to POMDPs and uncertain decision making settings in general. We introduce a formal description of IDT in Section 3
believe that the insights we gain from studying IDT should
While we hope to provide insight into general reward learning, IDT is also a useful tool its own right; even in this binary, non-sequential setting, human decisions can reveal important preferences. For example, during a deadly disease outbreak, a government might pass a law to quarantine individuals with chance of being sick. The decision rule the government uses to choose who to quarantine depends on the relative costs of failing to quarantine a sick person versus accidentally quarantining an uninfected one. In this way, even human decisions where there is "right" answer revealing they are made under uncertainty. This example could distinguish a preference for saving lives versus one for guaranteeing freedom of movement. These preferences the tradeoff between costs of mistakes are expressed through the loss function that the decision maker optimizes.
In our main results on IDT in Section 4 we find that the identifiability of human's 's loss function is dependent on whether the decision we observe them making involves uncertainty. If the human faces sufficient uncertainty, we give tight sample complexity bounds on the number of decisions we must observe to identify their loss function, and thus preferences, to any desired precision (Theorem 4.2). On the other hand, if there is no uncertainty-icc. the correct decision is always obvious-thhe show that there is no way to identify the loss function (Theorem 4.11 and Corollary (412). Technically, we show that learning the loss function is equivalent to identitying a threshold function over the space of posterior probabilities for which decision is correct given an observation (Figure 2 This threshold can be determined to precision in O (p.c)) samples, where Pa is the probability density of posterior probabilities around the threshold. In the case where there is no uncertainty in the decision problem, P.. 0 and we demonstrate that the loss function cannot be identified.
These results apply to optimal human decision makers-that is, those who completely minimize their expected loss. When decision rule or policy is suboptimal, in general their loss function cannot be
2

---

learned 4 19. However, we show that decisions made under uncertainty are also helpful in this case; under certain models of suboptimality, we can still exactly recover the human's 's loss function.
We present two such models of suboptimality (see Figure 3). In both, we assume that the decision maker is restricting themselves to choosing a decision rule h in some hypothesis class H. which may not include the optimal decision rule. This framework is similar to that of agnostic supervised learning [10 but solves the inverse problem of determining the loss function given hypothesis class and decision samples. If the restricted hypothesis class H. is known, we show that the loss function can be learned similarly to the optimal case (Theorem (..7) Our analysis makes a novel connection between Bayesian posterior probabilities and binary hypothesis classes. However, assuming that H. is known is strong assumption; for instance, we might suspect that decision maker is ignoring some data features but we may not know exactly which features. We formalize this case by assuming that the decision maker could be considering the optimal decision rule in any of a number of hypothesis classes in some family H. This case is more challenging because we may need to identify which hypothesis class the human is using order to identify their loss function. We show that, assuming a smoothness condition on IHI, we can still obtain the decision maker's 's loss function (Theorem 4.10).
We conclude with a discussion of our results and their implications in Section | We extend IDT to more complex loss functions that can depend on certain attributes of the data in addition to the chosen decision; we show that this extension can be used to test for the fairness of a decision rule under certain criteria which were previously difficult to measure. We also compare the implications of IDT for preference learning in uncertain versus clear decision problems. Our work shows that uncertainty is helpful for preference learning and suggests how to exploit this fact.
2 Related Work
Our work builds upon that of Davies [ and Swartz et al. 77]. who first introduced inverse decision theory. They describe how to apply IDT to settings in which a doctor makes treatment decisions based on a few binary test outcomes, but provide no statistical analysis. In contrast, we explore when IDT can be expected to succeed in more general cases and how many observed decisions are necessary to infer the loss function. We also analyze cases where the decision maker is suboptimal for their loss function, which are not considered by Davies or Swartz et al.
Inverse reinforcement learning (IRL) 2 12 13 14 15 also known as inverse optimal control, aims to infer the reward function for an agent acting in a Markov decision process (MDP). Our formulation of IDT can be considered as special case of IRL in partially observable MDP (POMDP) with two states and two actions (see Appendix BJ. Some prior work explored IRL in POMDPs 5 by reducing the POMDP to belief-state MDP and applying standard IRL algorithms.. Our main purpose not to present improvements to IRL. algorithms; rather, we give an analysis of the difference between observable and partially observable settings for preference learning. We begin with the restricted setting of IDT but hope to extend to sequential decision making in the future. We also consider cases where the human decision maker is suboptimal, which previous work did not explore.
Performance metric elicitation (ME) aims to learn a loss function (aka performance metric) by querying human [16 17 18). ME and other active learning approaches [19] 20 21 (2 require the ability actively ask a user for their preference among different loss or reward functions. In contrast, IDT aims to learn the loss function purely by observing decision maker. Active learning is valuable for some applications, but there are many cases where it is infeasible. Observed decisions are often easier to obtain than expert feedback. Also, active learning may suffer from the description-experiinn gap M; that is, it may be difficult to evaluate in the abstract the comparisons that these methods give as queries to the user, leading to biased results. In contrast, observing human decision making "in the wild" with IDT could lead to a more accurate understanding of human preferences.
Preference and risk elicitation aim to identify people's 's preferences between different uncertain or certain choices. A common tool is to ask a person to choose between lottery (i.e., uncertain payoff) and guaranteed payoff, or between two lotteries, varying parameters and observing the resulting choices 23 24 25
our analysis of IDT, decision making under uncertainty can be cast as a natural series of choices between lotteries. If we observe enough different lotteries, the decision maker's preferences can be identified. On the other hand, there is no uncertainty, then we only observe choices between guaranteed payoffs and there is little information to characterize preferences.
3

---

(a) Uncertain decision
(b) Clear decision
(c) Suboptimal decision
Observed decisions
Y
y =1
PDF of (()
C- C+C
0
Probability that the ground truth Y
Figure 2: A visualization of three settings for inverse decision theory (IDT), which aims estimate the parameter of a decision maker's loss function, given observed decisions Ø1...., Um E {0, Here, each decision 0G is plotted against the probability g P(Y 1 X = that the ground truth (correct) decision Y is 1 given the decision maker's observation T; Lemma 4.1 shows that an optimal decision rule assigns i 1()(x,) 2 c}. (a) For uncertain decision problems, IDT can estimate as the threshold of posterior probabilities ((x;) where the decision switches from 0 to (Section 4.1). If the distribution ((X) has probability density at least Pe on C, + c], Theorem 4.2 shows we can learn to precision with m 2 ((1/(pcc) samples. (b) When there is no uncertainty the decision problem, IDT cannot characterize the loss parameter c because the threshold between positive and negative decisions could be anywhere between O and 1 (Section 4.44).
(c) A suboptimal human decision maker does not use an optimal decision rule for any loss parameter but we can often still estimate their preferences (Sections 4. and
Problem Formulation
We formalize inverse decision theory using decision theory and statistical learning theory. Let D be distribution over observations X E X' and ground truth decisions Y E {0, 1}. We consider an agent that receives an observation X and must make binary decision Y E {0, 1}. While many decision problems include more than two choices, we consider the binary case to simplify analysis. However, the results are applicable to decisions with larger numbers of choices; assuming irrelevance from independent alternatives (i.e. the independence axiom (26)), ) a decision among many choices can be reduced to binary choices between pairs of them. We generally assume that D is fixed and known to both the decision maker and the IDT algorithm. Unless otherwise stated, all expectations and probabilities on X and Y are with respect to the distribution D.
We furthermore assume that the agent has chosen decision rule (or hypothesis) h X + {0, 1} from some hypothesis class H. that minimizes a loss function which depends only on the decision Ý = (X) that was made and the correct decision Y:
E arg min B(XYY>D [((M(x),)) 4Eи
In general, the loss function might depend on the observation X as well; we explore this extension Assuming the formulation above, since Y,Ý {0, 1} we can write the loss function E as matrix C g2x2 such that ((ğ. v) Cay- We denote by (h) = Exx,Y) >DD [X), Y)] the expected loss or "risk" of the hypothesis h with cost matrix C. This cost matrix has four entries, but the following lemma shows that effectively has only one degree of freedom.
in the context of fair decision making in Section 5.1
Lemma 3.1 (Equivalence of cost matrices), Any cost matrix C' ( Con CoL is equivalent to cost Csa Cn matrix C" = (2 1_() where c = Cip+Coo Cro Cin as long as Cio + Coi - Coo - C11 * 0. That is. there are constants a, E R such that Re (h) = aRRr (h) + b bor all h.
Cia Cro
See Appendix A. for for this and other proofs. Based on Lemma 3.1 from now on, we assume the cost matrix only has one parameter which is the cost of false positive; 1 - c is the cost of false negative. Intuitively, high values of e indicate a preference for erring towards the decision Y 0 under uncertainty while low values indicate a preference for erring towards the decision Y Finally, we assume that making the correct decision is always better than making an incorrect decision, i.c. Coo < Co0 and Cn Co1. This implies that 0 < 1.

---

Optimal decision rule for loss parameter
Optimal decision rule in H for
Optimal ' for c
ha
he
he No
Optimal
ha
Optimal in H for
rule for 2
All decision rules
H
(a) Optimal
(b) Known suboptimal
(c) Unknown suboptimal
Figure 3: We analyze IDT for optimal decision makers and two cases of suboptimal decision makers. (a) In the optimal case (Section (4.1). the decision maker chooses the optimal decision rule / for their loss parameter from all possible rules. (b) In the known suboptimal case (Section 4.2) the decision maker chooses from a restricted hypothesis class H. which may not contain the overall best decision rule. (c) In the unknown suboptimal case (Section 4.3), the decision maker chooses any of several hypothesis classes H E HI and then uses the optimal rule within that class, which may not be the optimal rule amongst all classes. This case is more difficult than (b) because we often need to identify the hypothesis class H in addition to the loss parameter
We write le and R. to denote the loss and risk functions using this loss parameter c. Thus, we can formally define a binary decision problem:
Definition 3.2 (Decision problem). A (binary) decision problem is pair (D,c), where D is distribution over pairs of observations and correct decisions (X,Y) E X' x {0, 1] and c E (0, is the loss parameter. The decision maker aims choose decision rule h X' - {0, 13 that minimizes the risk (h) = ((xx,)))=((((((X)...
As a running example, we consider the decision problem where an emergency room (ER) doctor needs to decide whether to treat a patient for heart attack. In this case, the observation X might consist of the patient's 's medical records and test results; the correct decision is Y if the patient having a heart attack and = 0 otherwise; and the made decision is Y = if the doctor treats the patient and y = O if not. In this case, a higher value of c indicates that the doctor places higher cost on accidentally treating patient not having heart attack, while lower value of e indicates the doctor places higher cost on accidentally failing to treat patient with a heart attack.
In inverse decision theory (IDT), our goal is to determine the loss function the agent is optimizing, which here is equivalent to the parameter c. We assume access to the true distribution D of observa- tions and labels and also finite sample of observations and decisions S = {(x1, 11 ................................ ..... (Im 9m)) where x; ~ i.i.d. and the decisions are made according to the decision rule, i.e. d1 h(x;))
Some of our main results concern the effects on IDT of whether or not decision is made under uncertainty. We now formally characterize such decision problems.
Definition 3.3 (Decision problems with and without uncertainty). decision problem (D,c) has no uncertainty if P (xxX))>>D( = X) E (0,1) almost surely. The decision problem has uncertainty otherwise.
That is, if it is always the case that, after observing and conditioning on X, either Y = with 100% probability or Y with 100% probability, then the decision problem has no uncertainty.
Identifiability and Sample Complexity
We aim to answer two questions about IDT. First, under what assumptions is the loss function identifiable? Second, if the loss function is identifiable, how large must the sample S be to estimate e some precision with high probability? We adopt framework similar that of probably approximately correct (PAC) learning (271. and aim to calculate a è such that with probability at least 1 - 5 with respect the sample of observed decisions, Iè - cl < c. While PAC learning typically focuses on test or prediction error, we instead focus on the estimation error for c. This has multiple advantages. First, it allows for better understanding and prediction across distribution shift or in unseen environments (28). Second, there are cases where we care about the precise tradeoff the decision maker is optimizing for; for instance, in the ER doctor example, there are guidelines on the tradeoff between different types of treatment errors and may want
human behavior
5

---

to determine if doctors' behavior aligns with these guidelines 3 Third, if the decision maker is suboptimal for their loss function (explored in Sections 4.2 and we may not want to simply replicate the suboptimal decisions, but find a better decision rule according to the loss function.
We consider three settings where would like estimate c, illustrated in Figure 3 First, assume that the decision maker is perfectly optimal for their loss function. This is similar to the framework of Swartz et al. 77. However, moving beyond their analysis, we present properties necessary for identifiability and sample complexity rates. Second, we relax the assumption that the decision maker optimal, and instead assume that they only consider restricted set of hypotheses H. which is known to us. Finally, we remove the assumption that we know the hypothesis class that the decision maker is considering. Instead, we consider a family of hypothesis classes; the decision maker could choose the optimal decision rule within any class, which is not necessarily the optimal decision rule across all classes.
4.1 Optimal decision maker
First, we assume that the decision maker is optimal. In this case, the form of the optimal decision rule is simply the Bayes classifier (29).
Lemma 4.1 (Bayes optimal decision rule). An optimal decision rule h for decision problem
(D, e) is given by h(x) = [((()) 2 o} where q(x) = P(XXYND(Y =1 = x) is the posterior probability of class I given the observation x.
That is, any optimal decision rule corresponds to a threshold function on the posterior probability q(z), where the threshold is at the loss parameter Thus, the strategy for estimating e from a sample of observations and decisions is simple. For each observation zt. we calculate (x;)). Then, we choose any è such that (x:;) > <> ÿ: 1; that is, é is consistent with the observed data. From statistical learning theory, we know that a threshold function can be PAC learned in O O1oog(1/0) (1)/)) samples. However, such learning only guarantees low prediction error of the learned hypothesis. We need stronger conditions to ensure that è is close to the true loss function parameter c. The following theorem states conditions which allow estimation of e to arbitrary precision.
Theorem 4.2 (IDT for optimal decision maker). Let
0 and ō > 0. Say that there exists Pe 0 such that P(q(X) E (c, + <)) 2 Pee and P()((X) E [c e, c)) 2 P&t. Let è be chosen to be
consistent with the observed decisions as stated above, i.e. g(x;) è + 9: = 1. Then ( S
with probability at least
as long as the number of samples m
log(2/6)
Pef
The parameter Pe can be interpreted as the approximate probability density of ((X) around the threshold c. For instance, the requirements of T'Thoree 4.2 are satisfied if the random variable (XX) has a probability density of at least p.. on the interval [c p, c + p] for some p 2 e; the requirements of Theoremm 4.2 are more general to allow for cases when (XX does not have a density. The lower the density P... and thus the probability of observing decisions close to the threshold the more difficult inference becomes. Because of this, Theorem (4.2) requires that the decision problem has uncertainty. If the decision problem has no uncertainty according to Definition 3.3 then (X)) e {0, 1 always, i.e the distribution of posterior probabilities has mass only at 0 and I. In this case, Pc.
for small enough and Theorem 4.2 cannot be applied. In fact, as we show in Section 4.4 it is impossible to tell what the true loss parameter e when the decision problem lacks uncertainty. Figure] 2 a- illustrates these results.
4.2 Suboptimal decision maker with known hypothesis class
Next, we consider cases where the decision maker may not be optimal with respect to their loss function. Our model of suboptimality is that the agent only considers decision rules within some hypothesis class H. which may not include the optimal decision rule. This formulation is similar to that of agnostic PAC learning IT. It can also be considered case of restricted "choice set" as defined in the preference learning literature 30 31. It can encompass many types of irrationality or suboptimality. For instance, one could assume that the decision maker is ignoring some of the features in x; then H would consist of only decision rules depending on the remaining features. In the ER doctor example, we might assume that H consists of decision rules using only the patient's s blood pressure and heart rate; this models a suboptimal doctor who unable to use more data to make a treatment decision.

---

While there are many possible models of suboptimality, this one has distinct advantages for preference learning with IDT. One alternative model is that the decision maker has small excess risk, i.e. (h) < (h") + A for some small A where ht is the optimal decision rule. However, this definition precludes identifiability even in the infinite sample limit (see Appendix C Another form of suboptimality could be that the decision maker chooses a decision rule to minimize surrogate loss rather than the true loss. However, we show in Appendix [ for reasonable surrogate losses this is no different from minimizing the true loss. A final alternative model of suboptimality is that the human is noisily optimal; this assumption underlies models like Boltzmann rationality or the Shephard-Luu Luce choice rule 32 26 33 14]. However, these models assume stochastic decision making and also cannot handle systematiicaly suboptimal humans.
In this section we begin by assuming that the restricted hypothesis class H. is known; this requires some novel analysis but the resulting identifiability conditions and sample complexity are very similar to the optimal case in Section 4.1] In the next section, we consider cases where we are unsure about which restricted hypothesis class the decision maker considering.
Definition 4.3. A hypothesis class H is monotone if for any h, h' E H. either h(x) 2 ((xx) Vx E X or h(x) < h' (z) Vx E X.
Definition 4.4. The optimal subset of hypothesis class H. for distribution D is defined as (H) (h E H Be such that h arg min Re((h))
In this section, consider hypothesis classes whose optimal subsets are monotone. That is, changing the parameter e has to either flip the optimal decision rule's output for some observations from 0 to 1, or flip some decisions from to O. It cannot both change some decisions from O to 1 and some from 1 to 0. This assumption is mainly technical; many interesting hypothesis classes naturally have monotone optimal subsets. Any hypothesis class formed by thresholding a function is monotone, i.e H = (h(x) = 1 (x)())= 2 b} b E R). Also, the set of decision rules based on a particular subset of the observed features satisfies this criterion, since optimal decision rules in this set are thresholds on the posterior probability that Y = given the subset of features.
For hypothesis classes with monotone optimal subsets, analysis to that we introduced in Section 4.1 Let he denote a decision rule which is optimal for loss parameter in hypothesis class H. That is, he E arg minkeR Rh).). A key lemma allows to define a value similar to the posterior probability we used for analyzing the optimal decision maker.
prove properties that allow for similar
Lemma 4.5 (Induced posterior probability). Let op) be monotone and define
= TH (x) a sup (fc E [0, [0 hz(x)) = 13U(0)) and [x(x) e inf (fc [0. he(x)= -)(()))
Then all x E X, (x(x) = (x) Define the induced posterior probability of H. as qu(x) &
7u (x) = 4 (x)) (x).
Corollary 4.6. Let be be any optimal decision rule in for loss parameter c. Then for any x E X, he(x) if (x)
and ho(x) 0 (x) < c.
Using Lemma 4.5 the problem of IDT again reduces to learning a threshold; this time, any optimal
classifier in H is threshold function the induced posterior probability (X), as shown in
Corollary 4.6) Thus, to estimate é we calculate an induced posterior probability qx (2;) for each observation 2; and choose any estimate è such that qu (ax) ê Ú: = 1. This allows to state theorem equivalent to Theorem 4.2 for the suboptimal case.
Theorem 4.7 (Known suboptimal decision maker). Let
and 8 > O, and let (H) be monotone. Say that there exists Pe > 0 such that P(qx(()) E (c,c+ <)) Z p&s and P(x E cc- c,c) 2 P.e. Let è be chosen to be consistent with the observed decisions, i.e. qu(xx;) 2 E ih
Then 22- - cl S e with probability at least 1 as long as the number of samples m 2 log(2/0)
4.3 Suboptimal decision maker with unknown hypothesis class
We now analyze the case when the decision maker suboptimal but we are not sure in what manner. We model this by considering family of hypothesis classes H. We assume that the decision maker considers one of these hypothesis classes H E and then chooses a rule h E arg min (h). This case is more challenging because we may need to identify H to identify c.
7

---

One natural family H. consists of hypothesis classes which depend only on some subset of the features:
Hlfear (Hs S (1,...,,n}} where Hs 2 h(x)) ( - f(xs) / :2::s (0.11])
(I)
where æ5 denotes only the coordinates of x which are in the set S. This models a situation where we believe the decision maker may be ignoring some features, but are not sure which features being ignored. Another possibility for H. is thresholded linear combinations of the features in æ, i.e.
Hilinarr A {Hw w E ]R where Hew - {h(z) = 1( x 2 b} 6 E R).
In this case, we assume that the decision maker chooses some weights w for the features arbitrarily but then thresholds the combination optimally. This could model the decision maker under- or over-weighting certain features, or also ignoring some (if w O for some j).
In the high pressure and hectic environment of the ER example, we might assume that the doctor is using only a few pieces of data to decide whether to treat a patient. Here, lilfeat would consist of a hypothesis class with decision rules that depend only on blood pressure and heart rate, a hypothesis class with decision rules that rely on these and also on an ECG, and so on. The difficulty of this setting compared to that of Section 4.2 is that the doctor could be using an optimal decision rule within any of these hypothesis classes. Thus, we may need to identify what data the doctor is using in their decision rule in order to identify their loss parameter c.
Estimating the loss parameter e in the unknown hypothesis class case requires an additional assump- tion on the family of hypothesis classes H., in addition to the monotonicity assumption from Section 4.2
Definition 4.8. Consider a family of hypothesis classes H. Let H E H and H H. Then the minimum disagreement between h and H. is defined as MD(h, H) a inf P(h(X) & h(X)). Definition 4.9. A family of hypothesis classes IHI and hypothesis he E H E I. such that he arg min R. is a-MD-smooth if (PH) is monotone for every H E HH and
VH III Ve' E 10,
MD(her, (pthbe) S (1+ cl)MD(her (H)).
While MD- MD-smoothness is not particularly intuitive at first, it is necessary in some cases to ensure identifiability of the loss parameter c. We present a case in Appendix D.2 where lack of MD- smoothness precludes identifiability.
Theorem 4.10 (Unknown suboptimal decision maker). Let > O and 8 > 0. Suppose we observe decisions from a decision rule he which is optimal for loss parameter in hypothesis class H. H. Let he and H be a-MD-smooth. Furthermore, assume that there exists Pe >> O such that for any P S. e, (((x(() E (c,c+ p)) 2 PeP and (X) E (c p.c)) 2 Pep. Let d 2 VCdim (Uzen?) be an upper bound on the VC-dimension of the union of all the hypothesis classes in IH.
Let ha E arg mingeR Ra(h)) be chosen to be consistent with the observed decisions, i.e. ha(x;) D) for i = 1,...,m. m. Then 12 - c) S with probability at least 1 - 6 as long as the number of samples m 2 Ô ( +)) d+
Theorem 4.10 requires more decision samples to guarantee low estimation error |2 cl. Unlike
Theorems 4.2) and 4.7 the number of samples needed grow with the square of the desired precision 1/62. There also dependence on the VC-dimension of the hypothesis classes H E H. since are not sure which one the decision maker is considering.
Since our results in this section are highly general, it may be difficult to see how they apply to concrete cases. In Appendix [. we explore the specific case of IDT in the unknown hypothesis class setting for Hi defined in (1. We give sufficient conditions for MD-smoothness to hold and show that the sample complexity grows only logaramithically with n, the dimension of the observation space X, if the decision maker is relying on sparse of features.
4.4 Lower bounds
Is there any algorithm which can always determine the loss parameter e to precision e with high probability using fewer samples than required by Theorems 4.2 and 4.7) We show that the answer
8

---

is no: our previously given sample complexity rates are minimax optimal up to constant factors. We formalize this by considering any generic IDT algorithm, which we represent as function à (X' x 10,1)) - (0. 1). The algorithm maps the sample of observations and decisions S to an estimated loss parameter i(S). The algorithm also takes as input the distribution DD and in the suboptimal cases the hypothesis class H or family of hypothesis classes HI, but we leave this dependence implicit in our notation. First, we consider the optimal (Theorem (4.2 and known suboptimal (Theorem 4.7p cases; since these are nearly identical, we focus the optimal case.
Theorem 4.11 (Lower bound for optimal decision maker). Fix O < 6 < 1/4, 0 < 8 S 1/2, and 0 Pe 1/8c. Then for any IDT algorithm c(.), there exists decision problem (D, c) satisfying the conditions of Thhhorem 4.7 such that y
log(/26) implies that P((((() - c 2 6) > 6.
8pet
Corollary 4.12 (Lack of uncertainty precludes identifiability). Fix 0 <E < 1/4 and suppose a decision problem (D, c) has no uncertainly. Then for any IDT algorithm 8(), there is a loss
purameter and hypothesis class H such that for any sample size m, P(()(()) - c 2 c) 2 1/2.
shows that lack of uncertainty in the decision problem means that no algorithm can learn the loss parameter c to a non non-trivial precision with high probability. Thus. uncertainty is required for IDT to learn the loss parameter c. Since e represents the preferences of the decision maker, decisions made under certainty do not reveal precise preference information. In Appendix D we explore lower bounds for the unknown suboptimal case (Section 4.3 and Theorem 4.10).
Corollary shhws
5
Discussion
Now that we have thoroughly analyzed IDT, we explore its applications, implications, and limitations.
5.1 IDT for fine-grained loss functions with applications to fairness
First, we discuss an extension of IDT to loss functions which depend not only on the chosen decision y= h(X) and the ground truth Y, but on the observation X as well. In particular, we extend the formulation of IDT from Section to include loss functions which depend on the observations via a "sensitive attribute" A A. We denote the value of the sensitive attribute for an observation by a(x). We again assume that the decision maker chooses the optimal decision rule for this extended loss function:
h E arg min, E(x,r) (((())))(((())).))))))>))))))>>) Y, a()))
(2)
This optimal decision rule h E H is equivalent set of decision rules for every value of A, each of which is chosen to minimize the conditional risk for observations with that attribute value:
h(x)= ha(m) (x) where
ha E arg min Exx,r)=D(((()))
a, a(X)= a].
h
In this formulation, each attribute-specifi decision rule h, minimizes an expected loss which only depends on the made and correct decisions h( (X) and Y over a conditional distribution. Thus, we can split a sample of decisions into samples for each value of the sensitive attribute and perform IDT separately. This will result in loss parameter estimate é for each value of a.
Once we have estimated loss parameters for each value of A, we may ask if the decision maker is applying the same loss function across all such values, i.e. if = Ca' for any a, a' E A. If the loss function is not identical for all values of A, i.e. if c. * Ca', then one might conclude that the decision maker is unfair or discriminatory against observations with certain values of A. For instance, in the ER example, we might be concerned if the doctor is using different loss functions for patients with and without insurance. Concepts like these have received extensive treatment in the machine learning fairness literature, which studies criteria for when decision rule can be considered "fair." One such fairness criterion is that of group calibration, also known sufficiency R4 35 36]:
Definition 5.1. A decision rule h X + {0, 1} for a distribution (X, Y) ~ D satisfies the group
calibration/sufffiiennyy fairness criterion if there is function r X + R and threshold t E R such that h(x) = [[r(z)= 2 t} and r satisfies Y 1 A r(X).
Testing for group calibration is known to be difficult because of the problem of infra-marginality 337 While complex Bayesian models have previously been used to perform a "threshold test" for group calibration, we can use IDT to directly test this criterion in an observed decision maker:

---

Lemma 5.2 (Equal loss parameters imply group calibration). Let h be chosen as in 2 where E(g, y, a) co if -- and y 0. l(g. y. =1 co if = and y = 1, and ((..ya.) otherwise. Then h satisfies group calibration (sufficiency) if = Cal for every a, a' E A.
Conversely, if there exist a, a' such that Ca + ca and (X) E (Ca) > O, then h does not satisfy group calibration.
If we can estimate Cu for decision rule h for each E A, then Lemma 5.2 allows us to immediately determine if h satisfies sufficiency. The minimax guarantees on the accuracy of IDT may make this approach more attractive than the Bayesian threshold test in many scenarios.
5.2 Suboptimal decision making with and without uncertainty
We have far compared the effect of decisions made with and without uncertainty on the identifia- bility of preferences; here, we argue that uncertainty also allows for much more expressive models of suboptimality in decision making. In decisions made with certainty, suboptimality only take two forms: either the decision maker is noisy and sometimes randomly makes incorrect decisions, the decision maker is systematically suboptimal and always makes the wrong decision. Neither seems realistic in the ER doctor example: we would not expect to the doctor to randomly choose not to treat some patients who are clearly having heart attacks, and certainly not expect them to never treat patients having heart attacks. In contrast, the models of suboptimality we have presented for uncertain decisions allow for much more rich and realistic forms of suboptimal decision making, like ignoring certain data or overr/uunderweeiihting evidence. We expect that there are similarly more rich forms of suboptimality for uncertain sequential decision problems.
generally
5.3 Limitations and future work
While this study sheds significant light on preference learning for uncertain humans, there are some limitations that may be addressed by future work. First, while we assume the data distribution D of observations X and ground truth decisions Y is known, this is rarely satisfied in practice. However, statistics is replete with methods for estimating properties of a data distribution given samples from it. Such methods are beyond the scope of this work, which focuses on the less-studied problem of inferring decision maker's loss function. Our work also lacks computational analysis of algorithms for performing IDT. However, such algorithms are likely straightforward; we decide to focus on the statistical properties of IDT, which are more relevant for preference learning in general. Finally, we assume in this work that the decision maker is maximizing expected utility (EU), or equivalently minimizing expected loss. In reality, human decision making may not agree with EU theory; alternative models of decision making under uncertainty such as prospect theory are discussed in the behavioral economics literature (38). Some work has applied these models statistical learning 39.. but we leave their implications for IDT to future work.
Conclusion and Societal Impact
We have presented analysis of preference learning for uncertain humans through the setting of inverse decision theory. Our principle findings are that decisions made under uncertainty can reveal more preference information than obvious ones; and, that uncertainty can alleviate underspecification in preference learning, even in the case of suboptimal decision making. We hope that this and other work preference learning will lead to AI systems which better understand human preferences and can thus better fulfill them. However, improved understanding of humans could also be applied by malicious actors to manipulate people or invade their privacy. Additionally, building Al systems which learn from human decisions could reproduce racism, sexism, and other harmful biases which widespread in human decision-making, Despite these concerns, understanding human preferences is important for the long-term positive impact of AI systems. Our work shows that uncertain decisions can be valuable source of such preference information.
Acknowledgments and Disclosure of Funding
We would like to thank Kush Bhatia for valuable discussions, Meena Jagadeesan, Sam Toyer, and Alex Turner for feedback on drafts, and the NeurIPS reviewers for helping improve the clarity of
10

---

the paper. This research was supported by the Open Philanthropy Foundation. Cassidy Laidlaw is also supported by National Defense Science and Engineering Graduate (NDSEG) Fellowship.
References
[1] Ralph Hertwig and Ido Erev. The Descripiion-Experienne Gap in Risky Choice. Trends in Cognitive Sciences, 13(2)5117-523, December 2009. ISSN 1364-6613, doi: 10.1016//..ics.20000 2009009.004 URL
httg:://ww..cceeeddrees wwwp://wwccennccieeetcooooo wttp://wwwwccccc.ooooooooooooaaa
[2] Andrew Y. Ng and Stuart J. Russell. Algorithms for Inverse Reinforcement Learning. In ICMI, volume 1, page 2, 2000.
Sendhil Mullainathan and Ziad Ohermeyer. A Machine Learning Approach Low-Valu Value Hcalth Care: Wasted Tests, Missed Heart Attacks and Mis-predictions. Technical report, National Bureau of Economic Research, 2019.
[4] Stuart Armstrong and Sören Mindermann. Occam's Razor is Insufficient to In- fer the Preferences of Irrational Agents. Advances in Neural Information Process- ing Systems, 31, 2018. URL httpp:://proceeding neur.pp..cc/ppprr/011.. Aat.aaat---btttttthhaaaa
[5] Jaedeug Choi and Kee-Fung Kim. Inverse Reinforcement Learning in Partially Observable Environments. Journal of Machine Learning Research, 12(21))691-730, 2011. ISSN 1533-7928. URL http:// jmlr
choilla.htm
[6] Hamid R. Chinaei and Brahim Chaib-Draa. An Inverse Reinforcement Learning Algorithm for Partially Observable Domains with Application on Healthcare Dialogue Management. volume 1, pages 144-149, December 2012. doi: 10. 109//CMLA.2112..111
[7] Richard Swartz., Dennis Cox, Scott Cantor, Kalatu Davies, and Michele Follen. Inverse Decision Theory. Journal of the American Statistical Association, 101(473):1-8 March 2006. ISSN 0162-1459, doi: 10.119901122445500 10119000011145500000999 URL https: htat:s://mmstat tandfonline wtt../////ooo///oo/o 1198/ 016214505000000998
Publisher: Taylor & Francis.
[8] Kalatu Davies. Inverse Decision Theory with Medical Applications. PhD thesis, Rice University, Houston, Texas, May 2005. URLLaattp:://shhoaarret rice. http///annn///111//77666
[9] Rohin Shah, Noah Gundotra, Pieter Abbeel, and Anca Dragan. On the Feasibility of Learning, Rather than Assuming. Human Biases for Reward Inference. In International Conference Machine Learning, pages 5670-5679. PMLR, 2019.
[10] David Haussler. Decision Theoretic Generalizations of the PAC Model for Neural Net and Other Learning Applications. Information and Computation, 100(1):7--150 September 1992. ISSN 0890-5401. doi: (00006//8800-44112))90000000 0890540192900100
URL (RRLLLtts://www.oot http:pp:/www..ccceeeeeeeeeeeeees htt.://wwwaaaaccecccccc///eaaaaa
[11] Michael J. Kearns, Robert E. Schapire, and Linda M. Sellie. Toward Efficient Agnostic Learning, Machine Learning, 17(2): November 1994. ISSN 1573-0565. doi: 10.10077/F00999466. URL URL //doi. 1007 BF00993468
[12] Pieter Abbeel Andrew Y. Ng. Apprenticeship Learning via Inverse Reinforcement Learning. In Proceedings of the twenty-first international conference on Machine learning, page 1, 2004.
[13] Deepak Ramachandran and Eyal Amir. Bayesian Inverse Reinforcement Learning. In IJCAI, volume 7, pages 2586-2591, 2007.
[14] Brian D. Ziebart, Andrew L. Maas, J. Andrew Bagnell, and Anind K. Dey. Maximum Entropy Inverse Reinforcement Learning. In Aaai, volume 8, pages 1433-1438. Chicago, II, USA, 2008.
[15] Justin Fu, Katie Luo, and Sergey Levine. Learning Robust Rewards with Adversarial Inverse Reinforcement Learning, arXiv preprint arXiv:1710. 12448, 2017.
[16] Gaurush Hiranandani, Shant Boodaghians, Ruta Mehta, and Oluwasanmi Koyejo. Performance Metric Elicitation from Pairwise Classifier Comparisons. 380v:/806.0182. [cs, stat]. January 2019, URL arXiv: 1806.01827.
attp://arxivv org/abs/1806 abs/ 1806. 01827

---

[17] Gaurush Hiranandani. Shant Boodaghians. Ruta Mehta, and Oluwasanmi O Koyejo. Multiclass Per- formance Metric Elicitation. In H. Wallach, H. Larochelle, A. Beygelzimer, d'lextquotesingle Alché-Bue, E. Fox, R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 9356 9365. Curran Associates, Inc., 2019. URL http://papers. httpt//.iipp..cpppeeeeeeeeeees ccpperr
9133 multiclass per.elassspperrraarrrrreeee metric- wli.itatiniicciioo......
[18] Gaurush Hiranandani, Harikrishna Narasimhan, and Oluwasanmi Koyejo. Fair Performance Metric Elicitation. arXiv:2006. 12732 fcs, stat], November 2020. URL htttp://arii..rrrg.///// abtp//bb.//002222 arXiv: 12732.
[19] Erdem Biyik and Dorsa Sadigh. Batch Active Preference-Basee Leamning of Reward Functions. In Pruceedings of The 2nd Conference on Robot Learning. pages 519-528, PMLR, October 2018. URL ISSN: 2640-3498.
httpa://proceedinn mlr, pprpss//vr/biyiikk..... html
[20] Sören Mindermann, Rohin Shah, Adam Gleave, and Dylan Hadfield-Menell. Active Inverse Reward Design, 1809:08000000000 (cs, stat], November 2019. URL htttt:://aaxx...or//aaa 1809. 03060 arXiv: 1809.03066
[21] Erdem Bıyık, Malayandi Palan, Nicholas C. Landolfi, Dylan P. Losey, and Dorsa Sadigh. Asking Easy Questions: A Usee-Friendly Approach to Active Reward Learning. arXiv:9910.04365 [es], October 2019.
Jttp:///:/// hwwp:/..rg///baee/be wwwgg//bb/1999 04365 arXiv: 1910.04365.
[22] Kush Bhatia, Peter L. Bartlett, Anca D. Dragan, and Jacob Steinhardt. Agnostic Learning with Unknown Utilities. arXi::2144.08482 [es, stat], April 2021. URL RtL.htt::// http:://aaaxiv..r//aa////// 08482 arXiv: 2104.08482.
[23] Michele Cohen, Jean- Yves
Jean-Yves Jaffray, and Tanios Said. Experimental Comparison of Individual Behavior Under Risk and Under Uncertainty for Gains and for Losses. Organizational Behavior and Human
Decision Processes, 39(1); 22, February 1987. ISSN 5978. doi: 101101107449-977888899990007 997804)90443344
URL |RL/https:
http::: :
[24] Charles A. Holt and Susan Laury. Risk Aversion and Incentive Effects. The American Economic Review, 92(5); 1655, 2002. ISSN 0002-8282. URL/https://ww// jstor wwtp:/jjsoooooorttseooe orggsttabeee303320222 Publisher: American Economic Association.
[25] Tamás Csermely and Alexander Rabas. How Reveal People's Preferences: Comparing Time Consistency and Predictive Power of Multiple Price List Risk Elicitation Methods. Journal of Risk and Uncertainty, 53 (2):107-136, 2016. ISSN 0895-5646. doi: 1007/sl 166-016-9247-6.
[26] R. Duncan Luce. The Choice Axiom After Twenty Years. Journal of Mathematical Psychology, 15 (3):215-233, June 1977. ISSN 2496. doi: sciencedirect. wttp:///wcmmneeeeaaaaaaaa///////
URL https:///// //www
[27] Leslie G. Valiant. A Theory the Learnable. Communications of the ACM, 27(1111134-1111 1984. Publisher: ACM New York, NY, USA.
[28] Adam Gleave, Michael Dennis. Shane Legg, Stuart Russell, and Jan Leike. Quantifying Differences in Reward Functions. In International Conference on Learning Representations, 2021. URL https
[29] Luc Devroye, László Györfi, and Gábor Lugosi. A Probabilistic Theory of Pattern Recognition, volume 31. Springer Science & Business Media, 2013.
[30] Hong Jun Jeon, Smitha Milli, and Anca D. Dragan. Reward-Rational (Implicit) Choice: A Unifying Formalism for Reward Learning. arXiv:2002.044 04833 [cs], December 2020. URL httt:://arziv....////// org/
abs/2002. 04833
arXiv: 2002.04833.
[31] Rachel Freedman, Rohin Shah, and Anca Dragan. Choice Set Misspecification in Reward Inference. (XXi:2101107691 [cx], January 2021. http://azz orciiivvorr//aaa prg/abs/ 2101. 07691 arXiv: 2101.07691.
[32] Roger N. Shepard. Stimulus and Response Generalization: A Stochastic Model Relating Generalization Distance in Psychological Space. Psychometrika, 22(4):325 345, December 1957. ISSN 1860-0980. doi: 10. 10.10/8022288867. URL
org/10 1007 (T0.000000008666777
[33] Chris L. Baker, Joshua B. Tenenbaum, and Rebecca R. Saxe. Goal Inference as Inverse Planning. In Proceedings of the Annual Meeting of the Cognitive Science Society, volume 29, 2007. Issue: 29.
12

---

[34] Jon Kleinberg, Sendhil Mullainathan, and Manish Raghavan. Inherent Trade-Offss in the Fair Determination of Risk Scores. arXivv vrXiv:16000 (ete:::o69.0888 [cs, statj, November 2016. URL http::/arxiv, org/ abs/ 1609
05807
arXiv: 1609,05807.
[35] Lydla T. Liu, Max Simchowitz, and Moritz Hardt. The Implicit Faimess Criterion of Unconstrained Learning. In International Conference Machine Learning, pages 4051-4060. PMIR, May 2019. URL.
http://proceeddigga mlr Saaar-pree//v9///11111 html ISSN: 2640-3498.
[36] Solon Barocas, Moritz Hardt, and Arvind Narayanan. Fairness and Machine Learning. fairmlbook.org. 2019.
[37] Camelia Simoiu, Sam Corbett-Davies, and Sharad Goel. The Problem of Infra- Marginality in Outcome Tests for Discrimination. The Annals of Applied Statistics, 11
(3),
September 2017. ISSN 1932-6157. doi: 10.1214/1-A0ASIIO URL https
//projecteuclid org/
awt.://maaaaaalaae The She-problem-one of sef--infra-masn manra--arginaltty-yy org.://ae.....aoooo.ooooooooooon
1214/
17-ADAS1058 full
[38] Daniel Kahneman and Amos Tversky. Prospect Theory: An Analysis of Decision under Risk. Econometrica, 47(2):263-29) 1979. ISSN 0012-9682. doi: 10.2307/1914185. URL https: https://www.jstonn org/
stable/1914185 Publisher: [Wiley, Econometric Society).
[39] Liu Leqi, Adarsh Prasad, and Pradcep K Ravikumar. On Human-Aligne Aligned Risk Minimization. In H. Wallach, H. Larochelle, Beygelzimer, F. d'lextquotesingle Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 15064. Curran Associates, Inc., 2019. URL
http://papere nips wttpsctp.ppppaaceeee /94pe//99942-0 /942/ on human aliggddg-ddd- risk-miniiizztiinn pdf
[40] V. Vapnik. Estimation of Dependences Based on Empirical Data. Information Science Statistics. doi: 10.100770-387-44339-7 URI.
Springer- New York, 2006. ISBN
www.wue..rnngrr..... com/ gp/bgok//pp//ooo 9780387308644
[41] Anselm Blumer, Ehrenfeucht, David Haussler, and Manfred K. Warmuth. Learnability the Vapmik-Chervonenkii Dimension. Journal of the ACM, 3644)9929-965, October 1989. ISSN 0004-5411, 1557-735X. doi: 10.1 145/76339977667
htLhstts:://dl acm. org/ /oo//o//1..0/ 1114//63399.. 76371
[42] Jifí Matoušek and Jan Vondrák. The Probablistic Method. Lecture Notes, Charles University, Prague, Czech Republic, March 2008.
[43] D. Angluin and G. Valiant. Fast Prohabilistic Algorithms Hamiltonian Circuits and Match- ings. Journal of Computer and System Sciences, 18(2):155-193, April 1979. ISSN 0022-0000. doi: 10. 00.10160002--00000 (000009000077 002200007990045X
[44] Andrzej Ehrenfeucht, David Haussler. Michael Kearns, and Leslie Valiant, A General Lower Bound on the Number of Examples Needed for Learning. Information and Computation, 82(3):247-261, 1989. Publisher: Elsevier.
[45] V. Vapnik. Principles of Risk Minimization for Learning Theory. Advances in Neural Informa- tion Processing Systems, 4, 1991. URL http:::/pproceeeingga weeripp..c/pppeee.. 1ttpaapeee/99///ahh.. 71adffbbatii$/6cra0222222b2aabb
[46] Lorenzo Rosasco, Ernesto De Vito, Andrea Caponnetto, Michele Piana, and Alessandro Verri. Are loss functions all the same? Neural Computation, 1665);1063 1076, May 2004. ISSN 0899-7667. doi: 10. 00.1162009976644733355004
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section 5.3
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See
Section 6
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
13

---

2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] We include all assumptions in the theorems and lemmas stated in the main paper.
(b) Did you include complete proofs of all theoretical results? [Yes] Complete proofs are
presented in Appendix A
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits. hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "oJRHb7HUhJp", "reviewer": "Reviewer_FKEy", "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. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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:\n\n(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. \n(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)?\n(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?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2 hours"}, "extra_text": {}}, {"review_id": "fYNCXO1KS6s", "reviewer": "Reviewer_gz3s", "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. \n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nThe findings are not only interesting - it is easy to see they it could be used to develop better preference learning techniques.\n\nThe 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.\n\nThe 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_. \n\n\n___Detailed comments___\n\nWell-written abstract and introduction\n\nThm 4.2: how do you account for the fact that the posterior changes after each new sample? \n\nPlease explain MD-smoothness and how plausible it is. This is important if you want theorem 4.10 to be a main contribution.\n\nSome definitions are lacking. \n- Please define the human policy\n- 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.\n- Please define uncertainty (see above). Uncertainty in what?\n- Please define the posterior probability, conditioned on some data. And the distribution over posterior probabilities\n\nThe paper has somewhat disparate contributions ranging from decisions under uncertainty to suboptimal decisions. Perhaps these could be separated into two papers.\n\nTypo: “between between”\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "7A70lPX6B2v", "reviewer": "Reviewer_FDLv", "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.\n\n ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nThe risks of the paper that would push me towards rejection are:\n- Significant math errors—I couldn't find any, but I did not check thoroughly.\n- 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.\n\nMinor 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.\n\nPost-response: I am maintaining my score. The authors proposed changes will increase clarity.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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.\n\nI do not consider negative societal impact to be an issue with this paper.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3.5"}, "extra_text": {}}]

Author rebuttal:

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)