Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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.

**Strengths**

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

**Weaknesses**

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

[1]: J Ho and S Ermon. "Generative Adversarial Imitation Learning" https://arxiv.org/abs/1606.03476

[2]: J Ho et. al. "Model-Free Imitation Learning with Policy Optimization" https://arxiv.org/abs/1605.08478
limitations_and_societal_impact: It's a theory paper and it adequately mentions its limitations.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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. 
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.

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

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

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

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

Nitpicks:
- 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.
- r is a very poor choice of temporal subscript in the context of RL
- l414 -> "by linearity" is not an argument  in the context of a mathematical proof
- 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.
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
main_review: ***Major***
1. (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]. 

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

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

In 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? 

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


***Minor***
- Footnotes should appear after the punctuation sign.
- Equations (1) and (2). The two expectations are taken wrt different probability distributions. This should be clarified, maybe, introducing proper symbols.
- Algorithms and plots should appear at the top of the page.
- Figure 2: number of trials and meaning of the confidence bars missing.
- Figure 3: the number of runs missing.


***Overall***
I 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.


[1] Pirotta, Matteo, and Marcello Restelli. "Inverse reinforcement learning through policy gradient minimization." In Thirtieth AAAI Conference on Artificial Intelligence. 2016.
[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.
[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.
[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.

***Post Discussion***
I 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.
limitations_and_societal_impact: The paper is mainly theoretical, thus, I do not foresee any societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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. 

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. 

The 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 
- the demonstration policy is known and is optimal and deterministic
- the optimal reward is unique and \beta separable, which can be violated sometimes (see upper left of Page 4 [3])
- the MDP can be reset to any state 

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


[1] Sun, Wen, et al. "Provably efficient imitation learning from observation alone." International conference on machine learning. PMLR, 2019.

[2] Abbeel, Pieter, and Andrew Y. Ng. "Exploration and apprenticeship learning in reinforcement learning." Proceedings of the 22nd international conference on Machine learning. 2005.

[3] Ng, Andrew Y., and Stuart J. Russell. "Algorithms for inverse reinforcement learning." ICML. Vol. 1. 2000.

Other comments:

I 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]. 

I think this paper is related to a line of research on imitation learning that learns the transition dynamics from demonstration, e.g. [2]. 

This work extends from discrete setting to continuous state space. Is the same technique able to further extend to continuous action space?

Other minor comment:

In Fig. 1., it seems that the blue curve is a shifted-down version of the red curve. Is this always the case?

In 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?

The number of trials in the experiments is missing.

limitations_and_societal_impact: yes
review_title: null

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)