Year: 2021

Abstract:
Designing reward functions for complex, real-world tasks is challenging. Reward learning lets one instead infer reward functions from data. However, multiple reward 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 identifiability of popular data sources, including demonstrations and trajectory preferences, under multiple standard sets of assumptions. We analyse the impact of this partial identifiability on downstream tasks such as policy optimisation, including under shifts in environment dynamics. We unify our 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.

text: Designing reward functions for complex, real-world tasks is challenging. Reward learning lets one instead infer reward functions from data. However, multiple reward 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 identifiability of popular data sources, including demonstrations and trajectory preferences, under multiple standard sets of assumptions. We analyse the impact of this partial identifiability on downstream tasks such as policy optimisation, including under shifts in environment dynamics. We unify our 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.

heading: 1 INTRODUCTION
text: A wide range of problems can be represented as sequential decision-making tasks, where the goal is to maximise some numerical reward (Sutton & Barto, 2018). However, designing an appropriate reward function remains a challenge in complex real-world tasks (Amodei et al., 2016; Leike et 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 (Christiano et al., 2017), and many others (Jeon et al., 2020). This approach has extended the applicability of sequential decision-making 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 evaluating algorithms relative to 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 a given application, such as policy optimisation. Characterising this ambiguity tolerance for various applications allow us to evaluate the ambiguity of a data source relative to a given application. Learnt reward functions are often used for policy optimisation, for example via reinforcement learning (RL)1. 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 4, we explore a 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).
1We 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 et al., 2014; Peterson et al., 2021; Collins & Shenhav, 2021).

heading: 1.1 RELATED WORK
text: Inverse reinforcement learning (IRL; Russell, 1998) is the prototypical example of reward learning. IRL infers a reward function from the behavioural data of a task expert by inverting a 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., 2021) 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 et 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 et al., 2019; Bıyık et al., 2020; Koppol et al., 2020), or other multi-modal data sources (Tung et al., 2018; Jeon et al., 2020). One motivation is that different data sources may provide complementary 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 a primary application of learnt reward functions (Abbeel & Ng, 2004; Wirth et al., 2017). 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 in each task, including for additional policy optimisation techniques such as maximum entropy RL.
Ambiguity corresponds to the partial identifiability (Lewbel, 2019) of the reward function modelled as a 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).
IRL is related to dynamic discrete choice (Rust, 1994; Aguirregabiria & Mira, 2010), a problem where identifiability has been extensively studied (e.g., Aguirregabiria, 2005; Srisuma, 2015; Arcidiacono & Miller, 2020). We study a simpler setting with known tasks. IRL also relates to preference elicitation (Rothkopf & Dimitrakakis, 2011) and inverse optimal control (Ab Azar et al., 2020). Preferences over sequential trajectories are not typically considered as a data source in other fields.

heading: 1.2 PRELIMINARIES
text: 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 a tuple pS,A, τ, µ0, R, γq where S and A are finite sets of environment states and agent actions; τ : SˆAÑ ∆pSq encodes the transition distributions governing the environment dynamics; µ0 P ∆pSq is an initial state distribution; R : SˆAˆS Ñ R is a deterministic reward function2; and γ P p0, 1q is a reward discount rate. We distinguish states in the support of µ0 as initial states, and states s with τps|s, aq “ 1 and Rps, a, sq “ 0 for all a as terminal states. We represent the transition from state s to state s1 using action a as the tuple x “ ps, a, s1q. We classify ps, a, s1q as possible in an MDP if s1 is in the support of τps, aq, otherwise it is impossible. A trajectory is an infinite sequence of concatenate transitions ξ “ ps0, a0, s1, a1, s2, . . .q, and a trajectory fragment of length n is a finite sequence of n concatenate transitions ζ “ ps0, a0, s1, . . . , an´1, snq. 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 is initial. A state or transition is reachable if it is part of some possible and initial trajectory.
Given an MDP, we define the return function G as the cumulative discounted reward of entire trajectories and trajectory fragments: Gpζq “
řn´1 t“0 γ
tRpst, at, st`1q for a 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 π : S Ñ ∆pAq encodes an agent’s behaviour as a state-conditional action distribution. Together with an MDP’s transition distribution τ , a policy π induces a distribution of trajectories starting from each state. We denote such a trajectory starting from s with the random variable Ξs, and its remaining components with random variables A0, S1, A1, S2, and so on.
Given an MDP and a policy π, and the value function encodes the expected return from states, Vπpsq “ EΞs„π,τ “ GpΞsq ‰
; and the Q-function of π encodes the expected return given an initial action, Qπps, aq “ EΞs„π,τ “ GpΞsq ˇ ˇ A0 “ a ‰ . Qπ and Vπ satisfy a Bellman equation:
Qπps, aq “ ES1„τps,aq “ Rps, a, S1q ` γVπpS1q ‰ , Vπpsq “ EA„πpsq “ Qπps,Aq ‰ , (1)
for all s P S and a P A. Their difference, Aπps, aq “ Qπps, aq ´ Vπpsq, is the advantage function. We further define a policy evaluation function, J , encoding the expected return from following a particular policy in an MDP, J pπq “ ES0„µ0 “ VπpS0q ‰
. J 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 J may be multimodal, we often discuss the set of optimal policies. However, Q‹, V‹, and A‹ are unique.
Moreover, we consider several policies resulting from alternative planning algorithms. Given a base policy π0, and an inverse temperature parameter β ą 0, we define the Boltzmann policy with respect to π0, denoted ππ0β , using the softmax function:
ππ0β pa|sq “ exp
` βAπ0ps, aq ˘
ř a1PA exp ` βAπ0ps, a1q ˘ . (2)
The Boltzmann-rational policy, π‹β , is the Boltzmann policy with respect to optimal policies, as used for IRL by Ramachandran & Amir (2007). The popular Maximum Entropy policy, πβ , is defined using a modified policy evaluation function with an entropy regularisation term (Haarnoja et al., 2017), and solves the recurrence πβ “ π πβ β (i.e., πβ is a Boltzmann policy with respect to itself).
2Notably, we consider deterministic reward functions that may depend on a transition’s successor state. Alternative spaces of reward functions are often considered (such as functions from S or SˆA, or distributions). The chosen space has straightforward consequences for invariances, which we discuss in appendix C.

