# Provably Efficient Adversarial Imitation Learning with Unknown Transitions

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

## Key facts

- Cited by 16 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 33 of its 64 references that are in the map.
- First posted on arXiv 11 Jun 2023.

## 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 33)

- [Generative Adversarial Imitation Learning](https://mlsanity.com/paper/1606.03476/) (2016)
- [End-to-End Training of Deep Visuomotor Policies](https://mlsanity.com/paper/1504.00702/) (2015)
- [BC-Z: Zero-Shot Task Generalization with Robotic Imitation Learning](https://mlsanity.com/paper/2202.02005/) (2022)
- [Behavioral Cloning from Observation](https://mlsanity.com/paper/1805.01954/) (2018)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [An Algorithmic Perspective on Imitation Learning](https://mlsanity.com/paper/1811.06711/) (2018)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Benchmarking Deep Reinforcement Learning for Continuous Control](https://mlsanity.com/paper/1604.06778/) (2016)
- [Information-Theoretic Considerations in Batch Reinforcement Learning](https://mlsanity.com/paper/1905.00360/) (2019)
- [Discriminator-Actor-Critic: Addressing Sample Inefficiency and Reward Bias in Adversarial Imitation Learning](https://mlsanity.com/paper/1809.02925/) (2018)
- [IQ-Learn: Inverse soft-Q Learning for Imitation](https://mlsanity.com/paper/2106.12142/) (2021)
- [A Divergence Minimization Perspective on Imitation Learning Methods](https://mlsanity.com/paper/1911.02256/) (2019)
- [Reward-Free Exploration for Reinforcement Learning](https://mlsanity.com/paper/2002.02794/) (2020)
- [Imitation Learning as f-Divergence Minimization](https://mlsanity.com/paper/1905.12888/) (2019)
- [Primal Wasserstein Imitation Learning](https://mlsanity.com/paper/2006.04678/) (2020)
- [Toward the Fundamental Limits of Imitation Learning](https://mlsanity.com/paper/2009.05990/) (2020)
- [Fast active learning for pure exploration in reinforcement learning](https://mlsanity.com/paper/2007.13442/) (2020)
- [Error Bounds of Imitating Policies and Environments](https://mlsanity.com/paper/2010.11876/) (2020)
- [On Reward-Free Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2006.11274/) (2020)
- [Virtual-Taobao: Virtualizing Real-world Online Retail Environment for Reinforcement Learning](https://mlsanity.com/paper/1805.10000/) (2018)
- [Adaptive Reward-Free Exploration](https://mlsanity.com/paper/2006.06294/) (2020)
- [Maximum-Likelihood Inverse Reinforcement Learning with Finite-Time Guarantees](https://mlsanity.com/paper/2210.01808/) (2022)
- [Online Apprenticeship Learning](https://mlsanity.com/paper/2102.06924/) (2021)
- [Reward-Free Model-Based Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2110.06394/) (2021)
- [On Computation and Generalization of Generative Adversarial Imitation Learning](https://mlsanity.com/paper/2001.02792/) (2020)
- [Active Exploration for Inverse Reinforcement Learning](https://mlsanity.com/paper/2207.08645/) (2022)
- [Proximal Point Imitation Learning](https://mlsanity.com/paper/2209.10968/) (2022)
- [Minimax Optimal Online Imitation Learning via Replay Estimation](https://mlsanity.com/paper/2205.15397/) (2022)
- [Rethinking ValueDice: Does It Really Improve Performance?](https://mlsanity.com/paper/2202.02468/) (2022)
- [Near-Optimal Reward-Free Exploration for Linear Mixture MDPs with Plug-in Solver](https://mlsanity.com/paper/2110.03244/) (2021)

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

- [Imitation Learning in Discounted Linear MDPs without exploration assumptions](https://mlsanity.com/paper/2405.02181/) (2024)
- [Reward-Consistent Dynamics Models are Strongly Generalizable for Offline Reinforcement Learning](https://mlsanity.com/paper/2310.05422/) (2023)
- [Optimistically Optimistic Exploration for Provably Efficient Infinite-Horizon Reinforcement and Imitation Learning](https://mlsanity.com/paper/2502.13900/) (2025)
- [Provably and Practically Efficient Adversarial Imitation Learning with General Function Approximation](https://mlsanity.com/paper/2411.00610/) (2024)
- [How does Inverse RL Scale to Large State Spaces? A Provably Efficient Approach](https://mlsanity.com/paper/2406.03812/) (2024)
- [IL-SOAR : Imitation Learning with Soft Optimistic Actor cRitic](https://mlsanity.com/paper/2502.19859/) (2025)
- [Efficient Imitation under Misspecification](https://mlsanity.com/paper/2503.13162/) (2025)
- [Inverse Q-Learning Done Right: Offline Imitation Learning in Qπ-Realizable MDPs](https://mlsanity.com/paper/2505.19946/) (2025)
- [Learning Equilibria from Data: Provably Efficient Multi-Agent Imitation Learning](https://mlsanity.com/paper/2505.17610/) (2025)
- [Provably Efficient Off-Policy Adversarial Imitation Learning with Convergence Guarantees](https://mlsanity.com/paper/2405.16668/) (2024)
- [Near-Optimal Second-Order Guarantees for Model-Based Adversarial Imitation Learning](https://mlsanity.com/paper/2510.09487/) (2025)
- [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)
- [Split the Differences, Pool the Rest: Provably Efficient Multi-Objective Imitation](https://mlsanity.com/paper/2605.12000/) (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)

Imitation learning (IL) has proven to be an effective method for learning good policies from expert demonstrations. Adversarial imitation learning (AIL), a subset of IL methods, is particularly promising, but its theoretical foundation in the presence of unknown transitions has yet to be fully developed. This paper explores the theoretical underpinnings of AIL in this context, where the stochastic and uncertain nature of environment transitions presents a challenge. We examine the expert sample complexity and interaction complexity required to recover good policies. To this end, we establish a framework connecting reward-free exploration and AIL, and propose an algorithm, MB-TAIL, that achieves the minimax optimal expert sample complexity of widetildeO (H3/2 |S|/varepsilon) and interaction complexity of widetildeO (H3 |S|2 |A|/varepsilon2). Here, H represents the planning horizon, |S| is the state space size, |A| is the action space size, and varepsilon is the desired imitation gap. MB-TAIL is the first algorithm to achieve this level of expert sample complexity in the unknown transition setting and improves upon the interaction complexity of the best-known algorithm, OAL, by O(H). Additionally, we demonstrate the generalization ability of MB-TAIL by extending it to the function approximation setting and proving that it can achieve expert sample and interaction complexity independent of |S|