Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper proposed an imitation learning algorithm to handle both online and offline setting. First, an intractable convex problem is obtained by relaxing the primal problem. After that, the saddle point problem is derived by applying Lagrangian decomposition. Finally, the authors provided an practical algorithm based on the problem, named PPIQ-Learn. For the policy evaluation, PPIQ-Learn uses a convex and smooth objective over both cost and Q-value function. In addition, the theoretical analyses support the performance guarantee. Finally, the provided experiments show that the proposed algorithm outperforms baselines.
strengths_and_weaknesses: Strengths:

Theoretical analyses support the performance of the proposed algorithm.

The proposed algorithm shows convincing empirical results.

It can be applied to both online and offline imitation learning problem

Weakness:

The novelty of this work is not clear – IQ-Learn also uses a single convex objective to evaluate the policy and handles both online and offline setting.


questions: I enjoyed reading this paper, but I seem to have missed the main contribution of this paper (especially, compared to the IQ-Learn). It would be very helpful to understand if the authors clarify the following questions.

- I'm not sure why PPIQ-Learn shows better performance than IQ-learn. Would you explain the main contribution (or intuitive explanation) of PPIQ-Learn compared to IQ-Learn?
- Is there any reason to choose D to measure the distance between $\lambda$ and $\lambda’$? In addition, why the authors use fixed $\eta$ instead of optimizing $\eta$?
- The definition of $H$ is different from that of simple KL-divergence – sample $(s,a)$ from $d$ and measure the log-ratio between $\pi_d$ and $\pi_{d’}$ instead of the log-ratio between $d$ and $d’$. Is there any reason or justification?
- Why authors use only 2 MuJoCo domains (Ant and HalfCheetah) out of 4 domains used in IQ-Learn?
- I am curious about the feature matrix used in the actual experiments. Would you explain about the choice of feature matrix?
- Is it difficult to simply combine PPM and IQ-Learn? If so, what is the problem? If not, what are the advantages of PPIQ-Learn over such simple combining?

limitations: Yes
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: Based on the proximal point method, this paper propose a new algorithm to solve the minimax formulation of the imitation learning problem, which avoids the nested policy evaluation and cost updates. Based on the assumption of linearly parametrized cost classes, the paper further provides a theoretical analysis for the required number of expert transitions, trajectories and number of concave maximization problems to solve. Finally the paper provides an empirical study on several RL environments with both linear and non-linear function approximations.
strengths_and_weaknesses: Stengths:
- Detailed introduction to related work and background.
- Good writing and presentation quality.
- Solid math derivations.

Comments, Questions & Limitations:
- The motivation / key challenge to solve in this paper is not clear to me. It seems the derivations based on proximal point method may lead to a new algorithm for imitation learning, but what are the unique advantages (especially in terms of practical applications) of the proposed approach and what are the limitations of previous works this work has solved?
- I understand that the resulting algorithm avoids nested optimization / alternating updates. But this does not seem to be a unique feature of the proposed method and many previous IL methods also enjoy that property.
- The theoretical analysis is for linear functions, which may be restrictive. Moreover, I do not see particular insights from the theoretical analysis. If the main take-away message is the estimation error can be made arbitrarily small by increasing the number of expert transitions or computational resources in general, that is not very exciting. Is the sample complexity bound state-of-the-art, and is the bounds meaningful in practice (for example $\epsilon^{-5}$ sample transitions may be too large to be useful in practice)?
- The policy update step $\pi_k \propto \pi_{k-1} e^{- \alpha Q_{\theta_k}}$ seems to be something like density ratio correction of previous policy. Can you elaborate more on that part, and in particular the intuitions?
- From figure 2, the final performance of PPM and IQLearn seems similar in most cases, but PPM is indeed more sample efficient than other methods.
questions: See "Strengths And Weaknesses" Section.
limitations: See "Strengths And Weaknesses" Section. No potential negative societal impact.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper presents a novel method for imitation learning that is based on the LP formulation for MDPs. More precisely, the method uses the recently repopularized technique of splitting the occupancy measures to also obtain the Q-function as Lagrangian multiplier, and optimizes this program using a proximal point method with the regularizers used by Q-REPS. The resulting algorithm is similar to the state-of-art IQ-Learn algorithm and differs primarily by using a "logistic Bellman evaluation" objective for optimizing the Q-function (and jointly the reward function).
The paper provides a thorough theoretical analysis in the linear MDP setting (transition matrix and rewards are linear for given features), bounding the suboptimality depending on the evaluation/estimation errors (except for the policy improvements which are assumed optimal), and evaluates the methind in tabular settings, for offline imitation learning, and for continous control problems, where it performs overall better than IQ-Learn.
strengths_and_weaknesses: ## Originality
Imitation learning based on the LP formulation was already introduced in the classical work by Syed & Schapire (2007) (MWAL). However, the proposed algorithm, significantly deviates from MWAL, mainly by building on the recent advances by Bas-Serrano & Neu (2020) to derive a bi-linear saddle point problem that contains the Q-function as Lagrangian multiplier, and by orientating algorithmically on the state-of-art IQ-Learn algorithm by Garg et al. (2021). The resulting work is clearly novel, both algorithmically as well as theoretically.
 
