Foundations — Reward shaping and sparse rewards

This page assumes nothing. Every letter, arrow, and Greek symbol the parent note used is rebuilt here from the ground up, in the order you need them. If a symbol appears in the parent, it is defined below before we lean on it. To keep the narrative anchored, each figure is labelled (Figure 1, Figure 2, …) and referred to by that label in the text.

The world we are in: states, actions, and steps

Before any reward, we need the stage on which everything happens. This comes from Markov Decision Processes (MDPs).

Figure 1 below draws these three symbols at once — a state $s$, an action $a$ from the menu $\mathcal{A}$, and the resulting next state $s^{\prime }$ — plus the goal square we will reward.

The reward $R$ and its per-step name $r_t$ — the only feedback the agent gets

Adding up rewards over time: the sum symbol, the discount $\gamma$, and the return $G_t$

One reward at one step is not enough — the agent cares about the whole future. To talk about "the whole future" we first need a compact way to say "add up a long list."

Why ${\gamma }^k$ specifically? Because we apply the same shrink $\gamma$ once per step, so after $k$ steps the reward is multiplied by $\gamma \cdot \gamma \cdots \gamma ={\gamma }^k$. Repeated multiplication is exactly what powers mean.

Figure 2 shows the weights ${\gamma }^k$ for $\gamma =0.8$: each future reward is multiplied by a smaller number, so the tail of an infinite sum fades toward zero.

Policies $\pi$, the expectation $\mathbb{E}[\cdot ]$, and value: $V$ and $Q$

To decide which policy is best, we score situations. These come from Value Functions and Bellman Equations.

The number line $\mathbb{R}$

The shaping toolkit: $\Phi$, $F$, and $R^{\prime }$

Now the pieces unique to reward shaping.

Figure 3 draws $\Phi$ as a hill peaking at the goal; moving from $s$ to $s^{\prime }$ climbs a little, and the red arrow marks the potential difference that becomes the shaping bonus.

The algebraic WHY: telescoping to policy invariance

Here is the cancellation itself, so you see why shaping leaves the best policy alone — not just that it does.

Step 1 — Sum the shaping term along a trajectory. For a path $s_0,s_1,s_2,\dots$, the total discounted shaping is $T={\sum }_{t\ge 0}{\gamma }^t(\gamma \Phi (s_{t+1})-\Phi (s_t)).$ Why: the shaped return is $G_t^{\prime }=G_t+T$, so all the shaping's effect lives in this one sum.

Step 2 — Write out the first few terms. $T=(\gamma \Phi (s_1)-\Phi (s_0))+\gamma (\gamma \Phi (s_2)-\Phi (s_1))+{\gamma }^2(\gamma \Phi (s_3)-\Phi (s_2))+\cdots$ Why: seeing the pattern by hand is what reveals the cancellation.

Step 3 — Collect each $\Phi (s_t)$. Look at $\Phi (s_1)$: it appears as $+\gamma \Phi (s_1)$ (from the first bracket) and as $-\gamma \Phi (s_1)$ (from the second). Sum: $0$. Same for $\Phi (s_2)$: $+{\gamma }^2\Phi (s_2)-{\gamma }^2\Phi (s_2)=0$. Every interior potential is annihilated; only $-\Phi (s_0)$ (which never gets a partner) survives. Why: this is the telescope folding shut.

Step 4 — Collect the result. $T=-\Phi (s_0),\text{so}{G}_0^{\prime }=G_0-\Phi (s_0).$

Step 5 — Read off policy invariance. Averaging gives $Q^{\prime \pi }(s,a)=Q^{\pi }(s,a)-\Phi (s)$. Since $\Phi (s)$ is the same constant for every action $a$ in state $s$, $\arg {\max }_a{Q}^{\prime }(s,a)=\arg {\max }_a(Q(s,a)-\Phi (s))=\arg {\max }_{a}Q(s,a).$ Subtracting the same number from every bar in a bar chart does not change which bar is tallest — so the best action, and hence the optimal policy, is unchanged. ∎

(The parent note walks the same derivation in full; this sketch shows the load-bearing cancellation.)

How it all fits together

Read it top-down: the MDP gives you states (in $\mathcal{S}$), actions (in $\mathcal{A}$) and their random transitions; terminal states make the reward sum finite; rewards and discount build the return; expectation over that randomness defines value and the policy; potentials (real-valued) define the shaping term; and telescoping is what proves the shaped signal doesn't move the best policy.

Equipment checklist

Cover the right side and test yourself.

Ready? With these symbols in hand, every line of the parent note — including the full telescoping proof and the Hindsight Experience Replay, Curriculum Learning, Exploration vs Exploitation and Reward Hacking and Specification Gaming extensions — reads without a single unexplained symbol.