A Delivery Fleet That Never Explains Itself
A Swiggy-scale routing engine has to decide, for every one of a few hundred thousand orders a day, which road a delivery partner should take from depot to customer. The naive way to build this is to write down a reward function by hand: minus one point per minute of travel time, a large bonus on arrival. Feed that into a reinforcement learning algorithm, solve the underlying Markov Decision Process, and out comes a policy. This works badly. A hand-written reward built only from travel time will happily route a rider down a two-metre-wide lane between parked handcarts if it shaves ninety seconds off a five-kilometre trip, because nothing in that reward function knows that narrow lanes carry a real, if hard-to-articulate, cost: higher accident risk, higher chance of a dead end forcing a reversal, higher chance of a scooter simply not fitting. Engineers do not sit down and enumerate a clean formula for "risk of narrow lane in monetary-equivalent minutes." What the company actually has, in enormous quantity, is GPS logs of its most experienced delivery partners, people who have ridden every lane in a five-kilometre radius for three years and reliably choose the safe, slightly longer main road over the risky shortcut. Those logs are behavior, not a reward function. The problem this chapter solves is how to go from that observed behavior back to the reward function that would make the behavior optimal, so that the recovered reward can then be handed to an ordinary reinforcement learning algorithm and reused in situations the recorded riders never actually visited. That reversal, behavior in, reward out, is inverse reinforcement learning.
Flipping the Reinforcement Learning Problem
Recall the standard setup. An MDP is a tuple (S, A, P, R, γ): a state set S, an action set A, a transition model P(s'|s,a), a reward function R(s) or R(s,a), and a discount factor γ ∈ [0,1). A policy π(a|s) picks actions, and its value is V^π(s) = E[Σ_{t=0}^∞ γ^t R(s_t) | π, s_0 = s]. Forward reinforcement learning is given (S, A, P, R, γ) and searches for π* = argmax_π V^π. Every algorithm covered so far in this strand, value iteration, Q-learning, policy gradients, bandit algorithms, takes R as a known input.
Inverse reinforcement learning inverts the arrows. You are given (S, A, P, γ) and a set of trajectories τ_E = {(s_0, a_0, s_1, a_1, …)} sampled from an expert policy π_E (the delivery partner's actual routes), and you are asked to recover an R under which π_E is optimal, or at least under which π_E earns higher expected return than the alternatives you can enumerate. The name comes directly from this reversal: reinforcement learning maps reward to behavior, inverse reinforcement learning maps behavior to reward. Once you have a plausible R, you hand it to any forward RL algorithm and solve for a policy that generalizes beyond the exact roads the logged riders happened to travel, including new pincodes the fleet has never served.
Why Not Simply Copy the Expert's Actions?
A tempting shortcut is behavior cloning: treat (state, action) pairs from the logs as labelled training data and fit a classifier π̂(a|s) with ordinary supervised learning. This is simpler than IRL and is used in practice, but it fails in a specific, well-documented way. Behavior cloning has no model of why an action was good, only that it was taken in that state. The moment the learned policy drifts even slightly off the distribution of states the expert actually visited, perhaps because of a small early misprediction, it enters states the training data never covered, has no signal for what to do there, and compounds the error further with each step. This is the covariate-shift problem that motivates corrections like DAgger, and it is fundamentally a data-coverage problem: the policy is only ever as good as its state coverage.
A recovered reward function does not have this weakness in the same way. "Narrow lanes are penalized, main roads with fewer turns are rewarded" is a compact statement that transfers to a street the expert never rode down, because forward RL can re-solve the MDP for the new street layout using the same R. The reward is the more parsimonious, more transferable object; the policy is a derived, situation-specific artifact. This is the central argument for IRL over cloning wherever the deployment environment can differ from the environment the demonstrations were collected in, which is essentially always true at fleet scale.
The Reward Ambiguity Problem
IRL has a structural difficulty that forward RL does not: it is underdetermined. Andrew Ng and Stuart Russell, in the paper that named the problem in 2000, pointed out the most extreme case directly: if R(s) = 0 for every state, then every policy has value zero, so every policy, including π_E, is trivially optimal. The all-zero reward "explains" any behavior whatsoever while explaining nothing about it. More generally, for a fixed MDP there is an entire family of reward functions consistent with a given optimal policy, not one unique reward hiding behind the behavior. Any practical IRL method has to build in some way of ruling out the degenerate, uninformative members of that family and picking a reward that is not just consistent with the expert but distinguishes the expert's choices from the alternatives with some real margin.
Linear Reward Features and Feature Expectations
Pieter Abbeel and Andrew Ng's 2004 apprenticeship-learning framework handles this by restricting attention to rewards that are linear in a hand-chosen feature map φ: S → R^k, so R(s) = w · φ(s) for a weight vector w. Because expectation is linear, the value of a policy under this reward decomposes cleanly:
V^π = E[Σ_{t=0}^∞ γ^t R(s_t) | π] = E[Σ_{t=0}^∞ γ^t (w · φ(s_t)) | π] = w · E[Σ_{t=0}^∞ γ^t φ(s_t) | π] = w · μ(π)
where μ(π) is the policy's feature expectation, a vector in R^k that averages, with discounting, how much of each feature the policy's trajectories tend to accumulate. This is the key move: comparing the value of two policies under an unknown w reduces to comparing two fixed, computable vectors, μ(π_E) and μ(π), via the dot product with w. If you can find a w for which w · μ(π_E) exceeds w · μ(π) for every alternative policy π you have generated so far, you have a reward under which the expert beats those alternatives, and you can keep tightening the set of alternatives until no better-behaved policy can be found.
Worked Example: Why the Longer Road Wins
Take the routing scenario literally and give it two route-level features. For every road segment the rider enters, define φ(s) = (lane, turn), where lane = 1 if the segment is a narrow lane and 0 otherwise, and turn = 1 if entering that segment required a turn at an intersection and 0 if it continued straight. Use γ = 0.9.
Path A is the narrow-lane shortcut, three segments long, with the rider turning onto the lane, going straight through the middle stretch, then turning again to reach the customer's street: φ-sequence (1,1), (1,0), (1,1).
Path B is the main road, five segments long, turning onto the main road once, going straight for three segments, then turning once more into the customer's street: φ-sequence (0,1), (0,0), (0,0), (0,0), (0,1).
The discounted feature expectation for a path is μ = Σ_{t=1}^{T} γ^t φ(s_t), summing over the segments entered after the start. For path A:
μ_A = 0.9·(1,1) + 0.81·(1,0) + 0.729·(1,1) = (0.9+0.81+0.729, 0.9+0+0.729) = (2.439, 1.629)
For path B:
μ_B = 0.9·(0,1) + 0.81·(0,0) + 0.729·(0,0) + 0.6561·(0,0) + 0.59049·(0,1) = (0, 0.9+0.59049) = (0, 1.49049)
Now check what a naive reward, minus one point per segment regardless of features, predicts. Return of A is −(0.9+0.81+0.729) = −2.439. Return of B is −(0.9+0.81+0.729+0.6561+0.59049) = −3.6856 (rounded to four places). The naive reward strictly prefers A, −2.439 being greater than −3.6856, because A is shorter. If the logged expert always takes the five-segment main road anyway, this naive reward is simply wrong about the expert's preferences, and that mismatch is the raw signal IRL works from: no constant-per-step reward can explain a rider who repeatedly declines the shorter route.
Now search for a feature-based reward that does explain it. The requirement is w · μ_B ≥ w · μ_A, i.e. 1.49049·w_turn ≥ 2.439·w_lane + 1.629·w_turn, which simplifies to w_lane ≤ −0.05679·w_turn. Take w = (w_lane, w_turn) = (−1, −0.1): a strong penalty for being on a narrow lane, a mild penalty for turning. Check the bound: −1 ≤ −0.05679×(−0.1) = 0.00568, and indeed −1 ≤ 0.00568 holds. Compute the resulting rewards directly: R(A) = w · μ_A = (−1)(2.439) + (−0.1)(1.629) = −2.439 − 0.1629 = −2.6019. R(B) = w · μ_B = (−1)(0) + (−0.1)(1.49049) = −0.149. Since −0.149 is greater than −2.6019, path B now correctly outranks path A under this reward, matching the observed expert choice, even though B takes more steps and would lose under the naive per-step reward. The single feature that flips the ranking is the lane penalty; the turn penalty barely matters here, which is itself informative about what the data can and cannot pin down.
Tracing the Arithmetic in Code
The computation above is short enough to trace exactly in Python, with no external libraries and no helper calls.
gamma = 0.9
# Path A: narrow lane shortcut (3 segments)
# each entry is phi(s_t) = (lane_indicator, turn_indicator)
path_A = [(1, 1), (1, 0), (1, 1)]
# Path B: main road (5 segments)
path_B = [(0, 1), (0, 0), (0, 0), (0, 0), (0, 1)]
def feature_expectation(path, gamma):
lane_sum, turn_sum = 0.0, 0.0
for t, (lane, turn) in enumerate(path, start=1):
discount = gamma ** t
lane_sum += discount * lane
turn_sum += discount * turn
return (lane_sum, turn_sum)
mu_A = feature_expectation(path_A, gamma)
mu_B = feature_expectation(path_B, gamma)
print("mu_A =", (round(mu_A[0], 4), round(mu_A[1], 4)))
print("mu_B =", (round(mu_B[0], 4), round(mu_B[1], 4)))
w = (-1.0, -0.1) # candidate reward weights: (lane penalty, turn penalty)
def dot(w, mu):
return w[0] * mu[0] + w[1] * mu[1]
R_A = dot(w, mu_A)
R_B = dot(w, mu_B)
print("R(path A) =", round(R_A, 4))
print("R(path B) =", round(R_B, 4))
print("Expert path B preferred:", R_B > R_A)Run mentally, term by term: feature_expectation(path_A, 0.9) accumulates 0.9¹·1, 0.9²·1, 0.9³·1 into lane_sum giving 0.9+0.81+0.729 = 2.439, and 0.9¹·1, 0.9²·0, 0.9³·1 into turn_sum giving 0.9+0+0.729 = 1.629. The printed output is exactly:
mu_A = (2.439, 1.629)
mu_B = (0.0, 1.4905)
R(path A) = -2.6019
R(path B) = -0.149
Expert path B preferred: TrueApprenticeship Learning via IRL
One weight vector fit to two hand-picked paths is a toy. The real algorithm, apprenticeship learning via inverse reinforcement learning, treats it as an iterative loop that keeps generating new competing policies and re-fitting w until nothing beats the expert by any real margin. Start with any policy π_0, compute its feature expectation, and solve a max-margin quadratic program for the best current w: maximize the margin t subject to w · μ_E ≥ w · μ(π_i) + t for every policy generated so far, with ‖w‖₂ ≤ 1 to rule out the trivial, unbounded, or zero solutions from the ambiguity problem above. Take the resulting w, build R = w · φ, and hand it to a forward RL solver (value iteration, for a small enough MDP) to get a new candidate policy π_{i+1}. Compute that policy's feature expectation, add it to the comparison set, and repeat. The loop terminates once the margin t shrinks below a chosen tolerance ε, meaning no policy generated so far can be separated from the expert by more than a negligible amount under the best available w.
Each pass around this loop uses the forward RL solver as a subroutine, which is why apprenticeship learning is sometimes described as IRL wrapped around ordinary RL rather than a replacement for it. Step 5 has to be re-solved on every iteration, not once at the start, because w changes every time step 3 runs: the optimal policy for last iteration's reward is generally not optimal for this iteration's reward, so a stale policy would give a stale, uninformative μ to compare against.
A Misconception Worth Killing
Students who first meet IRL tend to assume it recovers the expert's true, singular internal reward, the actual number the delivery partner is unconsciously optimizing in their head. It does not, and cannot. The reward-ambiguity discussion above is not a footnote, it is a structural limit: reward functions are not identifiable from behavior alone. Go back to the worked example. The feasible region for the weights was derived as w_lane ≤ −0.05679·w_turn. Plug in w = (0,0): the boundary condition becomes 0 ≤ 0, satisfied with equality, so the degenerate zero reward technically clears the bar, just with zero margin, exactly the Ng-and-Russell degenerate case. Plug in w = (−2, −0.05): the bound requires −2 ≤ −0.05679×(−0.05) = 0.00284, and −2 ≤ 0.00284 holds comfortably, so this is a second, entirely different reward that also explains the same expert path perfectly. There is no computation that distinguishes "the lane penalty is exactly −1 and the turn penalty is exactly −0.1" from "the lane penalty is exactly −2 and the turn penalty is exactly −0.05" using this data; both make B beat A, and infinitely many other pairs do too. What the max-margin formulation buys you is not uniqueness, it buys you exclusion of the useless, zero-margin solutions like R = 0, by explicitly maximizing the margin t and bounding ‖w‖. The output of IRL should always be read as "a reward consistent with, and confidently separating, the observed behavior," never as "the one true reward the expert was actually running."
Active Recall
Attempt each question before reading its answer.
1. State one concrete reason a fleet-routing team would prefer inverse reinforcement learning over hand-designing a reward function, using the naive per-step reward computed in this chapter as evidence.
2. A third path, C, takes the narrow lane but only two segments: φ-sequence (1,1), (1,0). Using γ = 0.9, compute μ_C.
3. Using w = (−1, −0.1) from the worked example, compute R(path C) and rank paths A, B, and C by preference under this reward.
4. Explain why w = (0, 0) technically satisfies the IRL inequality w·μ_E ≥ w·μ(π) for every alternative policy, and why this makes it a useless solution rather than a correct one.
5. Give one specific failure mode of behavior cloning that a recovered reward function, re-solved through forward RL, does not share.
6. In the apprenticeship-learning loop, why must the forward RL step be re-solved on every iteration instead of once at the start?
Answers.
1. The naive reward of minus one point per travel segment gives path A a return of −2.439 and path B a return of −3.6856, so it predicts the rider should always take the shorter, riskier lane. Real experienced riders take the longer main road anyway. A hand-built reward that contradicts the people who actually do the job well is worse than useless, it actively misroutes new riders; IRL instead fits weights (here, a strong penalty on the lane feature) directly from the behavior that already gets this right.
2. μ_C = γ¹·(1,1) + γ²·(1,0) = 0.9·(1,1) + 0.81·(1,0) = (0.9+0.81, 0.9+0) = (1.71, 0.9).
3. R(C) = w·μ_C = (−1)(1.71) + (−0.1)(0.9) = −1.71 − 0.09 = −1.8. Comparing all three: R(A) = −2.6019, R(C) = −1.8, R(B) = −0.149. Since −0.149 > −1.8 > −2.6019, the ranking is B preferred over C preferred over A: the fully safe main road beats the short risky lane, which in turn beats the long risky lane, exactly the ordering a real risk-averse rider would produce.
4. With R(s) = 0 for every state, every trajectory has value exactly zero regardless of the policy that produced it, so w·μ_E = 0 and w·μ(π) = 0 for any π, and the inequality 0 ≥ 0 holds trivially. It "explains" the expert's behavior only in the empty sense that it explains every possible behavior equally; it gives zero margin and carries no information about which actions were actually preferred. Max-margin IRL rules it out by explicitly maximizing the margin t rather than merely checking that the inequality holds.
5. Behavior cloning is a supervised classifier over (state, action) pairs with no notion of why an action was good, so once the learned policy drifts into a state absent from the training distribution, typically because of a small early error, it has no reliable signal and the error compounds with each further step (covariate shift). A recovered reward function does not have this failure mode in the same way: forward RL re-solves the MDP under that reward for whatever states actually arise, including ones never seen in the demonstration data, because the reward is a compact statement of what generally matters (avoid narrow lanes) rather than a lookup table of specific actions in specific states.
6. The weight vector w is recomputed every time step 3 runs, so the reward R = w·φ is different on every iteration; the policy that is optimal for one iteration's reward is generally not optimal for the next iteration's reward. Re-running forward RL each time is what produces a fresh candidate policy π_(i+1) and a fresh μ(π_(i+1)) to add to the comparison set, which is exactly what lets the max-margin step keep tightening w until the expert can no longer be beaten by more than ε.
Think About It
Think about this: How would you explain inverse reinforcement learning: inferring rewards to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.
Key Takeaways — Summary and Recap
Let us recap what we covered: the core ideas behind inverse reinforcement learning: inferring rewards, how they connect to real-world applications, and why they matter for your journey in computer science. Remember these key points as you move forward. For competitive exam preparation (CBSE, JEE, BITSAT), focus on understanding the WHY behind each concept, not just the WHAT.