## Quality
The derivation of the algorithm is presented clearly and I checked the proofs up to proposition 3. That is, I did not check the proofs related to the "biased stochastic gradient estimates" and the theoretical bounds, which are quite involved and not in my field of expertise. However, I have no reason to believe that they are of worse quality compared to the rest of the work.

The empirical analysis is good by including tabular settings where the assumptions can be met, as well as continuous settings, where the practical competitiveness could be demonstrated. However, the latter could be improved by adding more experiments on different environments.

It would be very interesting to evaluate the learned reward function, by--after convergence--discarding the Q-function and policy, and learning a new policy from scratch from the learned reward function. Would the reward succeed in inducing a good policy? Would it even transfer better, compared to Q-function/policy with respect to changes in the dynamics?


## Clarity
I like the presentation of the paper a lot. There is a nice flow starting from the imitation learning objective Eq. 1 in the background section (Section 2) to the presentation of the saddle point problem and the PPM update equations in Section 4, which are the basis of the proposed algorithm. Only the discussion of the "Q-convex" dual (cf. Proposition 2) breaks the flow a bit. I wonder, why the authors chose to discuss the dual formulation at this place. The path "(Primal) -> (Primal') -> (Dual')" would seem more logically to me than "(Primal) -> (Dual) -> (Primal')".

The paper ends quite abruptly after briefly describing the experimental settings and results. I think the paper would be better structured by adding a conclusion for reflecting on the main insights (LP formulation can be used for competitive IL algorithm with nice properties such as joint reward-cost optimization and logistic Bellman errors) and for discussion the limitations of the current work (limited  evaluation in challenging environments).

I also think that the gradient estimates (6), (7) could be presented better. Or actually, I wonder, if the equations of the gradients need to be shown in the main document at all. I briefly looked into the code (thanks for submitting it!) and it seems like the gradients a computed by backpropagating through a different objective than Eq. 5. Would it be possible to state the objective that is used computing the gradients and refer to the appendix for showing that these gradients are biased estimates of the gradients of (5)?

The projections in Algorithm 1, should be briefly discussed in the text.

To save some space for additional discussions, I would consider integrating section 5 in section 4 (only briefly stating the theoretical results / theorems) and maybe removing the discussion of the dual in section 3 (at the cost of slightly extending the introduction to Eq. 2 in Section 4).

## Significance
I found the paper very interesting both from a theoretical and practical perspective, and believe that also many other researchers in the field of imitation learning could be inspired by the work.

## Minor
Line 706: The most important merits of the primal-dual algorithm [...] I wouldn't use "merits" for describing bad properties.

questions: 1. Compared to IQ-Learn, the proposed method explicitly learns a reward function. Intuitively, I would expect the parametric form of the reward function to perform better than the implicit form (referring to the way IQ-Learn recovers it from Q and Value function). I was a bit suprised, that the paper does not discuss the use of the reward function, given that one of the main algorithmic properties is that an explicit reward function is learned along with Q function. Why? 

2. How are the gradients estimated in the deep learning setting?
limitations: The paper states the theoretical assumptions, but overall the limitations should be better discussed.
review_title: null

Meta-review: metareview: It was agreed among the reviewers and AC that the paper should be accepted. Hope the authors will address the remaining comments from the reviews in preparing the final version of the paper. 
confidence: Certain
Decision: Accept