M5-T3 — Sparse Versus Dense Rewards

Learning objectives

After this lesson, you should be able to:

• Explain why a sparse reward defeats undirected exploration, and why credit assignment is slow even after the first success.
• Describe what a dense reward adds (a learning signal) and what it costs (bias and loopholes).
• Compare sparse, potential-shaped and dense rewards by episodes to first success and by final performance under the original reward.
• Describe curriculum learning and hindsight relabelling as ways to make a sparse reward learnable without changing it.

The intuition

Playing “hot and cold” with a blindfolded friend is a dense reward: every step, “warmer” or “colder”. Playing without hints, and being told only “you found it” when you stand on the object, is a sparse reward. In a small room the second game ends soon by luck. In a large room it can take longer than anyone has patience for. Two separate difficulties hide in it. Finding the reward at all by chance, which is an exploration problem (lesson M4-T7). And, once found, crediting it: a reward at step 200 has to be traced back through the 199 choices before it. Q-learning (lesson M4-T6) does this by passing the value one step back each time it visits a cell, so the credit trickles backward along the route.

Dense rewards attack both difficulties by telling the learner how it is doing at every step. The price is that “how it is doing” is a judgement by the designer. If the judgement is a potential difference (lesson M5-T2) the optimum is untouched. If it is a cost that is almost, but not exactly, the task, the optimum shifts a little. If it is a bonus for something Scout can collect without finishing, the optimum can move away from the task altogether (lesson M5-T4). The figure compares seven designs on one hall: only the designs that keep the goal as the main payoff and point toward it in a way the walls allow end with a good policy.

The mathematics

Why sparse rewards are hard

Take a task in which the only non-zero reward is G at the goal. A learner with a zero-initialised table and ε-greedy exploration (lesson M4-T7) starts with all values 0, so its greedy choices are ties, broken the same way every time, and all the movement comes from the ε fraction of random steps. The chance that a random walk of limited length reaches a goal that is n moves away falls quickly with n and with walls in the way. Until the first success there is no learning signal at all.

After the first success the signal exists but is thin. The value of a cell near the goal becomes positive after one visit; the cell before it needs a second pass, and so on: each episode that reaches the goal can push the signal back along its path one step per update (a Monte Carlo return, lesson M4-T5, would credit the whole path but only after the episode ends). This is the credit assignment problem: the delay between a choice and its reward dilutes the signal, and with discounting γ^k the value of a cell k moves away is only γ^k G.

What a dense reward adds

A dense reward is any design that gives non-zero information at most steps. It shortens the delay, so the signal reaches the table at once. It also changes the problem. Four kinds are worth separating:

Making a sparse reward learnable without changing it

Two ideas keep the task reward exactly as written and change how experience is gathered or reused.

• Curriculum. Start the learner where the reward is easy to find (close to the goal, or with a larger tolerance) and move the start or the difficulty outward as it succeeds. Bengio and colleagues (2009) is the standard reference for the idea in supervised learning. In reinforcement learning a curriculum needs a schedule: moving too fast loses the benefit (the example below), and a start near the goal teaches only the last part of the route.
• Hindsight relabelling. If the task is described by a goal that can vary (go to position g), then an episode that failed to reach g still reached some position g′. Relabel it as an episode whose goal was g′ and it becomes a success, so a sparse binary reward gives learning signal even when the original goal was never reached. Andrychowicz and colleagues introduced this as Hindsight Experience Replay (NeurIPS 2017), combined with an off-policy learner and a replay buffer (lesson M6). It needs a goal-conditioned task; in a single fixed-goal task like the hall of this lesson there is nothing to relabel.

Demonstrations (Module 3) and intrinsic or count-based exploration bonuses (lesson M4-T7) are further options. Each trades some of the sparse reward’s purity for learnability, and each deserves the same audit as a shaping term.

A worked example

