How does Inverse RL Scale to Large State Spaces? A Provably Efficient Approach

Authors: filippo  lazzati
mirco  mutti
alberto maria metelli
politecnico  di
milano  milan
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 14:32:46

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.

Main paper: 
 introduction: 
 Inverse Reinforcement Learning (IRL) is the problem of inferring the reward function given demonstrations of an optimal behavior, i.e., from an 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, 4] . Indeed, the solution of the IRL problem opens the door to a variety of interesting applications, including Apprenticeship Learning (AL) [2, 1] , reward design [16] , interpretability of the expert's behavior [17] , and transferability to new environments [15] .Nowadays, the factor that most negatively impacts the adoption of IRL solutions in real-world applications is the intrinsic 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 a variety of rewards. In other words, the IRL problem is underconstrained, even in the limit of infinite demonstrations [42, 39] .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 a heuristic to select a specific reward function from the set of all the rewards that explain the demonstrations. Implicitly, these works re-define IRL as the problem of 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, 15] . (ii) In the second approach, additional constraints beyond 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 [5, 10] . In Reward Learning (ReL) works [19] , demonstrations of optimal behavior are combined with other kinds of expert feedback, like comparisons [65] . (iii) As a third approach, recently, [39, 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 IRL task [e.g., 39, 33, 38, 68, 31] . On this basis, the IRL approach (iii) based on the feasible set [39, 38] 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, 33, 38, 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., 15, 7, 40, 14] .In this context, function approximation represents an essential tool to tackle the curse of dimensionality and enforce generalization [54, 41] . Linear Markov Decision Processes (MDPs) [23, 67] offer a simple but powerful structure, in which we assume the reward function and the transition model can be expressed as linear combinations of known features, that permits theoretical analysis of the sample complexity. Even though many extensions have been developed [64, 22, 13] , 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 [e.g., 63, 61] .In this paper, we aim to shed light on the challenges of scaling the feasible reward set to large-scale problems. Motivated by its limitations when dealing with large state spaces, we introduce the novel Rewards Compatibility framework. Being a generalization of the notion of feasible set, it allows us 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 CATY-IRL (CompATibilitY for IRL), a 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 as 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 a new formulation of IRL classification task (Section 4). • For the newly-devised framework, we develop CATY-IRL (CompATibilitY for IRL), a 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 policy is known (Section 5). • In the tabular setting, we prove a tight minimax lower bound to the sample complexity of the IRL classification problem of Ω `H3 SA ϵ 2 pS `log 1 δ q ˘episodes, where S and A are the cardinalities of the state and action spaces, H is the horizon, ϵ the accuracy and δ the failure probability. This bound is matched by CATY-IRL, up to logarithmic factors. Exploiting a similar construction, we show that a lower bound with the same rate holds also for the Reward-Free Exploration (RFE) problem, improving by an H factor over the RFE state-of-the-art lower bound [21] (Section 6.1).• Finally, we formulate a novel Objective-Free Exploration (OFE) setting that isolates the challenges of exploration beyond Reinforcement Learning (RL), by unifying RFE and IRL (Section 6.2). Additional related works and the proofs of all the results are reported in Appendix A and B -E. BPI and RFE. In both Best-Policy Identification (BPI) [37] and Reward-Free Exploration (RFE) [21] , the learner has to explore the unknown MDP to optimize a certain reward function. In BPI, the learner observes the reward function r during exploration, and its goal is to output a policy p π such that, in the true MDP with transition model p we have P `J˚p r; pq ´J p π pr; pq ď ϵ ˘ě 1 ´δ for every ϵ, δ P p0, 1q. RFE considers the setting in which the reward to optimize is revealed a posteriori of the exploration phase. Thus the goal of the agent in RFE is to compute an estimate p p of the true dynamics p so that P `sup rPR tJ ˚pr; pq ´J p πr pr; pqu ď ϵ ˘ě 1 ´δ for every ϵ, δ P p0, 1q, where p π r is the optimal policy in the MDP with p p as transition model and r as reward function.Online IRL. We consider the online 2 IRL setting [39, 33, 68, 66, 53] in which, similarly to the online AL setting [53, 66] , we are given a dataset D E " tps i 1 , a i 1 , . . . , s i H´1 , a i H´1 , s i H qu iP τ E of τ E P N trajectories collected by executing the expert's policy π E in a certain (unknown) MDP M " M Y tr E u. We make the assumption that π E is optimal under the true (unknown) reward r E in M. Since the dynamics of M is unknown, we are allowed to actively explore the environment through a forward model to collect a new state-action dataset D. The goal is to use the latter and demonstrations in D E to estimate a reward function that makes the expert's policy π E optimal. Sometimes, we will denote an IRL instance as M Y tπ E u, and a Linear IRL instance with recovered reward r as an IRL instance in which M Y tru is a Linear MDP. 
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., 39, 33, 38, 68, 31] , the feasible set contains the rewards that make the expert's policy π E optimal, as defined below. Definition 3.1 (Feasible Set [31] ). Let M be an MDP without reward and let π E be the expert's policy. The feasible set R p,π E of rewards compatible with π E in M is defined as: R p,π E :" tr P R | J π E pr; pq " J ˚pr; pqu.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. 3 Definition 3.1 can be adapted to Linear MDPs with feature map ϕ as: R ϕ,p,π E :" tr P R | J π E pr; pq " J ˚pr; pq ^Dθ : H Ñ R d , @ps, a, hq P S ˆA ˆ H : r h ps, aq " xϕps, aq, θ h yu. We omit ϕ in R ϕ,p,π E for notational simplicity. Proposition 3.1. Let M be a Linear MDP without reward with a finite state space, and let ϕ be a feature mapping. Let tΦ π E h u hP H and tΦ h u hP H be the sets of expert's and non-expert's features, defined for every h P H as:Φ π E h :" ␣ ϕps, a E q | s P S p,π E h , a E P A E h psq ( , Φ h :" ␣ ϕps, aq | s P S p,π E h , a P AzA E h psq ( ,where A E h psq :" ta P A|π E h p¨|sq ą 0u for every s P S. If for none of the H pairs of sets pΦ π E h , Φ h q there exists a separating hyperplane, then R p,π E " tru, with r h ps, aq " 0 @ps, a, hq P S ˆ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 in Appendix B.1.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). Let ϵ, δ P p0, 1q, and let A be an algorithm that collects τ E samples about π E using a generative model, and τ episodes from a Linear MDP without reward M " pS, A, H, d 0 , pq using a forward model. Let p R be the estimate of the feasible set R p,π E outputted by A.Then, A is pϵ, δq-PAC for IRL if P M,A `Hd pR p,π E , p Rq ď ϵ ˘ě 1 ´δ, where P M,A is the probability measure induced by A in M, and dpr, p rq9 sup πPΠ ř hP H E ps,aq"d p,π h p¨,¨q |r h ps, aq ´p r h ps, aq|. 4 The sample complexity is the pair pτ E , τ q.It is worth noting that in Definition 3.2, we are considering a 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 Y tπ E u be a Linear IRL instance with finite state space S and deterministic expert's policy, and let ϵ, δ P p0, 1q. If an algorithm A is pϵ, δq-PAC, then τ E " ΩpSq, 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 ΩpSq dependence. Nevertheless, if π E is known, it is possible to construct sample efficient algorithms. Algorithm 1 (whose pseudocode is presented in Appendix B.3), under the assumption that π E is known, makes use of an inner RFE routine (Algorithm 1 of [62] ) to recover the feasible set. Theorem 3.3. Assume that π E (along with its support S p,π E ) is known. Then, for any ϵ, δ P p0, 1q, Algorithm 1 is pϵ, δq-PAC for IRL with a number of episodes τ upper bounded by:τ ď r O ´H5 d ϵ 2 ´d `log 1 δ ¯¯.Limitations of the Feasible Set. We can now conclude that the feasible set suffers from two main limitations. (i) Sample Inefficiency: If π E is unknown, it requires a number of samples that depends on the cardinality of the state space (Theorem 3.2). (ii) Lack of Practical Implementability: It contains a continuum of rewards, thus, no practical algorithm can explicitly compute it. We will discuss in the next section how to overcome both these issues. 
rewards compatibility: 
 In this section, we present the main contribution of this work: Rewards Compatibility, a novel framework for IRL that allows us to conveniently rephrase the learning from demonstrations problem as a classification task. We anticipate that the presentation of the framework is completely general and independent of structural assumptions of the MDP (e.g., Linear MDP).In the following, for ease of presentation, we consider the exact setting, i.e., when d 0 , p, and π E are known. In addition, we will drop the dependence on p when clear from the context.In IRL, an expert agent demonstrates policy π E assumed optimal under some (unknown) reward function r E , i.e., J ˚pr E q " J π E pr E q . The task is to recover a reward r such that J ˚prq " J π E prq. By definition, IRL tells us that r E makes the demonstrated policy π E optimal, but what about other policies? We do not and cannot know. Since there are (infinite) rewards making π E optimal (but they differ in the performance attributed to other policies) we realize that there are many rewards equally "compatible" with π E . 5 Clearly, wih no additional information, we are unable to identify r E .The feasible set considers only these rewards, i.e., r P R for which J ˚prq " J π E prq, and it refuses all the others. This can be interpreted as the feasible set carrying out a classification of rewards based on a "hard" notion of compatibility with demonstrations. In other words, rewards r satisfying condition J ˚prq " J π E prq are compatible with π E , and the others are not. Nevertheless, our insight is that some rewards are "more" compatible with π E than others.Example 4.1. Consider an MDP with one state and H " 1 in which the expert has three actions: Eating a muffin (M), a cake (C), or some (bad) vegetable soup (S). The true reward r E assigns r E pM q " `1, r E pCq " `0.99 and r E pSq " ´1, i.e., the expert has a (weak) preference for the muffin over the cake, while she hates the soup; thus, she will demonstrate π E " M . Let r g , r b be: r g pM q " `0.99, r g pCq " `1, r g pSq " ´1, r b pM q " ´1, r b pCq " ´1, r b pSq " `1.Intuitively, r g is "more" compatible with π E than r b , because it establishes that M and C are much better than S, while reward r b reverses the preferences. Clearly, we make a small error if we model the preferences of the expert with r g instead of the true reward r E . However, the notion of feasible set is completely blind to the difference between r g and r b at modeling r E , and it refuses both of them.We propose the following "soft" definition of (non)compatibility to capture this intuition. 6Definition 4.1 (Rewards (non)Compatibility). Let M Y tπ E u be an IRL instance, and let r P R be any reward. We define the (non)compatibility C p,π E : R Ñ R ě0 of reward r w.r.t. M Y tπ E u as:C p,π E prq :" J ˚pr; pq ´Jπ E pr; pq.In words, the (non)compatibility of reward r w.r.t. policy π E in problem M quantifies the suboptimality of π E in the MDP M Y tru. By definition, rewards r belonging to the feasible set (i.e., r P R p,π E ) satisfy C p,π E prq " 0, i.e., they have zero non-compatibility with π E in M. 7Example 4.1 (Continued). (Non)compatibility discriminates between r g and r b . Indeed, we have that C p,π E pr E q " 0, C p,π E pr g q " 0.01, and C p,π E pr b q " 2. In words, reward r g suffers from very small (non)compatibility, while r b suffers from large (non)compatibility, thus we say that reward r g is more compatible with π E than r b , as expected.By definition of IRL, the true reward r E makes the observed π E optimal, but reveals no information about the other policies. Thus, it is meaningful that C p,π E considers the suboptimality of π E only, because demonstrations from π E do not provide information about other policies, as illustrated below. Example 4.2. Let r 1 b be such that r 1 b pM q " `0.99, r 1 b pCq " ´1, r 1 b pSq " `1. Clearly, r 1 b is much worse than r g at modeling r E , because it does not capture the fact that the expert appreciates the cake but she hates the soup. However, demonstrations from π E alone do not provide information about C or S, but only about π E " M (i.e., the expert always eats the muffin). Thus, we have that C p,π E pr g q " C p,π E pr 1 b q " 0.01, i.e., r g and r 1 b are equally compatible with the given demonstrations.For a discussion on comparing the (non)compatibility of different rewards, see Appendix C.4.Our goal is to overcome the limitations of the feasible set highlighted in Section 3. 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 a tuple pM, π E , R, ∆q, where M is an MDP without reward, π E is the expert's policy, R Ď R is a set of rewards to classify, and ∆ P R ě0 is some threshold. The goal is to classify all and only the rewards r P R based on their (non)compatibility with π E in M w.r.t. ∆. In symbols: @r P R : if C p,π E prq ď ∆ then return True, else return False.An IRL algorithm takes in input a reward r P R and outputs a boolean saying whether C p,π E prq ď ∆.Given r P R, we output whether it makes the expert's policy π E at most ∆-suboptimal or not. Intuitively, we classify rewards in R based on how good π E performs w.r.t. them. A ∆-(non)compatible reward guarantees that, among its ∆-optimal policies, there is π E , but the optimal policy might be different from π E (see Appendix C.3 for how this relates to (forward) RL). Note that we allow for R ‰ R to manage scenarios in which we have some prior knowledge on r E , i.e., r E P R Ă R.Remark 4.1. Permitting non-zero (non)compatibility is equivalent to enlarging the feasible set. Let R " R, and define the set of rewards positively classified as R ∆ , i.e., R ∆ :" tr P R | C p,π E prq ď ∆u. For any ∆, ∆ 1 s.t. 0 ď ∆ ď ∆ 1 ď 2H, we have: R p,π E " R 0 Ď R ∆ Ď R ∆ 1 Ď R 2H " R.Discussion on Reward Compatibility. It should be remarked that:• The limits of the rewards compatibility framework are the same as the limits of the feasible set.We cannot identify r E from the feasible set or among the rewards with small (non)compatibility. As aforementioned, this is an inherent limit of IRL and cannot be overcome with a more refined objective formulation, unless further information on r E is available (e.g., preferences). • Rewards compatibility offers advantages over feasible set. Differently from the feasible set, as we will see in Section 5, 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.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 on its accuracy at estimating the (non)compatibility of the rewards, as formalized by the following PAC requirement. where P M,π E ,A is the joint probability measure induced by π E and A in M, and p C is the estimate of C p,π E computed by A. The sample complexity is defined by the pair pτ E , τ q. Intuitively, our goal is to estimate the (non)compatibility of the rewards in R with sufficient accuracy, so that, given a threshold ∆ ě 0, we are able to classify "most" of them correctly w.h.p. (with high probability). The concept is exemplified in Figure 2 . Note that the estimation problem is independent of the threshold ∆, which can be appropriately selected to cope with noise in the demonstrations, (unknown) expert suboptimality, or to manage the amount of "false negatives" and "false positives".Remark 4.2. For η ě 0, let R η :" tr P R | C p,π E prq ď ηu and p R η :" tr P R | p Cprq ď ηu denote the sets of rewards positively classified using, respectively, the true (non)compatibility C p,π E and the estimate p C constructed by an pϵ, δq-PAC algorithm. Then, with probability 1 ´δ, it holds that: p R ∆´ϵ Ď R ∆ Ď p R ∆`ϵ . Thus, we can trade-off the amount of "false negatives" (resp. "false positives") by, e.g., choosing the threshold ∆ Ð ∆ `ϵ (resp. ∆ Ð ∆ ´ϵ). 
