Apprenticeship Learning via Inverse Reinforcement Learning

Pieter Abbeel and Andrew Y. Ng address tasks whose reward tradeoffs are difficult to specify, using expert demonstrations instead. Their ICML 2004 paper builds on Algorithms for Inverse Reinforcement Learning, but shifts the aim from recovering the true reward to performing comparably under it. A learner can reproduce the relevant consequences of a policy without identifying why the demonstrator chose it.^[1]

Feature expectations and the performance bound

The setup supplies an MDP’s transitions, discount factor and initial-state distribution, but withholds its reward. Reward is assumed to be a weighted sum of known features, each bounded between 0 and 1; the sum of the absolute true weights is at most 1. The discount factor is less than 1. A policy’s feature expectations are its expected totals of these features over time, with later observations discounted. Expected return is the dot product of reward weights and feature expectations (section 2).^[1]

This gives the central bound: if the Euclidean distance between the learner’s and expert’s feature-expectation vectors is at most ε, their expected discounted returns differ by at most ε for every reward in the specified normalized class. Both expectations use the same initial-state distribution and environment. The expert need not be optimal: the comparison is to its performance, not necessarily the best achievable performance.^[1]

The algorithm alternates between finding weights that distinguish the expert from policies already found, and solving the corresponding reinforcement-learning problem to generate another policy. The max-margin version uses quadratic programming; a projection version avoids that solver. The paper assumes an optimal RL solver for its exposition. On termination, one can inspect candidate policies or construct a mixture whose feature expectations approach the expert’s. A mixture chooses a constituent policy once at the start of a trajectory, rather than switching randomly at every action. The result does not make every intermediate policy good.^[1]

Section 4 separately treats finite demonstrations. Its sufficient trajectory count grows with the feature count and inverse squared accuracy and discount gap, with a logarithmic confidence term. The guarantee is probabilistic and depends on sampled feature estimates, the reward representation and the planning assumptions. It does not learn the transition dynamics from demonstrations or establish performance outside the modeled environment.^[1]

Gridworld and simulated driving

The gridworld experiments use 128-by-128 grids divided into 64 macrocells, with sparse randomly generated rewards, discount 0.99, a uniform start distribution and 30% random movement. Figure 3 compares convergence using exact expert feature expectations over 40 runs. Figure 4 averages 20 instances and varies the number of sampled expert trajectories; its performance measure is the best policy in the returned set. One variant is additionally told which macrocell features have nonzero reward. These conditions matter when interpreting the reported advantage over simple action-imitation baselines.^[1]

In highway simulation, the car travels at a fixed 25 m/s and chooses among three lanes or either roadside. Each of five styles is demonstrated by an author for two minutes: a single 1,200-sample trajectory at 10 Hz. Features describe lane position and distance to another car. Styles include avoiding collisions, deliberately hitting cars, and staying in the middle lane regardless of collisions. After 30 iterations, a policy is selected by inspection. The algorithm qualitatively imitates these styles; Table 1 compares estimated feature expectations and fitted weights. No true driving reward is specified, so the experiment does not measure return under an independently known reward.^[1]

For AI Alignment, the distinction is consequential: a guarantee about matching a demonstrator under chosen features can faithfully reproduce undesirable behavior. Selecting the features, the demonstrator and the task’s acceptable objectives remains a separate responsibility. The paper establishes a conditional route to imitation performance, not real-world driving safety or the moral legitimacy of the behavior learned.