Reward Distance Comparisons Under Transition Sparsity
Authors: Clement Nyanhongo
Bruno Miranda Henrique
Eugene Santos
Venue: Accepted by TMLR ()

Abstract: Reward comparisons are vital for evaluating differences in agent behaviors induced by a set of reward functions. Most conventional techniques utilize the input reward functions to learn optimized policies, which are then used to compare agent behaviors. However, learning these policies can be computationally expensive and can also raise safety concerns. Direct reward comparison techniques obviate policy learning but suffer from transition sparsity, where only a small subset of transitions are sampled due to data collection challenges and feasibility constraints. Existing state-of-the-art direct reward comparison methods are ill-suited for these sparse conditions since they require high transition coverage, where the majority of transitions from a given coverage distribution are sampled. When this requirement is not satisfied, a distribution mismatch between sampled and expected transitions can occur, leading to significant errors. This paper introduces the Sparsity Resilient Reward Distance (SRRD) pseudometric, designed to eliminate the need for high transition coverage by accommodating diverse sample distributions, which are common under transition sparsity. We provide theoretical justification for SRRD's robustness and conduct experiments to demonstrate its practical efficacy across multiple domains.

Published in Transactions on Machine Learning Research (04/2025)
Reward Distance Comparisons Under Transition Sparsity
Clement Nyanhongo
Thayer School of Engineering Dartmouth College
Bruno Miranda Henrique
bruno. bww.o..irrand....uriuuu....e hwt.
Thayer School of Engineering Dartmouth College
Eugene Santos Jr.
Thayer School of Engineering Dertmouth College
Reviewed OpenReview: https: //ppre/veeen net/ form?? id= haP58YYomm.
Abstract
Reward comparisons vital for evaluating differences in agent behaviors incuced by set of reward functions. Most conventional techniques utilize the input reward functions to learn optimized policies, which are then used to compare agent behaviors. However, learning these policies can be computationally expensive and can also raise safety concerns. Direct reward comparison techniques obviate policy learning but suffer from transition sparsity, where only a small subset of transitions are sampled due data collection challenges and fcasibility constraints. Existing
taae-ooftheearttt direct reward comparison methods are ill-suited for these sparse conditions since they require high transition coverage, where the majority of transitions from a given coverage distribution are sampled. When this requirement is not sat- isfied, a distribution mismatch between sampled and expected transitions can occur, leading to significant errors. This paper introduces the Sparsity Resilient Reward Distance (SRRD) pscudometric, designed to climinate the need for high transition coverage by accommodat- ing diverse sample distributions, which are common under transition sparsily. We provide theoretical justification for SRRD's robustness and conduct experiments to demonstrate its practical efficacy across multiple domains.
1 Introduction
In sequential decision problems, reward functions often serve the most "succinct, robust, and transferable" representations of task (Abbeel & Ng. 2004), encapsulating agent goals, social norms, and intelligence (Silver et al. 2021 Zahavy et al. 2021 Singh et al. 2009). For problems where reward function is specified and the goal is to find an optimal policy that maximizes cumulative rewards, Reinforcement Learning (RL) is predominantly employed (Sutton & Barto 2018). Conversely, when a reward function is complex or difficult to spocify and past expert demonstrations (or policics) are available, the reward function can be learned via Inverse Reinforcement Learning (IRL) (Ng & Russell 2000).
In both RL and IRL paradigms, reward functions govern agent decision-making and reward comparisons can help assess the similarity of these functions in terms of their induced bchaviors. The task of reward comparisons aims to assess the similarity among collection of reward functions. This can be done through pairwise comparisons where the similarity distance D. RB) between two reward functions, RA and Rg (vectors, not scalars), computed. The similarity distance should reflect variations not only magnitude but also the preferences and behaviors induced by the reward functions. This characterized by the property of policy invariance, which ensures that reward functions yielding the same optimal policies are considered

---

