Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: This paper investigates the theoretical support for Generative Adversarial Imitation Learning (GAIL).   Specifically, two main points are shown: (1) For general reward parameterization, the generalization of GAIL can be guaranteed, as long as the class of the reward functions is properly controlled; (2) When the reward is parameterized as a reproducing kernel function, GAIL can be efficiently solved by stochastic first order optimization algorithms. 

Numerical experiments are provided on three classic continuous control tasks. RL algorithms are generally questioned in terms of reproducibility. Does the variance of different runs have an impact on the validation of the proposed theory?
review_title: Official Blind Review #3

final_score: rating: 6: Weak Accept
review_content: The submission provides theoretical analysis of GAIL regarding its generalization and convergence properties.
The first part establishes a probabilistic upper bound on the change of the worst-case regret (over the possible reward function) when shifting from the empirical expectation of the expect reward to the true expectation.
The second part considers the convergence properties of GAIL when alternating mini-batch stochastic gradient updates on the policy and discriminator. This section shows that number of iterations required to achieve a "sub-stationarity" J < epsilon is in O(1/epsilon). The proof assumes (vanilla) policy gradient updates, and seems to be further restricted to linear discriminators with bounded weights.
Experiments on Acrobot, Hopper and MountainCar compare learning curves for a 3-layer neural network reward function, and linear reward functions. The linear reward function uses the neural network architecture but does not optimize the first two layers (and is thus linear in random features). Furthermore--for the linear reward function--single gradient updates are compared with 10 gradient updates per iteration. The experiments indicate that single updates perform similar to 10 updates and that the linear reward function converges more stable than the neural network. The neural network, however, can achieve slightly better performance on the considered problems. These results are consistent with the provided theory.

Contribution/Significance:
I think that the theoretical properties of GAIL and related adversarial IL and IRL methods are not yet sufficiently understood. Both achieving stable convergence and generalization from limited number of trajectories can be difficult in practice, so there is high interest in theoretic analysis of these methods. I am not aware of similar analysis of GAIL.

Soundness:
I did not have the time to fully verify the proofs, so I only skimmed the appendix and focused on the proof sketches in the actual manuscript. The assumptions seem reasonable and I could not find errors in the proof sketches. I am having some problems with the proof sketch of Theorem 1. I am not sure about the meaning of $\mathbb{E} \phi(s')$ at the last line of page 4, which is unfortunately not rigorously defined. I assume the expectation is with respect to the sampled blocks. So wouldn't this term be a functional of r? However, I assume the supremum is only w.r.t. the first term (what would be a supremum over an inequality anyway?). Also it seems like the term could be subtracted from both sides of the inequality. Some hints would be highly appreciated here.

On a minor note, I think that min and max should be swapped in Equation 1 and 2 (r corresponding to a reward, not cost).

Presentation/Clarity:
I don't have a strong mathematical background and would not say that the paper is fully clear to me. However, this is rather caused by the nature of the paper. Indeed, I think that the paper is well written and relatively clear.

Evaluation:
The paper only contains a very short experiment section, however, this is reasonable given that contributions are theoretical. I would be interested in some insights on the strong oscillatory behavior of the NN-reward on the acrobot task. I noticed such behavior with GAIL also on more complex tasks and sometimes it would not even recover as quickly as in the acrobot plot. Is this caused by overfitting of the discriminator?

Assessment:
I think that the paper could be an interesting contribution for ICLR. However, my confidence is rather small here.
review_title: Official Blind Review #1

final_score: rating: 6: Weak Accept
review_content: Summary: This paper presents theoretical analysis of the generalization properties of GAIL, as well as the local convergence of the traditional minibatch SGD applied to its min-max optimization problem (without assuming convex-concave structure of the game).  Specifically, the authors first prove a generalization bound for GAIL that characterizes how well optimizing the empirical GAIL objective minimizes the true population version (in terms of an "R-distance" they use the characterize the expected distributions induced by the underlying policies for a given reward class).  Second, they prove a convergence result for minibatch SGD applied to the min-max game, showing that the method will converge to a stationary point regardless of any convex-concave structure.

Comments: Before I begin, I should add that several elements of the paper were a bit difficult for me to follow, so I'm happy for the authors to correct any factual errors that I might make.  Overall, I think that this is an interesting, if somewhat incremental and technical paper about the generalization and convergence of GAIL.

First, on the generalization aspects, the methodology here seems to largely parallel Arora et al.'s analysis of generalization in GANs.  The main technical steps seem to be, 1) some effort in determining the proper distance to use in the first place, and how to define generalization, which they do via the R-distance, and then 2) on the more technical side, overcoming the fact that trajectories do not provide iid samples as is the case in the GAN analysis.  This later difficulty is overcome via the independent block technique, which allows one to bound the relevant population quantities of interest by sampling from subsampled blocks of the original trajectory.

Second, on the convergence side, the main result here seems to be a generic convergence result for minibatch SGD applied to a non-convex-concave game.  I may be missing something here, but it doesn't seem like there is any real specificity to the GAIL objective, but rather this would apply to any such min-max problem (I suppose also in the case where there is an L2 projection in the gradient step); while there is some discussion of the chain mixing properties, this seems largely needed just to provide bounds on certain constants.  The proof is rather technical (I admit I didn't go through it in much detail) and even the sketch doesn't provide a great intuition about what might make this problem harder than proving convergence of traditional SGD in the non-convex pure minimization case.  And for example, even convex-concave games have well-known pathologies when running gradient descent, such as cycling around an optimal point, and I didn't understand whether anything was being done to explicitly account for this, or if one of their assumptions essentially just avoids this possibility (maybe the mixing properties prevent this?).

On the whole, despite what seems to me to be a somewhat incremental nature, I'm still leaning toward accepting the paper: technical analysis like this is good to have, and the setting is distinct enough from past e.g., GAN work, that I believe it stands on its own.  I do think the clarity of the paper can be improved, as well.  This includes some simple elements like spacing out the equations better in Section 4, which were currently very condensed and difficult to read (and there is plenty of space to make the paper longer).  But I also would have liked a bit higher-level explanation of the challenges involved in proving convergence (like avoiding cycling), rather than just highlighting the functional elements of the proof.  I actually think the generalization section did this relatively well, in regards to the setting up their choice of IPM in contrast to the GAN work, but it was lacking in the convergence section.
review_title: Official Blind Review #2

Meta-review: The paper provides a theoretical analysis of the recent and popular Generative Adversarial Imitation Learning (GAIL) approach. Valuable new insights on generalization and convergence are developed, and put GAIL on a stronger theoretical foundation. Reviewer questions and suggestions were largely addressed during the rebuttal.
Decision: Accept (Poster)