🤖 machine learning

Provably Efficient Off-Policy Adversarial Imitation Learning with Convergence Guarantees

This paper establishes the first theoretical convergence guarantees and sample complexity bounds for off-policy Adversarial Imitation Learning, demonstrating that reusing samples from recent policies without importance sampling correction enhances sample efficiency while maintaining convergence.

Original authors: Yilei Chen, Vittorio Giammarino, James Queeney, Ioannis Ch. Paschalidis

Published 2026-07-09

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yilei Chen, Vittorio Giammarino, James Queeney, Ioannis Ch. Paschalidis

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Teaching a Robot by Watching a Master

Imagine you want to teach a robot to walk like a human. You don't have a manual or a list of rules (rewards) telling the robot what to do. Instead, you only have a video of a perfect human walker (the "expert").

This is the problem of Imitation Learning. The robot has to figure out how to walk just by watching the expert.

Adversarial Imitation Learning (AIL) is a popular way to solve this. Think of it as a game between two players:

The Agent (The Robot): Tries to walk as much like the expert as possible.
The Adversary (The Critic): Tries to spot the differences between the robot and the expert. If the robot looks clumsy, the Critic gives it a "bad score" (a low reward). If the robot looks good, the Critic gives a "good score."

They play this game over and over. The Critic gets better at spotting flaws, and the Robot gets better at hiding them, until the Robot walks just like the expert.

The Problem: The "Fresh Data" Bottleneck

In standard AIL, there is a major inefficiency. Every time the Critic updates its "scoring rules," it needs to see the robot walking right now (using "on-policy" data).

The Analogy: Imagine a cooking class where a student (the robot) is learning to cook from a master chef (the expert).

The Standard Method: Every time the teacher (the Critic) wants to give feedback on the student's technique, the student must cook a brand new dish from scratch. The teacher tastes it, gives feedback, and then the student throws the dish away and cooks another one for the next lesson.
The Result: This is incredibly wasteful. It takes a huge amount of time and ingredients (samples) to learn. In the real world, interacting with the environment (cooking, driving, flying) is expensive or dangerous, so we can't afford to throw away so many attempts.

The Solution: Reusing Old Recipes (Off-Policy Learning)

The authors propose a smarter way: Off-Policy Adversarial Imitation Learning.

The Analogy: Instead of making the student cook a fresh dish every time the teacher gives feedback, the teacher looks at a mix of dishes the student cooked in the last few days.

The teacher says, "Okay, I'm going to grade your performance based on the stew you made yesterday, the soup you made two days ago, and the salad from three days ago."
The Benefit: The student learns much faster because they aren't wasting time cooking new dishes just to get feedback. They reuse the data they already have.

The Catch: There is a risk. If the student's cooking style changed drastically between yesterday and today, the teacher might get confused. The "flavor" of the data has shifted. In technical terms, this is called distribution shift error.

The Paper's Breakthrough: Proving It Works Safely

The big question the paper answers is: "Can we reuse old data without breaking the learning process?"

Many previous methods tried to fix the "flavor shift" using complex mathematical corrections (like "Importance Sampling"), but these often made the math unstable or the learning slow.

The Authors' Claim:
They show that you don't need complex corrections if you are careful about how much old data you use.

The "Sweet Spot" Rule: You can reuse data from the most recent $N$ attempts. However, $N$ cannot be too big. If you look back too far (e.g., data from a month ago), the robot's style has changed too much, and the feedback becomes useless.
The Magic Number: The paper proves mathematically that if you reuse data from roughly the square root of the total number of lessons ( $\sqrt{K}$ $K$ ), you get the best of both worlds:
- You get the speed of reusing old data (sample efficiency).
- You still get the guarantee that the robot will eventually learn to walk perfectly (convergence).

The Metaphor:
Imagine the robot is a dancer.

If the teacher only watches the dance right now, the teacher is very accurate but gets tired quickly because they need a fresh performance every time.
If the teacher watches a video of the dance from 10 years ago, the teacher is confused because the dancer has changed.
The Paper's Solution: The teacher watches a playlist of the dancer's last 5 performances. It's close enough to the current style to be accurate, but it saves the dancer from having to perform a brand new routine for every single critique. The paper proves that as long as the playlist isn't too long, the dancer will still learn the perfect routine.

What They Found in Experiments

The authors tested this on computer simulations (like a robot navigating a grid or a virtual character running on a treadmill).

Result: The "Off-Policy" method (reusing old data) learned much faster than the standard method.
Observation: In some tasks, reusing data from 32 recent attempts was perfect. In others, reusing 128 was better. This confirms their theory: the "perfect number" of past attempts to reuse depends on how complex the task is.
Key Takeaway: You don't need to throw away your past attempts. By carefully mixing them into your training, you can teach robots to learn with far fewer interactions.

Summary

This paper provides a mathematical safety net for a practical trick. It proves that if you teach a robot by looking at its recent past attempts (rather than forcing it to generate new ones every time), you can make learning much more efficient without sacrificing the guarantee that the robot will eventually learn the task correctly. It turns a "wasteful" learning process into a "recycling" one, backed by solid math.

Technical Summary: Provably Efficient Off-Policy Adversarial Imitation Learning with Convergence Guarantees

Problem Statement

Adversarial Imitation Learning (AIL) frames imitation learning as a two-player game where an agent updates its policy to match an expert's performance, while an adversary updates a reward function to maximize the performance gap between the two. Standard AIL algorithms require on-policy data (samples generated by the agent's current policy) to evaluate the expected cumulative rewards during reward function updates. This requirement leads to significant sample inefficiency, as it necessitates new environment interactions at every update step, rendering the approach impractical for settings where interactions are expensive or limited.