Published in Transactions on Machine Learning Research (04/2025)
(a)
(b)
(c)
No feasibility
feasibility constraints. Limited sampling (low rollout count).
Movement restrictions imposed.
constraints.
No limited sampling
(high rollout count).
R
10
10
100
Figure 1: (Transition Spansity in a 10 10 Gridworld Domain) In this illustration, each transition starts from a starting state and ends in a destination state s'. For clarity in visualization, we consider action- independent rewards, 8'). In (a), high transition coverage results from a high rollout count (number of policy rollouts) in the absence of feasibility constraints, leading to the majority of transitions being sampled (blue points). In (b); low coverage results from a low rollout count the absence of feasibility constrainns, leading fewer sampled transitions (red points). In (c), low coverage results from feasibility constraints, such movement restrictions that only allow actions to adjacent cells, which significantly reduce the space of sampled transitions (green points) irrespective of rollout count.
similar even if their numerical reward values differ (Ng et al. 1999). This makes direct reward comparisons via distance measures such as Fuclidean or Kullback-Teibler (KT.) divergence unfavorable since these distances do not maintain policy invariance. To satisfy policy invariance, traditional reward comparison techniques have adopted indirect approaches that compare behaviors derived from the optimized policies associated with the reward functions under comparison (Arora & Doshi 2021j. However, these indirect approaches pose the following challenges: (1) they can be slow and resource-intensive due to iterative policy learning via RL, and (2) policy learning may not be favorable in critical online environments such as healthcare or autonomous vehicles, where safety considerations are paramount (Amodei al. 2016 Thomas et al.) 2021). Therefore, developing direct reward comparison methods that bypass the computationally expensive process of policy learning, while maintaining policy invariance is highly important.
To achieve policy invariance in direct reward comparisons, Gleave et al. 2021 | introduced the Equivalent Policy Invariant Comparison (EPIC) pseudometric. Given the task to compare two reward functions, EPIC first performs reward canonicalization to express rewards in a standardized form by removing shaping, and then compules the Pearson distance to measure the difference between the canonical reward functions. Although theoretically rigorous, EPIC falls short in practice since it is designed compare reward functions under high transition coverage, when the majority of transitions within the explored state and action space are sampled. In many practical scenarios, achieving high transition coverage can be impractical due to transition sparsity, a condition where minority of transitions are sampled. The remaining unsampled transitions may have unknown or undefined reward values (especially if unrealizable), which can distort the computation of reward expectations during the canonicalization process.
Transition sparsity can be attributed to: (1) limited sampling when data collection challenges result fewer sampled transitions; and (2) feasibility constraints when environmental or agent-specific limitations restrict certain transitions. Consider, for instance, standard 10 10 Gridworld domain which has total of 100 states, each represented by an (x,y) coordinate. The total number of possible transitions is least 10, 000 (100 states x number of actions x 100 states) if at least one action cxists between every pair of states (see Figure D However, feasibility constraints such as movement restrictions might limit the transitions that can be sampled. For example, an agent that can only move to its neighboring states by taking singlo-step cardinal directions (actions: up, right, down, left) in cach state will explore fewer than 400 transitions (100 states x4 actions), as shown in Figure [.. To illustrate the impact of limited sampling, consider scenario where transitions sampled via policy rollouts. Assuming that factors such feasibility
2

---

Published in Transactions on Machine Learning Research (04/2025)
constraints, the transition model, and the policy rollout method are kept constant, the extent of sampled transitions is proportional to the number of policy rollouts (see Figure [ and ( To alleviate the impact of transition sparsity in reward comparisons, we present the Sparsity Resilient Reward Distance (SRRD) pscudometric, which does not assume the existence of reward samples with high transition coverage. During canonicalization, SRRD introduces additional reward expectation lerms to accommodate a wider and more diverse range of transition distributions.
In practical settings, reward comparisons can be useful for broad range of applications such as: (1) Evaluating Agent Behaviors- By comparing how different reward functions align or differ using specified similarity measures, agent rewards can be grouped, to reason and interpret different agent behaviors. This can be useful in IRL domains, where there is need to extract meaning from inferred rewards computed to represent agent preferences (Ng & Russell 2000 Santos & Nyanhongo 2019). For instance, in sport domains such as hockey, reward comparisons could be useful in inferring player rankings and their decision- makiing strategies (Luo et al. 2020). (2) Initial Reward Screening- In RL domains, direct reward comparisons could serve as preliminary step to quickly identify rewards that will achieve a spectrum of desired behaviors before actual training. This could be beneficial in scenarios where multiple possible reward configurations exist, but some might be more efficient. (3) Addressing Reward Sparsity Reward comparisons could also tackle issues such as reward sparsity, by identifying more informative and easier-to-lears reward functions that might be similar in terms of optimal policies but are more desirable than sparse reward functions.
Contributions In this paper, we introduce the Sparsity Resilient Reward Distance (SRRD) pseudometric, designed to improve direct reward comparisons in environments characterized by high transition sparsity. SRRD demonstrates greater robustness compared to existing pseudometrics (such as EPIC), which require high transition coverage. SRRD's strength lies in its ability to integrate reward samples with diverse transi- tion distributions, which are common in scenarios with low coverage. We provide the theoretical justification for SRRD's robustness and demonstrate its superiority through experiments in several domains of varying complexity: Gridworld, Bouncing Balls, Drone Combat, Robomimic, Montezuma's 's Revenge, StarCraft II, and MIMIC-IV. For the simpler domains, Gridworld and Bouncing Balls, we evaluate SRRD against man- ually defined factors such nonlinear reward functions and feasibility constraints, to fully understand its strengths and limitations under controlled conditions. In the more complex domains such as StarCraft II, we assess SRRD in environments characterized by large state and action spaces, to gauge how it is likely to perform in realistic settings. Our final experiment explores a novel and practical application of these pseu- dometrics as distance measures within a k-nearest neighbors algorithm, tailored to classily agent behaviors based on reward functions computed via IRL. Empirical results highlight SRRD's superior performance, as evidenced by its ability to find higher similarity between rewards generated from the same agents and higher variation between rewards from different agents. These results underscore the crucial need to account for transition sparsity in direct reward comparisons.
2 Related Works
The EPIC pseudometric is the first direct reward comparison technique that circumvents policy learning while maintaining policy invariance (Gleave et al. 2021 In practical settings, EPIC's major limitation is that it is designed to compare rewards under high transition coverage. In scenarios characterized by transition sparsity, EPIC underperforms due to its high sensitivity to unsampled transitions, which can distort the computation of reliable reward expectation terms, needed during canonicalization. This limitation has been observed by Wulfe et al. (2022). who introduced the Dynamies-Aware Reward Distance (DARD) pscudometric. DARD improves on EPIC by relying on transitions that are closer to being physically realizable; however, it still remains highly sensitive to unsampled transitions.
Skalsc et al. 2024h also introduced a family of reward comparison pscudometrics, known as Standardized Reward Comparisons (STARC). These pseudometrics are shown to induce lower and upper bounds on worst- case regret, implying that the metrics are tight, and differences in STARC distances between two reward
Transition sparsity arises when minority transitions are sampled. This is different from reward sparsity, which occurs when rewards are infrequent or sparse, making RT. tasks diffieult.
3

---

Published in Transactions on Machine Learning Research (04/2025)
functions correspond to differences in agent behaviors. Among the different STARC metrics explored, the Value-Adjusted Tevelling (VAL) and the VAT.Poenntial functions are empirically shown to have marginally tighter correlation with worst-case regret compared to both EPIC and DARD. While an improvement, a significant limitation of these metrics is their reliance on value functions, which can be computed via policy evaluation a process that. incurs a substantially higher computational overhead than sample-based approximations for both EPIC and DARD. In small environments, these metrics can be computed using dynamic programming for policy evaluation, an iterative process with polynomial complexity relative to the state and action spaces (Skalse et al. 2024). In larger environments, computing the exact value functions becomes impractical hence the value functions need to be approxinated via neural networks updated with Bellman updates (Skalse et al.] 2024). Since the primary motivation for direct reward comparisons is to eliminate the computationally expensive process of policy learning, incorporating value functions is somewhat contradictory since policy evaluation is iterative, and it can have comparable complexity with policy learning tochniques such as value iteration. Our work focuses on computationally scalable direct reward comparison pseudometrics (such as EPIC and DARD), which do not involve iterative policy learning or evaluation.
The task of reward comparisons lies within the broader theme of reward evaluations, which aim to explain or interpret the relationship between rewards and agent behavior. Some notable works tackling this theme, include, Lambert et al. (2024), who developed benchmarks to evaluate reward models in Large Language Models (LLMs), which are often fine-tuned using RI. via human feedback (RLHF) to align the rewards with human values. These benchmarks assess criteria such as communication, safety and reasoning capabilities across a variety of reward models. In another line of work, MMhmud et al. (2023) presented a framework leveraging human explanations to evaluate and realign rewards for agents trained via IRL. on limited data. Lastly, Russell & Santos (2019) proposed method that examinos the consistency between global and local explanations, to determine the extent to which reward model can capture complex agent behavior. Similar to reward comparisons, reward evaluations can be influenced by shaping functions, thus necessitating techniques such as canonicalization as preprocessing steps to eliminate shaping (Jenner & Gleave 2022
Reward shaping is a technique that. transforms a base reward function into alternate forms (Ng el al. 1999)
This technique mainly employed in RL for reward design where heuristics and domain knowledge are
integrated to accelcrate learning (Mataric 1994 Hu et al. 2020 Cheng ct al. 2021 Gupta ct al. 2022 Suay
ct al.
2016). Several applications of reward shaping have been explored, and some notable examples include:
training autonomous robots for navigation (Tenorio-oonalez, et al. 2010); training agents to ride bicycles
Randlov & Alstrom 1998); ; improving agent behavior in multiagent contexts such as the Prisoner's Dilemma
Babes et al.] 2008); and scaling RL algorithms in complex games (Lample & Chaplot 2017 Christiano
et al.] 2017). Among several reward shaping techniques, potential- shaping is the most popular due to its preservation of policy invariance, ensuring that the set of optimal policies remains unchanged between
different versions of reward functions (Ng al. 1999 Wiewiora al., 2003 Gao & Toni 2015).
3 Preliminaries
This section introduces the foundational concepts necessary for understanding direct reward comparisons, and the critical challenge of transition sparsity which our proposed approach, SRRD (detailed in Section 4), is designed to address. We begin by outlining the Markov Decision Process formalism, followed by a discussion of policy invariance. Finally, we review the existing key direct reward comparison pseudometrics (EPIC and DARD) and examine their limitations, which motivate the development of SRRD.
3.1 Markov Decision Processes
A Markov Decision Process (MDP) is defined as a tuple (8, A. R), where S and A are the state and action spaces, respectively. The transition model T: S :SSSx A S + 1], dictates the probability distribution of moving from one state, s E S, to another state, s' E S, under an action a E A, and each given transition is specified by the tuple (s, a, s'). The discount factor 7 E [0, 1] reflects the preference for immodiate over future rewards. The reward function R: : S A X + R assigns a reward R(s, a, s') to each transition. A trajectory = ((50, on), "i,,)."))"............. n E Zt, is sequence of states and actions, with total return:
4

---

Published in Transactions on Machine Learning Research (04/2025)
g(T) = Ei oe, $141). The goal in MDP is to find policy S x A- [0, 1] (often via RL) that maximizes the expected return [[g(r)].
Given the subsets S. CCS, A S A, and Sj S, the tuple (Si, A, Sz) represents the set of transitions within the cross-product S, A Sy. The associated rewards are:
R(S,, A,5)) = {R(s, a, (',, E E Ax
and the expected reward over these transitions is denoted by AI, In the standard MDP for- mulation, the reward function is fully specified for all possible transitions including those that may be unrealizable. However, in many practical settings, such as offline RL (Levine et al. 2020 Agarwal et all 2020 Chen et al.) (024). we are often limited to datasets of reward samples that are only defined over a subset of observed realizable transitions. In this paper, a reward sample is defined as a restriction of R to a subset B _ S x A x S, where B consists of sampled transitions under a specified policy. We assume that rewards are defined for transitions in B, and are undefined for transitions not in B. Given a batch of sam- pled transitions B, the coverage distribution D(s, a, defines the probability distribution over transitions used to generate B. The sampled state space and action space are denoted by S S and A C A. The sets of all possible distributions over A and S are denoted by AA and AS respectively, and the individual distributions over states and actions are denoted by Ds E AS and D E AA.
3.2 Policy Invariance and Direct Reward Comparisons
In direct reward comparisons, policy invariance is crucial as it ensures that reward functions that differ due to potential shaping are treated equivalent, since they yield the same optimal policies (Ng et al. 1999
Formally, any shaped reward can be represented by the relationship: R'(s, a, s') = R(s, a, s') + F(s, a, where is a shaping function. Potential shaping guarantees policy invariance, and takes the form:
R' a, 8') = R(s, a') + ro(s)) ((s),
(1)
where is the original reward function, and e is a state-potential function. Reward functions R and R'' are deemed equivalent as they yield the same optimal policies. To effectively compare reward functions that may differ numerically but induce the same optimal policies, the use of pseudometrics is highly important. Tet X be a set, with z, y, E X, and let d X x X - (0) define pseudometric. This pseudometric adheres to the following axioms: (premetric) d(æ,
0 for all x E X; (symmetryy d(x,,)) v) d(u, a)) for all x, E X; and (triangular inequality) d(x, v) S d(x, 2) d(z,, y) for all x, y, 2 E X. Unlike true metric, pseudometric does not require that: d(z. y) = = x = making it ideal for identifying equivalent reward functions that might have different numerical values.
The EPIC pseudometric was introduced by Gleave et al. (022) as a direct reward comparison method that maintains policy invariance. To compute EPIC, reward functions are first transformed into canonical form without potential shaping; and then, the Pearson distance is computed to differentiate the canonical rewards. The EPIC canonicalization function is defined as follows:
CEPIC (R) = R(s, s') + E|TR(s', A, S² - R(s, (, -RS,,
(2)
where, S ~ Ds, S' ~ Ds, A ~ DA, with Ds and DA being distributions over states and actions, respec- tively. Given a potentially shaped reward, I''ss, a, 8') = R(s, a, s') + 76(5)) - o(s), canonicalization yields: CRPIo(R'))s,, 8') = (R) a, 8') Pres; where Φres = -
is the remaining residual shaping. EPIC assumes that S and S' are identically distributed such that E[o(S)) B[o(S)), resulting in Ores 0. This makes EPIC, invariant to potential shaping, since, CErIC(R) = (R') Finally, the EPIC pseudometric between two reward functions RA and Rn is compuled as:
DEPIC RB) (p(CEPIc(RA)) CEPIC((B)),
(3)
where, for any random variables X and Y, the Pearson distance Dp is defined as:
D,(XYY) = 1 v1-
(4)
5

---

Published in Transactions on Machine Learning Research (04/2025)
The Pearson correlation coefficient is given by: p(X, Y) B[(x -xx) -x where j denotes the mean, a the standard deviation, and E[(( 1x) /uy)] is the covariance between X and Y. The Pearson distance is defined over the range: 0 S Dp(X, < 1, where D, Y) = 0 indicates that X and Y are highly similar since p) = -1 (perfect positive correlation), and Dp(X, = indicates that X and Y are maximally different since ((X,Y) = -1. The Pearson distance is scale and shift invariant since Dp(aX bc,bY+d] = DD(X,.Y) Y), where, a, b. d E IR are constants (Gleave et al. 2021 Therefore, the EPIC pseudometric is scale, shift and shaping invariant, which are volicy-preserving translormations. Computing CEPIC requires access to all transitions in reward function, making it feasible only for small environments. For reward functions with large or infinite state and action spaces, Gleave et al. (022)) introduced the sample-based EPIC approximation, denoted as ČEPIC, and is computed as:
()) = R(s,a, 8') + NM (z,
Σ
R(s',u,
Σ
R(s u,
NM (x,u)EBar
Σ (a,))BM B
E R(x,uxx))
(5)
where transitions are sampled from a batch By of Ny samples from a coverage distribution D, and state- action pairs, are sampled from a batch BM of NM samples from the joint state and action distributions, Ds x DA- Each term in ČEPIC approximates the corresponding expectation term in CEPIC (Equation 2 for example, 2
NM ((nn))BB R(s', u, x)) estimates E|yR(s', A. S.)
Wulfe et al. (2022) observed that EPIC oflen depends on transitions that are physically unrealizable, as it requires all (both realizable and unrealizable) transitions from the space A x S The unrealizable transitions can introduce crrors in reward comparisons since rewards for these transitions are often arbitrary and unreliable. To mitigate this challenge, the authors introduced DARD, which incorporates transition models to prioritize physically realizable transitions. The DARD canonicalisation function is given by:
CDARD(R))s, a,,)'') R(s, 8') + BlyR(s', : A,) R(s, A,S") - 7R(('' -,((S'AA,"))
(6)
where A ~ DA, S' T(s.A), S" T(s', A), and T is the transition model. DARD is invariant to potential shaping and generally improves upon EPIC by distinguishing between the subsequent states to (denoted by S') and s' (denoted by 5"). Transitions A, and (s' A, are generally in-distribution with respect to the transition dynamics T since S' is distributed conditionally based on (s, A), and S" is distributed conditionally based on (s',A). Therefore, these transitions naturally align with the dynamics of the sampled transitions, resulting lower likelihood of being unrealizable. However, transitions (S', A, are more likely to be out-o--distribution with respect to the transition dynamics T, since S" is not distributed conditionally according to (S", A), but rather to (s', A). Consequently, DARD can be sensitive to out-of- distribution transitions in (S' (S", S",,, which have higher likelihood of being unrealizable. Nonetheless, Wulfe et al. (2022) argue that these transitions are closer to being physically realizable since (5', A,S") transitions are in close proximity to and 8', compared to transitions that are utilized in EPIC. Computing the exact DARD compulation can also be impractical in large environments, hence, Wulfe et al. (2022) introduced a sample- based DARD approximation, denoted by CDARD (see Appendix A.1
3.3 Unsampled Transitions
Consider a reward function R: R:SxAxS- R, where S the state space and A the action space. A reward sample generated according to a coverage distribution D, and it spans a state space 5d C S and an action space AD C A. We define the following sets of transitions:
Full Coverage Transitions (TD)- The set of all theoretically possible transitions within the reward sample's statc-action space. This set is represented as T = 5 x AP x SD SS Ax
Sampled Transitions (TS)- The set of transitions that are actually present in the reward sample. Due to feasibility constraints and limited sampling, this set is a subset of the full coverage transitions: T CTP.
Unsampled Transitions (T")- The set of full coverage transitions that are not explored in the reward sample. These transitions be both realizable and unrealizable, and T TD) \ T.S
6

---

Published in Transactions on Machine Learning Research (04/2025)
(a)
55
(b)
83
(c)
16
55
54
84
S5
$3
Sp
52
Transitions
Sampled
Expected
Transitions
Sampled
Expected
Transitions
Sampled
Expected
($,,4,5)
Nu 8
(4,,,,5)
N₂
(4,,,55)
N₂
8
NM 8
(s).A,5)
4
Nи 8
A,
Ny 8
(S.A.S")
NM
(S,A,S")
Nia 64
(S,A,S")
N2
a(Ceric a..))) 0.0
(,, 2.84
(R) 7.36
(()annD(R) (z)) = 0.0
(RCna sz)) = 0.46
(R) (z))) = 1.18
a(CsnRD(R) (R) 0.0
= 0.18
a(CsAKD (R)s,, 1.10
Figure 2: (Impact of unsampled transitions on canonicalizing R(s1, 21, (2)8)) Sampled transitions are those explored in the reward sample, while expected transitions are those anticipated by ČErIC assuming full coverage. As coverage decreases from (a) to (c), due to a reduction in the number sampled transitions, the standard deviation of ČEPIC (SPic(R)(s))) (s), a, $2) increases, indicating CEPIC'S increased instability to unsampled transitions. For comparison, CSARD and ČDard have lower standard deviations, signifying higher stability.
A major limitation of the EPIC and DARD pseudometrics is that they are designed to compare reward func- tions under high coverage, where |T$| = 1T% As | + [T',, the performance of these pseudometrics significantly degrades due to an increase the number of unsampled transitions. To illustrate this limita- tion, consider Equation 5 used to approximate CEPIC. To perform the computation, we need to estimate: E[R(s', A, S))) by dividing the sum of rewards from s' to S by NM transitions; E[R(s, A,)) by dividing the sum of rewards from to S' by NM transitions; and E[R(S, A, 5")] by dividing the sum of all rewards from S to S' by NM transitions, where NM < SSP x A is the size of the state-action pairs in the batch BM- Every state E S is ideally expected to have NM transitions to all other states S', which can be impractical under transition sparsity when some transitions might be unsampled. Since reward summations are divided by large denominalors due to NM (see Equation 5 when coverage is low, the number of sampled transitions needed to estimate the reward expectation terms will be fewer than expected, introducing significant error.
Figure 2 illustrates an example showing the effect of unsampled transitions on canonicalization across three reward samples spanning a state space S = S' = (s1,..,,88) 88} and an action space, A = {a1), ). such that NM 8, under different levels of transition sparsity. Rewards are defined as R(s;, 85) = - where i E {1,...,8) 8), and state potentials are randomly generated such that: [Ø(s)] < 20, with 7 0.5. The task is to compute CEPIC(())s), 01, $2) over 1000 simulations. For all reward samples, the mean (R)rIc(R)ss (1188))))))))) 82)) O, but the standard deviation ((CEric(R)(s) 01, 82)) varies based on coverage. In Figure a the reward sample has high coverage (100%), hence, the number of observed and expected mapped to the same value (se 0), resulting in standard deviation a aCCepic (1), a1 s2)) = O, highlighting consistent reward canonicalization. In Figure 2p, the reward sample has moderate coverage and the fraction of unsampled transitions is approximately 33%. As a result, (CCepre(()))) (,, 82)) 2.84, which is relatively high, signifying EPIC's sensitivity to unsampled transitions. In Figure 2 the reward sample exhibits low coverage and the fraction of unsampled transitions is approximately 77%, indicating significant discrepancy between the number of observed and expected transitions. Consequently, af ((CEPIC(R)(s) (1, 01 $2)) 7.36, highlighting EPIC's increased instability due to unsampled transitions. For comparison, we include the DARD and SRRD
transitions equal. In this scenario, EPIC is highly effective and all shaped rewards

---

Published in Transactions on Machine Learning Research (04/2025)
estimates, which exhibit lower standard deviations, signifying greater stability. DARD reduces the effect of unsampled transitions by relying mostly on transitions that are closer to 8 and s' (8' and S"), which typically comprise a smaller subset of states compared to those required by EPIC. However, this localized focus can make DARD highly sensitive to variations in the composition of transitions between the reward samples under comparison, since it might lack the context of transitions further from s and 8', potentially limiting robustness. In this paper, we use DARD as an experimental baseline.
4 Approach: Sparsity Resilient Reward Distance (SRRD)
The molivation behind SRRD is to establish a direct. reward comparison lechnique that imposes minimal assumptions about the structure and distribution of transitions in reward samples, ensuring robustness under transition sparsity. To derive SRRD, we integrate key characteristics of CDARD and CEPIC as follows:
ODARD eliminates the requirement that the set of states that can be reached from and s' must be similar, thereby increasing the flexibility of transition sample distributions considered. We will refer to states that can be reached from o as St, and states from s as S2.
In CDard, the transitions (S', A, S") are generally in close proximity to and s' because S' ~ T(s, A) and S" ~ T'''', A). These transitions may not capture the states that are further away from s and s', potentially lacking the overall context of the reward sample. To address this issuc, similar to how CEPIC uses transitions for the entire sample, (S, A,S", we utilize transitions for the entire sample, which we denote as: (S3, A, S4), where S3 encompasses all initial states from the sampled transitions, and S4 is the set of all states that are subsequent S3.
These modifications reduce the impact of unsampled transitions, as reward expectations computed based on the observed stuctueee of the sampled transitions, without assuming full coverage. With these consider- ations, we derive the modified canonical equation as:
Ci(R) s') = R(s, a, s') - Ely((s A, - A.S
(7)
where: S₁ and S2 are subsequent states to s' and s, respectively; Sg encompasses all initial states from all sampled transitions; and S₃ are subsequent states to S3. Applying C1 to a potentially shaped reward R'(s, s') = R(s, a, s') + ro(s') ) o(s), we get: (s, = (R) a, s') + &resl, where,
&rest Eh - (Sa)) + (5(5)) 76(S2))
C is not theoretically robust since it yields the residual shaping drest (the remaining shaping after canoni- calization). To cancel E[o(S)), V, E 4} in Grest, we can add rewards R(S,, A, k;) to induce potentials (ki);) - (SS:); where k; can be any arbitrary set of states. This results the equation:
C2(R))(,,0, 8') R(s, + E(7R(6, A,S:) R(s, A, 7R(S,, A,S4)
(9)
+ + A1 R(S2, A, K2) + 7R(5, A,ka) R2S(S A, k.))
Applying C2 to a potentially shaped reward, we get: (2(t' 0, = C2( a, s') dres2, where,
dres2 = E[T>0((k1) 7 (k))) 72 (ks) 72 (k2))
(10)
See Appendiz A.3 for derioations of &rest and Øres2-
The canonical form Cg is preferable to C1, since it enables the selection of k; to eradicate dres2. A convenient solution to ensure that: k = k4 and hn = ha such that E(((k) )] = E[((k;)) and E[o(k2]] = E[ resulting in 0res2 O. We choose the solution: in kG = Ss, and k2 ky Ss: where S3 are subsequent states to S1, and Sg are subsequent states to Sz. This leads to the following SRRD definition:
8

---

Published in Transactions on Machine Learning Research (04/2025)
Definition 1 (Sparsity Resilient Canonically Shaped Reward). Let R: S A R be reward functionn. Given distributions Ds E AS and DA E AA over states and actions, let S3 be the set of states sampled according to Ds, and let A be the set of actions sampled according to DA. Furthermore, let T(5 A) be a transition model governing the conditional distribution over next states, where, SS are subsequent states to S3. For each & E S3 and s' E S1, let S be the set of stales sampled according to T(1 s', A), and S. be the set of states sompled according to T(S2ls, A). Let S2 represent non-terminal states in S2. Similarly, let So and Se be set of states sampled according to T(S Si, A) and T(So) (2, A), respectively. The Sparsity Resilient Canonically Shaped Reward is defined
CannD(R)(s.a) s' a(s.a,s' + R(y A, 51) - R(s, S25) RR(S,, + 2 R(S( 4, 5s) y R((2,, A, 56) + y R(S,, A, 56) R( Ss)] +1
(11)
Note that in OSRRD, we first sample S2 as subsequent states from 8, and then derive S2 as non-terminal states in S2. This modification ensures that A,, S A, Se), which is crucial for SRRD's robustness in Theorem 1 In practice though, the difference between $2 and S2 is generally minimal, especially in long-horizon problems where terminal states tend to be fewer compared to non-terminal states. The SRRD canonicalization function is invariant to potential shaping as described by Proposition [
Proposition 1. (The Sparsity Resilient Canonically Shoped Reward is Invariant to Shaping) Let R S x A + R be a reward function and & + R be a state potential function. Ayplying CSRRD to a polentially shaped reward (s,,,,, = R(s, a, 8") + 70(s) - Φ(s) satisfies: CsnnD( = Cs"
Proof. See Appendix A.4
Given reward functions RA and RB, the SRRD pscudometric is computed as:
DSRRD RB) = D,(CsRRD (RA), CSRRD (SRRD(RB))
(12)
where Dp is the Pearson distance. For robustness, we establish an upper bound on regret showing that as DSRRD - 0, the performance difference between the policies induced by the reward functions under compar- ison, RA and Rg, approaches 0, as described by Theorem 2 Depending on the transition model dictating the composition of [Si,.... Sa), CSARD can be invariant to shaping across various transition distributions without requiring full coverage, provided that, for each set of transitions (S:, S2) in the reward expectation terms, all transitions in the cross-product S x A x S, have defined reward values. This is guaranteed when the full reward function R is available.
In practical scenarios, the full reward function may be unavailable, and CSRRD can be approximated from reward samples, resulting in ČSRRD (see Definition S). In these settings, the transitions needed for each reward expectation term in ČSRRD: might be unsampled due to transition sparsity. Despite this challenge, approximations for ČSRRD are robust due to the strategic choices of k; (see Equation and [1]. S, and Se, which ensure that the approximations are ideal for the following two reasons: First, for any reward sample, we can compute reliable expectation estimates for the first six terms, since for each set of transitions (S:, A, Sj). S, is distributed conditionally based on (S;.A) hence, these transitions naturally align with the transition dynamics that dictate the nature of the reward sample. However, for transitions in the last two terms, (S3, A, S6) and (S4, A, Ss), Sg is not distributed conditionally based on (S3, A) but on (S2, A), and S; is not distributed conditionally based on (S4, A) but on (S1, A); hence these transitions may not align well with the transition dynamics that dictate the structure of the reward sample, making these transitions highly susceptible to being unsampled. Second, while there might be significant. fractions of unsampled transitions in (Sa, Ss), and (S,, A, Se), minimal set of sampled transitions are likely to exist, because:
Transitions A, S (S,, S;S;):
Since S₁ are subsequent states to 8', and S₁ are subsequent states for all sampled transitions. It follows that, S, S S4 (see example Appendix A.6), hence, (S1, Ss) S (S4, A, Ss).
Transitions (S,, A6) S A,
S2 is the set of non-terminal subsequent states from s. Since S3 encompasses all initial non-terminal states from all sampled transitions, it follows that: S2 S3, hence, (S2, A, C (S3, S,).).
9

---

Published in Transactions on Machine Learning Research (04/2025)
Therefore, we can get decent fractions of sampled transitions in (Sg, S6) and (S4, A,),, which typically reduces the extent and impact of unsampled transitions in SRRD, making it robust under transition sparsity, as described in Section 4.1, Theorem
In summary, SRRD is designed to improve reward function comparisons under transition sparsity. To achieve this, SRRD introduces additional reward expectation terms into canonicalization, to ensure that rewards are standardized (remove shaping) based on the observed distribution of sampled transitions, without assuming full transition coverage. Regarding computational complexity, when employing the double-batch sampling method that involves batch By of Nv transitions, and another batch Bys of NM state-action pairs for canonicalization (refer to Appendix A.1 EPIC has a complexity of O(mxx NN N3))), and both DARD and SRRD have complexities of ( (see Appendix A.11 This paper adopts the double-batch sampling approach to maintain consistency with prior works, however, alternative sample- based approximations are also viable. Specifically, Appendix [3.2 explores sample-based approximation method that employs unbiased estimates, and Appendix B.3 explores the use of regression to infer reward values for unsampled transitions. Across all these approximation variants, SRRD consistently outperforms both DARD and EPIC under conditions of transition sparsity, confirming its robustness.
4.1 Relative Shaping Errors
This section provides theoretical evaluation on the robustness of the sample-based approximations: ČSRRD. Čdard, and CepIc, to unsampled transitions. We first discuss the relevant definitions and assumptions for the analysis, then present Theorem ! comparing the three methods. For reward function R. the structure of an arbitrary reward canonicalization method (such as CSRRD, CDARD, and CEPIc) takes the form:
Cs( -Ro,))))8--,,,,,,,,-
R(s, 8') 8') + + Σ (a,
(13)
where, a, is a constant, |ag| S I, and i E (l,..., 1} are indices denoting the state subsets, S S. The sample-based approximation for Og is denoted by Čs. Given non-zero reward sample R we can bound the maximum range of each canonical reward by defining the upper bound canonical reward as follows:
Definition 2. (Upper Bound Canonical Reward) Let R be a non-zero reward sample defined over a set of transilions B, and let Ös be an arbitrary sample-bused canoniculization method. Furthermore, let Z = (ax a, s'll) be the marimum absolute reward. The upper bound canonical reward is given by:
U(Cs(B)(s,a,5))) = nZ
(14)
The justification for Definition is that Cs(R)(s, has n-terms with absolute values bounded by 7 (both (Rss,,,5)), S Z and A,)) s 2), hence, U(Cs(B)(s, as))'')) nZ. The non-zero assumption on R guarantees that there exists at least one sampled transition with non-zero reward, ensuring that U(Cs(R)(s a, s²)) 2 O. To quantify the performance bounds of the canonicalization methods, we define the relative shaping error as follows:
Definition 3. (Relative Shaping Ervor (RSE)) Let H' be shaped, non-zero reward sample defined over a set of transitions B, and let Ös be a sample-based based reward canonicalization method, such that: Cs(R') = Cs(R) + ØR, where ΦR is the residual shaping term. Suppose that OR can be expressed as: ΦR = òØ + K where Kg a constant that does not vary with (s, a, s'), and &a is the effective residual shaping term. Furthermore, let (P(Cs(R)(ss 8²)) = represent the upper bound of the unshaped canonical reward, where, Z = max a, s')l). The relative shaping error is defined as:
RSE(Cs(R)(s,a = l U(Cs(B((s,a,51)
(RR(s,0,5)) nZ
(15)
The relative shaping error (RSE) designed to theoretically quantify the impact of residual shaping in reward distance comparisons. The denominator, U(Cs(R))s, 8')) nZ, represents upper bound on the
10

---

Published in Transactions on Machine Learning Research (04/2025)
magnitude of the base (unshaped) canonical reward, and it serves to normalize the impact of shaping. A low RSE suggests that U(Cs(R)(+ a, s")) is substantially larger than @ a, 8'),, indicating that the impact of shaping is likely minimal. Conversely, high RSE implies that U(Cs (R)(s, (asss,,s))) a,)") is relatively small compared to ( s')), highlighting more likely significant influence of the effective residual shaping. Note that in the RSE definition, the effective residual shaping term is $ = Φn K2 where K is a constant that does not impact the Pearson distance (since its shift invariant), and hence, the reward distances. For a comprehensive discussion on the derivation of the RSE definition, refer to Appendix [A.2.I
With regard to reward samples, we define forward and non-forward transitions as follows:
Definition 4 (Forward transitions). Given a reward sample that spans state space S, and an action space A. Consider the state subsets S; E S. Transitions (S,, S,) are forward transitions if Sj is distributed conditionally based on A), according to the underlying transition dynamics of the reward sample.
Definition 5 (Non-forward transitions). Given reward sample that spans a state space S, and action space A. Consider the state subsets St, Sy C S. Transitions (St, A, Sy) are non-forward transitions when the states in Sj are not distributed conditionally based on (St, A), but are instead based on (Sk, A), according to the underlying transition dynamics of the reward sample.
In reward canonicalization methods, given transitions A.. needed in computing reward expectations, both forward and non-forward transitions can have unsampled transitions since canonicalization methods typically require the cross- product of all transitions from S; to Sj. However, forward transitions are gen- erally more robust to being unsampled since they are usually in-distribution with the underlying transition dynamics governing the reward samples, hence, they naturally align with the progression of rewards in the sample. In contrast, non-forward transitions are highly prone to being unsampled (and also unrealizable) as they may include a significant fraction of transitions that are out-of-distributtin with the reward sample's transition dynamics. Based on the rationale that forward transitions are more robust being unsampled compared to non-forward transitions, to make our analysis more tractable, we will assume that the fraction of unsampled transitions in forward transitions is negligible, leading to Theorem
Theorem 1. Consider the reward comporison task two equivalent non-zero reward samples that differ due to potential-bass basse shaping, and share the same set of sampled transitions, B. During canonicalization, consider the forward and non-forward transition sets needed to compute the reward expectation terms, and assume that the fraction of unsampled forward transitions in both reword samples is negligible. Each reward sample can be expressed as R8[s,,, a, s') R(s, a, a,s') + +s))('')- -x()) for i E [1,2], where, is the unshaped reward sample, y a discount factor, and (5(() is the potential shaping function for R,. Under transition sparsity, the upper bound of the Relative Shaping Error (RSE) for OSRRD is lower than that of ČDARD and ČEPIC respectively, in the order:
M
2M 37 RSE(CEEICC S
M 7
RSE((SRRD) S RSE(( 37'
where, M = mnax,e5(1)666) is the marimum magnitude of potential shaping across all states for the reward samples, and Z = max R(s,,((s, s')) is the marimum absolute value of the unshaped reward sample.
Proof. See Appendix A.2
In more precise terms, Theorem evaluates the robustness ČSRRD, CDARD, and ČEPIC against residual shaping introduced by unsampled transitions from non-forward transitions, which are more likely to be out-of-distribution with the transition dynamics that generated the reward samples. The theorem assesses the upper bounds of the RSE across the three canonicalization methods to determine their sensitivity to residual shaping, assuming that the reward samples under comparison induce the same optimal policies, and share the same set of transitions. These assumptions ensure that we isolate the differences between the canonicalized reward samples to variations in residual shaping. A lower upper bound implies that a canonicalization method is likely to be less sensitive to the effects of residual shaping and, hence, it is more likely to reveal the actual similarity between the unshaped reward samples under comparison. As shown by the upper bounds of the relative shaping errors, the approximation for ČSaRd theoretically more robust, compared to those of CEPIC and CDARD, since it has the smallest upper bound.
11

---

Published in Transactions on Machine Learning Research (04/2025)
5 Experiments
To empirically evaluate SRRD, we examine the following hypothoses:
H1: SRRD is a reliable reward comparison pseudometric under high transition sparsity.
H2: SRRD can enhance the task of classifying agent behaviors based on their reward functions.
In these hypotheses, we compare the performance of SRRD to both EPIC and DARD using sample-based
approximations (see Appendix A.1) h. In H1, we analyze SRRD's 's robustness under transition sparsity resulting from limited sampling and feasibility constraints. In H2, we investigate a practical use case to classify agent behaviors using their reward functions. Experiment tests H1 and Experiment 2 tests H2.
Domain Specifications To conduct Experiment 1, we need the capability to vary the number of sam- pled transitions, since the goal is to test SRRD's performance under different lcvels of transition sparsity. Therefore, Experiment 1 is performed in the Gridworld and Bouncing Balls domains, as they provide the flexibility for parameter variation to control the size of the state and action space:] These two domains have also been studied in the EPIC and DARD papers, respectively. The Gridworld domain simulates agent movement from given initial state to specified terminal state under static policy, within 200 timesteps. States are defined by (r, v) coordinates where 0 S x < N and 0 S y < M implying |S = NM. The action space consists of four cardinal directions (single steps), and the enviromment is stochastic, with a probability of transitioning to any random state irrespective of the selected action. When c = 0, a fcasibility constraint is imposed, preventing the agent from making random transitions. The Bouncing Balls domain, adapted from Wulfe et al.] (2022). simulates a ball's motion from a starting state to a target state while avoiding randomly mobile obstacles. These obstacles add complexity to the environment since the ball might need to change its strategy to avoid obstacles (at a distance, d = 3). Each state is defined by the tuple (z, y, d), where (I. indicates the ball's current location, and d indicates the ball's Euclidean distance to the nearest obstacle, such that: 0 S x < N and 0 S y < M. The action space includes cight directions (cardinals and ordinals), and we also define the stochasticity-level parameter for choosing random transitions.
The objective for Experiment 2 is to test SRRD's performance in diverse and near-realistic domain settings, where we have no control over factors such as the nature of rewards and the level of transition sparsity, Therefore, in addition to the Gridworld and the Bouncing Balls domains used in Experiment 1 (but with fixed parameters), extend our evaluation to the following testbeds: Drone Combat-
battlefield environment
between two swarms, adapted from a predator-prey gym environment (Anurag 2019 Montezuna'ss 's Revenge an Atari benchmark dataset with human demonstrations for the Montezuma's ' Revenge game (Kurin et al., 2017), StarCraft IT - a simulation of combat, scenarios where a controlled multiagent team aims to defeat a default Al enemy team (Vinyals et al., 2019 Robomimic an open source dataset of robotics manipulation tasks incorporating both human and simulated demonstrations (Mandlekar et al. 2021), and MIMIC-IV a real-world de-identified electronic health dataset for patients admitted at an emergency or intensive care unit at Beth Israel Deaconess Medical Center in Boston, MA (Johnson et al.] 2023 These domains resemble complex scenarios with large state and action spaces, enabling us to test SRRD's (as well as the other pseudometrics) generalization to rear-realistc scenarios. Further details about these domains, including information about the state and action fcatures are described in Appendix C.5
Reward Functions Extrinsic reward functions are manually defined using a combination of state and action features. For the Drone Combat, Montezuma's Revenge, and StarCraft II domains, we use the default game engine scores as the reward function, and for Robomimic, rewards are based on task completion (see Appendix C. For the Gridworld and Bouncing Balls domains, in each reward function, the reward values are derived from the docompasition of state and action features, where, (sy1...., 8fn) is from the starting state 8; (afi,..., f is from the action a; and (f/1...., ( is from the subsequent state s'. For the Gridworld domain, these features are the (z, y) coordinates, and for the Bouncing Balls domain, these include (x, y, d), where d is the distance of the obstacle nearest to the ball. For each unique transition, using randomly
Experiment excludes the Drone Combat, MIMIC-IV, Robomimic, Montezuma's 's Revenge, and StarCraft II, since these domains have very large state and action spaces that hinder effective coverage computation.
12

---

Published in Transactions on Machine Learning Research (04/2025)
generated constants: {ul,,..., un) for incoming state features; {wi,... wm } for action features; {ui, for subsequent state features, we create polynomial and random rewards as follows:
Polynomial:
R(s,a, = w18 +... + Jn + wiafi +... #m + 81
+.... + un
where a is randomly generated from 1-10, denoting the degree of the polynomial. Random: R(s, a, s') B, where B is a randomly generated reward for each unique transition.
For the polynomial rewards, the same across the ent sample, but other constants vary between different transitions. The same reward relationships are used to model potential shaping functions. In addition, we also explore linear and sinusoidal reward models (see Appendix C.2 For complex environments such StarCraft IT and MIMIC-IV, specilying reward functions can be challenging, hence we also incorporate IRL to infer rewards from demonstrated behavior. For IRL, we consider the following methods: Maximum Entropy IRL (Maxent) (Ziebart et al.) 2008); Adversarial IRL (AIRL) (Fu et al. 2018); and Preferential-Trajedd
IRL (PTIRL) (Sntos et al. 2021). The algorithms are summarized in Appendix C.7
5.1 Experiment 1: Transition Sparsity
The goal of this experiment is to test SRRD's ability to identify similar reward samples under transition sparsity as a result of limited sampling and feasibility constraints.
Objective:
The EPIC and DARD pseudometrics struggle in conditions of high transition sparsity since they are designed compare reward functions under high coverage. SRRD developed to be resilient under transition sparsity and this experiment tests SRRD's performance relative to both EPIC and DARD.
Relevance:
This experiment is conducted on a 20 x 20 Gridworld domain and a 20 x 20 Bouncing Balls domain. For all simulations, manual rewards are used since they enable the flexibility to vary the nature of the relationship ween reward values and features, enabling us to Lest the performance of the pseudometrics on diverse reward values, which include polynomial and random reward relationships. We also vary the shaping potentials such that [R(s, a, s')l S 1nø(s') o(s) I 5) ap(s,,,.')) s')l. For each domain, a ground truth reward function (GT) and an equivalent potentially shaped reward function (SH) are generated, both with full coverage (100%). Using rollouts from uniform policy, rewards R and R' are sampled from GT and SH respectively, and these might differ in transition composition. After sample generation, R and It' are canonicalized and reward distances are computed using common transitions between the reward samples, under varying levels of coverage due to limited sampling and feasibility constraints. The SRRD, DARD, and EPIC reward distances are computed, as well as DIRECT, which is the Pearson distance between the reward samples, without canonicalization. Since R and R' are drawn from equivalent reward functions, an accurate pseudometric should yield distances close to the minimum Pearson distance, Dp O; and the least accurate should yield a distance close to the maximum, Dp 1. DIRECT serves as a worst-case performance baseline, since it computes reward distances without canonicalization (needed to remove shaping). We perform 200 simulation trials for each comparison task and record the mean reward distances.
Approach:
Simulations and Results: Limited Sampling: Using rollouts from a uniform policy, we sample R and R' from GT and SH, respectively, under a stochasticity-level parameter, = 0.1. The number of transitions sampled controlled by varying the number of policy rollouts from 1 to 2000. The corresponding coverage is computed the number of sampled transitions over the number of all theoretically possible transitions (= 18 x A x SI). Figure 3p summarizes the variation of reward distances to transition coverage across different levels of transition sampling in the Gridworld and Bouncing Balls domains. As shown, SRRD outperforms other basclines as it converges towards Dp = 0 faster, even when coverage is low. DARD generally perforrmss EPIC, however, it is highly prone to shaping compared to SRRD since it is more sensitive to unsampled transitions. All pseudometrics generally outperform DIRECT, illustrating the value of removing shaping via canonicalization. No significant differences are obscrved the general trends of results between the two domains, and additional simulations are presented in Appendix C.4 In conclusion, the proposed SRRD consistently outperforms both EPIC and DARD under limited sampling.
13

---

Published in Transactions on Machine Learning Research (04/2025)
Legend:
DIRECT
SRRD
EPIC
DARD
Gridworld
Bouncing Balls
random rewards
polynomial rewards
random rewards
polynomial rewards
Distance
0.4
0.50
Distance
0.4
0.4
Dp
0.2
0.25
Dp
0.2
0.2
20
40
60
80
100
20
40
60
80
100
0.0
0
20
40
60
80
100
0
20
40
60
80
100
coverage (%)
coverage (%)
coverage (%)
coverage (%)
(a) Effect of limited sampling
random rewards
polynomial rewards
random rewards
polynomial rewards
Distance
0.4
0.3
0.4
0.2
Dp
0.2
Dp
0.2
0.1
0.2
0.1
2
4
7
3
4
6
3
2 coverage (%)
coverage (%)
coverage (%)
coverage (%)
(b) Effect of feasibility constraints
Figure 3: (Transition Sparsity). The figure illustrates the performance of reward comparison pseudometrics in identifying the similarity between potentially shaped reward functions under two conditions: (a) limited
sampling and (b) feasibility constraints. A more accurate pseudometric yields Pearson distance Dp close 0, indicating a high degree of similarity between shaped reward functions, while a less accurate pscudometric results in D, close to 1. In both experiments, transition coverage is calculated transitions to the set of all theoretically possible transitions | A S], including both feasible and unfeasible transitions. Each coverage data point represents an average over 200 simulations at constant policy rollout count, with coverage data points generated by varying the number of policy rollouts from to 2000 (see Appendix C.3). In panel (a), EPIC and DARD lag behind SRRD at low transition coverage due to limited sampling, but their performance gradually improves as coverage increases with higher rollout counts. In panel (b), movement restrictions significantly reduce transition coverage, regardless of rollout sampling frequency, which negatively impacts EPIC's performance (almost similar to DIRECT).
the ratio of sampled
Simulations and Results: Feasibility Constraints: Using rollouts (ranging from to 2000) from a uniform policy, we sample R and R' from GT and SH, respectively. To impose feasibility constraints, we set the stochasticity-level parameter, = 0, restricting random transitions between states such that only movement to adjacent states is permitted. These movement restrictions ensure that coverage is generally low (< 10%), even though the number of rollouts is similar to those in the first experiment. Figure 3p summarizes the results for the variation of reward distances to transition coverage under the movement restrictions. As shown, SRRD significantly outperforms all the basclines indicating its high robustness.
5.2 Experiment 2: Classifying Agent Behaviors
The goal of this experiment is to assess SRRD's effectiveness distance measure in classifying agent behaviors based on reward functions. If SRRD is robust, it should identify similarities among reward functions from the same agents while differentiating reward functions from distinct agents.
Objective:
This experiment demonstrates how reward comparison pseudometrics be used interpret reward functions by relating them to agent behavior. In many real-world situations, samples of agent behaviors are available, and there is need to interpret the characteristics of the agents that produced these behaviors. For example, several works have atlempted to predict player rankings and strategies using past game histories (Luo et al. 2020 Yanai et al.) 2022). This experiment takes a similar direction by attempting to classify the identitics of agents from their unlabeled past trajectories using reward functions. The reliance on reward functions rather than the original trajectories based on the premise that reward functions are "succinct." " and "robust", hence preferable means to interpret agent behavior (Abbeel & Ng 2004).
Relevance:
14

---

Published in Transactions on Machine Learning Research (04/2025)
Approach: In this experiment, we train k-nearest neighbors (k-NN) classifier to classify unlabeled agent trajectories by indirectly using computed rewards, to identify the agents that produced these trajectories. We examine the K-NN algorithm since it is one of the most popular distance-based classification techniques. The experiment is conducted across all domains, and since we want to maximize classification accuracy, we consider different IRL rewards, including: Maxent, AIRL, PTIRL as well as manual (extrinsic) rewards. For manual rewards: we utilize the default game score for the Drone Combat, StarCraft II, and Montezuma's Revenge domains; environmental sparse rewards for task completion in the Robomimic domain; and feature- based (for example, polynomial) rewards for the Gridworld, Bouncing Balls and MIMIC-IV domains, where we induce random potential shaping. For each domain, examine SRRD, DIRECT, EPIC, and DARD distance measures for & k-NN reward classification task. The steps for the approach are as follows:
Create agents X (.1,..., with distinct behaviors.
2. For each agent E X, generate collection of sets (CF (.). where each 9 (rfii J.l is a q-sized set of trajectories. Compute reward functions { ..... Rg. using IRL or manual specification based on each corresponding 9
3. Randomly shuffle all the computed reward functions R (from all agents), and split into the training Rtroin and testing Beest sets.
4. Train N-NN classifier using each pseudometric (as distance measure) Rarain and test it Riest-
Table 1: The accuracy (%) of different reward comparison distances in N-NN reward classification.
DOMAIN
REWARDS
DIRECT
EPIC
DARD
SRRD
Manual
69.8
69.3
70.0
75.8
Maxent
57.4
57.5
68.9
70.0
Gridworld
AIRL
82.3
84.9
85.0
86.2
PTIRL
82.2
84.2
83.4
86.0
Manual
46.5
47.3
52.0
55.2
Bouncing Balls
Maxent
39.7
46.0
50.8
49.9
AIRL
41.2
46.1
49.8
56.3
PTIRL
70.3
71.1
69.5
72.4
Manual
67.1
67.2
66.2
73.9
Drone Combat
Maxent
70.3
77.7
73.2
76.7
AIRT.
90.1
90.7
92.3
93.8
PTIRL
52.5
63.7
65.1
78.3
Manual
65.5
67.4
69.5
76.5
Maxent
72.3
74.1
73.9
74.8
StarCraft II
AIRL
75.1
75.3
78.1
77.0
PTIRL
77.2
78.1
77.6
79.8
Manual
66.4
70.1
68.3
73.5
Montezuma's 's Revenge
Maxent
67.8
69.1
68.7
71.2
AIRT.
68.2
71.4
69.8
72.3
PTIRI
68.2
69.6
70.6
70.2
Manual
78.2
80.3
79.5
82.4
Maxent
82.3
86.8
79.5
89.8
Robomimic
AIRL
85.9
87.1
86.3
91.8
PTIRL
80.3
83.6
83.1
84.2
Manual
53.5
56.5
57.3
59.2
Maxent
57.8
59.1
53.9
60.2
MIMIC-IV
AIRL
56.5
60.7
57.6
63.3
PTIRL
58.9
61.4
60.3
60.9
15

---

Published in Transactions on Machine Learning Research (04/2025)
Across all domains, in step 1 and 2, fixed parameters are defined such that: m is the number of distinct agent policies; p is the number of trajectory sets per agent; and q is the number of trajectories per set in each IRL run (refer to Appendix A.pendix/C.6). In step 1, different agent behaviors are controlled by varying the agents' policies. In step 4, to train the classifier, grid-scarch is used to identify candidate values for h and y and twofold cross-validation (using Reraen) is used to optimize hypeer-araaeeerss based on accuracy. Since we assume potential shaping, Y is a hyperparameter as its value is unknown beforchand. To classify a reward function R& E Beest; we traverse reward functions R2 E Rerain, and compute the distance, DR R2) using the reward pseudometrics. We then identify the top k-closest rewards to Ra, and choose the label of the most frequent class. We select a training to test set ratio of 70 30, and repeat this experiment 200 times.
Table 1 summarizes experimental results. As shown, SRRD generally achieves higher accuracy compared to DIRECT, EPIC and DARD across all domains, indicating SRRD effectiveness at disccrning similaritics between rewards produced by the same agents, and differences between those generated by different agents. This trend more pronounced with manual rewards where SRRD significantly outperforms other baselines. This can be attributed to potential shaping, which is intentionally induced in manual rewards that SRRD is specialized to tackle. Therefore, SRRD proves to be more effective distance measure at classifying rewards subjected to potential shaping. For IRL-based rewards such as Maxent, AIRL, and PTIRL, while we assume potential shaping, non-potential shaping could be present. This explains the reduction in SRRD's performance gap over EPIC and DARD, as well as the few instances where EPIC and DARD outperform SRRD, though SRRD is still generally dominant. We also observe that all the pseudometrics tend to perform better on AIRL rewards compared to other IRL-based rewards. This result is likely due to the formulation of the AIRL algorithm, which is designed to effectively mitigate the effects of unwanted shaping in reward approximation (Fu et al., 2018), thus providing more consistent rewards. Overall, SRRD, EPIC, and DARD outperform DIRECT, emphasizing the importance of canonicalization at reducing the impact of shaping.
Simulations and Results:
To verify the validity of results, Welch's t-tests for unequal variances are conducted across all domain and reward type combinations, to test. the null hypotheses: (1) MSRRD S #DDRECT, (2) 1SRRD S μEPIC, and (3) MSRRDD S μDARD; against the alternative: (1) PSRRD > #DIRECT, (2) PSRRD > μEPIC, and (3) PSRRD > PDARD, where μ represents the sample mcan. We reject the null when the p-value < 0.05 (level of significance), and conclude that: (1) MSRRD > PDIRECT for all instances; (2) MSRRD > ('PIIC for 22 out of 28 instances, and (3) USSRDD > PDARD for 24 out of 28 instances. These tests are performed assuming normality as per central limit theorem, since the number of trials is 200. For additional details about the tests, refer to Appendix C.8 In summary, we conclude that SRRD is a more effective distance measure for classifying reward samples compared to its baselines.
6 Conclusion and Future Work
This paper introduces SRRD, a reward comparison pseudometric designed to address transition sparsity, a significant challenge encountered when comparing reward functions without high transition coverage. Con- ducted experiments, and theoretical analysis, demonstrate SRRD's superiority over state-of-the-at the-ttt---rtttte pseudo- metries, such as EPIC and DARD, under limited sampling and feasibility constraints. Additionally, SRRD proves effective as a distance measure for k-NN classification using reward functions to represent agent be- havior. This implies that SRRD can find higher similarities between reward functions generated by the same agent and higher differences between reward functions that are generated from different agents.
Most existing studies, including ours, have primarily focused on potential shaping, as it is the only additive shaping technique that guarantees policy invariance (Ng et al. 1999 Jenner et al. 2022). Future research should consider the effects of non-potential shaping on SRRD (see Appendix [.1] or random perturbations, as these might distort reward functions that would otherwise be similar. This could help to standardize and preprocess a wider range of rewards that might not necessarily be potentially shaped. Fut ure sludies should also explore applications of reward distance comparisons in scaling reward evaluations in IRL algorithms. For example, itcrative IRL approaches such as MaxentIRI, often perform policy learning to assess the quality of the updated reward in each training trial. Integrating direct reward comparison pseudometrics to determine if rewards are converging, could help to skip the policy learning steps, thereby speeding up IRL. Finally, the
16

---

Published in Transactions on Machine Learning Research (04/2025)
development of reward comparison metrics has primarily aimed to satisfy policy invariance. A promising area to examine in the future is multicriteria policy invariance, where invariance might be conditioned to different criteria. For example, in the context of reward functions in Large Language Models (LLMs), it might be important to compute reward distance pscudometrics that consider different criteria such as bias, safely, or reasoning, to advance interpretabiliy, which could be beneficial for applications such as reward fino-tuning and evaluation [Labbert al.) 2024
Acknowledgments
This research was funded part by the Air Force Office of Scientific Research Grant No. FA9550-20 1-0032, the Office of Naval Research Grant No. N00014-19-1-2211, and Fulbright- Fulbright-CAPESS, CAPES, Grant No. 01881.625406/2021-22 We thank the anonymous reviewers for their valuable suggestions, which helped to improve the paper.
References
Picter Abbecl and Andrew Y Ng. Apprenticeship Learning via Inverse Reinforcement Learning. In Proceed- ings of the Twenty-First International Conference Machine Learning, pp. 2004.
Rishabh Agarwal, Dale Schuurmans, and Mohammad Norouzi. An optimistic perspective on offline rein- forcement learning. In International conference on machine learning, pp. 104 104-114. PMLR, 2020.
Dario Amodei, Chris Olah, Jacob Steinhardt, Paul Christiano, John Schulman, and Dan Mané. Concrete problems in ai safety. arXiv preprint arXiv:166..00 16060666.0 2016.
Koul Amurag. Ma-gym: Collection of Multi-agent Environments based on OpenAl gym. https://github
com/koullanragg/aaataa 2019.
Saurabh Arora and Prashant Doshi. A Survey of Inverse Reinforcement Learning: Challenges, Method and Progress. Artificial Intelligence, 297(1), 2021.
Monica Babes, Enrique Munoz de Cote, and Michael Littman. Social Reward Shaping in the Prisoner's Dilemma (Short Paper). In Proc. of 7th Int. Conf. on Autonomous Agents and Multiagent Systems (AAMAS), 2008.
Xiaocong Chen, Siyu Wang, Julian McAuley, Dietmar Jannach, and Lina Yao. On the opportunities and challenges of offline reinforcement learning for recommender systems. ACM Transactions on Information Systems, -266) 2024.
Ching-An Cheng, Andrey Kolobov, and Adith Swaminathan. Heuristic-guided Reinforcement Learning. In Advances in Neural Information Processing Systems, volume 34, 2021.
Paul Christiano, Jan Leike, Tom B. Brown, Miljan Martic, Shane Legg, and Dario Amodci. Deep Rein- forcement Learning from Human Preferences. Advances in Neural Information Processing Systems, 30, 2017.
Justin Fu, Katie Luo, and Sergey Levine. Learning Robust Rewards with Adverserial Inverse Reinforcement Learning. In International Conference on Learning Representations, 2018.
Yang Gao and Francesca Toni. Potential Based Reward Shaping for Hierarchical Reinforcement Learning. Fourth International Joint Conference on Artificial Intelligence, 2015.
Adam Gleave, Michael Dennis, Shane Legg, Stuart Russell, and Jan Leike. Quantifying Differences In Reward Functions. In International Conference on Learning Representations, 2021.
Adam Gleave, Mohammad Taufceque, Juan Rocamonde, Erik Jenner, Steven Wang, Sam Toyer, Maxim- ilian Ernestus, Nora Belrose, Scott Emmons, and Stuart Russell. Imitation: Clean imitation learning implementations. arXiv:2211.119722 [cs.LG),, 2022. URL https:://taaatt
17

---

Published in Transactions on Machine Learning Research (04/2025)
Abhishek Gupta, Aldo Pacchiano, Yuexiang Zhai, Sham Kakade, and Sergey Levine. Unpacking Reward Shaping: Understanding the Benefits of Reward Engineering on Sample Complexity. In Advances in Newral Information Processing Systems, volume 35, 2022.
Yujing Hu, Weixun Wang, Hangtian Jia, Yixiang Wang, Yingfeng Chen, Jianye Hao, Feng Wu, and Changjic Fan. Learning to Utilize Shaping Rewards: A New Approach of Reward Shaping. In Advonces in Neural Information Processing Systems, volume 33, 2020.
Erik Jenner and Adam Gleave. Preprocessing Reward Functions for Interpretability. arXiv:2203.13533, 2022.
preprint
Erik Jenner, Herke van Hoof, and Adam Gleave. Calculus on MDPs: Potential Shaping as Gradient. preprint arXiv:2208.09570, 2022.
Alistair EW Johnson, Lucas Bulgarelli, Lu Shen, Alvin Gayles, Ayad Shammout, Steven Horng, Tom J Pollard, Sicheng Hao, Benjamin Moody, Brian Gow, et al. Mimic-iv, a freely accessible electronic health record datasot. Scientific data, 10(1):1, 2023.
Vitaly Kurin, Sebastian Nowozin, Katja Hofmann, Lucas Beyer, and Bastian Leibe. he atari grand challenge dataset. In arviv preprint arXiv: 705. 10998, 2017.
Nathan Lambert, Valentina Pyatkin, Jacob Morrison, I.J Miranda, Bill Yuchen Lin, Khyathi Chandu, Nouha Dziri, Sachin Kumar, Tom Zick, Yejin Choi, et al. Rewardbench: Evaluating reward models for language modeling. arXiv preprint wrXiv22403.1898" 2024.
Guillaume Lample and Devendra Singh Chaplot. Playing FPS Games with Deep Reinforcement Learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017.
Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tutorial, review, and perspectives on open problems. arXiv preprint arXiv:2005.0166 2020.
Yudong Luo, Oliver Schulte, and Pascal Poupart. Inverse Reinforcement Learning for Team Sports: Valuing Actions and Players. In Proceedings of the Twenty-Ninlh International Joinl. Conference on Arlificial Intelligence (IJCAT-20), 2020.
Saaduddin Mahmud, Saisubramanian Sandhya, and Zilberstein Shlomo. Explanation Reward Align- ment. In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, pp. 473 482,, 2023.
Ajay Mandlekar, Danfei Xu, Josiah Wong, Soroush Nasiriany, Chen Wang, Rohun Kulkarni, Li Fei-Fei Silvio Savarese, Yuke Zhu, and Roberto Martín-Martin. What matters in learning from offline human demonstrations for robot manipulation. In arXiv preprint orXiv:2108. 03298, 2021.
Maja J Mataric. Reward Functions for Accelerated Learning. Machine Learning Proceedings 1994, pp. pp. 181 189, 1994. doi: http:://abi.og///..00/////ss 1-00:///0000001111--000000555550 sciencedirect. httpa///s.aataarrrrraaaaaaaaaaaa
URI. https://www.
Andrew Y Ng and Stuart Russell. Algorithms for Inverse Reinforcement Learning. In International Confer-
ence on Machine Learning (ICML), volume 2, 2000.
Andrew Y. Ng, Daishi Harada, and Stuart Russell. Policy Invariance under Reward Transformations: Theory and Application to Reward Shaping. In International Conference on Machine Learning, pp. 278-287, 1999.
Jette Randlov and Preben Alstrøm. Learning to Drive a Bicycle Using Reinforcement Learning and Shaping. International Conference on Machine Leaning, volume 98, 1998.
Jacob Russell and Eugene Santos. Explaining Reward Functions in Markov Decision Processes. In The Thirty-Second International Flairs Conference, 2019.
18

---

Published in Transactions on Machine Learning Research (04/2025)
Eugene Santos and Clement Nyanhongo. A Mantextual-Basel Framework for Opinion Formation. In The Therty-Second International Flairs Conference, 2019.
Eugene Santos, Clement Nyanhongo, Hien Nguyen, Keum Joo Kim, and Gregory Hyde. Contextual Evalua- tion of Human-Machine Team Ffffectiveness. Systems Engineering and Artificial Intelligence, pp. 283 307, 2021.
David Silver, Satinder Singh, Doina Precup, and Richard Sutton. Reward Enough. Artificial Intelligence, 299, 2021.
Satinder Singh, Richard Lewis, and Andrew G Barto. Where Do Rewards Come From. In Proceedings of the Annual Conference of the Cognilive Science Sociely, pp- pp. 2601 2606. Cognitive Science Sociely, 2009.
Joar Max Viktor Skalse, Lucy Farnik, Sumeet Ramesh Motwani, Erik Jenner, Adam Gleave, and Alessandro Abate. Stare: A general framework for quantifying differences between reward functions. In The Twelfth International Conference on Learning Representations, 2024.
Halit Bener Suay, Tim Brys, Matthew E. Taylor, and Sonia Chernova. Learning from Demonstration for Shaping through Inverse Reinforcement Learning. In Proceedings of the 2016 International Conference Aulonomous Agents Mulliagent Systems, pp. 429 437, 2016.
Richard S Sutton and Andrew G Barto. Reinforcement Leurning: An Introduction. MIT Press, 2018
Ana CenorioGonzalez, Eduardo F. Morales, and Luis Cillasnoor-inedaa Dynamic Reward Shaping: Training a Robot by Voice. In Advances in Artificial Intelligence IBERAMIA 2010, pp. 483 492, 2010.
Garrett Thomas, Yuping Luo, and Tengyu Ma. Safe reinforcement learning by imagining the near future. Advances in Newral Information Processing Systems, 34:13859-133 13869, 2021.
Oriol Vinyals, Igor Babuschkin, Wojciech M. Czarnecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung, David H. Choi, T. Ewalds R. Powell, and J. Oh P. Georgiev. Grandmaster Level in StarCraft II using Multi-agent Reinforcement Learning. Nature, 575:350-355 354,, 2019.
Eric Wiewiora, Garrison Cottrell, and Charles Elkan. Principled Methods for Advising Reinforcement Learn- ing Agents. In Proceedings of the 20th International Conference on Machine Learning, pp. 792 799, 2003.
Blake Wulfe, Logan Michael Ellis, Jean Mercat, Rowan Thomas McAllister, and Adrien Gaidon. Dynamics- Aware Comparison of Learned Reward Functions. In International Conference on Learning Representations (ICLRR) 2022.
Chen Yanai, Adir Solomon, Gilad Katz, Bracha Shapira, and Lior Rokach. Q-ball: Modeling basketball games using deep reinforcement. learning. In Proceedings of the AAAT Conference on Artificial Intelligence, volume 36, pp. 8806-8813, 2022.
Tom Zahavy, Brendan O'Donoghue, Guillaume Desjardins, and Satinder Singh. Reward is Enough for Convex MDPs. In Advances in Neural Information Processing Systems, volume 34, 2021.
Brian D. Ziebart, Andrew Maas, J.Andrew Bagnell, and Anind K. Dey. Maximum Entropy Inverse Rein- forcmeent Learning. In Association for the Advancement of Artificial Intelligence (AAAT), volume 8, pp. 1433 1438, 2008.
19

---

Published in Transactions on Machine Learning Research (04/2025)
A Derivations, Theorems and Proofs
A.1 Sample-Based Approximations
While the EPIC, DARD, and SRRD pseudometrics can be computed exactly small environments, doing so in environments with large or infinite state-action spaces is generally infeasible because it requires eval- uating rewards for all possible transitions. To address this computational barrier, we adopt samplo-basod approximations for scalability. Specifically, we employ the double-batch sampling technique introduced by Gleave et. al. (2021) to estimate CEPIC and was later applied by Wulfe et al. (2022) to approximate CDARD- This technique uses two separate batches of samples: Bv, a set of Nv transitions; and BM, a set of NM state-action pairs that are sampled from the joint state-action space. To ensure consistency across the three pseudometrics, we extend the double-batch sampling approach to estimate CSNRD. The resulting sample-based approximations used in this paper are defined as follows:
Definition 6. (Sample-bused EPIC) Given a botch By of Ny samples from the coverage distribution D, and a batch BM of NM samples from the joint state and action distributions, D3 x DA. For each (s,a, s') E Bv, the cononically shaped reward is approzimated by taking the mean over BM:
(E)Ic(R)(s,a,55) R(s,a,
T
Σ
R(sl,u,))
Σ
R(s, u.
NM (sy
NM (a
(16)
Σ E
R(x, u,,')
No
(a.))EBM (2/
Definition 7. (Sample-based DARD) Given a batch By of Nv samples from the coverage distribution D, and a batch BM of NM samples from the joint state and action distributions, Ds x DA- For each (s, a, s') transition in By, we derive sets X', X" S. BMs where, |X*| N' and |X"| N". Here, for the set X' = [(x', u)), x' denotes the subsequent states for transitions starting from 8; and in X" {("", ")}, x" denotes subsequent states for transitions starting from 8', such that:
(D(Rn(R)(s,,,5))) = R(s,a,8),
Σ
1
Σ (x("))X
R(s, u.)
N
N
(a",
Σ
Σ
A(d'uux²)
(17)
N'
(x,,) (a" (a)E""
Definition 8. (Sample-based SRRD) Given set of transitions By from reward sample, let Bys be batch of Nar slate-action puirs sampled from the explored slates and uctions. From BM, derive sels X; C BM, for E [l,...,6] 6). Each X4 is a set, {(z, w)}, where x is a state and u is an action. The magnitude, |xal = N,. We define X3 = {Ixs u)}, where I3 denotes all initial states for all transitions; X4= ((xa, b)}, where I4 denotes all subsequent stales for all transilions. For each (s, s') transition in By, we define X1 = {211 u)}, where æn denotes subsequent states for transitions starting from s'; X2 = {(122 u)]; where 22 denotes non-terminal subsequent states for transitions starting from s; Xs5 {(x,,, u)}, where I6 denotes subsequent states X1; and X6 {(za, u)}, where Is denotes subsequent states to X2- For each (s, a') in By:
CSRRD(R) R(s,a,8') N
Σ (en,))Xx
1
Σ
R(s, x2)
N₂
72
7
Σ
Σ
R(xa, u, + Ni
Σ
Σ
R(II u.
NgN4
(x).u)e Na (xx
(xI.))Ex, (xS:)eXs
(18)
7
Σ
Σ
R( vo) + N₂
Σ
R(a3, xe)
N₂No
(x2,M)e X2 (mer)EX;
( (x
722
Σ
Σ
(,
N₂N;
(x (xx
20

---

Published in Transactions on Machine Learning Research (04/2025)
In each approximation, each term estimates the corresponding term in the original formula. For example, in ČSAND, NgN, Llasaiex, L(m,))xx, R(23, u,,44) estimates - A, A,)4) and x ajy, R(s', 1,) estimates "E[R(s', A,)) These approximations utilize two batches: By con- taining Ny transitions and BM containing NM state-action pairs, to canonicalize rewards in By. Each transition in By is canonicalized using state-action pairs in BM- Depending on how Bм is sampled (usually uniformly); it can help reduce bias from the sampling policy used to generate Bv, by including state-action pairs that may not be present in By: thereby providing a better representation of the entire state-action space, As a result, Bм can help to provide broader coverage, and reduce bias and variance in results, using relatively fewer state-action pairs compared enumerating all possible combinations. In the original ČEPIe, and Cdard approximations, it's unclear how duplicates would be handled. In our experiments, we implement all batches as sets, thereby removing duplicates to further reduce sampling bias.
A.2 Relative Shaping Error Comparisons
This section provides the proof for Theorem ! which compares the upper bounds of the relative shaping errors for ČSARD, ČDard, and ČEPIC- We organize the presentation follows:
Discuss the motivation for the relative shaping errors in quantifying the variation in the residual shaping normalized by the upper bound base (unshaped) canonical rewards (Appendix A.2.1
2. Proof of Theorem [Appendix A.2.2
A.2.1 Motivation for the Relative Shaping Error (RSE) Measure
Consider the task of comparing two equivalent reward samples, Ri and R2 which induce similar policies, share the same set of transitions B, but may differ due to potential shaping. To compare the reward samples, we first eliminate shaping by applying a sample- based canonicalization method, Čs. After canonicalization, compute the Pearson distance to quantify the difference between the canonical rewards as:
-1
(19)
where p is the Pearson correlation. Since RG and R2 are assumed to have the same set of transitions, and only differ due to potential shaping, after canonicalization we have:
Cs(RK)) = Cs(Ri) + OR. = =Cs(R) + ÓR
(s(RR)) = (R2) + OR, = CCs(R) + ΦR
where on, and on, are residual shaping terms, and (R) is the base canonical reward, which is similar between the reward samples since the sets of explored transitions are similar hence, Cs(Ri) (R() Cs( When computing D, (Equation 199. the Pearson correlation can thus be expressed as:
(CCs(R)), pCCs(R) on. Cs(R))+nn))
+ dna).
(20)
Analyzing Equation 20
When | << [Rs( for all i {1,2} then C(Cs( = P(Cs(R), CR()) = 1, since
the residual shaping terms have negligible impact. Conversely, when either |øn, >> (R) or |ona >> (R)), then the Pearson correlation is predominantly influenced by the residual shaping terms, and p can become low or even negative, especially when dR, and ΦR, differ significantly
Since (R) is the same across (R)) and Cs(R)), variations in the Pearson correlation can be primarily attributed to variations in the residual shaping lerms.
We assume that the reward samples under comparison equivalent (in of optimal policies) and share the same transitions, simplify our analysis by isolating the differences between the reward samples potential shaping.
21

---

Published in Transactions on Machine Learning Research (04/2025)
To assess the impact of residual shaping, it is essential to also consider the magnitude Cs(R) normalizing factor. Ti [Cs( is significantly larger than the residual shaping terms, the influence of the shaping terms diminishes, resulting in a higher Pearson correlation closer to 1. Conversely, [R)( is significantly smaller than the residual shaping terms, these shaping terms will have a higher influence on the correlation, polentially reducing it.
To generalize these insights, let's consider the canonicalization task on a reward sample It' such that:
Cs(Rt') Cs(R) + O
(21)
To quantify the influence of the residual shaping term ΦR relative to the base canonical reward Cs()),, let's establish the Relative Shaping Error (RSE) as follows:
løn(s,
(R((s,,,5)
(IS((S(()(Ss,,5')) = (((ssR)(
(22)
nZ
A low RSE indicates that U(Cs(R)(s, a, 8)) is substantially large relative to ( a, 8'),, suggesting that the residual shaping has minimal impact on Dp- Conversely, high RSE implies that small relative to (ØR(s, a, s highlighting a more significant influence of residual shaping. By normalizing with the upper bound of the RSE, we obtain a conservative measure to quantify the impact of shaping in extreme scenarios. This formulation helps assess the robustness of reward canonicalization methods mitigating shaping effects during reward comparisons. From Equation 21 suppose we can express:
a,) is
Cs(R)(s,a, = (s) + Kn: a = @2(5, + K
where Kn and K2 are constants that do not vary with (s, a, s'), and dn is the effective residual shaping. When comparing reward samples R₁ and R2, in computing Dp: the constants Ka and Kş do not affect the Pearson correlation since it is shift invariant. Therefore:
(C))(R))Cs((E)) ((Cs(RI)) + ΦR. Cs() + +Ra)
= ((C) + KR, + + + K ( + Kn, + +Rū + Kaa))
= p(C)(BR) + +R. Os(R) 2R.)
(23)
Relating this to the RSE in Equation 22 note that |Φll serves as a measure of reward variation due shaping, and UR))(R)) acts as normalizing term. For the term on. we can omit K3 to get:
6R = ΦR K
(24)
since, K3 does not affect the variation in the Pearson correlation. However, for the denominator U(Cs(R)) cannot omit KR (hence no change to the denominator) because the denominator serves to normalize the residual shaping. When KR is large, even though it does not affect the Pearson correlation, it lowers the impact of l and vice versa. This leads to the final RSE equation below:
1dn(s,a,')) 10,[s, a, a') nZ
RSF((C((R((s
(25)
U((s(R)(s.a,5')
A.2.2 Proof of Theorem 1
Theorem aims to compare the upper bounds of the RSEs for ČEPIC ČDARD and ĆSRRD.
Proof. Assuming finite reward sample that spans state space S and an action space AD, where D is the coverage distribution. The following subsets are defined: for ČErIC, S C 5 and S' C S for ČDaRD. S" C 5D and S' C SP; and for ČSRRD, each S; S 5 where i E (l,..., 6}. Let's define:
M max ()(s)))
SES
22

---

Published in Transactions on Machine Learning Research (04/2025)
the maximum absolute shaping for states in SP, where M R. Then, for all shaping expectations:
B[o(5)]1 S M, E[o(S') S M, E[o(5") S M, and E[((S))I S M for all iE (1...,,66) .6.
In the following analysis, we impose the assumption that unsampled forward transitions are negligible, based on the rationale that. forward transitions are generally consistent, or in-distribution with the transition dynamics of reward samples, compared to non-forward transitions which have a higher chance of being out-of-distribution with respect to the reward samples' transition dynamics. For the analysis, find the upper bound of the RSEs under different scenarios of transition sparsity from the best case (no unsampled transitions) to the worst case (high levels of unsampled non-forward transitions).
Analysis of EPIC:
Considering Equation 2 for CEPIC, the transitions (5, A,, are forward transitions since by definition, S' is created based on (S, A). However, the transitions: (s, S") and (s', S") are non-forward transitions since S" is not created based (s, A) or (s', A), but (S, A). Since we only have unsampled non-forward transitions, let the fraction of randomly sampled transitions in (s', S") and A,) be u and respectively, where 0 S < 1. Note that and vary based on (s, s'); however, for visual clarity, we will denote them as u and v. Incorporating a and v into CEPIC:
ČEPIC (R),,( R(s, a, s') + EluyR(s', (, - -))
(26)
Applying ČEPIC (Equation 26 to a shaped reward R' a, 8'), we get the residual shaping:
Depic = (T ( + (u - 1))(s) + [[(+ - (0())) ((76(()) - E(yvv((S))
(27)
Best Case: In this scenario there are no unsampled transitions such that: u, v 1. Applying u, into Equation 27 we get: Pepic = [[}(()) E
In ČEPIC, all transitions are canonicalized using the same state subsets and S" such that the shaping terms ((S) and ((S') do not vary with changes in (s,a,s)). Therefore, in depies the constant K3 E[rΦ(S)] TE [[))(S")) does not vary with changes in (,,,,s), and based on Equation 24 Depie = 0, such that:
RSE(CEPIO(RR) = O.
Average Case: In this scenario, < u, v < 1. From Depio (Equation 27 we can extract the constant term
K3 =Bhh2d(')) + E[ro(S)), which does not vary with (s, s'). Therefore, the effective residual shaping (see Equation 24 is given by:
b Pepic = (() + (u
1)0(s) =U)()=-oo))((""), r)))
(28)
such that:
S (7 - --
+ - -====")lE((((""
$ M(7 1 1 ru))
(since M = max ()())). EES
< M(2 - u + w))
(whon =
< 2M
ÓEPIC has four reward terms. Following Definition ((C) = 4Z, hence:
From Equation 26
2 the upper bound of ČEPIC(R) is
2MM
M
(SE(CEPio(R)) = U(CErIC(R))
< 47
27
Worst Case: this scenario, u, v = 0. Applying u and into ČEPIC (Equation 26 we get:
CEPIC(R)(s,a, s') R(s, s') A,,),,
(29)
23

---

Published in Transactions on Machine Learning Research (04/2025)
and Pepic 70(5') ((s) ((5) + B[))
Since S and S' are the same across all transitions, K ([S)) + (((r(S)) is constant, hence, Pepie ro(8') ((s) such that:
eeppel S (r((s)) +(- S 7M M 2M
From Equation 29 ČEPIC has two reward terms. Following Definition
2
U(CEPIC(RR) = =2Z, hence:
1pppel
M
RSF(CEric(R)) U(CEPIC(R))
S Z
:. Based on all the three cases, we have:
RSE(CEric(R)) $ M
(30)
Analysis of DARD:
Considering Equation 6 for CDARd, the state subset S" is subsequent to s', and S' is subsequent to 8. For approximations, the transitions (S", A, S") are non-forward transitions since S" is created based on (s', rather than (S', A). Let the fraction of randomly sampled transitions (S', S") ) be w, where S w Note that also depends on (s, a, s'); however, for visual clarity we denote as simply w. Incorporating w into ÖDARD:
(DARD(R)(s,,, 8') R(s, a, RER R(s, A,S, wy Wy A, S,)),,
(31)
Applying ČDARD to shaped reward R', we get the residual shaping:
Ødard Bi( wy "O(")" + (wy {))(5")
(32)
Best Case: In this scenario, w = 1, such that Joderall = O, hence, RSE(CDARD) = 0. Average Case: For this scenario, 0 < w < 1: Jodaral S (7² w E[d((")] (7 w=) < - + (7- wy)M 2M
In ČDard: the state subsets and S" vary due to (s, a, s'); hence, K' 0. Following Definition and applying it to OAARD (Equation 31 ((CDARD(R)) = 42, such that:
Iddaral RSF((DAAD(RR)+ U(CDARD(R))
2M M
47
27
Worst Case: In this scenario, = 0, hence we eliminate terms with w in Equation 31 get:
(RAnn(R)(s,a,)) = R(s, 8') + ElyM(s', A,S") - A(s,),)))
(33)
which corresponds to: Ødard = E(7 + ( such that:
[danaal < <E(>" | [E 1 |7 2M
Following Definition 2 and applying it to ÒDARD (Equation
33
U(CDARD( (R)) = 32, such that:
Iihaardl
2M
(SE(CDARD(R)) U(CDARD(R))
32
:. Based on all the three cases, we have:
2M
(SB(CDARD(B)) <
(34)
37
24

---

Published in Transactions on Machine Learning Research (04/2025)
Analysis of SRRD
Considering OSARD in Definition D the first six reward terms are forward transitions, since for each set of transitions A, Sj), Sj is distributed conditionally based on (S;, The last two terms violate this condition; hence, they are non-forward transitions. As mentioned in Section SRRD is designed such that:
Transitions A,,, Ss) S A,
Since S1 are subsoquent states to s', and S4 are subsequent states for all sampled transitions. It follows that S S4, hence, A, (S4, A,).).
Transitions (,,, S A,
S2 is the of non-terminal subsoquent states s. Since S3 encompasses all initial states from all sampled transitions, it follows that S2 C S3, hence, (S2, A,,)) C (S3, A, St).
For ÖSRRd, let the fraction of the randomly sampled transitions for A, and (S,, Ss) be p and q. respectively. Considering that the number of unsampled forward transitions are negligible, we establish minimal thresholds m,, m2 > 0 such that: -= my when (S4, A,Ss) only contains sampled transitions from A,,,A,55) and q = m2 when A, mi S p S and m2 s q S 1. Note that p and q vary based on (s, a, 5'), but for visual clarity, we express them as p and q. Incorporating p and q, we get:
only contains sampled transitions from A,, Sg). Therefore:
(RRRD(B)(s500,6) = R(s, a, 8)) E[7R(ss, A,Si) - R(s, A, S2) - RR(S,, A,S.) + R(S). S, -7R(S2, S6) + R7 A, S6) 1ri² m72 S.))
(35)
Applying ESAnD (Equation 35 to shaped reward R'(s,, s'), we get the residual shaping:
Parrd E[(r (S3)) - - + (7 poS) + (g7² (()))
(36)
Best Case: In this scenario there are no unsampled transitions such that: p.q = 1. Applying and q into Equation 36 we get: Øerrd = 0, hence, RSF(CSRRD) RR)) =
Average Case: In this scenario, mi <p< < 1 and m2 <9 < Note that in ČSRRD, Sa and S4 are the same for all transitions, since S3 encompasses all initial states, and S₁ includes all subsequent states to Sg. Therefore, ((Ss) and (SS4) do not vary with (s, s').. From @arrd (Equation 36), we can extract the constant - ())))) Based on Equation 24 the effective residual shaping is given by:
K -
Daird E(-9yd((s) (SA)) + (73 (o(S)) (g7 (S))
such that:
S
(
< M(97 + +23 +77 -
< M(atp+1-pt1-0
(when = 1)
< 2M
Since ČSRRD has terms, following Definition 3 and applying it to Equation 35 Therefore:
we get U(CSRRD = 87,
1dsiral
M
RSE(CsnnD(RR) ((CSRRD(R))
4Z
Worst Case: In this scenario, p m (when (S4, A, Ss) only has sampled transitions from (S1, A,)) A, and q m2 (when (S,, A, So) only has sampled transitions from AS,, So)). Consider situation where
(Sa,, A, St)] >> (Si A, and (S5,, A, Sa)l >> (S2, A, Sa)), such that: + 0 and my + 0. Therefore:
(R)RD(R(ss,a = R(s,a,s)) E/ A,S R(s, A, 7R(S, A, S4) (R,
7,, So)]
337)
25

---

Published in Transactions on Machine Learning Research (04/2025)
with the corresponding residual shaping:
Porrd z - P
(38)
From Darra (Equation 38 we can extract the constant K3 = Blr - (24( since it does not vary
with (s, a, s'). Therefore, the effective residual shaping is given by:
① srird ~ El - {
hence:
serrall S 7 ( (00((5))l+++111111 +
| 2 22
Following Definition 2 and applying it to ÓSRRD (Equation
37
U(CSRRD(R) (R)) 6Z, such that:
10 sird
M
RSE((snan(RR))
$
U(CSRRD(R)
3Z
:. Based on all the three cases, we have:
M
RSE((SRRD(R)) S 3Z
(39)
Conclusion
Based on the upper bounds of the RSE values aggregated from the best, average and worst scenarios we conclude that:
of transition sparsity (Equation 39
34
30
M
2M 37'
RSE(CEPIC) S M Z
RSE(CsRRD)
<
RSE(CDARD)
32'
The RSE serves as a thcorctical measure to evaluate the robustness of the psoudometrics by quantifying the influence residual shaping errors relative to the rewards. It's important to acknowledge that the RSE is a conservative measure, since the residual shaping is normalized by (R)) Therefore, practice, it may not guarantee the order of performance predicted in Theorem as the impact of residual shaping could be more pronounced when normalized by smaller reward values. Despite this limitation, the RSE still offers meaningful theoretical measure the robustness of the pseudometrics.
A.3 Residual Shaping
Derivation of prest:
Applying C₁ (Equation 7 shaped reward (', = s7)(())))) ((8):
= 1'(s,, a, - (,
= +0
- [BBB445555--4433310000--22232163
= =C,(R) a, + - + 76((2))
Hence, (R))ss,,, a, yields the residual shaping:
drest Eh"d(S1) ()s)) (5())) ~
26

---

Published in Transactions on Machine Learning Research (04/2025)
Derivation of Gres2:
Applying C2 (Equation 9
to shaped reward R'(s,a,s') +0((s) o(s):
+ 3403::3--55411333-0000000----333 d(s'))
-1011,1555)1---3333---0000011110 -(Ss))
70(k2) d(2))
A, (kk)) - A,
Ak) + ((s)))
= =c((R)(8, B ((k)) - 7 + +kk)) - (k2)
Hence, C2(It)s,,,, a, 8') yields the residual shaping:
Pres2 = ((1)) - - (kaa) + 72 (
A.4 The Sparsity Resilient Canonically Shaped Reward is Invariant to Shaping
Proposition 1 (The Sparsity Resilient Canonically Shaped Reward is Invariant to Shaping) Let R S x x S be reward function and S + R be state potential function. Applying CSnRD to po- tentially shaped reward R((s,,,s') R(s,a,8)) + rō(s') - -(s) satisfies: CSRRD(R) = CsRRD(
Proof. Lot's apply CSNRD, Definition to a shaped reward R'(s, = a, +7)))()))))))))))) +) ((8):
CSRRD(H') a, = +)0()) (0000000000000000------14-----)-
-
[R(s, A. -1h- x(S3)
x - ((2))
+ +7|1((3, A, + 76(6)) - (o((5) -SS))]
Regrouping the reward terms and the potentials, this reduces to:
= CsRnd (-
+ +4777(0011--100111-------6666663 + ++
Since [[/d((5)) = 70'6s) and B[p(s)) (bs), this leads to:
(H's, (s
A.5 Invariance under the Sample-Bass Based SRRD Approximation
For the sample-based SRRD canonical reward (Definition 8 under transition sparsity, rewards may
be undelined since the associated transitions may be unsampled. However, when all the necessary rewards are defined, policy invariance can be achieved. To show this, we will first derive Lemma [ then present the proof that assumes all the necessary rewards are available.
Lemma 1. Let o: S + RR be a potential function. Given states D4 and x, E S, then:
13
72
n2 o(x)).
(70(Z)) ((x;))
b(xz))
Σ
T12
27

---

Published in Transactions on Machine Learning Research (04/2025)
Proof.
n1 12
n2
(To(2;) o(0;)) T2
o(xi)
Σ
o (xxz))
T2 712
:=1 j=1
Notice that (xx;) is independent of j and obT;) is independent of i, thus,
n20(2;))
ni m1)(zz)
111
==1
22 1
b(zz) j=1
74
t=1 n2
Proposition 2. Given transition sets (S,, S3) needed to compute each reward expectation term in ČSRRD, if the transitions fully cover the cross-product S; A Sj, then for a shaped reward R' R'(s, a, R(s, a, s rols') (()), the sample-based SRRD approcimation is inveriant to shaping.
AxSs,
Proof.
R(s,a,5)
+ 70(s') Φ(s)
+
Σ
[R(s',u, + (0(x1) -((5)] N₂
Σ
[R(s, x2) + +70(22) 6(s)
Ni
(#1.))ex,
(#2.0)EX2
?
Σ
Σ
[M(23, u, x4) + 70(xx) - ((x))
NaN4
(aa, (#aa)EX,
n²
Σ
Σ
[R(a1, 25) + + ((a1))
N
(m (#s:)eX,
Σ
Σ
[R(22, u.) + 76(()) ((22)
No
(x2, (x
+ NgNo
Σ
Σ
[R(23, u. 26 + 7 ((xs)l
(xa (e
72
Σ
Σ
[R(a, u,z5) 4,) r ((xa))-
N4
(x4,))EX;
(x5:)EXx
Rearranging terms, the above equation can be written as:
(SRRD(P))ss as,,' CERRD(R)(s, + d residuals:
where:
= o(s) + 7
Σ hδ(x1) o(s')]
Σ hΦ((2)) - o(s)
N1
N₂
7
Σ
Σ
(rd(2a) - ((xa))
72
Σ
Σ
(To(15) ((21)]
N4
N1
(*a, Na (xx
(*1.))eX, X1 (N
(40)
Σ
Σ
hro(xe) - -(x2)) +
Σ
Σ
(nd(xa) 6(za))
N₂No
N₂
( 2 (xx
(x (No
72
Σ
Σ
(ro(1s) - ((Ta))-
N
(x (xS
28

---

Published in Transactions on Machine Learning Research (04/2025)
Applying Lemma 1 to Equation 40 and simplifying terms, get:
?2
residuuls 70(ss) ((s)
Σ
[o(21)] -70(s')
Σ [d(x))] + 0(s)
Ni (mi,))Ex,
N2 (a2,w)EX2
72
7 Σ [o(x5)]
32
[o(xa)] 7
Σ [d(x3)] +
Σ
[d(x))]
N4
N3 (
Ns
N1
X4
(
(x1,))EX,
7
Σ [a(za)] +
Σ
[x(22) +
Σ [6(26)]
Σ [+(x3)]
N6
N2
No
N3
Xo
(xa,
(x
(aa,
7
[o(xs]] +
Σ [x(x))] =
N5 X
N4
(M..))EX4
Therefore: OSRRD = (RR
A.6 Example: SRRD State Definitions
Figure illustrates a transition graph from a reward sample with 10 states SP action A ={a]} }. This example illustrates how the sets {SI,..,, are defined in SRRD, along with their relationships: (SI C S4) and (S2 S 83), which contribute SRRD's robustness unsampled transitions.
{ #9 and a single
Figure 4: A transition graph with 10 states {Fo, ..,g and a single action {az}. State subsets are defined based the transition: (1))))
The Sparsity Resilient Canonically Shaped Reward is given by:
(Snnd(R)(s,a, s') = R(s,a, E/RR('',,,) A1) R(s, A, S2) - 7R(S 4,84) + R,,, 7R(S2, A, Sa) R(S,, 5.) ( 4,
where: S₁ subsequent states to s', and S2 are subsequent non-terminal states to S3 encompasses all initial states from all transitions; S4, Ss, and Sg are subsequent states to S3, Si and S2, respectively.
29

---

Published in Transactions on Machine Learning Research (04/2025)
Following the SRRD definition, the states in Figure 4 are defined as follows:
s: state 20-
8/: stale 21.
Si (subsequent to s'): (02, Je, #o,
S2 (subsequent non-terminal states to 8): 04,
S3 (initial states from all transitions): {Io, 22, 23, 17, terminal states øg and 2g not included
(subsequent states S3): (I1, (2, #3; 24 24, 23 Ts,
starting state zp included
Ss (subsequent states to S1): {I2, TA T6. 27)
So (subsequent states to S2): {I), 12, 33 44, 25, To, T8, Hn]
Transition Relationships (see Section 4 for reference)
1. S C S4, therefore, A,5)) A,
2. S2 C S3, therefore, (S2, S,) S (Sg, A, Se).
A.7 Pseudometric Equivalence Under Full Coverage
Proposition 3. Given the state subset S C S, the SRRD, DARD, and EPIC canonical rewards equivalent
under full coverage when: S S =... S6 for SRRD; = S' = S" for DARD, and S = S' for EPIC.
Proof.
(s),,, BB, - R(s, A, S') A,,,,
CDARD (s, (s, s') CSRRD (s, s') R(s,a,8') B(y A,8,) A(s,A,5,) 7R(S3, A,S,)
A,S") - A,S' (A,5"
+ R A, Ss) - RR(2,, A, + RR(S, A, - R Ss)]
Under full coverage, every state transitions to every S under every action A. Consequently, all relative subscts are equal: S S' = 5" - S S3 S4 S₃ Ss, such that:
CEPIC = CDARD = OSRRD = R(s, a, ( E(T A) - R(s, A, S) -RR(S, A, S)].
(41)
A.8 Repeated Canonicalization Under Full Coverage
Proposition
Given the state subset S S, under full coverage when: S S ... So for SRRD; S = S S" for DARD, and S S' for EPIC. Then: CSRRD, CEPIC, and CDARD connot be further canonicalized.
30

---

Published in Transactions on Machine Learning Research (04/2025)
Proof. From Proposition 3 we showed that under full coverage, C3 CEPIC CDARD CSRRD- Applying Os to canonicalize previously canonicalized reward we get:
+ , R(s, -
=
= Cs((R)(s,,,))
+ (/B/:RSSAA..))-EAASSS...... -(ss A.)) ]|]
R(S,A,5) S) 7R(S,
= =Cs(R)(s, +>E[R((s' - 445) A,),
-)EiR(S,, A, - -1 -
= Cs(R)(s,a,8)
A.9 Regret Bound
this section, we establish a regret bound in terms of the SRRD distance. The procedure for the analysis is adapted from the related work on EPIC by Gleave al. (2021). Given reward functions RA and Rø and their optimal policies x and By: show that the regret of using policy TB instead of policy # is bounded by function of DSHRD (RA, Rg). We also show that DSRRD(RA Ry) + 0, the regret approaches 0 suggesting that T TB. The concept of regret bounds is important it shows that differences in DSRRD reflect differences between the optimal policies induced by the input rewards.
For our analysis, we will use the following Lemmas:
Lemma 2. Let f E Rn be vector of real numbers and let fa E IR be subvector formed by selecting subsel of the entries of f. Then:
lIfall - 11f112
(42)
Proof. Suppose f has n clements and ft has elements. Since fi S f, every clement in fa is also in f. and S n. Therefore, 2 2 ESe such that: [|Ai[a S 11/1|2.
Lemma Let RA Rn S AXSS R be reward functions with corresponding oplimal policies T and T Let (t, St, a1,,,,444 S1+1) denote the distribution over trajectories that policy æ induces at time step t. Let a's, be the coverage distribution over transitions. Suppose that there crists some K > O such that KD(st, de, 8141) 2 Da(1, St, ac, St41) for all time sleps t E N, triples St, at 8t41 E S x A x S and policies m E (T).TB). Then the regret under RA from execuling n optimal for Ry instead of T is al most:
2K DL, (RA. RB)-
(T)) (T)) < 1-y
where DL is a pseudometric in L1 space, and GR(T) resembles the return of R under a policy n.
Proof. See Gleave al. 2021 Lemma A.11.
31

---

Published in Transactions on Machine Learning Research (04/2025)
Lemma 4. Let RA, Rg: S x x R be reward functions. Let n' and F be policies optimal for reward functions RA and RB- Suppose the regret under the slandordized reward RA from execuling TBB instead of A is upper bounded by some U E R:
GRg (T Ggg. (T S.
(43)
Assuming that Sx is identically distribrutdd to S4 in CSRND, then the regret is bounded by:
GRA (TA) GR (TT) S RAll2
(44)
Proof. Following Gleave et al. 2021 express the standardized reward as:
CSRRD (
R
(45)
[CsnnD (
In CSRRD (Equation 11g the states S and S5 depend on 8', while S2 and Sg depend on Assuming that Sq is identically distributed to S4, we can see that CSARD a potential function, where o(s')
E[R(s', A, Si)] + -RR(S), , A, S.) - -RR(S4, , A, St)], and ((s) = E[R(s, A,S2) + A, S6) -R((S,, A, S6)]
Therefore, CSRRD is simply shaped by some potential 4, such that:
(CSnno(R)(T) = GR(T)) - Beg [ss)]
Therefore, we can write:
1
Gns(TT [[CsRRD((B] G (CSRR((M(()) [CsRRD(R)]l (GR(T) Be (+)s)))
(46)
where, 8o depends only on the initial state distribution do; but not m. Applying Equation 46 o and xß:
GgS (TT² (TB) (Ra)ll (G (TB))
(47)
Combining Equation and
GRA (Tī) GR. (Th) S U|]CsnnD(Ra)lle
(48)
We now bound [[CRRRD (RA)ll in terms of |R |22 The SRRD canonical reward expressed as:
CsRRD(U[(ss,,,5) R(s, E| S,) - R(s, - A, + A. -R, A, Se) 7R(S,, ((S A, St)]
Now, using the triangular incquality rule on the L2 distance, and lincarity of expectation:
(R)sn,(R)(s,,,,) s') - |[[[s s ||2 + B/ R 1, l1) + R(s 4,52) + R(S,, S,
+ " R A, 11) >11 - R(S,, A, S6) + 4, 7 R(Sa Sb)
Using Lemma the L2 norm of each reward subspace such that:
|[R(S,, Sk)l12 ||R(S, A, S') ||
(49)
Therefore,
[CsnnD (R),,, S |
(50)
Combining Equation 50 and 48
we get:
GRA(TA) - GRA (FT) 80 |
32

---

Published in Transactions on Machine Learning Research (04/2025)
Lemma 5. Given reward function R: Rx8xAx5 - R, then: BICsnnD(R)(S.A,5)) = 0, if S and S' are idendically distribuled.
Proof. Applying the transitions (S,A, into CSRRD (Equation 11 8 St S S2 Ss Ss. and S = S3, such that:
(, = R(S, A,5" + B| A,5) - R(S, A, -
Therefore:
E (RC A")) = B|R(S, 44 E( (,,)) R(S, - RR(S,
if S is identically distributed to S" then E[R(S", A') = E[R(S, A, S")]. hence:
E[Csmo(()(SSA45') 4 E17 R(S, A, - -R(RS, = =0
Theorem 2. Let RA, RB S x Ax + IR be reward functions with respective optimal policies, T TB. Let y be discount factor, (x St. at 0t, St+1) the distribution over the transitions induced by policy æ at time L, and D(s, 8') be the coverage distribulion. Suppose there erists K > such that KD(st, Ut 8441) D= St, at, 8141) for all times t N, triples (st, at, $141) S Ax x S and policies π E AT BB). Then the regret under RA from executing TB instead of n is at most:
GRA (T(A -n (TT) & 32K
Ralla(1 | -1 Danao( RA RB),
where GR(z) the relurn of policy w under reward R.
Proof. Since CSRRD zero-mean centered for transition inputs (S, S') (see Lemma 5 from Gleave et al.
2021 [A.4), follows that:
DSRRD Rp) = (S,,,) - (S,
(51)
From Lemma A.10 Gleave et al. 2021 the I norm of a function is upper bounded by its T,2 norm on a probability space, such that:
(R, |
R (S, -.S.AA,)))
(S,
2D5RRDD (RA, RB).
(52)
Combining Lemina and Equation 52
G ORgano(T3) G GRgann (m))
2K
DL, RR
(RSRDD RSRRD) < (R
4K DSnnD (RA, Ra)-
(53)
1-9
Applying Lemma we get:
GRA(TR)~ - GRA -GaA(T)) < 32K RAllz
DSRRD (RA, Rg).
(54)
1-7
As shown, when DSRRD 0, the regret: Cn GR, (m1)
33

---

Published in Transactions on Machine Learning Research (04/2025)
A.10 Generalized SRRD Extensions
We derive generalized form of SRRD by recursively eliminating shaping residuals via higher-order terms.
1. To create SRRD, the first step is to adopt the desirable characteristics from both DARD and EPIC (refer to Section 4); and derive C1 as follows:
(s,))s = R(s, a, s') Bh A
C1 yields the residual shaping term: Øresl = -S) - (())( + -
2. To cancel Bl)(S.)), V, E {I,...,4) 4}, we add rewards ItSS, k;)) to induce potentials vo(k)) (SS), which results in C2:
C2 8)) = R(s,a,8) El S)) -
+72 A1 - A, (2)) + A, --)) - Ab
C2 yields the residual shaping: Φresz = [(h) - 7kk + -k]((k))]
3. To cancel [],, we add rewards R(K) A, k2)) to induce potentials ?p(k?) ((ki),, yielding C3:
C2(R)(s,,,,') R A, R(s, A,52 - R(Ss, A.
A, kg)) - (10)--p00 RR(S2, A, kb)
+ . - ( R(K,, A, A2) - R 1, -7² R( A, A,13)
O3 yields the residual shaping: 0rea3 = (07 (x)))) - **(()))
-
4. As we can see, this process results in the generalized formula:
C, 5 = R(s, a,s'),))))))))) E/TR(s', A, - R(s, A2 - R(Ss, S4)
2 R(S, A, A,1 - 72 A, + + A,K)) RR(S, 1,4))
+ R(K) A, k2) - -7² R² A, A, + A kg) 72 R(k) A 13)
x" R(K A, A, 7"h R(K
-7" 10 A,
--
--" R(k222 A,A, AAA
where, 2 3. Cn yields the residual shaping:
6n Eiy 11 ((KT-)))))))) -
(OK -( + (0"(k""k))))))) - "k=²
Looking 6n. increases, each residual shaping term is scaled by y", their contribution diminishes exponentially with n. Therefore, the upper bound magnitude of Φ significantly decreases since 0 < 7 < 1, and each [o(k:] < M, where M is the upper bound potential for all distributions k; C SD (see Appendix A.2.2 Therefore, as approaches infinity, Φn approaches 0.
The advantage of the gencralized SRRD form is that on approaches 0 as n increases. However, com- puting many k; sets makes the process expensive and difficult to implement in practice. Therefore, a smaller n is preferable. In SRRD, we choose n = 2, then use our intuition to select sets k,, which further reduce the residual shaping.
A.11 Computational Complexity
The pscudometrics discussed in this paper all utilize a double sampling method that uses the batches: By of Ny sampled transitions, and By of Na state-action pairs. The sample-based approximations for the methods have the following computational complexities:
34

---

Published in Transactions on Machine Learning Research (04/2025)
EPIC Complexity:
C) R(s, a, + + R, A. - -
For all transitions in Bv, approximating E A, S"]] from Bи takes approximately O(N))) com- plexity since we iterate Bas in a double loop (see Equation However, this expectation the same for all transitions, hence can be computed once.
For each transition (s, a, s') E Bv, the reward expectations, E[R(s', and A, can be approximated in one iteration through BM, resulting in O(NM) time complexity per transition. Since the computation varies based on as,a,s) s'), the overall complexity is O(NyNN)).
Therefore, the overall complexity for EPIC O(max(Ny NM)) When NM is significantly larger pared to Nv, the complexity is approximately O(N)), and if Ny is significantly larger relative to NM, the complexity is approximately O(Ny-MM).
DARD Complexity:
CDARD(R)(s,as5) 8') E[ A,") R(s, A,S") -R((S,,
For each transition (s, 8') By, the reward expectations, E A,S") and E[R(s, A, S') can be approximated through a single iteration of Ba, resulting O time complexity per transition. The reward expectation, E[R(S', A, s")) can be computed via double loop through BM, and it varies based on (s, s'), resulting in O(N2, time complexity per transition.
Therefore, the overall complexity for DARD is O(N
SRRD Complexity:
(ennn(R)(s.a,5))) R(s, a,), BRT A,51) R(s, RR(S3, A, + + R S3) - RR(2 S6) + +RR(S,, S, - --2 R(S, A, Sa)]]
For all transitions Bv, approximating E[R(S,, S.)] from By takes approximately O complexity since we iterate Ba in double loop (see Equation 18 However, this expectation is the same for all transitions, hence it can be computed once.
For each transition (s, 85) s') E By, the reward expectations, B[R(s', S1) and R[ S2)] can be approximated one iteration through BM, resulting in O(NM) time complexity per transition. The reward expectations, E E[R(S,, A, Ss)], B[R(S2, A, So)], E[R(S,, A, S6)] and E[R(S,, A, Ss)], all require double iterations through BM, and they vary based (s, a, s'), hence, they take O(N2) complexity per transition.
Therefore, the overall complexity for SRRD is OLNv
B Additional Considerations
B.1 Deviations from Potential Shaping
Reward comparison pseudometrics are generally designed to eliminate potential shaping, and in this study, we examine how deviations from potential shaping can affect the performance of these pseudometrics. Within a 20 Gridworld domain, we generate a ground truth (GT) polynomial reward function and a corresponding shaped reward function (SH), both with full coverage (100% transitions). From GT and SH, we sample rewards R and R' using uniform policy rollovers. For both samples, add additional noise, N, with the
35

---

Published in Transactions on Machine Learning Research (04/2025)
DIRECT
SRRD
EPIC
DARD
(a)
(b)
(c)
N = 0
[ S max((R'))
M 5
0.6
0.6
0.6
0.4
0.4
0.4
0.2
0.2
0.2
0.0
20
40
60
80
100
0.0
0
20
40
60
80
100
0.0
20
40
60
80
100
coverage (%)
coverage (%)
coverage (%)
Figure 5: (Non-Potential Shaping Effects): As the severity of randomly generated noise increases from part (a) to (c), rewards deviate more from potential shaping, hence, all the pseudometrics degrade in performance. In the end (part (c)), the pseudometrics perform similarly to DIRECT, showing that canonicalization does not yield any additional advantages when the rewards significantly deviate from potential shaping.
N 0, Mild: [ S max(( )) and High: |N] S 5 max( R'),, where N is randomly generated from a uniform distribution within bounds defined by the severity levels. Thus, the updated shaped reward is given by:
following severity levels: None:
="= R' + N.
Figure shows the performance variation of the reward comparison pseudometrics to different noise severity levels. When = (noise free), the difference between SRRD, EPIC, DARD, and DIRECT is the highest, with a performance order: SRRD > DARD > EPIC DIRECT, which demonstrates SRRD's performance advantage over other pseudometrics under potential shaping. As the impact of N increases, the shaped reward R" becomes almost entirely comprised of noise, and the shaping component significantly deviates from potential shaping. As shown, SRRD's performance gap over other pseudometrics significantly diminishes. At high severity (Figure 5p), SRRD's performance is nearly identical to all other pseudometrics, including DIRECT, which does not involve any canonicalization. In conclusion, these results still demonstrate SRRD's superiority in canonicalizing rewards even with minor random deviations from potential shaping (Figure 5 b). However, as the rewards become non-potentially shaped, all pseudometrics generally become ineffective, performing similarly to non-canonicalized tochniques such as DIRECT.
B.2 basele-based Approximations using Unbiased Estimates
In this paper, the sample-based SRRD approximation presented adopts a similar form to that of EPIC and DARD, primarily to maintain consistency with well-established methods. This approach utilizes two types of samples: By, a batch of transitions of size Ny, and BM, a batch of state-action pairs of size NM- Each transition in By is canonicalized using statc-action pairs from B The advantage is that if BM is representative of the joint state-action distribution of the reward function (or sample), canonicalization can be highly effective even with smaller sizes of Ba.. Since each transition in By is canonicalized using state-action pairs from BM, the computational load required during canonicalization can be reduced compared to using all possible transitions. For example, suppose we have a reward function with 10, 000 states and 100 actions. In this case, the total number of transitions 10, 000 100x 10, 000 = 1010 However, using the sample-basee SRRD approximation method, we could generate a sample By with 100 transitions, and another sample BM, with 100 stale-action pairs. Each transition in By is then canonicalized using state-action pairs from BM, and the total mumber of transitions needed is approximately Ny NM R 100 1002 = 10t transitions (see Appendix A.11 b; which is way less than the transitions needed in the full computation.
The double-batch sampling approach (using By and BM) generally works well in environments where tran- sition sparsity is not a major problem. However, when transition sparsity is a concern, a large fraction of transitions generated from the combination of By and By might be unsampled, and can have undefined reward values, which can introduce errors in canonicalization. Our proposed pseudometric, SRRD, is much more robust under these conditions compared to both EPIC and DARD, even though it uses a similar sam-
36

---

Published in Transactions on Machine Learning Research (04/2025)
pling form. An alternative approach to the double-batch sampling method is to use unbiased estimates. The
unbiased estimate approximations are described as follows:
() R(s,a,5) + 2 En Ni
1 =E ((,,,,)')) - N₂
7 Σ R(x, R(a, u,,",, N3
(55)
where: ((s', x') is the set of sampled transitions that start from the state s', with the total number of transitions equal to Ní; {(s, x'}} is the set of sampled transitions that start from the state with the total number of transitions equal to N2; and {(2, u, x'}} is the set of all the sampled transitions, with the total number of transitions equal to N3.
( = R(s,a,s') + Ni Σ R(s',,,z") N₂ Σ R(s,u,x))-
7 N3
Σ R(x',u x,)"
(56)
where: ((6',u, u, x")}, 1,,,,,,,,,, is the set of all sampled transitions that start from the state 8', with the total number of transitions equal N1: {(s, x,²")} is the set of all sampled transitions that start from the state s, with the total number of transitions equal to N2; and ((,', u,)")) is the set of transitions that start from the subsequent states of s to the subsequent states of s', and have total number of transitions equal to Ng.
(SnnD(R)(s,a,,, = R(s,a,8')
+
7 Σ R(s',u,20 N₂
N₂ Σ R(s, U2)
7
Σ
R(Iss, U, X.a)
N₂
+ 22 N4
72
Σ
R(11,
7 Σ R(22, 06))
? Σ R(x,, u, 26)
Σ R(xs, Us).).
NB
No
Nr
(57)
For SRRD, let Xı represent the set of all subsequent states from 8i; X2 represent the set of all subsequent states to and X3 be the set of all initial states for transitions, while X4, Xs, and Xs denote the sets of subsequent states from X3, X1, and X2, respectively. For all transitions, the set: { u, x4)} contains all sampled transitions where Zy E X3 and x4 E X4, with the total number transitions equal to Ng. For cach sampled transition, (8, a, the del:((s', (1,,,,,20 x1)} contains observed transitions starting from s' and ending in 21 e X1, with magnitude Ni. {(s, u, x2)) contains observed transitions starting from and ending in 22 E X2. with a magnitude N2. {[21, u, #5)) contains observed transitions starting from Φ X1 and ending in 25 Xs, with magnitude N1. {(x2, u, [6)} contains observed transitions starting from T2 E X2 and ending in E Xe, with magnitude Ns. ((13, u, 1&)} contains observed transitions starting from 23 E X3 and ending in To E X6, with a magnitude No- {(04, 25 contains observed transitions starting from 24 E X1 and ending in Ø3 E Xs, with a magnitude N7.
Figure shows results obtained for Experiment (refer to Section 5.1 using sample-based approximations relying on unbiased estimates, instead of the double-batch sampling approach. The obtained results show similar trend to the results obtained from the double sampling approach, with SRRD still yielding better performance compared to both EPIC and DARD. In general, unbiased estimates tend to be more accurate under transition sparsity, as reflected in Figure 7 showing results for both the double-sampling and the unbiased estimate approaches. Overall, the unbiased estimate approach tends to outperform the double-batch approach, however the double-sampling approach catches up as the level of transition sparsity decreases. The SRRD approach still outperforms both EPIC and SRRD especially when coverage is low (< 20%), and it also performs well under the double-batch sampling mechanism, highlighting its robustness in climinating potential shaping.
37

---

Published in Transactions on Machine Learning Research (04/2025)
Legend:
DIRETT
SARD
Gridworld
Bouncing Balls
random rewards
polynomial rewards
random rewards
polynomial rewards
0.75
- 0.50
0.50
0.50
0.25
0.25
0.25
0.25
0
25
50
75
25
50
75
20 coverage (%)
0.00
20 coverage (%)
coverage (%)
coverage (%)
(a) Effect of limited sampling.
random rewards
polynomial rewards
random rewards
polynomial rewards
0.65
0.6
0.5
0.60
0.4
0.4
0.3
1.0
2.0 coverage (%)
1.5
2.5
coverage (%)
coverage (%)
coverage (%)
(b) Effect of feasibility constraints.
Figure 6: (Unbiased Estimate Approximations). The figure shows results for Experiment (refer to Section 5.1 which is conducted using unbiased estimates as approximations for the SRRD, DARD and EPIC. As shown, results demonstrate a similar trend as the one obtained when using the bouble-batch sampling approach reliant on By and By. The goal of the experiment is to compare the effectiveness of reward comparison pseudometrics
identifying the similarity between potentially shaped reward functions under two conditions: (a) limited sampling and (b) feasibility constraints. A more accurate pseudometric yields Pearson distance D, close to 0, indicating high degree of similarity between shaped reward functions, while less accurate pscudometric results in D, close to 1. In (a), EPIC and DARD lag behind SRRD at low coverage due to limited sampling, but their performance gradually improves as coverage increases. In (b), movement restrictions significantly reduce transition coverage, negatively impacting both EPIC and DARD.
DIRECT
SRRD
EPIC
DARD
uSRRD
dEPIC
uDARD
random rewards
polynomial rewards
0.55
0.6
0.50
0.45
0.4
0.40
0.35
0.2
20
40
60
80
100
20
40
60 coverage (%)
80
100
coverage (%)
Figure 7: (Unbiased Estimates vs Double-batch Sampling). This figure presents the results for Experiment under limited sampling for the Gridworld domain. It compares the performance of pseudometrics using the double-sampling approach (with batches B& and Bx) versus the unbiased estimate approach. For the unbiased estimates, the results are plotted in bold lines and for the double-sampling approach, they are plotted using broken lines. The initial 'u' (legend) denotes the unbiased estimate methods, for example uSRRD. The objective is to compare the difference in performance between unbiased estimates and the double-batch sampling approach. As shown, the unbiased estimate approaches tend to outperform the double-batch approaches. In both sampling approaches (double-sampling or unbiased estimates), SRRD also outperforms both EPIC and DARD especially when coverage low (S 20%). The SRRD approach also performs well under the bouubee-btch sampling approach, highlighting its robustness eliminating potential shaping.
38

---

Published in Transactions on Machine Learning Research (04/2025)
B.3 Inferring Rewards for Unsampled Transitions via Regression
All the canonicalization methods discussed in this paper are susceptible to unsampled transitions. However, CSERD is more resilient since it mostly relies forward transitions rather than non-forward transitions (refer to Section 4.10. J. In this study, instead of relying solely on sampled transitions during canonicalization, we explore the possibility of addressing transition sparsity by generalizing rewards from sampled transitions to unsampled transitions via regression. Using a 20 x 20 Bouncing Balls domain, we generate reward samples from a uniform policy and compute the SRRD, DARD, and EPIC distances. To vary coverage, we adjust the number of trajectories generated from policy rollouts, and compute coverage as the fraction of sampled transitions over the total number of transitions, |S A x S]. In this experiment, reward samples are only defined for feasible transitions and unfeasible transitions have undefined reward values. However, during canonicalization, the reward values for the unsampled transitions (mostly unfeasible), are inferred via regression, Figure shows the results obtained in this experiment:
--- SRRD
EPIC
DARD
regressDARD
regressSRRD
regressEPIC
polynomial rewards
random rewards
sinusoidal rewards
0.6
0.6
0.4 d
0.5
0.5
0.4
0.4
1.0
1.5
2.5 coverage (%)
2.0
3.0
3.5
1.0
1.5
2.0
2.5
3.0
3.5
1.0
1.5
2.0
2.5
3.0
3.5
coverage (%)
coverage (%)
Figure 8: (Incorporating Regressed Rewards) When the relationship between rewards and state-action fea- tures is less complex, such as the case with polynomial rewards, learning the regression model is highly effective. Consequently, incorporating rewards that are inferred via regression into canonicalization can be beneficial, resulting in improved performance for regressDARD, regressSRRD, and regressEPIC. However, when the relationship between rewards and state-action features is complex, the learned regression model might struggle to generalize well such as the case for random and sinusoidal rewards.
As shown in Figure g the success of incorporating regressed rewards depends on the nature of the reward function. When the reward function is derived as a simple combination of state-action features, learning the regression model highly effective due to the less complex relationship between state-action features and reward values. This likely the case for polynomial rewards, where pseudometrics that incorporate regressed rewards, generally outperform the original non-regression-based pseudometrics, especially as the coverage increases. However, for sinusoidal and random reward functions, the relationship between state- action features and rewards is much more complex, making it challenging to effectively learn highly effective model under transition sparsity. Consequently, the rewards learned via regression may not generalize well, and the original sample-based approximations tend to outperform the regression-based approximations. In general, the regressed SRRD approximation outperformed all other regressed-basee approximations. This superiority attributed to the inherent nature of SRRD which relies more on forward transitions that are likely in-distribution with the reward samples' transition dynamics, than non-forward transitions that are more prone to being out-of-distribution with the dynamics of the reward samples. Therefore, even when incorporating regression, SRRD depends less the regressed rewards compared to EPIC and DARD, resulting in more accurate predictions. EPIC idcally requires full coverage, hence, under transition sparsity, it relies more heavily on regressed rewards which makes it more susceptible to errors when the regression model cannot generalize well. In this experiment, we compared linear regression, decision trees, and neural networks, and chose lincar regression since yielded the best results in terms of accuracy. This could result from the lack of diverse data, as rewards are only defined for feasible transitions, which are small subset compared to the total number of transitions that would be needed if no feasibility constraints were imposed.
39

---

Published in Transactions on Machine Learning Research (04/2025)
B.4 Sensitivity of SRRD to Sampling Policy
A crucial challenge in reward comparison tasks is the fact that reward samples partially represent the true reward function and might not fully capture the structure of the actual reward function. This section exam- ines the performance of SRRD to variations in the policy used to extract reward samples. The experiment is conducted in a 15 x 15 Gridworld environment, where an agent's 's objective is to navigate from an initial state (0) to the target state (14, 14). The agent selects actions from the set A = {up, right, down, left); The reward function is derived from predefined expert behaviors using Adversarial Inverse Reinforcement Learning (AIRL). Figure 9 shows a reward function Rdiagoual, computed for an agent with a diagonally oriented policy where for each state 8: 7 dddigonni( = 0.1, T (riigona(rrihh))s)) = 0.4, Tdiagonal (diagona((downls (down|s) = 0.4 and T (difsona(left(ss) 0.1. The reward for each transition is represented by the triangular directional arrows, for example, the reward from state (0, 0) to state (),1) is 2.5. The reward function is defined exclusively for feasible transitions, and the intensity of rewards is depicted using three three colors: red for high rewards (> 5), blue for moderate rewards (2 - 5), and light brown for low rewards (< 2). In this study, we compare the similarity between two shaped reward samples derived from Rdiagonal using a specified sampling policy. We then analyze the variation in DSRRD based on different sampling policies. The experiment is repeated
over 100 trials.
X-axis
1
3
5
7
8
9
10
11
12
13
14
15
16
28
08
17
16
16
0.
14
04
03
12
0.
11
0.0
0
25
16
36
38
38
18
08
07
1.
06
0.6
16
16
15
05
14
14
04
03
02
11
11
11x60
32
26
$1
56
17
28
18
28
17
166
15
1,5
24
2.3
2.3
1
22
46 26
41
51
56 36
27
17
18
18
28
28
18 18
27
27
26
16
15
155515
15
25
15
24 244
2.3 2.3
22
46
41
36
27
28
18
29
17
266
15
15
14
2.3
1.3
29
45
67
33
28
38
37
2.5
2
33
29 49
45
55
61
61
47
47
33
2.3
25 25
38 28
299
39
39
29
2.8 38
27 27
37 27 377
366 266
23
29
35
41
377
33
2.5
3.8
39
299
3.8
377
26
3.5
3
20
5.0 50
36 36
61
41
47
67
53
36 36
39 39
3.1 31
34 44
37
400
5.0
49 39
49 49
48 48
20
40
46
51
47
73
2.6
2.9
31
34
37
40
3.9
49
57
52 62
58 A8
54% 6.4
700
38 2.8
41
4.4 34
A7
4.0
4.0
53 5.
4.5 45
48
21
37
62
48
64
E0
2.8
31
4.4
37
5.0
3.3
45
4.8
5
23
23
14
49
15
7.6
44
4.0
53
5. 45
23
23
16
644
5.9
15
8.
7.6
31
44
47
5.0
5.3
45
5.8
11
14
16
29
51
76
72
88
73
3.4
47
5.0
4.
55
48
6
21
26
51X51
56
16
82X82
68
93
93
37
52
45K
35
266
377
42
Y-xiis
11
14
16
29 19
32
57
83
69
95
10 0
37
5.0
52
55
58
7-
112
16 16-26 2.6
22
57
73X83
69
89
89
85
9 90-30.0 0.0
3.7
5.0
5.0
52 42
45
45
38
3.7
52
22
24
26
299
32
35
84
80
86
10
87
5.0
53
45
58
8
22
44
26
26
29
32
35
35
84
6.
80
1.5x
92
92X30
17.
5.0
5.0
43
55
35
12
24
26
299
22
26
38
81
97
83
89
9.4
43
56
48
9
22
14
14
16 416
2.5
299
10
10
32 32
2.2
36
2.6
38
2.8
28
8
81
97
97
8. 83
10.3
99
10.9
89
10
94
11A
43 53
5.
46
588
27
2.9
2.2
25
29
32
88
94
11.
10.1
49
10
12
14
15
17
10 29
32 22
25
25
29
29
32 32
78 98
10 0-
90
190
5-
12
46
46
24
17
19
2.2
35
39
3.2
98
8.4
90
115
12.1
5.6
5.
45
32
11
23
25
25
17
19.49
22 32
35 35
29 29
32 32
355 35
85 10
91 91X11
11 2
13
15
17
2.9
3.2
35
2.9
32
35
95
10.1
9.7
10.2
10.8
5.9
45
10
13.5
12
23
25
15
29
22
35
25
29 29
42 32
35 45
38 48
11 2412
8-418
10
10
41.
23
15
27
10
32
35
29
3.2
35
38
1022
20.8
10.4
12.9
125
13
13
25
27
22
25 25
29
42
35
48
51
99
125511
BML
436
25
17
20
32
35
39
42
35
38
31
119
11.
B.
11
14
38
32
20
38
31
11.6
Figure 9: (Rdiagonal). The reward function generated via AIRL from an agent that executes the policy Adiagnoal; which favors movement. along the grid's main diagonal. High rewards highlighted in red, moderate rewards in blue, and low rewards in light brown.
40

---

Published in Transactions on Machine Learning Research (04/2025)
Table 2: Sensitivity of SRRD to different reward sampling policies. The coverage is computed as the fraction of sampled transitions, over the total number of feasible transitions.
Reward Sampling Policy
Tuniform
Tdiagons]
Ttop
"Teft
# of Trajectorics
50
100
50
100
50
100
50
100
Coverage (%)
33.2
43.4
56.9
74.6
11.91
14.3
10.86
13.03
D3RRD for Rdiagonal
0.62
0.60
0.57
0.56
0.64
0.63
0.62
0.62
Table 2 summarizes results for testing SRRD's sensitivity to different reward sampling policies: Tdiagonal: Stop biased toward the upper segment of the grid; Tuniform uniform policy across all four directions; and Teet biased towards the left grid segment. As shown, DSRRD varies based on the reward sampling policy. In Raiagonal when all the feasible transitions are used in reward comparisons, DSRRD s 0.58, which is the benchmark value to test the policy variations. This value closely matches the distance values obtained by Tuiiform and Tdiagonal, which both sample transitions that closely match the actual distribution of the bench- mark rewards, Rdiagonal- However, policies such as Ttop and Teff, generally achieve distances that deviate from the benchmark score, since the reward distribution in the reward samples might be less representative of the structure of Riingonal- Overall, DSRRD varies between: [0.56 0.64], while the benchmark distance from Rdiagonal is 0.58. We also observe that increasing the mumber of sampled trajectories from 50 to 100 generally leads to lower SRRD distances. However, this effect is less pronounced in this experiment because the reward function is defined only for feasible transitions, limiting the variability and coverage inherently. In conclusion, SRRD is sensitive to variations in the policies that generate the reward samples, since canon- icalization relies on the distribution of sampled transitions, which might not be representative of the actual transition distribution under full coverage. In sampling rewards, it is desirable to ensure that the sample has high coverage and broad support over the distribution of the true reward function. We also performed this study with EPIC and DARD, and they both yield higher distances within the range [0.63 0.7].
B.5 Environments with Infinite or Continuous State and Action Spaces
As previously mentioned in Section g and computing the exact reward comparison distances is only feasi- ble in small environments with finite discrete states and actions, where all the possible transitions between states and actions can be enumeaated. For complex environments with infinite or continuous states and actions, computing the exact values for DEPIC, DDARD and DSRRD becomes impractical, hence, sample- based approximation methods have been developed. These approximations take transition inputs composed of discrete states and acts, and when applied to continuous enviromments, it essent to discretize the state and action observations from the continuous signals as demonstrated in prior works (Gleave et al., necessary in environments such
2021 Wulfe et al.) 2022). In experiments, these approximations Robomimic, MIMIC-IV, Drone Combat Scenario and StarCraft II. For StarCraft II for example, while not necessarily continuous in a strict sense, the environment operates in real-time with partial observability, mul- tiagent decision-making, durative actions, and asynchronous, parallel action execution. The game updates at approximately 16 times per second, and it effectively has infinite states and actions. These fluid, real-time interactions align it more with continuous pocision-making scenarios, and to manage the complexity, we perform feature preprocessing to discrctize and cluster state and action observations before applying the sample-based approxinations.
An intriguing area for future research is the integration of function approximation to generalize reward canonicalization to reward functions represented as neural networks. While function approximation might not be necessary for straightforward reward comparisons where the goal is to retrieve a similarity distance they become essential in applications requiring the canonicalization of the entire reward functions, such as standardizing rewards during IRL. for example. Our initial proposed approach involves training a neural network to predict canonical rewards based on batches of transition observations. In the training process, the canonicalized rewards for the batch can be approximated via sample-based methods, and then the neural
41

---

Published in Transactions on Machine Learning Research (04/2025)
network aims to predict the canonicalized rewards from the imput transition batch. The network iteratively learns to predict the canonicalized rewards by minimizing the difference between its predictions and the sample-based approximations.
C
Experimental Details
C.1
Experiment 1: Transition Sparsity Pseudocode
Algorithm Analyzing the effect limited sampling on reward distance
Input:
T list of policy rollout counts,
number of experimental trials under same condition,
G grid size,
RD list to store reward distances at different coverages,
MC maximum coverage = S x A S.
O Output: RD
1: generate GT ground truth reward, SH shaped reward from all possible transitions.
for rollout.cont in do
trialdistance, trial (ist(), for trial in E do
5: Byt. B.h = set()
6: generate trajectories Tyt and Teh using uniform policy rollouts.
7: for (,,,,')= E Tyt do Bddaad((ss,,, ()) end for 10: for (s, 8') Tah do Bsh.add((s, a,
11:
12:
end for for s') E Bye and as) E Bah, retrieve R(s,a,s') using GT and a((s,,, using SH, respectivcly.
13:
coverage [BatBBal
14:
MC
15:
compute dist Rt Rt') using EPIC, SRRD, DARD, or DIRECT. R'))
16:
apield apiee (pvpeede coverage) end for
17:
18:
19:
R.D. append (oopendd[mean(taeen [Imeen mean(trialaistanee))
20: end for
C.2 Experiment 1: Reward Functions
Extrinsic reward functions are mamually defined using a combination of state and action features. For the Drone Combat, Montozuma's Revenge, and StarCraft II domains, we use the default game engine scores as the reward function, and for Robomimic, rewards are based on task completion (see Appendix C.2). For the Gridworld and Bouncing Balls domains, in each reward function, the reward values are derived from the decomposition of state and action features, where, (sy1,-.;8ju is from the starting state 8; (af1, ffm) is from the action a; and (s.),...,,8/, is from the subsequent state s'. For each unique transition, using randomly generated constants: (u1,... un) for incoming state features; {wi,..., Wm) for action features; { for subsequent state features, we create reward models as follows:
Linear:
R(s, #1851 .... + Un8fa wiafi +.. Wmafm + 4186f1 + Un
42

---

Published in Transactions on Machine Learning Research (04/2025)
Polynomial:
R(s,a,s') u189 +... un w/aj1 +... wmafm +u + n..+t Un
where, a randomly generated from 10, denoting the degree of the polynomial.
Sinusoidal:
R(s.a,s') =u sin(ss)) +... u, sin((s) w sin((aa) +... um sa + tvsin((611) ... sin
Random
a(s,a,s') B,
where, 3 is randomly generated reward for each given transition.
The same relationships are used to model potential functions, where: d(s) = f(sn1, 8tn), and f is the relationship drawn from the set: {polynomial, sinusoidal, linear, random). For StarCraft II, Drone Combat, and Montezuma's revenge, we used the default game score provided by the game engine the reward function; and for Robomimic, sparse rewards based task completion used. For the StarCraft. II domain, this score focuses the composition of unit and resource features. Since the Drone Combat environment is originally designed for predator-prey domain, adapt the score https: //t::///tttb.... com/ koul Boola//urg/maa taagg//aammttoo to essentially work for the Drone Combat scene (i.e instead of a predator being rewarded for cating some prey, the reward now an ally attacking an enemy).
C.3 Experiment 1: Parameters
A uniform policy in the Gridworld domain randomly selects one of the four actions, (north, cast, south, west), al each timestep. For the Bouncing Balls domain, it randomly selects an action from the set: {north, north-east, east, east-south, south, south-west, west, west-north, north}. The parameter dictates the ratio of times in which random transitions (instead of uniform policy) are executed. Table and Table shows the experimental parameters used in Experiment (Algorithm 1).
Table 3: (Low Coverage): Parameters used to test the variation of coverage for the Gridworld and the Bouncing Balls domain.
Parameter
Values
Rollout Counts,
[1, 4, 5, 6, 9, 10, 15, 20, 30, 40, 50, 75, 100, 200, 300, 400, 500, 1000, 2000]
Epochs, E
200
Policy,
uniform, 011
Discount, Y
0.7
Dimensions
20 20
Table 4:
(Feasibility Constraints): Parameters used to test the variation of coverage in the presence of movement restrictions, c = 0, for the Gridworld and Bouncing Balls domain.
Parameter
Values
Rollout Counts,
1,2, 3, 5, 10, 15, 20,30, 40, 50, 75, 100, 200, 300, 400, 500, 1000, 2000]
Epochs, E
200
Policy,
uniform, e
Discount, Y
0.7
Dimensious
20 20
43

---

Published in Transactions on Machine Learning Research (04/2025)
C.4 Transition Sparsity: Additional Results
In both the Gridworld and the Bouncing Balls domains, we did not see much difference the structure of results between the 10 10 domain and the 20 20 domains. Results were fairly consistent in that SRRD tends to outperform DARD and EPIC, and feasibility constraints tend to limit coverage significantly.
DIRECT
SRRD
EPIC
DARD
linear rewards
polynomial rewards
random rewards
sinusoidal rewards
0.50
Distance
0.5
0.4
0.50
0.25
0.2
0.25
0.0
20
40
60
80
100
20
40
60
80
100
20
40
60
80
100
0
20
40
60
80
100
coverage (%)
coverage (%)
coverage (%)
coverage (%)
(a) No feasibility constraints
linear rewards
polynomial rewards
random rewards
sinusoidal rewards
Distance
0.50
0.4
0.4
0.75
0.50
0.25
0.2
0.2
0.25
3
3
5
6
7
2
3
4
5
6
7
3 coverage (%)
coverage (%)
coverage (%)
coverage (%)
(b) Movement restrictions imposed
Figure 10: 10 10 Gridworld: Variation of reward relationships
linear rewards
polynomial rewards
random rewards
sinusoidal rewards
Distance
0.4
0.50
0.4
0.50
0.2
0.25
0.2
0.25
0
20
40
60
80
100
0
20
80 coverage (%)
40
60
100
20
40
60
80
100
20
40
60
80
100
coverage (%)
coverage (%)
coverage (%)
(a) No feasibility constraints
linear rewards
polynomial rewards
random rewards
sinusoidal rewards
Distance
0.2
0.3
0.4
0.2
0.2
0.1
0.1
0.2
0.1
2
3
6
7
2 3
5
6
3
4
5
7
3
4
6
7
coverage
(%)
coverage (%)
coverage (%)
coverage (%)
(b) Movement restrictions imposed
Figure 11: 20 x 20 Gridworld: Variation of reward relationships
44

---

Published in Transactions on Machine Learning Research (04/2025)
DIRECT
SRRD
EPIC
DARD
linear rewards
polynomial rewards
random rewards
sinusoidal rewards
Distance
0.4
0.50
0.4
0.25
0.2
0.2
0.25
0.00
20
40
60
80
100
40
60
80
100
20
40
60
80
100
20
40
60
80
100
coverage (%)
coverage (%)
coverage (%)
coverage (%)
(a) No feasibility constraints
linear rewards
polynomial rewards
random rewards
sinusoidal rewards
Distance
0.4
0.3
0.4
0.3
0.2
0.3
0.2
0.1
0.2
6
3
4
6
2
3
5
7
3
6
coverage (%)
coverage (%)
coverage (%)
coverage (%)
(b) Movement restrictions imposed
Figure 12: 10 x 10 Bouncing Balls: Variation of reward relationships
linear rewards
polynomial rewards
random rewards
sinusoidal rewards
Distance
0.50
0.50
0.
0.2
0.25
0.25
0.2
0.0 0
40
60
20
40
60
20
40
60
0
20
40
60
coverage (%)
coverage (%)
coverage (%)
coverage (%)
(a) No feasibility constraints
linear rewards
polynomial rewards
random rewards
sinusoidal rewards
Distanca d
0.35
0.4
0.3
0.25
0.30
0.2
0.2
0.20
0.25
0.1
0.15
2
3
3
2
3
coverage (%)
coverage (%)
coverage (%)
coverage (%)
(b) Movement restrictions imposed
Figure 13: 20 x 20 Bouncing Balls: Variation of reward relationships
45

---

Published in Transactions on Machine Learning Research (04/2025)
C.5 Experiment 2: Reward Classification Testbeds
The Gridworld domain simulates agent. movement from a given initial state to a specified terminal state under a static policy. Each state is defined by an (z, coordinate where 0 S < N, and 0 S y < M implying |S] = NM. For Experiment 2, the action space only consists of four cardinal directions {north, east, south, west], and to define classes, we use static policies based on the action-selection distribution (out of 100) per state. Table shows the Gridworld parameters used for Experiment 2.
Gridworld:
Bouncing Balls: The Bouncing Balls domain, adapted from Wulfe et al. (002), simulates a ball's motion from a starting state to a target state while avoiding randomly mobile obstacles. These obstacles add complexity to the environment since the ball might need to change its strategy to avoid obstacles (at a distance, d 3). Each state is defined by the tuple (z, y, d), where (z, y) indicates the ball's current location, and d indicates the ball's Euclidean distance to the ncarest obstacle, such that: 0 S x < N, S y < M, and d S max max(M,N) N). The action space includes eight directions (cardinals and ordinals), with the stochastic parameter for choosing random transitions. Table 5 describes the parameters for Experiment 2.
The Drone Combat domain derived from the multi-agent gym environment, which simulates a predator-prey interaction (Amurag) 2019). We adapt this testbed to simulate a battle between two drone swarms; blue swarm denoting the ally team; and red swarm denoting default. Al enemy. The goal is for the blue ally team to defeat the default AI team. This testbed offers discrete actions and states within a fully observable environment, while also offering flexibility for unit creation, and obstacle placement. However, the number of states and actions is still high such that we did not use the best in Experiment 1. Each unit (blue and red squares) possesses a distinct set of parameters and possible actions. Each team consists of drones and ships, and the team that wins either destroys the entire drones of the opponent or its ship. This ship adds complexity to the macision process of the teams which need to engage with the enemy, as well as saleguard their ships. Each drone is defined by the following altributes: visibility range (VR) the range unit see from its current position (partial observability); health (H) the number of firings a unit can sustain; movement range(MR) the maximum distance that a unit can move to; and shot strength(SS)- the probability of a shot hitting its target. These attributes are drawn from the set:
Drone Combat:
= ((VR, H, MR, SS) VR E (1,3, 5), E (5, (0,10, 15), MR e (1,2,3), (0.05, 0.13)
Table 7 summarizes the parameters used for Experiment 2.
Robomimic Robomimic is a framework designed for imitation learning and reinforcement learning in robotic manipulation tasks (Mandlekar et al. 2021p. It provides standardized datasets, and environments to facilitate reproducibility in learning from demonstrations. In our experiments, we focus on collected offline datasets, which include human and simulated demonstrations on the following robotic tasks: Lift the robot needs to pick up a cube and lift off the table; Can - the task requires lifting and placing a soda can upright; Square - the robot aligns and places a square peg into a hole; Tool Hang - requires a robot to use a tool to hang it on a rack; and Nut Assembly- screw it onto bolt. The goal in Experiment 2 is to distinguish between single human expert, machine generated, and mixed human agent behaviors, using k-NN classifier based on reward pseudometrics. For each agent type, we collect 200 trajectorics, and utilize the extrinsic sparse rewards based on task completion, as well as IRL computed rewards. The details about the agent types, and data collection are available at: 1.
multi-step task where the robot must pick up a mut and
https://robomimic. github.
Montezuma's Revenge: Montezuma's Revenge is classic Atari 2600 game generally used bench- mark in RL rescarch due to its challenging environment. The game involves controlling an explorer agent, in navigating a series of interconnected rooms in a temple filled with traps, ladders, enemies and collectible items. The game is challenging for RL since its characterized by sparse rewards, complex exploration, long- term dependencies, and high penalty for mistakes. In our experiments, we used a collection of Atari games from human demonstrations (Kurin et al.) (0017). We subdivide these games into three subgroups based on game scores: experts (> 3000), moderate (1000- 3000) and novice(< 1000); and sample 200 trajectories for
46

---

Published in Transactions on Machine Learning Research (04/2025)
each agent type. The task objective is to determine the agents' expertise using the reward pseudometrics to classify the agents based on samples of their demonstrated behavior.
StarCraft II (SC2): The SC2 domain is a strategy game created by Blizzard Entertainment that features real-time actions on a complex battlefield environment. The game involves planning, strategy, and quick decision-making to control a multi-agent ally team, aiming to defeat default Al team in a competitive, challenging, and timo-sensitive environment. SC2 serves not only entertainment but also a platform for professional player compelitions. Due to its complexity and the availability of commonly used interactive Python libraries, the SC2 game is widely employed in Reinforcement Learning, serving as a. testbed for multi-agent research. The goal of the ally team is to gather resources, and build attacking units that are used to execute a strategic mission to defeat the AI enemy; within an uncharted map, that gets revealed after extensive exploration (introduces partial observability). The sheer size of the map and the multitude of possible actions for each type of unit, as well as the number of units, contribute to the enormity of the action and state spaces. During combat, each ally unit, moves in a decentralized manner and attacks an enemy unit using an assigned cooperative strategy from the set: C= {cl, C2, C3, ci); where e1 move towards ally closest to enemy's ' start base; C2 move towards a random enemy unit; C3 move towards ally closest to an enemy unit; and c4 move towards the map's center. We focus on attack-oriented ally units to reduce the state space. Non-attacking units such as pylons are treated as part of the environment. The game state records the number of ally units (nummatg), and the total number of opponent units (numenemy); as well as the central coordinates of the ally and the enemy. The action records the number of ally units attacking the enemy al an instance. Table describes the StarCraft II parameters used for Experiment 2.
MIMIC IV: MIMIC-IV is a large, publicly available database of de-identified patients admitted to an emergency department (ED) or intensive care UnCU(ICU) at the Beth Israel Deaconess Medical Center in Boston, MA (Johnson et al., 2023). The dataset contains records for over 65, 000 patients admitted to an ICU, and over 200, 000 patients admitted to the ED. In our analysis, we model each patient's hospital's visit as Markov Decision Process, where, each state is list of assigned diagnoses (a patient may have multiple concurrent diagnoses), and the actions are the procedures and prescriptions provided. For manual rewards, we assign R = 5 7 when patient survives, where 7 0.9 is discount factor (to penalize frequent visits) and is the trial number of the patient's 's visit. A manual reward of -5 is assigned when the patient dies. We also compute AIRL, Maxent and PTIRL rewards. From the data, because both the states (diagnoses) and actions (prescriptions and procedures) are expressed in natural language, we transform them into numerical vectors using frequency counts of medical keywords (without stop words) from the diagnoses or prescription reports. We then apply standard scaling (mean and variance), and perform PCA to extract numerical features. For the behavioral classification experiment, we mamually group patients into 5 categories based keywords from the first diagnosis record of the patients. These categories arc: diabetes has diabetes oriented diagnoses, kidney has kidney oriented diagnoses, limb has limb or skeletal oriented diagnoses, respiratory has respiratory diagnoses, and substance- has substance abuse or mental health diagnoses. Our task is then to classify different pationt trajectorics (soquenees of states and actions), based on their reward functions, using the reward pseudometrics. It is important to note that some diseases overlap, hence we used a majority vote to assign the overall category. Since this data is inherently sparse, our final dataset had 409 patients distributed such that we have: [70, 75, 42, 35, 187] patients, corresponding to each disease class, respectively. Each trajectory has a length in the range 30 to 250. Most of the original MIMIC-IV data not useful for our analysis since patients rarely visit an ICU facility more than once. In the experiments we did not consider age, race or gender in the analysis.
C.6 Experiment 2: Parameters
The optimal values for (discount factor) and k (the neighborhood size) are not fixed for each independent trial. Therefore, for hyperparameter selection, we employ a grid search over the set defined by:
((%, k) 7 (0.0.1..... 1}, k E {10,
1003}
The agent classes shown describe the policy that an agent takes in each given state. For example, in the Gridworld domain, an agent with policy [25, 25, 25, 25], randomly selects the cardinal direction to take
47

---

Published in Transactions on Machine Learning Research (04/2025)
from uniform distribution. For the Drone Combat and StarCraft II domains, the agent behaves based the combination of the defined attributes.
Table Bouncing Balls Parameters.
Parameter
Values
Agent policies (10 classes)
[12, 12, 12, 12, [25, 25, 26,
13,
13,
13,
13
5,
5,6,5]
5, 5
G.
25,
0,,
5, 65,
6
5,
5,
[5, 25, 25, 2,
[20, 50 5,20,
20,
8
55
20,
5,
20,
20, 5,
Trajectory sets per policy
100
Number of obstacles
5
Distance to obstacle (Manhattan)
Number of comparison trials
200
Actions
move: [north, north-east, east, cast-south, south, south-west,, west, west- north)
State Dimensions
20 x3
Table 6: Gridworld Parameters.
Parameter
Values
Agent policies (10 classes),
[25, 25, 25, 25].
5, 85],
[85,
5. 5, 5],
5, 5]. [5, 5,
30,
55], [55, 30, 5), [15, 5, 55, 30,, [5, 55, 30,
15),
[15, 30,
5, 55]
Trajectory sets per policy,
100
Number of comparison trials,
200
Actions,
move: fnorth, west, south, east)
State Dimensions
x 20
Table 7: Drone Combat Parameters.
Parameter
Values
Agent policies
classes, each consisting agents. Each agent x has attributes randomly drawn from the set:
U {(VR, H, MR, I VR e (1,3,5) E {5, 10, 15), 15) MR (1,2,3), SS E (0.05,0.1)
Trajectory per policy
100
Number of agents per team
(1 ship, 10 drones)
Number of comparison trials
200
Actions, a the movement range,
{(left", up", right", down")) "rown""
attack)
15 a <
Dimensions
25, with obstacles occupying 30% of the area
Table 8: StarCraft II Parameters.
Parameter
Values
Agent policies generated based sources and strategy
10 classes, agents attributes randomly chosen from:
U ((c,u) c (ei, (2,,0,, c4) C (adept, voidray, phoenix, stalker)
Trajectory sets per policy
100
Comparison trials
200
Actions
Number of attacking units per unit. time
State representation
(numatly. nuMeneny, (Kally Hally): (Fenemys Venemyy)
48

---

Published in Transactions on Machine Learning Research (04/2025)
C.7 Experiment 2: Inverse Reinforcement Learning (IRL)
Table Reward Learning Parameters Across Domains
AIRL
MAXENT
PTIRL
Trajectories/mun /run:
Trajectories/rum: 5
Target Trajectories/run:
RL Algorithm: PPO
RL Algorithm: PPO
Non-Targe Trajectories/ /rum:
Discount (y): 0.9
Discount (?): 0.9
Max Reward Cap: +100
Reward Network MLP
Reward Network MLP
Min Reward Cap: -100
Hidden Size: [256, 128]
Hidden Size: [256, 128]
Learning Rate: 10-4
Learning Rate: 10-4
Solver: Cplex
Time Steps: 10a
Generator Batch Size: 2048
Discriminator Batch Size: 256
In Experiment 2, we utilize Inverse Reinforcement Learning (IRL) to compute agent rewards based on demonstrated behavior. Specifically, we employ three IRI. algorithms: Maximum Entropy IRL (Maxent- IRL) (Ziebart et al. 2008); Adversarial IRL (Fu et al.) 2018); and the Preferential Trajectory IRL (PT-IRL)
Santos al. 2021 In addition, we compute manual rewards that differ due to potential shaping.
The objective of the Maxent IRL algorithm is to compute reward function that will generate policy (learner) тz that matches the feature expectations of the trajectories generated by the expert's policy (demonstrations, assumed to be optimal) TE Formally, this objective can be expressed as:
Maxent IRL
[xzlo(T)] [xg(d(T)],
(58)
where o, are trajectory features. E., Σ Pr. (T) ((T), where Prr. (T) is the probability distribution of selecting trajectory from Te- The original Maxent-IRI, algorithm modeled the relationship between state features and agent rewards linear, however, recent modifications now incorporate non-linear features via neural networks. To resolve the ambiguity of having multiple optimal policies which can explain an agent's 's behavior, this algorithm applies the principle of maximum entropy to select rewards yielding a policy with the highest entropy.
The ATRL algorithm uses generative adversarial networks train a policy that can mimic the expert's behavior. The IRL problem can be seen training a generative model over trajectories, such that:
AIRL:
maxJ(w) max E,wD [log Pw.
(59)
where (T) x p(so) Ii P( s,, e as) and the parameterized reward (s, a). Using the gradient of J(w), the entropy-rege reguaayyre policy objective can be shown to reduce to:
(s) ar) ( logr(arls:))
max E
(60)
The discriminator designed to take the form: (s, exp(fa ())(ssss))/))e ())p(exp(fuu(s <alss)) and the training objective aims minimize the cross-entropy loss between expert demonstrations and generated samples: L(w)= Ex= (-Ep llog (st, ar)l E.,. [log(1 - (ws ad))). The policy optimization objective then uses the reward: R(s a) = (og(Dan (s. a)) - log - D (s)
PTIRL:
The PTIRL algorithm incorporates multiple agents, each with a set of demonstrated trajecto- ries 4ps To compute rewards for each agent, PTIRL considers target and non-target trajectories. Target trajectories are demonstrated trajectories from a target agent, and non-target trajectories are demonstrated
Maxent and AIRL implementations adapted from: http:////utthhbb.m///aaaaaaa haaee///aaaaaaaaaaiieaoaaaaae
Gleave 2022
49

---

Published in Transactions on Machine Learning Research (04/2025)
trajectories from other agents. Denoting P as the probability transition function for all the agents, the linear expected reward for each trajectory is defined as:
LER(T) Σ P(sk's au, sn) r(sk', on. sk).
For each trajectory set, there is a lower bound value lb(()) and an upper bound value ub({)), defined as: Ib(p) = (ninre;(LER(T)) and ub(p) = maxrey(LERRy
respectively. From lb(() and ub(p); the spread 5 PTIRL defines a preferential ordering between any two trajectories
is defined as: ((Pa, PP) (b(pa)-ubb Fa and fPb as poset, x, such that Gpb < Pa, then 8(Pa, P6) > Given the above definitions, let yo be the set of target trajectories and Pnn the set of non-target trajectories. The PTIRL objective is compute rewards such that Puu < Pis 6(pps, (ne)) a, where is the minimum threshold for the spread. PTIRL is generally fast because it directly computes rewards via linear optimization.
C.8 Reward Classification:
Significance Tests
Table 10: Experiment 2: Welch's 's t-tests
SRRD vs DIRECT
SRRD vs EPIC
SRRD vs
Domain
Rewards
t-statistic
p-value
t-statistic
p-value
t-statistic
p-value
Manual
11.522
0
12.478
0
10.385
Maxent
28.496
28.142
2.593
0.005
Gridworld
AIRL
13.610
6.117
0
4.266
PTIRL
11.209
5.719
0
7.725
Manual
18.801
17.375
6.955
Maxent
32.341
0
12.104
0
-2.586
0.995
Bouncing Balls
AIRL
45.020
28.226
19.488
PTIRL
5.089
3.101
0.001
7.096
Manual
16.152
15.851
0
16.786
Maxent
17.829
-2.343
9.123
Drone Combat
AIRL
9.772
8.023
3.935
PTIRL
61.534
34.679
30.384
Manual
24.419
20.633
15.760
Maxent
6.171
1.717
0.04
2.233
0.013
StarCraft
AIRL
4.992
4.300
-2,913
0.998
PTIRL
6.054
3.631
4.961
Manual
4.409
0
2.23
0.01
3.04
0.001
Maxent
8.02
3.19
Robomimic
AIRL
6.24
0
4.95
0
5.59
0
PTIRL
4.27
0.65
0.16
1.18
0.04
Manual
8.97
4.58
6.54
Maxent
4.40
0
2.95
0.001
3.23
Montezuma's Revenge
AIRL
4.73
1.03
0.15
2.87
PTIRL
2.30
0.01
0.763
0.223
-0.51
0.69
Manual
5.93
0
2.89
0
1.94
0.03
Maxent
2.71
1.18
0.12
6.66
MIMIC-IV
AIRL
7.73
2.97
0
6.29
0.
PTIRL
2.14
0.02
-0.55
0.71
0.65
0.26
50

---

Published in Transactions on Machine Learning Research (04/2025)
In Table 10 show the comprehensive results for the Welch's t-tests for unequal variances, which are conducted across all domain and reward lype combinations, to test the null hypotheses: (1) MSRRD S PDIRECT, (2) μSRRD & μEPIC, and (3) USRRD S μDARD; against the alternative: (1) USRRDD > PDIRECT; (2) PSHRD > НEPIC, and (3) PSRRD > PDARD: where represents the sample mean. Generally, the tests indicate that (1) MSRRD > PDIRECT for instances; (2) PSRRD PEPIC for out of 28 instances, and (3) PSRRD PDARD for 24 out of 28 instances. These tests are performed a significant level of = 0.05, assuming normality as per central limit theorem, since the number of trials 200. In summary, we conclude that the SRRD pseudometric is more effective at classifying reward samples compared to its baselines.
Detailed accuracy scores with variability are shown in Table 11
Table 11: Experiment 2: Accuracy Scores
Domain
Rewards
DIRECT
EPIC
DARD
SRRD
Manual
69.8 + 4.6
69.3 + 4.6
70.0 + 5.0
75.8 + 4.6
Gridworld
Maxent
57.4 4.5
57.5 4.5
68.9 4.5
70.0 4.4
AIRL
82.3 3.0
84.9 1.8
85.0 2.6
86.2 2.7
PTIRL
82,2 + 3.5
84.2 + 3.3
83.4 =: 3.5
86.0 +: 3.3
Manual
46.5 +: 4.8
47.3 1: 4.6
52.0 1: 4.8
55.2 1: 4.5
Bouncing Balls
Maxent
39.7 3.1
46.0 1: 3.3
50.8 1: 3.2
49.9 1: 3.2
AIRL
41.2 3.4
46.1 3.9
49.8 3.3
56.3 3.3
PTIRL
70.3 4.2
71.1 4.3
69.5 4.1
72.4 4.0
Manual
67.1 1: 4.1
67.2 1: 4.2
66.2 1: 4.9
73.9 1: 4.2
Drone Combat
Maxent
70.3 +: 3.7
77.7 +: 3.8
73.2 1: 4.2
76.8 4: 3.5
ATRL
90.1 3.9
90.7 3.9
92.3 3.7
93.8 3.7
PTIRL
52.5 4.3
63.7 4.3
65.1 + 4.6
78.3 +: 4.1
Manual
65.5 + 4.6
67.4 +: 4.5
69.5 +: 4.5
76.5 d: 4.4
StarCraft II
Maxent
72.3 + 4.1
74.1 + 4.1
73.9 + 4.2
74.8 + 4.1
AIRL
75.1 4.0
75.3 4.0
78.1 3.8
77.0 3.8
PTIRL
77.2 4.1
78.1 4.2
77.6 4.2
79.6 4.0
Manual
78.2 + 7.6
80.3 + 9.3
79.5 + 7.9
82.4 + 8.6
Robomimic
Maxent
82.3 + 8.3
86.8 + 7.9
79.5 + 9.1
89.8 + 8.8
AIRL
85.9 8.7
87.1 9.1
86.3 9.7
91.8 9.5
PTIRL
80.3 7.7
83.6 8.3
83.1 8.5
84.2 8.1
Manual
66.4 7.5
70.1 1: 8.3
68.3 4: 7.7
73.5 1: 7.5
Montezuma's Revenge
Maxent
67.8 J. 8.1
69.1 .. 8.3
68.7 L. 7.4
71.2 1 7.9
AIRL
68.2 8.3
71.4 8.7
69.8 7.9
72.3 8.2
PTIRL
68.2 7.9
69.6 7.6
70.6 7.9
70.2 7.7
Manual
53.5 + 9.7
56.5 + 9.2
67.3 + 10.1
59.2 + 9.5
MIMTC-IV
Maxent
57.8 +: 8.51
59.1 +: 9.5
53.1 + 9.7
60.2 4: 9.2
ATRL
56.5 + 8.7
60.7 + 8.6
57.6 + 9.2
63.3 + 8.9
PTIRL
58.9 9.4
61.4 8.9
60.3 9.1
60.9 9.3
51


Reviews:
[{"review_id": "mmlimUe8Vi", "reviewer": "Reviewer_ZWFj", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n1. SRRD is designed to handle sparse sampling conditions, outperforming existing methods like EPIC and DARD.  \n\n2. The method is theoretically proven to be invariant to potential-based shaping.\n\n3. SRRD avoids the computational cost of policy learning, making it scalable and effective for real-world applications.\n\n4. Extensive experiments validate SRRD’s superior performance across multiple environments, even under conditions of high transition sparsity.  \n\n\n**Weaknesses**\n\nThe paper could be organised more effectively:\n\n1. The author might consider switching the second and third paragraphs in Section 1. Presenting the objective of reward comparison first, followed by its applications, could provide a clearer structure for readers. Additionally, only a brief summary of the applications could be appended to the end of the third paragraph for better flow.\n\n2. The author should briefly introduce SRRD in Section 1 and explain the rationale behind its ability to address transition sparsity.\n\n3. The Preliminaries and Approach sections include numerous definitions, propositions, and existing methods without sufficient connections, making them challenging to follow.\n\nWhile this paper appears robust, I suggest the author refine its presentation for improved clarity and readability.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces SRRD pseudometric, a robust method for comparing reward functions under transition sparsity. SRRD eliminates the need for high transition coverage by leveraging sampled transitions, making it more effective than existing methods like EPIC and DARD. It is theoretically invariant to shaping and empirically outperforms prior approaches across diverse domains, demonstrating practical utility for reward comparison and agent behaviour classification.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Could the author provide more details about the experiments? For instance, in the $20 \\times 20$ Gridworld domain, what is the specific goal of the agent, and how is the ground truth reward function defined? Including such details would clarify the experimental setup. \n\n2. I think that goal-conditioned offline reinforcement learning could serve as a valuable benchmark for reward comparison. In this scenario, the agent receives a positive reward of $1$ only when it successfully achieves the goal (e.g., controlling a robotic arm to manipulate a cube to a designated position). The sparse reward would represent the optimal reward function, and the offline dataset could consist of policy rollouts, creating an ideal setting for evaluating reward comparison methods. Do you think whether it makes sense?\n\n3. While SRRD is robust to transition sparsity, do you think its performance might still depend on the quality and representativeness of the sampled transitions? In highly sparse environments, where critical transitions may remain unsampled, could this affect the accuracy and reliability of SRRD's reward comparisons?", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "bA0iN4S7Ei", "reviewer": "Reviewer_DLvw", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strength**\n- The paper tackles a significant issue in reward function comparisons under transition sparsity, a common challenge in real-world reinforcement learning (RL) applications.\n- Sparsity Resilient Reward Distance (SRRD) pseudometric is theoretically innovative and addresses a gap in prior methods like EPIC and DARD.\n- I appreciate that the authors provide detailed theoretical justifications for SRRD, including its robustness to transition sparsity.\n- I also like the comment after each theoretical results, which help reader for intuitively understanding \n\n**Weakness**\n- All the figures are poorly plotted. The authors should use vector graphics during plotting. The most of the figures blur when enlarged. \n- The paper’s structure is dense and could benefit from a clearer separation between theoretical developments, empirical studies, and practical implications\n- I found it is confusing why the authors directly choose Gridworld, Bouncing Balls, Drone Combat and etc. as the testing platform. There is  no justification for the experimental setup, nor why these environments would sufficiently demonstrate the applicability of SRRD in real world problems. In fact, without exploration with real-world related experiments, it is difficult to see how SRRD would have some solid impact, e.g. military scenarios mentioned during introduction.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces the Sparsity Resilient Reward Distance (SRRD), a pseudometric designed to robustly compare reward functions in reinforcement learning under transition sparsity, where data coverage is limited due to sampling challenges or feasibility constraints. SRRD eliminates the need for high transition coverage by leveraging observed transition distributions and maintaining shaping invariance, ensuring accurate comparisons even with sparse or biased data. Theoretical guarantees for SRRD’s robustness are provided, and extensive experiments across multiple domains (e.g., Gridworld, StarCraft II) demonstrate its superiority over existing methods like EPIC and DARD, particularly in scenarios with sparse transitions.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- More experiments are needed both in simulated environment and real world applications. The author should justify why the experimental platform are chosen and why that testbeds results would imply the applicability of the proposed methods in real world scenarios. For example, include experiments on real-world datasets with inherent sparsity (e.g., healthcare or autonomous driving). Additionally, consider Atari game series for benchmarking, e.g. Montezuma's revenge. \n- Simplify the mathematical derivations or provide intuitive summaries alongside the equations.", "broader_impact_concerns": "No concern.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "0sCV3WDV7T", "reviewer": "Reviewer_TrYj", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Disclaimer: I am not an expert in reward shaping or metrics and I cannot fully evaluate the correctness of this paper. \n\n**Strengths:**\n - This paper addresses an important problem. Since reward functions dictate agent behaviors, direct reward comparison without computing the policies or value functions can provide important information to practitioners that design RL agents.\n - This paper meticulously reviewed existing work and their technicality. Based on the survey in Section 3, the authors pointed out a drawback of DARD with a didatic example that it requires high sample coverage which is intractable for large-scale problems.\n - The authors provided comprehensive theoretical justifications as well as sample-based version for the proposed method.\n\n**Weaknesses:**\n - Because I am not an expert in this area, I find it hard to fully follow and appreciate the technical details the authors scattered in Section 3 and 4.  I was lost several times when trying to get through Section 3. The current draft has 19 pages which falls into the long paper category of TMLR, and in my opinion much of it can be moved to the appendix to keep the main story succinct. I believe it would help the reader to get to the point faster by having less than 12 pages in the main text so it becomes a short paper. This can be done by for example, merging Section 3.1-3.3 that provide preliminaries and Section 3.4 - 3.5 that discusses EPIC and DARD. Section 3.6 is okay as it reveals the claimed drawback of DARD. But having so much text in Section 4 before 4.1 seems a bit awkward from a paper structure viewpoint. The paper could benefit from clearly stating its proposal and key points to note in Section 4, followed by a list of proofs in a separate section. This way a reader like me can still appreciate the key idea without needing to wade through the technical part.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Reward functions govern the behavior of agents and therefore a sense of reward similarity is helpful in discerning how similar agent-learned behaviors are. This paper comprehensively reviewed the existing work EPIC and DARD on how they approached the problem, followed by the proposal to address their drawback of assumed high sample coverage. The authors provided many proofs to justify the proposed SRRD.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please refer to the weakness section above for my requested changes. I believe the paper can benefit from streamlining the main text into 12 pages so it becomes a short paper in TMLR.", "broader_impact_concerns": "Not applicable", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Though all reviewers agreed that the paper had sufficient evidence and a substantial audience, some of the reviewers expressed a concern about the paper's clarity. The paper is indeed technically dense. The authors made substantial revisions to the paper in response to these concerns, streamlining some sections, adding more intuition in the discussion, and moving some proofs and derivations to the appendix. Based on my own reading of the revised manuscript (aligning with one of the reviewer's assessment), I believe that, though the paper does require active engagement from the reader to follow the theoretical discussion, it is sufficiently clear and readable (and provides sufficient high-level discussion) to reach its audience.
Decision: Accept (poster)