Reward Shaping: Guiding Learning

A Swiggy-style instant-delivery agent is being trained to route a rider through a city's block grid to a customer's door. The only reward the designers trust is the one that actually matters: +10 when the parcel is delivered, 0 on every other move. Everything else — fuel burned, minutes elapsed, distance covered — is a proxy the designers deliberately refuse to hard-code, because proxies get gamed. The agent starts at a random intersection and must learn, purely from trial and error, which turns lead to a doorstep it has never seen.

Here is the problem. Under a uniform random policy, the number of moves needed to first stumble onto a fixed target on an L × L street grid grows roughly with L² (up to logarithmic factors) — a standard scaling property of two-dimensional random walks. On a 4×4 toy grid that is a nuisance; on a real 50-block city grid it is fatal to training. Almost every trajectory the agent generates in early training ends in reward 0, over and over, with no signal at all about whether a given turn was good or bad. This is the sparse reward / credit assignment problem: the only informative reward arrives so rarely, and so far downstream of the decisions that caused it, that gradient signal is nearly absent for most of training. Reward shaping is the technique for fixing this without lying to the agent about what the task actually is.

The setup: MDPs and the shaping transformation

Recall the Markov Decision Process tuple (S, A, P, R, γ): a set of states, a set of actions, transition dynamics P(s′|s,a), a reward function R(s,a,s′), and a discount factor γ ∈ [0,1) that shrinks the value of reward received t steps in the future by a factor of γ^t. An agent's goal is to find a policy π that maximises the expected discounted return G = Σ γ^tr_t.

Reward shaping replaces R with a transformed reward R′(s,a,s′) = R(s,a,s′) + F(s,a,s′), where F is an extra term the designer adds to make learning faster. The delivery agent's designer is tempted to set F to something like "+1 for every move that decreases straight-line distance to the customer." That instinct is correct in spirit and dangerous in its naive form — the rest of this chapter is about the one formula that makes it safe.

Potential-based shaping: the formula that cannot lie

In 1999, Andrew Ng, Daishi Harada, and Stuart Russell proved a theorem (Policy invariance under reward transformations, ICML 1999) that gives a precise recipe. Define a potential function Φ: S → ℝ, a single number attached to every state that represents how "promising" that state looks — for the delivery agent, a natural choice is Φ(s) = −distance(s, customer). Then set the shaping term to

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

Their theorem: for any choice of Φ, in this exact form, every optimal policy under R′ = R + F is also optimal under the original R, and vice versa. The shaped MDP and the original MDP disagree wildly on the numeric value of any given trajectory, but agree perfectly on which policy is best. You get to make the reward dense and immediate without ever changing what "winning" means.

If you have studied A* search, this should feel familiar. A* uses a heuristic h(s) to steer search toward the goal faster, and guarantees the shortest path is still found provided h is consistent (h(s) ≤ cost(s,s′)+h(s′)). Potential-based reward shaping is the reinforcement-learning analogue: Φ steers learning toward good behaviour faster, and guarantees the optimal policy is unchanged, provided Φ is folded in through the exact γΦ(s′) − Φ(s) form. Both are cases of a guiding function that is only safe when it obeys a specific consistency rule — get the rule wrong in either setting and the guide starts lying.

Why the formula works: telescoping

Write out the discounted sum of shaping rewards along one trajectory s₀, s₁, …, s_T:

Σ(t=0 to T-1) γ^t · F(s_t,a_t,s_{t+1})
  = Σ γ^t · [γΦ(s_{t+1}) − Φ(s_t)]
  = Σ [γ^{t+1}Φ(s_{t+1}) − γ^t Φ(s_t)]

Every interior term cancels — the γ¹Φ(s₁) produced at t=0 is exactly cancelled by the −γ¹Φ(s₁) produced at t=1, and so on down the line. Only the two ends survive:

Σ(t=0 to T-1) γ^t F_t = γ^T·Φ(s_T) − Φ(s_0)

The entire shaping bonus collected over an arbitrarily long, winding trajectory collapses to a number that depends only on where you started and where you ended, never on the path taken in between. That is precisely why it cannot change which policy looks best: two different paths from the same start to the same end receive the identical total bonus, so the shaping term can never flip the ranking between them.

Worked example: a 4×4 delivery grid

Take the rider on a 4×4 block grid, rows and columns 0–3, starting at (0,0), customer at (3,3). Base reward: +10 on the transition that reaches (3,3), 0 everywhere else. Discount γ = 0.9. Potential Φ(s) = −Manhattan_distance(s, goal), so Φ(3,3) = 0 exactly, as the theorem requires for the terminal state.