All numbers come from the hall of lesson M5-T2 (7 × 11 cells, a wall with one gap, slip 0.1, goal +10, no step cost, γ = 0.99, optimal value of the start 8.828, route of 12 moves), run with RLCore and SLAMCore.rng seeds 1 to 20. Q-learning: α = 0.2, ε = 0.1, 500 episodes of up to 200 steps. “Final value” is the exact value of the final greedy policy under the original reward; “good” means at least 90 % of 8.828.

1. The sparse reward. 0 of 20 seeds reach the goal even once in 500 episodes, so all 20 end with value 0. Two obvious fixes do not rescue it: with 2,000 episodes, 0 of 20 still reach the goal; with ε = 0.3, 1 of 20 does (first at episode 155) and none ends with a good policy. This is the same behaviour as the sparse ward of lesson M4-T7, made worse by a bigger room and a wall.

2. A potential. With φ = −(walking distance to the goal), 20 of 20 seeds reach the goal, the median first success is in episode 2 (mean 3.4), the mean final value is 8.71 and all 20 are good. The optimal policy is the one of the sparse problem, as lesson M5-T2 proves (and as value iteration confirmed: no cell differs). With φ = −(straight-line distance) the optimum is also identical, but 5 of 20 seeds reach the goal (median first success episode 16), the mean final value is 0.00 and none is good.

3. A dense cost. Pay −w × (straight-line distance to the goal) at every step, plus the +10. For w = 0.05 and 0.2 alike, 20 of 20 seeds reach the goal (median first success episode 1, mean 1.1) with mean final value 8.81 and all good. Its exact optimum, from value iteration, reaches the goal in 12 moves with a true value of 8.818 instead of 8.828: a different but nearly equal route, a bias of 0.01. Even though this cost uses the same bad straight-line distance that trapped the potential of example 2, it works here. A cost is not a hint toward the wall: every step costs, the cost is lowest next to the goal, and the only way to stop paying is to end the episode. I did not isolate the reason, but a likely contributor is that every reward is now negative, so a zero-initialised table is optimistic and that by itself drives exploration (lesson M4-T7, and lesson M5-T2, example 6). Do not read this as “a straight-line cost is better than a straight-line potential” in general.

4. A dense bonus. Pay w × (1 − straight-line distance / largest distance) at every non-final step. Value iteration shows the threshold: for w = 0.02, 0.05 and 0.1 the optimal policy still walks to the goal (true values 8.823, 8.818, 8.818). At w = 0.3 it does not: the optimal policy hovers beside the goal, stepping back and forth between two cells next to it, and never enters it. Its value in the dense reward is 24.331, nearly three times the honest optimum of 8.828, and its value in the task reward is 0.000. A designer who looked only at the training return would see 24 and be delighted. This is the pattern lesson M5-T4 studies. The learning result is poor even for small w: 2 of 20 seeds ever reach the goal (first success at episode 417 in both), and the final value is 0.00 for all seeds at every w tried (0.02, 0.05, 0.1, 0.3). A bonus for being near does not lead through a wall.

5. A bonus for each move closer (+0.5 whenever the walking distance falls). It is not a potential. 4 of 20 seeds reach the goal (median episode 378) and none ends with a value above 0.

6. A curriculum. One schedule, tried once: 100 episodes with the start 3 moves from the goal, 100 with the start 7 moves away, 300 with the original start, the table carried over. The goal is found from the 3-move start in 20 of 20 seeds, from the 7-move start in 4 of 20 and from the original start in 0 of 20, and no seed ends with a good policy (0 of 20, mean final value 0.00). A curriculum needs a better schedule than this one (more episodes per stage, or promotion only on success); the experiment shows that it is not automatic.

What the simulation simplifies. One small hall, tabular Q-learning, fixed hyperparameters and a particular zero initialisation. Counts like 5 of 20 and 20 of 20 would move with α, ε, the number of episodes and the initial table (example 3 is the clearest case). The ordering of the designs is the lesson; the size of the gaps is specific to this setup. HER is described but not run, because it needs a goal-conditioned learner.