While off-policy methods have been proposed to reuse data from previous policies to improve sample efficiency, they introduce a distribution shift error because the data no longer perfectly matches the current policy's state-action visitation distribution. Existing off-policy AIL approaches either rely on importance sampling (which induces high variance) or complex variable transformations that alter the objective function, often forfeiting theoretical convergence guarantees. The core challenge addressed in this work is: Can we guarantee the convergence of off-policy AIL and ensure sample efficiency without relying on explicit off-policy correction techniques like importance sampling?

Methodology

The authors propose an off-policy AIL algorithm that combines model-based mirror descent for policy updates with off-policy projected gradient ascent for reward updates. The key innovation lies in controlling the distribution shift error by carefully selecting the number of past policies ( $N$ ) whose data is reused during reward updates.

1. Policy Updates

The algorithm employs a model-based mirror descent approach.

Model Estimation: The state-transition function $\hat{P}_h$ is estimated empirically from state-action encounters.
Policy Optimization: The policy is updated using a KL-divergence regularized mirror descent step (Equation 3). This update rule, derived from the estimated Q-values, ensures that the policy changes are conservative enough to bound the Total Variation (TV) distance between consecutive policies. This stability is crucial for controlling the distribution shift in the off-policy reward updates.

2. Reward Updates

Instead of using only data from the current policy $\pi_{k-1}$ , the reward update utilizes a mixture of data from the $N(k)$ most recent policies.

Mixture Distribution: The algorithm samples from a mixture distribution $d^{k-1, mix}_h = \sum_{n=1}^{N} \beta_n d^{k-n}_h$ , where $\beta_n$ are uniform weights.
Objective: The reward parameters $\mu$ are updated via projected gradient ascent to maximize the loss $L(\pi^{k-1, mix}, \mu) = J(\pi_E, \mu) - \frac{1}{N}\sum_{n=1}^N J(\pi_{k-n}, \mu)$ .
Error Control: Theoretical analysis (Lemma 4.2 and Theorem 4.3) demonstrates that if the policy updates are sufficiently small (controlled by step size $\sigma$ ), the divergence between the mixture distribution and the current policy's distribution remains bounded.

3. Theoretical Framework

The regret of the AIL algorithm is decomposed into policy regret and reward regret (Lemma 3.2). The authors derive bounds for both:

Policy Regret: Bounded by $\tilde{O}(\sqrt{H^4 S^2 A K})$ using the mirror descent update.
Reward Regret: Bounded by a term comprising the standard regret, an error term induced by off-policy updates, and an estimation error term (Theorem 4.4).
Main Result (Theorem 4.5): The total regret is sublinear with respect to the number of iterations $K$ , provided that the number of reused policies $N(k)$ scales as $o(\sqrt{K})$ . Specifically, if $N$ is fixed, the optimal scaling is $N^* = \tilde{O}((S/(HAB))^{1/3})$ .

Key Contributions

Convergence Guarantees without Correction: The paper provides the first theoretical convergence guarantees for an off-policy AIL algorithm that does not require off-policy correction techniques (e.g., importance sampling).
Sample Efficiency Analysis: The authors establish that reusing samples from the $o(\sqrt{K})$ most recent policies does not undermine convergence. They prove that the distribution shift error is dominated by the benefits of increased data availability, particularly when the state space size ( $S$ ) is large relative to the horizon ( $H$ ) and action space ( $A$ ).
Practical Validation: The algorithm is validated on both discrete space MiniGrid tasks and continuous space OpenAI Gym (MuJoCo) benchmarks, demonstrating that off-policy variants ( $N > 1$ ) converge faster and require fewer samples than their on-policy counterparts ( $N=1$ ).

Experimental Results

MiniGrid (Discrete): In EmptyRoom tasks of varying sizes ( $3\times3$ , $5\times5$ , $9\times9$ ), off-policy algorithms with $N=32$ achieved expert-level performance with approximately 1,000 interactions, whereas the on-policy algorithm ( $N=1$ ) required the full 10,000 interaction horizon to converge. The results confirmed that larger state spaces benefit from larger $N$ .
MuJoCo (Continuous): In HalfCheetah, Hopper, and Walker2d tasks, off-policy algorithms consistently outperformed the on-policy baseline. While the optimal $N$ varied across environments, significant gains were observed even with small $N$ (e.g., $N=4$ or $N=16$ ).
Observation: The experiments support the theoretical claim that off-policy AIL can achieve superior sample efficiency, though the optimal number of reused policies depends on the specific environment characteristics.

Significance and Claims

The paper claims to bridge the gap between the theoretical understanding and practical application of off-policy AIL. While previous works demonstrated the practical success of off-policy AIL, they lacked rigorous convergence proofs. This work demonstrates that:

Theoretical Support: It is possible to guarantee convergence for off-policy AIL by simply controlling the distribution shift through conservative policy updates and limiting the number of reused policies.
Sample Efficiency: The "error" introduced by off-policy data is theoretically shown to be outweighed by the statistical benefits of having more data, especially in high-dimensional state spaces.
Simplicity: The proposed method avoids complex variance-reduction techniques like importance sampling, offering a simpler, theoretically grounded alternative that aligns with empirical observations of sample efficiency in practice.

The authors modestly note that their theoretical analysis assumes tabular settings (extended to linear MDPs in the appendix) and that the optimal $N$ in deep RL settings (MuJoCo) may not perfectly align with the theoretical worst-case bounds due to neural network parameterization, yet the performance trends remain consistent with the theory.