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