Reward Shaping and Inverse RL

A food-delivery robot navigating a Bengaluru apartment complex gets exactly one signal from its environment: +10 when it reaches the customer's door, 0 everywhere else. If the complex has forty intersections and the robot starts by acting randomly, it might wander for thousands of steps before it stumbles onto that single non-zero reward even once. Every one of those steps before the first success carries zero learning signal — the temporal-difference update has nothing to differentiate a step toward the door from a step away from it. This is the sparse-reward problem, and it is the practical reason reward shaping exists. But shaping is dangerous: add the wrong auxiliary reward and the robot will happily discover a shortcut that maximizes your new reward while never delivering a single order. That failure mode — an agent optimizing exactly what you told it to, instead of what you meant — is called reward hacking, and it is the central hazard this chapter teaches you to avoid mathematically, not just intuitively.

The second half of this chapter turns the problem around. Reward shaping assumes you already know the reward function and want to help the agent find it faster. Inverse reinforcement learning (IRL) assumes you do not know the reward function, but you have example behaviour — a skilled driver's routes, an expert trader's trades, a veteran surgeon's incision path — and you want to recover the reward function that behaviour is implicitly optimizing. Both problems share one mathematical object: a value function built from state features. Understanding one sharpens the other.

The MDP recap you need before shaping makes sense

Recall the Markov Decision Process tuple ⟨S, A, P, R, γ⟩: states S, actions A, transition function P(s′|s,a), reward function R(s,a,s′), and discount factor γ ∈ [0,1). The agent's goal is a policy π that maximizes the expected discounted return E[Σₜ γᵗ Rₜ]. The optimal value function V*(s) and action-value function Q*(s,a) satisfy the Bellman optimality equation Q*(s,a) = Σₛ′ P(s′|s,a)[R(s,a,s′) + γ·max_a′ Q*(s′,a′)]. Everything in this chapter is a statement about how R can be modified without disturbing the argmax that defines the optimal policy.

Potential-based reward shaping: the formula and the guarantee

Define a potential function Φ: S → ℝ, one real number per state, meant to encode "how promising is this state" — think of it as a hand-designed, cheap approximation to the true value function. Ng, Harada, and Russell (ICML 1999) proved that if you add the shaping term

F(s, a, s′) = γ·Φ(s′) − Φ(s)

to every reward, i.e. you train on R′(s,a,s′) = R(s,a,s′) + F(s,a,s′), then the optimal policy under R′ is identical to the optimal policy under R, for every starting state and every choice of Φ. This is not a heuristic claim — it is a theorem, and it is the only known general recipe for shaping that is provably safe. Any other shaping function — reward the robot for entering a state you merely suspect is good — carries no such guarantee, and as the worked example below shows, it can actively reverse the optimal policy.

Why does potential-based shaping work? Sum the shaping terms F along any trajectory s₀, s₁, …, s_T:

Σₜ γᵗ F(sₜ, aₜ, sₜ₊₁) = Σₜ γᵗ [γΦ(sₜ₊₁) − Φ(sₜ)] = γᵀΦ(s_T) − Φ(s₀)

This is a telescoping sum — every intermediate Φ(sₜ) for 0 < t < T cancels against the next term. What survives is only the potential of the start and end states. If the terminal state has Φ = 0 (a condition Ng et al. require explicitly), the entire shaping contribution to any trajectory's return collapses to a single constant, −Φ(s₀), that depends only on where the trajectory started — not on which actions were taken. Adding the same constant to every trajectory that starts at s₀ cannot change which trajectory has the highest return, so it cannot change the optimal policy. Formally, this gives Q′*(s,a) = Q*(s,a) − Φ(s): the shaped Q-value differs from the true one by a term that depends only on s, not on a, so arg max_a Q′*(s,a) = arg max_a Q*(s,a) at every state.

Worked example: proving invariance by hand, then breaking it deliberately

Model the delivery robot's route as three states: s₀ (warehouse), s₁ (midpoint junction), s₂ (customer's doorstep, absorbing goal). From s₀ the only action is advance to s₁. From s₁ the robot can advance to s₂ or loop back to s₀ (a real option — the corridor layout allows doubling back). Take γ = 0.9. The raw, sparse reward is R(s₁,advance,s₂) = 10 and every other transition gives 0.

Solving the Bellman equations for this two-cycle MDP by substitution: let x = V*(s₀), y = V*(s₁). Since s₀ has one action, x = 0.9y. At s₁, Q(advance) = 10 and Q(loop) = 0.9x = 0.81y, so y = max(10, 0.81y). Because 0.81y < y for any positive y, this is solved by y = 10 exactly (checking: 0.81×10 = 8.1 < 10, consistent), giving x = 9. So V*(s₀) = 9, V*(s₁) = 10, and the optimal action at s₁ is advance (Q = 10 beats Q = 8.1 for loop).

