Randomized algorithms and PAC bounds for inverse reinforcement learning in continuous spaces

Authors: angeliki  kamoutsi
peter  schmitt-förster
tobias  sutter
volkan  cevher
john  lygeros
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 23:34:20

Abstract: This work studies discrete-time discounted Markov decision processes with continuous state and action spaces and addresses the inverse problem of inferring a cost function from observed optimal behavior. We first consider the case in which we have  access to the entire expert policy and characterize the set of solutions to the inverse problem by using occupation measures, linear duality, and complementary slackness conditions. To avoid trivial solutions and ill-posedness, we introduce a natural linear normalization constraint. This results in an infinite-dimensional linear feasibility problem, prompting a thorough analysis of its properties. Next, we use linear function approximators and adopt a randomized approach, namely the scenario approach and related probabilistic feasibility guarantees, to derive $\varepsilon$-optimal solutions for the inverse problem. We further discuss the sample complexity for a desired approximation accuracy. Finally, we deal with the more realistic case where we only have access to a finite set of expert demonstrations and a generative model and provide bounds on the error made when working with samples.

Main paper: 
 introduction: 
 In the standard reinforcement learning (RL) setting [1, 2, 3, 4] , a cost signal is given to instruct agents on completing a desired task. However, oftentimes, it is either too challenging to optimize a given cost (e.g., due to sparsity), or it is prohibitively hard to manually engineer a cost function that induces complex and multi-faceted optimal behaviors. At the same time, in many real-world scenarios, encoding preferences using expert demonstrations is easy and provides an intuitive and human-centric interface for behavioral specification [5, 6, 7] . Considering the inverse reinforcement (IRL) problem involves deducing a cost function from observed optimal behavior. IRL is actively researched with applications in engineering, operations research, and biology [8, 9, 10] . There are two main motivations behind inverse decision-making. The first one concerns situations where the cost function is of interest by itself, e.g., for scientific inquiry, modeling of human and animal behavior [11, 12] or modeling of other cooperative or adversarial agents [13] . The second one concerns the task of imitation or apprenticeship learning [14] by first recovering the expert's cost function and then using it to reproduce and synthesize the optimal behavior. For instance, in engineering, IRL can be used to explain and imitate the observed expert behavior, e.g., in the highway driving task [14, 15] , parking lot navigation [16] , and urban navigation [17] . Other examples can be found in humanoid robotics and understanding of human locomotion [18] . Despite extensive research efforts, our understanding of IRL still has significant limitations. One major gap lies in the absence of algorithms designed for continuous state and action spaces, which are crucial for numerous promising applications like autonomous vehicles and robotics that operate in continuous environments. Most existing state-ofthe-art IRL algorithms for the continuous setting often adopt a policy-matching approach instead of directly solving the IRL problem [19, 20, 21, 22, 23, 24, 25, 26, 27] . However, this approach tends to provide a less robust representation of agent preferences [26] , since the recovered policy is highly dependent on the environment dynamics. State-of-the-art IRL algorithms are empirically successful but lack formal guarantees. Theoretical assurances are crucial for practical implementation, especially in safety-critical systems with potential fatal consequences.Contributions. This work deals with discrete-time Markov decision processes (MDPs) on continuous state and action spaces under the total expected discounted cost optimality criterion and studies the inverse problem of inferring a cost function from observed optimal behavior. Under the assumption that the control model is Lipschitz continuous, we propose an optimization-based framework to infer the cost function of an MDP given a generative model and traces of an optimal policy. Our approach is based on the linear programming (LP) approach to continuous MDPs [28] , complementary slackness optimality conditions, related developments in randomized convex optimization [29, 30, 31] and uniform finite sample bounds from statistical learning theory [32] .To this aim, we first consider the case in which we have access to the entire optimal policy π E and starting from the LP formulation of the MDP, we characterize the set of solutions to the inverse problem by using occupation measures, linear duality and complementary slackness conditions. This results in an infinite-dimensional linear feasibility problem. Although from a theoretical point of view our approach succeeds in characterizing inverse optimality in its full generality, in practice the following important challenges need to be addressed. First, the inverse problem is ill-conditioned and ill-posed, since each task is consistent with many cost functions. Thus a main challenge is coming up with a meaningful one. To this end, we enforce an additional natural linear normalization constraint in order to avoid trivial solutions and ill-posedness. Another challenge is the infinitedimensionality of the LP formulation, which makes it computationally intractable. To alleviate this difficulty, we propose an approximation scheme that involves a restriction of the decision variables from an infinite-dimensional function space to a finite dimensional subspace (tightening), followed by the approximation of the infinitely-uncountably-many constraints by a finite subset (relaxation). In particular, we use linear function approximators and adopt a randomized approach, namely the scenario approach [29, 33] , and related probabilistic feasibility guarantees [30] , to derive ε-optimal solutions for the inverse problem, as well as explicit sample complexity bounds for a desired approximation accuracy. Finally, we deal with the more realistic case where we only have access to a finite set of expert demonstrations and a generative model and provide bounds on the error made when working with samples.Related literature. Our principal aim is to address problems with uncountably infinitely many states and actions. Existing IRL algorithms treat the unknown cost function as a linear combination [34, 35, 15, 17, 36, 37] or nonlinear function [38, 39, 40] of features. In particular, there are three broad categories of formulations. In feature expectation matching [35, 15, 17] one attempts to match the feature expectation of a policy to the expert, while in maximum margin planning [36, 38, 40] the goal is to learn mappings from features to cost functions so that the demonstrated policy is better than any other policy by a margin defined by a loss-function. Moreover, a probabilistic approach is to interpret the cost function as parametrization of a policy class such that the true cost function maximizes the likelihood of observing the demonstrations [17, 37, 39, 41] . Most existing IRL methods that recover a cost function, are either designed exclusively for MDPs with finite state and action spaces, or rely on an oracle access to an RL solver which is used repeatedly in the inner loop of an iterative procedure. An exception are the works [42, 43, 44, 22, 25, 45, 26] , that perform well in the experimental settings considered, without providing theoretical guarantees. Relying on oracle access to an RL solver is a significant computational burden for applying these methods to MDPs with continuous state and action spaces since solving a continuous MDP is a challenging and computationally expensive problem on its own. As a result, IRL over uncountable spaces remains largely unexplored. In this work we aim to contribute to this line of research and propose a method that avoids repeatedly solving the forward problem and simultaneously provides probabilistic performance guarantees on the quality of the recovered solution. Linear duality and complementarity were first proposed in [46] for solving finite-dimensional inverse LPs. The idea was then extended to inverse conic optimization problems in [47] by using KKT optimality conditions. The fundamental difference between these works and the present paper is that they deal with finite-dimensional convex optimization programs where the agent has complete knowledge of the optimal behavior as a finite-dimensional vector. In our setting we have the additional difficulty of the infinite-dimensional and data-driven nature of the problem. In [48] the authors use occupation measures and complementarity in linear programming to formulate the inverse deterministic continuous-time optimal control problem. Under the assumption of polynomial dynamics and semi-algebraic state and input constraints, they propose an approximation scheme based on sum-of-squares semidefinite programming. Contrary to [48] , we consider the problem of inverse discrete-time stochastic optimal control. In such a stochastic environment, assuming polynomial dynamics clearly is restrictive, excluding any setting with Gaussian noise, e.g., the LQG problem. Our approach is not limited to the case of polynomial dynamics and semi-algebraic constraints but is able to tackle the general case, while also providing performance guarantees as in [48] . Our work is closely related to the recent theoretical works on IRL [49, 50, 51, 52, 53, 54, 55, 56] . However, these papers consider either tabular MDPs [49, 50, 52, 53, 54, 55] or MDPs with continuous states and finite action spaces [51, 56] . In contrast, our contribution delves into the theoretical analysis of IRL in the intricate landscape of continuous state and action spaces. Notably, our framework, when applied to finite tabular MDPs and a stationary Markov expert policy π E , simplifies to the inverse feasibility set considered in [52, 53, 54] (see also Appx A.2). The methodology put forth in those studies, extends the LP formulation previously explored in [12, 49, 50, 51] , which primarily dealt with deterministic expert policies of the form π E ≡ a 1 . In our work, by using occupancy measures instead of policies and employing Lagrangian duality, we are able to characterize inverse feasibility for general continuous MDPs regardless of the complexity of the expert policy. Moreover, our framework empowers us to leverage offline expert demonstrations to compute an approximate feasibility set and recover a cost through a sample-based convex program. This flexibility surpasses previous theoretical IRL settings, where either π E is assumed to be fully known [49, 51, 52] or active querying of π E is possible for each state [53, 54] . Finally, our assumption of a Lipschitz MDP model is milder and more general than the infinite matrix representation considered in [51] , thus accommodating a broader range of MDP models. Overall, we establish a link between our methodology and the existing body of literature on LP formulations for IRL, while also accounting for continuous states and action spaces and more general expert policies. Finally, we would like to highlight a key distinction between our work and recent theoretical IRL papers [52, 53, 54, 55] . Unlike these recent works, our study goes beyond the examination of the properties of the inverse feasibility set and its estimated variant. Our contribution extends to tackling the reward ambiguity problem, a well-known limitation of the IRL paradigm, and provides theoretical results in this direction. Additionally, our work introduces function approximation techniques that come with robust theoretical guarantees. Finally, we study how constraint sampling in infinite-dimensional LPs can be exploited to derive a single nearly optimal solution with probabilistic performance guarantees.Basic definitions and notations. Let (X, ρ) be a Borel space, i.e., X is a Borel subset of a complete and separable ρ-metric space, and let B(X) be its Borel σ-algebra. We denote by M(X) the Banach space of finite signed Borel measures on X equipped with the total variation norm and by P(X) the convex set of Borel probability measures. Let δ x ∈ P(X) be the Dirac measure centered at x ∈ X. Measurability is always understood in the sense of Borel measurability. An open ball in (X, ρ) with radius r and center x 0 is denoted by B r (x 0 ) = {x ∈ X : ρ(x, x 0 ) < r}. Given a measurable function u : X → R, its sup-norm is given by ∥u∥∞ ≜ sup x∈X |u(x)|. Moreover, we define the Lipschitz semi-norm by |u| L ≜ sup x̸ =x ′ |u(x)-u(x ′ )| ρ(x,x ′ )and the Lipschitz norm by∥u∥ L ≜ ∥u∥ ∞ + |u| L .Let Lip(X) be the Banach space of real-valued bounded Lipschitz continuous functions on X together with the Lipschitz norm ∥•∥ L . Then, (M(X), Lip(X)) forms a dual pair of vector spaces with duality brackets ⟨µ, u⟩ ≜ X u(x)dµ, for all µ ∈ M(X), u ∈ Lip(X). Moreover, if M(X) + is the convex cone of finite nonnegative Borel measures on X, then its dual convex cone is the set Lip(X) + of nonnegative bounded and Lipschitz continuous functions on X. Under the additional assumption that X is compact, the  
