How does Inverse RL Scale to Large State Spaces? A Provably Efficient Approach
Authors: Filippo Lazzati
Mirco Mutti
Alberto Maria Metelli
Venue: NeurIPS 2024 poster (2024)
Keywords: Inverse Reinforcement Learning
Reward-Free Exploration
Linear MDPs
Primary area: reinforcement_learning
TL;DR: We introduce a novel Inverse Reinforcement Learning formulation that permits efficient learning in Linear Markov Decision Processes.

Abstract: In online Inverse Reinforcement Learning (IRL), the learner can collect samples about the dynamics of the environment to improve its
estimate of the reward function. Since IRL suffers from identifiability issues, many theoretical works on online IRL focus on estimating the entire set of rewards that explain the demonstrations, named the *feasible reward set*. However, none of the algorithms available in literature can scale to problems with large state spaces. In this paper, we focus on the online IRL problem in Linear Markov Decision
Processes (MDPs). We show that the structure offered by Linear MDPs is not sufficient for efficiently estimating the feasible set when the state space is large. As a consequence, we introduce the novel framework of *rewards compatibility*, which generalizes the notion of feasible set, and we develop CATY-IRL, a sample efficient algorithm whose complexity is independent of the size of the state space in Linear MDPs. When restricted to the tabular setting, we demonstrate that CATY-IRL is minimax optimal up to logarithmic factors. As a by-product, we show that Reward-Free Exploration (RFE) enjoys the same worst-case rate, improving over the state-of-the-art lower bound. Finally, we devise a unifying framework for IRL and RFE that may be of independent interest.

