Identifiability in inverse reinforcement learning
Authors: Haoyang Cao
Samuel N Cohen
Lukasz Szpruch
Venue: NeurIPS 2021 Poster (2021)
Keywords: Inverse reinforcement learning
identifiability
entropy regularization
optimal control
Markov decision problem

Abstract: Inverse reinforcement learning attempts to reconstruct the reward function in a Markov decision problem, using observations of agent actions. As already observed in Russell [1998] the problem is ill-posed, and the reward function is not identifiable, even under the presence of perfect information about optimal behavior. We provide a resolution to this non-identifiability for problems with entropy regularization. For a given environment, we fully characterize the reward functions leading to a given policy and demonstrate that, given demonstrations of actions for the same reward under two distinct discount factors, or under sufficiently different environments, the unobserved reward can be recovered up to a constant. We also give general necessary and sufficient conditions for reconstruction of time-homogeneous rewards on finite horizons, and for action-independent rewards, generalizing recent results of Kim et al. [2021] and Fu et al. [2018].

Identifiability in inverse reinforcement learning
Haoyang Cao
Samuel N. Cohen
Alan Turing Institute hcao@turing. ac. uk
Mathematical Institute, University Oxford and Alan Turing Institute samuel. cohen&maths ox ac .u
Lukasz Szpruch
School of Mathematics,
University Edinburgh and Alan Turing Institute
L. Szpruchhed.. ac.
Abstract
Inverse reinforcement learning attempts to reconstruct the reward function in Markov decision problem, using observations of agent actions. As already observed in Russell [1998] the problem is ill-posed, and the reward function is not identifiable, even under the presence of perfect information about optimal behavior. We provide a resolution to this non-identifiability for problems with entropy regularization. For given environment, we fully characterize the reward functions leading to given policy and demonstrate that, given demonstrations of actions for the same reward under two distinet discount factors, or under sufficiently different environments, the unobserved reward can be recovered up to constant. We also give general necessary and sufficient conditions for reconstruction hime-homogeneous rewards on finite horizons, and for action-independent rewards, generalizing recent results of Kim et [2021] and Fu et [2018].
Introduction
Inverse reinforcement learning aims observations of agents' actions determine their reward function. The problem has roots the very early stages optimal control theory; Kalman [1964] raised the question of whether, by observation of optimal policies, can recover coefficients of a quadratic cost function (see also Boyd et al. [1994]). This question naturally generalizes to the generic framework of Markov decision process and stochastic control.
In the 1970s, these questions were taken up within economics, as a way of determining utility functions from observations. For instance, Keeney and Raiffa [1976] set out to determine proper ordering of all possible states which are deterministic functions of actions. In this setup, the problem is static and the outcome of an action is immediate. Later in Sargent [1978], dynamic version of a utility assessment problem was studied, under the context of finding the proper wage through observing dynamic labor demand.
As exemplified by Lucas' critique', many applications rewards corresponding to observed policies; instead we may need to identify the specific rewards agents face, as it is only with this information that we can make valid predictions for their actions in changed environment. In other words, we do not simply wish to learn reward which allows us to imitate agents the current environment, but which allows us to predict their actions in other settings.
not enough to find some pattern of
'The critique is best summarized by the quotation: "Given that the structure of an econometric model consists of optimal decision rules of economic agents, and that optimal decision rules vary systematically with changes the structure series relevant to decision maker. follows that any change in [regulatory] policy will systematically alter the structure of ecomometric models." (Lucas (1976))
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

