M5-T2 — Reward Shaping and Potential Functions

Learning objectives

After this lesson, you should be able to:

• Write the shaped reward r + γφ(s′) − φ(s), including the rule φ(terminal) = 0 for episodic tasks.
• State the policy-invariance theorem and explain it through the identity Q*_shaped(s, a) = Q*(s, a) − φ(s).
• Give a numeric counterexample in which a shaping bonus that is not a potential changes the optimal policy.
• Choose a potential (negative walking distance to the goal) and explain why straight-line distance through walls is a bad one even though it is also “correct”.

The intuition

Think of a hiking trail with signposts that say “2 km to the summit”. Each time you walk past a post that is closer than the last, you feel progress. If someone moved the posts so that you pass a “1 km” sign, then a “2 km” sign, then a “1 km” sign again, you would feel progress twice and lose it once. As long as every sign reads a fixed distance from a fixed place, the feelings add up to “distance covered” and nothing else. That is a potential: a number attached to places, not to moves. Paying for the change in that number as you move cannot be gamed, because going around any loop returns you to the same place and the changes sum to zero.

Now the contrast. A bonus of +1 “whenever the move gets closer to the goal” is attached to moves, not places. Step closer (+1), step back (0), step closer again (+1): the loop pays. The figure shows the second danger: even a true potential can be a bad one. Straight-line distance from the circled cell is 4.0, much better than from the start (8.0), but the walkable route from there is 8 moves, only 4 better than from the start. A learner that follows the straight-line hint is drawn toward the wall, because every move away from it, which is the way around, looks like a loss.

The mathematics

Shaping in one line

Keep the Markov decision process (lesson M4-T1) and change only its reward. For a function φ from states to real numbers, the shaped reward is

φ(s)

the potential of state s: a number you choose per state, for example minus the walking distance to the goal.

F

the shaping term. It depends on the move only through the two states it connects.

γ

the discount factor of the task. It must be the same γ in F as in the return.

terminal

a state that ends the episode. Its potential must be 0 (or, equivalently, the term γφ(s′) is dropped on the step that ends the episode). Truncating at a time limit is not terminal: there φ(s′) is used as usual.

The policy-invariance result

Ng, Harada and Russell (1999) proved, for a finite MDP, that shaping with a term of this form leaves the set of optimal policies unchanged: every policy that is optimal in the shaped MDP is optimal in the original and conversely. They also proved the converse: if F is not of this form, there exist transition and reward functions for which the shaped MDP has an optimal policy that is not optimal in the original. So a difference of potentials is the only shaping form that is safe for every task. In the episodic case the theorem needs φ to be 0 at the terminal state (in the paper, an absorbing state), which is the rule in the formula above.

Why it works: a proof sketch

Write Q* for the optimal action values of the original MDP, which satisfy the Bellman optimality equation (lesson M4-T3). Claim: the shaped MDP has optimal action values

Check that the right-hand side satisfies the shaped Bellman equation. Its target for a step to s′ is r + γφ(s′) − φ(s) + γ max_a′ [ Q*(s′, a′) − φ(s′) ]. The term γφ(s′) cancels, because φ(s′) does not depend on a′ and so passes out of the max. What is left is r + γ max_a′ Q*(s′, a′) − φ(s), whose expectation is Q*(s, a) − φ(s), the claimed value. The Bellman optimality operator has a unique fixed point, so this is Q*_shaped. At a terminal state the target is the reward alone, and the identity holds there exactly because φ(terminal) = 0.

Now the policy. φ(s) is subtracted from every action at s by the same amount, so the maximising action at each state is unchanged. A second way to see it: along any trajectory the shaping terms telescope. The discounted sum of F over a trajectory that ends at a terminal state is −φ(s₀), a constant fixed by where you start, so shaping shifts every return from s₀ by the same amount and no policy overtakes another.

Two consequences to remember

• Shaping moves the value, not the answer. V*_shaped(s) = V*(s) − φ(s). With a negative-distance potential the shaped values are larger than the true ones, by up to the distance. Do not report shaped returns as task performance; evaluate with the original reward.
• The constant in φ is free but not harmless for learning. Replacing φ by φ + c on non-terminal states keeps the optimal policy (it shifts every Q by −c) but changes what a zero-initialised table looks like to the learner. Wiewiora (2003) showed that potential-based shaping is equivalent to initialising the Q values to the potential, so a constant offset is an optimistic or pessimistic start. The experiments below show how large that effect is.

What shaping does not fix