markov decision processes and linear programming formulation: 
 Continuous Markov decision process. Consider a Markov decision process (MDP) given by a tuple M c ≜ X , A, P, γ, ν 0 , c , where X is a Borel space called the state space, A is a Borel space called the action space, P is a stochastic kernel on X given X × A called the transition law, γ ∈ (0, 1) is the discount factor, ν 0 ∈ P(X ) is the initial probability distribution, and c : X × A → R is the cost function. The model M c represents a controlled discrete-time stochastic system with initial state x 0 ∼ ν 0 (•). At time step t, if the system is in state x t = x ∈ X , and the action a t = a ∈ A is taken, then a corresponding cost c(x, a) is incurred, and the system moves to the next state x t+1 ∼ P(•|x, a).Once transition into the new state has occurred, a new action is chosen, and the process is repeated. A stationary Markov policy π is a stochastic kernel on A given X and π(•|x) ∈ P(A) denotes the probability distribution of the action a t taken at time t, while being in state x. We denote the space of stationary Markov policies by Π 0 . Given a policy π, we denote by P π ν0 the induced probability measure1 on the canonical sample space Ω ≜ (X × A) ∞ , i.e., P π ν0[•] = Prob[• | π, x 0 ∼ ν 0 ]is the probability of an event when following π starting from x 0 ∼ ν 0 . The expectation operator with respect to the trajectories generated by π when x 0 ∼ ν 0 , is denoted by E π ν0 . If ν 0 = δ x for some x ∈ X , then we will write for brevity P πx and E π x . The optimal control problem we are interested in is2 V ⋆ c (ν 0 ) ≜ min π∈Π0 V π c (ν 0 ), (MDP c )whereV π c (ν 0 ) ≜ E π ν0 [ ∞ t=0 γ t c(x t , a t )]. A policy π ⋆ is called γ-discounted ν 0 -optimal if V π ⋆ c (ν 0 ) = V ⋆ c (ν 0 ), and the optimal value function V ⋆ c : X → R is given by V ⋆ c (x) ≜ V ⋆ c (δ x ).We impose the following assumptions on the MDP model which hold throughout the article. These are the usual continuity-compactness conditions [59] , together with the Lipschitz continuity of the elements of the MDP; see, e.g., [60] . We recall that the transition law P acts on bounded measurable functions u : X → R from the left as Pu(x, a) ≜ X u(y)P(dy|x, a), for all (x, a) ∈ X × A. Assumption 2.1 (Lipschitz control model).(A1) X and A are compact subsets of Euclidean spaces;(A2) the transition law P is weakly continuous, meaning that Pu is continuous on X × A, for every continuous function u : X → R. Moreover, P is Lipschitz continuous, i.e., there exists a constant L P > 0 such that for all (x, a), Note that Assumption2.1 (A2) is fulfilled when the transition law P has a density function f (y, x, a) that is Lipschitz continuous in y uniformly in (x, a) [60] . This encompasses various probability distributions, such as the uniform, Gaussian, exponential, Beta, Gamma, and Laplace distributions, among others. Additionally, it applies to the infinite matrix representation considered in [51] . Consequently, Assumption 2.1 accommodates a broad range of MDP models and allows for the consideration of smooth and continuous dynamics that reflect the characteristics of several real-world applications, such as robotics, or autonomous driving. Importantly, Assumption 2.1 ensures that the value function V ⋆ c is in Lip(X ) and is uniquely characterized by the Bellman optimality equation V ⋆ c (x) = min a∈A {c(x, a) + γ X V ⋆ c (y)P(dy|x, a)}, for all x ∈ X [60, Thm. 3.1] and [61] . Occupancy measures. For every policy π, we define the occupancy measureµ π ν0 ∈ M(X × A) + by µ π ν0 (E) ≜ ∞ t=0 γ t P π ν0 [(x t , a t ) ∈ E], E ∈ B(X ×A).The occupancy measure can be interpreted as the discounted visitation frequency of the set E when acting according to policy π. The set of occupancy measures is characterized in terms of linear constraint satisfaction [62, Theorem 6.3.7] . To this end consider the convex set of measures, F ≜ {µ ∈ M(X × A) + : T γ µ = ν 0 }, where T γ : M(X × A) → M(X ) is a linear and weakly continuous operator given by for all B ∈ B(X ). Then, F = {µ π ν0 : π ∈ Π 0 }. Moreover, µ π ν0 , c = V π c (ν 0 ), for every π. The linear programming approach. A direct consequence is that (MDP c ) can be stated equivalently as an infinite-dimensional LP over measures(T γ µ)(B) ≜ µ(B × A) -γ X ×A P(B|x, a)µ( d(x, a)),J c (ν 0 ) ≜ inf µ∈M(X ×A)+ {⟨µ, c⟩ : T γ µ = ν 0 }. (P c )In particular the infimum in (P c ) is attained and π ⋆ is optimal for (MDP c ) if and only if µ π ⋆ ν0 is optimal for the primal LP (P c ). The dual LP of (P c ) is given byJ * c (ν 0 ) ≜ sup u∈Lip(X ) {⟨ν 0 , u⟩ : c -T * γ u ≥ 0 on X × A}, (D c )where the adjoint linear operator T * γ : Lip(X ) → Lip(X × A) of T γ is given by(T * γ u)(x, a) ≜ u(x) -γ X u(y)P(dy|x, a).Under Assumption 2.1, T * γ is well-defined and the dual LP (D c ) is solvable, i.e., the supremum is attained, and strong duality holds. That is, J c (ν 0 ) = J * c (ν 0 ) = V ⋆ c (ν 0 ). In particular, the value function V ⋆ c is an optimal solution for the dual LP (D c ). More details on the LP formulations for MDPs can be found in Appendix A.1.Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: We discuss limitations in Remark 4.1, where we point to the exponential dependence of our sample complexity with respect to the dimension of the state space (known as curse of dimensionality). Moreover, in this remark we point out that the selection of an "informative" distribution for the random state-action selection is not well understood and crucial for the practical efficiency of the method. Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. • The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
inverse reinforcement learning and characterization of solutions: 
 We first define the inverse reinforcement learning (IRL) problem and the inverse feasibility set. Definition 3.1 (IRL [12, 52] ). An IRL problem is a pair B ≜ (M, π E ), where M ≜ (X , A, P, ν 0 , γ) is an MDP without cost function and π E is an observed expert policy. We say that c ∈ Lip(X × A) is inverse feasible for B, if π E is a γ-discount ν 0 -optimal policy for (MDP c ) with cost c. The set of all c ∈ Lip(X × A) that are inverse feasible is called the inverse feasibility set and is denoted by C(π E ).Next, we use the primal-dual LP approach to MDPs and complementary slackness to characterize C(π E ). To this end, we first define the ε-inverse feasibility set C ε (π E ). Definition 3.2. Let ε ≥ 0. We say that a cost function c is ε-inverse feasible for B = (M, π E ) and denote c ∈ C ε (π E ) if and only if, c ∈ Lip(X × A) and there exists u ∈ Lip(X ) such thatEQUATIONWe are now ready to characterize the solutions to IRL, following arguments from [46, 47, 48] . Theorem 3.1 (Inverse feasibility set characterization). Let π E ∈ Π. Under Assumption 2.1 on the Markov decision model M c , the following assertions are equivalent1. c ∈ C 0 (π E ); 2. c ∈ ε>0 C ε (π E ); 3. π E is γ-discount ν 0 -optimal for (MDP c ) with cost function c. As a consequence, C(π E ) = C 0 (π E ) = ε>0 C ε (π E ). Moreover, C(π E ) is a convex cone and ∥•∥ L - closed in Lip(X × A).As a result, a cost function is inverse feasible for B = (M, π E ) if and only if it is ε-inverse feasible for all ε > 0. The characterization of the inverse feasibility set is due to linear duality and complementary slackness conditions. In particular, the constraint that holds pointwise in (19) is due to dual feasibility while the constraint that holds in expectation is due to strong duality, The details are provided in the proof of Theorem 3.1 in Appendix B.1.Notably, when X and A are finite, and the expert policy π E is stationary Markov, our formulation aligns with the finite-dimensional inverse feasibility set introduced in [52, 53, 54] . Furthermore, when the expert is deterministic of the form π E (x) ≡ a 1 , for all x, then we recover the linear programs discussed in [12, 49, 51] (see Appendix A.2).Using occupancy measures instead of policies, we can assess inverse feasibility for continuous MDPs, regardless of expert policy complexity. This approach allows us to utilize offline expert demonstrations for computing an approximate feasibility set and deriving costs via a sample-based convex program This flexibility surpasses previous theoretical settings, where either π E is assumed to be fully known and deterministic [49, 51, 52] or active querying of π E is possible for each state [53, 54] .Proposition 3.1 (ε-inverse feasibility set characterization). Under Assumption 2.1, for any ε > 0, it holds that a cost function c is inC ε (π E ) if and only if π E is 2-γ 1-γ ε-optimal for (MDP c) with cost c.As ε → 0, the next proposition indicates a close approximation to the inverse problem solution.Proposition 3.2. Let (ε n ) n be a sequence such that lim n→∞ ε n = 0 and let c n ∈ C εn (π E ). Then, every accumulation point c of the sequence (c n ) n is inverse feasible, i.e., c ∈ C(π E ).Finally we show that the ε-inverse feasibility set C ε (π E ) satisfies the ε-optimality criterion considered in [52, 53, 54] ; see for example [53, Def. 2] .Proposition 3.3. Let ε > 0. It holds that inf c∈C(πE) V π c (ν 0 ) -V πE c (ν 0 ) ≤ 2-γ 1-γ ε, for all c ∈ C ε (π E ), where π is an optimal policy for the recovered cost c. This condition ensures that when ε is small we avoid an unnecessarily large approximate feasibility set since there is a possible true cost in C(π E ) with a small error for every possible recovered cost function in C ε (π E ). 34 Towards recovering a nearly optimal cost function Although we characterized the inverse and ε-inverse feasibility sets in Theorem 3.1 and Proposition 3.1 respectively, it is not clear yet how to compute them, as ( 19) is an infinite-dimensional feasibility LP. In practice, the following challenges need to be addressed:(a) The inverse problem is ill-conditioned and ill-posed since each task is consistent with many cost functions, and thus a central challenge is to end up with a meaningful one. To avoid trivial solutions, in Section 4.1 we motivate the addition of a linear normalization constraint.(b) Another challenge appears because the LP formulation is infinite-dimensional, hence computationally intractable. In Section 4.2 we address this problem by proposing a tractable approximation method with probabilistic performance bounds.(c) In practice, complete knowledge of π E and P is often unavailable. In Section 4.3, we tackle this challenge by assuming that we have access to a finite set of traces of the expert policy and a generative-model oracle. We use empirical counterparts of π E and P and provide error bounds to quantify our approach's accuracy with sample data. The main building blocks of our methodology are depicted in Figure 2 .  