caty-irl: a provably efficient algorithm for irl: 
 In this section, we present CATY-IRL (CompATibilitY for IRL), a provably efficient algorithm for solving the online IRL 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) an exploration phase, in which the algorithm explores the environment using the knowledge of R and of the expert's dataset D E to collect samples about the dynamics of the MDP, and (ii) a classification phase, in which it performs the classification of a reward r P R without interactions with the environment. A flow-chart is reported in Figure 1 (pseudocode in Appendix D).Exploration phase. The exploration phase collects a dataset D in a 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 P R (when |R| " Θp1q, i.e., 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 D E .Cprq of the (non)compatibility term C p,π E prq for the single input reward r P R by splitting it into two independent estimates: p J E prq « J π E pr; pq, which is computed with D E only, and p J ˚prq « J ˚pr; pq, which is computed with D only. Concerning p J E prq, when the reward is linear r h ps, aq " xϕps, aq, θ h y, CATY-IRL uses D E to construct an empirical estimate p ψ E « ψ p,π E of the expert's expected feature count [6] . Otherwise, it directly estimates p d E « d p,π E the expert's occupancy measure. Such estimates can be used to derive p J E prq straightforwardly. Regarding p J ˚prq, CATY-IRL exploits the planning phase of the corresponding RFE (or BPI) algorithm adopted at exploration phase. 8 Finally, CATY-IRL applies the (potentially negative) input threshold ∆ to the difference p J ˚prq ´p J E prq to perform the classification. See Appendix D 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 is computationally efficient in 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 ϵ, δ P p0, 1q. Then CATY-IRL is pϵ, δq-PAC for IRL with a sample complexity upper bounded by: Tabular MDPs:τ E ď r O ´H3 SA ϵ 2 log 1 δ ¯, τ ď r O ´H3 SA ϵ 2 ´N `log 1 δ ¯¯,Tabular MDPs with linear rewards:τ E ď r O ´H3 d ϵ 2 log 1 δ ¯, τ ď r O ´H3 SA ϵ 2 ´N `log 1 δ ¯¯,Linear MDPs:τ E ď r O ´H3 d ϵ 2 log 1 δ ¯, τ ď r O ´H5 d ϵ 2 ´d `log 1 δ ¯¯,where N " 0 if |R| " Θp1q, and N " S otherwise.Some observations are in order. We conjecture that the d 2 dependence when |R| " Θp1q is unavoidable 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 τ E from r OpSAH 3 logpδ ´1q{ϵ 2 q to r OpSH 3{2 logpδ ´1q{ϵ 2 q. Finally, note that the choice ∆ " ϵ allows us to positively classify all the rewards in the feasible set R p,π E w.h.p. and, in this case, other rewards positively classified have true (non)compatibility at most 2ϵ 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-IRL is 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.In CATY-IRL, 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 a 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 τ . Theorem 6.1 (IRL Classification -Lower Bound). Let A be an pϵ, δq-PAC algorithm for the IRL classification in tabular MDPs. Let τ be the number of exploration episodes. Then, there exists an IRL classification instance such that:if |R| ě 1 : τ ě Ω ˆH3 SA ϵ 2 log 1 δ ˙, if R " R : τ ě Ω ˆH3 SA ϵ 2 ´S `log 1 δ ¯˙.In both cases, the lower bound is matched by CATY-IRL, up to logarithmic factors. Note that CATY-IRL explores without using D E , thus, minimax optimality for τ can be achieved without the knowledge of D E at exploration phase. As a by-product, we observe that a similar lower bound construction can be made also for RFE, leading to the following result. Theorem 6.2 (RFE -Refined Lower Bound). Let A be an pϵ, δq-PAC algorithm for RFE in tabular MDPs. Let τ be the number of exploration episodes. Then, there exists an RFE instance such that:τ ě Ω ˆH3 SA ϵ 2 ´S `log 1 δ ¯˙.This bound improves the state-of-the-art RFE lower bound Ωp H 3 SA ϵ 2 p S H `log 1 δ qq (obtained combining the bounds in [21] and [12] ) by one H factor, and it is matched by RF-Express [37] .What is the most efficient exploration strategy that can be performed in an unknown environment? It depends on the subsequent task that shall be solved. However, if the task is unknown at the exploration phase, we need a strategy that suffices for all the tasks that one 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 as a subroutine, we conclude that the RFE exploration strategy is 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 a posteriori of the exploration phase? We believe so, and in Appendix E, we identify two additional problems, i.e., Matching Performance (MP) and Imitation Learning from Observations alone (ILfO) [34] , that represent potential candidates to belong to F .More in general, we formulate the Objective-Free Exploration (OFE) problem as follows: Definition 6.1 (Objective-Free Exploration). Given a tuple pM, F , pϵ, δqq, where M is an unknown environment (e.g., MDP without reward), and F is a certain class of tasks (e.g., all RL and IRL problems), 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 P F in an pϵ, δq-correct manner.This problem is called "objective-free" because it does not require the knowledge of the specific "objective" f P F to be solved. In Appendix F, we describe a use case for OFE. We believe this is an interesting problem to be studied in future. 
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 a 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-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 a novel lower bound to the IRL classification problem. As a by-product, our construction improves the current state-of-the-art lower bound for RFE. Finally, we have introduced OFE, a unifying problem setting for exploration problems, which generalizes both RFE and IRL.Limitations. A 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. Nevertheless, while the rewards compatibility framework is general and not tied to Linear MDPs, we believe that Linear MDPs represent an important initial step toward the development of provably efficient IRL algorithms with more general function approximation structures. Although a lower bound for Linear MDPs is 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 to extend the notion of reward compatibility to other kinds of expert feedback (in the context of ReL), and to other IRL settings (e.g., suboptimal experts). Finally, we believe that OFE should be analysed in-depth given its practical importance.[65] Christian Wirth, Riad Akrour, Gerhard Neumann, and Johannes Fürnkranz. A survey of preference-based reinforcement learning methods. Journal of Machine Learning Research, 18:1-46, 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. In 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. In AAAI Conference on Artificial Intelligence 23 (AAAI), pages 1433-1438, 2008. 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification: The research conducted in the paper does not harm human subjects or participants, and there are no data-related concerns. In addition, we believe that there are no noteworthy potential harmful consequences of our research.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 a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
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 not tied to particular applications. In addition, we believe that there is no direct path to any negative applications.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
 
 Appendix: In this appendix, we report and describe the literature that most relates to this paper. Theoretical works concerning the online IRL 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. [33] focuses on the same problem as [39] , but adopts a forward model in tabular MDPs. By adopting RFE exploration algorithms, they devise sample efficient algorithms. However, as remarked in [68], the learning framework considered in [33] suffers from a major issue. [38] builds upon [39] to construct the first minimax lower bound for the problem of estimating the feasible set using a generative model. The lower bound is in the order of Ω `H3 SA ϵ 2 pS `log1 δ q ˘,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 a single optimal expert and multiple suboptimal experts with known suboptimality. [31] analyse the problem of estimating the feasible set when no active exploration of the environment is allowed, but the learner is given a batch dataset collected by some behavior policy π b . Interestingly, [31] focuses on two novel learning targets that are suited for the offline setting, i.e., a subset and a superset of the feasible set. Authors in [31] 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 [31] , 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 β-strict separable problems in the tabular setting. However, both the setting considered and the bound obtained are fairly different from ours. Analogously, [11] provides a sample efficient IRL algorithm for β-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.In this section, we collect additional related works that deserve to be mentioned.Identifiability and Reward Learning. As aforementioned, the IRL problem is 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 [70, 15] . Such setting is in some sense easier than the common IRL setting, because entropy-regularization permits a unique optimal policy for any reward function.[10] 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.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 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 RL literature. [20] introduces the notion of Bellman rank as complexity measure, and provides a sample efficient algorithm for problems with small Bellman rank. [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 a provably efficient algorithm.[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 introduced in [21] , where authors provided a sample efficient algorithm and a lower bound for tabular MDPs. Later on, the state-of-the-art sample-efficient algorithms for RFE in tabular MDPs have been developed in [24, 37, 32] . It should be remarked that RFE requires more samples than common RL in tabular MDPs. [63] proposes a sample efficient algorithm for RFE in linear MDPs. [62] improves the algorithm of [63] 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 of the deterministic expert's policy in tabular MDPs, presented in [47] . We mention also [46, 59] for the sample complexity of estimating the expert's policy in problems with linear function approximation. In the context of Imitation Learning from Observation alone (ILfO) [34] , the work [57] proposes a 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 a classification approach for IRL. However, this is fairly different from our IRL problem formulation in Section 4.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 3, while in Appendix B.4 we collect all the missing proofs of this section.The following examples aim to explain Proposition 3.1 in a simple manner.Example B.1 (Non-degenerate feasible set). Let M " pS, A, H, d 0 q Y tπ E u be an IRL instance such that S " ts 1 , s 2 u, A " ta 1 , a 2 u, H " 1, d 0 ps 1 q " d 0 ps 2 q " 1{2, π E ps 1 q " π E ps 2 q " a 1 .Consider the feature mapping ϕ 1 s.t. ϕ 1 ps, aq " 1ta " a 1 u for all s P S. Then, we have Φ π E " t1u and Φ " t0u. Clearly, these sets can be separated by any hyperplane w P R ą0 , since 1 ¨w ą 0 ¨w, and so R p,π E ‰ tru, with r h ps, aq " 0 @ps, a, hq P S ˆA ˆ H . Actually, R p,π E " tr P R | Dθ P p0, 1s : r 1 ps, aq " xϕps, aq, θy @ps, aq P S ˆAu.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 ps 1 , aq " 1ta " a 1 u, and ϕ 2 ps 2 , aq " 1ta " a 2 u. Then, we have Φ π E " t0, 1u and Φ " t0, 1u. Clearly, the two sets coincide, thus they cannot be separated, and R p,π E " tru, with r h ps, aq " 0 @ps, a, hq P S ˆA ˆ H .In tabular MDPs with small state space S, collecting samples from every state s P S is feasible, and it is exactly what previous works do:• Under the assumption that π E is deterministic, [39, 38] collect one sample from every ps, hq P S ˆ H using a generative model, obtaining π E exactly.• If π E is stochastic, under the assumption that all actions in the support of the expert's policy are played with probability at least π min (see Assumption D.1 of [38] ), both [38, 68] are able to learn the support of π E exactly w.h.p. using 91{π min samples in the online setting.9 • In the offline setting, assuming that the occupancy measure of the expert's policy is at least d min in all reachable ps, aq P S ˆA, then [31] learns the support of π E exactly w.h.p. using 91{d min 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 Y tπ E u be a Linear IRL instance with finite state space S and deterministic expert's policy, and let ϵ, δ P p0, 1q. If an algorithm A is pϵ, δq-PAC, then τ E " ΩpSq, where S :" |S| is the cardinality of the state space.Theorem 3.2 tells us that the Linear MDP assumption is too weak for the feasible set to be learnable using the PAC framework of Definition 3.2 with a 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 Y tπ E u 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: @ps, a, s 1 q P S ˆA ˆS : }ϕps, aq ´ϕps 1 , aq} 2 ď L}s ´s1 }, for some L ą 0 and some distance } ¨´¨} in S.We devise another assumption to attempt to fix this issue. Assumption B.2. We assume the following Lipschitz continuity property: @ps, s 1 q P S ˆS : }ϕps, π E h psqq ´ϕps 1 , π E h ps 1 qq} 2 ď L}s ´s1 }, for some L ą 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 π E , so that when the expert lies in s 1 which is really close to s, then she plays an action which has the same "effect" (i.e., same transition model and same reward, due to the Linear MDP assumption) as the expert's action in s.Assumption B.2 is not comparable with Assumption B.1 since, on the one hand, it does not hold for all actions in A, but only for those corresponding to π E , but, on the other hand, provides information on how to transfer knowledge about π E to neighbor states.Let ∆ 1 :" min sPS,a,a 1 PA:ϕps,aq‰ϕps,a 1 q }ϕps, aq ´ϕps, a 1 q} 2 , i.e., the smallest non-zero distance between the features of different actions. Clearly, when S is finite, since in Linear MDPs also A :" |A| is finite, then ∆ 1 is finite too. So we can define a new quantity ∆ to be any number0 ă ∆ ă ∆ 1 .Proposition B.2. Under the setting of Proposition 3.2, under Assumption B.2, then a number of samples τ E " |N p ∆ 2L ; S, } ¨}q| is sufficient to recover π E exactly in any ps, hq P S, where |N p ∆ 2L ; S, } ¨}q| is the ∆{p2Lq-covering 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 action in the neighborood of each state of the covering. Doing so, we are able to construct ϵ-correct estimates of the feasible set. Of course, this is possible as long as ∆ 1 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 in which ∆ 1 Ñ 0, and so the approach would still require too many samples.However, even for cases with finite and not too small ∆ 1 , the result in Proposition B.2 is not satisfactory, because it just allows to retrieve π E under a stronger assumption than Linear MDPs, but not to perform an interesting learning process. We observe that the feasible set is an "unstable" concept, in the sense that, based on Proposition 3.1, changing the expert action in a single state might reduce the feasible set from a continuum of rewards to a singleton, or vice versa. Remark B.1. If we want to be able to recover the exact feasible set efficiently, we need to recover the exact expert's policy almost everywhere.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 p p, that can be used to compute an "empirical" estimate of the feasible set p R « R p p,π E (since ϕ and π E are known). The algorithm is presented in Algorithm 1.Algorithm 1: IRL for Linear MDPs (known expert's policy) Data: failure probability δ ą 0, error tolerance ϵ ą 0, expert policy π E , all sets Z Ď S ˆ H that coincide with S p,π E almost everywhere based on measure d p,π E D Ð RFE_Explorationpδ, ϵq /* Various choices */ for h in tH, H ´1, . . . , 2, 1u doΛ h Ð I `τ ř k"1 ϕps k h , a k h qϕps k h , a k h q ⊺ p µ h p¨q Ð Λ ´1 h τ ř k"1 ϕps k h , a k h qδp¨, s k h`1 q end p p h p¨|s, aq Ð xϕps, aq, p µ h p¨qy for all ps, a, hq P S ˆA ˆ H p R Ð ␣ p r P R ˇˇDZ, @ps, hq P Z, @a P A : E a 1 "π E h p¨|sq Q hps, a 1 ; p p, p rq ě Q hps, a; p p, p rq (Simply put, Algorithm 1 uses the dataset collected by an RFE algorithm to compute a least-squares estimate of the transition model p p, and then it returns the feasible set defined according to it (recall that ϕ and π E are known). Notice that this algorithm cannot be implemented in practice due to various reasons, like the presence of the Dirac delta δ measure in the definition of some quantities (see Appendix B.4.3), and the fact that the feasible set is, potentially, a set containing infinite rewards. Nevertheless, Theorem 3.3 states that this algorithm is sample efficient. The proof of the theorem is provided in Appendix B.4.3.It should be remarked that Algorithm 1 takes in input also the true support of the visit distribution of the expert policy S p,π E in case S is finite, and all the possible sets Z that agree with S p,π E a.e. based on the measure d p,π E in case S is infinite. Intuitively, this set (S p,π E ) of ps, hq pairs represents the domain in which π E is defined. Indeed, since the expert in the true problem p never visits pairs ps 1 , h 1 q R S p,π E , its expert policy might reasonably be non well-defined there. When S is infinite, we require all sets Z because otherwise we cannot know which are the sets S p,π E zZ with zero measure, i.e., in which the reward can induce an 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 1 of [62] at Line 1 of Algorithm 1. In Appendix B.4.3, we demonstrate an upper bound also if we use Algorithm 1 in [63] .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. [31] ). In the setting of Definition 3.1, if S is finite, then the feasible set R p,π E satisfies: R p,π E " ! r P R ˇˇ@ps, hq P S p,π E , @a P A :Lemma B.3 (Lemma E.1 inE a 1 "π E h p¨|sq Q hps, a 1 ; p, rq ě Q hps, a; p, rq) .Notice that we have extended Lemma E.1 in [31] to 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, then the feasible set R p,π E satisfies:R p,π E " ! r P R ˇˇ@h P H , DS Ď S p,π E h : d p,π E h pSq " 0 ^@s R S, @a P A : E a 1 "π E h p¨|sq Q hps, a 1 ; p, rq ě Q hps, a; p, rq) .Simply, Lemma B.4 improves on Lemma B.3 by allowing the reward to enforce the "wrong" action (i.e., different from the expert's action) in a subset with zero measure based on the visitation distribution.Proof. The proof is completely analogous to that of Lemma E.1 in [31] . We just need to observe that if set S has zero measure (and the set of rewards R contains bounded rewards), then it does not affect the expected return.Another useful property that we 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 tw π h u hP H such that, for any ps, a, hq P S ˆA ˆ H , we have Q π h ps, aq " xϕps, aq, w π h y.We can combine the results of Lemma B.4 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 feasible set R p,π E satisfies:R p,π E " ! r PR ˇˇDtwhu hP H , @ps, a, hq P S ˆA ˆ H : r h ps, aq " xϕps, aq, θ h y ^@h P H , DS Ď S p,π E h : d p,π E h pSq " 0 ^@s R S, @a E P A E h psq : xϕps, a E q, w h y " max aPA xϕps, aq, w h y ) ,where θ h :" w h ´şS max a 1 PA xϕps 1 , a 1 q, w h`1 ydµ h ps 1 q for all h P H , and A E h psq :" ta P A|π E h pa|sq ą 0u.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 Q-function Q ˚is linear in the feature map too. So, there exist parameters tw h u h such that, for any ps, a, hq P S ˆA ˆ H , the optimal Q-function can be rewritten as Q hps, aq " xϕps, aq, w h y. From the Bellman equation, we know that:Q hps, a; p, rq " r h ps, aq `ż S V h`1 ps 1 ; p, rqdp h ps 1 |s, aq " xϕps, aq, θ h y `xϕps, aq,ż S max a 1 PAxϕps 1 , a 1 q, w h`1 ydµ h ps 1 qy.By rearranging this equation, and removing the dot product with ϕps, aq, we obtain that:θ h " w h ´żS max a 1 PA xϕps 1 , a 1 q, w h`1 ydµ h ps 1 q.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 tw h u h outside some S. This concludes the proof.It is useful to introduce the following definitions. First we define the set of parameters that induce a Q-function compatible with π E :W p,π E :" ! w : H Ñ R d ˇˇ@h P H , DS Ď S p,π E h : d p,π E h pSq " 0 ^@s R S, @a E P A E h psq : xϕps, a E q, w h y " max aPA xϕps, aq, w h y ) .Next, we define the set of parameters of the reward function obtained by using Q-functions parametrized by w P W p,π E :Θ p,π E :" ! θ : H Ñ R d ˇˇDtwhuh P W p,π E : θ h " w h ´żS max a 1 PA xϕps 1 , a 1 q, w h`1 ydµ h ps 1 q ) .Irrespective of the transition model tµ h u h and the feature map ϕ, we see that it is always possible to construct a surjective map from Θ p,π E to W p,π E (the map in the definition of Θ p,π E ). Thanks to these definitions, the feasible set can be rewritten as: R p,π E " tr P R | Dtθ h u h P Θ p,π E , @ps, a, hq P S ˆA ˆ H : r h ps, aq " xϕps, aq, θ h yu.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 a finite state space, and let ϕ be a feature mapping. Let tΦ π E h u hP H and tΦ h u hP H be the sets of expert's and non-expert's features, defined for every h P H as:Φ π E h :" ␣ ϕps, a E q | s P S p,π E h , a E P A E h psq ( , Φ h :" ␣ ϕps, aq | s P S p,π E h , a P AzA E h psq ( ,where A E h psq :" ta P A|π E h p¨|sq ą 0u for every s P S. If for none of the H pairs of sets pΦ π E h , Φ h q there exists a separating hyperplane, then R p,π E " tru, with r h ps, aq " 0 @ps, a, hq P S ˆA ˆ H i.e., the feasible set with linear rewards in ϕ contains only the reward function that assigns zero reward everywhere.Proof. From [8] , we recall that two sets Y 1 , Y 2 are separated by a hyperplane H " tx|a ⊺ x " bu if each lies in a different closed halfspace associated with H, i.e., if either:a ⊺ y 1 ď b ď a ⊺ y 2 , @y 1 P Y 1 , @y 2 P Y 2 ,or:a ⊺ y 2 ď b ď a ⊺ y 1 , @y 1 P Y 1 , @y 2 P Y 2 .By definition of W p,π E , for each stage h P H , we are looking for vectors w h P R d such that @ps, hq P S p,π E , it holds that:w ⊺ h ϕps, aq ď w ⊺ h ϕps, a E q @a E P A E h psq, @a P AzA E h psq.In words, for each ps, hq P S p,π E , we are looking for non-affine separating hyperplanes between features of expert and non-expert actions. However, since the hyperplane parameter w h is common to all states s P S p,π E h , then it must separate expert from non-expert actions at all states. This is equivalent to finding the separating hyperplanes to the sets Φ π E h and Φ h which contain all the points. Clearly, when the separating hyperplanes do not exist at all h P H , then the condition in W p,π E is satisfied by the zero vector alone. As a consequence, set Θ p,π E contains only the zero vector, and so does R p,π E . Remark B.2. By using the result of Lemma B.4, 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 explicitly. where: M r,p r :" maxt? d, max hP H }θ h } 2 , max hP H } p θ h } 2 u{ ? d,where tθ h u h and t p θ h u h are the (unbounded) parameters of rewards r and p r. As explained in [31] , 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 θ of the rewards to avoid the issue described in [38] and [31] . We still assume that the feature mapping is bounded. Observe that this relaxation does not affect the results we present, which would hold even if we considered bounded parameters θ. Indeed, as visible in the proofs, the instances do not need to be constructed with unbounded θ. Theorem 3.2 (Statistical Inefficiency). Let M Y tπ E u be a Linear IRL instance with finite state space S and deterministic expert's policy, and let ϵ, δ P p0, 1q. If an algorithm A is pϵ, δq-PAC, then τ E " ΩpSq, where S :" |S| is the cardinality of the state space.Proof. We construct two problem instances that lie at a finite Hausdorff distance, and show that, with less than S calls to the sampling oracle, we are not able to discriminate between the two instances.Let S be the finite state space with cardinality S, A " ta 1 , a 2 u, H " 1, d 0 psq " 1{S @s P S, ϕps, aq " 1ta " a 1 u, and consider two deterministic expert's policies π E 1 psq " a 1 @s P S, and π E 2 psq " a 1 @s P Sztsu, and π E 2 psq " a 2 , for a certain s P S. The set of parameters compatible with π E 1 is:Θ p,π E 1 " tθ P R | θ ě 0u, since Q π E 1 ps, a 1 q ě Q π E1 ps, a 2 q ðñ rps, a 1 q ě rps, a 2 q ðñ ϕps, a 1 qθ ě ϕps, a 2 qθ ðñ 1 ¨θ ě 0 ¨θ. Observe that, for π E 2 , due to the presence of s, we have: Θ p,π E 2 " tθ P R | θ " 0u, since s imposes θ ď 0, and the other states impose θ ě 0.Therefore, the Hausdorff distance between the two problems is:HpR π E 1 , R π E 2 q " sup θě0 1 maxt1, θ, 0u θ " sup θě0 1 maxt1, θu θ " 1.Obviously, we need a ΩpSq samples to spot, if it exists, state s, and thus distinguish between R π E Proof. The same proof of Proposition 3.2 works here.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: HpR π E 1 , R π E 2 q " sup θ1ě0 inf θ2"0 1 maxt1, θ 1 ,, π E h psqq ´ϕps 1 , π E h ps 1 qq} 2 ď L}s 1 ´s} ď ∆ 2 ,and since π E h ps 1 q and thus ϕps 1 , π E h ps 1 qq is known, then the fact that ∆ is finite guarantees us that π E h psq is equal to the action a that minimizes the distance to ϕps 1 , π E h ps 1 qq. Notice that if, by contradiction, there were two actions a 1 , a 2 with }ϕps, a 1 q ´ϕps 1 , π E h ps 1 qq} 2 ď ∆ 2 and }ϕps, a 2 q φps 1 , π E h ps 1 qq} 2 ď ∆ 2 , then by triangle inequality and finiteness of ∆, we would have: ∆ ă }ϕps, a 1 q ´ϕps, a 2 q} 2 ď }ϕps, a 1 q ´ϕps 1 , π E h ps 1 qq} 2 `}ϕps,a 2 q ´ϕps 1 , π E h ps 1 qq} 2 ď ∆ 2 `∆ 2 " ∆,which is clearly a contradiction.The proof is based on deriving an upper bound to the Hausdorff distance between the true feasible set and its estimate. To do so, first, using the notation of [23] , let us define the following quantities:P h p¨|s, aq :" xϕps, aq, µ h p¨qy,p P h p¨|s, aq :" ϕps, aq ⊺ Λ ´1 h τ ÿ k"1 ϕps k h , a k h qδp¨, s k h`1 q, P h p¨|s, aq :" ϕps, aq ⊺ Λ ´1 h τ ÿ k"1 ϕps k h , a k h qP h p¨|s k h , a k h q,where δp¨, xq is the Dirac measure, and ps k h , a k h q represents the state-action pair visited at stage h of exploration episode k P τ . In words, P denotes the true transition model, p P denotes the least squares estimate computed by Algorithm 1, and P represents a bridge between the two. As we will see, the core of the proof consists in upper bounding the term ˇˇ`P h ´p P ˘Vh`1 ps, aq ˇˇat all h P H and reachable ps, aq P S ˆA, for all the bounded linear functions V in class V, defined as:EQUATIONTo achieve this goal, it will be useful to apply triangle inequality and to bound the following two terms separately: ˇˇ`Ph ´p P ˘Vh` ) .Proof. We have:EQUATION" ϕps, aqEQUATION" ϕps, aqEQUATION" ϕps, aq⊺ Λ ´1 h " τ ÿ k"1 ϕps k h , a k h qP h V h`1 ps k h , a k h q ´τ ÿ k"1 ϕps k h , a k h qP h V h`1 ps k h , a k h q ´r w h ı " ´ϕps, aq ⊺ Λ ´1 h r w h ,where at (1) we have defined vector r w h :" ş S V h`1 ps 1 qdµ h ps 1 q, at (2) we have used the definition of Λ h , and at (3) we have recognized that ϕps k h , a k h q ⊺ r w h " P h V h`1 ps k h , a k h q. By taking the absolute value, we can write:ˇˇ`Ph ´Ph ˘Vh`1 ps, aq ˇˇ" ˇˇϕps,aq ⊺ Λ ´1 h r w h ˇ(4) ď } r w h } Λ ´1 h }ϕps, aq} Λ ´1 h (5) ď } r w h } 2 }ϕps, aq} Λ ´1 h (6) ď H ? d}ϕps, aq} Λ ´1 h ,where at (4) we have applied Cauchy-Schwarz's inequality, at (5) we have bounded the quadratic form with the 2-norm and the largest eigenvector of the matrix, i.e., } rw h } Λ ´1 h " b r w ⊺ h Λ ´1 h r w h ď ? σ} r w h } 2 ,where σ is the largest eigenvalue of matrix Λ ´1 h , and then we have upper bounded σ ď 1, since 1 is the smallest eigenvalue of invertible matrix Λ h (see [23] ); finally, at (6) we have used the fact that |V h`1 p¨q| ď H, and so that } rw h } 2 " } ş S V h`1 ps 1 qdµ h ps 1 q} 2 ď H}µ h pSq} 2 ď H ? d.The result follows by noticing that the quantity to bound cannot be larger than 2H.Lemma B.8. Let δ P p0, 1q. For any value function V in the class V, for any ps, a, hq P S ˆA ˆ H , with probability at least 1 ´δ{2, it holds that: ˇˇ´p P h ´Ph ¯Vh`1 ps, aq ˇˇď min " cHc d log `1 `τ ˘`log H δ }ϕps, aq} Λ ´1 h , 2H * ,for some constant c.Proof. We can write: ˇˇ´p P h ´Ph ¯Vh`1 ps, aq ˇˇ" ˇˇˇϕ ps,aq ⊺ Λ ´1 h τ ÿ k"1 ϕps k h , a k h q " V h`1 ps k h`1 q ´Ph V h`1 ps k h , a k h q ı ˇˇ( 1) ď › › › τ ÿ k"1 ϕps k h , a k h q " V h`1 ps k h`1 q ´Ph V h`1 ps k h , a k h q ı› › › Λ ´1 h › › ›ϕps, aq › › › Λ ´1 h (2) ď c 4H 2 ´d 2 logp1 `τ q `log 2N ϵ δ ¯`8τ 2 ϵ 2 › › ›ϕps, aq › › › Λ ´1 h (3) ď d 4H 2 ´d 2 logp1 `τ q `2d log ´1 `H? d ϵ ¯`log 1 δ ¯`8τ 2 ϵ 2 › › ›ϕps, aq › › › Λ ´1 h (4) " c 4H 2 ´d 2 logp1 `τ q `2d log ´1 `4τ ¯`log 1 δ ¯`8H 2 d › › ›ϕps, aq › › › Λ ´1 h (5) ď cH c d logp1 `τ q `log 1 δ › › ›ϕps, aq › › › Λ ´1 h, where at (1) we have applied Cauchy-Schwarz's inequality, at (2) we have applied Lemma B.13, at(3) we have upper bounded N ϵ using Lemma B.12, at (4), similarly to [62] , unlike [23] , we see that no union bound is needed (because there is no dependence on Λ), thus by choosing ϵ " H ? d{τ , we get the passage. Passage (5) follows for some constant c.The result follows by a union bound over h P H , and by noticing that the quantity to bound cannot be larger than 2H.We are now ready to upper bound the Hausdorff distance using the two lemmas just presented. Recall that we work with unbounded rewards (parameters θ), and that the definition of inner distance d is provided in Equation (1). Lemma B.9. With probability at least 1 ´δ{2, the Hausdorff distance between the true feasible set R p,π E and its estimate p R returned by Algorithm 1 can be upper bounded by: ? du, 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 p,π E normalized by K are a subset of the value functions in class V, i.e., of all the possible optimal value functions with parameters }w h } 2 ď 2H ? d. This is not trivial since we are working with unbounded rewards r, and thus their parameters tθ h u h can be any. The normalization by K permits this in the following manner. For any h P H , we have r h p¨, ¨q{K " xϕp¨, ¨q, θ h {Ky " xϕp¨, ¨q, θ h { maxt1, max h 1 }θ h 1 } 2 { ? duy. Therefore, if max h 1 }θ h 1 } 2 ą ? d, then the normalization makes sure that max h 1 }θ h 1 } 2 " ? d, while if max h 1 }θ h 1 } 2 ď ? d, then the normalization is by 1 and it has no effect. In this way, we see that value functions V h`1 ps, a; p, r K q can be created by a simple r 1 with parameters tθ 1 h u h with 2-norms bounded by ? d. This guarantees that, since by hypothesis of Linear MDPs }ϕp¨, ¨q} 2 ď 1, the value function never exceeds H, and that the norm of the Q-function parameters tw π h u h for any policy π can be bounded as: [23] ). It should be remarked that class V is more general than the actual set of optimal value functions that can be obtained using r P R p,π E in p, since such rewards induce optimal value functions for which the optimal action in S p,π E is always the expert's action/s π E psq.HpR p,}w π h } 2 ď }θ h {K} 2 `} ş S V π h`1 ps 1 qdµ h ps 1 q} 2 ď ? d `H}µ h pSq} 2 ď ? d `H? d ď 2H ? d (simi- larly to Lemma B.1 ofNotice 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: 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, at (9) we have applied Lemma B.7 and Lemma B.8 and used some absolute constants c 1 , c 2 ą 0, and also the fact that for any numbers x, y, w, z, we have mintx, yu `mintw, zu ď mintx `w, y `zu.H d pR p,To conclude the proof of the main theorem, we simply have to observe that any RFE algorithm provides a bound to J ˚pu 1 ; pq for some u 1 similar to u. Depending on the RFE algorithm instantiated as sub-routine, the sample complexity of Algorithm 1 varies.Theorem 3.3. Assume that π E (along with its support S p,π E ) is known. Then, for any ϵ, δ P p0, 1q, Algorithm 1 is pϵ, δq-PAC for IRL with a number of episodes τ upper bounded by:τ ď r O ´H5 d ϵ 2 ´d `log 1 δ ¯¯.Proof. To get the result, we instantiate Algorithm 1 of [62] as RFE sub-routine. Simply, observe that [62] sets β 1 so that β 1 ě r β :" c 1 H a d logp1 `dHτ q `logpH{δq ě β. By Lemma B.9, we know that:HpR p,π for some absolute constant c 1 ą 0. It should be remarked that the quantity in the last line is, modulo c 1 , the quantity that [62] bound in the proof of their Theorem 1 using their algorithm. Specifically, by taking:τ ď r O ˆH5 d ϵ 2 ´d `log 1 δ ¯`H 6 d 9{2 ϵ log 4 1 δ ˙,and a union bound over the two events that hold w.p. 1 ´δ{2, and re-setting ϵ Ð c 1 ϵ, we get the result.Notice that if we run Algorithm 1 of [63] for exploration instead of Algorithm 1 of [62] , we obtain:Theorem B.10. If we use Algorithm 1 of [63] at Line 1 of Algorithm 1, then for any ϵ, δ P p0, 1q, such algorithm is pϵ, δq-PAC for IRL with a number of episodes τ upper bounded by:τ ď r O ˆH6 d 3 ϵ 2 log 1 δ ˙.Proof. By Lemma B.9, we know that: , Hu for all ps, a, hq P S ˆA ˆ H , and β 1 :" c 1 dH a logpdH{δ{ϵq for some absolute constant c 1 ą 0. In addition, set the number of exploration episodes τ to τ " c 2 d 3 H 6 logpdHδ ´1ϵ ´1q{ϵ 2 , and notice that, for appropriate choices of c 1 , c 2 , it holds that: β 1 ě c 1 dH a logpdHτ {δq ě β :" cH a d logp1 `τ q `logp1{δq. This entails that u 1 h ps, aq ě u h ps, aq at all s, a, h, and so: HpR p,π E , p Rq ď cJ ˚pu 1 ; pq " cHJ ˚pu 1 {H; pqHpR p,ď c 1 Hd d 3 H 4 log dτ H δ τ (2) ď c 2 ϵ,where at (1) we have applied Lemma 3.2 of [63] (reported in Lemma B.14 for simplicity) with some new constant c 1 ą 0, and at (2) we have simply replaced τ with its value defined in Algorithm 1 of [63] .The result follows by union bound between the two events that hold w.p. The proof of the opposite case is completely analogous.In the case with infinite S, notice that both the feasible set R p,π E in Lemma B.4 and the definition of p R in Algorithm 1 make use of the same sets Z. Thus, we simply make the choice of reward with same Z and proceed like in the finite case.Lemma B.12 (Covering Number of Class V). Let V be defined as in Equation (2), and define distance dist in V as distpV, V 1 q :" sup sPS |V psq ´V 1 psq|. Then, the ϵ-covering number |N pϵ; V, distq| of set V with distance dist can be bounded as:log |N pϵ; V, distq| ď d log ´1 `4H ? d ϵ ¯.Proof. The proof follows that of Lemma D.6 of [23] , but is simpler because of the different form of V.For any V 1 , V 2 P V parametrized by w 1 , w 2 , we write: distpV 1 , V 2 q " supď max ps,aqPSˆA ˇˇϕps, aq ⊺ pw 1 ´w2 q ˇ( 2) ď sup ϕ:}ϕ}2ď1 ˇˇϕ ⊺ pw 1 ´w2 q ˇ( 3) " }w 1 ´w2 } 2 ,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 two functions, at (2) we have used the fact that the feature map is always bounded by 1 in 2-norm, and at (3) Lemma B.13 (Lemma D.4 of [23] ). Let ts k u 8k"1 be a stochastic process on state space S with corresponding filtration tF k u 8 k"0 . Let tϕ k u 8 k"0 be an R d -valued stochastic process where ϕ k P F k´1 , and}ϕ k } 2 ď 1. Let Λ τ " I `řτ k"1 ϕ k ϕ ⊺ k .Then, for any δ ą 0, with probability at least 1 ´δ, for all τ ě 0, and any V P V so that sup sPS |V psq| ď H, we have:› › › › τ ÿ k"1 ϕ k ´V ps k q ´E " V ps k q|F k´1 ‰ ¯› › › › Λ ´1 τ ď 4H 2 " d 2 logp1 `τ q `log N ϵ δ ı `8τ 2 ϵ 2 ,where N ϵ is the ϵ-covering number of V with respect to the distance distpV, V 1 q :" sup sPS |V psq V 1 psq|.Lemma B.14 (Lemma 3.2 of [63] ). With probability 1´δ{2, for the function u 1 defined as u 1 h ps, aq :" min ␣ β 1 }ϕps, aq} Λ ´1 h , H ( , with β 1 :" c 1 dH a logpdHδ ´1ϵ ´1q, we have:J ˚pu 1 {Hq ď c d d 3 H 4 log dτ H δ τ ,for some absolute constant c ą 0.In this appendix, we collect and describe additional insights to the notion of rewards compatibility introduced in Section 4. The appendix is organized in the following manner: Appendix C.1 provides a visual explanation to the notion of rewards compatibility, in Appendix C.2 we analyse a multiplicative alternative to the definition of rewards compatibility, and Appendix C.3 discusses the conditions under which a learned reward can be used for "forward" RL, by comparing rewards with small (non)compatibility with rewards learned in previous works.In this appendix, we aim to provide a visual intuition to the notion of rewards compatibility. For this reason, the reader should keep in mind Figure 3 .d p,π1d p,π2 . . . As explained in Section 4, even in the limit of infinite samples, i.e., even if we know M " pS, A, H, d 0 , pq Y tπ E u exactly, and even if we assume that the expert is exactly optimal, i.e.,d p,π E d p,π d p,π EJ ˚pr E ; pq ´Jπ E pr E ; pq " 0 (where r E is the true reward optimized by the expert), then we still do not have idea of how other policies perform. Expert demonstrations only provide information about the performance of a single policy, π E , w.r.t. to the reference J ˚pr E ; pq under the unknown r E , i.e., demonstrations say that π E in r E performs as good as J ˚pr E ; pq. But what about other policies? Demonstrations provide no information.To see this, consider Figure 3 , in which each line exemplifies the visitation distribution induced by some policy π P Π, and the point in the middle represents the starting state s 0 " d 0 . Intuitively, observing d p,π E along with knowing that J π E pr E ; pq is good (i.e., because of expert demonstrations), does not tell us anything about the distribution d p,π induced by some other policy π potentially arbitrarily different from d p,π E . Indeed, it might be the case that J π pr E ; pq is acceptable, or that it is as good as J π E pr E ; pq, or that it is very bad. We cannot know from demonstrations only.For this reason, if we consider the set of rewards with 0-(non)compatibility, i.e., the feasible reward set, we notice that it contains the rewards r that make π optimal J π pr; pq " J ˚pr; pq, but also the rewards r 1 that make π nearly optimal J π pr 1 ; pq « J ˚pr 1 ; pq, and also the rewards r 2 that make π a very bad-performing policy J π pr 2 ; pq ! J ˚pr 2 ; pq. Indeed, as long as both r, r 1 , r 2 make the direction pointed by d p,π E in Figure 3 a good direction, then they are in accordance with the constraint imposed by the demonstrations. The additional Degrees of Freedom (DoF) provided by policies beyond π E (e.g., π, . . . ) permit the ill-posedness of IRL.We said that expert demonstrations provide information just about the performance of a single policy, π E . However, to 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 π E is a very good-performing policy, in IRL we assume that the underlying problem is an MDP, i.e., that the expert agent is optimizing a reward function r E . 10 This additional structure (i.e., that the underlying environment is indeed an MDP), makes sure that the performances of various directions d p,π in Figure 3 are measured through a dot product with a fixed reward function r, i.e.:J π pr; pq " ÿ hP H xd p,π h , r h y.For this reason, we have the guarantee that the directions in the red area surrounding d p,π E are almost as good as d p,π E . Indeed, for all policies π such that ř hP H }d p,π h ´dp,π E h } 1 ď ϵ, i.e., for all policies 10 When this assumption does not hold, we incur in model misspecification [55, 51] .ϵ-close to π E in 1-norm, we can write:|J π E pr E ; pq ´Jπ pr E ; pq| " ˇˇÿ hP H xd p,π E h ´dp,π h , r E h y ˇˇď ÿ hP H }d p,π h ´dp,π E h } 1 ď ϵ.In other words, policies π and π E 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 1-norm), and so we do not risk to incur in the error of representing d p,π E and a direction d p,π inside the red area of Figure 3 with very different performances.In Section 4, we have defined an additive notion of (non)compatibility, based on the difference of performance between π E and π ˚(the optimal policy). Here, we analyze a multiplicative notion of (non)compatibility, based on the ratio of the performances. 11We make the following observation. Any reward r P R induces, in the considered environment p, an ordering in the space of policies Π, based on the performance J π pr; pq of each policy π P Π. It is easy to notice that for any scaling and translation parameters α P R ą0 , β P R, the reward constructed as r 1 p¨, ¨q " αrp¨, ¨q `β induces the same ordering as r in the space of policies. 12For this reason, it seems desirable to use a notion of (non)compatibility such that rewards r and r 1 p¨, ¨q " αrp¨, ¨q `β for some α, β, suffer from the same (non)compatibility w.r.t. some expert policy π E . However, observe that, for the notion of compatibility C in Definition 4.1, we have that, for any r P R:C p,π E pr `βq " C p,π E prq @β P R, C p,π E pαrq " αC p,π E prq ‰ C p,π E prq @α P R ą0 .Simply put, for the additive notion of (non)compatibility C, the scale (α) of a reward matters, and rescaling the reward modifies the (non)compatibility.To solve this issue, one might introduce a multiplicative notion of compatibility F (defined only for non-negative rewards and setting F p,π E prq " 0 when the denominator is 0): F p,π E prq :" J π E pr; pq J ˚pr; pq .Clearly, the larger F p,π E prq, the closer is the performance of π E to the optimal performance. Observe that, for this definition,we have:F p,π E pαrq " F p,π E prq @α P R ą0 F p,π E pr `βq ‰ F p,π E prq @β P R,i.e., this definition does not care about the scaling α of the reward, but it is sensitive to the actual position β of that reward.Therefore, both C and F suffer from some "rescaling" issues. Is it possible to devise a notion of compatibility, i.e., a measure of suboptimality, for a policy, that is independent of both the scale α and position β? Formally, we are looking for a function (notion of distance) f : R ˆR Ñ R ě0 such that, for any J 1 , J 2 P R:EQUATION) for all α P R ą0 , β P R. Unfortunately, this is not possible, since it is easy to show that all the functions f of this kind are of the following type:@J 1 , J 2 P R ˆR : f pJ 1 , J 2 q " $ & % K `if J 1 ą J 2 K 0 if J 1 " J 2 K ´if J 1 ă J 2 ,for some reals K `, K 0 , K ´. In words, any function f that satisfies Equation ( 3) is able to express just an ordering between inputs J 1 and J 2 , but not an actual measure of sub-optimality/compatibility. 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 multiplicative 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.1 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 ϵ-optimal policy π to r in the true environment p has similar performance in the same environment p under the true reward r E , that is, policy π is an f pϵq-optimal policy to r E in p, for some function f .Applications of IRL range from Apprenticeship Learning (AL), to reward design, to interpretability of expert's preferences. Concerning AL, it is common to "use" the reward r learned through IRL to optimize our learning agent. But what properties r should satisfy in order to obtain performance guarantees on our learning agent w.r.t. the true (unknown) r E ? We now list and analyze various plausible requirements.• First, we might ask that, being π E optimal w.r.t. r E , then π E P arg max π J π prq, i.e., that the expert policy π E is optimal under the learned reward r. However, this requirement is not satisfactory for the following reason. Reward r might induce more than one optimal policy (e.g., it might induce both π, π E as optimal), and optimal policies other than π E (e.g., π) are not guaranteed to perform well under r E (actually, π can be any policy in Π). Clearly, this is not satisfactory. Observe that there are rewards in the feasible set R p,π E for which multiple policies are optimal (thus, not all the rewards in the feasible set are satisfactory).• We might additionally ask that π E is the unique optimal policy of reward r (similarly to what happens in entropy-regularized MDPs [70, 15] ). 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 in RL, is to settle for an ϵ-optimal policy. Since any policy can be ϵ-optimal under reward r, then no guarantee we can have for such policy w.r.t. r E .• What if we ask that π E is at least ϵ-optimal under r (i.e., the requirement provided by ϵ-(non)compatible rewards)? Well, this is not satisfactory because optimal policies can be any, and because there might be other ϵ-optimal policies that can perform arbitrarily bad under r E .All the three requirements described above on r do not provide guarantees that optimizing the considered reward r provides a policy with satisfactory performance w.r.t. the true r E . However, as mentioned in Section 4 and in Appendix C.1, expert demonstrations do not provide any information about the performance of policies other than π E under r E .Remark C.1. If we want to be sure that an ϵ-optimal policy π for the learned reward r in p is if f pϵq-optimal for r E in p (for some function f ), then, clearly, we need that all the (at least) ϵ-optimal policies under the learned r have visitation distribution close to that of π E in 1-norm (see Appendix C.1).We stress that many IRL algorithms for AL, like max-margin [2] , learn a reward function just as a mere mathematical tool to compute a policy π which is close in 1-norm }d π ´dπ E } 1 to π E .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 E under distance d all (see Section 3.1 of [68]), defined as: d all pr, r E q :" sup πPΠ |J π prq ´Jπ pr E q|.If d all pr, r E q is small, then the performance of any policy in r, not just optimal policy or ϵ-optimal policy, is similar also under r E . In other words, if we use/optimize reward r, then we have the guarantee that the performance of the retrieved policy under r E is more or less the same as its performance in r. Therefore, clearly, rewards r with small distance to r E w.r.t. d all can be used for "forward" RL. However, we have the following result: Proposition C.1. Let M " pS, A, H, d 0 , pq be a known MDP without reward, and let π E be a known expert's policy. Let r E the true unknown reward optimized by the expert to construct π E . Then, there does not exist a learning algorithm that receives in input the pair pM, π E q and outputs a single reward r such that d all pr, r E q ď ϵ w.p. 1 ´δ.Proof. The proof is trivial. Indeed, since the feasible set R p,π E contains an infinite amount of reward functions along with r E , and the learning algorithm cannot discriminate r E inside R p,π E , then the best it can do is to output an arbitrary reward function r P R p,π E . However, since R p,π E contains, for any reward r P R p,π E , at least another reward r 1 P R p,π E such that d all pr, r 1 q " c is finite and equal to some positive constant c ą 0, 13 then we can simply construct the problem instance with r E :" r 1 to make the learning algorithm not able to output rewards that can be used for forward learning.Nevertheless, [38, 31, 68] seem to provide sample efficient algorithms w.r.t. d all . 14 By looking at Proposition C.1, we realize that this is clearly a contradiction. What is the right interpretation?The trick is that the algorithms proposed in works [68, 38, 31] are not able to output a single reward r which is close to r E w.r.t. d all , but, for any possible reward r E " r E pV, Aq parametrized15 by some value and advantage functions V, A, they are able to output a reward r such that d all pr, r E pV, Aqq is small. In other words, it is like if these works assume to know the V, A parametrization of the true reward r E . Simply put, these works are able to output a reward r that can be used for "forward" RL just under such assumption. Otherwise those algorithms do not provide such guarantee.To sum up, we conclude that, in general, an arbitrary reward function with small (non)compatibility can not be used for "forward" learning (see Proposition C.1), 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., an arbitrary reward in the feasible set, can not be used for "forward" learning.In Section 4, we said that rewards r with smaller values of C p,π E prq are more compatible with π E in M " pS, A, H, d 0 , pq. However, one might provide the following "counter-example":Example C.1 (Question by Reviewer KyLX). Let r 1 , r 2 be two rewards such that r 2 h ps, aq " 2r 1 h ps, aq ě 0 for all ps, a, hq P S ˆA ˆ H . Then, clearly, C p,π E pr 2 q " 2C p,π E pr 1 q. Therefore, based on Section 4, we say that reward r 1 is more compatible than r 2 w.r.t. π E in M. However, since r 2 is just r 1 re-scaled by a constant, the two MDPs M Y tr 1 u and M Y tr 2 u should be "equivalent", thus, r 1 and r 2 should be, intuitively, equally compatible with π E . However, Example C.1 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 2 different kinds of real-world scenarios: piq 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; piiq 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 [52, 9] (this is referred to as the Reward Hypothesis in literature [58] ).There is an enormous difference between scenario piq and scenario piiq. In piq the notion of ϵ-optimal policy is well-defined for any fixed ϵ ą 0, because the reward function is given and, thus, fixed. Instead, in piiq, 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 [52, 9, 58] . As Example C.1 shows, positive affine transformations of the reward do not affect the structure of preferences represented (see [52] or Section 16.2 of [50] or [30] ). Therefore, in piiq, the notion of ϵ-optimal policy is not well-defined, because rescaling a reward function r to kr changes the suboptimality of some policy π from ϵ to kϵ. In other words, for fixed ϵ ą 0, any policy can be made ϵ-optimal by simply rescaling a reward r to kr for some small enough k ą 0.In IRL, this issue is even more influential because, although we are in setting piq, 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 Cprq which implicitly contains information about the scale of the reward r. Compatibilities of different rewards (e.g., r 1 and r 2 in Example C.1) 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).It 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.In conclusion, to settle Example C.1, 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.This appendix is organized as follows. First, we report the full pseudo-code of CATY-IRL. Then, we provide the proof of Theorem 5.1 in Appendix D.2.In this section, we provide the extended version of CATY-IRL containing the explicit conditions under which we shall instantiate one BPI/RFE algorithm instead of another. Data: Failure probability δ ą 0, target accuracy ϵ ą 0, expert demonstrations D E , classification threshold ∆ P R, reward to classify r P R, problem structure ı P ttabular, linear rewards, Linear MDPu, dataset D // Estimate the expert's performance p J E prq: if ı " tabular then Notice that, according to Definition 4.3, an algorithm is pϵ, δq-PAC for IRL if it computes an estimate ϵ-close to the true (non)compatibility w.h.p.. Such definition does not depend on the specific strategy adopted by the algorithm to actually classify the input reward using the computed estimate of (non)compatibility.p d E Ð empirical estimate of d p,π E from D E p J E prq Ð ř h x p d E h , r h y else p ψ E Ð empirical estimate of ψ p,π E from D E p J E prq Ð ř h x p ψ E h ,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 π pr; pq of policy π under reward r in environment with dynamics p can computed as: where we have defined the feature expectations tψ p,π h u hP H as ψ p,π h :" E ps,aq"d p,π h ϕps, aq. Observe that vector ψ p,π h has d components instead of the SA components of each d p,π h vector. Since in our setting the IRL algorithm receives in input the reward function (or its parameter θ P R d ), to estimate the expected utility J π pr; pq we must estimate the visit distributions td p,π h u h or the feature expectations tψ p,π h u h . However, because of the different dimensionalities of such quantities (SA versus d), the estimates might require different amounts of samples. Theorem 5.1 (Sample Complexity of CATY-IRL). Let ϵ, δ P p0, 1q. Then CATY-IRL is pϵ, δq-PAC for IRL with a sample complexity upper bounded by: Tabular MDPs:J π pr; pq " ÿ hP H xr h , dτ E ď r O ´H3 SA ϵ 2 log 1 δ ¯, τ ď r O ´H3 SA ϵ 2 ´N `log 1 δ ¯¯,Tabular MDPs with linear rewards:τ E ď r O ´H3 d ϵ 2 log 1 δ ¯, τ ď r O ´H3 SA ϵ 2 ´N `log 1 δ ¯¯,Linear MDPs:τ E ď r O ´H3 d ϵ 2 log 1 δ ¯, τ ď r O ´H5 d ϵ 2 ´d `log 1 δ ¯¯,where N " 0 if |R| " Θp1q, and N " S otherwise.Proof. To prove the theorem, we aim to find a bound to the number of samples τ E such that the estimate p J E prq « J π E pr; pq is ϵ{2-correct with probability at least 1 ´δ{2. Next, similarly, we aim to bound τ so that p J ˚prq « J ˚pr; pq is ϵ{2-correct with probability at least 1 ´δ{2. Then, the conclusion follows after performing a union bound and observing that, for any r P R:ˇˇC p,π E prq ´p Cprq ˇˇ" ˇˇ´J p ψ E h :" ř iP τ E ϕps i h , a i h q τ E @h P H .Concerning the estimate of the visit distribution p d E , we can use the result of Lemma 6 in [53] (we are working with bounded rewards), to obtain that:ÿ hP H }d p,π E h ´p d E h } 1 ď d SAH 3 log 8SAH δ 2τ E ď ϵ 2 .Solving w.r.t. τ E we get the bound on τ E .In a completely analogous manner, we can bound the feature expectations as:ÿ hP H }ψ p,π E h ´p ψ E h } 1 ď d dH 3 log 8dH δ 2τ E ď ϵ 2 .Again, solving w.r.t. τ E we get the bound on τ E .Estimating p J ˚prq « J ˚pr; pq Let us begin with the case in which R is 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 ϵ, δ P p0, 1q, after having explored for τ ď r O ´H3 SA ϵ 2 `S `log 1 δ ˘¯in case of RF-Express [37] Clearly, if such property holds, then by computing the performance of the policy p π outputted by the RFE algorithm we are able to obtain an ϵ{2-correct estimate of J ˚pr; pq. 16Concerning the case in which |R| is a 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 a small constant, we can proceed with a union bound over R: This allows us to formally distinguish between small and large |R| based on the following inequality:P ´sup rPR,πPΠS `log 1 δ ă log |R| δ ùñ S ă log |R|.E Missing Proofs and Additional Results for Section 6.1This appendix is organized as follows. First, in Appendix E.1, 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. Next, in Appendix E.2, we provide the missing proofs.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 a 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.In all the 4 problems, the learner is placed into an unknown MDP without reward M " pS, A, H, d 0 , pq, i.e., an environment whose dynamics pd 0 , pq is unknown to the learner. For simplicity, w.l.o.g., we assume that there is a single initial state s 0 :" d 0 . 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 know which is the specific task it has to solve. It just knows that the specific task belongs to a given set of tasks T (e.g., set of reward functions). The agent can use the knowledge of T to engage in a more efficient task-driven exploration. For any ϵ, δ P p0, 1q, the goal of the agent is to being able to ouputting, for any task in T a quantity o (e.g., a policy) that solves that specific task in an ϵ-correct manner with probability at least 1 ´δ. The ultimate goal of exploration is to collect the least number of samples that permits pϵ, δq-correctness for all the tasks in T.Now, let us see what the quantities T and o represent in each of the 4 problems. In Table 1 , we provide a sum up of the various definitions.Reward-Free Exploration (RFE). In RFE, the learner receives a set of reward functions T " R Ď R in input, and the goal is to exploit the information about p collected at exploration phase to output, for any reward r P R, an ϵ-optimal policy o " p π r w.p. 1 ´δ. When T " tru is a singleton, the RFE problem is commonly termed the BPI problem. In symbols, any RFE algorithm must guarantee that:P ´sup rPR J ˚pr; pq ´J p πr pr; pq ď ϵ ¯ě 1 ´δ,where p π r is the estimate of the algorithm for reward r.Inverse Reinforcement Learning (IRL). In IRL, the learner receives in input an occupancy measure17 td p,π E h u hP H and a set of reward functions R Ď R: T " pd p,π E , Rq, but it does not know which specific reward it will have to classify. Under the assumption that the occupancy measure d p,π E is known, 18 the problem reduces to exploiting the information about p collected at exploration phase to output, for any reward r P R, an ϵ-correct estimate o " p Jprq of the optimal utility J ˚prq w.p. 1 ´δ. In symbols, under these conditions, any IRL algorithm must guarantee that: P ´sup rPR ˇˇJ ˚pr; pq ´p Jprq ˇˇď ϵ ¯ě 1 ´δ, where p Jprq 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 Ď R and a measure of performance for each of them J : R Ñ R: T " pJ, Rq. For any r P R, the utility Jprq represents a 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 P R, a policy o " p π r such that, if we denote the policy with performance closest to Jprq by π r P arg min π |J π prq ´Jprq|, then the utility of policy p π r is ϵ-close to the utility of policy π r w.p. 1 ´δ. In symbols, any MP algorithm must guarantee that: P ´sup rPR ˇˇJ πr pr; pq ´J p πr pr; pq ˇˇď ϵ ¯ě 1 ´δ, where π r P arg min π |J π prq ´Jprq|, and p π r is the estimate of the algorithm for reward r.Imitation Learning from Demonstrations alone (ILfO). In ILfO, the learner receives in input a set of state-only reward functions R Ă R and a state-only occupancy measure td h u hP H : T " pd, Rq.Under the assumption that d 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 P R, a policy o " p π r such that, if we denote the policy with performance closest to Jprq :" ř hP H xr h , d h y by π r P arg min π |J π prq ´Jprq|, then the utility of policy p π r is ϵ-close to the utility of policy π r w.p. 1 ´δ. Simply put, ILfO, as defined in this manner, exemplifies the MP setting by providing a functional form to J : R Ñ R as an inner product between a certain state-only occupancy measure and the input reward. It should be remarked that the assumption made for ILfO is mild, because it is 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 pϵ, δq-PAC algorithm for the IRL classification in tabular MDPs. Let τ be the number of exploration episodes. Then, there exists an IRL classification instance such that:if |R| ě 1 : τ ě Ω ˆH3 SA ϵ 2 log 1 δ ˙, if R " R : τ ě Ω ˆH3 SA ϵ 2 ´S `log 1 δ ¯˙.Proof. The proof is similar to that of [38] . We split the proof in two parts, by considering two classes of difficult problem instances in Lemma E.2 and Lemma E.3. Next, we combine the two bounds through maxta, bu ě pa `bq{2 for all a, b ě 0. For the proof, we will assume that the expert visit distribution is known. The obtained bound represents a lower bound to the more general setting in which it is unknown.Theorem E.1 (RFE -Refined Lower Bound). Let A be an pϵ, δq-PAC algorithm for RFE in tabular MDPs. Let τ be the number of exploration episodes. Then, there exists an RFE instance such that:τ ě Ω ˆH3 SA ϵ 2 ´S `log 1 δ ¯˙.Proof. The proof of this result is analogous to that of Theorem 6.1, and it employs Lemma E.2 and Lemma E.3.Some observations are in order. First, since MP is a more general setting than RFE, then this lower bound is a 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 cannot 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.1 holds for ILfO too, because we might a posteriori reveal the state-only distribution d of the optimal policy, and thus, in such manner, ILfO would be reduced to RFE.Lemma E.2. Let IRL and RFE be the learning problems defined as in Appendix E.1. Then, for each problem, any pϵ, δq-PAC algorithm must collect at least the following number of exploration episodes:τ ě Ω ˆH3 SA ϵ 2 log 1 δ ˙.Proof. Observe that the proof for RFE is present in [12] . Thus, we have to prove just the result for IRL. For doing so, we will use both the results of [12] and [38] . Notice that for the sake of this proof we consider R " tru, that will reduce our problem to simple RL as, in order to compute the function C p,π E prq, we just need to compute J ˚pr; pq, being J π E pr; pq known from the availability of d p,π E and r.s w s root s E action = π E ps w q 1 s 1 s 2 s 3 s 4 action ‰ a w action = a w s g s b r h ps g , aq " 1th ě H `d `1u r h ps b , aq " 0 1 2 1 2 1 2`ϵ1 The hard instances considered are exactly the same as [12] , and are reported in Figure 4 for simplicity. The only difference is the presence of state s E , to which the expert's policy π E brings, which is absorbing. Such state is needed to make the knowledge of the expert's visit distribution d p,π E useless at inferring information about the transition model in other parts of the state-action space. Based on [12] , we describe such hard instances. Similarly to [12] , we assume that S ě 7, A ě 2, and there exists an integer d such that S " 4 `pA d ´1q{pA ´1q, and we assume that H ě 3d. Note that [12] show how to relax the assumption on the existence of d.There are the initial state s w , from which the agent starts, and states s g , s b , respectively, the "good" and "bad" states which are absorbing. Moreover, there is state s E , which is reached by the expert, and is absorbing. The remaining S ´4 states are arranged in a full A-ary tree of depth d ´1 with root s root . We denote by H ď H ´d a certain integer parameter, and by L :" ts 1 , s 2 , . . . , s L u the set of leaves of the tree. We define I :" t1 `d, . . . , H `du ˆL ˆA. For any ı P I, we define and MDP M ı as follows. In any state of the tree, i.e., in states Szts w , s g , s b , s E u, the transitions are deterministic, and the a-th action of a state brings to the a-th child of that node. The transitions from s w are given by p h ps w |s w , aq :" 1ta " a w , h ď Hu and p h ps root |s w , aq :" 1 ´ph ps w |s w , aq.In other words, action a w allows the agent to remain in the initial state s w up to stage H. After stage H, the agent is forced to leave s w and to traverse the tree down to the leaves. Action a E " π E 1 ps w q is the only action that brings to state s E , which is absorbing. The transitions from any leaf s i P L are given, as in [12] , by: p h ps g |s i , aq :" 1 2 `∆ph ˚,ℓ ˚,a ˚q ph, s i , aq and p h ps b |s i , aq :" 1 2 ´∆ph ˚,ℓ ˚,a ˚q ph, s i , aq, (4) where ∆ ph ˚,ℓ ˚,a ˚q ph, s i , aq :" 1tph, s i , aq " ph ˚, s ℓ ˚, a ˚qu ¨ϵ1 , for some ϵ 1 P r0, 1{2s. For this reason, there exists a (single) leaf ℓ ˚where the agent can choose an action a ˚at stage h ˚to increase its probability of arriving to the good state s g , which provides higher reward. We define states s g and s b to be absorbing, i.e., they satisfy p h ps b |s b , aq :" p h ps g |s g , aq :" 1 for any action a. The reward function is state-only and is defined as @a P A, r h ps, aq :" 1ts " s g , h ě H `d `1u, so that even though the agent decides to stay at s w until stage H, it does not lose any reward. Observe that state s E does not provide any reward, so that to estimate the (non)compatibility, any algorithm must provide a good estimate of the optimal performance.Finally, we define a reference MDP M 0 which is an MDP of the above type but for which ∆ 0 ph, s i , aq :" 0 for all ph, s i , aq. For certain ϵ 1 and H to choose, we define the class M to be the set M :" tM 0 u Y tM ι u ιPI .Distance between problems We will prove the lower bound for instance M 0 . Observe that, in M 0 , the optimal utility is:J 0 " 1 2 pH ´H ´dq,because there is no triple with additional bias towards s g . Instead, for any other M ı P M, the optimal utility is:J i " pH ´H ´dq ´1 2 `ϵ1 ¯.Therefore, if we choose ϵ 1 :" 2ϵ{pH ´H ´dq, we have that, for any ı P I: ˇˇJ 0 ´Ji ˇˇ" 2ϵ.Thus, in particular, for any estimate p J P R we necessarily have |J 0 ´p J| ď ϵ ùñ |J i ´p J| ą ϵ, and vice versa, i.e., we cannot provide an estimate p J that is ϵ-close to both J 0 and J i .Identifying the underlying problem Following [38] , let us consider a generic pϵ, δq-correct algorithm A that outputs the estimated optimal utility p J. Then, for all ı P I, we have:δ ě sup all problem instances M P M,A ˆˇˇJ M ´p J ˇˇě ϵ ě sup MPM P M,A ˆˇˇJ M ´p J ˇˇě ϵ ě max ℓPt0,ıu P M ℓ ,A ˆˇˇJ l ´p J ˇˇě ϵ ˙.For every ı P I, we define the identification function Ψ ı as the index of the problem "recognized" by algorithm A. In symbols:Ψ ı :" arg min ℓPt0,ıu ˇˇJ l ´p J ˇˇ.In words, given estimate p J returned by algorithm A, the identification function Ψ ı returns the problem between M 0 and M ı whose optimal utility is closest to the estimate p J. For what we have seen in the previous paragraph, problems M 0 and M ı lie at a distance of at least 2ϵ for all ı P I. Therefore, for ȷ P t0, ıu, we have the following inclusion of events: Thanks to this fact, we can continue lower bounding the probability as:tΨ ı ‰ ȷu Ď t|J ȷ ´p J| ą ϵu.EQUATION"EQUATION" P M0,A `Ψı ‰ 0 ˘`P Mı,A `Ψı " 0 ˘ȷě 1 4 exp ´KLpP M 0 ,A ,P Mı,A q , where at (1) we have lower bounded the maximum with the average, i.e., maxta, bu ě pa `bq{2 for all a, b ě 0, and at (2) we have applied the Bretagnolle-Huber's inequality [38] .The proof can be concluded by upper bounding the KL divergence KLpP M0,A , P Mı,A q as in the proof of Theorem 7 in [12] , and then summing over all the ΘpSAHq 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 pϵ, δq-PAC algorithm must collect at least the following number of exploration episodes:τ ě Ω ˆH3 S 2 A ϵ 2 ˙.Proof. Instances description The hard instances that we use for the proof of this lemma are obtained by combining the hard instances in Lemma E.2 (i.e., the hard instances of [12] ), with those in [38] . Specifically, this construction is based on the intuition described in [21] that, if we want to increase the sample complexity, we have to learn transitions also to ΘpSq states, and not just from ΘpSq states.Observe the presence of state s E (only for IRL), which plays the same role as in the proof of Lemma E.2. Any action in such state receives always reward ´1, thus it is meaningless for the estimate of the (non)compatibility, which reduces to the estimation of the optimal performance. In this manner, the expert distribution d p,π E does not provide additional information about the transition model of other portion of the state-action space. Therefore, in the following, we will present the lower bound construction as if such state did not exist.The hard instances are reported in Figure 5 . Notice that they are exactly the same instances as those presented in the proof of Lemma E.2, with the difference that, from the S leaves (differently from earlier, we now denote the number of leaves through S instead of L), we do not reach just two states s g , s b , but we reach ΘpSq absorbing states, i.e., s 1 1 , s 1 2 , . . . , s 1 S . The transitions from the leaves to such states is the same as in [38] , and we report a description below.Let us introduce the set I :" ts 1 , . . . , s S u ˆA ˆt1 `d, . . . , H `du. Let ı :" ps 1 , a 1 , 1 `dq P I be a specific triple of set I, and denote I :" Iztıu. Let us also introduce set V :" tv P t´1, 1u S : ř S j"1 v j " 0u. Thanks to Lemma E.6 of [38] (that we report in Lemma E.4 for simplicity), we know that there exists a subset V Ď V (of transition models) with cardinality at least 2 S{5 such that, for every pair v, w P V with v ‰ w, we have that }v ´w} 1 ě S{16. In other words, we know that there exists a S{16-packing of V with cardinality at least 2 S{5 .Following [38] , we denote by v " pv ı q ıPI P V I the generic vector of V I . Now, for any v P V I , for any triple ȷ P I, and for some parameter ϵ 1 P r0, 1{2s to choose, we construct problem instance M v,ȷ as follows.First of all, we define the transition model at triple ı as:p hı ps 1 i |s ı , a ı q " 1 S @i P S ,where observe that we use notation ı " ps ı , a ı , h ı q P I to denote triples in I. Instead, for the generic triple ı P I (including triple ȷ), the probability distribution of the next state is given by:p hı ps 1 i |s ı , a ı q " 1 S `ϵ1 S v ı i @i P S ,where v ı i represents the i-th component of the ı-th vector in v. In words, the i-th component of vector v ı P V creates a bias of ϵ 1 {S towards the next state s 1 i for all i P S . Since v ı P V, then p hı p¨|s ı , a ı q P ∆ S for all ı P I.We consider non-stationary reward functions. Specifically, all the rewards r P R that we consider assign reward 1 to both triples ı and ȷ, i.e., r hı ps ı , a ı q " 1 and r hȷ ps ȷ , a ȷ q " 1. Next, for any other triple ps, a, hq P S ˆA ˆ H with state different from s 1 1 , s 1 2 , . . . , s 1 S , we assign reward 0. For states s 1 1 , s 1 2 , . . . , s 1 S , we consider state-only rewards whose value is always 0 in stages r1, H `ds, and whose value is stationary and arbitrary afterwards. Intuitively, as in [12] , forcing the reward to be 0 up h " H `d guarantees that we cannot obtain a higher expected return J by reaching the leaves states earlier (i.e., by exiting from s w before H).Given the definition above, we construct the class of instances M :" tM v,ı : ı P I, v P V I u.Moreover, we will use the notation M v ı Ðw,ȷ to denote the instance in which we replace the ı component of v, i.e., v ı , with w P V and M v ı Ð0,ȷ the instance in which we replace the ı 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 v ȷ Ðw,ȷ , then we omit the second parameter, and write just M v ı Ðw :" M v ı Ðw,ȷ . Distance between problems Consider an arbitrary problem instance M v,ı P M, for certain ı P I and v P V I . Let r P R be an arbitrary reward function that satisfies the constraints described earlier.Let π ı P Π be the deterministic policy that brings to triple ı. Then, its expected return is:J πı pr; M v,ı q " 1 `H ´H ´d S S ÿ i"1 r i ,In words, policy π ı is optimal in problem M v ı Ðv , and policy π ı is worse than 2ϵ-suboptimal in such problem. In addition, observe that policy π ı is optimal in problem M v ı Ðw , and policy π ı is worse than 2ϵ-suboptimal in such problem. We stress that any stochastic policy in-between π ı and π ı cannot be ϵ-optimal for both problems.To sum up, for the choice of ϵ 1 made earlier, for arbitrary pairs of problems M v ı Ðv and M v ı Ðw , we have seen that there exist rewards in R for which a policy ϵ-optimal for problem M ı,v is not ϵ-optimal for problem M ı,w , and vice versa.Identifying the underlying problem: RFE. We consider first RFE, and then IRL.Let us consider an pϵ, δq-correct algorithm A for RFE, that outputs, for any reward function r P R, a policy p π r . For simplicity, we consider as output of Algorithm A a function p π : R Ñ Π, that takes in input a reward and outputs a policy. We can continue to lower bound the probability as: 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, we remark that, now, the error is measured based on the expected utilities, and not on the policies.Let us consider an pϵ, δq-correct algorithm A for IRL, that outputs, for any reward function r P R, a utility p J r . For simplicity, we consider as output of Algorithm A a function p J : R Ñ R, that takes in input a reward and outputs a utility. which represents the same lower bound obtained also for RFE.The following derivation is analogous to that of [38] . To bound the KL-divergence term, for any ı P I, we can write:EQUATION"EQUATIONď 2pϵ 1 q 2 E M v ı Ðw ,A " N τ hı ps ı , a ı q ‰ ,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 τ hı ps ı , a ı q " ř τ t"1 1tps t , a t , h t q " ps ı , a ı , h ı qu). Plugging into Equation (6), we get: Notice that, since |V| " Θpe S q and ϵ 1 " Θpϵ{Hq, then this bound is in the order of Ωp H 2 S ϵ 2 q. To get the additional ΩpSAHq dependence, we can make the same observation as in [38] , i.e., that ince the derivation is carried out for every ı P I and v P V I , we can perform the summation over ı and the average over v. By noticing that we get a guarantee on a mean under the uniform distribution of the instances of the sample complexity, we realize that there must exist one v hard P V for which it holds the desired Ω ´H3 S 2 A ϵ 2¯dependency.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 " tv P t´1, 1u D : ř D j"1 v j " 0u. Then, the D 16 -packing number of V w.r.t. the metric dpv, v 1 q " ř D j"1 |v j ´v1 j | is lower bounded by 2 D 5 . Theorem E.5. (Theorem E.2 of [38] ) Let P 0 , P 1 , . . . , P M be probability measures on the same measurable space pΩ, Fq, and let A 1 , . . . , A M P F be a partition of Ω. Then, 1 M M ÿ i"1 P i pA c i q ě 1 ´1 M ř M i"1 D KL pP i , P 0 q ´log 2 log M , Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as 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 it into the paper).38th Conference on Neural Information Processing Systems (NeurIPS 2024).|µ h |pBq denotes the vector containing the variation of each measure µ i h over the measurable set B."Online" refers to how we estimate the transition model p, not to the expert's policy π E , for which we assume to have access to a batch dataset. This is justified by the fact that most of IRL real-world applications involve the presence of a 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.We exemplify this proposition in Appendix B.1. In Appendix B.4 we generalize to infinite state spaces.For simplicity, we provide the full expression of distance d in Appendix B.4, Equation (1).See Appendix C.1 for a visual intuition.In Appendix C.2, a multiplicative alternative definition is presented.We use (non)compatibility since a reward r P R is maximally compatible when C p,π E prq " 0. Thus, the larger C p,π E prq, the more r is non-compatible. In this sense, C p,π E prq quantifies the non-compatibility of r.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 J ˚pr; pq as an intermediate step, with negligible abuse of notation, we assume that they output such estimate.The intuition is that, based on the fact that in Linear MDPs the Q-function of any policy π is linear in the feature mapping Q π h p¨, ¨q " pϕp¨, ¨q, w π h q for some parameter vector w π h P R d (see[23]), then if we are able to ϵ-cover the state space S, we can approximate the Q-function Q π h ps, ¨q in any s P S with the Q-function Q π h ps 1 , ¨q of the closest point s 1 int the covering, so that |Q π h ps, aq ´Qπ h ps 1 , aq| " |pϕps, aq ´ϕps 1 , aqq ⊺ w π h | ď }ϕps, aq ´ϕps 1 , aq} 2 }w π h } 2 ď Lϵ}w π h } 2 . However, this assumption is not sufficient. Proposition B.1. Under the setting of Proposition 3.2, even under Assumption B.1, then an algorithm is pϵ, δq-PAC only if τ E " ΩpSq. Assumption B.1 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 S p,π E to get an acceptable feasible set.Actually, [68] makes use of a concentrability assumption too.E.g., see Theorem 7.2.7 in[45], which is inspired by[43].Indeed, simply observe that, for any π P Π: J π pr 1 ; pq " J π pαr `β; pq " αJ π pr; pq `β.This is immediate from the considerations in Appendix C.1.Actually,[38,31] use different notions of distance, like d8pr, r 1 q :" }r ´r1 }8. However, we can write }r ´r1 }8 ě }r ´r1 }1{pSAHq, and by dual norms we have that d all pr, r 1 q " sup πPΠ |xd p,π , r ´r1 y| ď sup d:}d}8ď1 |xd, r ´r1 y| " }r ´r1 }1. Therefore, the guarantees of[38,31] can be converted too d all guarantees too.While [68] makes this parametrization explicit,[38,31] keep the parametrization implicit, but everything is analogous.Actually, for Linear MDPs, instead of evaluating the policy returned by Algorithm 2 of[62], we can simply consider the optimistic estimate of the V -function computed by such algorithm, which has the property of being ϵ-close to the true optimal V -function.Actually, as explained in Section 6.1, the knowledge of d p,π E 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 p,π E is known is useful to reduce the estimation problem of the (non)compatibility of a reward C p,π E prq :" J ˚pr; pq ´Jπ E pr; pq to the problem of estimating the optimal utility J ˚pr; pq only. Indeed, if d p,π E is known, then, for any reward r, the utility J π E pr; pq is known. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