The theorem is about the optimal policy of the MDP. It says nothing about whether a learner with finite time, an exploration rule and an approximate value function will reach it, and it needs a well-chosen φ to speed anything up. A potential that is wrong about the task (lesson example 5) leaves the answer intact and the learning slow.

A worked example

Every number below was computed with RLCore (value iteration to 10⁻¹²; Q-learning with SLAMCore.rng seeds 1 to 20).

1. A hand-checkable chain. Four cells S . . G, moves left and right, γ = 0.9, reward 0 except +10 on entering G. Optimal values: Q*(right) = 8.1, 9.0, 10.0 at cells 0, 1, 2 (they are 10 × 0.9², 10 × 0.9, 10). Use φ = (−3, −2, −1) at cells 0, 1, 2 (minus the distance to G) and φ(G) = 0. The shaping terms for the move right are

The identity Q*_shaped = Q* − φ holds to every digit, for the move left as well (Q*(left) = 7.29, 7.29, 8.1 against shaped 10.29, 9.29, 9.1; the differences are 3, 2, 1). The best action in each cell is still right.

2. The terminal rule matters. Corridor G..S....G with the near exit (3 cells left) paying +3, the far exit (5 cells right) paying +10, step cost −4, γ = 0.95. Without shaping the near exit is best (Q(S, left) = −8.703 against −9.952 for right). Shape with φ = minus the distance to the far exit, φ(S) = −5 and φ(near exit) = −8. With φ(terminal) treated as 0 the policy is unchanged (still the near exit) and V(S) = −3.702 = −8.703 − φ(S). If the code forgets the rule and uses φ(near exit) = −8 on the step that enters it, that step receives an extra 0.95 × (−8) = −7.6; the near exit is now worse and the policy switches to the far exit (V(S) = −4.952). Reward shaping broke the task, with a formula that looks right.

3. A bonus that is not a potential. Corridor S.....G (six moves), step cost −0.1, goal +10, γ = 0.95, honest value of the start 7.208. Add a bonus c whenever a move enters a cell with a smaller walking distance to G. This is a function of the move, not a difference of potentials: stepping back costs nothing. With c up to 1, value iteration still walks to the goal (value 12.506 at c = 1, shaped). At c = 1.5 the optimal policy is >>>>><G: it walks to cell 5 and then goes back to cell 4, for ever. Each lap pays 1.5 − 0.1 − 0.1 = 1.3, a lap value of about 13.3 (1.3 / (1 − 0.95²)) beats finishing, and the true value of that policy is −2.000 (the step costs of a task that never ends, −0.1 / 0.05) instead of 7.208. Bisection puts the switch at c ≈ 1.361. The same bonus on the ward of lesson M4-T4 (slip 0.2): c = 1 changes nothing, c = 2 changes the optimal action in 5 of 23 cells and the true value of the policy at the start drops from 3.314 to −2.000. A potential-based hint cannot do this: its total around any lap is bounded by the telescoped constant.

4. Invariance on the hall. The hall of the figure has slip 0.1, goal +10 and no other reward, γ = 0.99, so the optimal value of the start is 8.828 and the walk is 12 moves. Shaping with φ = −(walking distance) gives V*_shaped(S) = 20.828 = 8.828 + 12, and with φ = −(straight-line distance) 16.828 = 8.828 + 8. In both cases the optimal action is identical in every cell (0 differences) and the largest gap between V*_shaped and V* − φ over all cells is 2 × 10⁻¹³.

5. Learning speed on the hall (20 seeds). Q-learning, α = 0.2, ε = 0.1, 500 episodes, up to 200 steps each, γ = 0.99. “First success” is the first episode in which Scout reaches the goal. “Final” is the exact value, under the original reward, of the greedy policy after 500 episodes (optimal: 8.828).

Both shaped versions have exactly the same optimal policy, as example 4 shows; only the first one lets Scout find it. With the straight-line potential no seed ends with a greedy policy that reaches the goal. The likely mechanism, which I did not measure cell by cell, is the one in the figure: moves toward the wall pay and moves away from it cost, and ε = 0.1 rarely carries Scout along the bottom row and through the gap often enough to overturn that.

6. The offset of φ. Repeat at γ = 0.95 (optimal value 5.308). With φ = −d (walking distance) 8 of 20 seeds reach the goal, final mean 0.50; with the straight-line version, 0 of 20. Now add a constant, φ = d_max − d (non-negative, φ(G) still 0 by the rule): both versions reach the goal in 20 of 20 seeds, median first success episode 1, final means 5.22 (walking distance) and 5.19 (straight line), and all 20 seeds within 10 % of optimal in both. The optimal policy did not change; the table started out looking optimistic and Scout explored. This is the initialisation equivalence at work, and it also means the apparent advantage of a “good” potential in a given experiment is mixed with the effect of its offset. Treat a comparison at one offset as evidence about that offset.

