Understanding Inverse Reinforcement Learning under Overparameterization: Non-Asymptotic Analysis and Global Optimality

Ruijia Zhang, Siliang Zeng, Chenliang Li, Alfredo García, Mingyi Hong

Abstract

Inverse Reinforcement Learning (IRL) aims to recover an underlying reward function and an optimal policy from expert demonstrations. Traditional IRL frameworks often rely on linear reward structures and computationally expensive nested-loop architectures. This paper introduces the first two-timescale, single-loop IRL algorithm that utilizes neural network-parameterized rewards while providing provable global optimality guarantees. By leveraging the properties of overparameterized neural networks, we provide a non-asymptotic convergence analysis, demonstrating that our approach can identify globally optimal rewards and policies in high-dimensional settings.

Introduction

Inverse Reinforcement Learning (IRL) is a powerful framework for imitation learning, where an agent seeks to uncover the latent reward function that motivates an expert's behavior. Despite its potential, IRL has historically been hampered by two significant challenges. First, the "nested loop" bottleneck requires solving a complete reinforcement learning (RL) problem (the inner loop) every time the reward function (the outer loop) is updated. This makes traditional methods like Maximum Entropy IRL (MaxEnt-IRL) computationally prohibitive in complex environments. Second, most theoretical guarantees for IRL are restricted to linear reward models. While neural networks offer the flexibility to model complex, non-linear rewards, their non-convex nature typically precludes guarantees of global optimality.

This research addresses these gaps by proposing a computationally efficient, single-loop algorithm that works with neural rewards and achieves provable global convergence.

Methodology: Two-Timescale Single-Loop ML-IRL

The proposed approach, Two-Timescale Single-Loop ML-IRL, departs from the traditional nested structure through several key innovations:

1. Maximum Likelihood Formulation

The task is framed as a bi-level optimization problem. The upper level focuses on maximizing the log-likelihood of the expert trajectories, treating the reward function as the primary variable to be learned.

2. Two-Timescale Stochastic Approximation

To eliminate the need for a full RL cycle at every reward update, the algorithm employs a two-timescale update rule inspired by actor-critic methods. The policy (lower level) is updated on a "fast" timescale using soft Q-learning, while the reward parameters (upper level) are updated on a "slow" timescale. This allows the policy to track the evolving reward function dynamically, collapsing the nested loops into a single, alternating update cycle.

3. Overparameterization and the NTK Regime

To overcome the non-convexity of neural networks, the authors analyze the algorithm within the "overparameterized" regime. By utilizing a sufficiently wide neural network, the model operates similarly to the Neural Tangent Kernel (NTK) regime. In this state, the neural network behaves like a linear model around its initialization, rendering the complex IRL objective function "approximately concave." This property is crucial for proving that gradient ascent can reach a global maximum.

Theoretical Results

The paper provides a rigorous non-asymptotic convergence analysis for the proposed algorithm. The authors establish a convergence rate of $O(K^{-1/8})$, indicating that the algorithm requires $O(\epsilon^{-8})$ steps to reach an $\epsilon$-stationary point.

Crucially, this work proves that as the neural network width ($m$) approaches infinity, the algorithm identifies the globally optimal reward and policy. This represents a significant milestone, as it is the first IRL algorithm to offer such guarantees for neural network-based reward functions.

Experimental Evaluation

The algorithm was evaluated using high-dimensional robotics benchmarks in the MuJoCo physics engine, including Hopper-v2, HalfCheetah-v2, Walker2d-v2, and Ant-v2. The experiments focused on the challenging limited data regime, where only a single expert trajectory was provided for training.

Performance Highlights

  • Superiority over Baselines: Single-Loop ML-IRL consistently outperformed state-of-the-art imitation learning methods such as GAIL, f-IRL, and IQ-Learn. For instance, in the Walker task, the proposed method achieved a score of ~5182, significantly higher than GAIL (~1023) and f-IRL (~4483).
  • Sample Efficiency: While traditional methods like Behavior Cloning (BC) often fail when data is scarce, the proposed method proved robust, successfully recovering high-performing policies from a single trajectory.

Discussion and Limitations

While this work bridges the gap between theoretical IRL and deep learning practice, certain limitations remain for future exploration:

  • Network Architecture: The current theoretical proof is centered on two-layer ReLU networks. Extending this analysis to deeper, more complex architectures is a logical next step.
  • Width Requirements: The global optimality guarantees rely on the assumption of extreme overparameterization. Investigating the performance and guarantees for finite-width or more compact networks would enhance practical applicability.
  • Convergence Constant: Although the $O(\epsilon^{-8})$ rate is a theoretical breakthrough for this setting, the high constant suggests that further refinements in the analysis may be possible to reflect the faster convergence often observed in practice.

Conclusion

This research presents a significant advancement in Inverse Reinforcement Learning by introducing a single-loop algorithm that is both computationally efficient and theoretically sound. By proving global optimality in the overparameterized neural network regime, the authors provide a rigorous foundation for using deep reward models in complex imitation learning tasks.

Summary updated

Abstract

The goal of the Inverse reinforcement learning (IRL) task is to identify the underlying reward function and the corresponding optimal policy from a set of expert demonstrations. While most IRL algorithms' theoretical guarantees rely on a linear reward structure, we aim to extend the theoretical understanding of IRL to scenarios where the reward function is parameterized by neural networks. Meanwhile, conventional IRL algorithms usually adopt a nested structure, leading to computational inefficiency, especially in high-dimensional settings. To address this problem, we propose the first two-timescale single-loop IRL algorithm under neural network parameterized reward and provide a non-asymptotic convergence analysis under overparameterization. Although prior optimality results for linear rewards do not apply, we show that our algorithm can identify the globally optimal reward and policy under certain neural network structures. This is the first IRL algorithm with a non-asymptotic convergence guarantee that provably achieves global optimality in neural network settings.
BibTeX
@inproceedings{zhang2025understanding,
  author = {Ruijia Zhang and Siliang Zeng and Chenliang Li and Alfredo García and Mingyi Hong},
  title = {{Understanding Inverse Reinforcement Learning under Overparameterization: Non-Asymptotic Analysis and Global Optimality}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2025},
  url = {https://openreview.net/forum?id=zEULQAAlnQ},
}
Figure