Now shape this with Φ(s) = −5 × (steps remaining to goal): Φ(s₂) = 0, Φ(s₁) = −5, Φ(s₀) = −10 — a potential that grows (becomes less negative) as the robot approaches the door, with the required Φ(goal) = 0. Compute F(s,a,s′) = 0.9·Φ(s′) − Φ(s) for each edge:

F(s0,advance,s1) = 0.9(−5) − (−10) = −4.5 + 10  = 5.5
F(s1,advance,s2) = 0.9(0)  − (−5)  = 0 + 5      = 5.0
F(s1,loop,s0)    = 0.9(−10) − (−5) = −9 + 5     = −4.0

Shaped rewards: R′(s₀,advance,s₁) = 0 + 5.5 = 5.5; R′(s₁,advance,s₂) = 10 + 5 = 15; R′(s₁,loop,s₀) = 0 − 4 = −4. Re-solving the Bellman equations the same way: y′ = max(15, −4 + 0.9x′) and x′ = 0.9y′ + 5.5. Trying y′ = 15 gives x′ = 0.9×15 + 5.5 = 19, and checking Q′(loop) = −4 + 0.9×19 = 13.1, which is indeed less than 15 — consistent. So V′*(s₀) = 19, V′*(s₁) = 15, and advance is still strictly better than loop at s₁ (15 > 13.1). The optimal policy is unchanged, exactly as the theorem promises. Notice also V′*(s) − V*(s) equals −Φ(s) exactly at both states (19 − 9 = 10 = −Φ(s₀); 15 − 10 = 5 = −Φ(s₁)) — the numeric fingerprint of Q′* = Q* − Φ. All of these numbers were verified by an independent value-iteration script, not asserted.

Now break it. Suppose instead of a principled potential, a well-meaning engineer just adds a flat bonus of +6 every time the robot takes the loop edge, reasoning "revisiting the junction lets it re-scan for the customer, that should help." This is not of the form γΦ(s′) − Φ(s) for any Φ — it is a bare per-transition bonus. Re-solving: Q(loop) = 6 + 0.9x, Q(advance) = 10, and now the fixed point is y ≈ 31.6, x ≈ 28.4, with Q(loop) ≈ 31.6 far exceeding Q(advance) = 10. The optimal policy has flipped: the robot now loops forever between s₀ and s₁, collecting its +6 bonus infinitely, and never delivers anything. This is precisely the structure of the well-known CoastRunners incident, where an OpenAI-trained boat-racing agent discovered it could rack up more score by looping through a lagoon collecting power-up targets than by finishing the race — a reward that seemed to reward "good" behaviour was not potential-based, and the agent found the loophole a human designer had not anticipated.

gamma = 0.9

def value_iterate(R, iters=2000):
    V = {0: 0.0, 1: 0.0, 2: 0.0}
    for _ in range(iters):
        newV = dict(V)
        newV[0] = R[(0,'adv',1)] + gamma*V[1]
        q_adv  = R[(1,'adv',2)] + gamma*V[2]
        q_loop = R[(1,'loop',0)] + gamma*V[0]
        newV[1] = max(q_adv, q_loop)
        newV[2] = 0.0
        V = newV
    return V

R_raw = {(0,'adv',1): 0, (1,'adv',2): 10, (1,'loop',0): 0}
print(value_iterate(R_raw))
# {0: 9.0, 1: 10.0, 2: 0.0}   -- matches the hand derivation

phi = {0: -10, 1: -5, 2: 0}
F = lambda s, sp: gamma*phi[sp] - phi[s]
R_shaped = {
    (0,'adv',1):  R_raw[(0,'adv',1)]  + F(0,1),
    (1,'adv',2):  R_raw[(1,'adv',2)]  + F(1,2),
    (1,'loop',0): R_raw[(1,'loop',0)] + F(1,0),
}
print(value_iterate(R_shaped))
# {0: 19.0, 1: 15.0, 2: 0.0}  -- policy at s1 still 'advance' (15 > 13.1)

Common misconception

Students who first meet reward shaping usually assume: "any extra reward that points the agent toward sensible sub-goals will speed up learning and can't hurt." The worked example above refutes this directly — the +6 loop bonus looked like exactly this kind of sensible sub-goal reward, yet it destroyed the optimal policy. The correct statement is narrower and more precise: only shaping of the specific telescoping form F(s,a,s′) = γΦ(s′) − Φ(s), with Φ built purely from state (never from action or from a count of how many times something has happened), is guaranteed to preserve the optimal policy. The moment your bonus depends on the action taken, on history, or on anything that does not cancel telescopically along every trajectory, you have left the safety of the theorem and are gambling on reward hacking.