heading: 2 REWARD FUNCTION TRANSFORMATIONS
text: 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 functions. The invariances of an objectX derived from rewardR via function f are all transformations t that preserve f : X “ fpRq “ fptpRqq for all R. We say that X determines R up to its invariances. A set of transformations 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 derivation function – grouping the reward functions from which identical objects are derived into partition blocks.
Given a 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 infinite-data ambiguity of the data source – it is impossible to recover the reward function beyond the corresponding partition block, as the remaining functions imply indistinguishable data.
Similarly, consider a downstream application of learnt reward functions involving the computation of an object. The object’s invariances capture the ambiguity tolerance of this computation, as by definition all reward functions in each block of the corresponding partition lead to identical outcomes.

heading: 2.1 FUNDAMENTAL REWARD TRANSFORMATIONS
text: 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 potential 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 Ñ R, where Φpsq “ 0 if s is a terminal state. If Φpsq “ k for all initial states then we say that Φ is k-initial. Let R and R1 be reward functions. Given a discount γ, we say R1 is produced by (k-initial) potential shaping of R if R1ps, a, s1q “ Rps, a, s1q ` γ ¨ Φps1q ´ Φpsq for some (k-initial) potential function Φ.
Definition 2.3 (S1-Redistribution). Let R and R1 be reward functions. Given transition dynamics τ , say R1 is produced by S1-redistribution of R if ES1„τps,aq “ Rps, a, S1q ‰ “ ES1„τps,aq “ R1ps, a, S1q ‰ . S1-redistribution allows changing R arbitrarily for impossible transitions. Moreover, if at least two states s11, s 1 2 are in the support of τps, aq then S1-redistribution lets us increase Rps, a, s11q and decrease Rps, a, s12q by a proportionate amount. Note that S1-redistribution depends crucially on the reward function’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). LetR andR1 be reward functions. SayR1 is produced by a zero-preserving monotonic transformation of R if for all pairs of transitions x, x1 P SˆAˆS, Rpxq ď Rpx1q if and only if R1pxq ď R1px1q, and Rpxq “ 0 if and only if R1pxq “ 0. Moreover, say R1 is produced by positive linear scaling of R if R1 “ c ¨R for some positive constant c. A zero-preserving monotonic transformation is simply a monotonic transformation that maps zero to itself. Positive linear scaling is a special case.
Definition 2.5 (Optimality-Preserving Transformation). Let R and R1 be reward functions. Given a function O : S Ñ PpAq ´ t∅u, transition dynamics τ , and discount rate γ, we say R1 is produced from R by an optimality-preserving transformation with O if there is a function Ψ : S Ñ R such that ES1„τps,aq “ R1ps, a, S1q ` γ ¨ΨpS1q ‰
ď Ψpsq for all s, a, with equality if and only if a P Opsq. This transformation gives the reward functions with optimal actions from O (Ψ determines the new value function). Note that in practice an implicit dependence on R is introduced through the definition of O. Also, we can reach arbitrary R1 if O is unconstrained (in practice, we constrain O). Finally, we consider transformations allowing the reward to vary freely for a given set of transitions. Definition 2.6 (Masking). Let R and R1 be reward functions. Given a transition set X Ď SˆAˆS, say R1 is produced by a mask of X from R if Rpxq “ R1pxq for all x R X .

heading: 3 INVARIANCES OF REWARD-RELATED OBJECTS
text: 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 objectX 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 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 1a. We defer all proofs until appendix B.

heading: 3.1 INVARIANCES OF EXPERT BEHAVIOUR
text: Inverse reinforcement learning (IRL) algorithms infer a task’s reward function from the behaviour of task experts. Formally, this behaviour is represented as an expert’s policy or a sample of trajectories.
To characterise the corresponding invariances, we begin withQ-functions – instrumental to deriving many policies. Q-functions are invariant to S1-redistribution since they are defined as an expectation over the successor state S1, We show that this is the only invariance for Q-functions. Theorem 3.1. Given an MDP and a policy π, the Q-function for π, Qπ , determines R up to S1redistribution. The optimal Q-function, Q‹, has precisely the same invariances.
This invariance is inherited by any object that can be derived from a Q-function. However, note that S1-redistribution vanishes in simpler spaces of reward functions, as we explore in appendix C.
We now turn to policies derived using various planning algorithms. These policies are instrumental in constructing the trajectories studied in IRL. For example, Ramachandran & Amir (2007) and Ziebart et al. (2008) assume that expert behaviour is drawn from a Boltzmann-rational 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 S1-redistribution. We show they are also invariant to potential shaping, but not to any other transformations. Theorem 3.2. Given an MDP, an inverse temperature parameter β, and a base policy π0, the Boltzmann policy ππ0β determines R up to S
1-redistribution and potential shaping. The Boltzmannrational policy, π‹β , and the Maximum Entropy policy, πβ , have precisely the same invariances.
By contrast, Ng & Russell (2000) and Abbeel & Ng (2004) assume that experts follow an optimal policy. Optimal policies inherit S1-redistribution invariance from the optimal Q-function, and are also known to be invariant to potential shaping (Ng et al., 1999). Under an additional assumption that a given policy is maximally supportive, in that it takes all optimal actions with positive probability, we show that these invariances and any additional invariances are captured in a class of optimalitypreserving transformations (Definition 2.5) based on the set of optimal actions in each state. Theorem 3.3. Given an MDP, let Opsq “ arg maxaA‹ps, aq. A maximally supportive optimal policy determines R up to optimality-preserving transformations with O. Additional invariances arise if we consider optimal policies that may lack support for optimal actions. As a well-known example, the zero-reward is consistent with any policy in this sense.
In the infinite-data limit, a 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 an MDP, an inverse temperature parameter β, and a base policy π0, the distribution of trajectories induced by the Boltzmann policy ππ0β from all initial states determines R up to S1-redistribution, potential shaping, and a mask of unreachable transitions. The distributions of trajectories induced by the Boltzmann-rational policy, π‹β , and the Maximum Entropy policy, πβ , from all initial states, have precisely the same invariances.
Similarly, trajectories sampled from an 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 a maximally supportive optimal policy. Let S be the set of states in supported trajectories. Let O be the set of functions O defined on S such that Opsq “ arg maxaA‹ps, aq for all s P S. The induced distribution of trajectories determines R up to optimality-preserving transformations with O P O. Note that a mask of the complement of S is not permitted. However, the fact that O is unconstrained outside S leaves reward effectively unconstrained in those states, except that the reward of transitions out of S may have to “compensate” for the value of their successor states, to prevent new actions that lead out of S from becoming optimal.

