Identifiability and generalizability from multiple experts in Inverse Reinforcement Learning
Authors: Paul Rolland
Luca Viano
Norman Schuerhoff
Boris Nikolov
Volkan Cevher
Venue: NeurIPS 2022 Accept (2022)
Keywords: Inverse Reinforcement Learning

Abstract: While Reinforcement Learning (RL) aims to train an agent from a reward function in a given environment, Inverse Reinforcement Learning (IRL) seeks to recover the reward function from observing an expert's behavior. It is well known that, in general, various reward functions can lead to the same optimal policy, and hence, IRL is ill-defined. However, \cite{cao2021identifiability} showed that, if we observe two or more experts with different discount factors or acting in different environments, the reward function can under certain conditions be identified up to a constant. This work starts by showing an equivalent identifiability statement from multiple experts in tabular MDPs based on a rank condition, which is easily verifiable and is shown to be also necessary. We then extend our result to various different scenarios, i.e., we characterize reward identifiability in the case where the reward function can be represented as a linear combination of given features, making it more interpretable, or when we have access to approximate transition matrices. Even when the reward is not identifiable, we provide conditions characterizing when data on multiple experts in a given environment allows to generalize and train an optimal agent in a new environment. Our theoretical results on reward identifiability and generalizability are validated in various numerical experiments.