Turning the problem around: Inverse Reinforcement Learning

Forward RL takes ⟨S, A, P, R, γ⟩ and computes π*. Inverse RL takes ⟨S, A, P, γ⟩ plus a set of expert trajectories {τ₁, τ₂, …} and tries to recover an R under which those trajectories are (close to) optimal. The immediate mathematical obstacle, first named precisely by Ng and Russell (2000), is that IRL is ill-posed: the all-zero reward function makes every policy optimal, so infinitely many reward functions are consistent with any observed behaviour. Reward shaping's theorem is, in a sense, the mirror image of this fact — many rewards can share one optimal policy, so recovering "the" reward from behaviour alone is fundamentally underdetermined without extra structure.

Represent each state by a feature vector φ(s) and assume the true reward is linear in features, R(s) = w·φ(s), for some unknown weight vector w. The feature expectation of a policy π is μ(π) = E[Σₜ γᵗ φ(sₜ) | π] — the discounted, expected feature counts a policy racks up. Because the value function is then V^π(s₀) = w·μ(π), two policies have equal value under R if they have equal feature expectations under w — and, provided w ≠ 0, only if: a degenerate w = 0 collapses every policy’s value to zero regardless of how its features differ. Abbeel and Ng's apprenticeship-learning algorithm (ICML 2004) exploits this: find w such that the expert's feature expectation μ_E out-scores every candidate policy's feature expectation by the largest possible margin, then solve forward RL under that w, compare feature expectations, and iterate.

Worked example: recovering a driver's reward function from one choice

An experienced Bengaluru cab driver, given a choice between the elevated highway and a local service road to the airport during peak hours, consistently takes the local road. Model each route by two cost features: φ₁ = normalized travel time, φ₂ = toll indicator.

Route A (highway):    phi = (0.2, 1)   -- fast, but tolled
Route B (local road):  phi = (0.5, 0)   -- slower, toll-free
Expert always chooses Route B.

Assume the driver's true reward is a negative cost, R(route) = −(w₁φ₁ + w₂φ₂), with w₁, w₂ ≥ 0 the (unknown) weights the driver places on time and tolls. Rational choice of B over A requires cost(B) ≤ cost(A):

0.5w1 + 0·w2  ≤  0.2w1 + 1·w2
0.3 w1  ≤  w2

Any pair (w₁, w₂) with w₂ ≥ 0.3w₁ explains the observed choice — for instance w₁ = 1, w₂ = 0.5 gives cost(B) = 0.5 and cost(A) = 0.7, correctly ranking B below A in cost. This single inequality is the entire content of one IRL "training example," and it already displays the ill-posedness Ng and Russell warned about: w₁ = 0, w₂ = 1 (the driver cares about tolls only) satisfies it just as well as w₁ = 1, w₂ = 0.5 (the driver mildly prefers avoiding tolls but time still matters), and so does every point on that half-plane. One demonstration only carves out a region of consistent reward functions, not a single answer. Real IRL systems narrow this region by using many demonstrations across many route pairs (each new choice adds another linear constraint on w) and by adding a preference for the largest-margin or maximum-entropy solution rather than an arbitrary corner of the feasible region — exactly the reason Ziebart, Maas, Bagnell, and Dey's Maximum Entropy IRL (AAAI 2008) was developed alongside closely related work using real Pittsburgh taxi GPS traces to model driver route preferences: with a stochastic softmax model instead of a hard margin, it also tolerates the reality that even skilled drivers do not take the literally optimal route on every single trip.

Max-margin versus maximum-entropy: one paragraph of contrast

Abbeel and Ng's max-margin formulation assumes the expert is exactly optimal and asks for the w that maximizes the gap between μ_E and the best competing policy's feature expectations — clean, but brittle if the expert occasionally takes a slightly suboptimal action, since a single outlier trajectory can swing the recovered w. Maximum Entropy IRL instead models trajectories as being sampled with probability proportional to exp(w·Σφ(sₜ)) — high-reward trajectories are more likely, not certain — and picks the w that makes the expert's observed trajectories look as probable as possible under this distribution while adding no more structure than the data demands (the maximum-entropy principle). This is why MaxEnt IRL, not max-margin, became the standard choice for modelling noisy human behaviour such as driving routes or pedestrian paths, while max-margin remains attractive when demonstrations really are close to optimal, such as a robot-arm trajectory recorded from a precision industrial task.

