Vol. XXVI · Training Agents Plate 4 of 10credit assignment, outcome reward, process reward, sparse reward, long episodes, REINFORCELE

Which Step Mattered.

One score at the end, many decisions before it. Which ones earned it?

An outcome reward says how the episode ended, not which actions caused it. The policy gradient gives every action in a successful episode the same push — the call that found the bug and the twenty that read irrelevant files — and every action in a failed one the same pull. Averaged over many episodes the right actions do come out ahead, because they appear more often in successes, but the signal for each one is diluted by all the others, more so the longer the episode. This is the credit assignment problem, and it is the reason long-horizon RL is slow.

Two remedies trade off. A process reward scores intermediate steps — tests passed so far, a sub-goal reached, a checker’s verdict on a step — so credit lands near the action that earned it, but only where steps can be checked, and a step can look right without being so. A learned value function estimates how promising each state is (as in PPO), but for language agents it is hard to train well. The workshop uses the chain task of plate XIX.8: k steps, each choosing among 4 actions with one right; outcome reward 1 only if all are right, process reward 1/k per right step.

Below: the share of fully correct episodes during training for outcome and process rewards, at the chosen chain length.

What you will learn
Workshop
A tabular softmax policy per step over 4 actions, one right; REINFORCE with a running-mean baseline, learning rate 0.5, 3 000 episodes. Fully correct: every step right. Curves are means over the episodes in windows of 100.

Credit diluted over steps

With four steps, outcome reward trains the chain to 99% fully correct; with ten, a random policy is fully right once in a million episodes, the outcome reward almost never arrives, and after 3 000 episodes the chain is fully correct 0% of the time. Process reward on the same ten steps reaches 99%, because each right step is rewarded whether or not the others were. The longer the episode, the more the end-of-episode signal is diluted — and agent episodes run to hundreds of steps.

Agent training therefore leans on starting points that already succeed sometimes (SFT, plate XXVI.2), on rewards that check intermediate progress where they can — tests passed, files correctly created — and on breaking long tasks into checked sub-tasks. Process rewards carry their own risk: a step can satisfy the checker without serving the goal, and a model trained on them learns to produce steps that look right (plate XXVII.6). Outcome rewards are harder to learn from but harder to fool.

In the tool world, an outcome reward checks only the final answer, while a process reward could check each calculator call against the right operands — exactly the steps the model gets wrong.

Terms

Credit assignment
Determining which actions caused a reward.
Outcome reward
A score only for the episode’s end.
Process reward
Scores for intermediate steps.
Value function
An estimate of how good a state is, used to assign credit earlier.
One reward at the end spreads credit over every action; longer episodes learn slower, and checked intermediate rewards help where steps can be checked honestly.

Sources

  1. Sutton and Barto, Reinforcement Learning: An Introduction, 2nd ed., 2018, chapter 13.
  2. Lightman et al., “Let’s Verify Step by Step”, ICLR 2024.
  3. Uesato et al., “Solving math word problems with process- and outcome-based feedback”, arXiv:2211.14275, 2022.