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

Abstract

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 $\tilde{\mathcal{O}}(H^2{d}^{3/2}{K}^{1/2}+K{H}^{3/2}d{N}_1^{-1/2})$ regret. Here $N_1$ 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 $\tilde{\mathcal{O}}(H^{2}d{K}^{-1/2}+H^2{d}^{3/2}{N}_2^{-1/2}+H^{3/2}d{N}_1^{-1/2})$ optimality gap. Here $N_2$ represents the number of trajectories of the additional dataset with sufficient coverage.

arXiv comment54 pages, in submission

References in corpus (28)

• Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems
• Guided Cost Learning: Deep Inverse Optimal Control via Policy Optimization
• Conservative Q-Learning for Offline Reinforcement Learning
• Generative Adversarial Imitation Learning
• MOPO: Model-based Offline Policy Optimization
• Provably Efficient Reinforcement Learning with Linear Function Approximation
• Benchmarking Batch Deep Reinforcement Learning Algorithms
• Apprenticeship Learning using Inverse Reinforcement Learning and Gradient Methods
• Learning human behaviors from motion capture by adversarial imitation
• Critic Regularized Regression
• Model-Based Reinforcement Learning with Value-Targeted Regression
• COMBO: Conservative Offline Model-Based Policy Optimization
• Information-Theoretic Considerations in Batch Reinforcement Learning
• Keep Doing What Worked: Behavioral Modelling Priors for Offline Reinforcement Learning
• Minimax Regret Bounds for Reinforcement Learning
• What are the Statistical Limits of Offline RL with Linear Function Approximation?
• Provably Good Batch Reinforcement Learning Without Great Exploration
• Information Theoretic Regret Bounds for Online Nonlinear Control
• The Importance of Pessimism in Fixed-Dataset Policy Optimization
• Off-Policy Evaluation via the Regularized Lagrangian
• Toward the Fundamental Limits of Imitation Learning
• Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning
• On the Global Convergence of Imitation Learning: A Case for Linear Quadratic Regulator
• Bellman-consistent Pessimism for Offline Reinforcement Learning
• Offline Learning from Demonstrations and Unlabeled Experience
• Optimistic Policy Optimization with Bandit Feedback
• Mitigating Covariate Shift in Imitation Learning via Offline Data Without Great Coverage
• Provably Breaking the Quadratic Error Compounding Barrier in Imitation Learning, Optimally