77 - Delayed Rewards, Reward Shaping and Reward Hacking: When the Agent Does Exactly What It Is Paid For

With the Bellman equation we have a powerful tool: given an MDP, we compute what it pays to do. But we took one enormous thing for granted: that the reward is the right one. In real problems the reward is written by a person, and writing it well is hard: the signal may arrive very late (you won the game after 200 moves: which move counted?), it may almost never arrive, and when we try to guide the agent with intermediate rewards we risk letting it discover a shortcut we did not want. This article has three parts, each with an experiment: how γ decides between a near prize and a far one; why finding a far prize is hard for an agent that explores at random; reward hacking, that is an agent that obtains a great deal of reward without doing what you wanted, and the theoretically grounded remedy, potential-based shaping.

The vocabulary, in a few lines

A delayed reward is a useful signal that arrives many steps after the action that caused it; a sparse reward is almost always zero and non-zero at a few moments, while a dense one gives a signal at almost every step. Credit assignment is working out which of the past actions caused the reward of now. Reward shaping adds intermediate rewards to guide the agent when the true one is too rare. Reward hacking (or specification gaming) is the exploitation of a loophole in the reward: the definition given by Krakovna and colleagues at DeepMind is a behaviour that satisfies the literal specification of an objective without achieving the intended outcome. Goodhart's law ("when a measure becomes a target it ceases to be a good measure") is its general principle in the form of a proverb. Finally a potential Φ(s) is a function that assigns a number to each state (for example "how far I have advanced") and serves to build a shaping that leaves the optimal policy unchanged.

The analogy: paying developers by lines of code

A company decides to reward developers by the lines of code written, because "more lines means more work". Within a month the code is full of useless lines, repeated comments and functions split into ten. The developers did not cheat: they did exactly what they were paid for. The measure (lines) was an imperfect substitute for the goal (software that works), and a strong enough optimisation always finds the distance between the two. An RL agent is a very strong and very literal optimiser: it does not guess intentions, it maximises the number you give it.

Part 1: delayed rewards and the weight of γ

Let us build the simplest possible case, with a computation that can be done by hand. A corridor of 13 cells numbered 0 to 12. The agent starts from cell 3. Entering cell 0 it collects a small prize (+1, 3 steps away); entering cell 12 it collects a big prize (+10, 9 steps away). Both cells end the episode. What will pay the agent?

If I take the small prize, I receive it at the third step: its discounted value is 1 · γ² (the reward of the first step is worth γ⁰, that of the third γ²). The big one I receive at the ninth step: 10 · γ⁸. The big one pays when 10γ⁸ > γ², that is γ⁶ > 0.1, that is γ > 0.1^(1/6) ≈ 0.6813. Below this threshold the agent is too short-sighted to wait. We verify with the value iteration of the Bellman article, adapted to the corridor. The listings of this article are run in sequence in the same file.

import numpy as np

class Corridor:
    """A line of cells 0..n-1. Actions: 0 = left, 1 = right. Same interface as GridWorld: P[s][a] = [(prob, next_state, reward, done)].
    `rewards` maps a cell to the reward received when ENTERING it; `terminals` ends the episode."""
    def __init__(self, n, rewards, terminals, step_reward=0.0):
        self.n_states, self.n_actions, self.terminals = n, 2, set(terminals)
        self.P = {}
        for s in range(n):
            self.P[s] = {}
            for a in range(2):
                if s in self.terminals:
                    self.P[s][a] = [(1.0, s, 0.0, True)]
                    continue
                s2 = min(max(s + (1 if a == 1 else -1), 0), n - 1)
                self.P[s][a] = [(1.0, s2, step_reward + rewards.get(s2, 0.0), s2 in self.terminals)]

def q_values(env, V, s, gamma):
    return [sum(p * (r + gamma * V[s2] * (not done)) for p, s2, r, done in env.P[s][a]) for a in range(env.n_actions)]

