Sub-optimal Experts mitigate Ambiguity in Inverse Reinforcement Learning
Authors: Riccardo Poiani
Curti Gabriele
Alberto Maria Metelli
Marcello Restelli
Venue: NeurIPS 2024 poster (2024)
Keywords: Inverse Reinforcement Learning
Sub-optimal Experts
Sample Complexity
Primary area: reinforcement_learning
TL;DR: We study how the presence of multiple and sub-optimal experts can mitigate the ambuigity that affects Inverse Reinforcement Learning.

Abstract: Inverse Reinforcement Learning (IRL) deals with the problem of deducing a reward function that explains the behavior of an expert agent who is assumed to act *optimally* in an underlying unknown task. Recent works have studied the IRL problem from the perspective of recovering the *feasible reward set*, i.e., the class of reward functions that are compatible with a unique optimal expert. However, in several problems of interest it is possible to observe the behavior of multiple experts with different degree of optimality (e.g., racing drivers whose skills ranges from amateurs to professionals). For this reason, in this work, we focus on the reconstruction of the feasible reward set when, in addition to demonstrations from the optimal expert, we observe the behavior of multiple *sub-optimal experts*. Given this problem, we first study the theoretical properties showing that the presence of multiple sub-optimal experts, in addition to the optimal one, can significantly shrink the set of compatible rewards, ultimately mitigating the inherent ambiguity of IRL.
Furthermore, we study the statistical complexity of estimating the feasible reward set with a generative model and analyze a uniform sampling algorithm that turns out to be minimax optimal whenever the sub-optimal experts' performance level is sufficiently close to that of the optimal expert.