normalization constraint: 
 A well-known limitation of IRL is that it suffers from the ambiguity issue, i.e., the problem admits infinitely many solutions. For example, any constant cost function, including the zero cost, is inverse feasible. In addition, as it is apparent from the characterization ofC(π E ) = C 0 (π E ) in Theorem 3.1,for any u ∈ Lip(X ) and c ∈ C(π E ), the cost c + T * γ u is inverse feasible. This phenomenon, also known as reward shaping [63] refers to the modification or design of a reward function to provide additional guidance or incentives to an agent during learning. In addition, since C(π E ) is a convex cone and closed for the sup-norm (Theorem 3.1) the set of solutions to IRL is closed to convex combinations and uniform limits.All these examples illustrate that the inverse feasibility set C(π E ) contains some solutions that arise from mathematical artifacts. To mitigate this difficulty and avoid trivial solutions, inspired by [48] , we enforce the additional natural normalization constraintX ×A (c -T * γ u)(x, a) d(x, a) = 1.The following proposition justifies this choice.Proposition 4.1. If Definition 3.2 of C(π E ) = C 0 (π E ) includes the normalization constraint X ×A (c- T * γ u)dxda = 1, then all constant cost functions are excluded from the inverse feasibility set.Alternatively, it is possible to employ additional heuristics to narrow down the set of possible solutions and incorporate prior knowledge, e.g., by restricting the class where the true cost belongs, constraining the dependence between costs and value functions, and enforcing conic constraints or shape conditions.It is worth mentioning that the normalization constraint in our formulation primarily aims to mitigate the ill-posedness, or ambiguity issue, intrinsic to the IRL problem, rather than to resolve issues of identifiability. In particular, we state and prove that the normalization constraint rules out a wide class of trivial solutions, i.e., all constant functions and inverse solutions of the form c = T * γ u, an outcome devoid of physical meaning and a mathematical artifact. While the identifiability problem and the ill-posedness problem are related in IRL, they are not the same. Identifiability deals with the uniqueness of the true cost function and cannot be fully resolved unless, for example, one has access to multiple expert policies or environments for comparison [64, 65] . On the other hand, ill-posedness is a broader concept from mathematical and statistical problems and refers to situations where a problem does not satisfy the conditions for being well-posed, e.g., in our case due to infinitely many solutions. Note that, unlike recent theoretical IRL works [52, 53, 54] which avoid discussing this issue altogether, we attempt to address the ambiguity problem and provide theoretical results in this direction, hoping to lay the foundations for overcoming current limitations.We first consider the case where the expert policy π E , the induced occupation measure µ πE ν0 and the transition law P are known. We leverage developments in randomized convex optimization, leading to an approximation scheme with a priori performance guarantees. As a first step, we introduce a semi-infinite convex formulation that enforces the normalization constraint, involves a restriction of the decision variables from an infinite-dimensional function space to a finite-dimensional subspace, and considers an additional norm constraint that effectively acts as a regularizer. The resulting regularized semi-infinite inner approximation, which we call inverse program is given by         inf α,β,ε ε s.t. µ πE ν0 , c -T * γ u ≤ ε, c(x, a) -T * γ u(x, a) ≥ -ε, ∀ (x, a) ∈ X × A, X ×A (c -T * γ u)(x, a) d(x, a) = 1, c ∈ C nc , u ∈ U nu , ε ≥ 0, (IP) where C nc ≜ { nc j=1 α j c j : α = {α i } nc i=1 ∈ R nc , ∥α∥ 1 ≤ θ} with {c i } nc i=1 ⊂ Lip(X × A) being linearly independent basis functions with Lipschitz constant L c > 0, U nu ≜ { nu i=1 β i u i : β = {β i } nu i=1 ∈ R nu , ∥β∥ 1 ≤ θ}, with {u i } nu i=1 ⊂ Lip(X )being linearly independent basis functions with Lipschitz constant L u > 0, and θ > 0 is an appropriately chosen regularization parameter. Note that (IP) is derived by relaxing the constraints in the inverse feasibility set C(π E ) and paying a penalty when violated. In particular, let (ε, α, β) be an optimal solution of the semi-infinite program (IP). Then, c ≜ nc i=1 αi c i ∈ C ε(π E ), from where it becomes apparent that the smaller the value of ε, the better the quality of the extracted cost function c (as by Proposition 3.1). One would intuitively expect that ε depends on the choice of basis functions for the cost (resp. value) function as well as on the parameters n c (resp. n u ) and θ. This dependency is highlighted by the following proposition. Proposition 4.2 (Basis function dependency). Let π E be an optimal policy for the optimal control problem MDP c ⋆ with cost c ⋆ and let u ⋆ be the corresponding optimal value function. Under Assumption 2.1, if u 1 ≡ 1 and θ >EQUATIONwhered = leb(X × A) is the Lebesgue measure of X × A, D γ,θ ≜ 2θ(Kc,∞+Ku,∞) (1-γ) 2 min{1,d}θ+γ-1 , with constants K c,∞ ≜ max i=1,...,nc ∥c i ∥ ∞ and K u,∞ ≜ max j=1,...,nu ∥u i ∥ ∞ .Proposition 4.2 sheds light on how the choice of basis functions and the regularization parameter θ influence the approximation error. Essentially, the approximation error term ε approx measures the expressiveness of the linear function approximators. Prior knowledge about the properties of the true cost allows us to choose appropriate basis functions to make the projection residuals in the theorem sufficiently small. For example, if the true cost function is known to be smooth, Fourier or polynomial basis functions can be used. In general, if we choose linearly dense bases in Lip(X × A) and Lip(X ), then the projection residuals and so ε tend to 0 as n c and n u and the regularization parameter θ tend to infinity. In particular note that when c ⋆ ∈ C nc and u ⋆ ∈ U nu , then the corresponding projection residuals are 0, and thus ε = 0 as expected. In a practical setting, observing a large value of ε is an indicator that more basis functions are needed.Finally, note that the regularizer helps to bound the dual optimizer using a dual norm, thus offering an explicit approximation error for the proposed solution (see Appendix B.6).Computationally tractable approximations to the semi-infinite convex program can be obtained through the scenario approach [29, 66] in which randomization over the set of constraints is considered. In particular, we treat the parameter (x, a) as an uncertainty parameter living in the space X × A. Let P be a Borel probability measure on (X × A, B(X × A)), where X × A is equipped with the norm ∥(x, a)∥ = ∥x∥ 2 + ∥a∥ 2 . We assume that P has the following structure. Assumption 4.1 (Sampling distribution). There exists g : R + → [0, 1] strictly increasing, such that P(B r (x, a)) > g(r), for all (x, a) ∈ X × A and r > 0.Assumption 4.1 is a sufficient structural assumption concerning the sample distribution P ensuring that the gap between the robust program (IP) and its sampled counterpart (SIP N ) can be controlled. It implicitly restricts the state and action spaces to be bounded.Let {(x (ℓ) , a (ℓ) )} N ℓ=1 be independent and identically distributed (i.i.d.) samples drawn from X × A according to P. We are interested in the following random finite-dimensional convex program:           inf α,β,ε ε s.t. µ πE ν0 , c -T * γ u ≤ ε, c(x (ℓ) , a (ℓ) ) -T * γ u(x (ℓ) , a (ℓ) ) ≥ -ε, ∀ ℓ = 1, . . . N, X ×A (c(x, a) -T * γ u(x, a)) d(x, a) = 1, c ∈ C nc , u ∈ U nu , ε ≥ 0. (SIP N )Notice that (SIP N ) naturally represents a randomized program as it depends on the random multisample {(x (i) , a (i) )} N i=1 . We assume the following measurability assumption holds for our analysis. Assumption 4.2. The (SIP N ) optimizer generates a Borel measurable mapping that associates each multi-sample {(x (ℓ) , a (ℓ) )} N ℓ=1 to a uniquely defined optimizer (α N , βN , εN ).To ensure uniqueness when multiple solutions exist, use a tie-break rule, such as selecting the solution with the minimum ∥•∥ 2 norm. It has been shown [30, Proposition 3.10 ] that applying such a tie-break-rule also ensures the measurability in Assumption 4.2.The appealing feature of (SIP N ) is that it is a convex finite-dimensional program and so it can be solved at low computational cost for small enough N . We study how many samples are needed for a good solution by examining the generalization properties of the optimizer (α N , βN , εN ) and the extracted cost function cN = nc i=1 αN i c i . For each n ∈ N, ϵ ∈ (0, 1) and δ ∈ (0, 1), we defineN(n, ϵ, δ) = min N ∈ N : n i=0 N i ϵ i (1 -ϵ) N -i ≤ δ .The sample size above asymptotically scales as ∼ {1/ϵ, log(1/δ), n}, see [29] . The following theorem determines the sample complexity of (SIP N ). In particular, for a given reliability parameter ϵ ∈ (0, 1) and confidence level δ ∈ (0, 1), we establish how many samples are needed to guarantee with confidence at least 1 -δ that cN ∈ C εapprox+ϵ (π E ). .2, if u 1 ≡ 1 and θ > 1 (1-γ)leb(X ×A) , then by sampling N ≥ N(n c + n u + 1, g( ϵ LΛ ), δ) constraints, where L Λ ≜ θ √ n c L c + θ √ n u (L u L P + L u ), with probability at least 1 -δ, cN ∈ C εapprox+ϵ (π E ).Remark 4.1 (Curse of dimensionality). As shown in [30] , the function g(r) is of order r dim(X ×A) . As a result, the number of samples grows exponentially as ϵ -dim(X ×A) . A similar exponential dependence to the dimension of the state space has been established in [51] . Considering the current performance of general LP solvers, this approach is attractive for small to medium-sized problems. As noted in [51] , dealing with the general d-dimensional case without exponential scaling in d is challenging. Therefore, understanding the selection of a suitable distribution for future sample drawing is crucial.Remark 4.2 (l 1 -regularization). To cut down on required samples N , a common method is using l 1 -regularization to reduce the effective dimension of the optimization variable. This concept is formalized in the current setting [67] . Moreover, in the spirit of the compressed sensing literature [68] , l 1 -regularization will promote sparse solutions and hence lead to "simple" cost functions. In the context of optimal control l 1 -regularization term is studied as the so-called "maximum hands-off control" paradigm [69, 70] . In our case, the utilization of the l 1 -norm offers two primary advantages. Firstly, the l 1 -norm promotes sparsity in solutions, thereby potentially reducing computational demands. Secondly, this specific type of regularization preserves the linearity of the program.In this section, we explore the realistic scenario where we lack access to the expert policy π E and the transition law P. The learner only receives a finite set of truncated expert sample trajectories and cannot interact or query the expert for additional data during training. Despite the unknown MDP model, we assume access to a generative-model oracle. It provides the next state x ′ given a state-action pair (x, a) sampled from P(•|x, a). This is known as the simulator-defined MDP [71, 72] .Sampling process. Let τ = {τ i = (x i 0 , a i 0 , . . . , x i H , a i H )} m i=1 be i.i.d., truncated sample trajectories according to π E . For any c ∈ Lip(X × A), we consider the sample average approximation of the expectation µ πE ν0 , c given by, ⟨µ πE ν0 , c⟩(τ) ≜ 1 m H t=0 m j=1 γ t c(x j t , a j t ). Similarly, if ξ = {x k 0 } n k=1are i.i.d., samples according to ν 0 , for any u ∈ LipF (X ), we define the corresponding sample average estimation of the expectation ⟨ν 0 , u⟩ by ⟨ν 0 , u⟩(ξ) ≜ 1 n n k=1 u(x k 0 ). Moreover, let ζ = {(x (l) , a (l) )} N l=1 be i.i.d. samples drawn from X × A according to P ∈ P(X × A). We also use the following notationT * γ u(x (l) , a (l) , y (l) ) ≜ u(x (l) ) -1 k k i=1 u(y (l) i ), {y (l) i } k i=1 i.i.d. ∼ P(•|x (l) , a (l) ).We are interested in the finite-sample analysis of the following random convex program:           inf α,β,ε ε s.t. ⟨µ πE ν0 , c⟩(τ ) -⟨ν 0 , u⟩(ξ) ≤ ε, c(x (l) , a (l) ) -T * γ u(x (l) , a (l) , y (l) ) ≥ -ε, ∀ l = 1, . . . N, α ∈ ∆ [nu] , β ∈ ∆ [nc] , c ∈ C nc , u ∈ U nu , ε ≥ 0, (SIP N,m,n,k )where the function classes C nc , U nu are defined as in the previous Section. We make the following measurability assumption which is analogous to Assumption 4.2. Assumption 4.3. The (SIP N,m,n,k ) optimizer generates a Borel measurable mapping that associates each multi-sample (y, τ, ξ, ζ) to a uniquely defined optimizer (α N,m,n,k , βN,m,n,k , εN,m,n,k ). Theorem 4.2. Under Assumptions 2.1, 4.1 and 4.3, if u 1 ≡ 1 and θ >1 (1-γ)leb(X ×A) , then for N ≥ N(n c + n u + 1, g( ϵ LΛ ), δ/2) constraints, n ≥ 8K 2 u,∞ θ 2 nu ln ( 8nu δ ) ϵ 2 , m ≥ 8K 2 c,∞ θ 2 nc ln ( 8nc δ ) (1-γ) 2 ϵ 2 expert samples with horizon H = 1 1-γ log( 2 ε ), and k ≥ 8Cnuθ 2 log(4nuN/γ) ϵ 2calls to the generative model per constraint, with probability at least1 -δ, cN,m,n,k ∈ C εapprox+ϵ (π E ). The constants K c,∞ and K u,∞ are given as K c,∞ ≜ max i=1,...,nc ∥c i ∥ ∞ and K u,∞ ≜ max j=1,...,nu ∥u i ∥ ∞ .Theorem 4.2 provides explicit sample complexity bounds for achieving a desired approximation accuracy with our proposed randomized algorithm. For continous MDPs when we use n u basis functions for the value function and n c basis functions for the cost function we needm = O nc log( nc δ ) (1-γ) 2 ε 2 expert samples and K = O nu log( nuN δ ) ε 2calls to the generative model per constraint and N = O(exp dim(X×A) ) sampled constraints and solve the resulted sampled finite LP with n u + n c variables and N constraints in polynomial time to learn a cost that is ε + ε approx -inverse feasible with probability 1 -δ.The corresponding sample complexities include the expert sample complexity m, the number of calls to the generator per constraint k, and the number of sampled constraints N . The first two complexities scale gracefully with respect to the problem parameters, whereas the number of sampled constraints scales exponentially with the dimension of the state and action spaces (see also Remark 4.1) . This makes the algorithm particularly suitable for low-dimensional problems of practical interest, e.g., pendulum swing-up control, vehicle cruise control, and quadcopter stabilization. Note that a similar exponential dependence to the dimension of the state space has been established in Dexter et al. [51] , a theoretical study addressing IRL in continuous state but discrete action spaces.A promising research direction is to enhance the sample complexity bounds through the utilization of the underlying problem structure [73] . In addition, it becomes imperative to gain an understanding regarding the selection of a suitable distribution for drawing samples in the future. Intuitively, it is reasonable to anticipate that certain regions within the state-action space carry more "informative" characteristics than others. One conjecture is that sampling constraints based on the expert occupancy measure could yield a more scalable bound [74] . However, a comprehensive mathematical treatment of these inquiries will be addressed in future research endeavors. Note that as we argued in detail above our setting is different from the one in [52] [53] [54] since we have offline access to the expert and address a different question, i.e. learning a single reward with formal guarantees in continuous MDPs. In this case, there is no need to solve the resulting linear program.Numerical Experiment. In Appendix C, we illustrate our method with a simple truncated Linear Quadratic Regulator (LQR) example to provide better intuition about the method and the proposed sample complexity bounds.In this section, we present essential facts and derivations concerning the Linear Programming (LP) approach to continuous Markov Decision Processes (MDPs). These insights and results will serve as valuable foundations for the subsequent discussions and analysis.The following theorem summarizes the properties of the optimal value function under the assumption that the control model is Lipschitz continuous. Theorem A.1 ([60, Theorem 3.1], [61] ). Under Assumption 2.1, the following hold:1. The value function V ⋆ c is in Lip(X ) with Lipschitz constant L V ⋆ c ≤ L c + γ 1-γ ∥c∥ ∞ L P ; 2.The value function V ⋆ c satisfies the Bellman optimality equationV ⋆ c (x) = min a∈A {c(x, a) + γ X V ⋆ c (y)Q(dy|x, a)}, for all x ∈ X ;3. There exists a γ-discount ν 0 -optimal policy which is stationary deterministic.Next, we characterize the set of occupation measures in terms of linear constraint satisfaction.Theorem A.2 ([62, Theorem 6.3.7]). Consider the convex set of measures, F ≜ {µ ∈ M(X × A) + : T γ µ = ν 0 }, where T γ : M(X × A) → M(X ) is a linear and weakly continuous operator given by(T γ µ)(B) ≜ µ(B × A) -γ X ×A P(B|x, a)µ( d(x, a)), for all B ∈ B(X ).Then,F = {µ π ν0 : π ∈ Π 0 }. Moreover, µ π ν0 , c = V π c (ν 0 ), for every π.A direct consequence of Theorem A.2 is thatV ⋆ c (ν 0 ) = min π µ π ν0 , c = min π∈Π0 µ π ν0 , c = inf µ∈F ⟨µ, c⟩ .Therefore the MDP problem (MDP c ) can be stated equivalently as an infinite-dimensional LP over measuresJ c (ν 0 ) ≜ inf µ∈M(X ×A)+ {⟨µ, c⟩ : T γ µ = ν 0 }. (P c )In particular the infimum in (P c ) is attained and π ⋆ is optimal for the OCP (MDP c ) if and only if µ π ⋆ ν0 is optimal for the primal LP (P c ).Consider the dual pair of vector spaces (M(X × A), Lip(X × A)) and (M(X ), Lip(X )). Then the adjoint linear operator T * γ : Lip(X ) → Lip(X × A) of T γ is given by(T * γ u)(x, a) ≜ u(x) -γ X u(y)P(dy|x, a).Indeed, T * γ is well-defined by Assumption (A2). Moreover, a direct computation shows that (see [28, Pg. 139]) µ, T * γ u = ⟨T γ µ, u⟩ , for all µ ∈ M(X × A), u ∈ Lip(X ).In addition, the dual convex cone of M(X × A) + is the set Lip(X × A) + of nonnegative bounded and Lipschitz continuous functions on X × A. This is because,M(X × A) + ≜ {v ∈ Lip(X × A) | ⟨µ, v⟩ ≥ 0, ∀ µ ∈ M(X × A) + } = {v ∈ Lip(X × A) | v ≥ 0}.The dual LP of (P c ) is given byJ * c (ν 0 ) ≜ sup u∈Lip(X ) {⟨ν 0 , u⟩ : c -T * γ u ≥ 0 on X × A}. (D c )Theorem A.3 (Strong duality). Under Assumption 2.1 on the control model M c , the dual LP (D c ) is solvable, i.e., the supremum is attained, and strong duality holds. That is, J c (ν 0 ) = J * c (ν 0 ) = V ⋆ c (ν 0 ). In particular the value function V ⋆ c is an optimal solution for the dual LP (D c ).Proof. By virtue of [62, Theorem 6.3.8] we have thatV ⋆ c (ν 0 ) = J c (ν 0 ) = J ⋆ c (ν 0) and moreover the supremum definiting J ⋆ c (ν 0 ) is attained by the optimal value function V ⋆ c : X → R. Therefore, the result follows by 1) of Theorem A.1.In this section, we will demonstrate that our formulation, when applied to finite tabular MDPs and a stationary Markov expert policy π E , simplifies to the inverse feasibility set considered in recent studies [52, 53, 54] . The formulation presented in these works extends the LP formulation previously explored in [12, 49, 50, 51] , which specifically addressed deterministic expert policies of the form π E (s) ≡ a 1 . By highlighting this connection, we establish a link between our approach and the existing body of literature on LP formulations for IRL, while also accounting for continuous state and action spaces and more general expert policies. EQUATIONIf π E ∈ Π 0 is a stationary Markov policy, then µ πE ν0 (x, a) = a ′ µ πE ν0 (x, a ′ )π E (a|x) and a ′ µ πE ν0 (x, a ′ ) > 0 [58, Thm. 6.9.1]. Therefore, for any state-action pair (x, a) ∈ X × A, it holds that µ πE ν0 (x, a) = 0 ⇔ π(a|x) = 0. We then get that (3) is equivalent to So we have recovered [52, Lem. 3.2], which forms the basis for the analysis and algorithms in [52, 53, 54] .EQUATIONNext, note that when π E (x) = a 1 , for all x ∈ X and c(x, a) = c(x), for all (x, a) ∈ X × A, then ( 4) is equivalent to c(x) -u(x) = -γ y P(y|x, a 1 )u(y), for all x ∈ X c(x) -u(x) ≥ -γ y P(y|x, a)u(y), for all x ∈ X , a ∈ A\{a 1 }.Therefore, a cost function c ∈ R |X ||A| is inverse feasible if and only if there exists u ∈ R |X | such that c(x) -u(x) = -γ y P(y|x, a 1 )u(y), for all x ∈ X y P(y|x, a 1 )u(y) ≤ y P(y|x, a)u(y), for all x ∈ X , a ∈ A\{a 1 }.By introducing the notation P a ∈ R |X ||X | with P a (x, y) = P(y|x, a 1 ) and noting that the first linear system in (6) admits a unique solution u = (I |X | -γP a1 ) -1 c, we end up that a cost function c ∈ R |X ||A| is inverse feasible if and only if (P a1 -P a )(I |X | -γP a1 ) -1 c ≤ 0, for all a ∈ A\{a 1 }. So we have recovered [12, Thm. 3] which forms the basis for the analysis and algorithms in [12, 49, 50] .Proof. The direction 3) ⇒ 1) is a consequence of the strong duality Theorem A.3 and complementary slackness. Indeed, assume that π E is optimal for (MDP c ) with cost c. Then, by Theorem A.2 µ πE ν0 is optimal to (P c ). By Theorem A.3, the dual (D c ) is solvable and there is no duality gap. Therefore, there exists a u ∈ Lip(X ) such that c -T * γ u ≥ 0, on X × A (feasibility), µ πE ν0 , c = ⟨ν 0 , u⟩ (strong duality).The second equality is equivalent to µ πE ν0 , c -T * γ u = 0, since T γ µ πE ν0 = ν 0 . This proves the desired implication.The implication 1) ⇒ 2) is straightforward.EQUATIONEQUATIONwhere we used that µ πE ν0 , 1 = 1 1-γ andT * γ 1 = 1 -γ, on X × A. Equation (8) states that {v n } ∞ n=1is feasible for the dual (D c ). Moreover, µ πE ν0 is feasible for (P c ). Therefore,EQUATIONBy ( 7)lim n→∞ ⟨ν 0 , v n ⟩ = lim n→∞ T γ µ πE ν0 , v n = lim n→∞ µ πE ν0 , T * γ v n = µ πE ν0 , c. So, by taking the limits in (9) as n → ∞, we conclude that µ πE ν0 is optimal for (P c ). Then, by Theorem A.2 π E is optimal to (MDP c ) with cost c.E ) = ε>0 C ε (π E ) = C 0 (π E ). One can check easily that C(π E ) is a convex cone. To show that C(π E ) is ∥•∥ L -closed in Lip(X × A), let {c n } ∞ n=1 ⊂ C(π E ), such that lim n→∞ ∥c n -c∥ L = 0, for some c ∈ Lip(X × A). Let ε > 0. Then, there exists n 0 ∈ N such that,EQUATION)On the other hand, c n0 ∈ C ε 2 (π E ). Combining this with (10) , we deduce that c ∈ C ε (π E ). Since this is true for arbitrary ε > 0, we get c ∈ ε>0 C ε (π E ) = C(π E ), which proves the desired closedness.Proof. Assume first that c ∈ C ε (π E ) for some ε > 0. Then, there exists ũ ∈ Lip(X ) such thatEQUATIONEQUATION)Since T γ µ πE ν0 = ν 0 , (11) can be written equivalently asEQUATIONLet μ be an optimal solution to the primal (P c) with cost function c. By integrating (12) with respect to μ and using that T γ μ = ν 0 and ⟨μ, 1⟩ = 1 1-γ , we get ⟨μ, c⟩EQUATION)Therefore, by combining ( 13) and ( 14), we getV ⋆ c (ν 0 ) ≤ V πE c (ν 0 ) ≤ V ⋆ c (ν 0 ) + 2 -γ 1 -γ ε.This proves that π E is 2-γ 1-γ -optimal for (MDP c) with cost c. For the inverse inclusion, π E be 2-γ 1-γ -optimal for (MDP c), and let û = V ⋆ c ∈ Lip(X ) (Theorem A.1) be the optimal value function for the forward (MDP c). Then, by virtue of Theorem A.3, the following hold:EQUATIONEQUATION-⟨ν 0 , û⟩EQUATIONNote that (15) holds due to dual feasibility, while ( 16) holds because π E is 2-γ 1-γ -optimal for (MDP c). By setting ũ = û + ε 1-γ ∈ Lip(X ), we get by ( 15) that c -T * γ ũ ≥ -ε, on X × A. Moreover, µ πE ν0 , c -T * γ ũ = µ πE ν0 , c -⟨ν 0 , û⟩ -ν 0 , ε 1-γ ≤ 2-γ 1-γ ε -ε 1-γ = ε,where the inequality holds due to (16) . Therefore, c ∈ C ε (π E ). This concludes the proof.Before stating the proof of Proposition 3.2 we need the following preparation. Without loss of generality, assume that the true cost belongs toC convex ≜ { k i=1 α i c i | α ≥ 0, n i=1 α i = 1},where {c i } k i=1 ⊂ Lip(X × A) are known features. By linearity the true optimal value function belongs to{ k i=1 α i u i | α ≥ 0, k i=1 α i = 1}, where u i = V ⋆ ci (π E ), for all i = 1, . . . , k. Note that by Theorem A.1, {u i } k i=1 ⊂ Lip(X ). By using similar arguments to the proof of Theorem 3.1, we get that a cost function c is inverse feasible, i.e., c ∈ C(π E ) if and only if there existsEQUATIONSimilar arguments hold for any choice of finite-dimensional space or convex set S ⊂ Lip(X ).EQUATIONSince the sequence {α n } n is bounded in R k , there exists a subsequence {α n l } ∞ l=1 such that lim l→∞ α n l = α, for some α ∈ R k . Taking the l → ∞ in (18), we get (17) and so c = k i=1 α i c i ∈ C(π E ). This concludes the proof.Proof. It is easy to check that for every c ∈ C ε (π E ), there exist c ∈ C(π E ) such that µ πE ν0 , c -c ≤ ε, and c -c ≤ ε, on X × A. For example, if ũ ∈ Lip(X ) such thatEQUATIONthen we may choose c = T * γ ũ. Let π be an optimal policy for (MDP c). Then,V π c (ν 0 ) -V πE c (ν 0 ) = µ π ν0 -µ πE ν0 , c = µ π ν0 , c -c + µ π ν0 -µ πE ν0 , c ≤0 + µ πE ν0 , c -c ≤ µ π ν0 -µ πE ν0 , c -c ≤ 2 -γ 1 -γ ε B.5 Proof of Proposition 4.1Note that Proposition 4.1 is a minor extension from [48, Prop. 7] .Proof. Let c ∈ C(π E ), then there exists a certificate u ∈ Lip(X ) such that c -T * γ u ≥ 0, on X × A and ⟨µ πE ν0 , c -T * γ u⟩ = 0. By Theorem 3.1 and its proof, we get that c is inverse feasible and u = V ⋆ c ν 0 -almost everywhere (a.e.). Thus, if c ≡ C, for some constant C, then u ≡ C 1-γ , ν 0 -a.e. We then have c -T * γ u = 0, ν 0 -a.e., and so X ×A (c -T * γ u)dxda = 0.For p ∈ [1, ∞], we denote by ∥•∥ p the p-norm in R n and by x • y the usual inner product.Proof. We consider the following tightening of the semi-infinite convex program (IP).EQUATIONwhere the last equality follows by using that µ πE ν0 , T * γ u = T γ µ πE ν0 , u = ⟨ν 0 , u⟩ and an epigraphic transformation.The assumption that u 1 ≡ 1 and θ > 1 (1-γ)leb(X ×A) ensures feasibility of the convex program (20) and by Assumption 2.1 (A1) the feasibility set is compact and thus the optimal value is finite and is attained. Note that leb(X × A) denotes the Lebesgue measure of X × A. Moreover, since ( 20) is a tightening of (IP) it holds that ε ≤ J nc,u .Consider the infinite-dimensional version of (20),EQUATION)By the characterization of the inverse feasibility set, we have that J = 0 and (c ⋆ , u ⋆ ) is an optimal solution for (21) 4 . Note that ( 21) can be expressed in the standard conic formEQUATIONwhere • (X, L) is a dual pair of vector spaces and l 0 ∈ L;• (B, Y ) is a dual pair of vector spaces and b 0 ∈ B;• K is a positive cone in B and K * is its dual cone in Y , i.e., K * = {y ∈ Y : ⟨y, b⟩ ≥ 0, ∀b ∈ B};• A : X → B is linear and continuous with respect to the induced weak topologies.Indeed, this is the case if we introduce the following:X ≜ Lip(X × A) × Lip(X ), L ≜ M(X × A) × M(X ), B ≜ Lip(X × A) × R, Y ≜ M(X × A) × R, K ≜ Lip(X × A) + × {0}, K * ≜ M(X × A) + × R, b 0 ≜ (0, 1), l 0 ≜ (µ πE ν0 , -ν 0 ), A(c, u) ≜ A 1 (c, u) A 2 (c, u) ≜ c -T * γ u X ×A (c -T * γ u)(x, a) d(x, a).On the pair (X, C) we consider the norms∥x∥ = ∥(c, u)∥ ≜ max{∥c∥ L , ∥u∥ L }, x = (c, u) ∈ X, ∥l∥ * = sup ∥x∥≤1 ⟨l, x⟩ = sup ∥c∥L≤1 ⟨l 1 , c⟩ + sup ∥u∥L≤1 ⟨l 2 , u⟩ = ∥l 1 ∥ W + ∥l 2 ∥ W , l = (l 1 , l 2 ) ∈ L,which are dual to each other. Similarly, on the pair (B, Y ) we consider the norms∥(b 1 , b 2 )∥ = max{∥b 1 ∥ L , |b 2 |}, ∥(y 1 , y 2 )∥ * = ∥y 1 ∥ W + |y 2 |.With this notation in mind, by virtue of [31, Th. 3.3] we have thatEQUATION)(∥c ⋆ -Π Cn c (c ⋆ )∥ L + ∥u ⋆ -Π Un u (u ⋆ )∥ L ),where D γ,θ is an upper bound of a dual optimizer of ( 20) with respect to an appropriately defined dual norm, and ∥A∥ op is the operator norm of A. We will next compute the involved quantities in (23) .We haveEQUATION)Next note that∥Pu∥ L = ∥Pu∥ ∞ + |Pu| L ≤ ∥u∥ ∞ + L P |u| L ≤ max{1, L P } ∥u∥ L ,where in the first inequality we used that P is a stochastic kernel and Assumption 2.1 (A2). Therefore,∥A 1 (c, u)∥ L = ∥c -u + Pu∥ L ≤ (2 + γ max{1, L P }) ∥(c, u)∥ .Moreover,|A 2 (c, u)| ≤ (∥c∥ ∞ + (1 + γ) ∥u∥ ∞ )dim(X × A) ≤ (2 + γ)leb(X × A) ∥(c, u)∥ .All in all,∥A∥ op ≜ sup ∥(c,u)∥≤1 ∥A(c, u)∥ ≤ max{(2 + γ)leb(X × A), 2 + γ max{1, L P }} ≤ (2 + γ) max{1, L P , leb(X × A)}.(25) It remains to compute the constant D γ,θ . To this aim, let {x i } nc+nu i=1 be basis elements in X given by x i = (c i , 0), for i = 1, . . . , n c and x i = (0, u i ), for i = n c + 1, . . . , n c + n u . These are linearly independent by assumption. Then, we define the linear operator A nc,u : R nc+nu → Y by A nc,u (ρ) = nc+nu i=1ρ i Ax i = nc i=1 α i Ax i + nc+nu i=nc+1 β i Ax i , for ρ = (α, β) ∈ R nc+nu . Then, it is easy to see that its adjoint A * nc,u : Y → R nc+nu is given by A * nc,u (y) = [⟨Ax 1 , y⟩ , . . . , ⟨Ax nc+nu , y⟩]. On R nc+nu we consider the norm ∥ρ∥ R = ∥(α, β)∥ R ≜ max{∥α∥ 1 , ∥β∥ 1 } Moreover, we set l0 ≜ [ µ πE ν0 , c 1 , . . . , µ πE ν0 , c nc = l0,1 , ⟨-ν 0 , u 1 ⟩ , . . . , ⟨-ν 0 , u nu ⟩ = l0,2 ]Then, the semi-infinite convex program ( 20) can be written in the formEQUATION)Dualizing the conic inequality constraint in (26) and using the dual norm definition, we get its dualEQUATION)Let y ⋆ be a dual optimizer for (26) . Assume that there exists a constant C > 0 such that∥A * nc,u y ⋆ ∥ R * ≥ C ∥y ⋆ ∥ * .Then by virtue of [31, Prop. 3.2] , we have the boundEQUATIONTo compute the constant D γ,θ , we need to bound the involved quantities in (28) .We will first show that y ⋆ 2 ≥ 0. By Sion's minimax Theorem [75] the duality gap between ( 26) and ( 27) is zero, i.e., J nc,u = Jnc,u . Note however that by construction J nc,u ≥ 0, since for any feasible ρ to (26) it holds that l0• ρ = µ πE ν0 , A nc,u ρ -b 0 ≥ 0. Then, 0 ≤ J nc,u = Jnc,u = ⟨b 0 , y ⋆ ⟩ -θ∥A * nc,u y ⋆ -l0 ∥ R ⋆ = y ⋆ 2 -θ∥A * nc,u y ⋆ -l0 ∥ R ⋆ . Thus, y ⋆ 2 ≥ 0. Therefore, ∥A * nc,u y ⋆ ∥ R * ≥ | ⟨Ax nc+1 , y ⋆ ⟩ | = | ⟨A(0, u 1 ), y ⋆ ⟩ | = | T * γ u 1 , y ⋆ 1 + y ⋆ 2 X ×A T * γ u 1 d(x, a)| = (1 -γ) ∥y ⋆ 1 ∥ W + (1 -γ)dim(X × A)|y ⋆ 2 | ≥ (1 -γ) min{1, leb(X × A)} ≜C ∥y ⋆ ∥ * ,where we used that u 1 ≡ 1, y ⋆ 1 ∈ M(X × A) + and so ∥y ⋆ 1 ∥ W = y ⋆ 1 (X × A), and y ⋆ 2 ≥ 0. In addition, a direct computation gives,∥ l0 ∥ R * = sup ∥ρ∥ R ≤1 l0 • ρ = ∥ l0,1 ∥ ∞ + ∥ l0,2 ∥ ∞ ≤ K c,∞ 1 -γ + K u,∞ .Putting them all together in (28), we getEQUATIONwhere we used that ∥b 0 ∥ = 1. A combination of ( 23), ( 24), ( 25) and ( 29) ends the proof.The symbol |= refers to feasibility satisfaction, i.e., x |= R means that x is a feasible solution for the program R. Z = z = (α, β, ε) ∈ R nc+nu+1 : ∥α∥ 2 ≤ θ, ∥β∥ 2 ≤ θ, µ πE ν0 , -f (z, •) -ε ≤ ε, Λ (-f (z, λ) + ε)dλ = 1, ε ≥ 0 .Note that Z ⊂ R nc+nu+1 is convex and compact and independent of λ ∈ Λ. We show that the set Z is nonempty. As noted in the proof of Proposition 4.2 (Appendix B.6) the assumption that u 1 ≡ 1 and θ > 1 (1-γ)leb(X ×A) considered in Proposition 4.2 and Theorems 4.1-4.2 ensures the feasibility of the convex program (IP) which in particular implies that Z ̸ = ∅. Here leb(X × A) denotes the Lebesgue measure of X × A.Note that the function f : Z × Λ → R is measurable, and linear in the first argument for all λ ∈ Λ. Moreover, by Assumption 2.1 (A1)-(A2), we get that f is bounded in the second argument for all z ∈ Z, and f is Lipschitz continuous on Λ uniformly in Z with Lipschiz constantL Λ ≜ θ √ n c L c + θ √ n u (L u L P + L u ).After introducing this notation, one can see that the random convex program (SIP N ) can be written as,SIP N : inf z∈Z h ⊤ z s.t. f (z, λ (ℓ) ) ≤ 0, ∀ℓ = 1, . . . , N,where h = (0 R nc , 0 R nu , 1) and the multisample {λ (i) = (x (ℓ) , a (ℓ) )} N ℓ=1 is a random element on the product probability space (Λ N , B(Λ) N , P N ). Moreover, (SIP N ) is the scenario counterpart of (IP),IP : inf z∈Z h ⊤ z s.t. f (z, λ) ≤ 0, ∀λ ∈ Λ,where one enforces constraint satisfaction for all the realizations of the uncertainty. Clearly ifz = (α, β, ε) |= IP, then the associated cost function c = nc i=1 α i c i ∈ C ε (π E ).For a fixed reliability level ϵ ∈ (0, 1), the associated chance-constrained program is given byCCP ϵ : inf z∈Z h ⊤ z s.t. P[λ ∈ Λ : f (z, λ) ≤ 0] ≥ 1 -ϵ,where one allows constraint violation with low probability. Now the assumption that u 1 ≡ 1 and θ > 1 (1-γ)dim(X ×A) is sufficient for the existence of a Slater point for the robust convex program (IP), i.e., there exists z 0 ∈ Z such that sup λ∈Λ f (z 0 , λ) < 0. By this fact and by Assumption 4.2, we can apply [29, Theorem 1] and conclude that for N ≥ N(n c + n u + 1, ϵ, δ) it holds thatEQUATIONwhere zN = (α N , βN , εN ) is the optimizer of (SIP N ). Note that by Assumption 4.2, the optimizer zN is uniquely defined and is a Z-valued random variable on (Λ N , B(Λ) N , P N ).EQUATIONFinally, note thatP τ,ξ sup c∈Cn c ,u∈Un u µ πE ν0 , c -T * γ u -⟨µ πE ν0 , c⟩ + ⟨ν 0 , u⟩ ≤ ϵ ≥ P τ,ξ [A ∩ B] ≥ 1 -δ/2,where in the first inequality we have used the monotonicity property of probability measures and the second inequality follows by ( 35), ( 36) and a simple union bound.Proof of Theorem 4.2. By using the same notation as in the proof of Theorem 4.1, we can writeSIP N,m,n : inf z∈Zm,n h ⊤ z s.t. f (z, λ (i) ) ≤ 0, ∀i = 1, . . . , N, where Z m,n = z = (α, β, ε) ∈ R nc+nu+1 : ∥α∥ 2 ≤ θ, ∥β∥ 2 ≤ θ, nc i=1 α i ⟨µ πE ν0 , c i ⟩(τ ) - nu j=1 β j ⟨ν 0 , u j ⟩(ξ) ≤ ε, Λ (-f (z, λ) + ε)dλ = 1, ε ≥ 0 .Let zN,m,n = ( αN,m,n , βN,m,n , εN,m,n ) be the optimizer of SIP N,m,n and let cN,m,n = nc i=1 αN,m,ni c i be the associated cost function. We first fix multi-samples τ, ξ. Similarly as in Theorem 4.1, we can conclude that for N ≥ N(n c + n u + 1, g( ϵ LΛ ), δ/2),P ζ [y ∈ Λ N : zN,m,n (y, τ, ξ) |= IP m,n,ϵ (y, τ )] ≥ 1 -δ/2,where IP m,n,ϵ is the ϵ-perturbed robust counterpart of SIP N,m,n given byIP m,n,ϵ : inf z∈Zm,n h ⊤ z s.t. f (z, λ) ≤ ϵ, ∀λ ∈ Λ,Integrating over the whole probability space (Ω m ⊗ X n , P τ,ξ ), we getEQUATIONHowever, by virtue of Proposition B.1, for n ≥EQUATIONwith probability P y,τ,ξ at least 1 -δ/2. Combining (37), (38) and the bounds in Theorem 2 of [76] by a simple union bound completes the proof.We consider a one-dimensional truncated Linear-Quadratic-Gaussian (LQG) control problem comprising a linear dynamical systemx t+1 = Ax t + Ba t + ω t , t ∈ N,and a quadratic state cost c(s, a) = Qx 2 + Ra 2 , where A, B ∈ R, Q > 0, R > 0. We assume that state and action spaces are given by X = A = [-L, L] for some parameter L > 0. The disturbances {ω t } t∈N are i.i.d. random variables generated by a truncated normal distribution with known parameters µ and σ, independent of the initial state x 0 . Thus, the process ω t has a distribution densityf (s, µ, σ, L) = 1 σ ϕ( s-µ σ ) Φ( L-µ σ )-Φ( -L-µ σ ) , s ∈ [-L, L] 0 o.w. ,where ϕ is the probability density function of the standard normal distribution, and Φ is its cumulative distribution function. The transition kernel P has a density function p(y | x, a), i.e., P(C | x, a) = C p(y | x, a)dy for all C ∈ B(X ), that is given by p(y | x, a) = f (y -Ax -Ba, µ, σ, L).In the special case that L = +∞ the above problem represents the classical LQG problem, whose solution can be obtained via the algebraic Riccati equation [77, p. 372] . By referencing [31, Lemma7.1], we can readily conclude that Assumption 2.1 holds in this context with specific constantsL P = 2L max{A, B} σ 2 √ 2π Φ L-µ σ -Φ -L-µ σ , L c = max{Q, R}2L.As value function u : X → R we use a simple polynomial of degree 2 (n u = 3) such thatu(x) = nu i=1 β i u i (x), u i (x) = x i-1 ,whereas the cost function c : X × A → R is approximated by the following weighted sum (n c = 9)c(x, a) = nc i=1 α i c i (x, a), where c 1 (x, a) = 1, c 2 (x, a) = x, c 3 (x, a) = a, c 4 (x, a) = xa, c 5 (x, a) = x 2 , c 6 (x, a) = a 2 , c 7 (x, a) = x 2 a, c 8 (x, a) = xa 2 , c 9 (x, a) = x 2 a 2 .For the simulation, the parameters are set as L = 10, A = -1.5, B = 1, Q = R = 1, µ = 0, σ = 1, and γ = 0.99. The code for these experiments can be found at github.com/RAPACIRLCS/code. The experiments were run on a workstation with an AMD Ryzen 9 5950X CPU (16 cores) and 128GB of RAM.Sampled Inverse Program with known transition kernel. In our first experiments highlighted in Figure 3 , we focus on the sampled inverse program SIP N . More precisely, we solve the program SIP N for various choices of sample sizes N and denote its corresponding optimizers as ( αN , βN , εN ) and its extracted cost function as cN = nc i=1 αNi c i . Figure 3a shows the probability of the learnt cost function cN being (ε N + ϵ)-inverse feasible for various choices of ϵ and N . The plotted probability represents the empirical probability derived from 1000 experiments. It is evident that, for a constant parameter ϵ, the likelihood of being inverse feasible grows with the increase of the sample size N . Additionally, for a constant sample size N , the probability of being inverse feasible increases as the parameter ϵ decreases. Both of these trends align with and support our theoretical findings as outlined in Theorem 4.1. Figure 3b shows the objective function of program SIP N for various choices of sample sizes N . Since these are random programs, we plot the empirical average (solid line) and its corresponding standard deviations (shaded area) derived from 1000 independent experiments. As expected, the objective value εN increases as a function of the sample size N . Figure 3c visualizes the theoretical sample complexity of Theorem 4.1, i.e., for various choices of δ and ϵ, we plot the ), δ). The variation parameter is set to ∆ = 1 • 10 -7 . Plot (d) compares the discounted long-run costs V π cN (ν 0 ) for the average cN of the learnt costs cN under the expert policy π E (red) and the optimal policy (blue). The solid line plots average over 1000 independent experiments, where the shaded area shows the standard deviations. sample size N = N(n c + n u + 1, g( ϵ LΛ ), δ). To simplify the computation, we used the closed form upper bound for the function N derived in [78] and given asN(n, ϵ, δ) ≤ 2 ϵ log 1 δ + 2n + 2n ϵ log 2 ϵ .When comparing Figure 3a and Figure 3c , we can see that there is a significant gap between the empirical and theoretical bounds. The dynamics of a variation in ϵ, however, match the empirically observed behaviour. Figure 3d visualizes the performance of the learnt cost cN by comparing the discounted long-run cost of the expert policy under this learnt policy V πE cN (ν 0 ) with its theoretical lower bound min π∈Π V π cN (ν 0 ). According to Theorem 4.1 and Proposition 3.1 for large N this difference vanishes with high probability, this behaviour can be observed in the plot. To reduce the computational effort replace in Figure 3d the learnt cost cN with its empirical average, denoted cN , taken over 1000 independent experiments. More precisely, for 1000 initial conditions x 0 ∼ ν 0 we plot V πE cN (x 0 ) and the theoretical lower bound min π∈Π V π cN (x 0 ). trends shown in Figure 3 . As expected, an increase in the number of samples increases the confidence of learning a cost function cN,m,n,k that belongs to the inverse feasibility set C εN,m,n,k +ϵ (π E ).It can be seen how, even for the largest possible ϵ, to reach a certain empirical confidence the SIP N,m,n,k program requires many more state-action samples N compared to the SIP N program. When comparing the empirical confidence of a given ϵ, N , and k with the theoretical sample complexity, following Theorem 4.2, of k corresponding to the same ϵ and N it can be seen that the empirical sample performance of SIP N,m,n,k is much more efficient.1. Claims Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? Answer: [Yes] Justification: The abstract and introduction do reflect and summarize the paper's contribution and scope. In the sections following we provide the rigorous statements of these contributions.Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments? Answer: [Yes] Justification: In our plots we show average performance over 1000 independent experiments (solid lines), but additionally we show the corresponding standard deviations with the shaded areas, see Figure 3 . In Figure 4 we run 1000 independent experiments and plots show empirical probabilities computed from them.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean. Justification: Yes, it does.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: [NA] Justification: Our work is a theoretical result on inverse reinforcement learning and has not direct, neither positive nor negative, societal impacts.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). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: Due to the theoretical and mathematical nature of our work, this question does not apply. The risks stated in the question are not present in our work.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [NA] Justification: We do not use any existing assets.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [NA] Justification: We do not introduce any new assets in our work.Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?Answer: [NA] Justification: The paper does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 
