Maximum Entropy Semi-Supervised Inverse Reinforcement Learning

1 Introduction

• Expert demonstrations offer a way to learn tasks when desirable factors make it difficult to specify an explicit reward function and their trade-offs.The introduction frames apprenticeship learning as learning from an expert’s behavior.Source: §1 · p. 1
• Expected feature-count matching can leave many policies eligible, motivating MaxEnt-IRL’s use of maximum entropy to resolve the ambiguity.The paper builds on Ziebart et al. (2008).Source: §1 · p. 1
• Unsupervised trajectories may come from experts, near-experts, different reward functions, or noisy data, rather than a simple expert/non-expert mixture.The paper therefore treats this as semi-supervised apprenticeship learning, not semi-supervised classification.Source: §1 · pp. 1–2
• MESSI combines MaxEnt-IRL with semi-supervised learning, using unsupervised trajectories to improve performance over MaxEnt-IRL.The paper reports empirical improvement in the highway-driving problem.Source: §1 · p. 2
• The introduction identifies problems with SSIRL: it labels generated policies as bad, relies on a cluster assumption, and lacks a stopping criterion.The authors say its performance eventually reverts to that of Abbeel and Ng (2004).Source: §1 · p. 2

2 Background and Notations

• An MDP is defined by state and action spaces, a state-reward function, and dynamics giving transition probabilities between states.A policy maps states to distributions over actions.Source: §2 · p. 2
• The reward is linear in state features, and a trajectory’s feature count sums those features over its visited states.For binary features, a feature count records how often the trajectory visits states activating that feature.Source: §2 · p. 2
• Expected feature-count matching seeks a policy whose trajectory distribution has the same expected feature count as the expert’s.The expert’s expected feature count summarizes which features are often visited and implicitly reveals preferences.Source: §2 · p. 2
• Because many policies can satisfy feature-count matching, MaxEnt-IRL assigns trajectory probabilities according to accumulated reward and a normalization constant.The algorithm searches for a reward vector that maximizes the likelihood of expert trajectories.Source: §2 · p. 2
• The resulting reward-induced trajectory distribution matches the expert’s expected feature count while favoring trajectories that achieve reward.In practice, trajectories need not include actions; states suffice.Source: §2 · pp. 2–3

3 Maximum Entropy Semi-Supervised Inverse Reinforcement Learning

• MESSI adds locally consistent trajectory probabilities to MaxEnt-IRL rather than reducing apprenticeship learning to supervised classification.The section identifies a clustering assumption in prior semi-supervised work that can fail as generated policies become more similar to the expert.Source: §3 · p. 3

Pairwise Penalty and Similarity Function

• The pairwise penalty discourages large reward differences between similar trajectories while allowing dissimilar trajectories to receive different rewards.It applies to expert and unsupervised trajectories and uses their feature counts and a supplied similarity function.Source: Pairwise Penalty and Similarity Function · p. 3
• Similarity choice encodes which trajectory characteristics should be shared; hand-crafted functions usually perform better, while an RBF kernel is also effective for feature counts.When prior knowledge is limited, the paper recommends a generic similarity with small generalization across trajectories.Source: Pairwise Penalty and Similarity Function · p. 3
• MESSI optimizes expert-trajectory likelihood minus a weighted pairwise penalty, with λ trading off likelihood and similarity coherence.The algorithm uses gradient descent to solve this objective.Source: Pairwise Penalty and Similarity Function · p. 3, Implementation of the Algorithm · p. 4
• MESSI’s regularization depends on both the similarity function and the distribution of unsupervised trajectories; adversarial data can worsen performance.The penalty is expected to be more effective when trajectories likely under the expert’s reward are represented among the unsupervised data.Source: Pairwise Penalty and Similarity Function · pp. 3–4

Implementation of the Algorithm

• Each iteration computes expected feature counts from the reward-induced policy and updates the reward vector toward the expert’s average feature counts.Expected counts are calculated from state visitation frequencies; computing the policy and visitation frequencies uses backward and forward passes.Source: Implementation of the Algorithm · p. 4
• The backward pass is MESSI’s main computational bottleneck; approximate dynamic programming such as fitted value iteration can reduce complexity and remove the need for exact MDP dynamics.Feature normalization and discounting bound feature counts, while a constraint on the reward-vector norm helps prevent numerical instability.Source: Implementation of the Algorithm · p. 4

Experimental setup

• Unsupervised data came from near-expert, random, or alternative-reward mixtures; MESSIMAX uses expert-distributed trajectories as an upper bound on attainable MESSI performance.The comparison also includes an EM-MaxEnt-inspired semi-supervised baseline.Source: §4 · p. 5
• The evaluation averages 50 runs and includes a four-lane highway task scored as minus expected collisions and off-roads, alongside grid-world problems.The highway expert stays on the left while avoiding collisions and off-road driving.Source: §4 · p. 5

Number of iterations