Follow one optimal six-move path: (0,0)→(0,1)→(0,2)→(0,3)→(1,3)→(2,3)→(3,3). The Manhattan distance to the goal at each stop is 6,5,4,3,2,1,0, so:

Before shaping, the agent received exactly one nonzero number, +10, on move 6, and pure zeros on every earlier move — no signal to tell it move 1 was a good idea. After shaping, every single move now returns a reward between 1.0 and 1.5, immediately telling the agent "correct direction" the moment it happens, five full moves before the original signal would have arrived.

Now verify the telescoping identity numerically rather than trusting it. The discounted sum of the F column:

1·1.5 + 0.9·1.4 + 0.81·1.3 + 0.729·1.2 + 0.6561·1.1 + 0.59049·1.0
= 1.5 + 1.26 + 1.053 + 0.8748 + 0.72171 + 0.59049
= 6.0

and the closed form predicts γ⁶Φ(s₆) − Φ(s₀) = 0.531441·0 − (−6) = 6.0. They match exactly, because Φ(goal)=0 makes every term of the closed form except −Φ(s₀) vanish — meaning any path the rider takes from (0,0) to the goal collects exactly a 6.0 shaping bonus in total, regardless of length or route, which is exactly the path-independence the invariance theorem relies on.

The full picture: the unshaped discounted return is G = γ⁵·10 = 5.9049 (the +10 arrives on the sixth reward, at index t=5). The shaped return is G′ = G + 6.0 = 11.9049. Every path to the goal gets the same +6.0 tacked on, so the six-move path still beats every longer path exactly as it did before shaping — the ranking, and therefore the optimal policy, is untouched.

Here is that same computation traced in code, with every intermediate value rounded so the printed output is exact and reproducible:

def manhattan(a, b):
    return abs(a[0]-b[0]) + abs(a[1]-b[1])

goal = (3, 3)
gamma = 0.9

def phi(s):
    return -manhattan(s, goal)

path = [(0,0),(0,1),(0,2),(0,3),(1,3),(2,3),(3,3)]

shaped_rewards = []
for t in range(len(path) - 1):
    s, s_next = path[t], path[t + 1]
    base_r = 10 if s_next == goal else 0
    F = round(gamma * phi(s_next) - phi(s), 4)
    shaped_rewards.append(round(base_r + F, 4))

print(shaped_rewards)
# [1.5, 1.4, 1.3, 1.2, 1.1, 11.0]

discounted_return = sum(round((gamma**t) * r, 6)
                         for t, r in enumerate(shaped_rewards))
print(round(discounted_return, 4))
# 11.9049

Tracing it by hand: phi returns negative integer Manhattan distances, so every F value matches the table above exactly (1.5, 1.4, 1.3, 1.2, 1.1, 1.0), and adding base_r=10 only on the final step gives shaped_rewards = [1.5, 1.4, 1.3, 1.2, 1.1, 11.0]. The second loop multiplies each entry by γ^t for t=0..5 (1, 0.9, 0.81, 0.729, 0.6561, 0.59049) and sums, reproducing 11.9049 to four decimal places — the same number derived by hand above.

The diagram: where the shaping term enters the learning loop

Common misconception: "any Φ that points toward the goal is safe"

Students who have just seen the invariance theorem often overgeneralise it to: "as long as I add a bonus for getting closer to the goal, the optimal policy can't change." The theorem has a boundary condition that this drops: for tasks with a terminal state, Φ must satisfy Φ(terminal) = 0. Without it, the guarantee silently fails.

Consider a tempting alternative for the delivery agent: instead of a distance-based Φ, just give a flat "+1 for staying on the road, still en route" bonus every step, independent of state — the reinforcement-learning equivalent of Pong's classic "+0.01 survival bonus" that keeps an agent alive longer per rally. Can this be written as valid potential-based shaping with Φ(terminal)=0? Solve for it directly: we need γΦ(s_t+1) − Φ(s_t) = 1 for every non-terminal transition, with Φ(terminal)=0 fixed. Working backward from the terminal state, if a state is k steps from termination, this recursion forces

Phi(s at k steps from terminal) = -(1 + gamma + gamma^2 + ... + gamma^(k-1))
                                = -(1 - gamma^k) / (1 - gamma)

