Watching the Path, Recovering the Goal

Every symbol the post uses, what it stands for, and how it's pronounced. The post is consistent about these, but the first appearance of each can come without warning.

Cost vs reward sign convention. Abbeel-Ng treats $w$ as reward weights (the expert maximises $w \cdot \phi$). MMP treats $w$ as cost weights with $w \geq 0$ (the expert minimises $w \cdot \phi$). The math is the same up to a sign flip, but the literature uses both, and the post follows whichever paper a given section is explaining. Within a section the convention is consistent.

The 12×12 trace earlier in the post showed the punchline numbers but skipped how they were computed. Let me work through every arithmetic step on a tiny example so you can see exactly what the algorithm is doing under the hood.

The MDP

Five states in a line, numbered 0 through 4:

• Two actions: L (left), R (right). Bumping a wall keeps you in place.
• Feature map $\phi$: 2-dim. $\phi(\text{grass}) = (1, 0)$, $\phi(\text{road}) = (0, 1)$, $\phi(\text{goal}) = (0, 0)$.
• True reward weights: $w_{\text{true}} = -(1, 0.2)$ giving the per-state rewards above. We don't know these.
• Horizon: $T = 5$ steps.

Step 1 · Compute the expert's path via finite-horizon value iteration

The expert knows $w_{\text{true}}$ and plans optimally. We do backward induction with $V_5(s) = 0$ for all $s$ (game over at time $T$). At each prior timestep, the Bellman backup is

$Q_t(s, a) = r(s) + V_{t+1}(\text{next}(s, a))$,    $V_t(s) = \max_a Q_t(s, a)$.

Step backward: $t = 4$ (one action remaining).

With $V_5 = 0$ everywhere, both actions from any state give $Q_4(s, a) = r(s)$. So:

$t = 3$ (two actions remaining).

From state 0, L bumps the wall → stays at 0 (so $Q_3(0, L) = r(0) + V_4(0) = -1 + (-1) = -2$). R moves to state 1 ($Q_3(0, R) = -1 + (-0.2) = -1.2$). Pick R.

From state 1, L → state 0 ($-0.2 - 1 = -1.2$). R → state 2 ($-0.2 - 0.2 = -0.4$). Pick R.

Continuing for every state:

$t = 2, 1, 0$. Keep applying the same Bellman backup, each time using the previous row's $V$. The final result:

The optimal policy at every timestep (from each state, take R) gives the expert's path:

$t=0$: state 0 → $t=1$: state 1 → $t=2$: state 2 → $t=3$: state 3 → $t=4$: state 4 (goal)

Total expert reward: $r(0) + r(1) + r(2) + r(3) + 0 = -1 - 0.2 - 0.2 - 0.2 + 0 = -1.6$ ✓ (matches $V_0(0)$).

Step 2 · Compute the expert's feature expectation $f_E$

Sum $\phi(s_t)$ along the path:

$f_E = \phi(0) + \phi(1) + \phi(2) + \phi(3) + \phi(4) = (1,0) + (0,1) + (0,1) + (0,1) + (0,0) = \mathbf{(1, 3)}$

The expert spends 1 step on grass and 3 steps on road. That's all the IRL algorithm gets to see, this 2-dim vector, the only "summary" of the demonstrations.

Step 3 · Abbeel-Ng iteration 0, a random policy

Start with any policy. Pick the worst one possible: "always L." From state 0, this bumps the wall every step, the agent never leaves state 0.

Trajectory: states 0, 0, 0, 0, 0 (over $t=0..4$).
Feature expectation: $f_0 = 5 \phi(0) = \mathbf{(5, 0)}$. All 5 steps on grass, none on road.

Step 4 · Iteration 1, find a separating direction

We want a unit vector $w$ that distinguishes the expert from our candidate $f_0 = (5, 0)$. Solve:

$\max\;t\quad\text{s.t.}\quad w \cdot (f_E - f_0) \geq t, \quad \|w\| \leq 1.$

Compute $f_E - f_0 = (1, 3) - (5, 0) = (-4, 3)$.

The optimal $w$ for "maximise $w \cdot v$ with $\|w\| \leq 1$" is just $v / \|v\|$:

