Reward shaping and sparse rewards

WHAT is a sparse reward?

WHY it's hard: RL learns from the return $G_t=\sum_{k\ge0}\gamma^k r_{t+k}$. If almost all $r=0$, then $Q(s,a)\approx 0$ everywhere the agent has actually visited, so no action looks better than any other → no policy improvement until the goal is hit by luck. The probability of hitting it by luck decays exponentially with the number of steps required.

WHAT is reward shaping?

The danger: a naïve $F$ can create reward hacking — the agent finds a loop that milks $F$ without ever solving the task.

HOW to shape safely: Potential-Based Reward Shaping (PBRS)

Derivation from first principles — WHY the optimal policy is preserved

We derive it, not memorize it.

Step 1 — Write the shaped return. For a trajectory $s_0,s_1,s_2,\dots$ the shaped return is $G'_0=\sum_{t=0}^{\infty}\gamma^t\big(r_t + \gamma\Phi(s_{t+1})-\Phi(s_t)\big).$ Why this step? By definition the return is the discounted sum of the shaped reward $r'_t = r_t + F_t$.

Step 2 — Split the sum. $G'_0=\underbrace{\sum_{t}\gamma^t r_t}_{G_0}+\sum_{t=0}^{\infty}\gamma^t\big(\gamma\Phi(s_{t+1})-\Phi(s_t)\big).$ Why? Sum of a sum splits linearly.

Step 3 — Telescope the shaping part. Let $T=\sum_t\gamma^t(\gamma\Phi(s_{t+1})-\Phi(s_t))$. Write it out: $T=\big(\gamma\Phi(s_1)-\Phi(s_0)\big)+\gamma\big(\gamma\Phi(s_2)-\Phi(s_1)\big)+\gamma^2\big(\gamma\Phi(s_3)-\Phi(s_2)\big)+\cdots$ Group terms with $\Phi(s_1)$: coefficient $= \gamma - \gamma\cdot 1 = 0$. Same for $\Phi(s_2)$: $\gamma^2 - \gamma^2 = 0$. Everything cancels except $-\Phi(s_0)$. Why? Each $\Phi(s_{t})$ appears with $+\gamma\cdot\gamma^{t-1}=\gamma^{t}$ from one term and $-\gamma^{t}$ from the next — they annihilate. This is a telescoping series.

Step 4 — Collect. $G'_0 = G_0 - \Phi(s_0).$

Step 5 — Interpret. The shaped value differs from the true value by a constant that depends only on the start state, not on the actions: $V'^{\pi}(s)=V^{\pi}(s)-\Phi(s),\qquad Q'^{\pi}(s,a)=Q^{\pi}(s,a)-\Phi(s).$ Why this is the punchline: $\arg\max_a Q'(s,a)=\arg\max_a\big(Q(s,a)-\Phi(s)\big)=\arg\max_a Q(s,a)$ because $\Phi(s)$ is a constant offset over $a$. So the greedy/optimal policy is identical. ∎

Other tools for sparse rewards (the 80/20)

• Intrinsic motivation / curiosity: add $F = \eta\,\|\text{prediction error}\|$ or a count bonus $F=\beta/\sqrt{N(s)}$ so the agent is rewarded for visiting novel states → explores until it finds the real reward.
• Hindsight Experience Replay (HER): if the agent aimed for goal $g$ but reached $g'$, relabel the episode as if $g'$ was the goal. Now a "failure" becomes a "success" → dense synthetic learning signal, no reward hacking.
• Curriculum learning: start with goals close to the agent (dense success), gradually move them farther.

Worked examples

Common mistakes (Steel-man them)

Flashcards

Connections

• Markov Decision Processes — shaping modifies $R$ but must preserve $\pi^*$.
• Value Functions and Bellman Equations — $V'^\pi=V^\pi-\Phi$ derivation.
• Exploration vs Exploitation — curiosity bonuses as intrinsic reward.
• Hindsight Experience Replay — sparse-reward remedy without hacking.
• Curriculum Learning — easing sparsity by ordering goals.
• Reward Hacking and Specification Gaming — failure mode PBRS prevents.

Concept Map

Hinglish (regional understanding)