Near-Optimal Second-Order Guarantees for Model-Based Adversarial Imitation Learning

• URL: http://arxiv.org/abs/2510.09487v2
• Date: Mon, 13 Oct 2025 18:33:29 GMT
• Title: Near-Optimal Second-Order Guarantees for Model-Based Adversarial Imitation Learning
• Authors: Shangzhe Li, Dongruo Zhou, Weitong Zhang,
• Abstract summary: We study online adversarial imitation learning (AIL), where an agent learns from offline expert demonstrations and interacts with rewards.<n>We introduce a model-based AIL algorithm (MBAIL)<n>We show that MB-AIL attains minimax-optimal sample complexity for online interaction (up to logarithmic factors) with limited expert demonstrations.
• Score: 35.41154497688405
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study online adversarial imitation learning (AIL), where an agent learns from offline expert demonstrations and interacts with the environment online without access to rewards. Despite strong empirical results, the benefits of online interaction and the impact of stochasticity remain poorly understood. We address these gaps by introducing a model-based AIL algorithm (MB-AIL) and establish its horizon-free, second-order sample-complexity guarantees under general function approximations for both expert data and reward-free interactions. These second-order bounds provide an instance-dependent result that can scale with the variance of returns under the relevant policies and therefore tighten as the system approaches determinism. Together with second-order, information-theoretic lower bounds on a newly constructed hard-instance family, we show that MB-AIL attains minimax-optimal sample complexity for online interaction (up to logarithmic factors) with limited expert demonstrations and matches the lower bound for expert demonstrations in terms of the dependence on horizon $H$, precision $\epsilon$ and the policy variance $\sigma^2$. Experiments further validate our theoretical findings and demonstrate that a practical implementation of MB-AIL matches or surpasses the sample efficiency of existing methods.

Related papers

• Sample Complexity of Distributionally Robust Off-Dynamics Reinforcement Learning with Online Interaction [11.339580074756187]
  Off-dynamics reinforcement learning (RL) can be formulated as learning in a robust Markov decision process (RMDP)<n>We study a more realistic and challenging setting where the agent is limited to online interaction with the training environment.
  arXiv  Detail & Related papers  (2025-11-07T16:24:22Z)
• Rate optimal learning of equilibria from data [63.14746189846806]
  We close theoretical gaps in Multi-Agent Imitation Learning (MAIL) by characterizing the limits of non-interactive MAIL and presenting the first interactive algorithm with near-optimal sample complexity.<n>For the interactive setting, we introduce a framework that combines reward-free reinforcement learning with interactive MAIL and instantiate it with an algorithm, MAIL-WARM.<n>We provide numerical results that support our theory and illustrate, in environments such as grid worlds, where Behavior Cloning fails to learn.
  arXiv  Detail & Related papers  (2025-10-10T12:28:35Z)
• Offline Learning for Combinatorial Multi-armed Bandits [56.96242764723241]
  Off-CMAB is the first offline learning framework for CMAB.<n>Off-CMAB combines pessimistic reward estimations with solvers.<n>Experiments on synthetic and real-world datasets highlight the superior performance of CLCB.
  arXiv  Detail & Related papers  (2025-01-31T16:56:18Z)
• How to Leverage Diverse Demonstrations in Offline Imitation Learning [39.24627312800116]
  Offline Imitation Learning (IL) with imperfect demonstrations has garnered increasing attention owing to the scarcity of expert data. We introduce a simple yet effective data selection method that identifies positive behaviors based on their resultant states. We then devise a lightweight behavior cloning algorithm capable of leveraging the expert and selected data correctly.
  arXiv  Detail & Related papers  (2024-05-24T04:56:39Z)
• A Simple Solution for Offline Imitation from Observations and Examples with Possibly Incomplete Trajectories [122.11358440078581]
  offline imitation is useful in real-world scenarios where arbitrary interactions are costly and expert actions are unavailable. We propose Trajectory-Aware Learning from Observations (TAILO) to solve MDPs where only task-specific expert states and task-agnostic non-expert state-action pairs are available.
  arXiv  Detail & Related papers  (2023-11-02T15:41:09Z)
• Model-based Offline Policy Optimization with Adversarial Network [0.36868085124383626]
  We propose a novel Model-based Offline policy optimization framework with Adversarial Network (MOAN) Key idea is to use adversarial learning to build a transition model with better generalization. Our approach outperforms existing state-of-the-art baselines on widely studied offline RL benchmarks.
  arXiv  Detail & Related papers  (2023-09-05T11:49:33Z)
• When Demonstrations Meet Generative World Models: A Maximum Likelihood Framework for Offline Inverse Reinforcement Learning [62.00672284480755]
  This paper aims to recover the structure of rewards and environment dynamics that underlie observed actions in a fixed, finite set of demonstrations from an expert agent. Accurate models of expertise in executing a task has applications in safety-sensitive applications such as clinical decision making and autonomous driving.
  arXiv  Detail & Related papers  (2023-02-15T04:14:20Z)
• On Efficient Online Imitation Learning via Classification [17.416831207557603]
  We study classification-based online imitation learning (abbrev. $textbfCOIL$) and the fundamental feasibility to design oracle-efficient regret-minimization algorithms. Our work puts classification-based online imitation learning, an important IL setup, into a firmer foundation.
  arXiv  Detail & Related papers  (2022-09-26T17:34:36Z)
• Offline Reinforcement Learning with Instrumental Variables in Confounded Markov Decision Processes [93.61202366677526]
  We study the offline reinforcement learning (RL) in the face of unmeasured confounders. We propose various policy learning methods with the finite-sample suboptimality guarantee of finding the optimal in-class policy.
  arXiv  Detail & Related papers  (2022-09-18T22:03:55Z)
• Discriminator-Guided Model-Based Offline Imitation Learning [11.856949845359853]
  offline imitation learning (IL) is a powerful method to solve decision-making problems from expert demonstrations without reward labels. We propose the Discriminator-guided Model-based offline Learning (DMIL) framework, which introduces a discriminator to simultaneously distinguish the dynamics correctness and suboptimality of model rollout data. Experimental results show that DMIL and its extension achieve superior performance and robustness compared to state-of-the-art offline IL methods under small datasets.
  arXiv  Detail & Related papers  (2022-07-01T07:28:18Z)
• Efficient Performance Bounds for Primal-Dual Reinforcement Learning from Demonstrations [1.0609815608017066]
  We consider large-scale Markov decision processes with an unknown cost function and address the problem of learning a policy from a finite set of expert demonstrations. Existing inverse reinforcement learning methods come with strong theoretical guarantees, but are computationally expensive. We introduce a novel bilinear saddle-point framework using Lagrangian duality to bridge the gap between theory and practice.
  arXiv  Detail & Related papers  (2021-12-28T05:47:24Z)
• GELATO: Geometrically Enriched Latent Model for Offline Reinforcement Learning [54.291331971813364]
  offline reinforcement learning approaches can be divided into proximal and uncertainty-aware methods. In this work, we demonstrate the benefit of combining the two in a latent variational model. Our proposed metrics measure both the quality of out of distribution samples as well as the discrepancy of examples in the data.
  arXiv  Detail & Related papers  (2021-02-22T19:42:40Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.