mlsanityData to 7 Oct 2026

Provably Efficient Generative Adversarial Imitation Learning for Online and Offline Setting with Linear Function Approximation

arXiv 2108.08765 ↗First posted 19 Aug 2021cs.LG cs.AI math.OCcited by 11

On the map: Offline RL and imitation learning from data → Imitation learning methods

Abstract (arXiv)

In generative adversarial imitation learning (GAIL), the agent aims to learn a policy from an expert demonstration so that its performance cannot be discriminated from the expert policy on a certain predefined reward set. In this paper, we study GAIL in both online and offline settings with linear function approximation, where both the transition and reward function are linear in the feature maps. Besides the expert demonstration, in the online setting the agent can interact with the environment, while in the offline setting the agent only accesses an additional dataset collected by a prior. For online GAIL, we propose an optimistic generative adversarial policy optimization algorithm (OGAP) and prove that OGAP achieves widetildeO(H2 d3/2K1/2+KH3/2dN1-1/2) regret. Here N1 represents the number of trajectories of the expert demonstration, d is the feature dimension, and K is the number of episodes. For offline GAIL, we propose a pessimistic generative adversarial policy optimization algorithm (PGAP). For an arbitrary additional dataset, we obtain the optimality gap of PGAP, achieving the minimax lower bound in the utilization of the additional dataset. Assuming sufficient coverage on the additional dataset, we show that PGAP achieves widetildeO(H2dK-1/2 +H2d3/2N2-1/2+H3/2dN1-1/2 ) optimality gap. Here N2 represents the number of trajectories of the additional dataset with sufficient coverage.

Key facts. Cited by 11 papers in the map (data through 7 Oct 2026). Placed in Imitation learning methods, one of 13 directions in Offline RL and imitation learning from data. Builds on 44 of its 78 references that are in the map. First posted on arXiv 19 Aug 2021.

Builds on

44 of 78 references.

Closest ancestors · 7

Same direction, newest first

  1. 2021Mitigating Covariate Shift in Imitation Learning via Offline Data Without Great Coverage6 Jun
  2. 2021Provably Breaking the Quadratic Error Compounding Barrier in Imitation Learning, Optimally25 Feb
  3. 2020Offline Learning from Demonstrations and Unlabeled Experience27 Nov
  4. 2020Error Bounds of Imitating Policies and Environments22 Oct
  5. 2020Toward the Fundamental Limits of Imitation Learning13 Sep
  6. 2020On Computation and Generalization of Generative Adversarial Imitation Learning9 Jan
  7. 2019On the Global Convergence of Imitation Learning: A Case for Linear Quadratic Regulator11 Jan

Other references · 37

  1. 2015Trust Region Policy Optimizationcited by 2,503
  2. 2020Conservative Q-Learning for Offline Reinforcement Learningcited by 1,777
  3. 2018Off-Policy Deep Reinforcement Learning without Explorationcited by 1,227
  4. 2019Introduction to Online Convex Optimizationcited by 793
  5. 2020MOPO: Model-based Offline Policy Optimizationcited by 630
  6. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  7. 2018Is Q-learning Provably Efficient?cited by 485
  8. 2016Guided Cost Learning: Deep Inverse Optimal Control via Policy Optimizationcited by 400
  9. 2021COMBO: Conservative Offline Model-Based Policy Optimizationcited by 365
  10. 2020Is Pessimism Provably Efficient for Offline RL?cited by 362
  11. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 285
  12. 2019A Theory of Regularized Markov Decision Processescited by 279
25 more
  1. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimismcited by 275
  2. 2020Critic Regularized Regressioncited by 269
  3. 2021Bellman-consistent Pessimism for Offline Reinforcement Learningcited by 267
  4. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  5. 2020Keep Doing What Worked: Behavioral Modelling Priors for Offline Reinforcement Learningcited by 213
  6. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
  7. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
  8. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learningcited by 157
  9. 2017A General Safety Framework for Learning-Based Control in Uncertain Robotic Systemscited by 150
  10. 2019Minimax Weight and Q-Function Learning for Off-Policy Evaluationcited by 150
  11. 2020What are the Statistical Limits of Offline RL with Linear Function Approximation?cited by 135
  12. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  13. 2020Minimax-Optimal Off-Policy Evaluation with Linear Function Approximationcited by 120
  14. 2019Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPscited by 113
  15. 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
  16. 2017Imitating Driver Behavior with Generative Adversarial Networkscited by 92
  17. 2020Information Theoretic Regret Bounds for Online Nonlinear Controlcited by 87
  18. 2020Off-Policy Evaluation via the Regularized Lagrangiancited by 86
  19. 2019Learning Adversarial MDPs with Bandit Feedback and Unknown Transitioncited by 84
  20. 2019Online Convex Optimization in Adversarial Markov Decision Processescited by 79
  21. 2020Optimistic Policy Optimization with Bandit Feedbackcited by 79
  22. 2020Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RLcited by 55
  23. 2021Online Apprenticeship Learningcited by 28
  24. 2020On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spacescited by 19
  25. 2017Multimodal Storytelling via Generative Adversarial Imitation Learningcited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 3; 2023: 0; 2024: 2; 2025: 1; 2026: 5.

11 papers.

  1. 2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimismcited by 63
  2. 2022Understanding Adversarial Imitation Learning in Small Sample Regime: A Stage-coupled Analysiscited by 13
  3. 2024A Dual Approach to Imitation Learning from Observations with Offline Datasetscited by 10
  4. 2024Provably and Practically Efficient Adversarial Imitation Learning with General Function Approximationcited by 6
  5. 2025Near-Optimal Second-Order Guarantees for Model-Based Adversarial Imitation Learningcited by 2
  6. 2022Dual Generator Offline Reinforcement Learningcited by 1
  7. 2026Your Self-Play Algorithm is Secretly an Adversarial Imitator: Understanding LLM Self-Play through the Lens of Imitation Learningcited by 1
  8. 2026Adversarial Imitation Learning with General Function Approximation: Theoretical Analysis and Practical Algorithmscited by 1
  9. 2026Non-Adversarial Imitation Learning Provably Free of Compounding Errors: The Value Flow Mechanismcited by 0
  10. 2026Provably Efficient Policy-Reward Co-Pretraining for Adversarial Imitation Learningcited by 0
  11. 2026Provable Benefits of Regularization: Fast Rates for Adversarial Imitation Learningcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2023Exploring Gradient Explosion in Generative Adversarial Imitation Learning: A Probabilistic Perspective
  2. 2018Sample-Efficient Imitation Learning via Generative Adversarial Nets
  3. 2020Generative Adversarial Imitation Learning with Neural Networks: Global Optimality and Convergence Rate
  4. 2024C-GAIL: Stabilizing Generative Adversarial Imitation Learning with Control Theory
  5. 2020When Will Generative Adversarial Imitation Learning Algorithms Attain Global Convergence
  6. 2020f-GAIL: Learning f-Divergence for Generative Adversarial Imitation Learning
  7. 2021A Pragmatic Look at Deep Imitation Learning
  8. 2018Risk-Sensitive Generative Adversarial Imitation Learning