institutional review board (irb) approvals or equivalent for research with human subjects: 
 Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?Answer: [NA] Justification: Our paper does not involve research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.Note that P π ν 0 is uniquely determined by the transition law P, the initial state distribution ν0 and the policy π [57, Prop. 7.28].For the discounted policy optimization problem considered in this paper it suffices to restrict our search to stationary Markov policies,[58, Thm. 5.5.3]. However, the expert policy πE can be nonstationary and history-dependent.The second condition in [53, Def. 2] is trivially satisfied with zero error since C(πE) ⊂ C ε (πE).(Cited on page 27.)Without loss of generality we may assume that X ×A (c ⋆ -T * γ u ⋆ )(x, a) d(x, a) since we can always rescale the optimal cost and value function by the same scale factor. 
 
 Appendix:  


Decision: The reviewers agree that the paper makes significant contributions to the IRL community. Importantly, this is the first work to solve the (reward learning) inverse problem in tabular MDPs with a tractable algorithm. However, in the continuous state-action case, the exponential dependence on $\text{dim}(X \times A)$ is not supported by any lower bound, which raises questions about its tightness. In general, the paper contains a lot of material that, understandably, is difficult to convey within the 8 pages allowed for a conference submission. This makes the paper's organization, in the reviewers' opinion, confusing, as the current version dedicates too much space to the continuous case, whose results (as discussed above) are not entirely satisfactory.

