Characterising Partial Identifiability in Inverse Reinforcement Learning For Agents With Non-Exponential Discounting

We thank reviewer HKSo for their review! Our responses to your questions are as follows:

Weaknesses:

1. To say that a policy is sophisticated is essentially to say that it satisfies a certain stability criterion --- namely, if $\pi$ is sophisticated, then the agent never has any (local) incentive to deviate from $\pi$. One way to understand this is that a sophisticated policy is somewhat analogous to a Nash equilibrium, if the agent at each time step is thought of as a separate decision maker (which is justified by the fact that its preferences are not temporally consistent). Another way to understand it is that if a policy $\pi$ is updated using policy gradients, then a sophisticated policy will be a sort of local optimum (though it may not necessarily be an attractor point, in the same way as a Nash equilibrium may not be an attractor point). This also means that it is not always clear how to compare sophisticated policies (again, in the same way as how it is not always clear how to select between Nash equilibria); a policy is simply either sophisticated or not. Thus, sophisticated policies do not give us an unambiguous notion of "optimality" (though they are nonetheless a solution concept).
2. We have choosen to quantify identifiability in terms of exponentially discounted optimal policies, because even if humans discount hyperbolically, we typically want to create systems that discount exponentially --- this is why exponential discounting is vastly more common in the RL literature. Therefore, we think the most relevant formalisation is to assume that the observed demonstrator discounts hyperbolically, but that the policy which will be computed with the learnt reward function discounts exponentially. Other choices could be made instead, which might lead to different results. Of course, some alternative formalisations would end up being quite trivial. For example, if $P$ is the equivalence relation under which $R_1 \equiv_P R_2$ iff $R_1$ and $R_2$ have the same sophisticated policies, and $f : \mathcal{R} \to \Pi$ returns a maximally supportive sophisticated policy, then it is immediate from the definition that $f$ is $P$-identifiable, etc. This setup would thus not allow for the derivation of any "deep" results.
3. We agree that experimental evaluations could be interesting, but we consider this to be out of scope for this paper. Similar recent works on identifiability in IRL are also typically theoretical, rather than experimental (see Dvijotham & Todorov, 2010; Cao et al., 2021; Kim et al., 2021; Skalse et al., 2022; Schlaginhaufen & Kamgarpour, 2023; Metelli et al., 2023). Note that the empirical performance of an IRL algorithm for hyperbolic discounting will be heavily dependent on the prior distribution from which the ground truth reward function is sampled, which limits the generalisability of such results. In particular, for any inductive bias of the learning algorithm there exists a prior distribution for the ground truth reward such that the counterexamples identified by our theorems will occur with high probability.

Questions:

1. Note that $\xi$ is a trajectory --- this means that $\pi(\xi)$ does depend on the time step, since it may be sensitive to the length of $\xi$.
2. Again, note that $\xi$ is a trajectory, rather than a state.
3. See above.
4. See above.
5. We think that the most promising solutions will rely on incorporating prior information, or data from other data sources. However, exploring these options is beyond the scope of this paper.

We hope that this clarifies our analysis, and that the reviewer might consider increasing their score!

First of all, we would like to thank reviewer nfpA for their thoughts and questions. Our responses to your feedback and questions are as follows:

Weaknesses:

1. First of all, we would like to note that the main motivation behind our work is the usage of IRL in the context of preference elicitation. That is, the setting where we wish to use IRL to learn a representation of the actual preferences of a human subject. In this setting, it is important that we use a behavioural model that actually represents the decision making process of a human as closely as possible. Now, a vast amount of research in behavioural psychology, and related fields, shows that humans are better modelled as using hyperbolic discounting rather than exponential discounting --- we provide references to some of this research in the introduction to the paper. This means that a behavioural model with hyperbolic discounting will be more accurate than (and hence preferable to) a behavioural model with exponential discounting, all other things being equal. Note also that this is not necessarily the case when IRL is used in the context of imitation learning, since it in this context is not fundamentally important that the learnt reward function represents the actual preferences of the demonstrator, as long as it helps the imitation learning process.
2. Yes, the main results on IRL are given in Section 5, but all results in Section 3 and 4 build towards these results. It would not be possible to derive (or even state) the results in Section 5 without first presenting the results given in Section 3 and 4.
3. We agree that experimental evaluations could be interesting, but we consider this to be out of scope for this paper. Similar recent works on identifiability in IRL are also typically theoretical, rather than experimental (see Dvijotham & Todorov, 2010; Cao et al., 2021; Kim et al., 2021; Skalse et al., 2022; Schlaginhaufen & Kamgarpour, 2023; Metelli et al., 2023).

Questions:

1. This choice was made to make our analysis more tractable. For example, if an optimality criterion corresponds to more than one policy, then we may assume that the demonstrator has some fixed criterion for breaking ties between them. This assumption is not fundamentally important, and can be lifted, at the cost of making some of the theorem statements and proofs more messy. For example, both Theorem 6 and 7 would go through without much modification.
2. To say that an MDP is episodic is simply to say that it cannot run forever; most MDPs used in practice satisfy this criterion. For example, note that any MDP with a bounded time horizon is episodic. The definition used in Proposition 1 is simply somewhat more general.
3. As noted before, the current literature in the behavioural sciences suggests that humans are better modelled as using hyperbolic discounting, rather than exponential discounting. For this reason, we consider the setting with non-exponential discounting in IRL to be both very relevant and under-explored.
4. To quantify the "size" of $\mathrm{Am}(f)$, we need to determine if all reward functions in $\mathrm{Am}(f)$ share some relevant property. There are multiple choices that could be made here, but we have choosen to use (exponentially discounted) optimal policies, for the reasons outlined in Section 5. In short, even if humans discount hyperbolically, we typically want to create systems that discount exponentially --- this is why exponential discounting is vastly more common in the RL literature. Therefore, we should assume that the observed demonstrator discounts hyperbolically, but that the policy which will be computed with the learnt reward function discounts exponentially.

We hope that this clarifies the context of our paper, and that the reviewer will consider increasing their score! We believe that this setting is very relevant, and that our results meaningfully extend the existing literature in interesting and non-trivial ways.

We thank reviewer wg8J for their feedback!

As for the first point, our results and proofs are original and non-trivial extensions of the existing literature. Only a small handful of papers have studied non-exponential discounting in IRL, and none of them have considered the (quite important) problem of partial identifiability. Concepts analogous to sophisticated, naïve, and resolute policies have been proposed in the Decision Theory literature, but doing the work of porting these over to the RL setting is non-trivial, and has (to the best of our knowledge) not been done before. As you can see from our proofs, it is not straightforward to show that these policies are guaranteed to exist in all MDPs, etc. The results about identifiability (in Section 5) are completely original.

The proofs take up ~10 pages, so it would difficult to let the main text include even proof sketches for all our results. However, we can move the MDP construction used in the proof of Theorem 6 to the main text, since this proof is quite central and since the MDP construction is fairly illuminating. We can also add a few short remarks to other proofs, such as e.g. "we can use the Kakutani fixed-point theorem to show that...", etc.

As for the last point, we would expect $\mathrm{Am}(f)$ to be contiguous in the non-exponential setting, but we do not have a proof of this fact. We should also note that we agree that it is not very important whether or not $\mathrm{Am}(f)$ is a singleton. Indeed, in both the exponential and the non-exponential setting, $\mathrm{Am}(f)$ is infinitely large (both in the sense that it has an infinite cardinality, and in the sense that it has an infinite Lebesgue measure). Therefore, we think it is more important to know whether or not all reward functions in $\mathrm{Am}(f)$ are "equivalent" in some relevant sense. This is why we use the notion of $P$-identifiability to express our results in Section 5.

We hope that this clarifies our results and contributions, and that the reviewer may consider increasing their score!