2. The algorithms that the authors propose are also just the existing algorithms in standard RL, so there is no novelty in the algorithm design.
questions: 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: limitations: None.
paper_summary: paper_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.
strength_weakness: strength_weakness: “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?”

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.

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.

No simulation included, although it should be easy provide some illustration, in particular for any worst-case results.

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.

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.

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.
questions: questions: Would objective-free exploration be independent on the linear MDP assumption? Is it needed at all in the present paper?

Can you compare to other IRL algorithms?
limitations: limitations: Practical application is limited, but this is outside the scope of this very impressive paper.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

2. 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.

3. 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?

4. Lack of empirical evaluation.

[1] Maximum-likelihood inverse reinforcement learning with finite-time guarantees

[2] First-person activity forecasting with online inverse reinforcement learning

[3] Online inverse reinforcement learning under occlusion

[4] Learning multi-agent behaviors from distributed and streaming demonstrations
questions: questions: Please see weaknesses.
limitations: limitations: The limitation is discussed in Section 7.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
2. 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.
3. 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.
4. Computational complexity: The authors claim that their algorithm is also computationally efficient, but I couldn't find a discussion about this.
5. 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$?
questions: questions: How would you apply your algorithm to a real world IRL problem? What is the computational complexity of the classification step?
limitations: limitations: I think the practical limitations should be discussed more extensively.