heading: 3.2 INVARIANCES OF TRAJECTORY EVALUATION
text: The return function, capturing the reward accumulated over a trajectory, is instrumental in deriving data for evaluative feedback such as 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 to possible trajectory fragments, Gζ , determines R up to a mask of impossible transitions; 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 a 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 as a minimum or maximum fragment length, or a restriction to initial trajectory fragments.
Pairwise comparisons between trajectories are studied as a data source for reward learning (Akrour et al., 2012; Christiano et al., 2017). It is common to model the comparisons as based on the return of trajectories, but with accompanying decision noise following a Boltzmann 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, so little invariance is introduced.
Formally, given an MDP and an inverse temperature parameter β ą 0, let ĺζβ be a distribution over each pair of possible trajectory fragments, ζ1, ζ2, such that
Ppζ1 ĺζβ ζ2q “ exppβGpζ2qq
exppβGpζ1qq ` exppβGpζ2qq ,
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, ĺζβ , determines R up to a mask of impossible transitions. Theorem 3.9. Given an MDP, the distribution of comparisons of possible and initial trajectories, ĺξβ , 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 comparisons permitted, including, for example, comparisons between individual transitions and empty trajectories. Additional invariances will arise from additional restrictions, such as permitting comparisons only between fragments of a fixed length. Moreover, it is 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 as 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 a relation, ĺζ‹, on possible trajectory fragments:
ζ1 ĺζ‹ ζ2 ô Gpζ1q ď Gpζ2q . Similarly, define the noiseless order of possible and initial trajectories as the analogous relation, ĺξ‹, 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).
Theorem 3.10. We have the following bounds on the invariances of the noiseless order of possible trajectory fragments, ĺζ‹. In all MDPs:
(1) ĺζ‹ is invariant to positive linear scaling and a mask of impossible transitions; and
(2) ĺζ‹ is not invariant to transformations other than zero-preserving monotonic transformations or masks of impossible transitions.
Moreover, there exist MDPs attaining each of these bounds.
We give a 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 ĺ ζ ‹, ĺξ‹ is always invariant to positive linear scaling.
Theorem 3.11. Given an MDP, the noiseless order of possible and initial trajectories, ĺξ‹, is invariant to k-initial potential shaping, positive linear scaling, and a mask of unreachable transitions.

heading: 3.3 INVARIANCES OF POLICY OPTIMISATION
text: The primary application of learnt reward functions is to compute optimal policies, using techniques such as RL. Policy optimisation procedures typically compute a single optimal policy. However, in terms of invariances, one may desire to preserve the whole set of optimal policies, so as not to tolerate any sub-optimal policies becoming optimal through a reward transformation.
The set of optimal policies inherits S1-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 a maximally supportive optimal policy (Theorem 3.3). Theorem 3.12. Given an MDP, let Opsq “ arg maxaA‹ps, aq. Then the set of optimal policies determines R up to optimality-preserving transformations with O. Moreover, if one uses an algorithm not guaranteed to find a globally optimal policy, one may desire to preserve the entire order induced on the space of 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. S1-redistribution and optimality-preserving transformations for a given MDP might not. Moreover, Theorem 3.12 implies that any transformation that is not an optimality-preserving transformation in a given MDP cannot preserve optimal policies in that MDP, let alone all MDPs.

heading: 4 IMPLICATIONS FOR REWARD LEARNING
text: So far we have catalogued the invariances of transformations to the reward function of various reward function derived objects. These invariances characterise the infinite-data 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 applications in terms of their ambiguity. The characterisation of ambiguity and tolerance as invariances to reward transformations suggests a natural partial order on data sources and applications. Recall that the invariances of an object correspond to a partition of the space of reward functions (section 2). We lift the refinement relation for partitions (Aigner, 1979, §I.2.B) to data sources and applications as follows. Definition 4.1 (Ambiguity refinement). Consider two reward learning data sources (or applications), X and Y . Let ΠX and ΠY be the partitions of the space of reward functions corresponding to their respective invariances (definition 2.1). If ΠX is a partition refinement of ΠY , we writeX ĺ Y , and we say X is no more ambiguous than Y (or X is tolerable for application Y ). If X ĺ Y but not Y ĺ X , then we write X ă Y and say X is (strictly) less ambiguous than Y .
Given two data sources X and Y , X ĺ Y corresponds to X conflating no additional reward functions compared to Y in the infinite-data limit. This is the sense in which we say X is no more ambiguous than Y . Moreover, given a downstream application Z, X ĺ Z is precisely the condition of Z tolerating the infinite-data ambiguity of data source X: 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 ambiguity refinement in a given MDP, as summarised in figure 1b. Invariance to k-initial potential shaping (k-Φ) corresponds to less ambiguity than general potential shaping (Φ). Likewise positive linear scaling (PLS) is less ambiguous than zero-preserving monotonic transformations (ZPMT), and a mask of impossible transitions is less ambiguous than S’-redistribution (S1-R). All of these transformations other than zero-preserving monotonic transformations are less ambiguous than the optimality-preserving transformations we have encountered.
More concretely, we can compare the ambiguity of specific data sources. Some of these comparisons are indicated in figure 1a. For example, the ambiguity tolerance of the set of optimal policies is a class of optimality-preserving transformations. Each of the data sources that are less ambiguous than this tolerance are sufficient for policy optimisation.
Notably, this excludes noiseless comparisons between trajectory fragments in some MDPs. Specifically, policy optimisation does not, in general, tolerate zero-preserving monotonic transformations (ZPMT), while noiseless comparisons are invariant to this transformation in some MDPs (Theorem 3.10). Policy optimisation also does not tolerate data sources based on 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 as under a shift in transition dynamics or 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 1 Ą 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 be tolerable for applications in the new MDP.
A similar results holds for S1-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, S1-redistribution 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 as depending on the successor-state (cf. appendix C). Theorem 4.1. Consider an MDP pS,A, τ, µ0, R, γq, a policy π, and alternative transition dynamics τ 1 with τps, aq ‰ τ 1ps, aq for all s P S, a P A. Given a function Q1 : SˆA Ñ R, there exists a reward function R1, produced from R by S1-redistribution under τ , such that Q1 is the Q-function for π under R1 and τ 1.
Ambiguity refinement is a partial order, and some data sources are indeed incomparable. In consolation, we observe that such incomparable ambiguity is complementary ambiguity, in that by combining the associated data sources, we reduce overall ambiguity about the latent reward. Theorem 4.2. Given data sources X and Y , let pX,Y q denote the combined data source formed from X and Y . If X and Y are incomparable, then pX,Y q ă X and pX,Y q ă 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. (2017) and Cao et al. (2021).

heading: 5 LIMITATIONS AND FUTURE WORK
text: 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 a poor fit for human data (Orsini et al., 2021). For example, human demonstrations are rarely perfectly optimal or Boltzmannrational. Moreover, there is often a trade-off between how informative a data source is and how easy it is for a user to provide data. As an extreme example, a user directly specifying the target reward function is maximally informative – if users could complete such a task correctly. We expect the maximum informativeness of a data source to be a useful metric, but it should be considered alongside the cost and tractability of collecting different kinds of data.

heading: 6 CONCLUSION
text: 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 to 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 are strictly less informative than others, such as noiseless preference comparisons vs. return labels. By contrast, others are incomparable and have complementary ambiguity, such as Q-values (invariant to S1-redistribution but not potential shaping) vs. episode return Gξ (invariant to some potential shaping, but not to S1-redistribution).
In particular, we have characterised the invariances of various reward-related objects to transformations such as potential shaping. We have shown that these objects form a partial order under ambiguity refinement. These results, summarised in figure 1, allow us to predict the ambiguity of 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 objects. 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.

heading: ETHICS STATEMENT
text: It is important that AI systems are aligned with the interests of users and other stakeholders. In openended problems, directly specifying how the AI 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 et 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 to misspecification, or the cost of data collection.
Moreover, even if a 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 AI 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 a thorough evaluation of these considerations 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.

heading: REPRODUCIBILITY STATEMENT
text: 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 B.

heading: A PROPERTIES OF FUNDAMENTAL REWARD TRANSFORMATIONS
text: We begin with some supporting results concerning the basic reward transformations, used in section 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 1, two MDPs differing only in their reward functions, respectively R and R1. Denote the return, Q-, value, and policy evaluation functions of M 1 by G1, Q1π , V 1 π , and J 1. If R1 is produced by potential shaping of R with a potential function Φ, then: (1) for a trajectory fragment ζ “ ps0, a0, s1, . . . , snq, G1pζq “ Gpζq ` γnΦpsnq ´ Φps0q; (2) for a trajectory ξ “ ps0, a0, . . .q, G1pξq “ Gpξq ´ Φps0q; (3) for a state s P S , and action a P A, Q1πps, aq “ Qπps, aq ´ Φpsq; (4) for a state s P S, V 1πpsq “ Vπpsq ´ Φpsq; and (5) for a policy π, J 1pπq “ J pπq ´ ES0„µ0 “ ΦpS0q ‰ .
Proof. (1) is given by straightforward induction on the length of ζ. For (2), take the limit as the length of a prefix goes to infinity, whereupon γnΦpsnq goes to zero (γ ă 1 by definition, and Φpsnq is bounded since its domain is finite). (3) and (4) were proved for optimal policies by Ng 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 pS,A, τ, µ0, R, γq be an MDP, R1 a reward function, and k P R a constant. Then we have thatG1pξq “ Gpξq´k for all possible and initial trajectories ξ, if and only ifR1 is produced from R by k-initial potential shaping and a mask of unreachable transitions.
Proof. The converse follows from Lemma A.1 and that varying the reward for unreachable transitions does not affect the return of any possible, initial trajectories, by definition.
In the forward direction, consider an arbitrary reachable state s P S. Let ζ be a possible, initial, length n trajectory fragment ending in s (at least one exists, since s is reachable). Let ξs be some possible trajectory starting in s, and let ∆ξs “ Gpξsq ´G1pξsq. Let ζ ` ξs denote the concatenation of ζ and ξs. Since ζ` ξs is an initial trajectory, we have by assumption Gpζ` ξsq´G1pζ` ξsq “ k. Moreover, note that Gpζ ` ξsq “ Gpζq ` γnGpξsq, (and likewise for G1), by definition of return. Then (recalling that we have defined γ ą 0),
∆ξs “ Gpξsq ´G1pξsq
“ Gpζ ` ξsq ´Gpζq γn ´ G 1pζ ` ξsq ´G1pζq γn “ k ´Gpζq `G 1pζq
γn .
Therefore ∆ξs is independent of ξs, except for possible dependence on ξs’s starting state s. We associate a unique P psq “ ∆ξs with each reachable s. Now consider a reachable transition ps, a, s1q. Further straightforward algebraic manipulation shows that R1ps, a, s1q “ Rps, a, s1q ` γ ¨ P ps1q ´ P psq. Moreover, from the definition of terminal states we must have that P psq “ ∆ξs “ 0 for terminal s, and by assumption we have that P psq “ ∆ξs “ k if s is initial. So R1 is given by k-initial potential shaping of R with Φpsq “ P psq for reachable transitions. Any variation in reward for unreachable transitions can be accounted for by the mask.
Lemma A.3. Let pS,A, τ, µ0, R, γq be an MDP, R1 a reward function, and c P R a constant. Then G1pξq “ c ¨Gpξq for all possible initial trajectories ξ, if and only if R1 is produced from R by zeroinitial potential shaping, linear scaling by a factor of c, and a mask of all unreachable transitions.
Proof. From Lemma A.1, we have that 0-initial potential shaping leaves G unchanged. Likewise, a mask of unreachable transitions does not affect G for possible initial trajectories. Moreover, it is straightforward that linear scaling of R by a factor of c leads to a linear scaling of G by the same factor of c. Hence the converse is established.
For the forward direction, consider an arbitrary reachable state s P S. Let ξs be some possible trajectory starting in s, and let ∆ξs “ c ¨ Gpξsq ´ G1pξsq. Let ζ be a possible, initial, length n trajectory fragment ending in s. Since the concatenation ζ ` ξs is a possible initial trajectory, we have that
G1pζ ` ξsq “ c ¨Gpζ ` ξsq Ñ G1pζq ` γnG1pξsq “ c ¨ pGpζq ` γnGpξsqq Ñ G1pζq “ c ¨Gpζq ` γnpc ¨Gpξsq ´G1pξsqq
“ c ¨Gpζq ` γn∆ξs
Ñ ∆ξs “ G1pζq ´ c ¨Gpζq
γn
Therefore ∆ξs is independent of ξs, except for possible dependence on ξs’s starting state s. We associate a unique P psq “ ∆ξs with each reachable s. Now consider a reachable transition ps, a, s1q. Further straightforward algebraic manipulation shows that R1ps, a, s1q “ c ¨Rps, a, s1q`γ ¨P ps1q´P psq. Moreover, from the definition of terminal states we must have that P psq “ ∆s “ 0 for terminal s, and by assumption we have that P psq “ 0 if s is initial. Thus R1 is given by first potential shaping R with Φpsq “ 1cP psq, and then linear scaling with c.

