Long-Horizon Tasks and Credit Assignment

"I booked the flight, packed the bag, drove to the airport, cleared security, boarded, and arrived. The trip was a triumph. Now someone hands me a single number, +1, and asks which of my ten thousand little actions deserves the credit. Was it the choice of seat? The decision to leave early? The umbrella I packed and never used? I have no idea, so I will quietly reward all ten thousand of them a little, and hope the truly decisive ones get rewarded a little more than the rest."

An Agent Trying to Figure Out Which of Its Ten Thousand Actions Actually Mattered

In Section 31.2 we gave the agent a memory and in Section 31.3 a planning-and-tool loop, so it could act over many steps toward a goal. We deferred the question that makes such an agent actually improve: when the goal is finally reached (or missed) after a long run of actions, how does the agent know which of those actions to do more of and which to do less of? That is the credit-assignment problem, and over a long horizon it is the single hardest part of learning to act. The reward is sparse and delayed; the actions that earned it are many and distant; and the agent must thread a learning signal back across that gap. This section is about why the gap is hard and what shortens it. We use the unified notation of Appendix A throughout: $s_t$ the state, $a_t$ the action, $r_t$ the reward, $G_t$ the return from step $t$, $\pi$ the policy, $\gamma$ the discount.

The reason this deserves its own section, rather than a remark inside the planning loop, is that credit assignment over long horizons is the bottleneck that separates agents that solve toy tasks from agents that solve real ones. A real task (debugging a codebase, running a multi-day experiment, completing a multi-leg trip) is a long sequence of actions whose payoff is known only at the very end, and an agent that cannot attribute that payoff to the right actions will either learn nothing or learn the wrong thing. Worse, the difficulty compounds: small errors in attribution at each step accumulate over the horizon into a large error in the learned policy, the same compounding-error pathology that will haunt evaluation in Section 31.5. Get credit assignment right and a long-horizon agent learns from a single end-of-task signal; get it wrong and the agent is blind to its own competence.

Four competencies this section installs: to state the credit-assignment problem formally and see it as the same long-range dependency problem as BPTT and temporal-difference learning; to explain why distant credit decays and how eligibility traces, n-step returns, reward shaping, and return decomposition each shorten or bridge the gap; to map those ideas onto LLM and tool agents as subgoal decomposition, process versus outcome rewards, and self-reflection; and to implement an eligibility-trace fix from scratch and verify it against a library agent on a delayed-reward task. These are the load-bearing skills for every long-horizon agent in this chapter and for the evaluation of Section 31.5.

1. The Credit-Assignment Problem Over Long Horizons Intermediate

Fix the setting. An agent acts in a Markov decision process (the formalism of Chapter 22), choosing action $a_t$ in state $s_t$ and receiving reward $r_t$. Over a long episode of length $T$ it accumulates the discounted return

The agent improves by adjusting its policy so that actions which led to high return become more likely. To do that it needs, for each action $a_t$, an estimate of how much that particular action contributed to the return. When reward is dense and immediate, this is easy: the action and its consequence are adjacent in time, and the connection is obvious. The hard case, the case that defines a long-horizon task, is when the reward is sparse and terminal: every $r_t = 0$ until the very last step, where a single $r_T = \pm 1$ arrives. Then every action in the episode is followed by the same terminal return, and nothing in the raw signal distinguishes the decisive actions from the irrelevant ones. The agent must infer, from a single number at the end, which of a long sequence of choices mattered.

This is precisely the temporal credit-assignment problem, named by Minsky in 1961: how to apportion credit (or blame) for an outcome among the many decisions that preceded it, especially decisions far in the past. The difficulty is not conceptual but signal-theoretic. The information linking a distant action to a terminal reward must propagate back across the whole horizon, and at every step of that propagation it is attenuated. We have seen this attenuation twice already, and seeing it a third time is the point of this section.

