Generative Adversarial Imitation Learning (GAIL) is a powerful and practical approach for learning sequential decision-making policies. Different from Reinforcement Learning (RL), GAIL takes advantage of demonstration data by experts (e.g., human), and learns both the policy and reward function of the unknown environment. Despite the significant empirical progresses, the theory behind GAIL is still largely unknown. The major difficulty comes from the underlying temporal dependency of the demonstration data and the minimax computational formulation of GAIL without convex-concave structure. To bridge such a gap between theory and practice, this paper investigates the theoretical properties of GAIL. Specifically, we show: (1) For GAIL with general reward parameterization, the generalization can be guaranteed as long as the class of the reward functions is properly controlled; (2) For GAIL, where the reward is parameterized as a reproducing kernel function, GAIL can be efficiently solved by stochastic first order optimization algorithms, which attain sublinear convergence to a stationary solution. To the best of our knowledge, these are the first results on statistical and computational guarantees of imitation learning with reward/policy function approximation. Numerical experiments are provided to support our analysis.
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.