20.3 Trajectory Credit Assignment

22.2 Multi-Turn RL Formalization wrote the trajectory probability as ${\rho }_{\theta }(x|s_0,c)=\mathbb{I}(s_0,x){\prod }_{t\in a(x)}{p}_{\theta }(x_t|\cdot )$, and derived the action mask -- only action tokens participate in the policy gradient. But that only answers "which tokens should we compute a gradient on," not "how large an advantage should each action token be multiplied by."

The policy gradient has the form:

$$\nabla J(\theta )={\mathbb{E}}_{\tau \sim {\pi }_{\theta }}\left[R(\tau )\nabla \log {\pi }_{\theta }(\tau )\right]$$

The trajectory-level scalar $R(\tau )$ treats the whole trajectory the same way -- if it succeeds, every action was good; if it fails, every action was bad. This is the core difficulty of Agentic RL: if 7 turns of interaction end in failure, does the correct search in turn 1 also get punished?

Breaking $R(\tau )$ back down into a step-level advantage $A_{i,t}$ for every step is credit assignment. This section works through the problem systematically: starting from the simplest ORM/PRM dichotomy, then unpacking four families of finer-grained methods developed over 2025-2026.

Three Layers of Signal: From Final Outcome to Token Update

When a rollout fails, the signal has to pass through three layers before it reaches the LLM's weights.

Layer 1: Trajectory reward. The whole trajectory ends up with a single $R({\tau }_i)$, which only tells us "did this episode succeed or not." This is the entirety of the signal the environment provides.

Layer 2: Step advantage. The final outcome is broken down into $A_{i,1},A_{i,2},\dots ,A_{i,T}$, answering "should turn $t$ be rewarded or not." This is the core work of credit assignment.

Layer 3: Token gradient. $A_{i,t}$ is multiplied onto the token log-probabilities of that turn's action:

$$\Delta \theta =A_{i,t}\cdot \sum _{k\in a_{i,t}}\nabla \log {\pi }_{\theta }(y_k\mid h_{i,t},y_{<k})$$

where $a_{i,t}$ is the set of tokens generated by the LLM at turn $t$ of trajectory $i$, and $h_{i,t}$ is the context at that point. Content returned by web pages or tools is masked and does not participate in this step.

Much of current GRPO-style Agentic RL work is, at its core, about constructing a better $A_{i,t}$.

ORM and PRM: The Basic Dichotomy of Credit Assignment

The two simplest approaches define the two extremes of credit assignment.

ORM: Look Only at the Final Outcome

ORM (Outcome Reward Model) gives a reward only at the end of the trajectory; every intermediate step gets 0:

