Apprenticeship Learning via Inverse RL

Why Does This Exist?

When training autonomous systems from human demonstrations—such as robotic aerobatics, autonomous driving, or robotic surgery—two classical paradigms fail in distinct ways:

1. Behavioral Cloning (Supervised Imitation): Direct supervised learning fits a policy $\pi(a \mid s)$ directly to state-action pairs $(s, a)$ demonstrated by an expert. However, compounding temporal errors cause covariate shift: a minor steering mistake at time step $t$ moves the vehicle into unfamiliar states never visited by the human driver. In these unvisited states, the policy makes larger errors, leading to quadratic error growth $\mathcal{O}(T^2)$ and catastrophic failure.
2. Standard Inverse Reinforcement Learning (IRL): Classic IRL attempts to recover the unknown reward function $R^*(s)$ that made the expert's trajectory optimal. But recovering the true reward is fundamentally ill-posed and underdetermined: an infinite family of reward functions (including degenerate constants like $R(s) = 0$) can make any demonstrated policy optimal.

Pieter Abbeel and Andrew Ng (2004) resolved this impasse with Apprenticeship Learning via Inverse Reinforcement Learning. They asked a foundational question: Do we actually need to uncover the expert's true reward function $R^*(s)$ to match their performance?

Their answer was no. Under the mild assumption that rewards are linear combinations of known state features $R(s) = w^\top \phi(s)$, an agent does not need to identify the true weight vector $w^*$. Instead, if the apprentice can find a policy that matches the expert's long-term discounted feature expectations within a tolerance $\epsilon$, the Cauchy-Schwarz inequality guarantees that the apprentice's performance will be within $\epsilon$ of the expert's performance across any possible underlying reward weight vector.

Think of It Like This

How It Actually Works

The Feature Expectation Formulation and Performance Guarantee

