Inverse Reinforcement Learning in a Continuous State Space with Formal Guarantees
Authors: Gregory Dexter
Kevin Bello
Jean Honorio
Venue: NeurIPS 2021 Poster (2021)
Keywords: Statistical Learning Theory
Inverse Reinforcement Learning

Abstract: Inverse Reinforcement Learning (IRL) is the problem of finding a reward function which describes observed/known expert behavior.  The IRL setting is remarkably useful for automated control, in situations where the reward function is difficult to specify manually or as a means to extract agent preference. In this work, we provide a new IRL algorithm for the continuous state space setting with unknown transition dynamics by modeling the system using a basis of orthonormal functions. Moreover, we provide a proof of correctness and formal guarantees on the sample and time complexity of our algorithm.  Finally, we present synthetic experiments to corroborate our theoretical guarantees.

Inverse Reinforcement Learning in a Continuous State Space with Formal Guarantees
Gregory Dexter
Kevin Bello
Department of Computer Science
Department of Computer Science
Purdue University
Purdue University
West Lafayette, IN, USA gdexter@purdue..m edu
West Lafayette, IN, USA kbell Abellomenn sbellomeSpurrdee edu
Jean Honorio
Department of Computer Science Purdue University
West Lafayette, IN, USA j jhonorio@purdue edu
Abstract
Inverse Reinforcement Learning (IRL) is the problem finding a reward function which describes observed/known expert behavior. The IRL setting is remarkably useful for automated control, in situations where the reward function difficult to specify manually as a means to extract agent preference. In this work, we provide a new IRL algorithm for the continuous state space setting with unknown transition dynamics by modeling the system using basis of orthonormal functions. Moreover, we provide a proof correctness and formal guarantees on the sample and time complexity of our algorithm. Finally, present synthetic experiments corroborate our theoretical guarantees.
1 Introduction
Reinforcement learning in the context a Markov Decision Process (MDP) aims to produce a policy function such that the discounted accumulated reward of an agent following the given policy is optimal. One difficulty in applying this framework to real world problems that for many tasks of interest, there is obvious reward function to maximize. For example, must account for many different criteria, c.g., avoiding crashing and maintaining adequate speed, and there is not an obvious formula of these variables producing reward which reflects expert behavior 3. The Inverse Reinforcement Learning (IRL) problem consists of having as input an MDP with no reward function along with policy, and the goal is to find reward function that the MDP plus the learned reward function is optimally solved by the given policy. Describing expert behavior in terms of reward function has been shown to provide suceinct, robust, and interpretable representation of expert behavior for purposes of reinforcement learning 3 Furthermore, this representation of agent preference can give insight the preferences goals of agent.
merging onto highway
Despite much work over the years, there still exist major limitations in our understanding of IRL. One major gap is the lack of algorithms for the setting of continuous state space. This setting is of primary importance since many promising applications, such as autonomous vehicles and robotics, occur in continuous setting. Existing algorithms for IRL. in the continuous setting generally do not directly solve the IRL. problem, but instead take a policy matching approach which leads to a less robust description of agent preference []. Finally, there is lack of formal guarantees for IRL methods which make principled understanding of the problem difficult.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