def value_iteration(env, gamma, tol=1e-12):
    V = np.zeros(env.n_states)
    while True:
        delta = 0.0
        for s in range(env.n_states):
            v = max(q_values(env, V, s, gamma))
            delta = max(delta, abs(v - V[s])); V[s] = v
        if delta < tol:
            return V

# Cells 0..12.  Start at cell 3: a SMALL prize (+1) 3 steps to the left, a BIG prize (+10) 9 steps to the right.
env = Corridor(13, rewards={0: 1.0, 12: 10.0}, terminals=(0, 12))
start = 3
print("distance to the small prize:", start - 0, " to the big prize:", 12 - start)
print("break-even: 1 * g^2 = 10 * g^8  ->  g =", round(0.1 ** (1 / 6), 4))
for gamma in (0.5, 0.65, 0.68, 0.69, 0.8, 0.99):
    V = value_iteration(env, gamma)
    q = q_values(env, V, start, gamma)
    print(f"gamma={gamma:4.2f}  value of the start {V[start]:7.4f}   best first move: {'RIGHT (big prize)' if q[1] > q[0] else 'LEFT (small prize)'}")

# Output (two consecutive runs, same output):
# distance to the small prize: 3  to the big prize: 9
# break-even: 1 * g^2 = 10 * g^8  ->  g = 0.6813
# gamma=0.50  value of the start  0.2500   best first move: LEFT (small prize)
# gamma=0.65  value of the start  0.4225   best first move: LEFT (small prize)
# gamma=0.68  value of the start  0.4624   best first move: LEFT (small prize)
# gamma=0.69  value of the start  0.5138   best first move: RIGHT (big prize)
# gamma=0.80  value of the start  1.6777   best first move: RIGHT (big prize)
# gamma=0.99  value of the start  9.2274   best first move: RIGHT (big prize)

The Corridor class has the same interface as GridWorld (table P[s][a] of probability-state-reward-end tuples); the rewards dictionary says which reward is collected on entering a cell. q_values computes the value of each action with the Bellman formula and value_iteration applies it until it no longer changes. Then, for each γ, we look at which first move has the highest q. The result confirms the hand computation: the choice goes from "left" (small prize) to "right" (big prize) between 0.68 and 0.69, with the threshold at 0.6813. The starting value with γ = 0.5 is 0.25 (1·0.5²); with γ = 0.99 it is 9.23, close to 10·0.99⁸.

The lesson is that γ is not just a numerical parameter: it decides the agent's preferences. An agent with γ = 0.5 will always choose the small, near prize, even if the big one is worth ten times as much. If your problem requires patience (investing today to earn in a thousand steps) you need a high γ, with the cost already seen: slower computation and less stable learning.

Part 2: a far prize is hard to find

Value iteration gave the exact answer because it knew the map. An agent that learns from experience (as in Q-Learning) must first discover where the prize is, and if the reward is zero everywhere except at one distant point it receives no signal until it stumbles on it by chance. We measure how likely that is with a completely random agent (step left or right with probability ½, starting from the left edge) in a corridor with the prize at the opposite end.

# Delayed reward and EXPLORATION: how often does a purely random agent stumble on a far-away prize?
def random_agent_success(n_cells, horizon=300, episodes=3000, seed=0):
    rng = np.random.default_rng(seed)
    hits = 0
    for _ in range(episodes):
        pos = 0                                    # start at the left end, the single reward sits at the right end
        for _ in range(horizon):
            pos = max(pos + (1 if rng.random() < 0.5 else -1), 0)
            if pos == n_cells - 1:
                hits += 1
                break
    return hits / episodes

for n in (5, 10, 20, 40, 80):
    print(f"corridor of {n:2d} cells: random agent reaches the prize within 300 steps in {100 * random_agent_success(n):5.1f}% of episodes")

