Invariance in Policy Optimisation and Partial Identifiability in Reward Learning
Authors: Joar Max Viktor Skalse
Matthew Farrugia-Roberts
Stuart Russell
Adam Gleave
Venue: ICLR 2022 Submitted (2022)

Abstract: It is challenging to design a reward function for complex, real-world tasks. Reward learning algorithms let one instead infer a reward function from data. However, multiple reward functions often explain the data equally well, even in the limit of infinite data. Prior work has focused on situations where the reward function is uniquely recoverable, by introducing additional assumptions or data sources. By contrast, we formally characterise this partial identifiability for popular data sources such as demonstrations and trajectory preferences. We analyse the impact of this ambiguity on downstream tasks such as policy optimisation, including under shifts in environment dynamics. These results have implications for the practical design and selection of data sources for reward learning.

Under review as a conference paper at ICLR 2022
INVARIANCE IN POLICY OPTIMISATION AND PARTIAL IDENTIFIABILITY IN REWARD LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Designing reward functions for complex, real-world tasks is challenging. Reward learning lets one instead infer reward functions from data. However, multiple re- ward functions often fit the data equally well, even in the infinite-data limit. Prior work often considers reward functions to be uniquely recoverable, by imposing additional assumptions on data sources. By contrast, we formally characterise the partial identifiabiliy of popular data sources, including demonstrations and tra- jectory preferences, under multiple standard sets of assumptions. We analyse the impact of this partial identifiability on downstream tasks such as policy optimisa- tion, including under shifts in environment dynamics. We unify results in a framework for comparing data sources and downstream tasks by their invariances, with implications for the design and selection of data sources for reward learning.
INTRODUCTION
A wide range of problems can be represented sequential decision-making tasks, where the goal is to maximise some numerical reward (Sutton & Barto 2018). However, designing an appropriate reward function remains challenge in complex real-world tasks (Amodei al.. 2016 Leike al.,
2018 Dulac-Arnold et al.) 2019). Reward learning algorithms infer task reward functions from data sources such as expert demonstrations (Ng & Russell, 2000), preferences over trajectories (Chris-) tiano et al. 2017), and many others (Jeon et al.] 2020). This approach has extended the applicability of sequential ceciisionmmakinn techniques to more complex tasks (e.g. Abbeel et al. 2010 Christiano
et al. 2017 Singh et al., 2019; (Stiennon et al.) 2020).
Multiple reward functions are often consistent with the data source, even in the infinite-data limit. For most data sources, this fundamental ambiguity has been acknowledged, but its extent has not been characterised. In section 3 we formally characterise the ambiguity of several popular data sources including expert demonstrations and trajectory preferences. These infinite-data limits bound the information recoverable from finite data sets using any algorithm, so they are useful for evaluat- ing algorithms relative their limits, and data sources relative to each other.
Uniquely identifying a reward function is unnecessary when all plausible reward functions lead to the same downstream outcome in given application, such as policy optimisation. Characterising this ambiguity folerance for various applications allow us to evaluate the ambiguity of data source relative a given application. Learnt reward functions are often used for policy optimisation, for example via reinforcement learning ( In section 3 we formally characterise the ambiguity tolerance of policy optimisation under arbitrary dynamics.
Ambiguity and ambiguity tolerance are formally related. Both concern invariances - of data sources or downstream outcomes to reward function transformations. Thus, our main contribution is to catalogue the invariances of various mathematical objects derived from the reward function. In section we explore partial order on these invariances, and its implications for the selection and evaluation of data sources, addressing an open problem in reward learning (Leike et al. 2018 $3.1).
'We focus on RL applications. Further applications arise in other fields, where reward functions are used in models to understand and predict the behaviour of humans, animals, and other systems (see, e.g., Schoemaker
1982 Dennett 1989
Rust 1994 Howes al. 2014 Peterson al. 2021 Collins & Shenhav 2021

---

Under review as a conference paper at ICLR 2022
increasing ambiguity (tolerance)
R
id
G
Q
GE
mask of
k-
PLS
supp(r)
T
IRL
pref. cmp.
+
S'-R.
ZPMT
OPT
(b)
(a)
Figure 1: (a) The infinite-daa ambiguity of reward learning data sources, and the ambiguity toler- ance of downstream applications of learnt reward function, are both invariances of objects derived from reward functions (sections] 1.2 and (3). These invariances have a partial order (section : here, X Y means that Y can be derived from X, or equivalently that Y is at least as ambiguous as X. The objects are: the reward function itself (R); Q-functions (Q); Maximum Entropy (8) and supportive optimal policies (+) and their induced trajectory distributions (Tp. Ag and π., A.); the return function restricted to partial and full trajectories (Gç. Gg); Boltzmann -istrrrbbdddtttuteedddd (5) and noiseless (+) comparisons between these trajectories (=)) zSz and =كك =S) (b) Several basic fami- lies of reward transformations form the basis for our main results (section 2). These transformations exist related hierarchy, within (shown here) and across tasks (section
1.1 RELATED WORK
Inverse reinforcement learning (IRL: Russell 1998) is the prototypical example of reward learning.
IRL. infers reward function from the behavioural data of a task expert by inverting model of the
expert's planning algorithm (Armstrong & Mindermann 2017; Shah et al. 2019). Existing work partially characterises the inherent ambiguity of behaviour for certain planning algorithms (Ng & Russell 2000; Cao et al. 202T) and classes of tasks (Dvijotham & Todorov 2010; Kim et al. 2021). )). We extend these results to more planning algorithms and arbitrary time-unbounded, stochastic tasks, using a more expressive space of reward functions that reveals novel ambiguity.
Reward learning models have been proposed for many other data sources (Jeon al., 2020). A popular and effective data source is preferences over behavioural trajectories (Akrour et al. 2012 Christiano et al. 2017). Unlike for IRL, the ambiguity arising from these data sources has not been formally characterised. We contribute a formal characterisation of the ambiguity for central models of evaluative feedback including trajectory preferences.
Several studies have explored learning from expert behaviour and preferences (Ibarz et al. 2018
Palan al. 2019 Biyık et al. 2020 Koppol al., 2020), other multi-modal data sources (Tung ct al. 2018 Jeon et al. 22200). One motivation is that different data sources may provide comple- mentary reward information (Koppol et al.. 2020). eliminating some ambiguity. Similarly, Amin et al. (2017) and Cao et al. (2021) observe reduced ambiguity by combining behavioural data across multiple tasks. Our partial order provides a general framework for understanding these results.
Computing an optimal behavioural policy is primary application of learnt reward functions (Abbeel & Ng. 2004) Wiithh et al.] (017). Ng et al. (1999) proved that potential shaping transformations always preserve the set of optimal policies, and so are always tolerable for this application. We extend this result, characterising the full set of transformations that preserve optimal policies each task, including for additional policy optimisation techniques such as maximum entropy RL.
Ambiguity corresponds to the partial identifiabiiiyy (Lewbel 2019) of the reward function modelled as latent parameter. The prevailing response to partial identifiability in reward learning has been to impose additional constraints or assumptions until the data identifies the reward function uniquely (or, at least, sufficiently for policy optimisation). Following Manski (1995) 2003) and Tamer (2010), we instead describe ambiguity given various constraints and assumptions. This gives practitioners results appropriate for their real data (and the ambiguity tolerance of their actual application).
2

---

