STARC: A General Framework For Quantifying Differences Between Reward Functions
Authors: Joar Max Viktor Skalse
Lucy Farnik
Sumeet Ramesh Motwani
Erik Jenner
Adam Gleave
Alessandro Abate
Venue: ICLR 2024 poster (2024)
Keywords: reward functions
reward learning
metrics
evaluations
Primary area: reinforcement learning
TL;DR: We introduce a family of methods for quantifying the difference between reward functions.

Abstract: In order to solve a task using reinforcement learning, it is necessary to first formalise the goal of that task as a *reward function*. However, for many real-world tasks, it is very difficult to manually specify a reward function that never incentivises undesirable behaviour. As a result, it is increasingly popular to use *reward learning algorithms*, which attempt to *learn* a reward function from data. However, the theoretical foundations of reward learning are not yet well-developed. In particular, it is typically not known when a given reward learning algorithm with high probability will learn a reward function that is safe to optimise. This means that reward learning algorithms generally must be evaluated empirically, which is expensive, and that their failure modes are difficult to anticipate in advance. One of the roadblocks to deriving better theoretical guarantees is the lack of good methods for *quantifying* the difference between reward functions. In this paper we provide a solution to this problem, in the form of a class of pseudometrics on the space of all reward functions that we call STARC (STAndardised Reward Comparison) metrics. We show that STARC metrics induce both an upper and a lower bound on worst-case regret, which implies that our metrics are tight, and that any metric with the same properties must be bilipschitz equivalent to ours. Moreover, we also identify a number of issues with reward metrics proposed by earlier works. Finally, we evaluate our metrics empirically, to demonstrate their practical efficacy. STARC metrics can be used to make both theoretical and empirical analysis of reward learning algorithms both easier and more principled.

Published as a conference paper at ICLR 2024
STARC: A GENERAL FRAMEWORK FOR QUANTIFYING DIFFERENCES BETWEEN REWARD FUNCTIONS
Joar Skalse
Lucy Farnik University of Bristol
Department of Computer Science
Future of Humanity Institute Oxford University
Bristol Al Safety Centre lucy. Sacy.farnieebristoolo .cc. .ukuk
joar joar. saarsssklsesss ox..sxxx.. ox. ac..k
Sumeet Ramesh Motwani
Erik Jenner
Berkeley Artificial Intelligence Research University of California, Berkeley motwani @berkeley edu edu
Berkeley Artificial Intelligence Research University of California, Berkeley jenner@berkeley edu
Adam Gleave
Alessandro Abate
FAR AI, Inc. adam far. ai
Department of Computer Science Oxford University
aabate@ cs ox.accu.
ABSTRACT
In order to solve a task using reinforcement learning, it is necessary to first for- malise the goal of that task reward function. However, for many real-world tasks, it is very difficult to manually specify a reward function that never incen- tivises undesirable behaviour. As result, is increasingly popular use reward learning algorithms,, which attempt to learn a reward function from data. How- ever, the theoretical foundations of reward learning are not yet well-developed. In particular, it is typically not known when a given reward learning algorithm with high probability will learn a reward function that safe to optimise. This means that reward learning algorithms generally must be evaluated empirically, which is expensive, and that their failure modes are difficult to anticipate in advance. One the roadblocks deriving better theoretical guarantees is the lack of good methods for quantifying the difference between reward functions. In this paper we provide solution to this problem, in the form of class of pseudometrics of all reward functions that we call STARC (STAndardised Reward Comparison) metrics. We show that STARC metrics induce both upper and lower bound on worst-case regret, which implies that our metrics are tight, and that any metric with the same properties must be bilipschitz equivalent to ours. Moreover, we also identify a number of issues with reward metrics proposed by earlier works. Finally, we evaluate our metries empirically, to demonstrate their practical efficacy. STARC metrics can be used to make both theoretical and empirical analysis of reward learning algorithms both easier and more principled.
the space
INTRODUCTION
To solve a sequential decision-making task with reinforcement learning or automated planning, we must first formalise that task using a reward function (Sutton & Barto 2018 Russell & Norvig 2020). However, for many tasks, is extremely difficult to manually specify reward function that captures the task the intended way. To resolve this issue, it is increasingly popular to use reward learning, which attempts to learn reward function from data. There many techniques for doing this. For example, it is possible to use preferences between trajectories (c.g. Christiano et al., 2017), expert demonstrations (e.g. Ng & Russell 2000), or combination of the two (e.g. Ibarz al. 2018)

---

Published as a conference paper at ICLR 2024
To evaluate a reward learning method, we must quantify the difference between the learnt reward function and the underlying true reward function. However, doing this is far from straightforward. A simple method might be to measure their Læ-distance. However, this is unsatisfactory, because two reward functions can have a large Trg-distance, even if they induce the same ordering of policies, or small lzy-distance, even if they induce the opposite ordering of policies!] Another option is to evaluate the learnt reward function on a test set. However, this is also unsatisfactory, because it can only guarantee that the learnt reward function is accurate on given data distribution, and when the reward function is optimised we necessarily incur a distributional shift (after which the learnt reward function may no longer match the true reward function). Yet another option is to optimise the learnt reward function, and evaluate the obtained policy according to the true reward function. However, this also unsatisfactory, both because it is very expensive, and because it makes it difficult to separate issues with the policy optimisation process from issues with the reward learning algorithm. Moreover, because this method is purely empirical, it cannot be used for theoretical work. These issues make it challenging to evaluate reward learning algorithms in way that is principled and robust. This in turn makes it difficult to anticipate in what situations a reward learning algorithm might fail, or what their failure modes might look like. It also makes it diffieult to compare different reward learning algorithms against each other, without getting results that may be heavily dependent on the experimental setup. These issues limit the applicability of reward learning in practice.
In this paper, we introduce STAndardised Reward Comparison (STARC) metrics, which is a family of pseudometrics that quantify the difference between reward functions in a principled way. Moreover, we demonstrate that STARC metries enjoy strong theoretical guarantees. In particular, we show that STARC metries induce an upper bound on the worst-case regret that can be induced under arbitrary policy optimisation, which means that small STARC distance guarantees that two reward functions behave similar way. Moreover, we also demonstrate that STARC metrics induce a lower bound on worst-case regret. This has the important consequence that any reward function distance metric which induces both an upper and lower bound on worst-case regret must be bilipschitz equivalent to STARC metries, which in turn means that they (in a certain sense) are unique. In particular, should not expect to be able to improve on them in any substantial way. In addition to this, we also evaluate STARC metrics experimentally, and demonstrate that their theoretical guarantees translate into compelling empirical performance. STARC metrics are cheap to compute, which means that they can be used for empirical evaluation of reward learning algorithms. Moreover, they can be calculated from a closed-form expression, which means that they are also suitable for use in theoretical analysis. As such, STARC metries enable us to evaluate reward learning methods in a way that both easier and more theoretically principled than relevant alternatives. Our work thus contributes towards building a more rigorous foundation for the field of reward learning.
1.1 RELATED WORK
There are two existing papers that study the problem of how to quantify the difference between reward functions. The first Gleave al. (2020), which proposes a distance metric that they call Equivalent-Policq Invariant Comparison (EPIC). They show that the EPIC-distance between two reward functions induces a regret bound for optimal policies. The second paper is Wulfe et al. (022)) which proposes a distance metric that they call Aynae Reward Distance (DARD). Unlike EPIC, DARD incorporates information about the transition dynamics of the environment. This means that DARD might give tighter measurement, in situations where the transition dynamics are known. Unlike Gleave et al. (2020). they do not derive any regret bound for DARD.
Our work extends the work by Gleave et al. 2020) and Wulfe et al. (0022) in several important ways. First of all, Wulfe et al. (2022) do not provide any regret bounds, which is unsatisfactory for theoretical work, and the upper regret bound that is provided by Gleave al. (2020) is both weaker and less general than ours. In particular, their bound only considers optimal policies, whereas our bound covers all pairs of policies (with optimal policies being special case). Moreover, we also argue that Gleave et al. (2020) have chosen to quantify regret in a way that fails to capture what we care about in practice. In Appendix A we provide an extensive theoretical analysis of EPIC, and show
For example, given an arbitrary reward function It and an arbitrary constant c, we have that Hi and c R have the same ordering of policies, even though their L2 L2-distance may be arbitrarily large. Similarly, for any c. we have that e R and -e- - R have the opposite ordering of policies, unless R is constant, even though their Tigddittncce may be arbitrarily small.
2

---