Consider a Markov Decision Process without a predefined reward function, denoted $\text{MDP}\setminus R = (\mathcal{S}, \mathcal{A}, P, \gamma, D)$, where $\mathcal{S}$ is the state space, $\mathcal{A}$ is the action space, $P(s' \mid s, a)$ represents transition dynamics, $\gamma \in [0, 1)$ is the discount factor, and $D$ is the initial state distribution.

We assume a known feature mapping $\phi: \mathcal{S} \to [0, 1]^k$ such that $\|\phi(s)\|_2 \le 1$. The true environmental reward is assumed to be linear in these features:

For any policy $\pi$, we define the discounted feature expectation vector $\mu(\pi) \in \mathbb{R}^k$ as:

Given an empirical demonstration dataset of $m$ expert trajectories $\mathcal{D}_E = \{\tau^{(1)}, \dots, \tau^{(m)}\}$, the expert's feature expectations are estimated empirically:

The total expected discounted return of any policy $\pi$ under reward weights $w$ is a linear inner product:

This formulation yields the Fundamental Apprenticeship Performance Guarantee:

If the learning agent discovers a policy $\tilde{\pi}$ satisfying $\|\mu(\tilde{\pi}) - \mu_E\|_2 \le \epsilon$, then for any true weight vector $w$ with $\|w\|_2 \le 1$, the return gap is strictly bounded:

The agent achieves near-optimal expert performance without ever identifying the true reward parameters $w^*$.

The Projection Algorithm

To find a policy whose feature expectations match $\mu_E$, Abbeel and Ng introduced two iterative algorithms: the Max-Margin algorithm (which solves a support vector machine quadratic program) and the more computationally efficient Projection Algorithm.

The Projection Algorithm maintains the convex hull of feature expectations discovered by the learner's previous policies, $\text{conv}(\mu^{(0)}, \mu^{(1)}, \dots, \mu^{(i)})$, and iteratively projects $\mu_E$ onto this hull:

1. Initialization: Run an arbitrary initial policy $\pi^{(0)}$ (e.g., uniform random) to compute feature expectation $\mu^{(0)}$. Set $\bar{\mu}^{(0)} = \mu^{(0)}$.
2. Compute Separating Hyperplane: At iteration $i$, compute the vector from the current convex hull projection $\bar{\mu}^{(i-1)}$ toward the expert: $$w^{(i)} = \mu_E - \bar{\mu}^{(i-1)}$$
3. Check Termination: Compute the margin $t^{(i)} = \|w^{(i)}\|_2$. If $t^{(i)} \le \epsilon$, terminate.
4. Forward RL Inner Loop: Normalize candidate weights $\hat{w}^{(i)} = w^{(i)} / \|w^{(i)}\|_2$. Train an RL agent to find the optimal policy $\pi^{(i)}$ for reward function: $$R^{(i)}(s) = (\hat{w}^{(i)})^\top \phi(s)$$
5. Evaluate New Features: Compute $\mu^{(i)} = \mu(\pi^{(i)})$.
6. Update Convex Projection: Project $\mu_E$ onto the line segment connecting $\bar{\mu}^{(i-1)}$ and $\mu^{(i)}$: $$\bar{\mu}^{(i)} = \bar{\mu}^{(i-1)} + \beta \left(\mu^{(i)} - \bar{\mu}^{(i-1)}\right)$$ where $\beta$ is computed via orthogonal projection and clipped to $[0, 1]$: $$\beta = \text{clip}\left( \frac{(\mu^{(i)} - \bar{\mu}^{(i-1)})^\top (\mu_E - \bar{\mu}^{(i-1)})}{\|\mu^{(i)} - \bar{\mu}^{(i-1)}\|_2^2}, 0, 1 \right)$$
7. Iterate: Repeat steps 2–6 until $t \le \epsilon$.

Abbeel and Ng proved that this algorithm converges in at most $\mathcal{O}\left(\frac{k}{(1 - \gamma)^2 \epsilon^2} \log \frac{k}{(1 - \gamma) \epsilon}\right)$ iterations, where $k$ is the feature dimension.

Worked numerical example

Let the state feature dimension be $k = 2$. The expert's feature expectation vector is:

Our convergence threshold is $\epsilon = 0.10$.

Iteration 0: Baseline Policy

1. An initial random policy $\pi^{(0)}$ yields feature expectation: $$\mu^{(0)} = \begin{bmatrix} 0.20 \\ 0.20 \end{bmatrix}$$
2. The initial convex projection point is $\bar{\mu}^{(0)} = \mu^{(0)} = [0.20, 0.20]^\top$.
3. Difference vector: $$w^{(1)} = \mu_E - \bar{\mu}^{(0)} = \begin{bmatrix} 0.80 - 0.20 \\ 0.60 - 0.20 \end{bmatrix} = \begin{bmatrix} 0.60 \\ 0.40 \end{bmatrix}$$
4. Initial margin: $$t^{(0)} = \|w^{(1)}\|_2 = \sqrt{0.60^2 + 0.40^2} = \sqrt{0.36 + 0.16} = \sqrt{0.52} \approx 0.7211$$ Since $0.7211 > 0.10$, the algorithm continues.
5. Normalized candidate reward vector: $$\hat{w}^{(1)} = \frac{w^{(1)}}{\|w^{(1)}\|_2} = \begin{bmatrix} 0.60 / 0.7211 \\ 0.40 / 0.7211 \end{bmatrix} \approx \begin{bmatrix} 0.8321 \\ 0.5547 \end{bmatrix}$$

Iteration 1: First RL Inner Loop

1. The forward RL solver optimizes $R(s) = 0.8321 \phi_1(s) + 0.5547 \phi_2(s)$, returning policy $\pi^{(1)}$ with feature expectation: $$\mu^{(1)} = \begin{bmatrix} 0.55 \\ 0.35 \end{bmatrix}$$
2. Direction vector along the line segment: $$v_1 = \mu^{(1)} - \bar{\mu}^{(0)} = \begin{bmatrix} 0.55 - 0.20 \\ 0.35 - 0.20 \end{bmatrix} = \begin{bmatrix} 0.35 \\ 0.15 \end{bmatrix}$$
3. Projection scalar $\beta_1$: $$v_1^\top (\mu_E - \bar{\mu}^{(0)}) = (0.35 \times 0.60) + (0.15 \times 0.40) = 0.210 + 0.060 = 0.270$$ $$\|v_1\|_2^2 = 0.35^2 + 0.15^2 = 0.1225 + 0.0225 = 0.1450$$ $$\beta_1 = \frac{0.270}{0.1450} \approx 1.8621 \implies \text{clipped to } 1.0$$
4. Since $\beta_1$ is clipped to $1.0$, the closest point on the segment is the endpoint: $$\bar{\mu}^{(1)} = \mu^{(1)} = \begin{bmatrix} 0.55 \\ 0.35 \end{bmatrix}$$
5. New difference vector: $$w^{(2)} = \mu_E - \bar{\mu}^{(1)} = \begin{bmatrix} 0.80 - 0.55 \\ 0.60 - 0.35 \end{bmatrix} = \begin{bmatrix} 0.25 \\ 0.25 \end{bmatrix}$$
6. New margin: $$t^{(1)} = \|w^{(2)}\|_2 = \sqrt{0.25^2 + 0.25^2} = \sqrt{0.0625 + 0.0625} = \sqrt{0.125} \approx 0.3536$$ The margin has shrunk from $0.7211 \to 0.3536$.
7. Normalized candidate reward vector: $$\hat{w}^{(2)} = \frac{w^{(2)}}{\|w^{(2)}\|_2} = \begin{bmatrix} 0.25 / 0.3536 \\ 0.25 / 0.3536 \end{bmatrix} \approx \begin{bmatrix} 0.7071 \\ 0.7071 \end{bmatrix}$$

Iteration 2: Second RL Inner Loop

1. The forward RL solver optimizes $R(s) = 0.7071 \phi_1(s) + 0.7071 \phi_2(s)$, returning policy $\pi^{(2)}$ with feature expectation: $$\mu^{(2)} = \begin{bmatrix} 0.75 \\ 0.52 \end{bmatrix}$$
2. Direction vector along segment $[\bar{\mu}^{(1)}, \mu^{(2)}]$: $$v_2 = \mu^{(2)} - \bar{\mu}^{(1)} = \begin{bmatrix} 0.75 - 0.55 \\ 0.52 - 0.35 \end{bmatrix} = \begin{bmatrix} 0.20 \\ 0.17 \end{bmatrix}$$
3. Projection scalar $\beta_2$: $$v_2^\top (\mu_E - \bar{\mu}^{(1)}) = (0.20 \times 0.25) + (0.17 \times 0.25) = 0.050 + 0.0425 = 0.0925$$ $$\|v_2\|_2^2 = 0.20^2 + 0.17^2 = 0.0400 + 0.0289 = 0.0689$$ $$\beta_2 = \frac{0.0925}{0.0689} \approx 1.3425 \implies \text{clipped to } 1.0$$
4. The projection updates to the endpoint: $$\bar{\mu}^{(2)} = \mu^{(2)} = \begin{bmatrix} 0.75 \\ 0.52 \end{bmatrix}$$
5. New difference vector: $$w^{(3)} = \mu_E - \bar{\mu}^{(2)} = \begin{bmatrix} 0.80 - 0.75 \\ 0.60 - 0.52 \end{bmatrix} = \begin{bmatrix} 0.05 \\ 0.08 \end{bmatrix}$$
6. New margin: $$t^{(2)} = \|w^{(3)}\|_2 = \sqrt{0.05^2 + 0.08^2} = \sqrt{0.0025 + 0.0064} = \sqrt{0.0089} \approx 0.0943$$
7. Because $t^{(2)} = 0.0943 \le \epsilon = 0.10$, the algorithm terminates.

By the performance guarantee, the expected return gap between policy $\pi^{(2)}$ and the expert is bounded:

The apprentice is guaranteed to perform within $0.0943$ return units of the expert under any arbitrary linear combination of features.

Code

The following type-hinted implementation demonstrates the Abbeel & Ng Projection Algorithm, performing iterative convex projection, candidate reward weight calculation, and margin tracking.

1from typing import List2import numpy as np3
4
5class ApprenticeshipLearningProjection:6    """7    Abbeel & Ng (2004) Projection Algorithm for Apprenticeship Learning.8    Matches feature expectations between learner and expert via iterative projection.9    """10
11    def __init__(self, mu_expert: np.ndarray, epsilon: float = 0.10) -> None:12        self.mu_expert = np.asarray(mu_expert, dtype=np.float64)13        self.epsilon = epsilon14        self.history_mu: List[np.ndarray] = []15        self.history_w: List[np.ndarray] = []16        self.history_margins: List[float] = []17
18    def compute_projection(19        self, mu_bar_prev: np.ndarray, mu_new: np.ndarray20    ) -> np.ndarray:21        """22        Projects mu_expert onto the line segment connecting mu_bar_prev and mu_new.23        """24        v = mu_new - mu_bar_prev25        denom = float(np.dot(v, v))26        if denom < 1e-12:27            return mu_new28
29        numer = float(np.dot(v, self.mu_expert - mu_bar_prev))30        beta = np.clip(numer / denom, 0.0, 1.0)31        return mu_bar_prev + beta * v32
33    def run_demonstration(34        self, simulated_responses: List[np.ndarray]35    ) -> None:36        """37        Executes the outer apprenticeship loop across iterations.38        """39        # Step 0: Initial random policy feature expectation40        mu_0 = np.array([0.20, 0.20])41        self.history_mu.append(mu_0)42
43        mu_bar = mu_0.copy()44        w = self.mu_expert - mu_bar45        margin = float(np.linalg.norm(w))46        self.history_margins.append(margin)47        self.history_w.append(w / margin if margin > 0 else w)48
49        print(f"Iteration 0: Initial margin t = {margin:.4f}")50
51        iteration = 152        for mu_new in simulated_responses:53            candidate_w = w / margin54            self.history_mu.append(mu_new)55
56            # Update orthogonal projection onto convex hull57            mu_bar = self.compute_projection(mu_bar, mu_new)58
59            # Recompute separating hyperplane and margin60            w = self.mu_expert - mu_bar61            margin = float(np.linalg.norm(w))62            self.history_margins.append(margin)63            self.history_w.append(w / margin if margin > 0 else w)64
65            print(66                f"Iteration {iteration}: "67                f"w = [{candidate_w[0]:.4f}, {candidate_w[1]:.4f}], "68                f"mu_new = [{mu_new[0]:.4f}, {mu_new[1]:.4f}], "69                f"mu_bar = [{mu_bar[0]:.4f}, {mu_bar[1]:.4f}], "70                f"margin t = {margin:.4f}"71            )72            iteration += 173
74            if margin <= self.epsilon:75                break76
77        print(f"\nFinal Convergence: Margin {margin:.4f} <= epsilon {self.epsilon}")78        print(f"Expert Performance Guarantee: |J(pi) - J(pi_E)| <= {margin:.4f}")79
80
81if __name__ == "__main__":82    expert_features = np.array([0.80, 0.60])83    learner = ApprenticeshipLearningProjection(84        mu_expert=expert_features, epsilon=0.1085    )86
87    # Simulated policies produced by forward RL on candidate rewards88    policy_rollouts = [89        np.array([0.55, 0.35]),90        np.array([0.75, 0.52]),91        np.array([0.79, 0.58]),92    ]93
94    learner.run_demonstration(simulated_responses=policy_rollouts)

Output:

1Iteration 0: Initial margin t = 0.72112Iteration 1: w = [0.8321, 0.5547], mu_new = [0.5500, 0.3500], mu_bar = [0.5500, 0.3500], margin t = 0.35363Iteration 2: w = [0.7071, 0.7071], mu_new = [0.7500, 0.5200], mu_bar = [0.7500, 0.5200], margin t = 0.09434
5Final Convergence: Margin 0.0943 <= epsilon 0.16Expert Performance Guarantee: |J(pi) - J(pi_E)| <= 0.0943

Watch Out For

The Quick Version

• Feature Expectation Matching: Apprenticeship Learning guarantees near-expert performance by matching the expert's discounted feature expectation vector $\mu_E$, bounding return error by $|J(\pi) - J(\pi_E)| \le \|\mu(\pi) - \mu_E\|_2$.
• Reward Agnosticism: The apprentice achieves expert competence without ever identifying or recovering the expert's true underlying reward weight vector $w^*$.
• Geometric Margin Optimization: Abbeel and Ng's Projection Algorithm iteratively builds candidate reward vectors pointing from the convex hull of past learner policies toward the expert, shrinking the margin monotonically.
• Inner-Loop Complexity: Solving a full forward RL MDP for every candidate reward vector is computationally expensive, motivating warm-start heuristics and modern single-loop adversarial frameworks like GAIL.

What to Read Next

• Inverse Reinforcement Learning
• Maximum Entropy Inverse Reinforcement Learning
• Generative Adversarial Imitation Learning (GAIL)