$w_1 = \frac{(-4, 3)}{\|(-4, 3)\|} = \frac{(-4, 3)}{\sqrt{16+9}} = \frac{(-4, 3)}{5} = \mathbf{(-0.8, +0.6)}$

Margin: $t_1 = \|(-4, 3)\| = \mathbf{5.0}$.

Reading $w_1$: the expert weighs grass negatively (−0.8) and road positively (+0.6). Roughly correct: the expert prefers road and avoids grass.

Step 5 · Plan an optimal policy under $w_1$

Treat $w_1$ as the new reward weights: $r(s) = w_1 \cdot \phi(s)$, giving

Notice: road now gives positive reward, so the agent will want to stay on the road as long as possible. Goal still gives 0, actually less attractive than road!

Running VI again with these new rewards, the optimal policy turns out to be:

The action at state 3 flips from "R (reach goal)" to "L (back to road)." Goal-reaching costs +0 but road gives +0.6, the agent prefers the road. Trajectory:

state 0 → 1 → 2 → 3 → (L) 2 → end of horizon

Feature counts of this candidate policy: states visited are 0, 1, 2, 3, 2 (one of state 2 twice because we bounced back).

$f_1 = \phi(0) + \phi(1) + \phi(2) + \phi(3) + \phi(2) = (1, 0) + 4 \cdot (0, 1) = \mathbf{(1, 4)}$

Compare with the expert $f_E = (1, 3)$. Grass count matches; road count is 1 too high.

Step 6 · Iteration 2, find a new separating direction

Now we have two candidates: $f_0 = (5, 0)$ and $f_1 = (1, 4)$. The optimization is:

$\max\;t\quad\text{s.t.}\quad w \cdot (f_E - f_0) \geq t,\;\; w \cdot (f_E - f_1) \geq t,\;\; \|w\| \leq 1.$

The two difference vectors:

• $v_0 = f_E - f_0 = (1, 3) - (5, 0) = \mathbf{(-4, 3)}$. "From all-grass toward the expert, go down on grass, up on road."
• $v_1 = f_E - f_1 = (1, 3) - (1, 4) = \mathbf{(0, -1)}$. "From too-much-road toward the expert, cut the road count."

The single-candidate trick (just normalise $f_E - f_0$) no longer works, because the resulting $w$ would have positive margin on $v_0$ but negative margin on $v_1$. We need a $w$ that beats both at once. Solve the system directly.

Setup. At the optimum, both constraints are tight, otherwise we could rotate $w$ toward the slack constraint and gain margin. So:

$w \cdot v_0 = t \quad\text{and}\quad w \cdot v_1 = t \quad\text{and}\quad \|w\|^2 = 1.$

Let $w = (w_1, w_2)$. Plug the two vectors in:

$-4 w_1 + 3 w_2 = t \qquad (1)$

$-w_2 = t \qquad (2)$

Substituting (2) into (1):

$-4 w_1 + 3 w_2 = -w_2 \;\Longrightarrow\; -4 w_1 + 4 w_2 = 0 \;\Longrightarrow\; w_1 = w_2.$

Use the norm constraint:

$w_1^2 + w_2^2 = 1 \;\Longrightarrow\; 2 w_1^2 = 1 \;\Longrightarrow\; w_1 = \pm \tfrac{1}{\sqrt 2}.$

Pick the sign that gives positive margin. From (2), $t = -w_2$, so for $t > 0$ we need $w_2 < 0$. That forces both components negative:

$w_2 = \left(-\tfrac{1}{\sqrt 2},\ -\tfrac{1}{\sqrt 2}\right) \approx \mathbf{(-0.707,\ -0.707)}, \quad t_2 = \tfrac{1}{\sqrt 2} \approx \mathbf{0.707}.$

Verify both constraints:

• $w_2 \cdot v_0 = (-0.707)(-4) + (-0.707)(3) = 2.828 - 2.121 = 0.707$ ✓
• $w_2 \cdot v_1 = (-0.707)(0) + (-0.707)(-1) = 0 + 0.707 = 0.707$ ✓
• $\|w_2\| = \sqrt{0.707^2 + 0.707^2} = \sqrt{0.5 + 0.5} = 1$ ✓