$$r_1=r_2=\cdots =r_{T-1}=0,r_T=\{\begin{array}{ll}1& \text{success}\\ 0& \text{failure}\end{array}$$

The advantage of ORM is that it is simple and cheap -- you only need to know whether the final result is right. For verifiable tasks (whether code passes tests, whether a math answer is correct), you don't even need to train a reward model; you can use a verifier directly. RLVR (Reinforcement Learning with Verifiable Rewards) is the extreme form of ORM, and DeepSeek-R1's success proved that pure ORM can elicit strong reasoning ability.

The disadvantage of ORM is that the signal is sparse. A 10-step trajectory has only 1 reward signal, and it's hard for the model to learn from that "which specific step should be improved." If every step is punished on failure -- including the intermediate steps that were actually done correctly -- credit assignment becomes badly distorted.

PRM: Score Every Step Independently

PRM (Process Reward Model) scores each step independently:

$$r_t=f_{\text{PRM}}(s_1,a_1,s_2,a_2,\dots ,s_t,a_t)$$

PRM looks at the complete history from step 1 through step $t$ and judges whether step $t$ is correct. OpenAI's "Let's Verify Step by Step" (Lightman et al., 2023) formally proposed this idea: the first step of reasoning is correct (+1), the second step has a computational error (-0.5), the third step is correct but takes a detour (+0.3). The model can pinpoint exactly which step needs improvement.

The disadvantage of PRM is that the labeling cost is extremely high -- labeling "correct/incorrect" for every step is $T$ times more work than labeling only the final outcome. OpenAI built the PRM800K dataset for exactly this reason. Current research hotspots include automated PRM (e.g. Math-Shepherd, which lets the model judge the quality of each step on its own) and domain-specialized PRM (e.g. Web-Shepherd, purpose-built for web navigation).

	ORM	PRM
Signal density	Sparse (only final reward)	Dense (reward at every step)
Labeling cost	Low (only look at outcome)	High (every step must be labeled)
Learning speed	Slow (little signal, high variance)	Fast (more signal, lower variance)
Best suited for	Verifiable tasks (code / math)	Complex reasoning (needs fine guidance)

SALT: Extracting Step-Level Advantage from a Trajectory Graph

ORM is too coarse, PRM too expensive. SALT (Li et al., EACL 2026) offers a third path -- it doesn't train a PRM, but it's much finer-grained than pure ORM.

The core idea: sample multiple trajectories for the same prompt and build a trajectory graph -- nodes are the actions taken at each step, and if two trajectories take the same action at a given step, they share the same node. Analyzing the graph structure lets you quantify each step's contribution to the final outcome.

The intuition: if a step is shared by many successful trajectories but rarely appears in failed ones, it's probably a good step and should get a positive advantage. Conversely, if a step only appears in failed trajectories, it probably held things back. SALT uses the graph structure to compute an advantage for every step, without requiring any extra reward model or human annotation -- only the binary signal of the final outcome.

This makes SALT particularly convenient inside GRPO: GRPO already samples multiple trajectories within a group for comparison, and SALT refines that comparison further down to the step level.

Three Sources of Step-Level Advantage

Beyond ORM/PRM/SALT, a large family of finer-grained methods emerged over 2025-2026. XiaoRed5's introductory material and the April 2026 survey From Reasoning to Agentic: Credit Assignment in RL for LLMs group these methods into three categories by where the signal comes from. What distinguishes them isn't how the policy gets updated at the end, but where the step-level signal $A_{i,t}$ originates.

Direction One: State-Anchored Stepwise -- Comparing Actions Under the Same State

Core idea: under the same state, the relative quality of different actions can be read off from their respective subsequent returns. No PRM needed -- just the natural structure of multiple rollouts within a group.

GiGPO: Relative Return Within the Same State Group

GiGPO (Group-in-Group Policy Optimization) works like this: sample multiple rollouts for the same task, and if these rollouts pass through the same environment state $s$ somewhere in the middle, you can compare "given the same situation, which action was better."

First, group together all the actions that occurred at state $s$:

$$G^S(s)=\{(a_t^{(i)},R_t^{(i)})\mid s_t^{(i)}=s\}$$

Here $R_t^{(i)}$ is not the whole-trajectory reward, but the discounted return from this step onward:

$$R_t^{(i)}=\sum _{k=t}^T{\gamma }^{k-t}{r}_k^{(i)}$$

If the environment only has a final success reward, you can think of it intuitively as: if the episode eventually succeeds after this step, the return is positive; the later success arrives, the smaller the discounted return; and if it ultimately fails, the return is close to 0.

Then compute a relative advantage within the same state group:

$$A^S(a_t^{(i)})=\frac{R_t^{(i)}-\text{mean}(\{R_t{\}}_{G^S(s)})}{F_{\text{norm}}(\{R_t{\}}_{G^S(s)})}$$

An action's step score equals the return it led to, minus the average subsequent return of other actions at the same state.

WebShop example: several rollouts all arrive at the same product-search-results page:

Action	Subsequent outcome	$R_t$
Click the correct item	Succeeds quickly	1.00
Click the wrong item, but later goes back and buys the right one	Succeeds a bit later	0.73
Click "next page"	Eventually fails	0.00

The group average is $\bar{R}=0.58$. The relative scores of the three actions:

Click the correct item:   1.00 - 0.58 = +0.42
Click the wrong item:     0.73 - 0.58 = +0.15
Click "next page":        0.00 - 0.58 = -0.58

What the model learns is not "every action in a successful trajectory is good," but a much finer local preference: given the same situation, clicking the correct item is best; clicking the wrong item isn't ideal but there's still room to recover; clicking "next page" is worst, because what followed it was failure.

Finally, GiGPO combines the whole-trajectory macro advantage with this step's micro advantage:

$$A(a_t^{(i)})=A^E({\tau }_i)+\omega \cdot A^S(a_t^{(i)})$$

where $A^E$ is the trajectory-level relative quality, and $A^S$ is the step-level relative quality within the same state.

HGPO: Also Accounting for Historical Context

HGPO (Hierarchy-of-Groups Policy Optimization) is a key correction to GiGPO. GiGPO compares actions under the same state, but HGPO points out: the same current state doesn't necessarily mean the same decision context.

The scenario most prone to error is web tasks: two rollouts might arrive at exactly the same page, but they got there via different paths. One agent might have arrived here carrying the full set of constraints ("black, waterproof, low-price rain boots"), while another agent already dropped the "waterproof" constraint earlier (searching only "black boots"). At this point, the same action ("add to cart") carries a different meaning depending on which agent takes it -- for the first agent it's probably a good action, while for the second it might be a bad one, because a key constraint got dropped. HGPO calls this historical context inconsistency.

HGPO defines a $k$-step context operator:

$${\mathcal{C}}_k(s_t^{(i)})=(s_{t-k}^{(i)},s_{t-k+1}^{(i)},\dots ,s_t^{(i)})$$

meaning "the current state plus the previous $k$ historical states." When $k=0$, only the current state matters; the larger $k$ is, the longer the shared history required, and the more consistent the context.

For each step, construct multiple levels of groups:

$$G_k^H(s_t^{(i)})=\{(j,n):{\mathcal{C}}_k(s_t^{(i)})={\mathcal{C}}_k(s_n^{(j)})\}$$

These groups are nested: $G_0^H\supseteq G_1^H\supseteq \cdots \supseteq G_K^H$. $G_0^H$ is the large group of "just look at the current page" (many samples but easy to conflate); $G_K^H$ requires a longer shared history (fairer, but fewer samples).

Compute a within-group relative advantage at each level:

$$A_k^H(s_t^{(i)})=\frac{R(s_t^{(i)})-\frac{1}{|G_k^H|}{\sum }_{(j,n)\in G_k^H}R(s_n^{(j)})}{{\sigma }_{G_k^H}}$$

Finally, HGPO combines the advantages from different levels with weights:

$$A^H(s_t^{(i)})=\sum _{k=0}^K{w}_k{A}_k^H(s_t^{(i)}),w_k=\frac{(k+1{)}^{\alpha }}{{\sum }_k(k+1{)}^{\alpha }}$$

$\alpha$ controls how much weight goes to deeper-level groups -- essentially a bias-variance trade-off: deeper groups are fairer but have fewer samples and higher variance.

In short, GiGPO asks "which action is better under the same state," and HGPO goes one step further and asks "which action is better under the same state and a similar historical context."

Group-Graph PO: Modeling the Trajectory as a DAG

Group-Graph Policy Optimization (2026-06) goes further still. It points out that existing step-level frameworks still treat an agent's exploration as "isolated linear trajectories" -- an oversimplified view. In practice, multiple rollouts often share prefixes and share intermediate states, so structurally they look more like a directed acyclic graph (DAG) than a set of parallel lines.

Once the trajectory is modeled as a graph, you can do finer-grained credit assignment on that graph: identify critical branch points, trace the independent contribution of a particular sub-path, and avoid recomputing the advantage of a shared prefix multiple times. This is especially valuable for long-horizon tasks -- when feedback is delayed until dozens of steps later, the DAG structure attributes it back to specific decisions more accurately.

Direction Two: Process / Progress Reward -- Training an Extra Step-Level Scorer

The second family of methods doesn't rely on rollouts colliding at the same state; instead, it trains an extra model that can score individual steps.

SPA-RL: Redistributing the Final Reward into Per-Step Progress

SPA-RL (Stepwise Progress Attribution) takes the reward redistribution route: it trains an extra progress estimator that learns to judge "how much did this step move the task toward completion."

The basic assumption: a long-horizon task's eventual completion is the accumulation of incremental progress at every step. So instead of directly assigning each step an "absolute quality score," the model predicts each step's contribution ${\hat{c}}_t$, and requires these contributions to sum back to the final reward:

$$\hat{R}=\sum _{t=1}^N{\hat{c}}_t\approx R$$

The form of the progress estimator:

$${\hat{c}}_t=\text{MLP}(h_t),h_t=f_{{\pi }_{\gamma }}(s_t,a_t)$$

An LLM encodes the current state-action pair, followed by a lightweight MLP that outputs a scalar contribution. Training uses the final reward from multiple exploration trajectories as supervision:

$${\mathcal{L}}_{\text{PE}}=\frac{1}{|\mathcal{D}|M}\sum _i\sum _j({\hat{R}}_{i,j}-R_{i,j}{)}^2$$

The meaning is direct: if a trajectory ultimately succeeds, the sum of its step contributions should be close to 1; if it ultimately fails, the sum should be close to 0. To fit this objective, the model learns to assign positive contribution to the steps that actually drove the task toward success, and low or negative contribution to steps that were ineffective.

Intuitive example: a search agent that ultimately answers correctly might have a trajectory with 5 steps:

Step	Behavior	Possible progress
1	Issue a vague query	0.05
2	Open an irrelevant page	0.00
3	Rewrite the query and hit the key page	0.30
4	Extract the key evidence	0.45
5	Assemble the final answer	0.20

These scores sum to roughly the final success reward. In RL training, the signal is no longer confined to the last step -- every step gets a dense reward.

SPA-RL also adds a grounding signal $g_t$ (whether the action was actually executable in the environment); the final intermediate reward is $r_t^{\text{fused}}=\alpha c_t+\beta g_t$ -- an action needs to be both "useful" and "executable."

AgentPRM: Treating the PRM as an Agent's Q(s,a)

AgentPRM takes an approach closer to classic actor-critic RL. It treats the process reward model as a state-action value function:

$$Q^{\pi }(s_t,a_t)={\mathbb{E}}_{\pi }\left[\sum _{k=t}^T{\gamma }^{k-t}r(s_k,a_k)\mid s_t,a_t\right]$$

What the PRM outputs isn't "how much did this small step contribute," but "if you take this action at the current state and keep following the current policy afterward, how much total return do you expect."

AgentPRM's training is a three-stage loop:

1. Rollout and Compute Target: sample a large number of trajectories with the current policy ${\pi }_{i-1}$, and use Monte Carlo returns to estimate a target value for each $(s,a)$.
2. Train PRM: treat these automatically labeled $\hat{Q}(s,a)$ values as soft labels, and train the PRM with soft BCE.
3. Train Policy: use the trained PRM as a dense reward to update the policy, while a KL constraint keeps it from drifting too far from the previous round's policy:

$${\pi }_i=\arg \underset{{\pi }_{\theta }}{\max }{\mathbb{E}}_{s,a\sim {\pi }_{\theta }}[Q_{\varphi }(s,a)]-\beta {\mathbb{D}}_{\text{KL}}[{\pi }_{\theta }(\cdot |s)\Vert {\pi }_{i-1}(\cdot |s)]$$

Note that the KL constraint is against the previous round's policy ${\pi }_{i-1}$, not the SFT policy -- because the PRM was trained on rollouts from the previous round's policy, and if the new policy drifts too far, the PRM's estimates become unreliable.

AgentPRM can also do Best-of-N at inference time: at each step, sample $N$ candidate actions from the policy and use the PRM to pick the one with the highest $Q(s,a)$. The biggest risk is reward hacking -- the policy learns to make the PRM score it highly rather than actually succeeding at the real task. Common mitigations include iteratively retraining the PRM, collecting more rollout data, and adding a KL constraint.

PAIR: Prefix-Aware Internal Reward

PAIR (Prefix-Aware Internal Reward Model, 2026-05) targets the training-cost problem of methods like AgentPRM -- retraining the PRM inside a three-stage loop is expensive. PAIR trains an internal reward model that, when scoring a given step, explicitly conditions on the prefix: the same action should get different scores under different prefixes.

Web-Shepherd: A Domain-Specialized PRM

Web-Shepherd (NeurIPS 2025 Spotlight) is the first step-level PRM purpose-built for web navigation; it can automatically judge whether the agent's action at each step is correct. Experiments show that using Web-Shepherd to provide step-level reward improves GPT-4o-mini's performance by 10.9%, at only 1/10 the cost of using an LLM as judge. This shows that PRM isn't merely a theoretical nicety -- in a specific domain, a domain-specialized PRM can provide dense step-level signal cheaply and efficiently.

Direction Three: Intrinsic Signal -- Finding Signal Within the Policy Itself

The third family of methods doesn't train an extra PRM at all; instead it finds step-level signal in the policy's own behavior distribution.

ARPO: Spending the Rollout Budget Where Entropy Spikes

ARPO (Agentic Reinforced Policy Optimization) focuses on tool-calling scenarios. Its key observation: right after an LLM receives a tool's return value, the entropy of the next 10 to 50 generated tokens tends to spike noticeably.

The definition of token entropy:

$$H_t=-\sum _{j=1}^V{p}_{t,j}\log p_{t,j},p_t=\text{Softmax}(z_t/\tau )$$

High entropy means the model is uncertain at that moment: there might be multiple interpretations, multiple candidate tool calls, multiple reasoning paths. ARPO's idea: since the positions of highest uncertainty are most likely to be key decision points, the rollout budget shouldn't be spread evenly -- it should be concentrated there.

ARPO splits rollouts into two kinds:

• Global rollout: sample a complete trajectory start to finish, to guarantee overall exploration
• Partial rollout: branch at high-entropy tool-call nodes, focusing exploration on local decisions

The concrete procedure: given a total rollout budget of $M$, first sample $N$ complete trajectories, leaving $M-N$ for local branching. After each tool call returns, generate $k$ tokens and compute the entropy $H_t$; compare it against the initial entropy $H_{\text{initial}}$ to get a normalized entropy change $\Delta H_t$; if it exceeds a threshold, branch off $Z$ partial rollouts from the current node.

For example, if a search tool returns several pieces of conflicting evidence, the model's entropy spikes, and ARPO branches more heavily there: one branch chases evidence A, one chases evidence B, one rewrites the query to verify. Differences after the branch point are used to update individual tokens; the shared prefix absorbs the average advantage across the branches.

IGPO: Using the Increase in Correct-Answer Probability as a Turn-Level Reward

IGPO (Information Gain Policy Optimization, from DR-Venus) is built on a simple idea: every round of searching, reading evidence, or calling a tool should, in principle, bring the model closer to the correct answer. So just measure directly whether the model's probability of the ground-truth answer went up after that round.

Let the ground-truth answer's token sequence be $a=(a_1,\dots ,a_L)$. The history of rollout $i$ up through turn $t$ is $o_{i,\le t}$. IGPO uses teacher forcing to compute the model's average log probability of generating the correct answer:

$$\log {\pi }_{\theta }(a\mid q,o_{i,\le t})=\frac{1}{L}\sum _{j=1}^L\log {\pi }_{\theta }(a_j\mid q,o_{i,\le t},a_{<j})$$

Dividing by $L$ avoids longer answers naturally having lower log probability.

Then the log-probability increment between two consecutive turns is defined as the information gain reward:

$$r_{i,t}^{\text{IG}}=\log {\pi }_{\theta }(a\mid q,o_{i,\le t})-\log {\pi }_{\theta }(a\mid q,o_{i,\le t-1})$$

Intuitively:

• A useful interaction: log-prob rises from -4.0 to -1.5 → $r^{\text{IG}}=+2.5$ (the search turned up key evidence, and the model is now more confident about the correct answer)
• A misleading interaction: log-prob drops from -2.0 to -3.2 → $r^{\text{IG}}=-1.2$ (the search brought back irrelevant content, and the model actually drifted away from the correct answer)

IGPO also keeps the final outcome reward, and applies group-wise z-normalization to the two kinds of reward separately:

$${\tilde{r}}_{i,t}=\{\begin{array}{ll}\frac{r_{i,t}^{\text{IG}}-{\mu }_{\text{IG}}}{{\sigma }_{\text{IG}}},& 1\le t<T\\ \frac{r_i^O-{\mu }_O}{{\sigma }_O},& t=T\end{array}$$

Then, as in ordinary RL, it accumulates a discounted return backward, ${\tilde{R}}_{i,t}={\sum }_{k=t}^T{\gamma }^{k-t}{\tilde{r}}_{i,k}$, and assigns it to the decision tokens produced at turn $t$; the tool's returned content itself is not updated.

IGPO's advantage is that it's cheap, dense, and ground-truth-aware, requiring neither an extra PRM nor Monte Carlo value estimation. Its drawback is that it depends on high-quality ground truth -- if a question actually has multiple valid answers but the dataset only recognizes one of them, IGPO may end up punishing a reasoning path that is factually correct but doesn't match the label.

AEM: Adaptive Entropy Modulation

AEM (Adaptive Entropy Modulation, 2026-05) takes another intrinsic route. It points out that sparse outcome-only reward gives limited guidance, but adding a PRM or a self-supervised signal increases supervision and tuning complexity, which can limit cross-task generalization.

AEM introduces no extra supervision at all; instead it dynamically adjusts the policy's entropy bonus -- increasing the entropy incentive when exploration is insufficient, and decreasing it when the policy starts to collapse. Specifically, it adaptively adjusts the entropy coefficient based on trajectory-level reward variance, avoiding both the "echo trap" common in work like ARPO/RAGEN (the model gets stuck looping through a self-generated reasoning template) and entropy collapse.

RefGRPO: The Reflection Gap and a Calibration Bonus

RefGRPO (Closing the Reflection Gap, 2026-06) uncovers a counterintuitive phenomenon: LLM agents tend to misjudge their own output after seeing environment feedback -- even for questions they had already answered correctly. The authors call this the "reflection gap," and point out that standard RL can barely fix it, due to a "credit-assignment mismatch."

RefGRPO's fix is simple: add a calibration bonus on top of GRPO -- extra reward is given when the model, after seeing environment feedback, still correctly evaluates its own output. This bonus is "free" (it needs no extra labeling), but it noticeably narrows the reflection gap and teaches the agent to actually use environment feedback rather than react to it mechanically.

The Step-Aligned Paradigm: Fixing the Granularity Mismatch

All three families above are working on "how to assign advantage more precisely." One more line of work attacks the problem at a more fundamental level: changing the basic unit of optimization.

StepPO (2026-04) points out that existing LLM RL algorithms inherit the token-centric paradigm from RLHF/RLVR -- the token is the basic unit of modeling and optimization. But in agentic RL, an LLM makes step-level decisions through a loop of "environment observation ↔ action," and there's a granularity mismatch between token-level optimization and step-level decision-making. StepPO proposes a paradigm centered on the step: each step is a complete decision unit, and the policy gradient is computed at step granularity rather than token granularity.

Turn-PPO (2025-12) arrives at a similar conclusion from a different angle. It finds that directly applying GRPO to multi-turn tasks -- especially long-horizon reasoning scenarios -- performs poorly, because GRPO's group-relative advantage has too much variance when estimated at the trajectory level. Turn-PPO switches to PPO and designs turn-level advantage estimation: each turn (not each token, and not the whole trajectory) has its own advantage, and that advantage is shared across the tokens within the turn.

AT²PO (2026-01) goes further and brings tree search into turn-level optimization. It targets three core challenges of multi-turn agentic RL -- insufficient exploration diversity, sparse credit assignment, and misaligned policy optimization -- with a unified turn-based-plus-tree-search framework. Tree search expands multiple hypothetical paths at critical turns and compares their eventual returns, giving that turn a more precise advantage.

The shared insight across this group of work: agentic RL shouldn't be forced into RLHF's token-centric framework. An agent's decisions are naturally step/turn granularity, and the optimization framework should respect that granularity.

Turn-Level Discounting: The Earlier the Mistake, the Bigger the Blame

No matter which credit-assignment method you use, multi-turn RL still has to handle a time-axis issue: errors in earlier steps carry more consequence. The intuition is straightforward -- if you head in the wrong direction at step 1, every subsequent step builds on that mistake; but a small error at step 6 can still be fixed at step 7.

To capture this intuition, researchers introduced turn-level discounting:

$$R=\sum _{t=1}^T{\gamma }^t\cdot r_t$$

Note that ${\gamma }^t$ here isn't discounting "the future" -- it assigns different weights to steps in "the past." In practice, the more common implementation is backward discounting: working backward from the final outcome, with earlier steps discounted more heavily.

def compute_turn_rewards(turn_rewards, gamma=0.9):
    """Compute discounted cumulative returns for multi-turn RL."""
    T = len(turn_rewards)
    returns = []
    G = 0
    # Accumulate backward from the last turn
    for t in reversed(range(T)):
        G = turn_rewards[t] + gamma * G
        returns.insert(0, G)
    return returns

# 7 turns of interaction, only the last turn has an immediate reward
# turn_rewards = [0, 0, 0, 0, 0, 0, 1.0]
# discount gamma = 0.9
# Returns: [0.531, 0.590, 0.656, 0.729, 0.810, 0.900, 1.000]
# Earlier steps get discounted more -> their "blame" for the final outcome is diluted

This implementation is exactly the same as the $G_t$ computation from Chapter 6's REINFORCE -- the only difference is that now each step is a whole "turn" (including text generation and tool calls), rather than a single token.

Comparing the Representative Frameworks

Framework	Signal source	Main contribution	Best suited for
ORM (RLVR)	Final outcome	Simple, cheap, verifiable	Short-horizon tasks (≤ 5 steps), objective answers
PRM (PRM800K)	Human-labeled per step	Dense signal, precise attribution	High labeling budget, complex reasoning
SALT	Trajectory graph structure	No extra labeling needed	GRPO framework, long-horizon tasks
GiGPO	Same-state group	State-anchored comparison	Enumerable states (WebShop)
HGPO	$k$-step context	Fixes historical inconsistency	Web navigation, context-sensitive tasks
Group-Graph PO	Trajectory DAG	Long-horizon + shared prefixes	Long-horizon tasks (10+ steps)
SPA-RL	Progress estimator	Reward redistribution	Any multi-step task
AgentPRM	MC return + soft BCE	PRM as Q(s,a)	Needs Best-of-N inference
ARPO	Entropy spike	Local branching sampling	Tool-call-heavy tasks
IGPO	Correct-answer log-prob	Information gain	Tasks with ground truth
AEM	Adaptive entropy	No extra supervision needed	General, collapse-prone settings
RefGRPO	Calibration bonus	Narrows the reflection gap	Tasks needing self-evaluation
StepPO	Step-centric	Granularity alignment	Any agentic RL
Turn-PPO	Turn-level PPO	Lower variance than GRPO	Long-horizon multi-turn tasks
AT²PO	Turn + tree search	Exploration + precise attribution	High-compute-budget long-horizon tasks

Practical Recommendations

Choose a strategy according to task complexity:

• 3-5 turn simple tasks: plain ORM/GRPO is enough -- episodes are short, so signal sparsity isn't a serious problem.
• 5-15 turn medium tasks: milestone-style reward shaping, or a method like SALT/GiGPO that doesn't need extra labeling.
• 15+ turn complex tasks: you need PRM or progress reward (SPA-RL/AgentPRM) plus MCTS exploration (AT²PO).
• Non-reproducible environment / high variance: AEM's adaptive entropy modulation, or a two-stage STO-RL approach (offline warm-up first, then online refinement).
• Needs Best-of-N inference: AgentPRM provides step-level Q values, and inference picks the action with the highest $Q$.
• Severe granularity mismatch: switch to a step-aligned paradigm (StepPO / Turn-PPO).

The key principle: first confirm whether the reward signal is dense enough to support learning, then decide which RL algorithm to use. If the reward is too sparse, no algorithm, however sophisticated, will learn well.

From Credit Assignment to Planning

Credit assignment answers "how well was each step done." A deeper question is: can the model produce a good multi-step plan before it acts? That's the core of planning ability.

The agents discussed so far have mostly been reactive -- deciding the next step based on the current observation. A truly capable agent needs look-ahead planning: simulating multiple paths before acting, evaluating their expected outcomes, and choosing the best one.

Planning ability can emerge from RL training. Experiments in work like DeepResearcher reveal that models spontaneously develop behaviors like pre-search planning (listing keywords up front), information layering (searching for an overview before going deep), and cross-validation -- none of which was explicitly encouraged by the reward. They're purely a side effect of RL optimization.

The practical takeaway: before investing in complex tree search and hierarchical RL, try simple GRPO + outcome reward first -- the model might learn to plan on its own. Only when simple methods fail to produce planning behavior do you need explicit tree-search training methods like TreeRL (ACL 2025) or PGTS (ICML 2025).

Mini Agent Loop -- Comparing ORM vs PRM Credit Assignment

In earlier chapters, RL training has all been "single-turn": the model generates a piece of text, the reward function assigns a score, and the policy gets updated. A real agent doesn't work this way -- it needs to search for information, execute code, and observe results across multiple turns before finally producing an answer. After 7 turns of interaction, you only get one "success/failure" signal. How do you distribute that signal across 7 steps?

This is the core challenge of Agentic RL: credit assignment. In this section we'll build a lightweight tool environment by hand, use Python to simulate a multi-turn agent interaction, and then compare two credit-assignment strategies -- ORM (look only at the final result) and PRM (evaluate every step) -- to see just how different they are.

Building a Mini Tool Environment

We'll build a simulated "research assistant" environment in pure Python. The agent can call three tools:

Tool	Function	Returns
search(query)	Simulates searching for information	Search result text
calculate(expr)	Executes a math calculation	Calculation result
verify(fact)	Verifies a fact	True / False

# ==========================================
# 1. Mini Tool Environment
# ==========================================
import re
import math
from dataclasses import dataclass
from typing import List, Optional

@dataclass
class ToolResult:
    """The return value of a tool call."""
    tool: str          # Tool name
    input: str         # Call input
    output: str        # Returned content
    success: bool      # Whether it succeeded

class MiniToolEnv:
    """A simulated lightweight tool environment."""

    # Preset "knowledge base" that the search tool looks things up in
    KNOWLEDGE = {
        "earth_radius": "6371",
        "pi": "3.14159265",
        "speed_of_light": "299792458",
        "gravity": "9.8",
        "moon_distance": "384400",
        "population_china": "1400000000",
        "python_release": "1991",
        "gpt_release": "2020",
        "transformer_paper": "2017",
    }

    def search(self, query: str) -> ToolResult:
        """Simulated search: look things up in the preset knowledge base."""
        query_lower = query.lower()
        for key, value in self.KNOWLEDGE.items():
            if key in query_lower or any(w in key for w in query_lower.split("_")):
                return ToolResult("search", query, f"Found: {key} = {value}", True)
        return ToolResult("search", query, f"No information found related to '{query}'", False)

    def calculate(self, expression: str) -> ToolResult:
        """Simulated calculator: safe evaluation of a math expression."""
        try:
            safe_expr = re.sub(r'[^0-9+\-*/().]', '', expression)
            result = eval(safe_expr)
            return ToolResult("calculate", expression, str(result), True)
        except:
            return ToolResult("calculate", expression, "Calculation error", False)

    def verify(self, fact: str) -> ToolResult:
        """Simulated fact-checking."""
        for key, value in self.KNOWLEDGE.items():
            if key in fact.lower() and value in fact:
                return ToolResult("verify", fact, "Correct", True)
        return ToolResult("verify", fact, "Cannot verify", False)

# Test the environment
env = MiniToolEnv()
print(env.search("earth_radius"))
print(env.calculate("2 * 3.14159 * 6371"))
print(env.verify("earth_radius is 6371"))

Defining a Multi-Turn Agent Loop

# ==========================================
# 2. Agent Turn and Episode Definitions
# ==========================================
@dataclass
class Turn:
    """One interaction turn."""
    action: str          # "search" | "calculate" | "verify" | "answer"
    input: str           # Tool input or final answer
    observation: str     # Environment return
    success: bool        # Whether the tool call succeeded

@dataclass
class Episode:
    """One complete agent interaction."""
    task: str
    ground_truth: str
    turns: List[Turn]

def run_agent_loop(env, task, action_plan, ground_truth):
    """Execute one agent interaction loop."""
    turns = []
    for step in action_plan:
        tool = step["tool"]
        inp = step["input"]

        if tool == "search":
            result = env.search(inp)
        elif tool == "calculate":
            result = env.calculate(inp)
        elif tool == "verify":
            result = env.verify(inp)
        elif tool == "answer":
            correct = inp.strip() == ground_truth.strip()
            turns.append(Turn("answer", inp,
                              "Correct!" if correct else "Wrong", correct))
            return Episode(task, ground_truth, turns)
        else:
            result = ToolResult(tool, inp, f"Unknown tool: {tool}", False)

        turns.append(Turn(tool, inp, result.output, result.success))

    return Episode(task, ground_truth, turns)

Designing a Multi-Step Task

Task: "What is the circumference of Earth's equator, in kilometers?" The correct path is search → calculate → verify → answer.

# The correct sequence of tool calls
good_plan = [
    {"tool": "search", "input": "earth_radius"},
    {"tool": "calculate", "input": "2 * 3.14159 * 6371"},
    {"tool": "verify", "input": "earth_radius is 6371"},
    {"tool": "answer", "input": "40030"},
]

# Step 2 has an error (pi was rounded to 3)
bad_plan = [
    {"tool": "search", "input": "earth_radius"},
    {"tool": "calculate", "input": "2 * 3 * 6371"},
    {"tool": "verify", "input": "earth_radius is 6371"},
    {"tool": "answer", "input": "38226"},
]

good_episode = run_agent_loop(env, task, good_plan, ground_truth)
bad_episode = run_agent_loop(env, task, bad_plan, ground_truth)

Notice the key feature of the bad plan: only step 2 made a mistake (rounding pi to 3), but steps 1 and 3 were actually both correct. The final result is wrong (step 4), but the root cause of the error is step 2.

Comparing ORM and PRM Credit Assignment

# ==========================================
# 4. ORM vs PRM Credit Assignment
# ==========================================
import numpy as np

def orm_credit(episode: Episode, gamma: float = 0.95) -> List[float]:
    """ORM: reward only comes from the final outcome; intermediate steps are all 0."""
    T = len(episode.turns)
    final_success = episode.turns[-1].success
    immediate = [0.0] * (T - 1) + [1.0 if final_success else 0.0]

    returns = np.zeros(T)
    G = 0
    for t in reversed(range(T)):
        G = immediate[t] + gamma * G
        returns[t] = G
    return returns.tolist()

def prm_credit(episode: Episode, gamma: float = 0.95) -> List[float]:
    """PRM: each step gets an immediate reward based on whether the tool call succeeded."""
    T = len(episode.turns)
    immediate = []
    for turn in episode.turns:
        if turn.action == "answer":
            immediate.append(1.0 if turn.success else -0.5)
        else:
            immediate.append(0.3 if turn.success else -0.3)

    returns = np.zeros(T)
    G = 0
    for t in reversed(range(T)):
        G = immediate[t] + gamma * G
        returns[t] = G
    return returns.tolist()

orm_bad = orm_credit(bad_episode)
prm_bad = prm_credit(bad_episode)

print(f"\n{'Turn':<6} {'Action':<12} {'Result':<8} {'ORM Credit':<14} {'PRM Credit':<14}")
for i, turn in enumerate(bad_episode.turns):
    status = "OK" if turn.success else "FAIL"
    print(f"Turn {i+1}   {turn.action:<12} {status:<8} {orm_bad[i]:<14.3f} {prm_bad[i]:<14.3f}")

Output:

Turn   Action        Result    ORM Credit     PRM Credit
Turn 1   search       OK        0.000          0.656
Turn 2   calculate    OK        0.000          0.376
Turn 3   verify       OK        0.000          0.170
Turn 4   answer       FAIL      0.000          -0.500

Under ORM, every step of the bad plan gets a credit of 0 -- including step 2 (calculate). This is because ORM only looks at whether the final answer is right (step 4, answer, is wrong → reward = 0), and this zero signal is then propagated backward through the discount. Since $0\times \gamma =0$, every step's credit is 0.

If you switch to "punish all steps on failure," a more serious problem shows up -- the correct search in step 1 also gets punished:

def orm_negative(episode, gamma=0.95):
    """ORM variant: on failure, every step gets punished."""
    T = len(episode.turns)
    final_success = episode.turns[-1].success
    immediate = [0.0] * (T - 1) + [1.0 if final_success else -1.0]
    returns = np.zeros(T)
    G = 0
    for t in reversed(range(T)):
        G = immediate[t] + gamma * G
        returns[t] = G
    return returns.tolist()

# Output: step 1's correct search gets a credit of -0.857 -- wrongly punished

Step 1's search was completely correct, yet it received a penalty of -0.857. This is the core problem with ORM: the signal is too coarse to distinguish "a step that was done right" from "a step that led to failure."

PRM's discrimination is 19 times that of ORM. ORM can barely distinguish correct steps from incorrect ones (discrimination of only 0.045), while PRM can clearly tell the model "which steps were done right and which were done wrong" (discrimination of 0.856). With the same number of training steps, PRM's task success rate ends up about 30 percentage points higher than ORM's.

Lab Summary

This lab used pure Python to simulate a multi-turn agent environment, letting you experience the core challenge of Agentic RL directly:

• ORM's signal is too sparse: on failure, every step's credit is close to 0, so the model doesn't know what to fix.
• ORM blames good steps: on failure, even correct search steps get punished.
• PRM attributes precisely: correct steps get positive scores, incorrect steps get negative scores, with 19x the discrimination of ORM.
• PRM's cost: every step needs to be evaluated -- in real scenarios this means labeling cost or training a PRM.

Core insight: the key difficulty in multi-turn agents isn't "which RL algorithm to use," but "how to assign reward to intermediate steps." ORM is simple but coarse; PRM is precise but expensive. All the fine-grained methods from 2025-2026 (GiGPO / SPA-RL / ARPO / IGPO / StepPO...) are, fundamentally, searching for a better compromise between ORM and PRM.

This lab is simulated

In a real scenario, an agent doesn't use a predefined action_plan; the model dynamically decides which tool to call at every step. The quality of the model's policy depends on the effect of RL training, and the effect of RL training depends on the quality of credit assignment -- this is a closed loop. This lab skips policy learning and focuses on understanding credit assignment itself.

Connection to Earlier Chapters

The credit-assignment problem in multi-turn RL follows directly from the policy gradient theorem in Chapter 6. REINFORCE uses Monte Carlo sampling to estimate $G_t$ -- the cumulative return from the current step to the end. Multi-turn RL does the same thing; the only change is that a "step" goes from being a single token to being a complete turn. Chapter 8's PPO reduces variance by introducing a value function (the critic) -- the same idea still applies in multi-turn RL, except now the critic needs to evaluate not "the value of the current token," but "the value of the current turn." Turn-PPO is the modern version of exactly this idea.

Planning ability is a more advanced form of multi-turn RL -- credit assignment answers "how well was each step done," while planning answers "which overall path is optimal." Together, the two form the decision-making core of Agentic RL.

The next section breaks down the engineering core of Agentic RL -- 22.4 Tool-Use RL -- looking at where training data comes from, how tool-use policies are learned, and how the system actually runs.

References