All things considered, I recommend accepting this paper in light of its clear advancement of the IRL literature. **At the same time, I strongly recommend that the authors revise the paper for the camera-ready version, taking advantage of the additional page, to incorporate the reviewers' inputs about the issues with the presentation, e.g., give more space to the results for the tabular case (tractability) and clarify the limitations of the analysis for the continuous case (exponential dependence on $\text{dim}(X \times A)$).**

Reviews: review: paper_summary: paper_summary: The paper
1) establishes a formal framework for studying the problem of continuous state- and action-space inverse reinforcement learning (i.e. given an expert policy, recovering a set of cost functions for which the policy is optimal)
2) provides theoretical results characterizing the set of cost functions that would be recovered based on perfect knowledge of the expert policy assuming the ability solve an infinite-dimensional linear feasibility problem
3) provides a method for approximating the the infinite-dimensional problem using scenario approach to reduce the dimensionality of the problem, making the theoretical model computationally feasible
4) provides PAC results for the case where we only have access to a finite set of samples from the expert policy
strength_weakness: strength_weakness: - The paper certainly contains enough material for a substantially longer journal paper - some of the sections could benefit from being longer, trying to convey more intuitions and context about the presented theory. More thorough empirical evaluation ( /illustration) would also be beneficial to give readers a better intuitions for what are the actual numbers involved and what's the computational scalability beyond the simple example provided. That said, this is infeasible within the scope of a single conference paper on top of all that the authors already did and on balance, I personally think this paper is still a worthy contribution to NeurIPS readership as is. 
- The bounds provided by the theorems don't always seem meaningful. In the only example presented suggests >10^23 samples are needed to get guarantees - and that is on an super-simple problem with a 1D state-space and 1-D action space! But other theorems seem to provide more meaningful results, and I do consider the work presented a good starting point for further analysis.
questions: questions: - In Section 4.1 you claim that "the inverse feasibility set C(πE) contains some solutions that arise
from mathematical artifact". Sure, translation by a constant can be considered an artifact, but is this the case for all potential-shaping? Isn't the identifiability issue a deeper issue than a mere "mathematical artifact"? On a fixed environment, optimal policies for meaningfully different rewards may happen to coincide due to the environment structure; however, change the environment a bit (e.g. by changing the transition kernel), and the optimal policies may no longer coincide (see e.g. work on "transferability" or rewards learnt via IRL). It's a frequently raised selling point of IRL that the reward is a more generalizable representation of the goal than a policy.
- Do you have an intuitive explanation for why the constraint on the epsilon constraint on the consistency of the cost and value function is enforced point-wise from below and in expectation from above?