Both constraints are tight at margin $0.707$, and $w_2$ is unit norm. This is the solution.

Reading $w_2$: grass weight is $-0.707$, road weight is also $-0.707$. The algorithm has decided that both grass and road should be penalised equally. With every non-goal step costing $-0.707$ no matter what terrain, the only way to maximise return is to reach the goal as fast as possible. So the next planner will care only about path length, not about which terrain it walks on.

Step 7 · Plan an optimal policy under $w_2$

The updated per-state rewards are $r(s) = w_2 \cdot \phi(s)$:

Every non-goal step pays $-0.707$. The goal pays $0$. So the agent wants to reach the goal in as few steps as possible. Now run finite-horizon VI with these rewards. As before, $V_5(s) = 0$ for all $s$, and we work backward.

$t = 4$: $V_4(s) = r(s) + V_5(\text{next}(s, a))$ for any action; since $V_5 = 0$, $V_4(s) = r(s)$.

$t = 3$: $Q_3(s, a) = r(s) + V_4(\text{next}(s, a))$.

At state 3 with one step left to go, the agent strongly prefers R (which reaches the goal) over L (which keeps it on road). Everywhere else, both actions stay in non-goal cells, so the Q-values tie.

$t = 2$: use $V_3$ from above.

The advantage of R propagates back. Now at state 2 with two steps left, going R lets the agent reach the goal one step later, saving one $-0.707$ cost.

$t = 1, 0$: the same backup. By the time we reach $t = 0$, every state strictly prefers R (the path to the goal is shorter the further right you start). The final value table:

The optimal policy is "always go R" from any non-goal state (ties broken toward R since both ties lead to identical states and R is the path to goal). Starting from state 0 at $t = 0$:

$t=0$: state 0 $\to$ $t=1$: state 1 $\to$ $t=2$: state 2 $\to$ $t=3$: state 3 $\to$ $t=4$: state 4 (goal)

Total return: $-0.707 \times 4 + 0 = -2.828$ ✓ (matches $V_0(0)$).

Feature counts:

$f_2 = \phi(0) + \phi(1) + \phi(2) + \phi(3) + \phi(4)$

$= (1, 0) + (0, 1) + (0, 1) + (0, 1) + (0, 0) = \mathbf{(1, 3)} = f_E.$

The algorithm has matched the expert exactly. 🎉 The 5-state corridor is solved in 2 iterations.

Step 8 · Convergence check

At iteration 3, the SVM would try to find a direction in which $f_E$ outscores all candidates $\{f_0, f_1, f_2\}$. But $f_E = f_2$, so $f_E - f_2 = (0, 0)$. The SVM's margin is 0. We stop.

The output is a mixture over $\{\pi_0, \pi_1, \pi_2\}$ with weights $\lambda$ chosen to match $f_E$. Since $f_2 = f_E$ already, $\lambda = (0, 0, 1)$, just use $\pi_2$.

What the final policy mixture looks like

Abbeel-Ng's output isn't a single policy, it's a mixture over all the candidate policies the algorithm planned along the way. After convergence the algorithm picks mixing weights $\lambda = (\lambda_0, \lambda_1, \lambda_2)$ such that $\lambda_0 \, f_0 + \lambda_1 \, f_1 + \lambda_2 \, f_2 = f_E$. Here's the table of candidates and their mixture weights:

The mixture is "put all the weight on $\pi_2$." So the final returned policy is just $\pi_2$ itself: at every state, take $R$. This happened because $f_2 = f_E$ exactly, no convex combination of the earlier candidates was needed.

In a less convenient example, $f_E$ might not be a vertex of the polytope; it might sit in the interior. Then the algorithm would return something like $\lambda = (0, 0.3, 0.7)$, meaning "with probability 0.3 follow $\pi_1$, with probability 0.7 follow $\pi_2$." Each episode you flip the coin once at the start and commit to one policy for the whole trajectory. The resulting feature counts, averaged over episodes, equal $f_E$.

Side-by-side comparison against the expert