Comments: title: Post rebuttal comment
comment: Thank you for the rebuttal! I will keep a positive evaluation.
Thanks for the response. I'll keep my current positive rating.
Thank you very much for the clarifications. I will maintain my positive score.
Thank you. We address the Reviewer additional questions/remarks below:

> I think in the definition of the feasible reward set, it should be clarified that for linear MDPs, we are only considering rewards that are parametrized by $\langle \phi(s,a),\theta_h \rangle$. At the moment, the definition just requires $r\in[-1,1]^{S\times A \times [H]}$

Definition 3.1 is general and independent of structural assumptions of the MDP, like Linear MDPs. Nevertheless, we agree that we should remark that, for Linear MDPs, we consider just rewards parametrized through the feature mapping $\phi$. We will clarify this point in the paper.

> What exactly do you mean by "the feasible reward set contains a continuum of rewards"? Since you parametrize the reward using a finite number of features, the set of feasible rewards should be confined within the span of these features (which is a finite-dimensional subspace).

Yes, the feasible set is confined within the span of the features, which is still a continuous space. For this reason, there are *infinite* rewards inside the feasible set, thus we cannot construct an algorithm that outputs all these rewards. We might construct an algorithm that outputs the *constraints* defining the feasible set, but then we could use such constraints *only* for classifying rewards as inside or outside the feasible set. Therefore, we prefer to explicitly implement a classifier.