This value depends on k, the number of steps remaining — not on any property of the state itself. In Pong, the exact same board configuration (ball position, paddle positions) can occur five moves into a rally or fifty moves into a rally. A legal potential function must assign one fixed number to that configuration no matter how it was reached; this recursion demands two different numbers for the identical state depending on rally length so far. That is not a function of state — so a flat step-survival bonus is not expressible as valid potential-based shaping. The theorem's guarantee never applied to it in the first place, and in practice it does exactly what the algebra predicts: agents trained with such bonuses learn to prolong the episode — batting the ball back forever rather than trying to win the point — because episode length itself, not the true task, has become the thing being rewarded.

The fix is not to abandon shaping; it is to insist Φ be a genuine function of state alone (as −distance(s, goal) is, since it does not care how the agent arrived at s) and to pin Φ(terminal)=0 for every absorbing state the episode can end in. Get those two conditions right and the theorem's guarantee is airtight, as the 6.0-for-every-path result above demonstrates.

Active recall

Attempt each question before reading its answer.

1. In one sentence, what problem does reward shaping solve, and what specific mathematical form must the shaping term F take to guarantee the optimal policy is unchanged?
2. A 1D corridor has 5 cells, positions 0–4, goal at cell 4. Φ(s) = −(4−s), γ = 0.8. The agent walks 0→1→2→3→4. Compute F at each of the 4 steps and the discounted sum Σγ^tF_t. Verify it against γ^TΦ(s_T) − Φ(s₀).
3. Why does the invariance theorem require Φ to depend only on the state s (and not on the action a taken to leave it, nor on the trajectory history)?
4. A designer gives a Pong agent +0.05 every timestep it stays alive, hoping to speed up learning. Is this potential-based shaping? What failure mode should the designer expect?
5. You are shaping the reward for a UPI bill-splitting reminder bot, which currently only gets +5 the moment a debtor actually repays (which can happen weeks later). Propose a potential function Φ for the intermediate states (reminder sent, debtor viewed, debtor acknowledged, promised a date) and confirm your Φ satisfies the terminal condition.

Worked answers

1. Reward shaping solves the sparse-reward / credit-assignment problem, where a designer's trusted reward arrives too rarely for gradient-based learning to make progress. The safe form is potential-based shaping, F(s,a,s′) = γΦ(s′) − Φ(s) for some real-valued state function Φ, which the Ng–Harada–Russell theorem proves leaves the optimal policy unchanged.

2. Φ(0)=−4, Φ(1)=−3, Φ(2)=−2, Φ(3)=−1, Φ(4)=0.
F1 = 0.8(−3)−(−4) = 1.6
F2 = 0.8(−2)−(−3) = 1.4
F3 = 0.8(−1)−(−2) = 1.2
F4 = 0.8(0)−(−1) = 1.0
Discounted sum = 1·1.6 + 0.8·1.4 + 0.64·1.2 + 0.512·1.0 = 1.6+1.12+0.768+0.512 = 4.0.
Closed form: γ⁴Φ(s₄) − Φ(s₀) = 0.4096·0 − (−4) = 4.0. Matches exactly.

3. The telescoping proof relies on γΦ(s_t+1) being produced at time t and exactly cancelled by −Φ(s_t+1) at time t+1. If F depended on the action taken or on how s_t+1 was reached, the two occurrences of "Φ(s_t+1)" in the cancellation would no longer be the same number, and the sum would no longer collapse to a pure boundary term — the shaping bonus would then depend on path, not just endpoints, and could reorder policies.

4. No — as shown in the misconception section, a flat constant-per-step bonus cannot be written as γΦ(s′)−Φ(s) with Φ(terminal)=0 once the same physical state can occur at different distances from termination, which is true of Pong. Expect the agent to learn to prolong rallies rather than win points, since episode length is now directly rewarded.

5. A reasonable Φ ranks states by proximity to actual repayment: Φ(reminder sent) = −3, Φ(debtor viewed) = −2, Φ(debtor acknowledged) = −1.5, Φ(promised a date) = −1, Φ(repaid) = 0. This satisfies the terminal condition because Φ(repaid) = 0 exactly, so — as in the delivery-grid example — every path to repayment collects the same total shaping bonus (3.0, before discounting) regardless of how many reminders it took, and the bot's true objective (getting paid, not generating engagement with reminders) is never distorted into over-rewarding activity that never converts.

Think About It

Think about this: How would you explain reward shaping: guiding learning 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 reward shaping: guiding learning, 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.