• Relevant unsupervised data lets MESSI and MESSIMAX improve over MaxEnt-IRL; mismatched Pµ3 performs worse, and further iterations eventually yield little gain.MaxEnt-IRL may overfit and degrade after its reward reaches the norm constraint.Source: Figure 1 · p. 5, §4 · p. 6

Number of unsupervised trajectories

• More unsupervised trajectories generally improve performance and generalization, but gains may saturate; with Pµ3, additional trajectories instead worsen performance.Pµ3 trajectories provide no information about expert behavior.Source: Figure 1 · p. 5, §4 · p. 6

Proportion of good unsupervised trajectories

• ν ≥ 0.15 marks where MESSI with Pµ1 and Pµ2 begins outperforming MaxEnt-IRL; at ν = 1, MESSI and MESSIMAX coincide.With completely non-relevant trajectories, MESSI may perform worse, though the decrease is often negligible when the distribution sufficiently supports the expert distribution.Source: Figure 1 · p. 5, §4 · p. 6

Parameter λ

• A λ that is too small makes regularization negligible, while a λ that is too large can over-smooth rewards and reduce MESSI and MESSIMAX performance.This is described as a semi-supervised learning trade-off.Source: Figure 1 · p. 5, §4 · p. 6

Comparison to η-EM-MaxEnt

• η-EM-MaxEnt trails MESSI except at a few iterations; inaccurate reward-based trajectory probabilities amplify errors as unlikely unsupervised paths enter training.MESSI can be stopped at any iteration because its performance increases monotonically; η-EM-MaxEnt's policy quality cannot be directly evaluated for such a choice.Source: Figure 2 · p. 5, §4 · p. 6

Results

• When unsupervised trajectories carry useful structural information, MESSI outperforms MaxEnt-IRL; with none useful, it performs slightly worse, while partial support ν ≥ 0.15 suffices for significant gains.The supported cases include suboptimal expert behavior and incomplete expert information.Source: §4 · p. 6

• MESSI combines MaxEnt-IRL with semi-supervised learning through a pairwise penalty on trajectories.Source: §5 · p. 6
• Empirical results show MESSI can take advantage of unsupervised trajectories and perform better and more efficiently than MaxEnt-IRL.Source: §5 · p. 6
• The paper reports that MESSI does not suffer from the disadvantages of SSIRL, the other semi-supervised apprenticeship-learning algorithm it identifies.Source: §5 · p. 6
• Future directions include other ways to use unsupervised trajectories, alternative trajectory similarities such as the Fisher kernel, and settings with multiple experts.Source: §5 · p. 6

• Russell (1998) defined IRL as finding a reward from observed trajectories, while Ng and Russell (2000) identified degenerate solutions and introduced linear rewards over features, still a common assumption.Source: A Related Work · p. 8
• Abbeel and Ng (2004) and other max-margin methods match expert feature counts by making deviations from the expert policy costly.Source: A Related Work · p. 8
• MaxEnt-IRL uses maximum entropy to address ambiguity in matching expert feature counts, and related methods build on that idea.Source: A Related Work · p. 8
• Other apprenticeship-learning approaches avoid repeated forward RL, use access to the expert policy, or address scarce demonstrations; SSIRL combines Abbeel and Ng’s IRL with semi-supervised SVMs.Source: A Related Work · p. 8
• Unlike SSIRL, this paper’s approach does not heavily rely on the cluster assumption; SSIRL eventually converges to the supervised case, and its objective is non-convex and difficult to optimize.Source: A Related Work · p. 8

• The additional empirical results mostly confirm the findings reported in the main paper.Source: B Additional Experiments · p. 8

• Grid-world results vary with iterations, unsupervised-trajectory count, ν, and λ; a separate comparison pits MESSI and MESSIMAX against iterative η-EM-MaxEnt at η = 1, 5, 10, 20, and 50.Source: Figure 3 · p. 8, Figure 4 · p. 8
• The 16 × 16 grid has four actions, 70% success and 30% random different-action transitions, with 64 2 × 2 macrostates defining the features.Source: The Grid-world Problem · p. 8
• Policy performance is measured by expected reward under the true reward, and trajectory similarity uses an RBF kernel that does not exploit prior problem knowledge.Source: The Grid-world Problem · p. 9

The Pit Problem

• With an informative similarity function, MESSI significantly outperforms MaxEnt-IRL on the pit problem.The results vary with algorithm iterations, unsupervised-trajectory count, ν, and λ.Source: Figure 6 · p. 9, The Pit Problem · p. 9
• The experiment uses a 6×6 grid with three features and one expert trajectory that goes around the pit counter-clockwise.The agent moves from (1, 1) to (6, 6) while avoiding the pit.Source: The Pit Problem · p. 9
• Unsupervised trajectories mix pit-avoiding and pit-crossing policies; performance is measured by how frequently the learned policy crosses the pit.The hand-crafted similarity compares trajectories by their number of direction changes.Source: The Pit Problem · p. 9