Read the table top to bottom. The recovered weights $w_2 = (-0.707, -0.707)$ do not match the true weights $w_{\text{true}} = (-1, -0.2)$. They don't even have the same magnitude pattern (the true weights say "road is much cheaper than grass," the recovered weights say "grass and road cost the same"). But the recovered policy matches the expert's exactly: at every state, take $R$. The trajectory matches. The feature counts match.

The intuitive walk-through above hand-waved through two claims. This appendix proves both of them rigorously, following Ratliff, Bagnell & Zinkevich (2006), which itself builds on the general structured-prediction framework of Tsochantaridis, Joachims, Hofmann & Altun (2005).

What this appendix proves. Two results:

1. The path $\xi^*$ returned by shortest-path under modified costs $c'(s) = c(s) - L(s)$ is the worst violator of the MMP margin constraint.
2. The vector $f^* - f_E$ is the correct gradient-descent direction for the structured hinge loss, so the update rule $w \leftarrow w + \eta(f^* - f_E)$ is a valid optimisation step.

Both claims are non-trivial. Both follow from the same setup.

Notation, all in one place

Symbols used in this appendix:

• $\xi$, a feasible path through the gridworld.
• $\xi_E$, the expert's demonstrated path (observed).
• $\xi^*$, the worst-violator path (to be defined).
• $\phi(s)$, the feature vector of a single cell. $\phi(s) = (1, 0, 0, 0, 0)$ if $s$ is grass, and so on.
• $f(\xi) = \sum_{s \in \xi} \phi(s)$, the feature counts of path $\xi$. $f_E = f(\xi_E)$ and $f^* = f(\xi^*)$ are shorthands.
• $w$, the cost weights we are solving for. $w \cdot \phi(s) = c(s)$ is the cost of cell $s$. $w \cdot f(\xi) = c(\xi)$ is the total cost of path $\xi$.
• $L(s) \in \{0, 1\}$, the per-cell Hamming loss. $L(s) = 1$ if $s$ is not on the expert path.
• $\ell(\xi) = \sum_{s \in \xi} L(s)$, the total Hamming loss of path $\xi$. Counts how many cells $\xi$ visits that the expert did not.
• $\zeta \geq 0$, a slack variable allowing the margin constraint to be partially violated.
• $C > 0$, a regularisation tradeoff constant.

The MMP optimisation, formalised

The goal is to find weights $w$ such that the expert path is cheaper than every alternative by at least a Hamming-distance margin. With L2 regularisation and a slack variable for the soft-margin version:

$\displaystyle \min_{w,\, \zeta} \;\; \tfrac{1}{2}\|w\|^2 + C \cdot \zeta$

$\text{s.t.}\quad w \cdot f_E + \ell(\xi) \leq w \cdot f(\xi) + \zeta \;\;\text{for every feasible}\;\xi,\quad w \geq 0,\; \zeta \geq 0.$

Read the constraint left to right: expert cost plus margin (the Hamming distance) is at most alternative cost plus slack. The $\tfrac{1}{2}\|w\|^2$ term picks the smallest-magnitude $w$ among the many that satisfy the constraints (which would otherwise be under-determined). The constraint must hold for every feasible path $\xi$, of which there are exponentially many.

Claim 1: shortest-path under $c'(s) = c(s) - L(s)$ returns the worst violator

We want to show that the single most-violated constraint can be found with one shortest-path call, instead of enumerating exponentially many paths.

Step 1. Rearrange the soft-margin constraint to isolate the slack:

$\ell(\xi) - w \cdot \big(f(\xi) - f_E\big) \leq \zeta \quad\text{for every}\;\xi.$

The left-hand side measures how much path $\xi$ violates the constraint. A path with $\ell(\xi)$ much larger than $w \cdot (f(\xi) - f_E)$ is a serious violator: it is very different from the expert (high $\ell(\xi)$) and is not much more expensive (low $w \cdot (f(\xi) - f_E)$).

Step 2. The smallest $\zeta$ that satisfies every constraint is the maximum of the left-hand side over all $\xi$:

$\zeta^* \;=\; \max_\xi \big[\ell(\xi) - w \cdot f(\xi)\big] \,+\, w \cdot f_E.$