For a comprehensive list of results on the IRL problem, we refer the reader to [3] as we next describe works that are closest ours. Throughout the years, various approaches have been proposed to solve the IRI. problem in the continuous state setting. Aghasadeghi and Bretl [1] used finite set of parametric basis functions to model the policy and reward function for a policy matching approach. Boularias et al. [6] matched the observed policy while maximizing Relative Entropy and applied this method to continuous tasks through discretization. Levine and Koltun [12) maximized the likelihood of the observed policy while representing the reward function as a Gaussian Process. Finn al. 8 modeled the reward function through a neural network to allow for more expressive rewards. Ramponi et al. [88] and Pirotta and Restelli [17] search for optimal reward based on minimizing the gradient of the continuous policy. Metelli et al. [14 selects a reward function over a set of basis functions such that the policy gradient is zero. These previous methods rely heuristic arguments and empirical results to support each approach, but do not provide any theoretical guarantees or the insight that comes with them. Finally, Komanduru and Honorio [[]] and Metelli et al. [5 provided theoretical analysis similar to our work, but only for the finite state space setting.
Contributions. In contrast to the work above, this paper provides a formally guaranteed solution to the IRL problem over continuous state space when transition dynamics of the MDP are unknown. We accomplish this by representing the estimated transition dynamics as an infinite sum of basis functions from 2 + R. Then, under natural conditions on the representations, we prove that linear program can recover a correct reward function. We develop a model of IRL. in the continuous setting using the idea of infinite matrices, which in contrast to the more typical non-parametric functional analysis approach, allow us to derive "explicit, computable, and meaningful error bounds" [20]. We exhibit our main theorem by proving that if the transition functions of the MDP have appropriately bounded partial derivatives, then by representing the transition functions over a trigonometric basis, our algorithm returns a correct reward function with high probability. However, we emphasize that our results apply under a range of appropriate technical conditions and orthonormal bases. To the best of our knowledge, we present the first algorithm for IRL in the continuous setting with formal guarantces on correctness, sample complexity, and computational complexity. The total sample and computational complexity of our algorithm depends on the series representations of the transition dynamics over given basis. However, if given set of transition functions can be represented with sufficiently small error over a given basis by a k matrix of coefficients, then our algorithm (see Algorithm ( returns solution to the IRL problem with probability at least 1 - 8 in O122 log & samples by solving a linear program with (k)) variables and constraints. We show how the magnitude of k needed, i.e., the size of the representation, depends on characteristics of a given IRL problem. This sample complexity matches that of the discrete case algorithm of [I]]. For more detailed complexity results, see Section 4 We experimentally validate our results by testing our IRL algorithm on a problem with random polynomial transition functions. Finally, we show how our algorithm can be efficiently extended the dddiiennional setting.
2 Preliminaries
In this section, we first define the Markov Decision Process (MDP) formalizing the IRL problem. We briefly introduce the Bellman Optimality Equation, which gives necessary and sufficient conditions for a solution to the IRL problem. We then describe the problem of estimating the transition dynamics of the MDP. Finally, we show how represent the Bellman Optimality Criteria for the given MDP in terms of infinite-matriess and infinite-vectors. For now, we restrict our attention to a one dimensional continuous state space.
Definition A Markov Decision Process (MDP) is a 5-tuple
s)))) R) where
. S = [-1, is uncountable set of states]
A is a finite set of actions.
{Pa(''))))ae is a of probability density functions such that Pa(s'Is): S x S R+. Pa (s) represents the transition probability density function from state to state s' when taking action a,
While this paper considers S = 1111, 1..S can easily be generalize to any interval.

---

Y E (0,1) is the discount factor,
S + R is the reward function..
We consider the inverse reinforcement problem. That is, given an MDP without the reward function (MDP) \ R) along with policy : S - A, our goal is determine reward function R such that the policy л is optimal for the MDP under the learned reward function R.
Bellman Optimality Criteria. First we define the value function and Q-function
(50) = [() + R((1) + +
(1)
Q (s.a)= = R(s) + -E(V" 8 Pa('ss).
(2)
Using these terms, present the Bellman Optimality Equation which gives necessary and sufficient conditions for policy क to be optimal for a given MDP [21]
π (s) E arg max (s, VsES. aEA
Estimation Problem. We impose the additional task of estimating the transition dynamics of the MDP. While the policy is assumed to be exactly known, the transition probability density functions are unknown. Instead, we assume that for an arbitrary state 8, we can sample the one-step transition s' ~ Pa (-(ss), as previously done by Komanduru and Honorio [11.
Infinite Matrix Representation. We now introduce a natural assumption on the transition probability density functions, which will make further analysis possible.
Let (0 (0n(s))ne) be a countably infinite set of orthonormal basis functions over S. That is
S (s)dss = 1, and [" ()(
Examples of bases that fulfill the above conditions are the Legendre polynomials, the Chebyshev polynomials, and an appropriately scaled trigonometric basis.
We assume that the transition probability density functions (Pa(s'Is)aase can be represented over the given basis by.
Pa(s'(s)= - Σ o(('') 05(5), 2/00 E..
(4)
In Section 5 we demonstrate sufficient conditions on the transition functions to guarantee that our algorithm is correct when using a trigonometric basis as an example. The following proposition justifies considering only reward functions which are a linear combination of (dn()))nEN)
Proposition 1 If the transition functions can be represented over (x)) nEN as in Equation 4 and there at least one reward function such that the policy is optimal, then there is least one reward function R equal to a linear combination of (én(s) Ien such that the Bellman Optimally criterion fulfilled for the given policy.
(Missing proofs can be found in the Appendix A
This justifies considering only reward functions represented by a series such as,
R(s) Σ (s))(s), E IR.
(5)
The above conditions are equivalent to requiring that the transition function is a linear operator on the function space spanned by the Schauder basis (s)). Proposition I guarantees that if there exists reward which optimally solves the IRL problem, then there is an optial reward in the closure of the function space spanned by { (s))
will useful to identify the coefficients 2/00 and or in Equations and as entries of an infinite- matrix and infinite-vector respectively. This identification allows us to keep all the usual definitions of matrix-mates matriix multiplication, matrix-vecta vector multiplication, matrix transposition, matrix powers, as well as addition and subtraction.
3

---

We define additional simplifying notation. Let the infinite matrix Z(") be defined as the matrix of coefficients associated with Pa (s'ls). Let the infinite vector a correspond coefficients of an arbitrary reward function R. We drop the superscript a and write Z where possible. Let Z] represent the i-truncation of 2. That is, [ 21; = 2, for all i.j I k and [ 21g 0 otherwise. Define the complement of the k-truncation of Z I 2] 2 - 2 Let ((s) be definite-vecter where the n-th entry equals @n(s). Note that in contrast to finite matrices, typical objects, such as matrix products, do not always exist in the infinite matrix case. We add additional conditions on the infinite matrices where necessary to ensure that all needed operations are well-defined. This typically amounts to requiring absolute summability of the reward coefficients a and bounded row -ummabii- of the matrix (()).
We define operations on infinite matrices and vectors follow typical conventions. Let A and be infinite matrices and y be an infinite vector. Then let ||_A|] denote the induced infinity norm defined as |||||| = max;eN Zj=1 Adyl Let the vector E norm be defined as ||||| = Σi=1 (us and the foe norm defined as ||o|o0 = maxieN |os]. Let [A B];; = A.j + Bij. Let the infinite matrix product be defined as [AA]] = Σド= A., Matrix- vector multiplication is defined [Av]; = Σ}= Aij and [v Al, = Σ M.A.g. Matrix transposition is defined as [A lis = Ajt. Define matrix power as the repeated product of matrix, i.e., A' AA...A, times. The outer product of infinite vectors v and is denoted as vu and equals an infinite matrix such that [y ki = 1//41.. These definitions match those of finite matrices and vectors except that the index set countably infinite. For more information on infinite matrices, we refer the reader to (7].
Finally, we can give an infinite matrix analogue to the equations of Ng and Russell 16 to characterize the optimal solutions. We restrict our definition to only strictly optimal policies as motivated by Komanduru and Honorio [1]. For simplicity, we also assign the given optimal policy vs E S, as done in [16] and [Т]. Following the same intuition as in the discrete case, we can represent the expectation of reward function after a sequence of transitions through matrix-matrix and matrix-vector multiplication. Therefore, we can use the following definition to write the difference in Q-functions of the optimal action and any other action under the optimal policy:
x(s) d1.
F(() (Z) - -2(0)
Necessary and sufficient conditions for policy optimality. The following Lemma gives necessary and sufficient conditions for policy π to be strictly optimal for a given MDP of the form described above. The condition is analogous the condition in (16). However, key difference is that entries of the infinite transition matrices represent coefficients of basis functions and not transition probabilities directly. Therefore, our method of proof is necessarily different.
Lemma The given policy x (s) is strictly optimal for the MDP(S, A, (Pa(s)))) 2 (s)) if and only if.
a (Taa) ((s) 00 V VaE
Lemma will a relatively easy to verify sufficient condition on the reward function representation.
wwill be used in Section
4 to prove correctness of our main result, Algorithm 2 as it provides
3 Estimating MDP transition dynamics
As stated in the previous section, we consider the problem where the true transition dynamics of the MDP are unknown. Thus, in this section, we propose an algorithm to estimate the coefficient matrix (a)) and derive high-probability error bounds on the estimated matrices Fla), We denote any estimated matrices with a hat, i.e., (aa) is the estimation of 2(a) and F(a) is derived from 2(a).
Since Algorithm|] iis based on random samples, in our next theorem we show that, with probability at least 1 - 8, Algorithm| I returns an estimate of the true matrix 2(a) with bounded error measured by the induced infinity norm

---

Algorithm EstimateZ
Input: Action A, iteration count n E N, truncation parameter & E N.
1. Sample E I2 such that each s, is independent and 8y Uniform(-1,1)
2. Sample 6' E R such that each sf is independent and 6, Pa(-(8,).
3. Compute (()) Σr ((8,))(s,))
Output: return | ".)("..
Theorem Let Z(0) be the output of Algorithm for inputs (a, n, k), E
and å E (0,1). If
8k
2k
lI 27 & and n z E2
log
then - do I 2E with probability at least 6.
Theorem guarantees an e-approximation of g(a) with probability at least 5 in n E O log ;) samples. he condition that the truncation error is less than & can be guaranteed by properties of the Irue MDP, as we will demonstrate in Section 5 Next, we show how the error in estimating (a) propagates to the error the estimate of infinite matrix F(o).
Lemma 4 for all A, [| 1/00 and || |/ S SA fov then for all A {a1).
|5(()) - Ila S
(1-7A)2"
Lemma matches the intuition that the error of the (F(()) matrices is larger than that of the (2(a) matrices due to the infinite summation (see Equation 6 The propagation of error will be smaller there is lower discount factor or the entries of the matrices {Z(a)) are smaller.
4 The IRL, algorithm
In this section, we present our main algorithm that recovers a strictly optimal reward function with high probability under general conditions the infinite-matrix representations. Particularly, in Theorem 6 we give the precise assumptions on the series representation of the true MDP to guarantee the linear program in Algorithm (erooberrrecrrrr optimal reward function with high probability when using the estimated F(a)
matrices described in Section
Algorithm 2 IontinuousIRL
Input: Discount factor y E (0, 1), interval cover parameter > 0, number samples n N. truncation parameter & E N.
1. Compute (o()) by calling Algorithm with parameters (a, n, k) for each E A.
2. Compute (a)) }, for each o aj by using the (2(m)) in step and Equation 6 1] of [2/c] elements such that for all E [-1, 1], there exists E
3. Compute a set 5 1-1,
such that (s s <
4. Solve the following linear program. Denote this solution by a.
min |alli a. (lo) (b3) > 1, 1, E S AM(i).
Output: return reward function R((s) = Σ (s):
Let [-] denote the ceiling function.
5

---

We now provide an intuitive explanation of Algorithm 2 For fixed reward vector the term a FØ(s) can be regarded function from + R. This function has series representation over the basis functions (s) with coefficients given by the infinite-vector J a. Therefore, the Bellman Optimality criteria can be fulfilled if is chosen so that the coefficients FF a make Fo(() positive over S. However, bounds for the minimum of a function given its series representation are generally not tight enough and tighter approximations require expensive calculations such as solving semi-definite program 13 Instead, we exactly compute Fo(5) for all points in finite covering set S. Using Lipschitz continuity of a Fo(s), we can lower-bound o T Fo(s) over S. Since a T Fo(()) linear in a, linear optimization can be used to ensure the lower bound is positive over S.
ripist Lower bound Pigte
Figure Visualization of Algorithm 2 Here the black line represents a T Fo(s) and the red line lower bound for this function by using the Lipschitz assumption. The blue line is then lower bound for the true Bellman criteria FØ(s) where the distance between the red and blue scales Algorithm finds sparse such that o'' F(() (ss) is positive over S.
with | Fl
We extend the definition of B-separabilltyy given by Komanduru and Honorio to the continuous case in order to provide finite sample guarantees for Algorithm 2 Our experiments indicate that effective in measuring the intrinsic difficulty of given IRL problem.
Definition 2 (8-separability). We say that the IRL problem is 3-separable if there exists reward vector ā such that,
| and TT ((8) 28 0, VsES, a a ((A)(a)
The condition of 3-separability does not reduce the applicability of the algorithm since every IRL problem with strietly optimal solution is 8-separable for some >>> Furthermore, ||o|] is guaranteed to be well-defined, since if there exists such that a F(a) 3 0, then there
exists finite truncation of called ā such that à (T())(()))))))) B' 0.
Next, we provide conditions on the smoothness of the expected optimal reward, estimation error of F(a), and the size of the covering set S so that the minimization problem Algorithm 2 outputs correct solution.
Lemma the IRI. problem is 3-separable, E S. A {ai}, and S C S such that there exists 5 S so 5 s <ffr all then the solution (called &) to the optimization problem
(')())o(s)ll>> S
{ -F & 8-ee for all
minimize, ||a||1
t.t. a T ((aa) ((3)((3) 2
satisfies,
à Fo(s) 0, V
In Figure we provide an intuitive illustration of the correctness of Algorithm which relates to the blue line denoting a F(()((() being positive over S for a given A. First, the difference
Let (s)s) _ (s).

---

between the red and blue line must be small, which corresponds to || Fla))lo Secondly, the piece-wise linear bounds composing the red line must be sufficiently "high". The output will be chosen so that all points on the black curve corresponding to 8 E S will equal at least 1.
We have the necessary components to prove general conditions the infinite matrix repre- sentation under which Algorithm 2 outputs a solution to the IRL problem with high probability.
Theorem 6 If the given MDP without reward function, (MDP) R), is B-separable, B > cp, and for all A, 8 E [-1,1], the following conditions hold:
(1) |F <.
(1i) 10
IA<
1
(iti) 1 (1
3 cp (1
7/4)
2
8 2
83
k2 log 2
max 32, (B-cp) c - AAH4
-0-cpl
then Algorihmmccalled with parameters (7r, c, n. k) returns a correct reward function with probability at least 8 by solving linear program with is variables and O M|Al| constraints.
Remark 6.1 The conditions (i)-(iü) on the infinitemulrix representations of the transition functions given Theorem 6 are natural for many orthonormal bases. We explain the purpose of each condition and how they relate to assumptions on the MDP without reward function (MDP) (R).
The first condition (i) enforces that the Bellman Optimality condition a Fó(s) is p-Lipschitz continuous when ||a||ı = 1. A finite value for p exists over the basis { (8) whenever there is convergent representation of the derivative of expected optimal reward. Intuitively, this means that expected reward of the optimal policy does not change too quickly with slight changes in the starting state.
The second condition (ii) is needed to enforce that the infinite summation which equals F (see Equation 6 converges in the induced infinity norm. Conditions the MDP which enforce this assumption depend on the underlying basis of functions.
Finally, the third condition (iii) is always satisfied by some k N since it is assumed that each transition function has a convergent series representation. Different orthonormal bases provide different guarantees on bounding l given assumptions the transition function. We will show an example such bounds for a trigonometric basis in Section 3
We note that our sample complexity,
n E
k2
log
(8 cp)
matches the complexity of the discrete setting algorithm given by Komanduru and Honorio |I f (()).
when
Fourier instantiation
The conditions (i) (iii) of Theorem 6 were chosen maintain generality while being easily verified by leveraging classic results on orthonormal bases. To illustrate this claim, we prove that Theorem 6 applies class of transition functions over a trigonometic basis by using standard methods of proof for Fourier series. Due to space constraints, we leave the technical derivations to Appendix B and focus on the high-level idea this section. First, we define the basis of trigonometric functions (s))
(s. = cos (In/2] TS) for all odd n, (n(s) = sin ((n/2)Ts) for all even n.

---

Lemma 7 1f Pa(18) Σi.=1 (3) (b) where {dn(s)} are the trigonometric busis func-
tions, 0 < < 24'
E > 0, and
8
Pa(5)
<
05a053
((3)
then
4TA((2)
(i) (FF'ss)ll
(ii 12 A,
(ti) |1x 2| <
((3)
1 with truncation parameter i on the order of lo E O (V where ((r)=Eu no
the Riemann
zeta function.
A classical result Fourier series is that if periodic function f is of class C", then the magnitude of the n-th coefficient of its Fourier series is on the order (1//e). This can be used to bound the entries of (a)) and F(a), Then, known inequalities of the real Riemann Zeta function and its variants can be used guarantee the absolute infinite summations that make up conditions (i)-(iii)
appropriately bounded. An additional condition A < 47 is then sufficient to guarantee Algorithm
2 has simplified sample complexity of O log 1/86) (see Appendix B
6 Experiments
We validate our theoretical results by testing Algorithm| and on randomly generated IRL, problems using polynomial transition function. We give high level results in this section and leave the details of the experiment in Appendix C
The following graphs indicate that the theoretical sample complexity of Algorithm D given by Theorem is correct. We observe that the number of samples n to achieve estimation eтror & is less
than 8
log the theoretically guaranteed sample complexity.
26
Tracratioll Samsine Meaded
Thesneticll Samples Neeced Observed Ope lon Foad Sansiee
Trecretica Cumplen Neaded Observed Epdizo Tood Samples
Obeerved Carllon et Taas Surpple
0:33
0.2
002
30003
300000
50000
Marr of Samieks
NLFVOOT SE
Barber 5amploo
Figure 2: The red line shows the error in estimating the coefficient matrix as I|[* 2 11 versus the number of samples using Algorithm| for truncation parameter k= == 5, k == 15. k = 25. Error bars represent two standard deviations of the observed error. The line 'Theoretical Samples Needed' shows the corresponding sample complexity given by Theorem 3
Next, we verify the sample complexity of Algorithm 2 while varying the representation size controlled by truncation parameter k. We note that the separability parameter / has substantial impact on the sample complexity, as indicated by the complexity result of Theorem We explore this more in Appendix C
test the sample complexity result of Algorithm 2 by varying the truncation parameter k and number of samples for a fixed IRL. problem; that is, the actions, discount factor, and transition functions do not change. By keeping the IRI. problem fixed, we can derive the following simplified relation from the sample complexity of Theorem 6 where C' > 0 is a constant.

---

8
2x |A|
k² log
(3 - ( ( -1)4
8
n
(3 cp) (} -244 (log 24 |A| + log 1 8
83
k2
log 6 k2
C
log 2k A|
The relation log / =
x2 log 21: A| indicates that we expect to see an linear relationship between log 1/8 and n/L². Indeed, observe this relationship for various values of k.
C
5
I k=
+
k=
11
+ k=15
-00
600
1
10
20
30
40 50
60
70
g
Figure 3: This plot shows the linear relationship hetween log 1/a and n/1²2 while varying the truncation parameter k. The error bars show 95% confidence intervals computed via bootstrapping from 240 trials. Other constants: B 26.5, = 0.7, 0.05, A = 1.45, and |A| = 3.
IRL in d-dimensions
In this section, discuss IRI. in the d-dimensional setting, i.e., S 1]1 One obvious way of extending Algorithm 2 to the d-dimensional setting would be to modify Lemma to use f2- Lipschitz continuity a ((s) with an orthonormal basis (s) over [_ Such d-dimensional basis can be constructed by taking the product of 1-dimensional basis functions. This approach has the advantage that it allows for weak assumptions on the d-dimensional transition functions, which only need to satisfy the conditions of Theorem 6 when represented over some basis. However, this would require an exponential increase in the size of the covering set 5 used in Algorithm 2 and number of samples needed if the representativeness of the transition functions in each dimension are not restricted further.
It is unlikely that the general d-dimensional case be handled without exponential scaling in d since this also occurs in the finite state space setting. To see this, notice that if [S] is finite then an IRL problem with state space Sd can be equivalent to any IRL problem on space with [S] states when the transition function on St is arbitrary. Therefore, it necessary to add additional assumptions to reduce the worst-case computational and statistical complexity.
To simplify the d-dimensional setting, make the assumption that the total d-dimensional state space of the MDP can be decomposed as the direct sum of T subspaces of dimension at most such that the total transition function can be written a product of transition functions each of these component subspaces. In other words, we can decompose the state space as follows, S 5(1) e 22) @ ... + S(T) such that dim(St)) S 9. Then, given this decomposition, we require that for all E A, ( = I (1() ( where s(f) denotes the projection of to S(i), If the transition functions of a given MDP satisfy such assumptions, then we can solve the IRL. problem this setting in (T exp(1)) times the computational time of solving the 1-dimensional IRL problem due to the following theorem.

---

Theorem 8 Let decompasition S = S @D.. ( such that S C S, and tim((S()) S Let the transition function operates independently on these components, i.e., Pa(si[su) I1 (s for all a E with 2اا) Projgan (s). If each component IRL problem with transition functions ( A solved by reward R(i), then the total d-dimensional IRL. problem solved by the reward function
represent an (MDP) (R) such that S = [-1, 11d with some
functionn R(s)= = 1 (26())
This assumption is motivated by neurological evidence that human cognition handles the curse-of- dimensionality by decomposing a dingh-dimensioall task into multiple subtasks [9. This assumption was successfully used by Rothkopf and Ballard [19] in their Modular IRL algorithm to represent human navigation preference, implying that reward functions generated under this assumption could be particularly effective at representing human behavior. Further research on the type of assumptions which are empirically justified and allow strong theoretical guarantees d-dimensions would be an interesting future topic of study.
Discussion
We have presented formulation of IRL in the continuous setting by representing the transition functions with infinite-matrices over an orthonormal function basis. We show in Theorem ( that under natural assumptions on the transition funetion representations, Algorithm returns reward function solving the IRL problem with high probability.
Our method of estimating the transition matrices has a sample complexity of O
(p-epp= log }
which is same as the discrete IRL. method in [1] when B = O(1. The computational complexity cp
of Algorithm is dominated by solving a linear program with A variables and O (L constraints. Furthermore, we show how our main theorem, Theorem can be used to guarantee Älgorithm f a class of transition functions when represented over a trigonometric basis. We verify our theoretical results by empirically testing our method on randomly generated IRL problems with polynomial transition functions. Finally, we discuss how our method can be applied in the d-dimensional setting.
In future work, it would useful to better characterize transition functions that appear in applications of IRL. Much like the wavelet basis allows for sparse representations of audio and video, it is possible that particular orthonormal bases would be better suited for certain tasks where IRL is used. Better understanding of transition functions which appear in practice, such as whether bounds on its partial derviatives are justified, paired with more sophisticated results orthonormal bases, such as those given by Izumi and Izumi [TO), could allow for stronger theoretical guarantees in particular domains. Another potential line of future work could be determining which assumptions allow IRL scale efficiently with dimension of the state space, while maintaining effectiveness on practical tasks. While our assumption on the decomposability of d-dimensional transition functions is supported by prior literature on human motor control, it is unclear how limiting this assumption would be for other applications of IRL. Different methods of simplifying IRL. in the continuous d-dimensional setting may provide greater flexibility.
References
[1] Navid Aghasadeghi and Timothy Bretl. Maximum entropy inverse reinforcement learning in continuous state spaces with path integrals. In International Conference on Intelligent Robots and Systems, 2011.
[2] Horst Alzer. On some inequalities for the gamma and psi functions. Mathematics of computation, 66(217):373-38) 1997.
[3] Saurabh Arora and Prashant Doshi. A survey of inverse reinforcement learning: Challenges, methods and progress. ArXiv 1806. 068770 2020.
[4] Needet Batir. New inequalities for the hurwitz zeta function. Proceedings Mathematical Sciences, 2008.
10

---

[5] John J Benedetto and Wojciech Czaja. Integration and modern analysis. Springer, 2009.
[6] Abdeslam Boularias, Jens Kober, and Jan Peters. Relative entropy inverse reinforcement learning. In AISTATS, 2011.
[7] R.G. Cooke. Infinite Matrices and Sequence Spaces. Macmillan, 1950. URL https://books google. google.com/bonno.eoooooooo.ooo wwtp.//bokks.aa-710AAAA.....
[8] Chelsea Finn, Sergey Levine, and Pieter Abbeel. Guided cost learning: Deep inverse optimal control via policy optimization. ICMI,, 2016.
[9] Samuel J Gershman, Bijan Pesaran, and Nathaniel D Daw. Human reinforcement learning subdivides structured action spaces by learning effeecor-speciffe values. Journal of Neuroscience, 29(49):13524-1333 2009.
[10] Masako Izumi and Shin-ichi Izumi. Absolute convergence of fourier series of convolution functions. Journal of Approximation Theory, 1968.
[11] Abi Komanduru and Jean Honorio. On the correctness and sample complexity of inverse reinforcement learning. In NeurlPS, 2019.
[12] Sergey Levine and Vladlen Koltun. Continuous inverse optimal control with locally optimal examples. In ICML, 2012.
[13] Jeremy W McLean and Hugo Woerdeman. Spectral factorizations and sums of squares repre- sentations via semidefinite programming. SIAM journal on matrix analysis and applications. 2002.
[14] Alberto Metelli, Matteo Pirotta, and Marcello Restelli. Compatible reward inverse reinforcement learning. The Thirty-first Annual Conference on Neural Information Processing Systems-NIPS 2017, 2017.
[15] Alberto Maria Metelli, Giorgia Ramponi, Alessandro Concetti, and Marcello Restelli. Provably efficient learning of transferable rewards. In International Conference on Machine Learning, pages 7665-7676. PMLR, 2021.
[16] Andrew Y Ng and Stuart Russell. Algorithms for inverse reinforcement learning, In ICML, 2000.
[17) Matteo Pirotta and Marcello Restelli. Inverse reinforcement learning through policy gradient minimization. In Thirtieth AAAI Conference on Artificial Intelligence, 2016.
[18] Giorgia Ramponi, Amarildo Likmeta, Alberto Maria Metelli, Andrea Tirinzoni, and Marcello Restelli. Truly batch model-free inverse reinforcement learning about multiple intentions. In International Conference on Artificial Intelligence and Statistics, pages 2359-2369. PMLR, 2020.
[19] Constantin A Rothkopf and Dana H Ballard. Modular inverse reinforcement learning for visuomotor behavior. Biological cybernetics, 107(4):477-490, 2013.
[20] PN Shivakumar and KC Sivakumar. A review of infinite matrices and their applications. Linear Algebra and Applications, 430(4):976 998, 2009.
[21] Richard Sutton and Andrew Barto. Reinforcement learning: An introduction. MIT press, 2018.


Reviews:
[{"review_id": "uqfjhLyqQOp", "reviewer": "Reviewer_pRjN", "summary": "This paper offers a theoretical perspective on Inverse Reinforcement Learning in the continuous (state) setting. The main contribution is to show that under some smoothness assumptions, they are able to recover a reward function with high probability. ", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "This paper shows that in the continuous RL setting it is possible to recover a reward function with high probability in a single bounded dimensional state space, with discrete actions, by projecting the transition function (and an \"equivalent\" reward function on a functional basis). While the idea has some interest, its significance is limited for the following reasons.\n\n- The setting is presented as continuous in the title of the paper, which is confusing. Usually, the continuous setting refers to a continuous state and action space rather than a continuous state space. For instance, the authors argue that this setting is of interest for robotics although it is precisely the continuous state action setting that would be of interest.\n\n- A number of assumptions makes the approach impractical e.g. the estimateZ algorithm assumes that we can sample the state space uniformly, the expert policy is know in all states. Which reduces the interest of the paper in its theoretical contribution which itself is on a very contrived setup (one-dimensional state space).\n\n- What is the point of discretizing the problem in Algorithm 2. step 4, where you could discretize it in the very first place (which is fine since transitions as smooth and the projected \"equivalent reward\" function is smooth), to transpose the problem to a discrete state space for which there are existing results.\n\n- The section on adapting the approach to d-dimensional problem is not convincing. Assuming the independence of the transition function is not standard and as such should be verified by empirical evidence. \n\nNitpicks:\n- You assume that we can swap actions to make the policy be constant. While this makes sense when there are no assumption on the structure of the mdp I don't think this is as natural if there are smoothness assumptions on the transitions. The authors could comment on that.\n- r is a very poor choice of temporal subscript in the context of RL\n- l414 -> \"by linearity\" is not an argument  in the context of a mathematical proof\n- Even if mentioned later in the paper, in the proof of prop 1, exchanging an integral and an infinite sum is not trivial, you should mention why it is ok.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4h"}, "extra_text": {}}, {"review_id": "LKpW5Cmhsz9", "reviewer": "Reviewer_aTgp", "summary": "The authors present the first algorithm for IRL in continuous setting with formal guarantees including sample and computational complexity bounds. The theoretical analysis is based on the theory of infinite matrices. The theoretical bounds are corroborated by synthetic experiments. \n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "The ideas of the proofs and setups are extended from [Ng and Russell, 2000] and [Komanduru and Honorio, 2019]. Although the technique used in the proofs -- theory of infinite matrices --  is not new, (the book referred to in the text dated back to 1950), applying it in the IRL context seems novel and inspiring. Furthermore, the algorithm proposed seems to be the first IRL algorithm (i.e. learning reward function given optimal policy and query access to transition function) in continuous setting that has formal guarantees. \n\nThe impact the work can be boarder if the authors discuss a connection to state-of-the-art IRL and model-based RL algorithms and lift the assumptions that not unusually satisfied in practice, such as \n- the demonstration policy is known and is optimal and deterministic\n- the optimal reward is unique and \\beta separable, which can be violated sometimes (see upper left of Page 4 [3])\n- the MDP can be reset to any state \n\nThe paper is very well-written and easy to follow. However, I think there’s still some room for improvement. For example, Eq. (6) is very important, but it lacks explanation and intuition. It would help readers by providing some context beyond mentioning that it’s an analogue to the equations of Ng and Russel.\n\n\n[1] Sun, Wen, et al. \"Provably efficient imitation learning from observation alone.\" International conference on machine learning. PMLR, 2019.\n\n[2] Abbeel, Pieter, and Andrew Y. Ng. \"Exploration and apprenticeship learning in reinforcement learning.\" Proceedings of the 22nd international conference on Machine learning. 2005.\n\n[3] Ng, Andrew Y., and Stuart J. Russell. \"Algorithms for inverse reinforcement learning.\" ICML. Vol. 1. 2000.\n\nOther comments:\n\nI wonder whether the theoretical results in [Komanduru and Honorio, 2019] can be applied to continuous settings simply by discretizing the continuous state space. For example, this is done in Section 5.1 Lipschitz Continuous MDP case study in [1]. \n\nI think this paper is related to a line of research on imitation learning that learns the transition dynamics from demonstration, e.g. [2]. \n\nThis work extends from discrete setting to continuous state space. Is the same technique able to further extend to continuous action space?\n\nOther minor comment:\n\nIn Fig. 1., it seems that the blue curve is a shifted-down version of the red curve. Is this always the case?\n\nIn the caption of Fig. 3 \\beta = 26.5. And in the legend of Fig. 4 in the Appendix C.4., \\beta^{-1} = 26.5. Is there a typo?\n\nThe number of trials in the experiments is missing.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}, {"review_id": "Hq2I0mxc6YG", "reviewer": "Reviewer_MtyF", "summary": "The paper focuses on the theory of inverse reinforcement learning and provides a solution for a bounded continuous space MDP with unknown transition dynamics while maintaining formal guarantees. To this end, the paper proposes to use an infinite sum of orthogonal basis functions to represent the estimated dynamics which allows using a linear program to recover the reward functions. Instead of the standard functional analysis approach, the paper uses the toolset of infinite matrices claiming that it allows them to derive more meaningful error bounds. More practically, they demonstrate that if the transition functions can be represented by truncated matrix of coefficients, a solution to the IRL problem can still be recovered with bounded probability. The derived sample complexity in the continuous state space matches that of the earlier proven discrete case. The paper also provides an efficient extension for $d$-dimensional setting under some assumptions. The paper also performs some simple experiment to evaluate the bounds on randomly generated IRL problems.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "Overall, it's a hard paper for me to judge as I am no expert in the mathematical toolsets used in this paper.\n\n**Strengths**\n\nIRL is a difficult problem in general, and [1,2] showed ways to avoid the problem. But for a lot of tasks we do care about the reward function and not just the policy. This paper is amongst the few that try to carve out a space of MDPs where this reward inference problem can be solved with some guarantees. The paper uses very different math to achieve this which might be useful for other theoreticians in the field to explore.\n\n**Weaknesses**\n\nMajor portion of the results hinges on the specific orthonormal basis function that can be used for representing the transition dynamics and they still don't really work for the $d$ dimensional case except under strong separability of the dimensions which doesn't sound realistic for most problems. Source code would have been immensely useful to better understand how the practical inference of transition dynamics works using this theory to allow setting up the linear program for reward functions. It's hard for me to judge whether results in Fig 2 suggest that the proven bounds are fairly tight or not. \n\n[1]: J Ho and S Ermon. \"Generative Adversarial Imitation Learning\" https://arxiv.org/abs/1606.03476\n\n[2]: J Ho et. al. \"Model-Free Imitation Learning with Policy Optimization\" https://arxiv.org/abs/1605.08478", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "It's a theory paper and it adequately mentions its limitations.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "GK64ohkzYzi", "reviewer": "Reviewer_MeZM", "summary": "The paper studies the IRL problem in the presence of a compact state space and finite actions. Under the assumption that the transition model of the MDP can be represented by means of an (infinite) set of orthogonal basis functions, the authors prove that there always exists a reward function explaining the expert's behavior that can be constructed using the same basis functions. Then, the paper proposes an approach for estimating a reward function endowed with sample complexity guarantees. Synthetic experiments are then provided and the paper concludes with a discussion for the extension to multiple dimensions.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "***Major***\n1. (Related Works) I think that the paper lacks some important related works. First, in line 26, the authors claim that \"Existing algorithms for IRL in the continuous setting generally do 27 not directly solve the IRL problem, but instead take a policy matching approach\". However, there exists a class of IRL methods, called \"Truly-batch model-free\" that actually address the IRL problem with continuous states (and also continuous actions) producing as output a reward function [1, 2]. Second, the authors claim tha  \"there is a lack of formal guarantees for IRL methods\". Very recently, an IRL algorithm with sample complexity analysis has been presented [3]. Third, the idea of using an orthogonal basis in IRL was first introduced by [4]. \n\n2. The authors consider in Definition 1 a state-only reward function. Is the presented approach bounded to that assumption, or can it be extended to reward functions depending on state-action pairs?\n\n3. (Significance of the Theoretical Results) I have some concerns about the significance of the theoretical results about sample complexity presented on the paper, especially about how much the assumptiona are realistic. I will be more precise. \n- Theorem 3. In order to get the concentration result, it is assumed that the complement of the k-truncation of the infinite matrix Z has a norm bounded by \\epsilon. Is this assumption realistic? Isn't Z estimated from samples, so how can it be enforced? It seems to me that this represents just a way of computing a union bound over a finite (k^2) number of entries. Can the authors clarify this point?\n- Lemma 4. This lemma holds under the assumption that the \\infty norm of the infinite matrix \\hat{Z} is bounded by 1/\\gamma? How is this assumption guaranteed in practice, given that \\hat{Z} is estimated? More in general, which is the intuition behind the truncation of the infinite matrix? How is k selected? \n- Lemma 5. Also here, the bounds on the \\infty-norm of matrix \\mathcal{F} as well as the \\infty-norm of the difference between \\mathcal{F}  and \\hat{\\mathcal{F}}. How are they guaranteed to hold?\n\nIn general, I found difficulties in getting convinced on the assumptions used in the presented results and quite abstract. I would greatly appreciate that the authors motivate/justify all the assumptions and show how/when they are satisfied in practice, based on the properties of the problems at hand. The same holds for Section 5. How are the conditions of Lemma 7 guaranteed? Is there a particular class of MDPs in which it is satisfied? \n\n- Theorem 8. The authors show that when considering multiple dimensions, the IRL problem, as presented, becomes tractable when the reward function decomposes linearly over the dimensions. I think this assumption is quite restrictive. Think, for instance, to a two-dimensional gridworld where the goal is to reach a certain goal cell. The sparse reward that assigns +M to the goal cell and 0 elsewhere cannot be decomposed as in Theorem 8. Can the authors elaborate on this point?\n\n\n***Minor***\n- Footnotes should appear after the punctuation sign.\n- Equations (1) and (2). The two expectations are taken wrt different probability distributions. This should be clarified, maybe, introducing proper symbols.\n- Algorithms and plots should appear at the top of the page.\n- Figure 2: number of trials and meaning of the confidence bars missing.\n- Figure 3: the number of runs missing.\n\n\n***Overall***\nI think that the paper provides interesting ideas on a relevant topic (IRL in continuous state spaces). However, I found the results quite abstract and I had trouble understanding how much the assumptions are reasonable and when they are verified in practice. I would greatly appreciate it if the authors reorganize the core of the paper, focusing on clarity. Currently, I opt for a borderline score.\n\n\n[1] Pirotta, Matteo, and Marcello Restelli. \"Inverse reinforcement learning through policy gradient minimization.\" In Thirtieth AAAI Conference on Artificial Intelligence. 2016.\n[2] Ramponi, Giorgia, Amarildo Likmeta, Alberto Maria Metelli, Andrea Tirinzoni, and Marcello Restelli. \"Truly batch model-free inverse reinforcement learning about multiple intentions.\" In International Conference on Artificial Intelligence and Statistics, pp. 2359-2369. PMLR, 2020.\n[3] Metelli, Alberto Maria, Giorgia Ramponi, Alessandro Concetti, and Marcello Restelli. \"Provably Efficient Learning of Transferable Rewards.\" In International Conference on Machine Learning, pp. 7665-7676. PMLR, 2021.\n[4] Metelli, Alberto, Matteo Pirotta, and Marcello Restelli. \"Compatible reward inverse reinforcement learning.\" In The Thirty-first Annual Conference on Neural Information Processing Systems-NIPS 2017. 2017.\n\n***Post Discussion***\nI thank the authors for the detailed feedback. I think that my concerns have been addressed, thus I am raising my score. Regarding the reorganization of the paper, I believe that clarity would benefit from stating all the assumptions of Theorem 6 at the beginning of Section 3 and specify that the ones employed in the intermediate results are a consequence of those.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper is mainly theoretical, thus, I do not foresee any societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper provides an IRL algorithm for control processes with continuous states, discrete controls, and unknown transition dynamics with formal sample/time complexity guarantees. The authors addressed many of the initial concerns raised by the reviewers. The primary remaining ones are: (1) clarity and organization of the work---particularly where the assumptions are introduced; (2) the standardness and practicality of the assumption of a known and strictly optimal expert policy (rather than trajectory samples). The first issue seems possible to resolve in the paper's revision. For the second issue, the reviewers in discussion tended to view the paper as making an important theoretical contribution that could lead to extensions with more realistic/relaxed assumptions or serve as a bridge toward continuous state and control settings. Thus, there is still significant merit to the paper even with these concerns remaining. 

Given all of this, I recommend (weak) acceptance for the paper, but consider it to be the most borderline of the papers I am recommending for acceptance and I am not opposed to papers with stronger proponents being prioritized above it as space limits may require. 

As a minor comment to the authors: I agree with Reviewer pRjN that the paper title could potentially be misleading and suggest revision to "... Continuous State ..."
Decision: Accept (Poster)