# Output (two consecutive runs, same output):
# corridor of  5 cells: random agent reaches the prize within 300 steps in 100.0% of episodes
# corridor of 10 cells: random agent reaches the prize within 300 steps in  97.8% of episodes
# corridor of 20 cells: random agent reaches the prize within 300 steps in  52.5% of episodes
# corridor of 40 cells: random agent reaches the prize within 300 steps in   4.7% of episodes
# corridor of 80 cells: random agent reaches the prize within 300 steps in   0.0% of episodes

The function random_agent_success simulates 3000 episodes of 300 steps: at each step the agent moves one cell at random (the left edge pushes it back, max(pos + …, 0)) and we record whether it touches the prize cell. The fixed seed default_rng(0) makes the output reproducible. Up to 10 cells the random agent almost always makes it, at 20 cells in about half the cases, at 40 cells in only 4.7% and at 80 cells never in 3000 attempts. It is the physics of the random walk: the typical distance covered in n steps grows like the square root of n, not like n; to cover 80 cells you need of the order of 6400 steps, well beyond the horizon of 300.

If the only signal is at the end of a long path, the agent never sees a reward other than zero and has nothing to learn from: this is the problem of exploration with sparse reward. The main roads are intermediate rewards (reward shaping), guided exploration (curiosity, bonuses for new states), expert demonstrations and curricula (starting from problems close to the goal). Sutton and Barto, in section 17.4 of their text, discuss precisely the temptation to solve the sparse-reward problem by rewarding subgoals, with the risk that the agent optimises the subgoals and not the goal. And here lies the trap: reward shaping done by eye produces reward hacking.

Part 3: reward hacking, measured

We want to guide the agent towards the goal in a corridor of 8 cells (goal in cell 7, +1, terminal; cost −0.01 per step; start from cell 3). We try three ways of adding rewards "to help" and compare them with the honest task.

# Reward hacking: we add rewards to "encourage progress", and the agent finds a loophole.
def describe(env, gamma, start=3, max_steps=60):
    V = value_iteration(env, gamma)
    s, total, path = start, 0.0, [start]
    for _ in range(max_steps):
        a = int(np.argmax(q_values(env, V, s, gamma)))
        p, s2, r, done = env.P[s][a][0]
        total += r; s = s2; path.append(s)
        if done:
            return V, path, total, True
    return V, path, total, False

gamma = 0.95
# 0) The honest task: +1 at the goal (cell 7, terminal), a small cost per step.
honest = Corridor(8, rewards={7: 1.0}, terminals=(7,), step_reward=-0.01)
V0, path, total, reached = describe(honest, gamma)
print(f"HONEST          reached goal: {reached} | path {path} | reward {total:.2f}")

# 1) A "bonus tile": +0.3 EVERY time the agent enters cell 2 (the designer wanted to guide it).
bonus = Corridor(8, rewards={2: 0.3, 7: 1.0}, terminals=(7,), step_reward=-0.01)
V1, path, total, reached = describe(bonus, gamma)
print(f"BONUS TILE      reached goal: {reached} | path {path[:12]}... | reward in 60 steps {total:.2f}")

# 2) "Reward every step to the right": +0.3 whenever the agent moves right
progress = Corridor(8, rewards={7: 1.0}, terminals=(7,), step_reward=-0.01)
for s in range(7):
    p, s2, r, d = progress.P[s][1][0]
    progress.P[s][1] = [(p, s2, r + 0.3, d)]
V2, path, total, reached = describe(progress, gamma)
print(f"RIGHT-MOVE BONUS reached goal: {reached} | path {path[:12]}... | reward in 60 steps {total:.2f}")

# 3) The same intention written as POTENTIAL-BASED shaping (Ng, Harada & Russell, 1999):  F = gamma*Phi(s') - Phi(s),  Phi(s) = 0.3*s
phi = lambda s: 0.3 * s
shaped = Corridor(8, rewards={7: 1.0}, terminals=(7,), step_reward=-0.01)
for s in range(7):
    for a in range(2):
        p, s2, r, d = shaped.P[s][a][0]
        shaped.P[s][a] = [(p, s2, r + gamma * phi(s2) * (not d) - phi(s), d)]