heading: B PROOFS
text: We provide proofs for the theoretical results presented in the main paper.

heading: B.1 PROOFS FOR SECTION 3.1 RESULTS NOT CONCERNING OPTIMAL POLICIES
text: 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 B.2). Theorem 3.1. Given an MDP and a policy π, the Q-function for π, Qπ , determines R up to S1redistribution. The optimal Q-function, Q‹, has precisely the same invariances.
Proof. Qπ satisfies the Bellman equation for all s P S, a P A: Qπps, aq “ ES1„τps,aq,A1„πpS1q “ Rps, a, S1q ` γ ¨QπpS1, A1q ‰ .
This equation can be rewritten as
ES1„τps,aq “ Rps, a, S1q ‰ “ Qπps, aq ´ γ ¨ ES1„τps,aq,A1„πpS1q “ QπpS1, A1q ‰ .
From this, we can see that Qπ is invariant to S1-redistribution of R, and no other transformations. Q‹ “ Qπ‹ where π‹ is any optimal policy derived from Q‹, so the invariances of the optimal Q-function follow as a special case.
Theorem 3.2. Given an MDP, an inverse temperature parameter β, and a base policy π0, the Boltzmann policy ππ0β determines R up to S
1-redistribution and potential shaping. The Boltzmannrational policy, π‹β , and the Maximum Entropy policy, πβ , have precisely the same invariances.
Proof. By equation (2), ππ0β can be derived from Aπ0 . Aπ0 itself can be derived from Qπ0 , given π0 (by equation (1), Aπ0ps, aq “ Qπ0ps, aq ´ EA„π0psq “ Qπ0ps,Aq ‰ ). Thus ππ0β is invariant to S 1- redistribution by Theorem 3.1. Moreover, by Lemma A.1, potential shaping causes a state-dependent shift of Qπ0 . This shift does not affect Aπ0 . Therefore π π0 β is also invariant to potential shaping.
Conversely, recall (or see Lemma B.1, below) that the softmax function is invariant only to constant shifts. This means that ππ0β is invariant to all and only those transformations of R that produce statedependent shifts in Qπ . Let B : S Ñ R, and suppose R and R1 are two reward functions such that the corresponding Q-functions (for π) satisfy Q1ps, aq “ Qps, aq `Bpsq. Then
ErR1ps, a, S1qs “ ErQ1ps, aq ´ γ ¨maxa1PAQ1pS1, a1qs “ ErQps, aq `Bpsq ´ γ ¨maxa1PApQpS1, a1q `BpS1qqs “ ErBpsq ´ γ ¨BpS1q `Rps, a, S1qs
where the expectations are over S1 „ τps, aq. Now set Φpsq “ ´Bpsq, and we can see that the difference between R and R1 is described by potential shaping and S1-redistribution.
The Boltzmann-rational 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 of these policies follow as a special case of this result.
Lemma B.1. Consider two functions f : X Ñ R and g : X Ñ R defined on a finite set X . Then g is constant if, for all x P X ,
exppfpxq ` gpxqq ř x1PX exppfpx1q ` gpx1qq “ exppfpxqqř x1PX exppfpx1qq .
Proof. This is an elementary property of the softmax function. It can be seen as follows:
Ñ exppfpxq ` gpxqq exppfpxqq “
ř x1PX exppfpx1q ` gpx1qq ř
x1PX exppfpx1qq
Ñ gpxq “ ln ˆř x1PX exppfpx1q ` gpx1qq ř
x1PX exppfpx1qq
˙
which is constant in x. (The converse is true, but we do not make use of it, so we omit a proof.)
Theorem 3.4. Given an MDP, an inverse temperature parameter β, and a base policy π0, the distribution of trajectories induced by the Boltzmann policy ππ0β from all initial states determines R up to S1-redistribution, potential shaping, and a mask of unreachable transitions. The distributions of trajectories induced by the Boltzmann-rational policy, π‹β , and the Maximum Entropy policy, πβ , from all initial states, have precisely the same invariances.
Proof. That the distribution is invariant to S1-redistribution and potential shaping follows from Theorem 3.2. The distribution is 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 is additionally invariant to a mask of unreachable transitions.
The trajectory distribution can be factored into the separate distributions ππ0β psq P ∆pAq for each reachable state s, by conditioning on a supported prefix trajectory fragment that leads to s and marginalising over subsequent states and actions. Via a similar argument to the proof of Theorem 3.2, the distribution determines the reward function for transitions (out of these reachable states) up to potential shaping and transformations and S1-redistribution (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.

heading: B.2 PROOFS FOR SECTION 3.1 RESULTS CONCERNING OPTIMAL POLICIES
text: Our results concerning the invariance of optimal policies and their trajectories follow from the following general result: Lemma B.2. Given an MDP M , suppose we have access to the set of optimal actions for each state in a subset of states S Ď S. Assume that this subset is closed under optimal actions given the transition dynamics of M (that is, taking optimal actions from states in S never leads to states outside of S). Let O be the set of functions O defined on S such that Opsq “ arg maxaPAA‹ps, aq for all s P S (but O is unconstrained for states outside S). Then these optimal action sets determine R up to optimality-preserving transformations with O P O.
Proof. SupposeR1 is obtained fromM ’s rewardR via an optimality-preserving transformation with some O P O. Let Ψ be the corresponding value-bounding function, that is, a function Ψ : S Ñ R satisfying, for all s P S and a P A,
ES1„τps,aq “ R1ps, a, S1q ` γ ¨ΨpS1q ‰ ď Ψpsq , (3) with equality if and only if a P Opsq. Since Opsq is non-empty (by definition), we have for all s P S
Ψpsq “ max aPA
` ES1„τps,aq “ R1ps, a, S1q ` γ ¨ΨpS1q ‰˘ .
This recursive condition on Ψ is the Bellman optimality equation for the unique optimal value function, V 1‹ , of the MDP with transformed reward R
1. Therefore, Ψpsq “ V 1‹psq for all s P S , and we can rewrite equation (3) as
ES1„τps,aq “ R1ps, a, S1q ` γ ¨ V 1‹pS1q ‰ ď V 1‹psq , (4) with equality only for a P Opsq. Now, consider a state s P S. By assumption, for this s, Opsq “ arg maxaPAA‹ps, aq. Then for this state, the actions that attain the optimal value bound in equation (4) are these same optimal actions. Therefore, R1 induces the same sets of optimal actions from states in S. Conversely, consider a second MDP M 1, differing from M only in its reward function, R1. Assume the set of optimal actions in states in S agrees with the optimal actions in M for those states. Let V 1‹ and A1‹ denote the optimal value and advantage functions for M
1. The Bellman optimality equation for M 1 ensures that, for s P S,
V 1‹psq “ max aPA ` ES1„τps,aq “ R1ps, a, S1q ` γ ¨ V 1‹pS1q ‰˘
(5)
with the maximum attained precisely by the actions a P arg maxaPApA1‹ps, aqq. Setting Opsq “ arg maxaPApA1‹ps, aqq, equation (5) can be rewritten as
ES1„τps,aq “ R1ps, a, S1q ` γ ¨ V‹pS1q ‰ ď V‹psq (6)
for all s P S and a P A, with equality if and only if a P Opsq. Now, for s P S, we have arg maxaPApA1‹ps, aqq “ arg maxaPApA‹ps, aqq, becauseM andM 1 have matching sets of optimal actions for these states (by assumption). Then equation (6) shows thatR1 is produced from R by an optimality-preserving transformation with Opsq “ arg maxaPApA1‹ps, aqq (and Ψpsq “ V 1‹psq).
We are now in a position to prove the results from the main text: Theorem 3.3. Given an MDP, let Opsq “ arg maxaA‹ps, aq. A maximally supportive optimal policy determines R up to optimality-preserving transformations with O.
Proof. An arbitrary maximally supportive optimal policy determines the set of optimal actions from all states in the MDP. Its invariances follow as a special case of Lemma B.2, with S “ S .
Theorem 3.5. Given an MDP, consider the distribution of trajectories induced by a maximally supportive optimal policy. Let S be the set of states in supported trajectories. Let O be the set of functions O defined on S such that Opsq “ arg maxaA‹ps, aq for all s P S. The induced distribution of trajectories determines R up to optimality-preserving transformations with O P O.
Proof. The distribution of trajectories can be factored into separate distributions π‹psq P ∆pAq for each state s P S (in a manner similar to Theorem 3.4, as proved above). These individual distributions determine the set of optimal actions within those states.
Noting that S 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.

heading: B.3 PROOFS FOR SECTION 3.2 RESULTS
text: Theorem 3.6. Given an MDP, the return function restricted to possible trajectory fragments, Gζ , 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.
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 a 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, ĺζβ , determines R up to a mask of impossible transitions.
Proof. Since ĺζβ can be derived from Gζ , it is invariant to a mask of impossible transitions by Theorem 3.6. Conversely, ĺζβ determines R for all possible transitions. This is because Rps, a, s1q is encoded in the Boltzmann distribution of comparisons between the length zero trajectory fragment ζ0 “ psq and the length one trajectory fragment ζ1 “ ps, a, s1q, and can be recovered as follows:
Ppζ0 ĺζβ ζ1q “ exppβGpζ1qq exppβGpζ0qq ` exppβGpζ1qq “ exppβRps, a, s 1qq exppβ ¨ 0q ` exppβRps, a, s1qq
Ñ Rps, a, s1q “ 1 β ¨ ln
˜
Ppζ0 ĺζβ ζ1q 1´ Ppζ0 ĺζβ ζ1q
¸
.
Therefore ĺζβ is invariant to precisely a mask of impossible transitions.
Theorem 3.9. Given an MDP, the distribution of comparisons of possible and initial trajectories, ĺξβ , determines R up to k-initial potential shaping and a mask of unreachable transitions.
Proof. Note that as ĺξβ can be derived fromGξ, by Theorem 3.7, ĺ ξ β is invariant to 0-initial potential shaping and a mask of unreachable transitions. It is additionally invariant to k-initial potential shaping for arbitrary constants k P R, and no other transformations: Gξ 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 a similar manipulation as above, but we 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, ĺζ‹. In all MDPs:
(1) ĺζ‹ is invariant to positive linear scaling and a mask of impossible transitions; and
(2) ĺζ‹ is not invariant to transformations other than zero-preserving monotonic transformations or masks of impossible transitions.
Moreover, there exist MDPs attaining each of these bounds.
Proof. For (1), positive linear scaling of reward by a constant c leads to the same scaling of the return of each trajectory fragment, and this always preserves the relation ĺζ‹, since for any c ą 0, c ¨ Gpζ1q ď c ¨ Gpζ2q ô Gpζ1q ď Gpζ2q for all pairs of trajectory fragments ζ1, ζ2. Moreover, ĺζ‹ inherits invariance to a mask of impossible transitions from Gζ (Theorem 3.6).
For (2), let R1 be produced from R via some transformation that is neither a mask of impossible transitions nor a zero-preserving monotonic transformation. It must be that either R1 fails to preserve the ordinal comparison of two possible transitions, or that it fails to preserve the set of zero-reward possible transitions, compared to R. In the first case, consider two possible transitions whose rewards are not preserved, x1 and x2. Without loss of generality suppose Rpx1q ď Rpx2q but R1px1q ą R1px2q. This corresponds to a change in ĺζ‹’s comparison of the length one trajectories formed from x1 and x2, namely x1 ĺζ‹ x2 from true to false. Similarly, in the second case, the comparisons between the transition whose reward became or ceased to be zero and a length one trajectory (with return 0) will have changed. Therefore, ĺζ‹ is not invariant to such transformations.
The bound (1) is attained by the following MDP invariant precisely to positive linear scaling and a mask of impossible transitions. Let S “ tsu, A “ ta1, a2u, Rps, a1, sq “ 1, and Rps, a2, sq “ 1` γ. Since Rps, a2, sq “ Rps, a1, sq ` γRps, a1, sq, the corresponding order relation will contain both ps, a2, sq ĺζ‹ ps, a1, s, a1, sq and ps, a1, s, a1, sq ĺζ‹ ps, a2, sq. This property requires that Rps, a1, sq “ p1 ` γq ¨ Rps, a2, sq, which is preserved only by linear scaling of R. (Non-positive linear scaling is already ruled out by (2)).
The bound (2) is attained by the following MDP invariant to arbitrary zero-preserving monotonic transformations. Let S “ ts1, s2u, A “ tau, with possible transitions ps1, a, s2q and ps2, a, s2q, andRps1, a, s2q ą Rps2, a, s2q “ 0. Any zero-preserving monotonic transformation ofR preserves the ordering of all possible trajectory fragments, namely that all nonempty trajectories starting in s1 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, ĺξ‹, is invariant to k-initial potential shaping, positive linear scaling, and a mask of unreachable transitions.
Proof. The pairwise Boltzmann distributions of ĺξβ can be used to derive the noiseless comparisons of ĺξ‹. Therefore, ĺξ‹ is invariant to k-initial potential shaping and a mask of unreachable transitions.
That ĺξ‹ is also invariant to positive linear scaling follows from a similar argument as for the first bound in Theorem 3.10, proved above.

heading: B.4 PROOFS FOR SECTION 3.3 RESULTS
text: Theorem 3.12. Given an MDP, let Opsq “ arg maxaA‹ps, aq. Then the set of optimal policies determines R up to optimality-preserving 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 maximally supportive policy determines the set of optimal policies, namely as the set of all policies whose support is a subset of the maximally supportive policy. Therefore, these objects share precisely the same invariances.

heading: B.5 PROOFS FOR SECTION 4 RESULTS
text: Theorem 4.1. Consider an MDP pS,A, τ, µ0, R, γq, a policy π, and alternative transition dynamics τ 1 with τps, aq ‰ τ 1ps, aq for all s P S, a P A. Given a function Q1 : SˆA Ñ R, there exists a reward function R1, produced from R by S1-redistribution under τ , such that Q1 is the Q-function for π under R1 and τ 1.
Proof. Per definition 2.3, that R1 is produced from R by S1-redistribution under τ requires, for all s P S and a P A,
ES1„τps,aq “ R1ps, a, S1q ‰ “ ES1„τps,aq “ Rps, a, S1q ‰ . (7)
Per equation (1), that Q1 is the Q-function for π under R1 and τ 1 requires, for all s P S and a P A,
Q1ps, aq “ ES1„τ 1ps,aq,A1„πpS1q “ R1ps, a, S1q ` γQ1pS1, A1q ‰ ,
or, equivalently,
ES1„τ 1ps,aq “ R1ps, a, S1q ‰ “ Q1ps, aq ´ γES1„τ 1ps,aq,A1„πpS1q “ Q1pS1, A1q ‰ . (8)
For brevity, denote the right-hand sides of equations (7) and (8) as Rps, aq and Qps, aq respectively. Let s P S and a P A. By assumption, τ 1ps, aq ‰ τps, aq. Therefore, for at least two s1, denoted s11 and s 1 2, we have τ
1ps11|s, aq ă τps11|s, aq and τ 1ps12|s, aq ą τps12|s, aq. For the remaining s1, set Rps, a, s1q “ 0. This reduces equations (7) and (8) to the following:
τps11|s, aq ¨R1ps, a, s11q ` τps12|s, aq ¨R1ps, a, s12q “ Rps, aq τ 1ps11|s, aq ¨R1ps, a, s11q ` τ 1ps12|s, aq ¨R1ps, a, s12q “ Qps, aq
This system has a solution as its determinant is τ 1ps12|s, aq ¨ τps11|s, aq´ τps12|s, aq ¨ τ 1ps11|s, aq ą 0.
Theorem 4.2. Given data sources X and Y , let pX,Y q denote the combined data source formed from X and Y . If X and Y are incomparable, then pX,Y q ă X and pX,Y q ă Y .
Proof. Transformations that preserve pX,Y q necessarily preserve X , therefore pX,Y q ĺ X . But since X and Y are incomparable, there is some transformation that preserves X and not Y . This transformation does not preserve pX,Y q. Therefore, pX,Y q ă X . Similarly, pX,Y q ă Y .
We note that the above result is also an elementary consequence of the lattice structure of the partial order of partition refinement (Aigner, 1979, §I.2.B), since the combined data source corresponds to the meet of the original data sources.

heading: C OTHER SPACES OF REWARD FUNCTIONS
text: Hitherto we have assumed reward functions are members of SˆAˆS Ñ R. That is, they are deterministic functions of transitions, depending on the state, action and the successor state. In 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.

heading: C.1 RESTRICTED-DOMAIN REWARD FUNCTIONS
text: It 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ˆAˆS has an ‘equivalent’ MDP with a restricted domain, and some added auxiliary states (Russell & Norvig, 2009, §17). Conversely, reward functions with restricted domains can be viewed as a special case of functions from SˆAˆS 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 a restricted domain of S or SˆA is preferred, then our invariance results can be adapted in a 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 S1-redistribution vanishes to the identity transformation, 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 objects. Notably, the Q-function uniquely identifies the reward function, and Boltzmann policies have the same invariances as 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 we have explored.
Secondly, for most MDPs, the available potential shaping transformations are restricted, but not eliminated. The function added in a potential shaping transformation (γ ¨ Φps1q ´ Φpsq) 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 a discounted MDP without terminal states, a non-zero constant potential function Φpsq “ k does not effectively depend on s, and the reward transformation of adding γ ¨Φps1q´Φpsq “ pγ´1q ¨k to a reward function does not introduce a dependence on s1. In general, the set of remaining potential shaping transformations will depend on the network structure of the MDP. At the extreme, in a deterministic MDP with state-action rewards, all potential shaping transformations are permitted, since a dependence on s1 can be satisfied by a.

heading: C.2 STOCHASTIC REWARD FUNCTIONS
text: Certain tasks are naturally modelled as providing rewards drawn stochastically from some distribution upon each transition. An even more expressive space of reward functions than we consider is the space of transition-conditional reward distributions3. 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,
3Of course, it’s also possible to consider reward to be distributed conditionally on only the state or stateaction components of a transition, and not the full transition.
since the expectation operation is not injective (except in certain restricted cases such as for parametric families of distributions that can be parametrised by their mean). The invariance introduced is akin to S1-redistribution, but with an expectation over the support of the reward distribution rather than the successor state of each transition.
In the extension of the RL formalism to account for stochastic rewards, this expectation is effectively the first step in the derivation of each of 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 are understood to be performed based on the pairwise comparison of the expected return of each individual trajectory, then these comparisons are also invariant to transformations of the reward distributions that preserve their means.
Fortunately, much of reinforcement learning also focuses on expected return and reward in application. Accordingly, most downstream tasks are tolerant to any ambiguity in the exact distribution of stochastic rewards, beyond identifying the mean. Since this is the same kind of ambiguity that is introduced by considering the latent parameter of reward learning as a conditional distribution rather than a deterministic function, our results are still informative for these situations.

heading: C.3 FURTHER SPACES AND FUTURE WORK
text: For certain applications, including risk-sensitive RL where non-mean objectives are pursued (Morimura et al., 2010a;b; Dabney et al., 2018), 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 to transformations of the reward distribution, and thereby their ambiguity tolerance, is left to future work.
In future extensions of this work to handle continuous MDPs, there will be an opportunity to study the effect of restricting to various parametrised spaces of reward functions. For example, it is common in 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 a similar manner to restricting the domain of a finite reward function as discussed above.
The relaxation of the Markovian assumption also introduces a broader space of reward functions, and with it, new dimensions for transformations and invariance. As one example, related to potential shaping, the non-Markovian additive transformations studied by Wiewiora et al. (2003) will amount to new invariances of the optimal policy and other related objects.

Review summaries:
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.

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.