What the simulation simplifies. One hall, one wall, tabular Q-learning, one learning rate and one ε, 500 episodes. Different values give different numbers (example 6 already moves them a lot), so read the table as a demonstration of mechanisms, not as measurements of how much shaping helps on a robot.

Engineering implications and limitations

How to shape safely

1. Pick a potential that measures progress in the way the robot can actually move: walking distance from a planner or a breadth-first search over the map, not straight-line distance, when walls matter (lab M5-L1 has you build one).
2. Implement F = γφ(s′)(1 − done) − φ(s) with the same γ the learner uses, and the end-of-episode flag for real terminals only (lesson M4-T6). Time-limit truncation is not terminal.
3. Add F to the reward the learner sees, but evaluate and log the original reward. If the shaped return improves while the task return does not, the potential is misleading.
4. Scale φ so one step of progress is comparable to the other terms. A potential with huge steps dominates the task reward; with tiny ones it changes nothing.
5. Test invariance on a small instance: solve both versions exactly and check the optimal policies agree. A failure means the formula, the terminal rule or γ is wrong (lab M5-L1 grades exactly this).

Shaping and function approximation

The theorem is for the exact optimal policy. With neural networks (lesson M6) the shaped and original problems have the same optimum but different learning dynamics and different approximation errors, so shaping can help or hurt. It remains the safest way to add dense hints, and the invariance argument is why it is preferred to ad hoc bonuses.

Partial knowledge is fine

The potential need not be the true optimal value. It can be a rough planner estimate, a heuristic of the kind used in A* search, or a learned value from a simpler task. A better φ gives a faster start (if φ equalled −V* the shaped values would be 0 everywhere and greedy action selection would already be optimal), while a poor one costs time without costing correctness.

Shaping is not safety

Policy invariance is a statement about the optimum. During learning the robot still follows the hints, and a hint toward a stairwell edge is a hint toward a stairwell edge. Constraints belong in lesson M5-T5, not in φ.

Common misconceptions

Engineering takeaways

1. Potential-based shaping adds γφ(s′) − φ(s) to the reward, with φ = 0 at terminal states; it leaves the set of optimal policies unchanged and shifts the optimal action values by −φ(s).
2. The proof is two lines: Q* − φ satisfies the shaped Bellman equation, and subtracting a number that depends only on s cannot change the argmax over a. Along a trajectory the shaping terms telescope.
3. A bonus attached to moves rather than places (for example +c for getting closer) can create loops that pay for ever: on a six-move corridor it changed the optimal policy at c ≈ 1.36.
4. A good potential (negative walking distance) made 20 of 20 seeds reach a goal that sparse reward never reached in 500 episodes; straight-line distance through a wall has the same optimum and reached it in 5 of 20.
5. The offset of φ acts like an optimistic or pessimistic initialisation; it does not change the optimum but changes learning, so evaluate shaping with the original reward and over several seeds.

References and further reading

The theorem and its converse are in the first reference; the equivalence with Q-value initialisation is in the second.

• A. Y. Ng, D. Harada and S. Russell, “Policy invariance under reward transformations: theory and application to reward shaping”, Proceedings of the 16th International Conference on Machine Learning (ICML), 1999.
• E. Wiewiora, “Potential-based shaping and Q-value initialization are equivalent”, Journal of Artificial Intelligence Research 19, 205–208, 2003.
• J. Randløv and P. Alstrøm, “Learning to drive a bicycle using reinforcement learning and shaping”, Proceedings of the 15th International Conference on Machine Learning (ICML), 1998 (a progress bonus that is not a potential makes the bicycle ride in circles).

Knowledge check

Three conceptual questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

What’s next

Next: shaping is one answer to rewards that are too quiet. Lesson M5-T3 compares sparse, shaped and dense rewards directly, by learning speed and by the behaviours they invite.

Related content

Nothing below is required to finish this lesson.

• Before
  M5-T1: What a Reward Really Says

  Explain that the agent optimizes the reward written and not the intention, and give examples of the gap.

• Lab
  M5-L1: Shape a Reward Without Changing the Task

  Learning is too slow on the long corridor: add progress shaping that keeps the same best route.