Under review as a conference paper at ICLR 2022
IRL is related to dynamic discrete choice (Rust
1994
Aguirregabiria & Mira 2010). problem
where identifiability has been extensively studied (e.g., Aguirregabinaa 2005 Srisuma 2015 Ar-
eidiacono & Miller, 2020). We study simpler setting with known tasks. IRL also relates prefer- ence elicitation (Rothkopf & Dimitrakakis) 2011) ) and inverse optimal control (Ab Azar et al. 2020).
Preferences over sequential trajectories not typically considered data source in other fields.
1.2 PRELIMINARIES
We consider an idealised setting with finite, observable, infinite-horizon sequential decision-making environments, formalised as Markov Decision Processes (MDPs: [Sutton & Barto 2018 $3). An MDP is tuple (S, A. T. Ho. R, where S and A are finite sets of environment states and agent ac- fions; T SxAA (SS) encodes the transition distributions governing the environment dynamics; Mo E (SS) is an initial state distribution; R Ax - IR is deterministic reward function and 7 E (0, 1) is a reward discount rate. We distinguish states in the support of μi as initial states, and states with (ss|s, a) and R[s a, s) 0 for all a as terminal states.
We represent the transition from state 8 to state s' using action a as the tuple x (8, U, 8'). We clas- sify (s, a, s') as possible in an MDP if s' is in the support of ((s, a), otherwise it is impossible. A tra- jectory is an infimite sequence of concatenate transitions & = ($p, ag: 81, a1, 82.. and a trajectory fragment of length n is finite sequence of n. concatenate transitions
(su, ao, .1..... Og-1; 8n)- A trajectory or fragment is possible if all of its transitions are possible, and is impossible otherwise. A trajectory or fragment is initial if its first state initial. A state or transition is reachable if it is part of some possible and initial trajectory.
Given MDP, define the return function G as the cumulative discounted reward of entire tra- jectories and trajectory fragments: G(C) ->>=> 7 R(s,, at 81+1) for trajectory fragment Ç of length n, and similarly for trajectories. We primarily consider this return function with various restricted domains, such as only possible or initial trajectories or trajectory fragments.
A policy π ::a S - (AA) encodes an agent's behaviour as state-conditional action distribution. Together with an MDP's transition distribution T, a policy π induces a distribution of trajectories starting from each state. We denote such trajectory starting from 8 with the random variable E., and its remaining components with random variables Ag, S1, A1, S2, and so on.
Given an MDP and policy æ, and the value function encodes the expected return from states, V=(+)) = -5,-,,7 [G(E.)] and the Q-function of π encodes the expected return given an initial action, (s, Ra, [G(E.) Ao = a]. Qx and Vn satisfy a Bellman equation: (s(s,)) Eg [R(s, a, S') ) + (5'),
(s()) (A A)],
(1)
for all 8 e S and a E A. Their difference, Ar a) Qx( (s), is the advantage function.
We further define a policy evaluation function, J, encoding the expected return from following a particular policy in an MDP, [(r) = EE VV= (So)]. I induces an order over policies. A policy maximising J is an optimal policy, denoted ... Similarly, Q. V., and A, denote the Q-, value, and advantage functions of an optimal policy. Since I may be multimodal, we often discuss the set of optimal policies. However, Q., V., and A. are unique.
Moreover, consider several policies resulting from alternative planning algorithms. Given base policy To. and an inverse temperature parameter 3 >> O, we define the Boltzmann policy with respect to Tp, denoted TT using the softmax function:
(als) = exp(33 (3 (s, 3
To
(2)
EN'e exp (s,
The Boltzmann-rationall policy, TH. the Boltzmann policy with respect to optimal policies, used for IRL by Ramachandran & Amir (007)). The popular Maximum Entropy policy, na. is defined using a modited policy evaluation function with an entropy regularisation term (Haarnoja et al. 2017) and solves the recurrence Te "
To (i.e., Th is Boltzmann policy with respect itself).
'Notably, we consider deterministic reward functions that may depend on a transition's 's successor state. Al- ternative spaces of reward functions are often considered (such as functions from S or SxA,, or distributions). The chosen space has straightforward consequences for invariances, which discuss in appendix C
3

---

Under review as a conference paper at ICLR 2022
2 REWARD FUNCTION TRANSFORMATIONS
In this section, we discuss how invariance to reward function transformations relates to infinite-data ambiguity in reward learning and ambiguity tolerance in applications.
Definition 2.1 (Transformations and invariances). A transformation is a map between reward func- tions. The invariances of an object X derived from reward It via function f are all transformations t that preserve f: X ((R)- = [()( for all R. We say that X determines It up to its invariances.
A set of transformation carves out a partition of the space of reward functions by grouping together those reward functions reachable from one another using the transformations. The partition carved out by the invariances of an object is the equivalence kernel of the object's 's derivation function grouping the reward functions from which identical objects are derived into partition blocks.
Given reward learning data source, consider the object encoding the information available from the data source in the infinite-data limit (Lewbel| 2019 $3.1). The invariances of this object represent the infinitedaata ambiguity of the data source - is impossible to recover the reward function beyond the corresponding partition block, as the remaining functions imply indistinguishable data.
Similarly, consider downstream application of learnt reward functions involving the computation of an object. The object's 's invariances capture the ambiguity tolerance of this computation, as by def- inition all reward functions in each block of the corresponding partition lead to identical outcomes.
2.1 FUNDAMENTAL REWARD TRANSFORMATIONS
We introduce several fundamental sets of reward function transformations, forming a basis for the invariances we study in section 3 Before considering several novel transformations, we recall po- tential shaping, introduced by Ng et al. (1999) and widely known to preserve optimal policies in all MDPs. We further distinguish special potential shaping transformations with constant potential over an MDP's initial states. We explore some properties of potential shaping in appendix A
Definition 2.2 (Potential Shaping). A potential function is a function & : S - IR, where D(s) = if s is terminal state. If ((s) A for all initial states then say that Tb is k-initiall Let R and R' be reward functions. Given a discount y, we say R' is produced by (k-initiall) potential shaping of R if (8(ss, a, 8') = R(s, 8') + 7. ((5)) (bs)) for some (k-initiall) potential function +.
Definition 2.3 (S' Redisrriiribb.i..)). Let R and R' be reward functions. Given transition dynamics T, say R' is produced by S' r'eeisstribttto of R if (ssa) RR(s, a, s')] = Egr~r(s.o) [s, a, S.
S'-redistribution allows changing R arbitrarily for impossible transitions. Moreover, if at least two states s'1. 8/2 are in the support of 7(s, a) then S'-redistribution lets us increase R(s, s1) and decrease R( ((ss00 a, 552) by a proportionate amount. Note that S' r'-eriitrrbuttion depends crucially on the reward function's 's dependence on the successor state. This set of transformations collapses to the identity for simpler spaces of reward functions, as we explore in appendix C
Definition 2.4 (Monotonic Transformations). Let R and R' be reward functions. Say R' is produced by a zero-preserving monotonic transformation of R if for all pairs of transitions x; x' E Sx Ax,, R(x) & R(x') if and only if R'(x) & R'xx"), and R(x) = 0 if and only if R'(x)) = 0. Moreover, say Rt is produced by positive linear scaling of R R' = c- R for some positive constant c.
A zero-preserving monotonic transformation simply a monotonic transformation that maps zero to itself. Positive linear scaling is a special case.
Definition 2.5 Apptimality-Presevvvii Transformation). Let R and R' be reward functions. Given a function O : S - P(A) [Ø). transition dynamics т, and discount rate y. we say R' is produced from R by an optimaliiy-preserving transformation with O if there is a function V : S - R such that (r.a))) [s, [F', S*) + 7 ((S))) < (s) for all s, a, with equality if and only if a O(s). This transformation gives the reward functions with optimal actions from O (v determines the new value function). Note that in practice an implicit dependence R is introduced through the definition of O. Also, we can reach arbitrary R' if O is unconstrained (in practice, we constrain O).
Finally, we consider transformations allowing the reward vary freely for given set of transitions. Definition 2.6 (Masking). Let R and R' be reward functions. Given a transition set X s SxxAxS, say R' is produced by mask of X from R if R(x) R'(x) for all x & X.
4

---

Under review as a conference paper at ICLR 2022
3 INVARIANCES OF HEWARD-RELATER OBJECTS
In this section we catalogue the invariances of various central objects derived from reward functions, including expert trajectory distributions, the ranking of trajectories induced by the return function, and the set of optimal policies. Some of these objects correspond to the information available in the infinite-data limit of a reward learning data source, while others correspond to the outcome of a downstream application.
If an object X can be derived from another object Y without further reference to the reward function, then X" inherits Y's invariances. For example, the optimal Q-function's 's invariances are inherited by various expert policies. Accordingly, we organise this section by incrementally deriving our objects of interest starting from the reward function, cataloguing the invariances introduced in each step. This also mirrors the structure of figure Ta
We defer all proofs until appendix B
3.1 INVARIANCES OF EXPERT BEIIAVIOUR
Inverse reinforcement learning (IRL) algorithms infer task's reward function from the behaviour of task experts. Formally, this behaviour is represented as expert's ' policy sample of trajectories.
To characterise the corresponding invariances, we begin with Q-functions instrumental to deriving many policies. Q-functions are invariant to s'-redistribution since they are defined as an expectation over the successor state S", We show that this is the only invariance for Q-functions.
Theorem 3.1. Given MDP and a policy n, the Q-function for ग, Qm. determines R up to S'- redistribution. The optimal Q Q-function, Q., has precisely the same invariances.
This invariance is inherited by any object that can be derived from Q-function. However, note that S' s'-redistribution vanishes in simpler spaces of reward functions, as we explore in appendix
We now turn to policies derived using various planning algorithms. These policies are instrumental in constructing the trajectories studied in IRL. For example, RRaaccandran & Amir (2007) and
Ziebart et al. (008)) assume that expert behaviour is drawn from a Boltamann-rationd policy, and Ziebart et al. 2010) assume a Maximum Entropy policy We catalogue the invariances of arbitrary Boltzmann policies, of which these other policies are special cases. As these policies can be derived from Q-functions, they inherit invariance to S' s'-redistribution. We show they are also invariant to potential shaping, but not to any other transformations.
Theorem 3.2. Given MDP, inverse temperature parameter B, and base policy To. the Boltzmann policy 33 rational policy, Tt. and the Maximum Entropy policy, Tg, have precisely the same invariances.
To determines R up to S'-redistribution and potential shaping. The Boltzmann-
By contrast, Ng & Russell (2000) and Abbeel & Ng 2004) assume that experts follow an optimal policy. Optimal policies inherit S' s'-redistribution invariance from the optimal Q-function, and are also known to be invariant to potential shaping et al. 1999). Under an additional assumption that a given policy maximally supportive, in that it takes all optimal actions with positive probability, we show that these invariances and any additional invariances are captured in class of optimality- preserving transformations (Definition 2.5) based on the set of optimal actions each state.
et
Theorem 3.3. Given an MDP, let O(s) arg A. a). A maximally supportive optimal policy determines up to appimaaity-preserving transformations with O.
Additional invariances arise if we consider optimal policies that may lack support for optimal ac- tions. As well-known example, the zero-reward is consistent with any policy in this sense.
In the infinite-date limit, data source of trajectories sampled from a policy reveals the distribution of trajectories induced by the policy, and therefore the policy itself for all states reachable via its supported actions. A Boltzmann policy supports all actions, so in the infinite data limit, samples of trajectories determine the policy for all reachable states. We show this introduces invariance precisely to changes in the reward of unreachable transitions.
Theorem 3.4. Given MDP, an inverse temperature parameter B, and base policy no. the dis- zo from all initial states determines R
tribution of trajectories induced by the Boltzmann policy gH up to S' "-rreisttribution, potential shaping, and mask of unreachable transitions. The distributions of trajectories induced by the Boltzmann-ration from all initial states, have precisely the same invariances.
policy, why and the Maximum Entropy policy, ng,
5

---

Under review as a conference paper at ICLR 2022
Similarly, trajectories sampled from optimal policy reveal the policy in those states that its actions reach. This again introduces additional invariance to transformations of reward in other states.
Theorem 3.5. Given an MDP, consider the distribution of trajectories induced by maximally supportive optimal policy. Let 6 be the set of states in supported trajectories. Let D be the set of functions O defined on S such that (ss) distribution of trajectories determines R up to optimality-preserving transformations with O E D.
arg A. a) for all G. The induced
Note that a mask of the complement of is not permitted. However, the fact that O is uncon- strained outside & leaves reward effectively unconstrained in those states, except that the reward of transitions out of & may have to "compensate" for the value of their successor states, to prevent new actions that lead out of G from becoming optimal.
3.2 INVARIANCES OF TRAJECTORY EVALUATION
The return function, capturing the reward accumulated over a trajectory. is instrumental in deriv- ing data for evaluative feedback such reward labels and trajectory preference comparisons. We consider the invariances of the return function for various restricted domains.
Theorem 3.6. Given an MDP, the return function restricted possible trajectory fragments, Go, determines R up to a mask of impossible transitions;
Theorem 3.7. Given an MDP, the return function restricted to possible and initial trajectories, Ge, determines R up to zero-initial potential shaping and mask of unreachable transitions.
The limited invariance of the return of fragments arises because this restricted domain still includes individual (possible) transitions. Additional invariances will arise from additional restrictions, such minimum or maximum fragment length, restriction to initial trajectory fragments.
Pairwise comparisons between trajectories are studied as a data source for reward learning (Akrour al. 2012 Christiano et al. 2017). It common model the comparisons as based the return of trajectories, but with accompanying decision noise following a Bolizmann distribution. Under this assumption, in the limit of infinite noisy comparisons for each pair of trajectories, the data source reveals the Boltzmann distributions. Boltzmann noise encodes relative cardinal information about the return of trajectories and fragments, little invariance introduced.
Formally. given an MDP and an inverse temperature parameter O, let =S be distribution over each pair of possible trajectory fragments, Ç1, S2. such that exp((G((4))
IP( 2S (2) exp(3G((i)) + exp(3G((2))
and let > be the analogous distribution over each pair of possible and initial trajectories.
Theorem 3.8. Given an MDP, the distribution of comparisons of possible trajectory fragments, S determines R up to a mask of impossible transitions.
Theorem 3.9. Given an MDP, the distribution of comparisons of possible and initial trajectories, S determines R up to k-initial potential shaping and a mask of unreachable transitions.
The limited invariance of Boltzmann comparisons of fragments arises from the very flexible com- parisons permitted, including, for example, comparisons between individual transitions and empty trajectories. Additional invariances will arise from additional restrictions, such as permitting com- parisons only between fragments of a fixed length. Moreover, worth reiterating that these invariances rely heavily on the precise structure of the decision noise revealing cardinal information in the infinite- data limit.
It is also possible to model trajectory comparisons noiseless comparisons based on the return. The infinite data limit then corresponds to the order induced by the return functions. Formally, define the noiseless order of possible trajectory fragments as relation, <S, on possible trajectory fragments:
Si S &2 G(G)) & G((2)-
Similarly, define the noiseless order of possible and initial trajectories as the analogous relation, <1. for pairs of possible and initial trajectories. These relations omit cardinal information about pairwise comparisons, and so invariances to certain monotonic transformations are introduced. The precise monotonic invariances depend on the MDP (for example, see the proof in appendix B.3)

---

Under review as a conference paper at ICLR 2022
Theorem 3.10. We have the following bounds on the invariances of the noiseless order of possible trajectory fragments, s.. In all MDPs:
(1) 2S is invariant positive linear scaling and mask of impossible transitions; and
(2) 2. is not invariant to transformations other than zero-preserving monotonic transforma- tions or masks of impossible transitions.
Moreover, there exist MDPs allaining each of these bounds.
We give lower bound on the invariances of the noiseless order of possible and initial trajectories, =.. Since = can be derived from = it inherits the latter's invariances. Moreover, like 2/. = is always invariant positive linear scaling.
Theorem 3.11. Given an MDP, the noiseless order of possible and initial trajectories, =., is invari- ant to k-initial potential shaping, positive linear scaling, and mask of unreachable transitions.
3.3 INVARIANCES OF POLICY OPTIMISATION
The primary application of learnt reward functions compute optimal policies, using techniques such as RI. Policy optimisation procedures typically compute single optimal policy. However, terms of invariances, one may desire to preserve the whole ser of optimal policies, so as not to tolerate any sub-optimal policies becoming optimal through a reward transformation.
The set of optimal policies inherits 5' s'-redistribution invariance from the optimal Q-function, and is also known to be invariant to potential shaping (Ng et al. 1999). In fact, because a maximally supportive optimal policy can be derived from the set of optimal policies and vice versa, the set shares the same invariances as maximally supportive optimal policy (Theorem (.3).
Theorem 3.12. Given an MDP, let (ss) = arg max, (.(s, (s, a). Then the set of optimal policies determines R up to prrseevvng transformations with O.
Moreover, if one uses algorithm not guaranteed to find a globally optimal policy, one may desire to preserve the entire order induced on the space policies by the policy evaluation function, rather than just the set of maximising policies. Future work could investigate the invariances of the ordinal information in the policy evaluation function. Note that since the set of optimal policies can be derived from this order, the order has at most the invariances of the set of optimal policies.
Finally, we sketch some bounds on the invariances of the set of optimal policies across all MDPs. Potential shaping and linear scaling preserve optimal policies in each MDP, and hence in all MDPs. S' s'-redistribution and optimality- prreiityyreeeriingggg transformations for a given MDP might not. Moreover, transformation in
Theorem 3.12 jmplies that any transformation that is not an andimality-preserrvie a given MDP cannot preserve optimal policies in that MDP, let alone all MDPs.
IMPLICATIONS FOR REWARD LEARNING
So far we have catalogued the invariances of transformations to the reward function of various reward function derived objects. These invariances characterise the infinite-dala ambiguity of several reward learning data sources, and the ambiguity tolerance of policy optimisation. In this section, we discuss the implications for the practical evaluation of reward learning data sources.
We begin by defining a mathematical framework for comparisons between data sources and applica- tions in terms of their ambiguity. The characterisation of ambiguity and tolerance as invariances to reward transformations suggests natural partial order on data sources and applications. Recall that the invariances of an object correspond to a purtition of the space of reward functions (section 2 We lift the refinement relation for partitions (Aigner 1979 $1.2.B) to data sources and applications as follows.
Definition 4.1 (Ambiguity refinement). Consider two reward learning data sources (or applica- tions), X and Y. Let IIx and Ily be the partitions of the space reward functions corresponding to their respective invariances (definition 2.1). If II is a partition refinement of Il., we write X < Y, and we say X is no more ambiguous than (or is tolerable for application Y). If < but not Y X, then we write X < Y and say X is (strictly) less ambiguous than Y.

---

Under review as a conference paper at ICLR 2022
Given two data sources X and Y, X < Y corresponds to X conflating additional reward fune- tions compared to Y in the infinite-data limit. This is the sense in which we say X is no more ambignous than Y. Moreover, given downstream application Z, X Z is precisely the condi- tion of Z tolerating the infinite-data ambiguity of data source X: < Z if and only if the reward functions conflated by X in the infinite-data limit all lead to the same outcome in Z.
Of our fundamental reward functions transformations, there are several clear instances of ambi- guity refinement in a given MDP, summarised in figure [b] Invariance to k-initial potential shaping (k-@) corresponds to less ambiguity than general potential shaping (Φ). Likewise positive linear scaling (PLS) is less ambiguous than preserreggg monotonic transformations (ZPMT), and a mask of impossible transitions is less ambiguous than S -edditsttibttton (S' (S). All of these transformations other than rero-pres monotonic transformations are less ambiguous than the oprimality-preserving preserving transformations we have encountered.
More concretely, we can compare the ambiguity of specific data sources. Some of these comparisons are indicated in figure [a] For example, the ambiguity tolerance of the set of optimal policies is transformations. Each of the data sources that are less ambiguous than this tolerance are sufficient for policy optimisation.
class of aptimality-preservvie
Notably, this excludes noiseless comparisons between trajectory fragments in some MDPs. Specif- ically, policy optimisation does not, in general, tolerate pett-rreserving monotonic transformations (ZPMT), while noiseless comparisons are invariant to this transformation in some MDPs (Theo- rem 3.10p. Policy optimisation also does not tolerate data sources based possible and initial trajectories, which are invariant to a mask of unreachable transitions. However, these sources are tolerable if the application only requires optimal behaviour in reachable states.
Moreover, we can compare data sources drawn from one MDP to applications in another MDP, such under a shift in transition dynamics initial state distribution. This captures the common sim-to-real setting where learning takes place in a simulated or otherwise restricted environment that differs from the final deployment environment. The simplest transformations to consider are masks of possible or reachable transitions. These are parametrised by transition dynamics. In general, the ambiguity corresponding to a mask of X' is less than for a mask of X' X. For example, if the new dynamics supports transitions that were previously impossible, then sources with invariance to a mask from the original MDP may not tolerable for applications in the new MDP.
A similar results holds for S' S'-redistribution, which involves an expectation over MDP dynamics. As an extreme example, we prove that when the transition dynamics are changed for every state and action, S' d'rredistribution under the original dynamics permits an arbitrary Q-function under the new dynamics. Naturally, data sources derived from Q-functions may also be affected by shifts in dynamics. Note that this strong result relies on the formulation of rewards depending on the successor sttcessor-state (cf. appendix (..
Theorem 4.1. Consider an MDP (S,A, T, Ma; R) a n, and alternative transition dynamics '' with T(s, a) * T'( a) for all s E S,a E A. Given a function Q' :SxA A - IR, there exists a reward function R', produced from R by S'-redistribution under T, such that Q' is the Q-function for π under I'' and r'.
Ambiguity refinement is a partial order, and some data sources are indeed incomparable. In conso- lation, observe that such incomparable ambiguity is complementary ambiguity, in that by com- bining the associated data sources, we reduce overall ambiguity about the latent reward.
Theorem 4.2. Given data sources X and Y, let (X,Y) denote the combined data source formed from X and Y. If X and Y are incomparable, then (X,Y) < X and (X,Y) < Y.
This perspective highlights promising directions for the design of reward learning data sources. In particular, this suggests developing reward learning algorithms for mixtures of data sources with complementary ambiguity. Unfortunately. most popular data sources actually appear to have similar kinds of ambiguity given one MDP. However, ambiguity could be reduced by incorporating data from multiple MDPs, along the lines of Amin et al. (017) and Cao et al. (021).
and(Cao
8

---

Under review as a conference paper at ICLR 2022
5 LIMITATIONS AND FUTURE WORK
Our results give an upper bound on the amount of information that can be extracted from a given data source. However, in practice, these bounds may not be reached. In particular, our results are for the limit of infinite data. But in practice data sets are finite and, when data collection is expensive, may be fairly small. An important direction for future work is to characterise how much information is contained in data sets of varying sizes and data sources. This would enable practitioners to determine the most sample efficient data source for a fixed data collection budget.
Furthermore, our results rely on the data being generated according to the process assumed by the reward learning algorithm. However, most popular approaches are poor fit for human data (Orsini et al.) 2021). For example, human demonstrations are rarely perfectly optimal or Boltzmann- rational. Moreover, there is often a trade-off between how informative a data source is and how easy it is for user to provide data. As an extreme example, user directly specifying the target reward function maximally informative - users could complete such a task correctly. We expect the maximum informativeness of data source to be useful metric, but it should be considered alongside the cost and tractability of collecting different kinds data.
CONCLUSION
Substantial effort has been invested to develop reward learning algorithms for a variety of data sources. A fundamental question to ask is how effective are these algorithms relative an optimal algorithm for that data source? Our results characterise the information available in different data sources, enabling algorithms to be compared to this theoretical upper bound.
Moreover, our framework enables direct comparisons between different data sources. We find that some data sources strictly less informative than others, such noiseless preference comparisons vs. return labels. By contrast, others are incomparable and have complementary ambiguity, such as Q-values (invariant to S"-redistribution but not potential shaping) episode return Gg (invariant to some potential shaping, but not to S'-redistribution).
In particular, have characterised the invariances of various reward-related objects to transfor- mations such as potential shaping. We have shown that these objects form a partial order under ambiguity refinement. These results, summarised in figure D allow data sources generated from these objects. While practitioners could simply collect data from the least ambiguous source, this might be very expensive. Our framework also identifies the ambiguity tolerance of downstream applications (such as policy optimisation) that need to compute these ob- jects. This enables practitioners to identify reward learning data sources with low ambiguity in the areas their application is sensitive to, enabling higher performance without unnecessary costs.
predict the ambiguity of
ETHICS STATEMENT
is important that AI systems are aligned with the interests of users and other stakeholders. In open- ended problems, directly specifying how the Al system should behave is intractable. Prior work has identified reward learning as an essential building block for AI systems that can cooperate with humans [Dafoe al.) 2020 $4.1.3), especially for powerful AI systems (Bostrom) 2014 chapter 12). We hope that our work provides greater clarity on both the limits and potential of various reward learning data sources. However, given the importance of the domain, we should stress that our work provides only one useful angle by which to evaluate data sources. In particular, we do not consider sample efficiency, robustness misspecification, or the cost of data collection.
Moreover, even if theoretically optimal and practically robust reward learning algorithm were to be developed, there would still remain important normative questions. In particular, what kinds of values we are aligning the Al system to stated preferences, revealed preferences, instructions, or something else (Gabriel, 2020)? Additionally, it is important that all relevant stakeholders are able to provide input into the system. This may constrain the kinds of data we can collect. For example, while only task experts might be able to provide demonstrations, a wider variety of stakeholders might be able to provide preference comparisons. While thorough evaluation of these consid- erations are beyond the scope of this paper, we would encourage practitioners to evaluate reward learning data sources holistically, including but not wholly relying on our results.

---

Under review as a conference paper at ICLR 2022
REPRODUCIBILITY STATEMENT
Our results are all theoretical in nature. We introduce notation and other background material in sections 1.2 and 2 Necessary assumptions are listed there and in each theorem statement. Proofs for some fundamental lemmas are provided in appendix A and all other proofs are in appendix
REFERENCES
Nematollah Ab Azar, Aref Shahmansoorian, and Mohsen Davoudi. From inverse optimal control to inverse reinforcement learning: A historical review. Annual Reviews in Control, 50:1 19-138, 2020.
Pieter Abbeel and Andrew Ng. Apprenticeship learning via inverse reinforcement learning. In Proceedings the twenty-first international conference Machine learning, pp. 2004.
Pieter Abbeel, Adam Coates, and Andrew Y Ng. Autonomous helicopter acrobatics through ap- prenticeship learning. The International Journal of Robotics Research, 29(13):1608-1639, 2010.
Victor Aguirregabiria. Nonparametric identification of behavioral responses to counterfactual policy interventions in dynamic discrete decision processes. Economics Letters, 87(3):393-398, 2005.
Victor Aguirregabiria and Pedro Mira. Dynamic discrete choice structural models: A survey. Journal of Econometrics, 156(1):3867, 2010.
Martin Aigner. Combinatorial Theory. Die Grundlehren der mathematischen Wissenschaften se- ries of comprehensive studies in mathematics. Springer New York, 1979. ISBN 9783540903765..
Riad Akrour, Mare Schoenauer; and Michèle Sebag. April: Active preference learning-based rein- forcement learning. In Joint European Conference on Machine Learning and Knowledge Discov- ery in Databases, pp. 116-131. Springer, 2012.
Kareem Amin, Nan Jiang, and Satinder Singh. Repeated inverse reinforcement learning. In NIPS, 2017.
Dario Amodei, Chris Olah, Jacob Steinhardt, Paul Christiano, John Schulman, and Dan Mané. Con- crete problems in ai safety. arXiv preprint arXiv: 160600655, 2016.
Peter Arcidiacono and Robert A Miller. Identifying dynamic discrete choice models off short panels. Journal of Econometrics, 215(2):473-48) 2020.
Stuart Armstrong and Sören Mindermann. Occam's 's razor is insufficient to infer the preferences of irrational agents. arXiv preprint 1eX.v:1712.088/11 2017.
Erdem Bryik, Dylan P Losey, Malayandi Palan, Nicholas C Landolfi, Gleb Shevchuk, and Dorsa Sadigh. Learning reward functions from diverse sources human feedback: Optimally integrat- ing demonstrations and preferences. arXiv preprint arXiv:2006. 14091, 2020.
Nick Bostrom. Superintelligence: Paths, Dangers, Strategies. Oxford University Press, 2014. ISBN 978019967811 12.
Haoyang Cao, Samuel N. Cohen, and Lukasz Szpruch. Identifiability in inverse reinforcement learn- ing, 2021.
Paul Christiano, Jan Leike, Tom B Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep reinforcement learning from human preferences. arXiv preprint arXiv: 1706.0377,,, 2017.
Anne GE Collins and Amitai Shenhav. Advances in modeling learning and decision decision-making in neuroscience. Neurpsychoophamaccooyy pp. 1-15, 2021.
Will Dabney, Mark Rowland, Marc G Bellemare, and Rémi Munos. Distributional reinforcement learning with quantile regression. Thirty-Secooe AAAI Conference on Artificial Intelligence, 2018.
10

---

Under review as a conference paper at ICLR 2022
Allan Dafoe, Edward Hughes, Yoram Bachrach, Tantum Collins, Kevin R. McKee, Joel Z. Leibo, Kate Larson, and Thore Graepel. Open problems in cooperative ai, 2020.
Daniel C Dennett. The intentional stance. MIT press, 1989.
Gabriel Amolac,mood, Daniel Mankowitz, and Todd Hester. Challenges of real-world reinforcement learning, arXiv preprint arXiv:1904. 12901, 2019.
Krishnamurthy Dvijotham and Emanuel Todorov. Inverse optimal control with linearly-solvable mdps. In ICML, 2010.
lason Gabriel. Artificial intelligence, values, and alignment. Minds and Machines, 30(3):411 1-477, 2020.
Tuomas Haarnoja, Haoran Tang, Pieter Abbeel, and Sergey Levine. Reinforcement learning with deep energy-based policies. In International Conference on Machine Learning, pp. 1352-1361. PMLR, 2017.
Andrew Howes, Richard L Lewis, and Satinder Singh. Utility maximization and bounds on human information processing. Topics in cognitive science, 6(2): 203, 2014.
Borja Ibarz, Jan Leike, Tobias Pohlen, Geoffrey Irving, Shane Legg, and Dario Amodei. Reward learning from human preferences and demonstrations in atari. arXiv preprint arXiv:1811.06521, 2018.
Hong Jun Jeon, Smitha Milli, and Anca Dragan. Reward-rational (implicit) choice: A unifying formalism for reward learning. In NeurIPS, volume 33, pp. 4415-4426, 2020.
Kuno Kim, Shivam Garg, Kirankumar Shiragur, and Stefano Ermon. Reward identification in in- verse reinforcement learning. International Conference on Machine Learning, pp. 5505-5505. PMLR, 2021.
Pallavi Koppol, Henny Admoni, and Reid Simmons. Iterative interactive reward learning. Par- ticipatory Approaches to Machine Learning Workshop at ICML 2020, 2020.
Jan Leike, David Krueger, Tom Everitt, Miljan Martic, Vishal Maini, and Shane Legg. Scalable agent alignment via reward modeling: a research direction. arXiv preprint arXiv:1811.0799 2018.
Arthur Lewbel. The identification zoo: Meanings of identification in econometrics. Journal of Economic Literature, 57(4):835-903, 2019.
Charles F Manski. Identification problems in the social sciences. Harvard University Press, 1995.
Charles F Manski. Purtial identification of probability distributions. Springer Science & Business Media, 2003.
Tetsuro Morimura, Masashi Sugiyama, Hisashi Kashima, Hirotaka Hachiya, and Toshiyuki Tanaka. Nonparametric return distribution approximation for reinforcement learning. ICMI., 2010a.
Tetsuro Morimura, Masashi Sugiyama, Hisashi Kashima, Hirotaka Hachiya, and Toshiyuki Tanaka. Parametric return density estimation for reinforcement learning. Proceedings of the Twenty- Sixth Conference on Uncertainty in Artificial Intelligence, pp. 368-375, 2010b.
Andrew Y Ng and Staart J Russell. Algorithms for inverse reinforcement learning. In 17th Interna- tional Conference on Machine Learning, volume 1, 663-670, 2000.
Andrew Y. Ng, Daishi Harada, and Stuart Russell. Policy invariance under reward transformations: theory and application to reward shaping. NIPS, 1999.
Manu Orsini, Anton Raichuk, Léonard Hussenot, Damien Vincent, Robert Dadashi, Sertan Girgin, Matthieu Geist, Olivier Bachem. Olivier Pietquin, and Marcin Andrychowicz. What matters for adversarial imitation learning?, 2021.
11

---

Under review as a conference paper at ICLR 2022
Malayandi Palan, Nicholas C Landolfi, Gleb Shevchuk, and Dorsa Sadigh. Learning reward func- tions by integrating human demonstrations and preferences. arXiv preprint arXiv:1906 100.09990 2019.
Joshua Peterson, David D Bourgin, Mayank Agrawal, Daniel Reichman, and Thomas L Grif- fiths. Using large-scale experiments and machine learning to discover theories of human decision- making. Science, 372(6547):1209-1222
2021.
Deepak Ramachandran and Eyal Amir. Bayesian inverse reinforcement learning. In IJCAI, vol- ume 7, pp. 2586-2591, 2007.
Constantin A Rothkopf and Christos Dimitrakakis. Preference elicitation and inverse reinforce- ment learning. In Joint European conference on machine learning and knowledge discovery in databases, pp. 34 48. Springer, 2011.
Stuart Russell. Learning agents for uncertain environments. Proceedings of the eleventh annual conference on Computational learning theory, pp. 101-103, 1998.
Stwart Russell and Peter Norvig. Artificial intelligence: modern approach. Prentice Hall, third edition, 2009.
John Rust. Structural estimation of markov decision processes. Handbook of econometrics, 4: 3081-3143, 1994.
Paul JH Schoemaker. The expected utility model: Its variants, purposes, evidence and limitations. Journal of economic literature, pp. 529-563, 1982.
Rohin Shah, Noah Gundotra, Pieter Abbeel, and Anca Dragan. than assuming. human biases for reward inference. In International Conference on Machine Learning, pp. 5670-5679. PMLR, 2019.
On the feasibility of learning, rather
Avi Singh, Larry Yang. Kristian Hartikainen, Chelsea Finn, and Sergey Levine. End-to-end robotic reinforcement learning without reward engineering. arXiv preprint
2019.
Sorawoot Srisuma. Identification in discrete markov decision models. Econometric Theory, 31(3): 521-538, 2015.
Nisan Stiennon, Long Ouyang, Jeff Wu, Daniel M Ziegler, Ryan Lowe, Chelsea Voss, Alec Radford, Dario Amodei, and Paul Christiano. Learning to summarize from human feedback. arXiv preprint arXiv:2009.01333 2020.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Elie Tamer. Partial identification in econometrics. Annu. Rev. Econ., 20)::177-19,, 2010.
Hsiao- Yu Tung, Adam W Harley, Liang- Huang, and Katerina Fragkiadaki. Reward learning from narrated demonstrations. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 7004-7013, 2018.
Eric Wiewiora, Garrison W Cottrell, and Charles Elkan. Principled methods for advising reinforce- ment learning agents. In Proceedings of the 20th International Conference on Machine Learning (ICML-03), pp. 792-799, 2003.
Christian Wirth, Riad Akrour, Gerhard Neumann, Johanees Fürnkranz, al. survey of preference- based reinforcement learning methods. Journal of Machine Learning Research, 18(136):1-46, 2017.
Brian Ziebart, Andrew Maas, J Andrew Bagnell, Anind K Dey, et al. Maximum entropy inverse reinforcement learning. In Aaai, volume 8, pp. 1433-1438. Chicago, IL. USA, 2008
Brian D Ziebart, J Andrew Bagnell, and Anind K Dey. Modeling interaction via the principle of maximum causal entropy. In JCML, 2010.
12

---

Under review as a conference paper at ICLR 2022
A PROPERTIES OF FUNDAMENTAL REWARD TRANSFORMATIONS
We begin with some supporting results concerning the basic reward transformations, used in sec- tion 3 to characterise the invariances of various objects derived from the reward function.
The following result captures how potential shaping affects various reward-related functions.
Lemma A.1. Consider M and M', two MDPs differing only in their reward functions, respectively
R and R'. Denote the return, Q- value, and policy evaluation functions of M' by G', Q Va, and
J. If R' is produced by potential shaping of with a potential function 4, then:
(1) for trajectory fragment (s0. o0, 51). G)(C) = G(() + 7 - ((s));
(2) for trajectory & = (s0,00..... do....). G'()) G(E) (so):
(3) for state sE S, and action a E A, (s, = Qn(s, a) -ss));
(4) for state S. (s) Vs(s) (s); and
(5) for policy n, (TT (TT) - - + (Sn)]
Proof. (1) is given by straightforward induction on the length of Ç. For (2), take the limit as the length of prefix goes to infinity, whereupon >" goes to zero (7 by definition, and (s,,) is bounded since its domain is fimite). (3) and (4) were proved for optimal policies by [g et al.
(1999), and they also observed that the extension to arbitrary policies is straightforward (following immediately from (2), for example). (5) is immediate from (4).
The following results explain how k-initial potential shaping and linear scaling of R correspond to affine transformations of G.
Lemma A.2. Let (S, Mo. R.,) be an MDP, R' reward function, and k E R constant. Then we have that G'(E) = k all possible and initial trajectories &, if and only if R' is produced from R by k-initial potential shaping and mask of unreachable transitions.
Proof. The converse follows from Lemma A.1 and that varying the reward for unreachable transi- tions does not affect the return of any possible, initial trajectories, by definition.
In the forward direction, consider an arbitrary reachable state s E S. Let ( be a possible, initial, length n trajectory fragment ending in s (at least one exists, since s is reachable). Let & be some possible trajectory starting s, and let Aç, G(E.) GE Let + &, denote the concatenation of ( and f.. Since Ç + E. is an initial trajectory, we have by assumption G + - G" + {.) k. Moreover, note that G(Ç {.)) = G(() + 7 "(((), (and likewise for G'), by definition of return. Then (recalling that we have defined 7 > 0).
4e. G(G,) (5,)))
G(ş + {.) G(C)
G'(C + -
7m
7
k: k- G'(()
7
Therefore de, is independent of f., except for possible dependence on Es's starting state s. We associate unique P(s) = Ae, with each reachable s.
Now consider reachable transition (s, a. s'). Further straightforward algebraic manipulation shows that R' R'(ssa, a, 5') = R(s, a, 5¹) + 7- P(s') PPs)), Moreover, from the definition of terminal states we must have that P(s) Dg.
for terminal 8, and by assumption we have that P(s) De. = 1: if is initial. So R' is given by k-initial potential shaping of R with ((s) P(s) for reachable transitions. Any variation in reward for unreachable transitions can be accounted for by the mask.
Lemma A.3. Let (S,A, ng. (.o.R..)) R, be an MDP, R' reward function, and e R constant. Then (E) = G(E) for all possible initial trajectories e. if and only if R! is produced R by zero- initial potential shaping, linear scaling by a factor of e, and a mask of all unreachable transitions.
13

---

Under review as a conference paper at ICLR 2022
have that O-initial potential shaping leaves G unchanged. Likewise, a mask of unreachable transitions does not affect G for possible initial trajectories. Moreover, is straightforward that linear scaling of R by factor of leads to linear scaling of G by the same factor of c. Hence the converse is established.
Proof. From Lemma A.1
For the forward direction, consider arbitrary reachable state S. Let &. be some possible trajectory starting in 8, and let Ag. = c G(E.) - (E,).. Let be possible, initial, length n trajectory fragment ending in s. Since the concatenation < is possible initial trajectory, have that
C.(+ = c. G(S
G'()) = c. (G(() + +
G'(C) c. +(")+ G(S.) G'(E)))
4 -c
7Mt
Therefore 4g, is independent of &,, except for possible dependence on & 's starting state s. We associate unique P(s) Aç, with each reachable
Now consider reachable transition (s, a, s'). Further straightforward algebraic manipulation shows that (s, a, 8') c- R(s, a, s') + P(s') P(s). Moreover, from the definition of terminal states
we must have that P(s) A = O for terminal 8, and by assumption we have that P(s) = 0 if
initial. Thus R' is given by first potential shaping R with ((s) 1 Pss), and then linear scaling with c.
14

---

Under review as a conference paper at ICLR 2022
B PROOFS
We provide proof' for the theoretical results presented in the main paper.
B. PROOFS FOR SECTION RESULTS NOT CONCERNING OPTIMAL POLICIES
We provide proofs for some of the results in section 3.1 The proofs relating to optimal policies (theorems 3.3 and 3.5) are given in the next subsection (appendix [.2).
Theorem 3.1. Given MDP and a policy n, the Q-function for T, Qu. determines R up to S'- redistribution. The optimal Q-function, Q., has precisely the same invariances.
Proof. QT satisfies the Bellman equation for all 8 E S, A: (s, a) ((s))(aa)) (((,) R(s,,, +1 Q+()
This equation can rewritten as Egiar(s.a) [R(s,a,
(s) (s)r(s (Q"
From this, we can see that Q" is invariant to S s"-redistribution of R, and no other transformations. Q. = Qr,, where m. any optimal policy derived from Q., so the invariances of optimal Q-function follow as a special case.
O
Theorem 3.2. Given an MDP, an inverse temperature parameter 3, and base policy no the Boltzmann policy 33 determines R up S'-redistribution and potential shaping, The Boltzmann- rational policy, w... and the Maximum Entropy policy, Tg, have precisely the same invariances.
Proof. By equation 2 T can be derived from Amo- Axo itself can be derived from Quo given To (by equation 11. A (s. a) = Qra (s, a) - E Ao)oo(s) Q (s, A) Thus T To is invariant to S'- redistribution by Theorem 3.1 Moreover, by Lemma A. potential shaping causes a state-dependent shift of Qx. This shift does not affect A.o. Therefore z is also invariant to potential shaping.
Conversely, recall (or see Lemma B. below) that the softmax function is invariant only constant shifts. This means that T is invariant to all and only those transformations of Rt that produce state- dependent shifts in Q². Let B : S - IR, and suppose R and R' are two reward functions such that the corresponding Q-functions (for T) satisfy ((ss.a) a) Q(s,a) () + B(s). Then
[R[ a, S')] E[Q'(s, a) - 7 A a')]
E[Q(ss,) a) B(s) - m ,') B(S)))
E[B(s) -
where the expectations are over 5' Ts, a). Now set (sx) - B(s,, and we can see that the difference between R and R' is described by potential shaping and s'-reiistribution.
The Boltzmann- rationall policy determines its own base policy (it is enough to determine the optimal Q-function up to a state-dependent shift), and the Maximum Entropy policy is its own base policy, so the invariances these policies follow as a special case of this result.
Lemma B.1. Consider two functions X R and g X defined on finite X. Then g is constant if. for all x E X,
(xp(f(x)+
exp(f(x))
Lxex exp(f(x') g(x'))
Lxex exp(f(x'))
Proof. This an elementary property the softmax function. It can be seen as follows:
exp(.(<x) + g(x))
Emex exp(f(a') + a(x'))
exp(f(x))
Evex exp(s(x'))
2xxexeepi exp(f + +g(x"))
g(x) In
Erex exp(J(x'))
which is constant in x. (The converse is true, but we do not make use of it, omit proof.) n
15

---

Under review as a conference paper at ICLR 2022
Theorem 3.4. Given MDP, an inverse temperature parameter B. and base policy no. the dis- tribution of trajectories induced by the Boltzmann policy "B no from all initial states determines R up to S d'-reiistribution, potential shaping, and mask of unreachable transitions. The distributions of trajectories induced by the Boltzmann-rations raational policy, Th.. and the Maximum Entropy policy, Tg, from all initial states, have precisely the same invariances.
Proof. That the distribution is invariant to S'-redistribution and potential shaping follows from The- 3.2 The distribution also invariant to changes in the reward for transitions out of unreachable states, since these rewards cannot affect the policy for reachable states. As a result the distribution additionally invariant to a mask of unreachable transitions.
The trajectory distribution can be factored into the separate distributions T g (s) E A(A) for each reachable state by conditioning on a supported prefix trajectory fragment that leads to s and marginalising over subsequent states and actions. Via similar argument to the proof of Theo- rem 3.2 the distribution determines the reward function for transitions (out of these reachable states) up to potential shaping and transformations and S' s'-rriistribution (as they affect reachable states),
As for Theorem 3.2 the invariances for the Boltzmann-rational policy and the Maximum Entropy policy arise as special cases.
B.2 PROOFS FOR SECTION 3.1 RESULTS CONCERNING OPTIMAL POLICIES
Our results concerning the invariance of optimal policies and their trajectories follow from the fol- lowing general result:
Lemma B.2. Given MDP M, suppose have access to the of optimal actions for each state in a subset of states 6 C S. Assume that this subset is closed under optimal actions given the transition dynamics of M (that is, taking optimal actions from states in G never leads to states outside of G). Let D be the set of functions O defined on S such that (s)) = arg max A, (8,880 a) for all s e 6 (but O unconstrained for states outside G). Then these optimal action sets determine R up to optimality-presenee
transformations with O E D.
Proof. Suppose R' is obtained from M's reward via an optimality-ppeservinn transformation with some O E D. Let V be the corresponding value-bounding function, that is, a function V : S - IR satisfying, for all s E S and a E A.
Es-r(ss [R'ss, S') + y. U(S)] < (s)s)
(3)
with equality if and only if (s). Since (ss) is non-empty (by definition), we have for all s S
T (s) max (a as, 7 (SS)))
This recursive condition on is the Bellman optimality equation for the unique optimal value func- tion, V.. of the MDP with transformed reward R'. Therefore, (s)) (s'(s) for all S, and we can rewrite equation as
[1' Es [I' a, + V'(S') < V.(s),
(4)
with equality only for a O(s).
Now, consider a state s E G. By assumption, for this s, ((s) = arg A. As a). Then for this state, the actions that attain the optimal value bound in equation 44 are these same optimal actions. Therefore, R' induces the same sets of optimal actions from states in S.
Conversely, consider second MDP M', differing from M only in its reward function, R'. Assume the set of optimal actions in states in 6 agrees with the optimal actions in M for those states. Let V'' and A', denote the optimal value and advantage functions for M'. The Bellman optimality equation for M' ensures that, for S S,
(((s) max (Es-~T(saa) [R'(s, [R',,, S') + V((S')) a
(5)
= with the maximum attained precisely by the actions a E arg max A (AL a)). Setting O(s)
arg max (A, (A' a)), equation (5) can be rewritten
Eg [R' [R'' (s, 5') + 7 V.(S)) & V.(s)
(6)
16

---

Under review as a conference paper at ICLR 2022
for all S and A, with equality if and only if a O(s).
Now, for s G. we have arg a a)) = arg m (s, a)), because M and M' have matching sets of optimal actions for these states (by assumption). Then equation (6) shows that R' is produced from R by an ceimallty-preservvee transformation with ((s) = arg max A (A,(s, a)) (and V (s))
We are now in position to prove the results from the main text:
Theorem 3.3. Given an MDP, let O(s) arg A. a). A maximally supportive optimal policy determines I up to aptimality-preservvie trunsformations with O
Proof. An arbitrary maximally supportive optimal policy determines the set of optimal actions from all states in the MDP. Its invariances follow special case of Lemma B.2 with G S.
Theorem 3.5. Given an MDP, consider the distribution of trajectories induced by a maximally supportive optimal policy. Let G be the set of states in supported trajectories. Let D be the set of functions O defined on S such that Oss) arg A. a) for all G. The induced distribution of trajectories determines up to optimality-preserinng transformations with O E D.
Proof. The distribution of trajectories can be factored into separate distributions T (s) E A(A) for each state & (in manner similar to Theorem 3.4, as proved above). These individual distributions determine the set of optimal actions within those states.
Noting that & is clearly closed under optimal actions in the MPD since all optimal actions are supported by the policy, the invariance result follows from Lemma B.2
B.3 PROOFS FOR SECTION 3.2 RESULTS
Theorem 3.6. Given MDP, the return function restricted possible trajectory fragments, GG. determines R up to a mask of impossible transitions;
Proof. The result is immediate, since the restricted domain still includes all possible transitions (as length one trajectory fragments with return equal to the reward of the transition), and no fragments with impossible transitions.
L
Theorem 3.7. Given an MDP, the return function restricted to possible and initial trajectories, G determines R up to zero-initial potential shaping and mask of unreachable transitions.
Proof. The result follows from Lemma A.2 with k = 0.
Theorem 3.8. Given an MDP, the distribution of comparisons of possible trajectory fragments,, SS determines R up to a mask of impossible transitions.
Proof. Since 2 can be derived from Gç. it is invariant to mask of impossible transitions by Theorem 3.6 Conversely, = determines R for all possible transitions. This is because R(s, a, s') is encoded in the Boltzmann distribution of comparisons between the length zero trajectory fragment So (s) and the length one trajectory fragment Çi (8, a, s'), and can recovered as follows:
exp(BG(C1))
exp(BR(ss, a, s'))
IP(Co 23 (1) exp(3G((c)) + exp(3G(Gi)
exp(3 +
PP(Co 25 G1) 11
R(s, a.a 8') = 1 P(Go 2 <i)
Therefore <8 is invariant to precisely mask of impossible transitions.
17

---

Under review as a conference paper at ICLR 2022
Theorem 399. Given MDP, the distribution of comparisons of possible and initial trajectories, S determines R up to k-initial potential shaping and mask of unreachable transitions.
Proof. Note that as > can be derived from Gg. by Theorem 3.7 = invariant 0-initial potential shaping and mask of unreachable transitions. It is additionally invariant to k-initial potential shaping for arbitrary constants E I, and no other transformations: Gg can be recovered from < up to a constant (we can compare all possible initial trajectories to an arbitrary reference trajectory and recover their relative return using similar manipulation as above, but can't determine the return of the reference trajectory). From there, the precise invariance follows from Lemma A.2
Theorem 3.10. We have the following bounds on the invariances of the noiseless order of possible trajectory fragments, S.. In all MDPs:
(1) < is invariant to positive linear scaling and mask of impossible transitions; and
(2) < is not invariant to transformations other than zero-preserving monotonic transforma- tions masks of impossible transitions.
Moreover, there exist MDPs attaining each of these bounds.
Proof. For (1), positive linear scaling of reward by a constant leads to the same scaling of the return of each trajectory fragment, and this always preserves the relation =f. since for any > 0. G((1) e G((2) G(G1) G((2) for all pairs of trajectory fragments Ç1, Moreover, I inherits invariance to a mask of impossible transitions from Gş (Theorem (.6).
For (2), let R' be produced from R via some transformation that is neither mask of impossi- ble transitions nor a zero-preser pero-preserving monotonic transformation. It must be that either R' fails to preserve the ordinal comparison of two possible transitions, or that it fails preserve the set of zero-reward possible transitions, compared to R. In the first case, consider two possible transitions whose rewards are not preserved, Ij and æ2. Without loss of generality suppose R(z1) R(z2) but (z1) > (x2). This corresponds to change If's comparison of the length one trajec- tories formed from and Z2, namely æ1 <f from true to false. Similarly. in the second case, the comparisons between the transition whose reward became or ceased to be zero and length one trajectory (with return 0) will have changed. Therefore, =5 not invariant to such transformations.
The bound (1) is attained by the following MDP invariant precisely to positive linear scaling and mask of impossible transitions. Let {s}, A (a1,a2), R(s, 01, 1, and R(s, 022 8) 1 + 7. Since R(s, 022 s) R(s, ((s,a1,s) 7H[s, 01. s). the corresponding order relation will contain both (s, 022 8) =S (s, a1, 8,,,,, s) and (s, a1, 8,,,,,,,5 s) s) =S (s, 8). This property requires that R(s, (1,8) = (1 ++7) . R(ss (Rss,0,,8) 8), which is preserved only by linear scaling of R. (Non-positive linear scaling already ruled out by (2)).
The bound (2) is attained by the following MDP invariant to arbitrary zero-preserving monotonic transformations. Let S {51, A = {a}, with possible transitions ($1, 82) and (s2 a, $2), and R(s1, a, $2) > R(s2. a, $2) = 0. Any zero pero-preserving monotonic transformation of R preserves the ordering of all possible trajectory fragments, namely that all nonempty trajectories starting in $1 have positive return and all other possible trajectories have zero return.
Theorem 3.11. Given an MDP, the noiseless order of possible and initial trajectories, <S, is invari- ant k-initial potential shaping, positive linear scaling, and mask of unreachable transitions.
Proof. The pairwise Boltzmann distributions of 5 can be used to derive the noiseless comparisons of 55 Therefore, = is invariant to k-initial potential shaping and a mask of unreachable transitions.
That <5 is also invariant to positive linear scaling follows from a similar argument as for the first bound in Theorem 3.10 proved above.
18

---

Under review as a conference paper at ICLR 2022
B.4 PROOFS FOR SECTION 3.3 RESULTS
Theorem 3.12. Given an MDP, let O(s) arg A a). Then the set of optimal policies determines R up to optimllty-preservingg transformations with O.
Proof. The set of all optimal policies determines a maximally supportive policy, for example by constructing a policy that supports all actions supported by any policy in the set. Likewise, a maxi- mally supportive policy determines the set of optimal policies, namely the set of all policies whose support is a subset the maximally supportive policy. Therefore, these objects share precisely the same invariances.
B.5 PROOFS FOR SECTION 4 RESULTS
Theorem 4.1. Consider an MDP (S.A, A, Ho. R. 7). a poliey т, and alternative transition dynamics I' with T(s, a) * ('ss a) for all E S, A. Given a function Q' SSx I. there exists reward function Rt, produced from R by S' S'-redixtribution under such that Q' is the Q-function for a under R' and T'.
Proof. Per definition 2.3 that R' is produced from R. by S s--rriistributton under requires, for all 8 & and a E A,
E (g) (8' a, S`)] ((. R(s S')]
Per equation
1.. that Q' the Q-function for a under Rt and 7' requires, for all & E and a A,
Q'(s,a)= (3
or, equivalently,
[s as, = (s) - -BS (Q's",,
(8)
For brevity, denote the right-hand sides of equations and 8 as R(s, a) and ((s,a) respectively.
Let and a E A. By assumption, 7'(s, a) * T(s a). Therefore, for at least two s', denoted o and s/2, we have (s a) < 7(8i|s,0 a) and s) > 7(8215, a). For the remaining s', set R(s,a, a, 8) = This reduces equations 7 and (8) to the following:
T(si|s,0) a) (((s,a,5 + Ts32ss, H'(s, a, s/) R(s,a)
()) (s, s1) (.6,,,))) R'(s, 82) ((s,a)
This system has solution as its determinant is 7 (*6/1s, r 7611,, a) -
('81188,) > 0.
Theorem 4.2. Given data sources X and Y, let (X, Y) denote the combined data source formed from X and Y. If X and Y are incomparable, then (X, Y) < X and (X,Y) < Y.
Proof. Transformations that preserve (X, Y) necessarily preserve X, therefore (X, < X. But since X and Y are incomparable, there is some transformation that preserves X and not Y. This transformation does not preserve (X, Y). Therefore, (X, Y) < X. Similarly, (X,Y) Y
We note that the above result is also elementary consequence of the lattice structure the partial order of partition refinement (Aigner 1979 $1.2.B), since the combined data source corresponds to the meet of the original data sources.
19

---

Under review as a conference paper at ICLR 2022
C
OTHER SPACES OF REWARD FUNCTIONS
Hitherto we have assumed reward functions are members of SxAxS - R. That is, they are deterministic functions of transitions, depending on the state, action and the successor state. this appendix, we discuss several alternative spaces of reward functions, and their implications for the invariance properties of various objects derived from the reward function.
C.I
REWARD FUNCTIONS
is common in both reinforcement learning and reward learning to consider less expressive spaces of reward functions. In particular, the domain of the reward function is often restricted to S or S A. When modelling a task, the choice of reward function domain is usually a formality: An MDP taking full advantage of the domain S Sx.xx Axx has "equivalent' MDP with restricted domain, and some added auxiliary states (Russell & Norvig, 2009 $17). Conversely, reward functions with restricted domains can be viewed as a special case functions from S Axx where the functions are constant in the final argument(s). Restricting the domain can be an appealing simplification when modelling a task, hence the popularity of these formulations.
When modelling a data source, this equivalence may not apply: We may not have access to data regarding auxiliary states, and so assuming a restricted domain effectively assumes the latent reward is indeed constant with respect to the successor state (and possibly the action) of each transition. This assumption may or may not be warranted.
If restricted domain of S or SxA is preferred, then our invariance results can be adapted in straightforward manner. In general, since we are effectively considering a subspace of candidate reward functions for transformations, ambiguity can only decrease. In particular, these restrictions have two main consequences.
Firstly, the reward function transformation of S'-redistributiio vanishes to the identity transforma- tion, since it allows variation only in the successor state argument of the reward function, which is now impossible. This reduces the effective ambiguity of the Q-function and all derivative ob- jects. Notably, the Q-function uniquely identifies the reward function, and Boltzmann policies have the same invariances Boltzmann comparisons between trajectories. Restricting the domain to S means the (state) value function for an arbitrary known policy also uniquely identifies the reward function, but doesn't otherwise alter the invariances have explored.
Secondly, for most MDPs, the available potential shaping transformations are restricted, but not climinated. The function added in a potential shaping transformation (? (ss) (s)) nominally depends on the successor state of the transition. Some transformed reward functions may rely on this dependence, falling outside of the restricted domain. However, some non-zero transformations will usually remain. For example, in discounted MDP without terminal states, a non-zero constant potential function (ss) le does not effectively depend on s, and the reward transformation of (7- 1) A to reward function does not introduce a dependence on s'. In general, the set of remaining potential shaping transformations will depend on the network structure of the MDP. At the extreme, in deterministic MDP with state-action rewards, all potential shaping transformations are permitted, since a dependence on s' can be satisfied by a.
adding 7 <0x')= +(s)
C.2 STOCHASTIC REWARD FUNCTIONS
Certain tasks are naturally modelled as providing rewards drawn stochastically from some distribu- tion upon each transition. An even more expressive space of reward functions than consider is the space of transition-condiiiona reward distributions Bl Identifying the reward function in this case is more challenging in general because the latent parameter contains a full distribution of information for each input, rather than a single point. In the spirit of this paper, we sketch a characterisation of this additional ambiguity.
A deterministic reward function can be viewed as the conditional expectation of a reward distribution function. Taking the expectation of the reward distribution for each transition introduces invariance,
Of course, it's also possible to consider reward to be distributed conditionally only the state or state- action components of transition, and not the full transition.
20

---

Under review as a conference paper at ICLR 2022
since the expectation operation is not injective (except in certain restricted cases such for para- metric families of distributions that can be parametrised by their mean). The invariance introduced is akin to 5 rr-rriittibbttonn but with expectation over the support of the reward distribution rather than the successor state of each transition.
In the extension of the RL formalism account for stochastic rewards, this expectation is effectively the first step in the derivation of each the objects we have studied. Therefore, all of these objects inherit this new invariance.
As a consequence, all data sources are effectively more ambiguous with respect to this new latent parameter. For example, if optimal comparisons between trajectories understood be per- formed based on the pairwise comparison of the expected return of each individual trajectory, then these comparisons are also invariant transformations of the reward distributions that preserve their means.
Fortunately, much of reinforcement learning also focuses on expected return and reward appli- cation. Accordingly, most downstream tasks are tolerant to any ambiguity in the exact distribution of stochastic rewards, beyond identifying the mean. Since this the same kind ambiguity that introduced by considering the latent parameter of reward learning as conditional distribution rather than deterministic function, our results are still informative for these situations.
C.3 FURTHER SPACES AND FUTURE WORK
For certain applications. including risk-sensitive RL where non-mean objectives are pur- sued (Morimura et al.) 2010a b Dabney et al., (018), the distribution of stochastic rewards can be consequential. Moreover, the introduction of stochastic rewards suggests considering data sources based on samples rather than expectations, such as a data source of trajectory comparisons based on sampled trajectory returns. Characterising the invariances of these objectives transformations of the reward distribution, and thereby their ambiguity tolerance, is left to future work.
In future extensions of this work handle continuous MDPs, there will be an opportumity to study the effect of restricting to various parametrised spaces of reward functions. For example, it is com- mon reinforcement learning and reward learning to study MDPs with reward functions that are linear in a feature vector associated with each transition. This kind of restriction may reduce the available reward transformations compared to those available to a non parametric reward function, in similar manner to restricting the domain of finite reward function as discussed above.
The relaxation of the Markovian assumption also introduces a broader space reward functions, and with it, new dimensions for transformations and invariance. As one example, related to potential shaping. the non-Maakovian additive transformations studied by WWewwora et al. (2003) will amount invariances of the optimal policy and other related objects.
21


Reviews:
[{"review_id": "lzvuhbHt3O", "reviewer": "Reviewer_zcgk", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "Some clarification questions:\n\n1. At the end of page 3, you mentioned the maximum entropy policy as the fixed point to $\\pi_\\beta = \\pi_{\\beta}^{\\pi_\\beta}$. Could you provide a definition of the maximum entropy policy and a proof sketch of why it is equivalent to the fixed point? In my understanding, a maximum entropy policy is the optimal policy result from solving policy optimization with an entropy regularization. It's not obvious to me why this solution will coincide with the fixed point defined above.\n\n2. X never appears in Definition 2.1. Do you mean to define $X = f(R) = f(t(R))$?\n\n3. I don't quite understand Definition 2.5, as the mathematical definition of $R'$ seems to be independent of $R$?\n\n4. 5 transformations are defined in section 2.1. Do they mean to form an exhaustive list? Or are there potentially other relevant transformations not discussed here? At a higher level, an object (e.g. expert demonstration) can induce a set of reward functions not described by any finite combination of the listed or potentially new transformations. So instead of characterizing the information flow through the reward function, why not directly analyze whether the information from a data source is sufficient for a downstream task? The answer to this question is completely independent of whether one chooses to learn a reward function or not. For example, the information captured in an expert demonstration is sufficient for the downstream task of optimal policy identification, and therefore it is well-known that despite the non-uniqueness of reward function in IRL, an optimal policy can be recovered regardless.\n\nMajor comments:\n\n**Discussion of related works can be significantly improved**: Most of the mentioned related works on reward learning are empirical in nature. It would be good to instead comprehensively survey the theoretical works that concern reward learning, since the paper itself is theoretical in nature.\n**Example application of the framework to improve upon/subsume prior results**: While the introduced reward-function centered information-theoretical framework provide a novel and unified view on the information-theoretical relationship between different objects, it alone is in my opinion not sufficient for publication. When you introduce a brand-new framework, it is also important that you make some convincing argument of why this framework is **useful**, in addition to being mathematically correct. A typical way of doing this is to show that using the new framework, one can easily recover/improve results from various prior works, and thus truly provide a unifying framework that subsumes prior literature.\n\nI would suggest the authors throw a majority of the theorems and transformations in section 2 and section 3 into the appendix, and use the space to set up one or two concrete examples on which the proposed framework can be useful in deriving new/matching upper and lower bounds.\n", "summary_of_the_paper": "This paper provides a theoretical framework to understand the relationship between data source/downstream tasks and reward functions. ", "summary_of_the_review": "1. Discussion of related works can be significantly improved.\n2. Example application of the framework to improve upon/subsume prior results.\n\nIn summary, I think this paper provides some novel insight in the problem of reward learning, but there can be substantial improvements to be made to make the paper significantly stronger. I would highly suggest the authors make the additional effort, and I know it's gonna be a lot of work. But it will potentially make it a spotlight/oral paper instead of a borderline.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "lCzVhHmE3O5", "reviewer": "Reviewer_iFN9", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "The paper is overall well written. The related work is clearly discussed, and this work is well-positioned in the literature. I enjoyed reading the paper. \n\nI haven’t checked the proofs of the theorems; however, the justifications provided before the theoretical claims are convincing. \n\nThe paper is a bit heavy in terminologies; however, it is inevitable due to the theoretical nature and rigor purpose of the paper. \n\nComments:\n1/ Re. the optimality-preserving transformations in Definition 2.5: is it possible to extend this definition to regularized MDP (e.g., entropy regularized MDP) objective as well? In that case, will the function \\Psi intuitively correspond to the regularized value function? \n\n2/ In Theorem 3.3, the S’-redistribution invariance and potential shaping invariances are not mentioned -- is this because they are less ambiguous than optimality-preserving transformations? \n\n3/ Re Theorem 3.10 for noiseless comparison based on the return: compared to other objects/theoretical statements, in this theorem, there isn't any “determines”-style claim. It is said that the precise monotonic invariances depend on the MDP. It would be good to have a clarification/discussion on this point. \n\n4/ All the results are derived for the finite MDP setting. A brief discussion on the applicability (or possible extension) of these claims to the continuous MDP setting would be helpful. \n", "summary_of_the_paper": "This is a theoretical work on understanding the intrinsic limits of various data sources that are used for reward learning in RL. In particular, by considering the infinite data limit of the data source, they study the level of reward ambiguity that can be obtained for a given downstream task. For example, for the expert behavior data source, they characterize the reward transformations that are determined by the optimal Q-function. Similar attempts have been made previously for specific data sources and specific planning algorithms (Ng & Russell, 2000). However, this work makes substantial contributions by conducting this study in a unified and rigorous way for variety data sources and downstream tasks. ", "summary_of_the_review": "This is a strong theoretical work; it makes a fundamental contribution to reinforcement learning literature. The reward functions are atomic to RL -- understanding the theoretical limits on how much information can be extracted from various data sources used for reward learning is important. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "bSeQrLlEgWb", "reviewer": "Reviewer_CDLH", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "This is an unconventional paper. The problem it's attacking is very fundamental and interesting: given reward functions that are \"close\" to each other under some measure (doesn't have to be rigorous and literal \"measures\"), what will they affect (in both the optimum of the MDP and the behavior of the downstream algorithms). What the paper does is to provide a set of measures and a set of claims that partially answer the questions, for the cases that are more or less low-hanging fruits. These claims are not particularly strong I would say, but they do provide some reasoning and implications on this very important topic. I would personally be more interestied in a particular, presumably not that general, setting (say, just tabular and linear program), with a clear and complete answer to that question. To this end I would wonder if the manuscript better fits a journal publication or a book chapter etc. But I'm more or less open for discussion in case this manuscript could provide some support for future studies.\n\nSide question: Can authors just compile one single pdf of 21 pages for the main submission per the policy?", "summary_of_the_paper": "This paper characterizes the partial identifiability of data sources and the reward function. Then it analyzes the impact of this measure on the optimum and the algorithms. Some implications are given.", "summary_of_the_review": "Better fits journal publication or book chapter?", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "1cL6fLwzyPR", "reviewer": "Reviewer_zVCQ", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 1, "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 is very hard to follow due to many non-standard notation and concepts. It is not even clear what the goal of the paper is. The notion of invariance is vague and confusing. I think the authors should have given more effort to setup the problem and goal more precisely and concisely, while using easier to understand notation and terminologies. ", "summary_of_the_paper": "The submission considers a reward learning problem when the reward function is not uniquely recoverable from the data, even in the infinite-data regime. ", "summary_of_the_review": "The paper is very hard to follow and I may not be able to assess the paper properly. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper formally studies the problem of partial identifiability when inferring a reward function from a given data source (e.g., expert demonstrations or trajectory preferences). To formally characterize this ambiguity in a data source, the paper proposes considering the infinite-limit data regime, which bounds the reward information recoverable from a source. Furthermore, this ambiguity is then studied in the context of different downstream tasks, as recovering an exact reward function may not be necessary for a given task. The paper is primarily theoretical, and the results provide a unified view of the problem of partial identifiability in reward learning for different sources and downstream tasks.

Overall, the reviewers acknowledged the importance of the problem setting and found the results promising. There is quite a bit of spread in the reviewers' final assessment of the paper with ratings 8, 8, 3, 3 (note: one of the reviewers with rating 3 has a low confidence). The authors' responses did help in discussions; however, a few of the concerns, as raised by reviewers, still remained. The key issues are related to the general accessibility of the paper and the lack of concrete examples to highlight the proposed theoretical framework. At the end of the discussions,  several reviewers (including those with an overall positive rating) shared concerns about the paper's accessibility.  With this, unfortunately, the paper stands as borderline. Nevertheless, this is exciting and potentially impactful work, and we encourage the authors to incorporate the reviewers' feedback when preparing a future revision of the paper.
Decision: Reject