mlsanityData to 7 Oct 2026

Provably Efficient Adversarial Imitation Learning with Unknown Transitions

arXiv 2306.06563 ↗First posted 11 Jun 2023cs.LGcited by 16

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

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|

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

Builds on

33 of 64 references.

Closest ancestors · 15

Same direction, newest first

  1. 2022Proximal Point Imitation Learning22 Sep
  2. 2022Understanding Adversarial Imitation Learning in Small Sample Regime: A Stage-coupled Analysis3 Aug
  3. 2022Minimax Optimal Online Imitation Learning via Replay Estimation30 May
  4. 2022Rethinking ValueDice: Does It Really Improve Performance?5 Feb
  5. 2021IQ-Learn: Inverse soft-Q Learning for Imitation23 Jun
  6. 2021Provably Breaking the Quadratic Error Compounding Barrier in Imitation Learning, Optimally25 Feb
  7. 2020Error Bounds of Imitating Policies and Environments22 Oct
  8. 2020Toward the Fundamental Limits of Imitation Learning13 Sep
  9. 2020Primal Wasserstein Imitation Learning8 Jun
  10. 2020On Computation and Generalization of Generative Adversarial Imitation Learning9 Jan
  11. 2019A Divergence Minimization Perspective on Imitation Learning Methods6 Nov
  12. 2019Imitation Learning as f-Divergence Minimization30 May
3 more
  1. 2018An Algorithmic Perspective on Imitation Learning16 Nov
  2. 2018Discriminator-Actor-Critic: Addressing Sample Inefficiency and Reward Bias in Adversarial Imitation Learning9 Sep
  3. 2018Behavioral Cloning from Observation4 May

Other references · 18

  1. 2016Generative Adversarial Imitation Learningcited by 1,576
  2. 2015End-to-End Training of Deep Visuomotor Policiescited by 847
  3. 2022BC-Z: Zero-Shot Task Generalization with Robotic Imitation Learningcited by 517
  4. 2018Is Q-learning Provably Efficient?cited by 485
  5. 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 407
  6. 2016Benchmarking Deep Reinforcement Learning for Continuous Controlcited by 361
  7. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 285
  8. 2020Reward-Free Exploration for Reinforcement Learningcited by 177
  9. 2020Fast active learning for pure exploration in reinforcement learningcited by 92
  10. 2020On Reward-Free Reinforcement Learning with Linear Function Approximationcited by 89
  11. 2018Virtual-Taobao: Virtualizing Real-world Online Retail Environment for Reinforcement Learningcited by 80
  12. 2020Adaptive Reward-Free Explorationcited by 77
6 more
  1. 2022Maximum-Likelihood Inverse Reinforcement Learning with Finite-Time Guaranteescited by 42
  2. 2021Reward-Free Model-Based Reinforcement Learning with Linear Function Approximationcited by 29
  3. 2021Online Apprenticeship Learningcited by 28
  4. 2022Active Exploration for Inverse Reinforcement Learningcited by 27
  5. 2019Apprenticeship Learning via Frank-Wolfecited by 13
  6. 2021Near-Optimal Reward-Free Exploration for Linear Mixture MDPs with Plug-in Solvercited by 13

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 1; 2024: 4; 2025: 6; 2026: 5.

16 papers.

Sort:

  1. 2024Imitation Learning in Discounted Linear MDPs without exploration assumptionscited by 15
  2. 2023Reward-Consistent Dynamics Models are Strongly Generalizable for Offline Reinforcement Learningcited by 12
  3. 2025Optimistically Optimistic Exploration for Provably Efficient Infinite-Horizon Reinforcement and Imitation Learningcited by 12
  4. 2024Provably and Practically Efficient Adversarial Imitation Learning with General Function Approximationcited by 6
  5. 2024How does Inverse RL Scale to Large State Spaces? A Provably Efficient Approachcited by 5
  6. 2025IL-SOAR : Imitation Learning with Soft Optimistic Actor cRiticcited by 5
  7. 2025Inverse Q-Learning Done Right: Offline Imitation Learning in Qπ-Realizable MDPscited by 5
  8. 2025Efficient Imitation under Misspecificationcited by 4
  9. 2025Learning Equilibria from Data: Provably Efficient Multi-Agent Imitation Learningcited by 4
  10. 2025Near-Optimal Second-Order Guarantees for Model-Based Adversarial Imitation Learningcited by 2
  11. 2024Provably Efficient Off-Policy Adversarial Imitation Learning with Convergence Guaranteescited by 1
  12. 2026Adversarial Imitation Learning with General Function Approximation: Theoretical Analysis and Practical Algorithmscited by 1
4 more
  1. 2026Non-Adversarial Imitation Learning Provably Free of Compounding Errors: The Value Flow Mechanismcited by 0
  2. 2026Split the Differences, Pool the Rest: Provably Efficient Multi-Objective Imitationcited by 0
  3. 2026Provably Efficient Policy-Reward Co-Pretraining for Adversarial Imitation Learningcited by 0
  4. 2026Provable Benefits of Regularization: Fast Rates for Adversarial Imitation Learningcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2021On Generalization of Adversarial Imitation Learning and Beyond
  2. 2020State-only Imitation with Transition Dynamics Mismatch
  3. 2024Efficient Imitation Learning with Conservative World Models
  4. 2022Imitation Learning by State-Only Distribution Matching
  5. 2022Planning for Sample Efficient Imitation Learning
  6. 2022Robust Learning from Observation with Model Misspecification
  7. 2019A New Framework for Query Efficient Active Imitation Learning
  8. 2022Learning from Guided Play: Improving Exploration for Adversarial Imitation Learning with Simple Auxiliary Tasks