(The $w \cdot f_E$ term came out of the max because it does not depend on $\xi$.)

Step 3. Convert the $\max$ to a $\min$ by flipping the sign:

$\max_\xi \big[\ell(\xi) - w \cdot f(\xi)\big] \;=\; -\min_\xi \big[w \cdot f(\xi) - \ell(\xi)\big].$

The worst violator is the $\xi$ that minimises $w \cdot f(\xi) - \ell(\xi)$.

Step 4. Now the key observation: both $w \cdot f(\xi)$ and $\ell(\xi)$ decompose additively over the cells of the path:

$w \cdot f(\xi) \,=\, \sum_{s \in \xi} c(s), \qquad \ell(\xi) \,=\, \sum_{s \in \xi} L(s).$

So their difference is also a sum over cells:

$w \cdot f(\xi) - \ell(\xi) \;=\; \sum_{s \in \xi} \big(c(s) - L(s)\big) \;=\; \sum_{s \in \xi} c'(s).$

where $c'(s) = c(s) - L(s)$ is the loss-augmented per-cell cost.

Conclusion. The worst violator $\xi^* = \arg\min_\xi \sum_{s \in \xi} c'(s)$ is exactly the shortest path under modified per-cell costs $c'$. A standard shortest-path algorithm (Dijkstra, value iteration, A*) returns it in one call. ∎

Claim 2: the update rule is gradient descent on the full objective

We want to show that line 5 of the algorithm, $w \leftarrow (1 - \eta\lambda)\,w + \eta\,(f^* - f_E)$, is exactly one gradient-descent step on the regularised MMP objective. This is the part that justifies where the $(1 - \eta\lambda)$ shrinkage factor comes from.

Step 1, write down the objective for one demonstration. Combine the L2 regulariser and the structured hinge loss:

$J(w) \;=\; \underbrace{\tfrac{\lambda}{2}\|w\|^2}_{\text{L2 regulariser}} \;+\; \underbrace{\max\big(0,\; \ell(\xi^*) - w \cdot (f^* - f_E)\big)}_{\text{structured hinge } \mathcal H(w)}.$

The hinge term $\mathcal H(w)$ is the constraint-violation amount for the worst violator $\xi^*$. It is zero when the expert beats $\xi^*$ by the required margin, positive when the constraint is violated. The $\tfrac{\lambda}{2}\|w\|^2$ term is the L2 regulariser ($\lambda$ is its strength). We want to minimise $J(w)$.

Step 2, differentiate the L2 term. The gradient of $\tfrac{\lambda}{2}\|w\|^2$ with respect to $w$ is:

$\dfrac{\partial}{\partial w} \left[\tfrac{\lambda}{2}\|w\|^2\right] \;=\; \dfrac{\partial}{\partial w} \left[\tfrac{\lambda}{2}\, (w_1^2 + w_2^2 + \cdots)\right] \;=\; \lambda\, w.$

(Each $w_i^2$ differentiates to $2 w_i$, the $\tfrac{1}{2}$ cancels the 2, leaving $\lambda w_i$ in each coordinate, i.e. $\lambda w$.)

Step 3, differentiate the hinge term. In the regime where the hinge is active (constraint violated, $\mathcal H > 0$), the hinge equals $\ell(\xi^*) - w \cdot (f^* - f_E)$. Its gradient:

$\dfrac{\partial \mathcal H}{\partial w} \;=\; \dfrac{\partial}{\partial w}\big[\ell(\xi^*) - w \cdot (f^* - f_E)\big] \;=\; -\,(f^* - f_E) \;=\; f_E - f^*.$

($\ell(\xi^*)$ does not depend on $w$, so it drops. The term $-w \cdot (f^* - f_E)$ is linear in $w$ with coefficient $-(f^* - f_E)$, so its derivative is $-(f^* - f_E)$.)

Step 4, combine. The gradient of the full objective is the sum of the two pieces:

$\dfrac{\partial J}{\partial w} \;=\; \lambda\, w \;+\; (f_E - f^*).$

Step 5, take a gradient-descent step. Gradient descent moves $w$ in the direction opposite the gradient, scaled by step size $\eta$:

$w \;\leftarrow\; w \,-\, \eta \cdot \dfrac{\partial J}{\partial w} \;=\; w \,-\, \eta\,\big(\lambda w + (f_E - f^*)\big).$

Distribute the $\eta$ and group the $w$ terms:

$w \;\leftarrow\; w \,-\, \eta\lambda\, w \,-\, \eta\,(f_E - f^*) \;=\; (1 - \eta\lambda)\, w \,+\, \eta\,(f^* - f_E).$

Conclusion. This is exactly line 5 of the algorithm. The $(1 - \eta\lambda)\,w$ part is the L2 shrinkage (it pulls $w$ toward zero each step, in proportion to the regularisation strength $\lambda$). The $\eta\,(f^* - f_E)$ part is the structured-hinge subgradient (it raises the cost of terrains the violator overused). Setting $\lambda = 0$ removes the shrinkage and recovers the bare subgradient step. ∎

Why this is called "structured"

Standard classification predicts a label from a small finite set (cat, dog, fish). The output space is small enough to enumerate, so the loss is just per-example accuracy.

Structured classification predicts a combinatorial object: a parse tree, a translation, a path through a graph. The output space is exponentially large, so enumeration is impossible. The structured-SVM framework (Tsochantaridis et al. 2005) handles this with the loss-augmented inference trick we just used: find the worst-violating output via a problem-specific solver (here, shortest path), then take a subgradient step.

MMP is the path-prediction specialisation. The "structure" is that the output (a trajectory) is a sequence of states with feature counts that decompose additively over cells. That decomposability is what lets the worst-violator search collapse into a shortest-path call. Other structured outputs (trees, alignments) use different solvers but the same overall framework.

For MMP we need an MDP where the expert doesn't visit every cell, otherwise the Hamming-loss bonus has nothing to grab onto. Here's a 2-row, 3-column grid:

• Six states, indexed 0–5. State 0 is start, state 2 is goal.
• Actions: N, E, S, W. Walls reflect.
• True cost: grass = 1, road = 0.2, goal = 0.
• Feature map: $\phi$ is 2-dim grass/road one-hot.

Step 1 · The expert's path and visited states

The expert plans optimally under the true costs. The cheapest path from state 0 to state 2:

state 0 (grass) → E → state 1 (road) → E → state 2 (goal)

Total cost = 1 + 0.2 + 0 = 1.2. (Going via the bottom row would cost 1+1+1+1+0 = 4, much more.)

Feature expectation:

$f_E = \phi(0) + \phi(1) + \phi(2) = (1, 0) + (0, 1) + (0, 0) = \mathbf{(1, 1)}$

States the expert visited: $V_E = \{0, 1, 2\}$. Non-expert states: $\{3, 4, 5\}$.

Step 2 · Build the per-state Hamming loss

$L(s) = 1$ if $s$ is not on the expert's path, else 0:

The bottom row (which the expert avoided) carries a 1-unit "bonus", the loss-augmented planner will see those cells as cheaper than they really are.

Step 3 · MMP iteration 0, initial $w$

Start with a random non-negative weight vector. Say $w = (0.3, 0.7)$, grass costs 0.3, road costs 0.7.

Current cost map $c(s) = w \cdot \phi(s)$:

Note that under this random init, grass is cheaper than road, the opposite of the truth. The algorithm has to fix this.

Step 4 · Compute the loss-augmented cost $c'(s) = c(s) - L(s)$

The bottom-row cells now have negative cost, visiting them saves 0.7 each. The augmented planner will be tempted to detour.

Step 5 · Find the worst-violator path $\xi^*$

Plan the minimum-cost path from state 0 to state 2 under $c'$. Some candidate paths and their augmented cost:

The cheapest under the loss-augmented cost is the long detour through the bottom row: $\xi^* = (0, 3, 4, 5, 2)$, cost $-1.8$. This is the "worst violator", the path the algorithm wants to make more expensive.

Feature counts of $\xi^*$:

$f^* = \phi(0) + \phi(3) + \phi(4) + \phi(5) + \phi(2) = (1, 0) + (1, 0) + (1, 0) + (1, 0) + (0, 0) = \mathbf{(4, 0)}$