Minor points and suggestions:
- In the first paragraph, I don't fully understand your third motivation for inverse decision making: I suggest either explaining it better (and how it meaningfully differs from motivation 2) or removing it to prevent confusion.
- There seems to be minor tension between the end of the initial introduction, ending by emphasizing "especially in safety-critical systems with potential fatal consequences", and then just after that, in the second sentence of contributions, you "emphasize that we are interested in situation where the cost function is of interest in itself". The first point seem to point in the direction of using the recovered cost to control a safety-critical system, while the second is emphasizing the cost in itself (supposedly as opposed to being just instrumental for synthesizing an apprentice policy). Could you clarify?


Here are a few minor typos (or subjective suggestions) I noticed:
- "infinitely-uncountably-many constraints" - I think saying "uncountably many" implies infinitely many and thus is sufficient as a shorter term. If you insist on including both, I'd write uncountably-infinitely many, since the uncountably is qualifying the "infinitely".
- l. 108 missing comma after citation
- "\gamma-discount \nu_0 optimal policy" - the "discount" sounds strange. Maybe \gamma-discounting would sound better?
l. 330 "Theorem" -> theorem
l.379 missing closing brackets
l. 550 extra comma before "under"
l. 838 sate -> state
l. 841 performs -> performance
limitations: limitations: - As said, the bounds provided are not always useful in practice yielding completely impractical requirements.
- The applicability to real-world problems is unexplored in the paper and requires further work.
paper_summary: paper_summary: This paper investigates the problem of inferring cost functions from observed optimal behavior in continuous state Markov Decision Processes. The authors develop their theoretical framework initially assuming full access to the expert policy. To address the issue of trivial solutions, they introduce a linear normalization constraint. The study then progresses to a more practical scenario, providing error bounds for cost estimation when working with limited expert samples and a generative model. This approach bridges the gap between theoretical analysis and practical applications in inverse reinforcement learning for continuous domains.
strength_weakness: strength_weakness: - The paper appears to present a series of theorems without providing sufficient intuitive explanations or justifications. This approach can make the work difficult to understand for reviewer.

- Despite the theoretical rigor, the paper seems to lack substantial practical demonstrations or empirical results. This absence makes it challenging to assess the real-world applicability.

- The algorithms proposed might be theoretically sound but potentially impractical for real-world applications. The paper may not adequately address computational complexity or scalability issues that could arise when applying these methods to large-scale or complex problems.
questions: questions: See Weakness
limitations: limitations: NA
paper_summary: paper_summary: The paper proposes an optimization formulation of the inverse RL problem. The paper discusses the properties of the solution to the optimization problem. It further discusses how to reduce of the raw problem to a computation feasible one. It gives the theoretical analysis on the approximation error and sample complexity.
strength_weakness: strength_weakness: 1. The paper's result lacks benchmark. First, it lacks comparison with existing results, which makes it hard to evaluate the improvement made by the paper. Second, the paper doesn't reduce its general result to simpler special cases, like tabular or linear MDPs, so it's hard to get an idea how the result looks like on these more familiar examples. Third, the paper doesn't give insights on the hardness of the problem, namely, a lower bound. Without these benchmarks, the first impression is the bounds given by the paper are very loose, which heavily depends on $\Vert\cdot\Vert_\infty$ or $\Vert\cdot\Vert_L$ norms. 

2. Part of the result is unintuitive. In Proposition 4.2, the notation $\min\{1, d\}$ seems to imply the possibility $d < 1$, which seems to be unintuitive. Can the authors give a more detailed explanation on it? And the bound shows that the bigger $\theta$ is, the better the result is. In this case, what's the point of introducing $\theta$, instead of directly letting it be $\infty$?
questions: questions: 1. For challenge (a), it seems the paper's solution only excludes constant functions. There should still be ambiguity in the optimal solution. In this case, how do the authors ensure $c^\star, u^\star$ in the later sections are well-defined? 