V3, path, total, reached = describe(shaped, gamma)
print(f"POTENTIAL-BASED reached goal: {reached} | path {path}")
print(f"value at the start: honest {V0[3]:.3f}  potential-based {V3[3]:.3f}  difference {V3[3] - V0[3]:.3f} = -Phi(start) = {-phi(3):.3f}")

# Output (two consecutive runs, same output):
# HONEST          reached goal: True | path [3, 4, 5, 6, 7] | reward 0.96
# BONUS TILE      reached goal: False | path [3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2]... | reward in 60 steps 8.40
# RIGHT-MOVE BONUS reached goal: False | path [3, 4, 5, 6, 5, 6, 5, 6, 5, 6, 5, 6]... | reward in 60 steps 8.70
# POTENTIAL-BASED reached goal: True | path [3, 4, 5, 6, 7]
# value at the start: honest 0.820  potential-based -0.080  difference -0.900 = -Phi(start) = -0.900

describe computes the optimal policy for the given reward (value iteration) and then executes it for at most 60 steps from the starting state, returning the path, the total reward collected and whether it reached the goal. In the honest task there is only +1 at the goal and the agent goes straight: 3 → 4 → 5 → 6 → 7, total reward 0.96 (+1 minus four steps of 0.01). No surprise.

With the bonus tile the designer adds +0.3 every time the agent enters cell 2 (he wanted to "attract" it towards an intermediate point). Result: the agent never reaches the goal. It runs 3 → 2 → 3 → 2 → … forever, collecting 0.3 every two steps: 8.40 in 60 steps, against 0.96 for the honest path. With the discounted return the loop is worth about 0.2805 / (1 − γ²) ≈ 2.88 (the outward step gives +0.29, the return step −0.01 discounted by γ) against about 0.82 for the goal: for the agent the loop is the optimal choice. It is right: it is the reward that is wrong.

The reward at every step to the right is subtler: +0.3 every time you move right, "to encourage progress". The agent advances 3 → 4 → 5 → 6 and then oscillates 5 → 6 → 5 → 6, collecting +0.3 at every step to the right. It never enters the goal, because the final step (+1 and +0.3, then the episode ends) is worth less than the perpetual flow of small prizes: 8.70 in 60 steps. In the fourth case, potential-based shaping, the same intention ("reward progress to the right") written in a particular way repairs the problem: the agent goes straight to the goal. Let us see why.

Potential-based shaping, with the proof

Ng, Harada and Russell (1999) proved that there is a way of adding intermediate rewards without changing the optimal policy, and that this form is also necessary: any other form can change it. You choose a potential Φ(s) (here 0.3·s: further right, more "advanced") and add to every transition s → s′ the term

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

Why does it work? Let us look at what happens to the discounted sum of the F terms along a trajectory s_0, s_1, s_2, …, s_T:

Σ_{t=0..T−1} γ^t · F(s_t, s_{t+1}) = Σ γ^t · ( γ Φ(s_{t+1}) − Φ(s_t) )
                                   = Σ ( γ^{t+1} Φ(s_{t+1}) − γ^t Φ(s_t) )
                                   = γ^T Φ(s_T) − Φ(s_0)

The sum is "telescoping": all the intermediate terms cancel. If we set Φ = 0 on the terminal states (as we do), γ^T Φ(s_T) = 0 and the total bonus depends only on the starting state: −Φ(s_0). A value that does not depend on how you walked cannot be exploited in any loop: every return is altered by the same constant, so the ordering of the policies does not change. Formally the optimal value becomes v′*(s) = v*(s) − Φ(s). The last line of the output confirms it: the starting value goes from 0.820 to −0.080, a difference of −0.900 = −Φ(3) = −0.3·3, and the path stays 3 → 4 → 5 → 6 → 7.

