Occam's razor is insufficient to infer the preferences of irrational agents
Inverse reinforcement learning (IRL) attempts to infer human rewards or preferences from observed behavior. Since human planning systematically deviates from rationality, several approaches have been tried to account for specific human shortcomings. However, the general problem of inferring the reward function of an agent of unknown rationality has received little attention. Unlike the well-known ambiguity problems in IRL, this one is practically relevant but cannot be resolved by observing the agent's policy in enough environments. This paper shows (1) that a No Free Lunch result implies it is impossible to uniquely decompose a policy into a planning algorithm and reward function, and (2) that even with a reasonable simplicity prior/Occam's razor on the set of decompositions, we cannot distinguish between the true decomposition and others that lead to high regret. To address this, we need simple 'normative' assumptions, which cannot be deduced exclusively from observations.
This paper presents a novel and important insight in value alignment: that the No Free Lunch theorem for inferring human preferences cannot be alleviated using simplicity priors. It also claims to introduce this theorem, which was however already proved in Everitt et al, 2017 (as Theorem 11). The paper states that "A No Free Lunch result analogous to theirs applies in our case" (section 4.1), but it's not clear to me in what sense this result is analogous rather than identical (since the theorem statement and assumptions are exactly the same). This paper presents a different proof for the No Free Lunch theorem - please make clear how this proof is an improvement on the proof in the Everitt et al paper.  The presentation of the main insight (that simplicity priors don't work) has some issues as well. The argument relies on a key assumption that B(p-dot, R-dot) is complex even given human policy pi-dot (in section 5.2 on informal complexity results), which is made precise as l_L(pi-dot, B(p-dot, R-dot)) > l_L(pi-dot) + 5C (in section 5.4 on formal complexity results). This is a strong assumption that is not justified in the paper, and the coefficient 5 for the constant C is chosen in a seemingly contrived way to make the proof of Theorem 8 work out. The larger the constant C, the stronger this assumption is, and the constant C could be large, since it needs to simultaneously satisfy all the inequalities in Theorem 7. For the same reason, the result of Theorem 7 is not very impressive: the three pairs of interest are among the 2^(-K) N > 2^(l_L(pi-dot) + 4C) simplest pairs in the language L, which is exponential in C and thus is very large if C is large. The paper should provide some upper bounds on the value of C to make these results more meaningful. I expect the central claim of the paper probably still holds, and the informal argument in section 5.2 makes sense, but it needs more rigorous support.  The paper is clearly written and well-motivated, though a bit unpolished: - There are some incorrect theorem labels: Corollary 4 refers to theorems 4.1 and 4.2, which should be theorems 1 and 3. - Some terms are not defined before they are used, e.g. "simple function". - The conclusion section ends abruptly and seems unfinished.  The paper includes a thorough literature review and makes clear how this work relates to previous works and how this approach is more general than previous approaches to the problem. It opens up new avenues for research into normative assumptions for deducing human preferences from behavior.   UPDATE after reading author feedback:  - The explanation of the assumption that B(p-dot, R-dot) is complex given the human policy seems convincing, so I'm happy to increase my score. - I still think there is not much novelty in the NFL theorem. The planning function in this setting is analogous to the reward corruption function in the Everitt et al (2017) paper. The Everitt paper's NFL theorem shows that if we don't assume anything about the reward corruption function, the worst-case regret of any policy is high. This paper's NFL theorem analogously shows that if we don't assume anything about the planning function, the worst-case regret of any policy is high. The statement in the author feedback that the setting in the Everitt paper is "unrelated to reward inference" does not seem right, since that paper is about the agent's ability to infer the true reward function. Thus, I don't think it took much work to transfer the NFL theorem to the preference inference setting.  Overall, I would recommend that the authors put less emphasis on the NFL theorem and more emphasis on the "Simplicity does not help" section, since that is the main novel and impactful contribution of the paper.