How does Inverse RL Scale to Large State Spaces?
A Provably Efficient Approach
Filippo Lazzati
Mirco Mutti Technion Haifa, Israel
Alberto Maria Metelli Politecnico di Milano Milan, Italy
Politecnico di Milano
Milan, Italy
filippo. saappo..lzzzzer www.lllzzziiioo poottiippmmiiii.
Abstract
In online Inverse Reinforcement Learning (IRL), the learner can collect samples about the dynamics of the environment to improve its estimate of the reward func- tion. Since IRL suffers from identifiability issues, many theoretical works on online IRL focus estimating the entire set of rewards that explain the demonstrations, named the feasible reward ser. However, none of the algorithms available in the literature scale to problems with large state spaces. In this paper, focus the online IRL problem in Linear Markov Decision Processes (MDPs). We show that the structure offered by Linear MDPs is sufficient for efficiently estimating the feasible set when the state space is large. As a consequence, we introduce the novel framework of rewards compatibility, which generalizes the notion of feasible set, and we develop CATY-IRL, a sample efficient algorithm whose complexity is independent of the cardinality of the state space in Linear MDPs. When restricted to the tabular setting, we demonstrate that CATY- IRL is minimax optimal up to logarithmic factors. As by-product, we show that Reward-Free Exploration (RFE) enjoys the same worst-case rate, improving over the saae--of-the-ad art lower bound. Finally, devise a unifying framework for IRL and RFE that may be of independent interest.
Introduction
Inverse Reinforcement Learning (IRL) is the problem inferring the reward function given demon- strations of an optimal behavior, i.e., from expert agent. [49 42 Since its formulation, much of the research effort has been put into the design of efficient algorithms for solving the IRL problem 6 Indeed, the solution of the IRL problem opens the door variety of interesting applications, including Apprenticeship Learning (AL) 2 [] reward design [16], interpretability of the expert's
behavior 17| and transferability to environments [15].
Nowadays, the factor that most negatively impacts the adoption of IRI. solutions in real-world applications is the intrinsic ill ill-posedness of its formulation. The IRL problem has been historically defined as the problem of recovering the reward function underlying the demonstrations [49 42).
even though mere demonstrations can be equivalently explained by variety of rewards. In other words, the IRL problem is underconstrainee. even in the limit of infinite demonstrations 42
To overcome this weakness and to come up with a single reward function, three main approaches are commonly adopted in the literature. (i) The first approach consists of the use of heuristic to select specific reward function from the set of all the rewards that explain the demonstrations. Implicitly, these works re-define IRL. as the problem recovering the reward function explaining the demonstrations and complying with the heuristic. As an example, [42, 48] select the reward that maximizes some notion of margin, and (70) implicitly chooses the reward returned by the optimization algorithm among those that maximize the likelihood. However, these approaches may generate issues in applications [56 (ii) In the second approach, additional constraints beyond
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

mere demonstrations are enforced to guarantee the uniqueness of the reward function to recover. In "reward identifiability" works, the additional information commonly concerns some structure of the environment (25], or multiple demonstrations across various environments [
10 In Reward Learning (Rel.) works [T9], demonstrations of optimal behavior are combined with other kinds of
expert feedback, like comparisons [65]. (iii) As third approach, recently, (9 38 proposed the
alternative formulation of IRL as the problem of recovering all the reward functions compatible with the demonstrations, i.e., the feasible reward set. In this manner, we are not subject to the limitations of the first approach, and we do not depend on additional information like in the second approach.
In practical applications. the chosen IRL formulation has to be tackled by algorithms that use a finite number of demonstrations and a limited knowledge of the dynamics of the environment. In the common online IRL scenario, the learner explores the (unknown) environment, and exploits this additional information to improve its performance on the IRI. task [e.g..
39 33
68 31. On
this basis, the IRI. approach (iii) based on the feasible ser 39 [3] displays desirable properties since "postpones" the choice of the heuristic and/or enforcement of additional constraints, with the advantage of analyzing the intrinsic complexity of the IRL problem only, without being obfuscated by other factors. In other words, this recent formulation of the IRL problem paves the way for the design and analysis of provably efficient IRL algorithms, endowed with solid theoretical guarantees.
However, the algorithms designed for learning the feasible set currently available in the literature [e.g..39 [3 (8 68 31] struggle when attempting to scale them to IRL problems with large state spaces. This is apparent because their sample complexity exhibits an explicit dependence on the cardinality of the state space. This inevitably represents a major limitation since most real-world scenarios concern problems with large, or even continuous, state spaces [e.g.[55 15 40
In this context, function approximation represents an essential tool to tackle the curse of dimensional- ity and enforce generalization [54] 4T) Linear Markov Decision Processes (MDPs) 223 67 offer a simple but powerful structure, in which we assume the reward function and the transition model can be expressed linear combinations of known features, that permits theoretical analysis of the
sample complexity. Even though many extensions have been developed [64] 22 [3] the Linear
MDPs framework typically represents one of the first function approximation settings to analyze when focusing on a novel problem, before moving to more complex settings [c.g.. 63 61].
In this paper, we aim shed light the challenges of scaling the feasible reward set large-scale problems. Motivated by its limitations when dealing with large state spaces, we introduce the novel Rewards Compatibility framework. Being generalization of the notion of feasible set, it allows to define the new IRL Classification Problem, a fourth approach to cope with the ill-posedness of the IRL formulation. This permits the development of CRLY-IRL (CompATibility for IRL), provably efficient IRL algorithm for Linear MDPs characterized by large or even continuous state spaces.
Original Contributions. The main contributions of the current work can be summarized follows:
We prove that the notion of feasible set can not be learned efficiently in MDPs with large/continuous state spaces, even under the structure enforced by Linear MDPs. Nevertheless, we show that this problem disappears under the assumption that the expert's policy is known, by providing a sample efficient algorithm for such setting (Section 3)
To overcome the need for knowing the expert's policy exactly, we propose Rewards Compatibility, a novel framework that formalizes the intuitive notion of compatibility of a reward function with expert demonstrations. It generalizes the feasible set and allows us to define an original learning setting, IRL classification, based on new formulation of IRL classification task (Section 4
For the newly-devised framework, we develop CATY-IRL (CompATibility for IRL), new sample and computationally efficient IRL algorithm for both tabular and Linear MDPs. Remarkably, this CATY-IRL does not require the additional assumption that the expert's 's policy is known (Section 5). the tabular setting, we prove tight minimax lower bound to the sample complexity of the IRL.
classification problem of 22 H²SA (S + log t)) episodes, where S and A are the cardinalities of the state and action spaces, H is the horizon, the accuracy and d the failure probability. This bound is matched by CATY-IRL, up to logarithmic factors. Exploiting similar construction, we show that lower bound with the same rate holds also for the Reward-Free Exploration (RFE) problem. improving by an H factor over the RFE -tate-of-thheart lower bound [2] (Section 6.1) Finally, we formulate a novel Objective-Free Exploration (OFF) setting that isolates the challenges of exploration beyond Reinforcement I learning (RI.), by unifying RFF and IRI. (Section 6.2
Additional related works and the proofs of all the results are reported in Appendix A and B
2

---

2 Preliminaries
Notation. Given an integer N e N. we define [M] := (1...., ......... N). Given sets X' and V we denote Ha(X := max(suPmex inf yey d(x sup inf zex d(y, x)} their Hausdorff distance with inner distance d. We denote by A & the probability simplex over X, and by AI the set of functions from y to A x²_ Sometimes, we denote the dot product between vectors 2; y as (a, y) = xTy. We employ O,Ω, θ for the common asympiotic notation and O, 0, θ to omit logarithmic terms.
Markov Decision Processes. A finite-horizon Markov Decision Process (MDP) without reward [45] is defined as a tuple M == (S, A. H. do- p), where S and A are the measurable state and action spaces, H N is the horizon, dg E A is the initial-state distribution, and p P A x.Axx ["]
is the transition model. Given (deterministic) reward function E R = 1- [M]] we denote by M == M (r) the MDP obtained by pairing .M and r. Each policy E II := S
induces in M a state-action probability distribution dp.a= := [dh ) Waalt (we omit do for simplicity) that assigns, to each subset Z s S x A, the probability of being in Z at stage h E [H] when playing π in M. We denote with 5% the set of states supported by d; for any action at stage h, and with SR.* the disjoint union of sets (S), [e[[H]- The Q-function of policy π in MDP M is defined at every (s, a, h) Sx x A x [H]] (7, a; and the optimal Q-function as (5, is computed over the stochastic process generated by playing policy æ in the MDP M. Similarly, we define the V-function of policy at hs) as V ( (s: == Ep 1
(r Ep. E dy)[s, = 8, 8, = aj. r) == suPREll Q7 (s. a; p. r), where the expectation Ep."
re(se, at) (s) s). and the optimal V-function as V/2 (s:p.r) == supren V/ (s; ps.p.)). r). We define the utility of π as and the optimal utility as J (r;p) = Ex-do [V (s) A forward (sampling) model of the environment permits to collect samples starting from s ~ dg and following some policy. A generative (sampling) model consists in an oracle that, given an arbitrary
J ("::p) [VT
state-action-stee triple h in input, returns a sampled next state s' ~ Ph (p(ssa))).
Linear MDPs. Based on (23], we say that an MDP M = (S, A. H. do. P. r) is a Linear MDP with a (known) feature map Φ S A Rd, if for every h E [H] there exist d E N unknown (signed) measures 14, [1 1-----0 T over S and an unknown vector 0g E Rdd such that for every (s, () E S x A, we have ph (-ss, a) = (Ø(s, a), (n)-)) and ri, a) = (Ø(s,, a), 0%). Without loss of generality, we assume ()(s,))2 < for all (s. E S x A, and max [6,, l2, lll (S)]2} & va[ M is a Linear MDP without reward if its transition model satisfies the assumption described above.
BPI and RFF. In both Best-Policy Identification (BPI) 37 and Reward- Free Exploration (RFE) (1]. the learner has to explore the unknown MDP optimize certain reward function. In BPI, the learner observes the reward function r during exploration, and its goal is to output a policy â such that, in the true MDP with transition model p we have (())(r:)) - 2 (r:p) & E) > 1- for every 8 E (0, 1). RFE considers the setting in which the reward optimize is revealed posteriori of the exploration phase. Thus the goal of the agent in RFE is to compute an estimate p of the true dynamics p so that IP suprest (J*((:p) - ()) & e) > 1 5 for every c, 6 E (0, 1), where î,,
is the optimal policy in the MDP with f as transition model and r as reward function.
53 in which, similarly to the "1-1 1 of TE E N trajectories collected by executing the expert's policy _ in a certain (unknown) MDP M = MM {r We make the assumption that - is optimal under the true (unknown) reward F in M. Since the dynamics of M is unknown, we are allowed to actively explore the environment through a forward model to collect new state-action dataset D. The goal is to use the latter and demonstrations in D to estimate a reward function that makes the expert's 's policy π optimal. Sometimes, we will denote an IRL instance M { }. and a Linear IRL instance with recovered reward r as an IRL instance in which M J {r} is a Linear MDP.
Online IRI. We consider the online? IRL. setting 39
33
68
66
online AL setting [53 66), we are given a dataset D
.......... s .i.....
|pn (B) denotes the vector containing the variation of each measure μi, over the measurable set B. "Online" refers to how we estimate the transition model p. not to the expert's policy _ for which we assume to have access to a batch dataset. This is justified by the fact that most of IRL world applications involve the presence of fixed dataset of expert demonstrations previously collected and the agent can explore the environment in order to reconstruct one (or more) reward functions compatible with those demonstrations.
3

---

3 Limitations of the Feasible Set
In this section, after having characterized the feasible set formulation in Linear MDPs, we show that it suffers from statistical (and computational) inefficiency in problems with large state spaces, even under the Linear MDP assumption. We will provide a solution to these issues in Section 4
The Feasible Set. According to the standard definition [e.g.. 1.gg..9... B3 38 contains the rewards that make the expert's s policy nh optimal, as defined below.
68 31], the feasible set
Definition 3.1 (Feasible Set (3I)) Let M be MDP without reward and let x be the expert's s policy. The feasible set Ry of rewards compatible with _. in M is defined as:
Rp == fre [ J (r: = J (r:p)).
Without function approximation, the feasible set contains a variety of rewards for any deterministic policy. In Linear MDPs, due to the feature map, the feasible set might exhibit some degeneracy BaaeeyyeDeee Def-
inition 3.1 can be adapted to I Linear MDPs with feature map & as: R := (r R J (r: J* (*;pp) 30: [H] - Rd ('ss, a, h.) e S x A [ ru(ss a) (ő(s, Bn)). We omit Φ in Rog. for notational simplicity.
Proposition 3.1. Let M be a Linear MDP without reward with a finite state space, and let & be feature mapping. Let { Ine[mn] and (Dalne[m be the sets of expert's 's and non- non-expert's 's features, defined for every h [H] as:
4% = { |ss,a")ssE
SE Sp Sp.r. , E.
T = = a) 8 SESP Sp. .GE .EE (s)).
where (s) = fa ((T)())) > for every 8 S. Ifr none of the H pairs of sets (0, 2p) there exists a separating hyperplane, then R, (7), with (n, a) 0 a, h) S x A [H] i.e. the feasible set with linear rewards in & contains only the reward function that assigns zero reward everywhere.
Intuitively, expert's actions must have the largest optimal Q-value among all actions, and linearity imposes the "separability" requirement. The result holds also for MDPs with linear rewards only. We exemplify Proposition 3.1 Appendix [..]]
Learning the Feasible Set. In order to highlight the challenges of learning the feasible set with large-scale MDPs, based on [38 31], we devise the following PAC requirement.
Definition 3.2 (PAC Algorithm). e, E (0, 1), and let A be an algorithum that collects - samples about π F using a generative model, and T episodes from a Linear MDP without reward M (S, A, H, do. p) using a forward model. Let R be the estimate of the feusible set Re, oulputted by 21 Then, 2 (c, PPC for IRL if M. (Ha(Rp,.E, R) & t) > 1- ô, where IP PM, is the probability measure induced by 2 in M, and d(r, F)x sup Σnejun (ss,a)= (..) (n, (s, a) The sample complexity is the pair (7 .).
It is worth noting that in Definition 3.2 we are considering generative model for collecting samples from the expert's policy, which represents the easiest learning scenario. The following result shows that, even in this convenient setting, estimating the feasible set is statistically inefficient.
Theorem 3.2 (Statistical Inefficiency). Let M u [T be a Linear IRL instance with finite state space S and deterministic expert's 's policy, and let e, 8 (0. 1). an algorithm A is (c,8)-PACe then T = (SS), where S = (S] is the cardinality of the state space.
In other words, even under the easiest learning conditions (i.e., generative model and deterministic expert), the sample complexity scales directly with the cardinality of the state space S, thus, it is infeasible when S is large or even infinite. Observe that this result extends to any class of MDPs that contains Linear MDPs. In Appendix B.2, we analyze if additional assumptions can drop the ((S) dependence. Nevertheless. if T is known, it is possible to construct sample efficient algorithms. Algorithm | (whose pscudocode is presented in Appendix B.3). under the assumption that π is known, makes use of an inner RFE routine (Algorithm of 62 to recover the feasible set.
We exemplify this proposition Appendix B.1 In Appendix we generalize to infinite state spaces. For simplicity, we provide the full expression of distance d in Appendix B.4 Equation II)

---

Theorem 3.3. Assume that x (along with its support SP:*#) is known. Then, for any e, ô E (0, 1),
Algorithm iis (e, (),A for IRL with a number of episodes upper bounded by:
T T Ō Hdd (d [o 3))
Limitations of the Feasible Set. We can now conclude that the feasible set suffers from two main limitations. (i) Sumple Inefficiency: If xe _ is unknown, it requires number of samples that depends on the cardinality of the state space (Theorem 3.2). (ii) Lack of Practical Implementability contains continuum of rewards, thus, practical algorithm can explicitly compute it. We will discuss in the next section how to overcome both these issues.
4 Rewards Compatibility
In this section, present the main contribution of this work: Rewards Compatibilityy novel framework for IRL that allows us to conveniently rephrase the learning from demonstrations problem classification task. We anticipate that the presentation of the framework completely general and independent of structural assumptions of the MDP (c.g., Linear MDP).
4.1 Compatible Rewards
In the following, for ease of presentation, we consider the exact setting, i.e., when do, p. and x² are known. In addition, will drop the dependence on p when clear from the context.
In IRI., an expert agent demonstrates policy F assumed optimal under some (unknown) reward function r i.e., () = J (7 The task is to recover a reward such that J*(r)= J= (r). By definition, IRL tells that rー makes the demonstrated policy - optimal, but what about other policies? We do not and cannot know. Since there are (infinite) rewards making -h optimal (but they differ the performance attributed other policies) we realize that there are many rewards equally "compatible" with x Clearly, wih no additional information, we are unable to identify y T.
The feasible set considers only these rewards, i.e., E R for which (r) J (r), and it refuses all the others. This can be interpreted as the feasible set carrying out classification of rewards based on "hard" notion of compatibility with demonstrations. In other words, rewards satisfying condition (+) _ (r) are compatible with π and the others not. Nevertheless, our insight that some rewards are "more" compatible with F= than others.
Example 4.1. Consider an MDP with one state and = 1 in which the expert has three actions: Eating a muffin (M), cake (C), some (bad) vegetable soup (S). The true reward B assigns y (M) = +1, (.C)) = + +0.99 and (S) -1, tee, the expert has a (weak) preference for the muffin over the cake, while she hates the soup; thus, she will demonstrate N = M. Let gg Tb be: =.
(2(M) +0.99, ry(C") (S) -1,
To(M)
Intuitively, rg "more" compatible with E than rt. because establishes that M and C are much better than S. while reward reverses the preferences. Clearly, we make small error if we model the preferences of the expert with Tg instead of the true reward E However, the notion of feusible set completely blind to the difference between rg and rb at modeling E. and refuses both of them.
We propose the following "soft" definition of (non)compatibility to capture this intuition 6
Definition 4.1 (Rewards (non)Coopatibilitt)). Let M Fx } be an IRL instance, and let r R be any reward. We define the (non)compatibility Cp, R200 of reward r w.r.t. M u { F) as:
Cp == (*;pp) _J=" -== (r:p).
SSee Appendix C.1
for a visual intuition.
"I Appendix C.2
multiplicative alternative definition is presented.
5

---

In words, the (non)compatiiility of reward w.r.t. policy T² in problem M quantifies the sub- optimality of nh in the MDP M o fr). By definition, rewards belonging the feasible set (i.e.. r RR, satisfy P, R (r) O, i.e., they have zero non-compatibility with x in M Example 4.1 (Continued). (Non (Non)compatibiliy discriminates between rg and rb- Indeed, have that C,, E (rb) 0, (r,) 0.01, and p (To) 2. In words, reward Tg suffers from very small (non compatibility, while 7b suffers from large (non (nonjcompatibilityy thus we say that reward rg is more compatible with π than rb. as expected.
By definition of IRL, the true reward F makes the observed RF optimal, but reveals no information about the other policies. Thus, it is meaningful that Cp,r5 considers the suboptimality of _ only, because demonstrations from π² do not provide information about other policies, as illustrated below. Example 4.2. Let ry be such that (M) +0.99, (C) = =))
+1. Clearly, ryJ is much worse than T at modeling r., because it does not capture the fact that the expert appreciates the cake but she hates the soup. However, demonstrations from T alone do not provide information about C or S, but only about x. = M (i.e., the expert always eats the muffin). Thus, we have that E (rg) C
C p (r()) 0.01, i.., T'g and r'g equally compatible with the given demonstrations.
For discussion on comparing the (non)compatibility of different rewards, see Appendix C.4
4.2 The IRL Classification Formulation
Our goal is to overcome the limitations of the feasible highlighted in Section Drawing inspiration from the notion of "membership checker" algorithm in (31, we propose a novel formulation of IRL.
Definition 4.2 (IRL Classification Problem and IRL Algorithm). An IRL Classification Problem instance is made of tuple (M, T R, A). where M is an MDP without reward, π is the expert's policy, R S R is a set of rewards to classify, and A E 22 is some threshold. The goal is to classify all and only the rewards E R based on their (nonjcompatibility with π in M w.r.t. A. In symbols:
Vr E R: if Ep,x=(r)
& A then return True, else return False.
An IRL algorithm takes in input reward e R and outputs a boolean saying whether Cr, A.
Given 7 E R. we output whether it makes the expert's policy π F at most A A-suboptimal or not. Intu- itively. we classify rewards in R based on how good π7 performs w.r.t. them. A A (moo)coompaib reward guarantees that, among its A-optimal policies, there is F but the optimal policy might be different from n: (see Appendix C.3 for how this relates to (forward) RL). Note that we allow for R * H to manage scenarios in which we have some prior knowledge on E iie., r E R c R.
Remark 4.1. Permitting non-zero (non) compaatiii is equivalent to enlarging the feasible set. Let R R, and define the set of rewards positively classified as Rr, i.e. Rs := frr R 7 (r) & A). For any A, A' s.t. 0 & A < A' & 2H, we have: Rp = Ro S RA S Rr S R2H R.
Discussion Reward Compatibility. It should be remarked that:
The limits of the rewards compatibility framework
the same the limits of the feasible set. We cannot identify R from the feasible set or among the rewards with small (non) compatibiiil, As aforementioned, this is an inherent limit of IRL and cannot be overcome with more refined objective formulation, unless further information on E is available (e.g., preferences).
Rewards compatibility offers advantages over feasible set. Differently from the feasible set, as we will see in Section [ it is possible to practically implement algorithms that solve the IRL classification problem, with guarantees of sample efficiency even when the state space is large.
4.3 A Learning Framework for Online IRL Classification
In this section, we combine the online IRL setting presented in Section 2 with the IRL classification problem of Definition 4.2 Intuitively, the performance of an algorithm depends its accuracy estimating the (non) compattiit of the rewards, as formalized by the following PAC requirement.
We use (nom)computiiiliy since reward Ri is maximally compatible when 2 = (r) Thus, the e (r) quantifies the non-compatibility of
larger C, E (r). the more r is non non-compatible. In this sense, Cp

---

Z(r)
R
((r)
A
A
A
(a) Reward is classified cor- rectly.
(b) Reward
can be
mis-
Range of uncertain (non)compatibility values.
classified.
Figure 2: The axis represents (estimated) (non)compatibility values. (a) Rewards whose true (non)compatibility C(r) = = (r) is far from threshold A by at least while (b) the opposite case, rewards can be mis-classified. (c) The red interval [A E, + e] exemplifies the set of rewards {r R R[[((r) - A < e) that are (potentially) mis-classifidd. The length of the interval reduces with
correctly classified,
Definition 4.3 (PAC Framework). L E (0, 1), and let D be a dataset of expert's trajectories. An algorithum 2 exploring for episodes is 6y-A) PACCffff for the IRL classification problem if:
IP
sup
(p.)*(r) A(r) rER
5,
M.r
where P F x is the joint probability measure induced by Th and A in M, and C is the estimate of C computed by The sample complexity is defined by the pair (TB,T).
Intuitively, goal is to estimate the (non cooppttoitti of the rewards in R. with sufficient accuracy, so that, given threshold A > O, are able to classify "most" of them correctly w.h.p. (with high probability). The concept is exemplified in Figure Note that the estimation problem is independent of the threshold A, which can be appro- priately selected cope with noise in the demonstrations, (unknown) expert suboptimality, or to manage the amount of "false negatives" and "false positives".
Input: expert dataset DF. threshold A sct classify
Exploration phase
Collert exploration dataset
Input: reward clos- slyy E R
Remark 4.2. For 17 3 O, let Ry := & RIC. &
7) and R, == {r E R (()) & ni denote the sets of rewards positively classified using, respectively, the true (non compatibility Cp.n" and the estimate Ć constructed by an (c, 6)C algorithm. Then, with probability - 5, it holds that: RA- S Rs S Rstc. Thus, can trade-off the amount of "false negatives" (resp. "false positives" ") by, e,g., choosing the threshold A < A (resp. e).
Classifiettion phase
Estimate (r(rr æ (r:p) using DE
Estimate (+(r (r(pp)
via planning with
Classity reward ((r) ("(r) (r)
CATY-IRL: A Provably Efficient Algorithm for IRL
Ćir) x A?
no
In this section, we present IRL (CompATibility for IRL), a provably efficient algorithm for solving the online IRI. classification problem. We consider three different kinds of structure for the MDPs: tabular MDPs, tabular MDPs with linear rewards, and Linear MDPs. Similarly to RFE, our online IRL classification setting is made of two phases: (i) exploration phase, in which the algorithm explores the environment using the knowledge R and of the expert's dataset D collect samples about the dynamics of the MDP, and (fi) classification phase, in which it performs the classification of a reward r e R without interactions with the environment. flow-chart reported in Figure (pseudocode in Appendix [
class Troe
class Falso
Output: class
Figure 1: Flow-chart of CATY- -IRL
Exploration phase. The exploration phase collects a dataset D in way that depends on the structure of the MDP and of the set of rewards R to be classified. Specifically, for Linear MDPs.

---

CATY- IRL executes RFLin 62 Instead, for tabular MDPs (with or without linear reward), CATY-IRL
instantiates either BPI-UCBVI (37 for each reward r E (when |R| ( a "small" constant w.r.t to the size of the MDP, where "small" depends on the size of the state space, see Appendix (D.2)
or RF-Express 37 Note that CATY-IRL in this phase does not use the expert's dataset DE
Classification phase. The classification performs the estimation C(r) of the (non)compatibility term C p. (r) for the single input reward r E R by splitting into two independent estimates: (r) * Jx (r:p), which is computed with D only, and J J (r;p), which is computed with only. Concerning (r), when the reward is linear ra(s, a) = (ő(s, a), 0n), CATY-IRL uses DE to construct an empirical estimate 5. se aip.* of the expert's expected feature count [6] Otherwise, it directly estimates d= 2 d the expert's occupancy measure. Such estimates can be used to derive (r) straightforwardly. Regarding (r), CATY-IRL exploits the planning phase of the corresponding RFE (or BPI) algorithm adopted at exploration phase Finally, CATY-IRL applies the (potentially negative) input threshold A to the difference J*(1) - (r( to perform the classification. See Appendix [ for the full pseudo-code. Clearly, CATY- IRL can be implemented in practice, since it considers a single reward at a time instead of computing the full feasible set, and it computationally efficient linear MDPs, since it uses a computationally efficient algorithm as subroutine (see 62)).
Sample Efficiency. The next result analyzes the sample complexity (Definition 4.3 of CATY-IRL.
Theorem 5.1 (Sample Complexity of CATY-IRL). Let c, (0, 1). Then BATY-IRLI is (c, (c,8)-PAC for IRL with a sample complexity upper bounded by:
Tabular MDPs:
T
< δ
H SA
log 7
1)
T < δ
HA
N + log 2))
6
62
Tabular MDPs with linear rewards:
B
< θ
Hdd
log
7)
1
T θ
H SASA
N + log 1))
6
6²
Linear MDPs:
+ & 3
Hdd
log
))
T :
Hdd
(2
(d+ (d+ log )))
2
where N 0 if | [
0(1), and N S otherwise.
Some observations are in order. We conjecture that the d2 dependence when [R] O(1) is unavoid- able in Linear MDPs because of the lower bound for BPI in (62). In tabular MDPs with deterministic expert, one might use the results in [66] to reduce the rate of - from OSSA log(d-+)/e2) to O($113/2log) 8 (E²). Finally, note that the choice A = allows us to positively classify all the rewards in the feasible set Rp. w.h.p. and, in this case, other rewards positively classified have true (non) (non)compatibility at most 2e w.h.p. In light of this result we conclude that rewards compatibility framework allows the practical development of sample efficient algorithms (e.g., CATY-IRL) in Linear MDPs with large/continuous state spaces.
Statistical Barriers and Objective-Free Exploration
In this section, we show that CATY minimax optimal for the number of exploration episodes in tabular MDPs, and that RFE and IRL share the same theoretical sample complexity. This allows us to formulate Objective-Free Exploration, a unifying setting for exploration problems.
6.1 The Theoretical Limits of IRL (and RFE) in the Tabular Setting
In CATY-IRI we use a minimax optimal RFE algorithm for exploration. However, this does not entail that CATY-IRL is minimax optimal for the IRL classification problem. There might exist another PAC algorithm with sample complexity smaller than CATY-IRL. The following result states that, in the tabular setting, the bound in Theorem 5.1 is tight for the number of episodes T.
"RFE/BPI algorithms, at planning phase, return a policy, and not its estimated performance. Since BPI- UCBVI, RF-Express, and RFLin each compute an estimate of 2 (r: p) as an intermediate step, with negligible abuse of notation, assume that they output such estimate.
8

---

Theorem 6.1 (IRL Classification Lower Bound), Let 2 be an (c. 6.- algorithm for the IRL classification in tabular sDPs. Let be the number of exploration episodes. Then, there exists an IRI. classification instance such that:
SA
SA 62
(S +010 log 2 ))
3| 7 2
log
if - T 1
In both cases, the lower bound is matched by CATY-IRL, up to logarithmic factors. Note that CATY-IRL explores without using DE, thus, minimax optimality for be achieved without the knowledge of D at exploration phase. As by- product we observe that a similar lower bound construction can be made also for RFE, leading the following result.
Theorem 6.2 (RFE- Refined Lower Bound). Let 2 be an (c. 6PC algorithm for RFE in tabular MDPs. Let T be the number of exploration episodes. Then, there exists an RFE instance such that:
SA 2
S + +l+1o 7)
T 2
This bound improves the state-of-the-art RFE lower bound Q2 = 1 log })) (obtained combining the bounds in 21 and (12) by one factor, and it is matched by RF-Express (37].
6.2 Objective-Free Exploration (OFE)
What is the most efficient exploration strategy that can be performed in unknown environment? depends on the subsequent task that shall be solved. However, if the task unknown at the exploration phase, need strategy that suffices for all the tasks that might be interested in solving. Let us denote by f the set of RL and IRL classification tasks. Since CATY-IRL is a sample efficient algorithm for the IRL classification problem, and it uses RFE subroutine, conclude that the RFE exploration strategy sufficient (and also minimax optimal in tabular MDPs) to obtain guarantees for class F. Are there other problems for which RFE exploration suffices when the specific problem instance is revealed posteriori of the exploration phase? We believe so, and in Appendix E. identify two additional problems, i.e., Matching Performance (MP) and Imitation Learning from Observations alone (ILfO) 334, that represent potential candidates to belong to P.
More in general, we formulate the Objective-Free Exploration (OFE) problem follows:
Definition 6.1 (Objective-Free, Exploration). Given a tuple (M, I (e, 8)), where M is an unknown environment (e.g., MDP without reward), and F is certain class of tasks (e.g., all RL and IRL prob- lems), the Objective- Free Exploration (OFE) problem aims to find an exploration of the environment M (e.g., RFE exploration) that permits to solve any task f E I in (c, (c,8)-come -0-orret manner.
This problem is called "objective-free" because it does not require the knowledge of the specific "objective" f e & be solved. In Appendix F we describe a use case for OFE. We believe this an interesting problem to be studied in future.
7 Conclusions
In this paper, we have shown that the feasible set cannot be learned efficiently in problems with large/continuous state spaces even under the strong structure provided by Linear MDPs. For this reason, we have introduced the powerful framework of compatible rewards, which formalizes the intuitive notion of compatibility of reward function with expert demonstrations, and it allows us to formulate the IRL problem as a classification task. In this context, we have devised CATY-IRI. IRL, a provably efficient IRL algorithm for Linear MDPs with large/continuous state spaces. Furthermore, in tabular MDPs, we have demonstrated the minimax optimality of CATY-IRL at exploration by presenting novel lower bound to the IRL classification problem. As by-product, our construction improves the current state-of-the -fhte-rr lower bound for RFE. Finally, we have introduced OFE, a unifying problem setting for exploration problems, which generalizes both RFE and IRL.
Limitations. limitation of our contributions concerns the adoption of the Linear MDP model, whose assumptions are overly strong to be consistently applied to real-world applications. Neverthe- less, while the rewards compatibility framework is general and not tied Linear MDPs, we believe that Linear MDPs represent important initial step toward the development of provably efficient IRL

---

algorithms with more general function approximation structures. Although lower bound for Linear MDPs missing, we believe that it represents an interesting direction for future works. Finally, we note that the empirical validation of the proposed algorithm is out of the scope of this work.
Future Directions. Promising directions for future works concern the extension of the analysis of the rewards compatibility framework beyond Linear MDPs to general function approximation and to the offline setting. In addition, it might be fascinating extend the notion of reward compatibility to other kinds of expert feedback (in the context of ReL), and to other IRL settings (c.g., suboptimal experts). Finally, we believe that OFE should be analysed in-depth given its practical importance.
Acknowledgments and Disclosure of Funding
AI4REALNET has received funding from European Union'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.
Funded by the European Union Next Generation EU within the project NRPP M4C2, Investment 1.,3 DD. 341 15 march 2022 FAIR Future Artificial Intelligence Research Spoke 4 PE00000013 DS3C220023800066.
References
[1] Pieter Abbeel, Adam Coates, Morgan Quigley, and Andrew Ng. An application of reinforcement learning to aerobatic helicopter flight. Advances in Neural Information Processing Systems 19 (NeurIPS), 2006.
[2] Pieter Abbeel and Andrew Y. Ng. Apprenticeship learning via inverse reinforcement learning. In International Conference on Machine Learning 21 (ICML), 2004.
[3] Picter Abbeel and Andrew Y. Ng. Exploration and apprenticeship learning in reinforcement learning. In International Conference on Machine Learning 22 (ICML), 2005.
[4] Stephen Adams, Tyler Cody, and Peter A. Beling. A survey of inverse reinforcement learning. Artificial Intelligence Review, 55:4307-4346. 2022.
[5] Kareem Amin and Satinder Singh. Towards resolving unidentifiability in inverse reinforcement learning, 2016.
[6] Saurabh Arora and Prashant Doshi. A survey of inverse reinforcement learning: Challenges, methods and progress. Artificial Intelligence, 297:103500, 2018.
[7] Matt Barnes, Matthew Abueg, Oliver F. Lange, Matt Deeds, Jason Trader, Denali Molitor, Markus Wulfmeier, and Shawn O' Banion. Massively scalable inverse reinforcement learning in google maps, 2024.
[8] Dimitri Bertsekas. Convex Optimization Theory. Athena Scientific, 2009.
[9] Michael Bowling, John D. Martin, David Abel, and Will Dabney, Settling the reward hypothesis.
In International Conference Machine Learning 40 (ICML), 2023.
[10] Haoyang Cao, Samuel Cohen, and Lukasz Szpruch. Identifiability in inverse reinforcement learning. In Advances in Neural Information Processing Systems 34 (NeurIPS), pages 12362- 12373, 2021.
[11] Gregory Dexter, Kevin Bello, and Jean Honorio. Inverse reinforcement learning in a continuous state space with formal guarantees. In Advances in Neural Information Processing Systems 34 (NeurIPS), pages 6972-6982, 2021.
[12] Omar Darwiche Domingues, Pierre Ménard, Emilie Kaufmann, and Michal Valko. Episodic reinforcement learning in finite mdps: Minimax lower bounds revisited. International Conference Algorithmic Learning Theory 32 (ALT), volume 132, pages 578-598, 2021.
10

---

[13] Simon Du, Sham Kakade, Jason Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang. Bilinear classes: structural framework for provable generalization in rl. In International Conference Machine Learning 38 (ICML), volume 139, pages 2826-2836, 2021.
[14] Chelsea Finn, Sergey Levine, and Pieter Abbeel. Guided cost learning: Deep inverse optimal control via policy optimization. In International Conference on Machine Learning 33 (ICML), volume 48, pages 49-58, 2016.
[15] Justin Fu, Katie Luo, and Sergey Levine. Learning robust rewards with adversarial inverse reinforcement learning. In International Conference on Learning Representations 5 (ICLR), 2017.
[16] Dylan Hadfield-Menell, Smitha Milli, Pieter Abbeel, Stuart Russell, and Anca Dragan, Inverse reward design. In Advances in Neural Information Processing Systems 30 (NeurIPS), 2017.
[17] Dylan Hadfield-Meneld Stuart Russell, Pieter Abbeel, and Anca Dragan. Cooperative inverse reinforcement learning. In Advances in Neural Information Processing Systems 29 (NeurIPS), 2016.
[18] Jonathan Ho and Stefano Ermon. Generative adversarial imitation learning. In Advances in Neural Information Processing Systems 29 (NeurIPS), 2016.
[19] Hong Jun Jeon, Smitha Milli, and Anca Dragan. Reward-rational (implicit) choice: A unifying formalism for reward learning. In Advances in Neural Information Processing Systems 33 (NeurlPS), pages 4415-4426, 2020.
[20] Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E. Schapire. Contextual decision processes with low Bellman rank are PAC-learnable. In International Conference Machine Learning 34 (ICML), volume 70, pages 1704-1713, 2017.
[21] Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu. Reward-free exploration for reinforcement learning. In International Conference on Machine Learning 37 (ICML), volume 119, pages
2020.
[22] Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of problems. and sample-efficient algorithms. In Advances Neural Information Processing Systems 34 (NeurIPS), pages 13406-13418 2021.
[23] Chi Jin, Zhuoran Yang. Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory 33 (COLT), volume 125, pages 2137-2143, 2020.
[24] Emilic Kaufmann, Pierre Ménard, Omar Darwiche Domingues, Anders Jonsson, Edouard Leurent, and Michal Valko. Adaptive reward-free exploration. In International Conference Algorithmic Learning Theory 32 (ALT), volume 132, pages 865-891, 2021.
[25] Kuno Kim, Shivam Garg, Kirankumar Shiragur, and Stefano Ermon. Reward identification in inverse reinforcement learning. In International Conference on Machine Learning 38 (ICML), pages 5496-5508 2021.
[26] Kuno Kim, Yihong Gu, Jiaming Song, Shengjia Zhao, and Stefano Ermon. Domain adaptive imitation learning. In International Conference on Machine Learning 37 (ICML), volume 1 119, pages
2020.
[27] Edouard Klein, Matthieu Geist, Bilal Piot, and Olivier Pietquin. Inverse reinforcement learning through structured classification. In Advances in Neural Information Processing Systems 25 (NeurIPS), 2012.
[28] Abi Komanduru and Jean Honorio. On the correctness and sample complexity of inverse reinforcement learning. In Advances in Neural Information Processing Systems 32 (NeurIPS), 2019.
[29] Abi Komanduru and Jean Honorio. A lower bound for the sample complexity of inverse reinforcement learning. In International Conference on Machine Learning 38 (ICML), volume 139, pages 5676-5685, 2021.
11

---

[30] David M. Kreps. Notes On The Theory Of Choice. Westview Press, 1988.
[31] Filippo Lazzati, Mirco Mutti, and Alberto Maria Metelli. Offline inverse rl: New solution concepts and provably efficient algorithms. In International Conference on Machine Learning 41 (ICML), 2024.
[32] Gen Li, Yuling Yan, Yuxin Chen, and Jianqing Fan. Minimax-optimal reward-agnostic explo- ration in reinforcement learning, 2023.
[33] David Lindner, Andreas Krause, and Giorgia Ramponi. Active exploration for inverse reinforce- ment learning. In Advances in Neural Information Processing Systems 35 (NeurIPS), pages 5843-5853, 2022.
[34] YuXuan Liu, Abhishek Gupta, Pieter Abbeel, and Sergey Levine. Imitation from observation: Learning to imitate behaviors from raw video via context translation. In JEEE International Conference Robotics and Automation (ICRA), pages 1118 118--111 1125, 2018.
[35] Zhihan Liu, Yufeng Zhang, Zuyue Fu, Zhuoran Yang, and Zhaoran Wang. Learning from demonstration: Provably efficient adversarial policy imitation with linear function approxi- mation. In International Conference on Machine Learning 39 (ICML), volume 162, pages 14094-14133 2022.
[36] Manuel Lopes, Francisco Melo, and Luis Montesano. Active learning for reward estimation in inverse reinforcement learning, In Machine Learning and Knowledge Discovery in Databases (ECML PKDD), pages 31 31-46, 2009.
[37] Pierre Menard, Omar Darwiche Domingues, Anders Jonsson, Emilie Kaufmann, Edouard Leurent, and Michal Valko. Fast active learning for pure exploration in reinforcement learning. In International Conference on Machine Learning 38 (ICML), volume 139, pages 7599-7608, 2021.
[38] Alberto Maria Metelli, Filippo Lazzati, and Marcello Restelli. Towards theoretical understanding of inverse reinforcement learning. In International Conference on Machine Learning 40 (ICML), volume 202, pages
2023.
[39] Alberto Maria Metelli, Giorgia Ramponi, Alessandro Concetti, and Marcello Restelli, Provably efficient learning of transferable rewards. In International Conference on Machine Learning 38 (ICML), volume 139, pages 7665-7676. 2021.
[40] Bernard Michini, Mark Cutler, and Jonathan P. How. Scalable reward learning from demonstra- tion. In JEEE International Conference on Robotics and Automation (ICRA), pages 303-308, 2013.
[41] Volodymyr Mnih, Koray Kavukeuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning, 2013.
[42] Andrew Ng and Stuart Russell. Algorithms for inverse reinforcement learning. In International Conference on Machine Learning 17 (ICML), pages 663-670, 2000.
[43] Donald Ornstein. On the existence of stationary optimal strategies. Proceedings of the American Mathematical Society, 20(2):563-569 1969.
[44] Riccardo Poiani, Gabriele Curti, Alberto Maria Metelli, and Marcello Restelli. Inverse rein- forcement learning with sub-optimal experts, 2024.
[45] Martin Lee Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, Inc., 1994.
[46] Nived Rajaraman, Yanjun Han, Lin Yang. Jingbo Liu, Jiantao Jiao, and Kannan Ramchandran. On the value of interaction and function approximation imitation learning. In Advances in Neural Information Processing Systems 34 (NeurIPS), volume 34, pages 1325-1336, 2021.
[47] Nived Rajaraman, Lin Yang, Jiantao Jiao, and Kannan Ramchandran. Toward the fundamen- tal limits of imitation learning. In Advances in Neural Information Processing Systems 33 (NeurIPS), pages 2914-2924 2020.
12

---

[48] Nathan D. Ratliff, J. Andrew Bagnell, and Martin A. Zinkevich. Maximum margin planning. In International Conference on Machine Learning 23 (ICML), pages 729-736, 2006.
[49] Stuart Russell. Learning agents for uncertain environments (extended abstract). Conference on Computational Learning Theory 11 (COLT), pages 101-103, 1998.
[50] Stuart Russell and Peter Norvig. Artificial Intelligence: A Modern Approach. Prentice Hall, 3 edition, 2010.
[51] Rohin Shah, Noah Gundotra, Pieter Abbeel, and Anca Dragan. On the feasibility of learning, rather than assuming, human biases for reward inference. In International Conference on Machine Learning 36 (ICML), volume 97, pages 5670-5679, 2019.
[52] Mehran Shakerinava and Siamak Ravanbakhsh. Utility theory for sequential decision making. In International Conference on Machine Learning 39 (ICML), volume 162, pages 19616-19625, 2022.
[53] Lior Shani, Tom Zahavy, and Shie Mannor. Online upprenticeship learning. In AAAI Conference on Artificial Intelligence 36 (AAAI), pages 8240-8248, 2022.
[54] David Silver, Aja Huang, Christopher J. Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schrittwieser, loannis Antonoglou, Veda Panneershelvam, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lil- licrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis. Mastering the game of go with deep neural networks and tree search. Nature, 529:484-5033 2016.
[55] Joar Skalse and Alessandro Abate. Misspecification in inverse reinforcement learning, In AAAI Conference Artificial Intelligence 37 (AAAI), pages 15136-15143, 2023.
[56] Joar Max Viktor Skalse, Matthew Farrugia-Robert Stuart Russell, Alessandro Abate, and Adam Gleave. Invariance in policy optimisation and partial identifiability in reward learning. In International Conference Machine Learning 40 (ICML), volume 202, pages 32033-3203 2023.
[57] Wen Sun, Anirudh Vemula, Byron Boots, and Drew Bagnell. Provably efficient imitation learning from observation alone. In International Conference on Machine Learning 36 (ICML), volume 97, pages 6036-6045, 2019.
[58] Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. A Bradford Book, 2018
[59] Gokul Swamy, Nived Rajaraman, Matt Peng. Sanjiban Choudhury, Bagnell, Steven Z. Wu, Jiantao Jiao, and Kannan Ramchandran. Minimax optimal online imitation learning via replay estimation. In Advances in Neural Information Processing Systems 35 (NeruIPS), volume 35, pages 7077-7088, 2022.
[60] Umar Syed and Robert E Schapire. A game-the approach apprenticeship learning. In Advances in Neural Information Processing Systems 20 (NeurIPS), 2007.
[61] Luca Viano, Stratis Skoulakis, and Volkan Cevher. Imitation learning in discounted linear mdps without exploration assumptions, 2024.
[62] Andrew J Wagenmaker, Yifang Chen, Max Simchowitz, Simon Du, and Kevin Jamieson. Reward-free RL is no harder than reward-aware RL in linear Markov decision processes. In International Conference on Machine Learning 39 (ICML), volume 162, pages 22430-22456. 2022.
[63] Ruosong Wang, Simon S Du, Lin Yang, and Russ R Salakhutdinov. On reward free rein- forcement learning with linear function approximation. In Advances Neural Information Processing Systems 33 (NeurIPS), pages 17816-17826, 2020.
[64] Ruosong Wang, Ruslan Salakhutdinov, and Lin F. Yang- Reinforcement learning with general value function approximation: provably efficient approach via bounded eluder dimension. In Advances in Neural Information Processing Systems 34 (NeurIPS), pages 6123-6135. 2020.
13

---

[65] Christian Wirth, Riad Akrour, Gerhard Neumann, and Johannes Fürnkranz. A survey of preference-basee based reinforcement learning methods. Journal of Machine Learning Research, 18:1 2017.
[66] Tian Xu, Ziniu Li, Yang Yu, and Zhimin Luo. Provably efficient adversarial imitation learning with unknown transitions. In Conference on Uncertainty in Artificial Intelligence 39 (UAI), volume 216, pages 2367-2378 2023.
[67] Lin Yang and Mengdi Wang. Sample-optimal parametric q-learning using linearly additive features. In International Conference on Machine Learning 36 (ICML), volume 97, pages 6995-7004, 2019.
[68] Lei Zhao, Mengdi Wang, and Yu Bai. Is inverse reinforcement learning harder than standard reinforcement learning? In International Conference on Machine Learning 41 (ICML), 2024.
[69] Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari. Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. Conference on Learning Theory 34 (COLT), pages 4532-4576, 2021.
[70] Brian D. Ziebart, Andrew L. Maas, J. Andrew Bagnell, and Anind K. Dey. Maximum entropy inverse reinforcement learning. AAAI Conference on Artificial Intelligence 23 (AAAI), pages 1.33-1438 2008.
14

---

A Related Works
In this appendix, report and describe the literature that most relates to this paper. Theoretical works concerning the online IRI. problem can be grouped in works that concern the feasible set, and works that do not.
Let us begin with works related to the feasible set. While the notion of feasible set has been introduced implicitly in 42] the first paper that analyses the sample complexity of estimating the feasible set in online IRL is [39]. Authors in [39] adopt the simple generative model in tabular MDPs, and devise two sample efficient algorithms. [31 focuses on the same problem [39], but adopts forward model in tabular MDPs. By adopting RFE exploration algorithms, they devise sample efficient algorithms. However, as remarked in 68) paper (33) suffers from limitation in the definition of the dissimilarity between feasible sets. [88] builds upon [39] to construct the first minimax lower bound for the problem of estimating the feasible set using generative model. The lower bound
in the order of Q 54 (S + log 2)), where S and A are the cardinality of the state and action spaces, H is the horizon, is the accuracy and ó the failure probability. In addition. (38] develops
US-IRL, an efficient algorithm whose sample complexity matches the lower bound. [44] analyze a
setting analogous to that of (38. in which there is availability of single optimal expert and multiple suboptimal experts with known suboptimality. [1] analyse the problem of estimating the feasible set
when no active exploration of the enviromment is allowed, but the learner is given batch dataset collected by some behavior policy n². Interestingly, [31] focuses on two novel learning targets that suited for the offline setting, i.e., a subset and superset of the feasible set. Authors in [I demonstrate that such sets are the tightest learnable subset and superset of the feasible set, and propose a pessimistic algoroithm, PIRLO, to estimate them. (68) analyses the same offline setting as B1. but instead of focusing on the notion of feasible set directly, it considers the notion of reward mapping, which considers reward functions as parametrized by their value and advantage functions. and whose image coincides with the feasible set.
With regards to online IRL works that do not consider the feasible set, we mention 36), which analyses an active learning framework for IRL. However, [36) assumes that the transition model is known, and its goal is to estimate the expert policy only. Works (28) and [29] provide, respectively, an upper bound and a lower bound to the sample complexity of IRL. for B-strict separable problems in the tabular setting. However, both the setting considered and the bound obtained are fairly different from ours. Analogously, [1I provides a sample efficient IRL algorithm for 3-strict separable problems with continuous state space. However, their setting is different from ours since they assume that the system can be modelled using a basis of orthonormal functions.
A.1 Additional Related Works
In this section, we collect additional related works that deserve to be mentioned.
Identifiability and Reward Learning. As aforementioned, the IRL problem is ill- ill-posed. thus, to retrieve a single reward, additional constraints shall be imposed. [5] analyses the setting in which demonstrations of an optimal policy for the same reward function are provided across environments with different transition models. In this way, authors can reduce the experimental unidentifiability. and recover the state-only reward function. [10] and (26) concern reward identifiability but in entropy-regularized MDPs 770, [5]. Such setting is in some sense easier than the common IRL permits unique optimal policy for any reward function. 110 uses expert demonstrations from multiple transition models and multiple discount factors to retrieve the reward function, while 26 analyses properties of the dynamics of the MDP to increase the constraints. With regards to the more general field of Reward Learning (Rel.), we mention [19], which introduces a framework that formalizes the constraints imposed by various kinds of human feedback (like demonstrations or preferences (65)). Intuitively, multiple feedbacks about the same reward represent additional constraints beyond mere demonstrations. [56) characterizes the partial identifiability of the reward function based on various reward learning data sources.
setting, because entropy-regularizaen
Linear MDPs and Extensions. As explained for instance in 23 since lower bounds to the sample complexity of various RL tasks in tabular MDPs depend explicitly on the cardinality state space S, then we need to add structure to the problem if we want to develop efficient algorithms that scale to large state spaces. For this reason, the works 67 23 analyze the Linear MDP model, which enforces
15

---

some linearity constraints to the common MDP model. In this way, authors are able to provide efficient algorithms for RL in problems with large/continuous state spaces. However, there are other settings beyond Linear MDPs that are analysed in the RI. literature. 20 introduces the notion of Bellman rank as complexity measure, and provides sample efficient algorithm for problems with [64] analyzes general value function approximation when the function class has a low eluder dimension. [22] generalizes both the eluder dimension and Bellman rank complexity measures by defining the Bellman eluder dimension and providing provably efficient algorithm.
small Bellman rank.
13 introduces bilinear classes, a structural framework that, among the others, generalizes Linear MDPs
Reward-Free Exploration (RFE) in Tabular and Linear MDPs. The RFE problem was intro- duced in (11,, where authors provided a sample efficient algorithm and a lower bound for tabular MDPs. Later on, the state-of-the-at sample-efficient algorithms for RFE in tabular MDPs have been developed in [24] (7 32.. It should be remarked that RFE requires more samples than common RL
in tabular MDPs. 63 proposes sample efficient algorithm for RFE in linear MDPs. [62 improves
the algorithm of 663 and, interestingly, demonstrates that RFE is no harder than RL in Linear MDPs.
Online Apprenticeship Learning (AL). The first works that provide a theoretical analysis of the AL setting when the transition model is unknown are 3 60]. Recently, [53] formulates the online AL problem, which closely resembles the online IRL. problem. The main difference is that in online AL the ultimate goal is to imitate the expert, while in IRL. is to recover a reward function. [66] improves
the results in [53] by combining an RFE algorithm with an efficient algorithm for the estimation of
the visitation distribution the deterministic expert's 's policy tabular MDPs, presented in [47). We
mention also 46 59] for the sample complexity of estimating the expert's 's policy in problems with linear function approximation. In the context of Imitation Learning from Observation alone (ILfO) (34, the work [57] proposes probably efficient algorithm for large-scale MDPs with unknown transition model. (35) provides an efficient AL algorithm based on GAIL 18] in Linear Kernel
Episodic MDPs [69] with unknown transition model.
Others. We mention work 27 which considers classification approach for IRL. However, this is fairly different from our IRL problem formulation in Section 4
B Additional Results and Proofs for Section 3
In this section, we provide additional results beyond those presented in Section 3 and then we report the missing proofs. Specifically, in Appendix [B.1 we provide two numerical examples that explain Proposition 3.1. in Appendix [B.2 we show that some additional regularity assumptions beyond the Linear MDP cannot remove the dependence on the cardinality of the state space in the sample complexity. In Appendix B.3] we report and describe the sample efficient algorithm mentioned in Section while in Appendix B.4 we collect all the missing proofs of this section.
B.1 Some Examples for Proposition 3.1
The following examples aim to explain Proposition 3.1 in a simple manner.
Example B.1 (Non-degenerate feasible set). Let M = (S, do)) u { be an IRL instance such that S = {$1, $2).A {a,, az). H 1, = do(s2) = 1/2, F (s1 ==(2)) ai- Consider the feature mapping Φ1 s.t. (1(88)) = Ia = an) for all s E S. Then, we have
$x 5 [1} and T- {0}. Clearly, these sety can be separated by any hyperplane
E Rso. since 1. w > w, and so Rp * (7), with (n)(s,)) = 0 V(ss, h) E S x A x [H]. Actually, R {r R 30 (0, 1]: (1(s,a) ()(s, 0) v(s a) S A).
Example B.2 (Degenerate feasible set). Consider the same IRL instance as in the previous example, but this time consider the feature mapping Φ2 s.t. Φ2(s1, a) 1 {a a1), and dz( a) Iiaa a2). Then, we have th {0, 1) and tb {0, 13. Clearly, the two sets coincide, thus they cannot be separated, and Rp (F), with (s, a) 0 V a, h) E S x A x [H].
16

---

B.2 Additional Regularity Assumptions of the State Space do not Make the Problem Learnable
In tabular MDPs with small state space S, collecting samples from every state s S is feasible, and it is exactly what previous works do:
Under the assumption that x² is deterministic, 39 38
collect one sample from every exactly.
(s, h) E x [H] using a generative model, obtaining π
If n is stochastic, under the assumption that all actions in the support of the expert's 's policy are played with probability at least mii (see Assumption D.1 of (38), both [38 688 are able to learn the support of x exactly w.h.p. using 01 /mi/ samples in the online setting
In the offline setting, assuming that the occupancy measure of the expert's policy least dmin in all reachable (s, a) E 8 x A, then [3]] learns the support of x exactly w.h.p. using x1/dmin episodes.
However, when S is large, even under the Linear MDP assumption, this is not possible. In Section 3 we have formalized this fact with the following proposition:
Theorem 3.2 (Statistical Inefficiency). Let M u (m be a Linear IRI. instance with finite state space S and deterministic expert's 's policy, and let c, 5e (0, 1). If an algorithu M is (c,8)-PAC, then 7 SS)). where 5 = (S] is the cardinality of the state space.
Theorem 3 tells us that the Linear MDP assumption is too weak for the feasible set to be learnable using the PAC framework of Definition (.22 with number of samples independent of the cardinality of the state space. Therefore, we can try to introduce an additional assumption on the structure of the IRL problem M u [n and see whether it helps in alleviating the issue. Let us consider the following first assumption.
Assumption B.1.
We assume a Lipschitz continuity property between features and states:
((s,,,s') E S A S: in S. for some L 0 and some distance
[ō(s, o(s',a)lla L||s s'll.
The intuition that, based on the fact that in Linear MDPs the Q-function of any policy is linear in
the feature mapping (-::) ()(:,-), wx)) for some parameter vector w E R (see (23) then if
we are able to e-cover the state space S, we can approximate the Q-function (7, any s S
with the Q-function (7,(s', of the closest point s' int the covering. so that (s. (s', (((ss))) a) =
(()(s, o(s', , ())TTTj) & [lo(s, a) o(s', |2 not sufficient.
Le| [e][w[][2. However, this assumption
Proposition B.1. Under the setting of Proposition 3.2 even under Assumption B.1 then an algorithm is (e.8)-PAC only - = Q(S).
Assumption B. fails because it does not provide any information about how the knowledge of the expert's policy at a state can be "transferred" to other states, and thus we still need to sample almost all the states of SP." to get an acceptable feasible set.
We devise another assumption attempt to fix this issue.
Assumption B.2. We assume the following Lipschitz continuity property: V(s,s') E S x S: [[o(s, (s)) 0(s', - a (s'))lla & Llls - s'
for some > 0 and some distance | - in S.
This assumption says that states that are close to each other cannot have the features corresponding to the expert's action too far away from each other. From a high-level point of view, it says that the features are "somehow" regular with F= so that when the expert lies in s' which is really close to then she plays an action which has the same "effect" (i.c., same transition model and same reward, due to the Linear MDP assumption) as the expert's is action in 8.
Assumption B.2 is not comparable with Assumption B. since, the one hand, it does not hold for all actions in A, but only for those corresponding to π but, on the other hand, provides information on how to transfer knowledge about E to neighbor states.
AAtuallyy 688 makes of concentrability assumption too.
17

---

Let A' = mi s. (.)((s.)))(((a)) (l)(s, o(s,, a') 12) i... the smallest non-zero distance between the features of different actions. Clearly, when S finite, since Linear MDPs also
A : A| is finite, then A' is finite too. So we can define a new quantity A to be any number A A'
Proposition B.2. Under the setting of Proposition 3.2 under Assumption B.2 then number
of samples F W II) is sufficient to recover Th exactly in any (8, h) E S, where (1 S IDI is the A/22e)-oovering number of space S w.r.t. distance
Intuitively, by constructing a covering with a sufficiently small radius in the state space S, then we are able to retrieve the exact expert's 's action in the neighborood of each state of the covering. Doing so, we are able construct e-correct estimates the feasible set. Of course, this is possible long as A' is not too small, and L is not too large. When S is infinitely large or continuous, it might be possible to construct feature mappings which A 0, and so the approach would still require too many samples.
However, for cases with finite and not small A', the result in Proposition B.2 is not satisfactory, because it just allows to retrieve T under stronger assumption than Linear MDPs, but perform an interesting learning process. We observe that the feasible set an "unstable" concept, in the sense that, based on Proposition 3.T changing the expert action in single state might reduce the feasible set from continuum of rewards a singleton, or vice versa.
Remark B.1. we want be able to recover the exact feasible set efficiently, need recover the exact expert's 's policy almost everywhere.
B.3 Algorithm
By exploiting an RFE algorithm as sub-routine like that of Algorithm 1 in [63 or Algorithm 1 in 62.. we are able to construct estimates of the transition model f. that can be used to compute an "empirical" estimate of the feasible set R R2 (since & and n are known). The algorithm is presented in Algorithm T
Algorithm 1: IRL for Linear MDPs (known expert's policy)
Data: failure probability 8 > 0, error tolerance >> 0, expert policy TF, all sets Z = x [M]
that coincide with SP.* x
almost everywhere based on measure d=.""
D RFE Exploration( 6, c) for h in {H, H
/* Various choices */
1...., 2. do
Aa - I Σ 0(s of ( a
k=1
(an()) A Σ osh o(0, s
end
(n(sss,)) - (ó((,,)), (. (-)) for all SSS Ax [H]
7 R - {f E R 32, ((s, h)) VaE A:
d's (3 (1s))(1s))
E
8 Return R
Simply put, Algorithm ! Jses the dataset collected by an RFE algorithm compute least-squares estimate the transition model f. and then returns the feasible set defined according to (recall that é and , are known). Notice that this algorithm cannot be implemented in practice due to various reasons, like the presence the Dirac delta measure in the definition of some quantities (see Appendix (B.43), and the fact that the feasible set is, potentially, set containing infinite rewards. Nevertheless, Theorem (.3] states that this algorithm is sample efficient. The proof of the theorem is provided in Appendix [B..3
should remarked that Algorithm ttakes in input also the true support of the visit distribution of the expert policy SP. in case S is finite, and all the possible sets Z that agree with SP.* a.e. based on the measure d=.*. in case S is infinite. Intuitively, this set (SP.* ) of (s, h) pairs represents
18

---

the domain in which x is defined. Indeed, since the expert in the true problem p never visits pairs (s', $ Su.s" its expert policy might reasonably be non well-defined there. When S is infinite, require all sets Z because otherwise we cannot know which are the sets Sp. 2 with zero measure, ie., in which the reward can induce optimal action different from the expert's one, since the overall contribution to the expected return is zero.
The proof of Theorem 3.3 is obtained by using Algorithm I of 62 at Line 1 of Algorithm In
Appendix B.4.3 we demonstrate an upper bound also we use Algorithm in 63
B.4 Missing Proofs
Before diving into the proofs, we recall some important properties of the feasible set and of the Linear MDPs that will be useful in the proofs. First, we provide an explicit form for the feasible set presented at Definition 3.1
Lemma B.3 (Lemma E.I in (3I).. Rp. satisfies:
the setting of Definition 3.1 if is finite, then the feasible set
R. fre A Y(s, h) e SP."", Vae A:
(h(,,d:pp))) (7(s.app))) d'
E
Notice that we have extended Lemma E.1 in 31 consider stochastic expert policies (the extension is trivial). We can easily extend it to problems with large/continuous S.
Lemma B.4 (Feasible Set Explicit). In the setting of Definition 3.1 satisfies:
then the feasible set Rp
R Ry -fre Di vh [H] 33 Spa d (8) A Vs 1343,VaEs 8,V
(hs,,':p.)) (.s.app.))
d'>a (1+)
Simply, Lemma B.4 improves on Lemma B.3 by allowing the reward enforce the "wrong" action (i.e., different from the expert's action) in subset with zero measure based on the visitation distribution.
Proof. The proof is completely analogous to that of Lemma E.1 in B1. We just need to observe that if set S has zero measure (and the set of rewards Ri contains bounded rewards), then it does not affect the expected return.
Another useful property that need is that the Q-function is always linear in the feature map for any policy in Linear MDPs. Proposition B.5 (Proposition 2.3 in 23 For a Linear MDP, for any policy æ, there exist weights [we] he[H] such that, for any (s, a, h) E S x A [H], have (7, a) (Ø(s, a), wT).
We can combine the results of Lemma and Proposition B.5 to obtain the following characterization of the feasible set in Linear MDPs
Lemma B.6. In the setting of Definition 3.1 the feusible set Rp satisfies:
{r Et 3m hhwwhheepn [M] hee
R
a, E S x A H rn(s,a) (d(s,a),
A vh E H1 = Sp :
(S) = 0 Vs S. e Ah(s):
(Ø(s a )) wh> max a). wn)
where On == Wh Is (0(s'' o'), wh+ wh+1)dpnn( for all h [H]. and (s = {a
AlT (a|s) (als) > 0}.
Proof. From 45). we know that in any MDP there exists an optimal policy. Therefore, thanks to
Proposition B.5 we know that the optimal Quuctiio Q* is linear in the feature map too. So, there
19

---

exist parameters (a such that, for any (s, h) E S x A x [H]] the optimal Q-function can be rewritten as (s, (0(s. a), wn). From the Bellman equation, we know that:
(s. as)
= < 0n) + (),
max(o(s' a'), wn (nn1)dpu(ss)
a'EAA
By rearranging this equation, and removing the dot product with ((8 a), we obtain that:
Wh - max a'); wh wh+1 (n++)dpp(ss))
a'EA
Now, this holds in any Linear MDP. If we desire to enforce the constraints in Lemma B.4 we simply have to impose the constraint on the optimal Q-function using parameters {wata outside some S. This concludes the proof.
useful to introduce the following definitions, First we define the set of parameters that induce Q-function compatible with r=
W W 7 := ww: [H] Rdd vh E [H], Spi (
(S) 0 V& V, (s):
(p(s,a")) wn> max (d(( a), wn>
a
Next, we define the set of parameters of the reward function obtained by using Q-functions parametrized by w E ==
+ P.st 00 [M] Rd 3(wnka E Wp On w/ max(dls' (6''s''''') aa), wh+ ddun (6)) a'EA
Irrespective of the transition model {Mr In and the feature map o. we see that it is always possible to construct a surjective map from Pp to Wp (the map in the definition of Op,r=) R. Thanks to these definitions, the feasible set can be rewritten as:
R Rp fr A ((0a) E pe, V(s, a, h) e S x A [M] (s.
We are now ready to provide the proofs of the various results of this section.
B.4.1 Proof of Proposition 3.1
Proposition 3.1. Let M be a Linear MDP without reward with finite state space, and let & be feature mapping. Let {2 heeh and [Pn]be[ be the sets of expert's and non-expert' features, defined for every h E [H] as:
_aa E (s)), T7 = ( IS ST
T : (0(s, SE ST AE (s)
where (s) fa ((r(( > for every S. Ifr none of the H pairs of sets (Ø Pr there exists a separating hyperplane, then Rp, = (r), with Y (s, = 07(s, a, h) x Ax [H] i.e., the feasible set with linear rewards in contains only the reward function that assigns zero reward everywhere.
Proof. From S we recall that two sets V1, 3/2 are separated by a hyperplane = {x/ (z/aTz = b} each lies in different closed halfspace associated with H, i.e. either:
a'yı & b & aJy,,
Vy V1, Vy2 V2.
or:
a a & b & a a
y1,
Vy V1. Vyz E V2.
By definition of W 5, for each stage h [H]] we are looking for vectors wn. Rd such that V(s, h) e - holds that:
(T & wfo(ssaF) va e A VaE A1A
20

---

In words, for each (s, E Sn.=", we are looking for non non-affine separating hyperplanes between features of expert and non-expert actions. However, since the hyperplane parameter w/. is common to all states E Sh then it must separate expert from non-expert actions at all states. This is equivalent to finding the separating hyperplanes to the sets 27 and 2, which contain all the points. Clearly, when the separating hyperplanes do not exist at all h e [H]. then the condition in Wp is satisfied by the zero vector alone. As a consequence, set O p contains only the zero vector, and so does R.
Remark B.2. By using the result of Lemma B. we can easily convert Proposition 3.1 into a more general result by considering the impossibility of separating any pair of sets constructed by varying at will some subsets with zero measure. We will not provide such result explicilly.
B.4.2 Proofs of Proposition 3.2 and Appendix B.2
In the PAC framework of Definition 3.2 we have not specified formally the inner distance d:
f(r,
E My well he[H] (f (.))
sup Σ
(ra(s,a)
where:
M :- max Vd. max 00ll2, max 100ll23/Vd, he[m]
he [M]
where {0,],. and 1h are the (unbounded) parameters of rewards r and As explained in [i], such normalization term allows us to work with unbounded reward functions. In practice, we are relaxing the Linear MDP assumption presented in Section 2 about the boundedness of the parameters 0 of the rewards to avoid the issue described in (38) and B1 We still assume that the feature mapping bounded. Observe that this relaxation does not affect the results we present, which would hold even if we considered bounded parameters 0. Indeed, visible in the proofs, the instances do not need to be constructed with unbounded 0.
Theorem 3.2 (Statistical Inefficiency). Let M u BT be a Linear IRL. instance with finite state space S and deterministic expert's 's policy, and let e, E, (0, 1). If an algorithm 2 is (e, (e,8)-PAC. then T ((S), where S = |S] is the cardinality of the state space.
Proof. We construct two problem instances that lie at finite Hausdorff distance, and show that, with less than calls the sampling oracle, we are not able to discriminate between the two instances.
Let S be the finite state space with cardinality S, A = (a1,a2), H = 1, do(s) = 1/S Vs E S. ((s a) Ia a.), and consider two deterministic expert's policies ( an Vs 8, and (s)) = an vs E Si(s), and n m(()) 022 for a certain 8 E S. The set of parameters compatible
with of is:
+ Paf 10 R
> 0),
since Q (s, an) Qa (s, a²) 1. 0 > 0- 0. Observe that, for TT. due to the presence of 3, we have:
r(s, a1) r(s, a2) = o(s,0100 > o(s 02)0 =
10 E R 0 = 0),
since imposes 0 & O, and the other states impose 0 > 0. Therefore, the Hausdorff distance between the two problems is:
030 max 0, sup 1
1
H(R=F, R.g) = sup
0 1.
020 max 0}
Obviously, need R(S) samples to spot, if it exists, state and thus distinguish between R_ and R.g.
Proposition B.I. Under the setting of Proposition 3.2 even under Assumption B. then algorithm is (c, PPAC only - = (SS).
Proof. The same proof of Proposition 3.2 works here.
21

---

In particular, we now show that Assumption B.1 does not help. The Hausdorff distance between the instances in the proof of Proposition 3.2 can be written as:
RF Rx
sup E 0, 30 =0=0 max 01 02) reil s=do(),am (r)(s,a) r2(
sup inf
1
sup E 0 a0 === max 1 013
sup inf
[0(s, a)0 - o(s, a)
well (-1,
I b 0) o(s', ,)002
sup
well -m do d. (0(s,a) ((s', +0
E
+ sup sup = 20 max (1, 01) 0==0 s-
inf
E
10 (0(s',))0 a,,, - 065', a(ss',))02)
sup well ((10)
E
(0(8, a) (s'' a)l + sup
E
(bs', a).
well d0
where s' is the state in the covering closest to state 8; while the first term be bounded, the assumption does not help us with the second term.
Proposition B.2. Under the setting of Proposition 3.2 under Assumption B.2 then number of samples e [M( :S [ S - is the A((2L) number of space S w.r.t. distance
SS [I) is sufficient to recover Th exactly in any (s, E 8, where
Proof. For any state 8 SP.=", by definition of covering N A S,
I. D), there always exist another
27.
state s' E (Z Il) such that Is - =| < 21. By Assumption B.2
we know that:
A 2
[l0(s, (r((,,T/60 (s)) - ((s'' " (s)))ll2 & L|s - s|
and since Th. (s') and thus xf is known, then the fact that A is finite guarantees us that ohe (s)) ) is equal to the action that minimizes the distance to Φ(s', f (s)). Notice that if, by contradiction, there were two actions a, a2 with a,(s,,)) o(s', 2 (s' ())) < & and [ a2)
A (6s', T (s'))lla & 2. then by triangle inequality and finiteness of A, we would have:
A < lø(s, 01) - Φ(s, a2)llz
[0s 01) - ((s', T (8)))l + (0(s, 02) 6(s' ( (
A
2 2
which is clearly a contradiction.
B.4.3 Proof of Theorem
The proof is based on deriving an upper bound to the Hausdorff distance between the true feasible set and estimate. To do so, first, using the notation of (3), us define the following quantities:
Pa(+(s,)) (Ø(s, a), pn(.))
Pa(-Is,0) == )(s a(s,
(s o0,
Pn(+(s,a) = o(s,a)
( P/ aft))
where 2(,,x)) the Dirac measure, and (5/, ag) represents the state-action pair visited at stage of exploration episode & E [7]. In words, P denotes the true transition model, IP denotes the least squares estimate computed by Algorithm and F represents a bridge between the two. As we will see, the core of the proof consists in upper bounding the term (PP, PP Vh+ (s, (s.a) all e [H]
22

---

and reachable (s, a) E S x A, for all the bounded linear functions V in class V, defined as:
V== V S x [M] - [-I1,+ V()
max o(, a,w, |w]2 < 2/1 2//va..
(2)
To achieve this goal, it will be useful apply triangle inequality and to bound the following two terms separately:
(PA P) Vi (s, & (Pa + (Pn - Va+
Lemma B.7 and Lemma B.8, which we now present, serve exactly this purpose.
Lemma B.7. For any value function V in the class for any (s,a,h) S A [H] it holds that:
( - Ph. Vn+1(s. min (0)
Proof. We have:
P -Pa) V)+1(8,a)= ( MV
(55h Pn a PA (1+1(ss)))
1 a(
(6 Pn
a(s,a) T
= A
O(ss AA,, 'An a. a
A
Σ
( MP V oft An
2
A,
Σ
( I/ Vn+1
-Iwh
Σ
Msh a 1 af)
B
T(
Σ ( ax) Vn+ (5h, a%)
Ms at Pr Vn 1s att))
wwA
= a) A Wh:
where at (1) we have defined vector wi Is Vn+ 1 (1+1(5)dd (s)ddu at (2) we have used the definition of Ag. and at (3) we have recognized that (s a T = Pr,, 1 att).
By taking the absolute value, we can write:
(PA - Ph+ a)
|0(s, a) TA7 Th
[ A5 |1 a) |,
| 12l12110s a) |l
where at (4) we have applied Cauchy-Schward 's inequality, at (5) we have bounded the quadratic form with the 2-norm and the largest eigenvector of the matrix, i.e.. | |@oall,; = ".,.,"""" wn & | 2. S
where a is the largest eigenvalue of matrix A,71 and then we have upper bounded a & 1, since is the smallest eigenvalue of invertible matrix Ab (see [2]); finally, at (6) we have used the fact that | (+) H, and so that ||,x]]2 IS Vn+1(s' Vi+a(s")duuaff & H (S)(l)) H.d.
23

---

The result follows by noticing that the quantity to bound cannot be larger than 2H.
Lemma B.8. Let 5 E (0, 1). For any value function V in the class V. for any (s,a,h) A [ with probability at least 1 6/2, it holds that:
( (Pr. - Vi+1(s. )
H 8 min { cH / d (1 + +1) + log (0) (1
for some constant c.
Proof. We can write:
(Pn - Ph) Vn+1(s, (1) = (6(s,
A) Σ 0ss at) Vi+z(sh+t)) Ph Va+ aB)
33
Σ
(s a Va+ (n+1(5h+t)) I' Vh+1 (5 amt
|/1, A, (o(s.a)/l..
2V. log(1 + + log 1
+ 87262 [6((() 87222(10(3,00) |,
8
4H2
2 log(1 + + 2d (1+Hcc)
d
HVd)
+ log :) + 87 18022 AF
c
(4)
4H2
2 log(1 + r) + 2d (1+ + log 1) + ssFra|o(s,0))
(5)
cH dloo(1 + +) + log g ( ArT
where at (1) we have applied
incquality, at (2) we have applied Lemma B.13 at (3) we have upper bounded No using Lemma [.12 at (4), similarly to [62], unlike [23]. we see that no union bound is needed (because there is no dependence on A), thus by choosing e = H d/r. /,, we get the passage. Passage (5) follows for some constant
The result follows by a union bound over e [H], and by noticing that the quantity to bound cannot be larger than 2/.
We are now ready to upper bound the Hausdorff distance using the two lemmas just presented. Recall that we work with unbounded rewards (parameters 0), and that the definition of inner distance d is provided in Equation (
Lemma B.9, With probability at least - 5/2, the Hausdorff distance between the true feasible set R E and its estimate R. returned by Algorithm can be upper bounded by:
H(R R) & (u;
where an = min ai)l 1, H1 for all (s, a,, h) SSxAL A X [H]. and 3 cH /dlog(1 T) + log( /8) for some absolute constant c >
Proof. Let us begin to bound the first branch of the Hausdorff distance.
sup inf d(r, = sup inf 1 sup Σ rER FER MrF well hE]Hi (s.0) (v)
E (m)(s,)) (x)
reR x PER
sup inf sup Σ R ba R Mp sell ke[ (s,a)
E
- (P.Vi
0 0: P, + Pn Ve
(s,
sup Σ rER F Mr well hell
sup
1
E
@M(s,a;p.r))
(s.a)
a;
24

---

sup
1
sup Σ
E (s.))_d) (v.)
[M(s,,;p.r)) PA
rER pi M nell he he|H|
Qh(s, P
sup 1
sup Σ reR pia M rell ha]H!]
(Ph-PPh)
(e.0)=
V (8,
(6.0)-dh (1)) ((Pn - Ph)
sup
max maxi 10 12/l2//1)
rER pia e he[M]
Σ
( a. R (iPh-PP)Vis (8,,
sup
ERR Pin R he[H]
(s,a)~dh (1))
sup sup Σ VEV xell [M]
1(p - PA) (n)t(aa)) (s,0)~d (.))
E
where at (1) we have simply applied the Bellman optimality equation twice w.r.t. the reward function, at (2) we have upper bounded the infimum over the second set of rewards R with the specific choice of reward 7 E R provided by Lemma B.11 at (3) we use the property of F de- scribed in Lemma B.I1. at (4) we bring term 1/ inside, and then we upper bound it by: 1 1/M, == 1/ max ( v d. max, |0x max, 12/l2//v & 1/ max(1, max, ||0n|l// d) i.e., by sim- ply removing one of the terms inside the maximum operator denominator. At (5) define K == max{1] 1, max, 10 hall///d; dj. and, since the value function is linear in the reward, we apply K directly to the reward. At (6) we realize that the possible optimal value functions that can be constructed in p using rewards in R., normalized by K are subset of the value functions in class V, i.e. of all the possible optimal value functions with parameters lw l22l222 & 2H vd. This is not trivial since we working with unbounded rewards r, and thus their parameters {0xhn can be any. The normalization by K permits this in the following manner. For any h E [H]] we have (ra(.-)) (,(:)),o,/ K> = () 0n/ max(1, 1, max 10, 10, ll////d). Therefore, if max |0 > Vd, then the normalization makes sure that max |10x~122 = vd, while if max |0x112 & vd, then the nor- malization is by and it has no effect. In this way, we see that value functions V (8,, p; x) can be created by a simple r' with parameters {0/}}, with 2-norms bounded by vd. This guaran- tees that, since by hypothesis of Linear MDPs 1((:-)]2 & 1, the value function never exceeds H, and that the norm of the Q-function parameters {w J. for any policy π can be bounded as: |[w]] ll & |/0n/ K + SS ( (s")dunss)) & Vd + H | (8) & vdl HVd & 2.11 V d (simi- larly to Lemma B. of (23). It should be remarked that class V is more general than the actual set of optimal value functions that can be obtained using Ry in p. since such rewards induce optimal
value functions for which the optimal action in SP. is always the expert's action/s π (s).
Notice that the same derivation can be carried out also for the other branch of the Hausdorff distance, ending up with the same expression. Therefore, the last line is an upper bound to the Hausdorff distance:
Hed HR R) & sup sup Σ VeV well he [M]
E (a.))
[(A, - P-)
(.))
sup
E
sup (Pr - V*)1
well
H
(3, (5 (1) Vev
Σ
(Pn - (s))
sup
E
sup VeV
well
he[m
(3,0) d
VVV
sup
E
sup Ve
(F, -P.--)) 10h Pr) (s+1(,a))
Tell H
(8.0) d.
(.)
H min c H dlog(1 + 7) + log o (((s,))la
sup
E
nell
he
(3.0) (. 2 (1:)
25

---

suu Σ
B (s (..)
min { c2 (o2Hyddogg dog((1 +r) + log
H
10(8 a) A), H}
8
sell ke]H]
sup
Σ
E
min (3110(s, a a)
selt He]H]
(s,a)=dR (v,)
(o.a)
sup
Σ
(f (..)) un(s,a)
zell ke[H]
(w:
where at (7) we have noticed that class V contains the cartesian product of H sets, one for each stage, and therefore the supremum can be brought inside the summation, at (8) we have applied triangle inequality, (9) we have applied Lemma B.7 and Lemma [B.8] and used some absolute constants C1 C2 > 0, and also the fact that for any numbers 2; y, w, 2, we have min y) + min(w, < min(r + w, y 2).
To conclude the proof of the main theorem, we simply have to observe that any RFE algorithm provides a bound to J (u':p)) p) for some u' similar to u. Depending on the RFE algorithm instantiated sub-routine, the sample complexity of Algorithm varies.
Theorem 3.3. Assume that Th (along with its support SP.* is known. Then, for any e, 6 E (0, 1), Algorithm 7 is Oe,A for IRL with number of episodes upper bounded by:
Hdd (d log 1 2)
T T T
Proof.
To get the result, we instantiate Algorithm of 62 RFE sub-routine. Simply, observe that
62 sets H so that f > B === c'H cc'H cHool + dHr) log H > B. By Lemma B.9 9
we know
that:
H(R R) x 4sup Σ
E (a.0) d d (1))
min {B11((8 a) a)) H}
welt
he[H]
Σ sup
E (.
|| (((8,)))),)))
well
for some absolute constant ei > It should remarked that the quantity in the last line is, modulo C1, the quantity that (62 bound in the proof of their Theorem using their algorithm. Specifically, by taking:
( Hdd (d log 3)
H
log log²! !)
and union bound over the two events that hold w.p. 5/2, and re-setting < Cıé, we get the result.
Notice that if we run Algorithm of (63 for exploration instead of Algorithm I of 62 we obtain:
Theorem B.10. If we use Algorithm of (03) at Line I of Algorithm D then for any 6, E (0, 1), such algorithm is (e, 8)C for IRI. with a number of episodes upper bounded by:
H
log 1
T T
2
8
Proof. By Lemma B.9 know that:
H(R R R. & 4J
4sup Σ
E (x.a)
min
he he|H|
(7.
26

---

+og for == cHHddolgl 1+ +) log(H/ H/) Now, let us define, similarly to Appendix A of [63].
the quantities v/, (s, = min a) A, H for all as S x A [H]. and 9 d'dH Log(dHo
for some absolute constant e' O. addition, set the number of exploration episodes to r c"d Ho 1og(dH55-<<")/e and notice that, for appropriate choices of d, holds that: 3 > c'dHyloggee [lg(ddT/ > B = cHty h dloog1 + 7) + log(1/6). This entails that 2 (s,0) a) 2 (s, a)) at all 8, a, h, and so:
HiR p. R R) & cJ (u':p)
cHJ (u' H:p)
d3 114 log dr
< H
C26,
where at (1) we have applied Lemma 3.2 of 663 (reported Lemma B.14 for simplicity) with some new constant > 0, and at (2) we have simply replaced with its value defined in Algorithm I of
63
The result follows by union bound between the two events that hold w.p. - 6/2 to get 1 - 6, and by noticing that 02 is constant, thus setting c26 provides the result.
L
Lemma B.11. Let R be the feasible set of policy x w.r.t. transition models p. and let R be its estimate constructed as in Algorithum using the true n. - Sp for sets 2) and some p. For any reward r RR,,7 , the reward f such that, for all (s, h) Ax [
an(s,a) = =n((s,)) [
pn p
s'ES
SES
belongs R. Moreover, observe that: us,,,, (, a; at all (s, a, h)) E S A [H]. In addition, any reward E R, it is possible to construct reward in analogous manner so that R, R, and such that (s,
(s, af f) at all (s, a) E S x Ax [H].
Proof. First, consider the case when S is finite. By rearranging the terms in the definition of f, we see that, for all (s, a, h) E S x A [H]:
an(s,a) Σ inl''ss V (5:: rn(s,a)
s'eS
s'88
which, by the Bellman optimality equation, entails that Q (s. (s
We recall that R. defined as:
R= = (fe R V(s, h) Sp A:EA:
(Ms
a'~xf((1))
while thanks to Lemma B.4 the feasible set R can be written
R = {r E R ((s,h) E S A: d(1))(1)))
0 > (%s..ap.))))
It is clear that, if Q a,p,r) = (t, for all (s, e Ax [M] then since E R we necessarily have R.
The proof of the opposite case is completely analogous.
In the case with infinite S. notice that both the feasible set Rp in Lemma B.4 and the definition of R. in Algorithm make use of the same sets 2. Thus, we simply make the choice reward with same Z and proceed like the finite case.
Lemma B.12 (Covering Number of Class V). Let V be defined in Equation ② and define distance dist in V as dist( V, V²) == supses (V(s) V'(s)). Then, the e-covering number (N V. dist)) of
27

---

set V with distance dist can be bounded as:
log V,(et),dsss)) & dlog (1 4Hl
e
Proof.
The proof follows that of Lemma D.6 23] but simpler because of the different form of V.
For any V1, V/2 V parametrized by W1, w2, we write: dist(Vi, V2)
sup
max a), w1) - anA
())
sES
aEA
me
Φ( ((5,a) TWT -w2)
(s,0)ESxA A
o (wi (2m
stip
W2
where at (1) we have used the common bound that the absolute difference of maxima is upper bounded by the maximum of the absolute difference of the functions, (2) have used the fact that the feature map is always bounded by in 2-norm, and at (3) we have recognized the dual norm of the 2-norm, i.c., itself.
we construct an e-cover W == {w IR ||ll2 & 2 w.r.t the 2-norm, we get a covering number bounded by [W(e; W, |12)] < (1+ 4H)d/e) Clearly, this value upper bounds the covering number of class V and the result follows.
Lemma B.13 (Lemma D.4 of (23)) Let (sk be stochastic process on state space S with 1oc
corresponding filtration (Fx) and |0xl|2 & 1. Let A, k-o Let {or be an Rd -aluee stochastic process where Og FR-1- E ORO Then, for any ô > O, with probability at least 8, for all 0, and any V E V that supses [V(s)] & H, have:
Σ ou
< 4H2
log(1 + + log
No
+ 8
2
5
A,
where No is the e-covering number of with respect to the distance dist V') == supses (V(s) V.(s)..
Lemma B.14 (Lemma of 63
With probubility 5-/2 for the function u' defined as u/, (s, a)
min (0( o))l,,,, H H3. with B' == dogHH/log(dEl dHo--i c-)), we have:
d3 H log
(*( & ov
for some absolute constant c
C Additional Insights on Compatibility
In this appendix, we collect and describe additional insights the notion of rewards compatibility introduced in Section The appendix is organized in the following manner: Appendix C.I provides visual explanation to the notion of rewards compatibility, in Appendix C.2 we analyse multiplicative alternative to the definition of rewards compatibility, and Appendix C.3 discusses the conditions under which a learned reward can used for "forward" RL, by comparing rewards with small (non)compatibility with rewards learned in previous works.
C.1 Visual Explanation for Rewards Compatibility
In this appendix, we aim to provide visual intuition to the notion of rewards compatibility. For this reason, the reader should keep in mind Figure 3
28

---

do
P
dP.7
d
dP
Figure 3: this figure, the point at the center represents the initial state s0 = do of the environment M, and each ray starting from it represents the occupancy measure dp of some policy æ. The figure aims to provide the intuition that policies with rays close to each other induce similar visit distributions (e.g.. both point towards the same direction in some grid-world), and policies with rays far away from each other point toward very different directions (i.e., they have different occupancy measures). The red area in the right denotes the set of directions (occupancy measures d for some T) that are close in lla norm the direction of the expert d=
As explained in Section 4 even in the limit of infinite samples, i.e., even if we know M = (S, A. H, do J {-8) exactly, and even if we assume that the expert is exactly optimal, i.e., )*) J= pp): not have idea of how other policies perform. Expert demonstrations only provide information about the performance of single policy, T" w.r.t. to the reference J (r":: :) under the unknown r i.c., demonstrations say that =5 in " performs as good as J* (r(":p)) :). But what about other policies? Demonstrations provide no information.
(where و is the true reward optimized by the expert), then we still do
To this, consider Figure 3 in which each line exemplifies the visitation distribution induced by some policy π E II, and the point in the middle represents the starting state 80 = do- Intuitively, observing d 5 along with knowing that J (r is good (i.e., because of expert demonstrations), does not tell us anything about the distribution d/ induced by some other policy क potentially arbitrarily different from d=.== Indeed, it might be the case that (=( :p) is acceptable, or that it is as good J=² " (y.E.p), that it is very bad. We cannot know from demonstrations only.
For this reason, if we consider the set of rewards with O-(non) compatiiiii i.e., the feasible reward set, we notice that it contains the rewards r that make iT optimal J (r:p)
(r; but also the rewards r' that make т nearly optimal (T(:: :)) a (*(''pp) p), and also the rewards r" that make (+(""))). Indeed, as long as both r, r,r', r make the direction pointed by d=.=" in Figure good direction, then they are in accordance with the constraint imposed by the demonstrations. The additional Degrees of Freedom (DoF) provided by policies beyond F (e.g., ..... permit the ill- ill-posedness of IRL.
a very bad-performing policy J (=(r":
We said that expert demonstrations provide information just about the performance of a single policy, FF. However, be precise, in the context of IRL, this is not correct. Indeed, differently from the mere learning from demonstrations setting, in which we just assume that = is a very good-performing policy, in IRL assume that the underlying problem is MDP, i.e., that the expert agent is optimizing a reward function r 10) This additional structure (i.e., that the underlying environment is indeed an MDP), makes sure that the performances of various directions dP.7 in Figure 3 are measured through dot product with a fixed reward function r, i.e.:
(r((p))
Σ (dh rn).
he[m]
For this reason, we have the guarantee that the directions in the red area surrounding d= are almost E
as good as d=.== Indeed, for all policies π such that Σxe[Hj ddh." dp.
1| < e, i.c., for all policies
Wheee this assumption does not hold, we incur in model misspecification
55 51
29

---

e-close to x= in 1-norm, we can write:
| (r - J (r
Σ he[
P.
d=
do. 4/
11 E
4
hE H
In other words, policies and n7 have similar performances.
However, it should be remarked that, since we aim to recover the rewards explaining the expert's preferences, then we are guaranteed that policies close in 1-norm perform similarly under any reward function (by definition of I-norm), and so we do not risk to incur in the error of representing d=. and direction dp-" inside the red of Figure with very different performances.
C.2 A Multiplicative Compatibility
In Section we have defined an additive notion of (non) compatibbil,, based on the difference of performance between R and r (the optimal policy). Here, we analyze multiplicative notion of (non)compatibility, based on the ratio of the performances 11
We make the following observation. Any reward 9t induces, in the considered environment p, an ordering in the space of policies II, based on the performance J (r:p) p) of each policy π E II. is easy to notice that for any scaling and translation parameters
R= R, the reward constructed as (:) ) = ar(..-) + 8 induces the same ordering as r in the space of policies 12
For this reason, it seems desirable to use notion of (non)compatibilityy such that rewards and r) = ar(:.)) -) + 3 for some a, B, suffer from the same (non)compatibilityy w.r.t. some expert policy x = However, observe that, for the notion of compatibility C in Definition 4.1 for any e R:
we have that,
Cp. C (r)
VHER, R,
p (ar) at 5 (r) * (r) Va E R>o-
Simply put, for the additive notion of (non)compatibility C, the scale (ai) of a reward matters, and rescaling the reward modifies the (non) conppaatatibil
To solve this issue, one might introduce a multiplicative notion of compatibility F (defined only for non-negative rewards and setting F F
= (r) when the denominator is O):
J (r:p)
F F
(+(rpp)
Clearly, the larger = (r), the closer is the performance of π. to the optimal performance. Observe that, for this definition, we have:
Fn Fr)
Va R Vß R,
F = (3) * Fr)
i.e., this definition does not care about the scaling a of the reward, but it is sensitive to the actual position of that reward.
Therefore, both č and F suffer from some "rescaling" issues. Is it possible to devise notion of compatibility, i.e., measure of suboptimality, for policy, that is independent of both the scale and position 8? Formally, we are looking for function (notion of distance) f R R R3o such that, for any J2 RR:
s(aJ + 8, aJ2 3) ((J,,
for all Rso. 3 R. Unfortunately, this is not possible, since it is easy to show that all the functions ff of this kind are the following type:
K
if > J2 if J2 if J1 J2
J2 3()..
Ku
K_
11 F.,.. see Theorem 7.2.7 in 45
which is inspired by Indeed, simply observe that, for any II: J (T':p)) J (ar 8:p) a.= +
30

---

for some reals K+, Ku. K_ In words, any function f that satisfies Equation (3) is able to express just an ordering between inputs J1 and J2, but not an actual measure of sub-optimaliy/compaibinn
We conclude by stating that we prefer to use C instead of F for the following reasons:
First, most RL literature prefers the additive notion of suboptimality towards the multiplica-
live one.
The additive notion of suboptimality is simpler to analyze w.r.t the multiplicative one.
C.3 When can a learned reward be used for "forward" RL?
In this appendix, we exploit the intuition developed in Appendix[C.) to discuss under which conditions we can exploit demonstrations alone to recover a single reward that can be used for "forward" RL, i.e. to recover a single reward r for which we have the guarantee that any e-optimal policy я to r in the true environment has similar performance in the same environment under the true reward e that is, policy π an f((e) ooptimal policy to y p. for some function f.
Applications of IRL range from Apprenticeship Learning (AL), to reward design, to interpretability of expert's preferences. Concerning AL, common to "use" the reward r learned through IRL to optimize our learning agent. But what properties should satisfy in order to obtain performance guarantees on our learning agent w.r.t. the true (unknown) ,. We now list and analyze various plausible requirements.
First, we might ask that, being F optimal w.r.t F then T. E arg max, J= i.e., that the expert policy π is optimal under the learned reward However, this requirement is not satisfactory for the following reason. Reward might induce more than one optimal policy (e.g., it might induce both म, _h optimal), and optimal policies other than n E (e-g.. a) are not guaranteed to perform well under e (actually, मे can be any policy in IT). Clearly, this not satisfactory. Observe that there are rewards in the feasible set Ry for which multiple policies are optimal (thus, not all the rewards in the feasible set are satisfactory).
We might additionally ask that B is the unique optimal policy of reward (similarly to what happens in entropy-regularized MDPs (70) [5).. However, this is not satisfactory for the following reason. In practice, it is really difficult (almost impossible) to compute the optimal policy of a given reward. Thus, what is usually done RL, is to settle for an c-optimal policy. Since any policy can have for such policy w.r.t. F.
be e-optimal under reward r, then guarantee
What if we ask that B is at least e-optimal under (i.e., the requirement provided by ((mon))coppatible rewards)? Well, this not satisfactory because optimal policies can be any. and because there might be other e-optimal policies that can perform arbitrarily bad under E
All the three requirements described above considered reward r provides a policy with satisfactory performance w.r.t. the true F However, as mentioned in Section 4 and in Appendix [.I expert demonstrations do not provide any information about the performance of policies other than π under F.
do not provide guarantees that optimizing the
Remark C.1. If we want to be sure that an c-optimal policy n for the learned reward r in is if f(c)-optimal for F in p (for some function f), then, clearly, need that all the (at least) e-optimal policies under the learned r have visitation distribution close to that of B in 1-norm (see Appendix C.7.
We stress that many IRL algorithms for AL., like max-margin (2), learn a reward function just as mere mathematical tool to compute policy π which is close in I-norm ||d -d= || to -.=
A remark about works on the feasible set. If we look at recent works about the feasible set 38 31 68 it might seem that these works are able to provide guarantees between r, r under distance dall (see Section 3.1 of (68)). defined
Jull (r,r = sup (F() - B)
Tell
31

---

If (r.r" is small, then the performance of any policy in not just optimal policy or e-optimal policy, is similar also under r". In other words, if we use/optimize reward r, then we have the guarantee that the performance of the retrieved policy under r is more or less the same as its performance in r. Therefore, clearly, rewards r with small distance to r w.r. dall can be used for "forward" RI. However, we have the following result:
(S, H, do p) be a known MDP without reward, and let Th be a known expert's 's policy. Let r the true unknown reward optimized by the expert construct x F. Then, there does not exist a learning algorithm that receives in input the pair (M, x BB) and outputs a single reward such that d (r, & E w.p. 1-
Proposition C.1. Let = =
Proof. The proof is trivial. Indeed, since the feasible set Rp. contains an infinite amount of reward functions along with p and the learning algorithm cannot discriminate r inside R, then the best it can do is to output an arbitrary reward function r E Rp.x.. However, since R R. contains, for any reward r Rp , at least another reward r' E R such that (r,
cs finite and equal to some positive constant > 0 L then we can simply construct the problem instance with r := r'
to make the learning algorithm not able to output rewards that can be used for forward learning. O
Nevertheless,
38 31
By looking at we realize that this is clearly a contradiction. What is the right interpretation?
68
seem to provide sample efficient algorithms w.r.t. dall 14
Proposition C.I
The trick is that the algorithms proposed in works [68
are not able to output single reward r which is close r w.r.t. dall for any possible reward E = (V, A) parametrized 15 by some value and advantage functions V. A. they are able output reward such that d r (V. A)) is small. In other words, it is like these works assume to know the V, A parametrization of the true reward E Simply put, these works are able output reward that can be used for "forward" RI. just under such assumption. Otherwise those algorithms do not provide such guarantee.
38
31
Conclusions. To up, conclude that, in general, an arbitrary reward function with small (non)compatibility can not be used for "forward" learning (see Proposition C.T). because we cannot know given demonstrations alone whether the performances assigned by such reward to policies other than the expert policy are meaningful. In addition, for the same reason, we realize that also an arbitrary reward with zero (non)compatibility, i.e., arbitrary reward in the feasible set, can not be used for "forward" learning.
C.4 Comparing the (non)aoomiii of various rewards
In Section 4 we said that rewards with smaller values of C Cg.x5(r) are more compatible with n E in M= = (S, A, H, do, p). However, one might provide the following "counter-example"
Example C.1 (Question by Reviewer KyLX), Let r', ,2 be two rewards such that ri,ss, a) (s, a) for all (s, a, h) E S x [H]. Then, clearly, (x22 2Cp,x=(r)) Therefore, based on Section 4 we say that reward > is more compatible than r² w.r.t _ in M. However, since x² is just r' re-scaled by a constant, the two MDPs M u {r") and M u {r²] should be "equivalent", thus, r¹ and x2 should be, intuitively, equally compatible with F.
However, Example C.I misleads the correct interpretation of the notion of reward function in MDPs, and in particular about the scale of the rewards. Let us explain better our point.
The MDP is a model, i.e., a simplified representation of reality. which is commonly applied to different kinds of real-world scenarios: (i) problems in which the agent (leamer in RL or expert in IRL) actually receives some kind of scalar feedback from the environment, which can he modelled as reward function; (ii) problems in which the agent does not receive feedback from the environment,
This immediate from the considerations in Appendix C.1
"A "Actually, [38 31 use different notions of distance, like dzg (r, == Ir 1r-rrllle. r'lle. However, we can write |r - 1' 2 ||r - r' ('Ih/((HH)) and by dual norms we have that dall (r,r') supren
r')l &
supa, 7 <n Kd, Kd,r-r") -rr-rr>- I ||r (rr-rlll. 11. Therefore, the guarantees of [8 31 can be converted too dall guarantees too.
Whiile (68] makes this parametrization explicit, [38 31 keep the parametrization implicit, but everything is analogous.
32

---

but its objective, i.e., its structure of preferences among state-action trajectories (which trajectories are better than others), satisfies some axioms that permit to represent it through a scalar reward [ (this is referred to as the Reward Hypothesis in literature (58)
There enormous difference between scenario (i) and scenario (ii). In (i) the notion of c-optimal policy is well-defined for any fixed e > 0, because the reward function is given and, thus, fixed. Instead, in (ii), the notion of reward function is a mere mathematical artifact used to represent preferences among trajectories, whose existence is guaranteed by a set of assumptions/axiom
As Example C.I shows, positive affine transformations of the reward do not affect the structure of preferences represented (see [22 or Section 16.2 of [50] or (3)). Therefore, in (ii), the notion of e-optimal policy is not well-defined, because rescaling reward function r kr changes the suboptimality of some policy т from to ke. In other words, for fixed > 0, any policy can be made e-optimal by simply rescaling a reward r to for some small enough A >
52 58
In IRI., this issue is even more influential because, although we are setting (1), we have no idea on the scale of the reward function. For this reason, our solution is attach any reward notion of compatibility C(r) which implicitly contains information about the scale of the reward Compatibilities of different rewards (c.g., and r² in Example cannot be compared unless the rewards have the same scale (e.g., r and 2² have different scales, thus their compatibilities shall not be compared).
It should be observed that in Appendix C.2 we discuss notion of compatibility independent of the scale of the reward. However, we show that it suffers from major drawbacks that make the notion of compatibility introduced in the main paper (Definition 4.1 more suitable for the IRL problem.
In conclusion, settle Example C.I rewards y1 and y² should not have the same compatibility, because they have different scales, and the notion of compatibility (i.e., suboptimality) is strictly connected to the scale of the reward. To carry out fair comparison of compatibilities, one should rescale the compatibility of each reward based on the scale of the reward.
D Missing Proofs and Additional Results for Section 5
This appendix is organized as follows. First, report the full pseudo-code of CATY-IRL. Then, provide the proof of Theorem 5.T Appendix D.2
D.1 Algorithm
In this section, provide the extended version of CATY-IRL containing the explicit conditions under which we shall instantiate one BPI/RFE algorithm instead of another.
Algorithm 2: CATY-IRL- exploration
Data: Failure probability 5 > 0, target accuracy c >> 0, expert demonstrations DE set of rewards classify R, problem structure (tabular, linear rewards, Linear MDP) (tabular, linear rewards) then is small constan! then
i
if [
- 0
for r R do
5
- D u BPI BPLLExploratioo((.f/2...
/* Algorithm BPI-UCBVI
37
end
else
- RFE_ RFE__Exlorattio((. c/22)
/* Algorithm RF-Express
37
end
10 else
11
D RFE, AFF_Exxlora
Algorithm RFLin
622
end
13 Return D
33

---

Algorithm 3: CATY-IRL- classification
Data: Failure probability > O, target accuracy > O, expert demonstrations DE classification threshold A E IR, reward to classify R, problem structure (tabular, linear rewards,
Linear MDP). dataset
// Estimate the expert's performance J (r):
tabular then
2 - empirical estimate of dp." from D
(F) Σn (dk. rn>
else
E empirical estimate of o from DE [F( - Σn rn)
end
// Estimate the optimal performance (+)::
if E (tabular, linear rewards) then
if [ a small constant then
10
J (r) - BPL PPanninnnn
/* Algorithm BPI-UCBVI [37
else
13
J (r) RFE_ Pla_ninan
/* Algorithm RF-Express
37
14
15
end
16 else
17
(*( - RFE, Planning D,r)
Algorithm RFLin 662
end
// Classify the reward:
C(r) - J (r)
21 class - True C(r) < else False
return class
D.2 Proof of Theorem 5.1
Notice that, according to Definition 4.3 an algorithm is (c. P)-A for IRL if computes an estimate e-close the true (non)compatibility w.h.p.. Such definition does depend on the specific strategy adopted by the algorithm to actually classify the input reward using the computed estimate of (non)compatiiilitt.
Before diving into the proof of Theorem 5.1 we make the following considerations.
In the common tabular MDPs setting without additional structure, we know that the expected utility J= (ripp) policy ı under reward r environment with dynamics p can computed as:
Js (r:p)
Σ (rn,
be he[m]
where d'-"" is the occupancy measure of policy и in It should be remarked that both ra and d= have SA components for all e [H].
In tabular MDPs with linear reward functions and in Linear MDPs, the reward function is linear in some feature map o, i.e.:
r((::)) ( vh [H],
where (0(s a))2 & for all (s, a) S x A and max, 10,12 & vd. Using this decomposition, we rewrite the expected utility J (r:p)
J (r:pp)
Σ
(rh. (.
34

---

Σ (0
din))
hE[m
Σ
0
E
((),a)
(s.a)
df
Σ
0%
where have defined the feature expectations (+/R.") [=]H] as 4% (s.a))=ff" ((s, a). Observe that vector v.h. has d components instead of the S components of each di vector.
Since in our setting the IRL algorithm receives input the reward function (or its parameter 0 Rd), to estimate the expected utility J (r;;)) we must estimate the visit distributions [d," Ja or the feature expectations (vip.") hn- However, because of the different dimensionalities of such quantities (SA A versus d), the estimates might require different amounts of samples.
Theorem 5.1 (Sample Complexity of CATY-IRL). Let e, E (0, 1). Then CATY-IRL is O),A) for IRL with a sample complexity upper bounded by:
H
HAAA
log 1)
5))
HASA
N log 1 1))
Tabular MDPs:
T
T Ö
2
Had
1)
HASA
11 3))
Tabular MDPs with linear rewards:
log
8)
2
N log
Linear MDPs:
11'd
log
7)
1
T & δ
11'd
d log log 1))
where N = 0 if [ = ((1), and N = S otherwise.
Proof. To prove the theorem, aim to find bound to the number of samples - such that the estimate [r(rr = J= (r:p) e/2-correct with probability at least - 8/2. Next, similarly, we aim to bound 7 so that (*(r) = J (r:pp) is e/2-correct with probability at least 1 - 6/2. Then, the conclusion follows after performing union bound and observing that, for any R:
(p) -(()
( (r:p) - -= (r:p)) (
(*(rp) - + (r:))
2 +
Estimating (r) J= (r:p)
To estimate J= (r:p), CATY-IRL simply computes the empirical estimate of {dh." in case of tabular MDPs, and the empirical estimate of (u } in case of tabular MDPs with linear rewards and Linear MDPs. Notice that by empirical estimates mean:
Σ
10
ot a}
(s,
Σ 51
1[s, = 5)
and:
Σ
1/
-
Vh [H].
Concerning the estimate of the visit distribution 2 we can use the result of Lemma 6 in |53 (we are working with bounded rewards), to obtain that:
SAH3 log
8SAH à
dh 111 < <\
2
2
l
35

---

Solving w.r.t 7 we get the bound on T".
In completely analogous manner, can bound the feature expectations as:
d log
8dH
Σ
I
2T F
2
[e[
Again, solving w.r.t. - we get the bound on 7
Estimating (+)r)= J (r:
Let us begin with the case in which R large. As explained for instance in Definition 4 of [66], both algorithms RF-Express [37 and RFLin [62] satisfy the uniform policy evaluation property, i.e. they
guarantee that, for any c, 8 (0, 1), after having explored for r & Ö H² (5 log (og!)) in case of
RF-Express [37 and T < ( Had (d+ log ))) for the algorithm in 62 (we omit linear terms in 1/c), they compute an estimate p = of the true transition model such that:
log
P( sup FEBt
(T::)) < > 1 -
Clearly, if such property holds, then by computing the performance of the policy म outputted by the RFE algorithm we are able to obtain an e/2-correct estimate of J T6
Concerning the case in which [R] is finite small constant, for tabular and tabular with linear rewards MDPs, we can simply use algorithm BPI-UCBVI of [37] as sub-routine, and run it as many times as there are rewards in R. When [R] is small constant, we can proceed with union bound over R:
TP
sup FEll
J (r:
J (r: = 21
Σ
P
sup
J (r: J (r: P)
1 |
PER
nell
This allows formally distinguish between small and large |R| based the following inequality:
1
|R|
S + log
log
S log [R].
8 5
E Missing Proofs and Additional Results for Section 6.1
This appendix is organized as follows. First, in Appendix E. we introduce two problems that share similarities with RFE and IRL, and we characterize the main differences among them. In addition. we enunciate a lower bound to the sample complexity that is common to some of these 4 problems. we provide the missing proofs.
Next, Appendix E.2
E.1 Four Problems
The 4 problems that we consider here are Reward-Free Exploration (RFE), Inverse Reinforcement Learning (IRL), Matching Performance (MP), and Imitation Learning from Demonstrations alone (ILfO). MP represents novel generalization of RFE, while ILfO, introduced in 34] represents an exemplification of MP. Before enunciating the minimax lower bound, it is important to formally define each of these problems, as well as what we mean by learning in each problem.
E.1.1 Definition of the Problems
In all the 4 problems, the learner is placed into an unknown MDP without reward M (S, A, H, do p). i.c., an environment whose dynamics (da, p) is unknown to the learner. For simplic- ity, w.l.o.g.. we assume that there single initial state 8g := dg- In each problem, the learner can explore the environment at will to collect samples about the dynamics p, whose knowledge improves the performance of the agent at solving the task. However, at exploration phase, the learner does not
16 Actuaalyy for Linear MDPs, instead of evaluating the policy returned by Algorithm 2 of (22) we can simply consider the optimistic estimate of the V-function computed by such algorithm, which has the property of being c-close the true optimal V -function.
36

---

know which is the specific task it has to solve. It just knows that the specific task belongs to a given set of tasks I (e.g., set of reward functions). The agent can use the knowledge of I engage in a more efficient task-driven exploration. For any e, (0, 1), the goal of the agent is to being able to ouputting, for any task in I a quantity (e-g. a policy) that solves that specific task in an e-correct manner with probability at least 1 6. The ultimate goal of exploration is to collect the least number of samples that permits (c, corrreetesss for all the tasks in S.
Now, let us see what the quantities I and represent in each of the 4 problems. In Table | we
provide a sum up of the various definitions.
Reward-Free Exploration (RFE). In RFE, the learner receives a set of reward functions I R S Di in input, and the goal is to exploit the information about collected at exploration phase to output, for any reward E R, an e-optimal policy o म, w.p. 6. When I {(r} is singleton, the RFE problem is commonly termed the BPI problem. In symbols, any RFE algorithm must guarantee that:
P sup - (r:p) < rER
> 1 - 8,
where n is the estimate of the algorithm for reward r.
Inverse Reinforcement Learning (IRL). In IRI., the learner receives in input an occupancy measure (d ]he[m]] and a set of reward functions R R: (dr.** R),, but does not know which specific reward it will have to classify. Under the assumption that the occupancy measure d=.= is known [8 the problem reduces to exploiting the information about p collected at exploration phase to output, for any reward r R. an e-correct estimate [(r of the optimal utility J (r) w.p. 1 1- 5. In symbols, under these conditions, any IRL algorithm must guarantee that:
sup
(+:::) - J(r) < > 5, PER
where ((r is the estimate of the algorithm for reward r.
Matching Performance (MP). In MP, the learner receives in input a set of reward functions R S M and measure of performance for each of them J
R: I (J, R). For any E R. the utility J(r) represents performance measure for which we aim to find the policy that achieves closest performance. Thus, in MP, the goal is to exploit the information about p collected at exploration phase to output, for any reward r E R. a policy
क. such that, if we denote the policy with performance closest to (r) by 7. E arg min, (r) - ](r)), then the utility of policy म, is e-close to the utility of policy म, w.p. 1 - 8. In symbols, any MP algorithm must guarantee that:
P sup (r:pp - (r:p) < <) > 1-6,
rR
where म, E arg min, (r) [(r),, and क, the estimate of the algorithm for reward
Imitation Learning from Demonstrations alone (ILIO). In ILfO, the learner receives in input set of state-only reward functions R Di and state-only occupancy measure {dl he[ : I (d, R). Under the assumption that does not leak any information about the true transition model p. the goal is to exploit the information about p collected at exploration phase to output, for any reward R, policy क, such that, if we denote the policy with performance closest to J(r) == Enejar (rh, dn
by म, E arg min, (r²(r) - [(r),, then the utility of policy म. is c-close to the utility of policy ,, w.p. 6. Simply put, ILfO, as defined in this manner, exemplifies the MP setting by providing functional form to J R - IR as inner product between certain state-only occupancy measure and the input reward. should be remarked that the assumption made for ILfO is mild, because is
17 Actuallyy, as explained in Section the knowledge of - at exploration phase is useless. The visit measure might be provided after the exploration along with the true reward to classify.
The assumption that d= is known is useful to reduce the estimation problem of the (non)compatibiility of a reward (r) == (r:p) - ==" (r:p) to the problem of estimating the optimal utility J (r; p) only. Indeed, if dp. is known, then, for any reward r. the utility J (r: p) is known.
37

---

BPI
IRL
MP
1LfO
Set of Tasks I
(dv."". .R)
(J,R)
(d. R.
Assumptions Output
de known
J can be non-realisable
state-only, a no info
j
f
(8(::) (x:p)) J (r:p)
(r:p) = Table Summary of the problems.
(R(r:p) = In nn.
satisfied by the setting in which the expert and the learner have the same state space but different action spaces (or different dynamics). Indeed, in such case, the visit distribution of the expert would not leak any information about p. In symbols, any ILfO algorithm must guarantee that:
sup J (r:p) (r: & 211 FR
where 7. arg ming (r* [r) and J(r) = (ne dr), and म. is the estimate of the algorithm for reward r.
E.1.2 Lower Bound
We now present a minimax lower bound rate that is common to RFE, IRL, and MP. We report here the lower bounds presented in Section 6.1
Theorem 6.1 (IRL Classification Lower Bound). Let A be an (e, P algorithm for the IRL classification in labular MDPs. Let t be the number of exploration episodes. Then, there exists an IRL classification instance such that:
SA 2
H (s log 1og 1)
Rf| > 1: 1:
log
iR T 00
Proof. The proof is similar to that of 38 We split the proof two parts, by considering two classes of difficult problem instances in Lemma H.2 and Lemma H.3 Next, combine the bounds through max(a, b} > (a + 2)/2 for all b O. For the proof, we will assume that the expert visit distribution is known. The obtained bound represents lower bound the more general setting in which it is unknown.
Theorem E.1 (RFE- Refined Lower Bound), Let 2 be an (e, 8)-PAC algorithm for RFE in tabular MDPs. Let T be the number of exploration episodes. Then, there exists an RFE instance such that:
SAA S S 10g
10)
T T
2
Proof. The proof of this result is analogous to that of Theorem 6. and it employs Lemma E.2 and
Lemma
Some observations are in order. First, since MP is more general setting than RFE, then this lower bound is lower bound for MP too. However, this is not guaranteed for ILfO. We observe that, while for RFE and IRL the bound is tight, for MP we cannor say so because we do not have the upper bound. Notice that, in case the expert state-only distribution d was unknown at exploration phase, and revealed afterwards, then the lower bound of Theorem 6. for ILfO too, because might posteriori reveal the state-only distribution d of the optimal policy, and thus, in such manner, ILfO would be reduced to RFE.
E.2
Missing proofs
Lemma E.2. Let IRL and RFE be the learning problems defined as in Appendix E.1 Then, for each problem, any (e, 8PCA algorithm must collect at least the following number of exploration episodes:
3
Ω
log
2
38

---

Proof. Observe that the proof for RFE is present in [2] Thus, we have to prove just the result for IRL. For doing so, we will use both the results of [2 and 38 Notice that for the sake of this proof we consider R (r). that will reduce our problem to simple RI as, in order to compute the function (,,r=()) (r), we just need compute J (r:p), being J (rip) known from the availability of d'. and r.
action Our
A
Sor
action n (sw)
action of aw
S rroot
$1
82
+
$3
84
(h a) =0
8h
$8
(h a) 1( 17 d+1)
Figure 4: Hard instances.
Instances Description The hard instances considered are exactly the same [12] and are reported in Figure 4 for simplicity. The only difference is the presence of state sg, to which the expert's policy - brings, which absorbing. Such state needed to make the knowledge of the expert's 's visit distribution d=. useless at inferring information about the transition model in other parts of the state-action space. Based [12], we describe such hard instances. Similarly to [12], we assume that > 7, A > 2, and there exists an integer d such that 5 = 4 + (Ad - 1)/(A - 1), and we assume that > 3d. Note that [2] show how relax the assumption on the existence of d.
There are the initial state sw, from which the agent starts, and states 8g. Sb, respectively, the "good" and "bad" states which are absorbing. Moreover, there is state sg, which is reached by the expert, and is absorbing. The remaining 5 4 states are arranged in a full A-ary tree of depth root Stoot- We denote by И
with
- a certain integer parameter, and by := {81, 82, 82, .., ,,, sr.) the set leaves of the tree. We define : (1 + d, ...... H + d} x L x A. For any E I, we define and MDP M, as follows. In any state of the tree, i.e., in states S' S (Sw 8g: 8b, s the transitions are deterministic, and the a-th action of a state brings to the a-th child of that node.
The transitions from Sw are given by
( Sw: a) = laa = aw h & H) and (S Sww, ( a) == - a).
39

---

In other words, action de allows the agent to remain in the initial state up to stage H. After stage H, the agent is forced to leave 8w and to traverse the tree down to the leaves. Action ag = of (8w) the only action that brings state sg, which is absorbing. The transitions from any leaf s C given, as in [12). by:
Ph (h S1
(n= e0 ( S1,a) a) and (s(ss]s,, = (n e* .a*) (h, 8 a), (4)
where ((,,, (h, 8t, a) = 1[(h, 31, a) (h* Sp* a*)) c', for some E [0, 1/2]. For this reason, there exists a (single) leaf e* where the agent can choose an action a* at stage h to increase its probability of arriving to the good state Sg. which provides higher reward. We define states 5 and sy to be absorbing, i.e., they satisfy pa (56188, a) = Pa Pa( ( Sg. a) = for any action a. The reward function is state-only and is defined
Va A, on( 1|s= 5 sg.
H + 1
so that even though the agent decides to stay at &w until stage H, does not lose any reward. Observe that state gæ does not provide any reward, so that estimate the (non)compatibiltty any algorithm must provide a good estimate the optimal performance.
Finally, we define reference MDP Mo which is MDP of the above type but for which (h, 83, a) = 0 for all s;,a. For certain é' and H to choose, we define the class M to be the set M := (Mo} u (M.).eT-
Distance between problems We will prove the lower bound for instance Mo- Observe that, in Mo. the optimal utility is:
J 2 - d).
because there is no triple with additional bias towards $g. Instead, for any other M, e M, the optimal utility is:
J -H (c)
Therefore, if we choose é' = 26/(H H -d), d), we have that, for any 8 E I:
| J 2e
Thus, in particular, for any estimate J E I we necessarily have |_ - J E - |, J > and vice versa, i.e., we cannot provide an estimate J that is e-close to both J and J,
Identifying the underlying problem Following (38, let consider generic (e, --cor))rcttttgeeee algorithm that outputs the estimated optimal utility J. Then, for all v E I, we have:
8
>
sup
PM..
JM J 2
problem instances
sup P..
J
3
MEM
max P Ma.a (0.))
J 5 3 2C
For every 1 E I, we define the identification function V as the index of the problem "recognized" by algorithm 2. In symbols:
V arg min J -
(E(0),)
In words, given estimate , returned by algorithm 21 the identification function V returns the problem between Mo and M, whose optimal utility is closest to the estimate J. For what we have seen in the previous paragraph, problems Mo and M, lie at a distance of at least 2e for all 1 E I. Therefore, for g {0, 2), we have the following inclusion of events:
V * o} S {15 51> el.
40

---

action
actionen (Sw)
Set
action Ou
Spoct
81
85
W.p.
140' (1
wip
14el 1 (y
14 9
By
w.p.
w.p.
0, Vgg..
Figure 5: Hard instances.
Thanks to this fact, we can continue lower bounding the probability as:
(15 J >
max P. (E(0,))
max IP PM VV, # # (E(U,))
P Mo a U * +0) + P. U. #1)
2
1
P P.o.a V * + P.M. (1, 0)
2
@ 1
4 exp KL
where at (1) we have lower bounded the maximum with the average, i.e., max a, b) > (a + b)/2 for all a, 2 and at (2) have applied the Bretagnolle- Huber's inequality (38).
KL-divergence computation The proof can concluded by upper bounding the KL divergence KL Mo. a. P. a) as in the proof of Theorem 7 in [12], and then summing over all the O (SAH) instances to retrieve the result.
Lemma E.3. Let IRL and RFE be the learning problems defined as in Appendix E.1 For each problem, if the set of reward functions R in input is R R, then any (e, ()AA) algorithm must collect at least the following number of exploration episodes:
H
Ω
2
Proof. Instances description The hard instances that we use for the proof of this lemma are obtained by combining the hard instances in Lemmal E.2 (i.c., the hard instances of (12). with those in [38]. Specifically, this construction based on the intuition described [1] that, if we want to increase the sample complexity, we have learn transitions also ( states, and not just from ((S) states. Observe the presence of state Sg (only for IRL), which plays the same role as in the proof Lemma E.2, Any action in such state receives always reward -1, thus it meaningless for the estimate of the (non)compatibility which reduces to the estimation of the optimal performance, In this manner, the expert distribution dp.x does not provide additional information about the transition model of
41

---

other portion of the state-action space. Therefore, in the following, we will present the lower bound construction if such state did not exist.
The hard instances are reported in Figure S Notice that they are exactly the same instances as those presented in the proof of Lemma E.2 with the difference that, from the leaves (differently from earlier, we now denote the number of leaves through S instead of L), we do not reach just two states Sg: Sb, but we reach (S) absorbing states, i.e., 51, 8/2 ..... K5. The transitions from the leaves to such states is the same in 38 and we report description below.
Let us introduce the set == (81,...,, x A {1 d,..., H + dj. Leti (51, 01, 1 +d dZ be specific triple of set I, and denote I == I (T). Let us also introduce set = f (-1,
-j=1" 0}. Thanks to Lemma E.6 of 338 (that we report in Lemma E.4 for simplicity). we know that there exists subset V = V (of transition models) with cardinality at least 2 such that, for every pair v, w E V with v * w, we have that |v- will >> S/16. In other words, we know that there exists 1/161/16ppaae 1/16-packing of V with cardinality at least 25/5
Following [38], we denote by v = (ez) V" the generic vector of V Now, for any v E V for any triple 2 E I, and for some parameter e' e [0, 1/2] to choose, construct problem instance M..3
as follows.
First of all, we define the transition model at triple as:
Ph. (s([ss, ar) = Vi e
where observe that we use notation = (8., Cr h,) I to denote triples in I. Instead, for the generic triple I (including triple J), the probability distribution of the next state is given by:
( a,) = + S
Vi 1
where it represents the i-th component of the 2-th vector in In words, the i-th component of vector o² V creates bias of é' e//S towards the next state 8f for all i [S]. Since vA V, then Ph. (-1s,, a.) A for all z e I.
We consider non non-stationary reward functions. Specifically, all the rewards r R that we consider assign reward 1 to both triples and J. i.e., (S,, a.) and Thy (3j, a,) Next, for any other triple (s, a, h) E S A [H] with state different from s s ....... S we assign reward 0. For states S we consider state-only rewards whose value is always in stages [1, H + d], and whose value is stationary and arbitrary afterwards. Intuitively, as in [1), forcing the reward to be O up H + guarantees that we cannot obtain a higher expected return by reaching the leaves states earlier (i.e., by exiting from sw before H).
s1 ..y...... ..... ......
Given the definition above, we construct the class of instances M = {M... 1 I, V*B. Moreover, we will use the notation M M, to denote the instance which we replace the component of v, ic., v', with w E V and _,, the instance in which we replace the z component of v. i.e., v", with the zero vector. Since we will always use this notation when substituting triple i.e., we always use this notation in situations as M Melny' then we omit the second parameter, and write just M vetw M
Distance between problems Consider an arbitrary problem instance Me, M, for certain I and V², Let Ri be an arbitrary reward function that satisfies the constraints described earlier. Let Wy E II be the deterministic policy that brings to triple 7. Then, its expected return is:
H H d
(r: (o.) =
r4
S
42

---

where ry == "T +d+11 (s() for all i e [S]. Let policy T,, E II be the deterministic policy that brings to triple a. Then, expected return is:
Mo,)) - 1+ H H
H H
d)
S
Finally, let policy Ty II be the deterministic policy that brings to any other triple j M(t). its expected return is:
Then,
Mox)) = H - H -d
H
H d)
Σ 1/r
3 1-1
5
should be remarked that (u,r) long as:
ie
[3]
Ust
[-5,5] for any r R and E V. therefore, as
1-6 2(H H -d)
<1 <
(5)
then any policy т, is cannot be e-optimal in problem Mp in which, thus, the optimal policy shall be searched for between Ty and m..
Now, consider arbitrary pair v, Y such that v o w. and an arbitrary triple E I and vector E V.. We now compare problem instances M and M Among all possible reward functions that satisfy the definition provided in the construction of the hard instances, we find reward r' such that, in every component E [S] satisfies:
+1
if 0 = +1 A wi = --
- if -1 my = +1
0
if U2 W;
For what we have seen before about class V, we know that ||e w||1
Σ
|U;
mil 3
S/16,
thus, since v, w E V, i.e., their components belong to +1,, we know that there are at least S/32 components of u, that differ from each other. By using reward r', we have that:
5
U.T 2
> 0,
32
3
w
< 0.
32
As consequence, the expected returns of policies गं and in problems M Mepp and M w
are:
3
H - H d
(n; M M
(r: M
== =1
5
H-H
3
(H
d)
(ni M
S
32
Ja: H - H1 d
3
(H H d)
32
1=1
from which we infer that:
(r:: Main)) 30 (FT('': JT(' J=:;
Now, let us choose é' 64c/(H HH- H d). To satisfy also the constraint in Equation 55. we can roughly assume < 1/256 and set 63e/ (H H d). Thanks to this choice, observe that: (r; m(n)) > = (M' 2c,
(T; ( (r' M ( 2c.
43

---

In words, policy π, is optimal in problem M Madg. and policy π; is worse than 2e-suboptimal in such problem. In addition, observe that policy яं is optimal in problem M M and policy n, worse than 2e-suboptimal in such problem. We stress that any stochastic policy in-between n, and ny cannot be c-optimal for both problems.
To sum up, for the choice of e' made earlier, for arbitrary pairs of problems MM Mndn and M M peein we have seen that there exist rewards in Ri for which a policy e-optimal for problem Ma is not e-optimal for problem MM,w. and vice versa.
Identifying the underlying problem: RFE. We consider first RFE, and then IRL.
Let us consider an (c, -correet algorithm A for RFE, that outputs, for any reward function E R, policy क. For simplicity, we consider as output of Algorithm 2 function f R - II, that takes in input reward and outputs a policy.
For any E I and v D",
we can lower bound the error probability as:
sup (i - (Za(r) =6 ree
sup
P.M.I
all problem instances M
sup F FM
sup rest
(r) -((()) 20)
MeM
(r) - ()))))
max
P.M.P..... S
sup
sup re
WEV
where at (1) we have lower bounded by replacing all possible RFE problem instances with problem instances in M., and at (2) we have lower bounded by replacing all instances in M with just instances {MM wen w V} for the fixed triple and vector v.
For every e I and v V", we define the identification V,, as the index of the problem w "recognized" by algorithm 2. In symbols:
Vi, = arg min sup J JM,_.
J J (r).
weB re9t
In words, given estimate âे 9 returned by algorithm 21, the identification function V.,, returns the problem in {M
is closest the estimate â. For what / whose solution æ -
we have seen in the previous paragraph, for any v, w E V with v * w, for any fixed
and v E V there exists a reward function r' E Ri such that no policy can have expected utility E-close to the optimal expected utility of both problems M Mein and MM M. Therefore, for w E V, we have the following inclusion of events:
{ I I
w) S sup JM (r)
Jú Mew (r)=
rest w.
We can continue lower bound the probability as:
max wED
PM w. &
sup
JM rest
M
(r)
JM MM (r)
JM
(3)
Σ
PM, 21 (Ver w)
PM
un
WeV
1
Σ KL(PM,, WED
P PM, log
log
where at (3) we have lower bounded the maximum over V with the average, and at (4) we have applied, similary to (38] the Fano's inequality, reported in Theorem E.5 for simplicity.
Identifying the underlying problem: IRL. For IRL, it is possible to carry out a similar derivation. However, remark that, now, the error is measured based on the expected utilities, and not on the policies.
Let us consider an (c, 8)-orretct algorithm A for IRI., that outputs, for any reward function e R. utility J.. For simplicity, we consider as output of Algorithm A function J : Rt I. that takes in input a reward and outputs a utility.
44

---

For any I and D", lower bound the probability as:
JM (r) -J. -rr|30 3
8
sup
P P.M
sup ree9
all problem instances M
sup
P. PMa
sup
(M(r) - J x()
MEM
rebt
Ju (r) (r)- - Jr 3 20)
max WEY
sup regt
For any E I and V. we define an identification function i,, as:
V Ve == arg min sup
J JM, 22 (r) J
we
rest
and by a reasoning analogous to that for RFE, we can continue to lower bounding as:
max
M
sup rEM
JM, M.w
(r)
- Jr
EE
Σ
PMM..
(Vo, # w)
weV
V
WEV
1
Σ weV
KL(F
o.w a P. PM -log2)
(6)
log
[V]
M
which represents the same lower bound obtained also for RFE.
KL.-divergence computation The following derivation is analogous to that of [38] To bound the KI-divergence term, for any E I, we can write:
KL(P M. 02. 21 PM
(I)
E
1 (s), (L Man (11ss, M (1)0,
2(
M oo 21 [NT, a.)].
E
where at (1) we have applied Lemma E.7 and at (2) we have applied Lemma E.6 (having observed that the transition models differ in and defined Nř, (s,, 0,) Ei=1 1[ at he)
(S ag h2)3).
Plugging into Equation (6). we get:
(1 (1- 0) log D -log2 2(c²)2
5
Σ V
PM W
PM a (V, * w)
E
[N [8 (8,,
M
weV
Notice that, since V O(e)) and é' O(e/ H), then this bound is in the order of Q2 11's) To get the additional ((SAH) dependence, we can make the same observation as in [38], i.e., that ince the
derivation carried for every I and u V² we can perform the summation over and the average over v. By noticing that we get guarantee on mean under the uniform distribution of the instances of the sample complexity, we realize that there must exist one hard e V for which it holds the desired = dependency.
E.2.1 Technical Tools
We report here some results from other works. The notation adopted is the same as the original works. Lemma E.4 (Lemma E.6 of 38 Let V E 1-1,111, -Pー 0}. Then, the D number V w.E.. the metric d(v, v')
16 -packing D |B e//1 is lower bounded by 2
Theorem E.5. (Theorem E.2 of (38 Let Po. PI..... PM be probability measures on the same measurable space F), and let A Am E F be partition of Q. Then,
1 M DRa (P, Po) log
1 M
Σ
P((A)) > -
M
log M
45

---

where A = A is the complement of A..
Lemma E.6 (Lemma E.4 of [8)) Let e E [0.1/2] and v E {-G,e] such that Ed
1/2
Consider the two categorical distributions IP ( D....: :) and IP = [+t 1+
1t0p
D
Then, it holds that:
(IP Q) & 2c and
(R. 2
Lemma E.7 (Lemma 5 of [2).. Let M and M' be two MDPs that are identical except for their transition probabilities, denoted by ph and phe respectively. Assume that have (sa), Ph (i(-ss.a) a) & P,(.s,,), a). Then, for any stopping time T with respect to (F'i) Yea1 that satisfies P. PMT < 00 1,
KL PM (L'
3E E SES DEANE(H-])
(L N KL (ph(-s, a), ())s,((1s,))))
E
where No. == Ei A((S), = (s, a)} and 1 : Ω - U1a1 IH : w + I (w) is the random vector representing the history up to episode
F A Use Case for Objective-Free Exploration (OFE)
Consider the following setting. You are given certain MDP without reward M (8, H, do. p). which you do not know neither do nor p. Your job is to explore the environment to collect samples that allow you to construct estimates dg * do and f = that will be subsequently used to perform a task in given class F in an (e, 8) -ccoreett manner. Of course the number of samples should be as small as possible. How do you explore? It depends on which problems are contained in class P.
A use case for OFE is the following.
Example F.1. Assume that we are given single fixed environment (for instance, a warehouse), which there are many tasks to do (e.g., labelling objects, putting stuff on the shelves, bringing products from one side to the other), and assume (it is reasonable) that it is desirable to have one robot for each task. To teach these robots how to behave, we decide to use RL. Since all the robots work in the same environment (warehouse), then the (unknown) transition model is the same. For this reason, an efficient exploration (potentially through RFE) is meaningful. However, we realize that some tasks are difficult to design (i.e., the rewards of such tasks). For these lusks, we prefer to use human expert to exhibit demonstrations, and then use ReL. (in particular, IRI.), to learn the reward, that will be subsequently used for AL. To perform IRL nicely, the samples collected at the beginning shall be used. To sum up, we might be interested in performing multiple RL and IRL tasks in the same unknown MDP, and, for efficiency reasons, our exploration of the environment has to be performed only once (before) being given the tasks to solve.
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 Reviewer can find the list of contributions in Section 1 and the related content the rest of the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
46

---

2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The Reviewer can find a "Limitations" paragraph in Section 7
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "I "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 on 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 few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions 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 a complete (and correct) proof?
Answer: [Yes]
Justification: The Reviewer can find the full set of complete proofs in the supplemental material.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
47

---

Answer:
[NA]
Justification:
The paper does not include experiments.
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 to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make 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 a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS 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
model architecture, the paper should describe the architecture clearly and fully.
(c) 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- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which authors are welcome to 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 be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.c ec/
jublic/guides, http:///uuiids//oeuuuuiiisssss
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https /niiss cc/ httpa/////gudde///eeeuubbiiiiii/
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.
48

---

The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. 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 to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: 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 to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
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 not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
49

---

Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU 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 or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics sictps://neurips. http://s....pbbcc//cccccctiteaae
Answer: [Yes]
The research conducted in the paper does not harm human subjects or par- ticipants, and there are no data-related concerns. In addition, believe that there no noteworthy potential harmful consequences of our research.
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: This paper represents foundational research, and it is tied particular applications. In addition, we believe that there is no direct path to any negative applications.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (c.g., deployment of technologics 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 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, 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 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.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (c.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
50

---

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 no 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 controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
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 the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: The paper does not use existing assets.
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.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, pwperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are 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 was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
51

---

14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as 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 much detail as possible should be included 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/teview based the requirements of your country institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to 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.
52


Reviews:
[{"review_id": "gd98rMUEF5", "reviewer": "Reviewer_AxcE", "summary": "This paper shows that finding the feasible reward set in IRL needs to sample $\\Omega(S)$ number of samples, even when the MDP possesses a linear structure. To enable more efficient scaling with $S$, the authors propose another task in IRL called rewards compatibility: deciding whether $\\pi^{E}$ is $\\epsilon$-optimal under a given reward $r$. They further use reward-free algorithms to solve such tasks and propose a matching lower bound. As a byproduct, the lower bound also improves the existing lower bounds in tabular reward-free RL.", "questions": "The lower bound in Theorem 3.2 characterizes the difficulty of identifying the exact feasible reward set. However, in many cases we just want to learn a feasible reward with some desirable properties instead of the whole set. For this setting will the lower bound still hold?", "limitations": "None.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The theoretical analysis is solid. In particular, the lower bounds for feasible reward set learning and reward compatibility are novel and significant as they quantify the hardness of these two tasks in IRL.", "weaknesses": "1. The reward compatibility framework is not that interesting in my opinion because it requires you to input a reward function, which indeed makes IRL a standard RL problem given that reward. More specifically, the reward compatibility framework is just policy optimization and evaluation of $\\pi^E$ under a given reward $r$, which has been studied sufficiently before.\n2. The algorithms that the authors propose are also just the existing algorithms in standard RL, so there is no novelty in the algorithm design.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are glad that the Reviewer appreciated the novelty and significance of the lower bound results, and the solidity of the theoretical analysis. Below, we report answers to the Reviewer's comments.\n\n## Weaknesses\n> The reward compatibility framework is not that interesting in my opinion because it requires you to input a reward function, which indeed makes IRL a standard RL problem given that reward. More specifically, the reward compatibility framework is just policy optimization and evaluation of $\\pi^E$ under a given reward $r$, which has been studied sufficiently before.\n\nWe agree with the Reviewer that, as we *demonstrate* in the paper (Theorem 5.1 and Theorem 6.2), the rewards compatibility framework turns out to be minimax optimally solvable by a policy optimization and evaluation algorithm in the Reward-Free Exploration (RFE) [1] setting, showing an equivalence of the two problems. *However*, it should be remarked that the significance and the novelty of the scheme lies in the **original formulation and interpretation of the Inverse Reinforcement Learning (IRL) problem**, and *not* in the specific solution technique. \n\nOur ultimate goal is to understand the computational and statistical complexity of inferring as much information (i.e., constraints) as possible about the expert's reward function $r^E$ in an approximate setting. Due to the partial identifiability of the IRL problem [2,3,4], as explained in the introduction, common IRL approaches like *margin* [2] or *entropy* [5] maximization are heuristically \"biased\" toward a specific reward function somehow close to $r^E$. For this reason, we resort to the *feasible set* formulation [4,6], which does not introduce additional assumptions about $r^E$ beyond the optimality of the observed expert policy $\\pi^E$. Nevertheless, since the feasible set is inefficient to learn (being a set) in problems with a large state space (see Theorem 3.2), we introduce the notion of *rewards compatibility*.\n\n**Ideally**, we would like to have an IRL classification algorithm (e.g., some variant of CATY-IRL) that takes in input the problem instance and outputs a binary partition of the space of reward functions into *at most* $\\epsilon$-compatible rewards and *at least* $\\epsilon$-compatible rewards. **In practice**, due to the impossibility of computing such output (limited computational resources), we develop an algorithm, i.e., CATY-IRL, that *potentially* can classify all possible rewards, but that actually classifies only the input rewards.\n\n > The algorithms that the authors propose are also just the existing algorithms in standard RL, so there is no novelty in the algorithm design.\n\nWe agree with the Reviewer that the proposed algorithm, CATY-IRL, executes existing RFE algorithms as sub-routines. *However*, a major contribution of our work is **demonstrating that such sub-routines actually solve the IRL classification problem** (Definition 4.2) **in a minimax optimal manner** (Theorem 5.1 and Theorem 6.1), and thus, *proving* an equivalence between IRL and RFE from the sample complexity viewpoint which has been *conjectured* in previous works (e.g., Appendix A of [4] or Appendix D of [7]). We will stress this in the final version.\n\n## Questions\n> The lower bound in Theorem 3.2 characterizes the difficulty of identifying the exact feasible reward set. However, in many cases we just want to learn a feasible reward with some desirable properties instead of the whole set. For this setting will the lower bound still hold?\n\n**Yes**. To see why, as an example, assume you aim to learn only the feasible reward function that satisfies the *margin maximization* criterion in Equation (6) of [2]. By re-using the same hard instance constructed in the proof of Theorem 3.2, we see that no algorithm can discriminate between policies $\\pi^E_1$ and $\\pi^E_2$ unless it collects a sample from state $\\overline{s}$. Without knowing which policy between $\\pi^E_1$ and $\\pi^E_2$ is the true expert policy, any algorithm will fail with probability at least $0.5$ in the worst case at outputting an accurate estimate of the reward function, since reward $\\theta_1=1$ is the margin maximizer for policy $\\pi^E_1$, and $\\theta_2=0$ is the margin maximizer for policy $\\pi^E_2$, and the distance $d$ (see Equation (1)) between these rewards is exactly $1$. The result follows by observing that we need $\\Omega(S)$ samples to spot state $\\overline{s}$.\n\nTo avoid this negative result, we can **learn a single $\\epsilon$-compatible reward** (for some $\\epsilon>0$) that satisfies the same margin-maximization criterion, instead of learning the feasible reward that satisfies the criterion. Nevertheless, for the reasons presented in the introduction of the paper, we prefer to be *criterion-agnostic*, and to learn *all* the compatible rewards.\n\nWe will make this point clear in the paper.\n\n## References\n\n[1] Chi Jin et al. Reward-free exploration for reinforcement learning. ICML, 2020.\n\n[2] Ng and Russell. Algorithms for inverse reinforcement learning. ICML, 2000.\n\n[3] Skalse et al. Invariance in policy optimisation and partial identifiability in reward learning. ICML, 2023.\n\n[4] Metelli et al. Provably efficient learning of transferable rewards. ICML, 2021.\n\n[5] Ziebart et al.. Maximum entropy inverse reinforcement learning. AAAI, 2008.\n\n[6] Zhao et al. Is inverse reinforcement learning harder than standard reinforcement learning? ICML, 2024.\n\n[7] Lindner et al. Active exploration for inverse reinforcement learning. NeurIPS, 2022.", "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": "EH5rgD1oDJ", "reviewer": "Reviewer_K3ze", "summary": "Even under the strong assumption implicit in Linear MDPs, the learning of the set of rewards that make the expert’s policy optimal doesn’t scale well. This improves somewhat, if additionally a notion of compatibility of rewards is introduced, because in this way and under these conditions the IRL problem can be seen as a classification task. In this context a number of theoretical results are possible minimax optimality of a thus formulated IRL algorithm, complexity bounds and some contribution to the complexity theory of reward-free exploration.", "questions": "Would objective-free exploration be independent on the linear MDP assumption? Is it needed at all in the present paper?\n\nCan you compare to other IRL algorithms?", "limitations": "Practical application is limited, but this is outside the scope of this very impressive paper.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "Outsourcing some of related work to the appendix seems a good idea here, as the proper introduction is still readable and interesting. However, it may have been an alternative option to move the “original contributions” to the appendix as these are already mentioned in the abstract and in --- the paper. The paper aims at much, and although it delivers, but could be more focused and concise.", "weaknesses": "“How to” is not really addressed, “How to Scale Inverse RL to Large State Spaces?” should be “How does Inverse RL Scale to Large State Spaces?”\n\nThe separation of exploration and classification phases may not appear to be a problem at this level of abstraction, but practically this can be a forbidding features of an algorithm.\n\nThe approach uses a restrictive problem setting, while it could be preferable to attempt to discover any compositional structure or any latent low-dimensional manifolds, as would be the present in any practical problem if the problem can be treated at all at larger scales.\n\nNo simulation included, although it should be easy provide some illustration, in particular for any worst-case results.\n\nObjective-free exploration need more study to receive the attention that it is claimed to deserve, but the current definition probably needs to be more precise.\n\nHere (as in most contributions to this conference) the use of display equations is dearly missed. Couldn’t the amount of ink be used to measure the length of the papers?\n\nThe use of color in the manuscript could be more systematic, if it is encouraged at all.\n\nThere is too much material in the paper. It may be tempting to publish a systematic study at a conference to reach some visibility, but it creates an imbalance among the contribution and may bias future submission.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are glad that the Reviewer found our paper to be impressive and our contribution to be substantial. We provide detailed replies to their questions/comments below.\n\n## Weaknesses\n\n> “How to” is not really addressed, “How to Scale Inverse RL to Large State Spaces?” should be “How does Inverse RL Scale to Large State Spaces?”\n\nWe thank the Reviewer for the observation. We will change it.\n\n> The separation of exploration and classification phases may not appear to be a problem at this level of abstraction, but practically this can be a forbidding features of an algorithm.\n\nFrom a theoretical perspective, the separation of the exploration phase from the subsequent phase permits to *isolate the challenges of exploration*, as mentioned in [1]. In practical applications, we require our learner to be able to actively explore the environment. Since the results of the classification phase are available *after* the exploration has completed, then any subsequent task has to be postponed.\n\n> The approach uses a restrictive problem setting, while it could be preferable to attempt to discover any compositional structure or any latent low-dimensional manifolds, as would be the present in any practical problem if the problem can be treated at all at larger scales.\n\nWe agree with the Reviewer that Linear MDPs suffer from some limitations if we want to apply them to real-world applications, but we believe that they represent an important initial step toward the development of provably efficient IRL algorithms with more general function approximation structures.\n\n> No simulation included, although it should be easy provide some illustration, in particular for any worst-case results.\n\nWe agree that an empirical validation would be nice, but, as the Reviewer also noted, we are already providing a lot of contributions, leaving no space for experiments unfortunately.\n\n> Objective-free exploration need more study to receive the attention that it is claimed to deserve, but the current definition probably needs to be more precise.\n\nThe formulation of the Objective-Free Exploration (OFE) problem setting (Definition 6.1) is intentionally provided in a general way. The reason is that we aim that this definition will be used as a *template* for analysing exploration problems, and, thus, it should be instantiated more precisely in the specific problem depending on the tasks to be solved (see Example F.1 in Appendix F). In appendix E.1, we provide more insights on OFE, by identifying two additional problems beyond RL and IRL whose exploration phase can be casted in this scheme.\n\n> Here (as in most contributions to this conference) the use of display equations is dearly missed. Couldn’t the amount of ink be used to measure the length of the papers? The use of color in the manuscript could be more systematic, if it is encouraged at all.\n\nWe agree with the Reviewer that some choices about the layout and the design of the paper may be improved. We will leverage the additional page to improve the readability of the paper.\n\n> There is too much material in the paper. It may be tempting to publish a systematic study at a conference to reach some visibility, but it creates an imbalance among the contribution and may bias future submission.\n\nWe agree with the Reviewer that it may be hard to process all of the contributions we provide. Nevertheless, we believe that they cannot be separated from each other, because it would negatively affect the presentation and the understanding of the paper.\n\n## Questions\n\n> Would objective-free exploration be independent on the linear MDP assumption? Is it needed at all in the present paper?\n\nYes, Objective-Free Exploration (OFE) is a problem setting which is independent of specific assumptions on the structure of the MDP (e.g., linear MDP).\n\nAlthough, at first sight, OFE may seem out of scope in this paper, we believe that its formulation is significant as: $(i)$ it provides a unifying *exploration* framework for RL and IRL problems; $(ii)$ it highlights the efficiency and efficacy of Reward-Free Exploration (RFE) strategies for solving both tasks.\n\nSince part of our contribution consists in showing that RL and IRL enjoy the same sample complexity rate (Theorem 5.1, Theorem 6.1, and Theorem 6.2) in tabular problems and the same upper bound in Linear MDPs, the OFE problem setting permits to interpret these results in a *unifying* and original manner.\n\n> Can you compare to other IRL algorithms?\n\nUnfortunately, we cannot compare with popular IRL algorithms like margin maximization [2] or entropy maximization [3] (and their variants) because they enforce additional assumptions on the reward function to recover. The IRL algorithms that consider a problem setting analogous to ours are those in [4,5,6,7,8], whose objective is the estimation of the feasible reward set. Nevertheless, all algorithms presented in [4,5,6,7,8] focus on the tabular setting, and they exhibit an explicit dependence on the size of the state space. Thus, they cannot be used for problems with large state spaces.\n\n## References\n\n[1] Chi Jin et al. Reward-free exploration for reinforcement learning. ICML, 2020.\n\n[2] Ng and Russell. Algorithms for inverse reinforcement learning. ICML, 2000.\n\n[3] Ziebart et al. Maximum entropy inverse reinforcement learning. AAAI, 2008.\n\n[4] Metelli et al. Provably efficient learning of transferable rewards. ICML, 2021.\n\n[5] Zhao et al. Is inverse reinforcement learning harder than standard reinforcement learning? ICML, 2024.\n\n[6] Lindner et al. Active exploration for inverse reinforcement learning. NeurIPS, 2022.\n\n[7] Lazzati et al. Offline inverse rl: New solution concepts and provably efficient algorithms. ICML, 2024.\n\n[8] Metelli et al. Towards theoretical understanding of inverse reinforcement learning. ICML, 2023.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nEyp9nOWfh", "reviewer": "Reviewer_KyLX", "summary": "This paper finds that the feasible reward set cannot be efficiently learned even under linear MDPs. Therefore, the paper proposes a new notion called \"reward compatibility\" that generalizes the notion of \"feasible set\" and thereby casts IRL as a classification problem. The paper proposes an algorithm to solve this new classification problem and theoretically show that the sample complexity of the proposed algorithms is independent of state cardinality for linear MDPs.", "questions": "Please see weaknesses.", "limitations": "The limitation is discussed in Section 7.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1. This paper proposes a new notion called \"reward compatibility\" and novelly formulates IRL as a classification problem based on the notion.\n\n2. This paper is theoretically solid, which is also the biggest strength of the paper.", "weaknesses": "1. The paper title is a little bit exaggerating. The title is \"scale IRL to large state spaces\", while what the paper does is to scale one specific kind of IRL, i.e., learning the feasible reward set, to large state spaces. In fact, many other kinds of IRL algorithms can work quite efficiently in continuous state spaces without the linear MDP assumption. For example, maximum likelihood IRL [1] is sample efficient where only one sample is needed for each reward update. I think what the authors mean here is that learning the feasible reward set is difficult in large state space, however, learning feasible reward set is only a kind of IRL, but does not represent all IRL methods. I suggest that the authors change the general terminology \"IRL\" to some more specific terminologies, given that some other kinds of IRL methods can already scale to large state spaces.\n\n2. The paper uses the terminology \"online IRL\" to represent IRL that needs to interact with the environment. The paper also adds a footnote to explain this notion. I know that this is to contrast offline IRL. However, it is still confusing because online IRL is already defined in literature [2,3,4], i.e., the IRL setting where the demonstrated trajectories are revealed sequentially. Therefore, I highly suggest the authors to use another terminology to avoid confusion.\n\n3. In example 4.1, the authors mention that the reward function with smaller $\\bar{C}(r)$ is more compatible. This can be questionable. For example, suppose $r_2=2 r_1$, then $\\bar{C}(r_2)>\\bar{C}(r_1)$ if they are both positive. However, can we say that $r_1$ is more compatible than $r_2$? The MDPs are equivalent if we multiply the reward by a constant. Then intuitively, $r_1$ and $r_2$ should be same compatible right?\n\n4. Lack of empirical evaluation.\n\n[1] Maximum-likelihood inverse reinforcement learning with finite-time guarantees\n\n[2] First-person activity forecasting with online inverse reinforcement learning\n\n[3] Online inverse reinforcement learning under occlusion\n\n[4] Learning multi-agent behaviors from distributed and streaming demonstrations", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer for praising our theoretical analysis as solid, and for recognizing the novelty of the formulation of IRL as a classification problem, which we believe is an important finding of our work.\n\n## Weaknesses\n\n1- We agree with the Reviewer that the general terminology \"*Inverse Reinforcement Learning*\" may be confusing, since it does not reveal the specific IRL formulation considered. Even though previous works on the feasible set have adopted the same general notation [5,6,7,8,9], we agree that a more specific terminology, like \"*Maximum Likelihood IRL*\" [1], \"*Bayesian IRL*\" [10], or \"*Maximum Entropy IRL*\" [11], would be clearer. We will change it to \"*How does Learning the Feasible Reward Set Scale to Large State Spaces?*\".\n\n2- Again, we agree with the Reviewer that overloading common IRL terminology may create some confusion. Although \"*Online IRL*\" fits the analysed problem setting, we will resort to \"*Active Exploration IRL*\", which describes the possibility of exploring the environment, and which is compatible with previous work [7].\n\n3- Thank you for the interesting question, which allows us to remark a *very important* point about the **interpretation of the notion of reward function** in MDPs, and in particular about the **scale** of the rewards.\n\nThe MDP is a model, i.e., a simplified representation of reality, which is commonly applied to 2 different kinds of real-world scenarios: $(i)$ problems in which the agent (learner in RL or expert in IRL) actually **receives** some kind of scalar feedback from the environment, which can be *modelled as a reward function*; $(ii)$ problems in which the agent does **not receive** a feedback from the environment, but its objective, i.e., its structure of preferences among state-action trajectories (which trajectories are better than others), satisfies some axioms that permit to *represent it through a scalar reward* [13,14] (this is referred to as the *Reward Hypothesis* in literature [12]).\n\nThere is an enormous difference between scenario $(i)$ and scenario $(ii)$. **In $(i)$ the notion of $\\epsilon$-optimal policy is well-defined** for any fixed $\\epsilon>0$, because the reward function is given and, thus, *fixed*. Instead, in $(ii)$, the notion of reward function is a *mere* mathematical artifact used to represent preferences among trajectories, whose existence is guaranteed by a set of assumptions/axioms [12,13,14]. As the Reviewer has observed, *positive affine transformations* of the reward do not affect the structure of preferences represented (see [13] or Section 16.2 of [15] or [16]). Therefore, **in $(ii)$, the notion of $\\epsilon$-optimal policy is *not* well-defined**, because rescaling a reward function $r$ to $kr$ changes the suboptimality of some policy $\\pi$ from $\\epsilon$ to $k\\epsilon$. In other words, for fixed $\\epsilon>0$, any policy can be made $\\epsilon$-optimal by simply rescaling a reward $r$ to $kr$ for some *small enough* $k>0$.\n\nIn **IRL**, this issue is even more influential because, although we are in setting $(i)$, we have *no* idea on the scale of the true reward function. For this reason, *our solution* is to attach to any reward $r$ a notion of compatibility $\\overline{\\mathcal{C}}(r)$ which **implicitly** contains information about the *scale* of the reward $r$. Compatibilities of different rewards (e.g., $r_1$ and $r_2$ in the Reviewer example) cannot be compared unless the rewards have the same scale (e.g., $r_1$ and $r_2$ have different scales, thus their compatibilities shall not be compared).\n\nIt should be observed that in Appendix C.2 we discuss a **notion of compatibility *independent* of the scale of the reward**. However, we show that it suffers from major drawbacks that make the notion of compatibility introduced in the main paper (Definition 4.1) more suitable for the IRL problem.\n\nIn conclusion, the answer to the Reviewer's question is **no, rewards $r_1$ and $r_2$ should not have the same compatibility, because they have different scales, and the notion of compatibility (i.e., suboptimality) is strictly connected to the scale of the reward**. To carry out a fair comparison of compatibilities, one should rescale the compatibility of each reward based on the scale of the reward.\n\nWe will make this point clear in the paper.\n\n4- We stress that the contribution of the paper is theoretical and, given the contributions provided, we believe that an empirical validation of the proposed algorithm is out of the scope of this work.\n\n## References\n\n[1] Zeng et al. Maximum-likelihood inverse reinforcement learning with finite-time guarantees. NeurIPS, 2022.\n\n[2] Rhinehart and Kitani. First-person activity forecasting with online inverse reinforcement learning. ICCV, 2017.\n\n[3] Arora et al. Online inverse reinforcement learning under occlusion. AAMAS, 2019.\n\n[4] Liu and Zhu. Learning multi-agent behaviors from distributed and streaming demonstrations. NeurIPS, 2023.\n\n[5] Zhao et al. Is inverse reinforcement learning harder than standard reinforcement learning? ICML, 2024.\n\n[6] Lazzati et al. Offline inverse rl: New solution concepts and provably efficient algorithms. ICML, 2024.\n\n[7] Lindner et al. Active exploration for inverse reinforcement learning. NeurIPS, 2022.\n\n[8] Metelli et al. Towards theoretical understanding of inverse reinforcement learning. ICML, 2023.\n\n[9] Metelli et al. Provably efficient learning of transferable rewards. ICML, 2021.\n\n[10] Ramachandran and Amir. Bayesian inverse reinforcement learning. IJCAI, 2007.\n\n[11] Ziebart el al.. Maximum entropy inverse reinforcement learning. AAAI, 2008.\n\n[12] Sutton and Barto. Reinforcement Learning: An Introduction. 2018.\n\n[13] Shakerinava and Ravanbakhsh. Utility theory for sequential decision making. ICML, 2022.\n\n[14] Bowling et al. Settling the reward hypothesis. ICML, 2023.\n\n[15] Russell and Norvig. Artificial Intelligence: A Modern Approach. 2010.\n\n[16] David M. Kreps. Notes on the theory of choice. Westview Press, 1988.", "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": "Gyc52GzLzC", "reviewer": "Reviewer_x3io", "summary": "The paper studies IRL in linear MDPs. The authors first demonstrate that the feasible reward set cannot be efficiently learned in large state and action spaces. To address this challenge, they propose a new IRL framework called reward compatibility, where the goal is to learn a classifier that determines whether the expert is approximately optimal for a given reward. Using CATY-IRL, they also introduce a new sample-efficient algorithm for this task, which first explores the MDP via reward-free exploration (RFE) and then evaluates whether a given reward is compatible with the expert's demonstrations. Furthermore, for the tabular setting, they provide a tight minimax lower bound and show that a similar bound also improves on existing lower bounds for RFE. Lastly, the authors propose a novel problem setting of objective-free exploration, which generalizes RFE to arbitrary tasks of interest.", "questions": "How would you apply your algorithm to a real world IRL problem? What is the computational complexity of the classification step?", "limitations": "I think the practical limitations should be discussed more extensively.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "The paper provides a good and original contribution to the challenging problem of IRL in large state-action spaces. In my opinion, its strengths are:\n1. Technical quality: The authors use elegant notation and carefully introduce all symbols. Moreover, clear proofs for all results are provided in the appendix.\n2. Sample complexity bounds: The sample complexity of CATY-IRL is thoroughly analyzed for tabular MDPs, tabular MDPs with linear rewards, and linear MDPs. Additionally, a tight minimax lower bound for the tabular setting is given. This lower bound is particularly appreciated, as lower bounds are still rare in the IRL literature.\n3. Originality: After proving that identifying the feasible reward set is intractable, the authors introduce the novel problem setting of checking for reward compatibility and provide a sample efficient algorithm for it.", "weaknesses": "1. Motivation: While original, the motivation for learning a reward compatibility classifier is not entirely clear to me. I would expect the authors to better explain its usefulness and potential applications.\n2. Writing: The paper is not easy to understand on the first read. There are many propositions and theorems, but more emphasis on motivation and intuition building would be beneficial. For instance, a simple example for Proposition 3.1 could help build geometric intuition.\n3. Related work: The authors introduce reward non-compatibility as a novel metric for IRL. However, minimizing the suboptimality of the expert is a core idea behind many imitation learning and IRL algorithms, such as GAIL and others. Of course, in the unregularized setting minimizing the suboptimality would lead to trivial solutions. However, I would expect a discussion about similarities and differences to min-max IL/IRL in the main part of the paper.\n4. Computational complexity: The authors claim that their algorithm is also computationally efficient, but I couldn't find a discussion about this.\n5. This is a minor point, but in line 103 you use but don't introduce the notation $Y^X$ for the set of functions mapping from $X$ to $Y$. Moreover, slightly inconsistently the set of functions from $X$ to $\\Delta^Y$ is denoted as $\\Delta_X^Y$. Why don't you change the notation to $\\Delta_Y^X$?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer for praising our analysis as solid and novel, and for noting the significance of the proposed lower bounds. We answer the Reviewer questions and comments below.\n## Weaknesses\n1- We divide the answer in two parts. First, we explain why learning a reward compatibility classifier is *useful* from a technical perspective. Next, we describe some *applications*.\n\nOur **ultimate goal** is *to understand how many samples are necessary for inferring as much information as possible about the expert's reward function $r^E$ from demonstrations*. Since the problem is *ill-posed* (underconstrained) [1,2], i.e., $r^E$ is only partially identifiable from demonstrations [3], we resort to understanding how many samples are needed to infer the constraints characterizing $r^E$, i.e., the feasible set (see Definition 3.1). However, as we demonstrate in Section 3, inferring the constraints, i.e., the feasible set, in Linear MDPs cannot be done either in a sample efficient manner (because of the lower bound in Theorem 3.2), or in a computational efficient manner (because it contains a continuum of functions, see lines 184-186). **For these reasons**, instead of learning the feasible set (i.e., the set of rewards with $0$ (non)compatibility), **we propose** to learn the *set* of rewards with $\\Delta$ (non)compatibility (for some $\\Delta>0$), and we demonstrate that this task is sample efficient (same upper bound as CATY-IRL, see Theorem 5.1) but not computationally efficient, because, again, the set contains a continuum of functions. Thus, we propose to learn a *classifier*, which can be seen as a *trick* for the practical computation of a set of infinite items.\n\nBeyond offering a *significant characterization* of the intrinsic complexity of the IRL problem (see Theorem 5.1 and Theorem 6.1), an algorithm (e.g., CATY-IRL) for learning a reward compatibility classifier **can be applied to most common IRL applications**, **without suffering from the bias induced by some *heuristics*** (e.g., margin maximization [1]) **or *additional assumptions*** (e.g., entropy maximization [4]). For instance, $(i)$ in the context of **designing rewards** for RL agents [5], CATY-IRL permits to combine domain knowledge and expert demonstrations by calculating the degree to which some human-designed rewards are compatible with the given demonstrations; $(ii)$ given some rewards candidate at **modelling the preferences** of the observed agent, obtained for example through human design or some IRL algorithms [1,4], with purposes like imitating or predicting  behaviour [6], CATY-IRL permits to discriminate among such rewards based on their level of compatibility with the demonstrations. $(iii)$ In a **Reward Learning** [3] setting, CATY-IRL allows us to integrate the constraints provided by various feedbacks (e.g., demonstrations and preferences) based on a *soft* notion of constraints satisfaction. Finally, $(iv)$ CATY-IRL also allows us to integrate **demonstrations from different environments** [7] in a *soft* manner.\n\nWe will make this point clearer in the paper.\n\n2- The Reviewer can find two examples for Proposition 3.1 in Appendix B.1. We will leverage the additional page to provide more insights and intuition on the propositions and theorems, and to improve the readability of the paper.\n\n3- In common **IRL algorithms** [6], the goal is to learn a *single* reward function that minimizes the suboptimality of the expert's policy. In **IL algorithms** (e.g., [8]), the goal is to learn a *policy* whose suboptimality w.r.t. the expert's policy suboptimality is minimized under all rewards, since the true reward is unknown.\n\nInstead, the goal of **our IRL classification algorithm** is to *minimize the error at estimating the suboptimality of the expert's policy under any reward*. In other words, we are not looking for some special reward for which the expert's suboptimality is small, but our objective is to learn the expert's suboptimality under any possible reward function. The insight is that we aim to exploit the *entire expressive power* of demonstrations from an optimal expert to characterize the *whole* range of reward functions.\n\nWe will integrate the section on the related works with this discussion.\n\n4- We thank the Reviewer for having made us notice this issue. Simply put, CATY-IRL is computationally efficient because it exploits a computationally efficient algorithm, RFLin [9], as a sub-routine (see Remark 4.1 in [9] for additional details), and then all other steps require constant time and space to be executed.\n\nWe will add this comment to the main paper and a detailed analysis of the computational complexity.\n\n5- We thank the Reviewer for the suggestion. We will change it.\n## Questions\n> How would you apply your algorithm to a real world IRL problem?\n\nSee the comment to the *Motivation* weakness.\n\n> What is the computational complexity of the classification step?\n\nThe classification step consists in executing a RFE algorithm as sub-routine, and then executing some simple operations that require constant time and space, thus, the computational complexity of the classification step is the same as the RFE sub-routine. Specifically, for Linear MDPs, algorithm RFLin [9] is computationally efficient (see Remark 4.1 in [9]).\n\n## References\n\n[1] Ng and Russell. Algorithms for IRL. ICML 2000.\n\n[2] Metelli et al. Provably efficient learning of transferable rewards. ICML 2021.\n\n[3] Skalse et al. Invariance in policy optimisation and partial identifiability in reward learning. ICML 2023.\n\n[4] Ziebart et al. Maximum entropy IRL. AAAI 2008.\n\n[5] Hadfield-Menell et al. Inverse Reward Design. NeurIPS 2017.\n\n[6] Arora and Doshi. A survey of IRL: Challenges, methods and progress. Artificial Intelligence 2018.\n\n[7] Cao et al. Identifiability in IRL. NeurIPS 2021.\n\n[8] Ho and Ermon. Generative adversarial IL. NeurIPS 2016.\n\n[9] Wagenmaker et al. Reward-free RL is no harder than reward-aware RL in linear MDPs. ICML 2022.", "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:

Meta-review: The paper provides a solid and original contribution to the problem of inverse reinforcement learning (IRL) in large state-action spaces, particularly by introducing the reward compatibility framework and the CATY-IRL algorithm. While the reviewers raised concerns about the clarity of motivation for reward compatibility and the need for better intuition and comparisons to related work, they also recognized the technical novelty. All the reviewers agree with acceptance.
Decision: Accept (poster)