Step 6 · Compute the subgradient and apply the update

We use the update from Section 8 Step 4 with $\lambda = 0$ (no L2 regularisation), to keep the arithmetic clean. With $\lambda = 0$ the shrinkage factor $(1 - \eta\lambda)$ becomes 1, so the update reduces to the bare subgradient step $w \leftarrow w + \eta \cdot \big(f^* - f_E\big)$. (A real run would keep a small positive $\lambda$ to bound the weights; here it would only add a tiny shrinkage and clutter the numbers.) The update direction is violator features minus expert features:

$f^* - f_E = (4, 0) - (1, 1) = \mathbf{(+3, -1)}$

Reading this:

• $+3$ on grass: the violator visited grass 3 more times than the expert. Raise $w_{\text{grass}}$ to discourage grass.
• $-1$ on road: the expert visited road 1 more time than the violator. Lower $w_{\text{road}}$ to encourage road.

With $\eta = 0.5$:

$w_{\text{new}} = w + \eta \cdot \big(f^* - f_E\big) = (0.3, 0.7) + 0.5 \cdot (+3, -1) = (0.3 + 1.5, \; 0.7 - 0.5) = \mathbf{(1.8, \; 0.2)}$

After projecting to non-negative orthant (both entries already $\geq 0$): $w = (1.8, 0.2)$.

Step 7 · Compute the slack at this iteration

The "violation" the algorithm just measured:

slack$_E = \ell(\xi^*) - w \cdot (f^* - f_E)$

$\ell(\xi^*) = L(0) + L(3) + L(4) + L(5) + L(2) = 0 + 1 + 1 + 1 + 0 = 3$ (three non-expert cells visited).

$f^* - f_E = (4, 0) - (1, 1) = (3, -1)$.

$w \cdot (3, -1) = 0.3 \cdot 3 + 0.7 \cdot (-1) = 0.9 - 0.7 = 0.2$.

slack $= 3 - 0.2 = \mathbf{2.8}$.

2.8 is large, the algorithm has work to do.

Step 8 · Iteration 1, recompute everything with the new $w$

$w = (1.8, 0.2)$. Cost map:

Now grass is much more expensive than road. ✓

Loss-augmented cost:

Even with the 1-unit bonus on the bottom row, those cells still cost 0.8 each, not enough to compete with road at 0.2.

Find $\xi^*$ now:

The cheapest is now the expert path itself. $\xi^* = (0, 1, 2)$, same as $\xi_E$.

Subgradient: $g = f_E - f^* = (1, 1) - (1, 1) = (0, 0)$. No update.

Slack: $\ell(\xi^*) = 0$ (no non-expert cells), $w \cdot (f^* - f_E) = 0$. slack $= 0$.

Converged. 🎉

Step 9 · What we recovered (the final answer)

After one iteration, the loss-augmented planner under $w = (1.8, 0.2)$ returns the expert's path itself. The algorithm has converged.

The final recovered policy, state by state

Unlike Abbeel-Ng, MMP doesn't output a mixture of candidate policies. It outputs a single cost vector $w$, and the "policy" is implicit: it's whatever a planner produces from $w$. Here's what the planner produces on this 2×3 grid, for every starting state:

The recovered policy at every non-goal state: get to the road or goal as fast as possible, then ride the road home. Starting at the official start state (0), this produces the expert's trajectory exactly. Starting elsewhere, the policy is what you'd want a sensible agent to do, but those starts weren't demonstrated, so the recovered policy there is just whatever falls out of running a planner on the recovered $w$.

Side-by-side comparison against the expert

The recovered policy (the "go through the road" path) is exactly the expert's. The recovered cost vector has the right ordering and gets road exactly right, but grass came out 1.8× too high. This is the typical MMP outcome on under-constrained problems: ordering correct, magnitude off, policy correct.

What does the recovered cost give you on a NEW map?