You also see why the two "shortcuts" failed: a prize for every step to the right is not of the form γΦ(s′) − Φ(s), so it does not telescope, and a right-left-right loop collects the prize several times with nothing to compensate it. In potential-based form going right gives a positive term and going back left a negative one larger in absolute value: a loop costs about 0.3(γ − 1) < 0 in shaping terms. Cyclic profit is impossible by construction.

How to design a reward (and how to notice it is wrong)

1. Write the true goal first, then the reward. If you cannot say in words what "success" means, you cannot write a number that measures it.
2. Prefer few rewards tied to the outcome (won/lost, time taken) to many tied to the means (steps walked, objects touched).
3. If you must add intermediate rewards, use potential-based shaping. It is the family with the theoretical guarantee of not changing the optimal policy.
4. Measure the behaviour, not just the reward. A rising reward is compatible with an agent that is cheating (8.4 against 0.96): evaluate with a separate metric, here "did it reach the goal?".
5. Look at the trajectories. Loops, oscillations and agents stuck in a corner are typical signs of hacking.
6. Remove the fuel of the loops. A time limit, a cost per step or non-repeatable bonuses (collected once per episode) remove what feeds the loop.

The order is not a ranking, but there is a thread: points 1 and 2 avoid creating the loophole, 3 gives you a safe way of helping learning, points 4 and 5 discover it when it is there anyway, 6 closes it. If you have to pick just one, pick the fourth: without a metric independent of the reward you cannot even notice you have a problem.

Public examples of this phenomenon are not lacking. A much-cited one is the agent of the boat game Coast Runners, described by Amodei and Clark in 2016 and taken up in DeepMind's post on specification gaming: the agent received a shaping reward for the green blocks along the course, and learned to circle hitting the same blocks over and over instead of finishing the race. DeepMind's post notes precisely that shaping changes the optimal policy if it is not potential-based. I did not reproduce that case, but the mechanism is the same as our bonus tile.

Trade-offs and pitfalls

A dense reward gives fast learning but more risk of hacking, a sparse one is faithful to the goal but often impossible to learn by exploration. A high γ gives patience but harder learning, a low γ is fast but short-sighted (threshold 0.68 in our example). Hand-made shaping is flexible and dangerous, potential-based shaping is safe but requires knowing how to write a sensible potential; theory guarantees that the potential does not change the optimal policy, and its quality affects only the speed of learning.

The recurring pitfalls follow from here. Rewarding what can be repeated is an invitation to the loop. Evaluating only with the training reward hides hacking, because the hacker agent has the highest reward. Thinking that hacking is a bug of the algorithm is a mistake: here value iteration is exact and does its job, the defect is in the reward. With γ too low a prize 9 steps away is worth 10·0.5⁸ ≈ 0.04, practically invisible. A potential that does not vanish at the terminals breaks the proof, because the term γ^T Φ(s_T) remains, depends on the ending and can change the choice. And with sparse reward and small ε a "null" learning result does not mean the problem is impossible, but that exploration did not find the prize.

A worked example by hand: "every step" rewards and shaping, transition by transition

We take up the corridor with γ = 0.95 and the potential Φ(s) = 0.3·s, that is Φ(3) = 0.9, Φ(4) = 1.2. The cost of a step is −0.01.

Reward "at every step to the right" (not potential-based). The step 3 → 4 is worth −0.01 + 0.3 = +0.29; the step back 4 → 3 is worth −0.01. A there-and-back loop collects 0.29 − 0.01 = +0.28 without discount: positive and repeatable forever. With the discount (0.29 − 0.95·0.01 = 0.2805 per two-step loop) the value of the infinite loop is 0.2805/(1 − 0.95²) ≈ 2.88, more than the goal is worth (0.82). The agent does the loop.