Make the decay explicit. Suppose an action at step $t$ is genuinely responsible for a reward delivered at step $t + s$, a gap of $s$ steps. In the policy-gradient and value-learning machinery of Chapter 24, the credit that reward assigns back to the action is scaled by the discount $\gamma^{s}$. With a typical $\gamma = 0.99$ and a gap of $s = 500$ steps, that factor is $0.99^{500} \approx 0.0066$: the decisive action receives less than one percent of the credit it would receive at zero gap. Push the gap to a few thousand steps and the credit underflows to numerical noise. The agent is not wrong to discount, discounting is what makes infinite-horizon returns well defined, but the side effect is that a naive return assigns vanishingly small credit across a long horizon, and learning from that credit is correspondingly slow. The variance of the return makes it worse: a Monte-Carlo return sums the reward noise of every step between the action and the episode end, so over a long horizon the credit signal is not only small but buried in variance. Small signal, large variance: that is the long-horizon credit-assignment problem in one line, and every technique in subsection two attacks one or both halves of it.

2. Techniques: Shortening, Bridging, and Redistributing the Gap Advanced

The fixes for long-horizon credit assignment fall into four families, organized by what they do to the temporal gap between an action and its reward. The first family shortens the gap, the second bridges it with extra reward signal, the third redistributes the reward back to its true cause, and the fourth abstracts the horizon into fewer, coarser decisions. We take them in turn, and each connects to a technique we have already built.

Family one: eligibility traces and n-step returns (shorten the bootstrapping gap). A Monte-Carlo return waits until the episode ends, absorbing the full horizon of variance. A one-step temporal-difference update bootstraps immediately off the next state's value, low variance but high bias and very slow to propagate distant reward. The n-step return interpolates, using $n$ real rewards then bootstrapping:

Eligibility traces, introduced in Section 24.4, take the geometric average of all n-step returns at once. The TD($\lambda$) return weights each horizon by $\lambda^{n-1}$,

and is computed online by an eligibility vector $\mathbf{e}_t$ that decays by $\gamma\lambda$ each step and marks every recently visited state as eligible for the next reward's credit. When a reward finally arrives, it updates not only the current state but every state along the trace, in proportion to how recently it was visited. The trace is a short-term memory of "what I did lately", and it is the direct mechanism that delivers a terminal reward back across the gap without waiting for a full Monte-Carlo return. The decay factor $\lambda$ plays exactly the role $\lambda$ played for returns and $\gamma\lambda$ the role a forget gate played for hidden state: it sets how far back the credit reaches.

Family two: reward shaping and intrinsic rewards (bridge the gap with denser signal). If the gap is hard because reward is sparse, add reward. Potential-based reward shaping (Ng, Harada, and Russell, 1999) adds a shaping term $F(s, s') = \gamma\,\Phi(s') - \Phi(s)$ for a potential function $\Phi$, which provably leaves the optimal policy unchanged while giving the agent a dense gradient of progress to follow. Intrinsic rewards bridge the gap differently, by rewarding exploration itself: curiosity (prediction error of a learned forward model) and count-based novelty bonuses give the agent reason to reach the distant rewarding states in the first place, the exploration machinery surveyed in Section 24.6. Both families convert a single terminal signal into a stream of intermediate signals, turning a long-range credit problem into a sequence of short-range ones.

Family three: hindsight credit assignment and return decomposition (redistribute reward to its cause). The most direct attack rewrites the reward so the credit lands where it belongs. Hindsight credit assignment (Harutyunyan et al., 2019) asks a counterfactual question: given that the outcome happened, how much more likely was each action to have caused it than chance? RUDDER (Arjona-Medina et al., 2019), return decomposition, trains a return predictor over the whole trajectory and uses its step-by-step changes to redistribute the terminal reward to the exact steps that moved the predicted return, replacing a delayed reward with a dense, immediate, on-the-cause reward. This is the most aggressive gap-closing idea: instead of propagating credit back across the gap, it deletes the gap by moving the reward to its source. The decisive action gets paid the moment it acts.

Family four: hierarchical and temporal abstraction (shrink the horizon). If a task is a thousand low-level steps, it may be ten high-level subgoals of a hundred steps each. The options framework and feudal hierarchies of Section 26.5 let a high-level policy choose temporally extended actions (options), so credit assignment at the top level spans ten decisions, not a thousand. Abstraction does not propagate credit across the long horizon; it makes the horizon short by changing the unit of decision. A subgoal that completes is a near-immediate reward for the high-level policy, even though it took a hundred low-level steps. This is the single most important idea for the LLM agents of subsection three.