Sub-optimal Experts mitigate Ambiguity in Inverse Reinforcement Learning
Riceardo Poiani
Gabriele Curti DEIB, Politecnico di Milano
DEIB, Politecnico di Milano
riccardo, iom.rmppmmm.i.....m....m..
gabriele. curti pom.i.ollimmii...mmm.mmmma.mmiil it
Alberto Maria Metelli
DEIB, Politecnico di Milano
albertomaria, illlertooariie.meeeliillllllol wwt.lmm@polllim.mi.........
Marcello Restelli
DEIB, Politecnico di Milano
marcello. restel eellppplliie ipolimi.
Abstract
Inverse Reinforcement Learning (IRL) deals with the problem of deducing a reward function that explains the behavior of an expert agent who is assumed to act optimally in an underlying unknown task. Recent works have studied the IRL problem from the perspective of recovering the feasible reward set, i.e., the class reward functions that are compatible with a unique optimal expert. However, in several problems of interest it is possible to observe the behavior of multiple experts with different degree of optimality (c.g.. racing drivers whose skills ranges from amateurs professionals). For this reason, in this work, focus the reconstruction the feasible reward set when, in addition to demonstrations from the optimal expert, observe the behavior of multiple sub-optimal experts. Given this problem, we first study the theoretical properties showing that the presence of multiple sub-optimal experts, in addition to the optimal one, significantly shrink the set of compatible rewards, ultimately mitigating the inherent ambiguity of IRL. Furthermore, reward set with a generative model and analyze a uniform sampling algorithm that turns be minimax optimal whenever the sub-optimal experts' performance level is sufficiently close to that of the optimal expert.
study the statistical complexity of estimating the feasible
Introduction
deals with the problem recovering a reward function that explains the behavior of expert agent who is assumed to act optimally in underlying unknown task. Over the years, the IRL problem has consistently captured the attention of the research community (see, for instance, [4] and [1] for in-depth surveys). Indeed, this general scenario, where the reward function needs to be learned, emerges in numerous real-world applications. A example arises from human-in-the-lonn explicit specification the human's goal in the form of a reward function is often unavailable. Notably, humans encounter difficulty in expressing their intentions in numerical form, preferring instead to demonstrate what they perceive as the correct behavior. Once we retrieve a reward function, (i) obtain explicit information for understanding the expert's choices, and, furthermore, (ii) can utilize it to train reinforcement learning agents, even under shifts in the underlying system.
Inverse Reinforcement Learning [IRL, 26
settings (25). where the expert is human solving task, and an
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Since the seminal work [26,, IRL has emerged as significantly complex task. One of its primary challenges lies in the intrinsic ill posed nature of the problem, as multiple reward functions compatible with the expert's behavior exist. Recently, a promising avenue of research [24 this ambiguity issue from an intriguing perspective. Specifically, this strand of works focuses on estimating all the reward functions that are compatible with the observed demonstration, thereby postponing the selection of the reward and directing their focus solely on the expert's intentions.
19 22
has tackled
Nevertheless, these approaches based on recovering the feasible set 24 more articulated situations that arise in the real world. In several problems of interest, it is possible to observe the behavior of multiple agents with different degrees of expertise. As an illustrative example, consider the human-in -aatu----tth--oog settings, mentioned above, in which we are interested in recovering reward functions that explain the intent behind racing drivers. In this scenario, racing car companies typically have access to variety of drivers with diverse skills, including professionals, test drivers, and emerging talents from developmental programs. In this context, while the focus is typically on the reward function of professional drivers, we expect a proficient IRI, method to effectively leverage demonstrations provided by drivers with lower expertise. From an intuitive perspective, if we have some information on the degree of expertise of other drivers, we expect that, by exploiting their demonstrations, we can reduce the ambiguity of IRL problem.
22 fall short in modeling
With these motivations, in this work, we extend the IRL formulation as the reconstruction of the feasible reward set to settings where, in addition to demonstrations from an optimal expert, we observe the behavior of multiple sub-optimal experts, of which we know a bound on their sub-optimality. More specifically, we will primarily focus in answering the following theoretical questions:
(Q1) How does the presence of sub-optimal experts affect the set of reward functions that are compatible with the observed behaviors? Can they mitigate the intrinsic ambiguity of IRL? (Q2) What is the statistical complexity of estimating the set of reward functions that are compatible with the given experts? How does it compare against the one of single-expes IRL problems?
Contributions and Outline. After providing the necessary background, we introduce the novel problem of Inverse Reinforcement Learning with multiple and sub-optimal experts (IRL-SE, Section 2). We then proceed by studying the theoretical properties of the class of reward functions that are compatible with given set of experts under the assumption that upper bound on the performance between a sub-optimal expert and the optimal expert is available to the designer of the IRL system (Section 3). Our findings indicate that having multiple sub-optimal experts can significantly shrink the set of compatible rewards, thereby mitigating the ambiguity issue that affects IRL. Leveraging our previous results, we continue by studying the statistical complexity of estimating the feasible reward set with a generative model (Section 4. To this end, after formally introducing a Probabilistic Approximately Correct [PAC,9] 9 framework, we derive a novel lower bound on the number of samples that are required to obtain an accurate estimate of the feasible reward set. Then, we present a uniform sampling algorithm and analyze its theoretical guarantees. Our results show that (i) the IRL. problem with sub-optimal experts is statistically harder than the single expert IRL setting, and (ii) that the uniform sampling algorithm is minimax optimal whenever the sub-optimal experts performance level is sufficiently close to the one of the optimal expert. Finally, we conclude with discussion on existing works (Section 5) and by highlighting potential avenues for future research (Section 6)
2 Preliminaries
In this section, we provide the notation and essential concepts employed throughout this document. Appendix (A contains tables of symbols and a summary of the notation.
Notation. Let X be a finite set, we denote with A the set of probability measures over X. Let }' be a set, we denote with A the set of functions f y + A Given f E R", we denote with ||/ the infinite norm of f. Let X' and X' be two non-empty subsets of a met- ric space ()), d). we define the Hausdorff distance [3 between X and X' as Ha(X,'') max(sup inf d(z, x'), sup.ru infaex d(z,x')}. The Hausdorff distance directly de- pends on the metric d. We denote with 1, the n-dimensional vector given by (I,...,1)".
Markoy Decision Processes. Markov Decision Process without a reward function (MDPIR) is tuple M (S,A,p,)) 7), where S is the set of states, A is the set of actions, p E A is

---

the transition probability kernel, and y E [0, 1) is the discount factor. We consider finite state and action spaces, namely |S| S and |A] A. A Markov Decision Process [M obtained by combining an MDPAR M with reward function E RRSAA, Without loss of generality, we assume reward functions bounded [0, 1). We denote with M U the resulting MDP. The behavior of an Ag. that, for each state, prescribes distribution over actions.
agent is described by a policy
Operators. Let f E R and g E RSxA, We denote with P and π the operators induced by the transition model p and the policy respectively Specifically, Pf a) =xrss p(s'|s, a) and (s(s) Ened T(als)g(( a). Moreover, we introduce the operators E and B" defined as: Ef(s, a) = f(s) and (B*g) (s, = {a(als) = 0} g(s, a). Finally, we define d f as the expecta- tion of f under the discounted occupancy measure: d= (Is -XP) f Ei=0
respeciiely__Spcciiaallll
Value Functions and Optimality. Given an MDP MUr and a policy x, the O-function QMur represents the expected discounted sum of rewards collected in M U starting from (s, a) and following policy л. Formally:
+00 (s) Σ
( 5,00 a
where the expectation is taken w.r.t. the stochasticity of the policy and the environment, i.e.. 8++1 p(]|s), ar) and a, ~ T-|(s)). The V-function Vūur is the expectation of the Q-function over the action space, namely V M.u
rQu... The advantage function A immediate gain of taking a given action, rather than following policy т. A policy π is optimal if has non non-posion constooiiive advantage in each-state action pair; namely Aju S holds element-wise.
QMur EV is the
Inverse Reinforcement Learning. An Inverse Reinforcement Learning [IRL., 26 problem is tuple 2 (M, TE), where M is an MDPAR and F E A is the expert policy. Given a reward function E 5x5A we say that r feasible for 2 if it compatible with the behavior of the expert, namely Te is an optimal policy for the MDP M r. We denote with Ry the set of feasible reward functions:
Rs = fr== [0, 1s
TTE
MUr 50}-
The set Ray named feasible reward set [24 19 22 To characterize the set Rg. 24 have shown that a reward function r belongs to RB and only if there exists ( E SxA and E R such that:
r r= - ( + (E PPV..
(2)
Thus, each reward function in Ro, is the sum of two components. The first one, =B which is non-zero only when (a(ass) = 0, can be interpreted as the advantage function AM The second one, (E - 105--PP V,V, instead, can be interpreted as seward-shaping via function V, which maintains the optimality of the expert's ' policy (26). follows that || S (1 (1->)) and |K| I (1-7)-1
Sub-Optimal Experts and the Feasible Reward Set
In this section, we extend the IRL formulation to problems where, in addition to demonstrations from an optimal expert, we observe the behaviors of multiple and sub-optimal experts. After having formulated and motivated the problem (Section 3.Ip. delve into the theoretical properties of the induced feasible reward set, by providing both an implicit (Section (3.) and explicit (Section (33) descriptions. Our results indicate that the presence of sub-optimal experts significantly shrink the feasible set of compatible rewards, thus, mitigating the ambiguity issue of IRL.
3.1 Problem Formulation
We define the Inverse Reinforcement Learning problem with multiple and Sub-optimal Experts (IRL- SE) as a tuple B (M, TE, ( w+1 (E.) where M is an MDPIR, TE, is the policy of an
We use the symbol to indicate both the operator and the policy. In the following, the intended meaning will be clear from the context.
3

---

n+1 optimal expert (TE)) 1= are collection of n sub-optimal experts policies, and (5:)=22 are the corresponding sub-optimality bounds. More concretely, & represents a known upper bound on the performance gap between the optimal expert and the i-th sub-optimal expert. Consequently, a reward function r R.SAA is feasible for B if TE is an optimal policy for the MDP M Ur and if:
Vi f2....., n 1}:
V VMürll S.
(3)
Thus, feasible reward must make the value function VM of the i-th expert smaller than that of the optimal expert (s) = (s) by no more than the threshold &. uniformly over
E S. We denote by Rg the set of feasible rewards for B, i.c. E [0. 1| belongs to R&g. if (i) Auur S 0 and (ii) Equation (3) holds. Notice that, whenever no sub-optimal expert present, we recover the definition of the feasible set for single-expert IRL problems, i.e., Rag in Equation (
We remark that & can even be crude overestimate (i.e., an upper bound) of the sub-optimality of expert i. Nevertheless, as we shall see, the ability of the sub-optimal policy Tæ; in mitigating the IRL. ambiguity, i.e., shrinking the feasible reward set, will be tightly connected on the magnitude of The following examples illustrate how an expression & can be obtained in common scenarios with no knowledge of the (possible) reward function optimized by the expert policy TE, Formal proof for these statements are reported in Appendix [
Example 3.1. Suppose that the i-th sub-optimal expert TE, is optimal for the same reward function that TT, is optimizing for, but under different transition model P.. this case, ||V Murlll I
2x (1-7)² max(s, [|P({|s, a) (- a)lla =: &, holds for all rewards r.
Example 3.2. Suppose that the i-th that nT, is optimizing for, but using a different discount factor y'. In this case, ||V 1o I
expert TE, is optimal for the same reward function
2 b- 7J =: E, holds for all rewards r.
Example 3.3. Suppose that the i-th sub-optimal expert TE, is sufficiently close to the optimal policy TE namely that max,es ||Tæ, (-(s)-=re TE. (+1s)lla I e. In this case, || [IV -V S I E
holds for all rewards r.
3.2 Implicit Formulation of R-g
In this section, we analyze the implicit description of the feasible reward set Rg. From its definition (Equations ① and (3)) a reward function r E [0, 1] belongs to Ros if and only if the following
conditions are satisfied:
(i) Q RE (sr a) V (s)
(s, E E x A nE, (a|s) () > 0. ((s,a) E S x A: TE, (a =
Q Mur (s, a) S Vir (s)
(iii) MU. (8) S Vie (s) +
Vs EsES, vi E (2, . +
Specifically, conditions (i) and (ii) directly encode the optimality of policy TE, for M r., i.e., the advantage function A non-positive. Condition (iii), on the other hand, arises from the presence of sub-optimal experts, and directly follows from Equation (3). At this point, by closely examining these conditions, it is possible to gain insight into the advantages and limitations associated with the presence of multiple and sub-optimal experts. Consider, the following illustrative examples.
Example 3.4. Suppose that TE. = TE, holds for all E f2...., n + 1}. Condition (iii) is clearly satisfied for any reward function Thus, the feasible reward set R5g is determined by the requirement that the advantage function of TE, is non-negative and, as a consequence, the set Rg coincides with the one of the single-expert IRL problem, namely RB Rg. Analogously, if E; > (1 7)) holds for all sub-optimal experts, condition (iii) is vacuous, and, similarly, R& reduces to Ræx-
Example 3.5. Consider the MDP with 2 states depicted in Figure D and suppose that only one additional sub-optimal expert is present. The optimal and the sub-optimal experts follow different policies in Sg. From the definition of Rgg, we can see that, addition to the constraint r(S,, Z r(So, A2) (i.e., nE, is optimal), condition (iii) enforces further relationship between r(So. A1) and r r(So. A2), i.e., r(So, A1) r(Su, A2) S & If & is sufficiently small (i.e., &, < 1), the presence of the sub-optimal experts significantly reduces the set of compatible rewards (Figure
Forr the sake of exposition, we consider a single optimal expert. The extension to cases where multiple optimal policies available is straightforward. For further details on this point see Appendix B

---

A1l TE. (1
r(S,, A2)
0.75
0.75
0.5
0.5
So
Si
A
0.25
0.25
0
0.25 0.5 0.75
0 0.25 0.5 0.75
r(S,,
r(Su.
Aal NE, (42) So)
Figure 2: Visualization of the feasible reward set (i.e., shaded red area) for the problems described in Example On the left, the feasible reward set for the single-expert IRL. problem and on the right the feasible reward set for the multiple and sub-optimal setting when using 0.5.
Figure 1: MDP example, with 2 states and 2 ex- perts, that highlights the benefits of sub-optimal experts (Example 3.5 In S1 both TE, and TE, identical, i.c., TE (A = TE (A[S1) = 1.
Abstracting away from the examples, we deduce that whenever (a) the sub-optimal experts exhibit behavior significantly different from that of the optimal expert and (b) their performance level is sufficiently close to being optimal, Rg can notably shrink compared to Rag In the next section, through an explicit formulation of the feasible set, we analyze this phenomenon quantitatively.
3.3 Explicit Formulation of R.g
In this section, we continue by providing an explicit formulation of the feasible Rg. The following result (proof in Appendix D) summarizes our findings.
Theorem 3.6. Let 2 be an IRL problem with sub-optimal experts. Let r E 10,1 Then, r E Rag if and only if there exists Ç E RSSA and V E RRS such that the following conditions are satisfied: 20
r r= - c+ S+
and. for all (2...., n 1}:
T TE, BTEI 1sE,.
(5)
Theorem 3.6 deserves some comments. First, from Equation 4 we see that a necessary condition for having E Rg is that can be expressed as the sum of two components, namely - -B= 5t (E' - VVV.. This result is a direct consequence of the fact that TE, is an optimal policy for M U
and
and, in this sense, it recovers the existing condition of single expert IRL settings (Equation 2 24
Sub-optimal experts constrain the sub-optimalitty gaps. The role of the sub-optimal experts is apparent in Equation (5) enforcing set of linear constraints the values that ( can take Since, as discussed in Section 2 - BT represents the advantage function of the optimal policy TE₁ Equation (5) limits how much sub-optimal the values of actions not played by nE, can be. Indeed, TEj the resulting Q-function of the optimal expert can be expressed as Q BB < EV (24).
Sub-optimal experts affect only states in which they behave sub-optimally. The linear constraints Equation (5) are expressed
terms of Tæ, B Ç. As a consequence, they will only affect state- action pairs (s.a) a) S x A that played by the sub-optimal experts (i.e., TE. (als) 0) and that are not played by the optimal expert (i.e., Tg, (a|s) = 0). Therefore. as previously highlighted with the implicit formulation of Ra. sub-optimal expert TE, should behave differently w.r.t. the optimal expert in order to provide meaningful information and reduce the feasible reward set. Furthermore, the constraints ( expressed w.r.t. expected discounted occupancy of NE.
Contrarr single-experts IRL problems, Equation is only necessary condition for having R.g. Moreover. whenever n (i.e.. we have optimal expert nE, only). (neorem[3.6/reducee Equation and, thus, it smoothly generalizes existing results for the classical IRI. prohlem.
TThaks to the linearity, testing whether given satisties Equation (5) is computationally efficient.
5

---

Therefore, Equation (5) has provided precise mathematical description (i.e., if and only if conditions) of the effect produced by the presence of sub-optimal experts on the feasible rewards r.
While in classical IRL. problems, we have ||C]l S (1 - -- the maximum value ( can take in the sub-optimal experts case may be smaller. Let fix state s' E S and sub-optimal expert i E n + I: then, the constraint associated to state s' in Equation (5) can be written as:
Σ BES
Σ
TE, (als))(ss,)) Ei
(6)
BEATE, (a/s)=u
where d
(s) (8) is the discounted expected number of times that policy TE, visits state 8 E S starting from state s' From Equation ( obtain necessary conditions on the values of Ç. More specifically, let (((s, a) C {2.... n + } be the subset of sub-optimal experts such that Tg, (a]s) > 0. Then, for each state-action pair (s, a) E S A such that TE, (als) and TE, (als) > O, we have that:
((s,a) S min k(s, a).
- = g(s,a), where k(s, = min
&
(7)
(EX(..)) d' FL (a)s),
The term kss,a) directly follows from Equation (6. while (1-7)-1 is the maximum value that any ((s, a) can take, and arises, as in the classical IRL setting, from the fact that advantage functions are bounded by (1-7)-1 for any reward function. Thus, confirming our previous observations, Equation (7) implies a significant potential reduction in the maximum values that the advantage function can take, i... how much sub-optimal an action not played by TE, can be in terms of Q-function values.
Example 3.7. Consider an IRL. problem with only one additional sub-optimal expert. Suppose that TE, and π are deterministic. For all state-action pairs in which TE, (als) 0 and TE, (als) = 1, Equation 7 implies that ((s, a) S min { (1 - -))- If & is significantly smaller than (1 - -1- we obtain notable restriction on the set of feasible reward functions.
Remark 3.8 (About alternative Sub-optimality Formulations). We have described the sub-optimal
experts by means of upper bounds on the value functions gaps: i.e., MUr - VTT, S 1s In principle, we may consider lower bounds on the value functions gaps; i.c. VMUr- - -VT 2 1s Intuitively, in the former case, we know that an expert is sub-optimal at most E.. whereas, in the latter, that an expert sub-optimal at least &.. Our theory smoothly generalizes to these latter scenario obtaining analogous of Theorem 3.6 where the constraints of Equation (5) are replaced with d B Ç 2 1sE,. We refer the reader to Theorem D.5 for a formal statement.
Mur
4 Learning the Feasible Set with Sub-Optimal Experts
In this section, we address the statistical complexity of estimating R.g. with generative model. Specifically, we first introduce Probabilistic Approximately Correct (PAC) framework (Section 4.1). Then, we study the statistical complexity of the problem by presenting lower bounds on the sample complexity any algorithm requires in order to correctly identify the feasible set (Section 4.1) Finally, we propose uniform sampling algorithm and analyze its theoretical guarantees (Section 4.3 0
4.1 PAC Framework
We define a learning algorithm for an IRL-SE problem 2 as a tuple 21 = (r, v) where T is a stopping and v = (vi)teN is a history-dependent sampling strategy, i.e., Us E A
SXA D where
D. (S x A S (A)*+1yf is the set of samples collected up to time step & N. At each time step i, the algorithm selects a state-action pair (st, Qz) ~ Pt, and observes sample st ~ p(-|st, ax) from the environment, together with actions sampled from the experts' policy, namely (a )ii where ~ TE, (-Isz). The observed realizations D, are then used to update the sampling strategy Vt. and the process goes on until the stopping rule 7 is satisfied. Then, the algorithm leverages the
In Appendix I we also provide some simple numerical experiments that aim at visualizing the reduction of the feasible reward set. Forr the sake of presentation, all results are presented under the assumption that Ta, is deterministic. The extension the case in which mE; stochastic presented in Appendix

---

collected data D, to output the estimate of the feasible reward set R.. We are interested in designing algorithms that, for any desired accuracy E (0, 1) and any risk parameter ó (0, 1). guarantee that: Fa, (Hx (Rg, R.) c) S.
(8)
We refer to these algorithms as (e, 6) oo-corttct identification strategies and we define their sample complexity as the total number of interactions with the generative model before stopping, i.e., T.
4.2 Lower Bound
In this section, we present lower bounds on the sample complexity that any (c, - algorithm needs to perform to learn Rg. The following theorem (proof in Appendix ED reports our result. Theorem 4.1. Lef Q be (e, 8) -corrctt algorithm for the IRI. problem with sub-optimal experts. There exists a problem instance B such that the expected sample complexity is lower bounded by:
E Eg ( (2(1-7)²
SA
llog
(
+ +5)))
where (1-)) hides constant dependencies. Let min 0 be:
Tmin
min ie (2............ (s.a)e8x A s)20
min
TF, (a|s);
(10)
and let 9o "T max
max (2, +1) Es. Then, there exists an instance B in which qo < such that:
9 log (1)
E a [T] 2
(1I)
Theorem 4.1 provides two distinct lower bounds (i.e., Equations 9 and for IRL problems with sub- optimal experts. Whenever do holds, the lower bound for the IRL-SE setting can be expressed as the maximum between Equation and [1]. We now comment in-depth on these two equations.
Sub-optimal experts do not reduce the statistical complexity of IRI. Concerning Equation (9) as our analysis reveals, it directly arises from the problem of estimating rewards functions that are compatible with Te, (i.e., with Equation 4 Theorem (36)). In this sense, it represents the complexity of single-expert IRL problems As consequence of the structure of the feasible set we derived in Theorem 3.6 this leads to Tower bound also for the multiple sub-optimal experts setting. Therefore, Equation ( formally shows that the sub-optimal expert setting is always at least as difficult as the single expert IRL problem.
Sub-optimal experts have introduce further statistical complexities. Equation (1). the other hand, is tightly related to the presence of sub-optimal experts. More precisely, under the assumption that go < (e.g., for sufficiently small values of {:), it shows dependency in the lower bound of factor TH min. where miin is the minimum probability with which sub-optimal experts plays their actions. From an intuitive perspective, its presence is related to the difficulty in estimating reward functions that are compatible with Equation 55) in Theorem 3.6 As we have shown in Section [ the presence of sub-optimal experts can limit the value of ( with relationship that involves Tiin (i.e., Equation (7). As our analysis will reveal, the proof of Equation (TT) is directly related these worst-case upper-bounds on Ç. We remark that, according to the value of Tmin- Equation [II can be significantly
larger than Equation (5). thus showing an increased difficulty in the statistical complexity that is related to the stochasticity of sub- sub-optimal experts.
We remark that represents the number of calls the generative model and that each call, in our setting, provides demonstrations from each (sub- jopt-oottimll expert. It can be shown that, by slightly modifying the learning formalism, Equation (11) actually represents lower bound the number of samples that should be gathered from each sub-optimal expert In this sense, the statistical complexity increases significantly in the sub-optimal expert setting compared to the single expert one.
7 We notice that similar results were presented [22 the -orie-h single expert IRL problem. In this work, we extend their analysis the infinite-horizon setting.
For further details, refer the reader Appendix
7

---

Therefore, to conclude. we notice that, in order to gain the reduction in the feasible reward set that we discussed in Section [ we need to gather additional sampled demonstrations from the sub-optimal experts. This unavoidable trade-off is a direct consequence of the structure of the feasible set Rog that we derived Theorem 3.6] and, arises from the statistical complexity of estimating reward functions that are compatible with the linear constraints of Equation
4.3 Uniform Sampling Algorithm
In this section, we present the Uniform Sam- pling algorithm for Inverse RL with Suboptimal Experts (US-IRL-SE).
Algorithm 1 US-IRL-SE Algorithm
Require: Number of samples for each (s, a) pair
m
Algorithm. The pseudo-code can be found in Algorithm [ US-IRL-SE takes as input the number of samples m that will be queried to the generative model in each state-action pair. Then, it uniformly gathers data across the entire state-action space, and it updates the empirical estimates Pr and (ft, M of the transition model and expert's policies. Let {l....,m, m tuples D. = [(s}, aj, s'y, (a) /i=l p(-|sj, a,). and aj TE, (+1sy). Given D,, we define the empirical transition model P. and the empirical experts' policy S.. as follows:
1: for t E (1....,mi) m.] do
2: Collect (s', (=()))))))))))))))))))))) where s' ~ p(1)s,a)
and (()) TE, (-1s) from each (s, 8x
A and E {1 (1..., n +++1)
3: Update io and (f,,), according to
Equation (2
4: end for
D, be dataset of (00+1)11 ) where s'z
5: return R 8m
Ni(sia,s') Nils.a)
if Ne(, otherwise
(x.)) Ni(o)
if >
pe(s'ss,a) =
(als)
(12)
otherwise
where Ni(s, a's) Ej 1[s))
(s,a, N,(s, =
Eves Ne(s, N.(s)
E(os)))A Ne(s,a, a, 8'), and N, a) = [[(ss, /0 = (s, a))- Then, we denote with B, the empirical IRL problem induced by P. and m+= Finally, the algorithm returns the feasible set R corresponding to the estimated IRL-SE problem Bn, defined in terms of pm and (fm, y++1
Sample Complexity Upper Bound The following theorem (proof in Appendix E}. describes the theoretical guarantees of US-IRL-SE.
Theorem 4.2. Let q1 min { ami ( & (1-11) 1)) and 92 max (1, Then, with a total budget of:
of (7)
SASS + log (2)) 1):
δ max
(13)
2 TTin
e² - 7)
US-IRL-SE is (c, ()corret and Ō hides constant and logarithmic dependencies.
Theorem 4.2 deserves some comments. First of all, it shows that when the total number of queries to the generative is sufficiently large, US-IRL-SE is (e, 5)-correct, and its sample complexity is provided Equation [3). Since m represents the number of calls to the generative model in each state-action pair, its expression can simply be calculated dividing Equation (13) by S SA As a consequence, we remark that, in order to compute the value of m, the algorithm requires knowledge of the minimum probability miin with which the sub-optimal experts play their actions.
US-IRL-SE is minimax optimal when - < 1. Equation 13 is the maximum between two
terms whose expressions closely resemble the lower bound of Theorem 4.1 The only difference arises in the definition of go. and 92. We remark that, whenever the sub- optimml expert's 's performance level sufficiently close to the one of the optimal expert, i.e., - < for all i E f2...., + 1}.
TTe exact expression of m (i.e., constants and hidden logarithmic factors) is provided in Appendix

---

Equation 13 exactly recovers the lower bound that we presented in Theorem 4.1 Indeed, under this condition, it holds that qa = qi and Q2 1. We recall that, according to Theorem 3.6 as the values of Ei's decrease, the feasible reward set is substantially reduced. In this sense, US-IRI.-SE enjoys minimax optimality in the most interesting scenarios where the presence of sub-optimal experts is particularly useful for mitigating the intrinsic ambiguity that affects IRI, pro.bersssss
We highlight that the proof of Theorem 4.2 poses notable technical challenges beyond the ones of the analysis for standard IRL (24]. In our setting, studying how the Hausdorff distance between Ra and R gg decreases as we collect more samples requires taking into account that these feasible reward sets are subject to the peculiar structure identified in Theorem 3.6] namely the set of constraints of Equation (5) arising from the presence of sub-optimal experts. We study, with probabilistic arguments, error terms of the form || - proja, Sl where
Technical challenges of Theorem 4.2
is feasible for the exact problem B, S4 denotes the set of & that are compatible with the empirical problem B,, and proj(-) denotes the infinite norm projection. Analyzing these terms to obtain nearly optimal rates requires careful considerations the geometry of feasible reward set that the sub-optimal experts induce. For further details, we refer the interested reader to Appendix E
5 Related Works
In this section, we survey the works about IRL and the presence of multiple (sub-optimal) experts that are related to our proposal.
Inverse Reinforcement Learning. Historically, solving an IRL problem [ involves determining a reward function that is compatible with the behavior of an optimal expert. Since the seminal work of (26), the problem has been recognized as ill-posed, as multiple reward functions that satisfies this requirement exists 34 For this reason, over the years, several algorithmic criteria have been introduced to address this ambiguity issue. These criteria includes maximum margin 300, Bayesian approaches (28), maximum entropy (37), and many others fe.g..121 23 36). More recently, new line of works have circumvented the ambiguity issue by redefining the IRL task as the problem of estimating the entire feasible reward set (24 19 22] In our work, we take this novel perspective, and, in this sense, this recent research strand is the most related to our document. Specifically, of particular interests is the work of [22). In their work, the authors study, for the first time, lower bounds for the single-expert IRL problem in finite horizon settings. Furthermore, they show that uniform sampling algorithm is minimax optimal for this task. Nevertheless, it has remarked that this recent strand of research focuses entirely on single expert problems. As we have shown, however, the extension to the multiple and sub-optimal experts setting requires non-trivial effort. The reason is that the feasible reward set significantly differ (see, e.g., Theorem 3.6), and the problem is harder from statistical perspective (see, e.g., Theorem
Multiple and/or Sub-optimal Experts. The presence of multiple/sub-optiie experts has garnered attention in the Imitation Learning [II,[I]] community. In IL problems, contrary to IRI., the goal lies in directly leveraging demonstrations of optimal behavior to accelerate the training process of reinforcement learning algorithms. In this context, works that are close in spirit to ours are 11 13 6 20]. Here, the authors extend the IL formulation account for the fact that demonstrations are provided from multiple and/or sub-optimal experts. However, unlike our specific focus, their emphasis is understanding how to effectively exploit imperfect demonstrations improve training of RI. agents. In our work, instead, we exploit the presence of sub-optimal experts to reduce the intrinsic ambiguity that affects the IRL formulation. In this sense, our work is complementary to several studies that analyzed how to improve the identifiability of the reward function in IRL problems by making additional structural assumptions. These include the possibility of observing and focusing on peculiar types of MDPs that allows for strong theoretical guarantees [e.g., & 1S 5) Along this line of work, the most related to ours is 32 Here, the authors study how the presence of multiple experts impact the identifiability of the reward function. Contrary to our work, however, the authors assume each expert to follow an entropy regularized objective and, furthermore, they focus on the case in which all experts act optimally in the underlying environment. In this sense, our work encompasses a wider spectrum of applications, we do not require optimality for each of the expert, nor an entropy
an optimal expert interacting with several MDPs [e.g.. 30 3 2

---

regularized objective. Furthermore, it has to be remarked that the multiple expert setting and IRL have been studied in [18] with the goal of providing practical algorithms that can be used in real- world applications. Also in this scenario, each expert is assumed to act optimally in the underlying domain. Finally, our work is related to approaches that aimed at extracting a single reward function by leveraging possibly sub-optimal demonstrations [e.g.. [5] 16 12 29). In our work, instead, we take a different theoretical perspective, and focus on the set of reward functions that are compatible with multiple sub-optimal experts.
Conclusions
In this work, we studied the novel problem of Inverse RL where, in addition to demonstrations from an optimal expert, we can observe the behavior of multiple and sub-optimal experts. More precisely, we first investigated the theoretical properties the class of reward functions that are compatible with given set of experts, i.e., the feasible reward set. Our results formally show that, by exploiting this additional structure, it is possible to significantly reduce the intrinsic ambiguity that affects the IRL. formulation. Secondly, we have tackled the statistical complexity of estimating the feasible reward set from a generative model. More precisely, we have shown that a uniform sampling algorithm is minimax optimal whenever the performance level of the sub-optimal expert is sufficiently close to the one of the optimal expert.
Our research opens up intriguing avenues for future studies, In the following, we highlight several possibilities.
Closing the Theoretical Gap The results that we presented in Section do completely match. When the performance of the sub-optimal experts are not sufficiently close to the one of the optimal agent, the upper bound differs from the lower bound. Closing this gap, either by (i) developing tighter lower bounds or (ii) proposing novel algorithms and/or refining the analysis of US-IRL to achieve tighter upper bounds, an interesting future direction. This would allow for a complete understanding of the statistical complexity of the problem.
Offline IRL with Sub-Optimal Experts Secondly, we note that this work leverages the presence of generative model in the algorithm design. In the future, would be interesting to remove this assumption by considering an offline setting where only a dataset of collected demonstrations is available to the learning system. This formulation more practical since, in several real-wort IRL. applications [88], only dataset of pre-collected demonstrations is available to the designer of the IRL system. We also note that this setting is, in principle, more challenging, as the data coverage of the dataset is not under the control of the IRL system.
Large State-Action Spaces For instance, since we have shown that sub-optimal experts can improve the identifiability of the reward function, future research should focus on building practical algorithms that can exploit this additional structure. To this end, as an intermediate step, it might be interesting to extend our results to the case in which the reward function is expressed linear combination of features. This approach would enable addressing infinite state-spaces [e.g.. (e.g..6).
Acknowledgments and Disclosure of Funding
Funded by the European Union Next Generation EU within the project NRPP M4C2, Investment I..3 DD. 341 15 march 2022 FAIR- Future Artificial Intelligence Research - Spoke 4 PE00000013 D53C22002380006 AI4REALNET has received funding from European Union's 's Horizon Europe Research and Innovation programme under the Grant Agreement No 101 19527. Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union. Neither the European Union nor the granting authority can be held responsible for them.
References
[1] Stephen Adams, Tyler Cody, and Peter A Beling. survey of inverse reinforcement learning. Artificial Intelligence Review, 5306):4007-4346, 2022.
10

---

[2] Kareem Amin, Nan Jiang, and Satinder Singh. Repeated inverse reinforcement learning. Advances neural information processing systems, 30, 2017.
[3] Kareem Amin and Satinder Singh. Towards resolving unidentifiabilitty in inverse reinforcement learning. arXiv preprini arXiv:1601. .66569, 2016.
[4] Saurabh Arora and Prashant Doshi. A survey of inverse reinforcement learning: Challenges, methods and progress. Artificial Intelligence, 297: 2021.
[5] Haoyang Cao, Samuel N Cohen, and Lukasz Szpruch. Identifiability in inverse reinforcement learning. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021.
[6] Ching-An Cheng, Andrey Kolobov, and Alckh Agarwal. Policy improvement via imitation of multiple oracles. Advances in Neural Information Processing Systems, 33:5587-5598, 2020.
[7] Joseph I. Doob. Measure theory, volume 143. Springer Science & Business Media, 2012.
[8] Krishnamurthy Dvijotham and Emanuel Todorov. Inverse optimal control with linearly-solvable mdps. In Proceedings of the 27th International conference on machine learning (ICMI-110, pages 335-342, 2010.
[9] Eyal Even-Dar, Shie Mannor, and Yishay Mansour. Pac bounds for multi-armed bandit and markov decision processes. In Computational Learning Theory: 15th Anmual Conference on Computational Learning Theory, COLT 2002 Sydney, Australia, July 8-10, 2002 Proceedings
15, pages 255-270. Springer, 2002.
[10] Torben Hagerup and Christine Rüb. A guided tour of chernoff bounds. Information processing letters, 300 1990.
[11] Ahmed Hussein, Mohamed Medhat Gaber, Eyad Elyan, and Chrisina Jayne. Imitation learning:
A survey of learning methods. ACM Computing Surveys (CSUR), 50(2):1-35, 2017.
[12] Alexis Jacq, Matthieu Geist, Ana Paiva, and Olivier Pietquin. Learning from a learner. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 2999-2999. PMLR, 09-15 Jun 2019.
[13] Mingxuan Jing, Xiaojian Ma. Wenbing Huang, Fuchun Sun, Chao Yang. Bin Fang, and Huaping Liu. Reinforcement learning from imperfect demonstrations under soft expert guidance. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages 5109-5116 16. 2020.
[14] Anders Jonsson, Emilie Kaufmann, Pierre Ménard, Omar Darwiche Domingues, Edouard Leurent, and Michal Valko. Planning in markov decision processes with gap-dependent sample complexity. Advances in Neural Information Processing Systems, 33: 253-1163,, 2020.
[15] Kuno Kim, Shivam Garg, Kirankumar Shiragur, and Stefano Ermon. Reward identification in inverse reinforcement learning. In International Conference on Machine Learning, pages 5496-5505. PMLR, 2021.
[16] Edouard Klein, Matthieu Geist, and Olivier Pietquin. Batch, off-policy and model-free appren- ticeship learning. In European Workshop on Reinforcement Learning, pages 285-296. Springer, 2011.
[17] Andrey Kurenkov, Ajay Mandlekar, Roberto Martin-Martin Silvio Savarese, and Animesh Garg. Ac-teach: A bayesian actor-criti method for policy learning with an ensemble of suboptimal teachers. In Proceedings of the Conference on Robot Learning, 2020.
[18] Amarildo Likmeta, Alberto Maria Metelli, Giorgia Ramponi, Andrea Tirinzoni, Matteo Giuliani, and Marcello Restelli. Dealing with multiple experts and non-stationarity in inverse rein- forcement learning: an application real-life problems. Machine Learning, 110:2541-2576. 2021.
11

---

[19] David Lindner, Andreas Krause, and Giorgia Ramponi. Active exploration for inverse re- inforcement learning. Advances Neural Information Processing Systems, 35:5843-5853, 2022.
[20] Xuefeng Liu, Takuma Yoneda, Chaoqi Wang, Matthew Walter, and Yuxin Chen. Active policy improvement from multiple black-box oracles. In International Conference on Machine Learning, pages 22320 222377.. PMLR, 2023.
[21] Anirudha Majumdar, Sumeet Singh, Ajay Mandlekar, and Marco Pavone. Risk-sensitive inverse reinforcement learning via coherent risk models. In Robolics: science and systems, volume 16, page 117, 2017.
[22] Alberto Maria Metelli, Filippo Lazzati, and Marcello Restelli. Towards theoretical understanding of inverse reinforcement learning, arXiv preprint 2en::2304..99666 2023.
[23] Alberto Maria Metelli, Matteo Pirotta, and Marcello Restelli. Compatible reward inverse reinforcement learning. Advances in neural information processing systems, 30, 2017.
[24] Alberto Maria Metelli, Giorgia Ramponi, Alessandro Concetti, and Marcello Restelli. Provably efficient learning of transferable rewards. In International Conference Machine Learning, pages 7665-7676. PMLR, 2021.
[25] Eduardo Mosqueira-Rey, Elena Hemenneez-Pereira, David Alonso-Ríos, José Bobes-Bascarán, and Angel Fernández- Human-in- in-the-loopp machine learning: A state of the art. Artificial Intelligence Review, 56(4):3005-3055 2023.
[26] Andrew Y Ng, Stuart Russell, al. Algorithms for inverse reinforcement learning. In Interna- tional Conference on Machine Learning, volume 1, page 2, 2000.
[27] Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
[28] Deepak Ramachandran and Eyal Amir. Bayesian inverse reinforcement learning. In IJCAI, volume 7, pages 2586-2591, 2007.
[29] Giorgia Ramponi, Gianluca Drappo. and Marcello Restelli. Inverse reinforcement learning from a gradient-basee learner. Advances in Neural Information Processing Systems, 33:2458-2468 2020.
[30] Nathan D Ratliff, J Andrew Bagnell, and Martin Zinkevich. Maximum margin planning. In Proceedings of the 23rd international conference on Machine learning, pages 729-736, 2006.
[31] R Tyrrell Rockafellar and Roger J-B Wets. Variational analysis, volume 317. Springer Science Business Media, 2009.
[32] Paul Rolland, Luca Viano, Norman Schürhoff, Boris Nikolov, and Volkan Cevher. Identifiability and generalizability from multiple experts in inverse reinforcement learning, Advances in Neural Information Processing Systems, 35:550-5644 56000-564770 2022.
[33] Igal Sason. On reverse pinsker inequalities. arXiv preprint arXiv: 150.007118,, 2015.
[34] Joar Max Viktor Skalse, Matthew Farrugia-Roherts, Stuart Russell, Alessandro Abate, and Adam Gleave. Invariance in policy optimisation and partial identifiability in reward learning. In Proceedings of the 40th International Conference on Machine Learning. 2023.
[35] Umar Syed and Robert E Schapire. A game-theoretic approach to apprenticeship learning. Advances neural information processing systems, 20, 2007.
[36] Siliang Zeng, Chenliang Li, Alfredo Garcia, and Mingyi Hong. Maximum-likelihonn inverse reinforcement learning with finite-time guarantees. Advances in Neural Information Processing Systems, 35:10122-10113 2022.
[37] Brian D Ziebart, Andrew L Maas, J Andrew Bagnell, Anind K Dey, et al. Maximum entropy inverse reinforcement learning. In Aaai, volume 8, pages 1433-1438. Chicago, IL, USA, 2008.
12

---

The structure of the supplementary materials is organized as follows:
Appendix provide tables that summaries the main symbols used this document.
Appendix describes how to extend our result to the multiple optimal expert setting.
Appendix provides proof Examples 3.1 3.3
Appendix provides formal proofs of the theoretical claims Section together with discussions on alternative formulations of the IRL-SE problem.
Appendix provides formal proofs of the theoretical claims of Section 4
Appendix discusses how extend our result to the setting in which TE, is stochastic.
Appendix discusses how to change the learning formalism to derive lower-bound that directly depends on the number of samples that are needed from each sub-optimal expert.
Appendix provides additional details on US-IRL-SE (i.e., exact description of m) and computational complexity analysis.
H
Appendix presents simple numerical experiments that highlights the reduction of the feasible reward set due to the presence of multiple and sub-optimal experts.
A Symbols and Notation
To begin, we provide tables that summaries the main symbols used this document. Table reports summary the notation used throughout the paper. Table 2 reports a precise definition of the operators used.
Table I: Notation
SYMBOL
MEANING
B
Inverse RL problem with single optimal agent.
B
Inverse RL problem with multiple and sub-optimal experts.
Number of sub-optimal experts, n E N>o-
TE.
Policy of the i-th expert. If = 1, the expert is optimal.
Sub-optimality of the i-th expert, where E (2...., n
1}.
TE
Empirical estimates of the i-th expert policy TE,
P
Empirical estimate the transition model p.
D:
Dataset of tuples from the generative model. Number of samples gathered at state-action pair (s, a) in D.. Number of samples gathered at state in D,
(s. a)
(s)
Empirical estimate the IRL-SE problem induced by and fg.
Ræ
Feasible reward set of single-agent IRL. problem.
Ro
Feasible reward set of a IRL-SE problem.
R
Feasible reward set of the IRL-SE problem induced by e and RÆ.-
Ho (Xx,
Hausdorff distance between set X and X'.
Learning algorithm for the US-IRL-SE problem. Sampling strategy of learning algorithm 2.
T
Stopping time (i.e., sample complexity) of learning algorithm Desired level of accuracy when estimating the feasible reward set.
8
Maximum risk tolerated when estimating the feasible reward set.
m
Number of samples that the US-IRL-SE algorithm gathers in each state-action pair.
B Additional Multiple Optimal Expert Setting
In this section, we discuss the extension of the IRL-SE setting to the case which multi- ple optimal policies are available. More specifically, define this IRL-SE setting tuple
13

---

Table 2: Operators
SYMBOL SIGNATURE
DEFINITION
R$ R
(Pf)(s, Plss
π
RSSAA + +RS
=f)(s)==nm m(als){(s,a)
E
RS R2XA
(Ef)(s,a) f(s)
B
RSXA RXXA
(BT = [{T(aas) = 0 f(s,a)
D
RSXA + RAA
(B* = -[(r(a(s) > f(s,a)
d"
R + R
(d" = +00 (()TP)(f)
Is
R$ + R
(Isf)(s) = f(s)
B (T (( where (#T,) n1 is set of nı optimal policies, (=
m2 sub-optimal policies with known degree of sub-optimality (E:)
At this point, one can verify that the shape of the feasible set R.g. is exactly the one of Theorem 3.6 where Equations
(5) obtained by replacing nE, with each optimal policy Tg. with
E R1).
Concerning learning the feasible reward set, is sufficient extend the generative model so that samples are gathered from all optimal and sub-optimal experts. The proof of Section holds almost unchanged.
C Proof of Examples 3.1 3.3
We now give formal proofs of Examples 3.1 3.3
Proof of Example 3.7 Consider two MDPs M, and My that differs only the transition kernel, which denote by P1 and p2. Suppose that Tg, and TE, optimal for M1 and Mr respectively. For any state s, it holds that:
TE (s) TB (b) S TH (s) My.r (s)
R8 My (s) T (t))
where we added and subtracted V- Mr
E M,ür due to the optimality of F in M2. Then, focus VIT;, MM,ur (8) T (s) (but an identical reasoning can be applied for the second difference as well):
and we used V M, Ur
S
TT (x) VTW,
M,j (8) = Σ TB. (a|s) aV (8) VM (8)))
+ - p2(s' [ (s'),
which, in turn, can be further bounded by:
1-7 |pI p2ll1
Σ TE, TE, (a|s)
Σ (s((sss, (s') Mr (s))
Unrolling the summation to iterate the aforementioned argument, and using the fact that E 7d 1 concludes the proof.
Proof of Example 3.2 this proof, we explicit the relationship of the value function with the discount factor y by writing V Then, it holds that:
TB, Mur (s) - Vo (s) < V TR. (s) (s)- Vi (s) + V (s) - V V (s),
where we added and subtracted V '2' (s), and we used V Mur (s) S
Tegi (s) due to the
Mur
optimality of TEa for the discount factor Y. Then, focus on = (s) Vit, .
(s). By the
14

---

definition of the value function, together with the fact that rewards are bounded in [0. 1]. we can rewrite this difference as;
+00
7 7
E (7' - ("(,," = =8] 5/5
>) -²)
identical argument holds for the second difference, thus concluding the proof.
Proof of Example 3.3 By using the definition of value function, we can rewrite V (M) V Mur as (T(E)) (als) - T. (s)s))r(ss a) + E. p(s' Is, a)VV Mur (s') ) V (s'))) this point, since rewards are bounded in [0, 1] and by the policy similarity assumption, have that the difference in value functions be upper bounded by e 7 p(5'|s, a) (Ur Mur (u)(s')) Unrolling
the summation iterate the aforementioned argument, and using the fact that Σ 7f concludes the proof.
D Proofs and Derivations of Section 3
In this section, we provide formal proofs of the theoretical results of Section 3 We begin by reporting for completeness some results from 24 that will be used our analysis.
Lemma D.1. Let B (M, πT) be single-agent IRL problem. Let [0,1]5xA then is feasible reward if and only for all (s E (S, it holds that:
(su a) Vuu TR
if T 00
ii)
(s - Mur S
if ( =0
Lemma D.2. Let B = (M, TE) be a single-agent IRL problem. A Q-function satisfies condition of Lemma D.1 if and only if there exist Ç R and V E =R such that:
Qm - - EV
Tg) be single-agent IRL problem. Let E RSA then is a feasible reward, if and only if there exist Ç E RSSA and E R$ such that:
Lemma D.3. Let B
B + (E->P)V
At this point, we proceed by proving Lemma that implicitly describes the of reward functions that are compatible with a IRL-SE problem.
Lemma D.4. Let B be an IRL problem with sub-optimal experts. Let r E [0,1]SxA Then, r E Rog and only if the following conditions satisfied:
(i) Thi = (s)
V(s TE, (a|s) > 0,
(ii) (s, (s)
V(s, a) TE, (als) = O,
(iii) Q I Mur + 156
Vi E (2..... n
Proof. Condition (i) and (ii) are necessary conditions for the claim to hold. This directly follows by the definition of Rg and from Lemma D.I At this point, what remains be proven is condition (ii)).
We begin by showing that, i E Rg then condition (iii) is satisfied. Since (i) and (ii) holds, sufficies to plug V - Mii < & within (i) and (ii) to obtain the desired result.
We conclude by showing that if (i)-(iii) are satisfied, then E Rag. Since (i) and (ii) holds, then, by Lemma D.1 we know that mg is optimal for MUr. remains to be proven that v= Muur V < &
holds well. However, since (i) holds, (iii) implies that VMU Vi (s) < {((s) holds for all s E S, thus concluding the proof.
We continue by proving Theorem 3.6
15

---

Theorem 3.6. Let B be an IRL problem with sub-optimal experts. Letr E [0,1] Then, E Rog if and only if there exists E R2 and V E R such that the following conditions are satisfied:
- B (E
(4)
and. for all i E f2...., 1}:
T B S 1s4.
(5)
Proof. First of all, Equation (4) is necessary condition for the claim hold. Indeed, from Lemma and Lemma D.4 Equation is necessary and sufficient condition to make TE, optimal in
MUr.
At this point, we proceed conditioning on the fact that Equation (4) holds. We need to show that, E R.g, then Equation (5) holds, and if Equation (5) holds, then Rg..
From Lemma D.4 we know that a necessary and sufficient condition for the previous statements to hold is that:
2e (s, S MMr (s) +
holds for any state-action pair (s,a) a) and for all experts E (2,..., n + 13. Given Equation 4 and Lemma D.2. the previous equation can be conveniently written as:
B F1 + EV & EV + Elgf.
(14)
At this point, consider a) such that n (a|s) > 0. Then, Equation 14 reduces to:
V(s) - Mun (s) + & Conversely, consider (s, a) such that TE, (a|s) then Equation reduces to:
(15)
-((s, a) + V(s) < (M) +
(16)
Since ((s, a) 2 0 by assumption, Equation I6 is directly implied by Equation 15 Therefore, it suffices study:
V(s) S ()) t.:
which can be rewritten as:
V V-1sf: < V. RE, (Is -YTE,, P) TE...
At this point, can plug Equation (4 within the previous Equation. More specifically, we obtain:
V 1s5, (Is yT, P) n (- B + (E->P)V)
(17)
We now proceed by rewriting the right hand side of Equation [7]. More precisely, we notice that:
(Is - P) TE, ((E PP) v) = (Ls TTTE, P) V 7 (Is - YTE, P) PV (Is TTTE P) -1 (Is -T PjV
V.
Plugging this result within Equation (17 we arrive at:
(Is P) TE. (B*Eic) < 1sE..
which concludes the proof.
D.1 Other Assumptions the Behavior of the Sub-optimal Experts
In this section, we investigate the generality of the results presented in Theorem 3.6 Specifically, we remark that all the results that derived in Section can be casily extended to other assumptions the sub-optimal experts. More specifically, the results of Theorem 3.6 can easily be extended to the following cases:
V V-E 2 1sE.,
(18)
16

---

Or
MU. - -ur 1sh.-
(19)
Equation 18) encodes the fact that that a given sub-optimal expert is at least & sub-optimal w.r.t the optimal policy TE while Equation (19) encodes the the fact that the sub-optimal expert is exactly & sub-optimal w.r.t. the optimal agent. In these cases, it is possible to derive the following generalizations of Theorem 3.6
Theorem D.S. Let B be an IRL problem with sub-optimal experts where V "uu - -Vuur 2 Lss:
holds for all sub-optimal experts i. Let r E [0, (]1A) Then, t E Ro if and only if there exists <E SxA A and V E IR$ such that the following conditions are satisfied:
20
r= == -
(20)
and, for all i E (2...., n+ 1}:
d T TE BTH ( 1s6,
(21)
Theorem D.6. Let B be an IRL problem with sub-optimal experts where V V VM 1s
holds for all sub-optimal experts i. Let [],1),xA, Then, E Roy and only if there exists <E E SxA and V IRS such that the following conditions are satisfied:
= (+
(22)
and, for all i E 12...., 1}:
E T BTET = 15
(23)
The proofs of Theorem D.5 and D.6 are identical to the one of Theorem 3.6 In terms of results, the only difference lies the fact that the set of linear constraints introduces a different type of relationship between { and Ex 10
At this point, remark that Theorem D.5 follows very similar interpretation of the one presented in Section In other words, the sub-optimal experts introduces lower bounds on the values of the advantage function that are played by the sub-optimal experts TE, and that are not played by the optimal expert [1] This result is as expected. Indeed, if we know that given policy is sub-optimal least by given quantity &., then, intuitively, we can extrapolate knowledge, expressed as lower bounds, on how sub-optimal certain actions are.
Concerning Theorem D.6 instead, we notice that the result is much more stronger w.r.t. to the case in which inequalities are involved in the problem (i.e., Theorem 3.6 and Theorem D.5). More specifically, notice that in this case, starting from Equation 23 it is possible to obtain the following result on the values of Ç:
TE BTBI Ç (Is YT P)L
(24)
Developing this constraint for specific state we obtain the following linear constraint:
Σ
TE, (al())s (1 7)-
(25)
In other words, it provides set of hard constraints that the values of ( should satisfy. At this point, we remark on two important observations. The first one that Equation (25) might not be satisfied for any choice of Ç E SxA In particular, suppose that there is only one sub-optimal expert. In this case, if TE Te. Equation 25) reduces to:
0 0= 0=E(11- (1-
10 As a consequence these results, we notice that direct extend properties the feasible reward V-TE, & &,, while for other experts it holds
set the case in which, e.g., for some experts it holds that MMUr- that VE === 2 &
As a consequence, highly sub-optimal experts with different behaviors leads to the most effective reduction of the feasible reward set R.g. This is opposed to the results of Section 3.3 where close-to to-optimal experts with different behaviors lead to the most effective reduction.
17

---

which is clearly false for any strietly positive value of ε,. We notice that this result is as expected. If the two policies are identical, then there should be no gap the performance of Fæ, and T As consequence, the feasible reward set of this IRI. problem is empty! |2 that all the experts are deterministic, and suppose that they all behave differently to TE in each state-action pair (so that the feasible reward set is non-empty). Then, focus on the i-th expert and consider a state-action pair (s, a) such that TE, (als) = 1. Then, Equation (25) reduces to:
Secondly, instead, suppose
((8,a) = E:(1 - 7)
In this sense, the presence of the sub-optimal expert implies a unique value that ((s. can take 13 follows that, for each state-action pair (s, a) such that næ (als) O, there exists a single sub-optimal expert i such that Ty (als) = we are able to recover entirely unique vector { that is compatible with the underlying IRI. problem. In other words, in this scenario, we are able to exactly recover the values of the ad advantage function that express the sub-optimality gaps of actions that are not played by the optimal agent.
D.2 Measuring Volumes of the Feasible Values of
Finally, we conclude this section by reporting additional analysis that quantitatively measure the reduction in the feasible values of Ç that are compatible with the presence of the sub-optimal experts.
To begin, we first introduce some notation. Let X' be measurable subset of IR"" we denote with Vol(.() the Lebesgue measure of X' 77. In other words, Vol(.)) represents the n-dimensional volume of X.
At this point, from Theorem 3.6 we know that the presence of sub-optimal experts can effectively limit the values that { can assume. Consequently, in order to measure the reduction of the feasible reward set, we will compute upper bounds on the volume of the region of Ç that induces at least one feasible reward function in Rg. In the remainder of this section, for generic IRL problem B, we will denote with (B)) such set. More specifically, we define:
Z(B) = <E E SSSA :3r E Ro : 3V e R 20
r - + (E - PVV and ((s,a) = 0 (V) mE, (a|s) = =
Notice that, we are directly restricting the analysis to state-action pairs for which TTE (als) = O holds. Indeed, fix (s, a) such that TE, (a i) holds. Then, changing the value of ((s, does not affect class of compatible reward functions.
At this point, the following proposition provides upper bounds the volume of the feasible values of ( for IRL and IRL-SE problems.
Proposition D.7. Let and be an IRL and an IRL-SE problem. Let g(s, a) be defined as follows:
a( = min k(s,
}
if (s, a): Tg, (als) = and X((s, ((s.a)>> >0
otherwise
where (((s,a) a) is defined as Equation 7 such that TE, (als) O. Then, it holds that:
and X(s a) denotes the subset of sub-optimal experts
Vol(Z <
II
1
(26)
(8,0), (s,0)=0 I-
Vol(Z(23) <
g(s,
(27)
(8.0) (s,0)=0
Nootcc that, to obtain empty feasible region, it is sufficient that the two experts behave identically in single state-action pair. This is direct consequence of the fact that the sub-optimality constraint is imposed with equality for each state-action pair. 13 Notice, in this sense, that, if any other deterministic sub-optimal expert is present, if it holds that TE, nE, (als) = 1. then should have E, to avoid obtaining an empty reward set.
18

---

Proof. The proof of Equation as consequence:
26 follows directly by noticing that ||cll S (1-7)-1 Therefore,
7)=
(2))
II
1dx
II
1
(3,0):TE)) (ale))= (als)=0
(8.0):FE) (s.0)=0
Equation 27 instead, follows from worst-case upper bounds on ((s, a) that arise from Equation (
Specifically, discussed in Section 3.3 it is possible to show that:
((s,a) S g(s
As consequence, we have that:
((E,))
Vol (((B)) <
II
1dr
II
g(8,
(s,a)=s;; (als)=0
(8.0)=,, (s,a)=0
which concludes the proof.
At this point, we recall that k(s, a) is given by:
k(s,a)=
min iEX(s,a), d (als)
Therefore, Proposition D.7 highhlghhs that, for sufficiently small values of & we obtain a notable reduction in the upper bounds of Vol Vol(Z(23)).
E Proofs and Derivations of Section
In this section, we provide formal proofs for the statements of Section 4 the proof of the lower bound (Theorem 4.1 and then we continue with the analysis US-IRL-SE (Theorem
We first proceed with
E.1 Proof of Theorem 4.1
In this section, prove Theorem 4.1 We recall that Theorem 4.1 composed of two parts. The first one is related to learning reward functions that are compatible with the behavior of the optimal expert (i.e., Equation ()). while the second one directly arises from the structure of the sub-optimal experts (i.e., Equation (Ib)..
We begin by proving Equation 99) As have anticipated in Section Equation (9) directly connected with the problem of learning reward functions that are compatible with the behavior the optimal expert TE, In this sense, recall that, recently, [22) have provided lower bounds for the single-agent IRL problem finite-horizon MDPs. In our work, we provide an extension of these results for the infinite-horizon IRL formulation.
Theorem E.1. Let & be (e, 8) correctt algorithm for the IRL problem with sub-optimal experts. There exists a problem instance B such that the expected sample complexity is lower bounded by:
F [r] 2
SA
log
8 + +5
(28)
2(1
Proof. Similarly to (22], this results follows from two different lower bounds (i.e.. Theorem E.2 and Theorem E.3). and by assuming to observe instances like the ones of Theorem E.2 with probability and instances like the ones of Theorem E.3 with probability 1 z-
As discussed, Theorem E. follows from two intermediate results that leverage two different con- structions (i.e., Theorem and Theorem We now delve into the proofs of these intermediate theorems.
19

---

Spoot
w.p.
w.p.
w.p.
81
8j
53
w.p.
w.p. 1
2
tc
w.p.
w.p.
w-p.
w.p.
w.p.
W.P. F
8+
Figure 3: Representation of the IRL-SE problem for the instances used in Theorem F.2
Theorem E.2. Let A be a (c, (..))-coreee algorithm for the IRL problem with sub-optimal experts. There exists a problem instance B such that the expected sample complexity is lower bounded by:
SA
Eg, [T]
Ω
log
(29)
2
7)
Proof. The proof is split into several steps. Since most of the arguments are borrowed from the proof of Theorem B.2 in [22]. we only provide a short sketch that involves the main differences between the finite-horizon and the infinite horizon IRL model.
Step 1: Base Instance and Alternative Instances We consider MDPUR instances that are pre-
sented in Figure 3 More specifically, the state space is given by S = {Smoat 81,... 88, 8_, 8+ 8_,84 the J. the transition model is described below,
action space is composed of actions A {ai, and 7 E (0, 1).
In state Stoot all actions have the same effect, and they lead, with probability 1/2 to state in (s1...., Similarly, in state s and 4 all actions have deterministic effect, and they all lead to 8- and 84 respectively. All the experts are deterministic and take action a1 with probability in all states. We then consider base instance, where, in each state sy {si,..., 85). all actions lead, with probability 1/ to and $4-
We then consider set of 5 x A alternative instances by varying the behavior of the transition model in state-action pairs (s,, ax) E ffs....... .sg) A. Specifically, by taking ag, the agent will end up. with probability 1 + e' in 84, and, with probability 1 in 8..
Step 2: Feasible Reward Set and Hausdorff' Distance lower bound At this point, we study the structure of the feasible reward set that compatible with the instances we described. Specifically, we are interested in the behavior of the reward function related to actions taken in states sj E {s1,... sg).
Specifically, for the base instance, we have:
7 1
[ r(s_.a a1) ) + (())
r(8;, 01) + 1 2 r(s an) + 2 (()) 2 2(88, ax) +
1- 2
20

---

which can be rewritten as:
((.j01) 2 r(s), 0x).
For the alternative instance in which we varied the behavior of the state-action pair (sj, az), instead, we obtain:
1-7 2 r(ss_,0)) 2 r((4 2
7 [
01)
ac) + 7 -
1-7 ( -e) r(s__, ai) + ( (e) r(s a(s
thus leading
r(sj, (1) 2 ((j: ax) - 7 a1) - - r(s,, 1-7
Given this construction, we lower bound the Hausdorff distance hetween the feasible reward set of the base and the alternative instance. Specifically, we first pick a reward function r' compatible with the alternative instance as follows: r' as) (s+'(s
O, r'sj, ag) and r' (s. a))) 1 1- -. Then, we study which reward function compatible with the base instance minimizes the infinite norm w.r.t. r'. Given these choices, similarly to [22]. it is possible to obtain the following lower-bout bound to the Hausdorff distance:
H (R, R') 2 6'7
where denotes the feasible reward set of the base instance, while R' denotes the feasible reward set of the alternative instance. We enforce the following constraint on the previous equation:
26,
which, in turns, leads to the following requirement on e':
2c - 7)
Step 3: Lower bounding the sample complexity At this point, the rest of the proof follows identical Theorem B.2 [22), and leads to the desired result.
We now continue with the proof of second intermidiate result that is needed for the proof of Theorem
Theorem E.3. Let 2 be a (e, -)-orrect algorithm for the IRL problem with sub-optimal experts. There exists problem instance B such that the expected sample complexity is lower bounded by:
S²A
Eg [T] 2
(30)
2 7)
Proof. The proof split into several steps. Since most of the arguments are borrowed from the proof of Theorem B.3 in (22). we only provide a short sketch that involves the main differences between the finite-horizon and the infinite horizon IRL. model.
Step 1: Base Instance and Alternative Instances We consider MDPRR instances that are pre-
sented in Figure More specifically, the state space is given by S = { S ...... $3, the action space composed of k actions A {a1, .2..... .... }. the transition model is described below, and 7 E (0, 1). In the following. we will assume S to be divisible by 16.
$3.5$' .......... s,.,,, s'
In state Swat all actions have the same effect, and they lead, with probability 1/8 to state in (g)) In state 8 E { s''} all actions have deterministie effect, and they all lead to the same state in which the action taken. All the experts are deterministic and take action aj
21

---

w.p.
By W.D. (1
4y w.p.
(
w.p.
w.p.
Figure 4: Representation of the IRL-SE problem for the instances used in Theorem BXS
with probability 1 in all states. Finally, in all states E (91,...88) action dn leads w.p. to any state in 6'3 E (s1....,.'))
We then consider class of instances by varying the behavior of the transition model in state-action pairs (8), ax) E {s1....8s) 88} x A \ {-1}- Specifically, for each triplet ($5, 8/ ak), p(s(1sj, ax)
1ee' (2ji0)) where olssn)) = ( (3))), U...Ug (2))))) E V, and V { 11, Σ. Uy = 0 and
2 E [o, 4]
Step 2: Feasible Reward Set and Hausdorff Distance lower bound We now proceed with lower bounding the Hausdorff distance between the feasible reward set that is induced by two instances that belongs to V, namely RB, and R. To this end, first of all, we notice that our class of reward functions admits elements that are bounded [0. 1]. Let us denote with R.g, the class of compatible rewards functions that are bounded in [-1, 1]. Then, we have that:
Hop (Ro. Ro..)
2 Ho (R R
(31)
The proof of Equation (31 follows by the following reasonings. First all, we can see that, for any F E R.g, holds if and only if 1+1 E R.g, holds 14 Then, with simple algebraic manipulations, we have that:
1
sup inf =ER yERs.
||x - yl1oo = sup inf
z yER
2
sup
inf
|| ylloor
ER
yeR.
from which it follows Equation 31
At this point, our analysis follows by lower bounding the Hausdorff distance using reward functions that are bounded in [-1,1]. 1]. To this end, first of all, analyze the feasible reward set for single instance B.. In this case, since a1 is played by the optimal expert, we have that:
a1) 51
7
Σ r ((() r(sj, ax)
7 Σ (1 ( 31-2
NNotiee that we are considering single-experts IRL problems. Indeed, in the considered IRL-SE problem, all sub-optimal experts behave identically to the optimal agent, and the constraints of Equation 5 are vacuous.
22

---

Sroot
w-p.
regardless the action w-p. 3
w.p.
TE, (a1 =
RE (02)8) miin
EE, (01 18 =1 Tinn
a1
a1
02
02
8sink
Figure 5: Representation of the IRL-SE problem for the instances used in Theorem E,4
which, in turns, leads to:
(1)),a) 2 r(s), ax) + ?
Σ uer"
At this point, following the same steps of (22), we obtain:
Ho (R Ro... 2 d' 7
Hoc (R Ro...
2
641 y
on which we enforce the following constraint:
é' 7 2 2c,
64
1-9
that is e' 2 128c 1=
Step 3: Lower-bounding the sample complexity At this point, the rest of the proof follows identical to Theorem B.3 in (22), and leads to the desired result.
We continue by proving the novel statement related to Equation 1T], which captures the role of the estimating reward functions that are compatible with the behavior of the sub-optimal experts.
Theorem E.4. Let A be a (e, -)-orrecc algorithm for the IRL problem with sub-optimal experts. For sufficiently small values of e, there exists instance B in which < 1 such that the expected sample complexity is lower bounded by:
o6 log (1)
Eg [7] 2 Ω
(32)
2 Tmii
23

---

Proof. The proof follows as the combination of several steps. We first describe the construction considering the case in which there is a single sub-optimal expert. Then, the results will follow by iterating the procedure for each sub-optimal expert in the given set.
Step I: Base Instance and Alternative Instance We consider MDPAR instances that presented in Figure 5 More specifically, the state space is given by S = {Sroat, Si,..., 85, Ssink J. the action space is composed of two actions E 1).
[0), the transition model is described below, and
In state Sooot all actions have the same effect, and they lead, with probability }/2 to state in (gg.. In each state 8; E $g], again, all actions have the same effect, and they lead, deterministically to state sinnk state Siink all actions are deterministic and they all lead to Ssink
We then consider a base instance, where, in states Stoot and state Ssink all experts take action dn with probability 1. each state 8, {si..... $3), instead, Tg, (a1]s;) 1, while TE, (a1ls;) 1 Tmin and nT (02)8)) Tmin for the sub-optimal expert.
We then consider a set of 3 alternative instances by varying the behavior of the sub-optimal expert in state 8, {s1, -- 83). Specifically, the sub-optimal expert will act accordingly to the following policy: TE, (8y) = a.Tmin, and TE, (a2]8}) = O'Tmmn for some a > (to be defined later). We
will denote our set of instances as MI = T (1) IE [ [ and denotes the behavior of the base instance described above.
Step 2: Feasible Reward Set At this point, we study the structure the feasible reward set that is compatible with the each instance we described. Specifically, we are interested in the properties of feasible reward functions in states 3j E {8)).
For the base instance, in each state 8, E {s...... 8s). we have that, since is the action taken by the optimal expert:
7 (ssink a1) 2 r(3j,
a1) 1 1-y
r (Ssinkk a1),
1-9
which reduces to:
a1) 2 r(sj,
(33)
-T (0)
Moreover, due to the presence of the sub-optimal expert, we have that V which results in:
(o) S (isr + E..
r(8j, .1) + 1 r (Ssink, a1) S
(r(8))a1)+ + 1-7
7 r ((siink an)) --222(0m
+ Tmin (r(s).00) 02) +
7
- (Bsinnk a1) + E,;
(1 mmin)
1-
which can be rewritten as:
r(sj, 01) -r(ss, S
(34)
Tmin
Similarly, for each alternative instance in M, we obtain:
r(33, 01) ) 2 r(s): 02)
(35)
r(a1,8) 8y) r(sj a2) <
(36)
a.
Step Lower-bounding the Hausdorff Distance this point, we proceed by lower bounding the Hausdorff distance between the feasible reward set of the base instance, namely Rgy,, and that of alternative instance j in which the policy of the sub-optimal expert is modified in state 8j, namely Royo)
To this end, we notice that it sufficient to pick any r E Roz and then study the following optimization problem:
inf
||r - looo
(37)
r' PER m (i)
24

---

We pick the following choice for For action d1 in state sj we pick r(s,, = ___ Instead, for all the other state-action pair, pick r(+,-) LS In this case, one can verify that the optimization problem in (37) can be rewritten as follows:
Kiin
Si Aiin
inf 2.y
max
,
s.t.
2. E [0,
(38)
& O'77min
x y S
y,
where x corresponds to r'(s a1), and to r'jj 02). further cower-bounded by:
The optimization problem in
38 can be
inf
Wiin
2;, y E [0, 1]
S
(39)
O177min
x 2 y
29
Wiin
We study the optimization problem in (39) by cases (i.e., EmTii -1 < œ, and EyTmin -1 2 x.). First, suppose that E However, in this case, would have y EiTT that is
y + Emi Chaining this inequality with S y & (armii) yields:
& @iT
Minn
which is impossible since a > Concerning the case which EmTiin -1 x, instead, we have that y S mnTi æ. It follows that, since S E + y. the maximum value of æ will be attained for the maximum value of Therefore, we obtain:
&1 @rTmin
E1
+
miin
Thus leading to:
Ex
+1)
2 TTin
Plugging this result into the objective function, we obtain the solution to optimization problem (39) which in turn provides a lower bound the Hausdorff distance. More specifically, we have that:
1 & 1 (1--) a
Hos (Rgg, Ryoh)
(40)
2 Tmin
We enforce the following constraint on this quantity, that is:
&
1 = 2c.
(41)
2 Tiin
We notice that in this sense, we need impose a = & (E, 4c7min) than 1 for all values of &: 4erminn Furthermore, since @'7min < condition on values which guarantes that the construction valid:
which results being greater
16
obtain the following
E
1-
1
min
4m
4
15 Notice that this step we have used assumption that go 16This condition directly arises from the fact that acTmin represents the probability with which the sub aub-optimal expert takes certain action.
25

---

Step 4: Lower-bounding Probability At this point, consider an (c, ---orrec algorithm 2 that outputs the correct feasible set gg for each IRL-SE problem B. For 21 it holds that:
2 sup Pa.
Rg: R
26)
(42)
max P H
RB R
2c),
(43)
8eM
where Fs. denotes the joint probability distribution of all events realized by the execution of algorithm Q in the IRL-SE problem B, that is:
n++1
P B = I1 M (st, a Dr D ac)
II
TE (a
(6) (st)
At this point, following the same reasonings of, e.g., Theorem B.2 in 22 one can see that, for all the alternative instances M, the previous equation can be further lower-bounded obtain:
8 z
exp [KL (Po,,)) P.o.i p))
(44)
Step KL-divergence As a final step, we will proceed by analyzing Equation (46). We will start by analyzing the KL divergence between Po a and Pocco), a Specifically, have that:
KL (P a Pgm 2)) = Egg00 22
KL E.
(-1st), 7
(-)ss)) (11s2)
1=1
TV
E, (- (1))) , क E. (-18g)
$ Eg:00 a2 [Nr (s,)]
Tiin
Eg au [N+ (s,)] min
Wiin
Fimin
where (V P2) represents the total variation distance between distribution pi and p2. The first inequality step follows from the reverse Pinkser's inequality [33. and the second one, instead, from the definition of the total variation distance.
At this point, however, from Equation
we obtain that:
4a
@TTin
Tmin
thus leading to:
mm m e
KL (P 1 I Pamnaa a < Egi, a [N>(s;)]
(45)
E
Plugging this result into Equation 46). and rearranging the terms, we obtain:
log 46
E log (1)
Eg [N+(s;)]
(46)
16 3
16e T
Finally, to conclude, we notice that:
Ego a [7] 2
Σ
Eg a (s)]
(47)
.E(31...,gg)
(S 2)
log
(48)
16 n
46
Iterating this procedure over all the possible experts yields the desired result.
26

---

Finally, we are now ready to prove Theorem Theorem 4.1. Let a (e, ---orrett algorithm for the IRL problem with sub-optimal experts. There exists problem instance B such that the expected sample complexity is lower bounded by:
SA
8 [r] 2
log
8 +
c
7)2
where (1-) hides constant dependencies. Let miin 0 be:
Tiin
min 1E,2,...11... ) (s.a)eSxAnnt (a e)>0
min
TE (a|s);
(10)
and let qu == - min maxie +1) &c. Then, there exists an instance B in which qu < such that:
% log (1)
Eg 18 20
(11)
Tii
Proof.
The proof follows directly by combining Theorem and Theorem E.4
E.2 Proof of Theorem 4.2
In this section, we provide formal proof for Theorem 4.2
First of all, we begin by defining a good event & that holds with probability at least 1 - 8. To this end, we begin by reporting, for the sake of completeness, the concentration tools that are used in controlling the probability with which & holds.
Lemma E.5 (Multiplicative Chernoff bound [TO). Consider independent random variables X1,..., X, taking values in [0, 1]. Suppose that [[X.] = holds for all i E [1,....,}} (]. Con- sider (0, 1). Then, we have that:
Σ x, tp(1 +a) ta(1+a)
(-Itua²)
P
S exp
Lemma E.6 (Proposition in 14). Let p be a categorical distribution over the simplex dimension and let P be the maximum likelihood estimate of p obtained with 2 1 independent samples. Then, for all 8 E (0, 1) holds that:
log (1) (u- (1(
P 1KL (KL
5
where KL(qi, Q2) denotes the Kullback-Leible divergence between distributions QI and q2.
At this point, we proceed by defining our good event. In the following, the subscript t is used to denote the iteration number of the US-IRL-SE algorithm.
Lemma E.7 (Good event). Consider t such that:
3 3log (35AA)
<1
(49)
TE, Ne((s
holds for all i (2...., 1) and for all (s,a) E S x A such that TF TT, (als) > O. Let us define the following events:
(3SAn)
(c(1+ Ne(8, a)
5-1 ))}
Ep = (ilo,))KI((((((1s)))))) (a.e)eSxA
log
+ +SS 1)
n iE(2....n+t)) sES n Mics) s log
(3SAA
+(A (A-1) log e (e(1+ Ni(s)
E, =
8
3log A5
Ext
(x,.(ell)) S (als)
14
TE. (a)x))
VE (=())...++)) (sa))Sxdte (ale)
Consider & = Ep nE, En n Exma. Then, it holds that IPEE) > - 8.
27

---

Proof. The proof follows by controlling the probability of the complementary event E More specifically, have that:
(E P (Ep U UE S SP (E)) + P(E)) + (E (amm))
where in the last passage we have used Boole's inequality. At this point, we will use Lemma E.5 and
Lemma B.6 to control IP (Ep) + (EG) +P (E#mm.) More specifically, concerning Ep. we have that:
355n
P (ES)
Σ
P
(i (pi(ss, p(- log
(s,0)ESXA
(e (c(1+
N1(s,a)
+ (5
1)
5-1
Σ
3SAn
3'
(s.a)ESxA
where, in the first step we have applied Boole's inequality, and in the second one Lemma E.6 identical reasoning, we can upper bound I (Ef), thus obtaining:
From
P(E)) S
Finally, concerning _
have that:
3 log (3SAA)
IP (E
Σ
Σ
P
* TE. (als)
1+
nF (2
#22 (a,a):T,, (a 8>>U
8
Σ
Σ
35
3
iE(2...,n+2) (5,a)amg, s)20
where, in the first step we have used Boole's ' inequality, and in the second one Lemma E.. together with Equation 449) At this point, combining these results, we obtain P (E*) S thus concluding the proof.
At this point, it has to remarked that Lemma E.7 holds whenever:
3 log (38Am)
Ne(s)
Tmin
We remark that this term is due to the requirement that Lemma E.5 requires in (0, As shall see, however, this will be sufficient to carry out the theoretical analysis of US-IRL-SE.
We now proceed by presenting error propagation results that study the Hausdorff distance between Rg and Rgg. Before diving into the details, we introduce the following notation. We denote with v the set of Ç's that are compatible with the linear constraints of Equation (5). More specifically:
TRSAA Vi f 1} d. B 11
(50)
Similarly, we denote with v the set of Ç's that are compatible with the linear constraints of Equation (5) that are induced by the empirical IRL problem B. More precisely:
R Vi f2...., n 1} _R f B 1st]
(51)
where å' denotes the discounted expected occupancy policy æ under the transition model p.
At this point, we provide a preliminary Lemma that will be used to study the Hausdorff distance.
Lemma E.S (Error Propagation). Let B be an IRL-SE problem and let B be its empirical estimate.
Then, for any r E R& such that r = -B Ç + (E VP,,V and (I TT P) TH B E there exists E R. such that element-wise it holds that:
< T B ++ <P P)V| B. B ||C projj (C) 11lo 1SxA
(52)
where projæ (-) denotes the infinite norm projection on the set क. More formally, for ( RSSA, proje (C) = argmin || Cl
zEV
28

---

Proof. From Theorem 3.6 we know that we can express the reward functions as:
- BB ( + (E -PV,,
f -BAR. ?+ (
where V and V belongs to R and <. E I satisfies the following equations for all n2. n 1}:
(I - TT. P) B c S.5 E..
(I - P) R B Ç Es.
At this point, we recall that, for any r E Rv, we are interested in a specific reward function i E Rgg that is sufficiently close to For this reason, we pick V - V, and Ç 8 prois (C) 17 these choices within | - fl. and applying the triangular inequality, we obtain:
Plugging
Fl
(B Ç + B 2 + (P P.V.
(53)
Let us focus now on (BTRr BBc 2)1-
(B Ç + Ban B proj (<))
(BTTr ( + Brn; Bads proj (5)) + B&n BuTl
BTEl ( + B BTEI ( + B Ç - B B C
<
Bas Bd& c + B&s, B proje (s)) - B& BuBi c/.
where in the last step we have used 1= + D 1sxA
18
We now focus on the last term:
Bes B proja(())) B&*, BERsC C = Bdn, R |s proja (c)
< B* nm ||< -
Plugging these results within Equation (53) concludes the proof.
Before providing some interpretation to Lemma E.8 we recall the definition of the Hausdorff distannce we are interested in:
H (Rg Riy max
sup inf FER
|r- flloo,
sup inf FR rERs
|r
fl1
(54)
PER
Given this definition, we can appreciate how Lemma E.8 can be used upper-bound the error of the first component of the Hausdorff distance, namely:
sup inf ||r 11r-f flloc.
rER FER
Nevertheless, is possible to obtain symmetric version of Lemma E.8 that analyzes the existence of an r E Rg that is sufficiently close to any f Rg. At this point, notice that Lemma E.g decomposes the error the recovered reward set the sum of three different components. The first one is related to the error in the estimation of the optimal policy TE, and, to zero it out, is sufficient estimate for each state action that is played by the optimal expert. The second one, instead, is related to the errors in the estimation of the transition model, and, finally, the last one is notice that the first
related to the presence of multiple and sub-optimal experts. More precisely, two components are present also for the single-agent setting [24], and, in this sense, they arise from the difficulty of estimating reward functions that are compatible with Equation 44) The last term, instead, is related to the presence of sub-optimal experts, and it denotes the infinite norm between
any Ç E V and its infinite-norm projection to the set T. As one can imagine. and as our proofs will reveal, studying how this last source of error decreases with the iterations of US-IRL-SE introduces significant challenges in the analysis w.r.t. the single agent setting. Precisely, this complexity will be tackled within the proof of the following Lemma, which analyzes how the error of Equation (52) decreases with the number of iterations of US-IRL.
17 Notice that, if x E T. AT x belongs to T as well.
Consider SxA, then BT is the operator defined as (BT (s) (m(aas) > (()
29

---

Lemma E.9 Probabbbbb Error Propagation). Let t be the iteration of US-IRL. Suppose that (s) for all (s,a) E x A and, furthermore. suppose that is such that:
3og (35 Ano-1)
2
(55)
ATmin
8
3SAn
log
(56)
(1 - 7)2
8
+ (S log
6471
log
33An
+ +S - s1(vve 1
1
(57)
(1 - 7)
5-1
t 87
35
log
(58)
A(1 -7)²
647
F3AAn 8
+ (A- - 1) log
log
(A-
Ve+
(59)
(1-7)1
A-1
Then let B be an IRL-SE problem and let B be its empirical estimate after t iteration of US-IRL. Then, with probability at least for any r E Rgg. there exists R such that:
2v2r 31 +
2v
11- - 1
Pt +
(ar + Be) min min max & (1 (1-7)-11 1
(60)
1 1-7
where:
log 38An
+ (S log (c(1+ z
3g
(61)
log 38An
+ (A - 1) log
e @e 14
#-1
7-1
0g
(62)
LA
log
(3.AAn
Pt
(63)
miin tA
Proof. The proof follows by analyzing in greater detail the result of Lemma E.8 Indeed, from we know that there exists & E Rø such that:
Lemma E.8
- fl < [ BaE al + >|[(p P)V + ||< - projæ (C) Ilao
(64)
We split the analysis of Equation (64) into three parts. First of all, we will focus the two first terms, that are =m B Clooo and 7|[(P P) and then we will tackle the most challenging aspect, that is - p (<) Iloo.
Concerning | B& [ll so. we notice that, whenever Ne(s, a) > holds, we have that:
RTH B R < O,
for any possible value of Ç. This is direct consequence of the fact that TE, is deterministic.
Secondly, let focus (P P)V] First of all, notice that, since N.(s) 3 log (3SAnd-1) aiin holds for all S. then E holds with probability at least 1 - 8 (Lemmal E.7
30

---

At this point, conditioning on &, we have that:
>I((P
PJV
max
(p(5")s, -((( ((5((ss)))
8,0
e'ES
7
(p(''sss)) ( (()1ss))))
max
1
8,
#'ES
7
max ||p(-|s, - p(-1s,
1
2
max (L) p(1s,,))
7)
2
log
38An 0
+ (S log (e 1
Ni(a.)) S-1
max
8,0
a)
where the first inequality follows the fact that |V S - the third one by Pinksker's inequality, and the last one from Lemmal E.7 At this point, since US-IRL gathers samples uniformly from each A. Thus leading to:
state-action pair, have that (1 s, a) for all (s, a)
2v 2/
log
(3.A2) b
+ (S log (e (1
2V21
- 1-7 7I((P- - PIVIl
Be.
t
Finally, we focus on -S--jroja (c) Iloe. To upper-bound this last term we proceed in several steps.
Step 1: Relationship between & and v First of all, we begin by finding a more explicit relation- ship between V and T. To this end, we recall that Ç E RXA belongs to T if the following condition is satisfied for all i E (2...., 1}:
E. tE BBB S 1sf.
Under the assumption that N2(s, a) 2 1, since the expert policy ne, is deterministic, the previous Equation can be equivalently rewritten as:
j t B Ç S 1sf.
At this point, we proceed with some algebraic manipulations of the left-hand side of the previous Equation. Specifically:
d R, RE Ban: 5=
gRm. + d
Rg. BTR
(jFt - d
# BTE ( + d= मे. BTE C
(dtt, d
RE B= ( + d= (म + TE. BT C
ftE. E.
Rg. B Ç d= (#g. TE,) BT ++ E. BRE
At this point, focus d= R
fez - d (Is - -tt 1 Is- - (Is YTTE, P)
(Is FT -1 (Ts 7TT P) - (Is -tt P)] gec.
=E ( P TE, P
j+
At this point, plugging this result into the previous Equation, we obtain that ( belongs to T if and only if the following holds for all experts E (2....,
E. BEEL + =. [ P TE, P)] d BTES + E. (#g. TE,) B < 1s
(65)
31

---

As we can appreciate, Equation by renaming (1(S) == "
65
relates the sets v and vi by an explicit relationship. Indeed,
E
P TE. P d" tg. B and e2(C) = d= (# TT,) n Ç,
Equation (65) can be rewritten as:
EE B + & 1sf.,
which closely resambles the definition of V.
Step 2: Restricting the set We continue our proof by defining a new set vp such that v C V with probability at least 6. Indeed, by definition of the projection according to the infinite norm, this allows to upper- upper-bound bound || - proje (C) lo.. More specifically, for any C V we have that:
I|< - projæ (c) llc S lIC - projo (C) ll...
(66)
More specifically, in order to define V, we will first proceed by upper bounding eC(C) and e2(().
Precisely, consider Ç E V. For e1(5) we have that:
(C) = =d #g. P - TE. P j t BTBi
=7 d (ft. - -TE,) p
j B +7 ME (P- - P)]
dm fE. Bags
Y d mg. TE, P
jht. ag BT 5 +
d TE, p- P d+te tt BUES
where, given f R and ISA, - π denotes the operator defined as i - g(s,a) = (als) g(s, a), and, similarly PP -P- p(s)) E. |(s'|s, a) p(s'|s, f(s'). At E. [(als) -(cl))))a((ass)))
this point, we notice that, since, for all ( E V it holds that d= & E, Brs, S 1st.. Therefore, we can further upper bound the previous equation to obtain:
(c) s >0||<0m
d RE. - TE. 1sxAši | 1s +
*
P pl
1sti 1s. (67)
At this point, let us focus on 7/| [ jR.. -TE, TE, 1sxaei|1
TE.
ISxAL1
S 266 max
E (als) - (a.(a
7h, max
Ei (8) [fTE (-18) - <1s5(l
2 2/27/
KL (:,8'), (E,
1-7 s
log (3SA2) + (A log (e (1 (1+
Nc(a)
2 27 max
3-1
--
Ne(s)
2 2/22/
log 38AA
+ (A log
(e (11++1)
x-1
1 1-7
tA
2 2/2
1-7
where in the third step we have used Pinkser's inequality, the fourth we have used Lemma E.7 and
in the fifth one we have used the fact that, in US US-IRL-SE, No(s) = Eaea (s) +A. At this
32

---

point, focus on the second term of Equation (67. namely > [d p- rl]
1s xc 1s:
d T..
p P
1st,
$ 7 max
R. (s) Σ TE. (dl))l)((()) p(-1s,))]l
20
2v 2/
max 8a
(L(E(-18,,))) - p(-1,,a))
1-7
log (8AA + + - 1) log (e (e(1+ Ne(s)
2v 2/22
8-1
max
1
Ni(s)
log ( + (S - log (e (1+ (1+
2//2
1-7
2/225i Br,
1 1-y
where in the second step we have used Pinkser's inequality, the third one Lemma F.7 and in the fourth one we have used the fact that, in US-IRL-SE, (s) for all states S. Therefore, plugging these results within Equation (67 we obtain an high-probability upper bound on (C). that is:
2V27E (or + 8.).
[1) I 1-7
(68)
We now proceed with similar reasoning to obtain an upper bound on e2( Nevertheless, contrary to 61 (C), here we proceed with an element-wise upper bound on (c))). Specifically, for each state
s' E S:
(s))
Σ
(s)
Σ
(als) - nE. (a.(a)))
O (a/s)=0
Σ
tE, (als) - (a)(( C(s,a) ((s,s)
0: By (a)s)=0,
xg (als)>0
ã (als) TE, (als)
Σ
TE, (()))
TE, (a|s)
A: (0) xE, (a|a)>0
TE. T (a"ls")
TE (a"
Σ
Σ
EE (a(a)))((ss
max
(6" o6 "mme (a" "=")
TE, (a"
a: (a/s)=0
3 log 3SAn
Σ 5f
Σ
TE, (als)(((s))
Tmin (s)s)
amm,, [a|s]=
3 log 3SAn
RR
TE, (s)s)
Tmin LA
a:WE [a]e]=0
where the third step follows from the fact that, since Nr(s) > #E (als) 0 for all (s, a) such that Tg, (a) s) = 0, the fifth one, instead, from Lemma E.7 and the last one from the fact that, in US-I SE, (s(s) = En Ns(s,a) a) tA T9 Therefore, we have obtained an element-wis upper-bound on cc(C) of the following form:
log (35Az) 8
e2( <
T TF, BT Ç "i TF BT C.
(69)
Tiin I.A
Nottce that Equation
55 guarantees that apply Lemma E.7
33

---

We are finally ready to define the set L. More specifically:
2/275. CE SXA (1 (1+p:)d TE, B S 1 (at ..0).
=
(70)
As one can verify, the definition of y follows from upper-bounding e (C) and e2( with Equations As a direct consequence, whenever Ç E W, we have that belongs to as well.
668 and
69
Step 3: Ensuring that the feasible region of v is non-empty At this point, might be tempted to directly study the projection of ||I - projæ (c) bl.. Nevertheless, we notice that, for sufficiently large values of ar and Be, V might be empty.
Sufficient conditions to guarantee that V not empty are the following ones:
2 2v
Ee 2
S
(71)
1 7
2 2/ 5: 2
Be S
(72)
1 1-7
Using Lemma 12 in [14]. it is possible to verify that Equations (56 and 558 are sufficient conditions
for Equations 7T 72 hold.
Step 4: Picking Ç V to upper-hound || projæ (C) loo this point, we ready to conclude
our proof. As we have previously verified, the set v non-empty. We can now study || proję (C) bo.. More precisely, we have that:
Ik - projæ (c) S |K - projæ (C) oo..
To further upper bound this Equation, we notice that we can always pick, by definition of the infinite norm projection, any Č E V. In other words, we have that:
Ic - proj (C) |>x s lk proje (C) bo S |15 člloo.
More specifically, we choose ? the following way. If for all i E (2...., then we pick Č(s, a) = ((s, a) otherwise, we pick ((s, a) in the following way:
.e.....,. n 13. TE, (als) =
1 2/22 (at + Be)
Č(s,a) a)
I-7
((s.a).
(73)
Pt
First of all, we verify that this choice of Č belongs to V. Plugging Equation 73 into the definition of T obtain that:
(1 (1-1-2
2727 (ar + +B))
1 Pt Th TE, BTTi ( &: 1-
2/27 (ar, + Bc)
1
However, since Ç w, have that TE B < t., thus leading to:
2//21/ & 1-7 (or + 3r)
S 2/271
1- (ar + Bt)
which is always true, and, consequently Ç E V
20 Notice that, if for all E (,...., 1}. ns. (als) = 0, C(s, a) does not contribute to any of the linear
constraints that introduced by Equation 5
34

---

To conclude the proof, it remains to analyze ||ş - Elloo. At this point, we notice that:
[(s,a) - 2/27 I-3
(a+ + BB) ((s,a)/.
||s E1loo
max (s.a) (m|=) =0, Siwn, (a|s)>0
+ Pt
Indeed, for a acatenaction pair (s, a) such that Tæ, (a|s) | 0, we can notice that any value <(s, a) will not affect the resulting reward function 21 Furthermore, whenever there is sub-optimal expert such that n (als) > 0, then {(s, ((s, a) holds by definition. To conclude, with simple algebraic manipulations we can obtain the following result:
2/22 1-2222 (as + Bi) 5(s,
15 - 5110o S
max (s,a)er (u, Bi:ee, (a|s)>0
(1 pt)((s))
1-7
2v2y
max (s,a): =0, 7i:EE, E, (a/s)>0
(ptt 1 1-7
(ar + Bi) ((s,a)
2v2y Pt --
(ae + Be))
max
((s.a)
(s.a): (0) Bi:E, (als)>0
2 1 (as + Be)
min miin max &e (1 - -1)=1
$ Pt +
where in the last step we have upper- houeded [(s, a) with an upper bound that follows directly from Equation 77). thus concluding the proof.
We can appreciate Lemma E.9 provides, under certain conditions on the time-step t, high- probability upper bound on the difference infreR ||| ||r- for any choice of E Rgg. Furthermore, as we can see, the proof is fairly involved due to the necessity of upper bounding the error term kk (K-projj (C) ol At this point, by deriving symmetric results (i.e., Lemma E.8 and Lemma E.9), it is possible to derive an identical upper-bound for infreR ||r - fl for any choice of f E R As a consequence, Lemma E.9 provides the following high-probability upper-bound on the Hausdorff' distance between R2 and Rg:
2V27
202r Br Pt + 1-7 (ar B.) min Tiinn max Ei, (1 - 7)) (74)
Hoo RRØ RB S
Theorem 4.2. Let q1 = min { (mi maxie (2.... (1 (1-1)) and 92 = max q1). Then,
with total budget of:
of Sog (1)
SESA(S log (3)) 1)
δ max
(13)
2 TTin
(2117))
US-IRL-SE is (c, 8)-coreect and Ö (.) hides constant and logarithmic dependencies.
Proof. Let us start from Lemma E.9 and consider such that the condition of Lemma E.9 are satisfied. As previously discussed, due to Lemma E.9 we have that, at time t, the algorithm US-IRL-SE induces an estimated feasible reward set such that the following holds with high probbbbbbbbiltt:
2/27
2/27 (ar + Bt) min T max & (1 - (-)--- 7)-1}
Hoo RoB R
<
3 + Pc +
1
1-
In other words, if (s, a) is such that nT; (als) = 0, we can add the following constraint to any of the set we detined: ((s, a) 0. The resulting feasible reward set is left unchanged.
35

---

To conclude the proof, we need to find sufficiently large t such that the following holds:
27 Br +
202y Pt + 7-7 (ar Bc) min
Hoo
RB, R
{ "min max E,, (1 -
(1-7) 7)- Se
for any e E (0,1). To this end, sufficient to find the smallest that satisfies the following conditions:
Pr min {
mmin -1
max &i, (1 -)-- = 4
(75)
2/27
Be S 4
(76)
(1-?)
2/2y
min min max & (1 - -) Br S
6
(77)
(1-?)
4
2/2y
min "min max &a (1 7) 71 aq 1
e
(78)
(1-7)
4
At this point, let focus on P: min {-m max; &, (1 - -1)--11 z. By simple algebraic manipula- tions we obtain the following sufficient condition for d:
48qî log 33
t.A
Tiin 2
For 2v2x (1 (I->)
Bt S 4.
instead, we obtain the following condition on 22
128y²
An
t 2 (1 22
log
16384y
(3SAn
(ve+
+ (S - 1)
log
+S -1) (S--1)
(1 (1-21 22
8
Similarly, for 2v (1->)
min Tmin max; Eoe (1-7) 7) Be S 5. we need least the following number
of samples:
12
A35An 5
1 1 (1 222
log
16
ASAn
1 + (S-1)
(iVeVVVss V S-1
+ (S - log
log
(1 76
Finally, for 2v27 (1-7)
min ( max; &i, (1 - -11 a S 4. obtain:
12
log AS
LA > (1 - 22
163844f7*
(3SAn) + (A-1)
(v++
1
(A log
log 8
(1 (1-7)
At this point, we notice that the total number of samples gathered from the generative at step is given by iSA. Therefore, from the previous equations, together with the conditions of Lemma E.9 we obtian the following sufficient condition guarantee that US-IRL-SE is (c, -ooorect
of log (1)
GESA log (2)) S Slog (1)
tSA - O max
(79)
e2
(1 222
minnn
This follows by applying Lemma 12 in 14
36

---

where the first term is due to Equation (7). the second one comes from Equations 767-(77) and the last term arises from Equation (55) and is independent w.r.t. the desired accuracy ef Specifically, we notice that for sufficiently small values of (i.e., < q1), the last term is always dominated by the first one, which concludes the proof.
F Stochastic Optimal Expert
In this section, discuss how to extend our analysis the case in which the optimal expert plays stochastic policy. First of all, let us define E, as the minimum probability with which the optimal expert plays its actions 24
At this point, we notice that, for obtaining sample-complexity guarantees of the US-IRL-SE algorithm, Lemma E.8 implies that we are interested learning which are the actions that are played with positive probability by the optimal expert. In other words, for any non-7ero vector J E S we want the following to hold with prosaprbbbbblity:
(BeE, B*a) 0.
(80)
To this end, one can apply Lemma D.3 of 22 which implies that with number of samples that is:
log (#)
s
(81)
log (1/(1 Tmin,
Equation (80) holds w.p. at least 1 - 5. Once this condition is verified, the rest of the proof of complexity of US-IRL-SE follows identically to the one of Theorem 4.2 We notice that this introduces an additional maximum in the result of the sample-complextty However, it is also possible to extend the proof of the lower bound [22] (see Theorem D. in (22]). to show that the dependency resulting from (8I) is unavoidable. In this sense, US-IRL-SE remains minimax optimal whenever the performance of the sub-optimal experts are sufficiently close to the ones the optimal agent.
G Per-expert Complexity of IRL-SE
In this section, we provide description of how to change the PAC learning formalism to show that Equation [T]) actually represents a lower bound to the number data that is necessary to gather from each of the different sub-optimal experts.
Specifically, we define learning algorithm for an IRL problem 2 as a tuple X (r, v), where is stopping time that controls the end of the data acquisition phase, and v/ = (Vt) is a history-
dependent sampling strategy over S x A x (s)*+1, More precisely, 2/4
A Sxxx(S))=* where
D. ((S A)*+ s) At each time step / E N. the algorithm selects, by means of v4:
(i) a state-action pair Ar) and observes a sample St ~ p(-1S,, from the environment
(ii state s(10 for each expert E (l,..., 1} and observes sample A TE. (-Is(")
The observed realizations are then used to update the sampling strategy Vi, and the process goes on until the stopping rule is satisfied. At the end of the data acquisition phase, the algorithm leverages the collected data to output the estimate of the feasible reward set Rg that is induced by the resulting
empirical IRL problem B,. Given this formalism, we are interested designing learning algorithms that, for any desired accuracy e E (0, 1) and any risk parameter 5 E (0, 1), guarantee that:
Pa,s (Ro R
(82)
23 All the other equations introduce negligible terms in the O(-) notation. Notice that, in principle, Rmin. E, A Mmin that defined for the sub-optimal experts. 25 Notice, indeed, that we can apply Lemma E.9 as-is, but introducing the further constraints that t should be sufficiently large that Equation (80) holds.
37

---

Expression of m From the proof Theorem 4.2 is possible to derive an exact expression m that can be used in US-IRL-SE. More specifically, since = (, 26 it is sufficient to take as upperizunnddo on C3..5
Uppercound on
15,00 Inder
Figure 6: Experiment Results. Visualization of the maximum value that can assume (using perfect knowledge of the underlying MDP) (left). Visualization of the empirical maximum value that Ç can assume (the results report the mean over 20 runs) (right).
We refer to these algorithms as (e, correett identification strategies. For (c, -coorrect strategies, define their sample complexity the of the number of unitary samples gathered from the generative model. In other words, let us denote with [s, a) the number of samples gathered, at step from the environment, and let N(0) (s) denotes the number of samples gathered step & from the i-th expert at state Then, the sample complexity is given by:
a) + ΣΣ NO (s).
(5.a)
Given this learning formalism, is straightforward to extend the results of Theorem 4.1 to this setting. More specifically, Theorem E.1 can used to lower bound Σ, Nz. (s) for each sub-optimal expert, thus showing significant increase in the sample complexity (i.e., linear in the number of sub-optimal experts).
H Further details on US-IRL-SE
In this section, provide further details US-IRL-SE. More precisely, specify the exact expression of the parameter m that is used to provide (c, (coorec
the minimum t that satisfies Equations 75 78 and Equations (55) 58
Computational Complexity of US-IRL-SE At each iteration, US-IRL-SE will query the genera- tive model in all state-action pair (s, S A. Notice that the generative model samples (i) the environment (ii) all the expert's policy. Assuming a unitary cost for generating each sample, a single query to the generative model results in computational complexity of O (n). Therefore, the total computational complexity of US-IRL-SE given (SAm.).
I Numerical Validation
We designed an experiment that aims visualizing the reduction of the feasible reward set.
This is direct consequence of the uniform sampling strategy.
38

---

Computing Resources The experiments have been run on laptop with 8 Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz and 8GB of RAM. Total time gather the results less then a few hours.
Experiment Setup We considered as environment the forest management scenarios with 10 states and 2 actions that is available in the "pymdptoolbox" library We considered a discount factor y = 0.9. We have run policy iteration on this domain to recover set of expert policies (i.e., the policy returned at each iteration by the policy iteration algorithm is a sub-optimal expert), and we have considered as & the infinite norm between the value functions of the optimal policy and the sub-optimal ones computed using the true reward function.
Results To appreciate the reduction in the feasible set that is introduced by the sub-optimal experts, we have plotted the maximum value that ((s, a) can achieve according to the theoretical bound of Eq. 7 (notice that this way easier to visualize rather than an entire set of reward functions). have flattened the matrix that contained upper bounds For the sake of visualization, (left.. As one can notice, the presence the sub-optimal experts we plotted the result in o significantly limit the value of the advantage function in many state-action pairs (notice that the maximum value for C is given by (1 - 7) s 10; this theoretical threshold represents the upper-bound that was derived in [24] for the single-agent problem).
and
We have then run our algorithm for 20 times using c = 0.1 and ō 0.1, and computed the (empirical) theoretical upper bound on Ç. The reviewer can find the empirical value of the upper bounds on in the Figure (right). We have reported only the empirical mean, as the 95% confidence intervals are in the order of le-5, As one can verify, the results are almost identical to the exact case.
Code can be found at httttp:://gtthuu com////wwwordielllyyyyyapooooooo License is BSD 3-Clause
"New" or "Revised" License. Master branch at commit commit 1 200100000000000000000000066666 was used.
39

---

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:
The abstract and the introduction reflect the original contribution of the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
Limitations are noted as future directions the conclusion section.
Guidelines:
The answer NA means that the paper has no 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-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
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 low images are taken in low lighting. Or speech-to-text system might 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 address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a 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 to 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 complete (and correct) proof?
Answer: [Yes]
40

---

All the statements are correlated with proofs. The definitions and the quantity used are clearly presented.
Justification:
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 the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide 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
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Appendix | provides detail on how to reproduce the experiments. We will also make the code public for reproducibility.
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 be 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 a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or 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 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) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or 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 be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
41

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
The codebase to reproduce the results will be public.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is 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 the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
//nips.c./ httpsscccpbbbcccccceeceeeec.c guides/ /ac////oddbiissseeeeeeee htt.:///e/..eee/eteSSuuiiiiisss
sii.isiiicyyyyyyycc for more details.
The authors should provide instructions on data access and preparation, including how to 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
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification: Experiment details are reported in Appendix Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to a 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, 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: Figure 6 reports only the mean as the 95% confidence intervals are in the interval of Ie-5.
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, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for
example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
42

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one 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 figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
If 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
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
Experiment results and details are provided in Appendix
Guidelines:
The answer NA means that the paper does not 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 estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't It make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http://wwwrr...cccpppbb/eeeeeeee
Answer:
[Yes]
Justification:
We checked the guidelines and we are compliant with them.
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 cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- cration due to laws or regulations 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: a theoretical research paper, the authors do not see any negative societal impact.
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 why the paper does not address societal impact.
43

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment 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 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 is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are 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 a system learns from feedback over time, improving the efficiency and accessibility of ML).
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 (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses such risks.
Guidelines:
The answer NA means that the paper poses no 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 usage guidelines 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.
12. Licenses for existing assets
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?
Question:
Answer: [Yes]
Justification:
We rely the pymdptoolbox library, and we make explicit reference it in Appendix[I
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 or dataset.
The authors should state which version of the asset is used and, if 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.
44

---

If assets are released, the license, copyright information, and terms of use in the thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssi
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl 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 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. Crowdsoureing 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 details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information 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.
According to the NeurIPS 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/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending 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.
45

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we 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.
46


Reviews:
[{"review_id": "X6P44wS6yX", "reviewer": "Reviewer_Euvz", "summary": "The paper develops a theory to address inverse reinforcement learning (IRL) from sub-optimal expert demonstrations. The authors assume a set of experts with known degrees of sub-optimality. Rather than learning a single reward model, as is often done in standard IRL, they provide an explicit characterization of all plausible reward models compatible with the experts. Moreover, they give lower bounds on the number of generated samples from the experts for a PAC guarantee on the set of reward models. Finally, they propose a uniform sampling procedure that can result in near-optimal estimation of the reward models in terms of sample complexity.", "questions": "N/A", "limitations": "N/A", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Although this is not the first work for IRL from sub-optimal experts, I haven't seen characterizing all plausible reward models for such a setting, so I would call the work original in this sense.\n2. The authors provide good intuition on why having more sub-optimal experts can shrink the set of feasible reward models in Figures 1 and 2.\n3. I haven't fully validated the proofs for the theory. But it seems both Theorem 4.1 (the lower bound on the required sample size for the $(\\epsilon,\\delta)$-correct identification of the reward set) and Theorem 4.2 (the upper bound for the uniform sampling algorithm) are mainly based on the theoretical results in Metelli et al., 2023. Moreover, the characterization of plausible reward models in Theorem 3.3 is mainly developed by Metelli et al., 2021 (especially the eq. (5), which characterizes the feasible rewards for the case of optimal experts). In that sense, the novelty of this work is introducing more constraints based on the sub-optimality index of additional demonstrators, which is characterized in eq. (3) and point (iii) in line 162 of page 3. Having said that, those extensions based on the extra constraints seem non-trivial. So, I'd call the theoretical contribution novel.", "weaknesses": "The main weakness of the setting is that it assumes having access to a generative model for the optimal and sub-optimal experts during sampling and that there is a performance gap between the sub-optimal and optimal experts. However, given that the main contribution of the paper is theoretical, I still vote for acceptance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> ### The main weakness of the setting is that it assumes having access to a generative model for the optimal and sub-optimal experts during sampling and that there is a performance gap between the sub-optimal and optimal experts\n\nWe thank the Reviewer for raising this point. Extending this work to remove the assumption on the generative model and working directly on a dataset of demonstrations is an intriguing avenue for future research. In this sense, one could draw inspiration from the recent paper \"Offline Inverse RL: New Solution Concepts and Provably Efficient Algorithms\", Lazzati et al., 2024, where the authors analyze solution concepts and algorithms for recovering the feasible reward set in the single-agent IRL setting. Concerning the assumption of the performance gap, we take the chance to note that our formulation still generalizes existing theoretical works on IRL, which usually assume to have access to possibly multiple **optimal** experts (see, e.g., \"Identifiability and generalizability from multiple experts in inverse reinforcement learning.\", Rolland et al., NeurIPS 2022, or additional works that we discuss in Section 5).", "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": "qi8IZRe18p", "reviewer": "Reviewer_zNGu", "summary": "This paper studies unregularized IRL involving one optimal expert and $n$ suboptimal experts. The authors show that the additional suboptimal experts can help mitigate the reward ambiguity in IRL that arises due to the unknown suboptimality of unvisited state-action pairs. They present an analytical expression for the feasible reward set in this setting and demonstrate that the reward ambiguity can be reduced when learning from not-too-suboptimal experts yet playing differently from the optimal expert. Furthermore, assuming a generative model and sample-based access to experts' policies, the authors provide a PAC lower bound for the sample complexity of IRL and propose an algorithm that is minimax optimal for small suboptimalities of the experts.", "questions": "1. As pointed out, we would generally like the suboptimalities $\\xi_i$ to be small and the $\\pi_{\\min}$ to be large. However, these may be conflicting goals, given that we also want the suboptimal experts to deviate from $\\pi_{E_1}$. Could this problem be mitigated by having experts that are more suboptimal (e.g. a completely uniform expert) but with lower and upper bounds on their suboptimality?\n2. What if we were to drop the optimal expert $\\pi_{E_1}$? Can we say anything about the feasible reward set in that setting?", "limitations": "Some limitations are discussed in the conclusion section. However, it would be good to be more clear about the practical limitations of the provided results.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The paper makes a notable contribution to IRL by showing that leveraging suboptimal experts can effectively reduce reward ambiguity.\n2. Theorems 4.1 and 4.2, presenting lower and upper bounds, are particularly appreciated.\n3. The mathematical notation is clearly introduced, and full proofs are available in the appendix.", "weaknesses": "1. The paper assumes access to a generative model of the experts' policies. However, in practical IRL a finite data set of precollected expert demonstrations is the norm. This makes Algorithm 1 difficult to implement in practice. \n2. Minor points: a) In my opinion the claims made in line 109 and in Examples 3.1-3.3 need a reference or a brief proof. b) I believe there is a typo in Eq. (5): Since we are taking the expectation with respect to the state-action occupancy measure, we don't need the right-hand side should be a scalar, right? Moreover, in Eq. (10), I assume it should be $\\min$ instead of $\\max$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> ### The paper assumes access to a generative model of the experts' policies. However, in practical IRL a finite data set of precollected expert demonstrations is the norm\n\nWe thank the reviewer for raising this point. We agree with the reviewer that the generative model represents a limitation. Extending this work to remove the assumption on the generative model and working directly on a dataset of demonstrations is an intriguing avenue for future research. In this sense, one could draw inspiration from the recent paper \"Offline Inverse RL: New Solution Concepts and Provably Efficient Algorithms\", Lazzati et al., 2024, where the authors analyze solution concepts and algorithms for recovering the feasible reward set in the single-agent IRL setting. \n\n> ### Minor points\n\nWe thank the Reviewer for these notes. \n\nWe have inserted proofs for Example 3.1-3.3 in a revised version of the manuscript and also in this Rebuttal (see reply to Reviewer KsdM). \n\nOn Equation (5). Having fixed a sub-optimal expert $i$, Equation (5) represents a set of $S$ inequalities. This is visible in Equation (6) that makes explicit *one* of such inequalities having fixed $s'$ (the initial state of the occupancy measure). By varying $s'\\in \\mathcal{S}$, we obstain $S$ inequalities, and for this reason, the right hand side of Equation (5) is an $S$-dimensional vector.\n\nOn Equation (10). Yes, thanks for the typo. Equation (10) should be changed to a $\\min_{i \\in \\{2, \\dots n \\}} \\min_{(s,a): \\pi_{E_i} > 0} \\pi_{E_i}(s,a)$.\n\n> ### As pointed out, we would generally like the suboptimalities to be small and the $\\xi$ to be large. However, these may be conflicting goals, given that we also want the suboptimal experts to deviate from $\\pi_{E_1}$. Could this problem be mitigated by having experts that are more suboptimal (e.g. a completely uniform expert) but with lower and upper bounds on their suboptimality?\n\nWe thank the Reviewer for the interesting question. We agree that these may be conflicting goals, at least when no additional structure is enforced (consider, for example, a kernelized and continuous state-action space which has been discretized; here, taking similar but distinct actions leads to similar effects on the underlying MDP; in this case, the goals are not necessarly conflicting).\n\nNevertheless, as the Reviewer suggests, we agree that one way to mitigate this problem would be having experts with lower and upper bounds on their sub-optimality. In this case, the lower and upper bounds will delimit the set of reward functions with potentially more information, thus avoiding the \"need\" for \"precise\" experts with small sub-optimality gaps. \n\n>  ### What if we were to drop the optimal expert ? Can we say anything about the feasible reward set in that setting?\n\nWe thank the Reviewer for raising the interesting question. If we drop the optimal expert, we are still be able to make use of this knowledge to reduce the feasible reward set. Consider a set of experts for which we know that $0 \\le V^{E_1} - V^{E_i} \\le \\xi_i$ holds. Then, for each pair $(i,j) \\in \\{2, \\dots, n+1 \\}$, simple algebraic manipulations leads to the following inequalities: $V^{E_j} - V^{E_i} \\le \\xi_i$, which does not depend on the optimal policy $\\pi_{E_1}$. As a remark, we note that, by considering only these inequalities (i.e., by neglecting the presence of $\\pi_{E_1}$), one can still obtain sufficient conditions for describing the feasible reward set.\n\nAs an illustrative example, consider a simple bandit with two sub-optimal experts $i$ and $j$. Then, suppose that $\\pi_{E_i}(a_i) = 1$ and $\\pi_{E_j}(a_j) = 1$ for some actions $a_i, a_j$ such that $a_i \\ne a_j$. Then, the previous set of equations leads to $r(a_j) - r(a_i) \\le \\xi_i$ and $r(a_i) - r(a_j) \\le \\xi_j$, thus introducing constraints on the values that the reward functions can assume in these actions.", "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": "Xd9Tbc91b2", "reviewer": "Reviewer_6BJu", "summary": "This paper aims to mitigate the intrinsic reward ambiguity in IRL problems.  The authors propose that incorporating sub-optimal expert demonstrations can lead to a more accurate estimate of the feasible reward set. Initially, they formulate the IRL with Sub-Optimal Experts (IRL-SE) problem and explore the theoretical properties of the resulting feasible reward set, offering both implicit and explicit descriptions. Additionally, they establish the lower bound of the statistical complexity for IRL-SE problems within the Probably Approximately Correct (PAC) framework. Finally, the authors introduce a uniform sampling algorithm that achieves minimax optimality for IRL-SE.", "questions": "Based on the weaknesses, my questions are as follows.\n\n- How can we utilize the feasible reward set in a real-world scenario? I understand that IRL enables learning of reward models from expert demonstrations, which can then optimize policies through RL. However, if we obtain a reward set instead, how should we make use of it?\n- Can you provide more insights into determining the performance gap of sub-optimal policies?\n- Can you experimentally verify if sub-optimal experts can mitigate reward ambiguity? For example, in certain MDPs, as more sub-optimal experts are provided, the cardinality of the feasible reward set tends to decrease.", "limitations": "This paper does not discuss the limitations of the work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- This paper is well-written and easy to follow. The examples provided in the paper effectively illustrate the role of sub-optimal experts.\n- This paper provides a clear and comprehensive theoretical analysis of the IRL-SE problem. The approach of identifying, modeling, evaluating, and solving the problem is highly commendable and worth emulating. First, the authors formalize the problem and demonstrate the theoretical feasibility of resolving reward ambiguity. Then, they determine the difficulty of the problem by analyzing the lower bound of statistical complexity within the PAC framework. Finally, the authors propose an algorithm that achieves minimax optimality to solve the IRL-SE problem.", "weaknesses": "- The paper does not provide a method for determining a suitable performance gap $\\zeta$ for sub-optimal experts. Additionally, in examples such as 3.1 and 3.3, when $\\gamma=0.99$ (a commonly used value), the estimated performance gap $\\zeta$ tends to be quite large. This may limit the effectiveness of sub-optimal experts in resolving ambiguity in reward sets, which could be a significant obstacle for algorithm deployment.\n- The paper lacks experimental results to validate the role of sub-optimal experts in resolving reward ambiguity.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> ### How can we utilize the feasible reward set in a real-world scenario? \n\nWe thank the Reviewer for raising this point. How to make the best use of the feasible reward set to learn a policy in RL is currently an open problem, even for the single-agent IRL formulation of the feasible reward set (see Section 8 in Metelli et al., ICML 2023). \n\nNevertheless, suppose that the algorithm has terminated, and, consequently, the estimated policies $\\\\{ \\hat{\\pi}\\_{E\\_i} \\\\}\\_{i=1}^{n+1}$ and the empirical model $\\hat{P}$ are available to the agent.  At this point, given any $V$ and $\\zeta$ that satisfies Eq. (4) and (5) for $\\\\{ \\hat{\\pi}\\_{E\\_i} \\\\}\\_{i=1}^{n+1}$  and $\\hat{P}$, let us write $\\hat{r}\\_{v,\\zeta}$ for its corresponding reward function. \n\nNow, suppose we are given a function $f: \\mathcal{S} \\times \\mathcal{A} \\rightarrow \\mathbb{R}$ that evaluates the quality of a compatible reward function $\\hat{r}\\_{V, \\zeta}$, i.e., $f(\\hat{r}\\_{V, \\zeta})$, so that we are interested in learning a policy for the reward function that maximizes $f$. Then, we can search over the feasible reward set for the function that maximizes $f$. This problem is simply a constrained optimization problem, where the constraints are the ones on $V$ and $\\zeta$ specified by the empirical versions Eq. (5) and (6) (i.e., $P$ is replaced with $\\hat{P}$ and $\\pi_{E_i}$ is replaced with $\\hat{\\pi}_{E_i}$). Since all these constraints are linear in $V$ and $\\zeta$, the complexity of the optimization is entirely dominated by the complexity of evaluating the objective function $f$. If evaluating $f$ is computationally efficient, then, searching for a reward function that maximizes $f$ is computationally efficient.\n\nOnce the reward function that maximizes $f$ (or an approximation) is available, we can use it to train the RL agent. Notice that, in this sense, we can appreciate that this approach does not force us to select a criterion $f$ beforehand, and therefore, we might adopt the aforementioned strategy for several criteria (e.g., the max-margin approach of \"Algorithms for inverse reinforcement learning\", Ng and Russel, ICML 2000) and train several RL agents. \n\nFinally, it has to be remarked that learning a policy in RL is not the only purpose of IRL. Another typical application is the interpretability of the behavior of the expert. In this sense, the feasible reward set approach offers broader perspectives w.r.t. standard IRL methods that adopt specific criteria to select a single reward function. \n\n> ### Can you provide more insights into determining the performance gap of sub-optimal policies?\n\nDetermining the performance gap $\\xi_i$ for sub-optimal experts is a relevant issue. First of all, in the paper we have provided three scenarios (Examples 3.1-3.3) in which the values of $\\xi_i$ can be computed, with no assumption of no knowledge of the (possible) reward function optimized by the expert policy. We remark that $\\xi_i$ is to be intended as an upper bound of the degree of sub-optimality of expert $i$ and, for this reason, even a rought estimate (provided that it is an overestimate) is acceptable. Furthermore, the presence of a human domain expert is able to evaluate the sub-optimality of several agents, providing estimates of $\\xi_i$, is a more realistic scenario than requesting the human expert to explicitly design a reward function.\n\n>  ### Can you experimentally verify if sub-optimal experts can mitigate reward ambiguity?\n\nWe thank the Reviewer for raising this point. We have designed an experiment that aims at visualizing the reduction of the feasible reward set. We have considered as environment the forest management scenarios with $10$ states and $2$ actions that is available in the \"pymdptoolbox\" library. We considered a discount factor $\\gamma = 0.9$. We have run policy iteration on this domain to recover a set of expert policies, and we have considered as $\\xi_i$ the infinite norm between the value functions of the optimal policy and the sub-optimal ones computed using the true reward function. \n\nTo appreciate the reduction in the feasible set that is introduced by the sub-optimal experts, we have plotted the maximum value that $\\zeta(s,a)$ can achieve according to the theoretical bound of Eq. (7) (notice, indeed, that this is way easier to visualize rather than an entire set of reward functions). For the sake of visualization, we have flattened the matrix that contained upper bounds on $\\zeta$, and the reviewer can find the result in the right figure in the pdf that we attached to the general answer. As the Reviewer can notice, the presence of the sub-optimal experts can significantly limit the value of the advantage function in many state-action pairs (notice that the maximum value for $\\zeta$ is given by $1 / (1-\\gamma) \\approx 10$; this theoretical threshold represents the upper-bound on $\\zeta$ that was derived in Metelli et al., 2021 for the single-agent problem). \n\nWe have then run our algorithm for $20$ times using $\\epsilon = 0.1$ and $\\delta = 0.1$, and computed the again the theoretical upper bound on $\\zeta(s,a)$. The reviewer can find the empirical value of the upper bounds on $\\zeta$ in the left figure. We have reported only the empirical mean, as the $95\\%$ confidence intervals are in the order of $1^{-5}$. As one can verify, the results are almost identical to the exact case. \n\n\nWe integrated this result in the appendix in a revised version of our manuscript.", "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": "iLXerYv1CC", "reviewer": "Reviewer_KsdM", "summary": "The authors introduce the IRL-SE problem, which which uses multiple experts, including sub-optimal ones, to enhance reward function learning. Given a bounded performance gap between experts, the authors provide a theoretical analysis on shrinking the feasible set of compatible reward functions. Using a PAC framework, the authors provide a lower bound on the sample complexity for estimating the feasible reward set \n\nThe authors propose a uniform sampling algorithm with theoretical guarantees, demonstrating its minimax optimality under certain conditions.", "questions": "Examples 3.1,3.2,3.3. Maybe it's \"easy to show\", but can you please show where these come from? \n\nSuggestion: The word \"Indeed\" is used too many times. It is quite repetitive. \n\nSuggestion: For line 109, can you explain why the infinite norm is limited to the particular range? \nOperators: $\\pi$ is overloaded to be both an operator and a policy", "limitations": "Future research directions are provided, but a dicussion on technical limitations would be also be good to have. No discussion on potential negative societal impact.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The authors provide interesting novel insights in a more general sitaution compared to previously cited work\n\nThe submission is technically sound and well supported by extremely detailed theoretical analysis. The work is complete and the authors evaluate their strenghts and provide future research avenues. The techincal notation is dense and can be difficult to follow, but the authors did well in writing precisely. \n\nI think the overall proposal in this paper is quite applicable in many RL settings, so this is a strong submission with many potential use cases.", "weaknesses": "The submission could be written more clearly. Some results could be expanded instead of just staing the results. Particularly, the use of \"it's easy to see\" should be removed and expanded upon for ease to the reader. In some cases it may also aid readability to expand out expression instead of writing it in the most concise way possible. \n\nThe paper has a strong theoretical focus, which is strong and necessary. However, it would be powerful to see it actually employed in a case study to see how such a technique would be used. Even outside of empirical evidence, it would aid in readability of the paper to see how the notations used in the theoretical sections are actually used in practice. To that end, even a case study with a toy example would go a long way. The authors do a good job in providing technical examples through the paper, but these could be be futher enhanced by connecting them to a toy example of some kind. For a such a dense technical paper, it would make a world of difference in readability.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> ### It would be powerful to see it actually employed in a case study to see how such a technique would be used. Even outside of empirical evidence, it would aid in readability of the paper to see how the notations used in the theoretical sections are actually used in practice. To that end, even a case study with a toy example would go a long way.\n\nWe thank the Reviewer for raising this point. We have added an experiment to show how the presence of sub-optimal experts limit the feasible reward set in a tabular domain. We refer the reviewer to our reply to Reviewer 6BJu. \n\nFinally, we agree with the Reviewer that an intuitive example can benefit the reader. Given the page limit, however, we preferred to give more space to an appropriate formalism to model the problem. We will make use of the additional page to insert an intuitive example on a 2D goal-based grid-world that shows how the presence of the sub-optimal experts shrinks the feasible reward set. \n\n> ### Examples 3.1,3.2,3.3. Maybe it's \"easy to show\", but can you please show where these come from?\n\nWe thank the reviewer for pointing this out, and we are sorry about this. We agree that the presentation would benefit from formal justifications. Below, the Reviewer can find proofs about these examples. We integrated them in the appendix in a revised version of the paper.\n\n**Proof of Example 3.1**\nConsider two MDPs \\ R $\\mathcal{M}\\_1$ and $\\mathcal{M}\\_2$ that differs only in the transition function, namely $p_1$ and $p_2$. Suppose that $\\pi\\_{E\\_1}$ and $\\pi\\_{E\\_2}$ are optimal for $\\mathcal{M}\\_1$ and $\\mathcal{M}\\_2$ respectively. We are interested in upper-bounding $V\\_{\\mathcal{M}\\_1 \\cup r}^{\\pi\\_{E\\_1}}(s) - V\\_{\\mathcal{M}\\_1 \\cup r}^{\\pi\\_{E\\_2}}(s)$. Then, for any state $s$, we have that:\n\n$$\nV\\_{\\mathcal{M}\\_1 \\cup r}^{\\pi\\_{E\\_1}}(s) - V\\_{\\mathcal{M}\\_1 \\cup r}^{\\pi\\_{E\\_2}}(s) \\le V\\_{\\mathcal{M}\\_1 \\cup r}^{\\pi\\_{E\\_1}}(s) - V\\_{\\mathcal{M}\\_2 \\cup r}^{\\pi\\_{E\\_1}}(s) + V\\_{\\mathcal{M}\\_2 \\cup r}^{\\pi\\_{E\\_2}}(s) - V\\_{\\mathcal{M}\\_1 \\cup r}^{\\pi\\_{E\\_2}}(s)\n$$\n\n(we have added and subtracted $V^{\\pi\\_{E\\_1}}\\_{\\mathcal{M}\\_2 \\cup r}$, and then we have used $V^{\\pi\\_{E\\_1}}\\_{\\mathcal{M}\\_1 \\cup r} \\le V^{\\pi\\_{E\\_2}}\\_{\\mathcal{M}\\_2 \\cup r}$ due to the optimality of $\\pi\\_{E\\_2}$ in $\\mathcal{M}\\_2$). Then, focus on $V\\_{\\mathcal{M}\\_1 \\cup r}^{\\pi\\_{E\\_1}}(s) - V\\_{\\mathcal{M}\\_2 \\cup r}^{\\pi\\_{E\\_1}}(s)$ (an identical reasoning can be applied for the second difference). This can we written as $$ \\gamma \\sum\\_a \\pi\\_{E\\_1}(a|s) \\sum\\_{s'} p\\_1(s'|s,a) (V^{\\pi\\_{E\\_1}}_{\\mathcal{M}\\_1}(s') - V^{\\pi\\_{E\\_1}}\\_{\\mathcal{M}\\_2}(s')) + (p\\_1(s'|s,a) - p\\_2(s'|s,a))V^{\\pi\\_{E\\_1}}\\_{\\mathcal{M}_2}(s')$$\n\nwhich, in turn, can be further bounded by:\n\n$$\\frac{\\gamma}{1-\\gamma} ||p\\_1 - p\\_2 ||\\_1 + \\gamma \\sum\\_a \\pi\\_{E\\_1}(a|s) \\sum\\_{s'} p\\_1(s'|s,a) (V^{\\pi\\_{E\\_1}}\\_{\\mathcal{M}\\_1}(s') - V^{\\pi\\_{E\\_1}}\\_{\\mathcal{M}\\_2}(s'))$$\n\nUnrolling the summation to iterate the aforementioned argument, and using the fact that $\\sum\\_{t=0}^{+\\infty} \\gamma^t = \\frac{1}{1-\\gamma}$ concludes the proof.\n\n**Proof of Example 3.2**\nIn this proof, we explicit the relationship of the value function $V$ with the discount factor $\\gamma$ by writing $V^{\\pi, \\gamma}\\_{\\mathcal{M} \\cup r}$. Then, we have that \n\n$$V\\_{\\mathcal{M} \\cup r}^{\\pi\\_{E\\_1}, \\gamma}(s) - V\\_{\\mathcal{M} \\cup r}^{\\pi\\_{E\\_2}, \\gamma}(s) \\le V\\_{\\mathcal{M} \\cup r}^{\\pi\\_{E\\_1}, \\gamma}(s) - V\\_{\\mathcal{M} \\cup r}^{\\pi\\_{E\\_1}, \\gamma'}(s) + V\\_{\\mathcal{M} \\cup r}^{\\pi\\_{E\\_2}, \\gamma'}(s) - V\\_{\\mathcal{M} \\cup r}^{\\pi\\_{E\\_2}, \\gamma}(s)$$\n \n(we have added and subtracted $V\\_{\\mathcal{M} \\cup r}^{\\pi\\_{E\\_1}, \\gamma'}(s)$, and then we have used $V\\_{\\mathcal{M} \\cup r}^{\\pi\\_{E\\_1}, \\gamma'}(s) \\le V\\_{\\mathcal{M} \\cup r}^{\\pi\\_{E\\_2}, \\gamma'}(s)$ due to the optimality of $\\pi\\_{E\\_2}$ for the discount factor $\\gamma'$). \n\nAt this point, focus on $V\\_{\\mathcal{M} \\cup r}^{\\pi\\_{E\\_1}, \\gamma}(s) - V\\_{\\mathcal{M} \\cup r}^{\\pi\\_{E\\_1}, \\gamma'}(s)$. Using the definition of the value function, together with the fact that rewards are bounded in $[0,1]$, we can rewrite this difference as $\\mathbb{E}[\\sum\\_{t=0}^{+\\infty} (\\gamma^t - {\\gamma'}^{t}) r(s\\_t, a\\_t)] \\le \\sum\\_{t=0}^{+\\infty} \\gamma^t - {\\gamma'}^{t} = \\frac{\\gamma - \\gamma'}{(1-\\gamma)(1-\\gamma')}$. An identical argument holds for the second difference, thus concluding the proof.\n\n**Proof of Example 3.3**\n\nBy using the definition of value function, we can rewrite $V\\_{\\mathcal{M} \\cup r}^{\\pi\\_{E\\_1}}(s) - V\\_{\\mathcal{M} \\cup r}^{\\pi\\_{E\\_2}}(s)$ as \n$\\sum\\_{a} (\\pi\\_{E\\_1}(a|s) - \\pi\\_{E\\_2}(a|s) )r(s,a) + \\gamma \\sum\\_{s'} p(s'|s,a) (V\\_{\\mathcal{M} \\cup r}^{\\pi\\_{E\\_1}}(s') - V\\_{\\mathcal{M} \\cup r}^{\\pi\\_{E\\_2}}(s')))$. \nAt this point, since rewards are bounded in $[0,1]$ and by the policy similarity assumption, we have that the difference in value functions can be upper bounded by $\\epsilon + \\gamma \\sum\\_{s'} p(s'|s,a) (V\\_{\\mathcal{M} \\cup r}^{\\pi\\_{E\\_1}}(s') - V\\_{\\mathcal{M} \\cup r}^{\\pi\\_{E\\_2}}(s'))$. Unrolling the summation to iterate the aforementioned argument, and using the fact that $\\sum\\_{t=0}^{+\\infty} \\gamma^t = \\frac{1}{1-\\gamma}$ concludes the proof.\n  \n\n> ### Writing suggestions \n\nWe thank the Reviewer for the suggestions. In a revised version, we limit the use of word \"Indeed\" and we removed the use of \"it's easy to see\" and we replaced with formal justifications (see point above). \nOn the use of the symbol $\\pi$, we replaced the operator $\\pi$ with $\\bar{\\pi}$ to distinguish it from the policy symbol $\\pi$.", "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:
We thank the reviewers for the time they spent reviewing our paper. Specifically, we are happy that the reviewers considered our work "original" and with "novel technical contribution" (Reviewer Euvz), with "notable contribution to IRL" (Reviewer zNGu), and a "clear and comprehensive theoretical analysis of the IRL-SE problem" (Reviewer 6BJu), and that it models "more general situation compared to previously cited work" (Reviewer KsdM).

In the following, we answer the remaining questions. We are also attaching a PDF that contains figures on an experiment that was asked by reviewers 6BJu and KsdM.

Meta-review: The paper examines an instance of the inverse RL problem, where the goal is to reconstruct the feasible reward set from demonstrations provided by both an optimal expert and multiple sub-optimal experts. All reviewers were positive about this work, appreciating its theoretical contributions to the literature on IRL and the soundness of its main technical claims. Although the paper lacks experimental results to validate its main findings, its theoretical contributions appear strong enough on their own. Therefore, I recommend acceptance.
Decision: Accept (poster)