This is the answer to "why bother recovering a cost at all instead of just using Abbeel-Ng?" Suppose tomorrow you get a new map: an L-shaped corridor where the same kinds of terrain appear in different places. Hand the recovered $w = (1.8, 0.2)$ to a planner on the new map and it returns the road-hugging path automatically. The cost transfers because it depends only on terrain type, not on the specific map layout. Abbeel-Ng's policy-mixture output, by contrast, is tied to the original map and gives nonsense on the new one.

The Cauchy-Schwarz inequality says that for any two vectors $a, b \in \mathbb R^n$:

$|a \cdot b| \leq \|a\| \cdot \|b\|$

with equality if and only if one is a non-negative scalar multiple of the other (they point in the same direction).

Apply this to $w$ and $v$, using the constraint $\|w\| \leq 1$:

$w \cdot v \;\leq\; |w \cdot v| \;\leq\; \|w\| \cdot \|v\| \;\leq\; 1 \cdot \|v\| \;=\; \|v\|.$

So $\|v\|$ is an upper bound on $w \cdot v$. Now we need to show this bound is achieved. Pick $w = v / \|v\|$. Compute:

$w \cdot v \;=\; \dfrac{v}{\|v\|} \cdot v \;=\; \dfrac{v \cdot v}{\|v\|} \;=\; \dfrac{\|v\|^2}{\|v\|} \;=\; \|v\|.$

And the norm constraint is satisfied:

$\|w\| \;=\; \left\| \dfrac{v}{\|v\|} \right\| \;=\; \dfrac{\|v\|}{\|v\|} \;=\; 1 \leq 1. \;\;\checkmark$

So $w^* = v / \|v\|$ achieves the upper bound, and is therefore the maximiser. ∎

The dot product has a geometric definition:

$w \cdot v \;=\; \|w\| \cdot \|v\| \cdot \cos\theta$

where $\theta$ is the angle between $w$ and $v$. So:

$w \cdot v \;\leq\; \|w\| \cdot \|v\| \cdot 1 \;=\; \|w\| \cdot \|v\|$

with equality when $\cos\theta = 1$, that is, $\theta = 0$, that is, $w$ and $v$ point in the same direction. Under the constraint $\|w\| \leq 1$, the right-hand side is at most $\|v\|$, with equality when $\|w\| = 1$.

So to maximise the dot product we need two things at once:

• Make $\|w\|$ as large as the constraint allows. Set $\|w\| = 1$, saturate the constraint.
• Make $\cos\theta$ as large as possible. Set $w$ parallel to $v$.

The unique vector satisfying both is $w^* = v / \|v\|$. The picture: $w^*$ is the unit arrow pointing exactly the way $v$ points. Any other direction loses you $\cos\theta$; any shorter vector loses you $\|w\|$. ∎

Set up the constrained optimisation. Use $\|w\|^2 \leq 1$ (the squared norm) so the constraint is smooth:

$\max_w \; w \cdot v \quad\text{subject to}\quad w \cdot w \leq 1.$

The Lagrangian is:

$\mathcal L(w, \lambda) \;=\; w \cdot v \;-\; \lambda \, (w \cdot w - 1)$

with $\lambda \geq 0$. Stationarity, set $\nabla_w \mathcal L = 0$:

$v - 2\lambda w \;=\; 0 \quad\Longrightarrow\quad w \;=\; \dfrac{v}{2\lambda}.$

So $w$ must be parallel to $v$. For the unconstrained maximum to be bounded, the constraint must be active (otherwise $w$ could grow without bound and so could $w \cdot v$), so $w \cdot w = 1$, giving:

$\left\| \dfrac{v}{2\lambda} \right\|^2 \;=\; 1 \quad\Longrightarrow\quad \dfrac{\|v\|^2}{4\lambda^2} \;=\; 1 \quad\Longrightarrow\quad 2\lambda \;=\; \|v\|.$

Plugging back:

$w^* \;=\; \dfrac{v}{2\lambda} \;=\; \dfrac{v}{\|v\|}.$

The optimal Lagrange multiplier $\lambda^* = \|v\| / 2$ measures how much the optimum would increase per unit relaxation of the norm constraint. Bigger $\|v\|$ means more room to grow $w \cdot v$ if we were allowed to let $\|w\|$ exceed 1. ∎