2. For figure (c) in the experiment, the $x$-axis looks to be extremely large, with the values almost not changed on the whole axis. And the value $\delta$ also becomes extremely small. What's the value of $\varepsilon$ in this figure and what happens if one sets $\varepsilon$ values to be the same as in figure (a)?
limitations: limitations: /
paper_summary: paper_summary: This paper addresses inverse RL in discounted MDPs with continuous state and action spaces. First, the paper delves on the design of a suitable solution concept, which results in learning a reward that makes the expert at least approximately optimal plus a linear normalization constraint. Then, the paper studies the computational problem of extracting the latter solution with knowledge of the expert's policy and transitions. Finally, the paper provides a sample complexity result for the setting in which a dataset of trajectories collected by the expert and a simulator of the environment are available.
strength_weakness: strength_weakness: - The presentation is confusing and could be improved in many ways to make the paper more accessible;
- The paper provides mostly negative statistical results, despite the relatively strong assumptions. This is in contrast with the premise of the work to provide solutions for IRL in continuous state and action spaces;
- The motivation for some design choices (e.g., linear normalization constraint) and assumptions appears to be weak or absent.
questions: questions: ## Last comment after the author-reviewer discussion deadline

Dear Authors,

Sorry if my reply comes a little late on this. Having read the last replies, I wanted to get back to the manuscript and (briefly) to the recent papers (Metelli et al., 2021, 2023; Lindner et al., 2022; Lazzati et al., 2024a,b) on the reward feasible set formulation. I believe I have now a more robust understanding of the paper's contribution and I am changing my evaluation and confidence accordingly. A few words below to explain my reasons.

1)  Prior works have presented statistically efficient algorithms to learn the feasible reward set already. Especially, Metelli et al. (2023) did that for the tabular setting with generative model, Lazzati et al. (2024a) for tabular setting with offline data. The setting of this paper is slightly different (basically a mix of them, having offline demonstrations but online generative model). However, getting results for the latter setting from a combination of (Metelli et al., 2023; Lazzati et al., 2024) looks trivial. There is a very important caveat though: Their approaches are computationally intractable due to the nature of the feasible reward set. Lazzati et al. (2024) sidestep the issue by reframing the problem as a "reward checker". Given a reward, they have a tractable and efficient algorithm that can tell whether the reward belongs to the feasible set whp. This paper instead proposes an algorithm to provide a single reward belonging to the feasible set. Thus, the claim that this is the first work to solve the (reward learning) inverse problem in tabular MDPs with a tractable algorithm seems to be correct. This is a significant contribution in my opinion.
2) The main problem arise in the continuous state-action setting instead. The authors are saying that their expert's query and sample complexity are still polynomial for the considered "Lipschitz" MDP. However, to my understanding the number of sampled constraints should also be considered in the sample complexity, as they also require querying the generative model for one step. This makes the resulting sample complexity exponential in $dim (X \times A)$. The authors claim that the exponential dependence with the state and action dimensionality is inherent to the problem. Normally, in RL theory literature one would then prove a lower bound that support the claim to state that the problem is far-fetched, instead of claiming it is "solved" for low-dimensional settings.

Overall, I think the paper has valuable contributions and even the tabular results alone shall be communicated to the community. Other reasons for acceptance include a novel approach for reaching the tabular result and a nice concept of inverse feasibility. However, I'm changing my evaluation to only weak accept because most of the space in the paper is dedicated to a continuous space setting that appears to be mostly a dead end.

Some additional notes to the authors:
- Interestingly, the reward-feasibility notion seems to match the reward compatibility of the concurrent Lazzati et al. (2024b). The fact that two independent efforts reached a similar formulation may be further proof that this is the right direction;
- The discussion on the comparisons with previous papers above is extremely valuable and I suggest the authors to include that in a final version of the paper;
- While the authors may have a point that reward feasible set formulation is still ill-posed from a computational perspective, it looks well-posed to me in a statistical sense (which is arguably what matters the most);
- Having a deeper understanding of the paper required me quite some back-and-forth interactions with the authors. Perhaps some of the blame is on the presentation here, which could be made more accessible for a RL theory audience. I strongly encourage the authors to include the version of the bounds in the last comment in a final version.




----
----
----
----

This paper tackles an interesting problem in the recent wave of inverse RL with theoretical guarantees. While I have seen some recent works studying both IRL without online access to the expert's policy (Lazzati et al., Offline inverse RL, 2024) and IRL in continuous state spaces (Lazzati et al., How to scale RL to large state spaces? A provably efficient approach, 2024. Concurrent), this appears to be the first attempt at provably efficient IRL with continuous states and actions, as well as the first with this optimization perspective. Thus, I would tend to reward the paper for the novelty and originality. However, the provided results are mostly negative (even under strong assumptions, the number of samples required scales exponentially with the target accuracy) and they seems to leave IRL with continuous states and action as an open problem. This together with a cluttered presentation makes me lean towards a negative evaluation. There is a chance I am not understanding crucial parts of the submission, for which I encourage the authors to revise the presentation. I further provide some detailed comments below.

FUNCTION CLASS

The paper does not seem to commit to a specific (known) function class, such as linear MDPs, linear-mixture MDPs, etc. Trying to provide general results is definitely a feature, but not when generality hampers the ability to provide positive results (although in more restrictive settings).

INTERPRETABLE RESULTS

To my understanding, the paper provides essentially two main theoretical results: (1) approximation guarantees for computing a reward with knowledge of the expert's policy and transitions with a randomized program, (2) a sample complexity results with access to a dataset of trajectories obtained with the expert's policy and a generative model to estimate transitions. Both of the results are quite hard to interpret and a clear departure from how analogous results are presented in prior works. For instance, it would be important to understand the sample complexity as a function of the dimensionality of states and actions and other characteristics of the MDP. It is hard to extract those information from Th. 4.2.

SOLUTION CONCEPT

Instead of attempting at learning the feasible set of rewards, the paper proposes to add a linear normalization constraint. The latter choice is supported through Proposition 4.1, which assures that constant rewards can be avoided this way, but looks rather weak as a motivation in general. Aside from avoiding constant reward, we would like to be sure that the resulting reward is useful for a downstream application (such as one between the applications mentioned in the Introduction). The paper does very little to make a case in this sense.

On the same line, the Proposition 3.3 assures that the existence of at least one "good" reward in the feasible set. Do we have a similar guarantee for the reward resulting from the normalization constraint?

TYPOS

A few typos I noted while reading: 
- l.73 "of"
- l.108 missing full stop
- l.254 "F" at start of the sentence
limitations: limitations: A section discussing limitations could have been included at the end of the paper.