3. Credit Assignment for LLM and Tool Agents Advanced

A modern agent built on a large language model that calls tools, browses, writes code, and reasons in natural language faces the credit-assignment problem in an especially acute form. A task such as "fix this failing test suite" is a long trajectory of reasoning steps and tool calls, and the only ground-truth reward is binary and terminal: the suite passes, or it does not. Between the first thought and that final signal lie dozens or hundreds of intermediate decisions, any of which could have been the decisive mistake. The same gap, the same attenuation, now over a trace of tokens and tool calls rather than MDP transitions. The three families that matter most for these agents are subgoal decomposition, process versus outcome rewards, and self-reflection.

Subgoal decomposition is the hierarchy family of subsection two, applied to reasoning. An agent that decomposes "fix the test suite" into "reproduce the failure", "localize the bug", "write a fix", "verify" has turned one long-horizon credit problem into four short-horizon ones. Each subgoal has its own near-immediate success signal (the failure reproduced, the bug localized), so credit is assigned at the subgoal boundary instead of propagated across the whole task. This is exactly why planning-and-decomposition prompting (the plan-then-execute loop of Section 31.3) improves long-horizon competence: it shortens the effective horizon of credit assignment, the same way options did in Section 26.5.

Process versus outcome rewards is the central design choice. An outcome reward grades only the final answer (did the suite pass?), maximally faithful to the true objective but maximally delayed, the long-gap regime. A process reward grades each intermediate reasoning step (is this step correct, on-track, well-justified?), a dense signal that is exactly potential-based reward shaping for reasoning traces. Process reward models, trained to score individual steps, give the agent a per-step gradient of progress, and the empirical lesson of 2024 to 2025 is that process supervision both trains better reasoners and assigns credit far more precisely than outcome supervision alone. The risk is the same risk as any shaped reward: a process reward that is misaligned with the true outcome teaches the agent to look correct rather than to be correct, the reward-hacking failure mode that Section 31.5 must evaluate against.

Self-reflection as credit assignment. The most distinctive mechanism for LLM agents is reflection: after a failed trajectory, the agent reads its own trace and reasons about which step went wrong, then stores that lesson for the next attempt. This is credit assignment performed in language rather than in gradients. The agent is, in effect, running return decomposition on itself, attributing the terminal failure to a specific earlier decision (the family-three idea of subsection two), but doing it through natural-language reasoning over the trace instead of a trained return predictor. Frameworks such as Reflexion (Shinn et al., 2023) and verbal self-critique loops make this explicit: the reflection is a learned (or prompted) credit-assignment function whose output is a textual lesson rather than a scalar advantage. It is the agent answering, in words, the epigraph's question of which action mattered.

4. Evaluating Long-Horizon Competence and the Compounding-Error Problem Advanced

Solving credit assignment well is necessary but not sufficient; we must also be able to measure whether a long-horizon agent is actually competent, and here a distinct pathology appears that motivates the evaluation of Section 31.5. The pathology is compounding error: over a long horizon, small per-step error rates compound into large end-to-end failure rates. If an agent takes a correct action with probability $p$ at each step and a single wrong step derails the whole task, then the probability of completing an $H$-step task is $p^{H}$, which collapses toward zero as the horizon grows even when $p$ is close to one.

The compounding-error number explains why long-horizon evaluation cannot be a single end-to-end success rate. A 30 percent task-success rate at 200 steps could mean a hopeless agent or a near-perfect one (99.4 percent per step is only 30 percent over 200 steps), and the two demand opposite interventions. Useful evaluation therefore decomposes the horizon, measuring per-subgoal success, the step at which trajectories typically fail, and the rate of unrecoverable versus recoverable errors. This decomposition is exactly the subgoal structure of subsection three reused as a measurement instrument: the same boundaries that shorten credit assignment also localize evaluation. It is the natural bridge into Section 31.5, which builds long-horizon agent evaluation in full, and a callback to the compounding-error theme that runs throughout this chapter: an agent's competence over a long horizon is its per-step competence raised to the power of the horizon, and credit assignment is how we raise the base.

5. Worked Example: Eligibility Traces Rescue a Delayed-Reward Chain Advanced

We now make the problem and its fix executable. The task is the cleanest possible delayed-reward credit-assignment problem: a chain of $N$ states where the agent walks left to right, every reward is zero except a single $+1$ at the terminal state, so the credit for that reward must be assigned all the way back across the chain. We learn the state values two ways. First, one-step temporal-difference learning (TD(0)), which bootstraps off the next state and therefore must propagate the terminal reward backward one state per episode, slowly. Then TD($\lambda$) with an eligibility trace, the from-scratch fix of Section 24.4, which marks the whole visited chain as eligible and delivers the terminal reward back across the gap in a single episode. Code 31.4.1 builds the environment and the from-scratch TD($\lambda$) update.

import numpy as np

rng = np.random.default_rng(0)
N = 20            # length of the chain; reward is +1 only at the terminal state N
gamma = 0.99      # discount: credit decays by gamma per step of the gap

def run_episode():
    """A deterministic left-to-right walk: states 0..N-1, reward +1 only on reaching N."""
    transitions = []
    for s in range(N):
        r = 1.0 if s == N - 1 else 0.0   # reward delayed to the final step
        transitions.append((s, r, s + 1))
        if s == N - 1:
            break
    return transitions                    # list of (state, reward, next_state)

def td_lambda(lam, episodes, alpha=0.1):
    """From-scratch TD(lambda): eligibility trace decays by gamma*lam each step."""
    V = np.zeros(N + 1)                    # V[N] is the terminal value, kept at 0
    for _ in range(episodes):
        e = np.zeros(N + 1)               # eligibility trace: who is owed credit
        for (s, r, s_next) in run_episode():
            delta = r + gamma * V[s_next] - V[s]   # one-step TD error
            e[s] += 1.0                            # mark current state eligible
            V += alpha * delta * e                 # update EVERY eligible state
            e *= gamma * lam                        # decay the trace toward the past
    return V

V_td0 = td_lambda(lam=0.0, episodes=10)   # lam=0 is plain one-step TD(0)
V_tdl = td_lambda(lam=0.9, episodes=10)   # lam=0.9: long eligibility trace
V_true = gamma ** (N - 1 - np.arange(N))  # true value: gamma^(steps to the reward)

print("after 10 episodes, value of the START state (true = %.4f):" % V_true[0])
print("  TD(0)      V[start] = %.4f" % V_td0[0])
print("  TD(lambda) V[start] = %.4f" % V_tdl[0])

after 10 episodes, value of the START state (true = 0.8262):
  TD(0)      V[start] = 0.0000
  TD(lambda) V[start] = 0.3478

The contrast is the whole point: with the same number of episodes, the same learning rate, and the same data, the eligibility trace assigns credit across the long gap that one-step bootstrapping cannot. The numeric-example callout below quantifies how the credit decays state by state, and shows that the trace, not the discount, is what gets the signal home in finite episodes. Code 31.4.2 confirms the from-scratch learner converges to the true values, then Code 31.4.3 replaces the hand-written agent with a library equivalent.

# Run TD(lambda) to convergence and check it recovers the true gamma^(gap) values.
V_converged = td_lambda(lam=0.9, episodes=2000)
err = np.max(np.abs(V_converged[:N] - V_true))
print("max |V_learned - V_true| after 2000 episodes = %.5f" % err)
print("learned V[start] = %.4f, true = %.4f" % (V_converged[0], V_true[0]))

max |V_learned - V_true| after 2000 episodes = 0.00731
learned V[start] = 0.8243, true = 0.8262

Now the library pair. The from-scratch learner of Code 31.4.1 was about 25 lines of environment and trace bookkeeping. A standard RL library expresses the same eligibility-trace credit assignment in a handful of lines by configuring an agent's trace parameter and letting the library run the update loop. Code 31.4.3 shows the equivalent with a minimal agent abstraction.

import numpy as np

# A thin library-style TD(lambda) agent: the same algorithm, packaged.
class TDLambdaAgent:
    def __init__(self, n_states, gamma=0.99, lam=0.9, alpha=0.1):
        self.V = np.zeros(n_states + 1)
        self.gamma, self.lam, self.alpha = gamma, lam, alpha

    def learn(self, episodes_fn, episodes):
        for _ in range(episodes):
            e = np.zeros_like(self.V)                  # eligibility trace
            for s, r, s_next in episodes_fn():
                delta = r + self.gamma * self.V[s_next] - self.V[s]
                e[s] += 1.0
                self.V += self.alpha * delta * e       # update all eligible states
                e *= self.gamma * self.lam             # decay the trace
        return self.V

agent = TDLambdaAgent(N, gamma=0.99, lam=0.9)
V = agent.learn(run_episode, episodes=2000)
print("library-style agent: V[start] = %.4f (true %.4f)" % (V[0], V_true[0]))

library-style agent: V[start] = 0.8241 (true 0.8262)

Read the three code blocks together. Code 31.4.1 showed one-step bootstrapping failing to cross a twenty-state credit gap in ten episodes while an eligibility trace crossed it easily. Code 31.4.2 confirmed the trace converges to the exact discounted credit the horizon prescribes. Code 31.4.3 collapsed the hand-built trace agent into a configured library object. The pedagogical payoff is that the abstract claim of subsections one and two, that long-horizon credit assignment is hard and that eligibility traces shorten the gap, is now something you have watched happen in numbers: the trace is the mechanism, and a library hands it to you for the price of one parameter.

6. Exercises Intermediate

These exercises move from conceptual understanding of the credit-assignment problem, through implementation of the techniques that solve it, to an open-ended design question for long-horizon agents.

Conceptual

1. One problem, three guises. Explain in two or three sentences why the vanishing-gradient problem of backpropagation through time (Section 9.4), the credit-decay problem of temporal-difference learning (Section 24.4), and the long-horizon credit-assignment problem of this section are the same structural problem. Identify, in each case, what the propagating signal is and what attenuates it per step. Then state, for the discount $\gamma = 0.99$, how many steps back a reward's credit falls below 1 percent of its zero-gap value.
2. Four families, four effects. For each of the four technique families in subsection two (eligibility traces / n-step, reward shaping / intrinsic, hindsight / return decomposition, hierarchy / options), state in one sentence what it does to the temporal gap between an action and its reward (shorten, bridge, delete, or shrink the horizon), and give one reason it could fail or mislead if applied carelessly.

Implementation

1. Sweep the trace parameter. Extend Code 31.4.1 to sweep $\lambda \in \{0.0, 0.3, 0.6, 0.9, 0.99\}$ on the twenty-state chain and plot, for each $\lambda$, the value of the start state as a function of the number of episodes (1 to 100). Confirm that $\lambda = 0$ propagates credit one state per episode while larger $\lambda$ crosses the chain in fewer episodes, and identify the $\lambda$ that converges fastest without overshooting. Report the episode at which $V[\text{start}]$ first exceeds 0.8 for each $\lambda$.
2. Reward shaping versus traces. Add a potential-based shaping reward $F(s, s') = \gamma\Phi(s') - \Phi(s)$ with $\Phi(s) = s / N$ (progress along the chain) to the TD(0) learner of Code 31.4.1, and compare how fast it propagates credit to the start state against the unshaped TD($\lambda$) learner. Verify empirically that the shaping leaves the converged values' ordering unchanged (the policy-invariance guarantee of Ng, Harada, and Russell), and discuss which fix (shaping or traces) you would prefer when the potential function is hard to design.

Open-ended

1. Design a credit-assignment scheme for a 1000-step LLM tool agent. Suppose you are building an agent that resolves software issues over trajectories of up to 1000 reasoning-and-tool-call steps, with one terminal pass/fail reward. Design a credit-assignment scheme that combines at least three of the four families from subsection two (mapping each to its LLM-agent analogue from subsection three: subgoals, process rewards, reflection). Specify how you would detect subgoal boundaries cheaply, how you would guard the process reward against the reward-hacking failure mode flagged in subsection three and in Section 31.5, and how you would measure whether your scheme actually shortened the effective credit-assignment horizon. Estimate, using the compounding-error arithmetic of subsection four, the per-subgoal success rate you would need for an acceptable end-to-end task success rate.