Reward shaping and sparse rewards: Exercises — AI-ML deep dive

Before we start, one symbol reminder so nothing is used unearned:

Definition Symbols used on this page

$s, s^{'}$ — a state and the next state (where the agent is, and where it lands next).
$a$ — an action the agent takes.
$R (s, a, s^{'})$ — the environment reward, the real number the world hands back.
$γ$ — the discount factor, a number in $[0, 1)$ that shrinks future rewards.
$Φ (s)$ — a potential, any number we assign to each state (think "height on a landscape").
$s_{T}$ — the terminal state where an episode ends. We use the standard convention $Φ (s_{T}) = 0$ : the potential of any end-of-episode state is set to zero, so it contributes no leftover boundary term.
$F (s, a, s^{'})$ — the shaping term we add: $R^{'} = R + F$ .
$G_{t}$ — the return, the discounted sum of rewards from time $t$ onward.
$V^{π} (s), Q^{π} (s, a)$ — value functions: expected return from a state (or state-action).

The five exercise levels below form a staircase of rising difficulty. The figure makes that ladder explicit — read it left to right, and notice the accent-red top step (Mastery) is where the discount-factor subtleties bite hardest.

Figure — Reward shaping and sparse rewards

Figure s01 — the D4 difficulty ladder: each black step is a level (L1→L5), and the red node marks L5 Mastery, the rung where the $γ < 1$ telescoping identity of Exercises 5.1–5.2 must be handled with care.

Level 1 — Recognition

Exercise 1.1

Which of these reward functions is sparse, and which is dense?

(a) $+ 1$ only when the agent reaches the goal cell, else $0$ .
(b) $- 1$ every single step until the goal is reached.

Recall Solution 1.1

(a) is sparse — the reward is $0$ almost everywhere, non-zero only at the rare goal state. Along a 200-step episode you might see a single non-zero number. (b) is dense — every step delivers an informative $- 1$ , telling the agent "still not done, hurry up." There is a gradient of "warmer/colder" at every step. Why the distinction matters: in (a) the learned $Q$ -values stay flat (all $\approx 0$ ) over visited states, so no action looks better than another until the goal is hit by luck. That is the whole reason we shape rewards.

Exercise 1.2

State the potential-based shaping (PBRS) formula from memory, including the role of every symbol.

Recall Solution 1.2

$F (s, a, s^{'}) = γ Φ (s^{'}) - Φ (s) .$

$Φ$ is any function from states to real numbers you choose.
$γ Φ (s^{'})$ is the (discounted) potential of the state you enter.
$Φ (s)$ is the potential of the state you leave. The bonus is "discounted new height minus old height." Because entering and leaving cancel, loops net to zero.

Level 2 — Application

Exercise 2.1

Goal at $(0, 0)$ ; sparse reward $+ 1$ on reaching it. Use $γ = 0.9$ and potential $Φ (s) = - d (s)$ where $d$ is Manhattan distance to the goal. The agent moves from a cell with $d = 3$ to a cell with $d = 2$ . Compute the shaping bonus $F$ .

Recall Solution 2.1

$F = γ Φ (s^{'}) - Φ (s) = 0.9 \cdot (- 2) - (- 3) = - 1.8 + 3 = 1.2 .$ What it looks like: the agent stepped toward the goal (height rose from $- 3$ to $- 2$ ), so it earns a positive nudge. It now has a gradient at this step even though the real reward is still $0$ here.

Exercise 2.2

Same setup, but the agent moves away: from $d = 3$ to $d = 4$ . Compute $F$ .

Recall Solution 2.2

$F = 0.9 \cdot (- 4) - (- 3) = - 3.6 + 3 = - 0.6 .$ Moving away is penalized. Notice the toward-bonus ( $+ 1.2$ ) and away-penalty ( $- 0.6$ ) are not equal magnitudes — the discount $γ$ makes them asymmetric. That asymmetry is exactly what preserves policy invariance in the discounted setting.

Exercise 2.3

A loop: agent goes $s_{A} \to s_{B} \to s_{A}$ with $γ = 1$ , $Φ (s_{A}) = 2$ , $Φ (s_{B}) = 7$ . Compute the total shaping reward over the loop.

Recall Solution 2.3

Step $s_{A} \to s_{B}$ : $F = 1 \cdot Φ (s_{B}) - Φ (s_{A}) = 7 - 2 = 5$ .
Step $s_{B} \to s_{A}$ : $F = 1 \cdot Φ (s_{A}) - Φ (s_{B}) = 2 - 7 = - 5$ .
Total $= 5 + (- 5) = 0$ . Why: the entry bonus is exactly undone by the exit penalty. Loops earn nothing ⇒ no incentive to spin in circles ⇒ no reward hacking. (This clean cancellation is the special case $γ = 1$ ; Exercise 5.1 shows what changes when $γ < 1$ .)

Level 3 — Analysis

Exercise 3.1

Prove that under PBRS the shaped return satisfies $G_{0}^{'} = G_{0} - Φ (s_{0})$ for the infinite trajectory $s_{0}, s_{1}, s_{2}, \dots$ . State where each simplification comes from.

Recall Solution 3.1

Step 1 — Write the shaped return. $G_{0}^{'} = \sum_{t = 0}^{\infty} γ^{t} (r_{t} + γ Φ (s_{t + 1}) - Φ (s_{t})) .$ Step 2 — Split linearly. $G_{0}^{'} = G_{0} t \sum γ^{t} r_{t} + T t = 0 \sum \infty γ^{t} (γ Φ (s_{t + 1}) - Φ (s_{t})) .$ Step 3 — Telescope $T$ . The potential $Φ (s_{k})$ appears with coefficient $+ γ \cdot γ^{k - 1} = γ^{k}$ (from the $γ Φ (s_{t + 1})$ piece at $t = k - 1$ ) and $- γ^{k}$ (from the $- Φ (s_{t})$ piece at $t = k$ ). These annihilate for every $k \geq 1$ . Only $- Φ (s_{0})$ (from $t = 0$ ) survives. Step 4 — Collect. $T = - Φ (s_{0})$ , so $G_{0}^{'} = G_{0} - Φ (s_{0})$ . $■$ Assumption used: $γ^{t} Φ (s_{t}) \to 0$ as $t \to \infty$ (true since $γ < 1$ and $Φ$ is bounded), otherwise the telescope's tail wouldn't vanish.

Exercise 3.2

From Exercise 3.1 conclude $Q^{' π} (s, a) = Q^{π} (s, a) - Φ (s)$ , and use it to argue $ar g max_{a} Q^{'} (s, a) = ar g max_{a} Q (s, a)$ .

Recall Solution 3.2

Taking expectations of the return starting from $(s, a)$ gives $Q^{' π} (s, a) = Q^{π} (s, a) - Φ (s)$ : the $- Φ (s_{0})$ constant carries through because $s_{0} = s$ is fixed. Now $Φ (s)$ does not depend on $a$ — it is a constant offset across all actions from the same state. Subtracting the same constant from every option never changes which option is largest: $ar g max_{a} (Q (s, a) - Φ (s)) = ar g max_{a} Q (s, a) .$ So the greedy (and hence optimal) policy is identical — this is policy invariance.

Exercise 3.3

Take non-potential shaping $F (s) = + 0.1$ for every step spent adjacent to a wall (independent of $s^{'}$ ). Show it can change the optimal policy by computing the accumulated $F$ over a 4-step wall-hugging loop with $γ = 1$ .

Recall Solution 3.3

Over 4 steps each earning $+ 0.1$ : total shaping $= 4 \times 0.1 = 0.4 > 0$ . Why this breaks the guarantee: $F$ is not of the form $γ Φ (s^{'}) - Φ (s)$ (it depends only on the current state's wall-adjacency, with no cancelling exit term). So the telescoping of Exercise 3.1 does not happen. A closed loop nets $+ 0.4$ , not $0$ . The agent can farm this reward indefinitely and will prefer hugging walls to solving the task — a form of reward hacking.

Level 4 — Synthesis

Exercise 4.1

You have a rough heuristic $h (s)$ estimating "how good" a state is. Design a PBRS scheme, and explain what the ideal choice of $Φ$ would be and why it makes learning almost trivial.

Recall Solution 4.1

Design: set $Φ (s) = h (s)$ and shape with $F (s, a, s^{'}) = γ h (s^{'}) - h (s)$ . By PBRS this cannot change the optimal policy no matter how bad $h$ is — worst case it just fails to help. Ideal choice: $Φ (s) = V^{*} (s)$ , the true optimal value. Then the shaped optimal values become $Q^{' *} (s, a) = Q^{*} (s, a) - V^{*} (s)$ . For the best action $a^{⋆}$ this is $Q^{*} (s, a^{⋆}) - V^{*} (s) = 0$ , and every worse action is negative. So good and bad actions are cleanly separated from step one — the agent barely needs to learn. See Value Functions and Bellman Equations for why $max_{a} Q^{*} (s, a) = V^{*} (s)$ . Reality: we don't know $V^{*}$ , but any $h$ pointing roughly the right way (e.g. negative distance-to-goal) already turns a flat, uninformative landscape into a downhill slope toward the goal.

Exercise 4.2

You are training a robot arm to push a puck to a target, but you have no distance heuristic and the reward is $+ 1$ only on success. PBRS needs a heuristic you lack. Propose two alternative strategies from the parent note, and say which failure mode each avoids.

Recall Solution 4.2

(1) Hindsight Experience Replay (HER): when the arm misses the target $g$ and instead moves the puck to $g^{'}$ , relabel the episode as if $g^{'}$ was the goal. A failure becomes a success ⇒ dense synthetic signal, and because we only relabel achieved outcomes there is no fake reward to hack. (2) Intrinsic curiosity / exploration bonus: add $F = β / N (s)$ (or a prediction-error bonus) so the agent is paid to visit novel states. This needs no domain knowledge and drives exploration until the real $+ 1$ is found. What each avoids: HER avoids the "no heuristic, no shaping" dead end; curiosity avoids getting stuck exploiting a flat, zero-reward region forever.

Level 5 — Mastery

Exercise 5.1

Design a full grid-world shaping. Goal at $(0, 0)$ , $γ = 0.95$ , $Φ (s) = - d (s)$ (Manhattan distance). Compute $F$ for a step from $d = 10$ to $d = 9$ . Then, for a two-step round trip $d = 10 \to d = 9 \to d = 10$ that returns to the same state $s_{A}$ , use the trajectory telescope to compute the total discounted shaping contribution and show it equals the constant $- Φ (s_{A})$ (plus the discounted end-of-trajectory potential) — not zero, because $γ < 1$ .

Recall Solution 5.1

Toward step ( $d = 10 \to 9$ ): $F = 0.95 \cdot (- 9) - (- 10) = - 8.55 + 10 = 1.45 .$ Round trip back to the same state. Let the state at $d = 10$ be $s_{A}$ with $Φ (s_{A}) = - 10$ , and the state at $d = 9$ be $s_{B}$ with $Φ (s_{B}) = - 9$ . The trajectory is $s_{0} = s_{A}, s_{1} = s_{B}, s_{2} = s_{A}$ (so here $s_{T} = s_{2} = s_{A}$ ).

$F_{0}$ ( $s_{A} \to s_{B}$ ): $γ Φ (s_{B}) - Φ (s_{A}) = 0.95 (- 9) - (- 10) = 1.45$ .
$F_{1}$ ( $s_{B} \to s_{A}$ ): $γ Φ (s_{A}) - Φ (s_{B}) = 0.95 (- 10) - (- 9) = - 0.5$ . Correct accounting — the discounted trajectory sum (the quantity the return actually uses): $\sum_{t = 0}^{1} γ^{t} F_{t} = γ^{0} (1.45) + γ^{1} (- 0.5) = 1.45 + 0.95 (- 0.5) = 1.45 - 0.475 = 0.975.$ Closure via the telescope. The finite-horizon identity (Exercise 3.1, stopped at $T = 2$ ) says this sum must equal $γ^{T} Φ (s_{T}) - Φ (s_{0})$ . Check: $γ^{2} Φ (s_{2}) - Φ (s_{0}) = 0.9 5^{2} \cdot (- 10) - (- 10) = - 9.025 + 10 = 0.975. ✔$ Punchline: with $γ < 1$ the round trip does not net zero — it nets $0.975$ . That non-zero value is not free hackable reward: it is exactly the fixed telescope quantity $γ^{T} Φ (s_{T}) - Φ (s_{0})$ , which depends only on the start and end states, never on the actions taken between them. Because it is a constant offset over actions, policy invariance still holds. The "loops = 0" mantra is only the $γ = 1$ special case (Exercise 2.3).

Exercise 5.2

Full-trajectory check. A 3-step episode visits $s_{0}, s_{1}, s_{2}, s_{3}$ with potentials $Φ = 4, 1, 2, 0$ and $γ = 0.9$ . Here $s_{3} = s_{T}$ is terminal, so by our convention $Φ (s_{3}) = 0$ . Compute the total discounted shaping contribution $\sum_{t = 0}^{2} γ^{t} F_{t}$ and confirm it equals $- Φ (s_{0})$ .

Recall Solution 5.2

The exact finite-horizon identity is $\sum_{t = 0}^{T - 1} γ^{t} F_{t} = γ^{T} Φ (s_{T}) - Φ (s_{0})$ . Compute each $F_{t} = γ Φ (s_{t + 1}) - Φ (s_{t})$ :

$F_{0} = 0.9 (1) - 4 = - 3.1$
$F_{1} = 0.9 (2) - 1 = 0.8$
$F_{2} = 0.9 (0) - 2 = - 2.0$ Discounted sum: $γ^{0} (- 3.1) + γ^{1} (0.8) + γ^{2} (- 2.0) = - 3.1 + 0.72 - 1.62 = - 4.0$ . Check RHS: $γ^{3} Φ (s_{3}) - Φ (s_{0}) = 0. 9^{3} \cdot 0 - 4 = 0 - 4 = - 4.0$ . ✔ Because $Φ (s_{3}) = 0$ by the terminal-potential convention, the leftover boundary term $γ^{T} Φ (s_{T})$ vanishes and we recover exactly $- Φ (s_{0})$ — the pure constant offset that makes the policy invariant.

Recall One-line summary to self-quiz

PBRS bonus $F = γ Φ (s^{'}) - Φ (s)$ ::: shifts every $Q (s, \cdot)$ by the same constant $- Φ (s)$ , so the best action never changes — while giving a per-step gradient that cures sparse reward.