Comments: title: Clarification on other raised points (Cont'd)
Clarifications on other raised points.
Detailed comparison to prior works (Cont'd)
Detailed comparison to prior results
comment: Thank you for your valuable feedback. We understand your concern regarding the phrasing in the paragraph, particularly the mention of reward shaping and the reference to "mathematical artifacts.". We will revise the phrasing to ensure that reward shaping and underdeterminacy are not inadvertently grouped with mathematical artifacts, thereby maintaining a clear distinction between them. Indeed, these issues cannot be fully resolved unless, for example, one has access to multiple expert policies or environments for comparison. Thank you again for pointing this out.
Dear Reviewer,

As the discussion window is closing soon, we wanted to check if you have any remaining questions or concerns. We would be happy to provide further clarification on any points that may need additional discussion.

Thank you again for your time and valuable feedback.

Best regards,
The Authors
Thank you for the thorough review and for highlighting this important point. We will incorporate the suggestion by expanding on the need for theoretical guarantees and the limitations of relying solely on strong empirical results. This expanded discussion will help clarify the nuances of why empirical successes, while valuable, may not always suffice in contexts where formal performance bounds are crucial. We believe this will provide a more comprehensive understanding, particularly for those from allied fields who may not be as familiar with the intricacies of reinforcement learning. Thank you again for your constructive feedback.
> Can the authors elaborate here? What does make their assumptions minimal? Ass. 2.1 appears to be rather strong: Does this include tabular MDPs? Would you provide references to support the claim that the assumption is standard?

For finite discounted MDPs the existence of an optimal policy and the Bellman optimality equation hold automatically. However, in continous MDPs this is not the case. 

Assumption 2.1 involves the usual continuity-compactness conditions [ 56 ]  -which ensure the existence of an optimal policy and the Bellman optimality equation - together with the Lipschitz continuity of the
elements of the MDP (see, e.g., [57]) - which ensures the Lipschitz continuity of optimal value function.  The Lipschitz continuity assumption encompasses various probability
distributions, such as the uniform, Gaussian, exponential, Beta, Gamma, and Laplace distributions, among others. 
Consequently, Assumption 2.1 accommodates a broad range of MDP models and allows for the
consideration of smooth and continuous dynamics that reflect the characteristics of several real-world
applications, such as robotics, or autonomous driving. (see lines 179-187) 

In the tabular MDP setting, our analysis holds without any additional assumptions on the MDP model. This is because we bypass the need for sampling constraints by solving a finite linear program using off-the-shelf solvers. In contrast, [48, 49] assume that the problem is $\beta$-separable and that every state is reachable with probability $\alpha$. For the MDP with a continuous state space in [50], the authors assume that the transition law density has an infinite matrix representation. Our Assumption 2.1 on the MDP is significantly milder and includes the representation considered in [50] as a special case.

> Interpretation: Can the authors provide {expert's query complexity, sample complexity} rates in the form $O(S^x A^y (1 - \gamma)^{-k} \epsilon^{-z} ...)& as it is common in tabular reinforcement learning literature? Can they provide analogous for the function approximation setting?


For tabular MDPs, offline access to expert for tabular MDPs and a generative model we require  $m = \mathcal{O}\left(\frac{|X||A|(\log(\frac{|X||A|}{\delta})}{(1-\gamma)^2\varepsilon^2}\right)$ expert samples and $K|X||A| = \mathcal{O}\left(\frac{X|^2|A|\log(\frac{|X|^2|A|}{\delta})}{\varepsilon^2}\right)$ calls to the generative model and solve the resulted sampled finite LP with $|XA|+|X|$ variables and $|X|$ constraints in polynomial time, to learn a cost function that is $\varepsilon$-inverse feasible with probability $1-\delta$.


For continous MDPs when we use $n_u$ basis functions for the value function and $n_c$ basis functions for the cost function we need $m = \mathcal{O}\left(\frac{n_c\log(\frac{n_c}{\delta})}{(1-\gamma)^2\varepsilon^2}\right)$ expert samples and $K = \mathcal{O}\left(\frac{n_u\log(\frac{n_u N}{\delta})}{\varepsilon^2}\right)$ calls to the generative model per constraint and $N=\mathcal{O}(\exp^{dim(X\times A)})$ sampled constraints and and solve the resulted sampled finite LP with $n_u+n_c$ variables and $N$ constraints in polynomial time to learn a cost that is $\varepsilon+\varepsilon_{\textup{approx}}$-inverse feasible with probability $1-\delta$

Note that as we argued in detail above our setting is different from the one in [51-53] since we have offline access to the expert and address a different question, i.e. learning a single reward with formal guarantees in continuous MDPs. For the PAC learning scenario considered in [51-53] our bounds translate in $m = \mathcal{O}\left(\frac{|X||A|(2-\gamma)^2\log(\frac{|X||A|}{\delta})}{(1-\gamma)^4\varepsilon^2}\right)$ expert samples and $K|X||A| = \mathcal{O}\left(\frac{(2-\gamma)^2|X|^2|A|\log(\frac{|X|^2|A|}{\delta})}{(1-\gamma)^2\varepsilon^2}\right)$ calls to the generative model. There is no need to solve the  sampled program. The factors $\frac{2-\gamma}{1-\gamma}$ arise from Prop. 3.3.

> Solution concept

Overall, the purpose of the normalization constraint is to exclude a large class of meaningless solutions. In particular, we state and prove that the normalization constraint rules out a wide class of trivial solutions, i.e., all constant functions and inverse solutions of the form  $c=T_\gamma^* u$, an outcome devoid of physical meaning and a mathematical artifact. The recovered cost is $\varepsilon+\varepsilon_{\textup{approx}}$-inverse feasible with probability $1-\delta$. The interpretation of this guarantee is given in Prop. 3.1 and 3.3. In particular, note that by adopting the terminology of Lazzati et al. 2024 the recovered cost is  $\varepsilon+\varepsilon_{\textup{approx}}$- compatible with respect to the expert. Investigating how to define different normalization constraints and the implications for the resulting learned cost is a topic of future research.
>The papers [51-53] definitely discuss the ill-posedness.

We respectfully disagree with this point. The authors in [51-53] address the a*mbiguity problem* by estimating and learning the entire inverse feasibility set—essentially, the full set of cost functions that make the expert policy optimal. While this is an interesting theoretical challenge, it is impractical in reality. Even in the simplest finite MDP setting, with a known expert policy and transition law, computationally learning the entire inverse feasibility set is impossible. This set is uncountably infinite, and only a few classes of inverse-feasible costs can be represented analytically, such as trivial solutions of the form {${c\equiv C | C\in\mathbb{R}}$} and {$c=T_\gamma^*u | u\in\mathbb{R}^{|X|}$}.

Please note that in"How to Scale IRL to Large State Spaces? A Provably Efficient Approach" (2024 Concurrent), the authors explicitly say (page 5):

*Limitations of the Feasible Set. Lack of Practical Implementability: It contains
a continuum of rewards, thus, no practical algorithm can explicitly compute it.*

>The authors in these works study solely how to deal with the unknown transition law and how to sample efficiently from the expert policy. Isn't this what we care about in understanding the sample efficiency of inverse RL?

If one aims to estimate only the entire inverse feasibility set, there are two primary sources of error: estimation error due to the unknown expert policy and estimation error due to the unknown transition law. Consequently, the relevant sample complexities are the expert sample complexity and either the number of queries to the generative oracle (for the generative model) or the number of episodes (for the forward model).

However, if the goal is to extract a single cost function that is $\varepsilon$-inverse feasible for large-scale finite MDPs, we must manage  a feasibility problem of $|X||A|$ constraints and variables of dimension $|X||A|$. This challenge also applies to the formulations in [50-53]. For continuous MDPs, the problem becomes even more complex due to its infinite-dimensional nature. In addition to the earlier sources of error, we must also account for approximation error due to function approximation and optimization error in solving the feasibility problem. This results in additional iteration complexity if using gradient-based algorithms or an the number of sampled constraints if choosing constraint sampling techniques.

This theoretical challenge is not addressed in [51-53] or in the new 2024 submissions. We emphasize that for small finite tabular MDPs, one can simply solve a finite linear program in polynomial time.

>The sample complexity depends on MDP characteristics, such as state-action space dimension (exponentially)
Exponential sample complexity in state-action dimension is perceived as a negative result in reinforcement learning literature

First of all, we would like to highlight that the corresponging bound is a part of the the big amount of theoretical concepts covered by the paper.

The exponential growth in sample complexity with respect  to the dimensions of the state and action space, as demonstrated in our paper, is an unavoidable consequence of Bellman's curse of dimensionality. Given the generality of our bounds, this growth is inherent. However, it's important to note that even with this exponential growth, settings with low-dimensional MDPs can still achieve practically useful convergence, as evidenced by our  theory and numerical experiments on the one-dimensional LQR problem.

In contrast to heuristic IRL algorithms for continuous state and action spaces, where no guarantees are provided, our work proves convergence and offers explicit bounds. While our bounds for high-dimensional MDPs may not yet be practically useful, we view this paper as a crucial first step toward developing provably efficient algorithms for continuous IRL problems.

Furthermore, as we’ve already discussed, the works [51-53] and the recent 2024 contributions do not address the extraction of a cost function, i.e., solving a large-scale, even infinite-dimensional feasibility problem for continuous MDPs. In these cases, the exponential growth in the number of constraints does not appear in the finite sample analysis.

Finally, the only work that extracts a single cost function in continuous state and discrete action spaces, [50], also suffers from exponential dependence on the dimensionality of the state space.
I'd like to thank the authors for a thorough response to the points raised in the review. I'll gladly keep the "accept" recommendation. 

Regarding the discussion on
> Isn't the identifiability issue a deeper issue than a mere "mathematical artifact"?

Just to clarify: I'm happy with your technical solution, and the point I was raising was more of a subtle phrasing issue. What I was objecting to was mainly that in the first paragraph, you mention reward shaping and then you say that "*all* these examples illustrate ... mathematical artifacts". I'd say your solution correctly filters out mathematical artifacts and meaningless rewards. However, the issue of underdeterminacy (e.g. with respect to reward shaping) can remain (unless we have access to e.g. multiple environments) and is important in IRL, rather than being mere mathematical artifact (which is a label I'm ok with in relation to the rewards you're filtering out). Maybe a slight rephrasing may help not to sound like putting all these transformations (incl. general reward shaping) in a single basket.
**Comparison to [51,52,53]**

The characterization of the inverse feasibility set which forms the basis for the analysis in [51,52,53] is the following: 

Let $\pi_E$ be stationary Markov. A cost function $c$ is inverse if and only if there exists $u\in\mathbb{R}^{|X||A|}$ and nonnegative $L\in{\mathbb{R}}^{|X||A|}$ such that $c(x,a)-u(x)+\gamma\mathbb{E}_{y\sim P(\cdot|x,a)}[u(y)] = L(x,a)\mathbb{1}[\pi_E(a|x)=0]$, for all $(x,a)\in X\times A$.

This formulation considers a stationary Markov expert, whereas our proposed approach is independent of the complexity of $\pi_{E}$. Their formulation cannot be extended to MDPs with continuous state and action spaces due to the presence of the term $\mathbb{1}[\pi_E(a|x)=0]$. For continuous distributions, $\pi_E(a|x)=0$ always, making the extension infeasible. Additionally, the term $\mathbb{1}[\pi_E(a|x)=0]$ significantly complicates the estimation of the inverse feasibility set. To address this challenge, they assume active querying of $\pi_E$. In contrast, our optimization-based framework formulates the problem using occupancy measures instead of policies. This allows us to tackle the more challenging learning scenario where the learner has access only to a finite set of expert trajectories and is not permitted to query the expert for additional data during training. In our formulation, efficiently estimating the term $\widehat{<\mu^{\pi_{\textup{E}}}_{\nu_0},c>}$ via sample averages is straightforward (see the sampling process in lines 361-367), and the estimation error can be computed using a simple Hoeffding bound.

In [51, 52, 53], the authors focus exclusively on estimating the inverse feasibility set, bypassing the task of learning a single cost with formal guarantees. For the tabular setting with a generative model and an (online) interactive expert, [53] provides a sample complexity lower bound of $\mathcal{O}\left(\frac{|X||A| (|X|+\log(\frac{1}{\delta}))}{(1-\gamma)^3 \varepsilon^2}\right)$ and proposes a sampling strategy that achieves this bound up to logarithmic factors. It is important to note that when estimating the inverse feasibility set, the sample complexities of interest are the number of queries to the generative model and the expert sample complexity. In other words, in our Thm 4.2, the number of sampled constraints required to solve the reduced finite LP for extracting a single cost is not necessary (recall that the curse of dimensionality appears only in the number of sampled constraints).

In our offline setting for tabular MDPs, we require $m = \mathcal{O}\left(\frac{|X||A|(2-\gamma)^2\log(\frac{|X||A|}{\delta})}{(1-\gamma)^4\varepsilon^2}\right)$ expert samples and $K|X||A| = \mathcal{O}\left(\frac{(2-\gamma)^2|X|^2|A|\log(\frac{|X|^2|A|}{\delta})}{(1-\gamma)^2\varepsilon^2}\right)$ calls to the generative model. The factors $\frac{2-\gamma}{1-\gamma}$ arise from Prop. 3.1 and 3.3.

Furthermore, we address the challenge of extracting a single cost with formal guarantees for continuous MDPs by incorporating a normalization constraint, employing function approximation, and using constraint sampling techniques. For tabular MDPs, this task is straightforward, as one only needs to solve a finite MDP using off-the-shelf solvers in polynomial time.

**Comparison to "How to Scale IRL to Large State Spaces? A Provably Efficient Approach" (2024 Concurrent)**

The authors consider the setting of linear MDPs, where the agent can query the expert in any state and interact online with the environment (forward model). By generalizing the notion of the inverse feasibility set and introducing the *cost compatibility* framework, they provide a provably efficient algorithm for MDPs with continuous states and discrete actions to estimate the compatibility of all costs with high accuracy.

Interestingly, in our versatile formulation, any cost that is $\varepsilon$-inverse feasible is also $\frac{1-\gamma}{2-\gamma}\varepsilon$-compatible (Prop. 3.1). This key feature, which seems absent and unaddressed in the formulations of [51-53], highlights another significant distinction in our approach. We conjecture that by employing the same Ridge regression estimators as in [Jin et al., "Provably Efficient RL with Linear Function Approximation" (2020)], one could establish similar efficient bounds for continuous $X$ and $A$. We leave this exploration for future work. We also emphasize that, akin to estimating the inverse feasibility set, this new theoretical question does not require sampling constraints. 
 
**Comparison to "Offline IRL" (ICML 2024), and Lazzati et al.**

This setting contrasts with our assumption of a generative model.

**A new perspective**

Our optimization-based approach results in problem formulations directly amenable to modern large-scale stochastic optimization methods. Consequently, we anticipate that our techniques will benefit future algorithm designers and establish a foundation for more comprehensive research in this area.
Thank you for your prompt response and for providing us with the opportunity to further clarify our points. Below, we address the issues you raised.

>CONCERNS:
> Motivation: The novel optimization perspective looks great, but I would like to understand what kind of benefits it provides on top of prior results. Does it allow for sharper rates in {expert's query complexity, sample complexity} or polynomial rates for previously unaddressed settings? Does it open the door for more scalable algorithms? Something else?

Recent research in IRL with theoretical guarantees has seen significant advancements, as evidenced by works such as [48,49,50,51,52,53], Lazzati et al., "Offline Inverse RL" (ICML 2024), and Lazzati et al., "How to Scale RL to Large State Spaces? A Provably Efficient Approach" (2024). These studies have laid the groundwork for exploring the mathematical foundations of IRL, a complex and challenging topic. In the following, we will clarify the specific benefits our optimization-based perspective and formulation provide on top of prior results.

First, as discussed in our manuscript and demonstrated in Appendix A.2, our formulation—when applied to finite tabular Markov decision processes (MDPs) and a stationary Markov expert policy—simplifies to those considered in [48-53].


**Comparison to [48,49,50]** 

*Setting*: The formulation underlying the analysis and algorithms in [48, 49, 50] addresses scenarios where the expert policy is known and deterministic. In contrast, our formulation accommodates more general unknown, nonstationary, and randomized expert policies. Additionally, our approach assumes access to an offline, static dataset of expert demonstrations. While the works in [48, 49] focus on tabular MDPs, and [50] addresses MDPs with continuous state and discrete action spaces, we extend these contributions by providing a formulation and formal guarantees for IRL in continuous state and action spaces.

*Formal Guarantees*: Notably, similar to our Theorems 4.1 and 4.2, the sample complexity in the continuous-state setting, as provided in [50], scales exponentially with the dimension of the state space.

*Assumptions*: In the tabular MDP setting, our analysis holds without any additional assumptions on the MDP model. This is because we bypass the need for sampling constraints by solving a finite linear program using off-the-shelf solvers. In contrast, [48, 49] assume that the problem is $\beta$-separable and that every state is reachable with probability $\alpha$. For the MDP with a continuous state space in [50], the authors assume that the transition law density has an infinite matrix representation. Our Assumption 2.1 on the MDP is significantly milder, as it encompasses the majority of probability distributions (see lines 179-187) and includes the representation considered in [50] as a special case.
Dear Authors,

Thank you for considering the points raised in my review and for providing extensive replies. Let me first clarify that I made use of the "Weaknesses" box to summarize, in a few brief points, my evaluation of the paper. This is intended to help the AC in their decision and do not require rebuttal from the authors. Instead, I reported detailed comments in the "Questions" box covering points I would ask for clarifications.

On the latter, I am following up below to better express some of my concerns, which I do not currently consider resolved. Then, I pointedly reply to some of the authors' comments.

CONCERNS

1) Motivation

The novel optimization perspective looks great, but I would like to understand what kind of benefits it provides on top of prior results. Does it allow for sharper rates in {expert's query complexity, sample complexity} or polynomial rates for previously unaddressed settings? Does it open the door for more scalable algorithms? Something else?

2) Interpretation

Can the authors provide {expert's query complexity, sample complexity} rates in the form $O(S^x A^y (1 - \gamma)^{-k} \epsilon^{-z} ...)$ as it is common in tabular reinforcement learning literature? Can they provide analogous for the function approximation setting?

3) Solution concept

Are the authors saying something on the lines of "since the inverse problem is ill-posed, we chose to learn a single reward selected arbitrarily (through normalization constraints) in the feasible reward set"? If so, then my concern is that this would make the problem well-posed, but it risks defeating the purpose of solving the problem itself: We want to learn a reward to make some use of it. I have to admit this problem is not fully solved by prior works either, but this is why some recent works make a conservative choice of learning all of the feasible rewards in the absence of any more reasonable criteria.

REBUTTAL

> The authors in these works study solely how to deal with the unknown transition law and how to sample efficiently from the expert policy.

Isn't this what we care about in understanding the sample efficiency of inverse RL?

> Second, unlike recent theoretical IRL works [48-53] which avoid discussing this ill-posedness issue altogether

The papers [51-53] definitely discuss the ill-posedness

> Our paper tackles the inverse RL problem with minimal assumptions

Can the authors elaborate here? What does make their assumptions minimal? Ass. 2.1 appears to be rather strong: Does this include tabular MDPs? Would you provide references to support the claim that the assumption is standard?

> The sample complexity depends on MDP characteristics, such as state-action space dimension (exponentially)

Exponential sample complexity in state-action dimension is perceived as a negative result in reinforcement learning literature

Best regards,

Reply Author
Reviewer PJ8y