Towards the Transferability of Rewards Recovered via Regularized Inverse Reinforcement Learning
Authors: Andreas Schlaginhaufen
Maryam Kamgarpour
Venue: NeurIPS 2024 poster (2024)
Keywords: Inverse reinforcement learning
Transferability
Identifiability
Robustness
Alignment
Primary area: reinforcement_learning

Abstract: Inverse reinforcement learning (IRL) aims to infer a reward from expert demonstrations, motivated by the idea that the reward, rather than the policy, is the most succinct and transferable description of a task [Ng et al., 2000]. However, the reward corresponding to an optimal policy is not unique, making it unclear if an IRL-learned reward is transferable to new transition laws in the sense that its optimal policy aligns with the optimal policy corresponding to the expert's true reward. Past work has addressed this problem only under the assumption of full access to the expert's policy, guaranteeing transferability when learning from two experts with the same reward but different transition laws that satisfy a specific rank condition [Rolland et al., 2022]. In this work, we show that the conditions developed under full access to the expert's policy cannot guarantee transferability in the more practical scenario where we have access only to demonstrations of the expert. Instead of a binary rank condition, we propose principal angles as a more refined measure of similarity and dissimilarity between transition laws. Based on this, we then establish two key results: 1) a sufficient condition for transferability to any transition laws when learning from at least two experts with sufficiently different transition laws, and 2) a sufficient condition for transferability to local changes in the transition law when learning from a single expert. Furthermore, we also provide a probably approximately correct (PAC) algorithm and an end-to-end analysis for learning transferable rewards from demonstrations of multiple experts.

Towards the Transferability of Rewards Recovered via Regularized Inverse Reinforcement Learning
Andreas Schlaginhaufen SYCAMORE, EPFL andreas dadresa..callgiinaafeeeeeee....
Maryam Kamgarpour SYCAMORE, EPFL
maryam konyyannkamgarpour@@pll....
Abstract
Inverse reinforcement learning (IRL) aims to infer a reward from expert demonstrations, motivated by the idea that the reward, rather than the policy, is the most succinet and transferable description of a task (Ng et al.) 2000). However, the reward corresponding to an optimal policy is not unique, making it unclear if an IRL-learned reward is transferable to new transition laws in the sense that its optimal policy aligns with the optimal policy corresponding to the expert's true reward. Past work has addressed this problem only under the assumption of full access to the expert's policy, guaranteeing transferability when learning from two experts with the same reward but different transition laws that satisfy a specific rank condition [Rolland et al. 2022). In this work, we show that the conditions developed under full access to the expert's 's policy cannot guarantee transferability in the more practical scenario where we have access only to demonstrations of the expert. Instead of a binary rank condition, we propose principal angles as a more refined measure of similarity and dissimilarity between transition laws. Based this, we then establish two key results: 1) a sufficient condition for transferability any transition laws when learning from at least two experts with sufficiently different transition laws, and 2) a sufficient condition for transferability to local changes in the transition law when learning from a single expert. Furthermore, we also provide a probably approximately correct (PAC) algorithm and an end-to-end analysis for learning transferable rewards from demonstrations of multiple experts.
Introduction
Reinforcement learning (RL) has achieved remarkable success in various domains such as robotics (Hwangbo al., 2019] autonomous driving (Lu al.! 2023), or fine-tuning of large language models [Stiennon et al. 2020) Despite these advances, key challenge lies in designing appropriate reward functions that reflect the desired outcomes and align with human values. Misaligned rewards can lead to suboptimal behaviors [Ngo et al.) 2022]. undermining the potential benefits of RL in practical scenarios. Inverse reinforcement learning (IRL), also known inverse optimal control Kalman 1964] or structural estimation |ust 1994]. addresses this problem by inferring a reward from demonstrations of an expert acting optimally in a Markov decision process (MDP).
Compared to behavioral cloning [Pomerlcau 1988), which directly fits a policy to the expert's demonstrations, IRL is believed to provide Øt al. 2000). as recovering the expert's underlying reward would enable us to train policy in a new environment with different dynamics. However, it is also known that the reward corresponding to some optimal policy is not unique [Ng al., 1999], making it difficult to recover the expert's 's true underlying reward. This raises the question: Is a reward recovered via IRL transferable new
transferable description of the expert's task (Ng
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

