Inverse Reinforcement Learning in Relational Domains

Thibaut Munzer, Bilal Piot, Matthieu Geist, Olivier Pietquin, Manuel Lopes

Introduction

Presented at IJCAI 2015, this research marks a significant milestone in apprenticeship learning by bridging the gap between Inverse Reinforcement Learning (IRL) and Relational Learning. The authors introduce a framework that allows an agent to go beyond simple mimicry, enabling it to understand the underlying "why" (the reward function) in complex environments where the number of objects can vary dynamically.

The RCSI Framework

Most traditional IRL algorithms are "propositional," assuming a fixed environment with a set number of features. These systems fail when the state-space dimensions change—for example, moving from a 4-block to a 5-block stacking task. To address this, the authors developed Relational Cascaded Supervised IRL (RCSI), the first IRL algorithm designed for relational domains.

The RCSI process follows three primary stages to recover a compact, logic-based reward function:

  1. Relational Score-Based Classification (SBC): The algorithm utilizes TBRIL (Tree Boosted Relational Imitation Learning) to learn a "score" for actions from expert demonstrations, effectively turning imitation into a classification problem.
  2. Reward Shaping: A key contribution of this work is an intermediate optimization step using CMA-ES. This process finds a potential function that makes the resulting reward signal "simpler" (lower entropy), facilitating more accurate learning in the final stage.
  3. Relational Regression: Finally, the algorithm uses TILDE (a relational decision tree learner) to map the shaped scores back to a compact reward function expressed in first-order logic (e.g., "The reward is 1 if clear(X) is true for only one block").
The three-step RCSI process: score-based classification, reward shaping, and relational regression.

Experimental Evaluation and Generalization

The primary evaluation was conducted in the Blocks World domain, focusing on "Stack" and "Unstack" tasks. The power of the relational approach is most evident in its generalization capabilities. Agents were trained on small sets (4–5 blocks) and tested on up to 15 blocks. While a 5-block world has 501 states, a 15-block world contains approximately $6.6 \times 10^{13}$ states.

Key Results

  • Transfer Performance: RCSI achieved an Optimal Actions Count (OAC) and Mean Value Ratio (MVR) of over 0.98 in a 15-block world after training on only 4 and 5 blocks. This demonstrates that the agent successfully captured the "essence" of the task rather than just memorizing trajectories.
  • The Power of Diversity: Training on a mix of domain sizes (e.g., combining 4-block and 5-block examples) significantly improved the agent's ability to transfer knowledge to larger, unseen environments.
  • Robustness: Unlike pure imitation learners (like TBRIL), which are brittle when environment dynamics change (e.g., a block becomes unmovable), RCSI agents can use their understanding of the goal to re-plan and succeed.
Performance comparison and generalization results (MVR) across different training and testing block configurations.

Conclusion

RCSI demonstrates that recovering logic-based rewards allows for remarkable scalability and interpretability. Instead of a massive table of numbers, the output is a small, human-readable decision tree. While the system currently relies on human-provided predicates, it sets the stage for future work in active learning and the automated discovery of symbolic representations from raw sensor data.

Summary updated

Abstract

HAL is a multi-disciplinary open access archive for the deposit and dissemination of sci-entific research documents, whether they are pub-lished or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers. L’archive ouverte pluridisciplinaire HAL, est destinée au dépôt et a ̀ la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d’enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.
BibTeX
@inproceedings{munzer2015inverse,
  author = {Thibaut Munzer and Bilal Piot and Matthieu Geist and Olivier Pietquin and Manuel Lopes},
  title = {{Inverse Reinforcement Learning in Relational Domains}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
  url = {https://openreview.net/forum?id=HvhpkUg9El8},
}
Figure