The same intention, potential-based. The shaping term for 3 → 4 is F = γΦ(4) − Φ(3) = 0.95·1.2 − 0.9 = +0.24, so the reward is −0.01 + 0.24 = +0.23. For the step back, F = γΦ(3) − Φ(4) = 0.95·0.9 − 1.2 = −0.345, so −0.01 − 0.345 = −0.355. The loop is worth 0.23 − 0.355 = −0.125 without discount (and 0.23 + 0.95·(−0.355) = −0.107 with the discount): negative. Every step forward is rewarded, every return back is punished more: the loop never pays, however many laps. In the first case the reward depends only on the move and does not remember where you have been; in the second it depends on the potential difference between where you are and where you go, and that is why it is "zero-sum" over loops.

A hand check also for the exploration part. A symmetric random walk with a reflecting wall at 0 takes on average n² steps to reach distance n (a classical result, not derived here). For n = 20: 400 steps; for 40: 1600; for 80: 6400. With a limit of 300 steps one expects to reach 20 cells about half of the time (measured: 52.5%) and almost never to reach 80. The typical distance reached in 300 steps is of the order of √(2·300/π) ≈ 14 cells for the mean absolute displacement of a free walk (√300 ≈ 17 as the scale of the standard deviation), not 80.

Exercises with solutions

1. Prize +2 at 4 steps, prize +8 at 10 steps. At which γ do they break even?
   Solution: 2γ³ = 8γ⁹ → γ⁶ = 0.25 → γ = 0.25^(1/6) ≈ 0.794 (recomputed: 0.7937).
2. Why is the sum of potential-based shaping terms "telescoping"?
   Solution: because each Φ(s_t) appears once with a positive sign and once with a negative sign, multiplied by the same power of γ, and cancels with the adjacent term.
3. An agent receives +1 every time it collects a coin that reappears after 5 steps. What is the risk?
   Solution: that it learns to stay near the coin forever instead of completing the true goal (reward hacking through a repeatable bonus).
4. Why does a random agent not find a prize 80 cells away in 300 steps?
   Solution: because the typical distance of a random walk grows like the square root of the number of steps: you need of the order of 80² = 6400 steps, not 300.

The first exercise repeats the γ threshold computation with different numbers, the second is the proof in one sentence. The last two are the cases to carry into practice: recognising a repeatable bonus before training and estimating in advance whether a far prize is reachable at random. If you answer without rereading, you can move on to Q-Learning.

Frequently asked questions

How do I know if my reward is "leaky"?

By looking at the trajectories of the trained agent: loops, oscillations and repetition of the same gesture are the signs. Compare the total reward with that of an "honest" hand-written policy: if the agent earns many times as much without reaching the goal (here 8.40 against 0.96), you have hacking.

Does potential-based shaping really help learning?

It can help (it gives a signal at every step), but theory only guarantees that it does not change the optimal policy; the speed of learning depends on how informative the potential is. A poor potential does not change the optimum, but it does not help.

How do I choose the potential?

Often as an estimate of the value of the state (distance from the goal, altitude reached). If you knew v* exactly and set Φ = v*, the transformed optimal value v* − Φ would be zero everywhere: it is worth getting close to it.

Can I fix hacking by adding a penalty?

Sometimes (a cost per step discourages loops), but it is a game of cat and mouse: every penalty is a new reward that the agent can exploit in unforeseen ways. Better to make the reward faithful to the goal.

And if I cannot add rewards?

You can use demonstrations (imitation), a curriculum of progressively harder problems or an intrinsic reward of curiosity. Each has its own costs and risks: none is free.

What you can do now

You can compute when a far prize beats a near one (threshold 0.6813 in the corridor, verified with value iteration) and you can predict whether a random agent has a reasonable chance of finding it (100% at 5 cells, 52.5% at 20, 4.7% at 40, 0% at 80 over 3000 episodes). You can recognise reward hacking from the trajectories and from the distance between reward and goal (8.40 by circling against 0.96 by reaching the goal), and you can apply potential-based shaping F = γΦ(s′) − Φ(s), which shifts the value by a constant (−0.900 in our case) without touching the optimal policy. In the next article we stop knowing the model: the agent learns from experience with Q-Learning.