Quantifying Differences in Reward Functions
Authors: Adam Gleave
Michael D Dennis
Shane Legg
Stuart Russell
Jan Leike
Venue: ICLR 2021 Spotlight (2021)
Keywords: rl
irl
reward learning
distance
benchmarks

Abstract: For many tasks, the reward function is inaccessible to introspection or too complex to be specified procedurally, and must instead be learned from user data. Prior work has evaluated learned reward functions by evaluating policies optimized for the learned reward. However, this method cannot distinguish between the learned reward function failing to reflect user preferences and the policy optimization process failing to optimize the learned reward. Moreover, this method can only tell us about behavior in the evaluation environment, but the reward may incentivize very different behavior in even a slightly different deployment environment. To address these problems, we introduce the Equivalent-Policy Invariant Comparison (EPIC) distance to quantify the difference between two reward functions directly, without a policy optimization step. We prove EPIC is invariant on an equivalence class of reward functions that always induce the same optimal policy. Furthermore, we find EPIC can be efficiently approximated and is more robust than baselines to the choice of coverage distribution. Finally, we show that EPIC distance bounds the regret of optimal policies even under different transition dynamics, and we confirm empirically that it predicts policy training success. Our source code is available at https://github.com/HumanCompatibleAI/evaluating-rewards.