environment in the sense that its optimal policy aligns with the expert's 'ss true reward? For example, in autonomous driving, could we effectively reuse a reward learned from demonstrations of one car in a given city to train or fine-tune policy for another car in another city?
Ensuring transferability is challenging, as neither the optimal policy corresponding to a reward the reward corresponding to an optimal policy is unique. This leads to trivial solutions to the IRL problem, such as constant rewards that make all policies optimal. Common approaches address this challenge include characterizing the entire set of rewards for which the expert is optimal [Metelli al. 2022]. or assuming the expert is optimal with respect to an entropy regularized RL problem [Ziebart] 2010]. leading to many popular IRL and imitation learning algorithms (Ho and Ermon 2016 Fu et al. 2017] Garg al. 2021]. I. Entropy regularization results in unique and more uniform optimal policy, serving as a model for the expert's 's bounded rationality [Ortega et al.) 2015].
In the entropy-regularizzed setting, several recent works study the set of rewards for which given expert policy is optimal. In particular, CCo et al. (202T], Skalse et al. (2023) show that under entropy regularization. the expert's reward can be identified up so-called potential shaping transformations
[Ng et al. 1999]. The authors of [Schlaginhaufen and Kamgarpour 2023] extend this result to more general steep regularization. Furthermore, they show that guarantee transferability to any transition law, the expert's 's reward needs to be identified up to a constant. The latter can be achieved either by restricting the reward class, e.g.. to state-only rewards [Amin et al.) 2017 or by learning from multiple experts with the same reward but different transition laws, given that specific rank condition is satisfied [Cao al., 202T Rolland et al., 2022]. However, the above results cannot be applied directly in practice, as they rely on having full access to the experts" policies, whereas in practice, we typically only have a finite set of demonstrations available.
Contributions
We consider the framework of regularized IRL (Jeon et al. 2021 and address the transferability of rewards recovered from a finite set of expert demonstrations.
We define a novel notion of transferability (Definition to address the practical limitation of not having perfect access to the experts' policies. Furthermore, we show that when learning from finite data, the conditions developed under full access to the experts' policies are not sufficient to guarantee transferability (Example 3.3)
Instead of a binary rank condition, we propose to use principal angles to characterize the similarity and dissimilarity between transition laws (Definition 3.8). Based on these principal angles, we then establish two key transferability results: 1) guarantee for transferability any transition laws when learning from at least two experts with sufficiently different transition laws (Theorem 3.10). and 2) a guarantee for transferability to local changes in the transition law when learning from single expert (Theorem B.11.
Assuming oracle access to probably approximately correct (PAC) algorithm for the forward RL problem, we provide PAC algorithm for the IRL problem, which in ((K2/E2) steps recovers a reward for which, with high probability, all K experts are é-optimal (Theorem 4.1] Together with our results on transferability, this establishes end-to-end guarantees for learning transferable rewards from a finite set of expert demonstrations.
We experimentally validate our results a gridworld environment (Section
2 Background
Notation Given z and y in some Euclidean vector space V, we denote the p-norm by ||æ||pp- the orthogonal projection onto closed convex set X' c by [xx(z)= arg minyex ||x yll2, and the standard dot product by (z, y). For a linear operator A, we denote its image and rank by im A and rank A, respectively. Given for the set of all functions mapping from X' to y. Additionally, we denote Ax for the probability simplex over X' and 1 for the indicator function. The interior int X, the relative interior relint. X, the relative boundary relbd X, and the convex hull conv X' of some set X' are defined in Appendix A along with an overview of all other notations.
sets X and Yr we denote X' + 3/ for their Minkowski sum and y
'The code is openly accessible at httppp////stttbbooo/////////a/tt
2

---

Regularized MDPs We consider regularized MDP [Geist et al., 2019] defined by tuple (S,A, P,Y0,7, Y; v,h). h). Here, S and A represent finite state and action spaces with |S] [A] Vo E Ag the initial state distribution, E A the transition law, r IRSAA the reward, and (0, 1) the discount factor. Furthermore, h X + R is strictly convex regularizer that is defined on a closed convex set C R- with relint A S int X. Starting from some initial state 50 ~ vo the agent can at each step in time i, choose action d, A. will arrive in state 1 P(-(se, 0e), and receives reward r(tt, at). The goal is to find Markov policy æ E A maximizing the regularized ob- jective E,, |> 2 (r(s 0e) h (TT-|s²))]] Following the classical linear programming approach to MDPs Puterman 2014), this can be cast equivalently as the convex optimization problem
max J(; with J(r, == (r. p4) h(w),
(O-RL)
μEM
where M denotes the set of occupancy measures, n² (1-7)) (Ei= ('
a)).
and we have h(4) := (s,,)== [h(*" (-1s)),, with x" being the policy corresponding l (see Appendix[A] A).. The set of occupancy measures is characterized by the Bellman flow constraints
M= E A (E pp= (1- >) S ASXA
-1
where E' R RSxA and P R + SxA are the linear operators mapping E R$ to (Ev) a) = vs)) and (Pu)(s, = E.' P(s'|s, a)u(s'), respectively.
Due to the strict convexity of h, the regularized MDP problem has a unique optimal policy Geist al.) 2019], hence guaranteeing the uniqueness of the optimal occupancy measure in (O-RL). In addition, we assume that the gradients of h become unbounded towards the relative boundary of the simplex as detailed in Assumption 2. helow.
Assumption 2.1 (Steep regularization). Suppose that h: : + TR is differentiable in int X' and that lim;-420 Vh(pt)ll2 = do if (pi)tes is a sequence in int X' converging point p E relbd A
Assumption 2.J ensures that the optimal policy is non-vanishing, and together with Assumption 2.2 below, we also have that the optimal occupancy measure is non-vanishing.
Assumption 2.2 (Exploration). Let v(s) == 2(s, a) 2 Mmin for any S and μ E M.
One way to guarantee Assumption 2.2 to impose lower bound the initial state distribution Vo- In the following, it will be convenient to denote the optimal solution to (O-RL) for the reward r as
RL(r) argmax J(r, 14)
HEM
and the suboptimality of some occupancy measure 4 for the reward as
SubOpt(r, p)) == max J(r, J(r ((r,
(I)
P'EM
That is, p - RL(r) if and only if SubOpt(r, (1) 0. =
Remark 2.3. As we aim to analyze the transferability of rewards to new transition laws P E A AxA it will often be useful explicitly specify the dependency on P. We do by adding subscript e.g. we write Mp, RLp, and SubOptp. However, for better readability, we drop these subscripts whenever there is potential for confusion.
Inverse reinforcement learning Given a dataset of trajectories sampled from an expert ff that is optimal for some reward F the goal in IRL is to recover reward f R, within predefined reward class R C S such that the expert is optimal for That is, ideally, we aim to find a reward the feasible reward set
IRL(2 = fo R: F RL())))
However, since we don't have direct access to the expert's policy but only to finite set of demon- strations, the best we can hope for is an algorithm that with high probability outputs a reward f E R such that SubOpt(f. F) is small - i.e. algorithm that is PAC [Syed and Schapire 2007).
3

---

Reward equivalence The reward corresponding to an optimal occupancy is not unique. For example, all rewards in the affine subspace + U, where U == im im(E E P the subspace of so-called potential shaping transformations, correspond to the same optimal occupancy measure [Ng et al. [999]. From a geometrie perspective, the subspace 21 im(F: F2 - > P) lies perpendicular to the set of occupancy measures M. Therefore, adding an element of 2/ to the reward leaves the performance difference between any two occupancy measures invariant. Hence, it often convenient to consider these rewards as equivalent [Kim al. [021] and to measure distances between rewards in the resulting quotient space. Given linear subspace V c RSxA the quotient space IR$ 1g5xA/V is Pr--reaa the set of all equivalence classes [rlv := {r' E R55A r' - T v). which is itself a vector space with addition and multiplication operation defined by [rly + [r'ly [r r'Iv and c[rly [crly for e E I. Intuitively, R /V is the vector space obtained by collapsing V to zero, or in other words, it isomorphic the orthogonal complement of V. We endow IR //V /x///V with the quotient norm ||[r|/|| == min ||r + 2||2 = |[]ba and we say that and r' are close in R if [|[]] - [r]vll is small. Moreover, the expert's reward is said to be identifiable up to some equivalence class H-ly if IRL( [ [-5] y. In this paper, we will consider the equivalence relations induced by constant shifts, i.e., V = = {r E RSxA r(s, a)
R]. and by potential shaping transformations, ie., V = U. Note that since 1 is subspace of U and 2/ is dimeenmnss,,,l,,, [r] is strict subset of [rlu whenever |S| 1.
3 Transferability
In this section, we present our main results on transferability in IRL. To this end, we first introduce the problem of learning e-transferable rewards from multiple experts acting in different environments.
3.1 Problem formulation
Let R SxA be a compact reward class, and suppose we are given access to expert data sets,
N coD
DE =
50 k.4 ,00 HF
R.d
N.K HF
l 0......, K 1,
consisting of trajectories sampled independently from the experts p= pxx Each expert is optimal for the same unrevealed reward F E RR but under different transition laws, pD pk - Our goal is to recover a reward E R that transferable across a set of transition laws P S A AxA Specifically, the optimal occupancy measure corresponding to , should remain approximately optimal for F under every transition law in P. This yields the following definition e-transferability.
Definition 3.1 (e-transferability). Fix some E > We say that f is e-transferable to some set of transition laws P A5xA if SubOpt (r RF)( S for all P P. We say that i is exactly transferable to P if it is t-transferable to P with E 0.
The error margin of is crucial, exact transferability is unrealistic when learning from finite expert data. Moreover, note that Definition 3.1 is definition of uniform transferability, as it requires i to be e-transferable any P P with the same fixed E. In the following, we will analyze the transfcrability of reward f for which all experts are é-optimal for some é > 0. That is,
SubOptp (f, (px) E k= K-
(3)
In particular. we aim to establish appropriate conditions for choosing é so guarantee transferability to some set of transition laws P. In Section we will then provide an IRL algorithm that, with high probability, outputs reward such that (3) holds.
Remark 3.2. As discussed in Appendix | the assumption of perfect expert optimality with respect to F can be relaxed to allow for misspecification error. All our results remain applicable in this setting but include an additional error term due to the experts' suboptimality.
3.2 Related work
Most previous work has focused on reward identifiability. For a single expert, Cao et al. [2021] Skalse
et al. 2023 Schlaginhaufen and Kamgarpour [2033] show that under Assumption 2.1 (steepness)

---

the feasible reward set 2 can be expressed as
IRL(4F)=
n ==
In other words, steepness ensures that the expert's reward is identifiable up to potential shaping. To identify the reward up constant, we can either restrict the reward class, e.g. to state-only rewards as explored by Amiin et al. [2017], or learn from multiple experts [Cao et al. 2021] Rolland et al. 2022]. particular, when we are given access to two experts, 10 and pip,, we can identify the experts' reward up to the intersection
(e r (1Fx) [r 14po n 11pp RR (r +1p num) n.R.
That is, for the unrestricted reward class, R RSXA, A_ the reward is identifiable up to a constant and only if up Umm 1. Or equivalently, if and only if the rank condition
rank (E'->P"
E E- 2|8] - 1,
(5)
is satisfied [Rolland et al. 2022]. Moreover, Schlaginhaufen and Kamgarpour [2023] show that identifying the expert's 's reward up to constant is necessary and sufficient condition for exact transferability to any full-dimensional set P C A (a set whose interior, with respect to the subspace topology x [Bourbaki 1966]. non-empty).
The above results assume perfect access to the expert's policy, which isn't realistic. In practice, we can only learn a reward for which the experts are approximately optimal. In Example (.3 below, we show that under approximate optimality of the experts, the learned reward can perform very poorly in a new environment, even if the rank condition in Equation (5) satisfied.
Limitations
Example 3.3. We consider a two-state, two-action MDP with S A {0. 1}. uniform initial state distribution, discount rate 7 = 0.9, and Shanmon entropy regularization h: = =- (see Appendix C Suppose the expert reward is , a 1{s 1) and consider the transition laws, p0 and pt defined by pd (0)s, a) = 0.75 and p1 [0]s, a) 0.25 + 3
= 0, a = 0} for some / E [0, 0.75]. Also, consider the two experts p = Ro (r and f = RL (rF), and suppose we recovered the reward f(8,a) = - Then, as detailed in Appendix the following holds: 1) We have SubOpt (f, pppp) = 0 and pubOpt (f, (f:) = ( .) That is, for small 3, the reward f is a good solution the IRL problem, both experts
approximately optimal under f. 2) The rank condition (5) between po and pl is satisfied for any 8 >> 0. 3) For a new transition law P defined by P(O)s, 8, 1 {s 1,a 0}. we have SubOptp RL)(f) As 4.81, i.e. RLp(f) performs poorly under the experts' reward.
3.3 Theoretical insights
To establish a sufficient condition for e-transferability, our goal is to bound the suboptimality of an optimal occupancy measure, RL(r), for some reward r', in terms of reward distances measured in the quotient space S x /u. To this end, we first establish the relationship between the suboptimality in Equation ① and the Bregman divergence corresponding to the occupancy measure regularization.
Bregman divergences
The Bregman divergence (Teboulle 1992 associated to defined as
D'( h(H) h(p²) (Vh(p'), -1))--
Proposition 3.4. Under Assumptions 2.7 and 2.2 we have SubOpt(r', ( Du RL(r') for any μ M.
Proposition 3.4 above demonstrates that the suboptimality of an occupancy measure y for the reward coincides with the Bregman divergence between ju and the optimal occupancy measure under r'. This generalizes (Mei et al. 2020 Lemma 26] from entropy regularization to any steeply regularized MDP. The proof is presented Appendix [.6]
Reward approximation Next, show that under strong convexity and local Lipschitz gradients, the Bregman divergence between two optimal occupancy measures is bounded terms of reward distances in S
5

---

Assumption 3.5 (Regularity). Suppose the following holds:
a) The regularizer h is n-strongly convex over the set of occupancy measures M. That is, we have
h(p') 2 h(m) + (V((),,'' -1) + 2 ll ull "u E M.
b) The gradient Vh is locally Lipschitz continuous over relint M. That is, for any closed convex subset KC C relint M there exists Lx > 0 such that
Vh(μ)) vh(p')) - LK l| lelllll-e 2'12
Yu. E
We will show later that Assumption 3.3 is met for Shannon and Tsallis entropy regularization (sce
Proposition D.9). Under the above assumption, the following lemma establishes the desired upper
and lower bound on the Bregman divergence between two optimal occupancy measures with respect to reward distances measured in R
Lemma 3.6. Suppose Assumptions 2.7 2.2 and 3.5 hold, and let r, E R. Then, we have
I[rru [r' I SubOpt(r'. RR(()) Dj (RL()),RL(r") 2n [1 [r'ull2 (6)
for some problem-dependerr constant oR >
Remark 3.7. The proof of Lemma 3.6 hinges on the duality between equivalence classes of rewards and optimal occupancy measures (see Appendix [B). The main idea is leverage duality of Bregman divergences, and a dual smoothness and strong convexity result Proposition D.7] A key challenge arises because, by Assumption 2.I the regularizer cannot be globally smooth. This results problem-dependent dual strong convexity constant OR [Goebel and Rockafellar 2008). In Propo- sition D.9 we will provide lower bound OR for the specific choices of Shannon and Tsallis entropy regularization. For more details, we refer to the full proof in Appendix
The above lemma has two key implications: First, the lower bound in (6 implies that we recover a reward f for which all experts are approximately optimal, then the distance between and nF can be bounded in the quotient spaces & pupx. Second, the upper bound shows that to control the performance of Rf) in new environment P, need tightly bound the distance between and E in S /Upp- As distances in RRSA /Upp are bounded by distances in R-SxA/LL /1, this be achieved by bounding the distance between and , in RSxA /1. However, revisiting Example 3.3 in light of Lemma 3.6 that even though and F are close in RSXA [Upp, this does not guarantee their proximity in Sx.AA /1 and SxA [RSp.
Example 3.3 (continued). Recall the definition Upa = im(E 7P)). Given that Example 3.3 and SubOpt pp:)) = ((3). Lemma 3.6 ensures that ř and r coincide in SxA /Upo, and for small B. they are close in S /Upp. However, as illustrated Fig- ( this doesn't 't ensure that f and , are close in IR //1 and S fUp. In particular, can be computed that [f]u [r ll 1.51, which by Lemma 3.6 explains the poor transfcrability P.
we have SubOpt (4)))
a)
3.4 Sufficient conditions for transferability
With Lemma 3.6 in place, we are set to present our results on e-transferability. Example 3.3 indicates
that a sufficient condition for learning transferable rewards from experts (K = 2) should not rely solely on the binary rank condition (5), which only checks if Upo U = 1. Instead, we should consider the relative orientation between Le and UpI. To formalize this, need introduce the concept of principal angles between linear subspaces, as outlined in Definition (388 below.
Definition 3.8 (Principal angles [Galántai] 2013)). Let W.W C R. be two subspaces of dimension m S n. The principal angles 0 < 01 W) and W are defined recursively via
0m (V. W) =: 0m0x W) < x between V
cos(0, W)) = max (v. w) s.t. ||e|| = ||l||| = 1, (v. Uz) = (w, w)) = 0, 1..... vEV.
where Wy. Wy are the maximizers corresponding to the angle 0,. For two transition laws P, Pt, we define (P, = ((UU,UUp)) and refer to (P, P') as the i-th principal angles between P and P'.

---

RSXA11
RSXAA1
tupl
E
+ Upl
4p0
B + Up
E up
(a) Rewards in Example 3.3
(b) Proof sketch Theorem 3.10
Figure 1: (a) illustrates the equivalence classes Ffly and [r le. corresponding to the transition laws p6 Pl, P from Example 3.3 for small 3, in R25xA/A //. The blue lines correspond to p the red lines to pl, and the gray lines to P. Furthermore, the shaded areas illustrate the approximation error around [r=]u guaranteed by Lemma 3.6 (b) illustrates the uncertainty set for the recovered reward when learning from two experts, as discussed the proof sketch of Theorem 3.10
Principal angles are the natural generalization of angles between two lines or planes to higher dimen- sional subspaces. For principal angles between transition laws, we have the following proposition.
Proposition 3.9. Let P,P E AS SXA and H. = 1/(1-2). - 7). Then, we have (P,,P = 0 and sin (0max P") H PP - P where |1-11 denotes the spectral norm.
The proof can be found in Appendix D.7 The above result shows that while the first principal angle between two transition laws is always zero, all principal angles are small if the transition laws close to one another. In Example 3.3 we have sin(O2(Po P))) = ( indicating that the second and in this case maximal principal angle small when 3 is small (see Appendix [E). The following result shows that when learning from two experts, the transferability error is directly controlled by the second principal angle between the experts' transition laws.
Theorem 3.10. Let K 2, 02(Pa) Pl) > O, and suppose that Assumptions pubOptpa (f, (px)) for l 0, 1, then f is e-transferable to P A
2.1 and 3.5 hold. If with
ě/ [ sin (02(P", (()PP,,P)) /2)
Sketch of proof. The main idea of the proof is illustrated in Figure [b). First, it follows from Lemma 3.6 that ê and E are E /28/OR -close -cosee in S / for k = 0, 1, respectively, From using basic trigonometry that this implies that f and , are at least A E/ sin( (8/2)) in S /11 As shown in the full proof in Appendix F the relevant angle, 8, is the second principal angle 02 O2 pt). The result then follows from the upper bound in Lemma 3.6
Figure 1 bb)
Some observations are in order. First, the above theorem shows that the larger the second principal angle between the experts' transition laws, the better the recovered reward transfers new environment. Second, observe that (2 pl) > O is equivalent to the rank condition
(5). as the
second principal angle between two subspaces is non-zero if and only if their intersection is most one-dimensional. Therefore, for exact transferability. Theorem 3.10 requires the rank condition (5) be satisfied and O, recovering the results by Cao et al. [2021), Rolland al. 2002)
Schlaginhaufen and Kamgarpour [2023]. But in contrast to past results. Theorem 3.10 aaappppe to more realistic scenarios, where is merely small, not zero. Finally, we note that Theorem 3.10 can be trivially generalized to K 2 2 experts by replacing (2 pi) with the maximum of (2(P Pl)
over 0 < < S K 1. However, such bounds may be loose for K potentially leaving considerable room for improvement in this setting.
Local transferability When learning reward from single expert (K = 1), |Schlaginnhaufenn and Kamgarpour 2023) show that, without reducing the dimension of the reward class, cannot be exactly transferable to any neighborhood of the expert's 's transition law Pg. However, Theorem 3.1 below guarantee transferability to neighborhood of Po.
shows that by allowing for an e of error,
7

---

Theorem 3.11. Ler K = 1, D = max, ||r 1r--rlly and suppose that Assumptions 2.1 and
3.5 hold. Subttpt (f. 5 S É. then i is e--transferable to P E A
SxA with
{ 22 / D2 sin (Omax (P P)) 21
Pp = 2 max
The above theorem (which is proven in Appendix G) shows that the reward learned from a single expert transfers to transition laws that are sufficiently close to the expert's, ss where the closeness measured in terms of the maximal principal angle. In other words, while a large second principal angle between two experts' transition laws, as per Theorem 1.100 ensures that the reward recovered from these two experts is transferable to arbitrary transition laws, a small largest principal angle between two transition laws ensures that a reward recovered in one environment can be successfully transferred to the other environment.
Remark 3.12. As discussed in Appendix H value decomposition. Moreover, given estimates po f1 of the transition laws po, Pl, the error in the estimate of sin (,(P), p1) scales with ( (| - 10 ||P1 [ P)
we can compute the principal angles using singular
Regularizers To provide more insights about Theorems 3. and 3.11 we provide explicit values for the primal and dual strong convexity constants, 17 and RR. respectively. To this end, we focus on the Shannon entropy regularization h(p) -TH(p) and the Tsallis- entropy regularization
h(p) -T71 H2/422lll (2)) as defined in Appendix C While the Shannon entropy regularization is commonly
used in IRL [Ziebart 2010 Ho and Ermon 2016 the Tsallis- entropy is more often adopted in the
multi-armed bandit literature Zimmert and Seldin [202T]. Both regularizations satisfy Assumption [2.]
as well as Assumption 3.3 with the constants detailed in Proposition D.9 in the appendix. general, the Tsallis entropy leads to slightly smaller strong convexity constant 7). but avoids an exponential dependence on the effective horizon H,, = 1/(1 - 7) in ØR. Below, we summarize the implications of Proposition D.9 for e-transferability of reward f recovered from two experts.
Corollary 3.13. Suppose the conditions in Theorem h.lO.
hold. Furthermore, let H == 1/(1-7)) (1) :: mR ||r|loo D = r' ||r r'l12. and T < D. Then, for the Shannon entropy f is e-transferable to P A with
2 D1S|LAR exp (RHH,)
V r sin (O2 P1)
for the Tsallis entropy with
AV2HADIS1LAP (2H/7 + 3//11114 (A)
3
E.
V sin (PoP(P)))/
We observe that transferability generally becomes more challenging with decreasing regularization parameter T, i.c. if the expert's policy becomes more deterministic. Furthermore, we see that is easier recover a transferable reward in Tsallis reguapy-regularized MDP. Corollary 3.13 also shows that the constant between e and é tends to be large, meaning that we need to recover a reward for which the experts are é-optimal with very small é to guarantee e-transferability for reasonable e. However, it's important to note that our results provide sufficient conditions for the worst case, and remains for future work to determine under what conditions these constants can be improved.
Remark 3. 14. Our results in this section, especially Proposition 3.4 and Lemma 3.6] are critically relying on the steepness of the regularization (Assumption 2.T). which is essential to ensure that the expert's 's reward can be identified up to the equivalence class of potential shaping transformations. Although we can still upper bound the suboptimality SubOpt(r RL (f)) ) in terms of the distance between á to E in S A/A /2/ without this assumption (see Proposition D.10). we no longer have a lower bound as in Lemma 3.6 which is essential for establishing closeness of and , in S /U.. Hence, we expect it to be difficult to obtain guarantees similar to those in Theorem (3110
3.100 and 3.1 for
the unregularized setting, without either reducing the dimension of the reward class [Amin ct al. 2017
or making specific assumptions about the feasible reward sets [Metelli et al. 2021 Assumption 4.1].
4 Algorithm
To provide end-to-end guarantees for recovering transferable rewards from a finite set of expert demonstrations, analyze the convergence and sample complexity (in terms of expert demonstra-
8

---

tions) of an algorithm for recovering a reward for which all K experts are approximately optimal.
To this end, we focus on the reward class R {r E IXSAA, ||||] S } Furthermore, we assume oracle access a (e, PP-AAC algorithm for the forward problem (O-RL). That is, polynomial algorithm, A that outputs policy A (r) such that with probability at least 1 ó it holds that SubOpt(r: )²)= Σ & (see e.g. [Lan 2023 for specific example). The key idea of our meta-algorithm is to learn a reward minimizing the sum of the suboptimalities of the K experts pfm..... p
This leads to the following multi-expert IRL problem
min TER
(r
(0-IRL)
where (8, a) = - (1-))=(101))/) i=0 EE 11 h. = 8, u = a} is an empirical expert (8, occupancy measure. To solve Problem O-IRL), we propose the projected gradient descent scheme as detailed in Algorithm below, where rolloutps (T,, N. H) samples N independent trajectories of length H from policy т. Using stochastic online gradient descent analysis, Theorem 4.1 shows that any PAC algorithm for the forward problem yields PAC algorithm for the inverse problem.
Algorithm 1: Mupei-expert IRL
Input: a, T, (DE))-I K-1 N, Eopt: Sopt- arbitrarily.
k=0
Initialize: A and for i == .....,
T'' - do
for k ...,.
do
Th,t = A Sanmma (ri)
// Forward RL.
pt
DR, = rollout pe (TKK, N, H)
end
= EK-1 (DIDe - ADEE)
F++1 1 (rt - agg:)
// Reward step.
end
Return: f== ETs rt.
Theorem 4.1. Suppose that NE S log( lo (|(A1/8//E2) and H 22 / (ogg/))) Running Algorithm for T = /(K3/EE2) iterations with step-size a =1/(KVT) where Sept = ( / k Eapt O(ē/K), N = (2(K log (| and H holds with probability at least - 8 that SubOpt (f, pp S E, for l .,...,K K
The above result generalizes [Syed and Schapire 2007 Theorem 2] by considering multiple experts and by proving convergence in terms of the expert suboptimality. We refer to Appendix for the proof and the precise constants. Theorem 4.1 shows that with ((K/E?) demonstrations of each expert, we recover in Q /g²) steps of Algorithm[] I reward for which all experts are é-optimal. Together with Theorem 3. 30 and [.II. this provides a bound on the sample and time complexity of recovering in e-transferable rewards in regularized IRL.
5 Experiments
To validate our results experimentally. we adopt stochastic variant of the WindyGridworl Id environment (Sutton and Barto 2018]. In this environment, the agent moves to the intended grid cell with probability of (1 and is pushed one step further in the direction of the wind with probability 3. Using Algorithm we recover a reward from demonstrations of two experts, both exposed to the same wind strength 3 but different wind directions North and East. The experiments are repeated for a varying number of expert demonstrations NE E {103, 10a 105 10%) and wind strengths 3 {0.01, 0.1. 0.5, 1.0). We then test the transferability to two different environments: one with South wind, pSouth and a zero-wind environment with cyclically shifted actions, pShifeed Figure 2 (a) shows that the second principal angle between the two experts' transition laws Po and

---

0.25
0.01
0.1
0.20
reward dlstauee
8
0.5
transferabiiitt
8,pp) pl)
-5
0.15
1.0
20
0.10
0.05
0.00
0.0
0.5
1.0
10a
101
10
10
10a
10'
10
10a
10a
10a
10
10
8
N
(a)
(b)
(c)
(d)
Figure 2: (a) shows the second principal angle between the experts, for varying wind strength B. (b) shows the distance between f and , in IR R /
for a varying number of expert demonstrations NE and wind strength B. (c) and (d) show the transferability to PSouth and pStitedd in terms of SubOpt (r=, pson (f)) and SubOpt paitee (r panee (f)), respectively. The circles indicate the median and the shaded areas the 0.2 and 0.8 quantiles over 10 independent realizations of the expert data.
Pi increases with increasing wind strength. Moreover, Figure ((b)-(d) show that both the closeness between f and of in RSxA/11 /1 and the transferability to pSeat and PSiiiteed improve with a larger second principal angle, as expected from Theorem 3.10 For more detailed discussion of the experiments we refer to Appendix K
6 Conclusion
Summary In this paper, we investigated the transferability of rewards in regularized IRL. We showed that the conditions established under full access the experts' policies do not guarantee transferability when learning a reward from a finite set of expert demonstrations. To address this issue, we proposed using principal angles more refined measure of the similarity and dissimilarity of transition laws. Assuming strongly convex and locally smooth regularization, we then showed that if we recover reward for which least two experts are nearly optimal, and their environments are sufficiently different in terms of the second principal angle between their transition laws, then the recovered reward is universally transferable. Furthermore, we showed that if two environments are sufficiently similar in terms of the maximal principal angle between their transition laws, rewards learned in one environment can be effectively transferred the other environment. Additionally, we provided explicit constants for the Shannon and Tsallis entropy, as well PAC algorithm for recov- ering reward for which experts are approximately optimal. As result, we established end-to-end guarantees for learning transferable rewards in regularized IRL. Additionally, we experimentally validated our results through gridworld experiments.
Limitations and future work Our results provide only sufficient conditions for transferability. would be valuable to investigate necessary conditions to check whether our bounds are tight. Furthermore, extending our analysis to lower-dimensional reward classes could reduce the complexity of learning transferable rewards. Although our paper focuses on discrete state and action spaces, exciting avenue for future research would be to extend spaces, which are more commonly encountered in practice. We expect that our proof methods can be generalized this setting, but the analysis will be more intricate due the infinie-diimensional reward and occupancy measure spaces. Finally, as our work is mainly theoretical, experimental validation on real-world applications could provide valuable insight into the practical aspects and challenges of transferability.
results to continuous state and action
Acknovledgments Andreas Schlaginhaufen is funded by PhD fellowship from the Swiss Data
Science Center.
10

---

References
Abbeel and A. Y. Ng. Apprenticeship learning via inverse reinforcement learning. Proceedings of the twenty-first international conference on Machine learning, 2004.
K. Amin, N. Jiang, and S. Singh. Repeated inverse reinforcement learning. Advances neural information processing systems, 2017.
A. Beck. First-order methods in optimization. SIAM, 2017.
N. Bourbaki. Elements of mathematics: General topology. Hermann, 1966.
P. Boyd and Vandenberghe. Convex optimization. Cambridge university press, 2004.
H. Cao, S. Cohen, and L. Szpruch. Identifiability in inverse reinforcement learning. Advances in Neural Information Processing Systems, 34, 2021.
T. M. Cover. Elements of information theory. John Wiley Sons, 1999.
C. Dann, C.-Y. Wei, and J. Zimmert. Best of both worlds policy optimization. arXiv preprint 230.::3300.09008, 2023.
Z. Drmac. On principal angles between subspaces of euclidean space. SIAM Journal on Matrix Analysis and Applications, 2000.
Fu, Luo, and S. Levine. Learning robust rewards with adversarial inverse reinforcement learning. arXiv preprint arXiv: 2017.
A. Galántai. Projectors and projection methods. Springer Science & Business Media, 2013.
D. Garg, S. Chakraborty, C. Cundy, J. Song, and S. Ermon. Iq-learn: Inverse soft-q learning for imitation. Advances in Neural Information Processing Systems, 2021.
M. Geist, B. Scherrer, and O. Pietquin. A theory of regularized markov decision processes. In International Conference on Machine Learning. PMLR, 2019.
R. Goebel and R. T. Rockafellar. Local strong convexity and local lipschitz continuity of the gradient of convex functions. Journal of Convex Analysis, 2008.
Ho and Ermon. Generative adversarial imitation learning. Advances in neural information processing systems, 2016.
W. Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 1963.
J. Hwangbo, J. Lee, A. Dosovitskiy, D. Bellicoso, V. Tsounis, V. Koltun, and M. Hutter. Learning agile and dynamic motor skills for legged robots. Science Robotics, 2019.
W. Jeon, C.-Y. Su, P. Barde, T. Doan, D. Nowrouzezahrai, and J. Pineau. Regularized inverse reinforcement learning. In International Conference Learning Representations, 2021.
Ji-Guang. Perturbation angles between linear subspaces. Journal of Computational Mathematics, 1987.
R. Kalman. When Linear Control System Optimal? Journal of Basic Engineering, 1964.
K. Kim, S. Garg, K. Shiragur, and Ermon. Reward identification inverse reinforcement learning. In Proceedings of the 38th International Conference Machine Learning, pages 5496-5505, 2021.
A. V. Knyazev and M. E. Argentati. Principal angles between subspaces in an a-based scalar product: algorithms and perturbation estimates. SIAM Journal on Scientific Computing, 2002.
G. Lan. Policy mirror descent for reinforcement learning: Linear convergence, new sampling complexity, and generalized problem classes. Mathematical programming, 2023,

---

Y. Lu, J. Fu, G. Tucker, X. Pan, E. Bronstein, R. Roclofs, B. Sapp, B. White, A. Faust, S. Whiteson, al. Imitation enough: Robustifying imitation with reinforcement learning for challenging driving scenarios. In 2023 IEEF/RSJ International Conference Intelligent Robots and Systems (IROS), 2023.
J. Mei, C. Xiao, C. Szepesvari, and D. Schuurmans. On the global convergence rates of softmax policy gradient methods. In International conference on machine learning. PMLR, 2020.
A. M. Metelli, G. Ramponi, A. Concetti, and M. Restelli. Provably efficient learning of transferable rewards. In International Conference on Machine Learning. PMLR, 2021.
A. Y. Ng. D. Harada, and Russell. Policy invariance under reward transformations: Theory and application to reward shaping. In lcml, 1999.
A. Y. Ng, S. Russell, et al. Algorithms for inverse reinforcement learning. In Icml, 2000.
R. Ngo. L. Chan, and S. Mindermann. The alignment problem from a deep learning perspective. arXiv preprint arXiv:2209.0000 000666, 2022.
P. A. Ortega, D. A. Braun, J. Dyer. K.-E. Kim, and N. Tishby. Information-theoree theoretic bounded rationality. arXiv preprint arXiv: 1512.0679,, 2015.
R. Ouhamma and M. Kamgarpour. Learning nash equilibria in zero-sum markov games: A single time-scale algorithm under weak reachability. arXiv preprint arXiv:2312.08008, 2023.
R. Penrose. generalized inverse for matrices. In Mathematical proceedings of the Cambridge philosophical society. Cambridge University Press, 1955.
D. A. Pomerleau. Alvinn: An autonomous land vehicle in a neural network. Advances neural information processing systems, 1988.
M. L. Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
R. T. Rockafellar. Convex Analysis. Princeton University Press, 1970.
R. T. Rockafellar and R. J.-B. Wets. Variational analysis. Springer Science & Business Media, 2009.
Rolland, L. Viano, Schürhoff, B. Nikolov, and Cevher. Identifiability and generalizability from multiple experts in inverse reinforcement learning. Advances in Neural Information Processing Systems, 2022.
J. Rust. Structural estimation of markov decision processes. 3081-3143, 1994.
Handbook of econometrics, pages
A. Schlaginhaufen and M. Kamgarpour. Identifiability and generalizability in constrained inverse reinforcement learning. In Proceedings of the 40th International Conference Machine Learning. PMLR, 2023.
J. M. V. Skalse, M. Carrugia-Robert S. Russell, A. Abate, and A. Gleave. Invariance in policy optimisation and partial identifiability reward learning. International Conference on Machine Learning. PMLR, 2023.
N. Stiennon, L. Ouyang, J. Wu, D. Ziegler, R. Lowe, C. Voss, A. Radford, D. Amodei, and P. F. Christiano. Learning to summarize with human feedback. Advances in Neural Information Processing Systems, 2020.
R. Sutton and A. G. Barto. Reinforcement learning: An introduction. MIT press, 2018
U. Syed and R. F. Schapire. A game-theoretic approach to apprenticeship learning. Advances in neural information processing systems, 2007.
M. Teboulle. Entropic proximal mappings with applications to nonlinear programming. Mathematics of Operations Research, 1992.
12

---

B. D. Ziebart. Modeling purposeful adaptive behavior with the principle of maximum causal entropy. Carnegi Mellon University, 2010.
Zimmert and Seldin. Tsallis-inf: An optimal algorithm for stochastic and adversarial bandits. The Journal of Machine Learning Research, 2021.
M. Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In
Proceedings of the 20th international conference on machine learning (icml-03), 2003.
13

---

Appendix
Table of Contents
A
Notations
15
Conjugate duality in regularized TRI.
16
Regularizers
D
Technical Lemmas
17
D.1
Lipschitz continuity from policies occupancy measures
17
D.2
Strong convexity
18
D.3
Lipschitz gradients
19
D.4
Dual smoothness and strong convexity
22
D.5
Regularity constants
24
D.6
Suboptimality bounds
24
D..
Perturbation bounds
25
E
Proof of claim in Example 3.3
26
Proof of Theorem 3.10
28
Proof Theorem 3.11
30
Estimating principal angles
30
Proof of Theorem14.1
31
Suboptimal experts
33
Experimental details
34
14

---

A Notations
Overview Here, provide an overview of some of the most important notations. However, every notation is defined when introduced as well.
Table 1: Notations.
set of functions f X' +
Ax
probability simplex over some discrete set A'
M
set of feasible occupancy measures
R
{r E RSXA
||]] < 1). reward class
R
maxreR ||r| |oo reward bound
D
maxi || 2. diameter of the reward class
Hg
= 7)), effective horizon
v(s)
= (s)
p(ss Eur M(s, u(s,
v(s) >
(a(ss)
1/|Al (arbitrary)
otherwise
((1s)
n
M(4)
B( [M(T(')
J(r
(r,H) h(p)
SubOpt(r, p²)
maxpEM [r. p1) J(r,p')
RL(r)
argmax,ee (r, p), optimal occupancy measure for
(RL(25)
f== 1 {rER: R;
=LL))) feasible reward for j.E
Ar)((r)
PAC RL algorithm outputting some s-optimal policy with probability at least - 5
1-3 D.'' 1'1 {st of a). where D = {(b), ag.... ... 8/1 a2- -1) N
@DD
E
linear operator R SxA defined by (Ef)(s, ((8) for f IRS
P
linear operator R SxA defined by (Pf) E.. P(''l8, a))(s') for E ERS
im (A)
image of a linear operator
U
=
im( - 7PP) C SxA potential shaping subspace
[ constant) SxA. constant subspace
orthogonal complement of a linear subspace V
Additional definitions we denote B(x, r) := (x RD ||>||| < r) for an open ball of radius with center ar
the following, we briefly recall some additional definitions. this end,
Definition A.1 (Interior). The interior of set X' C R." is defined int X' {a X: B(z, r) C X for some > 0).
Definition A.2 (Affine hull). The affine hull of a set X R2" defined as aff x= [0 Definition A.3 (Relative interior). The relative interior of set X' C R" is defined as relint = (ar E X B(x,, O aff X C X' for some
0g. +... #1. FA E X, 0 +... + 0g = 1
0}.
Definition A.4 (Relative boundary). The relative boundary of closed set X R2 is defined as relbd = X \ relint X.
Definition A.5 (Convex hull). The convex hull of a set X' C 1. is defined as
conv X' = {0,z) + + O2TZ I1, E X, 01 + ... 0g 1,0; > 0, 1....,k) k}.
15

---

B Conjugate duality in regularized IRL
In this section, we first recall some background from convex analysis and then briefly discuss the duality between reward equivalence classes and optimal oceupancy measures.
Definitions We recall a few definitions related to convex functions. convex analysis it is standard to consider extended real value functions f I T == [-xc, 20], where convex functions defined on some subset X I_ are extended over the entire space by setting their value to +oo outside of their domain. The effective domain is defined as dom ff := {a f(z) < oo), , and a convex function and dom f * 0. Furthermore, f is referred to closed if its
is said to be proper if f epigraph {ax, y) : x E dom f. y 2 f(x)] is a closed set f In particular. f closed it is continuous on dom and dom is closed set (Boyd and Vandenberghe [004]. Lastly, recall two key concepts in convex analysis the subdifferential and the convex conjugate of some convex function.
Definition B.1 (Subdifferential. A subgradient of f IR R some point x E R is vector E Rn such that ((x') 2 f(x) + g (xr x) for all x' E X. The subdifferential (f(x) at a E X the set of all subgradients r, where 0f(x) is defined to be empty if x: & dom f-
Definition B.2 (Convex Conjugate). The convex conjugate of f R + R is the function f"
Rn + R defined as
f = suply. 2) f(z).
Key results Next, we list two key results from convex analysis.
Theorem B.3 (Rockafellar 1970). A function f R" R is differentiable at some point I E dom f if and only if f((z) is singleton. this case we have 0f(z) = {V)(
Theorem B.4 (Roocafellar 1970). For any proper convex function f: 1R R holds
f*(y) = (),z) - f(x)
=
y E @f()..)
additionally is closed, then
(0( x) - f(x)
=
y yEOf(r)
x x E)
Duality in IRL. Let f RSSAA_ + Rh be given by f= h + 8M, where 8M is a characteristic function defined as (m) = 0 0f μ E M and (M(()) = co, otherwise. Since f is closed proper convex, Theorem B.3 and B.4 imply that for a strictly convex i we have
RL(r) (r) and IRL(μ) 0f()) nR.
Additionally, under Assumption 2.1 and Slater's condition, which is ensured by Assumption 2.2 we have O (f)) Vh(uu)+ +u (Schlaginhaufen and Kamgarpour 22023]. Hence, is optimal for 1l and only r Vh(μ))u Therefore, there is a one-to-one mapping between elements of the quotient 15xAA/24 /U,, i.e. reward equivalence classes, and corresponding optimal occupancy measures in M. This mapping is given by
space R.xA
V SXA (5xA|U- M, V/ RR((r)
and its inverse by
0ʃ: : Mf:M- M SxA R 11,
-v(])) +u.
C Regularizers
We dedicate this section to discuss optimal policies in regularized MDPs and to recall their explicit form for Shannon and Tsallis entropy regularization.
A proper convex function is closed if and only if it is lower semi-continuous [Rockafellar 1970
16

---

Optimal policies
Throughout the appendix, it will convenient to use the notation T, == (-)ss). Given some proper closed strongly convex policy regularizer h, it can be shown [Geist et al. 2019 that the optimal policy, x²", satisfies
T = Vh (4
(T. 9.) h(TT), Vs S, x,EAA
where og E RR- the optimal q-function defined via
(a) = (s, a) = max Er
r(st, ai) +
Σ y¹ [r(s), ar) - h(T=)] so = 8, ag = a
TEAX
121
Next, we discuss the explicit form of T. = Vh (qt) for the specific cases of Shannon and Tsallis-1/ 1/2 entropy regularization.
Shannon entropy For some where
0, we define the Shannon entropy regularizer as h == -TH.
H(m,) ==
Σ (T(a) log (a))
is the Shannon entropy satisfying 0 < H < log [A]. It can be shown that h is r-strongly convex with respect to ||-II Cover 1999], and the optimal policy satisfies GGest et al. 2019
exp (8"(8, a)/T)
" (als) = Ea exp (q" (s, a')/))
Tsallis entropy For some parameter a E I, the Tsallis entropy, Ha. is defined as
Ha
a 1- mT(aa")
--Em((a))
In the limit - 1, the Tsallis entropy equals the Shannon entropy defined above. However, in this paper, we use Tsallis entropy to refer to the choice a 1/2, which is often adopted as regularization multi- bandit and, more recently, policy optimization algorithms [immert and Seldin 2021
Dann et al. 2023]. That is, consider h(T,,) 1
-2r E. VT - 1) for some
0. We have -h s 2r (VLAI - 1) and it can be shown that the optimal policy satisfies
2
(als) Jg - 9" (8, ()
where F, is a normalization parameter such that Σ. n (a|s) = Zimmert and Seldin 2021]. Furthermore, since has diagonal Hessian V² = (2 it T /22-strongly convex with respect to I|-ll2 and hence also 7
convex with respect to ||-
D Technical Lemmas
In this section, we show several new technical results that are required for the proofs of our main theorems.
D.1 Lipschitz continuity from policies to occupancy measures
Proposition D.1. Let Assumption 2.2 hold. For any μ1, P2 E M. we have
(-7) [| 12ll 1| & max || m
<
I1 - |2111
Vmnin
Proof. To show the first inequality, we decompose
|| - Hell z Σ (at* - =
Σ (12(()) - (2(+))=="<all))
8,0
< max m| - Tll + |lu u2l1
17

---

where we used the triangle and Hölder's inequality. From the Bellman flow constraints,
= - P(ols', d') + +1 >))
8'
it follows that where we again used the triangle inequality. Hence, we have
| 12l1 = Σ
Σ P(sls', d') v2(6',a'))
P(s|s', ,') 1un(s' 22((((a'))
=y 11 Mall
max | - = 2 || ا2ll - ||u1 - -2l1 2 (1 - ||l - #2111
To show the second inequality, we use the reverse triangle inequality
|1 Hell1 N (T" nT (a|s))
Σ (12(() (2(s))
Σ "1 (s) |TT TTa ||| || 1/2111
2 M min max
T |1 Mell
where in the last step we used again that || 12l11 S y Il u2ll1- By rearranging terms arrive at the desired inequality
1+7 Vmin
2 Mmni
max
T
11 12l11 S
11m1 Mell
D.2 Strong convexity
Next, we show that strong convexity of the policy regularizer translates into strong convexity in the occupancy measure.
Proposition D.2 (Strong convexity). Let Assumption 2.2 hold and suppose that h is mh -tronrrygly convex with respect the ||-II, norm. Then, h is mp Miin H H -stoonly convex with respect to II-I1y-
Proof. We need to show that for a E (0, 1),1), ā 1 and any two μi, 112 E M it holds that
h(pp -212) s ah(pi) ah(p2)
|| 12ll
2
18

---

for 1) = miii H..- To this end, we start similarly as in the proof of strict convexity by Schlagin haufen and Kamgarpour (023), but use v(s) 2 V/min and strong convexity of h.
h(ay11 a2p2)
(aju(ss) :) مميي(s;))
Σ (av)(s) + (vz(s)) h
avi(s) + (V2(s)
(H,) 11((s)
app((,,)) M2(s)
Σ (av)(s) + (v)(s)))
(v) + (12(()) (s)
av1 (5) + (01((8) v2(5)
(1)
(2))
Σ (av1(s) + (vvz(s)) h
(s) + (s)
av1 (s) + (2)
B.
1-3.
3e(1 - 3e)m1
(s))(s) + (vz(s))
B.h (T!!) + (1 B,)h (T!
TT!i 11?
EΣ (s) + (s2( (1t²2) (m!?)
aóm
v1 (8)
2 (1) (5))())
From here on, we use that
n (5)2(((())
Σ avi + ciu2 (8)
|TE - m
Σ max {v) (8), 2/ (8))
min for (s), (2()) lm - x
avn (s) + (v1(s))
Mam
21
Umin || T 1
1 Vmni max || |
Mmin/ H2 ||
pall2
where we used Proposition D.I in the last step. Plugging the inequality the proof.
( back into concludes
D.3 Lipschitz gradients
In this section, we show how we can get bounds on the Lipschitz constant Lg. To this end, we first need to lower bound the optimal policies.
Policy lower bounds The following proposition establishes lower bound for optimal policies with Shannon and Tsallis entropy regularization.
Proposition D.3. Let Hy, = 1/(1 - -7) and rmax = ||rlloc Then, we have the following lower bounds:
a) If -H then nr" (als) 2 exp (- max H// /|A|t
b) If -22 then x- (als) ((2rmax// (2rmax/ + /1i H.,) -2
Proof. Recall the formula for the optimal policies in Appendix
Part a): Since, -Tmax H, 9" (s. a) < (r max log [Al) Hy it holds that cxp (-r mrrmax /T)
t' (als) 2 A exp ((r max + T log Al) HT/T)
exp (-Tmax Hz/T)
exp ( 2m Hy/T)
A Ht exp (Fiaxx H/TT)
19

---

Part b): The proof of b) is similar to [Ouhamma and Kamgarpour 2023 settings are slightly different. Recall that
Lemma 8]. However, our
n (a(as)) = Iss O" (s, a)
T
By Ouhamma and Kamgarpour it holds that -Tmax H, 1 9" (s) a) < l'max 2T 2TT/A Hy. Hence, we have
2023
Lemma 10] have Fe 188-1145 11 S <TVIA,. Furthermore,
0 < x, (s) S TVAi + (fmax 2T (rVlll)) Hy + Tmaxtty S (2rmax 3T 33 V/TV Hy,
which yields the desired lower bound.
We also highlight the following result, which shows that if the policy T" is lower bounded on some set K C M,, then it is also lower bounded on its convex hull conv K.
Proposition D.4. Suppose = aj1 + (1 a2 with a E (0, and pl, p2 E M. Then, 021($) (s)
(v2($)
T
a11 (8) + 022 (8)
0W11 (8) (12(()
8,
B
where B. E 1).
Proof. The proof follows immediately from the proof of Proposition D.2
Hessian upper bounds In the following, we establish upper bounds for the Hessians of the occupancy measure regularizations. h. resulting from Shannon and Tsallis entropy regularization of the policy. In particular, smallest entry of the policy.
aim to upper-bound the maximum norm of the Hessian terms of the
Proposition D.5. Let Assumption 2.2 hold. Consider μ E M and let Tiin = mils, (als)) >
Then, the Hessian of is upper bounded as follows:
a) If -H, then (Ph(w))
3/2" b) h 112 then ( Masia Taa
Here, |1 denotes the maximum norm ||Al] maxi
Aggl
Proof. As shown by Schlaginhaufen and Kamgarpour satisfies
[2033 Proposition B.2], the gradient of
(s, M(TT)) (a) (Vh(Tt)), <²)
Moreover, have
0T (TT 8,,s' Sa TH (als)
ap(s', a²)
v(s)
Using the above two formulas, calculate the Hessians explicitly.
Purt a): For the Shannon entropy it holds by (9) that (i(u)(s, a) = T log 7 (als). Hence,
8hh(H)
60.0- da.' (als)
(als)
v(s)
and
8h(())
V (Ph( Epl(s' (p((s,))
Vmnin
Part b): For the Tsallis entropy it holds by that
vi(u)(s, -
Σ / (a"ls)
(als)
20

---

Therefore, the second derivative is bounded as follows
8h(()))
05,5' Σ
1
óa'a" (a(aass)
ar 2/ 2v
(p((s'a")@p(ssa)
(())
Sa,a' T (a|s)
2TH (a|(as))))) (als)
v(s)
0g.d
2v(s)
TH (a's))
(a/3333312
(als)
òa
E Va*(sas)) +
2//
TT
s3/a2s)312 VT
(A)
(B)
Now, since E. (als) < VĀ < 1/v Tmin. we have (A) + (B) S 1/ / Tiin + 1/TTim 2 n
3/2
3/2
min
which yields the desired result
3/2 V ( ST/ V/nin Mmin
Lipschitz gradients Next, we provide explicit Lipschitz constants LK for Vh corresponding to Shannon and Tsallis entropy regularization.
Proposition D.6 (Lipschitz gradients). Consider some closed convex set K. C M and suppose Tmin mingex mill,,a n* (a|s) > Then, the gradient of Lipschitz continuous over i.e.
Vh(pz) Vh(u2)]l2 s Lx 11ll -22l-1 Hun, P2 K.
where the respective Lipschitz constants are as follows:
a) If -H, then Lx = -T(S (Vmin minn) )
3/2 b) If -12 then LK = A|S (Vmin T min ).
Proof. Defining h = 42 - 11, Lipschitz continuity follows from
Vh(m)) vh(pe) 1 (1)
VISIAA Vh(pi) Vh(u2)l
VISIIA 1. v2h(p + th)hdtt
(0))
VISIIA / || + th)h/l dt
(10) VISIAA
|| + 11)l |1 di
ww
[S||A] max 05t51
/ th) Il -
Here, we used in (1) and (v) that || < v ||>||| < <n || for R", and in (ii) we applied
the fundamental theorem of calculus. Moreover, (ii) follows from | < [f]. and (iv) from Hölder's inequality. Now, by convexity μI; #22 E IC implies that # th E for [0, 1]. Hence, plugging in the upper bounds from Proposition D.5 concludes the proof.
0
21

---

D.4 Dual smoothness and strong convexity
Next, we show that the convex conjugate, f*, of the extended real value function f := + dm (see Appendix B is -f understood as mapping from IR 1R5xA// / to R - both smooth and strongly convex on R with respect to the quotient norm. While it well-known that global smoothness and strong convexity are dual properties [Rockatellar and Wets 2009 Proposition 12.60J, the key challenge for proving dual strong convexity that has only locally Lipschitz gradients (see Proposition D.6). Proposition D.7 below shows that 77strong convexity of h implies dual 1/n-smoothness and locally Lipschitz gradients imply dual R- ur-strong convexity on for some OR > Moreover, we provide explicit lower bounds dR. for Shannon and Tsallis entropy entropy regularization.
Proposition D.7. Let f* be the convex conjugate of = + 8M. Then, the following holds:
a) Suppose that h is n-strongly convex over M, that is for all p. E -M holds that
h(n') h(p) (Vh(1), -1) 11 1/112
then we have for all r, E SxA that
11 |rlell2.
(10)
2n
b) Suppose that for any closed convex subset K. C relint M, there is some Lx > such that for all μ. p¹ E K. it holds that
Vh(μ)) vh(p')l S LL 1| plll2
then we have for all r, r' RR that
(6)2 - RR 11 [rlee12
(11)
for OR > O.
c) Let H., 1/(1 ()), R == max,eR |||| D max,, 'RR ||r r' and suppose that D. then for the Shannon entropy the inequality holds with
2RH
Vmin exp
OR
2D A
H+
and for the Tsallis entropy with
Uminn
OR =
2/2D|S|IA| 2/2D)S11A| ((2/A)/(2///////// H.) 3.
Proof. Part a): Since is s-strongly convex with respect to ||:1|2- the conjugate / is 1 1/1/- smooth with respect the dual norm in SRSA Rockafellar and Wets 2009 Proposition 12.60). which is equivalent to (10).
Theorem 4.1], but need to account for the quotient spaces. define the sets K. Vf*(R) = RL(R) and K. = COCv(AC) + e(B (M)). where B c R denotes the closed unit ball with respect to I|-I|p and 0 is chosen such that KC, relint M. Moreover, we let L be the Lipschitz constant of Vh over
Part b): The show b), we closely follow [Goebel and Rockafellar 2008
22

---

Ke. Now, consider r E R and (r) Then, for any r' E R, we have
((rr)= sup Kr', p.- f(A)]
(1)
2 sup Kr', [2) - f())
μek.
(1)
L
2 sup
(r' .p) -(()) - (r. 11)
A - 1112
pek,
2
L
(r.p)) f(w) + sup
(r'-r, -r,
11 ml12
μek.
(1) (2(r) sup pEk.
(r' rr,
L
1 -m122
2
(r) + (r' r) + sup mek.
(r' r, p - 11)
1
mll
Here, (1) follows from K, C RSA (ii) from the fact that Lipschitz gradients imply that
f(z) - f()) + (g. - 14) + 1 - 1ll22
for any g (p(p) [Beck] 2017 Lemma 5.7] and E Of(μ)) (see Theorem B.4 Moreover, (iii)
and (v) follow from rearranging terms, and (iv) from (*( = (r, (a). Now, consider any
> such that ØR = 2(a La² /2) > and a S c. Setting j E K. in the above supremum to
(m (4) all (r' r) yields the desired result
La²
+ (r' (()()) + aafr - T2 (r' -r))
1 (r' - 11
2
= =f -f + OR |[r'lu - [r|u 12-
2
Note that we indeed have j E K. as E KC and / 1ll2 S a - saD
Part c): To get an explicit constant for dR. we need to appropriately choose and calculate the corresponding Lipschitz constant. To this end, we first recall that according to Proposition D.3 and D.4) corresponding to occupancy measures in conv A. are, for Shannon and Tsallis entropy,
lower bounded by
exp (-2RH,/T)
((2R/+ H²)²²
Tmin, Sh
A||
and miin Ts
respectively. Furthermore, for any μ E Ke, we have by Proposition D.I and equivalence of norms
2
(als)) 2 Amin
π min
Vmin
Hence, by setting c minn/ (4 (VS|IAA
we have ne (als)) for the Lipschitz constant over K,,, we have by Proposition D.6
2 n
min Tmin for any l E Kc., As
T|8||A|
T IA
Lsh
and Lts
(13)
Vinin " min, Sh.
Vanin min. Ts
3/2
for the Shannon and Tsallis entropy, respectively. Now, we need to ensure that > 0 such that
OR = 2(ax La /2) > 0 and a </D. To that end, we set for both regularizations a = T (TLD))
which in light of 13 ensures that
P'nin Ti
Vinin π min
(14)
LD
DISIIA
2D /
D'
for [S], |A| 2 2. Moreover, we get the dual strong convexity constant
T
72
2r
OR =
LD
2LD
LD
2D
23

---

which is larger than T/LD for T < D. We can therefore choose T/LD dual strong convexity constant. Plugging in the Lipschitz constants for the two regularizations yields
min, Sh Sh-mii
Tmin, Sh
exp (-2RH, Vmin
R,
DIS|AA
2DIS||A|
2D|S||AR2+ 2++H,
for the Shannon entropy, and
3/2
3/2
T min. Is
P'min
T min, Ts Mmmin
1/min
RR, D|S|[A|
2v2D|S11A!
2/2D|S|1A|
Hr)
for the Tsallis entropy.
Remark D.8 (Large regime). Note that if 2 2D VISIAA
On 1/I, while
still satisfying the condition (14p. This leads to the strong convexity constants
exp (-p2-RHH Umin
Vinin
R,
2T|5||A|2+H,
ORRIT
2v2r|S|1A| (22/T++3/14) H.)
D.5 Regularity constants
In the following Proposition, we summarize the regularity constants for Shannon and Tsallis entropy regularization. We highlight that these constants are lower bounds for and dR-
Proposition D.9. Let Hy := 1/(1 7), R == maxreR ||||| ogt and D max ||r r'll2. D, then for the Shannon entropy, Assumption 3.5 with
Suppose that
1 TVmin/ H and exp( 1-2RH Mmin
2
and for the Tsallis entropy with
1) TV/mn/ (2H2 and OR 2/2D|S||A|| (2R/T+3V/ 3/ H 3'
Umin
Proof.
The derivation for y is given Proposition D.2 and for dy in Proposition D.7 above.
D.6 Suboptimality bounds
Proposition 3.4. Under Assumptions 2.7 and 2.2 we have SubOpt(r', = Du(u, RL(r') for any
j E M.
Proof. Let fz = RL(r). We have
SubOpt(r; n²) = -r.p- --) h((p) + +h(())
= <Vh((),, 1/) -h(p) + T((y)) Da(p', ()),
where the second equality holds, as by we have vh(p) E U, and μ μl e u
Lemma 3.6. Suppose Assumptions 2.1 2.2 and 3.5 hold, and let r' E R. Then, we have
[[[r| - (r SubOpt(r', RL(r)) = Dj (RL(r), S 2n ||[re [r/
(6)
for some problem--dependent constant oR 0.
24

---

Proof. Let f = h dM and μ= RL(r), RL(r"). We then have
Dz(,, @ f(u) f(() - (r' .-
(0) f(()) - (r' (r) + (m. - -
(0)) (()) -r;; (r, (p
Here, (1) follows from the definition of and Vh(u")), in (ii) we use that ((u = (r, u1) (r) and f(u") (r's p²) (r'). and (tiz) follows from rearranging terms and V (r). The
result then follows from dual strong convexity and smoothness as established in Proposition D.7 C
Note that without steep regularization it is impossible to lower bound the suboptimality in terms of reward distances in R x ju (Proposition 3.4 doesn't 't hold). However, we still have the following upper bound.
Proposition D.10. Consider an arbitrary regularization and let RL(r), E RL(('). Then, SubOpt(r. n²) < 2 21[rru - [r']ullso 2 [1 - 1r
Proof. Let r" = argmin || 1i--lloo then the following holds
(ubOpt(r,11) = max [rr, 14) J(r MEM
IAG
max [r, 14) - max J(r", + "J("", - J(r MEM
HEM
(16)
max Kr r", pn) + Kr ,"'''> PEM
(H1)
|| - 1 oc
[[rr - 2 [1r) [r']ell2-
Here, (i) follows from the triangle inequality and optimality of n², (ii) from |max f max gl S max If g and simplifying, (tit) from Hölder's inequality, and (iv) from the definition r" and the quotient norm.
D.7 Perturbation bounds
Next, we provide bound quantifying the change in the quotient norm when changing the generating subspace.
Proposition D.11. Consider x. E Th and two subspaces V, W C IR" of dimension m < n. Then,
[[>] [ylwll S |[Tw Tyll || ||a--00 [|x=yllz [[[x]y [ylvll2.
where [[[w - Hy = sin (0max (0, W)).
Proof. The result follows from the triangle incquality and the definition of the spectral norm:
[[]] - [ylw l
[ww (x w)ll2 (1lw= 11E1 (xx y) + 14y1 (z y)
S [[[l - -Tly {(x - y)llz + [ (r y)
[[[ IIv) v)ll2 [|[x] [
S [[w myll || vlla + [[[x]v - [vlvll2-
Furthermore, for proof of [[[ - |y sin (0max (V, W)) we refer to [Drmac 2000
The following proposition shows that the maximal principal angle between two transition laws can be upper bounded by the spectral norm difference of the transition laws.
Proposition 3.9. Let P, P E A SXA and Hy, = 1/(1 - 7)). Then, we have 0, (P,,PP)) = 0 and sin (0max (P, (P)) HH, S P' where |I-1l denotes the spectral norm.
25

---

Before proceeding with the proof of Proposition 3.9. we need the following technical result.
Proposition D.12. For any P E S the smallest singular value of E - -pP satisfies
min (E -P) 2 VIAl/1S111- -
Proof. The main idea of the proof is use that miin (A) min /0 Azll2 / ||rll1 for any matrix A E R= We first lower bound o min (7 PP)) o min (T > (Pa)
) ). where Pa denotes the state
transition matrix under action a. Let x E RR. then we have
- (PP))
l2 2 1/v S || - >PPa 2|11
2 / (1|=||| - -Pl(a)) Txlli)
> (1- /// |0||, 2 /1/>)//o vis |x|||>
where the third inequality follows from
(Paa) Tx|11 =E Σ Pa )((')) S ΣΣ (s(s)') ( [1 ||l|
Hence, m yPa) 2 (1 7)/ v V|S Therefore, we have for any R that
-1EE- 7 P)xl Σ |1[ - >P)=)) (A//S|(1 7)² |
which yields the desired result.
We are now ready prove Proposition 3.9
Proof of Proposition 3.9 The first principal angle 01 (P, P') = 0 is zero as we always have C U. The bound on the maximal angle follows from a well-known perturbation result for orthogonal projections. Namely, if A, B E _axm are matrices of the same rank and II ll denote the orthogonal projections onto their column span, then we have [Ji-Guang 1987
A 1Bll < min [|| || BT
|} 11A - ||I,
where At denotes the Moore-Penroot inverse Penrose
1955
Recall that Up = im(E - P)),
sin (0max (P)P = ||u -114pp ||. and by Proposition D.12
[E -P) = (amin (E - 7P))- s vlSI/IAH
Therefore, we get
sin (6max (P.P')) / .7 Hr, HIP. P'll
E Proof of claim in Example 3.3
We recall Example 3.3 from the main paper.
Example 3.3 We consider two-state, two-action MDP with S A (0,= 1}. uniform initial state distribution, discount rate 7 0.9, and Shannon entropy regularization h = -H (see Appendix C Suppose the expert reward is { a) 1{s = 1) and consider the transition laws, p00 and Pt defined by (0)0)s, a) 0.75 and pl [0]s. a) 0.25 + 3 1 {s fs= 0, 0} for some / E [0. 0.75]. Also, consider the two experts E Ro (r and μf= RLp (r and suppose we recovered the reward f(s. a) E Then, the following holds: 1) We have pubOpt (f, / SubOptp (f, pF.)) = 0(3). That is. for small 3, the reward e is good solution to the IRL problem, as both experts approximately optimal under f. 2) The rank condition
0 and
5 between 0o and pl is
26

---

satisfied for any 3 > 0. 3) For a new transition law P defined by a())s,a) - = 1, = 0}, we have (r ( ~ 4.81, i.. (f) performs poorly under the experts reward.
In the following prove the claims 1. and 2., while 3. is computed via regularized dynamic program- ming (Gesst et al. 2019 Furthermore, we illustrate the occupancy measure spaces corresponding to p0 and Pl for different in Figure
0.4
-0.2
-0.4
-0.6
-0.4
0.2
0.6
0
0.4
v_2
0.2
0.2
0
0.2
0.4
0.4
0.6
-0.6
Mp
Mpt small
Mpt largo
Figure 3: The set of occupancy measures Mp and Mp are illustrated in SR: = 1-, For a wvo-state-two-action MDP, the set of occupancy measures given by the intersection of two- dimensional affine subspace (a plane in SxAA /1) with the probability simplex in R (a tetrahedron in gSx4/11, We see that for a small 3, the sets Mp po and Mp are approximately parallel. That is, the angle between their normal vectors, which span the potential shaping spaces Upo and Up,, small. In contrast, for a large 3 the orientation MPp po and Mp is very different, resulting in large angle between the corresponding normal vectors.
1. Consider the transition law P' defined by P'(O]s, 0.25. First, observe that while po - P'|| is large, the potential shaping spaces Upo and Up coincide. To see this note that have P'(-|s, a) (-]s, a) A, where A [-0.5, 0.5]T. Hence, have for any x E R that
-P--P0) (x. 74. x)) 12
(E (E-7P')z- (E- 1E->Po)a
1
where 1, denotes the all-one vector in RR. Therefore, span (F-7P') span F2 PO). Moreover, we have
|| - p'l
|P'- / s.s'.a
( - V23.
Thee code is openly accessible http:////.tttttoooo///.rr//////a
27

---

In light of Propositions D.10 D.1
and 3.9 this implies that
SubOptp: (f, RL (r
[f - [r 112
2 [lup - -llep |11
2y Hy: I|P - P'I 2222 Hy 8.
2. We need to show that p and pt are satisfying the rank condition
rank - ([
- y P!]] 2|S] 1.
By the same reasoning as above, we can equivalently show the rank condition for the transition laws po', pl defined by po1 (0]s, a) = and pl (0|s, a) = 3.1 {s = 0, = 0). To this end, choose the matrix representation
1 and P
P Pag
E
where / E || is the identity matrix and Pao: Pa, E ( [8] are the state transition ma-
trices corresponding to the actions 0, 1, respectively, Let C = [E -Pp0 We have
E E
0
po'
1
and pl'
and
1
0
1
1
BY
-7 By1
C=
7
0
1-7
0
1
-7
0
1-7
It's straightforward to see that the vector [1
-1
1
lies in the kernel of C, but
there is a 3 x 3 submatrix with non-zero determinant:
det (1=-)
1 - 7 1-3 By 1-
-
((1-)) -1-
37) (1 By(1 - 7) > 0.
In other words, we have rank C = 3 for any B > 0.
F Proof of Theorem 3.10
Theorem 3.10. Let K =
2, 12.00 > O, and suppose that Assumptions 2.1 2.2 and 3.5 hold. If pubOptps (f.)5.) S for k = 0, 1, then f is s-transferable to P = A A with
ε/ [noie sin (0z(P", /2)
The proof of Theorem 3.10 hinges on Lemma 3.6 and the following reward approximation result.
Lemma F.1. Let [[ - 1MMp, 1l, < 8 for h: = 0, Then, if ,,)) > 0, it holds that
||r-5,, - [f]11222 < sin (02(Po, P1)/2)
Proof of Lemma F.1 Throughout this proof, we will use the short-hand notation 24 := Ups for and by assumption we also have On (2 Ui) > 0, which implies that Wo U4 1. Furthermore, since for k = 0, we can rewrite S as the orthogonal sum S 24g 0 1 2 @ 1, we can uniquely decompose , - f into
0, 1. Recall that since C U4 ntd, we have 0, (U,,
F - 24 + yk + 2, where Fy E 44 0 1 Wi E 24 z E 1, for = 0, 1. Then, it holds that || the Assumption of Lemma F. implies
ato + yo = + 31- Since ||[r= pt
p+
pk.2
28

---

that 1/ 2l2 S E. For the 2-distance between the equivalence classes [r=] and [f]2 the Pythagorean theorem implies that
||rr [f 11 - 110ol22 + || = || 112 11 -
ag + Po: (27)
max ue Eleen ee ett
|| = 1- on exER+ (6 oo +81
where the upper bound follows from xo + yo = + y1 and ||ue|12 E. Next, want to show that the maximum on the right-hand side of (27) is achieved for 30 = B1 e. see this, note that taking inner products between uo and u1, respectively, and the equation agug 300 a1u1 + 31 B1 arrive at
or ai (uo, u1) + B1 (uo, v1), ai (o u1) + 8o (ui: vn),
which for any choice of BR, ug, uk. k 0, an invertible linear system of equations for coo 01 with the solutions
(o u, (un, vo) B1 (wo: v1)
31 (u,, un) (uo, 21) + Bo 0o)
a
01
(un, 41
uu1,
where (No, u1) < 1, due to Mu U4 - 0. As the sign of (wo, un (w1 vo) and (uo. 01) can be chosen arbitrarily by an appropriate choice of co U1, the objective in the hight-hand-side of (27)
increasing in fo. B1 and hence the maximum is achieved for 3o 31 E and == do a(ug.013 Therefore, it holds that 1- (Mo.as)
(no, 01)
(wo, uz) )
27
| 1
max MLEUNn my E
E2
1
27
max,, Elt - (wo 21)
i
max
1+
max 21 (20, u1
| =1
27
11f uo
(8)
max
1+
11 10
uo n1
14 ll2 =1
27
Il,e mo11 12
(62)
max ug 1u
1+
11 uoll2 1
||
V 1 - uoll2
max mo +
1
| m Holla
Il la =1
[ uo 22
max Mo Mo 1
1
|Moll =1
(0i)
+ cos (02 211)
cos (02 (U,, 211
(vit)
2
cos (02(26, (1))
(viis)
62
sin (0, 22)22)²
||[yul|| in (ii), and (iii) follows from the Pythagorean theorem. Furthermore, (iv) follows from uo E 1 and =/ (v, u) = ||Tpu/lg. the definition of the second principal angle (Definition (.8)) and the fact that the first principal vectors lie 1. Lastly,
Here, took the maximum over u1, U1 in (i), used that max.gv.lrll==i(e.
(v) from simplifying. In (wi) we then again use max,ev./|lll
(vii) follows from simplifying and (viit) from (in (1 cos z)/
29

---

Proof of Theorem 3.70 As mentioned in the proof sketch in the main paper, it follows from the lower bound in Lemma that k|r - [kee 1 S /28/0R. In light of Lemma F.1 this implies that for any P 5xA we have
V28/OR sin (02( p1)
||r - Fi 112 S || [illl2 S
Hence, applying the upper bound in Lemma 3.6 yields
(r RLp(()) - 2nj |[rFlur [flun 112
é no sin (02 P1) 21)
G Proof of Theorem 3.11
Theorem 3.11. Let K = 1, := max, ||r ||-- r and suppose that Assumptions 2.1 and 3.5 hold. SfSubOpt po (f, vF5 S ê, then i is p-ttrassferable to P E A5 with
Ep 2 max { 28 22/OR. D2 sin (0max (PO. PI)²} /n-
Proof. Similar to Theorem 3.10 it follows from Lemma 3.6 that ||| (upo - Iflpplll S 22/0OR- By Proposition D.11] we then have that
||| li- - [lu ll2 I sin max (P, (P,P))) ||rE- fll2 + 1110 - 1lu40ol2
S sin maax (P, pO) D + /28/OR
Hence, applying Lemma 3.6 again yields
1 SubOptp (r=, RL)())) s 2n
||| lur - [Flu
Dsin (Omax (P. po)) + /25/OR
21
2 max { D2 sin (Omax (P, po))² 28 22/ORR
71
H Estimating principal angles
Consider two full rank matrices A, B E _ and let the columns of UA Up gaxm form an orthonormal basis of V = im A and W = im B, respectively. Then, as discussed by Ui-Guang 1987 we have
o (os( W)), 1,...,m,
where 2 σ1 2 ... Fm denote the singular values UTU, Un sorted in decreasing order. Hence, given the transition matrices pa pll we can compute the principle angles 0, (P", pl) by first computing orthonormal bases for the column spans of E - PP,, i 1,2, 2, and then computing the singular values as described above.
Now, suppose that po, f1 are empirical estimates of p0 pl, then we have by Ji-Guang 1987 Theorem 3.1] the following perturbation result
max (in( P')) sin(0,(P0, p'n)| < [TT4 TTe ||
+
||T - -TTp ||
p0 50 + ||||++||111 p
< H //////// A
where the last inequality follows from Propositions sin ( p1) up an error of O [max
D.Il and
3.9
Hence, we can estimate
{||
po
p1
11
30

---

I Proof of Theorem 4.1
Theorem 4.1. Suppose that N = 2 (oKKoog((S)))) (((1)///))) and HE =[gl K K 1og(1/>)) (1>))-
Running Algorithm for T = /E² iterations with step- size a = -1/(KV2 /T), where dept = (882 / Eapr (E) N
( (66)) and H H it holds with probability at least 8 that pu (f, (4 - é, for O,..., K
The proof of Theorem 4.1 is inspired by (Syed and Schapire 2007 Theorem 2]. However, in contrast to Syed and Schapire 2007]. we consider the regularized problem with multiple experts, we use the suboptimality as the convergence metric, and we use projected gradient descent update (instead of multiplicative weights). The proof hinges on Hoeffding's inequality and regret bound for online gradient descent, which are provided in Theorem I.I and T.2 below.
Theorem L1 (Hoeffding's s inequality [Hoeffding 1963 ). Let Xo...., XM.... be independent random variables with X E [a,b) and let SM == Xo + XM--1- Then,
2c
Pr (ISM ESS c) exp
M(b a)}
Theorem 1.2 (Online gradient descent Zinkevich 2003 Consider some bounded closed convex X Rn with D max || x 12 Moreover let 1Ix 1R"" + X be the orthogonal
projection onto X. For any sequence of convex differentiable functions fo...., X + RR
satisfying maxzex [( S G, the online projected gradient descent update
I++1 Txx (xx (V
with step-size a = D/GGTT) satisfies
T-1 E $ DGVT. EX
Σ f((a)) - min t=
Proof of Theorem 4.7 The proof is in three steps. First, we use Hoeffding's inequality prove concentration of the empirical occupancy measures around the true occupancy measures. Then, we use the union bound upper bound the probability that any of our bounds fails hold. Finally, we prove the convergence rate of Algorithm Jusing the regret bound in Theorem I.2
Step 1: Let D {So, .u...., 8H-1, aH -)) the corresponding empirical occupancy measure defined as
N-1 be sampled from some policy x" and recall that
N
N-1 H-1
1
(ip(s, a) =
N
i=
1=
will be convenient to define the truncated occupancy measure
H-1
(s( a) = (1-7)
Σ
{st =
uo
1=
For K data sets Di...., Dx sampled from M we then have
K-1
K Σ
K
max PER k=
Σ
(r, A4
)D.)
max |hh
Σ k=U
(ux - Pow)
ER
K=0
(#0)
(m
pH,.))
(WHLL (Dw)
where (i) follows from Hölder's inequality, (ii) from our definition of R the 1-norm ball, and (Mi) from the triangle inequality. Since ||ı P lloo I 7 we have I S 7 K. Moreover, applying Hoeffding's inequality the M KN independent random variables
H-1
XAN+:
1
Σ
1
s,a, =a), iE [N]] [K],
N
31

---

with X; 10,1/M, we arrive at
K
E N
Pr (1SMM ESM 2 Fsta/2) = Pr
Σ
PrD. (s, a) (x.A(s,0)
2 Esta/
S 2 exx
2K
Hence, applying the union bound over all |S||si] components of the occupancy measure yields
Estat
Pr(12 < Estaa = Pr(2 2 Estat 22m 2 || exp
2K
Therefore, to ensure that with probability least 1
Ösent it holds that
(r, pkk (.D,)) S Estat:
PER
it suffices to choose
2K log (2|5)|A|/8g)
log (2K (2KK/su)) 6um) log(1/7) (1/)
N 2
and H
Stta
This concentration result applies to both empirical occupancy measures generated from the expert data sets D as well as the data sets Dz.t generated by Algorithm
Step 2:
When analyzing Algorithm 1 there three sources of stochasticity. The first two due to the randomness in the data sets DE and 'D,,,, and the third due to the randomness in the forward RL algorithm, A Amp that upon query with the reward ra outputs policy æaa such that with probability least Jup it holds SubOpt (F', p ( ) S Copt- Let's denote the event that max KK-1 (r, ppp= App) EsuiE by Estar, the event that max,ER K-11 (r. > Estal by Esm,, and the event that SubOpt (Th.)) > Cupt by Expt,k, Moreover, let us assume that Ex happens with probability most Eea,,,,, Estar,t happens with probability at most d and k. happens with probability at most 8pp.. By union bound, the probability of the event
K-1
F E
Estar,
Eopt,,
that none of the above events happens is lower bounded by
T-1
T-1 T-IK-1
Pr Pr(F) - Pr EsaatE V
V
Exta, V
V V
Expt,kit
1=
1=0 A=
T-1K-1
2 1 Pr (Exan,E) +
Σ
Pr (Estat,))
ΣΣ
Pr (Eop.k..)
t=0
t= k=0
> 1 (Asua,E + Thgtt KTTopp).
Hence, to ensure that F happens with probability at least --8 8, it suffices to choose
2K log (6]S|1A1/6)
log (2K/ (2K/Estu.E) EstatEE)
N >
and 2
log (1/7)
2K log (6T
8
N₂ 2
and
Sapt
2
3KT
Step 3: Note that bound ||sell2 || Σx
+ || < 2K =: G and the diameter of R is D = 2. Hence, given that event F happens, can bound the suboptimalities of the
32

---

K experts under the reward, f, recovered by Algorithm |
with stepsize D/GGVT) as follows
(f.
max (f, - ppp)) h(m) + h(app))
MeMMpt
A=
(1)
max (f, PrDE) h(()) + h((f))))
E
MEMpp
k=0
(8))
K-1
max (re, - -PE) - -h(u)= + h(ppps)) p
S Estaat,"
+
k=0
1
T
1-1
max (ri, (mg)) [(()) + T(( pe
E
T
1=
K=
(181)
Estat,
K Keppt +
(Te PIDE) hukx)) + hu(ppp))
(60)
T-1K-1
Esaa,E + KEept + Esta +
(re, PDD)) - -((x,e) + M((fpeo))
T
1=
k=0
(v)
DG
S E + Keopt + Estat
min
(r. AD,. PODE) h((w.)) + h(ppp)))
VT
rER
T
1=
(11) stat + KEopt + sa +
DG
min ER
[In, (nr - (Frn)) h(mee) + H(HFF)))
VT
(wix)
DG
I st + Koopt + sE +
VT
K-1
1 T
+ min ER k=0
(n. Pk
E Upxx)
h(px)) h(mp)))
with Pr =
Mktt
T
r=0
20
(vitt) S 2 + KEopt + 2 +
DG
4K
2Estat,E + Keopt + 21
VT
VT
Here, the inequalities (+), (fv), and (wi) follow from the concentration bound established in step 1. Moreover, inequality (1i) holds since + maxpeM,t pa (f, μ (TFx)) h())hh()hhht(t (p(F is the pointwise maximum of affine functions and therefore convex. Furthermore, (vii) follows from Eopr opttmmalyy of Mk,e, (v) from Theorem 1.2 and (vi)) from concavity of the mapping (4x. + (r, (r.
h((,,)) Finally, (véii) holds because all experts are optimal for the reward E.E In conclusion, to ensure that with probability at least 8 it holds that SubOpt (f, (Ep I
Σk= SubOptpa (f. HPx) é log(16K/e)) H = He = 10/(1/7)
K
it suffices to choose T = 256K2 22 a =
N
128K log (6((6())))))
I6KI. .
22
N₂ 128K log( (( dept
AE 768K3
8 Eapt
2
TK
Suboptimal experts
In our problem formulation, we assumed that the K experts are optimal with respect to F i.c. f RLps (rE) for h O,..., K 1. This assumption can be weakened by requiring that max rER
(((,N5)) J (r, RL (rF < Emis
33

---

where Eii is some misspecification error. The transferability results in Theorem 3.10 3.11 still apply whenever we recover a reward such that Su p (f, p (r5)) S É. Moreover, with straightforward modification of the proof of Theorem 4.1 it follows that with high probability Algorithm D recovers a reward é such that SubOpt (f. RL pz (r5) S
mmis Hence, our end-to-end transferability guarantees apply with & +- & + 2K However, mis cannot be further reduced by collecting more samples from the expert or MDP.
K
Experimental details
Setup To validate results experimentally, we are using stochastic adaption of the WindyGridworld environment [Sutton and Barto 2018 In particular, we consider a 6x6 grid with 4 actions (Up, Down, Left, Right), wind direction (Norh,, East, South, West), and wind strength 3 E [0. 1.. When the agent takes an action, with probability (1 - 3), it moves to the intended grid cell, and with probability 3, the wind pushes the agent one step further in the direction of the wind. This means that the transition law is a convex combination of two laws: (1 - 3) pGrldword + P where pGridworld and WWind represent the transition laws for deterministic Gridworld and a deter- ministic WindyGridworld. For our experiments, we then consider the pairs of expert transition laws Pg (1-3) (11-33))tiwwwaaaa pGridworld + PNoth and P/ = (1-3) (1- pGridwoldd + PEas with 3 in {0.01, 0.1, 0.5, 1.0). As shown in Figure 4(a), the second principal angle between P3 and Pj.. calculated using a singular value decomposition Knyazev and Argentati 2002). increases as the wind strength increases.
Inverse reinforcement learning We observed that under small second principal angle, the recovered reward heavily depends on both the expert reward and the reward initialization. Hence, we sample 10 independent expert rewards, each generated by first sampling random set of 10 state-action pairs and then randomly assigning a reward of +1. Using Shannon entropy regularization with r 0.3, then use soft policy iteration to get expert policies for each combination of expert reward and wind strength 3. For each of these expert policies, we then generate expert data sets with N {103, 10 105, 109} trajectories of length H 100. Next, policy iteration as a subroutine, for 30' 000 iterations, where rewards are initialized by sampling from standard normal distribution. As reward class, choose the ||-II, -ball with radius 10 (essentially unbounded), as stepsize a 0.05 for the first 15'000 iterations and a = 0.005 for the second half. Moreover, we sample N 100 new trajectories of horizon H 100 each gradient step. Figure (b) illustrates the distances between the recovered f and the experts' reward , measured in R RSxxx/1. evident that the recovered reward gets closer to the experts' reward as the number of expert demonstrations increases. Moreover, we observe that the recovered reward is closer to the experts' reward when the second principal angle between the experts is larger, as expected from Lemma F.
Algorithm 1 with soft
Transferability We evaluate the transferability of the obtained reward by considering two new environments. First, a south wind setting PSouth with wind strength terministic gridworld pShited with cyclically shifted actions, i.e., Right-> Down, Up-> Right, Left Up. Down-> Left. In Figure 4c) and (d), we illustrate the transferability SubOpt (r_,, ps (f)) and SubOpt pr RL psines (f)), respectively. We observe that for both environments the transferability improves with a larger second principal angle, thus confirming our theoretical result in Theorem 3.10 The effect is even more pronounced for the shifted environ- ment. While confirming our results, the experiments also reveal a high sample complexity in terms of expert demonstrations. This is to be expected, IRL aims match the expert's 's empirical occupancy measure, leading to overfitting when there are not enough demonstrations (Ho and Ermon| [0166]. This issue can be mitigated by reducing the dimension of the reward class (see e.g. Abbeel and Ng 2004
and second, a de-
terms of
1 'lll our experiments were carried out within day a MacBook Pro with an Apple M1 Pro chip and 32 GB of RAM.
34

---

0.25
0.01
0.1
0.20
reward dlstauee
8
0.5
transferabiiitt
8.pp) pl)
-5
0.15
1.0
20
0.10
0.05
0.00
0.0
0.5
1.0
10a
101
10
10
10a
10'
10
10a
10
10a
10
10
NE
N
(a)
(b)
(c)
(d)
Figure 4: (a) shows the second principal angle between P1 and P3 for varying wind strength B. Furthermore, (b) shows the distance between i and , R for varying number of expert demonstrations N and wind strength 3. Moreover, (c) and (d) show the transferability to pSouth and pShileed in terms of SubOpt pson (r psea (f)) and SubOpt (r paine (f)), respectively. The dots indicate the median and the shaded areas the 0.2 and 0.8 quantiles over the independent realizations.
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: As mentioned in the abstract and introduction, our main contributions are sufficient conditions for learning transferable rewards, given in Theorem 3.10 and 3.11 Furthermore, we also provide an algorithm and experiments in Section and
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations in the Limitations and future work paragraph in
Section 6
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
35

---

The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: Yes, all assumptions are stated in the main paper, and proofs are provided in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: All details about our experiments are provided in Appendix K Furthermore, we also provide the code attached as .zip file.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same
36

---

dataset, provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis-
sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (c.g.. a large language model), then there should either be way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-souree models, it may be that access to the model is limited in some way (e.g.. registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: All code (for experiments and computations in Example 3.3) is attached as .zip file. Furthermore, we provide a README.mb md with instructions how run the code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.ce cc/
wwm.iisssssiccccyico for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ //nips
wwwaiiicgguieeeeeeeeeeee www.o/oooidissiioooooooooo sww.uoooiisiooooooocccoooo for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Yes, discuss the chosen stepsizes and parameters in Appendix K
37

---

Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We repeated experiments 10 random seeds and provide quantile plots.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (c.g. negative error rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification: Yes, the hardware details are specified as footnote in Appendix
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics http:///ww....appppppppppttettea
Answer: [NA]
38

---

Justification:
This work is purely theoretical and did not cause any harm to society.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there is a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This work is purely theoretical.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymentt of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI...
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (c.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We don't work with any potentially harmful models or datasets.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
39

---

12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: The experiments are based on our own codebase.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
Answer: [Yes]
Justification:
We provide our code as .zip file. We will make it openly available github later.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This research does not involve any human experts but only synthetically generated ones.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
40

---

According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/teview based on the requirements of your country institution) were obtained?
Answer: [NA]
Justification: No humans are involved in this research.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
41


Reviews:
[{"review_id": "YU7bTYDsbv", "reviewer": "Reviewer_hiXS", "summary": "In the context of inverse reinforcement learning (IRL) -- i.e. the task of recovering a reward based on demonstrations from experts acting (approximately) optimally with respect to that reward -- this paper studies the question of transferability to new environment dynamics: if we learn a reward function from demonstrations on environments with dynamics P1 and P2, when can we expect for this reward to lead to the optimal policy on a third environment with dynamics P3? The authors show that previous results guaranteeing transferability do not generalize to cases where we are able to learn the reward only approximately, which would be the case in most practical settings. They then provide two theoretical results giving sufficient conditions for transferability.", "questions": "I would appreciate more discussion on how you would expect similar results to generalize to continuous state and action spaces - you title the paper \"Towards the Transferability ...\" so it would be good to have more discussion of whether and how this simple finite linear case is a useful step toward establishing more practically useful results. This is key for assessing the importance of this paper.", "limitations": "The results in the paper are limited to only finite state and action spaces and furthermore to recovering reward from an expert whose policy is corresponding to a particular kind of regularization. It is unclear whether this kind of regularization anyhow corresponds e.g. to how a human would demonstrate a practical task to a robot (I would say it doesn't).", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "- The broader question the paper addresses (transferability in IRL) is a key question for the practical usefulness of IRL. IRL papers often claim that the recovered reward is a more generalizable representation of the goal than a policy (that could be recovered e.g. using behavioural cloning, which is usually cheaper). This paper makes a step toward putting such claims on firmer theoretical basis.\n- The paper clearly shows important limits of prior results in the area.\n- The authors prove novel theoretical results using an original method.\n- Once one grasps the necessary formalisms, the rest of the paper has a clear and easy-to-follow structure.\n- The writing is largely free of typos and other mistakes.", "weaknesses": "Only major objection is the lack of pedagogical effort: I think the paper is not optimized to be read by a broader NeurIPS audience. I think it would be easy to read to someone who is (1) an expert on IRL (already a somewhat niche area) and at the same time (2) an expert on the kind of theoretical analysis used in the paper, which leaves only handful of people (I think an audience not big enough to even hold a workshop). Even someone from category (1) with a degree in math and some familiarity with similar theoretical results, I would really appreciate if authors put much more effort into explaining what are the intuitions behind the different abstract concepts that they use. E.g. I think most people active in IRL and RL have much stronger existing intuitions in thinking about policies, rather than occupancy measures, so a slight build-up toward defining stuff in terms of measures would help them. Similarly when introducing a \"strictly convex regularizer\" it may be useful to give an intuition what is the purpose of that regularizer .Often adding a single sentence in places like this would make a huge difference to many readers. Also defining the transition operator as $(Pv)(s,a) = \\sum_{s'} P(s'|s,a)v(s')$ is about as unintuitive as it gets for an otherwise so intuitive concept.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback, valuable comments, and helpful suggestions. While we addressed most of your concerns in the response to all reviewers, we would like to respond in detail to some of your comments below.\n## Our comments:\n- __(C)__ *\"I think the paper is not optimized to be read by a broader NeurIPS audience. (...) \"* __(A)__ Thank you for pointing this out. We will try to address this in the camera-ready version (see response to all reviewers).\n- __(C)__ *\"I would appreciate more discussion on how you would expect similar results to generalize to continuous state and action spaces.\"* __(A)__ We will extend the corresponding discussion in the limitations section (see response to all reviewers). In short, we expect our results to translate to the continuous setting, but dealing with infinite-dimensional reward and measure spaces will introduce several technical subtleties.\n-  __(C)__ *\"It is unclear whether this kind of regularization anyhow corresponds e.g. to how a human would demonstrate a practical task to a robot (I would say it doesn't).\"* __(A)__ Assumptions about the expert's behavior are necessary to analyze identifiability and transferability of rewards. As outlined in the response to all reviewers, entropy regularization can be seen as a model of bounded rationality, and the assumption of perfect expert optimality can be relaxed. However, we believe that further research is needed to determine suitable models of expert behavior for specific applications.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hOJz1oSCTL", "reviewer": "Reviewer_jeG2", "summary": "This paper introduces the logical framework regarding rewards identification (up to potential shaping transformations, which can be achieved under entropy regularization) and rewards transferability (up to a constant, more difficult to achieve). The paper considers a practical scenario where only expert demonstrations are accessible, not the full expert policy, and analyzes $\\epsilon$-transferability using the principal angles technique. Additionally, when only expert demonstrations are available, they analyze two cases: for two experts, transferring to an arbitrary transition law requires the two laws (from two experts) to be sufficiently different; for a single expert, transferring from the original to the target environment requires the transition laws to be closely related. Finally, they present a probably approximately correct (PAC) algorithm and an end-to-end analysis for learning transferable rewards from multiple expert demonstrations.", "questions": "1. As the authors mentioned in Section 2, the reward in $\\mathcal{U}$ and $\\mathcal{V}$ is defined on $\\mathcal{S} \\times \\mathcal{A}$. According to Definition 3.7 (lines 237-239), how are the elements in $\\mathcal{U}_{P}, \\mathcal{U}_{P'} \\in \\mathbb{R}^{\\mathcal{S} \\times \\mathcal{A}}$ processed for inner product and modulus operations (to be a constant)? \n\n2. $\\|[r]_{\\mathcal{V}}-[r']_{\\mathcal{V}}\\|_{2}$ is small. How to define 'minus' and 'small' needs clarification, as I believe this involves the difference between two sets or two equivalence classes. A detailed explanation would be better.\n\n3. The description of the lower and upper bounds in (6) is unsatisfactory. For the recovered reward, we need to consider both the lower bound (not optimal) and the upper bound (approximately optimal). Therefore, both the lower and upper bounds should be included. \n\n4. I think the implications of Theorem 3.10 should be introduced separately according to single expert and multi experts due to the different meanings of transition law differences. For multiple-experts, the difference in transition laws pertains to the source environments. For single experts, it pertains to the difference between the source environment and the target environment.", "limitations": "The authors have discussed the limitations and future work in Section 6.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. I have particularly appreciated the logical framework regarding rewards identification (up to potential shaping transformations, which can be achieved under entropy regularization) and rewards transferability (up to a constant). I also value the introduction of two methods for attaining rewards transferability: first, by restricting the reward class, such as to state-only rewards, and second, by learning from multiple experts who share the same reward but have different transition laws, provided a specific rank condition is met.\n\n2. The topic selection is meaningful, exemplifying that under the approximate optimality of experts, the learned reward can perform poorly in a new environment, even if the rank condition in Equation (5) is satisfied. \n\n3. They consider a practical scenario where only expert demonstrations are accessible, not the full expert policy, and analyze $\\epsilon$-transferability using the principal angles technique. This result encompasses the scenario where the full expert policy is accessible, recovering a reward r^ for which all experts are exactly optimal, with ϵ being 0 for all experts.\n\n4. The comparison between single-expert transfer and multi-expert transfer is insightful.", "weaknesses": "1. This work is mainly theoretical. I think experimental validation on real-world applications could provide valuable insight into the practical aspects and challenges of transferability (if possible).\n\n2. I think the example used to describe the rank condition's insufficiency for reward transfer when $\\epsilon$ is not exactly 0 (for all experts) is not effective. As $\\beta$ tends to 0, the two transition laws become completely different, which is too extreme, despite being easy to follow and aligned with the main theorem. Maybe a toy demo with illustrations is better.\n\n3. When $\\epsilon$ is exactly 0 (recover a reward $\\hat{r}$ for which all experts are exactly optimal), the work is already established, making the theoretical contribution slightly inferior. I believe a detailed discussion of this work's theoretical innovations and how it differs from the case when the expert policy can be achieved is necessary (from a theory aspect).\n\nI will be inclined to increase my score if I appreciate your response.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback, valuable comments, and helpful suggestions. While we addressed some of your concerns in the response to all reviewers, we would like to respond in detail to your comments below.\n## Our comments:\n-  __(C)__ *\"(...) I think experimental validation on real-world applications could provide valuable insight into the practical aspects and challenges of transferability (if possible)\"* __(A)__ This is a valid point. However, as our theoretical results apply to tabular settings only, we decided to experimentally validate them in a grid world environment and to leave extensions to more realistic continuous environments for future work.\n- __(C)__ *\"I think the example used to describe the rank condition's insufficiency for reward transfer when 𝜖 is not exactly 0 (for all experts) is not effective. As 𝛽 tends to 0, the two transition laws become completely different, which is too extreme, despite being easy to follow and aligned with the main theorem. Maybe a toy demo with illustrations is better.\"* __(A)__ We intentionally picked an example where $P^1$ doesn't tend to $P^0$ as $\\beta\\to 0$. The example shows that even if $||P^0 - P^1||$ is large, and the rank condition is satisfied, the recovered reward may fail to be transferable to a new transition law. We could have picked $P^1(0|s,a) = 1-\\beta·\\mathbb{1} \\lbrace s = 0, a = 0\\rbrace$, but then one might argue that the lack of transferability for small $\\beta$ is due to $P^0\\approx P^1$  and not due to the second principal angle being small. Alternatively, if you prefer, we could pick something intermediate like $P^0(0|s,a) = 0.75$ and $P^1(0|s,a) = 0.25+\\beta·\\mathbb{1} \\lbrace s = 0, a = 0\\rbrace$ and the example would still work out. Furthermore, for a toy demo we refer to the experiments, where we see that also for a gridworld example the rank condition alone, which is equivalent to $\\theta_2(P^0, P^1)>0$, does not suffice to ensure effective transferability to new environments. Is this sufficiently addressing your concerns?\n- __(C)__ *\"I believe a detailed discussion of this work's theoretical innovations and how it differs from the case when the expert policy can be achieved is necessary (from a theory aspect).\"* __(A)__ We dedicated Section 3.2 and Example 3.2 to the discussion of related work in the exact setting. Example 3.2 shows that the previously established binary rank condition is meaningless when we cannot identify a reward for which the expert is perfectly optimal.\n## Answers to Questions:\n1. Thanks for pointing this out, we will clarify this more explicitly in Section 2. In lines 237-239, $\\mathcal{V}, \\mathcal{W}$ are subspaces of $\\mathbb{R}^n$. As mentioned in the notation section, $\\langle \\cdot, \\cdot\\rangle$ denotes the standard inner product $\\langle x, y \\rangle = \\sum\\_{i=1}^n x\\_i y\\_i$ in $\\mathbb{R}^n$. Moreover, the inner product on $\\mathbb{R}^{\\mathcal{S}\\times\\mathcal{A}}$ is defined analogously by $\\langle r, r' \\rangle = \\sum_{s,a} r(s,a)r'(s,a)$. \n2. Thanks for pointing this out. We clarified it the response to all reviewers. The quotient space is itself a vector space. Hence, addition and multiplication are well-defined. Moreover, we introduced the norm on $\\mathbb{R}^{\\mathcal{S} \\times \\mathcal{A}}/\\mathcal{V}$ in line 129.\n3. Would you mind to elaborate more on this question? We're not sure whether we understand it correctly. Equation (6) contains a lower and an upper bound, and both are discussed before and after the statement of the result.\n4. We only stated Theorem 3.10 for a single expert. The idea is that when learning from only a single expert, transferability to arbitrary transition laws is impossible even in the exact setting. However, Theorem 3.10 shows that we are at least transferable to target environments that are close to the source environment in terms of the maximal principal angle. In contrast, Theorem 3.9 shows that when we are learning from two experts and the second principal angle between the two source environments is large enough, then we can transfer to any target environment. Does this sufficiently clarify your question?", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kWjyOF9NsS", "reviewer": "Reviewer_fi4j", "summary": "The paper establishes bounds on the reward transferability for inverse reinforcement learning in discrete MDPs with known transition matrix. It is well known that the reward function learned in a single environment is in general not transferable as the reward shaping potential can not be identified and therefore, the recovered reward function may perform poorly under different dynamics. Prior work showed conditions for recovering the true reward function (up to a constant) when observing multiple experts acting in MDPs with different dynamics. Probably most relevant, Rolland et al. (2022) showed that reward identifiability is ensured under some rank conditions on a matrix constructed based on the transition matrixes. However, their analysis assumes that the IRL problem can be accurately solved in the different environments.\n\n* The submission extends these previous results by allowing for an error in the recovery of the reward function. Namely, the paper derives a bound based on the principal angles between the subspaces of potential shaping transformations corresponding to the different transformation matrices of the experts. That is, the second largest principle angle between the two observed MDPs, in combination with the optimality gap of the recovered reward function, is used to bound the optimality gap of the optimal policy (wrt the recovered reward function) under any other transition matrix.\n\n* Similarly, the paper uses the principle angle to establish a bound on the optimality gap on a given environment, when the reward was recovered in a different environment.\n\n* The theoretical results are accompanied with empirical results on a gridworld environment that show the relation between the principle angle and the error of the recovered reward function. The results use projected gradient descent to optimize the reward function based on demonstration under different system dynamics.", "questions": "- Line 133 states that the paper considers equivalence relations induced by constant shifts and the \"aforementioned potential shaping transformations\". Do these include all general potential shaping transformations?\n\n- Could we use the principle angle to design experiments in order to learn transferable reward functions?\n\n- Any ideas on how the angles could transfer to continuous MDPs?\n\n- How could we estimate them from transition samples?\n\n- Could the angles be generalized for K>2?", "limitations": "Limitations and potential negative societal impact have been adequately addressed.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "**Originality**\n\nUsing prinicpal angles for bounding reward transferability seems to be a novel and useful concept. The previous rank conditions only provided a binary criterium usable for perfect conditions, whereas the principal angles enable us to relate approximation errors to the transferability of the recovered reward.\n\n**Significance**\n\nThe theoretical results could be a step towards better understanding reward transferability also for more realistic settings (e.g. non-finite MDPs, unknown transition matrices). Reward transferability is an important open and critical question in inverse reinforcement learning. Indeed, arguably there is little additional value in a non-transferable reward function compared to an imitation learning policy.   \n\n**Clarity**\n\nOverall, I find the paper well-written and easy to follow. The paper gives a good overview of the work and the theoretical results and assumptions are clear. I also like the geometrical proof Fig 1b a lot. In general the paper avoids unnecessary complications.  \n\n**Quality**\n\nThe assumptions (e.g. steepness & convexity of the regularizer and Lipschitz continuity of its gradient, full support for every state-occupancy measure) are reasonable.\n\nThe claims are well-supported and seem correct (I did not check all derivations in detail).", "weaknesses": "**Significance**\n\nThe paper builds on the concept of principle angles between different subspaces, which can be only computed in simple settings (finite MDPs with known transition functions). While I can imagine that concepts could be transferred to continuous MDPs and to settings where approximations based on transition samples are necessary, it is not fully clear if and how such extension could be accomplished.\n\n**Clarity** \n\nWhile overall the paper is clear, I think that the paper should provide some intution about its most relevant concepts. Namely, I am missing an intuition about the subspaces of potential shaping transformations $\\text{Im}(E - \\gamma T^\\top)$, which in turn would be useful for getting an intuition about the  principal angles of interest. \n\n**Quality**\n\nThe paper mainly considers the setting when learning with demonstrations from K=2 different transition dynamics. The paper proposes a trivial extension of the bound for K>2, that merely uses the tightest bound among all combinations of two different dynamics. However, I think it can be safely assumed that much better transferability can be guaranteed when learning in K>2 enviroments, as these could complement each other.\n\nThe bounds are quite loose as evident from Corollary 3.11 in the case of Shannon- and Tsallis-entropy regularization. In particular the term $\\exp(H_\\gamma)$ should easily explode for the Shannon-Entropy, and similarly the term $H_\\gamma^\\top$ for the Tsallis-entropy, where the term $H_\\gamma$ can easily be in the range of hundreds or thousands for reasonable discount factors. However, I give credit for the fact that the paper mentions this limitation, and at least the large bounds can be somewhat compensated by very small approximation errors (also recovering previous results for $\\hat{\\epsilon}=0$).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback, valuable comments, and helpful suggestions. While we addressed some of your concerns in the response to all reviewers, we would like to respond in detail to your comments below.\n\n## Our comments:\n- __(C)__ *\"While I can imagine that concepts could be transferred to continuous MDPs and to settings where approximations based on transition samples are necessary, it is not fully clear if and how such extension could be accomplished.\"* __(A)__ This is a good point. We will extend the corresponding discussion in the limitations section (see response to all reviewers). In short, we expect our results to translate to the continuous setting, but dealing with infinite-dimensional reward and measure spaces will introduce several technical subtleties and explicit constants could only be computed for special cases.\n- __(C)__ *\"While overall the paper is clear, I think that the paper should provide some intuition about its most relevant concepts. Namely, I am missing an intuition about the subspaces of potential shaping transformations $\\text{im}(E-\\gamma P)$, which in turn would be useful for getting an intuition about the principal angles of interest.\"* __(A)__ Thanks for pointing this out. We will try to address this in the camera-ready version (see response to all reviewers). As for the subspace of potential shaping transformations $U_P =\\text{im}(E-\\gamma P)$, it lies perpendicular to the set of feasible occupancy measures $\\mathcal{M}_P$ (see also [1] for more details). We will clarify this in the background section (see response to all reviewers).\n- __(C)__ *\"(...) I think it can be safely assumed that much better transferability can be guaranteed when learning in K>2 enviroments, as these could complement each other.\"* __(A)__ Yes, that's correct. We'll add it to the limitations and future work section (see response to all reviewers).\n## Answers to Questions:\n- __(C)__ *\"Line 133 states that the paper considers equivalence relations induced by constant shifts and the \"aforementioned potential shaping transformations\". Do these include all general potential shaping transformations?\"* __(A)__  Yes, all potential shaping transformations. We will drop the \"aforementioned\" for clarity.\n- __(C)__ *\"Could we use the principle angle to design experiments to learn transferable reward functions?\"*  __(A)__  Yes indeed, developing an online algorithm based on principal angles could be an interesting direction for future research. \n- __(C)__ *\"Any ideas on how the angles could transfer to continuous MDPs?\"* __(A)__ As mentioned in response to all reviewers, principal angles could be extended to the continuous setting. However, the resulting potential shaping spaces would be infinite-dimensional. We could then either resort to the theory of angles between infinite-dimensional subspaces [2], or consider a finite-dimensional reward class such as e.g. in linear quadratic regulators or linear MDPs.\n- __(C)__ *\"How could we estimate them from transition samples?\"* __(A)__ The principal angles can be computed via a singular value decomposition. As shown in [3], the error $|\\sin \\theta_k(P^0, P^1)-\\sin \\theta_k(\\hat{P}^0, \\hat{P}^1)|$ would scale as $\\mathcal{O}(\\max_k||P^k- \\hat{P}^k||)$ if $\\hat{P}^k$ are estimates of $P^k, k=0,1$.  We will add a brief section about this to the Appendix. Thanks for the question.\n- __(C)__ *\"Could the angles be generalized for K>2?\"* __(A)__ Yes, we believe so (see response to all reviewers).\n## References\n[1] Schlaginhaufen, Andreas, and Maryam Kamgarpour. \"Identifiability and generalizability in constrained inverse reinforcement learning.\" _International Conference on Machine Learning_. PMLR, 2023.\n\n[2] Zhu, Peizhen, and Andrew V. Knyazev. \"Angles between subspaces and their tangents.\" _Journal of Numerical Mathematics_ 21.4, 2013.\n\n[3] Ji-Guang, Sun. \"Perturbation of angles between linear subspaces.\" _Journal of Computational Mathematics_ (1987): 58-61.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "t12f9dU0Ih", "reviewer": "Reviewer_k5eY", "summary": "This paper analyses the problem of the transferability of the reward functions learned from expert demonstrations in regularized MDPs. After having formalized the problem, the authors introduce some assumptions that permit to connect the distance between equivalence classes of reward functions to the suboptimality of the expert. Next, they use the notion of principal angles to relate the distance between transition models with the \"amount of information\" provided by demonstrations in such settings. Finally, authors propose an algorithm with theoretical guarantees for solving the problem, which they validate empirically.", "questions": "questions:\n- Assumption 2.2 is rather strong, because you assume that the transition model is such that, for any arbitrary policy, each state is visited with a fixed non-zero probability. Do you agree?\n- As you comment in Remark 3.12, it seems clear that all the results depend a lot in how different the considered regularized MDP differs from a common MDP. Since common MDPs are more realistic models to model experts behavior, how limited do you think that your results are when applied to practical applications?\n\nminors:\n- the references should be made aligned with each other, and not like now where some have DOI code, others do not, some have volume, others number of pages, etc...\n- the checklist shall be put at the end of the appendix\n\ntypos:\n- line 130 the operation of difference between equivalence classes is not defined\n- line 140 it is not clear what is the difference between $N^E$ (which is not defined) and $K$\n- line 245 the simplex symbol has $\\mathcal{S}$ and $\\mathcal{S}\\times\\mathcal{A}$ reversed.", "limitations": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The paper is written in a clear manner.\n- The goal is to bring theoretical results (i.e., about known expert's policy) to the real world, by analysing the setting with demonstrations.\n- The transferability issue is one of the peculiar advantages of IRL over, for instance, BC, thus it is interesting.\n- The contributions are based on technically solid theoretical results (e.g., authors provide sample complexity analysis of the algorithm as well as convergence analysis).", "weaknesses": "- The framework of regularized MDPs makes things much easier w.r.t. the setting of common MDPs.\n- There are various assumptions along the way (which seem necessary).\n- Regularized MDPs do not represent a realistic model for expert behavior.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback, valuable comments, and helpful suggestions. While we addressed some of your concerns in the response to all reviewers, we would like to respond in detail to your comments below.\n\n## Our comments:\n- __(C)__ *\"Regularized MDPs do not represent a realistic model for expert behavior.\"* __(A)__ As noted in the response to all reviewers, entropy regularization is a widely recognized model of bounded rationality in social choice theory and behavioral game theory. Additionally, the assumption of perfect expert optimality can be relaxed. Nevertheless, we agree that further research is needed to determine suitable models of expert behavior for specific applications and we will discuss this in the limitations and feature work section.\n- __(C)__ *\"(...) common MDPs are more realistic models to model experts behavior, (...)\"* __(A)__ We believe that assuming perfect optimality in standard MDPs is also quite limiting. Humans are not perfectly rational. For example, in a bandit problem, if an expert chooses arm $a_1$ 99% of the time and arm $a_2$ 1% of the time, we would expect $r(a_1) > r(a_2)$. Yet, the only rewards consistent with these choices would be $r(a_1) = r(a_2)$. Similar but more subtle situations could arise in MDPs with multiple states. Of course, this issue can again be alleviated by relaxing the assumption of perfect expert optimality, which, however, leads to even less identifiable rewards.\n- __(C)__ *\"As you comment in Remark 3.12, it seems clear that all the results depend a lot in how different the considered regularized MDP differs from a common MDP. (...) how limited do you think that your results are when applied to practical applications?\"* __(A)__ 1) As mentioned in the response to all reviewers, our results still apply if the expert acts approximately optimally with respect to the regularized MDP. 2) Our proof technique based on principal angles between subspaces (Lemma F.1) can be applied whenever the reward can be approximately identified up to potential shaping. In unregularized MDPs, this may be achieved, e.g., by collecting preferences between different policies. 3) For standard IRL without a regularizer, the set of rewards for which all experts are optimal is no longer an intersection of subspaces but an intersection of convex cones (see, e.g., [1, 2]). We believe some of our tools, especially principal angles, would still be useful in this context, but without additional assumptions we expect it to be difficult to recover a transferable reward in this setting.\n-  __(C)__ *\"minors: the references should be made aligned with each other, and not like now where some have DOI code, others do not, some have volume, others number of pages, etc...\nthe checklist shall be put at the end of the appendix (...) typos: (...)\"* __(A)__ Thank you very much for pointing these out. We will address it in the camera-ready version.\n\n\n## References\n[1] Metelli, Alberto Maria, et al. \"Provably efficient learning of transferable rewards.\" _International Conference on Machine Learning_. PMLR, 2021.\n\n[2] Schlaginhaufen, Andreas, and Maryam Kamgarpour. \"Identifiability and generalizability in constrained inverse reinforcement learning.\" _International Conference on Machine Learning_. PMLR, 2023.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Thank you for the valuable reviews. In the following, we propose changes and answer to questions of general interest.
## Intuition building
Reviewers hiXS and fi4j suggested adding more intuition on key concepts of the paper. We will address this by adding clarifying sentences in the background section such as for example:
- Line 90: "Starting from some initial state $s_0\sim\nu_0$ the agent can at each step in time $t$, choose an action $a_t\in\mathcal{A}$, will arrive in state $s_{t+1}\sim P(\cdot|s_t, a_t)$, and receives reward $r(s_t,a_t)$."
- Line 126: "From a geometric perspective, the subspace $\mathcal{U}=\text{im}(E-\gamma P)$ lies perpendicular to the set of occupancy measures $\mathcal{M}$. Therefore, adding an element of $\mathcal{U}$ to the reward leaves the performance difference between any two occupancy measures invariant."
- Line 127: "Intuitively, $\mathbb{R}^{\mathcal{S} \times \mathcal{A}}/\mathcal{V}$ is the vector space obtained by collapsing $\mathcal{V}$ to zero, or in other words, it is isomorphic to the orthogonal complement of $\mathcal{V}$."

Additionally, we add an illustration of the occupancy measure spaces of Example 3.2 to Appendix E (see PDF).
## Expert optimality assumption
Reviewers hiXS and k5eY mentioned that our assumptions about experts' behavior might be restrictive. We agree that assuming perfect expert optimality with respect to $r^E$ and a steep regularization might be limiting. However, we would like to point out that:
- As mentioned in the introduction, entropy-regularization can be seen as an information-theoretic model of bounded rationality (see [1, Section 5]) and has been widely used as a model of human behavior in social choice theory (Bradley-Terry and Luce-Plackett models [2]), behavioral game theory [3], IRL [4], and RLHF [5].
- The assumption of perfect expert optimality can be relaxed. The transferability results in Theorem 3.9 & 3.10 apply if we recover a reward $\hat{r}$ such that $\ell_{P^k}(\hat{r}, \mathsf{RL}\_{P^k}(r^E))\leq \hat{\varepsilon}$. If $\max\_{r\in\mathcal{R}} |J(r, \mu^E_{P^k}) - J(r, \mathsf{RL}_{P^k}(r^E))|\leq \varepsilon\_{\text{mis}}$ where $\varepsilon\_{\text{mis}}$ is a misspecification error, the convergence proof of Theorem 4.1 can be adapted to show that with high probability we recover a reward $\hat{r}$ satisfying $\ell\_{P^k}(\hat{r}, \mathsf{RL}\_{P^k}(r^E))\leq \hat{\varepsilon} + 2K \varepsilon\_{\text{mis}}$. Thus, the transferability results apply with $\hat{\varepsilon}\leftarrow \hat{\varepsilon} + 2K \varepsilon\_{\text{mis}}$. However, $\varepsilon\_{\text{mis}}$ cannot be reduced by collecting more samples from the expert. We will add a brief discussion about this relaxation to the appendix.
## Limitations and future work
Aside from the above expert optimality assumption, we will discuss the following points in the "limitations and future work" section:
- **Continuous setting:** We believe Theorems 3.9 and 3.10 can be extended to continuous state and action spaces. However, the set of occupancy measures and potential shaping transformations are infinite-dimensional in this setting. Although our proof techniques involving convex analysis and principal angles can be extended to general Banach and Hilbert spaces (see [6] and [7]), the analysis is expected to be more challenging and technically involved. Moreover, deriving explicit constants, as in Corollary 3.11 or Theorem 4.1, would likely require further assumptions.
- **More than 2 experts:** While we mentioned that Theorem 3.9 can be trivially extended to $K>2$ experts by considering the maximum second principal angle between any two expert transition laws, the result may not be tight for $K>2$, as pointed out by reviewer fi4j. It would be an interesting direction for future research to generalize the principal angle condition in Theorem 3.9 to more than two experts.
## Clarifications
- In line 127, we clarify: "Given a linear subspace $\mathcal{V} \subset \mathbb{R}^{\mathcal{S} \times \mathcal{A}}$, the quotient space $\mathbb{R}^{\mathcal{S} \times \mathcal{A}}/\mathcal{V}$ is the set of all equivalence classes $[r]\_{\mathcal{V}} := \lbrace r'\in \mathbb{R}^{\mathcal{S} \times \mathcal{A}} : r' - r \in \mathcal{V}\rbrace$, which is itself a vector space with addition and multiplication operations defined by $[r]\_{\mathcal{V}} + [r']\_{\mathcal{V}} = [r+r']\_{\mathcal{V}}$ and $c[r]\_{\mathcal{V}} = [cr]\_{\mathcal{V}}$ for $c\in\mathbb{R}$."
- There is a typo in line 249. It should be: "In Example 3.2, we have $\sin(\theta_2(P^0, P^1))=\mathcal{O}(\beta)$, indicating that the second and in this case maximal principal angle is small when $\beta$ is small (see Appendix E)."  As shown in Appendix E, we have $||P'-P^1 ||=\mathcal{O}(\beta)$ where $P'$ is such that $\mathcal{U}\_P = \mathcal{U}\_{P'}$, while $||P^0-P^1 ||$ itself is large.
## References
[1] Ortega, P. A., Braun, D. A., Dyer, J., Kim, K. E., & Tishby, N. Information-theoretic bounded rationality. _arXiv preprint arXiv:1512.06789_, 2015.

[2] Hamilton, Ian, Nick Tawn, and David Firth. "The many routes to the ubiquitous Bradley-Terry model." _arXiv preprint arXiv:2312.13619_, 2023.

[3] McKelvey, Richard D., and Thomas R. Palfrey. "Quantal response equilibria for normal form games." _Games and economic behavior_ 10.1, 1995.

[4] Ziebart, Brian D. "Modeling purposeful adaptive behavior with the principle of maximum causal entropy". _Carnegie Mellon University_, 2010.

[5] Christiano, P. F., Leike, J., Brown, T., Martic, M., Legg, S., & Amodei, D. "Deep reinforcement learning from human preferences." _Advances in neural information processing systems_, 2017.

[6] Mordukhovich, Boris S., and Nguyen Mau Nam. "Convex analysis and beyond". _Springer International Publishing_, 2022.

[7] Zhu, Peizhen, and Andrew V. Knyazev. "Angles between subspaces and their tangents." _Journal of Numerical Mathematics_ 21.4, 2013.

Meta-review: The reviewers agree that the paper makes a novel and significant contribution to the IRL field. In particular, the question addressed in the paper (transferability in IRL) is of interest to the community. The paper highlights important limitations in the literature and provides novel theoretical results. **However, the reviewers have identified some weaknesses that the authors are strongly encouraged to address in the final version (presentation, comparison with similar works, etc.).** For these reasons, I am recommending acceptance.
Decision: Accept (poster)