Engineering implications and limitations

A decision procedure

1. Start with the honest, sparse reward and measure two numbers: the share of episodes (or seeds) that reach the goal, and the time to the first success. If the share is healthy, stop here.
2. If it is near zero, ask first whether the task can be made easier without changing the reward: start closer to the goal, give a larger goal region, add demonstrations (Module 3), or use directed exploration (lesson M4-T7).
3. If you need a dense signal, use a potential built from information the robot can really use: walking distance from a planner, not straight-line distance when walls or doors matter (lab M5-L1).
4. If you use anything else (a cost, a bonus), solve a small instance exactly first and compare the optimal policy under the dense reward with the one under the task reward. Differences are the bias you are about to accept.
5. Always evaluate the learned policy with the task reward: success rate, time to success, collisions (lesson M1-T5). Keep the dense return as a training diagnostic, never as the score.

Watch both returns

Log the sparse task reward and the total reward the learner sees, separately. If the learner’s total rises and the task success does not, the dense term is being collected for its own sake (lab M5-L2 practises spotting this).

Turn dense terms off late

A common practice is to anneal a dense term to zero over training so the final objective is the task alone. This works when the learner has already found the task reward by then; it fails if the policy depends on the hint. Check by evaluating with the hint removed.

Scale and discount

The threshold at which a bonus beats finishing depends on γ and on how long the bonus can be collected, so a dense reward that is harmless at γ = 0.95 can be exploited at γ = 0.99 (lesson M4-T2). Re-check the optimum when you change either.

Several terms

Once there are several reward terms (time, safety, comfort), their relative weights become the design problem; lesson M5-T5 and lab M5-L3 treat that.

Common misconceptions

Engineering takeaways

1. A sparse reward is the faithful statement of the task and the least exploitable, but a learner that never reaches the goal learns nothing: 0 of 20 seeds in 500 episodes, and 0 of 20 in 2,000, on the hall.
2. Credit assignment is the second difficulty: after the first success the signal moves back one step per update and is discounted by γ per step.
3. Dense rewards are only as good as their form. A potential (walking distance) gave 20 of 20 good policies with the same optimum; a bonus for closeness left 18 of 20 seeds without the goal and, at a high enough weight, has an optimum that never finishes.
4. Examine the optimum of a dense reward on a small instance by value iteration and evaluate every learned policy with the task reward.
5. Curriculum and hindsight relabelling leave the reward unchanged and change what experience is gathered or reused; both need design (a schedule, a goal-conditioned task).

References and further reading

Bengio et al. introduce curriculum learning; Andrychowicz et al. introduce hindsight relabelling; the rest is background for shaping.

• M. Andrychowicz, F. Wolski, A. Ray, J. Schneider, R. Fong, P. Welinder, B. McGrew, J. Tobin, P. Abbeel and W. Zaremba, “Hindsight Experience Replay”, Advances in Neural Information Processing Systems 30 (NeurIPS), 2017.
• Y. Bengio, J. Louradour, R. Collobert and J. Weston, “Curriculum learning”, Proceedings of the 26th International Conference on Machine Learning (ICML), 2009.
• 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.
• R. S. Sutton and A. G. Barto, Reinforcement Learning: An Introduction, 2nd edition, MIT Press, 2018 (credit assignment and exploration in chapters 6 and 8).

Knowledge check

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

What’s next

Next: a dense term that the robot can collect without doing the task is a reward hack. Lesson M5-T4 follows one through the docking station, shows why more training makes it worse, and says how to find it.

Related content

Nothing below is required to finish this lesson.

• Before
  M5-T2: Reward Shaping and Potential Functions

  Add a shaping term of the form gamma times phi of the next state minus phi of the state, and show it keeps the optimal policy.

• 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.