Published as a conference paper at ICLR 2021
QUANTIFYING DIFFERENCES IN REWARD FUNCTIONS
Adam Gleavel22 Michael Dennis'
Shane Legg'
Stuart Russell"
Jan Leike
UC Berkeley DDeppMind
OOpenAl
gleave@berkeley.cm
ABSTRACT
For many tasks, the reward function is inaccessible to introspection or too complex to be specified procedurally, and must instead be learned from user data. Prior work has evaluated learned reward functions by evaluating policies optimized for the learned reward. However, this method cannot distinguish between the learned reward function failing to reflect user preferences and the policy optimization pro- cess failing optimize the learned reward. Moreover, this method can only tell us about behavior in the evaluation environment, but the reward may incentivize very different behavior in even a slightly different deployment environment. To address these problems, we introduce the SisivvalettPPoliae Invariant Comparison (EPIC) distance to quantify the difference between two reward functions directly, without a policy optimization step. We prove EPIC is invariant reward functions that always induce the same optimal policy. Furthermore, we find EPIC can be efficiently approximated and is more robust than baselines to the choice of coverage distribution. Finally, we show that EPIC distance bounds the regret optimal policies even under different transition dynamics, and confirm empiri- cally that it predicts policy training success. Our source code available at ht tps //github. com Hww.//ouaannnaaaaaaaaaee www.b//llleeaaaaaaeaeaaaaaaaaaaa uut ing nng rewards
equivalence class of
INTRODUCTION
Reinforcement learning (RL) has reached surpassed human performance in many domains with clearly defined reward functions, such as games (20 15 23 and narrowly scoped robotic manipulation tasks []6. Unfortunately, the reward functions for most real-world tasks are difficult or impossible to specify procedurally. Even a task as simple as peg insertion from pixels has non-trivial reward function that must usually be learned [22] IV.AJ. Tasks involving human interaction can have far more complex reward functions that users may not even be able to introspect on. These challenges
have inspired work on learning a reward function, whether from demonstrations 13
26 g
preferences
1 25
6,
18
27 or both [10 4
Prior work has usually evaluated the learned reward function it using the "rollout method": training policy J to optimize it and then examining rollouts from g Unfortunately, using RL to compute Th is often computationally expensive. Furthermore, the method produces false negatives when the reward f matches user preferences but the RL algorithm fails to optimize with respect to R.
The rollout method also produces false positives. Of the many reward functions that induce the desired rollout in given environment, only small subset align with the user's preferences. For example, suppose the agent can reach states (A, B, C}. If the user prefers A > B > C, but the agent instead learns A C > B, the agent will still go to the correct state A. However, if the initial state distribution or transition dynamics change, misaligned rewards may induce undesirable policies. For example, if A is no longer reachable deployment, the previously reliable agent would misbehave by going to the least-favoured state C.
We propose instead to evaluate learned rewards via their distance from other reward functions, and summarize our desiderata for reward function distances in Table For benchmarks, it is usually possible to directly compare a learned reward ft to the true reward function R. Alternatively, benchmark creators can train a "proxy" reward function from a large human data set. This proxy can then be used as stand-in for the true reward R when evaluating algorithms trained on different or smaller data set.
Work partially conducted while at DeepMind.

---

Published as a conference paper at ICLR 2021
Table Summary of the desiderata satisfied by each reward function distance. Key the distance is: pseudometric (ection3); invariant to potential shaping [14] and positive rescaling (section B
computationally efficient approximation achieving low error (section 6.1]: robust to the choice of coverage distribution (section 6.2); and predictive of the similarity of the trained policies (section 6.3
Distance
Pseudometric
Invariant
Efficient
Robust
Predictive
EPIC
NPEC
/ X
X
X
ERC
/
X
Comparison with a ground-truth reward function rarely possible outside of benchmarks. However, even in this challenging case, comparisons can at least be used to cluster reward models trained using different techniques or data. Larger clusters are more likely to be correct, since multiple methods arrived at similar result. Moreover, regret bound (Theorem 4.9) suggests could use interpretability methods 12] on one model and get some guarantees for models in the same cluster.
We introduce the Equivalent-Policy Invariant Comparison (EPIC) distance that meets all the criteria in Table We believe EPIC is the first method to quantitatively evaluate reward functions without training a policy. EPIC (section canonicalizes the reward functions' potential- potential-based shaping (14), then takes the correlation between the canonical rewards over a coverage distribution of transitions. which partially satisfy the criteria.
We also introduce baselines NPEC and ERC (section 5
EPIC works best when 'D has support on all realistic transitions. We achieve this in our experiments by using uninformative priors, such rollouts of policy taking random actions. Moreover, find EPIC is robust to the exact choice of distribution D) producing similar results across a range of distributions, whereas ERC and especially NPEC are highly sensitive to the choice of D (section 6.2).
Moreover, low EPIC distance between a learned reward R and the true reward predicts low regret. That is, the policies тR and πa optimized for R and obtain similar returns under Theorem 4.9 bounds the regret even in unseen environments; by contrast, the rollout method can only determine regret in the evaluation environment. We also confirm this result empirically (section 6.3
RELATED WORK
There exist variety of methods to learn reward functions. Inverse reinforcement learning (IRL) a common approach that works by inferring reward function from demonstrations, The IRL problem inherently underconstrained: many different reward functions lead the same demonstrations. Bayesian IRI. [1 handles this ambiguity by inferring a posterior over reward functions. By contrast, Maximum Entropy IRI. (26) selects the highest entropy reward function consistent with the demonstrations; this method has scaled to -ighnnimeniional environments g].
An alternative approach is to learn from preference comparisons between two trajectories 25 68
T-REX 4 is hybrid approach, learning from ranked set of demonstrations. More directly, Cabi
et al. 5 learn from "sketches" of cumulative reward over an episode.
To the best of our knowledge, there is prior work that focuses evaluating reward functions directly. The most closely related work is Ng et al. [14), identifying reward transformations guaranteed not change the optimal policy. However, variety of ad-hoe methods have been developed to evaluate reward functions. The rollout method evaluating rollouts of a policy trained on the learned reward is evident in the earliest work IRL [33. Fu et al. refined the rollout method testing on a transfer environment, inspiring our experiment in section 6.3 Recent work has compared reward
functions by scatterplotting returns 1T 4 inspiring our ERC baseline (section 5.T
BACKGROUND
This section introduces material needed for the distances defined in subsequent sections. We start by introducing the Markov Decision Process (MDP) formalism, then deseribe when reward functions induce the same optimal policies in MDP, and finally define the notion of a distance metric.
2

---

Published as a conference paper at ICLR 2021
Definition 3.1. A Markov Decision Process (MDP) M = (S,A, d.,, do T.R) consists of set of states S and a set of actions A; a discount factor 7 E [o. 1]: an initial state distribution du(s); a transition distribution T(s' s, a) specifying the probability of transitioning to s' from s after taking action o; and a reward function R(s, 0, 8') specifying the reward upon taking action a in state s and transitioning to state 8'
A trajectory T = (So, an $1, "1. consists of a sequence of states s, E and actions a, E A. The return trajectory is defined as the sum of discounted rewards, g(T; R?) = > - -== 7 R(5 a2s 8241). )
where the length of the trajectory |T| may be infinite.
In the following, we assume a discounted (7 < 1) infinite-horizon MDP. The results can be generalized to undiscounted (:- = 1) MDPs subject to regularity conditions needed for convergence.
A stochastic policy <a s) assigns probabilities to taking action E AA in state E S. The objective of an MDP is to find a policy æ that maximizes the expected return (TT)) = (x)()) [9(T; R)], where T(T) a trajectory generated by sampling the initial state 8q from dg each action dt from the policy (a, (x)) and successor states 8441 from the transition distribution T(8++1 8,, 04). An MDP M has a set of optimal policies π r*(M) ) that maximize the expected return, ' (Ad) = arg max, G(T)).
In this paper, consider the case where we only have access an MDPIR, M (S, A, do. T). The unknown reward function I must be learned from human data. Typically, only the state space S, action space A and discount factor y are known exactly, with the initial state distribution do and transition dynamics T only observable from interacting with the environment M Below, we describe equivalence class whose members guaranteed to have the same optimal policy set in any MDPAR M with fixed S, AA and (allowing the unknown T and dg to take arbitrary values). Definition 3.2. Let " [0. 1] be the discount factor, and T S ++ R real-valuse function. Then R(s, a, 8') = (s') (s) is a potential shaping reward, with potential + [14].
Definition 3.3 (Reward Equivalence). We define two bounded reward functions RA and Rş to be equivalent, R = R..for a fixed (S, (. if and only if there exists a constant X > 0 and a bounded potential function ob S - R such that for all s, E S and A:
RB(s, a, s') XRA(s, a²) (.)5')++) (s') ((s).
(1)
Proposition 3.4. The binary relation = is an equivalence relution. Let RA, Ra, Re SS:Axxx + R be bounded reward functions. Then =\t is reflexive, RA RAi symmetric, RA =\t Rg implies Rg = Rai and transitive, (Ra- = RB) A (Rg = Rc) implies RA = Rc.
Proof. See section
1 in supplementary material.
The expected return of potential shaping ( - (ss) on a trajectory segment (so. .S). is yd ((T)) - (so). The first term 7 ((T) -> 0 as T + co, while the second term ((5)) only depends on the initial state, and so potential shaping does not change the set of optimal policies. Moreover, any additive transformation that is not potential shaping will, for some reward R and transition distribution T, produce a set of optimal policies that is disjoint from the original [4].
The set of optimal policies is invariant to constant shifts E R in the reward, however this can already be obtained by shifting & by --1 Scaling a reward function by a positive factor À > 0 scales the expected return of all trajectories by X, also leaving the set of optimal policies unchanged.
If RA Rg for some fixed (S.A,7) then for any MDPAR M (S.A. y, do, T) we have T ((M Ra)) = x² ((M RR))). where (M", RR denotes the MDP specified by M with re- ward function R. In other words, RA and Rn induce the same optimal policies for all initial state distributions do and transition dynamics? T.
Definition 3.5. Let X be set and d X x X + [0, oo) a function. d is a premetric if d(z, 0 for all x E X. d is pseudometric if. furthermore, il is symmelric, d(z, y) = d(y. for all x, y E X; and satisfies the triangle inequality, d(xx2) 1 d(x, y) + d(y. for all x. y, z X. d is metric if. y.
furthermore, for all x, E X, d(x,v) v) = +
We wish for d( d(RA, RB) = O whenever the rewards are equivalent, RA Rg, even if they not identical, RA f RB- This is forbidden in a metric but permitted in a pseudometric, while retaining
"Note constant shifts in the reward of an undiscounted MDP would cause the value function diverge. Fortunately, the shaping (08')) +(s) is unchanged by constant shifts to & when 7
3

---

Published as a conference paper at ICLR 2021
other guarantees such symmetry and triangle inequality that metric provides. Accordingly, pseudometric is usually the best choice for a distance over reward functions.
4 COMPARING REWARD FUNCTIONS WITH EPIC
In this section we introduce the Equivalent-Polic Invariant Comparison (EPIC) pseudometric. This novel distance canonicalizes the reward functions' potential-based shaping, then compares the canonical representatives using Pearson correlation, which is invariant to scale. Together, this construction makes EPIC invariant reward equivalence classes. See section A.3.2 for proofs.
We define the canonically shaped reward CDS.DA (R) as an expectation over some arbitrary distribu- tions Ds and DA over states S and actions A respectively. This construction means that CDs.DA (R) does not depend on the MDP's initial state distribution do or transition dynamics TT In particular, may evaluate on transitions that impossible in the training environment, since these may become possible in a deployment environment with a different do or T.
Definition 4.1 (Canonically Shaped Reward). Let S x X S + IR distributions Ds (SS) and D E ((A) over states and actions, let S and S' be random variables independently sampled from Ds and sampled from DA We define the canonically shaped be:
reward function. Given
DA (R) (s,a,s') R(s,a, + EE [yRi(ss A,S") R(s, (AAAA)))--(((A,,,, A,),, (2)
Informally, if R' is shaped by potential L, then increasing ((s) decreases R'ss, a, but in- creases E (- S')), canceling. Similarly, increasing (s')) increases It' It's,, a, 8') but decreases E R' A,S') Finally, Rl A, S")] centers the reward, canceling constant shift.
Proposition 4.2 (The Canonically Shaped Reward is Invariant to Shaping). Let R S A
be a reward function and +b S Th a potential function. Let E [0, be a discount rate, and Dg E (SS) and D (AA) be distributions over states and actions. Let R' denote R shoped by d: R'(ss, 0. = R(s, s') +s5 - 4(s). Then the canonically shaped R' and R are equal: DA (Rt) DA (R).
4.2 holds for arbitrary distributions Ds and DA- However, in the following Proposition we show that the potential shaping applied by the canonicalization CD.. D (R) is more influenced by perturbations to It of transitions (s, a, s') with high joint probability. This suggests choosing Ds and DA to have broad support, making CDA.DA (R) more robust to perturbations of any given transition.
Proposition
Proposition 4.3. Let S and A be finite, with [S] 2 2. Let Ds E A(S) and DA A(A). Let R, v S x A Ax& S + R be reward functions, with ass,a,s) = XI((s.a, = (I. u, x'),, ]. X E R, I, and u E A. Let DDD.DDD (R) a, s') CD. (R) (s,a, R(s,a,s'). Then:
(R
DD..DA (R) A(1 DA(u)Ds(z'),
(3)
We have canonicalized potential shaping; next, we compare the rewards in scale-invariant manner. Definition 4.4. The Pearson distance between random variables X and Y is defined by the expression
D), /1 p(X,Y)/V2, where p(X,Y) is the Pearson correlation between X and Y.
Lemma 4.5. The Pearson distance D is a pseudometric. Moreover, let a, b (0, co), c, e R and X,Y be random variables. Then it follows that 0 S D,(aX + c, bY + d) D,
We can now define EPIC in terms of the Pearson distance between canonically shaped rewards.
Definition 4.6 (Fquivalent-Policy Invariant Comparison (EPIC) pseudometric). Let 'D be some coverage distribution over transitions 2 s'. Let S, A, S" be random variables jointly sampled from D. Let Ds and D A be some distributions over states S and A respectively. The Equivalent-Pon -Pliccy Invariant Comparison (EPIC) distance between reward functions RA and Rg is:
DEPIC RB) (CD.s.DD (S, CDS.PA (BB) (S,
(4)
Theorem 4.7. The Equivalent-Polie Invariant Comparison distance is pseudometric.
Since EPIC is a pseudometric, it satisfies the triangle inequality. To see why this is useful, consider an environment with an expensive to evaluate ground-truth reward R. Directly comparing many learned
4

---

Published as a conference paper at ICLR 2021
rewards R to R might be prohibitively expensive. We can instead pay a one-off cost: query R finite number of times and infer a proxy reward Rp with DEPIC Rp) S c. The triangle inequality allows us to evaluate It via comparison to Rp, since DEPIC Rt R) I DEPIC Rp) + e. This is particularly useful for benchmarks, which can be expensive to build but should be cheap to use.
Theorem 4.8. Let RA. R' RB, R'B S xxxx A x S + I. be reward functions such that R'a RA and R'g= = Rg. Then S DEPIC(R's A. R'g) = PEPIC(RA. RB) 1.
The following is main theoretical result, showing that DEPIC RB) distance gives an upper bound on the difference in returns under either RA or Ry between optimal policies RA and Th. In other words, EPIC bounds the regret under RA of using R instead of RRA Moreover, by symmetry DEPIC RA, Rg) also bounds the regret under Rg of using TA instead of Tia
Theorem 4.9. Let M be a d-discounted MDPR with finite state and action spaces S and A. Let RA, RB S A S + R. be rewards, and TA T be respective optimal policies. Let DD(1, 8t, 0t, 91.41) denote the distribution over transitions S x A x S induced by policy at time I, and D(s,a, (8,,,88) 8') ) be the coverage distribution ased compute DEPIC- Suppose there exists K >> 0 such that KD(stt, at, s(41) ) 2 Dx (t, st, at St+1) for all times t E N. triples (st, at s(+1) E S x A x S and policies iT E (TA:TBB Then the regret under RA from executing π instead of A is at most
(TA) GRA(TT) S 16l]| (1-7)=² DEPIC(RA, RB),
where GR(T) is the return policy x under reward R.
We generalize the regret bound to continuous spaces in theorem A.16 via Lipschitz assump- tion, with Wasserstein distance replacing K. Importantly, the returns of T and T converge as DEPIC RR,, RB) - 0 in both cases, no matter which reward function you evaluate on.
The key assumption is that the coverage distribution D has adequate support for transitions occurring in rollouts of nr' and T--- The bound is tightest when D is similar to D=; and Dr;-- However, computing TÀ and wi is often intractable. The MDP M may be unknown, such as when making predictions about an unseen deployment environment. Even when M is known, RL is computationally expensive and may fail to converge in non-trivial environments.
In finite cases, a uniform D satisfies the requirements with K S | In general. it is best to choose D to have broad coverage over plausible transitions. Broad coverage ensures adequate support for P=; and Dr;- But excluding transitions that are unlikely or impossible occur leads to tighter regret bounds due to smaller K (finite case) or Wasserstein distance (continuous case).
While EPIC upper bounds policy regret, does not lower bound it. In fact, no reward distance can lower bound regret in arbitrary environments. For example, suppose the deployment environment transitions to a randomly chosen state independent of the action taken. this case, all policies obtain the same expected return, so the policy regret is always zero, regardless of the reward functions.
To demonstrate EPIC's properties, we compare the gridworld reward functions from Figure 1 reporting the distances between all reward pairs in Figure A.2 Dense is a rescaled and shaped version of Sparse, despite looking dissimilar at first glance, so DEPIC (Sparse, Dense) = 0. By contrast, DEPIC (Path, Cliff) 0.27. In deterministic gridworlds, Path and Cliff have the same optimal policy, so the rollout method could wrongly conclude they are equivalent. But in fact the rewards are fundamentally different: when there is significant risk of "slipping" in the wrong direction the optimal policy for Cli walks along the top instead of the middle row, incurring a penalty to avoid the risk of falling into the -4 "cliff"
For this example, we used state and action distributions Ds and D uniform over S and A, and coverage distribution D uniform over state-action pairs (s, a), with s' deterministically computed. is important these distributions have adequate support. As an extreme example, if Ds and D have no support for a particular state then the reward of that state has no effect on the distance. We can compute EPIC exactly in tabular setting, but in general use a sample- based approximation (section A.I.I)
5 BASELINE APPROACHES FOR COMPARING REWARD FUNCTIONS
Given the lack of established methods, we develop two alternatives as baselines: Episode Return Correlation (ERC) and Nearest Point in Equivalence Class (NPEC).
5

---

Published as a conference paper at ICLR 2021
Sparse Reward
Dense Reward
Path Reward
cliff Reward
0
4
44
0
0
0
-4
-4
0
0
1
11
1
0000
0
0
4
1
4
4
4
2
Figure 1: Heatmaps of four reward functions for 3 x 3 gridworld. Sparse and Dense look different but are actually equivalent with DEPIC (Sparse, Dense) = 0. By contrast, the optimal policies for Path and Cliff are the same if the gridworld deterministic but different if it is "slippery". EPIC recognizes this difference with DEPIC (Path, Cliff) 0.27. Key: Reward R(s,s) s') for moving from to is given by the triangular wedge in cell s that adjacent cell s'. R(s, s) is given by the central circle in cell s. Optimal action(s) (deterministic, infinite horizon, discount 7 = 0.99) have bold labels. See Figure A.2 for the distances between all reward pairs.
5.1 EPISODE RETURN CORRELATION (ERC)
The goal of MDP is maximize expected episode return, so it is natural to compare reward functions by the returns they induce. If the return of a reward function RA is a positive affine transformation of another reward Rg, then RA and Rg have the same set of optimal policies. This suggests using Pearson distance, which is invariant to positive affine transformations.
Definition 5.1 (Episode Return Correlation (ERC) pseudometric). Let 'D be some distribution over trajectories. Let E be random variable sampled from D. The Episode Return Correlation distance between reward functions R and Rg the Pearson distance between their episode returns on D, DEnC A,, RB) = Dp(s( E; RA), E; RB)).
Prior work has produced scatter plots of the return of R against R episodes [ Figure 3] and fixed-length segments [10] section DJ. ERC is the Pearson distance of such plots, so is a natural baseline. We approximate ERC by the correlation of episode returns finite collection of rollouts.
ERC is invariant to shaping when the initial state and terminal state 8y are fixed. Let R be reward function and & potential function, and define the shaped reward R' l'(s, a') = R(s, ((ssa, a,
( (ss). The return under the shaped reward on trajectory 7 = (sp. 4g. ST) is ((s)) constant. It follows that ERC is invariant to shaping, as Pearson distance is invariant to constant shifts. In fact, for unfinitehhorizon discounted MDPs only so needs to be fixed, since 72 ((sr) + 0 as T co.
g(r; R') g(:: R) y ((T)) ((s)). Since so and ST are fixed, 7 <T'((T))
However, if the initial state is stochastic, then the ERC distance can take on arbitrary values under shaping. Let RA and Rg two arbitrary reward functions. Suppose that there are at least two distinct initial states, 8x and sy, with non-zero measure in D. Choose potential ((s) 0 everywhere except (sxx) = (ssy) = c. and let R'A and R' denote RA and Rg shaped by 2. As co, the correlation (g[ E; R', E;; RT) + 1. This is since the relative difference tends to zero, even though g EE; R'a) and g E; R',, continue to have the same absolute difference as e varies. Consequently, the ERC pseudometric DERC(R', R'A R'g) + 0 as + By analogous argument, setting (sx) = and & ((s)) = -c gives DERC( RA Rg) 1 as Xo.
5.2 NEAREST POINT IN EQUIVALENCE CLASS (NPEC)
NPEC takes the minimum L" distance between equivalence classes. See section A.3.3 for proofs.
Definition 5.2 (L distance), Let D be coverage distribution over transitions 3 s' and let p > 1 be a power. The LP distance between reward functions RA and Rg is the LP norm of their difference: DiP ( RA, Rs) (Ba,,s'a [|RA(8,a, a,,,,,,,, RB(s, a, a, sP)

---

Published as a conference paper at ICLR 2021
1.0
S
-0.00
0.51
0.00
0.51
0.63
0.00
0.88
0.22
0.86
0.96
0.00
0.41
0.56
0.56
0.57
D(RA, RB)
0.51
0.00
0.51
0.00
0.55
0.92
0.00
0.94
0.04
0.74
0.41
0.00
0.61
0.55
0.62
RA
0.00
0.51 0.00
0.51
0.63
0.58
0.95
0.00
0.81
0.97
0.56
0.61
0.00
0.11
0.64
0.5
D
0.51
0.00
0.51 0.00
0.55
0.88
0.04
0.84
0.00
0.58
0.56
0.55
0.11
0.00
0.64
M
0.63
0.55
0.63
0.55
0.00
0.93
0.79
0.80
0.62
0.00
0.57
0.62
0.64
0.64
0.00
0.0
Set
S
Dunt
D
M
Ser
S
Dunt
D
M
S.rtt
S
Dart
M
R
RB
RB
(a) EPIC
(b) NPEC
(c) ERC
Figure 2: Approximate distances between hand-designed reward functions in Poi MtMsss, where the agent moves on line trying to reach the origin. EPIC correctly assigns distance between equivalent rewards such as rD Sart) while DN rt, Sart)
0.58 and DERC Sat) 0.56. The coverage distribution D is sampled from rollouts of a policy Tuni taking actions uniformly at random. accelerate # E R, producing future
Key: The agent has position x E R, velocity & E IR and position E R. quadratic penalty on control ø², st no control penalty. S is Sparse(z) (z) 1[[x|| < 0.05). is shaped Dense(r, x²) Sparse(x) |a'| |ar]. while is Magnilude(z) -|r]].
The IP distance is affected by potential shaping and positive rescaling that do not change the optimal policy. A natural solution is take the distance from the nearest point in the equivalence class: D (R RB) = inf DI= (R's RB). Unfortunately, D DEPEC is sensitive to RB 's scale.
is tempting to instead take the infimum over both arguments of Dr. However, inf RR,,,, Ry DT., Ra) = 0 since all equivalence classes come arbitrarily close to the origin in L space. Instead, we fix this by normalizing D&PEC
Definition 5.3. NPEC is defined by DxpEc(BAy RB) = D&PEC Ra) RB) when PP RB)= # O, and is otherwise given by DNPEC( RB) = O.
If D DNige (Zero, RB)= = 0 then DKrec (Ra, RB) = since RA can be scaled arbitrarily close to Zero. Since all policies are optimal for R = Zero, we choose DNPEC (RA. RB) 0 in this case.
Theorem 5.4. DNFEC is premetric on the space of bounded reward functions. Moreover, let be bounded reward functions such that RA RA' and
RA, RA', RB, S X x S RB = Rg' Then 0 S DNFEC( (RA' RB') = DNPEC ARA, RB) S 1.
Note that DNPEC may not be symmetric and so is not, in general, a pseudometric: see proposition A.3 The infimum in DKPEC can be computed exactly in tabular setting, but in general we must approximate it using gradient descent. This gives upper bound for DKpEc- but the quotient of upper bounds DNPEC may be too low or too high. See section A.1.2 for details of the approximation.
6 EXPERIMENTS
We evaluate EPIC and the baselines ERC and NPEC in a variety of continuous control tasks. In section 6.1 compute the distance between hand-designed reward functions, finding EPIC to be the most reliable. NPEC has substantial approximation error, and ERC sometimes erroneously assigns high distance equivalent rewards. Next, in section 6.2 we show EPIC is robust to the exact choice of coverage distribution D, whereas ERC and especially NPEC are highly sensitive to the choice of D. Finally, in section 6.3 we find that the distance of learned reward functions reward predicts the return obtained by policy training, even in an unseen test environment.
ground-trute
6.1 COMPARING HAND-DESIGNED REWARD FUNCTIONS
We compare procedurally specified reward functions in four tasks, finding that EPIC is more reliable than the baselines NPEC and ERC, and more computationally efficient than NPEC. [ results in the proof- of-oncet- PointMass task. The results for Gridworld. Ha HalfCheetahh and Hopper, in section A.2.4 are qualitatively similar.
7

---

Published as a conference paper at ICLR 2021
Table 2: Low reward distance from the ground-truth (GT) in SeiintMaze-Traae predicts high pol- icy return even in unseen task
EPIC distance is robust to the choice of coverage distribution D, with similar values across columns, while ERC and especially NPEC are sensitive to D. Center: approximate distances (1000x scale) of reward functions from GT. The coverage distribution ' is computed from rollouts PointMaze Maze-Tra in of: a uniform random policy Tuni, an expert π and a Mixture of these policies. Dg and D are computed by marginalizing D. Right: mean GT return over 9 seeds of RL training on the reward PointMaze- (Train, Test and returns for AIRL's generator policy. Confidence Intervals: see Table A.7
Reward Function
1000 X
DEPIC Mix
1000
DNPEC Mix
1000
DERC Mix
Episode Return
Tuni
π
Tuni
π
Tuni
π
Gen.
Train
Test
GT
0.06
0.05
0.04
0.04
3.17
0.01
0.00
0.00
0.00
-5.19
-6.59
Regress
35.8
33.7
26.1
1.42
38.9
0.35
9.99
90.7
2.43
-5.47
-6.30
Pref
68.7
100
56.8
8.51
1333
9.74
24.9
360
19.6
-5.57
-5.04
AIRL SO
572
520
404
817
2706
488
549
523
240
55.33
-27.3
-22.7
AIRL
SA
776
930
894
1067
2040
1039
803
722
964
-5.55
-30.7
- 29..0
Mirage
17.0
0.05
397
0.68
6.30
597
35.3
<0.01
166
-30.4
-99.1
In PointMass the agent can accelerate left or right on a line. The reward functions include or exclude (rt) quadratic penalty 3 The sparse reward (S) gives reward of 1 in the region 00.5 from the origin. The dense reward (D) is a shaped version of the sparse reward. The magnitude reward (M) is the negative distance of the agent from the origin.
We find that EPIC correctly identifies the equivalent reward pairs (S Se and -ettDDet) with estimated distance
x 10-3 By contrast, NPEC has substantial approximation error: D (N S.t) = 0.58. Similarly, DEaC (D, st) = 0.56 due to ERC's erroneous handling of stochastic initial states. Moreover, NPEC computationally inefficient: Figure took 31 hours to compute. By contrast, the figures for EPIC and ERC were generated in less than two hours, and lower precision approximation of EPIC finishes in just 17 seconds (see section A.2.6).
6.2 SENSITIVITY OF REWARD DISTANCE TO COVERAGE DISTRIBUTION
Reward distances should be robust to the choice of coverage distribution D. In Table 2 (center), report distances from the ground-truth reward (GT) reward functions (rows) across coverage distributions D E [Tuii, n², Mi,Mii
MMix } (columns). We find EPIC is fairly robust to the choice of 'D in each column D. By contrast, ERC and especially NPEC
with similar ratio between substantially more sensitive to the choice of DD
We evaluate in the PointMaze MuJoCo task from Fu al. navigate around a wall to reach a goal. The coverage distributions 'D are induced by rollouts from three different policies: Tuni takes actions uniformly at random, producing broad support over transitions; π is an expert policy, yielding distribution concentrated around the goal; and Mix is mixture of the two. In EPIC, Ds and D are marginalized from D and so also vary with D.
g where a point mass agent must
We evaluate four reward learning algorithms: Regression onto reward labels [target method from 6 section 3.3], re Pre ference comparisons on trajectories (6, and adversarial IRL with state-only (A IRL SO) and state-action (AIRL SA) reward model [8. All models are trained using synthetic data from an oracle with access to the ground-truth; see section A.2.2 for details.
We find EPIC is robust varying D when comparing the learned reward models: the distance varies by less than 2x, and the ranking between the reward models is the same across coverage distributions. By contrast, NPEC is highly sensitive to D; the ratio of AIRL SO (817) to Pref (8.51) is 96 under ग uni but only 2 : (2706 1333) under π². ERC lies somewhere in the middle: the ratio is 22: 1 (549: 24.9) under uuii and (523 360) under n²
We evaluate the effect of pathological choices of coverage distribution D in Table A.8 For example, Ind independently samples states and next states, giving physically impossible transitions, while Jail constrains rollouts to a tiny region excluding the goal. We find that the ranking of EPIC changes in only one distribution, whilst the ranking of NPEC changes in cases and ERC changes in all cases.
8

---

Published as a conference paper at ICLR 2021
However, we do find that EPIC is sensitive to D on Mi Mirage, reward function we explicitly designed to break these methods. Mi Mirage assigns a larger reward when close to a "mirage" state than when at the true goal, but is identical to GT at all other points. The "mirage" state is rarely visited by random exploration Tuni as it is far away and on the opposite side of the wall from the agent. The expert policy n² is even less likely to visit it, it is not on close to the optimal path to the goal. As result, the EPIC distance from Mirage to GT (Table 2 bottom row) is small under Tuni and x².
In general, any black-box method for assessing reward models including the rollout method only has predictive power on transitions visited during testing. Fortunately, we can achieve a broad support over states with Mix: it often navigates around the wall due to x but strays from the goal thanks to Tuni- As a result, EPIC under Mix correctly infers that Mirage aage is far from the ground-truth truth GT.
These empirical results support our theoretically inspired recommendation from section "in general, it is best to choose D to have broad coverage over plausible transitions." Distributions such as x' are too narrow, assigning coverage only on a direct path from the initial state to the goal. Very broad distributions such Ind waste probability mass impossible transitions like teleporting. Distributions like Mi x strike the right balance between these extremes.
6.3 PREDICTING POLICY PERFORMANCE FROM REWARD DISTANCE
We find that low distance from the ground-trun truth reward GT (Table 2 center) predicts high GT return (Table 2 right) of policies optimized for that reward. Moreover, the distance is predictive of return just in Poi ze- Train where the reward functions were trained and evaluated in, but also in the unseen variant PointMaze- Test. This is despite the two variants differing in the position of the wall, such that policies for PointMaze MeeeeMaaee--iaee Teriiaazze-rriinnnn run directly into the wall in PointMaze PointMaze-Test. Test.
Both Regress and Pref achieve very low distances at convergence, producing near-expert policy performance. The AIRL SO and AIRL SA models have reward distances an order of magnitude higher and poor policy performance. Yet intriguingly. the generator policies for AIRL SC and A AIRL SA trained simultaneously with the reward perform reasonably in suggests the learned rewards are reasonable on the subset of transitions taken by the generator policy, yet fail to transfer to the different transitions taken by policy being trained from scratch.
This
Figure A.6 shows reward distance and policy regret during reward model training. The lines all closely track each other, showing that the distance to GT is highly correlated with policy regret for intermediate reward checkpoints as well as at convergence. Regress and Pref converge quickly to low distance and low regret, while AIRL So and AIRL SA are slower and more unstable.
CONCLUSION
Our novel EPIC distance compares reward functions directly, without training a policy. We have proved it is pseudometric, is bounded and invariant to equivalent rewards, and bounds the regret of optimal policies (Theorems 4.7 4.8 and 4.9). Empirically, we find EPIC correctly infers zero distance between equivalent reward functions that the NPEC and ERC baselines wrongly consider dissimilar. Furthermore, we find the distance of learned reward functions to the ground-truth reward predicts the return of policies optimized for the learned reward, even in unseen environments.
Standardized metrics are an important driver of progress in machine learning. Unfortunately. tradi- tional policy-based metrics do not provide any guarantees as to the fidelity of the learned reward function. We believe the EPIC distance will be highly informative addition to the evaluation toolbox, and would encourage researchers to report EPIC distance in addition policy-based metries. Our implementation of EPIC and our baselines, including a tutorial and documentation, are available at con/ htt.:///www......oooooooooaaaaaa
ACKNOWLEDGEMENTS
Thanks to Sam Toyer, Rohin Shah, Eric Langlois, Siddharth Reddy and Stuart Armstrong for helpful discussions: to Miljan Martic for code-review; and to David Krueger, Matthew Rahtz, Rachel Freedman, Cody Wild, Alyssa Dayan, Adria Garriga, Jon Uesato, Zac Kenton and Alden Hung for feedback drafts. This work supported by Open Philanthropy and the Leverhulme Trust.

---

Published as a conference paper at ICLR 2021
REFERENCES
[1] Riad Akrour, Mare Schoenauer, and Michele Sebag. Preference-based policy learning. In Machine Learning and Knowledge Discovery in Databases, 2011.
[2] Dario Amodei, Paul Christiano, and Alex URL
Learning from hu- wwt.pp/enn.....ooooo/ooeeeee blog/ deep-reinforcemeee -earnnig from caaam-human..... wttatt--eeeeeeeeeeeeeeee
Ray.
man preferences, June 2017.
[3] Dzmitry Bahdanau, Felix Hill, Jan Leike, Edward Hughes, Arian Hosseini, Pushmeet Kohli, and Edward Grefenstette. Learning to understand goal specifications by modelling reward. In ICLR, 2019.
[4] Daniel S. Brown, Wonjoon Goo, Prabhat Nagarajan, and Scott Niekum. Extrapolating beyond suboptimal demonstrations via inverse reinforcement learning from observations. In JCML, 2019.
[5] Serkan Cabi, Sergio Gómez Colmenarejo, Alexander Novikov, Ksenia Konyushkova, Scott Reed, Rae Jeong, Konrad Zoina, Yusuf Aytar, David Budden, Mel Vecerik, Oleg Sushkov, David Barker, Jonathan Scholz, Misha Denil, Nando de Freitas, and Ziyu Wang. Scaling data-driven robotics with reward sketching and batch reinforcement learning. arXiv: 1909.12200v2 [cs.RO], 2019.
[6] Paul F Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep reinforcement learning from human preferences. In NIPS, pp. 4299-4307, 2017.
[7] Chelsea Finn, Sergey Levine, and Pieter Abbeel. Guided cost learning: Deep inverse optimal control via policy optimization. In ICML, 2016.
[8] Justin Fu, Katie Luo, and Sergey Levine. Learning robust rewards with adverserial inverse reinforcement learning. In ICLR, 2018
[9] Ashley Hill, Antonin Raffin, Maximilian Ernestus, Adam Gleave, Anssi Kanervisto, Rene Traore, Prafulla Dhariwal, Christopher Hesse, Oleg Klimov, Alex Nichol, Matthias Plappert, Alec Radford, John Schulman, Szymon Sidor, and Yuhuai Wu. Stable Baselines. https
7/github. www.cooccc...... hill- wwwplllllssaaeaaeeee w/stableebasellreeeeeeeeeeeeeeee 2018.
[10] Borja Ibarz, Jan Leike, Tobias Pohlen, Geoffrey Irving, Shane Legg, and Dario Amodei. Reward learning from human preferences and demonstrations in Atari. In NeurlPS, pp. 8011-8023, 2018.
[11] Charles L.. Lawson and Richard J. Hanson. Solving Least Squares Problems. SIAM, 1995.
[12] Eric J. Michaud, Adam Gleave, and Stuart Russell. Understanding learned reward functions. In Proceedings of the Workshop on Deep Reinforcement Learning NeurlPS, 2020.
[13] Andrew Y. Ng and Stuart Russell. Algorithms for inverse reinforcement learning. In ICML, 2000.
[14] Andrew Y. Ng, Daishi Harada, and Stuart Russell. Policy invariance under reward transforma- tions: theory and application to reward shaping. In NIPS, 1999.
[15] OpenAl. OpenAl Five. https://blog.openne wttp:/awi..co/ppppaaaaeee http://pnniiiiiiee///e.eee 2018.
[16] OpenAI, 1lge Akkaya, Marein Andrychowicz, Maciek Chociej. Mateusz Litwin, Bob McGrew, Arthur Petron, Alex Paino, Matthias Plappert, Glenn Powell, Raphael Ribas, Jonas Schneider, Nikolas Tezak, Jerry Tworek, Peter Welinder, Lilian Weng, Qiming Yuan, Wojeiech Zaremba, and Lei Zhang. Solving Rubik's Cube with robot hand. arXiv: 1910.071134 [cs.LG], 2019,
[17] Deepak Ramachandran and Eyal Amir. Bayesian inverse reinforcement learning. In IJCAI, 2007.
[18] Dorsa Sadigh, Anca D. Dragan, S. Shankar Sastry, and Sanjit A. Seshia. Active preference-basee learning of reward functions. In RSS, July 2017.
10

---

Published as a conference paper at ICLR 2021
[19] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. SEl.:1777.0634770 [cs.LG], 2017.
[20] David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George van den Driess- che, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, llya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis. Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587):4444889 2016.
[21] Satinder P. Singh and Richard C. Yee. An upper bound on the loss from approximate optimal- value functions. Machine Learning, 16(3):227-333, September 1994.
[22] Mel Vecerik, Oleg Sushkov, David Barker, Thomas Rothörl, Todd Hester, and Jon Scholz. A practical approach to insertion with variable socket position using deep reinforcement learning. In ICRA, 2019.
[23] Oriol Vinyals, Igor Babuschkin, Wojeiech M. Czarnecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung, David H. Choi, Richard Powell, Timo Ewalds, Petko Georgiev, Junhyuk Oh, Dan Horgan, Manuel Kroiss, Ivo Danihelka, Aja Huang, Laurent Sifre, Trevor Cai, John P. Agapiou, Max Jaderberg, Alexander Vezhnevets, Rémi Leblond, Tobias Pohlen, Valentin Dalibard, David Budden, Yury Sulsky, James Molloy, Tom L. Paine, Caglar Gulcehre, Ziyu Wang. Tobias Pfaff, Yuhuai Wu, Roman Ring, Dani Yogatama, Dario Wünsch, Katrina McKin- ney. Oliver Smith, Tom Schaul, Timothy Lillicrap. Koray Kavukcuoglu, Demis Hassabis, Chris Apps, and David Silver. Grandmaster level in StarCraft II using multi-agent reinforcement learning. Nature, 575(7782)3300-352 2019.
[24] Steven Wang. Adam Gleave, and Sam Toyer. imitation: implementations of inverse reinforcement learning and imitation learning algorithms. https://github com/ 2020.
[25] Aaron Wilson, Alan Fern, and Prasad Tadepalli. A Bayesian approach for policy learning from trajectory preference queries. In NIPS, 2012.
[26] Brian D. Ziebart, Andrew Maas, J. Andrew Bagnell, and Anind K. Dey. Maximum entropy inverse reinforcement learning. In AAAI, 2008
[27] Daniel M. Ziegler, Nisan Stiennon, Jeffrey Wu, Tom B. Brown, Alec Radford, Dario Amodei, Paul Christiano, and Geoffrey Irving. Fine-tuning language models from human preferences. arXiv: 1909.08593v2 [cs. [cs.CL), 2019.

---

Published as a conference paper at ICLR 2021
A SUPPLEMENTARY MATERIAL
A.1 APPROXIMATION PROCEDURES
A.1.1 SAMPLE- SAMPLE-BASED BASED APPROXIMATION FOR EPIC DISTANCE
We approximate EPIC distance (definition 4.6) by estimating Pearson distance on a set samples, canonicalizing the reward on-demand. Specifically, sample batch By of Ny samples from the coverage distribution D, and a batch Ви of NM samples from the joint state and action distributions Ds DA. For each (s, s') E Bv, we approximate the canonically shaped rewards (definition 4.1 by taking the mean over BM:
CDS.DA (R) as), R(s, a,. B A.
A, A,
(5)
~ aRss,a,5
Σ
R(s', u,
(6)
NM (g,
Σ
R(s, u,)
NM
We drop the constant e from the approximation since it does not affect the Pearson distance; can also be estimated in O(N)) M) time by N Ee Eas,,a) R(x, 2'). Finally, compute the Pearson distance between the approximate canonically shaped rewards on the batch of samples By, yielding MN) time algorithm.
A.1.2 OFTIMIZATION- BASED APPROXIMATION FOR NPEC DISTANCE
DNPRO RA, RB) (section 5.2 is defined as the infimum of IP distance over infinite set of equivalent reward functions RA- We approximate this using gradient descent on the reward model
Ry,e,w(s, a, = exp(v) a, s') + c 2 (s') (s).
(8)
where V, are scalar weights and vector of weights parameterizing a deep neural network &... The constant E IR is unnecessary if t has bias term, but its inclusion simplifies the optimization problem.
We optimize to minimize the mean of the cost
JV, c, (s a, s') = Ru,,,u a, s'), a
(9)
on samples (s, a, s') from coverage distribution D. Note
((,,,,)')> [ (), 1/ DIP D. (Bv RB)
AS, (
(10)
upper bounds the true NPEC distance since R = RA
We found empirically that and need to be initialized close to their optimal values for gradient descent to reliably converge. To resolve this problem, we initialize the affine parameters to v < log and found by:
arg min X20,cE a' (ARa(s, + - Rn(s,,,5'))
(11)
We use the active set method of Lawson & Hanson 11 to solve this constrained least-squares problem. These initial affine parameters minimize the I. distance Dir ( a, s'), R a, when 2 with the potential fixed at 2o(s) 0.
A.1.3 CONFIDENCE INTERVALS
We report confidence intervals to help measure the degree of error introduced by the approximations. Since approximate distances may not be normally distributed, we use bootstrapping to produce distribution free confidence interval. For EPIC, NPEC and Episode Return (sometimes reported as regret rather than return), compute independent approximate distances returns different
12

---

Published as a conference paper at ICLR 2021
Table A.I: Summary of hyperparameters and distributions used in experiments. The uniform random coverage distribution Duuit samples states and actions uniformly at random, and samples the next state from the transition dynamics. Random policy Tuni takes uniform random actions. The synthetic expert policy rt" was trained with PPO the ground-truth reward. Mixture samples actions from either Tuni or n², switching between them at each time step with probability 0.05. Warmstart Size the size of the dataset used to compute initialization parameters described in section A.1.2
Parameter
Value
In experiment
Random transitions Dunif
GricWorld
Coverage Distribution
Rollouts from Tuni
PointMass, HalfCheetah, Hopper PointMaze
Tuni, ' and Mixture 10000 0.99
Bootstrap Samples
All
Discount 7
All
EPIC
State Distribution Ds
Marginalized from D Marginalized from D
All
Action Distribution D
All
Seeds
30
All
Samples Ny
32 768
All
Mean Samples NM
32 768
All
NPEC
Seeds
All
Total Time Steps
x 106 Adam
All
Optimizer
All
Learning Rate
10-2 4096
All
Batch Size
All
Warmstart Size
16 386
All
Loss
f(r, y) = (xc - y)²
All
ERC
Episodes
131 072
All
Episode Return
Seeds
All
See Table A.2 for the policy training hyperparameters
seeds, and then compute a bootstrapped confidence interval for each seed. We use 30 seeds for EPIC, but only 9 seeds for computing Episode Return and 3 seeds for NPEC due to their greater computational requirements. bootstrapping to the collected episodes, computing the ERC distance for each bootstrapped episode sample.
ERC, computing the distance is very fast, so we instead apply
A.2 EXPERIMENTS
A.2.1 HYPERPARAMETERS FOR APPROXIMATE DISTANCES
Table A. summmarizes the hyperparameters and distributions used to compute the distances between reward functions. Most parameters are the same across all environments. We use coverage distribution of uniform random transitions Dunit in the simple Gr CridWordd environment with known determinstic dynamics. In other environments, the coverage distribution is sampled from rollouts of policy. We use random policy Tuni for PointMass, Hal fCheet ah and Hopper in the hand- designed reward experiments (section 6.1). In PointMaze, we compare three coverage distributions (section 6.2) induced by rollouts of Tuni- expert policy x² and Mixture of the two policies, sampling actions from either π Tuni or म and switching between them with probability 0.05 per time step.
13

---

Published as a conference paper at ICLR 2021
Table A.2: Hyperparameters for proximal policy optimisation (PPO) [9]] We used the implemen- tation and default hyperparameters from Hill et al. [9. PPO was used to train expert policies on ground-truth reward and to optimize learned reward functions for evaluation.
Parameter
Value
In environment
Total Time Steps
10
All
Seeds
9
All
Batch Size
4096
All
Discount y
0.99
All
Entropy Coefficient
0.01
All
Learning Rate
10
All
Value Function Coefficient
0.5
All
Gradient Clipping Threshold
0.5
All
Ratio Clipping Thrsehold
0.2
All
Lambda (GAE)
0.95
All
Minibatches
4
All
Optimization Epochs
4
All
Parallel Environments
8
All
Table A.3: Hyperparameters for adversarial inverse reinforcement learning (AIRL) used in Wang
al. 24
Parameter
Value
RL Algorithm
PPO 19
Total Time Steps
10000 000
Discount y
0.99
Demonstration Time Steps
100 000
Generator Batch Size
2048
Diseriminator Batch Size
50
Entropy Weight
1.0
Reward Function Architecture
MIP, two 32-unit hidden layers
Potential Function Architecture
MLP, two 32-unit hidden layers
Table A.4: Hyperparameters for preference comparison used in our implementation of Christiano et al. [6]
Parameter
Value
Range Tested
Total Time Steps
5 106 10000
[1, 10 108)
Batch Size
500, 250 000] [1, 100]
Trajectory Length
5
Learning Rate
1 x 10-2
[ 10 x 10-1]
Discount y
0.99
Reward Function Architecture
MLP, two 32-unit hidden layers
Output L2 Regularization Weight
1 x 10-4
Table A.5: Hyperparameters for regression used in our implementation of Christiano al. 6 targer method from section 3.3].
Parameter
Value
Range Tested
Total Time Steps
10 106 4096
[1, 20 10 256,, 16384]
Batch Size
Learning Rate
2 x 10-2
[1 10-3 10 10-1]
Discount
0.99
Reward Function Architecture
MLP, two 32-unit hidden layers
14

---

Published as a conference paper at ICLR 2021
A.2.2 TRAINING LEARNED REWARD MODELS
For the experiments on learned reward functions (sections 6.3 and 6.2), we trained reward mod- els using adversarial inverse reinforcement learning (AIRL; 8), preference comparison [6] and by regression onto the ground-truth reward [targel method from 6 section 3.3]. For AIRL, we existing open-source implementation 24 We developed new implementations for prefer- ence comparison and regression, available at btttps://iite
com/ HumanCompat ibltAII evaaluaiin rewards, We also use the RL algorithm proximal policy optimization (PPO; (9) on the ground-truth reward to train expert policies to provide demonstrations for AIRL. We use seeds, taking rollouts from the seed with the highest ground-trumt -ruth return.
Our hyperparameters for PPO in Table A.2 were based on the defaults in Stable Baselines 19. We only modified the batch size and learning rate, and disabled value function clipping to match the original PPO implementation.
Our AIRL hyperparameters in Table A.3 likewise match the defaults, except for increasing the total number of timesteps to 10". Due the high variance of AIRL, we trained 5 seeds, selecting the one with the highest ground-truth return. While this does introduce a positive bias for our AIRL results, in spite of this AIRL performed worse in our tests than other algorithms. Moreover, the goal in this paper is to evaluate distance metrics, not reward learning algorithms.
For preference comparison performed a sweep over batch size, trajectory length and learning rate to decide on the hyperparameters in Table A.4 Total time steps was selected once diminishing returns were observed in loss curves. The exact value of the regularization weight was found to be unimportant, largely controlling the scale of the output at convergence.
Finally, for regression we performed sweep decide on the hyperparameters in Table A.5 We found batch size and learning rate to be relatively unimportant with many combinations performing well, but regression was found to converge slowly but steadily requiring relatively large 10 x 10 time steps for good performance in our environments.
batch size, learning rate and total time steps to
All algorithms are trained on synthetic data generated from the ground-truth reward function. AIRL is provided with a large demonstration dataset of 100 000 time steps from an expert policy trained on the ground- truth reward (see Table A.3) In preference comparison and regression, each batch is sampled afresh from the coverage distribution specified in Table A.1 and labeled according to the ground-trun trrtt reward.
A.2.3 COMPUTING INFRASTRUCTURE
Experiments were conducted on a workstation (Intel 79-7920X CPU with 64 GB of RAM), and small number of r5. 24x1arge AWS VM instances, with 48 CPU cores Intel Skylake processor and 768 GB of RAM. It takes less than three weeks of compute on a single r5. 24xlarge instance to run all the experiments described in this paper.
A.2.4 COMPARING HAND-DESIGNEL REWARD FUNCTIONS
We compute distances between hand-designed reward functions four environments: GridWorld l.. PointMass, s, HalfCheetah and Hopper. The reward functions for GridWorld are described in Figure A.1 and the distances are reported in Figure A.2 We report the approximate distances and confidence intervals between reward functions in the other environments in Figures A.3
A.4 and A.5
We find the (approximate) EPIC distance closely matches our intuitions for similarity between the reward functions. NPEC often produces similar results to EPIC, but unfortunately is dogged by opti- mization error. This particularly notable in higher-dimensional environments like Ha @Cheetal and Hopper, where the NPEC distance often exceeds the theoretical upper bound of 1.0 and the confidence interval width is frequently larger than 0.2.
By contrast, ERC distance generally has tight confidence interval, but systematically fails in the presence of shaping. For example, it confidently assigns large distances between equivalent reward pairs in PointMass such as S.mt-Drft. However, ERC produces reasonable results in Hal fCheethh and Hopper where rewards are all similarly shaped. In fact, ERC picks up on detail in Hopper that EPIC misses: whereas EPIC assigns distance of around 0.71 between
15

---

Published as a conference paper at ICLR 2021
Distance Metric
Wall-Clock Time
Environment Time Steps
Reward Queries
# of Seeds
95% CI Width
Max
Mean
EPIC Quick
17s
8192
1.67 107
3
0.023 04
0.008 60
EPIC
6738
65 536
1.07 109
30
0.005 58
0.002 34
NPEC
29 769s
7.50 x 107
7.50 x 107
3
0.315 91
0.066 20
ERC
1376
6.55 x 106
6.55
106
0.015
0.005
RL (PPO) i
7.50 107
7.50
107
3
Table A.6: Time and resources taken by different metrics to perform 25 distance comparisons on PointMass. and the confidence interval widths obtained (smaller is better). Methods EPIC, NPEC and ERC correspond to Figures 2 2)) (b) and (c) respectively. EPIC Quick is an abbreviated version with fewer samples. RL (PPO) estimated from the time taken using PPO train a single policy (16m:23s) until convergence (10" time steps). EPIC samples NM + Ny time steps from the environment and performs Ny reward queries. In EPIC Quick, NM Ny = 4096; EPIC, NM = Nv 302768. Other methods query the reward once per environment time step.
all rewards of different types (running vs backflipping), ERC assigns lower distances when the rewards are in the same direction (forward backward). Given this, ERC may be attractive in some circumstances, especially given the ease of implementation. However, we would caution against using it in isolation due the likelihood of mislcading results in the presence of shaping.
A.2.5 COMPARING LEARNED REWARD FUNCTIONS
Previously, reported the mean approximate distance from ground-truth reward of four learned reward models in PointMaze (Table 2). Since these distances are approximate, we report 95% lower and upper bounds computed via bootstrapping in Table A.7 We also include the relative difference of the upper and lower bounds from the mean, finding the relative difference to be fairly consistent across reward models for a given algorithm and coverage distribution pair. The relative difference is less than 1% for all EPIC and ERC distances. However, NPEC confidence intervals can be wide as 50%: this is due to the method's high variance, and the small number of seeds we were able to run because of the method's computational expense.
A.2.6 RUNTIME OF DISTANCE METRICS
We report the empirical runtime for EPIC and baselines in Table A.6 performing 25 pairwise com- parisons across 5 reward functions in PointMass. These comparisons were run on an unloaded machine running Ubuntu 20.04 (kernel 5.4.0-52) with an Intel 79-7920X CPU and 64 GB of RAM. report sequential runtimes: runtimes for all methods could be decreased further by parallelizing across seeds. The algorithms were configured to use 8 parallel environments for sampling. Inference and training took place on CPU. All methods used the same TensorFlow configuration, parallelizing operations across threads both within and between operations. We found GPUs offered perfor- mance benefit in this setting, and in some cases even increased runtime. This is due to the fixed cost of CPU-GPU communication, and the relatively small size of the observations.
We find that in just 17 seconds EPIC can provide results with a 95% confidence interval < 0.023, an order of magnitude tighter than NPEC running for over 8 hours. Training policies for all learned rewards in this environment using PPO is comparatively slow, taking over hours even with only 3 seeds. While ERC is relatively fast, it takes large number of samples achieve tight confidence intervals. Moreover, since P MintMass has stochastic initial states, ERC can take on arbitrary values under shaping, discussed in sections 5. and 6.3
16

---

Published as a conference paper at ICLR 2021
Sparse Reward
Dense Reward
3
2
0
0
0
0
2
-4
1
2
-4
2
2
-4
0
0
2
-4
2
-4
0
0
0
2
2
2
-1
-4
-4
0
2
0
1
2
-4
1
2
0
3
3
4
Penalty Reward
Center Reward
2
0
0
0
0
0
0
0
0
0
0
0
0
-1
0
0
-
0
0
0
-1
-1
0
O
0
0
0
3
4
Path Reward
Cliff Reward
4
3
2
0
0
1
1
-1
-1
1
0
1
1
11
-1
1
0
-1
-1
-1
-1
2
0
0
0
0
0
0
0
0
0
-1
-1
-4
-4
4
-2
0
1
-1
-1
1
-1
4
4
4
-4
-
4
-4
4
4
-3
4
Figure A.1: Hcatmaps of reward functions R(s, a, for a 3 deterministic gridworld. R(s, stay, s) given by the central circle in cell R(s, a, s') is given by the triangular wedge in cell adjacent to cell direction a. Optimal action(s) (for infinite horizon, discount = 0.99) have bold labels against hatched background. See Figure A.2 for the distance between all reward pairs.
17

---

Published as a conference paper at ICLR 2021
1.0
Sparse
0.0000
0.0000
0.7500
1.0000
0.1602
0.3676
0.8
Dense
0.0000
0.0000
0.7500
1.0000
0.1602
0.3676
Center
0.7500
0.7500
0.0000
0.6614 4
0.7071
0.6692
0.6
D(RA, Ra)
RA
Penalty
1.0000
1.0000
0.6614
0.0000
0.9871
0.9300
0.4
Path
0.1602
0.1602
0.7071
0.9871
0.0000
0.2672
0.2
Clift
0.3676
0.3676
0.6692
0.9300
0.2672
0.0000
0.0
Sparse
Dense
Center
Penalty
Path
cliff
RB
(a) EPIC
1.0
Sparse
0.0000
0.0000
1.0016
1.0009
0.3068
0.7038
0.8
Dense
0.0000
0.0000
1.0016
1.0000
0.3068
0.7038
Center
1.0011 1
1.0133
0,0000
0.9853
1,0016
1.0004
0.6
D(RA. Ra)
RA
Penalty
1.0009
1.0213
0.9824
0.0000
1,0010
1.0010
0.4
Path
0.3069
0.3069
1.0023
1.0000
0.0000
0.5476
0.2
Cliff
0.7031
0.7031
1.0025
1.0000
0.5468
0.0000
0.0
Sparse
Dense
Center
Penalty
Path
Cliff
Rg
(b) NPEC
Figure A.2: Distances (EPIC, top; NPEC, bottom) between hand-designed reward functions for the 3 x deterministic Gr frridwoll environment, EPIC and NPEC produce similar results, but EPIC more clearly discriminates between rewards whereas NPEC distance tends to saturate. For example, the NPEC distance from Penalts to other rewards lies in the very narrow [0.98, 1.0] range, whereas EPIC uses the wider [0.66, 1.0) range. See Figure A.1 for definitions of each reward. Distances are computed using tabular algorithms. We do not report confidence intervals since these algorithms are deterministic and exact up floating point error.
18

---

Published as a conference paper at ICLR 2021
1.0
S.r
-0.00
0
0.00
0.51
0.63
0.00
0.88
0.22
0.86
0.96
0.00
0.41
0.56
0.56
0.57
D(RA. RB)
S
0.51
0.00
0.51
0.00
0.55
0.92
0.00
0.94
0.04
0.74
0.41
0.00
0.61
0.55
0.62
Det
-0.00
0.51
0.00
0.51
0.63
0.58
0.95
0.00
0.81
0.97
0.56
0.61
0.00
0.11
0.64
0.5
0.51
0.00
0.51
0.00
0.55
0.88
0.04
0.84
0.00
0.58
0.56
0.55
0.11
0.00
0.64
M
0.63
0.55
0.63 0.55
0.00
0.93
0.79
0.80
0.62
0.00
0.57
0.62
0.64
0.64
0.00
0.0
5 Ser
Dunt
D
M
Set
s
Durt
D
S.rt S
Dart
D
M
RB
RB
Rn
(a) EPIC Median
(b) NPEC Median
(c) ERC Median
1.0
S. 6 2e-3 9c-5 2e-3 9e-4
2e-5 9e-3 3e-2 2c-2 2e-1
7c-9 le-2 4e-3 4c-3 3e-3
Dw (RA.RR RB)
2e-3 6e-5 2e-3 5e-5 2e-3
9e-2 9e-7 2e- 1 4e-3 le-1
le-2 7e-9 6e-3 5e-3 4e-3
RA
Det -9-55 2e-3 7e-5 2e-3
9e-4
le-1 le-2 le-5 6e-3
le-1
4e-3 6e-3 1e-8 1e-3 4e-3
0.5
2e-3 5e-5 2e-3 5e-5 2
6e-2 2e-3 9e-2
2e-6
6e-2
4e-3 5e-3 1e-3 1e-8 4e-3
M
-9e-4 2e-3 9e-4 2e-3 5e-5
le-1 le-1
3e-1
le-2 4e-7
3e-3
4e-3 4e-3 4e-3 7e-9
0.0
Set
Dut
D
M
Set
s
Dar
D
Set s
Dart
Ra
R
RB
(d) EPIC CI Width
(c) NPEC CI Width
(f) ERC CI Width
Figure A.3: Approximate distances between mend-desigeed reward functions in PointMass. The
coverage distribution D is sampled from rollouts of a policy Tuni taking actions uniformly random. Key: The agent has position x E R. velocity 1 E TR. and can accelerate # E R. producing future position x' R. quadratic penalty on control _²2 et control penalty.
is Sparse(x) 0.05]. D is shaped Dense(æ, x²) Sparse (x) + |x' - |z]. while M is Magnitude(z) = | |||=| <
Confidence Interval (CI): 95% CI computed by bootstraping over 10 000 samples.
1.00
A
0.00
0.17
1.00
0.98
0.01
0.03
1.17
1.11
0.00
0.02
1.00
1.00
0.75
D(RA, RB)
0.17
0.00
0.98
0.94
0.03
0.01
1.13
1.19
0.02
0.00
1.00
1.00
RA
0.50
1.00
0.98
0.00
0.17
1.15
1.09
0.01
0.03
1.00
1.00
0.00
0.02
0.25
0.98
0.94
0.17
0.00
1.08
1.08
0.03
0.01
1.00
1.00
0.02
0.00
0.00
at
1 3
1
RB
RB
RB
(a) EPIC Median
(b) NPEC Median
(c) ERC Median
1.00
$ at
5c-5
6c-4
1e-8
le-4
le-2
le-2
le-1
3e-1
1e-8
2e-4
lc-16
3e-6
(R RB)
0.75
6c-4
5e-5
le-4
4c-4
2e-2
le-2
le-2
le-1
2c-4
1e-8
3e-6
le-5
0.50
le-8
le-4
5e-5
7e-4
2e-1
2e-1
le-2
le-2
le-16
3e-6
le-8
2c-4
0.25
le-4
4e-4
7e-4
6e-5
3e-1
8e-2
9e-3
le-2
3e-6
le-5
2e-4 1e-8
0.00
&
f
3.
1
st
RB
Rg
RB
(d) EPIC CI Width
(e) NPEC CI Width
(f) ERC CI Width
Figure A.4: Approximate distances between hand-designed reward functions in HalfCheet ah. The coverage distribution D is sampled from rollouts of policy Funi taking actions uniformly at random. Key: & is a reward proportional to the change in center of mass and moving forward is rewarded when to the right, and moving backward is rewarded when å to the left. quadratic control penalty, et no control penalty. Confidence Interval (CI): 95% CI computed by bootstraping over 10 000 samples.
19

---

Published as a conference paper at ICLR 2021
1.0
4
0.00 0.00
0.99
0.99
0.71
0.71
0.00
0:00
0:92
1.40
1.24
0.97
0.00
0.97 0.97
0.37 0.37
0.93 0.93
DRAA Re
0.99 0.99
0.00
0.00
0.71
0.71
0.71
0.71
1.25
1:46
0.00
0.00
1,02
0.99
0.95
1.08
0.97
0.97
0.00 0.00
0.88 0.8
0.47 0:47
R
0.99 0.99
0.00
0.00
0.71
0:71
0.71 0.71
0.94 1.13
0.00 0.00
1,03
1.00
0.55
0.99
0.92 0.97
0.00 0.00
0.88
0.57 0.47
0.6
0.71
0.4
0.71 0:71
0.71
0.71
1.29
2.
1:12
1:17
0:00
0.00
0.00
0.00
1.00
0.71
0.71
0.71
0.71
100
100
0.00
0.00
1.41
14
56
1.07
03
0.00 0.00
0.93 9:
0:47 0.47
1.00 1:00
0.00 0.00
0.2
0.71
0.7
0.71
0.71
1.00
0.00 0.00
1.18
6.65
16
1.09
1.01
0.00 0.00
0.93
1,00 1:00
0.00 0.00
0.0
Aet
RB
R
R
(a) EPIC Median
(b) NPEC Median
(c) ERC Median
1.0
-6e Se:5 2e 3e-d 1e:3 1e:3
Ie:3
3e 3e 3e:3.
1e-1
3e:
5e
Se
1e-1
7e Se-7 7e-4 Re-4 de 3 3e-3 3e
a -Be-S Se-5 20.4 20-4
1o:3
le-3
le-3
1e-3
3e-3 3e-3
9x-1
200
3e-1
Te-1
Se-2
2e-1
5e-7 7e-9 77-4 "eed 40-3 4o-3
2o-3 2e-3
0.8
Dw (R. R.)
i 1. -Be-4 2e-4 6e-5
8e-5
Le:3
1e:3
1e-3 Ie-3
le0
Ne:3
4e-3
2e-1
2e-1
le-1
3e-1
7e-4 7e-4 le 6e-7 2e-3 2e-3
4e-3 4e-3
3.
26:1
0.6
er -1e33 1e-3 1e-3 1e13 5e-5
26-5
le-8 4e-8
7e-1
1e-1
3e-1
3e-1
2o-4
Te-5
De-1
3e-1
Ae-3 4e-3 20.3 2e-3 1e-8 2e-lle-16le-10
0.4
aa -1e-3 1e:3 1e:3 1e le
6e-5
de-8 le:7
6e-
6e
7el
1e:
3e-4
2e-1
9e-2
2e-
4e:3 4e-3 2 2 2e-6 le 1e-8 102e-9
Ro-1
2o-1
164e-10
1e--3
1e-3
2x0
4e- 1022-- 20-6
0.0
ee A re ral
A
3 Ye
RB
R
R
(d) EPIC CI Width
(e) NPEC CI Width
(I) ERC CI Width
Figure A.5: Approximate distances between hand-designed reward functions Hopper. The coverage distribution D is sampled from rollouts of a policy Tuni taking actions uniformly random. Key: & is reward proportional to the change in center of mass and A is the backflip reward defined in Amodei et al. 2 footnote]. Moving forward is rewarded when & or y is the right, and moving backward rewarded when }. or Y is to the left. quadratic control penalty, की no control penalty. Confidence Interval (CI): 95% CI computed by bootstraping over 10 000 samples.
20

---

Published as a conference paper at ICLR 2021
Table A.7: Approximate distances of reward functions from the ground-truth (GT). We report the 95% bootstrapped lower and upper bounds, the mean, and a 95% bound on the relative enror from the mean. Distances (1000x scale) use coverage distribution D from rollouts in the PointMaze-Tae environment of: a uniform random policy π Tuii expert π and Mixture of these policies. Ds and A are computed by marginalizing D.
(a) 95% lower bound DLOW of approximate distance.
Reward
1000
DLOW
1000 X
DLOW NPEC
1000 X DLOW
Episode Return
ERC
Function
Tuni
π
Mix
Tuni
π
Mix
Tuni
π²
Mix
Train
Test
GT
0.03
0.02
<0.01
0.02
1.43
<0.01
0.00
0.00
0.00
-4.46
-5.82
Regress
35.5
33.6
26.0
1.22
38.8
0.33
9.94
90.2
2.42
-4.7
-5.63
Pref
68.3
100
56.6
7.02
1239
9.25
24.7
358
19.5
-5.26
-4.88
AIRL SO
570
519
402
734
1645
424
547
521
238
-27.3
-22.7
AIRL
SA
774
930
894
956
723
952
802
720
963
-29.9
-28
Mi Mirage
3.49
0.02 381
0.17
4.03
481
25.8
<0.01
162
-28.4
-26.2
(b) Mean approximate distance D. Results are same as Table
Reward
1000 x DEPIC
1000 x DNPEC
1000 X DERC
Episode Return
Function
Tani
π
Mix
Tuni
Mix
Tuni
Mix
Train
Test
GT
0.06
0.05
0.04
0.04
3.17
0.01
0.00
0.00
0.00
-5.19
-6.59
Regress
35.8
33.7
26.1
1.42
38.9
0.35
9.99
90.7
2.43
-5.47
-6.3
Pref
68.7
100
56.8
8.51
1333
9.74
24.9
360
19.6
-5.57
-5.04
AIRL So
572
520
404
817
2706
488
549
523
240
-27.3
-22.7
AIRL
SA
776
930
894
1067
2040
1039
803
722
964
-30.7
-29
Mirage
17.0
0.05
397
0.68
6.30
597
35.3
<0.01
166
33044
-29.1
(c) 95% upper bound D approximate distance.
Reward
1000 x
DUP EPIC
1000 x D
UP NPEC
1000 x DUP
Episode Return
ERC
Function
Tuni
Mix
Tuni
n²
Mix
Wuni
n²
Mix
Train
Test
GT
0.09
0.07
0.07
0.06
6.14
0.01
<0.01
<0.01
<0.01
-6.04
-7.14
Regress
36.1
33.7
26.2
1.53
39.1
0.37
10.0
91.2
2.44
-6.26
-6.83
Pref
69.1
101
57.1
10.0
1432
10.1
25.2
361
19.7
-5.9
-5.22
AIRL SC
574
520
407
982
3984
532
551
526
242
-27.3
-22.8
AIRL
779
930
895
1241
4378
1124
805
724
964
-31.7
-29.8
Mirage
35.2
0.09
414
1.66
10.8
821
45.4
<0.01
171
-32
-31.4
(d) Relative 95% confidence interval D REL
max
Upper
Lower Monn
percent. The population mean
Moan
contained within REL the sample mean
Table A.7b with probability.
Reward
REL % D
DREL % NPEC
DREL % ERC
Episode Return
EPIC
Function
Tuni
Mix
Tuni
n²
Mix
Tuni
n²
Mix
Train
Test
GT
50.0
62.5
80.0
61.8
94.0
29.7
inf
inf
inf
0.16
0.12
Regress
0.81
0.14
0.40
14.2
0.42
7.48
0.53
0.55
0.57
0.14
0.11
Pref
0.61
0.14
0.44
17.5
7.49
5.02
0.90
0.48
0.48
0.06
0.04
AIRL S0
0.38
0.08
0.67
20.2
47.2
13.2
0.34
0.40
0.69
<0.01
<0.01
AIRL SA
0.35
0.02
0.08
16.3
115
8.42
0.23
0.26
0.04
0.03
0.04
Mi rage
108
65.5
4.17
142
70.9
37.5
28.5
0.55
2.66
0.07
0.10
21

---

Published as a conference paper at ICLR 2021
Table A.8: Approximate distances of reward functions from the ground-truth (GT) under pathological coverage distributions. We report the 95% bootstrapped lower and upper bounds, the mean, and a 95% bound the relative error from the mean. Distances (1000 scale) use four different coverage distributions D. a independently samples states, actions and next states from the marginal distri- butions of rollouts from the uniform random policy uui in the Po i Mt.Ma ze-Tra in environment. Ind independently samples the components of states and next states from N (O, 1), and actions from UT-1, 1]. Jail consists of rollouts of Tuni restricted the goal state 0.5 distance away. Tbad are rollouts in PointMaze eeeeizeerrrie Train of a policy that goes to the corner opposite the goal state. o and Ind are not supported by ERC since they do not produce complete episodes.
small 0.09 x 0.09 "jail" square that excludes
(a) 95% lower bound DLOW of approximate distance.
Reward
1000 x DLOW
1000
DLOW
1000 X DLOW ERC
NPEC
Function
Ind
Jail
Tbad
Ind
Jail
badd
Jail
Tbad
Regress
127
398
705
205
87.6
590
2433
898
809
456
Pref
146
433
462
349
97.4
632
661
221
372
332
AIRL
So
570
541
712
710
697
821
957
621
751
543
AIRL
SA
768
628
558
669
720
960
940
2355
428
753
Mirage
9.22
0.03
<0.01
0.02
0.41
0.05
11.2
31.3
<0.01
0.02
(b) Mcan approximate distance D. Results are the same as Table
Reward
1000 x DEPIC
1000 X DNPEC
1000 x
DERC
Function
Ind
Jail
Tbad
Ind
Jail
Tbbad
Jail
Tbad
Regress
128
398
705
206
97.2
591
2549
921
810
458
Pref
147
433
463
349
117
633
683
237
374
333
AIRL So
573
541
713
710
826
823
988
852
753
545
AIRL
SA
771
628
558
669
859
962
964
2694
430
754
Mi Mirage
42.4
0.06
0.03
0.05
1.41
0.25 18.3 39
<0.01
0.02
(c) 95% upper bound D of approximate distance.
Reward
1000 x EPIC
1000 X
UP D
NPEC
1000 x UP
Function
Ind
Jail
Tbad
Ind
Jail
Tbad
Jail
Tbad
Regress
129
398
706
206
106
593
2654
948
812
460
Pref
148
433
464
349
132
635
705
265
376
335
AIRL 50
576
541
713
710
939
825
1047
1021
755
547
AIRL
SA
774
628
559
669
1015
963
981
3012
432
756
Mirage
85.9
0.09
0.05
0.09
3.25
0.46
28.6
45.3
<0.01
0.02
(d) Relative 95% confidence interval DRE = mmxx
Upper
1,
Lower Mewn
in percent. The population mean
Mean
is contained within REL% of the sample mean in Table A.8b with 95% probability.
Reward
D
DPPI %
D REL % NPEC
D
DREL% % ERC
Function
Ind
Jail
Tbad
Ind
Jail
Tbad
Jail
baa
Regress
0.79
0.01
0.08
0.06
9.81
0.24
4.54
2.89
0.18
0.42
Pref
0.76
<0.01
0.16
0.07
16.9
0.35
3.35
11.7
0.47
0.48
AIRL So
0.48
<0.01
0.07
0.02
15.6
0.28
6.01
27.1
0.23
0.38
AIRL SA
0.38
<0.01
0.13
0.03
18.2
0.22
2.47
12.6
0.45
0.23
Mi rage
103
50
80
83.3
131
85.4
56.4
19.7
0.54
0.55
22

---

Published as a conference paper at ICLR 2021
EPIC
NPEC
ERC
RL Train
RL Test
30
1.0
Distance
20
Regret
0.5
10
0.0
0
20
40
100
Regress Training Progress (%)
(a) Comparisons of Regress using all distance algorithms.
EPIC
NPEC
ERC
RL Train
RL Test
30
1.0
Distance
20
Regret
0.5
0.0
0
20
40
60
80
100
Pref Training Progress (%)
(b) Comparisons of Pref using all distance algorithms.
EPIC
NPEC
ERC
RL Train
RL Test
1.0
30
Distance
Regret
0.5
20
0.0
10
0
20
40
60
80
100
AIRL SO Training Progress (%)
(c) Comparisons of AIRL SO using all distance algorithms.
EPIC
NPEC
ERC
RL Train
RL Test
1.0
30
Distance
Regret
0.5
20
0.0
20
40
100
ATRL SA Training Progress (%)
(d) Comparisons of AIRL SA using all distance algorithms.
Figure A.6: Distance of reward checkpoints from the ground-truth in Poi ntizze and policy regret for reward checkpoints during reward model training. Each point evaluates reward function checkpoint from a single seed. EPIC, NPEC and ERC distance use the Mi xture distribution. Regret is computed by running RL the checkpoint. The shaded region represents the bootstrapped 95% confidence interval for the distance or regret at that checkpoint, calculated following Section A.1.3
23

---

Published as a conference paper at ICLR 2021
AIRL SA
AIRL SO
Pref
Regress
1.0
Distance
0.5
0.0
20
40
60
80
100
Reward Model Training Progress (%)
(a) Comparisons using EPIC on all reward models.
AIRL SA
AIRL SO
Pref
Regress
Distance
1.0
0.5
0.0
0
20
40
60
80
100
Reward Model Training Progress (%)
(b) Comparisons using NPEC on reward models.
AIRL
AIRL SO
Pref
Regress
1.0
Distance
0.5
0.0
0
20
40
60
80
100
Reward Model Training Progress (%)
(c) Comparisons using ERC on all reward models.
AIRL SA
AIRL SO
Pref
Regress
RL Train
RL Test
Regret
20
0
0
20
40
80
100
Reward Model Training Progress (%)
(d) Comparisons using Episode Return all reward models.
Figure A.7: Distance of reward checkpoints from the ground-trute trrnh in PointMaze and policy regret for reward checkpoints during reward model training. Each point evaluates reward function checkpoint from a single seed. EPIC, NPEC and ERC distance use the Mi xture distribution. Regret computed by running RL on the checkpoint. The shaded region represents the bootstrapped 95% confidence interval for the distance regret at that checkpoint, calculated following Section A.1.3
24

---

Published as a conference paper at ICLR 2021
A.3 PROOFS
A.3.1 BACKGROUND
Proposition 3.4. The binary relation = is an equivalence relation. Let RA, RB, Re SxAAx +R be bounded reward functions. Then = is reflexive, RA =\t RA; symmetric, RA = Rn implies Rn RA; and transifive, (Ra RB) A (Rn Rc) implies RA Re.
Proof. RA RA since choosing À 1 > 0 and (s)) = 0, bounded potential function, we have Rs 0, s') XRa (8, a, 8') + ( (s) for all 8, E S and a E A.
Suppose RA = Rg. Then there exists some À >> 0 and a bounded potential function + : S + IR such that Ra a, s') = ARA(S, 8, 7 ) (s)) for all 8, E and a E A. Rearranging:
1 aa(s.a,s')= = x ( + ( (-))))))))))))))))))))))) -
(12)
Since 1 > and = ( a bounded potential function, it follows that RB RA.
Finally, suppose RA = RB and RB = RC. Then there exists some \1, d2 > 0 and bounded potential functions 11, $2 S IR such that for all 8, ES and a E A:
RB(s, a, 8') = RA, (5') - 1s)), Ro(s,a, a, 80)= ( a, 5¹) + 2 - 22()).
(13)
(14)
Substituting the expression for Rg into the expression for Re:
ac) = A2 Rs a, 7b) 41 1
(
+ (s')
(15)
= as + + (
+ D2()')) - (2201(5) + P2(
(16)
= =ARA(s,a, + ( ((s).
(17)
where A = A1 > 0 and ((s) = ( + (2(s) is bounded. Thus RA = Rc.
A.3.2 EQUIVALENT-POLIC INVARIANT COMPARISON (EPIC) PSEUDOMETRIC
Proposition 4.2 (The Canonically Shaped Reward is Invariant to Shaping). Let R: R SxxxS=x
be reward function and tb S - R potential function. Let [0, 1] be discount rate, and Ds E (SS) and D E (AA) be distributions over states and actions. Let R' denote R shaped by Φ: ((,,,,,8)) R(s,,, 8') + +0'' $(s). Then the canonically shaped R' and R equal:
CDS.DA (R') = CDs.PA (R).
Proof. Let s, s E ES Ax S. Then by substituting in the definition of R' and using linearity of expectations:
CDs.PA (R') (s,a, a, &
RR',,, A,)))
(18)
(19)
+
- - - -[()((S,AAAS)))99)))) - -
-HS,...))=-1,,,664....) - H(s, A, RR(S, A, S
(20)
a(s,,,,')) E/T A, R(s, A, -
(21)
CDS.DA (R) (s,a,s')
(22)
where the penultimate step uses E. [(())) ({)( since S and S' are identically distributed.
n
25

---

Published as a conference paper at ICLR 2021
Proposition 4.3. Let S and A be finite, with |S| 2 2. Let Ds A(S) and DA A(A). Let
R, V VSSAAX S + R be reward functions, with v/(s, a, s') all a, = (æ, u, x')l, X E R, I, E -anndd u A. Let DDs (R)(s, a, DD
R(s,a,s)). ) Then:
D 1) DD +1+ PA()))
(3)
Proof. Observe that:
DA DA (R)(,,,,)) B/ A,,') R(s, -,
(23)
where S and are random variables independently sampled from Ds, and independently sampled from DA.
Then:
(R+t))(Rtv) - (R) = @DS.DA()..
(24)
Now:
LHS - 1 - [B)
(25)
= max a.''S
[R [ A,S") 1(8, A,5") 7,(5,
(26)
max
(27)
a.e'ES
1[r = (
(28)
max (D) (y11(z s')
- 1[ s) - >=)()))
(29)
*,*'E8
= (1 + )D)xx) (x))D((z')
(30)
where the final step follows by substituting
and s' * (using |S| 2 2).
Lemma 4.5. The Pearson distance D, is a pseudometric. Moreover, let a, b E (0, 00), c, d R and X, Y be random variables. Then it follows that 0 S Dp(aX c, + d) = (X, Y)+ 1
Proof. For a non-constant random variable V, define a standardized (zero mean and unit variance) version:
E
z(V)
(31)
E
(v E[V)
The Pearson correlation coefficient on random variables A and B is equal to the expected product of these standardized random variables:
p B) E(Z))_B(((
(32)
Let W, X, Y be random variables.
=. Symmetry. Have p(X,Y) XY by commutativity of multiplication, (x,XY = XY, Triangle Inequality. For any random variables A, B:
Identity. Have p(X, X) = 1, so
(((AA)) Z(B))² = E [7(4)² (A) + ((B)]
(33)
= E [Z(A)²] + [Z(B)] - 2E (E(Z())((B))
(34)
= -2 (A))2((B)
(35)
= - B))
(36)
-A,
(37)
26

---

Published as a conference paper at ICLR 2021
So:
4D, = E (Z(W) z(r))²
(38)
E (Z(W) - 2(x) + Z(X) - -
(39)
E (Z(W) - 2(x))² +E (((X)) 2(r))²
(40)
+ +E - -
-
(W,
YD) (Z(W) ((X)) 2(Y))-
(41)
Since (4, B) [ is inner product over R, it follows by the Cauchy-Schwer inequality that
E[AB] $ V E B So:
DW
(42)
(), D)x,X))))
(43)
Taking the square root of both sides:
(WW, Y) < x
(44)
required.
Positive Affine Invariant and Bounded Dy(aX + c, bY + +d) = YY) is immediate from
pXX, Y) invariant to positive affine transformations, Have -1 s <(x S so 1- Y)
S
2 thus 0 S Y)
Theorem 4.7. The Equivalent-Poligy Invariant Comparison distance a pseudometric.
Proof. The result follows from Dp being pscudometric. Let RA Ry and Rg be reward functions mapping from transitions S x A to real numbers R.
Identity. Have:
DEPIc(RA,RA) D, (CDs.DA
CDs.AA (Ra) (S,A,S)) 0,
(45)
since x)
Symmetry. Have:
DEPiC(BA, RB)
D, (CDS.DA (RA) A,5),, CD..DA (RB) (5,
(46)
D2 (CDS.DA (RB) A, CD..DA (Ra) A,))
(47)
DEPIC RB, RA):
(48)
since
Triangle Inequality. Have:
DErIC(RA, Rc) = Dp (CDs.DA (Ra) (S, A,S",, CDS.DA (Rc) (S,
(49)
S D, (CDs.DA (Ra) (S, A, CDS. (RB) (S, A,A,
(50)
+ DD, (CDs.DA (RB) (S, A,)), CD. (Rc) (8, A,S))
(51)
DEric RA, RB) + DEric (R,, Rc),
(52)
since D,(X, 2) D,(X,Y) D,(Y,
Theorem 4.8. Let RA. R' Rg, R S x A x S + R be reward functionn such that R', RA and R6' = Rg. Then DEPIC(RR R'g) = DEFIC(RA, Rn) 1.
Proof. Since DEPIC is defined in terms of Dp- the bounds 0 < DEPIC(RA, R'z)) and
DEPIC RA, RB) & are immediate from the bounds lemma 4.5
Since R'A = RA and RBg- Rg. can write for X E (),
Rs = Xx
(53)
Rx( R xx'x(s)) xx(s),
(54)
27

---

Published as a conference paper at ICLR 2021
for scaling factor Ax 0 and potential function 4x : - RR By proposition 4.2
DDs.DA (R'x) DD (Rx)
(55)
Moreover, since CDS.DA (R) is defined as an expectation over R and expectations are linear:
DD DA (Rx) DA
(56)
Unrolling the definition of DEPIC and applying this result gives:
DEPIC(H's R''g)
D, (CDs.DA (S, CDs (S,,,))) (K
(57)
Dr (AACDs DA (Ra) (,, Ap Ds. (RB) (8, A,)"))
eqs. 55 and 56
D DC (Ra) A,,), (RB) (S,
lemma 4.5
= DEPIC RA, R.)..
A.3.3 NEAREST POINT IN EQUIVALENCE CLASS (NPEC) PREMETRIC
Proposition A.I. (I) DLP, is metric in LP space, where functions and identified they agree almost everywhere on D. (2) DLr.D a pseudometric if fanctions are identified only if they agree all points.
Proof. (1) DLP,D is a metric in the L space since L is a norm in the L space, and d(z, y) | yll is always metric. (2) As f g all points implies f g almost every- where, certainly (L, R) = O. Symmetry and triangle inequality do not depend on identity so still hold.
Proposition A.2 (Properties of DKPEC). Let RA, RB, Re S AxS R be bounded reward functions, and 2 0. Then DKPEC:
Is invariant under = in source:
D DxvEc(RA: Rc) = D Rc) if R. = Rg.
Invariant under scale-preserving in target: "Kvec(RA, RB) D DNPEC RA, Rc) Rg Rc Zero.
Scalable in target: ARg)
RA,, RRA,
Bounded:
DKPeC(RAA RA, RB) < ( RB).
Proof. We will show each case in turn.
Invariance under in source
RA Rg, then:
DErEE (RA, Ro) A inf R= inf DIe,D(R, Rc)
DIS,D(R, Re)
(58)
(59)
Rg
DKrEc(Ra Rc),
(60)
(61)
since R RA if and only if R = Rg as = an equivalence relation.
Invariance under scale-preserving= in target
RB R = Zero, then we can write Rp a, Rc(s, a, s') = = (e(s) for some
potential function t S R. Define (()) a, R(s,a, 70((') +s).. Then for any
28

---

Published as a conference paper at ICLR 2021
reward function R:SxAx R:
[i((s, Ro(s,a,s'))1 1/8
DL RB) -
E
8,0,8' nD
- (Rc(s, - 7 - 1/9
E
8,
1/2
E
[[[[(s, - - + +())) - Rc(s,a,,')) s')
E sas''D [If(R)(s, a, Rc(s, 1/8
D Df Rc),
(62)
Crucially, note f(R) is a bijection on the equivalence class [R]. Now, substituting this into the expression for the NPEC premetric:
DNPEC (Ra, RB)
inf DLr DLr,D(R,RB)
R=RA
(Lr, Rc)
eq. 62
R R
inf DL DLr,p(((R). Rc)
bijection on [R]
I(R)=R
inf RR, Rc)
bijection on [
RERA
DNPEo(RA RA, Rc).
(63)
Scalable in target
First, note that DLP,D is absolutely scalable in both arguments:
1/p
(AR,D(ARA,ARR, ARg) A
E 5
E D (3) - Rass,,,, 6') 1/p
|.| absolutely scalable
1/r
aNp s,a.s'>D
[Ra((,,ass') RB(s,a, s
E linear
1/r
|a] [IAA(,,,,'') - -Ro(,,,))))))
S
|X] (R. RB).
(64)
Now, for 0, applying this to DPPE:
DRPEC(RA, ARR) a inf DIr.D (R,Aa)
(65)
RERA
DiR.DAR inf
R XR
(66)
R=RA
= inf ADLo RB)
eq. 64
(67)
RERA
> =
inf Dir (R, RB)
(68)
RERA
XD RA, Rg).
(69)
29

---

Published as a conference paper at ICLR 2021
In the case À= 0, then: (N Zero) & inf DL zero) n=RA
(70)
1 R, (,,
1 R R
inf RERa
DLADD
(71)
2
1
inf Iteli ((, Zero)
2
(72)
inf D (R, zero) REER
(73)
D (RA, Zero).
(74)
Rearranging, we have:
DKPRO RA, Zero)= = 0.
(75)
Bounded
Let d Dxprc(Zero, RB). Then for any O, there exists some potential function & 8 + R such that the L distance of the potential shaping R(s, a,s") & (0(s)) D(s) from Rg satisfies:
DLr,D(R, RB) S d
(76)
Let À E [0, 1]. Define:
Rx(8,0,85) & ARa(s,a,5)) + R(s,a,s').
(77)
Now:
1/p
(R,, a
E [|,'(s,,, - R(ssa, - a())),
(78)
1/D
[I,
E
(79)
1/8
E [AP
[|a(s,,,'))1))
(80)
3,0,8'~
1/P
|I|
E RA as,)
(81)
= |A]D RA. Zero).
(82)
Since RA is bounded, Dro (R Zero) must be finite, so:
lim DIEDD( R) = 0.
(83)
It follows that for any > 0 there exists some À > 0 such that: DIrDD R) See
(84)
Note that RA R', for all A > 0. So:
DNPEC RB) s DLr,D(R's (R' RB)
(85)
DLr,p(H's R) + DLr DR, RB)
prop
A.
(86)
< e (c)
eq. 76 and
84
(87)
d 2c.
(88)
Since e > 0 can be made arbitrarily small, it follows:
DNpEC(RA, Ra) < A DxpRo(Zero, Ra),
(89)
completing the proof.
30

---

Published as a conference paper at ICLR 2021
Theorem 5.4. DNPEC is premetric on the space of bounded reward functions. Moreover, let RA. RA', RB. Rg' : x A S + R be bounded reward functions such that RA = RA' and RB Rs' Then 0 I DNPEC(RA*) , RR')) = Direc (R RR)
Proof. We will first prove DNPEC a premetric, and then prove it is invariant and bounded.
Premetric
First, we will show that DNPEC is a premetric.
Respects identity: DNPEC (RA, RA) 0
Dxprc(Zero, RA) = O then DNPEC RA. RA) = as required. Suppose from now on that
D D A, RA) f 0. follows from prop A.1 that DLP, (RA, RA) = Since = X, is an upper bound for D NNPEC(RA, Ra). By prop A. D Le,D is non-negative, so this is also a lower bound for D (NEC(RA: Ra). So D DNPEO (RA, RA) and:
DKPEC RA, RA).
DNPEC RA RA) D (Zero, RA) (Zero 0.
(90)
Well-defined: DNPEC( RA, RB) 2 0
By prop A. it follows that DEP R, RB) 2 0 for all reward functions S A Thus O is a lower bound for (DI,p((A RB) R S x A x S}, and thus certainly lower bound for {Drr D (R, Y) |
RR= = }} for any reward function X. Since the infimum is the greatest lower bound,
it follows that for any reward function X:
DKPEc(X, RB) & inf DLE,D (R, RB) 2 0.
(91)
REX
In the case that PPEC (ipec(Zero, (eero, RB) O, then DNFEC (RA. RB) 0 which is non-negative. From now suppose that (Xpre(Zero, RB) + O. The quotient of non-negative value with a positive value is non-negative, so:
DKPEO RB) > 0.
DNPRO Rp) D #NPEc(Zero, (Zero,
(92)
Invariant and Bounded
Since R'B RB. we have R'B XR = Zero for some À > 0. By proposition A.2 D is invariant under scale-preserving in target and scalable in target. That is, for any reward R:
DKPEC R, R'')) DKPEC ARB) XD (R, RB).
(93)
In particular, DXpec(Zero, Rg') ADKPEC CoMpec(eez) (Zero, RB). As X 0, it follows that (X Rg') = = (Zeeoo RB) 0.
Suppose (zeroo, RB) 0. Then DNPEC (R, Rg) = = DNPEC R, RB') for any reward R, so the result trivially holds. From now on, suppose D (Zero RB) # 0.
By proposition A.2
D&
NPEC is invariant to in source. That is, DEPEC (RA, RB)
R,), so:
DNPRO (T', Rn) = DNPEC RB) DNPEE (RA, RB) = DNPEC CRPEc(RA, Rn). (94)
D RB) D (Zero, RB)
By eq. 93
DNPEC (RA, R',) = A RB)
AD
D DKPEC (RA. RB) DNPEc RB).
(95)
XD (Zero, RB)
D (Zero Rs)
Since DNPEC is premetric non-ne non-negative. By the boundedness property of proposition A.2 DNP (R, RB) < DKPEC (Zero, RB), so:
DNPEC RA, RB) = (REE RA) D Rp)
$1,
(96)
which completes the proof.
31

---

Published as a conference paper at ICLR 2021
Note when DLP,D p is metric, then DNPEc(X.Y) = 0 if and only if X Y.
Proposition A.3. DNPEC is not symmetric in the undiscounted case.
Proof. We will provide a counterexample showing that DxpEC is not symmetric.
Choose the state space S to be binary {0, } and the actions A to be the singleton {0). Choose the coverage distribution D to be uniform on s - a for s E S. Take 7 = 1, i.c. undiscounted. Note that as the successor state always the same the start state, potential shaping has no effect on Dr D. so WLOG we will assume potential shaping is always zero.
Now, take (s)s)
2s and Rs(s) 1. Take p 1 for the L" distance. Observe that
DLr,p(Zere) RA) = 2 (10) + 2 = and Dzo.p(Zero, Rg) = 2 (11|+ + (1]) = 1. Since poten- tial shaping has no effect, De Rt) = Drr, p(Zero, It) and so DNpec(Zero, RA) = 1 and EXpec(Zero) RB)
Now:
DKPEC (RA, Rn) inf DIP Ctr,((RA,, RB) ASU
(97)
1 (11) + 12 1))
inf
(98)
ASO
2
1
(99)
2'
with the infimum attained À 2-2 But:
DErEc (RrEC(RB.Cr RA)
inf D Der,p(ARB,B RA)
(100)
A>D
inf 1
(2))
(101)
ASU
inf f(2),
(102)
2 ASO
where:
S(A) = [A] + 12 - A/.
>>0.
(103)
Note that:
f(A) 2
A (0, 2].
(104)
22 -
A E (2)
So f(A) 2 2 on all of its domain, thus:
OXPEC(RE RA) 1.
(105)
Consequently:
1
DNPEC RB) 11= DNNEE RB, RA),
(106)
so DNPEC is not symmetric.
A.4 FULL NORMALIZATION VARIANT OF EPIC
Previously, we used the Pearson distance D, to compare the canonicalized rewards. Pearson distance naturally invariant to scaling. An alternative is to explicitly normalize the canonicalized rewards, and then compare them using any metric over functions.
Definition A.4 (Normalized Reward). Let R : x A x S - TR be a bounded reward function. Let |I-II be a norm on the vector space of reward functions over the real field. Then the normalized R is:
(" = R(s,a, a, s')
(107)
|
Note that (NR) R for any X > as norms are absolutely homogeneous.
We say reward is standardized if it has been canonicalized and then normalized.
32

---

Published as a conference paper at ICLR 2021
Definition A.5 (Standardized Reward). Let R 8 A 8 R be bounded reward function. Then the standardized R. is:
R DA (R))*
(108)
Now, we can define a pseudometric based on the direct distance between the standardized rewards. Definition A.6 (Direct Distance Standardized Reward). Let be some coveruge distribution over transitions s S s'. Let Ds and D D be some distributions over states S and A respectively. Let S, S. be random variables jointly sampled from D. The Direct Distance Standardized Reward pseudometric between two reward functions RA and Rg is the LP distance between their standardized versions over D:
DDDSR (USSR(BA, (RA, RB) = D (S, (3SS,,)))
(109)
2
where the normalization step, Re uses the L norm.
For brevity, we omit the proof that DDDSR is a pseudometric, but this follows from DLr D being pseudometric in similar fashion to theorem 4.7 Note it additionally is invariant to equivalence classes, similarly to EPIC.
Theorem A.7. Let RA, RA', RB and R,,'' be reward functions mapping transitions S A to real numbers R such that RA= = RA' and RB Rp'. Then:
S DDDSR R'g) DDDSR (RA. RB) 1.
(110)
Proof. The invariance under the equivalence class follows from R being invariant potential shaping and seale in R. The non-negativity follows from Dr.,. p being a pseudometric. The upper bound follows from the rewards being normalized to norm 1 and the triangle inequality:
DDDSR ( RB)
1 - R
(111)
< (11 |1
(112)
(1 +
(113)
2 1.
L
Since both DDSR and EPIC are pseudometrics and invariant on equivalent rewards, it is interesting to consider the connection between them. In fact, under the 1 norm, then DDSR recovers EPIC. First, we will show that canonical shaping centers the reward functions.
Lemma A.8 (The Canonically Shaped Reward is Mean Zero). Let R be reward function mapping from transitions S x A x S to real numbers R. Then:
E [CD.PA (R) (S, A, S')l 0.
(114)
Proof. Let X, U and X' be random variables that are independent of S, A and S' but identically distributed.
LHS A ECCDs.DA (R) (5)
(115)
[R(S,, A, R JU, X') R(S,U, - -R(X,,,)))
(116)
= 4 [R(S", U,) - [ [R(S, UA(S
X'X
(117)
= ([] [RX, U.X) - EE [R(S,U,X') 7E [R(X, U, X')]
(118)
0.
(119)
where the penultimate step follows since A is identically distributed to U, and S' is identically distributed to X' and therefore to X.
Theorem A.9. DDDSR with p 2 is equivalent DEPIC. Let RA and Rg be reward functions mapping from transitions S x A to real numbers R. Then:
DDDSR (RA, RB) DEPIC(RA, RB).
(120)
33

---

Published as a conference paper at ICLR 2021
Proof. Recall from the proof of lemma 4.5 that:
D)(U,V) 2 2VB (Z(U) 2(1))
(121)
1
2 [2(() - 2(V)
(122)
where ||-1la is the L² norm (treating the random variables as functions on a measure space) and Z(U) is centered (zero-mean) mean) and rescaled (unit variance) random variable. By lemma A.8 the canonically shaped reward functions are already centered under the joint distribution Ds x D x Ds. and normalization by the L norm also ensures they have unit variance. Consequently:
DEPIC (RA, Rg)
Dp (CDs,DA (RA) (S, A, CDS.DA (RB) (S,).S))
(123)
2 [CDD.DD (Ra) (5)) - (CDs.DA (Rg) (S))
"1,
(124)
2 |RA(S, S²) (S, 5
(125)
2 DIA,D (5, A,S),, R (S, A,)))
(126)
DDSRR RRA RB),
(127)
completing the proof.
L
A.5 REGRET BOUND
In this section, we derive an upper bound on the regret in terms of the EPIC distance. Specifi- cally, given two reward functions RA and Rg with optimal policies T and TT. we show that the regret (under reward Rx) of using policy Tß instead of a policy T is bounded by a function of DEPIC(RA, RB). First, in section A.3. we derive a bound for MDPs with finite state and action spaces. In section A.6 we then present an alternative bound for MDPs with arbitrary state and action spaces and Lipschitz reward functions. Finally, in section A.7 tends to 0 as DEPIC (RPIC(RA,,A RR) + O.
we show that in both cases the regret
A. DISCRETE MDPs
We start in lemma A. 10 by showing that 1,2 distance upper bounds 1 distance. Next, in lemma A. show regret is bounded by the 1,1 distance between reward functions using an argument similar to 21.. Then in lemma 12 we relate regret bounds for standardized rewards RS to the original reward R. Finally, in theorem 4.9 we use section A.4 to express DEPIC in terms of the L distance on standardized rewards, deriving bound on regret in terms of the EPIC distance.
Lemma A.10. Let F, be a probability space and f S + E a measurable function whose absolute value raised to the n-th power for n E [1,2) has finite expectation. Then the I,a norm of I is bounded above by the I?2 norm:
|| S 1f
(128)
Proof.
Let X be a random variable sampled from P, and consider the variance of f(X):
E - = E [[((x)22 (1 E(I(())
(129)
E [[x(x))] - 2E [[]
(130)
= E [[ [1f(()]
- -
(131)
2 0.
(132)
Rearranging terms, we have
M = E [1 [2 I1
(133)
Taking the square root of both sides gives:
|// < ||
(134)
required.
n
34

---

Published as a conference paper at ICLR 2021
Lemma A.11. Let M be MDPR with finite state and action spaces S and A. Let RA, Ri SxAXS- be rewards. Let a' and B be policies optimal for rewards RA and RB in M. Let trajectories that policy induces in M at time step t.
Dr,t, 8,, az St+1) denote the distribution Let D(,,a,,'') be the (stationary) coverage distribution over transitions S x A x S used to compute K > 0 such that (* 04, 0,, 1+1))
DEPIC- Suppose that there exists for all time steps E N, triples St, St:8141 E S x A x S and policies E { BB. Then the regret under RA from executing Th optimal for RB instead of a is at most:
(t, 8,, at 8141)
2K
GRA (TA) GRA (TB) S 1-7 D DLLDD(RD RB).
(135)
Proof. Noting GRA (T) maximized when π = A. it immediate that
GR (T GR (Tb) = GRA ( - (T)
(136)
(Gra (TT) Gra (TT + (G (mT)) - (R)(t)))
(137)
S GRa (TT²) GR, (+ + GR (m - (=
(138)
We will show that both these terms bounded above by T-y DL,DD (BA, RB), from which the result follows.
First, we will show that for policy π E (TA
K DI,,DD,,RRRR (RA, RB). 1-7
R (T) Gra (T)
(139)
Let T be the horizon of M. This may be infinite (T = oo) when y < 1; note since x A x S is bounded, are A. R the discounted infinite returns Rr, (T), GR, (T) converge (as do their differences). Writing T = (so, au $1, ", we have for any policy n:
A (R)(T)
Grg (T)
(140)
BINDA
y' (R1(5 - Ra(s),4008011)
(141)
<
E D~Dr
(R 0,, (1(8
(142)
E 9
Rn(8 (1,84))))) [
(143)
t=
Σ
81 (1,1)) (8,, (4 (n(
(144)
Let (5t T.). By assumption, D (t, S2, ar (41) S KD(s a22 s' 11),
A < K
Σ
RA(S, az 8t41) - RB(S az 8141)
(145)
1=0
8e.0 ASXAXS
K
DL Dla, Ba)
(146)
1=0 0
Dr. DR Rp),
(147)
1
as required.
In particular, substituting =r gives:
K
(+)) (=))) =GRAA (TT)) GRa (TT)) <
D DR.,(RR, Rg)-
(148)
1 1-
35

---

Published as a conference paper at ICLR 2021
Rearranging gives:
K
GR (TB) 2 Gra (TB)
DD DIADD (RA,
(149)
1-7
So certainly:
K Dr. DIA Rs).
GRA (Tx) = max GR. (T) 2 Gn (Tn)
(150)
1-7
By symmetric argument, substituting A gives:
K GR T max GRD (T) 2 GRA (Ta) - 1-7 DDpDDDu RB).
(151)
Eqs. 150 and 151 respectively give Gny (a GnA (T²) S l-q and Gn, (Tt - (n S l-7
Combining these gives:
K GRA (TA) - Gn (TB) < 1-7 Du (RAA, RB).
(152)
Substituting inequalities 148 and 152 into eq. 138 yields the required result.
L
Note that D = Dunif, uniform over S x A x S, then S [AA
Lemma A.12. Let M be an MDP with state and action spaces S and A. Let RA, RB SxAxS R. be bounded rewards. Let ''A and TB be policies optimal for rewards RA and RB in M. Suppose the regret under the standardized reward R from executing π B instead of ' is upper bounded by some U I:
GRg (x Gze (1TT) U.
(153)
Then the regret under the original reward RA is bounded by:
GrA (T)) (RA( S 4U RAll-
(154)
Proof. Recall that
R CDS.DA (R)
(155)
|CDss.A (R)ll2
where CDS.DA (R) is simply R shaped with some (bounded) potential Φ It follows that:
1
( [CDs. DA (R)ll2 (R)
(156)
(Gn(I)) Engado ((()))),,
(157)
|CDDs.P (R)ll2
where 89 depends only on the initial state distribution dg- Since so does not depend on æ, the terms cancel when taking the difference in returns:
GR (T))
GRg (m
|CDss.DA (Ra)ll (Gra(T)) GRA(#T))
(158)
Combining this with eq
153 gives
GRA(TA) G (Ti)) S SUIIDDs.A (Ra)ll2-
(159)
Finally, we will bound |[CDs.Pa (Ra) in terms of R completing the proof. Recall:
CDS.PA (R) as))) R(s, a, s') E|yR(s' A, R(s, RRSS A,S)), A,)),, (160)
where S and S" are random variables independently sampled from Ds and A sampled from D By the triangle inequality on the L2 norm and lincarity of expectations, have:
||CDs.PA (R)ll2 < [R]]2 à + >11f1l2 + llglla + 7/c|,
(161)
Inn the finite-horizon case, there is also term 7 ((r)). where sT is the fixed terminal state. Since sy is fixed, it also cancels in eq. 158 This term can he neglected in the discounted infinite-horizon case as 7 (sx) 0 T no for any bounded +
36

---

Published as a conference paper at ICLR 2021
where s') = = A, X' a random variable sampled from Ds independently from S and S", have
a')) s') [R(s, A, S']] and EE [R((S, Letting
| Ex [[[((X S")
(162)
S xx E [R(X', {
(163)
= R(XX A,
(164)
|
(165)
So fll s ||]| and, by an analogous argument, l|l||2 I |R||2 Similarly
|c| = 1 [R(S, A, S')]]
(166)
S E [[R(S, A, I'][]
(167)
|R|]
(168)
< |Rll2
lemma A.10
(169)
Combining these results, we have
I[CDs.DA (R)ll2 S 4||
(170)
Substituting eq. int eq. 159 yields:
Gna(TA) - GRA(TH) RAl|R
(171)
as required.
Theorem 4.9. Let M a "-discounted MDPAR with finile state and action spaces S and A. Let RA, Rg S x A S - R be rewards, and A. be respective optimal policies. Let Da (t, St, at, St+1) denote the distribution over transitions x A x induced by policy at time t, and D(s, a, 8') be the coverage distribution used compute DEPIC- Suppose there exists K > 0 such that (D((st, at, 8t41) 2 (t, 8t, at, 88+1) for all times t E N, triples (8t, at, 8441) E S x A x S and policies π E AT BB.. Then the regret under RA from executing π instead of A is at most
GRA (T - GR, (T S 16K Ra (1 -1 DEPIC(RA, Ra),
where GR(TT) is the return of policy under reward R.
Proof. Recall from section th4t
DEPIC (RA, RB) -1)
(172)
Applying lemma A.10 we obtain:
Dr (RR RD) = |
- (S, S'Il & DDEIIc(RA, RB).
(173)
Note that vi is optimal for R and n is optimal for R since the set of optimal policies for R is the same as for R. Applying lemma A. and eq. 173 gives
2K 1 Dr p R R
4K DEDIEE RA,, Rn).
G (T²)
G RR
(TT)
(174)
1-7
Since A x S is bounded, RA and Ry must bounded, so we can apply lemma A.12 giving:
16K]| DEric RB).
Gn. (TX) GRA (TT) <
(175)
1
completing the proof.
37

---

Published as a conference paper at ICLR 2021
A.6 LIPSCHITZ REWARD FUNCTIONS
In this section, we generalize the previous results to MDPs with continuous state and action spaces. The challenge is that even though the spaces may be continuous, the distribution xx- induced by an optimal policy π may only have support on some measure zero set of transitions B. However, the expectation over a continuous distribution D unaffected by the reward at any measure zero subset of points. Accordingly, the reward can be varied arbitrarily on transitions B causing arbitrarily small or large regret - while leaving the EPIC distance fixed. To rule out this pathological case, we assume the rewards are Lipschitz smooth. This guarantees that if the expected difference between rewards small on a given region, then all points in this region have bounded reward difference.
We start by defining relaxation of the Wasserstein distance Wa in definition A.13 In lemma LemmalA.14 we then bound the expected value under distribution jt in terms of the expected value under alternative distribution y plus W,(,, v). Next, in lemma A.15 we bound the regret in terms of the L' distance between the rewards plus Wa; this is analogous to lemma A. in the finite case. Finally, in theorem 16 we the previous results to bound the regret in terms of the EPIC distance plus W..
Definition A.13. Let S be some set and let μt, v be probability measures on with finite first moment. We define the relaxed Wasserstein distance between μi and v by:
/ ||0 ull dp(x,, y), inf per.lu.))
Walu,v)
(176)
where L' ['( v) is the set of probability measures on S x S satisfying for all x, E S:
[ pl (ly. u(x),
(177)
[ p(z, p(a,))do=+ s av(y).
(178)
Note that W, is equal the (unrelaxed) Wasserstein distance (in the E norm).
Lemma A.14, Let S be some set and let μr, v be probability measures S. Let ʃ S R be an L-Lipschitz function on the & norm I1-II1- Then, for any a 2 1;
Ex- [[(x)]] S aBy [I((Y)]] + (W,
(179)
Proof. Let p V)( Then:
/ [=)))du((z)
Ex~a [[f(x)]]
definition of E (180)
/ [(<))dp(<z.))
μ is marginal of p
(181)
S / ((()) + L ||æ wll dp(x.,)
f LL-Lipschitz (182)
/ (5())dp(r, v) + L /11x= ||x- vll dp(p, v)
(183)
I (5(6)) / pla,
pla.v)drdy vidrdy + L / || wll dp(x,v)
(184)
s / [ L / ||0 1 yll dp(x, v)
eq. 178
(185)
alEy~~ [| / ||0- vl dp(x, w)
definition of E. (186)
Since this holds for all choices of p. we can take the infimum of both sides, giving:
/II= |Ir- dp(x,))))
Ex-y [lf(x)]] < aBy ~n [If(Y) + inf
(187)
pET.(H.)) aBya [I I.W.(U,)).
38

---

Published as a conference paper at ICLR 2021
Lemma A.15. Let be an MDPR with state and action spaces S and A. Let RA. Ry SxAxS be L-Lipschitz, bounded rewards on the & norm I1-Il1- Let T and F be policies optimal for rewards RA and RB in M. Let ( a2 St41) denote the distribution over trajectories that policy T induces in M at time step t. Let D(s, 8') be the (stationary) coverage distribution over transitions S A S used to compute DEPIC- Let Z and let Ba (t) max Wa (D D) Then the regret under RA from executing hh optimal for Rg instead of π is at most:
2a DL.D(RA,
Gn GRA (TB)
- 1-9
DL
RB) 4L
Ba())
(188)
Proof. By the same argument as lemma A. to eq.
144
we have for any policy m.
Gn
Gn S
Dr Da. (RA, RB).
(189)
t=
Let a(s.a, = Ra(s, s') (s a, s'), and note is 2L Lipschitz and bounded since RA and Rg are both L-Lipschitz and bounded. Now, by lemma A.14 letting = Da and v = D, we have:
DLADS (RA, Ra) S aDD RB) + 2LW, (D.,,, D).
(190)
So, for a E ( mB). , it follows that
[R. (T) (
RB) + 2L (t)...
(191)
1-7
By the same argument as for eq. 148 to 152 in lemma
A.ll it follows that
2a
GRA (TX) GRA (TT) I
D
RA
+ 4L > (t)),) t=0
(192)
1-?
completing the proof.
Theorem A.16. Ler M be an MDPAR with state and action spaces S and A. Let RA RB X A S - R be bounded, L-Lipschitz rewards the & norm 11-112- Let n' and H' be policies optimal for rewards RA and Ra in M. Let D (1,1 St, at 81+1) denote the distribution over trajectories that policy induces in M at time step Let D(s, a, 8') be the (stationary) coverage distribution over transitions x A x S used to compute DEPIC- Let a 2 1, and let B,(1) = max an W. (Da,a, D). Then the regret under R. from executing To optimal for Rg instead of I at most:
a ( DEPIC RB) + L Σ + BBll)
GRA(TTA) - GRA (TB) < RA
(193)
Proof. The proof for theorem 4.9 holds the general setting up to eq. 173
Applying lemma A.15 to
eq. 173 gives
2a
GR
(T3)
Gpg (TT)
<
D DL (R R.g + 4T.
(1)
(194)
1 1-
1=0
4a
DEPIC (RA, RB) + 4L r Ba(t).
(195)
1
t=0
Applying lemma A.12 yields
GRA( GRA (TT) < 161//1l22
DEPIC DEPIC (RA, RB) + L Σ 7 Ba(1)
(196)
1 1-
t=0
required.
39

---

Published as a conference paper at ICLR 2021
A.7 LIMITING BEHAVIOR OF REGRET
The regret bound for finite MDPs, Theorem 4.9 directly implies that, as EPIC distance tends to 0, the regret also tends to O. By contrast, our regret bound in theorem A. for (possibly continuous) MDPs with Lipschitz reward functions includes the relaxed Wasserstein distance Wa as an additive term. At first glance, it might therefore appear possible for the regret to be positive even with zero EPIC distance. However, in this section we will show that in fact the regret tends to 0 as DEPIC RA, RB) + in the Lipschitz case as well as the finite case.
We show in lemma 1.17 that if the expectation of non-negative function over a totally bounded measurable metric space M tends to zero under one distribution with adequate support, then also tends to zero under all other distributions. For example, taking M to be hypercube in Euclidean space with the Lebesque measure satisfies these assumptions. We conclude theorem A.18 by showing the regret tends to 0 as the EPIC distance tends to O.
Lemma A.17. Let M = (S, d) be a totally bounded metric space, where d(x, v) = || - y/1 Let (S, A. be a measure space on S with the Borel o-algebra and measure p. Let p. E (S)) be probability density functions functions on S. Let >> 0 such that p(s) 2 8 for all E S. Let fn S - R fiiiscoitt,unctionns functions on norm ||-||. Suppose lim Ex-p lI (X)
be a sequence of L-Lipschitz
Then
lim Ey [I (Y)I)
Proof. Since M is totally bounded, for each r > 0 there exists a finite collection of open balls in S of radius whose union contains M. Let (c) {s S ||s cll < r), the open ball of radius centered at c. Let ((r) denote some finite collection of (()) open balls:
C(r) = (Br() In e {1, ((()))
(197)
such that UnECO) S.
It is possible for some balls (c,, to have measure zero, μ (c,() O, such as if S contains an isolated point cn. Define P(r) be the subset of C(r) with positive measure:
P(r) = (B E C() n(B) > 0).
(198)
and let Pr,1, .. (r.Qu(rr) denote the centers of the balls in P. Since P(r) a finite collection, must have a minimum measure:
aK (r) min BB..
(199)
BEP
Moreover, by construction of P, a(r) > 0.
Let ('(r) be the union only over balls of positive measure:
S'
U B. BEP()
(200)
Now, let D(r) = S (r)), comprising the (finite number of) measure zero balls C(r). Since mea-
sures are countably additive, it follows that D(r) is itself measure zero: μ (D(r) = 0. Consequently:
[ g(s)dn SS g(s)du,
(201)
for any measurable function S R.
Since lim Ex<p [l.x = 0, for all r > 0 there exists some N, E such that for all n 2 Ny:
Ex-p (lx (X)l < (T.r(()).
(202)
By Lipschitz continuity, for any s, E S:
[fx()')) 2 [f((s) L L|s s|ll-
(203)
In particular, since any point E S'(rr is at most r distance from some ball center Pr.s then I (pra)) 2 [f) - Lr. So if there exists
('( such that [s)) 2 3Lr, then there must exist a ball center pr.a with (fn(pr.)) > 2Lr. Then for any point s' E (P..):
[)n()') 2 (n(p)))) Lr 2 Tr.
(204)
40

---

Published as a conference paper at ICLR 2021
Now, we have:
Exsp [X] & (((()))(()ddu(s
(205)
JES
S (EES)(M) (F((s)l(()dd((s)
eq. 201
(206)
(((()))(()dd(())
non-negativity of [s)(
(207)
/.eT. (fn(s)du((s)
p(s) 2
(208)
8..11 La (P.))
1du(s)
eq. 204
(209)
-OLrH(B,
integrating w.r.t. P
(210)
öLra(r)
a(r) minimum of (PB,(prr)).
(211)
But this contradicts eq. 202 and so can only hold if n < N,. It follows that for all n 2 N, and
E (r()), have [s)] 3 and in particular:
By [V)( 3Lr.
(212)
Let 6 > 0. Choose
3L Then for all 2 Nr. By [1 (Y)] <. It follows that:
lim Ey [1 (Y) = 0,
(213)
n
completing the proof.
Theorem A.18. Let M be MDPAR with state and action spaces S and A. Let RA RR A S-tR R. be bounded rewards on some norm ||-I] on S x A x Let T and Fi be policies optimal for rewards RA and Ry in M. Let (t, 8,, (141))))) denote the distribution over trajectories that policy π induces in M at time step t. Let D(s, a, be the (stationary) coverage distribution over transitions S x A S used compute DEPIC-
Suppose that either:
Discrete: and A are discrete. Moreover, suppose that there exists some K >> such that (D( a, st,8't+1) 2 (1,,, 0q 8' (11)) all time steps E N. triples 8t, 04 8441 S A S and policies π E {B)
2. Lipschitz: (S x Ax S,d) d) is a totally bounded measurable metric space where d(x, y) |a yll- Moreover, RA and RB T-Lipschitz ||-I|- Furthermore, suppose there exists some ō > O such that D(s, s') 2 ö for all s, a, E S x A x S, and that D (t, St, 0z, 8141) is non-degenerate probability density function (i.e. no single point has positive measure).
Then as DEPIC(RAL Rg) + O. GR. (T22 GRA (TT) + 0.
Proof. In case (/) Discrete, by theorem 4.9
GRA (TTA GRA (TT) < 16K]|RAl 1l,
DEPIC(RA: RB). 1-7
(214)
Moreover, by optimality of T we have 0 < (T,(TTT) - GRA (TT)). So by the squeeze theorem, as DEPIC(RA, RB) + 0, GRA (TT)) GRA (T + 0.
From now on, suppose we are case (2) Lipschitz. By the same argument as lemma A. up to eq. [44] we have for any policy m:
Gry (T) -Ggg(T) <
Σ
(RS, R
(215)
t=
41

---

Published as a conference paper at ICLR 2021
Applying lemma A.12 we have:
GRa (T) GRA ( - RAll2
DrA (R Ris).
(216)
t=0
By equation 173 we know that D2 w RR R& + 0 DEPIC [RA, RB) + 0. By lemma A.17
we know that D De,, (R.) Rig + 0 Dr. R RT}
+ 0. So can conclude that as
DEPiC(RA, RB) + 0:
Gra (T) GB (T) +
(217)
required.
42


Reviews:
[{"review_id": "tgUGeaVRIK6", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "- This paper proposes one main method EPIC to measure the differences between the reward functions of MDPs, and two weaker baselines methods NPEC, ERC. The methods are useful in directly comparing two different reward functions on a common MDPs, without running RL algorithms and comparing the resulted performance. \n- To me, the proposed approach is novel and interesting, and there is no similar previous work to my best knowledge, so I tend to give it an accept. \n- There are extensive experiments, but most of them are still based on hand-designed reward, and to judge whether the distance measure is good or not, it is still largely based on human judgement.  In Table 2, there is some experiment showing some correspondence between the \"distance to ground truth\" and the \"return\". The result shows some effect of all three proposed approaches. \n- You're now comparing the reward functions directly in the \"reward space\". But very different reward functions might still give similar optimal policies, and make the resulted performance similar.   Is it possible to compare the reward functions by inferring the similarity between the optimal policies (and without resorting to a RL algorithm)?  What's the pros and cons of this direction and your current direction? \n\n============ after rebuttal =============\n\nThank you for the response and revision, and I am sorry for my late response.  One experiment that I can think of to get around the issue of failure in RL optimization is to consider simple examples where RL algorithms can surely find the global optima.  This is the case for the tabular setting (like your GridWorld). This can be a proof of concept, but I admit that it might also be limited. So I think it is okay to keep your current presentation. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "Z8Q70Q-0b7_", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "**Summary of decision**\n\nThe problem setting is significant and the approach is original. The work provides both clear theory and experiments in favour of EPIC to compare reward functions. I currently am leaning towards a marginal rejection because of theoretical issues I've outlined below, but would happily raise my score if they were addressed. Adding additional experiments that I outline below would increase the score further, but fixing the theoretical issues are primary. \n\n**Pros**\n\nA gap in the literature of learning and evaluating reward functions is clearly identified and an explicit argument is made in favour of searching for alternatives to the rollout method. \n\nI really appreciated the serious attempt to develop baselines in section 5, based on a couple of intuitive notions for a desirable pseudometric. A substantial portion of the appendix is devoted to proving properties of the baselines!\n\nThe theoretical results are well-presented and comprehensive. I found especially significant the regret bound in Theorem 4.9; in light of this theorem, we have the practical consequence that minimizing EPIC distance closes the gap between optimal policies of different reward functions. I have verified the proofs for correctness and have found issues which I note below. These issues, however, seem quite fixable, and I would certainly increase my score upon seeing a revised version with the fixes.\n\nI enjoyed the discussion of the theory and it's motivation: I especially liked how the validity of the triangle inequality is tied to being able to measure how well one is doing wrt the original reward by using a proxy. \n\nThe experimental questions are precise and the experiments to answer them clearly designed. Rather than focus on chasing some benchmarks, I like that the work analyzes the proposed algorithm in terms of being able to compare equivalent reward functions, predicting policy performance, and the sensitivity to different visitation distributions. \n\n**Cons**\n\nTable 2 is a little hard to understand; it might be helpful to provide some summary measure of the discrepancy between the uniform and expert policy distances, which would help in interpreting table 2 in light of section 6.3. \n\nI would have liked to see at least one experiment into examining the failure cases of EPIC, along the lines of the discussion in the last paragraph of section 6.3. The discussion is nice, but it would be even better if a concrete experiment was performed!\n\nThe trends in policy performance in table 2 are certainly suggestive and lend credence to the claim that reward distance predicts performance, but I feel the evaluation is still a little lacking. Some more analysis on the probability of achieving the rankings given by each method would be helpful. I also would have liked to see a variant of table 2 where each of the models were treated separately, but measuring the reward distances at various points of training. For example, for the Regression onto reward labels method, the reward distance and episode return could be calculated at selected checkpoints in the Regression training method (e.g., after every x steps in minimizing the mean-squared error). This variant of the experiment would help to give a better idea of the relationship between reward distance and return because it would be \"apples to apples\". A similar comment applies to the experiment for comparing the reward distances over different visitation distributions.\n\nBeing more explicit in the proof of Theorem 4.8 would be helpful. It seems to me to be a result of affine invariance rather than D_\\rho being a pseudometric?\n\nThe first equality in the proof of invariance under scale on page 24 is incorrect. The expectation is inside of the power 1/p, and the operand is the absolute value of the reward difference to the power of p. I don't see how one can write the term as shown. As far as I can tell, D is also not defined. The same issue permeates the scalable in target proof, and the boundedness proof. It seems though that these proofs still follows through if one uses the proper definition of the L_p norm, so I am willing to discount this issue if it is fixed in a revision. \n\nIn the equation after the definition of the joint distribution in Lemme A.15, it seems that the integral of the joint over y should be \\alpha \\mu(x) \\int_{||x - y|| < r*(y)} \\nu(y) dy. Since we are integrating over y here, I'm not sure the expression as given is correct. The overall claim of Lemma A.15 seems plausible to me though given the definition of the relaxed Wasserstein distance, so I think a fix should be straightforward.\n\n**Things which didn't affect my decision**\n\nThe D_S(x) notation in proposition 4.3 should be defined; from what I understand, it refers to the probability mass of x under the empirical distribution of D_S.\n\nTypo in first sentence of proof of Lemma 4.5: should be \"zero mean and unit variance\".\n\nType in equation 21: should be p(x, y) instead of p(x, x).\n\n** Edit after author response **\nI've raised my score after the response from the authors regarding my concerns with the theory. \n\n** Edit after further author experiments **\nI think the paper is now even stronger given the inclusion of additional experiments into the failure cases of EPIC. I have upgraded my score accordingly. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "GGh4HSsluPE", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\n##########################################################################\n\nSummary:\n \nThe paper introduced Equivalent-Policy Invariant Comparison (EPIC) pseudometric to compare different reward functions directly without training a policy function. The authors provide an interesting direction for inverse reinforcement learning. The EPIC distance gives a bound on the regret between policies optimizing for one of the two reward functions relative to the other. The authors also conduct a didactic example to demonstrate efficacy.\n\n##########################################################################\n\nReasons for score: \n \nOverall, I'd vote for acceptance for the paper. The paper is well written and well-motivated. I find the topic is interesting and worth researching. The paper gives a deep analysis of EPIC in a reasonable setting.  However, my concerns lie on the feasibility : \n1) it is not clear to me what the computation cost of distance in high-dimension environments is. \n2) the visitation distribution D should have adequate support for every state; however, in most IRL settings, the demonstrated policy could be bias. How does EPIC apply under such settings?\n  \n##########################################################################\nQuestions during the rebuttal period: \n \nPlease address and clarify the concerns above.", "extra_scores": {}, "extra_text": {}}, {"review_id": "A_Pidpgz8e2", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThe paper introduces a pseudometric on reward functions, EPIC (Equivalent-Policy Invariant Comparison), based on the potential-based reward shaping (Ng. 2020). It formally analyzes the EPIC distance in detail and demonstrates its usefulness in comparing learned reward functions without the necessity of optimizing reward-specific policies. The empirical results show that the EPIC is more predictive of the policy returns than some baseline variants and robust to visitation distributions, even in unseen test environments. \n\n\nPros: \n\n-- This paper proposes and analyzes a theoretically grounded distance metric to evaluate learned rewards. It has several properties appealing to practical RL tasks. The EPIC pseudometric does not rely on policy optimization, which differentiates it from previous approaches. Moreover, EPIC is computable over arbitrary visitation distributions, making EPIC flexible in various practical scenarios. Finally, EPIC provides bounds on the policy performance difference when the visitation distributions meet some constraints. \n\n-- EPIC can significantly impact the reward learning/design-related communities because it is the first rigorous approach to evaluating candidate reward functions against the ground truth reward function without direct or indirect policy optimization. \n\n\nCons: \n\n-- The claimed property that EPIC bounds the difference in policy returns relies heavily on the visitation distribution. It seems that the capability of EPIC to provide relevant information mostly comes from the visitation distribution. It would be helpful if there are some additional discussions about the EPIC's predictive power when this kind of reliance could be problematic. Moreover, the claim focuses on the upper bound of the difference. In some cases, it could also be helpful to know the lower bound of the policy-return difference if the EPIC value is big enough.\n\n-- The theoretical derivations and analyses of EPIC are the most substantial parts of the paper.  Some additional experimental studies on domains with high-dimension perceptions would strengthen the paper's contributions and provide more guidance in adapting EPIC.\n\n\n\nIn section 6.3, all three metrics degenerate significantly in the mixture case. Why does the predictive power of EPIC decrease in this mixture setting?  \n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The proposed approach for evaluating reward functions is theoretically grounded while having several properties appealing to practical RL tasks. This novel approach fills a gap in the literature. All reviewers agree that this paper has a place at ICLR.
Decision: Accept (Spotlight)