In this paper, we give precise characterization of the range of rewards which yield particular policy for an entropy regularized Markov decision problem. This separates the main task of estimation (of the optimal policy from observed actions) from the inverse problem (of inferring rewards from given policy). We find that even with perfect knowledge of the optimal policy, the corresponding rewards are not fully identifiable; nevertheless, the space of consistent rewards is parameterized by the value function of the control problem. In other words, the reward can be fully determined given the optimal policy and the value function, but the optimal policy gives no direct information about the value function.
We further show that, given knowledge of the optimal policy under two different discount rates, or sufficiently different transition laws, we can uniquely identify the rewards (up to a constant shift). We also give conditions under which action-independent rewards, or iimehhomogenous rewards over finite horizons, can be identified. This demonstrates the fundamental challenge of inverse reinforcement learning, which is to disentangle immediate rewards from future rewards (as captured through preferences over future states).
Background on reinforcement learning
The motivation behind inverse reinforcement learning is to use observed agent behavior to identify the rewards motivating agents. Given these rewards, one can forecast future behavior, possibly under a different environment. In a typical reinforcement learning² (RL) problem, agent learns an optimal policy to maximize her total reward by interacting with the environment.
In order to analyse the inverse reinforcement learning problem, begin with overview of the 'primal' problem. that is, how to determine optimal policies given rewards. We particularly highlight entropy regularized version of the Markov decision process (MDP), which provides a better- better-posed setting for inverse reinforcement learning. For mathematical simplicity, we focus on discrete-time problems with finitely many states and actions; results can largely be transferred to continuous settings, with fundamentally the same proofs, however some technical care is needed.
2.1 Discrete Markoy decision processes with entropy regularization
The environment. We consider simple Markov decision process (MDP) on infinite horizon. The MDP M = (S,A,T,J. is described by: a finite state space S; a finite set of actions A: (Markov) transition kernel T S A P(S), that is, function T such that T(s, a) gives probabilities of each value of 1 given the state S, = 8 and action A₁ = a at time i; and a reward function f f A -
with discount factor 7 E [0,
An agent aims to choose a sequence of actions (Ao, AI.... from A in order to to maximize the expected value of total reward
7 Ar).
will prove convenient for us to allow randomized policies x, that is, functions : S + P(A). where (-|ss) is the distribution of actions the agent takes when in state s. For given randomized policy n, we define T= E P(S), the distribution of S1+1 given state St, by
T (S s)) -nEA T(s1|s,a)T(als)
=)
Given initial distribution P E P(S) for So and a policy : S P(A), we obtain (unique) probability measure p. such that, and any a E 8,5 E S, (S0 = s) = p(s) and
(A, S, s) (als)) (= s' = s, A. a) T(s'ls, for all
We write E. for the corresponding expectation and E when the initial state is given by S. The classic objective in MDP is maximize the expected value E3 Σe= IS A.).. With this
'Reinforcement learning and optimal control are closely related problems, where reinforcement learning typically focuses the challenge of numerically learning good control policy, while optimal control focuses the context the inverse problem we consider they are effectively
on the description of the optimizer. equivalent and we will use the terms interchangeably.
Here, and elsewhere, write ((X) for the set of all probability distributions X.

---

objective, one can show (for example, see Bertsekas and Shreve [2004], Puterman [2014]) that there an optimal deterministic control (i.e. a policy æ, taking values zero and one, which maximizes the expected value). This implies that, typically, an optimal agent will only make use of a single action for each state, and the choice of this action will not vary smoothly with changes the reward, discount rate, or transition kernel.
Entropy regularised MDP. Given the lack of smoothness in the classical MDP, and to encourage exploration, a well-known variation on the classic MDP introduces regularization term based on the Shannon entropy. Given policy и and regularization coefficient À 2 the entropy regularized value of a policy n, when starting in state 8, is defined by
(1lo), 0x) log (x((clss)) = E
Σ 7' (166) t=0
(s) = E
1=0
Here H((T) -' ((a) log(<(a)) is the entropy of We call this setting the regularised
MDP Mr , Y,Y). X). The optimal value is given by (x) = max, Vx(s), (s). where the maximum is taken over all (randomized feedback') policies π S + P(A).
We define the state-action value of (s, S A
QT a) = f( + Σ T(((ss,))))))))
HEES
The dynamic programming principle (e.g. Haarnoja et al. [2017, Theorem 21) gives
(s) max MEP(A)
Σ
((, - Alog (m(a) + + (( [V (si))) m(a)
aEA
(3)
H
(() + tT (((ii)] m(a)) + H(m)
A max mEP(A)
aEA
Observing that on the right hand side we are maximizing over a linear function in m plus an entropy term, and applying [Dupuis and Ellis, 2011, Proposition 1.4.2], we have that for any S
(x())= = V = A log Σ e ( (V"A = A log Σ exp (1
acA
aEA
(4)
and the maximum in (3) is achieved by the randomized policy m(a) = (uls)) where
exp (1 (s,
(i(ass)=
for a E A.
(5)
Eoee exp (1 (s,a")))))
From (4) we see that exp (s)()) = =mEA exp policy
and so we can write the optimal
<x(a|s) = exp (s)
(6)
exp (()(s.))++_...eee.e Eag ( (T)())) /A),
From this analysis, make the following observations regarding the regularized MDP:
The optimal policy will select all actions in A with some positive probabilities.
If À is increased, this has the effect flattening out' the choice of actions, as seen in the softmax function in (5). Conversely, sending À 0 will result in a true maximizer being chosen, and the regularized problem degenerates to the classical MDP.
Adding constant to the reward does not change the policy.
Remark 1. In many modern approaches, one replaces dependence on the state with dependence on space of 'features'. This has benefits when fitting a model, but does not significantly change the problem considered.
'Given the Markov structure there loss generality when restricting policies of feedback form. Further, by replacing A with the set of maps S + A if necessary, all feedback controls a(s) can be written as deterministic controls a(-) in a larger space, so when convenient we can consider controls which do not depend on the state without loss of generality.

---

3 Analysis of inverse reinforcement learning
We now shift our focus to 'inverse' reinforcement learning, that is, the problem of inferring the reward function given observation of agents' actions.
Consider a discrete time, finite-state and finite-action MDP Ma, as described in Section 2. Suppose a "demonstrator' agent acts optimally, and hence generates a trajectory of states and actions for the system r = ($1, 01, $2, a2....). We assume that it is possible for us to observe T (over a long period), and seek infer the reward f which the agent faces.
first observation is that, assuming each state E S appears infinitely often in the sequence т, and the agent uses randomized feedback control (als)) it is possible to infer this control. A simple consistent estimator for the control is
(Tx))(als)= # #(a = a and S: = s; t N
+ (a a.s. as N + oc.
( 8; 1 IS N]
Similarly, assuming each state-action pair (s, a) appears infinitely often in т, we can infer the controlled transition probabilities (8'11,, a). A simple consistent estimator is given by
(s #1s = 5,a, = a and s1+1 = ss; t N T(5'ss, as. as N
#1s and ar a; t N}
If our agent known to follow a regularized optimal strategy, as in (6), and we have a simple accessibility condition on the underlying states, then every state-action pair will occur infinitely often in the resulting trajectory. Therefore, given sufficiently long observations, we will know the values of (a]ss) and [(s' (s, a.) for all s, s' S and A.
This leads, naturally, to an abstract version of the inverse reinforcement learning problem: Given knowledge of iT (a]s) and ((s'ls. a) for all s, E S and a E A, and assuming π is generated by an agent following an reguopy-regularized MDP Mx, can we determine the initial reward function f that the agent faces?
As observed by Kalman [1964], for an unregularized controller the only thing we can say that the observed controls are maximizers of the state-action value function, and not even that these maximizers are unique. Therefore, very little can be said about the underlying reward in the unregularized setting. Indeed, as already observed in Russell [1998] the problem of constructing reward using state-action data is fundamentally ill-posed. One pathological case simply take constant, so all actions are optimal. Alternatively, if we infer unique optimal action a for each s. we then could take any f(, a (s)) (0, oo] and f(, a) for # (s)..
Further literature. One of the carliest discussions of inverse reinforcement learning (IRL) in the context of machine learning can be found in Ng and Russell [2000]. Their method to first identify a class of reward functions, for an IRL. problem with finitely many states and actions, deterministic optimal strategy, and the assumption that the reward function depends only on the state variable. Then, assuming the reward function is expressable in terms of some known basis functions in the state, linear programming formulation for the IRL problem is presented, to pick the reward function that maximally differentiates optimal policy from the other policies. This characterization of reward solutions to IRL problems.
functions demonstrates the general non-uniqueness
In past two decades, there have been many algorithms proposed to tackle IRL problems. One significant category of algorithms (MaxEntRL) arises from the maximum entropy approach to optimal control. In Ziebart [2010], IRL problems were linked with maximum causal entropy problems with statistical matching constraints. Similar models can be found in Abbeel and Ng [2004]; Ziebart et al. [2008], Levine et al. [201] 1] and Boularias et al. [201 I]. A connection between maximum entropy IRL and GANs has been established in Finn al. [2016a]. Further related papers will be discussed in the text below.
'In particular, for every pair of states 8, there needs exist a finite sequence 81, 82, 8n s' of states and @1, ..., an of actions such that [[x=] ] T(s44) lsk,, a4) >> O. This is certainly the case, for example, if assume T(s' s, a) 0 for all s, E and E A.

---

In MaxEntRL, one assumes that trajectories are generated with law
((50) P(r) = 7.
II T( (s,, ut) ae)e M(re)))
for a constant Z > 0. Comparing with the distribution of trajectories from an optimal regularized agent, this approach implicitly assumes that ग (aas) oc exp(f(a, s)). Comparing with (6), this is analogous to assuming the value function is constant (from which we can compute 2) and == 1. This has a concrete interpretation: that many IRL methods make the tacit assumption that the demonstrator agent is myopic. As we shall see in Theorem 1, for inverse RL the value function can be chosen arbitrarily, demonstrating the consistency of this approach with our catropy-reguaarizer agents. We discuss connections with MaxEntIRL further in Appendix C.
3.1 Inverse Markov decision problems
We consider a Markov decision problem as in Section As discussed above, assume that we have full knowledge of S, A, T, y. and of the regularization parameter À and the entropy-regularieed optimal control म (6), but not the reward function f.
Our first theorem characterizes the set of all reward functions f which generate a given control policy. Theorem 1. For a fixed policy a(als) > O, discount factor y E [0, 1), and an arbitrary choice of function v + R. there is a unique corresponding reward function
such that the MDP with reward f yields value function V and entropy optimal policy 3 n. as) Alog म (a]s) Y Eves
+ v(s)
As a consequence of this theorem, we observe that the value function not determined by the observed optimal policy, but can be chosen arbitrarily. We also see that the space of reward functions consistent with a given policy can be parameterized by the set of value functions. simple offgrees-ooffreedeee
argument gives this result intuitively. There are n = |S] possible states and k = |A] possible actions each state, so the reward function can be described by vector in Baxk From the policy, which satisfies Eaea [{a|s)= for all s, we observe (K- 1) linearly independent values. Therefore, the space of consistent rewards has n. X K n x (k- free variables, which we identify with the n values {u(s))
Remark 2.
Remark 3. Ng et al. [1999] provides a useful insight to our result. In Ng et al. [1999] it is assumed that the rewards are of the form F(S,, S141): for a fixed MDP, this adds no generality, as we can write f(s, a)) = E[ a, S S+ s, A, = a). Ng et al. [1999] show that, for any 'shaping potential" S + R, the reward F = ( (((,) yields the same optimal policies for every (unregularized) MDP. However, shaping potentials do not describe the space of all rewards corresponding to given policy, for fixed transition dynamics. In our results, instead parameterize a family of costs f in terms of the value function (Theorem 1), and show these are the only costs which lead to the given optimal policy for fixed (regularized) MDP. We also note that Magnac and Thesmar [2002] give a similar result to ours, using a different randomization of strategies.
Given Theorem 1, we see that it is not possible to fully identify the reward faced by a single agent, given only observations of their policy. Fundamentally, the issue is that the state-action value function Q combines both immediate rewards f with preferences v over the future state. If we provide data which allows us disentangle these two effects, for example by considering agents with different discount rates or transition functions, then the true reward can be determined up to a constant, as shown by our next result. In order clearly state the result, we give the following definition.
Definition 1. Consider a pair of Markov decision problems on the same state and action spaces, but with respective discount rutes "Y, 5 and transition probabilities T, We say that this pair is value-distinguishie if. for functions W. w S IR, the statement
wr(s) - 7 TTs''ss ())(ss)(s))))))))))))))))))))a = ((s) Σ T(s''ss, for all a E A,SES
(7)
S'ES
E'ES
implies at least one of w and is constant function.
As discussed by Levine [2018]. for deterministic problems this simplities to P(r) x exp(E, f(a., st)).
which is often taken starting point.
5

---

In this definition, note that constant functions w, i are always solutions to (7), in particular for E I we can set w = and w- (1-7)cc/1 1--), 5). However, this is a system of |A| [S] equations in 2 x [S] unknowns, so the definition will hold provided our agents' actions have sufficiently varied impact on the resulting transition probabilities. a linear-quadratic context, it is always enough to vary the discount rates (see Corollary 5).
Suppose we observe the policies of two agents solving entropy-regularized MDPs, who face the same reward function, but whose discount rates or transifion probabilities vary, such that their MDPs are value-ditinguishine
Theorem 2.
Then the reward function consistent with both agents' actions either does not exist, or is identified up addition of a constant.
Given the addition of a constant to f does not affect the resulting policy (it simply increases the value function by a corresponding quantity), we cannot expect to do better than Theorem 2 without direct observation of the agent's s rewards or value function in at least one state.
Remark 4. Definition is essentially a statement regarding invertibility of a linear system of equations for w, w. This indicates that the stability of rewards obtained using Theorem 2 is principally determined by whether this linear system is well conditioned. This can be measured by the ratio of its largest to second smallest singular values (the second smallest is due to the constant functions always being in the kernel of the system) not being too large. Given the inevitable error arising from statistical estimation of policies and transition functions, a well conditioned system is often key requirement in practice. A similar observation will also be valid for the uniqueness results in later sections.
Our results show that it is typically sufficient to observe an MDP under two environments (transitions and discount factors) order to identify the reward. This can be contrasted with Amin and Singh [2016] and Amin et al. [2017] who show that, if the demonstrator is observed in multiple (suitably chosen) environments, the (state-only) reward can be identified up to a scaling and shift (the scaling is natural, given they do not use entropy regularization). Ratliff et al. [2006] consider finite number of environments, but explicitly do not attempt to estimate the 'true" underlying reward.
Remark 5.
Finite horizon results
Over finite horizons, for general costs, similar results hold to those already seen on infinite horizons. An entropy-regularize optimizing agent will use a policy x² = {mr:)/' which solves the following problem with terminal reward and (possibly time-dependent) running reward f:
T-1
maxEEx x
T
Σ
(f(t.s).
AAlo Alogme(a?ls?)) + 7 9(57))))))
For any π 1m s ES E A, and E fo...., 1] write
Q7 (s) EAwa, (-1+) A) log 7. (A |ss)],
[tt, 8, a) + BB (S')
v+()) = g())
Then, similarly to the fefnnie-horizznn discounted case discussed in the main text, we have V7 9 and for t E fo...., --.....,11,,, -1].
8,,) a) + +7E (59) (+(,,)- = f(1,
v(((s) = V," (s) = =Alog Σ exp (/(()
a'EA
x = exp { (Q](s,,)/1}
/
Σ exp (Qi(s, = exp ( a'EAA
-v((s)
Rearranging this system of equations, for any chosen function v : fo...., T7 x S + R with .T,,-) g)),, we see that मं (a[s) is the optimal strategy for the reward function
f(t, a) = > log कं (als) 7 Σ ((s')s,aju( + 1,,') + vt,,s),
EES

---

in which case the corresponding value function is V* = v. In other words, the identifiability issue discussed earlier remains. We note that identifying ι in this setting is more delicate than in the infinite-horizon case, as it is necessary to observe many finite-horizon state-action trajectories, rather than single infinite-horizon trajectory.
4.1 Time--omoogeneous finite-horizon identifiability.
Following the release of a preprint version of this paper, Kim et al. [2021] was published and presented a closely related analysis, for entropy-regularizee deterministic MDPs with zero terminal value. We here give an extension of their result which covers the stochastic case and includes an arbitrary (known) terminal reward.
The key structural assumptions made by Kim et al. [2021] are that the reward is time- homoghooogss (that is, does not depend on t), and that there is finite horizon. As diseussed in the previous section, there is no guarantee that an arbitrary observed policy will be consistent with these assumptions (that is, whether there exists any f generating the observed policy). However, given a policy consistent with these assumptions, and mild assumptions on the structure of the MDP, we shall see that unique identification of f is possible up to constant.
Definition 2. We say MDP has full access at horizon T (from state s) for some distribution over actions, for all states s we have P(Sr-1 = 5'1S0 - 8) > 0.
It is easy to verify that this definition does not depend on the choice of distribution over actions (provided has full support).
This is slightly weaker than assuming that the Markov chain underlying the MDP (with random actions) is irreducible, as there may exist transient states from which we have full access. It is a classical result (commonly stated as corollary to the Perron-Frobenius theorem) that an irreducible aperiodic Markov chain has full access (from every state). Kim et [2021] give an alternative graph-theoreti view, based on the closely related notion of T-coverings.
Theorem 3. Consider an MDP with unknown time-homogeneous reward function J. In order for be identified (up global constant) from observation of optimal policies and the resulting transitions up to some horizon T > O, with initialization from some state s, it is necessary that the MDP has full access at some horizon T" T (from state s).
The following definition is most easily expressed by associating our finite state space S with the set of basis vectors {e* jkm I and writing the transitions T (s''ss, a), for A in terms of the transition matrix T(a) with
T(a), = Te,yle,,).
While this definition is quite abstract, we will see that it precisely describes when many IRL problem with fixed terminal reward can be solved.
Definition 3. We say an N-state MDP has full action-rant rank on horizon T, starting a state e if the matrix with rows given by
T Σ
(1+ P=O
do, ar E {A}
of rank N (with the convention that products are taken sequentially on the right, that is I A AuA Az, and the empty product is the identity).
) is the expected state of S₁ given So e,. when following the actions (ao.... ar}. Hence, the quantity eī (ET-) 7²t T T(ay)) )) is time-weighted expected occupation density for the process, that is, measurement of how long we spend in each state. We have full action-rant rank if our actions are sufficiently varied that there are N linearly independent such density vectors (cf. [Kim et al,, 2021, Corollary 11, where it is the state-action occupation density which is considered).
Remark 6. Observe that e, I T(ar))
Theorem 4. Suppose our MDP has full action rank and full access, at horizon T, from an initial state 80. Then the time- timehhomogeneuus IRL. problem is identifiable, that is, knowledge of the ((ime-dependen) reguoay-egullarized optimal strategy nद (a]s), and the terminal reward g, is sufficient to uniquely determine time- time-homogeneous running reward f. if exists, up to a constant.
7

---

Conversely, if our MDP has full access but not full action rank at horizon T, from the state So. the IRL problem remains ill posed.
As corollary, we demonstrate a generalized version of [Kim et al., 2021, Theorem 2].
Corollary 1. Suppose Y + O and our MDP is deterministic,, that is ( a) E {0, and one of the following holds:
(i) the underlying Markov chain is irreducible and aperiodic (i.e. with randomly chosen actions, the underlying Markov chain is irreducible and aperiodic)
(i) the initial state 80 e; admits a self-loop (i.e. is possible to transition from this state to itself), and all states can be accessed from the initial state in most d transitions
(iii) there exist cycles? starting at the initial state So e; with lengths 1Q1, such that ged(IQ), (Q1)) = 1. and all states can be accessed from the initial state in at most transi- tions.
Then there exists horizon T such that the time- homogenoogs IRL problem is identifiable (as in Theorem 4). In particular, in case (ūi), is sufficient to take any finite T 2 dl + 1; in case (iii) it is sufficient to take any finite T 2 RR'.
We can extend this result to stochastic setting, assuming that our action space is sufficiently rich.
Corollary 2. Suppose & + O, and our MDP is stochastic and satisfies one of the sets of assumptions ((i), (iii) (ii) of Corollary I and that from every state, have at least many actions (with linearly independent resulting transition probabilities) as we have possible future states, that is.
rank T(+ss, a); E A} = #(s': s/':: T(s ([s'sssa) >> 0 for some E A}.
Then for any initial state so, there exists horizon T such that the homogeooggs IRL problem is identifiable (as in Theorem 4). The sufficient bounds on from Corollary also apply.
This result also addresses a concern raised in Magnac and Thesmar [2002, Section 4.1], as it demonstrates that, for sufficiently rich control problems, time-homopee homogenittt assumption on rewards and the existence of finite horizon is sufficient to guarantee identifiability.
5 Action-independent rewards
Earlier works such as Amin and Singh [2016], Amin [2017], Dvijotham and Todorov [2010) and Fu et al. [2018 8] consider the case of action- action-independent rewards, that is, where f is not function of a. In general, it is not immediately clear whether, for a given observed policy, the IRL problem will admit an oetion-independent solution. In this section, we obtain necessary and sufficient condition under which an action- eetion-independen time-homogeneous reward function could be a solution to a given timee-iiiie-oooonn IRL problem with discounting. We shall also obtain rigorous condition under which unique reward function can be identified.
regularized,
Consider cntropy-regularin MDP environment
given in Section 2. Without
loss of generality, assume that |S], |A] 2 and S = (81..... 8. Let मे : S + P(A) be observed optimal policy such that a ss) > for any (s, a) E
For a E A we write #(a) E R for the probability vector (#(als1) T(a) E [SS for the transition matrix with [T()]] = T(s)lsi,a). Fix particular action
# {alssss)) T) and
ag E A, and write
A Alog (a) = log ((a) log (ap) and AT(a) = T(a) - T(ao),
where log ((a) denotes the element-wise application of logarithm over the vector (a), for any a E A.
"A cycle is sequence of possible transitions which start and end in the same state. The length of cycle defined to be the number of transitions, e.g. a cycle {so + S1 Markov chain is aperiodic there no common factor (greater than one) the lengths of cycles.
so) has length 3. An irreducible
'The analogous results for finite-horizon problems with tmmeinhomogeenooe rewards (and general discount factor) can be obtained through the method.

---

Theorem 5. The above IRL problem admits a solution with action aetion-independent reward f: - R if and only if the system of equations
XA log il (()) 7)T(a) Va E A,
(8)
admits a solution v E RRii, (Note that this is a system of [A| X S equations in [S] unknowns, so this is a non-trivial assumption.)
Corollary 3. Suppose Y E [0, 1). Assuming a solution to (8) exists, the IRL problem is identifiable (i.e. the true action-independent reward function can be inferred up to constant shift) if and only if. writing K(a) for the kernel of AT()), we know that
{ : c)
N aEAlfao)
K(a) = N [n(()).
aEA
where 1 denotes the all-one vector in IR $), (Note that {cl : c R} C. K(a) for any E A\ {ao} and (an) ) = 0 implies K((o)) = (I))
Under the entropy regularized framework, the long-run total reward depends on actions through the entropy penalty term. Therefore, it cannot be reduced to the scenario in Amin and Singh [2016], where any linear perturbation of the reward function will not affect optimal behavior under any given environment.
Remark 7. Theorem 5 and Corollary 3 suggest various exlensions, in the case when (8) does not admit a solution, but the assumed property on the kernels in Corollary 3 holds. For example, one could consider the least-squares solution the system (8) (which is defined up constant). This gives a choice of value function which, in some sense, minimizes the action- diriondneeeddence of the resulting cost function (obtained through Theorem 1).
Fu et al. [2018] give result similar to Corollary 3. Unfortunately, the role of the choice of actions in their conditions is not precisely stated, and on some interpretations insufficient for the result to hold as we have seen, the condition of Corollary 3 is both necessary and sufficient for identifiability. We give a variation of their assumptions in what follows.
Definition Reeward-dccomposabiie
We say states 81, s are '1-step linked', there exist actions a, E A and state 8o E S such that T(s [ss]ss I80, a) > 0 and T(s so: a') > O. We extend this definition through transitivity, forming a set of 'linked' states St. We say say the MDP reward- decomposable if all its states are linked.
Note that there is no loss of generality if specific a' is selected this definition (instead of being allowed to vary), provided a is allowed to vary.
if = S is the only choice of nonempty sei S₁ C such that: there exists sel So C S with (i) every trunsition (with any action) S₁ is from So. and (ii) every transition from So is to Sj. (In other words, X₁ E So if and only if X1+1 E St.) We note that Fu et al. [2018] simply call this property 'decomposable', but this seems unfortunate choice of terminology given this alternative characterization.
Remark 8. An equivalent definition would be that our MDP is reward-decompostte
The following final corollary gives simple set of conditions under which identification is possible, clarifying (and extending to the stochastic case) the result of [Fu al., 2018, Theorem C.I].
Corollary 4. Suppose at least as many actions (with linearly independent resulting transition probabilities) as we have possible future states, that is,
MDP either has deterministic transitions T ((''ss,)) (0.1) or have
rank (nnk(T((),,)))
= for some E A].
Then the (action-independent) IRL problem is identifiable (i.e. the true action-independent reward function can be inferred up to a constant shift) if and only if the MDP is rewant-deccopposable
not, by itself, sufficient to guarantee identifiability of rewards simply consider the trivial MDP with action space containing only one element (so no information can be gained by watching optimal policies) but all transitions are possible (so the MDP is rewarr-decoopoosabee..
is clear that reward- doirodddeo

---

The necessity of reward dew.adddddcommabbiitt.... in general, can easily be seen as follows: Suppose there are sets Sp, C such that every transition from a state in So (under every action) to state in S1, and every transition to a state in S is from So. Then, if we add E IR. to the reward in So \ (S, subtract c/7 from the reward in S \ So, and add (1 - 1/7)cc the reward in state Sp O S1, we will have no impact on the overall value or optimal strategies. A reward-decomposabilty assumption ensures S = S (which implies So = as every transition into S must be from state in So), so this is simply constant shift; otherwise, we see our IRL problem is not identifiable.
Acknowledgements
The authors acknowledge the support of the Alan Turing Institute under the Engineering and Physical Sciences Research Council grant EP//510129// Samuel Cohen also acknowledges the support of the Oxford-Man Institute for Quantitative Finance. As a visiting scholar, Haoyang Cao also appreciates the support provided by the Mathematical Institute University of Oxford.
References
Pieter Abbeel and Andrew Y Ng. Apprenticeship learning via inverse reinforcement learning. In Proceedings of the twenty-first international conference on Machine learning, page 1, 2004.
Kareem Amin and Satinder Singh. Towards resolving unidentifiability in inverse reinforcement learning, arXiv preprint 1rXiv:1601.06569) 2016.
Kareem Amin, Nan Jiang, and Satinder Singh. Repeated inverse reinforcement learning. Advances in Neural Information Processing Systems, 30:1810: 1811-188244 2017.
Sreejith Balakrishnan, Quoe Phong Nguyen, Bryan Kian Hsiang Low, and Harold Soh. Efficient exploration of reward functions in inverse reinforcement learning via bayesian optimization. Advances in Neural Information Processing Systems, 33, 2020.
Dimitir P Bertsekas and Steven Shreve. Stochastic optimal control: the discrete-time case. 2004.
Abdeslam Boularias, Jens Kober, and Jan Peters. Relative entropy inverse reinforcement learning. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 182-189. JMLR Workshop and Conference Proceedings, 2011.
Stephen Boyd, Laurent El Ghaoui, Eric Feron, and Venkataramanan Balakrishnan. Linear matrix inequalities in system and control theory. SIAM, 1994.
Paul Dupuis and Richard S Ellis. A weak convergence approach to the theory of large deviations. volume 902. John Wiley & Sons, 2011.
Krishnamurthy Dvijotham and Emanuel Todorov. Inverse optimal control with linearly-solvable mdps. In Proceedings of the 27th International Conference on International Conference on Machine Learning, ICML' 10, page 335-342, Madison, WI, USA, 2010. Omnipress. ISBN 978 9781605589077.
Chelsea Finn, Paul Christiano, Pieter Abbeel, and Sergey Levine. A connection between generative adversarial networks, inverse reinforcement learning, and energy-based models. arXiv preprint (XXiv:611.003855 2016a.
Chelsea Finn, Sergey Levine, and Pieter Abbeel. Guided cost learning: Deep inverse optimal control via policy optimization. In International conference on machine learning, pages 49-58, 2016b.
Justin Fu, Katie Luo, and Sergey Levine. Learning robust rewards with adverserial inverse reinforce- ment learning. In International Conference on Learning Representations, 2018.
Tuomas Haarnoja, Haoran Tang. Pieter Abbeel, and Sergey Levine. Reinforcement learning with deep energy-based policies. In International Conference on Machine Learning, pages 1352-1361. PMLR, 2017.
R. E. Kalman. When Linear Control System Optimal? Journal of Basic Engineering, 86(1): 51-60, 03 1964.
10

---

Ralph L. Keeney and Howard Raiffa. Decisions with Multiple Objectives: Trade- Offee-Offs. Wiley, 1976.
Preferences and Value
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 5496-5505, PMLR, 18-24 Jul 2021. URL http: / htttt::/pprceeeeeeee http///rrceeee...ccoo//./. mlr alr.press/ 1L39/kim21e html.
Sergey Levine. Reinforcement learning and control as probabilistic inference: Tutorial and review. arXiv preprini arXiv: /805.0090, 2018.
Sergey Levine, Zoran Popovic, and Vladlen Koltun. Nonlinear inverse reinforcement learning with gaussian processes. Advances in neural information processing systems, 24:19 2011.
Robert E. Lucas. Econometric policy evaluation: A critique. Carnegie-Rochester Conference Series on Public Policy, 1:19 46, 1976.
Thierry Magnac and David Thesmar. Identifying dynamic discrete decision processes. Econometrica, 70(2):801-816 2002.
Andrew Y Ng and Stuart Russell. Algorithms for inverse reinforcement learning. In Proceedings of Seventeenth International Conference on Machine Learning. Citeseer, 2000.
Andrew Y. Ng. Daishi Harada, and Stuart Russell. Policy invariance under reward transformations:
Theory and application reward shaping. In In Proceedings of the Sixteenth International Conference on Machine Learning, pages 278-287. Morgan Kaufmann, 1999.
Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John
Wiley & Sons, 2014.
Nathan D. Ratliff. J. Andrew Bagnell, and Martin A. Zinkevich. Maximum margin planning. In Proceedings of the 23rd International Conference Machine Learning, ICML '06, page 729-736, New York, NY, USA, 2006. Association for Computing Machinery. ISBN 1595933832. doi: 10.1 14.11 143844. 143936. URL http::/ttt/......oo org/10..00.. 1145/1143844 1143936.
Stuart Russell. Learning agents for uncertain environments. In Proceedings of the Eleventh Annual Conference on Computational Learning Theory, pages 101-103, 1998.
Thomas Sargent. Estimation of dynamic labor demand schedules under rational expectations. Journal of Political Economy, 1606):1009-1044, 1978.
E. Seneta. Non-negative Matrices and Markov chains. Springer, revised printing edition, 2006.
Brian Zicbart. Modeling Purposeful Adaptive Behavior with the Principle of Maximum Causal Entropy. PhD thesis, Carnegie Mellon University, 2010.
Brian D Ziebart, Andrew L. Maas, Andrew Bagnell, and Anind K Dey. Maximum entropy inverse reinforcement learning. In Aaai, volume 8, pages 1433-1438. Chicago, II, USA, 2008.

---

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]
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This work connects with well known concerns in economies, which we mention. As a work in the theory of RL, it has limited potential for direct negative societal impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] All results are rigorously stated
(b) Did you include complete proofs of all theoretical results? [Yes] The main results' proofs are given appendix due to length.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)? [Yes] The code and instructions was included in the supplemental material. We did not work with any particular dataset.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] We specified training details in the main text.
(c) Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)? [No] For the purpose of demonstration, instead of reporting error bars, we included training and test errors with respect to each random seed.
(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)? [No] We did not include this information in the main text the supplemental material. All the experiments have been conducted Google Research Colaboratory with GPU as hardware accelerator. The experiment in Section 4 took minutes and 14 seconds total for all random initializations.
4. If you using existing assets (e.g., code, data, models) 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 new assets either in the supplemental material a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're
using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
you used crowdsoureing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable?
[N/A]
(b) Did you describe any potential participant risks, with links to 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]


