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

arXiv: https://arxiv.org/abs/2108.08765 · HTML: https://mlsanity.com/paper/2108.08765/

## Key facts

- Cited by 11 papers in the map (data through 14 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.

## Placed in

- Offline RL and imitation learning from data / [Imitation learning methods](https://mlsanity.com/offlinerl/imitation-learning-methods/)

## Builds on (most cited first, 30 of 44)

- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [Conservative Q-Learning for Offline Reinforcement Learning](https://mlsanity.com/paper/2006.04779/) (2020)
- [Off-Policy Deep Reinforcement Learning without Exploration](https://mlsanity.com/paper/1812.02900/) (2018)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [MOPO: Model-based Offline Policy Optimization](https://mlsanity.com/paper/2005.13239/) (2020)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Guided Cost Learning: Deep Inverse Optimal Control via Policy Optimization](https://mlsanity.com/paper/1603.00448/) (2016)
- [COMBO: Conservative Offline Model-Based Policy Optimization](https://mlsanity.com/paper/2102.08363/) (2021)
- [Is Pessimism Provably Efficient for Offline RL?](https://mlsanity.com/paper/2012.15085/) (2020)
- [Information-Theoretic Considerations in Batch Reinforcement Learning](https://mlsanity.com/paper/1905.00360/) (2019)
- [A Theory of Regularized Markov Decision Processes](https://mlsanity.com/paper/1901.11275/) (2019)
- [Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism](https://mlsanity.com/paper/2103.12021/) (2021)
- [Critic Regularized Regression](https://mlsanity.com/paper/2006.15134/) (2020)
- [Bellman-consistent Pessimism for Offline Reinforcement Learning](https://mlsanity.com/paper/2106.06926/) (2021)
- [Model-Based Reinforcement Learning with Value-Targeted Regression](https://mlsanity.com/paper/2006.01107/) (2020)
- [Keep Doing What Worked: Behavioral Modelling Priors for Offline Reinforcement Learning](https://mlsanity.com/paper/2002.08396/) (2020)
- [Provably Efficient Exploration in Policy Optimization](https://mlsanity.com/paper/1912.05830/) (2019)
- [Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound](https://mlsanity.com/paper/1905.10389/) (2019)
- [A General Safety Framework for Learning-Based Control in Uncertain Robotic Systems](https://mlsanity.com/paper/1705.01292/) (2017)
- [Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning](https://mlsanity.com/paper/2106.04895/) (2021)
- [Minimax Weight and Q-Function Learning for Off-Policy Evaluation](https://mlsanity.com/paper/1910.12809/) (2019)
- [What are the Statistical Limits of Offline RL with Linear Function Approximation?](https://mlsanity.com/paper/2010.11895/) (2020)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints](https://mlsanity.com/paper/2101.02195/) (2021)
- [Minimax-Optimal Off-Policy Evaluation with Linear Function Approximation](https://mlsanity.com/paper/2002.09516/) (2020)
- [Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPs](https://mlsanity.com/paper/1909.02769/) (2019)
- [Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping](https://mlsanity.com/paper/2006.13165/) (2020)
- [Toward the Fundamental Limits of Imitation Learning](https://mlsanity.com/paper/2009.05990/) (2020)
- [Imitating Driver Behavior with Generative Adversarial Networks](https://mlsanity.com/paper/1701.06699/) (2017)
- [Information Theoretic Regret Bounds for Online Nonlinear Control](https://mlsanity.com/paper/2006.12466/) (2020)

## Built on by (most cited first, 11 of 11)

- [Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimism](https://mlsanity.com/paper/2203.05804/) (2022)
- [Understanding Adversarial Imitation Learning in Small Sample Regime: A Stage-coupled Analysis](https://mlsanity.com/paper/2208.01899/) (2022)
- [A Dual Approach to Imitation Learning from Observations with Offline Datasets](https://mlsanity.com/paper/2406.08805/) (2024)
- [Provably and Practically Efficient Adversarial Imitation Learning with General Function Approximation](https://mlsanity.com/paper/2411.00610/) (2024)
- [Near-Optimal Second-Order Guarantees for Model-Based Adversarial Imitation Learning](https://mlsanity.com/paper/2510.09487/) (2025)
- [Dual Generator Offline Reinforcement Learning](https://mlsanity.com/paper/2211.01471/) (2022)
- [Your Self-Play Algorithm is Secretly an Adversarial Imitator: Understanding LLM Self-Play through the Lens of Imitation Learning](https://mlsanity.com/paper/2602.01357/) (2026)
- [Adversarial Imitation Learning with General Function Approximation: Theoretical Analysis and Practical Algorithms](https://mlsanity.com/paper/2605.01778/) (2026)
- [Non-Adversarial Imitation Learning Provably Free of Compounding Errors: The Value Flow Mechanism](https://mlsanity.com/paper/2603.22713/) (2026)
- [Provably Efficient Policy-Reward Co-Pretraining for Adversarial Imitation Learning](https://mlsanity.com/paper/2606.22056/) (2026)
- [Provable Benefits of Regularization: Fast Rates for Adversarial Imitation Learning](https://mlsanity.com/paper/2609.35698/) (2026)

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