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 2024 poster (2024)
Keywords: Inverse reinforcement learning
statistical learning
Markov decision processes
Primary area: learning_theory
TL;DR: Randomized algorithms and PAC bounds for IRL in continuous spaces

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.

Randomized algorithms and PAC bounds for inverse reinforcement learning in continuous spaces
Angeliki Kamoutsi
Peter Schmitt-Förster
EPFL, Switzerland angeliki. kamoutsi@epfl.cc
University of Konstanz, Germany
Tobias Sutter
Volkan Cevher
John Lygeros ETH Zürich, Switzerland
University of Konstanz, Germany tob. sutter@uni konstanz.de
EPFL, Switzerland volkan. cewher@epfl.ch
jlygerosBethz.c ch
Abstract
This work studies discrete-time discounted Markov decision processes with contin- state and action spaces and addresses the inverse problem of inferring cost function from observed optimal behavior. We first consider the case in which we have access the entire expert policy and characterize the set of solutions the inverse problem by using occupation measures, linear duality, and complementary slackness conditions. To avoid trivial solutions and ill-posedness, natural linear normalization constraint. This results in an fiiiitt-dimensiona. linear feasibility problem, prompting a thorough analysis of its properties. Next, we use linear function approximators and adopt randomized approach, namely the sce- nario approach and related probabilistic feasibility guarantees, derive e-optimal solutions for the inverse problem. We further discuss the sample complexity for desired approximation accuracy. Finally, we deal with the more realistic case where we only have access to a finite set of expert demonstrations and generative model and provide bounds on the error made when working with samples.
introduce a
Introduction
In the standard reinforcement learning (RL) setting 22 on completing a desired task. However, oftentimes, it is either too challenging to optimize a given cost (e.g.. due to sparsity), or prohibitively hard to manually engineer cost function that induces complex and muulti-faceted optimal behaviors. At the same time. in many real-world scenarios, encoding preferences using expert demonstrations is easy and provides intuitive and human-centric interface for hehavioral specification [5] 6 7 Considering the inverse reinforcement (IRI.) problem involves deducing cost function from observed optimal behavior. IRL. actively researched with applications in engineering, operations research, and biology B 9 [O]. There are two main motivations behind inverse midisiionmmkinng 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 [2] or modeling of other cooperative or adversarial agents [33. 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 [15), parking lot navigation [16), and urban navigation [77] Other examples can be found in humanoid robotics and understanding of human locomotion [18] Despite extensive research efforts, understanding of IRL. still has significant limitations. One major gap lies in the absence algorithms designed for continuous state and action spaces, which are crucial for numerous promising applications like
cost signal given to instruct agents
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

autonomous vehicles and robotics that operate in continuous environments. Most existing of the-art IRL algorithms for the continuous setting often adopt a batccy- approach instead of directly solving the IRI. problem 19 20
27 However, this approach tends to provide a less robust representation of agent preferences 26 since the recovered policy is highly
23 24
25
26
dependent on the environment dynamics. State-of-the-an 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 con- tinuous 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 ciimizatioon-asel 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 opti- mization [29] 30 BT and uniform finite sample bounds from statistical learning theory [22)
To this aim, we first consider the case in which we have access to the entire optimal policy Tg and starting from the LP formulation of the MDP, characterize the set of solutions to the inverse problem by using occupation measures, linear duality and complementary slackness conditions. This results in an fiiiiitediimessiona linear feasibility problem. Although from 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 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 infinite- dimensionality 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 dimenisoadmn function space to a finite dimensional subspace (tightening), followed by the approximation of the infinitely-unen uncouutaal-u many constraints by a finite subset (relaxation). In particular, we use linear function approximators and adopt randomized approach. namely the scenario approach 29 33 and related probabilistic feasibility guarantees 30), to derive e-optimal solutions for the inverse problem, as well as explicit sample complexity bounds for a desired approxi- mation accuracy. Finally, we deal with the more realistic case where we only have access to 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 linear combina- of features. In particular, there are three
tion 34 35 15
36 37 or nonlinear function 38
broad categories of formulations. In feature expectation matching 35 15 17 one attempts to match
the feature expectation of 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- fosccfun.ion. Moreover, a probabilistic approach is to interpret the cost function as parametrization of a policy class such that the true cost function maxi- mizes the likelihood of observing the demonstrations [7 37 39 41 Most existing IRL methods that recover 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
45 26), that perform well in the experimental settings considered, without providing theoretical guarantees. Relying on oracle access to an RL solver is significant computational burden for applying these methods to MDPs with con- tinuous state and action spaces since solving a continuous MDP is a challenging and computationally expensive problem on its own. As 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.
25
Linear duality and complementarity were first proposed in 46 for solving 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 knowledge of the optimal behavior as a dintte-dimensionl vector, In our setting we have the additional
inverse
convex optimization programs where the agent has complete

---

difficulty of the -iniiieeadmnniinnalll and data-driven nature of the problem. In 48 the authors use occupation measures and complementarity in linear programming to formulate the inverse deter- ministic 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-square 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 in [8
Our work is closely related to the recent theoretical works on IRL 449
50 5
52
53
54
55, 56].
However, these papers consider either tabular MDPs 49 50 52 53
MDPs with continuous states and finite action spaces 56]. In contrast, our contribution delves into the theoretical analysis of TRL. 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 TE. simplifies to the inverse feasibility set considered in [52 53 (54) (see also Appx (A.)). The methodology put forth in those studies, extends the LP formulation previously explored in [12 49 50 [1], which primarily dealt with deterministic expert policies of the form गे d1 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 cost through a sample-based convex program. This flexibility surpasses previous theoretical IRL settings, where either TE is assumed to be fully known [49] 51 52 or active querying of mh is possible for each state 53 54
54
55
Finally, our assumption of Lipschitz MDP model is milder and more general than the infinite matrix representation considered in [51), thus accommodating 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 Unlike these recent works, our study goes beyond the examination of the properties of the inverse fcasibility set and its estimated variant. Our contribution extends to tackling the reward ambiguity problem, 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 unfinite-dimensionn LPs can be exploited to derive a single nearly optimal solution with probabilistic performance guarantees.
our work and recent theoretical IRL papers [52 53 54 55
Basic definitions and notations. Let (X, p) be Borel space, i.e., X is a Borel subset of complete and separable p-metric space, and let B(X) be its Borel o-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 62 E P(X) be the Dirac measure centered at I E X. Mcasurability is always understood in the sense of Borel mcasurabilityy An open ball in PX with radius r and center xo is denoted by (r
{ar E X p(2,,ro) < r)- Given measurable function : X + R. its sup-norm is given by ||u|| A supzex [u(x)). Moreover, we define the Lipschitz semi-norm by |u/r. sup Iu(e)= p(a.æ")
} and the Lipschitz norm by
||u|| A ||=/ + |u|1. Let Lip(X) be the Banach space of real-valued bounded Lipschitz continuous functions on X together with the Lipschitz norm 11.1|2. Then, (M(X), Lip(X)) forms dual pair of vector spaces with duality brackets (14, n) $ .xx u(z))d,, for all μ E (X), u E 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 Wasserstein norm ll-lww on M(X) is dual to the Lipschitz norm, i.e., ||w||/ _ sup $1 (u, u). If X, Y are Borel spaces, a stochastic kernel on X given Y is a function P(-I-) : B(X) x X + [o, 1] such that P(-lg) E P(X), for each fixed E Y, and -(B).) is measurable real-valued function on Y, for each fixed B E B(X)
2 Markov decision processes and linear programming formulation
Continuous Markov decision process. Consider a Markov decision process (MDP) given by tuple & AX P, 7, No, c). where X' is Borel space called the state space, Ais Borel space
3

---

called the action space, P is a stochastic kemel on X' given X' x A called the transition law, 2 E (0. 1) the discount factor, 1/6 E P(X)) the initial probability distribution, and e X' A + R is the cost function. The model Me. represents a controlled discrete-time stochastic system with initial state Jo ~ v.()). ) At time step I, if the system is in state 2; = x E X, and the action a; = a E A is taken, then corresponding cost c( a) is incurred, and the system moves to the next state 2++1 ~ P(-)ar, 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 π (-11z) E P(A)) denotes the probability distribution of the action ag taken at time L, while being in state I. We denote the space of stationary Markov policies by HIg Given policy x, denote by PT the induced probability
measure on the canonical sample space f2 _ (X' x A) i.e., P [ = Prob[- n, Ho ~ vo) the probability of an event when following starting from 2o vo. The expectation operator with respect to the trajectories generated by π when zo ~ Vo, is denoted by Eyy If 1/0 = on for some E X, then we will write for brevity PT and Eg.
The optimal control problem we are interested in is
Vi( min (M)))
(MDP.)
xello
where V (vo) - E Ei=o 2'e0r' at).. policy x² is called y-discounted Vy-optimal if V.¹ (Po) = Vor (Po), and the optimal value function V X + R is given by (z) 2 (62() We impose the following assumptions on the MDP model which hold throughout the article. These are the usual coninnity-compaatness conditions [39], 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(z, a) a fx ( (x, a). for all (z,0) E X A.
Assumption 2.1 (Lipschitz control model). (Al) X and A are compact subsets of Euclidean spaces;
(A2) the transition law P is weakly continuous, meaning that Pu is continuous on X x A, for every continuous function u X + R. Moreover, is Lipschitz. continuous, i.e., there exists a constant Lp > O such that for all (z, a), (y.b) E X x A and all E Lip((X), it holds that [Pu(æ, a) - Pu(y, b) s Lp) w/1 - yll2 + ||a i-a-66 b11);;
(A3) the cost function e is in Lip(X x A) with Lipschitz constant L. > 0. That is, for all (z, a), (y,b) X A. |e(x, a) cly, b)l S Lo(1I= vll2 ||a bll2):
Note that Assumption 2.1 (A2) is fulfilled when the transition law P has density function fly x, a) that is Lipschitz continuous in y uniformly in (xr, a) 160). This encompasses various probability distributions, such the uniform, Gaussian, exponential, Beta, Gamma, and Laplace distribu- tions, among others. Additionally, it applics to the infinite matrix representation considered in(51). Consequently, Assumption 2.1] accommodates broad range of MDP models and allows for the consideration smooth and continuous dynamics that reflect the characteristics of several real- world applications, such robotics, or autonomous driving. Importantly, Assumption 2. ensures that the value function V is in Lip(X') and is uniquely characterized by the Bellman optimality equation V. (x) minae (c(z, a) Jxx V. (ddy((y), for all x E X 60 Thm. 3.1] and [61]
Occupancy measures. by nT,, (E) & - " [Ix,,;)) E DT, E E B(XxxA). The occupancy measure can be interpreted as the discounted visitation frequency of the set L' 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, 3 & {u E M(X x A)+ Trp vol. where T. MMXX' x A) + M(X) is a linear and weakly continuous operator given by
For every policy т. we define the occupancy measure Hoe E M(X x A)+
Sr XXXA
(I+))(B 1 x A)
P(B|z, a)p( d(z, a)),
Note that P is uniquely determined by the transition law P. the initial state distribution Mo 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 me can be nonstationary and history-dependent.

---

