Semi-Supervised Apprenticeship Learning

Michal Vaľko, Mohammad Ghavamzadeh, Alessandro Lazaric, Peter Deisenroth, Csaba Szepesvári, Jan Peters

TL;DR

This paper introduces Semi-Supervised Inverse Reinforcement Learning (SSIRL), a novel approach to apprenticeship learning that leverages unlabeled expert-like trajectories to learn a desired behavior more efficiently. By combining max-margin Inverse Reinforcement Learning (IRL) with semi-supervised Support Vector Machines (SVMs), SSIRL can discover better policies in fewer iterations, even when the unlabeled data doesn't perfectly align with the expert's true reward function.

What Problem Does This Paper Address?

Apprenticeship learning aims to teach an agent a desired behavior by observing an expert. A common approach, Inverse Reinforcement Learning (IRL), tries to infer the expert's underlying reward function from their demonstrated trajectories. However, traditional IRL often assumes access to a sufficient number of high-quality expert trajectories. This paper addresses a more realistic scenario where we have a few labeled expert trajectories but also a large number of unlabeled trajectories that might be "expert-like" but not necessarily optimal. The challenge is to effectively utilize these unlabeled trajectories to improve the learning process and find a better policy faster, without requiring them to be perfectly aligned with the expert's true reward.

Methods

The core contribution is the development of Semi-Supervised Inverse Reinforcement Learning (SSIRL). This method builds upon the max-margin IRL framework proposed by Abbeel and Ng (2004). The key innovation is the integration of semi-supervised Support Vector Machines (SVMs).

Here's a breakdown:

  • Max-Margin IRL (Abbeel & Ng, 2004): This method iteratively generates candidate policies and uses a max-margin classifier to find a reward function that separates expert feature expectations from the generated policies' feature expectations. The goal is to find a policy whose feature expectations are close to the expert's.
  • Semi-Supervised SVMs: SSIRL incorporates a "hat loss" from semi-supervised SVMs. This loss function penalizes classifiers that are too close to unlabeled data points, effectively encouraging the decision boundary to avoid dense regions of the feature space.
  • SSIRL Algorithm:
    1. It starts by estimating the expert's feature expectations ($\mu_E$) from the labeled expert trajectories.
  • It also estimates feature expectations ($\mu_U$) for the unlabeled trajectories.
  • The optimization problem is modified to include the unlabeled trajectories. The goal is to find a reward function ($w$) that not only separates expert trajectories from generated ones but also respects the clustering assumption in the feature space, guided by the unlabeled data.
  • An MDP solver is used to compute a new policy based on the learned reward function.
  • This process repeats, iteratively refining the reward function and generating better policies.

The crucial insight is that the unlabeled trajectories, even if not perfectly expert, can help guide the learning of the reward function by enforcing a separation in the feature space, especially when the "cluster assumption" (that data points with similar features belong to the same class) holds.

Datasets

The paper evaluates SSIRL on two domains:

  • Gridworld: A 64x64 gridworld with 4 actions and a 70% success rate. Features are defined based on macrocells. The rewards are randomly generated to encourage sparse and interesting policies.
  • Two Goals Navigation: A more naturalistic domain with a starting point, two goals ("A" and "B"), and a river with a bridge. Features are defined similarly to the gridworld. The reward function is designed to encourage reaching goal "A" while penalizing the river.

For both domains, the authors simulate trajectories by sampling different reward functions for the expert and non-expert performers. This allows them to control the number of labeled and unlabeled trajectories and to simulate scenarios where unlabeled trajectories might not perfectly match the expert's true reward.

Key Insights and Ideas

  • Unlabeled data can accelerate learning: The core idea is that unlabeled trajectories, even if imperfect, can provide valuable structural information about the desired behavior, helping to guide the reward inference process more quickly.
  • Leveraging the cluster assumption: SSIRL relies on the assumption that trajectories with similar feature expectations tend to belong to the same class (expert or non-expert). This assumption is key to how semi-supervised learning effectively uses unlabeled data.
  • Discovering better policies earlier: SSIRL has the potential to discover a better performing policy than standard IRL, even if it doesn't perfectly match the expert's feature counts in the early stages. This is because the unlabeled data can help find a more accurate reward function sooner.
  • Robustness to noisy unlabeled data: The experiments suggest that SSIRL can handle unlabeled trajectories that are not perfectly aligned with the expert's true reward, which is a significant practical advantage.

Key Results

  • Faster convergence: In gridworld experiments, SSIRL consistently found better policies than standard IRL after a fixed number of iterations, especially when more unlabeled trajectories were provided.
  • Improved performance: Figures 4.2 and 4.3 show that SSIRL achieved higher performance under the true reward function compared to IRL, particularly in the early stages of learning.
  • Potential for discovering superior policies: Figure 4.3 demonstrates that SSIRL can, in some cases, discover a policy that performs even better than the optimal policy derived from the true reward function, at least in the initial iterations. This is attributed to the influence of unlabeled data helping to find a more accurate reward function.
  • Effectiveness across domains: Similar improvements were observed in the "Two Goals Navigation" domain (Figures 4.4 and 4.5), indicating the generalizability of the SSIRL approach.

Limitations and Future Work

  • Cluster Assumption: The effectiveness of SSIRL is contingent on the cluster assumption holding in the feature space of the trajectories. If this assumption is violated, unlabeled data might not be helpful or could even be detrimental.
  • Linear Reward Assumption: Like many IRL methods, SSIRL assumes a linear reward function in the state features.
  • Mixture Policy Output: The algorithm, like its IRL predecessor, can output a mixture of policies rather than a single, unified policy.
  • Stopping Criterion: The stopping criterion for IRL (closeness to expert trajectory in feature space) is not directly applicable to SSIRL because the unlabeled trajectories' feature counts cannot be used for this purpose.
  • Future Work: The authors plan to extend SSIRL to other IRL methods like max-margin planning and maximum entropy IRL. They also intend to investigate the use of manifold assumptions in semi-supervised learning for further enhancements.

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{valko2012semi,
  author = {Michal Vaľko and Mohammad Ghavamzadeh and Alessandro Lazaric and Peter Deisenroth and Csaba Szepesvári and Jan Peters},
  title = {{Semi-Supervised Apprenticeship Learning}},
  booktitle = {EWRL},
  year = {2012},
  url = {https://openreview.net/forum?id=n0BHVlRayp-},
}
Figure