Engineering a reward function in Reinforcement Learning can be troublesome certain scenarios like driving 22 robotics (3 and economics/fnance 4 In economics and finance, the reward objective/utility function of the agent are of fundamental importance but are not known a priori ( Identifiability and Generalizability from Multiple Experts in Inverse Reinforcement Learning
Paul Rolland LIONS, EPFL Lausanne, Switzerland paul. roul.rolland@epl1.com ch
Luca Viano LIONS, EPFL Lausanne, Switzerland luca. wiaaviinan@ep...co ch
Norman Schürhoff
SFI, UNIL
Lausanne, Switzerland
norman norman. sewiaannsscheehff@@@uoooooo
Boris Nikolov
Volkan Cevher LIONS, EPFL
SFI, UNIL
Lausanne, Switzerland
Lausanne, Switzerland volkan. www.eereeeer...ccc
boris www.ooooovuii.....
Abstract
While Reinforcement Learning (RL) aims train agent from reward function in a given environment, Inverse Reinforcement Learning (IRL) seeks to recover the reward function from observing an expert's s behavior. is well known that, general, various reward functions can lead to the same optimal policy, and hence, IRL is ill-defined. However, [ showed that, if we observe two more experts with different discount factors or acting in different environments, the reward function can under certain conditions be identified up to constant. This work starts by showing an equivalent identifiability statement from multiple experts in tabular MDPs based on a rank condition, which easily verifiable and shown be also necessary. We then extend our result to various different scenarios. i... we characterize reward identifiability in the case where the reward function linear combination of given features, making it more
be represented interpretable, or when we have access to approximate transition matrices. Even when the reward is not identifiable, on multiple experts in given environment allows to generalize and train an optimal agent in a new environment. Our theoretical results reward identifiability and generalizability are validated in various numerical experiments.
provide conditions characterizing when data
Introduction
In such cases, it may be easier to get demonstrations from expert policy. Therefore, multiple algorithms have been developed to learn from demonstrations, e.g., in inverse reinforcement learning (IRL) and imitation learning (IL.)
In IRL, the goal to recover the reward function maximized by the agent, while in IL the expert demonstrations are used solely to learn nearly optimal policy. In economics/inance, inference the reward function is the focus structural models 11. However, the reward function is often highly parameterized and represented by a low- dimensional set of parameters, or the literature focuses on estimating reduced-fome causal rel relationships but not the true reward function [12 [3] The attractiveness of IRL relies the fact that the reward function is the most "succinct" representation task [14] Indeed, identifying the
large literature on estimation, testing, and policy analysis of
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

reward function for each state-action pair allows generalizing the task to different transition dynamics and environments, which not possible when using IL or highly parameterized structural models.
However, the IRI. problem is unfortunately ill-posed since there always exist infinitely many reward functions for which the observed expert policy is optimal [15] 16]. The problem is known reward shaping, and it is intuitively explained with the fact that, in the long term, the optimal policy is not affected by inflating the reward in the current period and decreasing the one in the next. This difficulty
originated a long debate on advantages and disadvantages of IL and IRL 17-20.
When multiple experts available, differing in the transition matrices of the environments they each act in, and/or their discount factors, IRL can in certain cases infer the true reward function, up to constant [21 23 T. Inspired by M. we derive equivalent necessary and sufficient condition the expert environments, which is easily verifiable, ensuring that the true reward can be identified up to constant shift. When this identifiability condition holds, the state-action dependent rewards can be recovered from expert demonstrations. We then derive identifiability results in various alternative scenarios, e.g., when we only have access approximate transition matrices and, alternatively, when the reward function is known to be a linear combination of given features (24 25
However, full reward identifiability remains strong requirement, and we provide negative result of non- con-identifiability from any number of experts, in the presence of exogenous variables in the MDP. Nonetheless, even when the identifiability condition does not hold, the recovered reward function could still be used to train an optimal expert for a different environment. To this end, we characterize situations where observing multiple experts in given environments allows train optimal agent in a new environment.
2 Related work
Since its introduction in 15
16). the IRL problem has been known to be ill-posed, since the
observed expert policy can be optimal with respect to various reward functions. The set of reward transformations that preserve policy optimality are studied in [26] 16 unidentifiability related to suboptimal experts.
I 27
28
29] studied the
In this paper, we assume access to the optimal entropy regularized policies of multiple experts. Significant progress has been made to construct heuristics that select a single reward function from the set of IRL solutions (often called the feasible set), such as caature-based matching [30, maximum margin IRL
33 maximum relative entropy IRL (31), maximum causal entropy IRL [22
34]. Bayesian IRL. [35 33), first-order optimality conditions 38 339 or second-order optimality
conditions 440 Popular IL algorithms implicitly select a feasible reward function via a convex
reward regularizer 19 42 43 or using preferenceeranking based algorithms [44 45). However, none
of these approaches guarantee the identification of the true reward function.
The problem of identifiability in IRL has been investigated first in 21 (22 that study a setting where the learner can actively select optimal experts in multiple environments. The main result in [21 22 is that interactively querying environments outputs a reward within a constant shift from the true one. The multiple experts setting has also been studied in 46) but in the context of value alignment verification where the aim is not to recover the reward function but rather verify that the value function
of the agent is close to a target value. IRL from multiple MDPs also appears in 23 where the authors consider the problem of learning a reward function compatible with dataset of demonstrations collected by multiple experts. addition, [47 study structural conditions on the MDP for reward identification in the finite horizon setting and 48 study identifiability in linearly solvable MDPs.
Our work is inspired by M. Our first identifiability result provides an equivalent statement as their value distinguishabiity condition, but can be easily checked in practice, and allows to derive other identifiability results in alternative scenarios. Finally, the motivation for IRL is often predicting
the expert behavior under new transitions dynamics 49 50, 20). We show that for this goal, it not necessary to identify the exact reward, hence we give condition on the observed experts' environments and the test environment under which an optimal expert can be trained in the test environment. This perspective has also been taken in [51]. However, this work requires stronger assumptions on the transfer environment that we avoid in this paper, only requiring access to multiple experts. Moreover, our work contributes to Al safety 54 alleviating the reward hacking and side effects problems (53). Indeed, by restricting the reward to linear combinations of set of chosen

---

features, we can provably recover an interpretable reward function inducing the optimal behavior, which is particularly desirable in medical applications [35 [66]
An important consideration for IRI. comes from [57 that formalizes the fact that there exist tasks that can not be induced by optimizing reward function. In this work and in IRL in general, we bypass this difficulty assuming that the expert is optimizing a reward function.
2.1 Related works in the economics literature
The economics/finance literature differentiates between axiomatic and revealed preference theory. In axiomatic preference theory, the reward function is posited or derived from basic axioms. In empirical and experimental work, however, simple reward function specifications are often rejected and agents have been shown exhibit behavioral biases and/or non-standard preferences.
Differently, our work relates to the literature revealed preference. Revealed preference theory, initiated by [58 [59], provides an approach to analyze actions (e.g., consumer's demand or investors' trading) by assuming that observed choices provide information about the underlying preferences, or reward function. Revealed preference theory is, hence, similar spirit to IRL. But IRL has not widely been used in revealed preference analysis. We refer to [60] [1 for excellent reviews of recent advances revealed preference theory. The goal of revealed preference theory is to recover the agents' preferences. This task is important because knowledge of the reward function is required to conduct counterfactual policy analysis. Notice that for this task, knowing only the policy function is insufficient. In financial applications, for instance, the impact of Tobin tax can be assessed only knowing investors' preferences for trading (see, e.g. (62))
Preliminaries
A typical RL environment is characterised by Markov Decision Process M A. AT, where S.A are the sets of states and actions respectively, 7 : S x A x S > [0, 1] is the state denotes the probability of arriving in state s' when taking action a in state s. R S x A + R denotes the reward function, y the discount factor and Po is the initial state distribution. At each time step I, an agent observes the current state 8; E S and takes an action ag ~ (-1(s;) where π is the agent's policy which determines a distribution over all actions in A every state. The agent gets a reward ri r(st, uz) and transitions to new state 8141 sampled according to the transition probability T.
transition probability, i.e., T(s' ss,a) (s,'ss,a)
An agent acting optimally in M seeks to maximize its cumulative sum of rewards. In addition, assume that the agent seeks to diversify its possible actions, and hence that maximizes the following entropy regularized sum of discounted rewards:
V (8)
= E
Σ 1=0
(r(ss))))))) + XM((T(1ss))))
where ET denotes the expectation over trajectories {st,, ag J22 starting from state sp and following policy π and M(TT) = E ((a) ) log (a) is the entropy of æ. The function VT is called the (entropy regularized) value function of π.
In Inverse RL, the reward function r is unknown, but we observe an agent acting optimally with respect to some reward function, and we wish to recover the reward function that the agent optimizes. We now recall some results from 11.
Theorem 1. For a fixed policy <{als)= O, discount factor E [0, 1), and an arbitrary choice of function v : S + IR, there is a unique corresponding reward function
r(s,a) a) = (log) Yr T(s'sss, ((s)
s'ES
such that the MDP with reward r yields an entropy-regularizee optimal policy गड. = π and V u.
By observing single expert, it is hence possible to design reward that yields any arbitrary value function, and there are hence [S] degrees of freedom remaining in the recovered reward function. An idea explored in [1 is to assume that we observe two experts in two different MDPs with different
3

---

transition dynamics and discount rates, but acting optimally with respect to the same reward function. The authors show that the reward can be identified up to constant from observing the expert policies provided that the MDPs of the experts satisfy the following value-distinguisen
assumption.
Definition 2. Consider a pair of Markov decision problems on the same state and action spaces, but with respective discount rates " "22 and transition probabilities T T2,22 We say that this pair is value- aaluedisstiggushingg if. for any function o²,u² S - IR, the statement
o (8) 7/
Σ T (5'18,8))e (6') (8) 72 Σ
(d'ss, for all A,SEES (2)
E'ES
implies at least one of v² and is a constart function.
The way this assumption is stated makes it difficult to verify in practice, and the authors of 0 do not attempt to verify their experiments.
Reward identification and generalization
In this section, we present our main theoretical results reward identifiability and generalizability. In the first part, we show an equivalent condition to Definition 2 for reward identification from two
experts (Theorem B). The simplicity of our condition makes it easily verifiable and extendable to various scenarios, in particular to the cases where we observe more than two experts (Corollary (5) when the class of rewards is linearly parameterized with set of given features (Theorem 7
when we have access to approximated transition matrices (Theorem 8 We also provide a negative result on reward non-identifiabilit in MDPs with exogenous variables. which are common in many real world scenarios. In the second part, we analyse reward generalizability. Here, we provide condition guaranteeing that reward compatible with two experts leads an optimal policy in a third environment (Theorem The proofs of the results are all postponed to Appendix A
4.1 Reward identifiability
Consider two Markov decision problems the same set of states and actions S and A respectively. but with different transition dynamics T 77 and discount factors 7/,72. Let E ISS] x X|A| be the reward function common to the two environments, and let ut, o² E RISl be the entropy regularized values functions associated expert policies x and n² in each environment respectively. According to Theorem 1 we have that v(s, a) E S x A.
r(s, a) = A log π (a|s) m Σ (1)()),,))0)))
E'ES
= (als) 72 Σ
(s)
E'ES
We hence deduce that Va E A,
v0' = log
(1- -(1 -(1-7218))
Alog (-la),
(3)
x
where Va E A, E RSS5 is the transition matrix for action and expert i = 1, i... (s,, (s)sss By including all available actions to the experts, we can write
71 TI
-(T - T2, : -(I - -(I-72I0 aili
A log (: Alog n (-la1)
(4)
I
TT aul
Alog 72 (+14 - Alog n (-lqpa))
In order to identify a unique reward function, we need to identify a unique associated value function. We hence want the linear system 4 to yield a unique solution, i.e., the ||]|S] hand side be full rank, i.e., to have rank 2|S). However, is well known that, for any MDP, adding constant to the reward would not change the associated optimal policy. Hence, there is intrinsic
x 2|S) matrix on the left

---

degree of freedom in reward identifiability which is impossible to get rid of from only observing expert policies. In order to identify the reward up to a constant, we need this degree of freedom be the only one in the linear system ④ i.e., the associated matrix to have rank 2|S] summarized in the following theorem, and complete proof can be found in Appendix[A.
This result is
Markov decision problems the same set of states and actions, but with different transition dynamics Tı, T2 and discount factors nH Y2. Suppose that we observe two experts acting each in one of these environments, optimally with respect to the same reward function, in the sense that their policies maximize the entropy regularized reward in their respective environments. Then, the reward function can be recovered up to the addition of constant if and only if
Theorem 3. Consider
- ITa
I- 1-12Ta
rank
=||8| 1.
(5)
1
71 %aa
1 1-72 T2 a/Ai
This condition turns out to be equivalent to Definition 2 as shown at the end of Appendix A. but is stated in way that is easier to check in practice and allows to further characterize identifiaillity in various scenarios. First of all, this result naturally extends to the case where we observe any number of experts. We provide hereafter the result in the case of three experts.
Corollary 4. Consider three Markov decision problems the same set of states and actions, but with different transition dynamics Tí, T2, Ta and discount factors 71, 72, Ya. Suppose that we observe three experts acting each in one of these environments, optimally with respect to the same reward function. Then, the reward function can be recovered up to the addition of a constant if and only if
711 T1
I T2?2
0
I 71 Ti
T2
0
rank
3|S 1.
1 71 T
T3
m TTI
73
T3
mIAi
An interesting scenario is the one where the two experts act in the same environment, and only the discount rate is varied.
Corollary 5. Consider two Markov decision problems on the same set of states and actions, with the same transition matrix T and reward function but different discount factors "/1 # 72. Then, the reward function is identifiable to a constant by observing two experts in (T, (T,72) iff
Ta
TTa
rank
= [S]
-1
Toi
Tajal
Remark 1. Interestingly, condition 7 is equivalent to the condition for identification of a action- independent reward from a single expert, assuming such a reward exists ([I). Corollary 3).
Next, we provide negative result concerning MDPs with exogenous variables, i.e., variable whose dynamics are independent of the agent's 's action. This MDP class is common in economies/finace and has been studied in many real world scenarios including inventory control problems [63], variable weather conditions and customer demands (44 wildfire management (65, and stock market fluctuations (66). We also provide examples involving such variables in the experimental section.
Corollary 6. Suppose that the state space is constructed number of values, i.e., S = {s Rdd 8; E S.). The transition matrices for each action a can be defined by specifying the evolution of each state variable 1+1 depending on (s' a). Suppose that there exists state variable whose evolution only depends on its previous value, but neither on the other state variables nor the action taken: such a variable is called an exogenous variable. Note that this variable can still affect the evolution of all other variables, and its evolution can vary across the environment of the observed experts. Then, the reward function is not identifiable (even up to constant) using any number of experts.
set of variables each taking finite
5

---

Such a negative result motivates the search for milder requirements than arbitrary reward identification, which is too hard of goal achieve certain scenarios.
possible way to improve reward identifiability is to restrict the class of possible rewards, e.g., by constraining it be linear combination of set of chosen features. This is known Feature matching IRL 49 67 67H70]. The smaller the set of features, the easier to identify the reward, as described in the following theorem. This method also allows recover more interpretable reward function, since the recovered parameters are associated with specific features.
Theorem 7. Suppose that restrict the class of possible reward functions to the one parameterized as Tw (8, = w Jan Va E A,8 E S where f : S x A - R2d is given feature function, and W. E IR" denotes the reward parameters. Suppose that the d chosen features are linearly independent,
far
i.e., that f2 V...a
Then, if Im
the reward identifiable up to
Sa
constant by observing experts acting in (T ,T), (T2 72) ) if and only if
71 TT
- 22 :
7 Th
- 72
rank
2|8] d 1.
(8)
0
far
0
fa
far
where fa (fn.a... fajspa))" E S|xd, On the other hand, if 1 & Im
then the reward
falAl
can be exactly recovered provided that the rank of the matrix on the left hand side of equation (8) which augments equation (5) by the features being matched, is 2|S] +
Finally, it usually happens that the exact transition matrices JoEA are not known exactly and must be estimated, e.g., from samples. Verifying condition (5) on the approximated matrices may be misleading since the rank is very sensitive to small perturbations. Hence, we provide hereafter an identifiability condition in the case where only have access to approximated transition matrices.
Theorem 8. Suppose that we approximate the transition matrices (Ta)aEA {Ta) such that
ITT - ll2 Va E A, i 1,2. Suppose that we verify condition (5) using the approximated matrices, iee, we compute the second smallest eigenvalue a of the following matrix:
nd
P2
(9)
92
f2 aial
Then, condition 5 on the true transition matrices {Ta JaaA holds provided that
a>> <></2|AA max(71:72).
(10)
The matrix estimator f. can be obtained from samples. For example, 77y)Lemmaa 5] shows that a high probability bound on the max norm [[T, T, Imax S requires O(c samples from a generative model [72]. This would imply the following bound on the spectral norm:
Remark 2.
IT, Tall2 S |S]][TT - maax & (S However, the dependence on e can be improved as we show
next applying the matrix Bernstein bound [73 74].
Theorem 9. Let fa be the empirical estimator for Ta- Then with probability greater than 5,
log SIAA
2([S) + 1)
SILAA
[Ta - -illall 5 1 |5s1
Va E A.
(11)
2N
3N
Therefore, we obtain I -Tal2 < with ( samples.

---

4.2 Generalization to unknown environments
We now focus on reward generalizability, i.e, the ability to recover a reward function that would allow us to train an optimal policy in a new environment. Suppose that we recover a reward function that is compatible with two experts acting in two MDPs MM and that we use this reward to train an expert in third environment Ma. assuming all environments share the same true reward function but possibly different transition dynamics and discount factors. What condition guarantees that the trained expert will be optimal in M33
This generalization requirement is milder than full reward identification. Indeed, being able to identify the reward (even up to a constant) naturally allows to train an optimal policy in any other environment sharing the same reward. However, even in the presence of non-trivial degrees of freedom, may be the case that any recovered reward suffices to train an optimal policy in given other environment.
Intuitively, the third training environment should not vary too much from the observed environments M2 More precisely. if observing a third expert in environment does not provide any further identification of the reward than with environments 1 and 2, then any reward compatible with environments and leads to an optimal policy in environment 3. The condition is made precise in the following theorem.
Definition 10. Consider three Markov decision problems on the same set of states and actions, but with different transition matrices Tı, T2, T3 and discount factors nn 72, 73- Suppose that we observe two optimal entropy regularized experts with respect to the same reward function in environments and 2. We say that (T -1)s (T2, r22) generalize to (I' na) if any reward compatible with the two experts in environments 1 and 2 leads to an optimal expert in environment 3. The definition naturally extends to more than two observed experts.
Theorem 11. (T), ,2) generalize to (T3, (T)) if and only if
1 --
I I- T2
:
[Tl
I -22
I 71 T1 Tapal
I - T2 1nll
0
rank
rank
- |S]
1 71 Ta
733 73
1 I- MIAI
I - I T2
1 TI TITAIAI RLAI
-
T3
(12)
This condition also necessary, in the sense that, it does not hold, then there exists reward function compatible with experts 1 and 2 but which leads to a sub-optimal policy in environment 3.
One interesting question is whether observing two experts in the same environment with different discount factors allows to generalize to any other expert with arbitrary discount factor. It turns out to be the case under some commutativity constraint on the transition matrices.
Corollary 12. Consider a single environment with transitions' T. Suppose that there exists an action ao E A such that Ta, commutes with To for all E A. Then for any 0 < "1, 72,73 71 * 7/2 (T, m,,, (2,72) generalize to (T, (a).
< 1 with
Remark 3. The commutativity condition cannot simply be removed. Indeed, provide in Ap- pendix A. 9 an example with two actions with non-commutative transition matrices for which condi- tion 12 not satisfied.
5 Experiments
We now present empirical validations of our claims" In particular, we verify the identifiability requirement given by Theorem 3 in the context of randomly generated transition matrices and different gridworlds with uniform additive noise the dynamics.
In addition, we study a Windy- both involving exogenous variables in their state spaces. In agreement with Corollary the reward
and a financial model that we term Serrbulleev-his ted
Code available the following htaklt/ss//gttttut.mmm/////////s
7

---

-30
100
(a) Fa
(b) Fy
(c) Ptrue
(d) Fa
Ptrue
(c)
P.
Ptrue
Figure 1: Comparison between true and recovered reward in Gridworld with an action dependent reward, [S] = 100. be noticed that the reward function r-y recovered changing discount factors is within constant shift from the true reward subplots (b),(e)). The same conclusion holds for recovered from different assee subplots (d).
function not identifiable in these environments, highlighting the necessity of imposing milder requirements than full reward recovery. For example, in Hindy-Gridworlld we show that by observing multiple experts acting in environments with different wind distributions, can generalize, ie.. train an optimal expert in environments with arbitrary other wind distribution, in accordance with Theorem I1 On the other hand, in Strebulaev -heitd, given the additional information that the reward function can be represented as linear combination of some known features, we can identify the reward, validating the condition of Theorem The algorithms are described in Appendix B
5.1 Identifiability experiments
Experiments on Random-Matrices The first experiment involves randomly generated transition matrices and reward function with |S| 18, |A| 5. This setting matches the numerical evidence in []. Their algorithm recovers the reward function but the connection with their theoretical contribution not highlighted. On the contrary, we have theory practice mismatch, since we verify exactly the condition in Theorem 3 In particular, for the 100 random seed we tried the rank of the matrix A is 2|S| 35, then invoking Theorem 3 we can conelude that the reward function is identifiable up to constant shift. We provide visual example of the recovered reward in Figure 4 in Appendix
Experiments on Gridworld As second example of identifiability, we consider Gri Gridworld, where the state space is a squared grid with 100 states while the action set is given by A = (up, down, left, right) with dynamics given by T., (s'|s,a) (1 - a:)aet (s'ls, a) + at (s'|s |s, a) where Taet (s'[s, a) represents deterministic transition dynamics where for example the action right leads to the state on the right with probability 1. If an action would lead outside the grid, then the agent stays in the current state with probability 1. The dynamics U'(s'ls, [[s'|s, a) are instead uniform over the
states that are first adjacent to the current state. In other words, U--1s, a) = (s))(N(ss) Va E A where (s) denotes the set of first neighbors of the state
We generate different environments changing the value of a, choosing a' 0.4 and a 0.2. We notice that, even using the same discount factor 7 0.9, the condition of Theorem 3 holds. When kept fixed, we also notice that the condition of Corollary 5 holds, and hence the reward can be recovered by just varying the discount factor ry of the experts. We numerically verify that the reward can indeed be identified up to a constant shift in these two settings (see Figure
5.2 Generalizability experiments
In this section, we present cases where identifiability is not possible due to the presence of exogenous variables. However, we notice that the generalizability condition Theorem 11 often satisfied, even for test environment with parameters rather different than the environments of the observed experts. We start briefly describing the environments later comment on the results.
Experiments on WindyGridworld The WindyGridworld environment augments the Gridworld state representation by including wind direction. The wind impacts the position transitions by making the agent move one step in the direction of the wind in addition to the action taken. The wind

---

(a) r
(b) Ptrue
Ptrue
(d) Thess
(c) IT
TTrue
Tlest Tioa
Figure 3: Comparison between true and recovered reward (r and Ttrue) from experts in WindyGridworld with |S] = 400. We notice that the reward function is not identified (see (a),
(b). (c)). However, when unseen dynamics we recover the optimal policy under the true reward in subplot (b). The subplot (d) shows the policy Teums recovered from the true reward in difference between the policy recovered from Ptrue and from the recovered reward denoted as π Tie
the recovered reward in subplot (a) train optimal policy under
environment Trest and (e) shows the
directions step i, are sampled i.i.d. from the distribution Pwind, and is hence an exogenous variable. While the reward is not identifiable whatever the number of experts, we can generalize to new environment with an arbitrary wind distribution by observing enough experts in environments with different wind distributions.
In Figure 2b we see that we can obtain better identifiability (although never full identifiability) when increasing the number of experts. Once we have observed ex- perts, we do not get further identifiability by observing more experts, hence leading to generalizability as shown in Figure 2a and Figure 3, We conjecture that this num- ber of experts is linked to the number of values that the exogenous variable, i.e. the wind direction, can take.
exprrs
(a) Generalizability
(b) Identifiability
Figure 2: Figure 2a shows the difference between right and left term of Theorem [1] Figure 2b shows the
Furthermore, although the actions in Grid- world do not exactly commute (because of the boundary), observing two experts in the same environment with different discount factors enables generalizing different discount factor (see Figure Appendix C The condition of Corollary 12 is hence sufficient but not necessary.
difference between columns and rank the matrix in Theorem We have identifiability or generalizability respectively when those values
The Strebulaev Whited environment is the neoclassical investment model in which a firm has Cobb-Dougla production function with decreasing returns to scale, as in 75). The goal of the agent is to maximize profits discounted at rate < Y < 1. The state of the agent is defined by the capital level & 2 0 and an exogenously given persistent stochastic productivity shock z. We can summarize
Experiments on Strebulaev-Win
state by = (ks, =). The next state s' (k',=') determined separately for k and z'. We have that k' (1 d)k: + ak, where ó is the depreciation rate of physical capital and a is today's 's rate of investment which is the action the model. The
variable z evolves according to In p In + where N (O.oo...
The continuous variables k and are discretized according to the scheme proposed in 76 Hence, we obtain discrete process with K possible values for the state variable s = (k, 2) (so [S| = K2) and К values for the action a. the experiments Figure 7 in Appendix C. we choose K consider two environments with different values of a, set to 0.02 and 0.04, respectively. We observe = 799. the reward function
and
that the rank the identifiability matrix 552. Since 552 < 2|S] not identifiable up to constant as expected in MDPs with exogenous states. Nonetheless, when we consider third environment with a, 0.6, the generalizability condition Theorem iTis satisfied. Hence, the expert behavior can be predicted in the third environment (see Figure 7e in Appendix C).

---

5.3 Identifiability experiments with restricted reward class
The final result presents a numerical validation of Theorem 7 in the environment with exogenous state variable. In this model, the true reward function can be ex- pressed as linear combination of the three features given by Sa,a = [=((1 -8)k++ak) (1-))k, ak)", where = (k, z) and the parameter E (0, 1) captures the curvature of the production function. We set p = 0.55. The first feature corresponds to the firm's 's output or sales which is available from the firm's income statement, the second feature is the firm's 's current capital stock net of depreciation which is available from the balance sheet, and the third feature is the level of investment that determines the future level of capital stock. The true reward function can be written as r(s, a) = w fs.a with = [1, -1"=. It can be interpreted as follows: the agent's 's reward of investment is an increase in output/sales, W1 = 1 > O, while the cost of capital is 1 and, hence, investment is costly, W'3 = -1 < O. At the same time, the capital stock is valuable and can be liquidated at price of W2 1 >> 0.
Knowing these features, we can verify that the rank of the matrix in Equation (8). 803 which
is equal to 2|S| + d in this environment (I.S = 400 and d = 3). Invoking Theorem 7 we can conclude that the reward function is identifiable exactly, which verified numerically in Figure X in Appendix Expressing the reward in terms of features hence helps identifiability and interpretability.
6 Conclusion
In this paper, we analyze conditions that guarantee identifiability of the reward function (up to an additive constant) from multiple observed experts maximizing the same reward and facing different transition dynamics. This allows us to train optimal policies in any other environment sharing the same reward with the enviromments of the observed experts. On the other hand, in order to generalize to unknown environments, such strong reward identification is not required, and we provide milder necessary and sufficient condition for generalizability. We also provide identifiability results in a variety of settings, i.e., linearly parameterized reward, approximated transition matrices, observation of any number of experts, as well as a non-identifiability result in the presence of exogenous variables. In the following, we list the main limitations of our work that will be the subject of future studies.
Observing experts in different environments. We saw that observing single expert in one environment cannot lead to reward identification in our setting. We hence need to observe at least two experts acting in different enough environments. To motivate this assumption, note that varying environments are ubiquitous in RL, in particular in Robust RL which deals with the training of experts that perform well in different environments, where the transition dynamics can vary to some extent. It hence rather common to consider that the transition dynamics of given environment can change. This was studied, e.g., in (77-80) where the authors considered different Mujoco environments with varying friction coefficients, or object masses, which influence the dynamics. Also, instead of observing different experts in different environments, we could imagine that we observe a single expert in a single environment that varies over time (but with fixed reward), and that the expert adapts to these changes. Such observations would provide us optimal actions in environments with different transition dynamics, and thus our results would apply. This is of particular interest in economics/fiancee where the environment is in constant evolution.
Assuming entropy regularized experts. When observing real world data, we have to face the fact that humans do not follow this idcalized mathematical model. However, it turns out that our results still hold for the more general class of regularized MDPs [81] where we replace the entropy with any strongly convex function (see Appendix Dj. Whether the flexibility in the choice of the strongly convex regularizer allows to better capture real-world behaviors is an open question.
Acknowledgements
This work has received financial support from the Enterprise for Society Center (E4S) and SNF project 100018_
100018_192584. 192584. This work was supported by the Swiss National Science Foundation (SNSF) under grant number 200021 100021_205011... 1. This project has received funding from the European Research Council (ERC) under the European Union's 's Horizon 2020 research and innovation programme (grant agreement n" 725594- time-data).
10

---

References
[1] Haoyang Cao, Samuel Cohen, and Lukasz Szpruch. Identifiability inverse reinforcement learning. Advances in Neural Information Processing Systems, 34, 2021.
[2] W. Bradley Knox, Alessandro Allievi, Holger Banzhaf, Felix Schmitt, and Peter Stone. Reward (mis)design for autonomous driving, 2021.
[3] T Osa, J Pajarinen, G Neumann, JA Bagnell, P Abbeel, and Peters. An algorithmic perspective on imitation learning. Foundations and Trends in Robotics, 2018.
[4] Arthur Charpentier, Romuald Elie, and Carl Remlinger. Reinforcement learning in economics and finance, 2020.
[5] J. von Neumann and O. Morgenstem. Theory of games and economic behavior. Princeton University Press, 1947.
[6] John W. Pratt. Risk aversion in the small and in the large. Econometrica, 32(1/2): 1964.
[7] Kenneth Joseph Arrow. Aspects of the theory of risk-bearing. Helsinki: Yrjo Jahnsonian Sa tio, 1965.
[8] Daniel Kahneman and Amos Tversky. Prospect theory: An analysis of decision under risk. Econometrica, 47(2):263-291, 1979.
[9] Lars Peter Hansen. Large sample properties of generalized method of moments estimators. Econometrica, 50(4): 1982.
[10] John Rust. Optimal replacement of gme bus engines: An empirical model of harold zurcher. Econometrica, (195):999-13333 1987.
[11] V. Joseph Hotz and Robert A. Miller. Conditional choice probabilities and the estimation of dynamic models. The Review of Economic Studies, 60(3):497-529, 1993.
[12] James Heckman. Sample selection bias as a specification error. Econometrica, 47(1):153-161 1979.
[13] Joshua D. Angrist, Guido W. Imbens, and Donald B. Rubin. Identification of causal effects using instrumental variables. Journal of the American Statistical Association, 91(434):444 455, 1996.
[14] R. S. Sutton and A. G. Barto. Introduction to Reinforcement Learning. MIT Press, 1st edition, 1998.
[15] Stuart Russell. Learning agents for uncertain environments (extended abstract). Annual Conference on Computational Learning Theory (COLT), 1998.
[16] A. Y. Ng and S. J. Russell. Algorithms for inverse reinforcement learning. In International Conference on Machine Learning (ICML), 2000.
[17] Bilal Piot, Matthieu Geist, and Olivier Pietquin. Learning from demonstrations: Is it worth estimating a reward function? Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 17-32. Springer, 2013.
[18] Bilal Piot, Matthieu Geist, and Olivier Pictquin. Bridging the gap between imitation learning and inverse reinforcement learning. IEEE transactions on neural networks and learning systems, 1814)11814 2016.
[19] J. Ho, J. K. Gupta, and S. Ermon. Model-free imitation learning with policy optimization. In International Conference Machine Learning (ICML), 2016.
[20] Justin Fu, Katie I Luo, and Sergey Levine. Learning robust rewards with adverserial inverse reinforcement learning. In International Conference Learning Representations (ICLR), 2018.

---

[21] Kareem Amin and Satinder Singh. Towards resolving unidentifiability in inverse reinforcement learning, 2016.
[22] Kareem Amin, Nan Jiang, and Satinder Singh. Repeated inverse reinforcement learning, 2017.
[23] Amarildo Likmeta, Alberto Maria Metelli, Giorgia Ramponi, Andrea Tirinzoni, Mattco Giuliani, and Marcello Restelli. Dealing with multiple experts and non-stationarity in inverse reinforce- ment learning: an application to real-life problems. Machine Learning, 1109))255112557, 2021.
[24] Rati Devidze, Goran Radanovic, Parameswaran Kamalaruban, and Adish Singla. Explicable reward design for reinforcement learning agents. Advances in Neural Information Processing Systems, 34, 2021.
[25] Daniel Jarrett, Ioana Bica, and Mihaela van der Schaar. Strictly batch imitation learning by energy-based based distribution matching, 2021.
[26] Andrew Y Ng. Daishi Harada, and Stuart Russell. Policy invariance under reward transforma- tions: Theory and application reward shaping.
[27] Joar Skalse, Matthew Farrugia-Roberts Roberts, Stuart Russell, Alessandro Abate, and Adam Gleave. Invariance in policy optimisation and partial identifiability in reward learning, 2022.
[28] Adam Gleave, Michael Dennis, Shane Legg, Stuart Russell, and Jan Leike. Quantifying differences in reward functions, 2020.
[29] Stuart Armstrong and Sören Mindermann. Occam's razor is insufficient to infer the preferences of irrational agents. S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Fesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
[30] Abbeel and A. Y. Ng. Apprenticeship learning via inverse reinforcement learning. In International Conference Machine Learning (ICML), 2004.
[31] N. D. Ratliff, J, A. Bagnell, and M. A. Zinkevich. Maximum margin planning. In International Conference on Machine Learning (ICML), 2006.
[32] B. D. Ziebart, A. Maas, J. A. Bagnell, and A. K. Dey. Maximum entropy inverse reinforcement learning. In National Conference on Artificial Intelligence (AAAI), 2008
[33] Brian D Ziebart. Modeling purposeful adaptive behavior with the principle of maximum causal entropy. PhD thesis, Carnegie Mellon University. 2010.
[34] Abdeslam Boularias, Jens Kober, and Jan Peters. Relative entropy inverse reinforcement learning. In Proc. Intl Conf. on Artificial Intelligence and Statistics (AISTATS), 2011.
[35] Sreejith Balakrishnan, Quoe Phong Nguyen, Bryan Kian Hsiang Low, and Harold Soh. Efficient exploration of reward functions in inverse reinforcement learning via bayesian optimization, 2020.
[36] D. Ramachandran and E. Amir. Bayesian inverse reinforcement learning. International Joint Conference Artifical Intelligence (IJCAI), 2007.
[37] Daniel S. Brown, Russell Coleman, Ravi Srinivasan, and Scott Nickum. Safe imitation learning via fast bayesian reward inference from preferences, 2020.
[38] Matteo Pirotta and Marcello Restelli. Inverse reinforcement learning through policy gradient minimization. Proceedings of the AAAI Conference on Artificial Intelligence, 30(1), Mar. 2016.
[39] Giorgia Ramponi, Gianluca Drappo, and Marcello Restelli. Inverse reinforcement learning from a gradient-based learner. 2020.
[40] Rakhoon Hwang, Hanjin Lee, and Hyung Ju Hwang. Option compatible reward inverse reinforcement learning. Pattern Recognition Letters, 154:83-89, 2022.
12

---

[41] Alberto Maria Metelli, Matteo Pirotta, and Marcello Restelli. Compatible reward inverse reinforcement learning. In Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus. S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[42] Tanmay Gangwani and Jian Peng. State-only imitation with transition dynamics mismatch, In Proc. Intl Conf. on Learning Representations (ICLR), 2020.
[43] Faraz Torabi, Garrett Warnell, and Peter Stone. Generative adversarial imitation from observa- tion. arXiv preprint arXi::1807.06133 2018.
[44] Daniel S. Brown, Wonjoon Goo, Prabhat Nagarajan, and Scott Niekum. Extrapolating beyond suboptimal demonstrations via inverse reinforcement learning from observations, 2019.
[45] Daniel S. Brown, Wonjoon Goo, and Scott Niekum. Better-than-demosstrii imitation learning via automaticaally-ranees demonstrations. In Leslie Pack Kaelbling, Danica Kragic, and Komei Sugiura, editors, Proceedings of the Conference on Robot Learning, volume 100 of Proceedings of Machine Learning Research, pages 330-359, PMLR, 30 Oct-01 Nov 2020.
[46] Daniel S Brown, Jordan Schneider, Anca Dragan, and Scott Niekum. Value alignment ver- ification. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference Machine Learning. volume 139 of Proceedings of Machine Learning Research, pages 1105-1115. PMLR, 28-24/1 Jul 2021.
[47] Kuno Kim, Shivam Garg, Kirankumar Shiragur. and Stefano Ermon. Reward identification in inverse reinforcement learning. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages $495-5505. PMLR, 18-24 Jul 2021.
[48] K. Dvijotham and E. Todorov. Inverse optimal control with linearly-solvable MDPs. In International Conference on Machine Learning (ICML), 2010.
[49] Pieter Abbeel and Andrew Y Ng. Apprenticeship learning via inverse reinforcement learning. In Proc. Inil Conf. on Machine Learning (ICML), 2004.
[50] S. Levine, Popović, and V. Koltun. Nonlinear inverse reinforcement learning with Gaussian processes, In Advances in Neural Information Processing Systems (NeurIPS), 2011.
[51] Alberto Maria Metelli, Giorgia Ramponi, Alessandro Concetti, and Marcello Restelli. Provably efficient learning of transferable rewards. In International Conference on Machine Learning, pages 7665-7676 PMLR, 2021.
[52] Tom Everitt and Marcus Hutter. Avoiding wireheading with value reinforcement learning. In International Conference on Artificial General Intelligence, pages 12-22. Springer, 2016.
[53] Dario Amodei, Chris Olah, Jacob Steinhardt, Paul Christiano, John Schulman, and Dan Mané. Concrete problems in ai safety, 2016.
[54] Jan Leike, David Krueger, Tom Everitt, Miljan Martic, Vishal Maini, and Shane Legg. Scalable agent alignment via reward modeling: a research direction, 2018
[55] Srivatsan Srinivasan and Finale Doshi Velez. Interpretable batch irl to extract clinician goals in icu hypotension management. AMIA Summits on Translational Science Proceedings, 2020:636. 2020.
[56] Daniel Jarrett, Alihan Hüyük, and Mihaela Van Der Schaar. Inverse decision modeling: Learning interpretable representations of behavior. In International Conference on Machine Learning, pages 4755 4771. PMLR, 2021.
[57] David Abel, Will Dabney, Anna Harutyunyan, Mark Ho, Michael Littman, Doina Precup, and Satinder Singh. On the expressivity of markov reward. In M. Ranzato, A. Beygelzimer, Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 7799-7812 12. Curran Associates, Inc., 2021.
13

---

[58] Samuelson Paul. A note on the pure theory of consumer behavior. Economica, 5(17):61-71, 1938.
[59] Paul A Samuelson. Consumption theory in terms of revealed preference. Economica, 15(60):243-
253, 1948.
[60] Thomas Demuynck and Per Hjertstrand. Samuelson's 's approach revealed preference theory: Some recent advances. Paul Samuelson, pages 193 193-227," 2019.
[61] Federico Echenique. New developments in revealed preference theory: decisions under risk, uncertainty, and intertemporal choice. Annual Review of Economics, 12:299-316, 2020.
[62] James Tobin. A proposal for international monetary reform. Eastern economic journal, 43344):13--15, 1978.
[63] S. Joshi, R. Khardon, P. Tadepalli, A. Raghavan, and A. Fern. Solving relational mdps with exogenous events and additive rewards, 2013.
[64] Thomas G. Dietterich, George Trimponias, and Zhitang Chen. Discovering and removing exogenous state variables and rewards for reinforcement learning, 2018.
[65] Sean McGregor, Rachel Houtman, Claire Montgomery. Ronald Metoyer, and Thomas G. Dietterich. Factoring exogenous state for model-free monte carlo, 2017.
[66] Vincent Liu, James Wright, and Martha White. Exploiting action impact regularity and exoge- nous state variables for offline reinforcement learning, 2021.
[67] Andrew Y Ng and Stuart Russell. Algorithms for inverse reinforcement learning. In Proc. Intl Conf. on Machine Learning (ICML), 2000.
[68] Nathan D Ratliff, J Andrew Bagnell, and Martin A Zinkevich. Maximum margin planning. In Proc. Intl Conf. on Machine Learning (ICML), 2006.
[69] U. Syed, M. Bowling, and R.E. Schapire. Apprenticeship learning using linear programming. In International Conference on Machine Learning (ICML), 2008
[70] Eric Heim. A practitioner's guide to maximum causal entropy inverse reinforcement learning, starting from markov decision processes. Technical report, CARNEGIEE-EELLON UNIV PITTSBURGH PA PITTSBURGH United States, 2019.
[71] Michael Kearns. Near-optimal reinforcement learning in polynomial time. In Machine Learning, pages 260-268. Morgan Kaufmann, 1998.
[72] Mohammad Gheshlaghi Azar, Remi Munos, and Bert Kappen. On the sample complexity of reinforcement learning with a generative model, 2012.
[73] Daniel Hsu, Sham M. Kakade, and Tong Zhang. Random design analysis of ridge regression. In Shie Mannor, Nathan Srebro, and Robert C. Williamson, editors, Proceedings of the 25th Annual Conference on Learning Theory, volume 23 of Proceedings of Machine Learning Research, pages 9.1 9.244, Edinburgh, Scotland, 25-27 Jun 2012. PMLR.
[74] Daniel Hsu, Sham M. Kakade, and Tong Zhang. Dimension-free tail inequalities for sums of random matrices, 2011.
[75] Ilya A Strebulaev and Toni M Whited. Dynamic models and structural estimation in corporate finance. Final pre-publication version, published Foundations and Trends in Finance, 6:1 6:1-163, 2012.
[76] George Tauchen. Finite state markov-chain approximations to univariate and vector autoregres- sions. Economics Letters, 17721:177-181, 1986.
[77] Parameswaran Kamalaruban, Yu-Ting Huang, Ya-Ping Hsieh, Paul Rolland, Cheng Shi, and Volkan Cevher. Robust reinforcement learning via adversarial training with langevin dynamics. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
14

---

[78] Lerrel Pinto, James Davidson, Rahul Sukthankar, and Abhinav Gupta. Robust adversarial reinforcement learning. In Proc. Intl Conf. on Machine Learning (ICML), 2017.
[79] Chen Tessler, Yonathan Efroni, and Shie Mannor. Action robust reinforcement learning and applications in continuous control. Proc. Intl Conf. on Machine Learning (ICMI.) 2019.
[80] Luca Viano, Yu-Ting Huang, Parameswaran Kamalaruban, Craig Innes, Subramanian Ra- mamoorthy, and Adrian Weller. Robust learning from observation with model misspecification. arXiv preprint arXiv:2202.0600 2022.
[81] Matthieu Geist, Bruno Scherrer, and Olivier Pietquin. A Theory of Regularized Markov Decision Processes. In International Conference Machine Learning (ICML), 2019.
[82] Terence Tao. 254a, notes 3a: Eigenvalues and sums of hermitian matrices. Terence Tao's 's blog. 2010.
[83] Luca Viano, Yu-Ting Huang, Parameswaran Kamalaruban, Adrian Weller, and Volkan Cevher. Robust inverse reinforcement learning under transition dynamics mismatch. Advances in Neural Information Processing Systems, 34:25917-25931, 2021.
Checklist
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]
(c) Did you discuss any potential negative societal impacts of your work? [No]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- URL)? [Yes]
mental results (either in the supplemental material
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(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, or cloud provider)? [Yes] See the supplementary.
4. If you using existing assets (e.g., code, data, models) or curating/releasing 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 new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'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, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
15


Reviews:
[{"review_id": "qW9xNVZ5cpN", "reviewer": "Reviewer_P6wR", "summary": "The authors propose an approach to solving the ill-posedness of IRL by exploiting multiple experts. In particular, a necessary and sufficient condition on the expert environments is derived, and further extended in different scenarios (e.g. approximated dynamics, linearly parametrized reward). Besides a negative result, a milder generalization requirement is given such that any recovered reward suffices to train an optimal policy in a given other environment.\n\nThe work is mainly theoretical (even though the conditions are numerically verifiable), and limited by a number of strong requirements, but the results are clearly stated, their impact is well described, and the findings constitute a good contribution to the literature.", "questions": "1) In Theorem 7, does the real reward need to belong to the same parametrized space of the recovered reward? Please clarify this in the text\n\n2) The work offers only theoretical conditions to check if the expert's reward con be properly reconstructed but does not comment on how this can be done. Which IRL algorithm can be used to be sure that the recovered reward is actually compatible with the expert's demonstrations?\nFor example, in the numerical results, how was the reward identified?", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well written, and it is mathematically sound. The theoretical results are well described, their requirements clearly stated, and their impact properly discussed.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "eCA2SPjLsZ", "reviewer": "Reviewer_4M5d", "summary": "This IRL theory paper presents a new statement of an identifiability result (first shown in [1]) for recovering a reward function given observations of multiple experts with different discount factors and/or acting under different transition dynamics in tabular MDPs. This paper improves the previous result from [1] by stating the main indentifiability result as a more practically useful matrix rank condition which can be easily verified (Thm. 3). This allows the authors to extend the result to several interesting cases - such as more than 2 experts (Corr. 4), MDPs with 'exogenous variables' (Corr. 6), Linear reward features (Thm. 7), and sample estimated transition dynamics matrices (Thm. 8). The authors also show how their result can be used to derive a reward generalization result (Thm. 11) under weaker conditions, and present numerical experiments on synthetic tabular MDPs to verify their theoretical results.\n\nI have checked the in-text derivations fairly closely and am familiar with prior theory in this area. I have not checked the proofs or extended derivations in the appendices.", "questions": " * The generalization pattern from 2 experts to 3 (and beyond) is not clear to my by comparing Eq 5. and Eq. 6. I.e. I would not be able to predict the structure of the equivalent rank condition for 4 experts. Can you please clarify exactly how the rank condition generalizes as the number of experts increases beyond 3? This is particularly important as other results (Thm. 7, 11) build on this expression.\n\n * Line 28 - 'highly parameterized and represented by a low-dimensional set of parameters' is a little unclear - are you alluding to Deep Neural Network reward representations here?\n\n * Line 121 - the main advance beyond [1] is that the identifiability result is easy to verify in practice (as stated on Line 121). Can you please include a brief sketch / outline in your paper illustrating why the result in [1] is _not_ easy to verify in practice, for readers not familiar with this work.\n\n * Line 243 - \"$T_{a_0}$ commutes with $T_a ~~\\forall a \\in \\mathcal{A}$\". It is difficult to intuit / conceptualize what this condition implies for the structure of the MDPs. Can you please provide a brief explanation of what this commutativity requirement implies for the MDP dynamics? Perhaps with a small example?", "limitations": "Nil comments here.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Originality\n\nAlthough this paper is a re-statement of an existing result from [1] (as the author's acknowledge), this re-statement is more practically useful and enables multiple extensions, as well as numerical validation and application of the result.\n\n# Quality\n\nThe authors have done a good job engaging with prior work. Overall, this paper is of high quality and feels solid and complete, although the paper is presently missing a conclusion section / paragraph - I encourage the authors to add one to their final submission.\n\n# Clarity\n\nThis paper is clearly written, although some of the notation, language and definitions could be tidied up. For instance;\n\n * The language switches between \"Markov Decision Process' (ex. line 91) and '... Problem' (ex. Line 117). Please be consistent unless these imply different things in your writing, in which case both terms should be defined.\n * Line 92 - it may clarify the definitions to explicitly state that $\\mathcal{S}$ and $\\mathcal{A}$ are finite.\n * Line 115 - Do you mean '[additive] constant'?\n * On line 119 and elsewhere $v$ denotes a _function_, whereas on line 137 and following it now denotes a _vector_. Please clarify the notation to disambiguate these if possible.\n * Consider annotating matrix expressions (e.g. Eq. 4) with the dimensions of each term, to help the reader understand the notation. Alternately, I suggest adding a 'bar' between the columns of block matrices such as the leftmost term in Eq. 4 to clarify the matrix contents.\n\nThe inclusion of an 'intuition' for the proof of Def. 10 (Lines 225-229) is very helpful. Please consider adding similar intuition / proof sketch text for more of your other results. This will aid less-technical readers in following the material.\n\nPlease ensure figures are legible in greyscale. E.g. consider using a log color scale for Fig 1d and 1e, as well as Fig 3e. Please include x and y axis labels for Figs 1 and 3 (I believe the axes are states and actions?).\n\n# Significance\n\nThis paper contributes a well scoped and executed body of theory work to the IRL literature, and creates multiple opportunities for future authors to build on the results. For instance, by extending the tabular MDP results to derive probabilistic bounds in approximate IRL settings, or by applying the results in practical applications of IRL to real-world MDP problems.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "ECJ9GecyE8u", "reviewer": "Reviewer_Pbuu", "summary": "This paper investigates the problem of identifying a reward function (up to a constant) having access to (entropy-regularized) optimal policies of multiple experts on different environments and with different discount factors (this result was previously known only with two experts). In addition to this theoretical result, the authors provide a practical method for identifying such a reward. Finally, when assuming the reward is a linear combination of features, the authors demonstrate an interpretable reward function can be identified.\nThe authors present some empirical results on random matrices and grid worlds that showcase and confirm their theoretical results.", "questions": "1. A high-level question I had is: wouldn't it be more realistic to assume that you have multiple experts operating with different _rewards_ as opposed to different environments/discounts? I realize this is a completely different problem, but I feel it should at least be discussed when motivating the problem (see points on significance above).\n2. In line 157 it says that the condition of Theorem 3 \"is easier to check in practice\" than Definition 2, why is this? Is it because there's no need of the $v$s? It would be good to clarify.\n3. In the proof of Theorem 3 the statement \"is an eigenvector of A with eigenvalue 0, and corresponds to the invariance of the optimal policy under addition of a constant to the reward function.\" is not clear).\n4. The statement in line 586 in Appendix (\"This is hence equivalent...\") is not clear at all. Please add some more clarifying text or a reference to an established result (it's fine if it points to a chapter in a textbook, say).\n\nIn general, statements of the form above (which are not trivially true) should be clarified or referenced rather than left \"as an exercise to the reader\".\n\n5.  In line 313, is $\\beta$ essentially just the standard $\\gamma$ discount factor?", "limitations": "I don't feel the authors added much discussion around limitations of their work; most of the discussions and results served only to highlight how their results improved on prior results. From a practical perspective it would have been nice to have a bit more of a nuanced discussion here (see points above regarding significance).\n\nNo negative societal impact of the work was provided.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Originality\nThe work seems to be largely a followup of [1], but as far as I can tell, the work is original (including theory and experiments). I went through the proofs and as far as I can tell they appear to be novel and non-trivial (e.g. not just a direct application of prior results).\n\n# Quality\nThe theoretical results and proofs are of high quality and clarity. The empirical validations were done very well and properly highlighted and confirmed the theoretical results of the paper.\n\n# Clarity\nThe paper was in general very well written and presented. The motivating paragraphs before each Theorem were very clear and useful in giving a high-level intuition for the results.\nA few suggestions to help make the paper clearer:\n* In Definition 2 I'd suggest using subscripts (instead of superscripts) for the $v^1$, $v^2$s and $T^1$, $T^2$s, as otherwise they can be confused with exponents.\n*  The paragraph describing the Strebulaev-Whited environment is quite difficult to follow. Although I appreciate the authors want to add a real-world-like environment, I feel it is mostly a distraction from the paper's flow and fails to effect its intended purpose (due to lack of clarity). Indeed, the actual figures are relegated to the appendix, so the main paper only contains a (too terse) description of this non-standard environment. I would suggest moving the environment's description to the appendix as well.\n\n# Significance\nThis is probably the weakest point of the paper for me. Although the authors present some high-level motivations in the first paragraph of the introduction, and then position it as resolving some of the issues with IRL, it remained unclear to me _when_ such a situation as explored by the authors would be useful. The Strebulaev-Whited environment, although less toy-ish than the grid worlds, is still quite artificial and unclear whether the situation considered (with different values of $\\sigma_{\\epsilon}$ has any ties to any real world situation.\n\nThese issues could have perhaps been addressed in a concluding section, but the authors chose not to include one. I would suggest removing the Strebulaev-Whited environment description (as suggested above) and adding a conclusion instead. In particular, I would suggest they clarify _when_ these methods can be useful and ideally give examples of situations where you have multiple experts operating under different environments/discount factors but with the same reward function.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "1h5TMpLY4S", "reviewer": "Reviewer_z9k4", "summary": "Inverse Reinforcement Learning (IRL) seeks to infer a reward function from demonstrations sampled from an agent acting (approximately) optimally. Unfortunately, the IRL problem is under-determined: an infinite number of reward functions will lead to exactly the same optimal policy. However, it is possible to obtain additional information when observing demonstrations from multiple experts, acting in environments that differ in transition dynamics or discount factor (but which have the same state and action space, and reward function).\n\nThis paper characterizes when this multi-expert IRL problem is or is not identifiable. The characterizations are in terms of the rank of matrices formed from the transition matrices of the different environments. In particular, Theorem 3 provides a charcterization in the two-expert, distinct dynamics case that is equivalent to that of Cao et al [1] but which is more amenable to direct validation. They derive corollaries for the three-expert case (Corollary 4) and two different discount rate (Corollary 5). There is also a key negative result (Corollary 6), showing that when there are exogeneous variables then the reward function can only be determined up to an additive function of the exogeneous variable (not a constant). They also derive stronger results in the case of a linear reward function (Theorem 7), and provide a condition suitable for estimated transition matrices (Theorem 8).\n\nThe paper concludes with Theorem 11 providing a condition for a reward function to generalize. This and other theorems are then illustrated in a brief empirical section.\n\n Some of these transformations -- such as potential shaping, or rescaling by a positive constant -- we might", "questions": "  - Most of the results in the paper describe whether or not IRL can characterize the reward function up to a constant. But why should we care about this? Isn't it sufficient to identify it up to potential shaping, since that never changes the optimal policy or ranking of policies?\n  - How might these results change if expert is not MaxEnt RL? E.g. no entropy bonus (hard optimal policy), or a different kind of suboptimality (epsilon-greedy)?", "limitations": "I did not see any substantive discussion of limitations of this work. One obvious limitation is it assumes a particular model of the demonstrator (MaxEnt RL). Humans, unfortunately, do not follow this idealized mathematical model. This is a limitation common with much work in this area -- but it'd be nice to at least see some discussion of how the results might vary with different demonstrator models, to get a sense of how robust these results are.\n\nNo discussion of ethical implications but I also don't see any significant negative ethical implications from this work.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality: moderate. The key result, Theorem 3, is equivalent to an earlier result due to Cao et al. Most of the other results are relatively simple applications of this theorem. However, Theorem 3 is a non-trivial restatement, and the corollaries although not technically deep are a useful set of results.\n\nQuality: all the claims seem plausible although I have not had time to validate the proofs in detail.\n\nClarity: comprehensible but significant room for improvement. The actual technical description was fairly clear. But there is little to signpost the reader in the introduction, and I even found the introduction misleading in places, e.g. you refer to \"reward shaping\" but later it is clear you are talking specifically about *potential shaping* (but for some reason do not cite the Ng et al, 1999 paper until later).\n\nThe motivation in the introduction focusing on economics & finance also felt rather odd. With the benefit of hindsight, I suppose this is meant to foreshadow the empirical results, and perhaps rewards linear in features are also more plausible in this setting. But in general, I do not think of this as being a major application of IRL. Indeed, it seems relatively easy to hand-design a passable reward function for many financial applications, e.g. PnL minus lambda*CVAR. By contrast, it seems far more challenging to work in settings that do not have directly measurable metrics of success, such as \"help the user build a house in Minecraft\" (BASALT benchmark, etc).\n\nMoreover, citations [5]-[8] seem only tangentially related (prospect theory, VnM utility theorem, etc). At best they establish the \"fundamental importance\" of reward functions. But not any difficulty in specifying them.\n\nPaper would also benefit from having a conclusion section, and limitations and future work.\n\nSignificance: moderate. The matrix rank conditions are more amenable to empirical validation than prior work -- especially given the approximation condition of Theorem 8. The results for generalization are also a useful application, and notably can give guarantees of generalization even when the reward is not perfectly identifiable (depending on the environment to be transferred to).\n\nMinor typos/grammar points I'd suggest fixing:\n  - \"However, [1] showed that\" -- [1] is not a proper noun, should read \"However, Cao et al [1] showed that\". (This misuse occurs many times later on in related work, as well.)\n  - \"This work starts by\" -- is this work [1], or your paper?\n  - \"maximized by the agent\" -- agent is ambiguous, could refer to the policy you learn, call it demonstrator instead?\n  - Line 94: R should be r (lowercase) for consistency with line 91 and 97.\n  - References: some words in titles need to be capitalized, plae inside {...} in the TeX, e.g. monte carlo->Monte Carlo.\n\n# Update after rebuttal\n\nThanks to the author for their detailed response. I understand the Econ motivation better now, IRL is certainly relevant for understanding human behaviour in financial transactions. I still find spotlighting this application a bit strange given that as the authors say themselves \"IRL has not (yet) been used in revealed preference analysis\". It'd be interesting to see work applying IRL to human financial decisions and see if it's more predictive than existing Econ models --- but this paper does not do that, so why focus on it?\n\nI'm still not sure in what setting we'd care about reward functions up to a constant rather than up to potential shaping as we know potential shaping does not change the ranking of policies. The author response doesn't really address this point.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept