Credit Assignment Over Long Horizons
9 min read · updated August 4, 2026
An agent takes 400 actions and receives one number at the end. Three of those actions mattered. Nothing in the reward says which three, and nothing in the learning algorithm knows either — it finds out by averaging over enough episodes for the irrelevant actions to cancel. This page works out how many that is.
The problem, stated precisely
The temporal credit assignment problem is the difficulty of attributing a delayed outcome to the decisions that caused it. It is not a defect of any particular algorithm; it is a property of the information available. A single scalar per episode is simply not enough to identify which of many decisions produced it, from one episode.
The REINFORCE gradient makes this explicit. It multiplies every action’s gradient by the same return, so a successful episode reinforces all 400 actions equally: the three that mattered, the 380 that were irrelevant, and the 17 that were actively bad but got away with it. The estimator is correct in expectation — average over enough episodes and the irrelevant actions appear equally often in good and bad episodes, so their contributions cancel. Everything hinges on “enough”.
How many episodes it takes
Assumptions. Episodes of 400 steps with a binary success reward. Overall success probability around 0.5, so the reward has standard deviation sqrt(0.5 * 0.5) = 0.5. One particular action at one particular step improves the success probability by 5 percentage points, from 0.50 to 0.55. Nothing else about the episode changes.
to see a difference of 0.05 between two groups of episodes, the standard error of each group mean must be comfortably below it. standard error = sigma / sqrt(N) = 0.5 / sqrt(N) require SE <= 0.025 (half the effect): 0.5 / sqrt(N) <= 0.025 sqrt(N) >= 20 N >= 400 episodes per group two groups (action taken / not taken) -> 800 episodes to resolve all 400 decision points -> 320,000 episodes
That last figure overstates it, because episodes are shared across decision points and function approximation generalises between similar states — the true requirement is far lower and depends on how much structure the policy network can exploit. It understates it in another direction, because a 5-point effect is large, most real decisions matter less than that, and the required sample size grows with the inverse square of the effect: a 1-point effect needs 25 times as many episodes.
The useful conclusion is the scaling, not the number. Sample requirements grow with the square of how small an effect you need to resolve, and with the number of decisions that need resolving. That is why long-horizon RL is expensive in a way that is not fixed by faster hardware, and it is the quantitative content of the field’s reputation for poor sample efficiency.
Why the gradient cannot tell the difference
It is worth being clear that this is an information problem rather than an algorithmic one. Consider two policies that differ only at step 200. The only observable consequence is a slightly different distribution over final rewards. Any method whatsoever — policy gradients, value learning, evolution strategies, random search — must distinguish two distributions that differ by 0.05 in their means using samples with a standard deviation of 0.5. No algorithm gets around the arithmetic in the previous section; algorithms differ only in how much additional structure they bring to reduce the variance.
That reframing is what makes the list of techniques below comprehensible. Every one of them is a way of adding information that the raw reward does not contain, and every one of them is therefore a form of assumption.
Choosing the grain of an action
Before choosing a technique there is a modelling decision that changes the problem’s size, and in an LLM system it is usually made by accident. What counts as one action?
| Grain | Description |
|---|---|
| one token | The horizon is the length of the response — hundreds or thousands of steps for a single answer. Maximum flexibility, worst credit assignment, and the reason a per-token value function is asked to do so much work in PPO-based RLHF. |
| one tool call | The horizon is the number of calls, typically 5 to 50. The policy is still the same model emitting tokens, but the unit being credited is a whole call and its result. Far more tractable, and it matches how failures are actually diagnosed. |
| one sub-task | The horizon is a handful of steps, each with a checkable intermediate state. Best credit assignment available, and it requires that you can define what a completed sub-task looks like — which is design work, not training work. |
The arithmetic in the previous section scales with the number of decision points, so moving from token grain to call grain on a 40-call task cuts the number of things needing credit by two or three orders of magnitude. That is a larger effect than any algorithmic improvement on this page, and it costs nothing at training time.
The cost is expressiveness. At call grain you cannot learn to phrase things better within a call, only to choose calls better. Whether that matters depends entirely on where your failures are, which is an argument for looking at where the agent fails before choosing what to optimise.
Five techniques, and what each one trades
| Technique | Description |
|---|---|
| discounting | A gamma below 1 makes distant rewards count for less, which cuts variance by effectively shortening the horizon. It is also a bias: if a reward genuinely arrives 400 steps later and gamma says it is worth nothing, the agent will correctly learn to ignore it. Discounting buys learnability by changing the problem. |
| bootstrapping (TD) | Replace the sampled future with a learned value estimate, so credit stops at one step instead of propagating from the end. Variance falls sharply; bias appears wherever the value function is wrong. The full spectrum is the lambda in GAE, worked numerically on the actor-critic page. |
| eligibility traces | Keep a decaying record of recently visited states and apply each update to all of them in proportion. Mathematically close to the lambda family, and useful when updates must be online rather than batched. |
| hindsight relabelling | In goal-conditioned tasks, a failed episode is a successful episode for whatever goal was actually reached. Hindsight Experience Replay (Andrychowicz et al., 2017) converts a zero reward into a positive one for a different goal, which fabricates dense signal from sparse outcomes. It requires that goals be part of the input, which many tasks can be rewritten to satisfy. |
| process supervision | Score intermediate steps instead of only the outcome. This is the direct attack: it replaces one number per episode with one per step. Lightman et al. (2023) reported that step-level rewards outperformed outcome-level rewards on mathematical reasoning. The cost is that somebody, or some model, has to produce those step labels. |
Reward shaping, and the one safe version
The tempting fix is to add intermediate rewards by hand: a point for getting closer to the goal, a point for picking up the key. This works often enough to be popular and changes the optimal policy often enough to be dangerous. Reward a robot for approaching a ball and it may learn to oscillate towards it forever, collecting approach reward without ever arriving.
There is a form of shaping that provably does not change the optimal policy, from Ng, Harada and Russell (1999). Shape with the difference of a potential function over states:
F(s, a, s') = gamma * PHI(s') - PHI(s) where PHI is any function of state alone. telescoping over an episode, the total added reward is gamma^T * PHI(s_T) - PHI(s_0) which depends only on where you started and finished -- so no policy can gain by cycling, and the ordering over policies is unchanged.
The condition is strict and it is the reason the guarantee holds: PHI may depend on the state only, not on the action and not on the step number. A shaping term of “+0.1 for moving towards the goal” is a function of the action and is not potential-based; a shaping term built from -distance_to_goal as a potential is. That distinction is small on the page and decides whether your agent optimises the task or the shaping.
The same problem in an LLM agent
An agent that makes 40 tool calls and either accomplishes the task or does not is exactly this problem at a smaller scale, and the same options apply.
- Outcome reward only is the honest baseline: cheap to compute, unambiguous, and it credits all 40 calls equally. Whether that is enough depends on how many episodes you can afford.
- Step-level rewards — did this tool call return something useful, did this search find the relevant document — are process supervision, and they buy an enormous amount of signal. They also introduce a new proxy per step, each with its own hacking potential, which is the trade reward hacking describes.
- Shortening the episode is the underrated option. Decomposing a 40-step task into four 10-step tasks with checkable intermediate states makes credit assignment four times easier and costs nothing at training time. Much of what looks like an RL problem is a task-decomposition problem that has not been done yet.
- Not training at all is frequently right. If the failure is that the agent takes a bad action in an identifiable situation, a rule, a better tool description or a retrieval fix addresses it in an afternoon, with a change you can read.
The last point is the general one. Credit assignment is the cost of learning from outcomes, and it is worth paying only when you cannot specify the behaviour any other way — which is the argument of the last page in this cluster.