Research map / Learning theory and algorithms / Sample complexity
Provably and Practically Efficient Adversarial Imitation Learning with General Function Approximation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes OPT-AIL, an adversarial imitation learning method with general function approximation that combines online (FTRL-style) reward optimization with optimism-regularized Bellman error minimization for Q-functions, giving polynomial expert and interaction complexity plus a practical neural implementation evaluated on DMControl.
Problem
Existing theory for online adversarial imitation learning covers only tabular or linear function approximation with algorithmic designs (count-based or covariance bonuses) that are hard to implement with neural networks, leaving a gap between theory and practice.
Approach
Decompose the imitation gap into reward error and policy error; update rewards by no-regret online optimization over historical policy-expert value gaps, and update Q-functions by minimizing an optimism-regularized Bellman error, then act greedily. The method admits a provable general-function-approximation guarantee and a simple actor-critic style practical implementation.
Key results
- OPT-AIL significantly outperforms BC on DMControl tasks across expert trajectory counts, consistent with the theoretical O(H) improvement over BC.
- With a single expert trajectory, OPT-AIL uniquely reaches expert or near-expert return on Finger Spin, Walker Run and Hopper Hop.
- OPT-AIL matches or exceeds prior SOTA deep AIL methods (IQLearn, FILTER, HyPE) on all 8 tasks after 500k interactions.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use OPT-AIL instead of BC | Imitation learning · DMControl tasks | return | Helped |
| Use OPT-AIL instead of prior state-of-the-art AIL methods | Deep adversarial imitation learning · DMControl tasks | return | Mixed |
| Use OPT-AIL instead of prior state-of-the-art AIL methods | Deep adversarial imitation learning · DMControl tasks with 1 expert trajectory | environment interaction efficiency | Mixed |
Limitations
- Theory requires Bellman completeness of the Q-value class, which the authors note as a limitation.
- Expert sample complexity H^2/eps^2 is worse than the best known tabular rate H^{3/2}/eps.
- Theoretical analysis assumes low generalized eluder coefficient, which is not verified for neural networks.
Experimental setup
Datasets: DMControl (feature-based) expert demonstrations
Benchmarks: DMControl (8 tasks)
Metrics: episode return expert sample efficiency interaction efficiency
Baselines: BC IQLearn PPIL FILTER HyPE
Builds on: generalized eluder coefficient framework GAIL IQLearn DrQ-v2 FTRL
Closest papers by meaning
- Near-Optimal Second-Order Guarantees for Model-Based Adversarial Imitation Learning (ICLR 2026 · similarity 0.92)
- On Computation and Generalization of Generative Adversarial Imitation Learning (ICLR 2020 · similarity 0.90)
- On Discovering Algorithms for Adversarial Imitation Learning (ICLR 2026 · similarity 0.90)
- Adversarial Imitation Learning via Boosting (ICLR 2024 · similarity 0.89)
- Exploring Gradient Explosion in Generative Adversarial Imitation Learning: A Probabilistic Perspective (AAAI 2024 · similarity 0.89)
- C-GAIL: Stabilizing Generative Adversarial Imitation Learning with Control Theory (NeurIPS 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.