Mechanism diagram

Active recall

Attempt every question before reading its answer.

1. Why does the potential-based shaping theorem require Φ(terminal state) = 0, and what breaks if you set it to a nonzero value like Φ(s2) = 10 instead?
2. A robotics team shapes their maze-solving agent with F(s,a,s′) = 3 whenever the agent moves into any square adjacent to a wall it has not visited before. Is this potential-based shaping? Will it necessarily preserve the optimal policy?
3. Using the delivery-robot MDP in this chapter (γ = 0.9, raw reward R(s1,advance,s2)=10, all else 0), compute Φ(s0) and Φ(s1) needed if you instead wanted Φ(s) = −2 × (steps remaining), and recompute F(s0,advance,s1).
4. Two candidate cab routes have features Route C = (0.3, 0) and Route D = (0.1, 1) (time, toll). If the expert always takes Route D, derive the constraint on weights w1, w2 analogous to the worked example.
5. Explain in one or two sentences why inverse RL is called "ill-posed," and name one algorithm (with author/year) that adds structure to resolve the ambiguity.
6. A classmate claims: "Since reward shaping and IRL both use a linear combination of state features, they must be solving the same optimization problem, just in opposite directions." Is this accurate? What is actually different between the two problems' inputs and outputs?

Worked answers

1. The invariance proof relies on the shaping sum telescoping to γᵀΦ(s_T) − Φ(s₀) along any trajectory. If Φ(s_T) ≠ 0, this residual term still depends on T (the trajectory length) and on which terminal potential was reached, so it no longer reduces to a pure function of the start state alone — different policies that terminate at different times or, in a multi-goal setting, different terminal states, would have their returns shifted by different amounts, which can change the argmax. With Φ(s2) = 10 in the chapter's first (rejected) construction, the clean relation V′*(s) = V*(s) − Φ(s) failed exactly as shown by the numeric check.

2. No. This bonus depends on the action taken (moving into a wall-adjacent square) and on visitation history (not visited before), neither of which is a static function Φ(s) of state alone that could appear in γΦ(s′) − Φ(s). It cannot be written in the required telescoping form, so the invariance theorem does not apply — it is exactly the shape of shaping that produced the loop-forever failure in the worked example, and it can, though will not always, distort the optimal policy toward wall-hugging behaviour instead of maze-solving.

3. Steps remaining: s0 is 2 steps from goal, s1 is 1 step. Φ(s0) = −2×2 = −4, Φ(s1) = −2×1 = −2, Φ(s2) = 0. F(s0,advance,s1) = 0.9×(−2) − (−4) = −1.8 + 4 = 2.2.

4. Cost(D) ≤ Cost(C) since the expert chooses D: 0.1w1 + 1w2 ≤ 0.3w1 + 0w2, which gives w2 ≤ 0.2w1 — the reverse-shaped inequality from the chapter's example, because here the expert is choosing the route with the higher toll feature, so tolls must matter less relative to time for this expert (w2 must be small relative to w1).

5. IRL is ill-posed because many, often infinitely many, reward functions (including the trivial all-zero reward) make any given policy optimal, so demonstrations alone cannot pin down a unique reward without extra assumptions. Abbeel and Ng's max-margin apprenticeship learning (ICML 2004) resolves this by picking the weight vector that maximizes the margin between the expert's feature expectations and the best alternative policy's; Ziebart et al.'s Maximum Entropy IRL (AAAI 2008) resolves it instead by picking the least-committal (maximum-entropy) distribution over trajectories consistent with matching the expert's feature expectations.

6. Not accurate. Reward shaping starts from a known R (or equivalently a known w) and asks for an auxiliary term that accelerates finding π* without changing it — the input is the reward, the output is a modified reward for the same fixed problem. IRL starts from a known π (via expert trajectories) and asks which R would make that π optimal — the input is behaviour, the output is a reward function, and the map from R to π* is many-to-one, which is exactly why IRL, unlike shaping, is fundamentally underdetermined and needs a margin or entropy criterion to select one answer.

Think About It

Think about this: How would you explain reward shaping and inverse rl 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.

Practice Exercises

Now it is time to practice! Complete these challenges to solidify your understanding:

• Exercise 1: Write a short program that demonstrates the core concept from this chapter. Test it with at least 3 different inputs.
• Exercise 2: Find a real-world example where reward shaping and inverse rl is used in an Indian company (like TCS, Infosys, Flipkart, or ISRO). Write a paragraph explaining the connection.
• Exercise 3: Create a mind-map connecting reward shaping and inverse rl to at least 3 other topics you have studied.