> Just an observation: In Theorem 3.2, the poor scaling $\Omega(S)$ seems to be related to the fact that we need to visit all states to exclude $\lbrace 0 \rbrace$ as the feasible reward set. I think when we additionally assume that the expert is uniquely realizable for some reward, then the problem wouldn't occur. Do you agree?

That is an interesting question. We agree with the Reviewer that the additional assumption that there is a single optimal policy $\pi^E$ for the expert's reward $\theta^E$ would simplify the hard instances in the proof of Theorem 3.2, so that the lower bound $\Omega(S)$ would not hold anymore. The intuition is interesting, and even though we are not sure that it gets rid of the $\Omega(S)$ dependence, we think that it might be analysed in future works.
Thank you for the thorough response. It mostly clarified my questions, so I decided to raise my score to 7. However, I would have the following follow-up questions /remarks:
1. I think in the definition of the feasible reward set, it should be clarified that for linear MDPs, we are only considering rewards that are parametrized by $\langle \phi(s,a),\theta_h \rangle$. At the moment, the definition just requires $r\in[-1,1]^{S\times A \times [H]}$.
2. What exactly do you mean by "the feasible reward set contains a continuum of rewards"? Since you parametrize the reward using a finite number of features, the set of feasible rewards should be confined within the span of these features (which is a finite-dimensional subspace).
3. Just an observation: In Theorem 3.2, the poor scaling $\Omega(S)$ seems to be related to the fact that we need to visit all states to exclude $\lbrace 0 \rbrace$ as the feasible reward set. I think when we additionally assume that the expert is uniquely realizable for some reward, then the problem wouldn't occur. Do you agree?