Inverse Reinforcement Learning in a Continuous State Space with Formal Guarantees

Gregory Dexter, Kevin Bello, Jean Honorio

Introduction

Reinforcement Learning (RL) relies heavily on a well-defined reward function to teach an agent how to behave. However, in complex real-world scenarios—such as autonomous driving or advanced robotics—manually defining a perfect reward function is notoriously difficult. Inverse Reinforcement Learning (IRL) addresses this by observing an expert's behavior and "back-calculating" the underlying reward function.

While IRL is well-understood and mathematically rigorous for discrete "grid-world" environments, the real world operates in continuous state spaces. Most existing continuous IRL methods rely on heuristics; they may work in practice, but they lack formal guarantees. Without these guarantees, it is impossible to know exactly how many samples are needed to succeed or if the algorithm will definitively find the true reward. This paper introduces a novel IRL algorithm for continuous state spaces that bridges this gap, providing formal theoretical guarantees on both correctness and sample complexity.

Methodology: Bridging Discrete and Continuous Spaces

The authors propose a framework that treats continuous functions as vectors in an infinite-dimensional space, allowing them to adapt the robust mathematical tools of discrete IRL to continuous environments.

  1. Orthonormal Basis Representation: The core innovation is modeling the reward function and the unknown transition dynamics using a basis of orthonormal functions (such as Fourier series or Legendre polynomials). This allows the system to represent complex, continuous transitions as "infinite matrices."
  2. Estimating Dynamics: Because the environment's transition dynamics are initially unknown, the algorithm first samples the environment to estimate the coefficients of these infinite matrices.
  3. Continuous IRL via Linear Programming: To find the reward, the authors formulate a Linear Program (LP). Since it is impossible to evaluate every single point in a continuous space, the algorithm utilizes a "covering set"—a finite grid of representative points.
Illustration of bounding a continuous function over a state space, demonstrating the covering set approach.

By assuming the functions are "smooth" (Lipschitz continuous), the authors prove that if the calculated reward is correct on this finite grid, it is mathematically guaranteed to be correct everywhere else in the continuous space.

Key Insights and Theoretical Guarantees

The paper introduces several critical theoretical insights for continuous IRL:

  • Sample Complexity: The authors provide a rigorous proof showing that the sample complexity of their algorithm is $O(k^2 \log \frac{k}{\delta})$, where $k$ is the size of the function representation (the truncation parameter) and $1-\delta$ is the probability of success. Remarkably, this matches the complexity bounds of the best-known algorithms for discrete state spaces.
  • Continuous $\beta$-Separability: The researchers adapt the concept of "separability" to continuous functions. Separability dictates that an expert's chosen action must be significantly better than the alternatives by a margin of $\beta$, which acts as a measure of the IRL problem's inherent difficulty.
  • The Importance of Smoothness: The formal guarantees rely heavily on the transition functions having bounded derivatives. If the environment's physics are highly discontinuous or "jittery," the number of samples required to learn the reward increases significantly.

Empirical Validation

Rather than benchmarking against standard RL datasets (like MuJoCo), the authors focused on synthetic experiments designed specifically to validate their theoretical bounds. They generated random IRL problems with polynomial transition functions to test the relationship between the number of samples ($n$), the truncation parameter ($k$), and the estimation error.

Observed estimation error versus theoretical sample bounds across different synthetic experiment settings.

The experiments confirmed that the theoretical bounds hold true in practice. In fact, the observed estimation error at fixed sample sizes consistently fell well below the conservative theoretical requirements, proving the algorithm's efficiency.

Limitations and Future Work

While this paper represents a significant theoretical leap, the authors note a few limitations:

  • Basis Selection: The algorithm's efficiency depends heavily on choosing an orthonormal basis that can represent the environment's transitions compactly. An inefficient basis choice means $k$ (the number of terms) must be very large, increasing computational cost.
  • Dimensionality and Decomposability: To avoid the "curse of dimensionality" in high-dimensional spaces (like a robotic arm with many joints), the method assumes the state space can be decomposed into independent sub-tasks. In highly coupled systems, complexity could still scale exponentially.
  • Real-World Application: The theory is robust, but the natural next step is applying this framework to high-fidelity simulators or real-world robotic tasks to evaluate its resilience to sensor noise and non-smooth physical transitions.

Summary updated

Abstract

Inverse Reinforcement Learning (IRL) is the problem of finding a reward function which describes observed/known expert behavior. The IRL setting is remarkably useful for automated control, in situations where the reward function is difficult to specify manually or as a means to extract agent preference. In this work, we provide a new IRL algorithm for the continuous state space setting with unknown transition dynamics by modeling the system using a basis of orthonormal functions. Moreover, we provide a proof of correctness and formal guarantees on the sample and time complexity of our algorithm. Finally, we present synthetic experiments to corroborate our theoretical guarantees.
BibTeX
@inproceedings{dexter2021inverse,
  author = {Gregory Dexter and Kevin Bello and Jean Honorio},
  title = {{Inverse Reinforcement Learning in a Continuous State Space with Formal Guarantees}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=A2CmhoQfWa},
}
Figure