C(n.)
("(me)
(Re)
Figure 1: Illustration of Theorem 3.1 for 61 > 82-
for all B E (()). Then, 3 =14 Io.e. Moreover, (1h, c) V. (vo), for every
The linear programming approach. direct consequence is that (MDP can be stated equiva- lently as an dimento-dimensionll LP over measures
Jc(Po)
inf nEM(XxA).
c), Tyj = To
(P.)
particular infimum P is attained and xt optimal for (MDP and only po is optimal for the primal LP (Pc). The dual LP of (P is given by
(v))
sup {(Vo, u) c- T- on X A), vELip(A)
(D&)
where the adjoint linear operator T Lip(X) + Lip(A' x A) of T, is given by
u(x) (T) u(() (T) - u(v)P(dylxx,)
Under Assumption 2.1, Т, is well-defined and the dual LP D is solvable, ie., the supremum is attained, and strong duality holds. That is, (o(P) T. (vo) function Va is optimal solution for the dual LP (D.) More details on the LP formulations for MDPs can be found in Appendix A.1
(v6)). In particular, the value
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 å (M, πg), where M & (X. P, Vo. Y) is an MDP without cost function and Te is observed expert policy. We say that E Lip(X' x A) is inverse feasible for B, if me a di-diccu byy vy-optimal policy for (MDP, with cost c. The set of all Lip(X' A) that inverse feasible is called the inverse feasibility set and is denoted by C(
Next, we use the primal-dual IP approach to MDPs and complementary slackness to characterize C(TE). To this end, we first define the e-inverse feasibility C (*EE).
Definition 3.2. Let 2 O. We say that cost cost function is e-inverse feasible for B (M, πε) and denote c E C (TTE if and only if. c E Lip(X x A) and there exists E Lip(X() such that
(NT c- Tīu C-TT
S E,
2 -,, X A.
We ready characterize the solutions IRL, following arguments from 46
47
48
Theorem 3.1 (Inverse feasibility set characterization). Let me E II. Under Assumption 2.1 on the Markov decision model M.. the following assertions are equivalent
1. c C* (TE);
2. NESo (FE);
5

---

3. Tg is y-diiscuut Vo- Py-optimal MDPP with cost finction c.
As consequence, ((TE) (TE) Neso C (TT)). Moreover, C(TE) is convex cone and I1-II2- closed in Lip(A' x A).
As result, cost function is inverse feasible for B - (M, MT) if and only if it is e-inverse feasible for all e > O. 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.I
Notably, when X' and A are finite, and the expert policy me is stationary Markov, our formulation aligns with the finite-dimensional inverse feasibility set introduced in [52 53 [4]. Furthermore, when the expert deterministic of the form TE (T = 01, 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 pamplebbase convex program This flexibility surpasses previous theoretical settings, where either is assumed to be fully known
and deterministic [49 51 52 or active querying of тe is possible for each state [53 [4].
Proposition 3.1 (e-inverse feasibility set characterization). Under Assumption 2.1 for any > 0, it holds that a cost function ē is in C (πR) if and only if mp. is s-opiiil for (MDPa) with cost ē.
As + O, the next proposition indicates a close approximation to the inverse problem solution. Proposition 3.2. Let (En)n n be a sequence such that limn-roe En = O and let on E C (TE). Then, every accumulation point of the sequence (cn) is inverse feasible, i.e., E C(TE).
Finally we show that the e-inverse feasibility set C (TT) satisfies the s-optimality criterion considered in 152 53 54]; see for example [53] Def. 2}.
Proposition 3.3. Let > 0. holds that inf V²* - (oo S 2- all E (TE)) where स is an optimal policy for the recovered cost č.
This condition ensures that when is small we avoid an unnecessarily large approximate feasibility set since there is possible true cost in C(TE) with small error for every possible recovered cost. function in C (TE).
4 Towards recovering a nearly optimal cost function
Although we characterized the inverse and e-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 infiniteddimensional 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 central challenge is to end up with a meaningful one. To avoid trivial solutions, in Section I. we motivate the addition of a linear normalization constraint.
(b) Another challenge appears because the LP formulation
anfinite-dimnssione hence com- putationally intractable. In Section 4.2 we address this problem by proposing tractable approximation method with probabilistic performance bounds.
(c) In practice, complete knowledge of me and P is often unavailable. In Section 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 me and P and provide error bounds to quantify our approach's is accuracy with sample data.
The main building blocks of our methodology are depicted in Figure 2
The second condition in [53 Def. trivially satisfied with error since C(TE) C C (*TE)))

---

Occepancy Incabuees
Nommlizztion coustrunt
liverse problmm
Infiite dimensional frashility L.
Regnlanzed sem- infinie peogrim
Projection reiduaas
duality
Projection
Canstniit sampllngg
Expent
Fanioosample atalysis
Dataedrioss cranterpust
Seutario cumoss program
Scesurio bound
Grazalive
Figure
Main building blocks our methodology
4.1 Normalization constraint
well-known limitation of IRL is that 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, for any u E Lip(X') and e E C(TE), the cost c + T u is inverse feasible. This phenomenon, also known as reward shaping [63] refers the modification or design of a reward function provide additional guidance or incentives to an agent during learning. In addition, since C(TT) is convex cone and closed for the sup-norm (Theorem 3.1 the of solutions IRL is closed to convex combinations and uniform limits.
is apparent from the characterization of ((Te) C² in Theorem 3.1
All these examples illustrate that the inverse feasibility set C(TE) contains some solutions that arise from mathematical artifacts. To mitigate this difficulty and avoid trivial solutions, inspired by [48), enforce the additional natural normalization constraint fxxA(c (x, a) d(z,,) The following proposition justifies this choice.
Proposition 4.1. If Deeiniitoo 3.2 ofC())) ( includes the normalization constraint fxxA(c- u)ddd = 1, then all constant cost 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.
is worth mentioning that the normalization constraint in our formulation primarily aims to mitigate the ill- pol-posedsess, ambiguity issue, intrinsic to the IRL problem, rather than resolve issues of identifiability. In particular, we state and prove that the normalization constraint rules out wide class of trivial solutions, i.e., all constant functions and inverse solutions of the form c T an outcome devoid of physical meaning and a mathematical artifact. While the identifiability problem and the ill poseddesssss 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 multiple expert policies environments for comparison (64 65). On the other hand, ill- poledesesssss is broader concept from mathematical and statistical problems and refers to situations where problem does not satisfy 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 thcoretical results this direction, hoping lay the foundations for overcoming current limitations.
4.2
The case of known dynamics and expert policy
We first consider the case where the expert policy Tg, the induced occupation measure f 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 first step, we introduce semi-infinite convex formulation that enforces the normalization constraint, involves restriction of decision variables from an nnfinie-dimensionall function space finite-dimensional subspace, and considers an additional norm constraint that effectively acts as a regularizer. The resulting

---

regularized cemi-infinite inner approximation, which we call inverse program is given by
inf 3.,
8
S.L.
{ (uy TT Se
c a) - TTu(I,a) 2 -,, (z, ( EX fxxA (c T ux, a) ((r 1,
(IP)
c CE n.. u E U.., E 2 0,
where Cn. A {Σ}= agG : a a= fa E R== ||a||| < 0 with {ar C Lip( x A) being
linearly independent basis functions with Lipschitz constant L. > 0. U,... - +Ein B,u; B {3:) E RR= || < 0}. with {ur |= C Lip(X*)) being linearly independent basis functions with Lipschitz constant L,, > O, and 0 > 0 is an appropriately chosen regularization parameter.
Note that (IP) is derived by relaxing the constraints in the inverse feasibility set C(TT) and paying penalty when violated. In particular, let (ě, 3) be optimal solution of the semi-infinite program (P). Then, ē _ Di=1 OeG (mE), from where becomes apparent that the smaller the value of é, the better the quality of the extracted cost function č (as by Proposition (.T). One would intuitively expect that é depends on the choice of basis functions for the cost (resp. value) function as well as on the parameters ne (resp. ney)) and 0. This dependency is highlighted by the following proposition.
Proposition 4.2 (Basis function dependency). Let Te be an optimal policy for the optimal control problem MDP.. . with cost c* and let u² be the corresponding optimal value function. Under if u1 1 and 0 mi(1)mi then E I Eapprox with
Assumption 2.1
2 7
Lp, LI,, 7 + Dy + 7) max
dl)
( min ||c* - cill + minn I|u wlle): (2) (cEC..
Capprox ==
ucUn.
where d leb(X A) is the Lebesgue measure of X A, Dy,0 (I->)" min (1d]oty--- with l|calloo and Ku,co - maxx==..... ||
20(Ks. Ka
constants K2 - max;=
Proposition 4.2 sheds light on how the choice of basis functions and the regularization parameter 0 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(A' x A) and Li'( as n. and nu and the regularization parameter tend
then the projection residuals and so ē tend to infinity. In particular note that when e* E C.., and u² E Un,, then the corresponding projection residuals are 0, and thus 0 as expected. In a practical setting, observing a large value of E an indicator that more basis functions are needed.
Finally, note that the regularizer helps bound the dual optimizer using dual norm, thus offering an explicit approximation eтror for the proposed solution (see Appendix B.6).
Computationally tractable approximations to the semi-infinite convex program be obtained through the scenario approach [29 66) in which randomization over the set of constraints is con- sidered. In particular,
treat the parameter (Ir, a) as uncertainty parameter living in the space X' x A. Let IP be Borel probability measure on (X' x A, B(x' x A)), where X' x A is equipped with the norm [zz a)ll = |x||| + ||||22 We assume that P has the following structure.
Assumption 4.1 (Sampling distribution). There exists R4 - [o, 1] strictly increasing, such that P(B,(z, a))= > f(r). all (I, a) X x Aandd r >> 0.
Assumption 4. is sufficient structural assumption concerning the sample distribution P ensuring that the gap between the robust program (IP) and its sampled counterpart (SIP can be controlled. implicitly restricts the state and action spaces to be bounded.
Let ((x(()) a 1 be independent and identically distributed (i.i.d)) samples drawn from X' x A according to P. We are interested in the following random finite-dimensional convex program:
infa,0.s
E
S.l.
(umse c T, Se, clx(1), (0(()) -T (f) (0) 2 -e, 41= = 1....N, ., Ixxa (c(x, a) - T u(x a)) d(z, a)= = 1,
(SIPN)
e E Cn.. u E U Un, 2 0.
8

---

Notice that (SIP naturally represents randomized program as it depends on the random multi-
sample {(xl))
a )
-= We assume the following measurability assumption holds for our analysis.
Assumption 4.2. The (SIP optimizer generates a Borel measurable mapping that associates each to uniquely defined optimizer (ãx, Bex,,N.55 .NN, Ex)
multi-sample {xx10,
To ensure uniqueness when multiple solutions exist, use lie-break rule, such as selecting the solution with the minimum Il-1l2 norm. has been shown 30 Proposition 3. 10] that applying such a tie- de-brrak--uule also ensures the measurability in Assumption 4.2
The appealing feature (SIP is that a convex tiite-aimensional 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 (ăx, 3.,, EN) and the extracted cost function eN = Di= āN,0z. For each n E N, e E (0, 1) and 8 E (0, 1), we define
N(n, min NN E
N: Σ i=U
( -c) c)N- =o..
The sample size above asymptotically scales theorem determines the sample complexity of (SIPN) In particular, for a given reliability parameter
{1/e, log(1/0), n). see 129] The following
e E (0, 1) and confidence level 5 E (0, 1), we establish how many samples are needed to guarantee with confidence at least 1 - 5 that čy E C C to (TE).
Theorem 4.1 (Scenario program guarantees). Let Ō E (0, 1). Under Assumptions 2.1 4.1 and 4.2 if u1 = and 0 > [1-7]1e((Xxx) then by sampling N 2 N(ne + nu + 1, 1, LA
J.0) constraints, where LA a 0 V 0 ( Iu]), with probability least 1 - 6, ēx E Co t (TE)-
Remark 4.1 (Curse of dimensionality). As shown in [30,, the funetion g(r) is of order dim((Xx
As result, the number of samples grows exponentially e dim' A similar exponential dependence to the dimension of the state space has been established in [5T]. 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 is challenging. Therefore, understanding the selection of suitable distribution for future sample drawing is crucial.
Remark 4.2 (12 (g-regularization). To cut down on required samples N, a common method is using 1 -eegglaarization reduce the effective dimension of the optimization variable. This concept formalized in the current setting (67]. Moreover, in the spirit of the compressed sensing literature 68.. 1 Irreguularization will promote sparse solutions and hence lead to "simple" cost functions. In the context of optimal control 4 l-regullarization term is studied as the so-called "maximum hands-off control" paradigm [69 (70.. In our case, the utilization of the I norm offers two primary advantages. Firstly, the nnorm promotes sparsity in solutions, thereby potentially reducing computational demands. Secondly, this specific type of regularization preserves the linearity of the program.
4.3 Sample-based inverse reinforcement learning
In this section, we explore the realistic scenario where we lack access the expert policy me 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- modell oracle. It provides the next state x' given state-action pair (ar, a) sampled from P(. a). This known as the simulator-definet MDP
72
Sampling process. Let = {T; = (xπ, ah...., Iy. a'y) } be i.i.d., truncated sample trajecto- ries according to mg. For any Lip(X' x A), we consider the sample average approximation of the expectation (M <) given by. (no5, c) (T) A 1 2t 7"c(/" are i..dd, samples according Vo, for any E LipF(X), we define the corresponding sample average estimation of the expectation (Mo, u) by (Vo, u) (E) 1 E u(xt). Moreover, let Ç ((<(),(()) ))N be i.i.d. samples drawn from X x A according to P P(K x A). We also use the following notation T,) ())) A w(z(0) - & E u(vi"),
Similarly, if g {=
{u (1) iid. )))))
h=

---

We are interested in the finite-sample analysis of the following random convex program:
S.L.
(prp c) (T) (Vo, u) (E) E, c(x(1) ) T (z(") aa"), y()) _ -E, 11= 1I.1,....
(,
(nu); 3 (ncl c E C 2 E U nu 0,
where the function classes Cn Un, are defined as in the previous Section. We make the following measurability assumption which is analogous to Assumption 4.2 Assumption 4.3. The (SIPN, optimizer generates a Borel measurable mapping that associates each multi-sample (y, &. () to uniquely defined optimizer m,, NN,,,, N.m.n.k)). Theorem 4.2. Under Assumptions
2.1 4. and 4.3 if u1 = a O
(1 (-x))xee(xXXx]] then for 8K n' in (
N 2 N(n. + + 1,9 f. 6/2) constraints, T S Hn (Ba )
(1-9722
expert samples with horizon - log(?), and 8Cn, 0" log(4n, N/21 calls to the generative model per constraint, with probability at least 1 6, m..kk E (S and o0 are given as Ke A mmx;=1....... l|cilloo and u0,00 A max ||ualloo
The constants Ke
Theorem 4.2 provides explicit sample complexity bounds for achieving desired approximation accu- racy with our proposed randomized algorithm. For continous MDPs when we use n. basis functions
log( 4F)
for the value function and n. basis functions for the cost function we need m = O (1-))2
calls to the generative model per constraint and expert samples and K O ing! DacN
N = (exxpdimmX AA) sampled constraints and solve the resulted sampled finite LP with nu + ne variables and N constraints in polynomial time to learn a cost that is + Eapprox -iverre feasible with probability 6.
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.
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 understanding regarding the selection of a suitable distribution for drawing samples in the future. Intuitively, is reasonable 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 more scalable bound (74). However, a comprehensive mathematical treatment of these inquiries will be addressed in future research endeavors.
Redunction to tabular MDPs. For tabular MDPs, offline access expert for tabular MDPs, and a generative model we require m O ||llo (X
expert samples, and K XX|| =
calls to the generative model, and solve the resulted sampled finite LP with X| log( [
|XA] + X variables and | + 2 constraints in polynomial time, to learn a cost function that is e-inverse feasible with probability 1 5.
Note that as we argued in detail above our setting is different from the one in [52-54] since we have offline access to the expert and address 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 simple truncated Linear Quadratic Regulator (LQRR) example to provide better intuition about the method and the proposed sample complexity bounds.
10

---

Acknowledgments
This work was supported by the DFG in the Cluster of Excellence EXC 2117
"Centre for the Advanced Study of Collective Behaviour" (Project-ID 390829875).
References
[1] D. P. Bertsekas. Dynamic programming and suboptimal control: survey from ADP to MPC. European Journal of Control, 11(4)311-334, 2005. (Cited on page
[2] Richard Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press,
second edition, 2018. (Cited pagel] 1
[3] Dimitri Bertsekas, Rollout, policy iteration, and distributed reinforcement learning. Athena Scientific, 2021. (Cited on page 1
[4] Sean Meyn. Control Systems and Reinforcement Learning. Cambridge University Press, 2022. (Cited on page
[5] D. A. Pomerleau. Efficient training artificial neural networks for autonomous navigation. Neural Computation, 3(1):88-9) 97, 1991. (Cited on page
[6] Stwart Russell. Learning agents for uncertain environments (extended abstract). In Annual Conference on Computational Learning Theory (COLT), 1998. (Cited on page[]
[7] Andrew Bagnell, An invitation to imitation. Technical Report CMU-RI-TR-15-08, Carnegie Mellon University, Pittsburgh. PA, 2015. (Cited on page I
[8] W. Bradley Knox, Alessandro Allievi, Holger Banzhaf, Felix Schmitt, and Peter Stone. Reward (mis)design for autonomous driving. arXiv:2104. 13906, 2021. (Cited page
[9] T Osa, J Pajarinen, G Neumann, JA Bagnell, P Abbeel, and J Peters. An algorithmic perspective on imitation learning. Foundations and Trends Robotics, 2018. (Cited on page
[10] Arthur Charpentier, Romuald Elie, and Carl Remlinger. Reinforcement learning economics
and finance. arXiv:2003 2020. (Cited page 1
[11] Brian D. Ziebart, Andrew L. Maas, J. Andrew Bagnell, and Anind K. Dey. Human behavior modeling with maximum entropy inverse optimal control. In AAAI Spring Symposium: Human Behavior Modeling, 2009, (Cited on page
[12] A. Y. Ng and S. J. Russell. Algorithms for inverse reinforcement learning. In International Conference Machine Learning (ICMI.), 2000. (Cited pages and 17
[13] Darse Billings, Denis Papp. Jonathan Schaeffer, and Duane Szafron. Opponent modeling in poker. In AAAIAAAI,, 1998. (Cited on page I)
[14] Abbeel and A. Ng. Apprenticeship learning via inverse reinforcement learning. In International Conference on Machine Learning (ICML), 2004. (Cited page[]
[15] Umar Syed and Robert E. Schapire. A game- theortic approach to apprenticeship learning. In Proceedings of the 20th International Conference on Neural Information Processing Systems, NIPS 07, pages 1449-1456, USA, 2007. Curran Associates Inc. (Cited on pages andd
[16] Abbeel, D. Dolgov, A. Y. Ng, and S. Thrun. Apprenticeship learning for motion planning with application to parking lot navigation. In 2008 IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 1083-1090, Sept 2008. (Cited on pagel
[17] Brian D. Ziebart, Andrew Maas, J. Andrew Bagnell, and Anind K. Dey. Maximum entropy inverse reinforcement learning. In Proc. AAAI, pages 1433- 1438, 2008 (Cited pages a
[18] J.P. Laumond, N. Mansard, and J.B. Lasserre. Geometric and Numerical Foundations of Movements. Springer Tracts Advanced Robotics. Springer International Publishing, 2017. (Cited on page I
11

---

[19] S. Levine, Z. Popović, and V. Koltun. Feature construction for inverse reinforcement learning.
In Advances in Neural Information Processing Systems (NeurIPS), 2010. (Cited on page
[20] J. Ho, J. K. Gupta, and S. Ermon. Model-free imitation learning with policy optimization. In International Conference on Machine Learning (ICML), 2016. (Cited page
[21] J. Ho and S. Ermon. Generative adversarial imitation learning. In Advances in Neural Informa- tion Processing Systems (NeurIPS), 2016. (Cited on page 2
[22] Justin Fu, Katie Luo, and Sergey Levine. Learning robust rewards with adverserial inverse reinforcement learning. In International Conference on Learning Representations (ICLR), 2018. (Cited on page
[23] Liyiming Ke, Sanjiban Choudhury, Matt Barnss, Wen Sun, Gilwoo Lee, and Siddhartha Srini- vasa. Imitation learning as f-divergence minimization. In International Workshop on the Algorithmic Foundations of Robotics (WAFR), 2020. (Cited page
[24] Ilya Kostrikov, Ofir Nachum, and Jonathan Tompson. Imitation learning via off-policy distribu- tion matching. In International Conference on Learning Representations (ICLR), 2020. (Cited
on page
[25] Paul Barde, Julien Roy, Wonseok Jeon, J. Pineau, C. Pal, and D. Nowrouzezahrai. Adversarial soft advantage fitting: Imitation learning without policy optimization. In Advances in Neural
Information Processing Systems (NeurIPS), 2020. (Cited on page 2
[26] Divyansh Garg, Shuvam Chakraborty, Chris Cundy, Jiaming Song, and Stefano Ermon. IQ- learn: Inverse soft-Q learning for imitation. In Advances in Neural Information Processing
Systems (NeuRIPS), 2021. (Cited page 2
[27] Luca Viano, Angeliki Kamoutsi, Gergely Neu, Igor Krawezuk, and Volkan Cevher. Proxi- mal point imitation learning. In Proceedings of the Neural Information Processing Systems (NeurIPS), 2022. (Cited on page 2
[28] O. Hernández-Lerma and J. B. Lasserre. Discrete-Time Markov Control Processes: Basic Optimality Criteria. Springer-Verlag New York, 1996. (Cited on pages P and 16
[29] M. Campi and Garatti. The exact feasibility of randomized solutions of uncertain convex programs. SIAM Journal on Optimization, 19(3):211-12200 2008. (Cited on pages 2 g 9
and
[30] Mohajerin Esfahani, T. Sutter, and Lygeros. Performance bounds for the scenario approach and an extension to a class of non-convex programs. IEEE Transactions on Automatic Control, 2014. (Cited on pages 2 9
23 and 24
[31] Mohajerin Esfahani, T. Sutter, D. Kuhn, and J. Lygeros. From infinite finite programs: Explicit error bounds with applications to approximate dynamic programming. SIAM Journal on Optimization, 1988 2018 (Cited on pages 21
and
26
[32] Olivier Bousquet, Stéphane Boucheron, and Gábor Lugosi. Introduction Statistical Learning Theory, pages 169-207. Springer Berlin Heidelherg, Berlin, Heidelberg, 2004. (Cited on page
[33] Giuseppe Calafiore and Marco C. Campi. Uncertain convex programs: Randomized solutions and confidence levels. Mathematical Programming. 102:25-400 2005. (Cited on page 2
[34] Andrew Y. Ng and Stuart Russell. Algorithms for inverse reinforcement learning. In in Proc. 17th International Conf. on Machine Learning, pages 663-670. Morgan Kaufmann, 2000. (Cited on page 2
[35] Pieter Abbeel and Andrew Y. Ng. Apprenticeship learning via inverse reinforcement learning. In Proceedings of the Twenty-firs International Conference on Machine Learning, ICML '04, pages 1-, New York, NY, USA, 2004. ACM. (Cited page 2)
[36] Nathan D. Ratliff, J. Andrew Bagnell, and Martin A. Zinkevich. Maximum margin planning. In Proceedings of the 23rd International Conference on Machine Learning, ICMI. '06, pages 729-736, New York, NY, USA, 2006, ACM. (Cited on page 2
12

---

[37] Gergely Neu and Csaba Szepesvári. Apprenticeship learning using inverse reinforcement learning and gradient methods. In UAI, 2007. (Cited on page
[38] Sergey Levine, Zoran Popovic, and Vladlen Koltun. Feature construction for inverse reinforce- ment learning. In J. D. Lafferty, C. K. Williams, J. Shawe-Taylor S. Zemel, and Culotta, editors, Advances in Neural Information Processing Systems 23, pages 1342-1350. Curran Associates, Inc., 2010. (Cited on page
[39] Sergey Levine, Zoran Popovic, and Vladlen Koltun. Nonlinear inverse reinforcement learning with gaussian processes. In J. Shawe-Taylor R. S. Zemel, P. Bartlett, F. Pereira, and Q Weinberger, editors, Advances in Neural Information Processing Systems 24, pages 19-27.
Curran Associates, Inc., 2011. (Cited on page?)
[40] Nathan Ratliff, David Bradley, J. Andrew (Drew) Bagnell, and Joel Chestnutr. Boosting structured prediction for imitation learning. In B. Sch" olkopf. J.C. Platt, and T. Hofmann", editors, Advances in Neural Information Processing Systems 19, Cambridge, MA, January 2007.
MIT Press. (Cited on pagel
[41] Deepak Ramachandran and Eyal Amir. Bayesian inverse reinforcement learning. In Proceedings of the 20th International Joint Conference on Artifical Intelligence, IJCAI'07, pages 2586-2591, San Francisco, CA, USA, 2007. Morgan Kaufmann Publishers Inc. (Cited on page 2
[42] Krishnamurthy Dvijotham and Emanuel Todorov. Inverse optimal control with linearly-solvable mdps. In ICML, pages 335-342. Omnipress, 2010. (Cited page D
[43] Sergey Levine and Vladlen Koltun. Continuous inverse optimal control with locally optimal examples. In Proceedings of the 29th International Conference Machine Learning, pages 41-48, 2012. (Cited on page
[44] Chelsea Finn, Sergey Levine, and Pieter Abbeel. Guided cost learning: Deep inverse optimal control via policy optimization. In International Conference on International Conference on Machine Learning (ICML), 2016. (Cited on page 2
[45] Siddharth Reddy, Anca D. Dragan, and Sergey Levine. (SQIL): Imitation learning via reinforce- ment learning with sparse rewards, In International Conference Learning Representations (ICLR), 2020. (Cited on page 2
[46] Ravindra K. Ahuja and James B. Orlin. Inverse optimization. Operations Research, 491 783, 2001. (Cited on pages] and
[47] Garud Iyengar and Wanmo Kang. Inverse conic programming with applications. Operations Research Letters, 33(3)3119 - 330, 2005. (Cited on pages and
[48] Edouard Pauwels, Didier Henrion, and Jean- Baan-Bernard Lasserre. Linear conic optimization for inverse optimal control. SIAM Journal on Control and Optimization, 54(3): (033):1798-198 1825, 2016. (Cited on pages
and 20
[49] A. Komanduru and Honorio. On the correctness and sample complexity inverse reinforee- ment learning. In Advances in Neural Information Processing Systems (NeurIPS), 2019. (Cited on pages and
[50] Abi Komanduru and Jean Honorio. A lower bound for the sample complexity of inverse reinforcement learning. In International Conference on Muchine Learning (ICML), 2021.
(Cited on pages and 17
[51] Gregory Dexter, Kevin Bello, and Jean Honorio. Inverse reinforcement learning in a continuous state space with formal guarantees. In Advances in Neural Information Processing Systems (NeurIPS), 2021. (Cited on pages
and 17
[52] Alberto Maria Metelli, Giorgia Ramponi, Alessandro Concetti, and Marcello Restelli. Provably efficient learning of transferable rewards. In International Conference on Machine Learning (ICML), 2021. (Cited on pages
and
13

---

[53] David Lindner, Andreas Krause, and Giorgia Ramponi. Active exploration for inverse reinforce- ment learning. In Advances Neural Information Processing Systems (NeurIPS), 2022. (Cited
pages
3
and 17
[54] Alberto Maria Metelli, Filippo Lazzati, and Marcello Restelli. Towards theoretical understanding of inverse reinforcement learning. arXiv:2304. 12966, 2023. (Cited on pages 3 6
and 17
[55] Filippo Lazzati, Mirco Mutti, and Alberto Maria Metelli. Offline inverse RL: New solution concepts and provably efficient algorithms. In Internationall Conference on Machine Learning (ICML), 2024. (Cited page B
[56] Filippo Lazzati, Mirco Mutti, and Alberto Maria Metelli. How does inverse RL scale to large state spaces? A provably efficient approach, 2024. (Cited page 3)
[57] D. P. Bertsekas and S. E. Shreve. Stochastic Optimal Control: The Discrete-Time Case. Academic Press, 1978. (Cited on page 4
[58] M. L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, Inc., USA, 1st edition, 1994. (Cited on pages and 17
[59] Onésimo Hernández-Lerma and Jean Bernard Lasserre. Discrete-time Markov control processes. Springer-Vertee Verlag, New York, 1996. (Cited on page
[60] F. Dufour and T. Trieto-Rumeate Finite linear programming approximations of constrained discounted markov decision processes. SIAM Journal on Optimization, (1()):1298 13244, 2013. (Cited on pages 4 and 16
[61] O. Hermandez-Lerma Adaptive Markov Control Processes. Veringer-Verlag, Berlin, Heidelherg, 2001. (Cited on pages 4 and 16
[62] O. Hernández-Lerma and J.B. Lasserre. Discrete- Time Markov Control Processes: Basic Optimality Criteria. Applications of Mathematics Series. Springer, 1996. (Cited on pages 16 and
[63] Andrew Y Ng, Daishi Harada, and Stuart J Russell. Potential- shaping and linearly- solvable markov decision problems. Jourmal of Artificial Intelligence Research, 11:131-167, 1999. (Cited on page
[64] Haoyang Cao, Samuel Cohen, and Lukasz Szpruch. Identifiability in inverse reinforcement learning. In Advances in Neural Information Processing Systems (NeurIPS), 2021. (Cited on page
[65] Paul Rolland, Luca Viano, Norman Schürhoff, Boris Nikolov, and Volkan Cevher. Identifiability and generalizability from multiple experts in inverse reinforcement learning. In Advances in Neural Information Processing Systems (NeurIPS), 2022. (Cited page
[66] Marco C. Campi, Simone Garatti, and Maria Prandini. The scenario approach for systems and control design. Annual Reviews in Control, 33(2): 149 - 157, 2009. (Cited on page 8)
[67] M. Campi and A. Carè. Random convex programs with $1 1S-regularization: Sparsity and generalization. SIAM Journal on Control and Optimization, 51(5):3532-3557, 2013. (Cited on page
[68] David L.. Donoho. Compressed sensing. IEEE Trans. Inform. Theory, 52:1289-1306, 2006. (Cited on page
[69] Masaaki Nagahara, Daniel E. Quevedo, and Dragan Nešić. Maximum hands-off control: A paradigm of control effort minimization. IEEE Transactions on Automatic Control, 61(3):735-
747, 2016. (Cited on page
[70] Debasish Chatterjee, Masaaki Nagahara, Daniel E. Quevedo, and K.S. Mallikarjuna Rao. Characterization of maximum hands-off control. Systems & Control Letters, 94:31-36, 2016.
(Cited on page )
14

---

[71] B. Szörényi, G. Kedenburg, and R. Munos. Optimistic planning in Markov decision processes using a generative model. In Advances in Neural Information Processing Systems (NeurIPS). 2014.
(Cited on page 9
[72] M. A. Taleghan, T. G. Dietterich, M. Crowley, K. Hall, and J. Albers. PAC optimal MDP planning with application to invasive species management. Journal of Machine Learning Research,
2015. (Cited page
[73] laojing Zhang, Sergio Grammatico, Georg Schildbach, Paul Goulart, and John Lygeros. On the sample size of random convex programs with structured dependence on the uncertainty. Automatica, 60: 10:1065-1056, 2015. (Cited page 10
[74] Daniela
De Farias and Benjamin Van Roy. On constraint sampling in the linear program- ming approach to approximate dynamic programming. Mathematics of Operations Research, 29(3):462 478, 2004. (Cited on page I0]
[75] M. Sion. On general minimax theorems. Pacific Journal of Mathematics, 8(1):171-176, 1958. (Cited page
[76] T. Sutter, A. Kamoutsi, P. E. Esfahani, and J. Lygeros. Data-driven approximate dynamic programmingg A linear programming approach. In IEEE Conference on Decision and Control (CDC), 2017. (Cited on page 25
[77] Dimitri P. Bertsekas. Dynamic Programming and Optimal Control, Vol. II. Athena Scientific, 4th edition, 2012. (Cited on page 26
[78] Marco C. Campi, Simone Garatti, and Maria Prandini. The scenario approach for systems and control design. IFAC Proceedings Volumes, 41(2):381-38,, 2008. 17th IFAC World Congress.
(Cited on page 27
15

---

A Supplementary material
A.1 The linear programming approach for continuous MDPs
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], [6]]. Under Assumption 2.1 the following hold:
1. The value function V. is in Lip(X)) with Lipschitz constant Lvz S Le 12y IcllooLpp
2. The value function V satisfies the Bellman optimality equation
Vi (z) min (c(,,,)))))))))))))))))) + 7 / (d) for all x E X;;
aEA
3. There exists a 7-discount Un-optimal policy which is stationary deterministic.
Next, we characterize the set of occupation measures in terms of linear constraint satisfaction.
Theorem A.2 (162, Theorem 6.3.7I). Consider the convex set of measures, 3 - {u E MMX x A)+ T. }o where T.: M(X x A) M(X) is linear and weakly continuous operator given by
/
(B) - M x A)
()) for all B E B(X).
XXA
Then, 5 (47 ll Moreover, (KT, V (V)). every
A direct consequence of Theorem A.2 is that
(v)) = min (1 c)
min
(1%,
inf (p,c). PEB
rETTo
Therefore the MDP problem MDP- can be stated equivalently an measures
LP over
Je(v))
inf ((pc)) T.μ v.
(Pa)
HEM(XxA)
In particular the infimum in (P is attained and x² is optimal for the OCP MDPc if and only if pi optimal for the primal LP P
Consider the dual pair of vector spaces (M(X' x A), Lip(A' x A)) and (M(A), Lip(X)). Then the adjoint linear operator T Lip(X)) + Lip(X' x A) of Tf is given by
uZ, e u(x) /
P(dgl()))
Indeed, т is well-defined by Assumption (A2) Moreover, direct computation shows that (see 28 Pg. 139])
(u, T,) (TaM, u), for all MM x A), E Lip(X).
In addition, the dual convex cone of M(X A) is the Lip(A' A)+ of nonnegative bounded and Lipschitz continuous functions on X' x A. This is because,
M(X x A)+
- {u E Lip(X' X x A) (n, 20, V ME MMX x A)+1
{UE Lip A) v v 0).
The dual LP of P is given by
T (vo)
sup wELip(X))
((v0 : 2
(D.)
16

---

Theorem A.3 (Strong duality). Under Assumption 2.1 on the control model M. the dual LP solvable, i.e., the supremum is attained, and strong duality holds. That is, Iel Jo(vo) Je (v)) V: (Vo). In particular the value function V is optimal solution for the dual L. De
De
Proof. By virtue of 62 Theorem 6.3.8] we have that
V (vo) = Je(vo) = (vo)
and moreover the supremum definiting Te (up) is attained by the optimal value function V X ++ R. Therefore, the result follows by 1) of Theorem A.
A.2 Comparison to the LP formulations for IRL from the literature
In this section, we will demonstrate that our formulation, when applied to finite tabular MDPs and a stationary Markov expert policy TE, 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 50 51]. which specifically addressed deterministic expert policies of the form establish 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.
(B(S) 01. By highlighting this connection,
Let X and A be finite sets with cardinality |-8] and [A], respectively. Then, Assumption 2.1 is trivially satisfied and Lip(X' x A) = R|
By Theorem 3.1 we have that a cost function c E R X is inverse feasible with respect to Te, i.c. E C(TE), if and only if there exists R such that
{
Ene (T, =0, (c TT O, for all (
TE E Ho is stationary Markov policy, then 1T 105 a') > 0 [58] Thm. 6.9.1]. Therefore, for any state-action pair (x, a) X x A, it
Ee 1wo (I, a (()mg(alz) and
holds that pig (z, a. = 0 + <(axx) = O. We then get that 3 is equivalent to
{
(c (c-TT,) (z)) = 0, if Te(a 0
(4)
(c TC-TT,) T, (2,) a) 20, if (T(a))) 0.
So end up that a cost function R! is inverse feasible if and only if there exists u E R| and Ay E R | such that for all (z, E A.A.
c(ε,a) u(x) + Σ P(ylz,a)u(y) Ay (m((al)===)))
So we have recovered [52] Lem. 3.2], which forms the basis for the analysis and algorithms in 52
53
Next, note that when (I: 01, for all X' and c(x, a) c(x)) for all (x, E X A, then equivalent to
c(x) u(x) E Ply x a))u()), for all x E X
(5)
c(xx) u(x) 2 -7 -72, Ply x a)u(y), for all x E X, a a
Therefore, cost function e RI is inverse feasible if and only if there exists E R such that
{ c(x)-u(x)= (0)-((x) ( E, P(ylx, a )u(y). for all X a1 P(yl,, u(())) S E, P(y|z, a)u(y), for all E X, a AMaa..
(6)
By introducing the notation Pa E R x with Pa(x, = P(y a1) and noting that the first c. linear system in (6) admits unique solution u = (1ą ?Pa.) -c. we end up that a cost function
c E *
is inverse feasible if and only if
(Pa, - (l)() - -P,,)) < 0, for all E AMa.1.
So we have recovered 12 Thm. 3] which forms the basis for the analysis and algorithms in 50
12 49
17

---

B Proofs
B.1 Proof of Theorem 3.1
Proof. The direction 3) + 1) is consequence of the strong duality Theorem A.3 and complementary slackness. Indeed, assume that we is optimal for (MDPe) with cost c. Then, by Theorem A.2 12 is optimal to (Pe) By Theorem A.3] the dual (De) is solvable and there is no duality gap. Therefore, there exists a u E Lip(X)) such that
0, X x A (feasibility).
TE c)
(vo. u)
(strong duality).
The second equality is equivalent to (peg, c Tuu) = O, since Typ = vo. This proves the desired implication.
The implication 1) + 2) is straightforward.
To show 2) 3). let E Nexo C (T(TE). Then, for each n N. there exists un E Lip(X)) such that (MEg c- T un) S and uh 2 n on x A. Set On un -(1-7)" Then, (u C Lip(A() and
lim (prg. c - vn) n
= 0,
(7)
c c T-T7,0 T7 2 0, on x A.
(8)
where used that (M76 feasible for the dual Moreover, 1400 is feasible for PPop. Therefore,
and T = -1-% on X' x A. Equation (8 states that {Un J
(vn, un) S (vn) = Jo(o)) S (150:00
By 7
lim (No, ux) lim (TrHin, = lim (uoo Tiva) = (mng (uggc). So, by
taking the limits in (9) as + 20, we conclude that fob is optimal for ( Then, by Theorem A.2
Te optimal (MDP.) with cost
Hence, we have shown that C(TT) = -eso (TE)) = ca (mE)) One can check easily that C(TB) is convex cone. To show that C(TE) is closee in Lip(X' x A), let [co C C(TE), such that
tom |lc, - cll, = 0, for some Lip(X' x A). Let e >> 0. Then, there exists no E IN such that,
(1 (1-
[|mm c/laa
(10)
2
On the other hand, Ono E Cá (mg). Combining this with (1).. deduce that c C (Tg). Since this
true for arbitrary & > 0, we get E Newo ( (#x) = C(ME), which proves the desired closedness. m
B.2
Proof of Proposition 3.1
Proof. Assume first that e C (TTE) for some 0. Then, there exists Lip(X') such that
(u T,ū) S E, غ T- 2 -E, on X' A.
(11)
(12)
Since To vo. 11 can be written equivalently
(pT6 8) (wo, ū) Se. (Vo)
(13)
Let j be an optimal solution to the primal (Pa) with cost function č. By integrating I2 with respect ji and using that T. иo and (ū, 1) T- get
( (vo, ū) > --
(14)
=V/(Ma)
18

---

Therefore, by combining 13 and (44. we get
2 2-Y
V (vo) V (vo) - Vgg (vD)
This proves that "g is - optimall for (MDPa) with cost For the inverse inclusion, TT. be - for (MDP2),, and let V E Lip(X)) (Theorem A.1 be the optimal value function for the forward (MDPs). Then, by virtue of Theorem A.3 the following hold:
T
2 0, on X
(15)
2
(1000
(o
e.
(16)
(vo)
(vo)
Note that 15 holds due to dual feasibility, while
16
holds because eв is 2-2 1-y -optimal for (MDPa).
By setting u à + 1 E Lip(2'), we get by (1% ē u) = (mōg ē) (Mo, di) Vo- - due to [6). Therefore, E (TTE). This concludes the proof.
15 that ē T 2 -E, on X x A. Moreover,
- 1- c, where the inequality holds
B.3 Proof of Proposition 3.2
Before stating the proof of Proposition 3.2 we need the following preparation. Without loss of generality, assume that the true cost belongs to Cooneex - {Σ Q44; 0, > 0g = 1}. where {c} C Lip(X' x A) are known features. By linearity the true optimal value function belongs to (Ei=] O:elyy a O, Σ 0; = 1}, where u, V. (M.), for all i 1..... k. Note that by Theorem A.1 {u.] C Lip(X).. By using similar arguments to the proof of Theorem 3.1 we get that cost function e inverse feasible, i.e., E C(TT) and only if there exists a E R such that
a 1 - TT,u) 04 =1 a20, E
= 0,
2 0, Xn
(17)
Similar arguments hold for any choice of mitee-iimessionll space convex set S C Lip(X')
Proof. Let Jc C (Cn(TT))
(TT). For each n E IN, there exists an E R such that
Σ E an, (440 TT
S Sni
Σ ani (c; Tx
2 -n, on X' x A
(18)
an 2, E An,i 1.
Since the sequence {aw)n is bounded in RR& there exists a subsequence {a,,, } such that limy +00 an = a, for some a R². Taking the I + 2o in 18 we get 11 and so Ei arc E C(TT). This concludes the proof.
B.4 Proof of Proposition 3.3
Proof. It easy to check that for every E ("TEE) there exist c e C(TE) such that (p ē c) S E. and c ē < E, on x A. For example, if E Lip(X)) such that
{ (uRe, ė T
T ū)
< c,
(19)
2 -c, X x A,
then we may choose e = T ū. Let be an optimal policy for (MDPa). Then,
vea (Mo) V.TE (vo) (u
1 .)
19

---

= (M c - 8) +
-Mw0 c) + (
50
(100
1lv0 2)
2 7
B.5 Proof of Proposition 4.1
Note that Proposition 4.1 is minor extension from 48 Prop. 7].
Proof. Let c C(T)). then there exists certificate u Lip((() such that e - T, 2 0, on x A and (M c TT² 0. By Theorem 3.1 and its proof, we get that e inverse feasible and u = V Vo-almost everywhere (a.e.). Thus, if C, for some constant C, then C have T;,; Po-ac., and f (c 477 O.
I-y- Vo-a.e. We then
B.6 Proof of Proposition 4.2
For [1, oo], denote by II- the p-norm in IR and by y the usual inner product.
Proof. We consider the following tightening of the remi-infinict convex program (IP)
in.,,8.
E
S.I.
c Se,
Jua.
c- T- 0, on X
SxxA (xx)(c(1,0) C CCC. U E
((( 1,
(u c) (Vo, u) inf s.t.
c- TT 2 0, on X x A,
(20)
Sx (c(z, a) - TT a)) d(x,a) = =1
CE C Uny?
where the last equality follows by using that (Hig T7 = (Ty u) = (wo, u) and an epigraphic transformation.
The assumption that u1 = 1 and 0 (1 (1-9)eb(((xxA) ensures feasibility of the convex program 20
and by Assumption 2.1 (Al) the feasibility set is compact and thus the optimal value finite and attained. Note that leb( x A) denotes the Lebesgue measure of X x A. Moreover, since (20) is
tightening of (IP holds that Jn
Consider the defnite-dimensional version of (20).
infe s.l.
(pT c) (po, u)
c- TT 0, X A,
(21)
[xxx(e(x, (c(x, u, a) d(x, = 1, cE Lip(X' A), E Lip(
By the characterization of the inverse feasibility set, we have that J 0 and (ct, w²) is an optimal solution for (21) Note that (1 can be expressed in the standard conic form
inf
(lo, ar)
s.t.
Ar bo E K, xEX,
(22)
where
"Without of generality we may assume that fxxal (c' - TTr d(z,a) since we can always rescale the optimal cost and value function by the same scale factor.
20

---

(X, L) is a dual pair of vector spaces and to L;
[, Y is dual pair of vector spaces and bo E B:
K is positive cone in B and K" is its dual cone in Y, i...
K y E (y. b) 0, vb B);
: X B is linear and continuous with respect to the induced weak topologies.
Indeed, this is the case we introduce the following:
x a Lip(X' A) Lip(X),
L a M(X A) x M(x),
B 2 Lip x A) x R,
Y & M(X x A) R,
K å Lip(X' A)+ x {0),
K & MiX x A)+ x R.
bo (0,1),
to - ( -vo),
(c, (c
c C-Tuu (xxale- (T) (Txa(e-T a) d(r, a)
Alc, u) A
On the pair (X, C) we consider the norms
||||| [I(c, u))l max{[clle //lll..3 x == (c, x,,
|/||. sup (L, sup ()),)) + sup (12, u) ||
l isi
114 llw + |12/|w. 1= (11,2) E L.
which are dual each other. Similarly, on the pair (B, Y) we consider the norms
[1(,,, bl)
m [|b [l,, |b21}:
[1 32) l1 llw 192)-
With this notation mind, by virtue
31 Th. 3.3] we have that
Jne.
=0
(1|4ll + D, 11Alllog)
(23)
(llc* Ilc.. (c*) + ||u Il,,,
(u*)]l)
where Dy,0 o is an upper bound of a dual optimizer of (20) with respect to an appropriately defined dual
norm, and || is the operator norm of A. We will next compute the involved quantities in 23
We have
[ol.. || llw + || (pollw I-
(24)
Next note that
|Pull] ||Pu|| + |PulL S [| + Lplu/1
< max(1, Lp} ||ullc.
where in the first inequality we used that P is stochastic kernel and Assumption 2.1 (22) Therefore,
|c,
||c Pull.
< (2 + 7 max(1, Lp [I(c, w)ll
Moreover,
A2(c,
< (feclloc + (1+>)) |iml x A)
(2 + >)lbb(X x A) (l,,, w)ll
All all,
||l|
sup [1
|A(c,))]
21

---

+ x A), + maxx Lp}}
(2 + 7) max Lp, leb(X' A)).
(25)
It remains to compute the constant 4, To this aim, let {a; f=l " be basis elements in X given by
Tu- These are linearly inde- 2; = (c, 0), for 1,... ... nh and z; = (0, uz), for = nee n +l. Re +h
pendent by assumption. Then, define the linear operator Ane. R R + Y by Ane,,. (p)
ERo PiAr; = Σi= AgAr; + Ek=t/+1 Ar for p= (0, E R Then, it is easy to see that its adjoint A ne... Y + Reot. is given by A (y) [[A41 v) (Av y)l
On tn consider the norm
|| = (1(a, B) & maxf[la||1 ||
Moreover, we set
To Th 11 ..... (pTe cn.) (- vo, u1) ..... (- vo: Un
=
=
Then, the semi-infinite convex program 20
can be written in the form
inf s.l.
to pp
Jn In.
Anc.a P bo K, lllR S 0, p E Ruot...
(26)
Dualizing the conic inequality constraint in 26 and using the dual norm definition, we get its dual
Jnc.
-{
suPyEr
(bo, y) 01|A4* me - TollR-
(27)
s.t.
y E K
Let y* be dual optimizer for (26). Assume that there exists a constant > 0 such that
| no R- 2 C/ ||3/
Then by virtue
31 Prop. 3.2], we have the bound
20 Ir-
|| S
S D,.0.
(28)
CO
||bol|
To compute the constant D.,0, we need to bound the involved quantities in (28
We will first show that y 2 0. By Sion's minimax Theorem 775 the duality gap between (26)
and 27 is zero, i.e., Jn... = J.n... Note however that by construction Jn.... 0, since for any feasible to (26) it holds that to pp- p= (1T7 Ane.u bo) 2 0. Then,
Jnc. Jncn (bo, y²¹ 01 ne.. y² TolRR
4/ 0|| O1lAAt -TolRR.
Thus, y5 2 0. Therefore,
|4 ne. 3011
2 (Axn+t1: y²) 1- (A(0,, u1 ())"")))
(i, + v2 / Trus d(z, a)l
XxA
(1 7) llvill wlw + (1 - (1im))dimX** (X' x A)
7) min (in leb A))l|("
20
where we used that = 1, E M(X A)+ and so Ilvillw vi A), and v/ 2 0. In addition, direct computation gives.
+ Ku,co. Ke00 sup T. p 110, + 11,220000 S
|ioll Rt
1-7
Putting them all together in we get
20 To R
20 (0(Ke,o 0,00 Ku,0o)
| S
Dy.00
(29)
C8 bbo
(1 (1-7)² m-nn
d10
+
where we used that ||bol| 1. A combination of (23 (24). 25 and 29 ends the proof.
22

---

B.7 Proof of Theorem 4.1
The symbol -= refers to feasibility satisfaction, i.e, x -= R. means that a feasible solution for the program R.
Proof. The proof is consequence of (29 Theorem 11. 30 Lemma 3.2] and [30 Proposition 3.2]. Let denote the optimization variable of (SIPN)
by (a, 8,6) E R where
(015...; (n.)) and (Bt...., Bo..). Let (x, the uncertainty parameter and
A X' A the uncertainty set. Consider the function
{22 - Σ =1
a,G(1,
Σ j=1
B,(u((z)) (Py)(t))~Pu((;,000
and the set
3 = B,, R Ructnut1 ||al|2 10,118112 10.
(p - (02.-)(2-)-220 se, (-f(2,)) /- + +e)dd 1,8 2 20)
Note that C Ro convex and compact and independent of À E We show that the set 2 is nonempty. As noted in the proof of Proposition 4.2
( (Appendix (B6)) the assumption that 11 = 1
and 0 (1=)))e((A'xxA) considered Proposition 4.2 and Theorems
4.2 ensures the feasibility
of the convex program [IP) which in particular implies that Z 0. Here leo x A) denotes the
Lebesgue measure of X' A.
Note that the function f Z x A - R is measurable, and linear in the first argument for all À E A. Moreover, by Assumption 2. (AI) (22)
we get that f is bounded in the second argument for all E 2, and f is Lipschitz continuous on A uniformly in Z with Lipschiz constant
LA 0 oo Th Lp Lu).
After introducing this notation, as,
that the random convex program
SIPN be written
SIPN of inf=ez hT s.t. f(2,A10) 20, ve vt= 1...,..
N,
where h (Onuee Open 1) and the multisample (1 (1(0) (0)0)(())))) (0)) W a random element on the
product probability space (A B(A)N PN). Moreover, SIPN is the scenario counterpart of (IP)
{ infzez s.t.
hT f(z,A) AAEA
IP:
where one enforces constraint satisfaction for all the realizations of the uncertainty. Clearly (a, 8) + IP, then the associated cost function c Σ age; (*TT).
For a fixed reliability level c E (0,1). 1), the associated chance-constrained program given by
CCP:: { infzez TT s.t. P[AE:: 5 2-cc
where one allows constraint violation with low probability. Now the assumption that 1 and
> [I->) Xii(X'XA sufficient for the existence of Slater point for the robust convex program
f20. A) < 0. By this fact and by Assumption 4.2 we can apply 29 Theorem 1] and conclude that for N 2 N(n. + ny + 1, e, 5) it holds that
i.c., there exists E Z such that AeA A
A [ēN + CCP. 2 1 8,
(30)
where nN = (iN, ( is the optimizer of (SIP h. Note that by Assumption 4.2 the optimizer En is uniquely defined and is Z-valued random variable (AN, PN
23

---

Consider now the (-perturbed robust convex program for some Ç > 0,
inf s.t.
hT2
IP&
5(z 5, A.
Note that due to the min-max structure of (IP), the mapping from Ç to the optimal value of IP is Lipschitz continuous with Lipschitz constant
[30 Remark 3.5].
We have the following implication,
Re
2 = (a, (,,) Ip + Σ ags (C+)(TT))
(31)
Moreover, under Assumption 4.1 and since f (2, -) is Lipschitz continuous on A uniformly in 2 with Lipschitz constant LA, by virtue of (30, Lemma 3.2] and [30] Proposition 3.8], we have that
- CCP. = 2 = Ph(()))
(32)
where
h(c) & LAg (e).
(33)
Combining (30)
31).
32
and (33
we get that for N 2 N(nc + nu + 1. +1,9(2,,,))
ININN E c 2 -
Finally notice that since (SIP
is relaxation of (PP) we have 5 S Expprox with probability 1.
B.8 Proof of Theorem 4.2
For the remaining analysis we will use for brevity the following notation,
P - pp,
P, - (PP))" Pe - vn" "
and adopt similar notation for products of probability measures, e.g., Pr. A Pr @ Pg. We first need the following result.
Proposition B.1. Let 8K2 8 In (S
10, and 5 E (0, Under Assumption 2. and (AI) for 2
and 8K2 In ( (8me) it holds with probability at least 8/2 that (1-7)222
(MDg,c- uu (1i5 c) + (Pis 24) Sc
sup NEUR,
where Kepp maxi=1,..... |calloo and Ku,00 max I.... l|uilloo
Proof. First note that under Assumption (Al) the quantities K6,00 and Ku,00 are finite. Now by using the Hoeffding's bound, have that for SK" Gn, In 18m)
Pe [1po. uz) - (Mo, uz}
e
2 1
(34)
4n.
for all j ..... Nu. Therefore,
P sup uEUny
(vo. u) (Vo, u)
I
2 P Vj I..... Ne. ())
(vo, uz)
S 2
N 6/4.
where the first inequality follows by the monotonicity property probability measures and the second one follows by 34 and union bound. Integrating over the whole (I2),,P,), end up that
P. sup uEU...
(vo, u) - (vo, u) S S 5/4.
(35)

---

By using analogous arguments and taking into account that 7 ax)l I KE for all
1-7
(x), E A.tEN,i -.LE,,i-L,..... L,..., we can conclude that for m 8K2 I'n, Iu (27c)
[1-3)=r2
Pr.l sup cECn.
(1050 c)
(1r0: C)
S 21
6 1 8/4.
(36)
BB
Finally, note that
IP P
sup
c C- -(170 ( + +v0, u)
6
ccC uuU
T, [ [An
2 1 8/2,
where in the first inequality have used the monotonicity property of probability measures and the
second inequality follows by (35). 36) and simple union bound.
Proof of Theorem 4.2
By using the same notation in the proof of Theorem 4.1
we can write
{
inf
hT
SIPN
s.l.
f(z, (() S 0, Vi 1, .,
where
Zm, {== (,, E Rn
|all2 118122 0,
The a (T) Σ
nu
3y Uz) (E) Se.
((() 1,, 2 20
Let mNm (a..m.. my.m. E.. be the optimizer of SIPN. and let CN.m.n De C,, C be the associated cost function.
We first fix multi-samples S. Similarly as in Theorem 4.1 we can conclude that for N 2 N(ne Tu + 1, 0 (,
PcWEAN a T,, / Pm... (y, r) 2 5/2,
where IP n. is the e-perturbed robust counterpart of SIPN.m.n given by
{
inf s.t.
TTz f(z, A) S e, A,
IP IPm.n
Integrating over the whole probability space (12m @ Xm P Pr.g), we get
P Py.T.eEEN.m..
- IP [pm,nee] 2 5/2.
(37)
SK2
n' 2
Brx
8K? 0n In a (1 (1-7)222
However, by virtue of Proposition B.1 for
and
( (un CN.mm T TT ÜNN...)
(uoo CN.m.) + (Mo, uN.m.))
(38)
with probability IP yy at least - 8/2. Combining
(38 and the bounds Theorem 2 of
by simple union bound completes the proof.
25

---

C
Numerical Results
We consider a one-dimensional truncated Linear- Sineea--uuadatii-Gaause (LQG) control problem com- prising a linear dynamical system
I++1 Ax, + Ba, + Wt: t N,
and a quadratic state cost c(s, a) Q2 + Ra², where A, E. 0,0>0,R>>
We assume
that state and action spaces are given by X = A = [- for some parameter L > 0. The disturbances { her are i.i.d. random variables generated by a truncated normal distribution with known parameters and a, independent of the initial state To. Thus, the process wt has distribution density
8 1E
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)
Sc ply x, addy for all C' E B())), that is given by
ply x. a,a)= fly Ax Ba, nr, a, D)-
In the special case that L too the above problem represents the classical LQG problem, whose lution can be obtained via the algebraic Riccati equation [77] 372]. By referencing [3] Lemma7.11, can readily conclude that Assumption 2.1 holds in this context with specific constants
2L max A, B}
Lp
L. ma
02v2T
2T
レ-
As value function u X - RR we use simple polynomial of degree 2 (n,, 3) such that
u(x) Σ (z), u,(x) = =
whereas the cost function X x A R is approximated by the following weighted sum (n. 9)
c(I Σ a;c(
where ei (1, = 1, c2(2, = x, ca a) a ca(a, a) = ra, cs a) = x², co(2, a) = a², (x) 2²0, c2(,,a) raa. co(x, x2 a For the simulation, the parameters are set as O, a = 1, and 7 0.99. The code for these The experiments were run on
L= 10, A -155,
Q
1, QQ==-- -R
experiments can be found at giggtu..cco.......... Btt.ub.coomAPPAAC...CC... 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 3 focus on the sampled inverse program|STD [SIPN] More precisely, we solve the program[SIPp for various choices of sample sizes N and denote its corresponding optimizers (āNN _,,, Ex) and its extracted cost function as ē The ã C. Figure shows the probability of the learnt cost function č being (É + ii-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 e, the likelihood of being inverse feasible grows with the inerease of the sample size N. Additionally, for 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.. Figure 33 shows the objective function of program SIPP 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 function of the sample size N. Figure (3r visualizes the theoretical sample complexity of Theorem 4.1 i.c., for various choices of d and e, plot the
26

---

-10"8
F(6x c (fo)))(me)))
0.8
0.2
0.2
200
400
600
800
1,000
(a) Empirical confidence
(b) Objective function of SIP
0.8
45,
-0.1
0.2
on V6 teol
1.19
1.19
1.2
1.2
-1
(c) Sample complexity of Theorem
(d) Performance of learnt cost
Figure 3: Solutions of the Sampled Inverse Program SIP The variable N is the number of i..d. samples (z, a) drawn uniformly from X' x A. We run 1000 independent experiments. Plot (a) shows the empirical probability of the estimated cost function ēλ being an element of the feasibility set, as described in Theorem 4.1 given values of N and e. Plot (b) shows the objective value the random program SSIN i.e., EN on average over the 1000 experiments, where the shaded area shows the standard deviations. Plot (c) is visualization of the theoretical sample complexity as given by Theorem 4.1 For various values of 8 and we plot the sample size N = N(n, + nh + 1, 9 ( 8). 10-7 Plot (d) compares the discounted long-run costs
The variation parameter is set to A V (Po) for the average čx of the learnt costs čN under the expert policy (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, + Th + 1, ( (, To simplify the computation, we used the closed form upper bound for the function derived in 78 and given as
N(n, c, 8) log (3)
2n
2 (3)
2n
log
c
When comparing Figure 3a and Figure 3c we can see that there is significant gap between the empirical and theoretical bounds. The dynamics of variation in e, however, match the empirically observed behaviour. Figure 3d visualizes the performance of the learnt cost čω by comparing the discounted long-run cost of the expert policy under this learnt policy Vi (26) with its theoretical and Proposition 3.1 for large N this
lower bound min V.T, (vo). According Theorem 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 ě with its empirical average, denoted ēx taken over 1000 independent experiments. More precisely, for 1000 initial conditions zo 1o we plot TH (zo) and the theoretical lower bound min V (x0). ēx
Ex
Sampled Inverse Program with unknown transition kernel. The second experiment, Figure solves the sampled inverse program SIP mm.nkkk with unknown transition kernel. Compared to SIP since we assume the transition kernel be unknown, the inequality constraints are based on sampled state transitions. The empirical probability, shown in Figure 4a is derived from 1000 independent experiments. To decrease the degrees freedom the parameter selection we set = m = & for the simulations. The behaviour of the empirical confidence. observable in Figure 4a follows the
27

---

[Boconu CCtimosatte (ooassaiiaaa (mal))
0.8
10
0.4
600 800
1,000
(a) Empirical confidence
(b) Sample complexity of l
Figure 4: Solutions of the Sampled Inverse Program SIP N. m.n.k The variable N is the number of i..d. samples (z, a) drawn uniformly from X' x A. We run 1000 independent experiments. Plot (a) shows the empirical probability of the estimated cost function ČN.m. being an element of feasibility set, as described in Theorem 4.2 for different N, k pairs given a chosen accuracy parameter Plot (b) shows theoretical lower bound on k depending on N, for set e, as described by Theorem 4.2
trends shown in Figure 3 As expected, an increase in the number of samples increases the confidence of learning a cost function CNmm,.. that belongs to the inverse feasibility M,,, to +(TE) It can be seen how, even for the largest possible to reach a certain empirical confidence the .m.. proggrm program requires many more state-action samples compared to the SSIP program. When comparing the empirical confidence of given c, N, and with the theoretical sample complexity, following Theorem 4.2 of corresponding the same and N it can be seen that the empirical sample performance of S. is much more efficient.
28

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The abstract and introduction do reflect and summarize the paper's contri- bution and scope. In the sections following we provide the rigorous statements of these contributions.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
It is fine to include aspirational goals as motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: 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 curse of dimensionality). Moreover, in this remark we point out that the selection of an "informative" distribution for the random state-action selection 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 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 vell-specifiiattin, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with 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, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails 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 faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
29

---

3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: All statements in the paper are equipped with detailed and correct proofs, which are provided in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: All our simulations are transparent and can be easily reproduced by the code available via the GitHub link in the paper, see Section C We would like note that our datasets are synthetic datasets.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
30

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open tions to faithfully reproduce the main experimental results, as described in supplemental material?
the data and code, with sufficient instruc-
Answer: [Yes]
Justification: The code of all our experiments available via the GitHub link in the paper, is therefore easy to reproduce our results.
see Section C
Guidelines:
The answer NA means that paper does not include experiments requiring code. Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
public/ poolic/guiies// CodeSuumissiooooooo.....o
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ //nips.
for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: The details of the experiments provided via our files available in the GitHub, whose link is provided the paper, see Section
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: 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 Figure we run 1000 independent experiments and plots show empirical probabilities computed from them.
31

---

Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should 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).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: As pointed out in Section C all our experiments were run on workstation with an AMD Ryzen 5950X CPU (16 cores) and 128GB of RAM.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: http:///warrr.c.ccppaaccccccceaa
Answer: [Yes]
Justification: Yes, 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 deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
32

---

Answer: [NA]
Justification: Our work 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 why the paper does not address societal impact.
Examples of negative socictal impacts include potential malicious unintended uses (c.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 being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Due 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 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 challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
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 any existing assets.
Guidelines:
The answer NA means that the paper does not existing assets.
33

---

The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the datasets..paerssttt paperswi thcode. com/datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of 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 s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
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 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 anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or 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.
34

---

Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors 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 the institution conducting the review.
35


Reviews:
[{"review_id": "sEDZGyxQfe", "reviewer": "Reviewer_p8oS", "summary": "The paper\n1) 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)\n2) 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\n3) 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\n4) provides PAC results for the case where we only have access to a finite set of samples from the expert policy", "questions": "- In Section 4.1 you claim that \"the inverse feasibility set C(πE) contains some solutions that arise\nfrom 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.\n- 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?\n\nMinor points and suggestions:\n- 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.\n- 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?\n\n\nHere are a few minor typos (or subjective suggestions) I noticed:\n- \"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\".\n- l. 108 missing comma after citation\n- \"\\gamma-discount \\nu_0 optimal policy\" - the \"discount\" sounds strange. Maybe \\gamma-discounting would sound better?\nl. 330 \"Theorem\" -> theorem\nl.379 missing closing brackets\nl. 550 extra comma before \"under\"\nl. 838 sate -> state\nl. 841 performs -> performance", "limitations": "- As said, the bounds provided are not always useful in practice yielding completely impractical requirements.\n- The applicability to real-world problems is unexplored in the paper and requires further work.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The optimal control and reinforcement learning communities (i.e. also communities studying the \"inverse optimal control\" and \"inverse reinforcement learning\" (IRL) problems) have been living somewhat separate lives, each using their own formalisms and solution methods. I think there is a lot the two can learn from each other so I'm glad to see this paper, drawing heavily on the control-theory angle, at NeurIPS that has been more a harbour for the RL community. \n\nI think the paper is great step toward putting work on IRL on firmer theoretical foundations. Almost all previous comparable cases of theoretical analysis in IRL that I've seen are addressing only the tabular case of finite state and action spaces which are of limited practical value. Extending this kind of theoretical treatment to continuous spaces is valuable. The paper does a great first step in that (and a sizeable one).\n\nThe paper tries to do a lot, but especially given the amount of theoretical concepts it covers, it manages to maintain good clarity, with a minimal amount of typos and other mistakes. (I want to emphasize my appreciation for the level of writing here - I can easily imagine a paper covering the same technical ground which would be hell to read for someone previously unfamiliar with some of the theory. It must have been a lot of work to rewrite it this way: I do appreciate it and think it makes for a much more impactful paper!)", "weaknesses": "- 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. \n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the time spent in evaluating our work. In the following, we address your comments.\n> 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.\n\nWe thank the reviewer for recognizing the substance and novelty in our paper, which could indeed justify an even longer manuscript. We are delighted by your appreciation of our writing style, as we put significant effort into presenting the material in an accessible and comprehensible manner without compromising on mathematical clarity and rigor.\nGiven the constraints of the conference paper format and the substantial amount of theoretical concepts we cover, we aimed to present our findings concisely while maintaining coherence. For the final version of the paper, we will utilize the additional page allowed to further elaborate on certain sections and provide additional intuition and context about the presented theory.\n\n> More thorough empirical evaluation would also be beneficial...\n\nWe illustrate our method with a simple truncated Linear Quadratic Regulator (LQR) example (see App. C) to provide better intuition about the method and the proposed sample complexity bounds. \nAlthough the focus of this work is theoretical, we will endeavour to provide a more complex numerical result, possibly in the Supplementary Material. It is worth noting that the work of Dexter et al. [50], the only theoretical study addressing IRL in continuous state (but discrete action) spaces, also includes simulations for a representative one-dimensional state space MDP.\n\n\n> The bounds provided by the theorems don't always seem meaningful ...\n\nTheorem 2.1 provides explicit sample complexity bounds for achieving a desired approximation accuracy with our proposed randomized algorithm. The corresponding sample complexities include the expert sample complexity, the number of calls to the generator, and the number of sampled constraints. 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. 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. We will include these examples of manageable dimensionality and related references in Rem. 4.1. Moreover, in the uploaded supplementary PDF, we show additional instances of figure (c) for different parameter choices, illustrating the significant effect on the resulting sample complexities. \n\nNote that  a similar exponential dependence to the dimension of the state space has been established in Dexter et al. [50], the only theoretical work on IRL in continuous states and discrete action spaces. \n\nWe intend to provide a more detailed discussion on enhancing sample complexity bounds through the utilization of the underlying problem structure in the paper. 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. However, a comprehensive mathematical treatment of these inquiries will be addressed in future research endeavors. \n\n> Isn't the identifiability issue a deeper issue than a mere \"mathematical artifact\"?\n\nThe normalization constraint in our formulation primarily aims to address the ill-posedness (or, equivalently, the ambiguity issue) inherent in the IRL problem.\nIn 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. 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, whereas 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).  Overall, the purpose of the normalization constraint is to exclude a large class of meaningless solutions, rather than to address the identifiability problem. Note that, unlike recent theoretical IRL works [48-53] 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.\n\n> 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?\n\nThe characterization of the inverse feasibility set is due to linear duality and complementary slackness conditions (lines 210-211). In particular, the constraint that holds pointwise is due to dual feasibility and  and the constraint that holds in expectation is due to strong duality (see proof of Thm. 3.1 lines 611-612). The formulation (IP) is a relaxation of the constraints in the inverse feasibility set and paying a\npenalty when violated (lines 288-289). We will add this insight to the revised text.\n\n> Minor points suggestions\n\nWe will follow your suggestions and remove the third motivation as well as the indicated sentence about the recovery of the cost function to avoid confusion.\n\n> Minor typos\n\nWe thank the reviewer for spoting these typos; We fixed all of them.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "sc1kOaioJe", "reviewer": "Reviewer_sQPr", "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.", "questions": "See Weakness", "limitations": "NA", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- Avoiding repeated RL solving: Unlike many existing methods, this approach does not rely on repeatedly solving the forward reinforcement learning problem, which is computationally expensive for continuous spaces MDP.\n\n- Sounding Theoretical guarantees: The paper provides probabilistic convergence guarantees on the quality of the recovered solution, bridging the gap between theory and practice in continuous IRL.\n\n- Addressing reward ambiguity: The paper contributes to tackling the reward ambiguity problem by adding a normalization term.", "weaknesses": "- 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.\n\n- 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.\n\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> 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.\n\n\n\nWe put significant effort into presenting the material in an accessible and comprehensible manner without compromising on mathematical clarity and rigor. Given the constraints of the conference paper format and the substantial amount of theoretical concepts we cover, we aimed to present our findings concisely while maintaining coherence. For the final version of the paper, we will utilize the additional page allowed to further elaborate on certain sections and provide additional intuition and context about the presented theory. In particular, we will make an effort to explain and justify the two theorems of our paper better. \n\nOur first theorem (Theorem 4.1) guarantees that the cost function $\\tilde{c}_N$, obtained from the solution of the proposed finite-dimensional random convex counterpart ($SIP_N$), is indeed $(\\tilde{\\varepsilon}_N + \\epsilon)$-inverse feasible for the expert policy $\\pi_E$. Here, $\\tilde{\\varepsilon}_N$ is the solution to $(SIP_N)$ and $\\epsilon$ is an accuracy parameter \naffecting the sample complexity $N$, which scales with $\\{1/\\epsilon, \\log(1/\\delta), n\\}$ as described on Line 328. The sample complexity depends on MDP characteristics, such as state-action space dimension (exponentially) and basis functions for cost $n_c$ and value function $n_u$, as noted in Rem. 4.1.\n\nTheorem 4.1 is primarily of practical interest because the program $(SIP_N)$ requires knowledge of the transition kernel, which is typically not available in RL. Therefore, our second theorem (Theorem 4.2) considers a more realistic setting where knowledge of the transition kernel is not required. In this setting, the proposed cost $\\tilde{c}_w$ for $w=\\{N,m,n,k\\}$ is derived from the program $(SIP_w)$ for $w=\\{N,m,n,k\\}$. Essentially, Theorem 4.2 extends the results of Theorem 4.1 to this more realistic scenario.\n\n\n> 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.\n\nWe illustrate our method with a simple truncated Linear Quadratic Regulator (LQR) example (see App. C) to provide better intuition about the method and the proposed sample complexity bounds. The focus of our paper is on an optimization perspective of IRL and deriving fundamental, provable PAC bounds for continuous inverse RL in a very general setting. Thus, studying the empirical performance beyond the academic LQR problem is out of scope and will be addressed in future work. It is worth noting that the work of Dexter et al. [50], the only theoretical study addressing IRL in continuous state (but discrete action) spaces, also includes simulations for a representative one-dimensional state space MDP.\n\n\n\n> 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.\n\n\nThe theoretical soundness of the proposed algorithm is ensured by our main results (Theorems 4.1 and 4.2). If \"large-scale\" is interpreted as the number of state/action variables, we address settings with continuous (uncountable) state and action spaces. Thus, even our simple 1-dimensional LQR example might be considered \"large-scale.\" However, if \"large-scale\" refers to the dimension of the continuous state and action spaces, our bounds indeed suffer from exponential sample complexity in these dimensions. This is a manifestation of the infamous curse of dimensionality, which cannot be avoided. Please refer to our detailed discussion in Remark 4.1 of the paper.\n\nWe agree with the reviewer that to apply our bounds to complex and high-dimensional real-world problems, we need to more carefully exploit underlying structures. Otherwise, the sample complexity bounds are too large and of limited practical use. However, we would like to emphasize that these sample complexity bounds are often conservative in practice, as can be seen in our empirical evaluation in the numerical results, see Section C. Experiments conducted on closely related scenarios have shown promising approximation bounds, as detailed in [1,2].\n\nIn this work, our aim is to address the most general setting possible with the minimal assumptions required to establish PAC bounds for inverse RL. We plan to explore exploiting additional structures to derive tighter bounds for well-structured subclasses of problems in future work.\n\nFinally, we would like to emphasize that the provided bounds are part of our contributions. We refer the reviewer to our response to Reviewer PJ8y (in section \"Questions\"), where we briefly highlight our main contributions and how they differ from recent theoretical works on IRL, underscoring the impact of our paper in this new research wave.\n\n\n[1] Marco Campi and Simone Garatti, Introduction to the Scenario Approach, Society for Industrial and Applied Mathematics, 2018\n[2] Xiaojing Zhang, Sergio Grammatico, Georg Schildbach, Paul Goulart, John Lygeros, On the sample size of random convex programs with structured dependence on the uncertainty, Automatica, Volume 60, 2015", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nvAoZR3FNY", "reviewer": "Reviewer_579s", "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.", "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? \n\n2. 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": "/", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "The paper proposes a detailed and rigorous description of the problem setting, the method and the results. The contributions are clearly stated and the overall writing is good and easy to follow. The paper provides both theoretical results and experiments, which makes the discussion relatively complete.", "weaknesses": "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. \n\n2. 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$?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the time spent in evaluating our work. In the following, we address your comments.\n\n## Weaknesses\n\n> The paper's result lacks benchmark ...\n\nThis work focuses on theoretical aspects of inverse RL, specifically on learning a cost function in continuous state and action spaces from observed optimal behavior, and deriving PAC bounds. We do this by approximating the infinite-dimensional problem with a finite convex problem and rigorously quantifying approximation errors.\n\nMost existing inverse RL research is on finite state and action spaces. Current work on continuous spaces either lacks theoretical guarantees or focuses on the feasibility set (see [42, 43, 44, 23, 26, 45, 27], [51, 52, 53]). Our related work section offers a detailed comparison. We also refer the reviewer to our response to Reviewer PJ8y (in section \"Questions\"), where we briefly highlight our main contributions and how they differ from recent theoretical works on IRL, underscoring the impact of our paper in this new research wave.\n\nWhile we demonstrate our method with a simple truncated LQR example (see Appendix C), we agree that comparing it with existing heuristic methods in continuous spaces is valuable. Our one-dimensional experiment underscores the need for further investigation into choosing basis functions and sampling informative state-action pairs. We are addressing these questions theoretically and will include a discussion in the revised paper.\n\n>Second, the paper doesn't reduce its general result to simpler special cases ...\n\nThank you for the comment. In the tabular MDP case, our proposed bounds become redundant. If the transition kernel $T$ is known, the $\\varepsilon$-inverse feasibility set (Equation 1) is a linear program with finite variables, solvable in polynomial time. Thus, our method for approximating infinite-dimensional LPs with function approximation and constraint sampling is unnecessary, making our error bounds for this approximation irrelevant.\n\nOur approach is intended for continuous MDPs. For large but finite state and action spaces, where direct solution of LPs is impractical, function approximation and constraint sampling are applicable, and our PAC bounds are relevant.\n\nRegarding additional structure, such as a linear MDP, related works suggest that incorporating such structures could improve PAC bounds (see [2]). Investigating how to leverage linear MDP structures in our inverse RL approximation hierarchy is a promising future direction, though it requires considerable effort.\n\n[2] Zhang et. al., On the sample size of random convex programs with structured dependence on the uncertainty, Automatica, Volume 60, 2015\n\n>Part of the result is unintuitive ...\n\nWe thank the reviewer for this comment. As written, it is indeed unintuitive because there is a small typo causing the confusion. The constant $d$ in Proposition 4.2 should be $d = leb(\\mathcal{X} \\times \\mathcal{A})$, where $leb(\\cdot)$ denotes the Lebesgue measure. In the proof, on line 671, it is clear why $leb(\\mathcal{X} \\times \\mathcal{A})$ is the correct constant. \n\n>And the bound shows that ...\n\nIndeed, the reviewer is correct. When examining the bound in Proposition 4.2, the resulting error monotonically decreases as $\\theta$ increases, suggesting that $\\theta = \\infty$ would be optimal. However, the sample complexity in Theorem 4.1 increases monotonically with $\\theta$. In other words, a larger $\\theta$ requires a larger number of constraint samples. Therefore, $\\theta$ must be selected to balance these two factors. We will include a remark on this in the revised version.\n\n## Questions:\n\n> 1.For challenge (a), it seems ...\n\nThis is an assumption. We assume that the expert policy $\\pi_E$ is optimal for a unique true cost function $c^\\star$ with $u^\\star$ the corresponding optimal value function. \nAlthough this true cost is unknown, some prior knowledge about its properties allows us to choose appropriate linear function approximators 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. Essentially, the term $\\varepsilon_{\\textup{approx}}$ measures the expressiveness of the linear function approximators. \n\nWe would like to highlight that, in practice, assuming the expert policy is produced by a unique true cost does not contradict the ill-posed nature of the IRL problem, where the expert policy is optimal for infinitely many cost functions.\n\nA key question is whether, despite assuming a unique true cost, any inverse feasible cost solution can replace the true cost in Proposition 4.2's approximation error expression due to IRL's inherent ambiguity. The answer is yes: if the basis functions approximate the true cost well, it will be recovered accurately. Otherwise, if the approximators represent a different inverse feasible cost, that cost will be recovered instead. This aligns with expectations.\n\nWe’ve added this discussion to the revised paper for clarity. Thank you for highlighting this point.\n\n> For figure (c) in the experiment ...\n\nThank you for your comment. Figure (c) shows how sample complexity (x-axis) depends on the confidence level $1-\\delta$ (y-axis). As sample size increases, the confidence parameter $\\delta$ decreases, which aligns with the logarithmic growth of sample complexity with $\\log(1/\\delta)$.\n\nFigure (a) evaluates empirical confidence with four different accuracy parameters. As noted, the parameters result in impractically large sample complexity bounds. The proposed bounds have large constants, limiting their practical use compared to the empirical results in figures (a), (b), and (d). The main value of these bounds is in understanding how sample complexity grows with problem parameters like accuracy $\\epsilon$ confidence $\\delta$ and dimensions.\n\nAdditional examples of figure (c) with different parameters are provided in the supplementary PDF.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7IGd151MSE", "reviewer": "Reviewer_PJ8y", "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.", "questions": "## Last comment after the author-reviewer discussion deadline\n\nDear Authors,\n\nSorry 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.\n\n1)  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.\n2) 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.\n\nOverall, 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.\n\nSome additional notes to the authors:\n- 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;\n- 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;\n- 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);\n- 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.\n\n\n\n\n----\n----\n----\n----\n\nThis 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.\n\nFUNCTION CLASS\n\nThe 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).\n\nINTERPRETABLE RESULTS\n\nTo 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.\n\nSOLUTION CONCEPT\n\nInstead 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.\n\nOn 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?\n\nTYPOS\n\nA few typos I noted while reading: \n- l.73 \"of\"\n- l.108 missing full stop\n- l.254 \"F\" at start of the sentence", "limitations": "A section discussing limitations could have been included at the end of the paper.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "- The paper tackles a relevant problem that miss a theoretical understanding in the literature;\n- The paper is base on an optimization perspective that is original with respect to prior works.", "weaknesses": "- The presentation is confusing and could be improved in many ways to make the paper more accessible;\n- 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;\n- The motivation for some design choices (e.g., linear normalization constraint) and assumptions appears to be weak or absent.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the time spent in evaluating our work. In the following, we address your comments.\n\n## Weaknesses\n\n> The presentation is confusing ...\n\nWe would greatly appreciate it if you could specify which parts of the paper you find confusing. We put significant effort into presenting the material in an accessible and comprehensible manner without compromising on mathematical clarity and rigor. Given the constraints of the conference paper format and the substantial amount of theoretical concepts we cover, we aimed to present our findings concisely while maintaining coherence. For the final version of the paper, we will utilize the additional page allowed to further elaborate on certain sections and provide additional intuition and context about the presented theory.\n\n> The paper provides mostly negative statistical results ...\n\n Could you please clarify what you mean? Additionally, we respectfully disagree with the comment that our assumptions are too strong. We believe that Ass. 2.1 in the setting of  continuous MDPs  is standard and, to the best of our knowledge, as general and mild as possible (see also lines 179-187). Ass. 4.1 is easily satisfied if X and A are compact and the sampling distribution continuous. Furthermore, Ass. 4.2 and 4.3 are directly satisfied if a tie-breaking rule is introduced, as noted in the text.\n\n\n>The motivation for some design choices ...\n\nThe normalization constraint is motivated by an entire section (Sec. 4.1) and theoretically justified by Prop. 4.1. We are certainly open for suggestions on how to motivate it even better. Also it would be helpful if you could specify what \"other design choices\" you are referring to.\n\n\n## Questions:\n\n> This paper tackles an interesting problem ...\n\nThank you for the 2024 references, which we will add and discuss in our revised manuscript. We briefly highlight our main contributions and how they differ from recent theoretical works on IRL, underscoring the impact of our paper in this new research wave.\n\nFirst of all we provide a novel optimization perspective of the IRL problem that allows us to characterize the inverse feasibility set by means of Lagrangian duality. We believe this new formulation, applicable to both discrete and continuous MDPs, is more powerful and independent of the expert's complexity, unlike previous works [48-53] and Lazzati et al. 2024. Most importantly, it erases  the problems encountered in the formulations [51-53] and Lazzati et al. 2024. \nThe authors in these works study solely how to deal with the unknown transition law and how to sample efficiently from the expert policy. In their formulation addressing these questions is complicated. However in our formulation this question is easily addressed with efficient expert sample complexity by just using Hoeffding bounds (Prop B.1 in the proof of Thm 4.2). \n\nSecond, unlike recent theoretical IRL works [48-53] which avoid discussing this ill-posedness 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. \n\nOur result on linear function approximators (Prop. 4.2) is applicable even in the tabular setting considered in [48,49,51-53]. This contribution is crucial and missing from the literature on large-scale finite MDPs.\n\nFinally, we addres the problem of extracting one single cost function with theoretical guarantees. Learning a whole inifinite feasibility set is impossible even for the simplest tabular MDP problem. While constraint sampling has been proposed as a heuristic in the pioneering paper by Abbeel and Ng (2000), we provide explicit performance bounds and sample complexity for this methodology in continuous MDPs. The corresponding sample complexities include expert sample complexity, number of calls to the generator, and number of sampled constraints. The first two complexities scale gracefully with problem parameters, whereas the number of sampled constraints scales exponentially with the state and action space dimensions, making the algorithm particularly suitable for low-dimensional problems.\n\n\n\n\n> FUNCTION CLASS: \n\nOur paper tackles the inverse RL problem with minimal assumptions, contributing significantly to the limited theoretical research in this area. While some sample complexity bounds may be impractical, the results are not negative. The reviewer suggested that additional structures like linear MDPs could improve PAC bounds. Prior work supports this idea (see Zhang et al., 2015). We are interested in exploring this in future work, although it will require substantial effort.\n> INTERPRETABLE RESULTS: \n\nThank you for your comment. Thm 4.1 ensures that the cost function $\\tilde{c}_N$ from the finite-dimensional random convex problem $(SIP_N)$ is $(\\tilde{\\varepsilon}_N + \\epsilon)$-inverse feasible for the expert policy $\\pi_E$. Here, $\\tilde{\\varepsilon}_N$ is the solution to $(SIP_N)$, and $\\epsilon$ is an accuracy parameter affecting the sample complexity $N$, which scales with $\\{1/\\epsilon, \\log(1/\\delta), n\\}$ as described on Line 328. The sample complexity depends on MDP characteristics, such as state-action space dimension (exponentially) and basis functions for cost $n_c$ and value function $n_u$, as noted in Rem. 4.1. Thm 4.2 addresses a more realistic scenario without requiring this knowledge. We will clarify these results further in the additional page we are given.\n\n\n> SOLUTION CONCEPT: \n\nOur approach allows learning an approximately feasible reward in a PAC sense, as demonstrated by Theorems 4.1 and 4.2. While our normalization constraint prevents trivial solutions, our paper does not address selecting the \"most informative\" reward, which could be motivated by its utility for downstream tasks. Adding regularization constraints, such as an entropy term, could help select such a reward. This integration into our scenario programs is a topic for future research.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all reviewers for their helpful feedback. Below, we provide our responses addressing each point raised by the reviewers.

Meta-review: 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)$).**
Decision: Accept (poster)