Inverse Reinforcement Learning in a Continuous State Space with Formal Guarantees
Year: 2022

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.

heading: 1 Introduction
text: Reinforcement learning in the context of 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 is that for many tasks of interest, there is no obvious reward function to maximize. For example, a car merging onto a highway must account for many different criteria, e.g., avoiding crashing and maintaining adequate speed, and there is not an obvious formula of these variables producing a 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 a policy, and the goal is to find a reward function so that the MDP plus the learned reward function is optimally solved by the given policy. Describing expert behavior in terms of a reward function has been shown to provide a succinct, robust, and interpretable representation of expert behavior for purposes of reinforcement learning [3]. Furthermore, this representation of agent preference can give insight on the preferences or goals of an agent.
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 a 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 [3]. Finally, there is a lack of formal guarantees for IRL methods which make principled understanding of the problem difficult.
35th Conference on Neural Information Processing Systems (NeurIPS 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 to ours. Throughout the years, various approaches have been proposed to solve the IRL problem in the continuous state setting. Aghasadeghi and Bretl [1] used a 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 et al. [8] modeled the reward function through a neural network to allow for more expressive rewards. Ramponi et al. [18] and Pirotta and Restelli [17] search for an 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 on 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 [11] and Metelli et al. [15] 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 a 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 R2 → R. Then, under natural conditions on the representations, we prove that a 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 guarantees 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 a given basis. However, if a given set of transition functions can be represented with sufficiently small error over a given basis by a k × k matrix of coefficients, then our algorithm (see Algorithm 2) returns a solution to the IRL problem with probability at least 1− δ in O(k2 log kδ ) samples by solving a linear program with O(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 [11]. 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 to the d-dimensional setting.

heading: 2 Preliminaries
text: 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 to represent the Bellman Optimality Criteria for the given MDP in terms of infinite-matrices and infinite-vectors. For now, we restrict our attention to a one dimensional continuous state space.
Definition 1 A Markov Decision Process (MDP) is a 5-tuple (S,A, {Pa(s′|s)}a∈A, γ, R) where
• S = [−1, 1] is an uncountable set of states1,
• A is a finite set of actions ,
• {Pa(s′|s)}a∈A is a set of probability density functions such that Pa(s′|s) : S × S → R+. Pa(s
′|s) represents the transition probability density function from state s to state s′ when taking action a,
1While this paper considers S = [−1, 1], S can easily be generalize to any interval.
• γ ∈ [0, 1) is the discount factor,
• R : 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 a policy π : S → A, our goal is to determine a 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
V π(s0) = E[R(s0) + γR(s1) + γ2R(s2) + ...|π], (1) Qπ(s, a) = R(s) + γE[V π(s′)], s′ ∼ Pa(s′|s). (2)
Using these terms, we present the Bellman Optimality Equation which gives necessary and sufficient conditions for policy π to be optimal for a given MDP [21].
π(s) ∈ arg max a∈A Qπ(s, a), ∀ s ∈ S. (3)
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 {Pa(s′|s)}a∈A are unknown. Instead, we assume that for an arbitrary state s, we can sample the one-step transition s′ ∼ Pa(·|s), 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 {φn(s)}n∈N be a countably infinite set of orthonormal basis functions over S. That is∫ 1 −1 φ2n(s)ds = 1, and ∫ 1 −1 φi(s)φj(s)ds = 0, ∀ i 6= j.
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′|s)}a∈A can be represented over the given basis by,
Pa(s ′|s) = ∞∑ i,j=1 φi(s ′)Z(a)ij φj(s), Z (a) ij ∈ R. (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 {φn(s)}n∈N.
Proposition 1 If the transition functions can be represented over {φn(s)}n∈N as in Equation 4 and there is a at least one reward function such that the policy is optimal, then there is at least one reward function R equal to a linear combination of {φn(s)}n∈N such that the Bellman Optimally criterion is 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) = ∞∑ k=1 αkφk(s), αk ∈ R. (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 {φn(s)}. Proposition 1 guarantees that if there exists a reward which optimally solves the IRL problem, then there is an optimal reward in the closure of the function space spanned by {φn(s)}n∈N.
It will be useful to identify the coefficients Z(a)ij and αk in Equations 4 and 5 as entries of an infinitematrix and infinite-vector respectively. This identification allows us to keep all the usual definitions of matrix-matrix multiplication, matrix-vector multiplication, matrix transposition, matrix powers, as well as addition and subtraction.
We define additional simplifying notation. Let the infinite matrix Z(a) be defined as the matrix of coefficients associated with Pa(s′|s). Let the infinite vector α correspond to coefficients of an arbitrary reward function R. We drop the superscript a and write Z where possible. Let [kZ] represent the k-truncation of Z . That is, [kZ]ij = Zij for all i, j ≤ k, and [kZ]ij = 0 otherwise. Define the complement of the k-truncation of Z as [∞k Z] = Z − [kZ]. Let φ(s) be an infinite-vector 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 α and bounded row absolute-summability of the matrix Z(a). We define operations on infinite matrices and vectors to follow typical conventions. Let A and B be infinite matrices and ν be an infinite vector. Then let ‖A‖∞ denote the induced infinity norm defined as ‖A‖∞ = maxi∈N ∑∞ j=1 |Aij |. Let the vector `1-norm be defined as ‖ν‖1 = ∑∞ i=1 |νi| and the `∞- norm defined as ‖ν‖∞ = maxi∈N |νi|. Let [A+B]ij = Aij +Bij . Let the infinite matrix product be defined as [AB]ik = ∑∞ j=1AijBjk. Matrix-vector multiplication is defined as [Aν]i = ∑∞ j=1Aijνj
and [ν>A]j = ∑∞ i=1 νiAij . Matrix transposition is defined as [A>]ij = Aji. Define matrix power as the repeated product of a matrix, i.e., Ar = AA...A, r times. The outer product of infinite vectors ν and µ is denoted as νµ> and equals an infinite matrix such that [νµ>]ij = νiµj . These definitions match those of finite matrices and vectors except that the index set is 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 [11]. For simplicity, we also assign the given optimal policy π as π(s) ≡ a1, ∀s ∈ S, as done in [16] and [11]. Following the same intuition as in the discrete case, we can represent the expectation of a 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:
F (a) = ∞∑ r=0 γr(Z(a1))r(Z(a1) −Z(a)). (6)
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 to the condition in [16]. However, a 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 2 The given policy π(s) is strictly optimal for the MDP(S,A, {Pa(s′|s)}a∈A, γ, R =∑∞ n=1 αnφn(s)) if and only if,
α>F (a)φ(s) > 0, ∀s ∈ S, ∀ a ∈ A \ {a1}.
Lemma 2 will be used in Section 4 to prove correctness of our main result, Algorithm 2, as it provides a relatively easy to verify sufficient condition on the reward function representation.

heading: 3 Estimating MDP transition dynamics
text: 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 Z(a) and derive high-probability error bounds on the estimated matrices F̂ (a). We denote any estimated matrices with a hat, i.e., Ẑ(a) is the estimation of Z(a) and F̂ (a) is derived from Ẑ(a). Since Algorithm 1 is based on random samples, in our next theorem we show that, with probability at least 1− δ, Algorithm 1 returns an estimate of the true matrix Z(a) with bounded error measured by the induced infinity norm.
Algorithm 1 EstimateZ Input: Action a ∈ A, iteration count n ∈ N, truncation parameter k ∈ N. 1. Sample s̄ ∈ Rn such that each s̄r is independent and s̄r ∼ Uniform(−1, 1). 2. Sample s′ ∈ Rn such that each s′r is independent and s′r ∼ Pa(·|s̄r). 3. Compute Ẑ(a) = 2n ∑n r=1 φ(s ′ r)φ(s̄r) >.
Output: return [kẐ(a)].
Theorem 3 Let Ẑ(a) be the output of Algorithm 1 for inputs (a, n, k), ε > 0, and δ ∈ (0, 1). If
‖[∞k Z](a)‖∞ ≤ ε and n ≥ 8k2
ε2 log
2k2
δ ,
then ‖Ẑ(a) −Z(a)‖∞ ≤ 2ε with probability at least 1− δ.
Theorem 3 guarantees an ε-approximation of Z(a) with probability at least 1− δ in n ∈ O(k 2
ε2 log k δ )
samples. The condition that the truncation error is less than ε can be guaranteed by properties of the true MDP, as we will demonstrate in Section 5. Next, we show how the error in estimating Z(a) propagates to the error in the estimate of infinite matrix F (a).
Lemma 4 If for all a ∈ A, ‖Ẑ(a) − Z(a)‖∞ ≤ ε and ‖Z(a)‖∞, ‖Ẑ(a)‖∞ ≤ ∆ < 1γ , then for all a ∈ A \ {a1},
‖F̂ (a) −F (a)‖∞ ≤ 2ε
(1− γ∆)2 .
Lemma 4 matches the intuition that the error of the {F (a)} matrices is larger than that of the {Z(a)} matrices due to the infinite summation (see Equation 6). The propagation of error will be smaller if there is a lower discount factor or the entries of the matrices {Z(a)} are smaller.

heading: 4 The IRL algorithm
text: In this section, we present our main algorithm that recovers a strictly optimal reward function with high probability under general conditions on 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 2 recovers an optimal reward function with high probability when using the estimated F̂ (a) matrices described in Section 3.
Algorithm 2 ContinuousIRL Input: Discount factor γ ∈ (0, 1), interval cover parameter c > 0, number of samples n ∈ N, truncation parameter k ∈ N. 1. Compute {Ẑ(a)} by calling Algorithm 1 with parameters (a, n, k) for each a ∈ A. 2. Compute {F̂ (a)}, for each a 6= a1 by using the {Ẑ(a)} in step 1 and Equation 6. 3. Compute a set S̄ ⊂ [−1, 1] of d2/ce elements such that for all s ∈ [−1, 1], there exists s̄ ∈ S̄ such that |s− s̄| ≤ c.2 4. Solve the following linear program. Denote this solution by α̂.
min α ‖α‖1 s. t. α>F̂ (a)φ(s̄) ≥ 1,∀s̄ ∈ S̄, a ∈ A\{a1}.
Output: return reward function R̂(s) = ∑k i=1 α̂iφi(s).
2Let d·e denote the ceiling function.
We now provide an intuitive explanation of Algorithm 2. For a fixed reward vector α, the term α>Fφ(s) can be regarded as a function from S → R. This function has a series representation over the basis functions {φn(s)}n∈N with coefficients given by the infinite-vector F>α. Therefore, the Bellman Optimality criteria can be fulfilled if α is chosen so that the coefficientsF>αmake α>Fφ(s) 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 a semi-definite program [13]. Instead, we exactly compute F̂φ(s̄) for all points in a finite covering set S̄. Using Lipschitz continuity of α>F̂φ(s), we can lower-bound α>F̂φ(s) over S. Since α>F̂φ(s̄) is linear in α, linear optimization can be used to ensure the lower bound is positive over S.
We extend the definition of β-separability given by Komanduru and Honorio [11] to the continuous case in order to provide finite sample guarantees for Algorithm 2. Our experiments indicate that β is effective in measuring the intrinsic difficulty of a given IRL problem.
Definition 2 (β-separability). We say that the IRL problem is β-separable if there exists a reward vector ᾱ such that,
‖ᾱ‖1 = 1, and ᾱ>F (a)φ(s) ≥ β > 0, ∀ s ∈ S, a ∈ A \ {a1}.
The condition of β-separability does not reduce the applicability of the algorithm since every IRL problem with a strictly optimal solution ᾱ is β-separable for some β > 0. Furthermore, ‖ᾱ‖1 is guaranteed to be well-defined, since if there exists α such that α>F (a)φ(s) ≥ β > 0, then there exists a finite truncation of α called ᾱ such that ᾱ>F (a)φ(s) ≥ β′ > 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 in Algorithm 2 outputs a correct solution.
Lemma 5 If the IRL problem is β-separable, ‖F (a)φ′(s)‖∞ ≤ ρ,3 ‖F̂ (a) −F (a)‖∞ ≤ β−cρ2 for all s ∈ S, a ∈ A \ {a1}, and S̄ ⊂ S such that there exists s̄ ∈ S̄ so |s̄− s| < c for all s ∈ S, then the solution (called α̂) to the optimization problem
minimizeα ‖α‖1 s. t. α>F̂ (a)φ(s̄) ≥ 1
satisfies, α̂>Fφ(s) > 0, ∀ s ∈ S.
In Figure 1, we provide an intuitive illustration of the correctness of Algorithm 2, which relates to the blue line denoting α>F (a)φ(s) being positive over S for a given a ∈ A. First, the difference
3Let φ′n(s) = ddsφn(s).
between the red and blue line must be small, which corresponds to ‖F̂ (a) −F (a)‖∞. 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 s̄ ∈ S̄ will equal at least 1. We now have the necessary components to prove general conditions on the infinite matrix representation 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 β-separable, β > cρ, and for all a ∈ A, s ∈ [−1, 1], the following conditions hold:
(i) ‖F (a)φ′(s)‖∞ < ρ, (ii) ‖Z(a)‖∞ ≤ ∆ < 1
2γ , (iii) ‖[∞k Z](a)‖∞ ≤ β − cρ 8
( 1
2 − γ∆
)2 ,
n ≥ max { 32, 83
(β − cρ)2( 12 − γ∆)4
} k2 log
2k2|A| δ ,
then Algorithm 2 called with parameters (γ, c, n, k) returns a correct reward function with probability at least 1− δ by solving a linear program with k variables and O(k|A|c ) constraints.
Remark 6.1 The conditions (i)-(iii) on the infinite-matrix representations of the transition functions given in 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 α>Fφ(s) is ρ-Lipschitz continuous when ‖α‖1 = 1. A finite value for ρ exists over the basis {φn(s)}n∈N whenever there is a 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 on 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 k given assumptions on the transition function. We will show an example of such bounds for a trigonometric basis in Section 5.
We note that our sample complexity, n ∈ O (
1
(β − cρ)2 k2 log
k
δ
) ,
matches the complexity of the discrete setting algorithm given by Komanduru and Honorio [11] when β cρ = O(1).

heading: 5 Fourier instantiation
text: The conditions (i) - (iii) of Theorem 6 were chosen to maintain generality while being easily verified by leveraging classic results on orthonormal bases. To illustrate this claim, we prove that Theorem 6 applies to a 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 in this section. First, we define the basis of trigonometric functions {φn(s)} as
φn(s) = cos (bn/2cπs) for all odd n, φn(s) = sin ((n/2)πs) for all even n.
Lemma 7 If Pa(s̃|s) = ∑∞ i,j=1 φi(s̃)Z (a) ij φj(s) where {φn(s)} are the trigonometric basis functions, 0 < ∆ < 12γ , ε > 0, and ∣∣∣∣ ∂6∂s̃3∂s3Pa(s̃|s) ∣∣∣∣ < π6∆ζ(3) ,
then
(i) ‖Fφ′(s)‖∞ < 4π∆ζ(2)
ζ(3) , (ii) ‖Z‖∞ < ∆, (iii) ‖[∞k Z]‖∞ < ε,
with truncation parameter k on the order of k ∈ O (√
∆ ε
) , where ζ(r) = ∑∞ n=1 1 nr is the Riemann
zeta function.
A classical result on Fourier series is that if a periodic function f is of class Cp, then the magnitude of the n-th coefficient of its Fourier series is on the order of O(1/np). This can be used to bound the entries of Z(a) and F (a). Then, known inequalities of the real Riemann Zeta function and its variants can be used to guarantee the absolute infinite summations that make up conditions (i)-(iii) are appropriately bounded. An additional condition of ∆ < 14γ is then sufficient to guarantee Algorithm 2 has a simplified sample complexity of O(β−3 log 1/βδ) (see Appendix B).

heading: 6 Experiments
text: We validate our theoretical results by testing Algorithm 1 and 2 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 1 given by Theorem 3 is correct. We observe that the number of samples n to achieve estimation error ε is less than 8k 2
ε2 log 2k2 δ , the theoretically guaranteed sample complexity.
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 a substantial impact on the sample complexity, as indicated by the complexity result of Theorem 6. We explore this more in Appendix C.
We test the sample complexity result of Algorithm 2 by varying the truncation parameter k and number of samples n for a fixed IRL problem; that is, the actions, discount factor, and transition functions do not change. By keeping the IRL problem fixed, we can derive the following simplified relation from the sample complexity of Theorem 6 where C > 0 is a constant.
n = 83
(β − cρ)2( 12 − γ∆)4 k2 log
2k2|A| δ
⇐⇒ n k2 = 83 (β − cρ)2( 12 − γ∆)4 (log 2k2|A|+ log 1 δ )
⇐⇒ log 1 δ = C n k2 − log 2k2|A|
The relation log 1δ = C n k2 − log 2k 2|A| indicates that we expect to see an linear relationship between log 1/δ and n/k2. Indeed, we observe this relationship for various values of k.
7 IRL in d-dimensions
In this section, we discuss IRL in the d-dimensional setting, i.e., S = [−1, 1]d. One obvious way of extending Algorithm 2 to the d-dimensional setting would be to modify Lemma 5 to use `2- Lipschitz continuity of α>F (a)φ(s) with an orthonormal basis {φn(s)}n∈N over [−1, 1]d. Such a 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 S̄ 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 a space with |S|d states when the transition function on Sd is arbitrary. Therefore, it is necessary to add additional assumptions to reduce the worst-case computational and statistical complexity.
To simplify the d-dimensional setting, we 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 q such that the total transition function can be written as a product of transition functions on each of these component subspaces. In other words, we can decompose the state space as follows, S = S(1) ⊕ S(2) ⊕ ...⊕ S(T ) such that dim(S(j)) ≤ q. Then, given this decomposition, we require that for all a ∈ A, Pa(s1|s0) = ∏T j=1 Pa(s (j) 1 |s (j) 0 ), where s
(j) denotes the projection of s to S(j). If the transition functions of a given MDP satisfy such assumptions, then we can solve the IRL problem in this setting in O(T exp(q)) times the computational time of solving the 1-dimensional IRL problem due to the following theorem.
Theorem 8 Let (S,A, {Pa(s1|s0)}, γ) represent an (MDP \R) such that S = [−1, 1]d with some decomposition S = S(1)⊕S(2)⊕...⊕S(T ) such that S(i) ⊂ S, and dim(S(i)) ≤ q. Let the transition function operates independently on these components, i.e., Pa(s1|s0) = ∏T j=1 Pa(s (j) 1 |s (j) 0 ) for all a ∈ A with s(j) = ProjS(j)(s). If each component IRL problem with transition functions {Pa(s(j)1 |s (j) 0 )}a∈A is solved by reward R(j), then the total d-dimensional IRL problem is solved by
the reward function R(s) = ∑T j=1R (j)(s(j)).
This assumption is motivated by neurological evidence that human cognition handles the curse-ofdimensionality by decomposing a high-dimensional 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 in d-dimensions would be an interesting future topic of study.

heading: 8 Discussion
text: We have presented a formulation of IRL in the continuous setting by representing the transition functions with infinite-matrices over an orthonormal function basis. We show in Theorem 6 that under natural assumptions on the transition function representations, Algorithm 2 returns a reward function solving the IRL problem with high probability.
Our method of estimating the transition matrices has a sample complexity of O ( k2
(β−cρ)2 log k δ
) ,
which is same as the discrete IRL method in [11] when βcρ = O(1). The computational complexity of Algorithm 2 is dominated by solving a linear program with k variables and O(k|A|c ) constraints. Furthermore, we show how our main theorem, Theorem 6, can be used to guarantee Algorithm 2 for 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 on orthonormal bases, such as those given by Izumi and Izumi [10], could allow for stronger theoretical guarantees in particular domains. Another potential line of future work could be determining which assumptions allow IRL to 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.

Review summaries:
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.

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.

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.