Published as a conference paper at ICLR 2024
that it lacks many of the important theoretical guarantees enjoyed by STARC metrics. In particular, we demonstrate that EPIC fails to induce either an upper or lower bound on worst-case regret (as we define it). We also include an extensive discussion and criticism of DARD in Appendix B Moreover, in Section 4 we provide experimental data that shows that STARC metrics in practice can have a much tighter correlation with worst-case regret than both EPIC and DARD. This means that STARC metrics both can attain better empirical performance and give stronger theoretical guarantees than the pseudometrics proposed by earlier work.
It is important to note that EPIC is designed to be independent of the environment dynamics, whereas both STARC and DARD depend on the transition dynamics. This issue is discussed in Section 2.3
The question of what happens if one reward function is optimised instead of a different reward function considered by many previous works. A notable example Ng et al. (199),, which shows that if two reward functions differ by type of transformation they call potential shaping, then they have the same optimal policies in all environments. Potential shaping is also studied by e.g. je.Jenner et al.] (022)). Another example is Skalse et al. (022b), which shows that if two reward functions R1, R2 have the property that there are no policies IT i2 such that JI(TT) > JI (TTA) and (2( < (2()) then either R₁ and Ry induce the same ordering of policies, or at least one of them assigns the same reward to all pohicies.Zhuang Zhuang & Hadfield Menell (02II) consider proxy rewards that depend strict subset of the features which are relevant to the true reward, and then show that optimising such a proxy in some cases may be arbitrarily bad, given certain assumptions, Skalse et al. (2022a) derive necessary and sufficient conditions for when two reward functions are equivalent, for the purposes of computing certain policies or other mathematical objects. Also relevant is Everitt al. (2017), which studies the related problem of reward corruption, and Pan et al. (2022). which considers natural choices of proxy rewards for several environments. Unlike these works, we are interested in the question of quantifying the difference between reward functions.
1.2 PRELIMINARIES
A Markov Decision Processes (MDP) is tuple (S, T, Po, R, 7) where S is a set of states, A is a set of actions, T : SxA - A(S) is a transition function, funnitiin,function,
μl E A(S) is an initial state distribution. is discount rate. A policy is a function R: Ax S - IR is reward function, and 7 (0,1) 1)
π. : S (A)). A trajectory 5 = (su, ao; $1, Q1 ....) is a possible path in an MDP. The return function G gives the cumulative discounted reward of a trajectory, G(E) Ei=p 7²t RR(s, at, 8t+1) and the evaluation function J gives the expected trajectory return given policy, ((T) Ee-= [G(E)] A policy maximising J is an optimal policy. The value function V S - I of a policy encodes the expected future discounted reward from each state when following that policy. We use R to refer to the set of all reward functions. When talking about multiple rewards, we give each reward a subscript R, and use J.. G, and V,", to denote R 's evaluation function, return function, and r-value function.
In this paper, we assume that all states are reachable under T and Po- Note that if this is not the case, then all unreachable states can simply be removed from S. Our theoretical results also assume that S and A are finite. However, STARC metrics can still be computed in continuous environments.
Given set X, function d: X X - R is called a pseudometric if d(z1, 21) 0. d(x), x2) > 0. d(z1, = d(I2,, II), ). and d(æ1,, xa)a & d(zi, x2) + d(I2, 23), for all T1, 22 E X. Given two pseudometrics d1, da on X, if there are constants é, u such that é. di (2), & d2(x1, x22 & u- di (I1, for all Z1, Z2 E X, then di and d2 are bilipschitz equivalent. Given a vector space V, U1 = 0, nic- 01) |cl n(v1). and n(v1 02) & n((1) + n((2)) for all 01, 12 E V.CC R. Given norm n, we can define a (pseudo) metric m as m(x v) n[[r - y)). In a mild abuse of notation, we will often denote this metric using n directly, so that n(z, v) = n((x yl). For any E N. Ip is the norm given by Lp(v) { /p, A norm is a weighted version of n' if n' M for diagonal matrix M.
a function n V R is a norm if n(v1) > 0, n((1)) =
We will use potential shaping. which was first introduced by Ng et al. (199).. First, a potential function is a function & S R. Given a discount 7 we say that R, and Rg differ by potential shaping if for some potential Tb, we have that R2(8, a, s') = (1 a, 8') + 7 ((s') - ((s). We also use S' --redistribution (as defined by (Skalse al. 2022a Given transition function 7, say that R₁ and R2 differ by 5' s'-redistribution if Eg (s.a) [2(s, a, S')] = Es-r((ea)) (s, a, S')]. Finally, we say that R and RS differ by positive linear scaling if R2 a, s') = c R (8, a, s') for some positive constant We will also combine these transformations, For example, say that R
3

---

Published as a conference paper at ICLR 2024
and R2 differ by potential shaping and S' s'-reiistribution if is possible to produce R2 from R1 by applying potential shaping and S'-redistribution (in any order). The cases where R1 and Rg differ by (for example) potential shaping and positive linear scaling, etc, are defined analogously. Finally, will use the following result, proven by (kkals & Abate (202)) in their Theorem 2.6:
Proposition 1. (S, A, T, pos R1; 7) and (S, A, po, R2:71 have the same ordering of policies if and only if R₁ and R2 differ by potential shaping, positive linear scaling, and S' -redistribution.
The "ordering of policies" is the ordering induced by the policy evaluation function J.
EPIC (Gleave et al. 2020) is defined relative to distribution Ds over S and distribution D over A. which must give support to all states and actions. It is computed in several steps. First, let CEPIC R R be the function where CEPIC (B) (s, (1) a, s') is equal
s() + E[yR(s',
A. A, R(s, -R,
where S, Ds and ~ DA. Note that S and S" are sampled independently. Next, let the "Pearson distance" between two random variables and be defined as v(1-p(X Y))/2, where denotes the Pearson correlation. Then the EPIC-distance DEPIC (R1, R2)) is defined to be the Pearson distance between C ("EIIC(R))) (R1) A, S") and CEPIC (S2 A, S"). where again S, Ds and A D Note that EPIIC is implicitly parameterised by Ds and DA-
To better understand how EPIC works, it is useful know that it can be equivalently expressed as CEPIC (R1)
CEPIC (R2)
EEPIC (R1. R2)
SEPIC(R1.5
L2,D
(C.D(CRPIC(B.)) L2, (R2))
where LN is a weighted L2-norm. For details, see Appendix Here CBPIC maps all reward functions that differ by potential shaping to single representative in their equivalence class. This, combined with the normalisation step, ensures that reward functions which only differ by potential shaping and positive linear scaling have distance 0 under DEPIC
DARD (Wulfe et al., 2022) is also defined relative to a distribution Ds over S and a distribution DA over A, which must give support to all actions and all reachable states, but it also requires a transition function т. Let CDARDD R - R. be the function where CDDRRD (H)
is
R(s, a, s') E(7 S, A'), -
- ~R(S" A,))),
where A ~ DA. S A)s,A), and S" T(s', A), Then the DARD-distance DARDD (R1, R2) defined the Pearson distance between CDARD R2 (S, A,S') and CARDD (S, S,)", where again S Ds and A ~ DA. Note that DAARD is parameterised by Ds, D and
2 STARC METRICS
In this section we formally define STARC metrics, and provide several examples of such metrics.
2.1 A FORMAL DEFINITION OF STARC METRICS
STARC metrics are defined relative to an environment, consisting of set of states S, a set of actions
A, transition function т, initial state distribution μ4o and a discount factor ry This means that many of our definitions and theorems are implicitly parameterised by these objects, even when this dependency is not spelled out explicitly. Our results hold for any choice of S, A, T, Mas and 7, as long as they satisfy the assumptions given in Section 1.2] See also Section 2.3
STARC metrics computed in several steps, where the first steps collapse certain equivalence classes in R to a single representative, and the last step measures a distance. The reason for this is that distinct reward functions can share the exact same preferences between all policies. When this is the case, we want them to be treated as equivalent. This is achieved by standardising the reward functions various ways before the distance is finally measured. First, recall that neither potential shaping nor S" s"-redistribution affects the policy ordering in any way. This motivates the first step:
Gleaav et al. 22220) allow different distributions to be used when computing (EPIC(R) (R) and when taking the Pearson distance. However, doing this hreaks some of their theoretical results. For details, see Appendix
4

---

Published as a conference paper at ICLR 2024
Definition 1. A function R R is canonicalisation function if is linear, c(R) and R only differ by potential shaping and S' s'-redisttibution for all E R, and for all R1, Re R, c(R)) (22)) if and only if R₁ and R2 only differ by potential shaping and S' redisiiitiibution.
Note that we require to be linear. Note also that CEPIC and CDAARD are not canonicalisation func- tions in our sense, because we here require canonicalisation functions to simultaniously standardise both potential shaping and s'-redistribution, whereas CEPIC and CDARD only standardise potential shaping. In Section we provide examples of canonicalisation functions. Let us next introduce the functions that
to compute distance:
Definition 2. A metric R R R is admissible if there exists norm p and two (positive) constants é such that E p(,, y) < m(x, v) & u tt.p(z, y) for all x, E R.
metric is admissible if it bilipschitz equivalent to a norm. Any norm is an admissible metric, though there admissible metrics which are not norms Recall also that all norms are bilipschitz equivalent on any finite-dimensional vector space. This means that if m satisfies Definition 2 for one norm, then it satisfies it for all norms. We can now define our class of reward metrics:
Definition 3. A function d: R. x R R is STARC metric (STAndardised Reward Comparison) if there is a canonicalisation function c, a function n that is a norm on Im(c), and a metric m that is admissible on Im(s) s). such that d(RR, R2) m()(Ri), s (2))), where s(R) = ((R)/n(c(It) when n(c(I))) * 0, and el (f) otherwise.
Intuitively speaking, c ensures that all reward functions which differ by potential shaping and S'- redistribution are considered to be equivalent, and division by ensures that positive scaling is ignored as well. Note that if ni((( [t)) = O, then c(Rt) assigns 0 reward to every transition. Note also that Im(e) is the image of c, e applied to the entirety of R. If n is norm on R, then n is also norm on Im(e c). but there are functions which are norms on Im(c) but not on R (c.f. Proposition
In Appendix C we provide a geometric intuition for how STARC metrics work.
2.2 EXAMPLES OF STARC METRICS
In this section, we give several examples of STARC metries. We begin by showing how to construct canonicalisation functions. We first give simple and straightforward method:
Proposition 2. For any policy n, the function e: R R given by
el (())ss a, 8¹) Egg-r(s.o) a - - (S)]
a,
is a canonicalisation function. Here V is computed under the reward function R given as input to We call this function Aajuuted Levelling (VAL).
The proof, as well as all other proofs, are given in the Appendix. Proposition 2 gives us an easy way to make canonicalisation functions, which are also easy to evaluate whenever / is easy to approximate. We next give another example of canonicalisation functions:
Definition 4. A canonicalisation function e is minimal for norm n if for all R we have that n(c(R)) (RR) for all R' such that R and R' only differ by potential shaping and S'rreiistibbution
Minimal canonicalisation functions give rise to tighter regret bounds (c.f. Section 3 and Appendix F-. not a given that minimal canonicalisation functions exist for a given norm n, or that they are unique. However, for any weighted L2-norm, this is the case:
Proposition 3. For any weighted L2-norm, minimal canonicalisation finctiinn exists and is unique.
A STARC metric can use any canonicalisation function c. Moreover, the normalisation step can use any function that is a norm on Im(c). This does of course include the Lnrnomm, Lg-norm, -nom, and so on. We next show that max J(T) min, J(r) also is norm on Im(e): Proposition 4. If is canonicalisation function, then the function n R - R given by n(R) = max, [(T) - min, (Tx) is a norm on Im(c).
Forr example, the unit ball of does have be convex, symmetric around the origin.
5

---

Published as a conference paper at ICLR 2024
For the final step of course have that any norm is admissible metric, though some other metries are admissible as well [ To obtain a STARC metric, we then pick any canonicalisation function c, norm and admissible metric m, and combine them as described in Definition [3] Which choice of n, and m is best in a given situation may depend on multiple considerations, such as how easy work with theoretically, or how well they together track they are to compute, how easy they worst-case regret (c.f. Section 3 and 4).
2.3 UNKNOWN TRANSITION DYNAMICS AND CONTINUOUS ENVIRONMENTS
STARC metrics depend on the transition function т, through the definition of canonicalisation functions (since 5" -r-rriistribution depends r). Moreover, is often unknown in practice. However, it is important to note that while STARC metrics depend on T, there are STARC metrics that can be computed without direct access T. For example, the VAL canonicalisation function (Proposition 2 only requires that we can sample from т, which is always possible in the reinforcement learning setting. Moreover, if we want evaluate learnt reward function in an environment that different from the training environment, then we can simply use the from the evaluation environment. As such, we do not consider the dependence on T to be meaningful limitation. Nonetheless, it is possible to define STARC-like pseudometrics that do not depend on at all, and such pseudometrics also have some theoretical guarantees (albeit guarantees that are weaker than those enjoyed by STARC metrics). This option is discussed in Appendix F:
Moreover, we assume that S and A are finite, but many interesting environments are continuous. However, it is important to note that while our theoretical results assume that S and A are finite, it is still straightforward to compute and use STARC metrics in continuous environments (for example, using the VAL canonicalisation function from Proposition 2). We discuss this issue in more detail in Appendix D In Section we also provide experimental data from a continuous environment.
3 THEORETICAL RESULTS
In this section, we prove that STARC metrics enjoy several desirable theoretical guarantees. First, we note that all STARC metrics are pseudometries on the space of reward functions, R: Proposition 5. All STARC metrics are pseudometrics on R.
This means that STARC metrics give well-defined notion of "distance" between rewards. Next, we characterise the cases when STARC metrics assign two rewards a distance of zero:
Proposition All STARC metrics have the property that di R1, R2) = 0 if and only if Rı and R2 induce the same ordering of policies.
This means that STARC metrics consider two reward functions to be equivalent, exactly when those reward functions induce exactly the same ordering of policies. This is intuitive and desirable.
For pseudometric d on R to be useful, it is crucial that it induces upper bound on worst-case regret. Specifically, we want it to be the case that if d(R,, R2) is small, then the impact of using Ri instead of R1 should also be small. When pseudometric has this property, we say that is sound:
Definition 5. A pseudometric d on R is sound if there exists positive constant U, such that for any reward functions R2 and R2, two policies गi and T2 satisfy that J2(m2) > J2(TI), then
(m) (1() U (max Ji(m) min (T)) R1, R2).
Let us unpack this definition. JI ( ) is the regret, as measured by Ri of using policy 22 instead of T1. Division by max, JI(TT) min, J1 (iT) normalises this quantity based on the total range of R₁ (though the term is put on the right-hand side of the inequality, instead of being used as a denominator, in order avoid division by zero when max, (T) min, (1( = 0). The condition that Jz( (22) > J2(m1) says that R2 prefers 22 over mı Taken together, this means that pseudometric d on R is sound d R1, R2) gives an upper bound on the maximal regret that could
*For example, if m1 y) is the angle between and when x,, y * 0, and we define m00, 0) and m(a, 0) x/2 for a: # O, then m is also admissible, even though m is

---

Published as a conference paper at ICLR 2024
be incurred under R1 if arbitrary policy is optimised to another policy л2 according to Rg. is also worth noting that this includes the special case when Ti is optimal under R1 and T2 is optimal under R2. Our first main result is that all STARC metrics are sound:
Theorem 1. All STARC metrics are sound.
This means that any STARC metric gives us an upper bound on worst-case regret. Next, we will show that STARC metrics also induce lower bound worst-case regret. It may not be immediately obvious why this property is desirable. To see why this is the case, note that if a pseudometric on R does not induce a lower bound on worst-case regret, then there are reward functions that have low worst-case regret, but large distance under d. This would in turn mean that d is not right, and that it should be possible improve upon In other words, we want small distance under to be both sufficient and necessary for low worst-case regret, then d must induce both upper and lower bound on worst-case regret. As such, we also introduce the following definition:
Definition 6. A pseudometric d on R is complete if there exists positive constant L, such that for any reward functions R1 and R2, there exist two policies Ti and such that J2( > (2(T1) and
J1 (mT) - J1 (m2) L (max (T) - min JI(TT) d(R,, R2),
and moreover, if both max, J/ (T) min, J1 (T) = 0 and max, J2(x) min, J2(TT) = 0, then we have that d( R1, R2)
The last condition is included to rule out certain pathological edge-cases. Intuitively, if is sound, then a small d is sufficient for low regret, and if is complete, then a small is necessary for low regret. Soundness implies the absence of false positives, and completeness the absence of false negatives. Our second main result is that all STARC metrics are complete:
Theorem 2. All STARC metrics are complete.
Theorems D and 2 together imply that, for any STARC metric d, we have that a small value of is both necessary and sufficient for low regret. This means that STARC metrics, in certain sense, exactly capture what means for two reward functions to be similar, and that we should not expect to be possible to significantly improve upon them. We can make this claim formal as follows:
Proposition 7. Any pseudometries on R that are both sound and complete are bilipschitz equivalent.
This implies that all STARC metrics are bilipschitz equivalent. Moreover, any other pseudometric on R that induces both upper and lower bound on worst-case regret (as we define it) must also be bilipschitz equivalent to STARC metrics.
In Appendix A and we provide extensive analysis of both EPIC and DARD, and show that they fail to induce similar theoretical guarantees.
EXPERIMENTAL RESULTS
In this section we present our experimental results. First, we demonstrate that STARC metrics provide better estimate of regret than EPIC and DARD in randomly generated MDPs. We then evaluate STARC metric a continuous environment.
4.1 1 LARGE NUMBERS OF SMALL. RANDOM MDPs
Our first experiment compares several STARC metrics EPIC, DARD, and a number of other non- STARC basclines. In total, our experiment covered 223 different pseudometrics (including rollout regret), derived by creating different combinations of canonicalisation functions, normalisations, and distance metrics. For details, see Appendix G.3 For each pseudometric, we generated large number of random MDPs, and then measured how well the pseudometric correlates with regret across this distribution. The regret is defined analogously to Definition (5 5nd 6 except that only optimal policies are considered for details, see Appendix G.2 We used MDPs with 32 states, actions, 7 0.95, a uniform initial state distribution, and randomly sampled sparse -enemmteriii transition functions, and for each MDP, we generated several random reward functions. For details on the random generation process, Appendix G We compared 49,152 reward function pairs (Appendix G.4) and
7

---

Published as a conference paper at ICLR 2024
used these estimate how well each pseudometric correlates with regret. We show these correlations in Figure [] and the full data is given in a table in Appendix[H) HH In Appendix H.I we also provide tables that indicate the impact of changing the metric m the normalisation function n.
The canonicalisation functions we used were None (which simply skips the canonicalisation step), C'EIIC, CDARD, Mi nimmmmall 1 Potent ial (which is the minimal "canonicalisation" that removes potential shaping but not S'-redistribution, and therefore is easier to compute), VALPotent.o (which is given by R[s, 0, ) - (*(s) + ?V"(s")), and VAL (defined in Proposition 2 For both CEPIC and CDARD both Ds and DA were chosen to be uniform over S and A. For both VALPotent and VAL, π was chosen to be the uniformly random policy. Note that VAL the only canonicalisation which removes both potential shaping and S' r'-rriistribution, and thus the only one that meets Definition [ - for this reason, it is listed as "STARC-VAS VAI." in Figure For the full details about which pseudometrics were chosen, and why, see Appendix G73
None
EPIC
DARD
Potential
WAL Potential
0.6
STARC VAL
Conraatton
0.2
Figure 1: This figure displays the correlation to regret for several pseudometrics. Each point represents one pseudometric, i.e. one unique combination of canonicalisation c, normalisation n. and distance metric m. They are grouped together based on their canonicalisation function, with each column corresponding to different canonicalisation function. Pseudometrics which skip canonicalisation or normalisation are shown in grey. The versions of EPIC and DARD that use the L2 norm for both normalisation and distance metric in Gleave et al. (2020) and Wulfe et al. (2022). The STARC metries, which are canonicalised using VAL., are reliably better indicators of regret than the other pseudometries.
highlighted in red, these are the original versions given
As we can see, the STARC metrics based on VAL perform noticeably better than all pre-existing pseudometrics for instance, the correlation of EPIC to regret is 0.778, DARD's correlation is 0.782, while VAL's s correlation is 0.856 (when using Le for both n and m, which is the same as EPIC and DARD). Out of the 10 best pseudometrics, use VAL (and the other both use VALPotents ial). Moreover, for each choice of n and m, we have that the VAL canonicalisation performs better than the EPIC canonicalisation in 40 out of 42 cases [] Taken together, these results suggest that STARC metrics robustly perform better than the existing alternatives.
Our results also suggest that the choice of normalisation function and metric can have a significant impact on the pseudometric's accuracy. For instance, when canonicalising with VAL, it is better to use the L1 norm than the Le norm for both normalisation and taking the distance this increases the correlation with regret from 0.856 to 0.873. Another example is the EPIC canonicalisation - when paired with the weighted Lx norm for normalisation and the (unweighted) L norm for taking the distance, instead of using the Le norm for both, its correlation decreases from 0.778 to 0.052. As we can see Figure [ this effect appears to be more prominent for the non-STARC metrics. Another thing to note is that it seems like not canonicalising for S'-redistribution, but only when a (r-)weighted norm is used. This may be because - w-eeghtted norms set all impossible transitions to 0, and reduce the impact of very unlikely transitions; plausibly, this could in practice be similar to canonicalising for S' "'rreiitributton. When using VAL, L1 was the best unweighted norm for both and n in experiment.
can perform as well as VAL despite
'The only exceptions are when no normalisation is used and m Lo. and when n = weighted- and m wei ghtgghtth.a.. -Tog. However, in the first case, both the EPICC-ased and the VAI pseudometric perform badly (since normalisation is used), and in the second case, the difference between them is not large.
8

---

Published as a conference paper at ICLR 2024
4.2 THE REACHER ENVIRONMENT
Our next experiment estimates the distance between several hand-crafted reward functions in the Reacher environment from MuloCo (Todorov et al. 2012). This is a deterministic environment with an 1 Il-dimensional continuous state space and a 2-dimensional continuous action space. The reward functions we used are:
1. GroundTruth: The Euclidean distance to the target, plus a penalty term for large actions.
2. PotentialShaper GroundTruth with random potential shaping.
3. SecondPeak: We create second target in the environment, and reward the agent based on both its distance to this target, and to the original target, but give greater weight the original target.
4. Random: A randomly generated reward, implemented as an affine transformation from
8, a, s' real numbers with the weights and bias randomly initialised.
5. Negative:
Returns - -GroundTruth..
We expect GroundTruth to be equivalent to PotentialShapa orthogonal to Random, and opposite to Negative ive. We used the VAL. canonicalisation function with the uniform policy, and normalised and took the distance with the L2-norm. This pseudometric was then estimated through sampling; full details can be found in Appendix D [and The results of this experiment are given in Table [ As we can see, the relative ordering of the reward functions match what we expect. However, the magnitudes of the estimated distances are noticeably larger than their real values; for example, the actual distance between GroundTruth and Potential maniiallaaped is 0, but it is estimated as = 0.9. The reason for this is likely that the estimation involves summing over absolute values, which makes all noise positive. Nonetheless, for the purposes of ranking the rewards, this is not fundamentally problematic.
similar to SecondP eak,
Potent i Shaped 0.8968
SecondPeak
Random
Negative 1.706
1.2570
1.3778
Table 1:
This figure displays the estimated distance (using each reward function the Reacher environment and the GroundTruth reward function.
VAL, L2, and m I,2) between
DISCUSSION
We have introduced STARC metrics, and demonstrated that they provide compelling theoretical guarantees. particular, we have shown that they are both sound and complete, which means that they induce both an upper and lower bound on worst-case regret. As such, a small STARC distance both necessary and sufficient to ensure that two reward functions induce a similar ordering of policies. Moreover, any two pseudometrics that are both sound and complete must be bilipschitz equivalent. This means that any pscudometric on R that has the same theoretical guarantees as STARC metrics must be equivalent to STARC metrics. This means that have provided what essentially a complete answer to the question of how to correctly measure the distance between reward functions. Moreover, our experiments show that STARC metrics have noticeably better empirical performance than any existing pseudometric in the current literature, for a wide range of environments. This means that STARC metrics offer direct practical advantages, in addition their theoretical guarantees. In addition to this, STARC metrics are both easy to compute, and easy to work with mathematically. As such, STARC metrics will be useful for both empirical and theoretical work on the analysis and evaluation of reward learning algorithms.
Our work can be extended number of ways. First of all, would desirable to establish more conclusively which STARC metrics work best in practice. Our experiments are indicative, but not conclusive. Secondly, our theoretical results assume that and A are finite; it would be desirable to generalise them to continuous environments. Third, we use fairly strong definition of regret. We could consider some weaker criterion, that may allow for the creation more permissive reward metrics. Finally, work considers the MDP setting it would be interesting also consider other classes environments. We believe that the multi-agent setting would be of particular interest, since it introduces new and more complex dynamics that not present in the case of MDPs.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENTS
The authors wish to acknowledge and thank the financial support of the UK Research and Innovation (UKRT) [Grant ref EP/S022937/1] and the University of Bristol.
REFERENCES
Paul Christiano, Jan Leike, Tom B. Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep reinforcement learning from human preferences, 2017.
Tom Everitt, Victoria Krakovna, Laurent Orseau, Marcus Hutter, and Shane Legg. Reinforcement learning with corrupted reward channel. CoRR, abs/1705.08417, 2017. URL http::tp/a////
org/abs / 08417
Eugene A.
Feinberg and Uriel G. Rothblum. Splitting randomized stationary policies in total-reward
markov decision processes. Mathematics of Operations Research, 37(1):129-153 2012. ISSN
0364765X, 15265471, URL
Adam Gleave, Michael Dennis, Shane Legg, Stuart Russell, and Jan Leike. Quantifying differences in reward functions, 2020. URL/sttps//arxvv.crr////bp
13900
Borja Ibarz, Jan Leike, Tobias Pohlen, Geoffrey Irving, Shane Legg, and Dario Amodei. Reward learning from human preferences and demonstrations in Atari. In Proceedings of the 32nd International Conference Neural Information Processing Systems, volume 31, pp. Montréal, Canada, 2018. Curran Associates, Inc., Red Hook, NY, USA.
Erik Jenner, Herke van Hoof, and Adam Gleave. Calculus on MDPs: Potential shaping as a gradient, 2022. UtL wttp//aaavvvv/ee///ee/eee/e.aeva org abs / 2208.000227
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization, 2019.
Andrew Y Ng and Stuart Russell. Algorithms for inverse reinforcement learning. In Proceedings of the Seventeenth International Conference on Machine Learning, volume 1, pp. 663-670, Stanford, California, USA, 2000. Morgan Kaufmann Publishers Inc.
Andrew Y Ng, Daishi Harada, and Stuart Russell. Policy invariance under reward transformations: Theory and application to reward shaping. Proceedings of the Sixteenth International Conference Machine Learning, pp. 278-288 287, Bled, Slovenia, 1999. Morgan Kaufmann Publishers Inc.
Alexander Pan, Kush Bhatia, and Jacob Steinhardt. The effects of reward misspeciffication: Mapping 03544
and mitigating misaligned models, 2022.
Gavin Rummery and Mahesan Niranjan. On-line Q-learning using connectionist systems, vol- 37, University of Cambridge, Department of Engineering Cambridge, UK, 1994.
Stuart Russell and Peter Norvig. Artificial Intelligence: A Modern Approach. Pearson, 4 edition, 2020.
Joar Skalse and Alessandro Abate. Misspecificatiin inverse reinforcement learning, 2023.
Joar Skalse, Matthew Farrugia-Roberts, Stuart Russell, Alessandro Abate, and Adam Gleave. In- variance in policy optimisation and partial identifiability in reward learning. arXiv preprint vrXiv:2203.07475 2022a.
Joar Skalse, Niki Howe, Krasheninnikov Dima, and David Krueger. Defining and characterizing reward hacking. In Proceedings of the 33rd International Conference on Neural Information Processing Systems, 2022b.
Richard S Sutton and Andrew G Barto, Reinforcement Learning: An Introduction. MIT Press, second edition, 2018. ISBN 9780262352703.
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 5026-5033 2012. doi: 00.1109/ROOS.202..6666
10

---

Published as a conference paper at ICLR 2024
Blake Wulfe, Logan Michael Ellis, Jean Mercat, Rowan Thomas McAllister, and Adrien Gaidon. Dynamics- aware comparison of learned reward functions. International Conference on Learning Representations, 2022. URL http:///weerrroeeeeeeeeeeeoeoena
Simon Zhuang and Dylan Hadfield-Menelll. Consequences of misaligned Al. CoRR, abs/2102..368% 2021. URL /ttpps///aarii....or/////22....0

---

Published as a conference paper at ICLR 2024
A COMMENTS ON EPIC
In this appendix, we will show that EPIC has a number of undesirable properties. For the sake of readability, the proofs of the theorems this section are given in Appendix F33 rather than here.
First of all, while EPIC does induce an upper bound on a form of regret, this is not the type of regret that is typically relevant in practice. To demonstrate this, will first provide generalisation of the regret bound given in Gleave et al. (2020):
Theorem 3. There exists positive constant U. such that for any reward functions R₁ and R2, and any and Po- if two policies πı and TT2 satisfy that J2( 2 J2 (T)), then have that
(1(m) (12) < U L2(R1) DEPIC (R1, R2).
Theorem 3 covers the special case when Ti is optimal under R1, and T2 is optimal under Rg. This means that this theorem is generalisation of the bound given in Gleave et al. (2020). However, we will next show that EPIC does not induce regret bound of the form given in Definition
Theorem 4. EPIC is not sound, for any choice of T poo
These results may at first seem paradoxical, since the definition of soundness is quite similar to the statement of Theorem 3 The reason why these statements can both be true simultaneously is that L (2g) can be arbitrarily large even as max, (T) mill, J1 (IT becomes arbitrarily small. Moreover, we argue that it is more relevant to compare J1 ( -1 (1 (2)) to max, (1)===))mnn J1()). rather than (R1). First of all, note that it is not informative to just know the absolute value of (m) J1 (T2), since this depends on the scale of R₁. Rather, what we want to know how much reward we might lose, relative to the total amount of reward that could be had. This quantity is measured by max, (T) - ming J1 (T)) not L2 (2)). For example, (11) (1(22) = e, but max, [1(TT- minl, J1 (T) is just barely larger than then this should be considered to be large loss of reward, even if (R1) >> c. For this reason, we consider the regret bound given in Definition to
be more informative than the regret bound given in Gleave et al. (2020) and in Theorem 3
Another relevant question is whether EPIC induces a lower bound on worst-case regret. We next show that this is not the case, regardless of whether consider the type of regret used in Gleave et al. 2020), or the type of regret used in Theorem 3 or the type of regret used in Definition
Theorem There exist rewards R1, R2 such that DEPIC Ri, ; R2) > 0, but where Rí and R2 induce the same ordering of policies for any choice of T poo
This means that EPIC cannot induce a lower bound on worst-case regret, for almost any way of defining regret. Together, we think these results show that EPIC lacks the theoretical guarantees that we desire in reward function pseudometric.
B COMMENTS ON DARD
In this appendix, we briefly discuss some of the properties of DARD. In so doing, we will criticise some the choices made in the design of DARD, and argue that STARC metrics offer better way to incorporate information about the environment dynamics.
To start with, recall that DARD uses the canonicalisation function DARDD, which the function where (DARD(R) (s, 3') is given by
R(s, a, 8') ElyR(s' A, - -
where A DA.
T(s, A), and S" T(8', A). Moreover, also recall that ODRRD only is designed to remove potential shaping, whereas the canonicalisation functions we specify in Definition I are designed to remove both potential shaping and S'-rrdistribution.
Now, first and foremost, note that while CDRRD is designed to remove potential shaping, it does this in a somewhat strange way. In particular, while is shown in Wulfe et al. (2022) that CBARD (R)) CARDD (R2) if R1 and R2 differ by potential shaping, it in general not the case that R and DARD (R) differ by potential shaping. To see this, note that the term R(S" A, S,)") depends on both and s', which a potential shaping function cannot do. This has few important consequences.
12

---

Published as a conference paper at ICLR 2024
In particular, it is unclear if CDARRD CDARD (Rz) only if R1 and R2 differ by potential shaping. It is also unclear if R and C'AAR (R) in general even have the same policy ordering. Note also that CDDRRD (R) is not monotonic, in the sense that CDDRD (CDARD (R)) and CDDRD (R) may
be different. This seems undesirable.
Another thing to note is that E[CDARD (R) A,, A")] may not be O. This means that it is unclear whether or not DARD can be expressed in terms of norms, like EPIC can (c.f. Proposition [2]. It is also unclear if DARD induces an upper bound on regret, since Wulfe et al. (2022) do not provide regret bound. The fact that CDARD( (t) is not a potential shaping function does not necessarily imply that DARD does not induce an upper bound on regret. However, without proof, there a worry that there might be reward pairs with a bounded DARD distance but unbounded regret.
Yet another thing to note is that, while DARD designed to be used cases where the environment dynamics are known, it can still be influenced by the reward of transitions that are impossible according to the environment dynamics. For example, the final term of CDARDD())ss,C a, s') can be influenced by impossible transitions. This gives us the following result:
Proposition 8. There exists transition functions T and initial state distributions μoo for which DARD not complete.
Proof. Consider an environment (S,A, T, (40, 7) where S = {81, 82, 83). A = {ai, 02). and where the transition function is given by T(51, a) 52. T (52, a) = $3, and 7(53, a) 81, for any a E A. We may also suppose μi = 51, and 7 = 0.9.
Next, let Rí Rs 0 for all transitions which are possible under т, but let Ri [s ai , R1 (s, 02. s') = 0, (s a1.6 s') = 0, and R2 o²)s²) = for all transitions which are impossible under т. Now D (R1, R2) > 0, even though (S, T. No. R1,7) and (S, A, T, po, R2,7) have
exactly the same policy ordering.
Together, the above leads us to worry that DARD might lead to misleading measurements. Therefore, we believe that STARC metrics offer better way to incorporate knowledge about the transition dynamics into the reward metric, especially in the light of our results from Section 3
C A GEOMETRIC INTUITION FOR STARC METRICS
In this section, we will provide a geometric intuition for how STARC metrics work. This will help to explain why STARC metrics are designed in the way that they are, and how they work. It may also make it easier to understand some of our proofs.
First of all, note that the space of all reward functions R. forms an [S]]AAl]ss-immmssiooo dimeesiional vector space. Next, recall that if two reward functions R3 and R2 differ by (some combination of) potential shaping and s'-redistribution, then Ri and R2 induce the same ordering of policies. Moreover, both of these transformations are additive. In other words, they correspond to a set of reward functions [Ro), such that R1 and R2 differ by combination of potential shaping and S' -'-reiistribution if and only if R1 R2 { Roo). This means that {Ra} is a linear subspace of R, and that for any reward function Rt the set of all reward functions that differ from by a combination of potential shaping and 5" s'-rrdiitributtin together form an affine subspace of R.
canonicalisation function is a linear map that removes the dimensions that are associated with [Ro). In other words, they map R to an |S[([A] -immensionall subspace of R in which reward functions differ by potential shaping or S' "rrreisttibutton. The null space of a canonicalisation function is always ( Ro). The canonicalisation function that is minimal for the norm is the orthogonal map that satisfies these properties, whereas other canonicalisation functions are non-orthogonal.
When we normalise the resulting reward functions by dividing by vector space onto the unit ball of n (except the zero reward, which remains at the origin). The metric m then measures the distance between the resulting reward functions the surface of this sphere
n, project the entire
13

---

Published as a conference paper at ICLR 2024
To make this more clear, may be worth considering the case of non-sequential decision making. Suppose we have finite of choices C. and utility function U R. Given distributions D1, D2 over C, we say that we prefer D1 over D2 if [U[[]] > E.-D,[U(c)] The set of all utility functions over C forms |Cl-dimensional vector space. Moreover, in this setting, is well-known that two utility functions U,, U2 induce the same preferences between all possible and only they differ by an affine transformation. Therefore, we wanted to represent the set of all non-equivalent utility functions over C, we may consider requiring that U((o) for some co C, and that L2(U)=
distributions over
unless (cc) = 0 for all c E C. Any utility function over C is equivalent to some utility function in this set, and this set in turn be represented the surface of a (IC) 1) -immenssio sphere, together with the origin.
This is essentially analogous the normalisation that the canonicalisation function and the normali- sation function n perform for STARC metrics. Here is analogous to the set of all trajectories, the trajectories.
trajectory return function G is analogous U, and policy induces distribution is worth knowing that affine transformations of the trajectory return function, G, correspond exactly potential shaping and positive linear scaling of R (see [Skalse al., 2022a their Theorem 3.1 However, while the cases are analogous, it is not direct correspondence, because not all distributions over trajectories can be realised as a policy
given MDP.
Another perspective that may help with understanding STARC metrics comes from considering occupancy measures. Specifically, for given policy ग,, let its occupancy measure 17" be the | dimensional vector in which the value of the (s, a, s') 'th dimension is
7 PP A; = a, = =d).
Now note that J(T) = 17" R. Therefore, by computing occupancy measures, we can divide the computation of / into two parts, the first of which is independent of It, and the second of which is linear function. Moreover, let Ω = {n7 т II} be the set of all occupancy measures. We now have that the policy value function J of reward function R can be visualised as linear function this set. Moreover, if we have two reward functions R,, R2, then they can be visualised as two different linear functions this set:
14

---

Published as a conference paper at ICLR 2024
R
R2
Ω
located in | (00--1))iimnn ddimensional affine subspace of IR (||A||S) and contains set which is open in this space (Skalse & Abate 2023). Moreover, it can be represented as the convex hull of finite set of points (Feinberg & Rothblum 2012 It thus polytope.
From this image, it is visually clear that the worst- case regret of maximising R1 instead of R2, should be proportional to the angle between the projections of R₁ and R2 onto Ω. Moreover, this is what STARC metrics measure; any STARC metric is bilipschitz equivalent to the angle between reward functions projected onto Q. This in should in turn give an intuition for why the STARC distance between two rewards provide both an upper and lower bound on their worst-case regret.
D APPROXIMATING STARC METRICS IN LARGE ENVIRONMENTS
In small MDPs, STARC metrics can be computed exactly (in time that is polynomial in [S] and [A[). However, most realistic MDPs are too large for this be feasible. As such, will here discuss how to approximate STARC metrics in large environments, including continuous environments.
First, recall the VAL canonicalisation function (Proposition 2 given by
el (R)(8, a, s') = Ess~r(s.a) [R(s, a, S') V (*) + (S)]
where x can be any (fixed) policy. This canonicalisation function is straightforward to approximate in any environment where reinforcement learning can be used, including large-scale environments. To do this, first pick arbitrary policy æ, such e.g. the uniformly random policy. Then compute an approximation of V* this can be done using a neural network updated with on-policy Bellman updates (Sutton & Barto 2018). Note that ı should be updated, and must remain fixed. Then simply estimate the expected value of R(s, a, S*) V*(s) + +VV((S") by sampling from т. This approximation can be computed in any environment where it is possible sample from and approximate V (which is to say, any environment where reinforcement learning is applicable). Note that we do not require direct access to т, we only need be able to sample from it.
Next, note that if v is an nz-dimensional vector, and L/ is the uniform distribution over (1...n}, mn), then
(v) (n- [1:-)
n/ [o>""0o::?"
This in turn means that
1/p
V Lp
U2
w;
Ei-u
[T (.p(1))
R [ 1/
Ry-ul I p
since the -PP--rerms cancel out. Therefore, the normalisation step and distance step can also be estimated through sampling: simply sample enough random transitions to approximate each of the expectations in the expression above. Indeed, this can even be done if the state space and action space continuous. Recall that the -orm of an infiniteddimensional vector is defined
L (J. ([l
1/p
where X E R This value also be approximated through sampling.
15

---

Published as a conference paper at ICLR 2024
It is also possible approximate division by and taking the distance with using the Pear- son distance, which is what EPIC does. particular, let D be a distribution over x A x S that assigns positive probability to all transitions, and let R1, R2 be reward functions such that (. (R, A,5")] = -...A.S-p(Ri(S. A,5") = 0. We then have that the Pearson distance /(1 - pl (1 A, S"), R,(S, A,5) between R1 (1 and R2(S, S"), where S, A. D, is equal to
1 L2, (L, L2,w L2,)(Ra)
Ri
R2
where W is a weight matrix depending on DD and denotes the Pearson correlation. For details, see the proof of Proposition 12 For this identity to hold, it is crucial that (ss.A.S:-([[(S.. S')] 0. However, this can easily be ensured; for an arbitrary canonicalisation function C1, let 22 (R) ei (R) ES S. (R)( A, S') If ei valid canonicalisation function, then so is C2. The Pearson correlation can of course be estimated through sampling.
E [ (S, A, S*)
E PROOFS OF MISCELLANEOUS CLAIMS
In this Appendix, we provide proofs for several miscellaneous claims and minor propositions made throughout the paper, especially in Section 2.2
Proposition 9. For any policy æ, the function e: R- - R given by
c(R)(s, a, s')= Es
is canonicalisation function.
Proof. To prove that is canonicalisation function, we must show
1. that is linear,
2. that c(R) and R only differ by potential shaping and S"-redistribution, and
3. that c(Ri) c( (2) if and only if Ri and Ra only differ by potential shaping and S redistribution.
We first show that c is linear. Given state s, let us be the | vector where
[ a,,, 8"]
TPS, 8 A, a, S, s²):
where the probability given for trajectory that generated from and т, starting s. Now note that (=(s)= = U, R, where R is represented as vector. Using these vectors {v.}. it is possible to express as linear transformation.
To see that e( R)) and R differ by potential shaping and S'-redistribution, is sufficient to note that VE acts as potential function, and that setting R2(s, a, s') Es [R1 (s, a, S')] a form of S' S'-redistribution.
To see that c(Ri) = of (2)) if R1 and R2 differ by potential shaping and S" s"-redistribution, first note that if R2 and Rg differ by potential shaping, that Rg a, s') s')= RR (s, a, s') + ( <(ss) for some 4. then V (s) (TT ((s) (see e.g. Lemma B. in Skalse et al. 2022a). This means that
el c(R2) a, 8¹) a (S" V.5 (s)]
a, ((S') ((s) + (VT(S)))))))))))))))))))) + (V7 +()))
= (s, + (T"(5") - (s)
= cc( =c(Ri)(s,
To see that c(Ri) c(l2) only if R and R2 differ by potential shaping and S'-redistribution, first note that we have already shown that R and c( R) differ by potential shaping and S' s'rredistribution for all R. This implies that R and cl R1) differ by potential shaping and S "'-reistrribuiinn and likewise for R2 and of R2). Then of R c(22), we can combine these transformations, and obtain that R2 and Ra also differ by potential shaping and S' s'-redistribution. This completes the proof. n
16

---

Published as a conference paper at ICLR 2024
Note that this holds regardless of which environment V is calculated in. Therefore, V could be computed in an environment that is entirely distinct from the training environment. For example, V could be computed in environment (and using a policy) designed specifically to make this computation easy.
Proposition 10. For any weighted I--noorm a minimal canonicalisation function exists and is unique.
Proof. Let Rg be the reward function that is 0 for all transitions. First note that the of all reward functions that differ from Rg by potential shaping and S'-redistribution form a linear subspace of R. Let this space be denoted by y, and let X' denote the orthogonal complement of y in R. Now any reward function R E R can be uniquely expressed in the form Rx + Ry, where Rx E X and Ry E y. Consider the function e R R where c(R) = Rx. Now this function is a canonicalisation function such that n(c(R) RR) < R for all R' such that cl (R) c(R'), assuming that n is a weighted L2-norm
To see this, must show that
1. cis linear,
2. o(R) and R differ by potential shaping and S' S'-redistribution,
3. c(R1) = c( R2) if R1 and Rg differ by potential shaping and S'-redistribution, and
4. n(c( R)) x n R') for all R' such that c(R) c(R').
follows directly from the construction that e is linear. To see that cR and R differ by potential shaping and 5" 3'-reeistribution, simply note that c(It) = R - Ry, where Ry is given by combination of potential shaping and S'-redistribution of Rg. To see that c(Ri) = ((
) if Rú and R2 differ by potential shaping and S'-redistribution, let Rg = R4 + R', where It' is given by potential shaping and S' s'-redistribution of Ro, and let R3 = Rx + Ry, where Rxx E X and Ry E Y. Now c( Rx. Morcover, R2 Rx Ry + R'. We also have that R' E y. We can thus express R2 as Rx + (Ry + R²), where Rx E X' and (Ry + R²) E y which implies that cf R22) = Rx- Therefore, if R₁ and R2 differ by potential shaping and S' d'-redistribution. then c( (R1)) (R2)). To see that c( = c( Rt) only if Ri and Rg differ by potential shaping and S'-redistribution, first note that we have already shown that R and c(It) differ by potential shaping and S'-redistribution for all R. This implies that Rj and c( R2) differ by potential shaping and S sy-rrdistributton, and likewise for R2 and c( R2)) Then if c(R = c(Rg), we can combine these transformations, and obtain that Ri and R2 also differ by potential shaping and S" s--rrdistribution.
To see that n(c(R)) & n(R') for all R' such that c(R) c( RR)), first note that if c(R) c(R'), then R = Rx + Ry and R' = Rx + Ry, where Rx X' and Ry, Ry E y. This means that n()(()) = n(xx), and n(It)= n(Rx + Ryy). Moreover, since n is a weighted L2-norm, and since Rx and Ry are orthogonal, we have that n Rx + Ry) (n(xx)² + (Ry)² > n( (Rxx) This means that nnc(RR)= & n(R").
To see that this canonicalisation function the unique minimal canonicalisation function for any weighted L2- norm n, consider arbitrary reward function R. Now, the set of all reward functions that differ from R by potential shaping and S' rreeisstribution forms an affine space of R, and a minimal canonicalisation function must map R to a point R' in this space such that ni R') & n (R")) for all other points R" in that space. If n is a weighted L--norm, then this specifies a convex optimisation problem with unique solution.
Note that this proof only shows that minimal canonicalisation function exists and is unique when a (weighted) Lz-norm. does not show that such a canonicalisation function only exists for these norms, nor does it show that it is unique for all norms.
Proposition 11. If is canonicalisation function, then the function R R. given by n(R) max, (T)) - ming (TT) is a norm on Im([c.
Proof. To show that a function n is norm on Im(c), we must show that it satisfies:
17

---

Published as a conference paper at ICLR 2024
1. n(R) > 0 for all E Im(c).
2. n(R) 0 if and only
Ro for all R Im(c).
3. n(a- R) a (R) for all R Tm((c) and all scalars a.
4. (R + R2) & (R)) + n (2) for all R1, Ro E Im(()..
Here Ry the reward function that is 0 everywhere. It is trivial to show that Axioms and are satisfied by n. For Axiom 2, note that nı (t) = 0 exactly when max, J(z) = min, J(x). If R is Ro. then ((x) = 0 for all т, and so the "if" part holds straightforwardly. For the "only if" part, let R be reward function such that max, [==
min, J(z). Then R and Rg induce the same policy ordering under and po. which means that they differ by potential shaping, S' S'-redistribution, and positive linear scaling (see Proposition DT. Moreover, since Rg is 0 everywhere, this means that R and Ry in fact differ by potential shaping and S'-redistribution. However, from the definition of canonicalisation functions, if R1, R2 Im(c) differ by potential shaping and S' S'-redistribution, then it must be that R R2. Hence Axiom 2 holds as well.
We can show that Axiom holds algebraically:
n R1 + R2) max (T) + J2(x)) min(J1(n) (T) J2(
"
$ max J1 (T) max J2(TT) min Ji (T) min J2(x))
"
= (max J1 (T) - min J1 (T)) (max - -min J2(T)) (RR)) + n R2))
x
This means that n(R) max; ( min, J(x) a norm on Im(c).
This means that we can normalise the reward functions so that max, J(z) - min, J(T) = 1, which nice. This proposition will also be useful in later proofs. Proposition 12. EPIC can be expressed
CEPIC (R2) (TED((EPIC(Ra)) Ln (CEPIC (RPII((2))
CEPIC (RG)
DEPIC(RR, R2) = = I2,D
where L2,D is a weighted Lz-norm.
Proof. Recall that by default, DEPIC R1, R2) is defined to be the Pearson distance between CEric (S, A, S') and (B) A'), where S, Ds and A ~ DA. and where the "Pearson distance" between two random variables X and Y be defined as /(1- p(X, Y))/2, where p denotes the Pearson correlation. Recall also that CEPIC ()PIC(R)(s a,,)) is equal to
R(s, 5') + ElTR(ss, A,
7R(S, S,]
For the sake of brevity, let RC = CBPIC (Ri) and Rº CEPIC (Rz), and let DD be the distribution over Ax given by
P(S.A.89~D(S = 8, A a, = PS-DD (S
8) P (A = (S' s').
Moreover, let X = (T) and Y (T", where T and T' are random transitions distributed according D. We now have that DEPIC R2) v(1 p(X, Y))/2, where is the Pearson correlation.
Next, recall that the Pearson correlation between two random variables X and Y is defined
[[ - [[ - E[У]]
where ox and By are the standard deviations of X and Y. Recall also that the standard deviation dx of random variable X is equal / [
[[
X
18

---

Published as a conference paper at ICLR 2024
Next, note that in this case have that [[ and B[Y] both equal to 0. This follows from the way that these variables were defined, together with the linearity of expectation. Therefore, we can rewrite p(X, Y)
E V B
Let W be the ([S][A))) x (($]][|[sS)-ddmmmeniooaad diagonal matrix which the diagonal value that corresponds to transition is equal to /Prrzp(T = t). We now have that v /E[X²] = L W Rf) and v /E|Y?] L2 (W R2) Moreover, we also have that E[XY] = (W (WRF) (W Rg) Next, recall that the dot product v w between two vectors v and can be written as L2(v) -2(ww) cos(O),
where 0 is the angle between and w. This means that we can rewrite p(X, Y)
L2(WR)) L2(WRR) cos(O) cos(O),
(2(WR)) L2( RR)
where 0 is the angle between W RY and WRS
Since the angle between two vectors unaffected by the scale of those vectors, we have that is also the angle between W R L2(L2/WWW/ (WR)) RT and W R L2(W R2)). We can now apply the Law of Cosines, and conclude that the L2 -ig-dtntance between W WRG / (W2 RT)) and W R (W is
equal /2- (0)
2p(X, (X, 2. DEPIC (R1, R2). This means that
1
WRY
WRC
DEPIC RR1 R2)
L2
2
L2(WRR) RG) L2( R$)
Rewriting this completes the proof.
The fact that EPIC can be expressed in this form is also asserted in Gleave et al.) (2020), but proof is not given. We have provided the proof here, to make the equivalence more accessible and intuitive. It worth noting that this equivalence only holds when the "coverage distribution" is the same as the distribution used to compute EPIC, which is left somewhat ambiguous in Gleave et al. (2020).
MAIN PROOFS
In this section, we give the proofs of all our results. We have divided into four parts. In the first part, we prove that STARC metrics are sound. In the second part, we prove that STARC metrics are complete. the third part, we prove that EPIC (and a class of similar metries) all are subject the results discussed in Appendix A In the final part, prove few remaining theorems.
F.1 SOUNDNESS
Before we can give the proof of Theorem 1 we will first state and prove several supporting lemmas.
Lemma 1. For any reward functions R₁ and R2, and any policy n, we have that
[T(()) - J2(T) &
1- (R,, R2)-
19

---

Published as a conference paper at ICLR 2024
Proof. This follows from straightforward algebra:
J1(TT) J2(x))
= Eg ~
As,
B2 Ar, Sct1)
Be -
1 [R((S, A1, - R2(Si, A,, St1))]
> /B A1, R2(SS, A,, S141)l]
7 Leo( R2) (1= Les (RI, R2)-
Here the second line follows from the linearity of expectation, and the third line follows from Jensen's ss inequality.
Thus, the Lye distance between rewards bounds the difference between their policy evaluation functions. Since all norms are bilipschitz equivalent on any ditte-iimnnion vector space, this extends to all norms:
Lemma 2. If p is norm, then there is positive constant Ky such that, for any reward functions Rı and R2, and any policy n. [J1(T) - (2(T)) < Kp p,,,, R2).
Proof. If p and y are norms on a iiite-dimensional vector space, then there are constants i and K such that k- p(ar) & <(x) K p(x). Since S and A are finite, R. is finite-dimensional vector space. This means that there is a constant K such that Lap Rı, R2) & K RR, R2). Together with Lemma [ this implies that
(1-
-2(m)))(TT))
&
K (K-m(R1,H R2). I 1-
Letting K, =
K completes the proof.
Note that the constant Kp given by Lemma 2 may not be the smallest value of K for which this statement holds of a given norm p. This fact can used to compute tighter bounds for particular STARC-metrics.
Lemma 3. Let R₁ and R2 be reward functions, and Tı, T2 be two policies. [ - J2(TT) < for x { n2), and if Jz( (22) > J2(m1), then
(1,( (1T2 < U.
Proof. First note that must non- negaatgaevve. Next, note that if J1 (TT] J1 (T2) then (11]
JI(TT) < 0, and so the lemma holds. Now consider the case when ./1 (TI) > (12):
(m J1 (T(2) = (((T)) - J2(TT) + (2((T)) J1 (11( - (2() (J2(T2) 21(2)
Our assumptions imply that (J2(T2) - J1 (T2) & U. We will next show that [J((T]) - -2((T2) & U
well. Our assumptions imply that
(J((T]) J2(m)) EU Jz(m1) > [1) - U
(2((T2) > [mm - U
20

---

Published as a conference paper at ICLR 2024
Here the last implication uses the fact that J2( > J2( A symmetric argument also shows that (T)) > (2(m²) U (recall that we assume that (1( > J1 (T22) Together, this implies that
(J((m) J2(x2) < U. We have thus shown that if (1( Ji((T) (T2) then
(J1(m)) (22)) ( (x2) 22-
and the lemma holds. This completes the proof.
Lemma 4. For any linear function e: R - such that ni ((())) & Kn, n(v) for all e R".
IR" and any norm n, there a positive constant Kn,
Proof. First consider the case when n(v) O. In this case, can find upper bound for n(c(v)) in terms of n(v) by finding an upper bound for x(c(R) Since e is linear, and since n is absolutely homogeneous, we have that for any v E IR" and any non-zero a E IR,
n(R2)
n(c(a- v)) = n(((()) n(c(v)) n(a v)
n(()
n(u)
m(a(())) is unaffected by scaling of v. We may thus restrict our attention to the unit m(e)
In other words, ball of n. Next, since the surface of the unit ball of n is compact set, and since nle(v))
is continuous m(#)
on this surface, the extreme value theorem implies that ale(v)) must take on some maximal value K₁,
a(n)
on this domain. Together, the above implies that n(c(v)) & Kn nnv) for all R such that nn()) > 0.
Next, suppose n(v) O. In this case, is the zero vector. Since c is linear, this implies that c(v) v, which means that ri((ee) = 0 as well. Therefore, if n2(v) = 0, then the statement holds for any Kn- In partieular, it holds for the value K,, selected above.
Let c be a linear function c: R + R. and let n be a norm on Im(c). Let R be any reward function, let Rc c(R), R)), and let Rs ((Re)) (fc)
Lemma 5.
Rc) > 0, and Re otherwise. Assume there is constant B such that Jc(T) -[x)++ B for all æ. Then - ((
Proof. Let us first consider the case where n( R) 0. Since n is a norm, R must be the reward function that is 0 everywhere. Since e is linear, this also implies that n(c(Rt)) O. In that case, both ((T1) - (m²) = for all Ii and T2, and n(c(R)) x = for all x. Therefore, the statement holds.
Let next consider the case when m((t) 0. Since is linear, this means that ((c(R)) 0. Moreover, since Rg- = Rc/n(Rc), and since Jc(T)) = [(x) + B, we have that
Js(m) (n(c(T)) ) (J(z)) + B)
This further implies that
Js(mT) - = (((((R))) (J(TT) ((T2))
since the B-terms cancel out. By rearranging, we get that
- - ((x2) m(c(R))(Js(m) Js(T)))
This completes the proof.
Lemma 6. If R2 and R2 differ by potential shaping with 4, then for any and μo, have that (T(T) = (T) Esg no (So)]. Moreover, if R2 and R2 differ by potential shaping with and S' s'-reiistribution for then for any Po, we have that J2( = J1 Ji(T) Es [ (So))
Proof. The first part follows from Lemma B. Skalse et al. (2022a). The second part then follows straightforwardly from the properties of S' sy-redistiibution.
Theorem 1. Any STARC metric is sound.
21

---

Published as a conference paper at ICLR 2024
Proof. Consider any transition function and any initial state distribution po. and let d be STARC metric. We wish to show that there exists a positive constant U, such that for any R₁ and R2, and any pair of policies ni and T2 such that (2( > (2(m)), we have that
J((m)) (=2) (max (1) min Ji()) Ka di R1, R2)-
Recall that d( [1, R2) mms((1)s))))))))) s (B2)), where m is an admissible metric. Since m admissible, we have that (()(R)), R2)) & Km mmn-mm(s (R( ), s (R2)) for some norm p and constant Km- Moreover, since p is a norm, we can apply Lemma 2 to conclude that there is a constant Kp such that for any policy have that
(T) < K2
where J is the policy evaluation function of s(R) and J is the policy evaluation function of s (R2). Combining this with the fact that p(s(( R₁ ) (R2)) & Km m(s(R1), (R2),, we get
- (T)) < Kp p(s(R1), s s(R2)
-
K Km m (R( ), s (R))
= Kmp d(Ri. R₂)
where Kmp- Kp Km. We have thus established that, for any n, we have
[T)( (T)) & Kmp RR R2).
Let πT and n2 be any two policies such that (T2) 11) )) Note that J2( J2(T1) if and only if ( e J (T)). We can therefore apply Lemma and conclude that
(f J (T2)
K Kmp d(R1, R2).
By Lemma there is a constant B such that J = J1 + B. We can therefore apply Lemma
J1 (m - (m & ((((R))) 2 Kmp d( R1, R2).
We have that n is a norm on Im(c). Moreover, max, (x) min, J1(x) is also a norm on Im(c) (Proposition 4 Since Im(c) is fiite-dimensionn vector space, this means that there is constant K, such that n((( & K2 (max Ji (π) ming (=)) for all R4 E R. Let U = 2 Kmp K3. We have now established that, for any mi and 22 such that J2( 2 (m1), have
Jı (m) (1()2) (max (1( min Jr (T)) U d( R1, Rz).
This completes the proof.
F.2 COMPLETENESS
In this section we give the proofs that concern completeness. We will need the following lemma:
Lemma 7. Let = IR. be the boundary of bounded convex set whose interior includes the origin. Then there is an > O such that for any y E S, the angle between x and I. is at least a.
Proof. Let be the largest sphere which is centred around the origin, and whose interior does not intersect S. Note that since the interior of S contains the origin, the radius of L is positive. Similarly, let U be the smallest sphere which is centred around the origin, and whose exterior does not intersect S. (In other words, L and U two spheres such that S lies "between" L and U. Note that if S is sphere centred around the origin, then L U.)
Let and be arbitrary points in S, and let be the angle between and y
22

---

Published as a conference paper at ICLR 2024
8
5
0
L
U
Consider the line that passes through and y. This line cannot intersect the interior of L, since S is the boundary of a convex set. Note also that @ gets bigger if we reduce the magnitude of x. Thus, let x' be the vector that results from reducing the magnitude of x until the line between x' and y is tangent of L:
x²
8
L
U
Now the angle 9 between = and y - x is at most as big as the angle 8' between -s' and y x'. Next, let the point where the line between x' and y intersects L be called A, and the point where intersects U be called B. Consider the line segment between A and B:
B
A
This line segment a compact set, which means that there is a point x" along this line which maximises the angle between -x" and y x" (note that this point in fact is equal to B, but we will not need this fact in our proof). Let this angle be 8" We now have that > 8' > 8" Moreover, the value of 8" does not depend on or y. which means that the angle 0 between - and y- is at most 0 for all points v, y E S. This in turn means that the angle between x and - x is at least a = π which completes the proof.
23

---

Published as a conference paper at ICLR 2024
Using this, can now show that get lower bound on the angle between two standardised reward functions in terms their STARC-distance:
Lemma 8. For any STARC metric d, there exist an & E BR+ such that the angle @ between s(R1) and s ((22) satisfies ε d( d(,,, R2) & for all R1, R2 for which neither s(Ri) or s s(R)) is O.
Proof. Let d be arbitrary STARC-metrie, and let R1 and Rg be two arbitrary reward functions for which neither s(R,) or s R2) is O. Recall that d(R,,R) = m(s(R)) ), s [2)), where m is a metric that is bilipschitz equivalent some norm. Since all norms bilipschitz equivalent any finite-dimensional vector space, this means that m is bilipschitz equivalent to the Lz-norm. Thus, there are positive constants p. q such that
p. m())s s(R))) & L2(s(Ri), s(R2) & q m(s(R1), s s(R2)..
In particular, the Ly-distance between s(Rj) and s is at least = p R1. R2). For the rest of our proof. it will be convenient to assume that < (2((R))) this can be ensured by picking a that is sufficiently small.
Let us plot the plane which contains ((1),, ((22), and the origin, and orient it so that s(R)) points straight up, and so that s (2)) is not on the left-hand side:
s R1
Since the distance between (1) and s (R2) at least c, and since s( R2) is not on the left-hand side, we know that s(R2) cannot be inside of the region shaded grey in the figure above (though it may be on the boundary). Moreover, as per Lemma we know that the angle between s(Ri) and s( (R2) a( (2) is at least a, where > 0. This means that we also can rule out the following region:
Ri
E
24

---

Published as a conference paper at ICLR 2024
Moreover, let be the element of Im(s) that is perpendicular to s( s(R1). lies a plane with s (R)), s s(R2), and the origin, and points in the same direction as s(Rg) within this plane. Since Im(s) is convex, we know that s (R2) cannot lie within the triangle formed by the z-axis, the y-axis, and the line between 8( R1) and u:
a
s R
Since Im(s) is closed and convex, we know that there is vector in Im(s) whose Lo-norm is bigger than other vectors in Im(s), and a (non-zero) vector b Im(s) whose L2-norm smaller than all other (non-zero) vectors in Im(s). From this, we can infer that the angle between s ((Ri) and v - ((1)) is at least arctan(b/ b/a). Also note that 0.
We now have everything need derive lower bound on the angle 0 between s s(R) and s (R)). First note that this angle can be no greater than the angle between s(R1) and the points marked A and B in the figure below (whichever is smaller):
Q
A
s(R)
B
25

---

Published as a conference paper at ICLR 2024
To make things easier, replace both and 3 with y min(a, 3). Since this makes the shaded region smaller, we still have that s R2) cannot be in the interior the new shaded region. Moreover, in this case, we know that the angle between s(Ri) and s(R2) is smaller than the angle 6' between of R1) and the point marked A:
((R)
2
Deriving this angle is now just a matter of trigonometry. Letting z denote (2(A), we have that:
sin
x
sin π
7)
sin(r) (>)
From this, get that
((5) sin(7))
0' = arcsin
sin(7)
Moreover, it is also straightforward to find an upper bound for 2. Specifically, we have that 2² L2(s(Ri))) = (22((s(R))) cos(T - 7). Since L2(s(Ri)), this means that
(T)( (T2(s(R1)) cos 7).
Moreover, since Tm(s) compact, there is vector a in Im(s) whose Lz-norm is bigger than all other vectors in Im(s). We thus know that
<< /2Lz(a)² (L) cOS(TT 7).
Putting this together, we have that
(sin(7)) x
8' sin(7) m(s(R1), s(R2))
Setting = p sin(7)
thus completes the proof.
Finally, before give the full proof, will also need the following:
26

---

Published as a conference paper at ICLR 2024
Lemma 9. For any invertible matrix M IR" - R there is an &g (0, 1] such that for any v, w IR, the angle between Me and Mw satisfies o' e E2 8, where is the angle between and
Proof. We will first prove that this holds in the 2-dimensional case, and then extend this proof to the general n-dimensional case.
Let M be an arbitrary invertible matrix IR2 - TR. First note that we can factor M via Singular Value Decomposition into three matrices U, Σ. V, such that M = UEV where U and V are orthogonal matrices, and > is diagonal matrix with non-negative real numbers on the diagonal. Since M is invertible, we also have that cannot have any zeroes along its diagonal. Next, recall that orthogonal matrices preserve angles. This means that
restrict our focus to just X
Let a and & be the singular values of M. We may assume, without loss generality, that
a 3
Moreover, since scaling the and y-axes uniformly will not affect the angle between any vectors after multiplication, instead equivalently consider the matrix
a
Σ
Let v, IR2 be two arbitrary vectors with angle 0, and let l' be the angle between Ev and Ew. We will derive lower bound on 0' expressed in terms of f. Moreover, since the angle between v and w affected by their magnitude, we will assume (without loss of generality) that both and have length 1 (under the L-onorm).
First, note that if then w. This means that Ed -Ew, since is linear transformation, which in turn means that 6' т. Thus 8' > lg O as long as bg & 1. Next, assume that < π.
We may assume (without loss of generality) that the angle between and the æ-axis is no bigger than the angle between and the r-axis. Let ø be the angle between the æ-axis and the vector that is in the middle between v and w. This means that we can express v as (cos(Ø - 0/2), sin(ő 0/2)) and w (cos( ( + 0/2), sin(d 0/2)). Moreover, since reflection along either of the axes will not change the angle between either v and w or Ev and Ew, we may assume (without loss of generality) that Φ [0, π /2. For convenience, let o a/3.
1
'If there are vectors such that the angle between r and y is 0 and the angle between Mr and My is 6' then there are vectors such that the angle hetween and is 0 and the angle hetween En and Ean is 0. and vice versa.
27

---

Published as a conference paper at ICLR 2024
(Note that we can visualise the action of E scaling the z-axis in the figure above by σ.)
We now have that Ev = (a c - 0/2), sin( 0/2)) and Ew = (a cos( + 0/2), sin( + 0/2)).
Using the dot product, we get that
o² cos( 2/2) cos ( + 0/2) + sin( - -8/2) sin( + 0/2)
cos(t") = V o2 cos ( 0/2) + sin?( 0/2) / 02 cos? + 0/2) + sin?( + 0/2)
We next note that if 0 [0. T) and 5 [0, T 1/22. then the derivative of this expression with respect to
d can only be 0 when di E {0, m/2] | This means that cos cos( must be maximised or minimised when
is either 0 or n n/2, which in turn means that the angle I' must be minimised maximised when
is either 0 or T/2.
now easy to see that if a then 0' is minimised when 0, and that if then O' is minimised when @ 7/2. Moreover, if Ø 7/2, then
a cos(m/2 0/2)
0' = 2 arctan
= 2 arctan (a tan()/2)).
Sin( - -0/2)
which in turn is greater than 0 when < 1. Similarly, if o 0, then
sin(0/2)
cos cos((/2) ) 2 arctan (o tan(0/2))
8' = 2 arctan
which is in turn greater than oー when σ > 1. In either case, we thus have that
8' 8 min(o,
min(3/o,a/3))
We have therefore show that, for any invertible matrix M : .R² - RR, there exists positive constant min(3/a, a, a/ /),, where a and B are the singular values of M, such that if u, w E IR2 have angle then the angle between Mu and Mw is at least 0 min(3/a,aa) a/3).
To generalise this to the general n-dimensional case, let v, w E R" be two arbitrary vectors. Consider the 2-dimensional linear subspace given by S span(v, w), and note that (S) also is 2- dimensional linear subspace of Rn" (since M is linear and invertible). The linear transformation linear transformation M' R - R We can thus apply our previous result for the -io-dimesiional case, and conclude that if the angle between v and
which M induces between S and (S) is isomorphic
0, then the angle between Mu and Mu is at least 0 min( (3/,, a/3). where and B are the singular values of M'. Next, note that the singular values of M' cannot be smaller than the smallest singular values of M or bigger than the biggest singular values of M. We can therefore let la a/3, where a is the smallest singular value of M and B is the greatest singular value of M, and conclude that the angle between Mr and Mu must be at least Eg 9. Since the value of &g does not depend on or w, this completes the proof.
With these lemmas, we can now finally prove that all STARC metrics are complete:
Theorem 2. Any STARC metric is complete.
Proof. Let d be an arbitrary STARC metric. We need to show that there exists positive constant L such that, for any reward functions R2 and Rg, there are two policies T2, T2 with (2(T2) > J2( and
(m)) - (1(2 > L (max (T() - min JI((T) d(R1,R2)
and moreover, if both max JI (T) min, (T) = 0 and max, J2(T) min, J2(TT) = 0. then we have that d( d(B,, R2) O.
Forr example, this may verified using tools such as Wolfram Alpha.
"To see this, let A be orthonormal matrix that rotates B.² to align with S, and let B be orthonormal matrix that rotates (S) align with R² Now M BM A is invertible linear transformation B B Moreover. since orthonormal matrices preserve the angles between vectors, we have that v, w S have angle and M v, M E (S) have angle 8. and only if A A 0, A =w E H² have angle 0 and BM v, BM e 2²² have angle 6'. Note that M' A that dr have angle 0 and MV, Mu w have angle 0', if and only if there are v', w/ E R22 such that v', u/ have angle 0 and o' and M us have angle o' (with o' A - and w/ A A
BM and A --
BM w. This means that there are v, w S such
28

---

Published as a conference paper at ICLR 2024
We first note that the last condition holds straightforwardly. If max, J1(m) min, J1(xz) = 0 and max, J2(TT) min, (T) = O then R1 and R2 have the same policy order, which means that Proposition 6 iimpliss that d(R,, R2) 0. This condition is therefore satisfied.
For the first condition, first note that if max; J1 (ΛT) min, J1 = O, then the statement holds trivially for any non-negative L (since the other two terms on the right-hand side of the inequality strictly non-negative).
Let next consider the case where both max, JT) ming (TT > O and max, J1 (TT) min, (z) 0. We need introduce new definition. Let m IT RR be the function that takes policy and returns the vector where m a, Σ P'((S, S1+1 6, s'), where the probability is for a trajectory sampled from т under T and 14u- In other words, m returns the long-run discounted cumulative probability with which visits each transition. Next, note that ((x = m(T) R. This means that m can be used to decompose J into two steps, the first of which independent of the reward function, and the second of which is linear function.
We will use d to derive a lower bound on the angle 0 between the level sets of J1 and J2 in Im(m). We will then show that Im(m) contains an open set with a certain diameter. From this, we can find two policies that incur a certain amount of regret.
First, by Lemma 8 there exists an E such that for any non-trivial Rí and R2, the angle between of R2) and a( (B2) is at least (1 d( R2 R2)) To make our proof easier, we will assume that we pick an & that is small enough to ensure that E d(( d(R1, R2) < n/2 for all R1, R2.
Note that s (())) and s(2)) may not be parallel with Im(m), which means that the angle between s(R)) and s(R2) may not be the same as the angle between the level sets of J1 and J/ in Im(m). Therefore, consider the matrix M that projects Im(c) onto the linear subspace of R that is parallel to Im(m), where is the canonicalisation function of d. Now the angle between Ms R2) and s is the same the angle between the level sets of the linear functions which Ji and J2 induce on Im(m). Moreover, note that M is invertible, since any two reward functions in Im(c) induce different policy orderings except when they differ by positive linear scaling (Proposition I]. We can therefore apply Lemma and conclude that there exists an Eg E (0, 1], such that the angle between the level sets of J1 and J2 in Im(m) is at least Ez E1 d( R1 R2). Moreover, since E d(R,, R2) is at most n/2, and since l & 1, we have that la l d( R1, R2) is at most 2/2.
This gives that, for any two policies 11, T2, have:
J1 (m1)) - (1(22) = (
= m())) - c(R)) (B{)) ((()))(((m))m(()
= M(((()))(m(()) - mm(x))
-2(M((((R))) -2((((m)) m(T2)) cos(Ø)
where &i is the angle between Mc((R)) and m((1) m (T)), and J is the evaluation function of e( (1). Note that the first line follows from Lemma 6 We can thus derive a lower bound on worst-case regret by deriving lower bound for the greatest value of this expression.
We have that Im(m) contains set that is open in the smallest affine space which contains Im(m) (see [Skalse et al. 2022b). This means that there is an 6 such that Im(m) contains a sphere of diameter We will show that we always can find two policies within this sphere that incur certain amount of regret. Consider the 2-dimensional cut which goes through the middle of this sphere and is parallel with the normal vectors of the level sets of JI and J2. The intersection between this cut and the c-sphere forms a 2-dimensional circle with diameter e. Let T1 T2 be the two policies for which (1( and m(T2) lie opposite to each other this circle, and satisfy that J2(TT) J2(T2) (or, equivalently, that Mc(R,) m(Ti) = Mc(R), m((z))) Without loss of generality, we may assume that Jr (m)) Jı (12)..
29

---

Published as a conference paper at ICLR 2024
Mc(Ba) Mc(R)
0
m x1
m(
Now note that [2(m((T)) -m( = e. Moreover, recall that the angle 0 between Mc(Ri and Me( R2) is least 0' f f2 d( R1; R2), and that this quantity is at most 7/2. This means that the angle o is at most T/2- 0", and so cos(d) is at least cos( 2 8*) cos( म //2 ( l2 d(Rj, R2)). This means that have two policies T1, T2 where (2(TT) = (2( and such that
(T(TT - (12) (c(M(((())) (z(m((T)) - m(T2)) cos(
(2(M R1)))
( lz 6 dl R1, R2)).
Note that cos(x/2 2 x)) 3 2/m when & x/2, and that l d(Rg, R2) & n/2. Putting this together, we have that there must exist two policies TI, T2 with J2( J2(x1) such that
(5.41-6--2 dl Ri, R2).
J (T2) > L2(M(c(Ri))
π
Next, note that, if is norm and M is invertible matrix, then p M is also norm. Furthermore, recall that max, J1 (TT) - min, Ji (x) a norm on Im(c), when e canonicalisation function vector space, this means that there must exist a positive constant la such that L2(Me (c(R))) > L3 (max, J/ (T() min, J1 (T)). We can therefore set I. (c- f
(Proposition 4). Since all norms
equivalent
la ls 2/TT,, and obtain the result that want:
(m) (m22 L (max (T() min J1 (I())) d( d(R1, R2).
Finally, must consider the case where Rg is trivial under and po. but where R; is not. In this case, (2( > (2(mT) for all क and T2, which means that ma ma (i(T)) - (m2) = max, (T) min, (T). Therefore, the statement holds for any L as long as we ensure that L. d R1, Ro) & for all R1 and R2. This completes the proof.
F.3 ISSUES WITH EPIC, AND SIMILAR METRICS
In this appendix, we prove the results from in Appendix A Moreover, we state and prove versions of these theorems that more general than the versions given in the main text. First, need a few new definitions:
Definition 7. function e: R - R is an EPIC-like canonicalisation function if e is linear, c(I) and R differ by potential shaping, and e( [1) = c(R2) if and only if R₁ and R₂ only differ by potential shaping.
Definition 8. A function d R x R R is EPIC-like metric if there is EPIC-like canon- icalisation function c, a function n that is a norm on Im Im(c), and a metric m that is admissible on Im(c), such that d(R,, R2) m(s(R) R1), s( (R2)). where s( R) el (R))n(((RR) when n(c( ((c(R) & 0. and of R) otherwise.
Note that EPIC is EPIC-like canonicalisation function, and that EPIC is EPIC-like metric.
30

---

Published as a conference paper at ICLR 2024
Theorem 3. For any EPIC-like metric there exists a positive constant U. such that for any reward functions R1 and R2, if two policies Tı and n2 satisfy that (2( > (2(T1), then we have that
(I - (1(T2) < U L2( - d( R2).
Proof. We wish to show that there is positive constant U, such that for any R₁ and R2, and any pair of policies n and 22 such that (2) (m1,, have
(())) J1 (T2) U L2(R,) d(R,,
Moreover, this must hold for any choice of T and μoa-
Recall that d( R2, R2) (n(s(Rg)) o ((R)),, where m is an admissible metric. Since m admissible, we have that p(s ((s( (R2)) & Km -mnmmms [1).
(RR).s((,)))) s(R)) for some norm p and constant Km Moreover, since p is a norm, we can apply Lemma 2 to conclude that there is a constant Kp such that for any policy n, any transition function т, and any initial state distribution No. have that
JJ (T) - J2 (=)] & Kp p(s(Ri), R2)).
Combining this with the fact that p(s((1))) R1) R2)) & Km m(s( R1), s( R2))), we get
Kp ((s(p(())))))p))p))))))()) (R2)) < Kp Km- m(s( (5 R1 s s(2))
= Kmp d(R,, R2)
where Kmp- = Kp. Km. We have thus established that, for any n, T, and fuo we have
(f( (T)) & Kmp d(Ri, R2)-
Consider arbitrary transition function 7 and initial state distribution Nus and let ii and nz be any two policies such that (2(m))= > (2(x1) under 7 and (gg- Note that (2 > (2(1)) if and only J (2) 1 (m)) We therefore apply Lemma and conclude that
(f(m) - J (T2) & 2. Kmp- d(R1, R2).
By Lemma there is constant B such that J = J1 + B. We can therefore apply Lemma
(1((1) - (1 < n(c( R1)) 2 Kmp d( d(R1. R2).
By Lemma 4 there is a positive constant K,, such that n(c(It)) & Kn n(R) for all R R.
(mm) - (12) & Kn n m(R1)) 2 Kmpp d( Rı, R2).
Moreover, since n a norm, and since R is dinte--imensional vector space, we have that there is constant K2 such that n (R) & K2 L2 (R) for all R R. Let U = 2 Kn Kmp K2. We have now established that, for any and л2 such that J2 (2(T2) > J2(T)). we have that
(mT) J1 & U L2(Rg) ) R1, R2).
Note that does not depend on 7 or No- This completes the proof.
Theorem 4. No EPIC-like metric is sound.
Proof. Consider an arbitrary transition function and an arbitrary initial state distribution fuu and let an EPIC-like metric with canonicalisation function c, normalisation function n, and admissible metric m..
Let X be linear subspace (m)c), such that there, for any reward function E Tm(c), is exactly one reward function R.' e X' such that R and H' differ by S s'-redistribution under
Let Rí be an arbitrary reward function in X' such that ni (2)) = 1, and let Rig = - RR Note that Ri and the reward function that is 0 everywhere do not differ by potential shaping and S' o'-redistribution this is ensured by the fact that they are distinct, and both included in X. As per Proposition T this implies that Rj does not have the same policy order as the reward function that is 0 everywhere. This, in turn, means that max, (TT min, Jn (T) > O. Moreover, since R₂ = - R,, this implies that, if m is policy that is optimal under R1, and #2 is policy that is optimal under R2, then m2
31

---

Published as a conference paper at ICLR 2024
is maximally bad under R1, and Ti is maximally bad under Rg. In other words, there policies Ti, T2 such that J2( 2 (2(TT1): and
(1 - (1(
1.
max,7 (I(T) min, JI(T)
This is the greatest value for this expression, and the regret for R₃ and Rg is maximally high.
Next, let Ri = e Rg. and P2 c. R2, for some small positive value c. Since positive linear scaling does not affect the regret, we have that the regret for Rij and R2 also is
Let x be vector in Im(c) that is orthogonal to X. Note that movement along æ corresponds to S'-redistribution under 7. Next, let RIj R2 x and Ri 12 + B x, where and / are two positive constants such that n R = and n R2)) 1. Since movement along z corresponds to S' r'-rriiitributton under т, and since S' d'-reiistribution under does not affect regret, have that the regret for R" and R2 is I.
R
R
R
rerddistributioon
R2
unit hall of vin Im(c)
R2
Now, since R" and R2 are in (m),), and since n(R)) = and n(R") 1, we have that d(R", Rby) = m(R" R2). By making sufficiently small, Therefore, for any simple STARC metric d and any environment, there are reward functions such that R. and Ry have maximally high regret, but d R" R2)) is arbitrarily close to 0.
ensure that this value is arbitrarily close to O.
Theorem 5. There exist reward functions R1. R2 such that di Rı, R2) > 0 for any EPIC-like metric but where Rí and R2 induce the same ordering of policies for any choice of transition function and any choice of initial state distribution.
Proof. Recall that S must contain at least two states 81, 82, and A must contain at least two actions
a1 .2 Let R, ($1, (1i,,j,, $1) 1, Rí ($1, 01 s2) c, R2(s1, 81) c, and R2(s), 01 $2) and let Rí and Rt be 0 for all other transitions. R2 and R2 do not differ by potential shaping or positive linear scaling: this means that d(R,, R2) for any EPIC-like metric d. However, R2 and Rg have the same policy ordering for all and μo-
F.4 OTHER PROOFS
In this section, we provide a the remaining proofs of the results mentioned in the main text. Proposition 1. Any STARC metric is pseudometric on R.
Proof. To show that d is a pseudometric, we must show that
1. d(R, R)
2. d( Ri, R2) d( R22 Ri)
32

---

Published as a conference paper at ICLR 2024
3. d(R1, Rs) & d(R1, R2) + d(R2, Rs)
1 follows from the fact that m a metric, and follows directly from the fact that the definition of STARC metrics is symmetric in Rı and Rg. For 3, the fact that is metric again implies that = (R)
mns(R.) R1), (i)),((B)) s(Ra) & m))((i)), ((R2) + m(s( sRa)) = d(B, R2) + d (B2, Ra).
This completes the proof.
Proposition 2. All STARC metrics have the property that d(R, R2) = 0 if and only if R₁ and R induce the same ordering of policies.
Proof. This is immediate from Proposition I. together with the fact that if R1 and R2 differ by potential shaping, S' d'rredistribution, and positive linear scaling, applied in any order, then R2 = a- Rs for some scalar a and some R3 that differs from Ri via potential shaping and S' S'-redistribution. D
Proposition 3. If two pseudometrics di d2 on R are both sound and complete, then d1 and d2 are bilipschitz equivalent.
Proof. Since d1 is complete, we have that
L1 d1 (R1, R2) (max (m)) min J1(T))
max J1((1) - J1 (22).
Tn (
Similarly, since d2 is sound, we also have that
max (1.3
JI(TT) J1((2) < U2 d2(R1, R2) (maxxJ((T) - min (J2(())
This implies that
In d--di (Ri, R2) (max Ji (T) - min J1 (T)) & U2 dz (R,, R2) (max J1 (T) min J1 (T)).
x
First suppose that (max, (T) - min, J1 (T)) > 0. We can then divide both sides, and obtain that
U2 L,
(R R₂) &
dg (R,, R2).
Similarly, we also have that
L2 T₂
d2 Ri, R2) < di (R1, R2).
This means that we have constants
Us
and
La Un
not depending on R₁ or R2, such that
( L2
U2
d2 d2(R1, R2) & d1 (R1. R2) &
d2(R1, R2)
U1
L1
for all R₁ and R2 such that (max, J (T) min, J (T) 0.
Next, assume (max, (T) - min, JI (T)) = 0 but (max, J2(TT) min, J2(T)) > 0. Since dj and d2 are pseudometrics, have that di R2,, R2) di R22 R1) and d2 (Ri, R2) da R2, R1). Therefore, (tz)) de (R, R2) & d2 R2) &
dR R2) in this case well.
L
Finally, assume that (max, (IT) - min, (T)) = 0 and (max, J2(TT) - min, ( = 0. In this case, Ri and R2 induce the same policy order (namely, the order where म = Ty for all n7, m2). de (R1, R2) & di (R,, R2) <
This in turn means that d1 (R1, R2) de(R1, RR) 0, and Ia (
U2 L1
de(R). R2) in this case well. This completes the proof.
G EXPERIMENTAL SETUP OF SMALL MDPS
In this appendix, we give the precise details required to reproduce our experimental results, as well as more of the data than what is provided in the main text.
33

---

Published as a conference paper at ICLR 2024
G.1 ENVIRONMENTS AND REWARDS
As mentioned in the main text, we used Markov Decision Processes with 32 states and 4 actions. The discount factor was set to 0.95 and the initial state distribution was uniform.
The transition distribution 7(8, a, 8') was generated as follows:
1. Sample i...d. Gaussians (fx 0, 1) generate a matrix of shape [32, 4,3].
2. For each item in the matrix: if the item is below 1, set its value to -20. This is done to ensure the transition distribution is sparse and therefore more similar to real-world environments. Without this step, when an agent is in state S and takes action A, the distribution 7(S, A, s') would be close to uniform, meaning that the choice of the action would not make much of difference.
3. Softmax along the last dimension (which corresponds to s') to get valid probability distribution.
We then generated pairs of rewards. This worked in two stages: random generation and interpolation.
In the random generation stage, we choose two random rewards R1, R2 using the following procedure:
1. Sample i.i.d. Gaussians (μ = 0, = to generate a matrix of shape [32, 4, 32] correspond- ing to R(s, a, 8').
2. With 20% probability, make the function sparse in the following way for each item in the matrix: if the item is below 3, set its value to O.
3. With a 70% probability, scale the reward function the following way - ssappe a uniform distribution between 0 and 10, multiply the matrix by this number.
4. With a 30% probability, translate the reward function in the following way sample uniform distribution between 0 and 10, add this number to the matrix.
5. With 50% probability, apply random potential shaping in the following way sample 32 i.i.d. Gaussians (μI = 0, a = 1) to get a potential vector &. Then sample a uniform distribution between 0 and 10 and multiply the vector by this number. Then sample uniform distribution between 0 and and add this number to the vector. Then apply potential shaping to the reward function: Rnew as, 5') R(s, a, s') + ( ((s).
When we say "With an X% probability". we are sampling a random number from a uniform dis- tribution between 0 and and if the number is above (100-X)%, perform the action described, otherwise we skip the step.
Then in the interpolation stage, we take the pair of reward functions generated above and do linear interpolation between them, finding 16 functions which lie between R1 and Rg. More precisely, we 16.
set R(y) R₁ id where (R2- R1)/10 and with ranging from
The interpolation step exists to give us pairs of rewards which are relatively close to each other for instance, R and R(y are very similar. This is important because nearly all reward functions generated with the random generation process described above will be orthogonal to each other, and thus their distances to each other would always be quite large. By including this interpolation step, we ensure a greater variety in the range of distance values and regret values we expect to see.
For each environment, we generated 16 pairs of reward functions, and then for each pair we performed 16 interpolation steps. This means that for each transition distribution, we compared 256 different reward functions.
We then compute all distance metrics well as rollout regret between R and R(a for all i.
G.2 ROLLOUT REGRET
We calculate rollout regret stages: 1, find optimal and anti-optimal policies, 2, compute returns under various policies and reward functions, 3, calculate regret.
In stage 1, we use value iteration to find policies T, which maximises reward R,, T()) which maximises reward Reg ny which minimises reward R2 (in other words maximising reward - R1,
34

---

Published as a conference paper at ICLR 2024
meaning Ta is the worst possible policy under R1), and ny which minimises reward Rg. Note that all of these policies are deterministic, i.c. π A.
In stage 2, simulate number of episodes to determine the average return of the policy. Specifically, we simulate 32 episodes such that no two episodes start in the same initial state (this helps reduce noise in the return estimates). The episode terminates when the discount factor being applied (i.e. y²) below 10-2.
In stage 3, calculate regret follows. The regret is the average of two regrets: the regret of using T()) instead of my when evaluating using R1 and the regret of using क instead of T(a) when evaluating using R(g (with both of these being normalised by the range of possible returns):
Reg, + Reg(s)
Reg
JI(mI) ((()
Reg1
(i(TT) - Ji (TT)
Jas (m))
(e
((0(((()) -(() (Ty)
In cases where the denominator is zero, simply replace it with (since the numerator in these cases is also necessarily 0).
G.3 LIST OF METRICS
Our experiment covers hundreds of metrics, derived by creating different combinations of canon- icalisation functions, normalisations, and distance metrics. Specifically, we used 6 "pseudo- canonicalisations" (some of which, like CEPIC and CDARDD do not meet the conditions of Def- inition D. 7 normalisation functions, and 6 distance norms.
used None (which simply skips the canonicalisation step), CEPIC (which is the minimal ppseudo-canonicalisattiio potential shaping but not 5" s'-redistribution, and therefore is easier to compute), VALPotent i (which is given by R(s,a, a, 8') (*(s) + (8)), and VAL (defined in Proposition 2 as E5 [R(s a, S*) (s) (S)). For both CEPIC and CDARD, both Ds and D were chosen to be uniform over S and A. For both VALPotentio
For canonicalisations, CDARD, MinimalPotentinnii
that removes
and VAL, π was chosen to be the uniformly random policy. I Note that VAL the only canonicalisation which removes both potential shaping and S' srrreistributtin, and thus the only one that meets the STARC definition of a canonicalisation function (Definition Tp. The other comparison. It is worth noting that our experiment does not include the minimal canonicalisation functions, given Definition because these functions are prohibitively expensive compute. They therefore better suited for theoretical analysis, rather than practical evaluations.
caaudoo-cnonicaliaationn were used for
The normalisation step and the distance step used L1s L2, Los wei weighted_Ly weighted_Ly and weighted_Lar The weighted norms are weighted by the transition function i.c. L,()) a, 8') normalisation step.
T(8, a, R(s, a, s//,, We also considered metrics that skip the
We used almost all combinations of these the only exception was that we did not combine weriimalPotentiin with normalisation norms Lie or we weighted Loo because the optimisation algorithm for Mi wwiimmmlootenttiomm does not converge for these norms.
G.4 NUMBER OF REWARD PAIRS
We used 49,152 reward pairs. This number was chosen in advance as the stopping point corresponds using 96 CPU cores, generating 2 environments on each core, choosing 16 reward pairs within each environment and then performing 16 interpolation steps between them.
SSinee V&L is valid canonicalisation function for any choice of policy æ, we simply picked policy for which TT would be easy to estimate. The reason for choosing a uniformly random policy, rather than some deterministic policy, is that this policy has exploration build in.
35

---

Published as a conference paper at ICLR 2024
H FULL RESULTS OF SMALL MDP EXPERIMENTS
We used the Balrog GPU cluster at UC Berkeley, which consists of 8 A100 GPUs, each with 40 GB memory, along with 96 CPU cores.
The notation in this table is in the format Canonicas Ceronicalisation For instance, VAL we whte__ means using the Val canonicalisation function, L2 normali- sation function, and then taking the distance with the weighted L1 norm. means normalisation is skipped.
Table Full experimental results
Distance function
Correlation regret
VALPolentall--weighheeL MAL-htweighted_
0,876
0.873
VAL-1-1
0.873
[ll--eiighedd_-weiiheeee
0.873
VAL-weightte__1-
0.873
VAI.-1-2
0.870
VAL-weighted 1-2
0,870
VAL-I-weighted
0.870
VAL-weightedd_Iwwiiihhee
0.870
0.867
DARD-I-weighted_
0.861
VAL-weighted_2-inn
0,858
VAL-2-inf
0.858
VAL-weighted, 2-weihhted 2 VAL-2-2
0,856
0.856
VAL-weighted 2-2
0.856
VAL-2-weighted
0.856
0.845
DARD-veighhedLL-wvihheed_d
0.835
DARD
wei--wighheed2-weihhhhee 2
0.831
PPIC-weiihted__I-weiee
0.830
VAL.Pootental222weeignedd
0.828
DARD-2-weighted
0.826
DARD-1-1
0.824
EPIC-weighted trrighhtdd-weighhteee_
0.823
EPIC-I-weighted
0.819
MAL-weightedd_iffiin inf-inf
0.816
MinimalPotential-1J.
0.815
MinimalPPrentta----viiieeed
0.814
EPIC-2-wwiigtedd2
0.814
EPIC-1-1
0.814
VALPotential-wcightee hiteeettiilliigghhhcd--i--eeeee 2-weigtted inf
0.807
EPIC-weighted 2-weighted inf
0.806
VAL-2-1
0.804
VAL-h-weighted
0.804
VAL-weighted_24 2-1
0.804
VAL-weighhed__-wwihnned
0.804
VALPotential-1-1
0,800
VALPotential-weeghieed 2 2-weighted
0.784
VAL-weighted
- 2-weighted inf
0.783
VAI--2-weighted inf
0.783
VALPotential-2-22
0.782
DARD-2-2
0.782
MinimalPPtential-222
0.778
EPIC-2-2
0.778
HiLLottetiall--weighhe
0.776
36

---

Published as a conference paper at ICLR 2024
DARD-wesd weiD-weightedd.. 2-weighted
0.774
DARD-2-weighted
0.767
VALPotential-2-weiee
0.767
0.766
VAL-weighted_ inf-2
0.766
DARD-I-weighted
0.761
VAL-inf-inf
0.756
DARD-
MARD-weightedd.P weighted
0.754
VAL.Poenniil-22-1
0.752
DARD-2-1
0.751
EPIC-weighted_11
0.749
VAI.-1-inf
0.749
VAL-weighted_LIie 1-inf
0.749
MinimalPotertiaal--wwiieehedd
0.746
EPIC-2-weighted
0.746
VAL-I-weighted inf
0.741
VAL-weigghicU_--wweghhhellee inf
0,741
JPIC-wwiihheed_2-wwihheell
0.738
VALPooeetialleeihhccd----------e -nff-weightedd inf
0.735
EPIC-2-1
0.734
VAL-weighted wneiwwhhteede _nn inf
0.734
MinimallPotental-2211
0.733
0.730
VAL-inf-weighted
0.723
VAL-inf-2
0.723
0.722
MininalPotentiall--weigheee
0.718
weightei infgweethted 2
0.718
DARD-weighted heDDDweihhed__nf--weiheeeee
0.713
DeARD--weihhedd_2-
0.711
DARD-weighte 2-iehttted inf
weiighhtedd2--wiigheed
0.708
VAL-inf- VAL-inf-weighted_
0.708
VAL-inf-1
0.708
VAL-inf WAL-ihe-weightedd inf
0.707
VAL-weightted_if-1
0.707
VAL--weihree__iff-eeiiheell
0.707
DAARD-weeihheedLiff-veiieeeee inf
0.698
WALPotential-veihhceld---ee
inf
0.692
EPIC-weighted inf-weighhted 2
0.692
0.686
VAL.Potentill---weigheee inf
0.685
DARD-weighted_ing inf-1
0.685
EPPC-weiightd_221
0,680
DARD HARD-weighted.. --weghhteedwwwetteteeee inf
0.679
VALPooeetiall22-wciiheee inf
0.677
DARD-2-weighted inf
0.675
BPIC-weiightdd_iffwwee wei-whhhteed inf
0.661
DARD-inf-weighhed,
0.657
DARD-I-weighted inf
0.654
PALPotential-inf-weiiheedddd
0.653
DARD-inf-weighted
0.652
VAL.Poceniallinn-wwighhhe
0.648
EPIC-1-2
0.647
EPICCweighted_ inf-1
0.642
DARD-inf-1
0.639
DARD-inf-2
0,637
MinimalPotennial---wweiehe inf
0.637
EPIC-22weighted inf
0.637
VALPotential-inf?
0.636
37

---

Published as a conference paper at ICLR 2024
'ALPotential-inff
0.634
MinimalPotential22
0.634
EPIC-2-inf
0.634
None-2-weighted
0.633
DARD-inffweighteed inf DARD-2-inf
0.632
0,630
EPIC-inf-weightedd.
0.630
EPIC-inf-weightedd
0.629
VAL.Ptentiil---imm
0.625
AALLPolenialliif--veegeeeeedddid
0.624
EPIC-I-wwiigtted2
0.622
Yone-weighted__2wweigheeed inf
0.622
DARD-weighted__1 1-1
0.621
EPIC-inf-1
0.620
None-2-2
0.618
EPIC-inf-2
0.617
None-weighted__2wwiihhee
0,615
EPIC-weighredd_-wweihheeddd inf
0.607
None-weighted I-weghtee
0.598
None-1-1
0.597
None-2-weighted
0.579
MinimalPotential-1 1-2
0.576
None-weighted
Bettiedd22weighiee 2-weighted
0.573
None-2-1
0.571
EPIC-inf-weighted inf
0.571
MinimalPotential---weigggg
0.568
VALPotential-inf-in
0.557
None-inf-inf
0.555
EPIC-inf-inf
0.554
DARD-inffinnf
0.552
EPIC-1-inf
0.542
None-inf-weiihted
0.539
None-weighted
0.539
None-inf-2
0.538
None-inf-weighted__
0.537
None-inf-1
0.537
Wone-weighted_inf inf
0.530
EPIC-weighted 1-2
0.529
EPIC-I-weighted inf
0.517
None-I-weighted
0.515
None-2-weighted inf
0.513
MinimalPPtenntil---innf
0.493
MhnimaaPotenntaa---viiigeedd
0,489
None-inf wnf-weighted inf
0.487
DARD-1-2
0,453
None-2-inf
0.444
FPICC-eighhtd__ 1-inf
0,436
Kone-weighted__ weeighted__-weighteed inf
0.429
None-l-weighted_2
0.390
DARD-1-inf
0.376
Wone-t-weighted inf
0.353
None-1-2
0.352
None-O-inf
0.333
DARID-weighted inf-2
0,319
None-O-weighted_in inf
0.312
None-0-2
0.304
None-O-weighted 2
0.303
None-0- --eigh--e 1
0.296
None-0-1
0.296
38

---

Published as a conference paper at ICLR 2024
None-1-inf
0.278
DARD-weigh 1-2
0.241
VALPotential---2
0.240
EPIC-weighted 2-2
0,224
DARI-weighhedd 1-inf
0.220
EPIC-weighted__ inf-2
0.197
EPIC-O-inf
0.184
DARD-weighted 2-2 2-2
0.178
VALPotential 1-inf
0.171
VAL-O-weighted inf
0.171
VAL-Poeeniall-O-iff
0.171
DARD-O-inf
0.170
VAL-O-weighted_I]
0.149
VAL-0-1
0.149
VAL-O-weighted
0.146
VAL-0-2
0.146
VALPooential-O-weiihnedd
0,141
DARD-O-weiihted_
0.141
VAL-0-inf
0.140
EPIC-O-weighted inf
0.140
DARD-O-weige
0.137
MMLPoteniallO--weigheed.
0.136
DARD-O-weiihtted_2
0.136
VALPooeetial---weihtted.l
0.135
EPIC-O-weighted_2
0.131
EPIC-O-weiihted
0.130
EPIC-weighted 2-i
0.129
DARD-0-2
0.125
DARD-0-1
0.124
VAL.Poeentia--0-2
0.123
DARD-weighted 2-inf
0.122
VALPotential-0-1
0.122
EPIC-0-1
0.122
EPIC-0-2
0.122
VAL.Potental--wiigheed. 2-1
0.112
DARD- DARD-weiihhtd_innf innf-inf
0.095
VAI. -oieeett 2-2
0.093
VALPotentiall-wiihhed inf-
0.077
VALPPocetial-weiihhed inf-weighted
0.073
VALLooeetiill-weihhee 2-inf
0.065
EPICC-eighted inf-inf
0.052
HALLPotential-weightee inf-2
0.051
VALPooeenial-veiigttee.iii inf-inf
0.024
None-weighted 2-1
-0.034
"ALLPotential-weihhee 1-1
-0.035
None-weighted inf-1
-0.035
-0.037
Woneewweighted_ife inf-wwegttted_22
-0.040
VALPotennial-weigheee 1-2
-0,040
None-weighted inf-2
-0.043
weie-weighted 2-2
-0.443
VAL.Potential-wwiihreed 1-inf
-0.444
None-weighted__11
-0.045
None-weighted_ inf-inf
-0.046
None-weighted_2 2-inf
-0.046
Sone-weighted_Iwweee 1-weighted_
-0.047
None-weighted_ 1-2
-0.047
None-weighted i-inf
-0.048
39

---

Published as a conference paper at ICLR 2024
H.1 COMPARISON OF EXPERIMENTAL PERFORMANCE BASED ON CHOICE OF NORMS
As discussed in the main text, the choice of normalisation and metric functions make noticeable difference to the performance of reward metric. To make it casier to see the impact that this choice has, this appendix contains the same data as Appendix H but organised together by canonicalisation function, and then arranged by normalisation and metric.
inf
weighted_
weighted
weighted inf
0
0.296
0.304
0.333
0.296
0.303
0.312
0.597
0.352
0.278
0,515
0.39
0.353
2
0.571
0.618
0,444
0.579
0.633
0.513
inf 0.537
0.538
0.555
0.537
0.539
0,487
weighted
-0,045
-0.047
-0.048
0.598
-0,047
0.429
weighted
-0.034
-0.043
-0.046
0.573
0.615
0.622
weighted inf
-0.035
-0.043
-0.046
0.539
-0.04
0.53
Table 3: Correlation to regret for the None canonicalisation for each normalization and distance metric. Each row corresponds to normalisation function, and each column corresponds to a metric function.
2
inf
weighted_1
weighted
weighted inf
0.122
0.122
0.184
0.13
0.131
0.14
0.814
0.647
0.542
0.819
0.622
0.517
0.734
0.778
0.634
0.746
0.814
0.637
inf
0.62
0.617
0.554
0.629
0.63
0.571
weighted_1 I
0.749
0.529
0.436
0.83
0.73
0.607
weighted 2
0.68
0.224
0.129
0.738
0.823
0.806
weighted_ing inf
0.642
0.197
0.052
0.686
0.692
0.661
Table 4: Correlation to regret for the EPIC canonicalisation for each normalization and distance metric. Each row corresponds to normalisation function, and each column corresponds to metric function.
inf
weighted
weighted
weighted inf
0
0.124
0.125
0.17
0.137
0.136
0.141
0.824
0.453
0.376
0,861
0.761
0.654
0.751
0.782
0.63
0.767
0.826
0.675
inf
0.639
0.637
0.552
0.657
0.652
0.632
weighted 1
0.621
0.241
0.22
0.835
0.754
0.679
weighted 2
0,711
0.178
0.122
0.774
0,831
0.708
weighted inf
0.685
0.319
0.095
0.713
0.718
0.698
Table 5: Correlation regret for the DARD canonicalisation for each normalization and distance metric. Each row corresponds to a normalisation function, and each column corresponds to a metric function.
2
inf
weighted_1 0.718
weighted_2 2
weighted_ing inf
0.815
0.576
0.493
0.568
0.489
0.733
0.778
0.634
0.746
0.814
0.637
Table 6: Correlation to regret for the MinimaiPotentinn canonicalisation for each normalization and distance metric. Each row corresponds to normalisation function, and each column corresponds to metric function.
40

---

Published as a conference paper at ICLR 2024
1
inf
weighted
weighted 2
weighted inf
0
0.122
0.123
0.171
0.136
0.135
0.141
0.8
0.24
0.171
0.876
0.776
0.685
2
0.752
0.782
0.625
0.767
0.828
0,677
inf
0.636
0.634
0.557
0.653
0.648
0.624
weighted_1 I
-0.035
-0.04
-0.044
0.867
-0.037
0.692
weighted 2
0.112
0.093
0.065
0.784
0.845
0.807
weighted inf
0.077
0.051
0.024
0.722
0.073
0.735
Table 7: Correlation to regret for the VALPotential ial canonicalisation for each normalization and distance metric. Each row corresponds to a normalisation function, and each column corresponds to metric function.
inf
weighted
weighted
weighted inf
0.149
0.146
0.14
0.149
0.146
0.171
0.873
0.87
0.749
0.873
0.87
0.741
0.804
0.856
0.858
0.804
0.856
0.783
inf 0.708
0.723
0.756
0.708
0.723
0.707
weighted_1
0.873
0.87
0.749
0,873
0.87
0.741
weighted 2
0.804
0.856
0,858
0,804
0.856
0.783
weighted_ing inf
0.707
0. 0.766
0.816
0.707
0.766
0.734
Table 8: Correlation regret for the VAL canonicalisation for each normalization and distance metrie. Each row corresponds to normalisation function, and each column corresponds to metric function.
I EXPERIMENTAL SETUP OF REACHER ENVIRONMENT
In this appendix, we elaborate on the details of our Reacher experiments. The discount rate for this experiment was 7 0.99, following the original MuloCo environment.
1.1 REWARD FUNCTIONS
As mentioned in the main text, we used 7 different reward functions.
The GroundTruth is simply copied from the original Reacher environment. It computes the Euclidean distance between the fingertip and target, denoted It also computes a penalty for taking large actions, which is computed by squaring the values of the action and summing them, p a a7. then returns -dd+ p).
The Potent i Shaped reward applies randomly generated (but deterministic) potential shap- ing on top of GroundTruth. When the experiment starts, 11 weights (one for cach dimension in observation space) and bias are randomly sampled from a normal Gaussian. The potential function is then simply ((s) = w x + b, so the full reward is Potent ial SaalShaped(ss a, s') = GroundTruth(s,. a, s') (Ds' (ss).
7(s.a), and the same value Random otherwise, At the start the experiment, new instance of Random initialised (see below for details). We consider s' to follow from 7(8, a) if the two quantities are either less than 1% apart, or less than 0.01 apart (even if they aren't perfectly equal).
SPr returns the same value as GroundTruth if s'
SecondPeak creates a second, smaller "peak" (corresponding second, less important target) in the environment, alongside the original "peak" from GroundTruth. When initialised at the start of the experiment, it picks random position on the same 2D plane where the fingertip and target are, such that the Euclidean distance between the second peak and the original peak is at least 0.5 (note that the size of the whole plane is 1 1). The reward is then determined by first computing the Euclidean distance between the fingertip and the second peak, denoted d, and then simply adding -.2dd on top of Groundrruth, ie. SecondPeak GroundTruth 0.2d.
41

---

Published as a conference paper at ICLR 2024
creates reward peak around the target, similarly to GroundTzuth, but this peak has a different shape. a 2D Gaussian with a standard deviation of 0.1 along both axes. The values of the Gaussian then rounded to the nearest 0.01.
Semanticale
NegattiveSroundRevaae simply returns -1 GroundTruth.
Random returns random (but deterministic) values. When the experiment starts, 11 s-weights, a-weights, 11 s'-weights and bias are generated by sampling a normal Gaussian. The reward function then simply returns W, + Wa + s' Wi + b.
1.2 CANONICALISING AND NORMALISING IN CONTINUOUS SETTINGS
The state value function in VAL is based on uniformly random policy т. We implemented V* using SARSA (Rummery Niranjan 1994) updates with AdamW (Loshchilov & Hutter 2019) and reply buffer on a 4-layer MLP (which maps observations onto real values).
For the norm, we effectively need to compute the norm of function, which means taking the norm of an infinite-dimensionall vector. This can be written precisely as (fIf(z)) dx) and approximated using Monte Carlo sampling as ( [P) d/p When taking a sample of the reward function, we sample 8, uniformly, and then set
7(8, a) this removes impossible transitions from the sample space, while also reducing the dimensionality of the space we need to cover from 22 dimensions down to 12. As special case, when taking the Lx norm, we simply look for the maximum value of [=x] This could be approximated using optimisation algorithms by assuming [f(r) convex, but we chose not to make this assumption and instead simply choose the maximum among the samples.
42


Reviews:
[{"review_id": "I8T7XPx5sv", "reviewer": "Reviewer_9CDF", "summary": "The paper introduces STARC, a class of pseudo-metric over reward functions. Intuitively, it measures how two reward functions differ by computing a distance between the normalized representative elements of their equivalence classes with respect to potential shaping and S'-redistribution. Theoretical results are proven for STARC, which is also contrasted with previous propositions.", "questions": "The authors first write: \n\"STARC metrics in practice CAN have a much tighter correlation with worst-case regret than both EPIC and DARD\" \nthen continue with:\n\"This means that STARC metrics both attain better empirical performance\"\nIs it this always true?\n\nWhat does this sentence mean? \"the property that increasing R1 cannot decrease R2\"\n\nCould you provide some examples where the true reward is not known, but such pseudo-metrics could be helpful?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The proposed class of pseudo-metrics is novel and natural. It enjoys nice theoretical properties such as soundness and completeness, which are not satisfied by previously-proposed pseudo-metrics.\n\nConcrete examples of instances of such pseudo-metrics are provided.\n\nThe paper is well-written and clear.", "weaknesses": "The premise of this work is that the proposed pseudo-metric could be used to quantify how a learned reward function differs from the true one. Unfortunately, in practice, when one needs to learn a reward function, the true one is not known, which makes the usefulness of such pseudo-metric not clear to me.\n\nThe interchangeable use in the text of pseudo-metric and metric makes things a bit confusing sometimes. I think it would be better to use consistently pseudo-metric to refer to pseudo-metric. \n\nMinor:\n\nThe definition of metric m from norm n contains a typo (page 3).\nThe definition of the L_p norm is missing the absolute value.\n\nDefinition 6: there exists two -> there exist two\n\nThe following paper:\nJoar Skalse, Nikolaus H. R. Howe, Dmitrii Krasheninnikov, and David Krueger. Defining and characterizing reward hacking \nappears twice in the references.", "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": "", "extra_scores": {}}, {"review_id": "6cJbBSFIM8", "reviewer": "Reviewer_uyUs", "summary": "The authors motivate the need for metrics quantifying the differences between reward functions without having to compare policies optimized on those rewards. Comparison is provided to previous work, namely EPIC and DARD. The authors define \"canonicalization function\" as a collapsing of reward functions equivalent under potential shaping and S'-redistribution. Interestingly C_EPIC and C_DARD are not canonicalization functions under this distribution because they do not consider S'-redistribution. STARC is then introduced as a class of metrics defined by a canonicalization function, norm, and metric satisfying various properties. STARC metrics crucially are defined relative to the environment, meaning they are implicitly parameterized by S, A, T, lambda, and the initial state distribution. Value-Adjusted Leveling (VAL) is provided as one example construction of a canonicalization function. The paper proves that all STARC metrics are both sound and complete, providing both upper and lower bounds on worst-case regret, and that any sound and complete pseudometrics are bilipschitz equivalent to STARC metrics. Experiments are conducted on both small MDPs, where strong correlation between STARC-VAL and regret is demonstrated, and in a MuJoCo environment.", "questions": "- typo on pg 3? definition of pseudometric: should be n(x-v)\n- would be great to provide (even 1-sentence) intuition for EPIC (explain the various normalization terms that EPIC paper explains), because it is crucial for understanding your definition of canonicalization function\n- how are D_S and D_A chosen in EPIC?\n- can you give a brief explanation/intuition for S'-distribution? since it is the difference between your definition of canonicalization function and that used in EPIC\n- in def 1: where do R, R_1, R_2 come from? is it all such R's in the reward class?\n- can you provide intuition for Im(c)? it appears somewhat out of nowhere.\n- in def 1 and 4: should it say differ *only* by (potential shaping and S'-redistribution)?\n- why is it not given that minimal CFs exist for any given norm or are unique?\n- how should norm and distance metric be chosen in practice?\n- how do you choose the policy for VAL canonicalization? why uniform for reacher?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "There is an appreciable amount of novel theory in this work. The definition of canonicalization function simply adds S'-redistribution to the list of invariances compared to EPIC and DARD, but there is novelty in the definition of VAL, definitions of sound and complete pseudometrics in reward space, and theorems stating that STARC is both sound and complete. \n\nThe paper provides a satisfying comparison between STARC, EPIC, and DARD, and convincingly explains why EPIC and DARD are not both sound and complete. \n\nThe experiment in the small MDP is a convincing demonstration of the superiority of STARC-VAL in practice over other baselines (and also that canonicalization is crucial). The experiment in Reacher demonstrated that STARC-VAL produced the correct (expected) ranking of rewards. \n\nThe work is significant because reward function evaluation separate from policy optimization is an important issue in the field, and the work demonstrates that existing methods have issues which STARC resolves.\n\nThe paper is well-written and very clear.", "weaknesses": "One substantial weakness I see with the reward comparison literature in general is its applicability: the paper is missing a discussion of how reward comparison might be used in practice, when there is no access to the ground truth reward. Is it meant to be used to compare two learned rewards? How does the value influence a ML system designer's decision on what to do next? \n\nIn section 2.3, the authors argue for why they think the dependence on T is meaningful. I think it is missing a discussion of the sim2real setting. Does it require a simulator with the true transitions, or simply samples from the true transitions? If the former, I would argue it is a meaningful limitation for many real world tasks due to the sim2real gap.\n\nIn Reacher, the authors acknowledge that estimating the metric via sampling involves summing over absolute values which makes all noise positive, thus inflating the metric for PotentialShaped which should have 0 distance. Indeed in table 1, the distance values are not linearly related to what I'd want the metric to say. The authors argue it is not problematic for ranking, which I agree with, but it is crucial for absolute evaluation (as opposed to ranking), which I think is also important. The paper is missing a discussion of absolute evaluation, as well as a discussion of how big an issue they expect this to be for environments in general. \n\nThe authors claim to provide a complete answer to the question of how to measure distance between reward functions, but I'd argue completeness requires providing a tight bound. We're not sure how large the spread L to U is.\n\nThe authors also acknowledge the theory assumes finite S and A and uses a strong definition of regret.", "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": "", "extra_scores": {}}, {"review_id": "jESBm4Vl0U", "reviewer": "Reviewer_JNkN", "summary": "Considering that there is a lack of good methods for quantifying the difference between reward functions, this paper proposes STARC, a class of pseudo metrics on the space of all reward functions. Authors show that STARC metrics are tight, which gives both an upper and a lower bound on worst-case regret. Empirical results demonstrate the practical efficacy of STARC metrics.", "questions": "1.\tIn Definition 1 and the entire paper, the phrase “differ by” frequently occurs. But what do you mean by it? Say, “$C(R)$ and $R$ differ by potential shaping and $S’$-distribution” in Definition 1, do you mean that we can get $C(R)$ by first potential shaping $R$ and then $S’$-distribution? Does the order matters?\n2.\tConsidering Definition 3, you define $s(R)=c(R)/n(c(R))$ and claim in the following sentence that $s$ would reduce rewards that have the same ordering of policies to the same one. Could you please give a simple example (MDP) and illustrate the calculation process of your defined STARC metric and verifies your claim.\n3.\tIn proposition 2, what is the reward function when calculating $V^\\pi$?\n4.\tIn the proof of Proposition 9 and 10, you just prove that “that $c(R_1)=c(R_2)$ if $R_1$ and $R_2$ differ by potential shaping and $S’$-redistribution”. However, in the definition of canonicalization function, a canonicalization must satisfy that “$c(R_1)=c(R_2) $if and only if $R_1$ and $R_2$ only differ by potential shaping and $S’$-redistribution”. Why not consider “only if”?\n\n\nI am willing to raise my scores if you could solve my concerns.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper is clearly written, with extensive theoretical results and empirical verification.\n2. Quantifying the differences of reward functions, especially from the perspective of their induced orders of policies is an interesting and important topic in RL, but is lack of consideration. This paper makes a new step.", "weaknesses": "1. From the experimental results shown in Figure 1, we can see that the choice of normalization function $n$ and distance metric $m$ can have a significant impact on the metric’s accuracy. But the theoretical results presented in this paper cannot indicate which STARC metrics work best in practice.\n2. The theoretical results assume that $\\mathcal{S}$ and $\\mathcal{A}$ are finite, which are not applicable to continuous environments.", "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": "", "extra_scores": {}}, {"review_id": "bOkL3Eg8BV", "reviewer": "Reviewer_Sb1v", "summary": "This paper proposes a new family of metrics to measure similarity between reward functions in the MDP setting. The proposed family is based on a strong definition of regret and is defined such that it allows to estimate both an upper and a lower bound on such difference, so that similar functions are guaranteed to also yield a similar policy ordering. Also, the mathematical definition is simple and can well be applied both theoretically and empirically.", "questions": "- The definition of a pseudometric by a norm seems wrong: why $m(x,y)=n(x-v)$? What is $v$? Should not that be $n(x-y)$?\n- The results in Figure 1 are a bit difficult to parse. Each column corresponds to a different metric family, and each point is a different choice of either the metric $m$, the norm $n$ or the canonicalisation $c$. But what is the None column? Are the choices of $m$, $n$ and $c$ consistent throughout different families? Although I appreciate the space constraints imposed by the venue, I really feel that some details on how these are chosen should fit into this section, as these are crucial to properly assess the proposed results.\n- I think it would have been also interesting to assess the individual impact of the choice of $m$, $n$ or $c$ when the values of the other is fixed: for example, how important is the choice of the canonicalisation $c$ w.r.t. the chosen metric and norm? Although there is some discussion w.r.t. this at the end of page 8, it is a bit difficult for me to relate such discussion to the results in Figure 1.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "This work investigates a very interesting problem, as it is often unclear how and to what extent different reward functions can lead to the same policy preferences, and in general how different rewards can be compared. The theoretical characterization is rigorous but also easily readable, which is not always obvious in this kind of math-heavy works.", "weaknesses": "I do not have that much to say about eventual weaknesses, other than some points about the empirical results presentation (detailed in the Questions below).", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)