Reviews:
[{"review_id": "ON2x333dpuU", "reviewer": "Reviewer_HJD7", "summary": "The authors consider the question of recovering the exact reward function from trajectories in inverse reinforcement learning. To this end, the authors consider the formalism of IRL with a maximum-entropy regularized objective which can be seen as a generalization of the MaxEntIRL objective. Using this view, the authors show that the degrees of freedom of the reward correspond to an arbitrary, desired value function. The authors show that the reward function can be fully recovered if the policy is known in two distinct MDPs with sufficiently different transition-dynamics and/or discount factors and give conditions for which this is the case. Similar theorems are given for finite MDPs as well as the linear quadratic regulator. \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": "I found the writing to be exceptionally clear and the proofs were easy to follow. One welcome change would be to clarify the contributions early on as they differ from what is typical in the IRL literature. Usually, identifiability is treated as a concern for stability and empirical analysis (of MaxEntIRL, for example) concentrates on the apprenticeship learning problem. In this paper, apprenticeship learning is not a concern as the authors explicitly assume that the policy can be fully recovered from demonstrated data. It is thus also unclear how well the algorithm would fare if expert data is limited and if there are scenarios where the insights from this paper could help recover optimal policies where behavioral cloning is insufficient.\n\nWhile the given theorem is clear and, to the best of my knowledge, novel, it is also likely to be of limited use in direct applications. Not only do the authors assume access to the full expert policy, they furthermore assume access to the policy in two different MDPs with identical reward functions. Such MDPs can be constructed numerically, but are difficult to construct in practice.  In the background section, the authors claim that the transition dynamics can be recovered from expert trajectories; however, this is inconsistent with the proposed procedure where the dynamics have to be constructed. Furthermore, if the expert is a human demonstrator or a differently specified system, the discount factor is likely not known and should be treated as a modelling assumption. (In fact, human expert demonstrators are assumed to follow hyperbolic discounting, rather than exponential). Asking a demonstrator to provide demonstrations for two specific discount factors is therefore highly limiting. Discussion on how the proposed methods may generalize in the approximate case would be appreciated.\n\nNumerical results are minimal and serve only as sanity checks. No application of the method is proposed. Overall, the contribution of this paper is clear, novel and well supported, but also limited.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "-", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "O3pg5Yosax4", "reviewer": "Reviewer_EpRH", "summary": "This work presents theory and experiments on the problem of reward function non-identifiability in IRL. The key result is Theorem 1, which entails that the reward function (in the entropy-regularized MDP setting) cannot be uniquely identified given an unknown value function. Following this line of reasoning, the authors argue that it is possible to identify the reward function (up to a constant) provided we can disentangle immediate rewards from preferences over future states (e.g., with data from two agents with different discount factors in the LQG setting). This result is also demonstrated empirically using a small example. ", "questions": "", "limitations": "", "rating": 6, "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": "This paper investigates a key problem in IRL, which is relevant for important issues, e.g., value alignment. The paper is generally well-written and the theoretical results are novel (to my knowledge) and elucidate why non-identifiability occurs, i.e., the unknown value function, and discusses when the true reward function can be retrieved. This theoretical study could potentially lead to novel downstream IRL methods. On the downside, the paper has issues that I hope the authors can address: \n- The paper is not well-placed wrt the existing literature surrounding identifiability in IRL and the related works section misses out on closely-related prior work, e.g.,  (Kim et al, 2012) discusses conditions under which the reward function identifiable, and recent methods (e.g., Amin et al, 2017; Balakrishnan et al, 2020) have been proposed with non-identifiability in mind. See below for additional references. \n- Can the authors provide some justification for the claim that the function class in Theorem 1 is unique? This is important as other reward function structures may also lead to the optimal policy, potentially giving rise to other forms of unidentifiability? Theorem 2 also relies on the uniqueness of the reward function. Also, can the authors clarify Remark 2? From my understanding, the results in Ng et al (1999) does not imply that non-identifiability solely arises from potential-based reward shaping functions. \n- The experiments serve to support the claims, albeit in a very simple setting, and could be better presented. I suggest the authors reorganize the results; it would be helpful if all the key results were in the main paper rather than split off into the supplementary (e.g., fig 6/7 is in the supp). Fig 2 and 3 take up unnecessary space and can be summarized. \n\nOverall, the work tackles an interesting problem, but due to the issues above, I remain uncertain and unconvinced about the significance of the work. I hope the authors can address my queries above.\n\nReferences:\n- “Reward Identification in Inverse Reinforcement Learning”, Kim et.al, ICML 2021\n- \"Repeated Inverse Reinforcement Learning”, Amin et.al., Neurips 2017\n- “Towards Resolving Unidentifiability in Inverse Reinforcement Learning”, Amin et.al., 2016\n- “Inverse Optimal Control with Linearly-Solvable MDPs”, Dvijotham et. al, ICML 2010\n- “Efficient Exploration of Reward Functions in Inverse Reinforcement Learning via Bayesian Optimization”, Balakrishnan et.al,\n\n### Post Response\nThank you for your response and the detailed comparison to other works. I agree that it was not reasonable to compare to Kim et al 2021 in the submitted version, but it would be good to include these comparisons in an updated version. While I think the contributions are of limited practical value at this time, there is some value to the findings and I have raised my score to a 6. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the limitations and societal impact are discussed. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "McF9GLA8Vlb", "reviewer": "Reviewer_TmNY", "summary": "This paper studies the reward identifiability problem in inverse reinforcement learning, under a special family of MDPs -- entropy-regularized MDPs. The authors provide some mathematical deductions to show the identifiability is still an issue given entropy-regularization and side information from another policy with a different transition probability or a different discount factor but a consistent reward function may be sufficient to resolve it. They then construct a simple linear-quadratic Gaussian MDP to support their theorems and conduct numerical simulations. The empirical results validate their claims. ", "questions": "", "limitations": "", "rating": 4, "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": "Originality: This paper makes some conceptual contributions in theorializing some intuitions of reward identifiability in IRL. I like the way the authors employ simple but appropriate mathematical language and examples to explain the idea. However, the idea they convey seems not novel to me, given the prior work from Ng et al. 1999. It is true that the entropy-regularization might be something not covered by Ng et al. 1999, but I wonder how the authors would compare this work with Kim et al., 2021, who study the same reward identifiability problem and deduce some structural properties for MDPs to obtain such identifiability. \n\nQuality: The problem this paper studies is interesting -- to what degree the reward function is identifiable in IRL. The \n\nClarity: This paper is overall well-written. I like the way the authors build up everything step by step. \n\nSignificance: This paper may be interesting in terms of how the authors conceptualize the problem. But in my opinion, it is at least not as significant as Kim et al., 2021, who go beyond a trivial solution of introducing side information from another optimal policy. I would like to know my fellow reviewers' thoughts on this.  \n\nKim et al. 2021, Reward Identification in Inverse Reinforcement Learning", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors did not make extrapolative claims. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "4BIjrAD00Ia", "reviewer": "Reviewer_YPRS", "summary": "The paper considers the problem of reward identifiability in a maximum entropy inverse optimal control setting when access to the expert policy is available. It is shown that the reward function can only be recovered up to a state-dependent shaping term (which relates to the temporal credit assignment). If access to the optimal policies for two variants (different discount factor or different transition model) of a given MDP is available, it is shown that the reward function can be recovered (up to a constant).\nThe results are validated on numerical experiments on a finite MDP, with known transition model policies.", "questions": "", "limitations": "", "rating": 5, "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": "Significance\n----------------\nLearning reward functions that generalize across different dynamics is one of the main open problems in inverse reinforcement learning. New insights under which assumptions such reward functions are recoverable could help to tackle this problem and would constitute an important contribution.\n\nOriginality\n--------------\nUnfortunately, I don't think that the paper presents any significant new insights. Fu et al. [2017] already noted that the log-policy corresponds to the soft advantage and thus a shaped reward function. They also noted that any reshaping with a potential function $\\phi(s)$ results in the same optimal policy, and that this potential function corresponds to the value function of a reward function that can be computed as $r(s,a) = A(s,a) - \\gamma E[\\phi(s')] + \\phi(s)$. Hence, I argue that its neither news that the expert policy alone only allows to recover the reward up to a temporal reshaping (relating to the Value function), nor is it news that the reward function can be recovered when in addition to the policy also the value function is known.\n\nThe paper also presents proof that the reward function can be recovered when having access to two optimal policies for different discount factors. While such proof seems to be novel, it is not surprising that the ill-posedness regarding the temporal credit assignment can be resolved by observing policies with different temporal weighting. Furthermore, I think that the derivations are straightforward and the insight little useful in practice.\n\nQuality\n-----------\nThe quality is good. The derivations seem correct, the numerical evaluation (or confirmation) make sense and shows the expected results.\n\n\nClarity\n----------\nThe paper is well written. Eq.1 is missing parentheses around reward and entropy (discounting should also affect the entropy). \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Sufficiently addressed.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Two reviewers recommended rejection of the paper (1x reject, 1x weak reject) and two reviewers recommended (weak) acceptance of the paper. Initially the reviewers raised concerns regarding novelty, significance, and relation to existing work. This was acknowledged by reviewers and some of them increased their score for the paper. I discounted the concern regarding comparison with Kim et al. as this paper was not available by the deadline of this conference (as also indicated by the authors). Overall the discussion of the authors with the reviewers and my own reading of the paper led me to the conclusion there are some interesting contributions in the paper and I am therefore recommending acceptance of the paper.
Nevertheless, the paper in its current form does not place the paper clearly in the context of existing results (as evidenced by a very short related work section and the initial confusion of the reviewers) and I strongly encourage the authors to make the relation to existing results more clear in final paper (e.g., by incorporating the responses they gave to reviewers during the discussion period).
Decision: Accept (Poster)