STARC: A General Framework For Quantifying Differences Between Reward Functions

We thank reviewer Sb1v for their review! Our answers to your questions are as follows:

Questions:

1. You are right, it should read $n(|x-y|)$. We will fix this in the text.
2. The None column corresponds to the case where no canonicalisation function is used. The choices of $m$ and $n$ are consistent throughout these families, except that the MinimalPotential canonicalisation function was not used with the $L_\infty$-norms, because the optimisation algorithm for MinimalPotential fails to converge for these norms. The full details are provided in Appendix F (and especially F.3), but we will move more of this information into the main text, to make the figure easier to parse.
3. We agree that this comparison is relevant, though it would be difficult to fit it in Section 4 given the space constraints. This information can be read from the raw data provided in Appendix G, but we will make this information more accessible.

We hope that this clarifies your questions!

We thank reviewer JNkN for their thoughts and feedback! Our answers to your questions are as follows:

Weaknesses:

1. It is true that our theoretical results cannot indicate which STARC metric would work best in practice, but our experiments suggest that the $L_1$-norm may be the best choice for both $m$ and $n$.
2. We should note that we expect our theoretical results to generalise to (sufficiently well-behaved) continuous environments, as also indicated by our experiments. However, we think it is reasonable to consider this extension of our analysis to be out of scope for this paper.

Questions:

1. Yes, that is correct; when we say that $R_1$ and $R_2$ differ by potential shaping and $S'$-redistribution, we mean that there is a potential shaping transformation $t_1$ and an $S'$-redistribution transformation $t_2$ such that $R_2 = t_1 \circ t_2(R_1)$. Equivalently, it means that there is a potential function $\Phi$ such that $E[R_2(s,a,S')] = E[R_1(s,a,S') + \gamma \Phi(S') - \Phi(s)]$. This also means that the order does not matter. We will amend the text, to make this more clear.
2. We can certainly do this. Consider a Bandit MDP with several actions and one state $s$, let $c$ be the VAL-canonicalisation for the uniformly random policy, and let $n$ be the $L_2$-norm. In this case, two reward functions induce the same ordering of policies if and only if they differ by an affine transformation. Moreover, for any reward function $R$, we have that $V^\pi(s) = E[R(s,A,s)]/(1-\gamma)$, where $\pi$ is the uniformly random policy, and $A$ is sampled uniformly at random. This means that $c(R)(s,a,s) = R(s,a,s) - E[R(s,A,s)]/(1-\gamma) + \gamma E[R(s,A,s)]/(1-\gamma) = R(s,a,s) - E[R(s,A,s)]$, where $A$ is sampled uniformly at random. In this case, it is easy to see that $c(R_1) = c(R_2)$ if and only if there is a constant $b$ such that $R_2 = R_1 + b$. Division by $n(c(R))$ normalises the resulting reward. This means that $s(R_1) = s(R_2)$ if and only if there is a positive constant $a$ such that $c(R_2) = a \cdot c(R_1)$. Since $c$ is linear, this means that $c(R_2) = c(a \cdot R_1)$. Putting this together, we get that $s(R_1) = s(R_2)$ if and only if $R_2 = a \cdot R_1 + b$ for some $a$ and $b$, which in turn is the case if and only if $R_1$ and $R_2$ induce the same ordering of policies.
3. $V^\pi$ should be calculated using the reward function that is being canonicalised. I.e., when calculating $c(R_1)$, $V^\pi$ should be calculated using $R_1$, and when calculating $c(R_2)$, $V^\pi$ should be calculated using $R_2$, etc. We will clarify this in the text.
4. It is correct that it should be "if and only if", and we will amend the proofs to make this explicit. Note that if $R$ and $c(R)$ differ by potential shaping and $S'$-redistribution for all $R$, then $R_1$ and $c(R_1)$ differ by potential shaping and $S'$-redistribution, and likewise for $R_2$ and $c(R_2)$. Then if $c(R_1) = c(R_2)$, we can combine these transformations, and obtain that $R_1$ and $R_2$ also differ by potential shaping and $S'$-redistribution.

We hope that these points help to clarify our paper, and that the reviewer will consider increasing their score!

Why does the order not matter?

If it is possible to produce $R_2$ from $R_1$ by first applying potential shaping and then applying $S'$-redistribution, then it is also possible to do this by first applying $S'$-redistribution, and then applying potential shaping, and vice versa. To see this, note that we can produce $R_2$ from $R_1$ by potential shaping if and only if $R_2 = R_1 + F$, where $F : S \times A \times S \to \mathbb{R}$ is a reward function such that $F(s,a,s') = \gamma \Phi(s') - \Phi(s)$ for some potential function $\Phi$. Similarly, we can produce $R_2$ from $R_1$ via $S'$-redistribution if and only if $R_2 = R_1 + G$, where $G : S \times A \times S \to \mathbb{R}$ is a reward function such that $\mathbb{E}_{S' \sim \tau(s,a)}[G(s,a,S')] = 0$. That means that we can produce $R_2$ from $R_1$ by a combination of potential shaping and $S'$-redistribution if and only if we can express $R_2$ as $R_1 + F + G$, where $F$ and $G$ satisfy the conditions above. Since $R_1 + F + G = R_1 + G + F$, the order does not matter. We will clarify this in the main text.

Please give proofs in your example if you say something like "only if".

In each case in that example, the "only if" parts follow from very straightforward though somewhat tedious algebra. Do you think it would be beneficial to provide this in full?

Moreover, is this bandit with only one state too special to be a good example?

Perhaps, but if we add several states then it will quickly become very complicated to directly determine neccessary and sufficient conditions for two reward functions to induce the same policy order, except by simply appealing to Theorem 2.6 in Skalse & Abate, 2023. This would make the example less illuminating, to the point that it may be easier to simply refer to the proof in Skalse & Abate, 2023, together with Definition 1 and 3 in our paper.

If possible, please update your manuscript and upload a revised version.

We will upload an amended manuscript which incorporates all the feedback from the reviewers in a few days [EDIT: we have now done this]. As for the proofs of Proposition 9 and 10 specifically, note that all which has to be done is to add the two sentences from point 4 in our previous response.

We hope that this clarifies your questions, and that you will consider increasing your score!

We would like to thank reviewer 9CDF for their review and feedback!

We should clarify that the intended use for these metrics is to evaluate reward learning algorithms, in a setting where the true reward function is known. For example, we may randomly generate reward functions, use a reward learning algorithm, and then measure how different the learnt reward function is from the true reward function. Alternatively, they can also be used in theoretical work, where we may wish to bound the distance between the true reward and the learnt reward (given different amounts of training data, for example). Such analysis would then indicate how reliable a given reward learning method is, which then tells us how accurate we should expect a learnt reward function to be, in a setting where the true reward function is not known. Note that Gleave et al is cited 37 times, and Wulfe et al is cited 6 times; these references will provide examples of practical situations where reward function pseudo-metrics can be used. For example, see eg Adeniji et al, 2023, Figure 1 in Sanghvi et al, 2021, or Figure 4(c) in Liang et al, 2022. We will amend the introduction, to make this intended use case more clear.

We will amend the text to consistently use the term pseudo-metric, to make it less ambiguous. We also fix the typos that you have spotted -- thank you for pointing them out to us!

Questions:

1. Our experiments suggest that this is not always true, but that it is true for most reasonable choices of normalisation norm and metric --- see Figure 1.
2. This means that if two reward functions $R_1, R_2$ and two policies $\pi_1, \pi_2$ satisfy that $J_1(\pi_1) > J_1(\pi_2)$, then it must be the case that $J_1(\pi_1) \geq J_1(\pi_2)$. In other words, if the expected cumulative sum of $R_1$-reward increases when we go from $\pi_2$ to $\pi_1$, then it cannot be the case that the expected cumulative sum of $R_2$-reward decreases. We will amend the text, to make this more clear.
3. We can evaluate a reward learning algorithm in a setting where the true reward is known. The result of this evaluation would then inform how much we should trust that algorithm, in a setting where the true reward is not known.

We hope that this will help to clarify our paper, and that the reviewer might consider increasing their score.

We thank reviewer uyUs for their feedback! We have responded to your questions and concerns below:

Weaknesses:

1. The intended use for these metrics is to evaluate reward learning algorithms, in a setting where the true reward function is known. For example, we may randomly generate reward functions, use a reward learning algorithm, and then measure how different the learnt reward function is from the true reward function. Alternatively, they can also be used in theoretical work, where we may wish to bound the distance between the true reward and the learnt reward (given different amounts of training data, for example). Such analysis would then indicate how reliable a given reward learning method is, which in turn then tells us how accurate we should expect a learnt reward function to be, in a setting where the true reward function is not known. Note that Gleave et al is cited 37 times, and Wulfe et al is cited 6 times; these references will provide examples of practical situations where reward function pseudo-metrics can be used. For example, see eg Adeniji et al, 2023, Figure 1 in Sanghvi et al, 2021, or Figure 4(c) in Liang et al, 2022.
2. We do not require a simulator with the true transitions --- samples from the true transitions are sufficient. For example, the VAL canonicalisation can be estimated using samples. This is discussed in the first paragraph of Section 2.3.
3. We agree that this may be a limitation in some contexts. However, note that the error can be reduced by increasing the number of samples used in the estimation. Moreover, it can be eliminated completely if the STARC metric is computed exactly (although this may not be feasible in large environments).
4. We agree that the spread between L and U is important. However, note that any metric which is sound and complete must be bilipschitz equivalent to STARC metrics -- this means that whichever metric has the smallest spread between L and U must be quite similar to STARC metric (and it might be an instance of a STARC metric). Note also that the exact value of L and U depends on the transition function; to see this, consider the second figure in Appendix B (the transition function affects the diameter of $\Omega$).

Questions:

1. Yes, this is indeed a typo, thank you for pointing this out.
2. We describe EPIC in Section 1.2. We can make this description more extensive, to make it easier to understand.
3. In our experiments, $D_S$ and $D_A$ were both uniform for EPIC. We will make sure that this is included in Appendix F; thank you for spotting this omission.
4. $S'$-redistribution is simply any transformation that never changes the expected value of the reward function. For example, suppose we have a nondeterministic MDP where an action $a$ in state $s$ leads to $s_1$ or $s_2$ with equal probability, and that $R_1(s,a,s_1) = 1$, $R_1(s,a,s_1) = 0$. Then $S'$-redistribution could be used to produce a reward function $R_2$ where $R_2(s,a,s_1) = R_2(s,a,s_2) = 0.5$.
5. The conditions in Definition 1 are meant to hold for all reward functions -- it can thus be read as "for all $R$, ..., and for all $R_1, R_2$, ... We will amend the text to make this more clear.
6. $\mathrm{Im}(c)$ is the output of the canonicalisation function, when it is applied to the space of all reward functions. From the definition of canonicalisation functions, we get that this is a linear subspace of $\mathcal{R}$ in which no reward functions differ by potential shaping or $S'$-redistribution. A geometric description of this is given in Appendix B, but we can also describe this in more detail in the main text.
7. Yes. We will amend the text to make this clear.
8. For example, relative to the $L_1$-norm or the $L_\infty$-norm, there will be multiple minimal canonicalisation functions. This is because the unit balls of these norms are not strictly convex.
9. We expect that it in practice often will be best to pick $n$ and $m$ so that they can be computed easily. Our experiments suggest that the $L_1$-norm is the best (unweighted) norm for both $n$ and $m$.
10. VAL is a valid canonicalisation function for any choice of policy, so we simply used a policy for which $V^\pi$ would be easy to learn. The benefit of using a uniform policy, rather than some deterministic policy, is that exploration then is built in automatically.

We hope that this clarifies our paper, and that the reviewer might consider increasing their score.