Classification structurée pour l'apprentissage par renforcement inverse

Edouard Klein, Bilal Piot, Geist, Matthieu, Olivier Pietquin

Abstract

This paper, originally presented at the 2012 Conférence Francophone sur l'Apprentissage Automatique (CAp), introduces a novel approach to Inverse Reinforcement Learning (IRL). By framing IRL as a structured classification task, the authors circumvent the primary computational bottleneck of traditional methods: the requirement to repeatedly solve the "forward" reinforcement learning problem. The proposed batch-mode algorithm utilizes structured risk minimization and sub-gradient descent to recover reward functions from expert trajectories. Experimental results on the inverted pendulum benchmark demonstrate that the method is both efficient and robust, even when provided with limited and highly localized expert data.

Introduction

In the field of Reinforcement Learning (RL), an agent typically learns to optimize its behavior based on a predefined reward signal. However, in many complex real-world scenarios, defining an appropriate reward function is difficult. Inverse Reinforcement Learning (IRL) addresses this by observing an expert's behavior and inferring the underlying reward function being optimized. This process is central to "Apprenticeship Learning."

Traditional IRL algorithms, such as those proposed by Abbeel and Ng, are inherently iterative. They guess a reward function, solve the forward RL problem to find an optimal policy, compare that policy to the expert's behavior, and adjust the reward accordingly. This loop is computationally expensive and often impractical, as solving the forward problem requires extensive interaction with a simulator or complete knowledge of environment dynamics. This paper proposes a "batch" approach that learns directly from expert traces without the need for repeated forward optimization.

Methodology: IRL as Structured Classification

The authors re-envision IRL as a structured multi-class classification problem. This transformation relies on several key technical components:

1. Feature Expectations and Reward Linearization

The reward function is assumed to be a linear combination of features: $R(s, a) = \theta^T \phi(s, a)$. This allows the value of a policy (or the Q-value of an action) to be expressed as the dot product between a weight vector $\theta$ and the "feature expectations" ($\mu^\pi$). These expectations represent the discounted sum of features an agent expects to encounter in the future under policy $\pi$.

2. Structured Risk Minimization

The core of the classification approach is the definition of an empirical risk function, $J_N(\theta)$. This function penalizes the model if the expert's chosen actions do not outperform alternative actions by a specific margin. This formulation is closely related to the loss functions used in Structured Support Vector Machines (SSVMs). By minimizing this risk, the algorithm finds a weight vector $\theta$ that makes the expert's behavior appear optimal.

3. Optimization via Sub-gradient Descent

To find the optimal reward weights, the authors employ a normalized sub-gradient descent algorithm. This iterative process converges rapidly, typically requiring far fewer iterations than traditional IRL loops.

4. Pure Batch Mode with LSTD$\mu$

To estimate the expert's feature expectations from raw trajectory data without a transition model, the authors utilize the LSTD$\mu$ algorithm. This enables the method to operate in a pure batch mode, relying solely on the provided expert trajectories rather than active environment exploration.

Experimental Evaluation

The algorithm was tested on the classic Inverted Pendulum (pendule inversé) benchmark. The objective is to maintain a pendulum in a vertical position through discrete torque applications.

Data and Constraints

The expert data consisted of only 10 trajectories, totaling 3,000 transitions. A significant challenge in this dataset is its limited coverage; because the expert is proficient, the pendulum remains near the vertical axis. Consequently, the agent never observes "bad" states where the pendulum is falling rapidly. This "off-policy" nature of the data makes it difficult for standard imitation learning methods to generalize.

Results and Insights

Despite the limited state-space coverage, the agent trained on the recovered reward function successfully balanced the pendulum for the entire 5-minute test duration (3,000 steps). The algorithm demonstrated remarkable efficiency, converging in just 20 iterations of sub-gradient descent.

An important observation made by the authors is the "ill-posed" nature of IRL. The reward function recovered by the algorithm often looked visually different from the "true" reward used to generate the expert data. However, the resulting value functions were nearly identical, and the learned policy achieved perfect performance. This suggests that multiple reward functions can support the same optimal behavior, and the structured classification approach effectively identifies a valid candidate.

Conclusion and Future Work

This research provides a significant step toward making IRL more practical for real-world applications. By decoupling the reward inference from the forward RL problem, the authors have created a method that is both computationally efficient and capable of learning from limited, localized datasets.

Future work may involve refining the estimation of feature expectations. The current reliance on LSTD$\mu$ means that the algorithm's success is tied to the quality of the chosen basis functions and the accuracy of the expectation estimates. Exploring ways to integrate MDP structure directly into the classification process without intermediate feature expectations could further enhance the robustness of this structured classification framework.

Summary updated

Abstract

http://cap2012.loria.fr/pub/Papers/13.pdf
BibTeX
@inproceedings{klein2012classification,
  author = {Edouard Klein and Bilal Piot and Geist, Matthieu and Olivier Pietquin},
  title = {{Classification structurée pour l'apprentissage par renforcement inverse}},
  booktitle = {HAL},
  year = {2012},
}
Figure